第三章（上）處理機調(diào)度與死鎖知識梳理

一、 處理機調(diào)度的基本概念與層次

處理機調(diào)度是操作系統(tǒng)的核心功能之一，其核心目標(biāo)是在多道程序環(huán)境下，合理地分配和回收處理機資源，以提高系統(tǒng)效率和資源利用率，滿足不同用戶和任務(wù)的需求。

1. 調(diào)度的三個層次：

• 高級調(diào)度（作業(yè)調(diào)度）：
• 對象： 作業(yè)（Job）。

• 功能： 決定將外存上處于后備隊列的哪些作業(yè)調(diào)入內(nèi)存，為其創(chuàng)建進(jìn)程、分配必要的資源，并放入就緒隊列。

• 發(fā)生頻率： 低，通常幾分鐘一次。

• 中級調(diào)度（內(nèi)存調(diào)度）：
• 對象： 進(jìn)程。

• 功能： 將暫時不能運行的進(jìn)程（如因等待I/O）調(diào)至外存等待（掛起狀態(tài)），當(dāng)內(nèi)存有富余或進(jìn)程具備運行條件時，再重新調(diào)入內(nèi)存。目的是提高內(nèi)存利用率和系統(tǒng)吞吐量。

• 發(fā)生頻率： 中等。

• 低級調(diào)度（進(jìn)程調(diào)度）：
• 對象： 進(jìn)程（或內(nèi)核級線程）。

• 功能： 按照某種算法，從就緒隊列中選取一個進(jìn)程，將處理機分配給它。這是操作系統(tǒng)中最基本、最頻繁的調(diào)度。

• 發(fā)生頻率： 很高，幾十毫秒一次。

二、 進(jìn)程調(diào)度

1. 進(jìn)程調(diào)度的任務(wù)與機制：
任務(wù)： 保存當(dāng)前進(jìn)程的現(xiàn)場信息，按算法選擇新進(jìn)程，恢復(fù)新進(jìn)程的現(xiàn)場并使其運行。
機制： 包括排隊器（組織就緒隊列）、分派器（切換上下文）、上下文切換器。

2. 調(diào)度方式：
非搶占式（非剝奪式）： 一旦把處理機分配給某進(jìn)程，該進(jìn)程會一直運行直至完成或發(fā)生阻塞事件主動讓出。實現(xiàn)簡單，但無法處理緊急任務(wù)。
搶占式（剝奪式）： 允許調(diào)度程序根據(jù)某種原則（如優(yōu)先級、時間片）暫停正在執(zhí)行的進(jìn)程，將處理機分配給更重要的進(jìn)程。能提供更好的響應(yīng)性和公平性，是現(xiàn)代系統(tǒng)的主流方式。

3. 進(jìn)程切換與上下文切換：
進(jìn)程切換必然發(fā)生上下文切換，但上下文切換不一定是由進(jìn)程切換引起（也可能是同一進(jìn)程內(nèi)的線程切換）。

三、 調(diào)度算法（本章重點）

調(diào)度算法的評價指標(biāo)：CPU利用率、系統(tǒng)吞吐量、周轉(zhuǎn)時間、等待時間、響應(yīng)時間。

1. 先來先服務(wù)（FCFS）：
規(guī)則： 按作業(yè)/進(jìn)程到達(dá)的先后順序進(jìn)行服務(wù)。
特點： 算法簡單，公平。但不利于短作業(yè)，平均等待時間較長。

2. 短作業(yè)優(yōu)先（SJF）/短進(jìn)程優(yōu)先（SPF）：
規(guī)則： 對預(yù)計運行時間最短的作業(yè)/進(jìn)程優(yōu)先服務(wù)。
特點： 能獲得最小的平均等待/周轉(zhuǎn)時間。但可能導(dǎo)致長作業(yè)“饑餓”，且運行時間難以準(zhǔn)確預(yù)估。

3. 高響應(yīng)比優(yōu)先（HRRN）：
規(guī)則： 在每次調(diào)度時，計算每個就緒作業(yè)的響應(yīng)比 R = (等待時間 + 要求服務(wù)時間) / 要求服務(wù)時間，選擇R最高的作業(yè)。
特點： 是FCFS和SJF的折中，既考慮了等待時間（防止饑餓），又考慮了運行時間。

4. 時間片輪轉(zhuǎn)（RR）：
規(guī)則： 將所有就緒進(jìn)程按FCFS原則排成一個隊列，每次調(diào)度將CPU分配給隊首進(jìn)程，但僅執(zhí)行一個時間片。時間片用完后，由計時器發(fā)出時鐘中斷，調(diào)度程序?qū)⒃撨M(jìn)程送到就緒隊列末尾，并讓新的隊首進(jìn)程執(zhí)行。
特點： 專為分時系統(tǒng)設(shè)計，公平、響應(yīng)快。時間片大小是關(guān)鍵：太大退化為FCFS；太小則上下文切換開銷過大。

