操作系統(tǒng)第4章

1、第四章第四章 調(diào)度與死鎖調(diào)度與死鎖4.1 調(diào)度的類型與模型調(diào)度的類型與模型4.2 調(diào)度算法調(diào)度算法4.3 實(shí)時系統(tǒng)中的調(diào)度實(shí)時系統(tǒng)中的調(diào)度4.6 死鎖的基本概念死鎖的基本概念4.7 死鎖的預(yù)防和避免死鎖的預(yù)防和避免4.8 死鎖的檢測和解除死鎖的檢測和解除4.1 調(diào)度的類型和模型調(diào)度的類型和模型一、調(diào)度類型一、調(diào)度類型二、調(diào)度模型二、調(diào)度模型 4.1 4.1 調(diào)度類型和模型調(diào)度類型和模型一、調(diào)度類型一、調(diào)度類型 1. 高級調(diào)度（也稱作業(yè)調(diào)度、長程調(diào)度）高級調(diào)度（也稱作業(yè)調(diào)度、長程調(diào)度）作用：作用：選擇外存上處于后備隊列中的一個或幾個作業(yè)調(diào)入內(nèi)存，選擇外存上處于后備隊列中的一個或幾個作業(yè)調(diào)入內(nèi)存，

2、 并為它們創(chuàng)建進(jìn)程，分配必要的資源，然后，再將新創(chuàng)建并為它們創(chuàng)建進(jìn)程，分配必要的資源，然后，再將新創(chuàng)建 的進(jìn)程排在就緒隊列，準(zhǔn)備執(zhí)行。的進(jìn)程排在就緒隊列，準(zhǔn)備執(zhí)行。使用系統(tǒng)：使用系統(tǒng)：批處理系統(tǒng)（分時系統(tǒng)和實(shí)時系統(tǒng)不需要）。批處理系統(tǒng)（分時系統(tǒng)和實(shí)時系統(tǒng)不需要）。作業(yè)調(diào)度時要決定：作業(yè)調(diào)度時要決定： 1. 一次選擇多少個作業(yè)：取決于多道程序度和資源使用情況。一次選擇多少個作業(yè)：取決于多道程序度和資源使用情況。 2. 選擇哪些作業(yè)：取決于作業(yè)調(diào)度算法和資源使用情況。選擇哪些作業(yè)：取決于作業(yè)調(diào)度算法和資源使用情況。何時執(zhí)行作業(yè)調(diào)度功能：何時執(zhí)行作業(yè)調(diào)度功能： 1. 有作業(yè)退出系統(tǒng)時；有作業(yè)退出系統(tǒng)

3、時； 2. 系統(tǒng)負(fù)荷不足時。系統(tǒng)負(fù)荷不足時。執(zhí)行頻率：執(zhí)行頻率：幾分鐘或幾秒種一次。幾分鐘或幾秒種一次。 4.1 4.1 調(diào)度類型和模型調(diào)度類型和模型一、調(diào)度類型一、調(diào)度類型 2. 低級調(diào)度（也稱進(jìn)程調(diào)度、短程調(diào)度）低級調(diào)度（也稱進(jìn)程調(diào)度、短程調(diào)度）作用：作用：從就緒隊列中選擇一個進(jìn)程，然后，由分派程序?qū)⑻幚頇C(jī)從就緒隊列中選擇一個進(jìn)程，然后，由分派程序?qū)⑻幚頇C(jī) 分配給該進(jìn)程。分配給該進(jìn)程。使用系統(tǒng)：使用系統(tǒng)：各種系統(tǒng)均需要。各種系統(tǒng)均需要。進(jìn)程調(diào)度時只決定：進(jìn)程調(diào)度時只決定： 選擇哪個就緒進(jìn)程：取決于進(jìn)程調(diào)度算法。選擇哪個就緒進(jìn)程：取決于進(jìn)程調(diào)度算法。執(zhí)行頻率：執(zhí)行頻率：幾十毫秒一次。幾十毫秒

4、一次。 4.1 4.1 調(diào)度類型和模型調(diào)度類型和模型一、調(diào)度類型一、調(diào)度類型何時執(zhí)行進(jìn)程調(diào)度功能：何時執(zhí)行進(jìn)程調(diào)度功能： 出現(xiàn)下列四種情況時，進(jìn)程調(diào)度功能被執(zhí)行：出現(xiàn)下列四種情況時，進(jìn)程調(diào)度功能被執(zhí)行： 1. 當(dāng)進(jìn)程從執(zhí)行態(tài)轉(zhuǎn)換到阻塞態(tài)時（例如提出當(dāng)進(jìn)程從執(zhí)行態(tài)轉(zhuǎn)換到阻塞態(tài)時（例如提出I/O請求或等待子請求或等待子 進(jìn)程結(jié)束）。進(jìn)程結(jié)束）。 2. 當(dāng)進(jìn)程從執(zhí)行態(tài)轉(zhuǎn)換到就緒態(tài)時（例如發(fā)生時鐘中斷）。當(dāng)進(jìn)程從執(zhí)行態(tài)轉(zhuǎn)換到就緒態(tài)時（例如發(fā)生時鐘中斷）。 3. 當(dāng)進(jìn)程從阻塞態(tài)轉(zhuǎn)換到就緒態(tài)時（例如當(dāng)進(jìn)程從阻塞態(tài)轉(zhuǎn)換到就緒態(tài)時（例如I/O操作結(jié)束）。操作結(jié)束）。 4. 當(dāng)一個進(jìn)程終止時當(dāng)一個進(jìn)程終止時。

5、4.1 4.1 調(diào)度類型和模型調(diào)度類型和模型一、調(diào)度類型一、調(diào)度類型進(jìn)程調(diào)度方式：進(jìn)程調(diào)度方式： 1.非搶占方式非搶占方式(nonpreemptive)： 一旦把處理機(jī)分配給某個進(jìn)程，便讓該進(jìn)程一直執(zhí)行，直至一旦把處理機(jī)分配給某個進(jìn)程，便讓該進(jìn)程一直執(zhí)行，直至 該進(jìn)程完成或發(fā)生某事件而阻塞時，才把處理機(jī)分配給其它該進(jìn)程完成或發(fā)生某事件而阻塞時，才把處理機(jī)分配給其它 進(jìn)程。（即僅在情況進(jìn)程。（即僅在情況1和和4下，才進(jìn)行進(jìn)程調(diào)度）下，才進(jìn)行進(jìn)程調(diào)度） 2.搶占方式搶占方式(preemptive)： 允許調(diào)度程序根據(jù)某種原則，去停止某個正在執(zhí)行的進(jìn)程，允許調(diào)度程序根據(jù)某種原則，去停止某個正在執(zhí)行的

6、進(jìn)程， 將已分配給該進(jìn)程的處理機(jī)，重新分配給另一進(jìn)程。（即在將已分配給該進(jìn)程的處理機(jī)，重新分配給另一進(jìn)程。（即在 情況情況1、2、3、4時均可調(diào)度）時均可調(diào)度） 時間片原則時間片原則 搶占原則搶占原則 優(yōu)先權(quán)原則優(yōu)先權(quán)原則 短進(jìn)程優(yōu)先原則短進(jìn)程優(yōu)先原則 4.1 4.1 調(diào)度類型和模型調(diào)度類型和模型一、調(diào)度類型一、調(diào)度類型分派程序的主要功能：分派程序的主要功能： 1. 進(jìn)行進(jìn)程切換；進(jìn)行進(jìn)程切換； 2. 轉(zhuǎn)到用戶態(tài)；轉(zhuǎn)到用戶態(tài)； 3. 開始執(zhí)行被選中的進(jìn)程。開始執(zhí)行被選中的進(jìn)程。 進(jìn)程進(jìn)程P P0 0 操作系統(tǒng)操作系統(tǒng) 進(jìn)程進(jìn)程P P1 1 執(zhí)行執(zhí)行執(zhí)行執(zhí)行將將P P0 0信息信息保存在保存在P

