Ch7 常見的 CPU Scheduling

在第六章，我們講解完 CPU virtualization 的基本機制了。在第七章，我們將要講解 CPU virtualization 的政策。因為我們有許多 process 要處理，但我們只有一個 CPU，如何制定 process 的執行方式是門學問，這也是本章的重點。

7-1 四大假設

在說明以下的各種排程策略前，我們必須介紹四大假設：

• 同時到達
• 不會中途停止
• 只使用CPU（無I/O）
• 執行時間已知 -> 很難成立

7-2 Scheduling Metrics

介紹如何衡量排程策略好壞的指標

• Execution time（E）：process 被執行的時間
• Response time（R）：process 從等待到開始執行的時間
• Turnaround time（T）：
  • process 從等待到執行結束的時間
  • T = R + E
    

7-3 FIFO

• First in, first out
• 通常會用 queue 來儲存要執行的 process
  
• 問題：當前面有一個 execution time 很長的 process，後面的程式 responce time 就會被拖很長，效率低下
  

7-4 SJF

• Shortest Job First
• 根據 turnaround time 來做排序，最短的先執行
• 最小化平均 turnaround time
  
• 問題：無法處理後來才到的短任務

7-5 STCF（Shortest Time to Config First）

• 賦予後到的程式有插隊（preemptive） 的能力
• 當新任務加入時會中斷當前執行的任務
• 比較 當前任務剩餘的 execution time 與 新任務的 execution time -> 選比較短的先執行
  
• 問題：Turnaround time 較長的工作會一直被插隊，無法被執行

7-7 RR(Round-robin)

犧牲 Turnaround time 來優化 Response Tine

• 把不同大小的 process 切成相同大小的區塊
• 輪流執行
  
• 問題：多次 context switch 可能會有額外的時間成本