5. 優(yōu)先級調(diào)度算法（PSA）：
規(guī)則： 為每個進(jìn)程賦予一個優(yōu)先級，調(diào)度時選擇優(yōu)先級最高的進(jìn)程。優(yōu)先級可以靜態(tài)設(shè)定或動態(tài)調(diào)整（如根據(jù)等待時間增長而提高）。
特點： 可用于實時系統(tǒng)。可能導(dǎo)致低優(yōu)先級進(jìn)程饑餓。

6. 多級隊列調(diào)度算法（MQ）：
* 規(guī)則： 將就緒隊列劃分為多個獨立隊列，每個隊列有自己的調(diào)度算法（如系統(tǒng)進(jìn)程隊列用RR，交互進(jìn)程隊列用FCFS）。隊列之間通常采用固定優(yōu)先級或時間片劃分的方式進(jìn)行調(diào)度。

7. 多級反饋隊列調(diào)度算法（MFQ）：
規(guī)則： 是MQ與時間片輪轉(zhuǎn)的結(jié)合與進(jìn)化。設(shè)置多個優(yōu)先級不同的隊列，新進(jìn)程進(jìn)入最高優(yōu)先級隊列。每個隊列的時間片大小不同，優(yōu)先級越高的隊列時間片越小。進(jìn)程在當(dāng)前隊列的一個時間片內(nèi)未完成，則被降級到下一級隊列。只有高優(yōu)先級隊列為空時，才調(diào)度低優(yōu)先級隊列的進(jìn)程。
特點： 是公認(rèn)的綜合性較好的一種調(diào)度算法，能較好地滿足各種類型用戶的需求：短作業(yè)優(yōu)先完成、長作業(yè)不會長期得不到服務(wù)、I/O密集型進(jìn)程能獲得較高響應(yīng)優(yōu)先級。

四、 死鎖概述

1. 死鎖的定義：
在多道程序系統(tǒng)中，由于競爭資源或進(jìn)程間通信不當(dāng)，導(dǎo)致一組進(jìn)程中的每一個進(jìn)程都在無限期地等待被該組中另一個進(jìn)程所占有的資源，從而導(dǎo)致所有進(jìn)程都無法向前推進(jìn)的現(xiàn)象。

2. 產(chǎn)生死鎖的必要條件（四個，必須同時成立）：
互斥條件： 資源在一段時間內(nèi)只能被一個進(jìn)程使用。
請求和保持條件（占有并等待）： 進(jìn)程在持有至少一個資源的又請求新的資源，而該資源被其他進(jìn)程占有，此時請求進(jìn)程被阻塞，但對自己已獲得的資源保持不放。
不可剝奪條件（非搶占）： 進(jìn)程已獲得的資源在未使用完之前，不能被其他進(jìn)程強行奪走，只能由該進(jìn)程主動釋放。
循環(huán)等待條件： 存在一個進(jìn)程-資源的環(huán)形等待鏈。

3. 處理死鎖的基本方法：
預(yù)防死鎖： 破壞死鎖四個必要條件中的一個或多個（靜態(tài)策略）。
破壞“請求和保持”：一次性申請所有資源（資源預(yù)分配）。

• 破壞“不可剝奪”：允許剝奪資源。

• 破壞“循環(huán)等待”：對資源類型進(jìn)行線性排序，要求進(jìn)程按序申請。

• 避免死鎖： 在資源動態(tài)分配過程中，用某種方法（如銀行家算法）防止系統(tǒng)進(jìn)入不安全狀態(tài)（動態(tài)策略）。
• 檢測與解除死鎖： 允許死鎖發(fā)生，通過檢測機構(gòu)及時發(fā)現(xiàn)，并采取撤銷進(jìn)程或剝奪資源等措施解除死鎖。
• 忽略死鎖： 如大多數(shù)操作系統(tǒng)對死鎖問題采取不理睬的策略，因為死鎖并非頻繁發(fā)生，且預(yù)防和避免的代價較高。

---

本章（下）預(yù)告： 將深入講解銀行家算法的原理與示例、死鎖的檢測與解除的具體方法，并結(jié)合實例進(jìn)行綜合分析。

---

腦圖關(guān)鍵詞索引：
調(diào)度層次（高/中/低） -> 進(jìn)程調(diào)度（任務(wù)/方式/切換） -> 調(diào)度算法（FCFS, SJF, HRRN, RR, PSA, MQ, MFQ） -> 死鎖（定義，四必要條件，處理策略：預(yù)防/避免/檢測解除/忽略）。