7、CBPCB0 0從從PCBPCB1 1中恢復(fù)中恢復(fù)P P1 1信息信息進(jìn)程進(jìn)程切換切換示意圖示意圖 4.1 4.1 調(diào)度類型和模型調(diào)度類型和模型一、調(diào)度類型一、調(diào)度類型 3. 中級調(diào)度（也稱中程調(diào)度）中級調(diào)度（也稱中程調(diào)度）作用：作用：負(fù)責(zé)進(jìn)程在內(nèi)存和外存對換區(qū)之間換進(jìn)負(fù)責(zé)進(jìn)程在內(nèi)存和外存對換區(qū)之間換進(jìn)/換出。換出。是內(nèi)存對換功能的一部分。是內(nèi)存對換功能的一部分。目的：目的：提高內(nèi)存利用率和系統(tǒng)吞吐量。提高內(nèi)存利用率和系統(tǒng)吞吐量。執(zhí)行頻率：執(zhí)行頻率：介于作業(yè)調(diào)度和進(jìn)程調(diào)度之間。介于作業(yè)調(diào)度和進(jìn)程調(diào)度之間。 4.1 4.1 調(diào)度類型和模型調(diào)度類型和模型二、調(diào)度模型二、調(diào)度模型僅有進(jìn)程僅有進(jìn)程調(diào)度

8、的調(diào)度隊列模型調(diào)度的調(diào)度隊列模型阻阻 塞塞 隊隊 列列 1 1就就 緒緒 隊隊 列列CPU進(jìn)程調(diào)度進(jìn)程調(diào)度進(jìn)程完成進(jìn)程完成交互用戶交互用戶等待事件等待事件1 1事件出現(xiàn)事件出現(xiàn)時間片用完時間片用完阻阻 塞塞 隊隊 列列 2 2等待事件等待事件2 2阻阻 塞塞 隊隊 列列 n n等待事件等待事件n n事件出現(xiàn)事件出現(xiàn)事件出現(xiàn)事件出現(xiàn) 4.1 4.1 調(diào)度類型和模型調(diào)度類型和模型二、調(diào)度模型二、調(diào)度模型具有作業(yè)調(diào)度和進(jìn)程具有作業(yè)調(diào)度和進(jìn)程調(diào)度的調(diào)度隊列模型調(diào)度的調(diào)度隊列模型阻阻 塞塞 隊隊 列列 1 1就就 緒緒 隊隊 列列CPU進(jìn)程調(diào)度進(jìn)程調(diào)度進(jìn)程完成進(jìn)程完成后備隊列后備隊列等待事件1事件出現(xiàn)時

9、間片用完時間片用完阻阻 塞塞 隊隊 列列 2 2等待事件2阻阻 塞塞 隊隊 列列 n n等待事件n事件出現(xiàn)事件出現(xiàn) 作業(yè)作業(yè)調(diào)度調(diào)度交互用戶交互用戶批處理批處理作業(yè)作業(yè)一、先來先服務(wù)調(diào)度算法一、先來先服務(wù)調(diào)度算法二、二、短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法三、時間片輪轉(zhuǎn)調(diào)度算法三、時間片輪轉(zhuǎn)調(diào)度算法四、優(yōu)先權(quán)調(diào)度算法四、優(yōu)先權(quán)調(diào)度算法五、高響應(yīng)比優(yōu)先調(diào)度算法五、高響應(yīng)比優(yōu)先調(diào)度算法六、多級隊列調(diào)度六、多級隊列調(diào)度七、多級反饋隊列調(diào)度算法七、多級反饋隊列調(diào)度算法4.2 4.2 調(diào)度算法調(diào)度算法縮寫：縮寫：FCFS（First Come First Served）既適用于作業(yè)調(diào)度，

10、又適用于進(jìn)程調(diào)度（非搶占方式）。既適用于作業(yè)調(diào)度，又適用于進(jìn)程調(diào)度（非搶占方式）。后備作業(yè)隊列、就緒隊列按后備作業(yè)隊列、就緒隊列按FIFO排列，調(diào)度時選擇處于排列，調(diào)度時選擇處于 隊首的作業(yè)或進(jìn)程。隊首的作業(yè)或進(jìn)程。優(yōu)點(diǎn)：簡單、易于實(shí)現(xiàn)。優(yōu)點(diǎn)：簡單、易于實(shí)現(xiàn)。 缺點(diǎn)：缺點(diǎn)：1 1）有利于長的作業(yè)或進(jìn)程，不利于短的。）有利于長的作業(yè)或進(jìn)程，不利于短的。 2 2）有利于）有利于CPU繁忙型的作業(yè)或進(jìn)程，不利于繁忙型的作業(yè)或進(jìn)程，不利于 I/O繁忙型的。繁忙型的。例：例： 4.2 4.2 調(diào)度算調(diào)度算法法一、先來先服務(wù)調(diào)度算法一、先來先服務(wù)調(diào)度算法 4.2 4.2 調(diào)度算法調(diào)度算法一、先來先服務(wù)調(diào)度

11、算法（例）一、先來先服務(wù)調(diào)度算法（例）進(jìn)程名進(jìn)程名 到達(dá)時間到達(dá)時間 服務(wù)時間服務(wù)時間 A 0 4 B 1 5 C 2 2 D 3 4A B C D0 4 9 11 15 0 4 9 11 15 開始時間開始時間 完成時間完成時間 周轉(zhuǎn)時間周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間 0 4 4 1 4 9 8 1.6 9 11 9 4.5 11 15 12 3平均平均 8.25 2.5258.25 2.525縮寫：縮寫：SJF（Shortest Job First）/SPF（Process)既適用于作業(yè)調(diào)度，又適用于進(jìn)程調(diào)度既適用于作業(yè)調(diào)度，又適用于進(jìn)程調(diào)度從后備作業(yè)隊列、就緒隊列中選擇估從后備作業(yè)隊

12、列、就緒隊列中選擇估 計運(yùn)行時間最短的作業(yè)或進(jìn)程。計運(yùn)行時間最短的作業(yè)或進(jìn)程。例：例： 4.2 4.2 調(diào)度算法調(diào)度算法二、短作業(yè)二、短作業(yè)/ /短進(jìn)程優(yōu)先調(diào)度算法短進(jìn)程優(yōu)先調(diào)度算法優(yōu)點(diǎn)：調(diào)度性能較好。優(yōu)點(diǎn)：調(diào)度性能較好。 缺點(diǎn)：缺點(diǎn)：1 1）不利于長的作業(yè)或進(jìn)程。）不利于長的作業(yè)或進(jìn)程。 2 2）不考慮作業(yè)或進(jìn)程的緊迫程度。）不考慮作業(yè)或進(jìn)程的緊迫程度。 3 3）估計運(yùn)行時間很難準(zhǔn)確獲得。）估計運(yùn)行時間很難準(zhǔn)確獲得。非搶占方式非搶占方式搶占方式搶占方式 4.2 4.2 調(diào)度算法調(diào)度算法二、短進(jìn)程優(yōu)先調(diào)度算法（例二、短進(jìn)程優(yōu)先調(diào)度算法（例1）進(jìn)程名進(jìn)程名 到達(dá)時間到達(dá)時間 服務(wù)時間服務(wù)時間 A

13、 0 4 B 1 5 C 2 2 D 3 4A C D B0 4 6 10 15 0 4 6 10 15 開始時間開始時間 完成時間完成時間 周轉(zhuǎn)時間周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間 0 4 4 1 10 15 14 2.8 4 6 4 2 6 10 7 1.75平均平均 7.25 1.88757.25 1.8875非搶占方式非搶占方式 4.2 4.2 調(diào)度算法調(diào)度算法二、短進(jìn)程優(yōu)先調(diào)度算法（例二、短進(jìn)程優(yōu)先調(diào)度算法（例2）進(jìn)程名進(jìn)程名 到達(dá)時間到達(dá)時間 服務(wù)時間服務(wù)時間 A 0 3 B 0 5 C 0 3 D 0 4 E 8 3搶占方式搶占方式1 1、基于最短服務(wù)時間搶占、基于最短服務(wù)時間

14、搶占：A C D E D B0 3 6 8 11 13 18 0 3 6 8 11 13 18 A C D E B0 3 6 10 13 18 0 3 6 10 13 18 非搶占方式非搶占方式2 2、基于最短剩余服務(wù)時間搶占、基于最短剩余服務(wù)時間搶占：A C D E B0 3 6 10 13 18 0 3 6 10 13 18 縮寫：縮寫：RR（Round Robin）僅適用于進(jìn)程調(diào)度（搶占方式）。僅適用于進(jìn)程調(diào)度（搶占方式）。主要為分時系統(tǒng)設(shè)計。主要為分時系統(tǒng)設(shè)計。就緒隊列按就緒隊列按FIFO排列，調(diào)度時排列，調(diào)度時選擇隊首進(jìn)程。但該進(jìn)程選擇隊首進(jìn)程。但該進(jìn)程 占用占用CPU至多執(zhí)行一個時

