# OS筆記-Chapter 5: CPU Scheduling

###### tags: `OS`
---
#### 目錄
* 總論
[Chapter 1: Introduction](https://hackmd.io/NoZq3J7IQvOQpcbo_tctjA)
[Chapter 2: Operating-System Structures](https://hackmd.io/OKykRLBESI6v9a13HgS35A)
* 行程管理
[Chapter 3: Processes](https://hackmd.io/HOqN-iQ3RIKIC-NB9QjBIQ)
[Chapter 4: Threads](https://hackmd.io/qzAIHeSASmKuecdkqidmHw)
<font color="red">Chapter 5: CPU Scheduling</font>
[Chapter 6: Process Synchronization](https://hackmd.io/rv-PNe3ESxi08PElyUTc4Q)
[Chapter 7: Deadlocks](https://hackmd.io/Uu0jDK-rSyKNKq690y146g)
* 記憶體管理
[Chapter 8: Main Memory](https://hackmd.io/4KS_yPkBQzGZfHDisPciog)
[Chapter 9: Virtual Memory](https://hackmd.io/yirxZFn8Rz2wT56AAR7Sxw)
* 儲存裝置
[Chapter 10: File-System Interface](https://hackmd.io/aNPWKsFhTlGc-WFgQ__KRg)
[Chapter 11: File System Implementation](https://hackmd.io/bFcrlmefQsGp6hZdbI1MHQ)
[Chapter 12: Mass-Storage Systems](https://hackmd.io/9Y7Qo0OERda6htK7OOI36Q)
[Chapter 13: I/O Systems](https://hackmd.io/VNwXrhJPSo-l_t9tUBhYIg)
* 保護和安全
[Chapter 14: Protection](https://hackmd.io/izkd4JwXRwub_ZmhSMTlNw)
[Chapter 15: Security](https://hackmd.io/ofyvDidvQf-PxLMMZYhtsg)
---

### 基本觀念
* 在單一處理器系統裡，同一時間只能有一個行程在執行，多元程式規劃(multiprogramming)的目的就是隨時保有一個行程在執行

* 行程是由CPU執行時間及I/O等待時間所組成的週期(cycle)
* CPU分割(CPU burst)
* I/O分割(I/O burst)

* CPU分割統計，一般都為指數或超指數型，這個分布方式對於選取一個適當的CPU排班演算法來說是一項非常重要的資料

* 短程排班程式/CPU排班程式(short-term scheduler):自記憶體中準備要執行的行程中選出一個，將CPU配置給它

* CPU排班的決策發生在下面四種狀況
1. 當一行程從執行狀態轉變成等待狀態時(I/O要求或wait())
2. 當一行程從執行狀態轉變成就緒狀態時(interrupt)
3. 當一行程從等待狀態轉變成就緒狀態時(I/O結束)
4. 當一行程終止時

* 上述四種狀況為不可搶先(nonpreemptive)/合作(cooperative)
* 一旦CPU配置給一個行程，此行程將保有CPU，直到中止或轉換到等待狀態

* 可搶先排班(preemptive)
* 在存取共用資料時可能造成競爭情況(race condition)，搶先的行程與原行程的資料不一致
* 當核心在處理系統呼叫時很可能要修改一些重要的資料結構，如果這個時候搶先的行程修改了相同的核心資料結構，這樣很可能造成系統當機。
* 一般來說，作業系統需要能夠隨時接收中斷，但為了解決上述問題，當系統進入系統呼叫後，就將系統中斷關閉，結束系統呼叫時，再將中斷開啟，以確保核心資料結構的一致性

* 分派程式(dispatcher)
* 將CPU控制權交給短程排班程式所選出的行程的模組
* 轉換內容
* 轉換成使用者模式
* 跳躍到使用者程式的適當位置以便重新開始程式
* 分派潛伏期(Dispatch latency):分派程式用來停止一個行程並開始另一個行程所用的時間

### 排班原則(Scheduling Criteria)
* CPU使用率(CPU utilization):使CPU盡可能的忙碌

* 產量(Throughput):單位時間內所完成的數量

* 回復時間(Turnaround time):行程完成所花費的時間，包括:進入等待記憶體、就緒佇列等待、CPU執行、I/O等等

* 等候時間(waiting time):在就緒佇列等待的時間

* 反應時間(response time):提出一個要求到第一個反應的時間

* 最佳化
* Max CPU utilization
* Max throughput
* Min turnaround time
* Min waiting time
* Min response time

### 排班演算法(Scheduling Algorithm)
* 先來先做(FCFS,First-Come First-Served):
* 使用先進先出佇列(FIFO,First-in First-Out)
* 平均等待時間長
* P1先，平均等待時間:(0+24+27)/3=17
* P1最後，平均等待時間:(3+6)/3=3
* 護送現象(convoy effect):所有行程都在等一個大行程離開CPU，造成CPU和裝置使用率降低
* 不可搶先

* 最短工作先做(SJF,Shortest-Job-First)
* 可以得到一組行程的最小平均等待時間(3+9+16)/4=7
* 難以得知下一個CPU要求的長度(難以找到最短的)
* 預測下一個CPU要求的長度
* 下個CPU分割的預估通常是根據前幾次CPU分割所測得的值之指數平均值(exponential average)
* τ₀=10、α=1/2
* 可搶先或不可搶先
* 可搶先稱為生於時間最短的先做(shortest-remaining-time-first)

* 優先權排班(Priority Scheduling)
* 可搶先或不可搶先
* 無限期阻塞/飢餓(indefinite blocking/starvation):優先權低的行程一直等待CPU
* 老化(aging):一段時間，調高等待行程的優先權

* 依序循環(RR,Round Robin)
* 為了分時系統所設計
* 可搶先，行程交互使用CPU
* 時間量/時間片段(time quantum/time slice):定義一個小的時間單位
* 平均等待時間較長
* 除非只有一個行程，不然不會有一個行程分配CPU的時間超過時間量
* 時間量:q=4，(10-4)+(4)+(7)/3=5.66
* 時間量極大時，等同於FCFS。時間量極小時，造成內容轉換的負擔
* 通常CPU分割的80%應該小於時間量
* 回復時間不因時間量增加有所改進

* 多層佇列(Multilevel Queue)
* 分成多層佇列，每層佇列分別使用自己的排班法則
* 每層之間不能轉移
* 分層之間:
* 除非前面都空了，後面才能分配CPU
* 或分配80%的CPU時間給前面的佇列，20%給後面

* 多層回饋佇列(Multilevel Feedback Queue)
* 允許行程在分層之間移動
* 第一層執行不完的就放到第二層，第二層執行不完的就放到第三層
* 較長的行程會自動放到較底層
* 隨著時間，較底層的，也會漸漸地移往高優先序，以免飢餓
* 最通用的CPU排班演算法
* 最複雜的CPU排班演算法

### 演算法評估(Algorithm Evaluation)
* 分析式評估(analytic evaluation):使用所給予演算法和系統工作量產生一個公式或數字，以此評估性能

* 定量模式(deterministic modeling):一種分析式評估，取一個特定的工作量，並針對每種演算法評估效能
* 例如:
* FCFS:(10+39+42+49)/5=28
* SJF:(3+10+20+32)/5=13
* RR:((10+20+2)+(20)+(23)+(30+10))/5=23

* 佇列模式(Queueing Models)
* 定出CPU和I/O分割的分布情況
* 指數型分布
* 可計算出平均產量、利用率、等待時間等等
* Little’s Formula:n=λxW
* 平均佇列長度n
* 新行程平均到達比率λ
* 平均等待時間W

* 模擬(Simulations)
* 更準確的評估

* 實做(Implementation)
* 即使是模擬精確度也有限
* 將程式碼直接放入系統評估工作情形
* 困難:
* 代價高(撰寫程式碼等等)
* 環境不一樣