操作系統精髓與設計原理讀書筆記4

處理器調度（CPU調度）

CPU調度

—— 其任務是控制、協調進程對CPU的競爭

即按一定的調度演算法從就緒隊列中選擇一個進程，把CPU的使用權交給被選中的進程

如果沒有就緒進程，系統會安排一個系統空閑進程或idle進程

系統場景

N個進程就緒、等待上CPU運行

M個CPU，M ≥ 1

需要決策：給哪一個進程分配哪一個CPU？

WHAT：按什麼原則選擇下一個要執行的進程

— 調度演算法

WHEN：何時選擇

— 調度時機

進程正常終止 或 由於某種錯誤而終止

新進程創建 或 一個等待進程變成就緒

當一個進程從運行態進入阻塞態

當一個進程從運行態變為就緒態

HOW： 如何讓被選中的進程上CPU運行

— 調度過程（進程的上下文切換）

進程切換：是指一個進程讓出處理器，由另一個進程佔用處理器的過程

進程切換主要包括兩部分工作：

切換全局頁目錄以載入一個新的地址空間

切換內核棧和硬體上下文，其中硬體上下文包括了內核執行新進程需要的全部信息，如CPU相關寄存器

切換過程包括了對原來運行進程各種狀態的保存和對新的進程各種狀態的恢復

場景：進程A下CPU，進程B上CPU

保存進程A的上下文環境（程序計數器、程序狀態字、其他寄存器……）

用新狀態和其他相關信息更新進程A的PCB

把進程A移至合適的隊列（就緒、阻塞……）

將進程B的狀態設置為運行態

從進程B的PCB中恢復上下文（程序計數器 、程序狀態字、其他寄存器……）

調度演算法設計

吞吐量 Throughput — 每單位時間完成的進程數目

周轉時間TT(Turnaround Time) 每個進程從提出請求到運行完成的時間

響應時間RT(Response Time) 從提出請求到第一次回應的時間

CPU 利用率(CPU Utilization) CPU做有效工作的時間比例

等待時間(Waiting time) 每個進程在就緒隊列(ready queue)中等待的時間

靜態優先順序：

進程創建時指定，運行過程中不再改變

動態優先順序：

進程創建時指定了一個優先順序，運行過程中可以動態變化

如：等待時間較長的進程可提升其優先順序

可搶佔式Preemptive（可剝奪式）

當有比正在運行的進程優先順序更高的進程就緒時，系統可強行剝奪正在運行進程的CPU，提供給具有更高優先順序的進程使用

不可搶佔式Non-preemptive（不可剝奪式 ）

某一進程被調度運行後，除非由於它自身的原因不能運行，否則一直運行下去

先來先服務（FCFS-First Come First Serve）

先進先出 First In First Out (FIFO)，按照進程就緒的先後順序使用CPU，非搶佔

優缺點，公平，實現簡單，長進程後面的短進程需要等很長時間，不利於用戶體驗

最短作業優先（SJF-Shortest Job First）

具有最短完成時間的進程優先執行，非搶佔式，最短剩餘時間優先

Shortest Remaining Time Next(SRTN)

SJF搶佔式版本，即當一個新就緒的進程比當前運行進程具有更短的完成時間時，系統搶佔當前進程，選擇新就緒的進程執行

思路：先完成短的作業

改善短作業的周轉時間

優缺點

最短的平均周轉時間，不公平，源源不斷的短任務到來，可能使長的任務長時間得不到運行 → 產生 「飢餓」現象 (starvation)

最短剩餘時間優先（SRTN-Shortest Remaining Time Next）

最高相應比優先（HRRN-Highest Response Ratio Next）

是一個綜合的演算法

調度時，首先計算每個進程的響應比R；之後，總是選擇 R 最高的進程執行

響應比R = 周轉時間 / 處理時間 =（處理時間 + 等待時間）/ 處理時間 = 1 +（等待時間 / 處理時間）

互動式系統中

輪轉調度（RR-Round Robin）

為短任務改善平均響應時間

解決問題的思路

周期性切換

每個進程分配一個時間片

時鐘中斷 → 輪換

最高優先順序調度（HPF—Highest Priority First）

多級反饋隊列（Multiple feedback queue）

最短進程優先（Shortest Process Next）

推薦閱讀：