15、間片，便放棄至多執(zhí)行一個時間片，便放棄CPU。例：例： 4.2 4.2 調(diào)度算法調(diào)度算法三、時間片輪轉(zhuǎn)調(diào)度算法三、時間片輪轉(zhuǎn)調(diào)度算法關(guān)鍵：時間片大小的確定關(guān)鍵：時間片大小的確定 太大：退化為太大：退化為FCFS 太?。合到y(tǒng)效率降低太小：系統(tǒng)效率降低特點(diǎn)：假設(shè)所有進(jìn)程都是同等重要的。特點(diǎn)：假設(shè)所有進(jìn)程都是同等重要的。 4.2 4.2 調(diào)度算法調(diào)度算法三、時間片輪轉(zhuǎn)調(diào)度算法（例）三、時間片輪轉(zhuǎn)調(diào)度算法（例）進(jìn)程名進(jìn)程名 到達(dá)時間到達(dá)時間 服務(wù)時間服務(wù)時間 A 0 4 B 0 5 C 0 2 D 0 4開始時間開始時間 完成時間完成時間 周轉(zhuǎn)時間周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間 0 10 10 2

16、.5 2 15 15 3 4 6 6 3 6 14 14 3.5A B C D A B D B0 2 4 6 8 10 12 14 15 0 2 4 6 8 10 12 14 15 時間片時間片=2=2既適用于作業(yè)調(diào)度，又適用于進(jìn)程調(diào)度既適用于作業(yè)調(diào)度，又適用于進(jìn)程調(diào)度選擇具有最高優(yōu)先權(quán)的后備作業(yè)或就緒進(jìn)程。選擇具有最高優(yōu)先權(quán)的后備作業(yè)或就緒進(jìn)程。例：例： 4.2 4.2 調(diào)度算法調(diào)度算法四、優(yōu)先權(quán)調(diào)度算法四、優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)的類型：優(yōu)先權(quán)的類型： 1.1.靜態(tài)優(yōu)先權(quán)：創(chuàng)建進(jìn)程時確定，進(jìn)程運(yùn)行期間保持不變。靜態(tài)優(yōu)先權(quán)：創(chuàng)建進(jìn)程時確定，進(jìn)程運(yùn)行期間保持不變。 簡單易行，系統(tǒng)開銷小，但不夠精確

17、。簡單易行，系統(tǒng)開銷小，但不夠精確。 2.2.動態(tài)優(yōu)先權(quán)：創(chuàng)建進(jìn)程時確定初值，運(yùn)行期間基于某種原則動動態(tài)優(yōu)先權(quán)：創(chuàng)建進(jìn)程時確定初值，運(yùn)行期間基于某種原則動 態(tài)改變。例如，優(yōu)先權(quán)可隨占用態(tài)改變。例如，優(yōu)先權(quán)可隨占用CPUCPU時間加長而降時間加長而降 低。低。 靈活，調(diào)度性能好，但系統(tǒng)開銷大。靈活，調(diào)度性能好，但系統(tǒng)開銷大。 非搶占方式非搶占方式搶占方式搶占方式 4.2 4.2 調(diào)度算法調(diào)度算法四、優(yōu)先權(quán)調(diào)度算法（例）四、優(yōu)先權(quán)調(diào)度算法（例）進(jìn)程名進(jìn)程名 到達(dá)時間到達(dá)時間 服務(wù)時間服務(wù)時間 優(yōu)先權(quán)優(yōu)先權(quán) A 0 10 3 B 0 1 5 C 0 5 2 D 5 3 4B A D C 0 1 11

18、 14 19 非搶占方式非搶占方式B A D A C 0 1 5 8 14 19 搶占方式搶占方式主要用于作業(yè)調(diào)度主要用于作業(yè)調(diào)度選擇具有最高響應(yīng)比的后備作業(yè)。選擇具有最高響應(yīng)比的后備作業(yè)。 響應(yīng)比響應(yīng)比= =1+等待時間等待時間/ /要求服務(wù)時間要求服務(wù)時間例：例： 4.2 4.2 調(diào)度算法調(diào)度算法五、高響應(yīng)比優(yōu)先調(diào)度算法五、高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)點(diǎn)：既照顧了作業(yè)到來的先后，又考慮了要求服務(wù)時間優(yōu)點(diǎn)：既照顧了作業(yè)到來的先后，又考慮了要求服務(wù)時間 的長短，是的長短，是FCFS和和SJF的很好的折衷。的很好的折衷。 缺點(diǎn)：算法較為復(fù)雜；每次調(diào)度時，均要重新計算響應(yīng)比。缺點(diǎn)：算法較為復(fù)雜；每次調(diào)度

19、時，均要重新計算響應(yīng)比。 4.2 4.2 調(diào)度算法調(diào)度算法五、高響應(yīng)比優(yōu)先調(diào)度算法五、高響應(yīng)比優(yōu)先調(diào)度算法作業(yè)名作業(yè)名J1J2J3到達(dá)時間到達(dá)時間8:008:309:30服務(wù)時間服務(wù)時間2小時小時1小時小時0.25小時小時三個作業(yè)在一臺處理機(jī)上單道運(yùn)行，三個作業(yè)在一臺處理機(jī)上單道運(yùn)行，9:40 9:40 進(jìn)行作業(yè)調(diào)度，問三個作業(yè)的執(zhí)進(jìn)行作業(yè)調(diào)度，問三個作業(yè)的執(zhí)行次序？行次序？9:40 9:40 調(diào)度時：調(diào)度時：J1J1：1+100/120 = 1+5/61+100/120 = 1+5/6J2J2：1+70/60 = 1+7/61+70/60 = 1+7/6J3J3：1+10/15 = 1+4/

20、61+10/15 = 1+4/6選擇選擇J2J2作業(yè)調(diào)度作業(yè)調(diào)度10:4010:40（J2J2完成）調(diào)度時：完成）調(diào)度時：J1J1：1+160/120 = 1+4/31+160/120 = 1+4/3J3J3：1+70/15 = 1+14/31+70/15 = 1+14/3選擇選擇J3J3作業(yè)調(diào)度作業(yè)調(diào)度執(zhí)行次序：執(zhí)行次序：J2J2、J3J3、J1J1適用于進(jìn)程調(diào)度。適用于進(jìn)程調(diào)度。調(diào)度方式：調(diào)度方式： 1.1.按性質(zhì)和類型將就緒隊列分為若干子隊列，每個就緒按性質(zhì)和類型將就緒隊列分為若干子隊列，每個就緒 進(jìn)程固定地分屬于一個子隊列，每個隊列有自己的調(diào)進(jìn)程固定地分屬于一個子隊列，每個隊列有自己的

21、調(diào) 度算法。度算法。 2.2.各隊列間的調(diào)度方式或采用固定優(yōu)先權(quán)搶占調(diào)度，或各隊列間的調(diào)度方式或采用固定優(yōu)先權(quán)搶占調(diào)度，或 為各隊列分配一定比例的為各隊列分配一定比例的CPU時間。時間。 4.2 4.2 調(diào)度算法調(diào)度算法六、多級隊列調(diào)度六、多級隊列調(diào)度適用于進(jìn)程調(diào)度適用于進(jìn)程調(diào)度-搶占方式。搶占方式。實(shí)施過程：實(shí)施過程： 4.2 4.2 調(diào)度算法調(diào)度算法七、多級反饋隊列調(diào)度算法七、多級反饋隊列調(diào)度算法就緒隊列就緒隊列1 1（FCFS）s1CPU結(jié)束或結(jié)束或阻塞阻塞就緒隊列就緒隊列2 2（FCFS）s2CPU就緒隊列就緒隊列n（RR）snCPU提交提交高高優(yōu)優(yōu)先先權(quán)權(quán)低低（時間片（時間片s1s2

