---
# System prepended metadata

title: 第10章 Operating System
tags: [Introduction of computer science]

---

# OS主要作業
* **Memory** and **Input/Output device** management
* allows program interact system resource
* provide human interact with **Interface**
 
# 多工處理(MultiProgramming)
* Memory Management：管理電腦記憶體資源的分配和使用的技術。
* Process Management：管理電腦中執行的程式。
* CPU Management：管理電腦的中央處理器。
將多個程式同時放在記憶體中，**輪流使用CPU**。
早期的作業系統是**人工操作員**執行批次處理，回傳各個請求。

* **Timesharing** 透過[多工處理](https://zh.wikipedia.org/zh-tw/%E5%88%86%E6%99%82%E7%B3%BB%E7%B5%B1#:~:text=%E5%A4%9A%E5%B7%A5%E8%99%95%E7%90%86%E4%BD%BF%E5%A4%9A%E5%80%8B%E4%BD%BF%E7%94%A8%E8%80%85%E5%8F%AF%E4%BB%A5%E5%90%8C%E6%99%82%E4%BD%BF%E7%94%A8%E4%B8%80%E5%8F%B0%E9%9B%BB%E8%85%A6)，使多個使用者可以同時使用一台電腦。


* **實時作業系統**
為保證最小反應時間的應用而設計(例如:機器人控制、核反應爐監控)。
保證在**短時間完成任務**，而**不是高吞吐量**。
* **裝置驅動程式 Device Driver**
**提供與特定裝置連接的介面**
這種程式建立了一個硬體與硬體，或硬體與軟體溝通的介面
經由主機板上的匯流排bus 或其它溝通子系統subsystem 與硬體形成連接的機制，
這樣的機制使得硬體裝置device 上的資料交換成為可能。

# 記憶體管理

## 單連續記憶體管理 Single contiguous memory management
必須分配一塊**連續**的記憶體給程式，可能導致兩種碎片化
**外部碎片 external fragmentation**
即使整個記憶體夠大，但"不連續"而無法滿足較大的記憶體需求
**內部碎片 internal fragmentation**
大小固定的區間，配置的記憶體可能比實際需要多，導致浪費

## **分區記憶體管理** Partition memory management
* **固定分區 Fixed Partitioning**
記憶體被劃分為固定大小，每個區域**只能分配給一個程式**
    - 首次適配：選擇第一個足夠大的分區來滿足需求。
    - 最佳適配：從所有足夠大的分區中選擇最小的一個。
    - 最差適配：從所有足夠大的分區中選擇最大的一個。
    
* **動態分區 Dynamic Partitioning**
在固定分區的基礎上，將該區域分割為兩個部分
一個用於新工作，另一個**可用於下一新工作**

## 分頁記憶體管理 Paged memory management: 
### **按需調頁(Demand Paging)** 
**程序需要時，才將程式從虛擬記憶體(磁碟)swap到物理記憶體。**

當程式訪問到一個還沒有在記憶體中的頁面時(會產生一個頁面缺失)，
作業系統會將該頁面從磁碟讀入到記憶體中，接著恢復程式的執行。
這樣，程式可以像擁有連續的記憶體空間一樣運行，即使記憶體是分散的。

* 實體記憶體被分為許多大小相同的欄(frame)(頁框)
    - 虛擬記憶體則被分為大小相同的頁(page)

* 過度的頁面交換Page Swapping會造成抖動Thrashing。

### 虛擬記憶體 vitual memory
**由磁碟空間及記憶體混合而成，使程式以為有大塊連續記憶體能使用**

例題：
![image](https://hackmd.io/_uploads/H1eof1jdp.png)
```
如果框架大小為1024，邏輯地址<2, 85>所對應的物理地址是多少？ <第幾頁框，位置>
解:  1024 * 7 + 85 = 7253#

如果框架大小為1024，邏輯地址<3, 555>所對應的物理地址是多少？
解: 1024 * 3 + 555 = 3627
```

# Logical and Physical Address
* **邏輯位址** 由程序的角度看到的記憶體位址，通常叫做虛擬位址(virtual address)
* **物理位址** 在記憶體中的實際位置

* **位址綁定** 將邏輯位址轉換為實體位址的過程。
# 處理器調度

* **周轉時間** 
進程從進入就緒狀態到最後一次退出運行狀態所花費的時間。

![image](https://hackmd.io/_uploads/S1CjsrYDp.png)
* ## 先來先服務 First come, First Served 非搶佔式
進程按其到達就緒狀態的順序被調度。一旦進程被調度到運行狀態，它就會保持直到完成。![image](https://hackmd.io/_uploads/BklwGdqwT.png)

* ## 最短作業優先 Short Job Next 通常非搶佔式
處理器調度算法查看所有處於就緒狀態的進程，並**調度具有最短估計服務時間**的進程![image](https://hackmd.io/_uploads/S1hPGu9v6.png)

* ## 輪詢 Round-Robin 搶佔式
將處理器時間**平均分配給**所有處於就緒狀態的進程，直到所有進程都完成。
一種**公平**的調度算法，因為它確保所有進程都有機會使用CPU。
![image](https://hackmd.io/_uploads/BygmYz_qvT.png)

舉例：
每個進程都獲得50個時間單位的 CPU 時間。進程 2 最初需要 75 個時間單位，但它只獲得50個時間單位。因此，它在其下一個時間片開始時仍有 25 個時間單位需要完成。

# Process control block (PCB)
一個資料結構，CPU用來管理process的資訊

* 當一個進程**首次被創建時**，
創建一個新的PCB**直到進程終止**

* 管理每個行程的信息，包括程式計數器、暫存器值、排程資訊、記憶體管理資訊和會計資訊。


![image](https://hackmd.io/_uploads/SJvRXudOa.png)
new > ready > running > waiting > terminate

# Top-Down design
1. 定義問題：明確問題的目標和需求。
2. 分解問題：將問題分解成更小的問題。
3. 解決子問題：對每個子問題進行 Top-Down design。
4. 整合子解決方案：將子解決方案整合成完整的解決方案。