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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

四、 死鎖概述

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

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

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

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

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

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

---

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

---

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