22、 sn ）結(jié)束或結(jié)束或阻塞阻塞結(jié)束或結(jié)束或阻塞阻塞一、對實(shí)時系統(tǒng)的要求一、對實(shí)時系統(tǒng)的要求二、二、實(shí)時調(diào)度算法實(shí)時調(diào)度算法三、實(shí)時調(diào)度實(shí)例三、實(shí)時調(diào)度實(shí)例4.3 4.3 實(shí)時系統(tǒng)中的調(diào)度實(shí)時系統(tǒng)中的調(diào)度一、對實(shí)時系統(tǒng)的要求一、對實(shí)時系統(tǒng)的要求實(shí)時系統(tǒng)與其他普通的系統(tǒng)之間的最大的不同之處就是要實(shí)時系統(tǒng)與其他普通的系統(tǒng)之間的最大的不同之處就是要滿足處理與時間的關(guān)系。滿足處理與時間的關(guān)系。在實(shí)時計算中，系統(tǒng)的正確性不僅僅依賴于計算的邏輯結(jié)在實(shí)時計算中，系統(tǒng)的正確性不僅僅依賴于計算的邏輯結(jié)果而且依賴于結(jié)果產(chǎn)生的時間。果而且依賴于結(jié)果產(chǎn)生的時間。對于實(shí)時系統(tǒng)來說最重要的要求就是實(shí)時操作系統(tǒng)必須有對于實(shí)時

23、系統(tǒng)來說最重要的要求就是實(shí)時操作系統(tǒng)必須有滿足在一個事先定義好的時間限制中對外部或內(nèi)部的事件進(jìn)滿足在一個事先定義好的時間限制中對外部或內(nèi)部的事件進(jìn)行響應(yīng)和處理的能力。行響應(yīng)和處理的能力。實(shí)時系統(tǒng)可以定義為實(shí)時系統(tǒng)可以定義為“一個能夠在事先指定或確定的時間一個能夠在事先指定或確定的時間內(nèi)完成系統(tǒng)功能和對外部或內(nèi)部、同步或異步事件作出響應(yīng)內(nèi)完成系統(tǒng)功能和對外部或內(nèi)部、同步或異步事件作出響應(yīng)的系統(tǒng)的系統(tǒng) 。（。（* *Real_Time UNIX Systems Design and Real_Time UNIX Systems Design and Application Guide )Appli

24、cation Guide )一、對實(shí)時系統(tǒng)的要求一、對實(shí)時系統(tǒng)的要求由于實(shí)時系統(tǒng)在設(shè)計時與應(yīng)用的關(guān)系非常強(qiáng)，所以有許多由于實(shí)時系統(tǒng)在設(shè)計時與應(yīng)用的關(guān)系非常強(qiáng)，所以有許多分類的方法。各種分類的側(cè)重點(diǎn)不同。分類的方法。各種分類的側(cè)重點(diǎn)不同。方法一方法一 分為周期性的和非周期性的（分為周期性的和非周期性的（periodicperiodic和和aperiodicaperiodic）。）。周期性的就是系統(tǒng)通過傳感器或其他設(shè)備周期性的探測外周期性的就是系統(tǒng)通過傳感器或其他設(shè)備周期性的探測外部環(huán)境的變化，在周期內(nèi)對探測到的變化作出反應(yīng)。比如化部環(huán)境的變化，在周期內(nèi)對探測到的變化作出反應(yīng)。比如化工廠中的反應(yīng)爐

25、的控制。工廠中的反應(yīng)爐的控制。非周期性的指外部事件是循環(huán)性的發(fā)生的，但不是有規(guī)律非周期性的指外部事件是循環(huán)性的發(fā)生的，但不是有規(guī)律的或者是突發(fā)事件。比如一架客機(jī)飛入一個空中交通管制的的或者是突發(fā)事件。比如一架客機(jī)飛入一個空中交通管制的管制范圍所產(chǎn)生的事件。管制范圍所產(chǎn)生的事件。一、對實(shí)時系統(tǒng)的要求一、對實(shí)時系統(tǒng)的要求方法二方法二 分為硬實(shí)時和軟實(shí)時（分為硬實(shí)時和軟實(shí)時（hard real_timehard real_time和和soft soft realtimerealtime）。硬實(shí)時系統(tǒng)就是系統(tǒng)必須及時的對事件作出反）。硬實(shí)時系統(tǒng)就是系統(tǒng)必須及時的對事件作出反應(yīng)，絕對不能發(fā)生錯過事件處理

26、的應(yīng)，絕對不能發(fā)生錯過事件處理的deadlinedeadline的情況。在硬實(shí)的情況。在硬實(shí)時系統(tǒng)中一旦發(fā)生了這種情況就意味著巨大的損失和災(zāi)難。時系統(tǒng)中一旦發(fā)生了這種情況就意味著巨大的損失和災(zāi)難。比如控制核電站的系統(tǒng)，如果沒有對堆芯過熱作出及時的處比如控制核電站的系統(tǒng)，如果沒有對堆芯過熱作出及時的處理，后果不堪想象。理，后果不堪想象。在軟實(shí)時系統(tǒng)中，當(dāng)系統(tǒng)在重負(fù)載的情況下允許發(fā)生錯在軟實(shí)時系統(tǒng)中，當(dāng)系統(tǒng)在重負(fù)載的情況下允許發(fā)生錯過過deadlinedeadline的情況而不會造成非常大的危害。比如在通信系的情況而不會造成非常大的危害。比如在通信系統(tǒng)中允許統(tǒng)中允許105105個電話中有一個接不通

27、。個電話中有一個接不通。對于軟實(shí)時系統(tǒng)基于優(yōu)先級調(diào)度的調(diào)度算法可以滿足要對于軟實(shí)時系統(tǒng)基于優(yōu)先級調(diào)度的調(diào)度算法可以滿足要求，提供高速的響應(yīng)和大的系統(tǒng)吞吐率；而對于硬實(shí)時系統(tǒng)求，提供高速的響應(yīng)和大的系統(tǒng)吞吐率；而對于硬實(shí)時系統(tǒng)則完成則完成timely responsetimely response是必須的。是必須的。一、對實(shí)時系統(tǒng)的要求一、對實(shí)時系統(tǒng)的要求作為實(shí)時系統(tǒng)其特性決定了傳統(tǒng)的性能衡量標(biāo)準(zhǔn)對其是作為實(shí)時系統(tǒng)其特性決定了傳統(tǒng)的性能衡量標(biāo)準(zhǔn)對其是不適用的。對傳統(tǒng)的通用系統(tǒng)的要求是大的系統(tǒng)吞吐量，合不適用的。對傳統(tǒng)的通用系統(tǒng)的要求是大的系統(tǒng)吞吐量，合理的響應(yīng)速度，對每個系統(tǒng)用戶相對公平的進(jìn)行計

28、算資源的理的響應(yīng)速度，對每個系統(tǒng)用戶相對公平的進(jìn)行計算資源的分配。然而在實(shí)時系統(tǒng)中，以上這些要求都不再適用或者是分配。然而在實(shí)時系統(tǒng)中，以上這些要求都不再適用或者是不再占重要位置。實(shí)時系統(tǒng)中系統(tǒng)的一切動作都以實(shí)時任務(wù)不再占重要位置。實(shí)時系統(tǒng)中系統(tǒng)的一切動作都以實(shí)時任務(wù)為中心。為次，系統(tǒng)應(yīng)該向調(diào)度程序提供的一些是信息：為中心。為次，系統(tǒng)應(yīng)該向調(diào)度程序提供的一些是信息：就緒時間就緒時間開始截止時間和完成截止時間開始截止時間和完成截止時間處理時間處理時間資源要求資源要求優(yōu)先級優(yōu)先級子任務(wù)結(jié)構(gòu)子任務(wù)結(jié)構(gòu)一、對實(shí)時系統(tǒng)的要求一、對實(shí)時系統(tǒng)的要求z 調(diào)度方式：調(diào)度方式：大部分采用搶占式調(diào)度方式，具有教高的

29、靈活性，較小大部分采用搶占式調(diào)度方式，具有教高的靈活性，較小的延遲，但算法復(fù)雜，開銷比較大。要求不太嚴(yán)格的系統(tǒng)中，的延遲，但算法復(fù)雜，開銷比較大。要求不太嚴(yán)格的系統(tǒng)中，也可以采用非剝奪調(diào)度方式，以簡化系統(tǒng)。也可以采用非剝奪調(diào)度方式，以簡化系統(tǒng)。z 快速響應(yīng)外部中斷的能力快速響應(yīng)外部中斷的能力緊迫事件出現(xiàn)時，系統(tǒng)可以及時響應(yīng)。系統(tǒng)需具有快速緊迫事件出現(xiàn)時，系統(tǒng)可以及時響應(yīng)。系統(tǒng)需具有快速硬件中斷機(jī)構(gòu)，使中斷間隔盡量短。硬件中斷機(jī)構(gòu)，使中斷間隔盡量短。z 快速任務(wù)分派快速任務(wù)分派任務(wù)的切換應(yīng)該盡量快速，使得消耗的時間盡量少任務(wù)的切換應(yīng)該盡量快速，使得消耗的時間盡量少二、二、實(shí)時調(diào)度算法實(shí)時調(diào)度算法

30、實(shí)時調(diào)度是計算機(jī)科學(xué)中最活躍的研究領(lǐng)域之一。實(shí)時調(diào)度是計算機(jī)科學(xué)中最活躍的研究領(lǐng)域之一。z 時間片輪轉(zhuǎn)調(diào)度算法時間片輪轉(zhuǎn)調(diào)度算法z 非搶占優(yōu)先權(quán)調(diào)度算法非搶占優(yōu)先權(quán)調(diào)度算法z 基于時鐘中斷搶占的優(yōu)先權(quán)算法基于時鐘中斷搶占的優(yōu)先權(quán)算法z 立即搶占的優(yōu)先權(quán)算法立即搶占的優(yōu)先權(quán)算法二、二、實(shí)時調(diào)度算法實(shí)時調(diào)度算法z 時間片輪轉(zhuǎn)調(diào)度算法時間片輪轉(zhuǎn)調(diào)度算法 這種調(diào)度算法的基本思想是將處理器的時間分為這種調(diào)度算法的基本思想是將處理器的時間分為“幀幀”。一個幀就是一個系統(tǒng)內(nèi)部時鐘觸發(fā)時鐘中斷的基本時間。一個幀就是一個系統(tǒng)內(nèi)部時鐘觸發(fā)時鐘中斷的基本時間。每個實(shí)時任務(wù)都在幀中占一段時間。仔細(xì)設(shè)計幀的大小每個實(shí)時

31、任務(wù)都在幀中占一段時間。仔細(xì)設(shè)計幀的大小可以保證系統(tǒng)中所有的實(shí)時任務(wù)都能在可以保證系統(tǒng)中所有的實(shí)時任務(wù)都能在deadlinedeadline之前完成。之前完成。而事件觸發(fā)的實(shí)時任務(wù)則在每個幀中最后一個周期性實(shí)時任而事件觸發(fā)的實(shí)時任務(wù)則在每個幀中最后一個周期性實(shí)時任務(wù)完成之后到幀結(jié)束這段時間內(nèi)得以運(yùn)行。這種算法在系統(tǒng)務(wù)完成之后到幀結(jié)束這段時間內(nèi)得以運(yùn)行。這種算法在系統(tǒng)相對簡單，任務(wù)數(shù)少，又可以事先定義任務(wù)的執(zhí)行順序的情相對簡單，任務(wù)數(shù)少，又可以事先定義任務(wù)的執(zhí)行順序的情況下很有效。況下很有效。二、二、實(shí)時調(diào)度算法實(shí)時調(diào)度算法z 非搶占優(yōu)先權(quán)調(diào)度算法非搶占優(yōu)先權(quán)調(diào)度算法優(yōu)先級隊列算法。這種算法從優(yōu)

32、先級隊列算法。這種算法從FIFOFIFO發(fā)展而來。給每個任發(fā)展而來。給每個任務(wù)設(shè)定優(yōu)先級，然后在務(wù)設(shè)定優(yōu)先級，然后在FIFOFIFO中按照優(yōu)先級排列。這種算法保中按照優(yōu)先級排列。這種算法保證了高優(yōu)先級的任務(wù)的完成，但是對于低優(yōu)先級的任務(wù)很可證了高優(yōu)先級的任務(wù)的完成，但是對于低優(yōu)先級的任務(wù)很可能無法滿足時間的正確性。而且對低優(yōu)先級的任務(wù)來說等待能無法滿足時間的正確性。而且對低優(yōu)先級的任務(wù)來說等待的時間是無法預(yù)知的。的時間是無法預(yù)知的。我們無法知道在什么情況下會發(fā)生時間正確性上的錯誤。我們無法知道在什么情況下會發(fā)生時間正確性上的錯誤。而且必須在設(shè)計時仔細(xì)的檢查任務(wù)優(yōu)先級的設(shè)定，要保證不而且必須在設(shè)

33、計時仔細(xì)的檢查任務(wù)優(yōu)先級的設(shè)定，要保證不會因?yàn)榈蛢?yōu)先級的任務(wù)無法按時完成而破壞整個系統(tǒng)的完整會因?yàn)榈蛢?yōu)先級的任務(wù)無法按時完成而破壞整個系統(tǒng)的完整性。這個算法也是與特定應(yīng)用有關(guān)的。當(dāng)環(huán)境或情況變化時性。這個算法也是與特定應(yīng)用有關(guān)的。當(dāng)環(huán)境或情況變化時系統(tǒng)無法隨之變化。系統(tǒng)無法隨之變化。二、二、實(shí)時調(diào)度算法實(shí)時調(diào)度算法z 基于時鐘中斷搶占的優(yōu)先權(quán)算法基于時鐘中斷搶占的優(yōu)先權(quán)算法這種算法用于搶先式多任務(wù)的實(shí)時操作系統(tǒng)。該算法的這種算法用于搶先式多任務(wù)的實(shí)時操作系統(tǒng)。該算法的基本思想是在系統(tǒng)中使用優(yōu)先級驅(qū)動的可搶先的調(diào)度算法?；舅枷胧窃谙到y(tǒng)中使用優(yōu)先級驅(qū)動的可搶先的調(diào)度算法。也就是系統(tǒng)首先調(diào)度高優(yōu)先

34、級的任務(wù)運(yùn)行。低優(yōu)先級的任務(wù)也就是系統(tǒng)首先調(diào)度高優(yōu)先級的任務(wù)運(yùn)行。低優(yōu)先級的任務(wù)在高優(yōu)先級的任務(wù)運(yùn)行時不能搶先；在高優(yōu)先級的任務(wù)運(yùn)行時不能搶先；CPUCPU由高優(yōu)先級進(jìn)程獨(dú)由高優(yōu)先級進(jìn)程獨(dú)占。占。當(dāng)中斷發(fā)生時，正在運(yùn)行的任務(wù)被中斷，進(jìn)入中斷處理。當(dāng)中斷發(fā)生時，正在運(yùn)行的任務(wù)被中斷，進(jìn)入中斷處理。如果中斷引起的操作是屬于一個較低優(yōu)先級的任務(wù)的，那么如果中斷引起的操作是屬于一個較低優(yōu)先級的任務(wù)的，那么為了保證中斷被及時的處理，此低優(yōu)先級進(jìn)程暫時繼承原來為了保證中斷被及時的處理，此低優(yōu)先級進(jìn)程暫時繼承原來當(dāng)中斷發(fā)生時正在運(yùn)行的高優(yōu)先級任務(wù)的優(yōu)先級。當(dāng)處理完當(dāng)中斷發(fā)生時正在運(yùn)行的高優(yōu)先級任務(wù)的優(yōu)先級。

35、當(dāng)處理完關(guān)鍵區(qū)域后，此低優(yōu)先級任務(wù)恢復(fù)原來的優(yōu)先級并被掛起，關(guān)鍵區(qū)域后，此低優(yōu)先級任務(wù)恢復(fù)原來的優(yōu)先級并被掛起，然后恢復(fù)原來高優(yōu)先級任務(wù)的運(yùn)行。然后恢復(fù)原來高優(yōu)先級任務(wù)的運(yùn)行。二、二、實(shí)時調(diào)度算法實(shí)時調(diào)度算法z 立即搶占的優(yōu)先權(quán)算法立即搶占的優(yōu)先權(quán)算法與算法三的區(qū)別在于立即進(jìn)行調(diào)度，而不等待時鐘的中與算法三的區(qū)別在于立即進(jìn)行調(diào)度，而不等待時鐘的中斷發(fā)生。斷發(fā)生。三、實(shí)時調(diào)度實(shí)例三、實(shí)時調(diào)度實(shí)例1.具有開始截止時間的非周期實(shí)時任務(wù)的調(diào)度具有開始截止時間的非周期實(shí)時任務(wù)的調(diào)度 在事先知道各任務(wù)的開始截止時間，且對調(diào)度時延不太在事先知道各任務(wù)的開始截止時間，且對調(diào)度時延不太嚴(yán)格的請情況下，可采用最早

36、截止時間優(yōu)先的非剝奪調(diào)度策嚴(yán)格的請情況下，可采用最早截止時間優(yōu)先的非剝奪調(diào)度策略。略。例：例：任務(wù)到達(dá)時間開始截止時間執(zhí)行時間A024B2155C365D6104調(diào)度結(jié)果是調(diào)度結(jié)果是A AC CD DB B 0 4 9 13 17 0 4 9 13 17三、實(shí)時調(diào)度實(shí)例三、實(shí)時調(diào)度實(shí)例2.具有完成截止時間的周期性實(shí)時任務(wù)的調(diào)度具有完成截止時間的周期性實(shí)時任務(wù)的調(diào)度例：一個系統(tǒng)，從兩個傳感器例：一個系統(tǒng)，從兩個傳感器A和和B中收集并處理數(shù)據(jù)。傳中收集并處理數(shù)據(jù)。傳感器感器A收集數(shù)據(jù)的最后期限必須是每收集數(shù)據(jù)的最后期限必須是每10ms一次，一次，B的最的最后期限是每后期限是每50ms一次。處理每個

37、來自一次。處理每個來自A的數(shù)據(jù)樣本需要的數(shù)據(jù)樣本需要10ms,處理每個來自處理每個來自B的數(shù)據(jù)樣本需要的數(shù)據(jù)樣本需要25ms（包括操作（包括操作系統(tǒng)的開銷）。系統(tǒng)的開銷）。 如何調(diào)度如何調(diào)度A、B處理進(jìn)程？處理進(jìn)程？進(jìn)程進(jìn)程到達(dá)時間到達(dá)時間執(zhí)行時間執(zhí)行時間最后結(jié)束期限最后結(jié)束期限A(1)01020A(2)201040A(3)401060A(4)601080A(5)8010100B(1)02550B(2)5025100啟動最后期限啟動最后期限 10305070902575A1A1A2A2B1B1A3A3A4A4B2B20 10 20 30 40 50 60 70 80 90 100 110B1B

38、1B2B2A5A5實(shí)時系統(tǒng)的其他問題實(shí)時系統(tǒng)的內(nèi)存和外圍設(shè)備管理實(shí)時系統(tǒng)的內(nèi)存和外圍設(shè)備管理實(shí)時系統(tǒng)的通信實(shí)時系統(tǒng)的通信實(shí)時操作系統(tǒng)的內(nèi)核實(shí)時操作系統(tǒng)的內(nèi)核一、產(chǎn)生死鎖的原因一、產(chǎn)生死鎖的原因二、二、產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件三、處理死鎖的四種策略三、處理死鎖的四種策略四、鴕鳥算法四、鴕鳥算法.死鎖（死鎖（Deadlock）：）：假若在一個進(jìn)程集合中的每個進(jìn)程都在假若在一個進(jìn)程集合中的每個進(jìn)程都在 等待只能由該集合中的其它一個進(jìn)程才能引發(fā)的事件，等待只能由該集合中的其它一個進(jìn)程才能引發(fā)的事件， 那么這種狀態(tài)被看成是死鎖。那么這種狀態(tài)被看成是死鎖。.多數(shù)情況下，進(jìn)程是在等待該集合中的另

39、一個進(jìn)程正占有的多數(shù)情況下，進(jìn)程是在等待該集合中的另一個進(jìn)程正占有的 資源。但由于所有進(jìn)程都在等待，都不能運(yùn)行，因而無法釋資源。但由于所有進(jìn)程都在等待，都不能運(yùn)行，因而無法釋 放任何資源，于是該集合中的所有進(jìn)程都不能被喚醒。放任何資源，于是該集合中的所有進(jìn)程都不能被喚醒。4.6 4.6 死鎖的基本概念死鎖的基本概念競爭資源引起死鎖競爭資源引起死鎖 4.6 4.6 死鎖的基本概念死鎖的基本概念一、產(chǎn)生死鎖的原因一、產(chǎn)生死鎖的原因資源：資源：在任何時候都只能被一個進(jìn)程使用的任何對象。在任何時候都只能被一個進(jìn)程使用的任何對象。資源分類：資源分類： 可剝奪資源：可從擁有它的進(jìn)程中剝奪而不會產(chǎn)生任何副作

40、用?？蓜儕Z資源：可從擁有它的進(jìn)程中剝奪而不會產(chǎn)生任何副作用。 不可剝奪資源：從擁有它的進(jìn)程中剝奪會產(chǎn)生錯誤。不可剝奪資源：從擁有它的進(jìn)程中剝奪會產(chǎn)生錯誤。資源使用順序：資源使用順序： 申請資源申請資源使用資源使用資源釋放資源。釋放資源。 l 某進(jìn)程申請資源失敗，則轉(zhuǎn)為阻塞狀態(tài)，進(jìn)入資源等待隊列。某進(jìn)程申請資源失敗，則轉(zhuǎn)為阻塞狀態(tài)，進(jìn)入資源等待隊列。l 申請資源的命令與系統(tǒng)有關(guān)。有些系統(tǒng)提供的是申請資源的命令與系統(tǒng)有關(guān)。有些系統(tǒng)提供的是request命令；命令； 有些系統(tǒng)則將資源看作特殊文件，用有些系統(tǒng)則將資源看作特殊文件，用open命令打開來表示進(jìn)命令打開來表示進(jìn) 程申請資源。另外，程申請資源

41、。另外，P/V操作也可表示對資源的申請和釋放。操作也可表示對資源的申請和釋放。競爭資源引起死鎖競爭資源引起死鎖 4.6 4.6 死鎖的基本概念死鎖的基本概念一、產(chǎn)生死鎖的原因一、產(chǎn)生死鎖的原因競爭不可剝奪資源可能引發(fā)死鎖。競爭不可剝奪資源可能引發(fā)死鎖。例：例：系統(tǒng)中只有一臺打印機(jī)和一臺磁帶機(jī)。系統(tǒng)中只有一臺打印機(jī)和一臺磁帶機(jī)。 進(jìn)程進(jìn)程p1 進(jìn)程進(jìn)程p2 1. request(打印機(jī)打印機(jī)); 3. request(磁帶機(jī)磁帶機(jī)); 2. request(磁帶機(jī)磁帶機(jī)); 4. request(打印機(jī)打印機(jī)); 使用使用; 使用使用; release(打印機(jī)打印機(jī)); release(打印機(jī)打

42、印機(jī)); release(磁帶機(jī)磁帶機(jī)); release(磁帶機(jī)磁帶機(jī)); 進(jìn)程進(jìn)程p1和和 進(jìn)程進(jìn)程p2交交替占用替占用CPU執(zhí)行時，執(zhí)行時，順序?yàn)轫樞驗(yàn)?234或或3412 不會出錯。但為不會出錯。但為 1324 時，會死鎖。時，會死鎖。進(jìn)程推進(jìn)順序不當(dāng)引發(fā)死鎖進(jìn)程推進(jìn)順序不當(dāng)引發(fā)死鎖 4.6 4.6 死鎖的基本概念死鎖的基本概念一、產(chǎn)生死鎖的原因一、產(chǎn)生死鎖的原因例：進(jìn)程進(jìn)程p1和進(jìn)程和進(jìn)程p2交替占用交替占用CPU執(zhí)行時，執(zhí)行時，順序?yàn)轫樞驗(yàn)?或或2或或3時，不會出錯。時，不會出錯。但為但為 4 時，會時，會死鎖。死鎖。p1 req(r1) p1 req(r2) p1 rel(r1)

43、 p2 rel(r2)p2 rel(r1)p2 rel(r2)p2 req(r1)p2 req(r2)4 41 12 23 3互斥條件互斥條件 每個資源要么已分配給了一個進(jìn)程，要么空閑。每個資源要么已分配給了一個進(jìn)程，要么空閑。請求和保持條件請求和保持條件 已經(jīng)得到資源的進(jìn)程可以申請新的資源，申請失敗時變?yōu)樽枞麪钜呀?jīng)得到資源的進(jìn)程可以申請新的資源，申請失敗時變?yōu)樽枞麪?態(tài)，此時它仍然保持著原有資源不放。態(tài)，此時它仍然保持著原有資源不放。不剝奪條件不剝奪條件 已經(jīng)分配給一個進(jìn)程的資源不能被剝奪，只能由占有它的進(jìn)程主已經(jīng)分配給一個進(jìn)程的資源不能被剝奪，只能由占有它的進(jìn)程主 動釋放。動釋放。環(huán)路等待

44、條件環(huán)路等待條件 系統(tǒng)一定有兩個或兩個以上的進(jìn)程組成的一條環(huán)路，該環(huán)路中的系統(tǒng)一定有兩個或兩個以上的進(jìn)程組成的一條環(huán)路，該環(huán)路中的 每個進(jìn)程都在等待著相鄰進(jìn)程正占用著的資源。每個進(jìn)程都在等待著相鄰進(jìn)程正占用著的資源。 4.6 4.6 死鎖的基本概念死鎖的基本概念二、產(chǎn)生死鎖的必要條件二、產(chǎn)生死鎖的必要條件預(yù)防死鎖預(yù)防死鎖 通過破除死鎖的四個必要條件之一，來防止通過破除死鎖的四個必要條件之一，來防止 死鎖產(chǎn)生。死鎖產(chǎn)生。避免死鎖避免死鎖 仔細(xì)地對資源進(jìn)行動態(tài)分配，以避免死鎖發(fā)生。仔細(xì)地對資源進(jìn)行動態(tài)分配，以避免死鎖發(fā)生。檢測與解除死鎖檢測與解除死鎖 檢測系統(tǒng)中是否出現(xiàn)死鎖，若出現(xiàn)則解除掉。檢測系

45、統(tǒng)中是否出現(xiàn)死鎖，若出現(xiàn)則解除掉。忽略該問題忽略該問題 4.6 4.6 死鎖的基本概念死鎖的基本概念三、處理死鎖的四種策略三、處理死鎖的四種策略假裝死鎖假裝死鎖永不發(fā)生永不發(fā)生保證系統(tǒng)保證系統(tǒng)永遠(yuǎn)不會永遠(yuǎn)不會發(fā)生死鎖發(fā)生死鎖允許系統(tǒng)允許系統(tǒng)發(fā)生死鎖發(fā)生死鎖然后解除然后解除思想：思想：不采取任何措施，對死鎖視而不見。不采取任何措施，對死鎖視而不見。實(shí)例：實(shí)例：UNIX系統(tǒng)（還有其它許多系統(tǒng)）。系統(tǒng)（還有其它許多系統(tǒng)）。由于不預(yù)防、避免死鎖，故系統(tǒng)中可能發(fā)生死鎖。而發(fā)由于不預(yù)防、避免死鎖，故系統(tǒng)中可能發(fā)生死鎖。而發(fā) 生時又無法知道（因不檢測），造成系統(tǒng)崩潰，需要重生時又無法知道（因不檢測），造成系

46、統(tǒng)崩潰，需要重 啟。啟。之所以被某些系統(tǒng)采用，是因?yàn)樗梨i不常發(fā)生。之所以被某些系統(tǒng)采用，是因?yàn)樗梨i不常發(fā)生。 4.6 4.6 死鎖的基本概念死鎖的基本概念四、鴕鳥算法四、鴕鳥算法一、死鎖的預(yù)防一、死鎖的預(yù)防二、二、死鎖的避免死鎖的避免4.7 4.7 死鎖的預(yù)防和避免死鎖的預(yù)防和避免如果能夠保證四個必要條件中至少有一個不成立，那么如果能夠保證四個必要條件中至少有一個不成立，那么 死鎖將不會產(chǎn)生。（死鎖將不會產(chǎn)生。（Havender,1968Havender,1968）但其中的但其中的“互斥互斥”條件不能破除。條件不能破除。 4.7 4.7 死鎖的預(yù)防和避免死鎖的預(yù)防和避免一、預(yù)防死鎖一、預(yù)防死鎖

47、破除破除“請求和保持請求和保持”條件條件 4.7 4.7 死鎖的預(yù)防和避免死鎖的預(yù)防和避免一、預(yù)防死鎖一、預(yù)防死鎖方法：方法：規(guī)定進(jìn)程在執(zhí)行前要一次性地申請運(yùn)行所需全部規(guī)定進(jìn)程在執(zhí)行前要一次性地申請運(yùn)行所需全部 資源。只有資源全部到手，進(jìn)程方可運(yùn)行，否則資源。只有資源全部到手，進(jìn)程方可運(yùn)行，否則 進(jìn)程等待。進(jìn)程等待。優(yōu)點(diǎn)：優(yōu)點(diǎn)：簡單、易于實(shí)現(xiàn)。簡單、易于實(shí)現(xiàn)。 缺點(diǎn)：缺點(diǎn)：1.1.資源利用率低。資源利用率低。 2.2.進(jìn)程運(yùn)行被延遲。進(jìn)程運(yùn)行被延遲。破除破除“不剝奪不剝奪”條件條件 4.7 4.7 死鎖的預(yù)防和避免死鎖的預(yù)防和避免一、預(yù)防死鎖一、預(yù)防死鎖方法：方法：保持資源的進(jìn)程申請新資源失敗

48、時，在轉(zhuǎn)為阻塞狀態(tài)之保持資源的進(jìn)程申請新資源失敗時，在轉(zhuǎn)為阻塞狀態(tài)之 前，必須釋放其占用的全部資源。而該進(jìn)程自身則必須前，必須釋放其占用的全部資源。而該進(jìn)程自身則必須 等到重新獲得原有資源及新資源后，才能重新運(yùn)行。等到重新獲得原有資源及新資源后，才能重新運(yùn)行。缺點(diǎn)：缺點(diǎn)：實(shí)現(xiàn)復(fù)雜，代價大。實(shí)現(xiàn)復(fù)雜，代價大。適用范圍：適用范圍：資源的狀態(tài)能夠很方便的保存和恢復(fù)，例如資源的狀態(tài)能夠很方便的保存和恢復(fù)，例如CPUCPU寄寄 存器和存儲空間。存器和存儲空間。破除破除“環(huán)路等待環(huán)路等待”條件條件 4.7 4.7 死鎖的預(yù)防和避免死鎖的預(yù)防和避免一、預(yù)防死鎖一、預(yù)防死鎖方法方法1 1：保證每個進(jìn)程在任何時

49、候只能占用一個資源。要用第二保證每個進(jìn)程在任何時候只能占用一個資源。要用第二 個，必須先釋放第一個。個，必須先釋放第一個。方法方法2 2：將系統(tǒng)中所有資源賦予一個全局編號，進(jìn)程申請資源時，將系統(tǒng)中所有資源賦予一個全局編號，進(jìn)程申請資源時， 必須按編號遞增順序進(jìn)行。必須按編號遞增順序進(jìn)行。缺點(diǎn)：缺點(diǎn)：1.1.找不出一種人人滿意的編號順序。找不出一種人人滿意的編號順序。 2.2.仍存在資源浪費(fèi)。仍存在資源浪費(fèi)。 3.3.用戶編程受到限制。用戶編程受到限制。思路：思路： 4.7 4.7 死鎖的預(yù)防和避免死鎖的預(yù)防和避免二、避免死鎖二、避免死鎖允許進(jìn)程動態(tài)的申請資源。允許進(jìn)程動態(tài)的申請資源。將系統(tǒng)狀態(tài)

50、分為將系統(tǒng)狀態(tài)分為 安全狀態(tài)：不會發(fā)生死鎖安全狀態(tài)：不會發(fā)生死鎖 不安全狀態(tài)：可能發(fā)生死鎖不安全狀態(tài)：可能發(fā)生死鎖 避免系統(tǒng)進(jìn)入不安全狀態(tài)！避免系統(tǒng)進(jìn)入不安全狀態(tài)！做法：做法：每次進(jìn)行資源分配時，首先檢測一下每次進(jìn)行資源分配時，首先檢測一下資源分配后資源分配后系統(tǒng)處系統(tǒng)處 于何種狀態(tài)，若處于于何種狀態(tài)，若處于安全安全狀態(tài)，則正式實(shí)施本次狀態(tài)，則正式實(shí)施本次分配分配； 若處于若處于不安全不安全狀態(tài)，則狀態(tài)，則不予分配不予分配，申請資源的進(jìn)程阻塞。，申請資源的進(jìn)程阻塞。系統(tǒng)的安全狀態(tài)：系統(tǒng)的安全狀態(tài)： 4.7 4.7 死鎖的預(yù)防和避免死鎖的預(yù)防和避免二、避免死鎖二、避免死鎖安全狀態(tài)：安全狀態(tài)：指系

51、統(tǒng)能按某種順序如指系統(tǒng)能按某種順序如（稱序列稱序列為安全序列），來為每個進(jìn)程分配其所需資源，為安全序列），來為每個進(jìn)程分配其所需資源， 直至最大需求，使每個進(jìn)程都可順序完成。若系統(tǒng)不存在直至最大需求，使每個進(jìn)程都可順序完成。若系統(tǒng)不存在 這樣一個安全序列，則稱系統(tǒng)處于這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)不安全狀態(tài)。例子：例子：系統(tǒng)有三個進(jìn)程系統(tǒng)有三個進(jìn)程P1、P2和和P3 ，共用，共用12臺磁帶機(jī)。臺磁帶機(jī)。 在在T0和和T1時刻，系統(tǒng)的資源分配情況分別如下表時刻，系統(tǒng)的資源分配情況分別如下表a和和b。進(jìn)程進(jìn)程 最大需求最大需求 已分配已分配 可用可用 P1 10 5 3 P2 4 2 P

52、3 9 2進(jìn)程進(jìn)程 最大需求最大需求 已分配已分配 可用可用 P1 10 5 2 P2 4 2 P3 9 3a ab b 4.7 4.7 死鎖的預(yù)防和避免死鎖的預(yù)防和避免二、避免死鎖二、避免死鎖結(jié)果：結(jié)果：T0時刻系統(tǒng)處于安全狀態(tài)。（安全序列時刻系統(tǒng)處于安全狀態(tài)。（安全序列）P1P2 P3可用可用 5(5)2(2)2(7)35(5)4(0)2(7)15(5)2(7)510(0)2(7)02(7)109(0)312結(jié)果：結(jié)果：T1時刻系統(tǒng)處于不安全狀態(tài)。時刻系統(tǒng)處于不安全狀態(tài)。P1P2 P3可用可用 5(5)2(2)3(6)25(5)4(0)3(6)05(5)3(6)4利用銀行家算法避免死鎖（利

53、用銀行家算法避免死鎖（Dijkstra提出提出) ) 4.7 4.7 死鎖的預(yù)防和避免死鎖的預(yù)防和避免二、避免死鎖二、避免死鎖數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：n個進(jìn)程（個進(jìn)程（P1,P2, ,Pn），），m類資源（類資源（R1,R2, ,Rm） 1.可利用資源向量可利用資源向量Available（m） Availablej表示表示Rj類資源的可用數(shù)目。類資源的可用數(shù)目。 2.最大需求矩陣最大需求矩陣Max（n m） Maxi, j表示進(jìn)程表示進(jìn)程Pi對對Rj類資源的最大需求量。類資源的最大需求量。 3.分配矩陣分配矩陣Allocation（n m） Allocation i, j表示已分配給進(jìn)程表示已分配

54、給進(jìn)程Pi的的Rj類資源的數(shù)目。類資源的數(shù)目。 4.需求矩陣需求矩陣Need（n m） Need i, j表示進(jìn)程表示進(jìn)程Pi對對Rj類資源的剩余需求量。類資源的剩余需求量。 5.Requesti ：進(jìn)程進(jìn)程Pi的請求向量的請求向量 4.7 4.7 死鎖的預(yù)防和避免死鎖的預(yù)防和避免二、避免死鎖二、避免死鎖銀行家算法：銀行家算法：進(jìn)程進(jìn)程Pi發(fā)出資源請求發(fā)出資源請求RequestiRequesti Needi ?Requesti Availablei ? 試分配：試分配： Available:= Available Requesti Allocationi:= Allocationi + Req

55、uestiNeedi:= Needi Requesti 執(zhí)行安全性算法，檢查分配后的系統(tǒng)狀態(tài)執(zhí)行安全性算法，檢查分配后的系統(tǒng)狀態(tài)正式分配正式分配將試分配作廢；將試分配作廢；恢復(fù)原資源分配狀態(tài)；恢復(fù)原資源分配狀態(tài)；進(jìn)程進(jìn)程Pi阻塞。阻塞。狀態(tài)安全狀態(tài)安全是是是是狀態(tài)狀態(tài)不安全不安全錯誤錯誤否否否否進(jìn)程進(jìn)程Pi阻塞阻塞 4.7 4.7 死鎖的預(yù)防和避免死鎖的預(yù)防和避免二、避免死鎖二、避免死鎖安全性算法：安全性算法：Work:=Available;Finish i :=false ( i=1,2,n);找一滿足下列條件的進(jìn)程：找一滿足下列條件的進(jìn)程：Finish i =false 且且 Needi

56、Work Work:=Work+Allocationi ; Finish i :=true; 所有進(jìn)程的所有進(jìn)程的Finish i =true？找到找到找不到找不到是是不是不是系統(tǒng)系統(tǒng)狀態(tài)狀態(tài)安全安全系統(tǒng)系統(tǒng)狀態(tài)狀態(tài)不安全不安全 4.7 4.7 死鎖的預(yù)防和避免死鎖的預(yù)防和避免二、避免死鎖二、避免死鎖例：例：系統(tǒng)中有五個進(jìn)程系統(tǒng)中有五個進(jìn)程 P0 , P1 , P2 , P3 , P4和三類資源和三類資源A , B , C， 每類資源的數(shù)量分別為每類資源的數(shù)量分別為10、5、7，在在T0時刻的資源分配情時刻的資源分配情 況如下表。問：況如下表。問：P1發(fā)出請求向量發(fā)出請求向量Request1

57、(1 ,0 ,2)，能否分配？，能否分配？Process Max Allocation Need Available A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2 0 0 1 2 2 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 4.7 4.7 死鎖的預(yù)防和避免死鎖的預(yù)防和避免二、避免死鎖二、避免死鎖結(jié)果：結(jié)果：因分配后的因分配后的系統(tǒng)狀態(tài)安全，故可以系統(tǒng)狀態(tài)安全，故可以 立即將立即將P1所申請的資源分配給它。所申請的資源分配給它。 Pr

58、ocess Max Allocation Need Available P0 7 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2 0 0 1 2 2 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 Request1 (1 ,0 ,2)試分配試分配（結(jié)果見（結(jié)果見綠字綠字）2 3 00 2 03 0 2安全性算法：安全性算法：Work= 2 3 0 Finish = falsefalsefalsefalsefalsetrue5 3 27 4 3true7 4 5true10 4 7true10 5 7

59、true一、死鎖的檢測一、死鎖的檢測二、二、死鎖的解除死鎖的解除4.8 4.8 死鎖的檢測與解除死鎖的檢測與解除資源分配圖資源分配圖RAG（Resource Allocation Graph） 4.8 4.8 死鎖的檢測與解除死鎖的檢測與解除一、死鎖的檢測一、死鎖的檢測 RAG=(N,E)，其中其中: : 結(jié)點(diǎn)集結(jié)點(diǎn)集N=P R 進(jìn)程結(jié)點(diǎn)子集進(jìn)程結(jié)點(diǎn)子集P=p1,p2, ,pn，用，用 表示。表示。 資源結(jié)點(diǎn)子集資源結(jié)點(diǎn)子集R=r1,r2, ,rm，用，用 表示，每表示，每 類資源中的一個單位用一個類資源中的一個單位用一個 表示。表示。 請求邊請求邊 ：進(jìn)程請求一個單位的資：進(jìn)程請求一個單位的

60、資 邊集邊集E包括包括 源并正在等待。源并正在等待。 分配邊分配邊 ：一個單位的資源已分配：一個單位的資源已分配 給進(jìn)程。給進(jìn)程。pirjrjpi死鎖定理死鎖定理 4.8 4.8 死鎖的檢測與解除死鎖的檢測與解除一、死鎖的檢測一、死鎖的檢測死鎖定理：死鎖定理：S為為死鎖死鎖狀態(tài)的充分條件是，當(dāng)且僅當(dāng)狀態(tài)的充分條件是，當(dāng)且僅當(dāng)S狀態(tài)的資源狀態(tài)的資源 分配圖是分配圖是不可完全簡化不可完全簡化的。的。RAG的簡化過程：的簡化過程： 1.找只有分配邊而沒有請求邊相連的進(jìn)程結(jié)點(diǎn)，將其分配邊刪掉。找只有分配邊而沒有請求邊相連的進(jìn)程結(jié)點(diǎn)，將其分配邊刪掉。 2.找雖有請求邊，但請求邊可立即全部轉(zhuǎn)化成分配邊的進(jìn)