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

1、第四章第四章 調(diào)度與死鎖調(diào)度與死鎖4.1 調(diào)度的類型與模型調(diào)度的類型與模型4.2 調(diào)度算法調(diào)度算法4.3 實(shí)時(shí)系統(tǒng)中的調(diào)度實(shí)時(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)度）作用：作用：選擇外存上處于后備隊(duì)列中的一個(gè)或幾個(gè)作業(yè)調(diào)入內(nèi)存，選擇外存上處于后備隊(duì)列中的一個(gè)或幾個(gè)作業(yè)調(diào)入內(nèi)存，

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

3、時(shí)； 2. 系統(tǒng)負(fù)荷不足時(shí)。系統(tǒng)負(fù)荷不足時(shí)。執(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)度）作用：作用：從就緒隊(duì)列中選擇一個(gè)進(jìn)程，然后，由分派程序?qū)⑻幚頇C(jī)從就緒隊(duì)列中選擇一個(gè)進(jìn)程，然后，由分派程序?qū)⑻幚頇C(jī) 分配給該進(jìn)程。分配給該進(jìn)程。使用系統(tǒng)：使用系統(tǒng)：各種系統(tǒng)均需要。各種系統(tǒng)均需要。進(jìn)程調(diào)度時(shí)只決定：進(jìn)程調(diào)度時(shí)只決定： 選擇哪個(gè)就緒進(jìn)程：取決于進(jìn)程調(diào)度算法。選擇哪個(gè)就緒進(jìn)程：取決于進(jìn)程調(diào)度算法。執(zhí)行頻率：執(zhí)行頻率：幾十毫秒一次。幾十毫秒

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

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

6、進(jìn)程， 將已分配給該進(jìn)程的處理機(jī)，重新分配給另一進(jìn)程。（即在將已分配給該進(jìn)程的處理機(jī)，重新分配給另一進(jìn)程。（即在 情況情況1、2、3、4時(shí)均可調(diào)度）時(shí)均可調(diào)度） 時(shí)間片原則時(shí)間片原則 搶占原則搶占原則 優(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)度隊(duì)列模型調(diào)度的調(diào)度隊(duì)列模型阻阻 塞塞 隊(duì)隊(duì) 列列 1 1就就 緒緒 隊(duì)隊(duì) 列列CPU進(jìn)程調(diào)度進(jìn)程調(diào)度進(jìn)程完成進(jìn)程完成交互用戶交互用戶等待事件等待事件1 1事件出現(xiàn)事件出現(xiàn)時(shí)間片用完時(shí)間片用完阻阻 塞塞 隊(duì)隊(duì) 列列 2 2等待事件等待事件2 2阻阻 塞塞 隊(duì)隊(duì) 列列 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)度隊(duì)列模型調(diào)度的調(diào)度隊(duì)列模型阻阻 塞塞 隊(duì)隊(duì) 列列 1 1就就 緒緒 隊(duì)隊(duì) 列列CPU進(jìn)程調(diào)度進(jìn)程調(diào)度進(jìn)程完成進(jìn)程完成后備隊(duì)列后備隊(duì)列等待事件1事件出現(xiàn)時(shí)

9、間片用完時(shí)間片用完阻阻 塞塞 隊(duì)隊(duì) 列列 2 2等待事件2阻阻 塞塞 隊(duì)隊(duì) 列列 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)度算法三、時(shí)間片輪轉(zhuǎn)調(diào)度算法三、時(shí)間片輪轉(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)度算法六、多級隊(duì)列調(diào)度六、多級隊(duì)列調(diào)度七、多級反饋隊(duì)列調(diào)度算法七、多級反饋隊(duì)列調(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è)隊(duì)列、就緒隊(duì)列按后備作業(yè)隊(duì)列、就緒隊(duì)列按FIFO排列，調(diào)度時(shí)選擇處于排列，調(diào)度時(shí)選擇處于 隊(duì)首的作業(yè)或進(jìn)程。隊(duì)首的作業(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á)時(shí)間到達(dá)時(shí)間 服務(wù)時(shí)間服務(wù)時(shí)間 A 0 4 B 1 5 C 2 2 D 3 4A B C D0 4 9 11 15 0 4 9 11 15 開始時(shí)間開始時(shí)間 完成時(shí)間完成時(shí)間 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間 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è)隊(duì)列、就緒隊(duì)列中選擇估從后備作業(yè)隊(duì)

12、列、就緒隊(duì)列中選擇估 計(jì)運(yùn)行時(shí)間最短的作業(yè)或進(jìn)程。計(jì)運(yùn)行時(shí)間最短的作業(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）估計(jì)運(yùn)行時(shí)間很難準(zhǔn)確獲得。）估計(jì)運(yùn)行時(shí)間很難準(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á)時(shí)間到達(dá)時(shí)間 服務(wù)時(shí)間服務(wù)時(shí)間 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 開始時(shí)間開始時(shí)間 完成時(shí)間完成時(shí)間 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間 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á)時(shí)間到達(dá)時(shí)間 服務(wù)時(shí)間服務(wù)時(shí)間 A 0 3 B 0 5 C 0 3 D 0 4 E 8 3搶占方式搶占方式1 1、基于最短服務(wù)時(shí)間搶占、基于最短服務(wù)時(shí)間

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ù)時(shí)間搶占、基于最短剩余服務(wù)時(shí)間搶占：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)度（搶占方式）。主要為分時(shí)系統(tǒng)設(shè)計(jì)。主要為分時(shí)系統(tǒng)設(shè)計(jì)。就緒隊(duì)列按就緒隊(duì)列按FIFO排列，調(diào)度時(shí)排列，調(diào)度時(shí)選擇隊(duì)首進(jìn)程。但該進(jìn)程選擇隊(duì)首進(jìn)程。但該進(jìn)程 占用占用CPU至多執(zhí)行一個(gè)時(shí)

15、間片，便放棄至多執(zhí)行一個(gè)時(shí)間片，便放棄CPU。例：例： 4.2 4.2 調(diào)度算法調(diào)度算法三、時(shí)間片輪轉(zhuǎn)調(diào)度算法三、時(shí)間片輪轉(zhuǎn)調(diào)度算法關(guān)鍵：時(shí)間片大小的確定關(guān)鍵：時(shí)間片大小的確定 太大：退化為太大：退化為FCFS 太?。合到y(tǒng)效率降低太?。合到y(tǒng)效率降低特點(diǎn)：假設(shè)所有進(jìn)程都是同等重要的。特點(diǎn)：假設(shè)所有進(jìn)程都是同等重要的。 4.2 4.2 調(diào)度算法調(diào)度算法三、時(shí)間片輪轉(zhuǎn)調(diào)度算法（例）三、時(shí)間片輪轉(zhuǎn)調(diào)度算法（例）進(jìn)程名進(jìn)程名 到達(dá)時(shí)間到達(dá)時(shí)間 服務(wù)時(shí)間服務(wù)時(shí)間 A 0 4 B 0 5 C 0 2 D 0 4開始時(shí)間開始時(shí)間 完成時(shí)間完成時(shí)間 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間 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 時(shí)間片時(shí)間片=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)程時(shí)確定，進(jìn)程運(yùn)行期間保持不變。靜態(tài)優(yōu)先權(quán)：創(chuàng)建進(jìn)程時(shí)確定，進(jìn)程運(yùn)行期間保持不變。 簡單易行，系統(tǒng)開銷小，但不夠精確

17、。簡單易行，系統(tǒng)開銷小，但不夠精確。 2.2.動態(tài)優(yōu)先權(quán)：創(chuàng)建進(jìn)程時(shí)確定初值，運(yùn)行期間基于某種原則動動態(tài)優(yōu)先權(quán)：創(chuàng)建進(jìn)程時(shí)確定初值，運(yùn)行期間基于某種原則動 態(tài)改變。例如，優(yōu)先權(quán)可隨占用態(tài)改變。例如，優(yōu)先權(quán)可隨占用CPUCPU時(shí)間加長而降時(shí)間加長而降 低。低。 靈活，調(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á)時(shí)間到達(dá)時(shí)間 服務(wù)時(shí)間服務(wù)時(shí)間 優(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+等待時(shí)間等待時(shí)間/ /要求服務(wù)時(shí)間要求服務(wù)時(shí)間例：例： 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ù)時(shí)間優(yōu)點(diǎn)：既照顧了作業(yè)到來的先后，又考慮了要求服務(wù)時(shí)間 的長短，是的長短，是FCFS和和SJF的很好的折衷。的很好的折衷。 缺點(diǎn)：算法較為復(fù)雜；每次調(diào)度時(shí)，均要重新計(jì)算響應(yīng)比。缺點(diǎn)：算法較為復(fù)雜；每次調(diào)度

19、時(shí)，均要重新計(jì)算響應(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á)時(shí)間到達(dá)時(shí)間8:008:309:30服務(wù)時(shí)間服務(wù)時(shí)間2小時(shí)小時(shí)1小時(shí)小時(shí)0.25小時(shí)小時(shí)三個(gè)作業(yè)在一臺處理機(jī)上單道運(yùn)行，三個(gè)作業(yè)在一臺處理機(jī)上單道運(yùn)行，9:40 9:40 進(jìn)行作業(yè)調(diào)度，問三個(gè)作業(yè)的執(zhí)進(jìn)行作業(yè)調(diào)度，問三個(gè)作業(yè)的執(zhí)行次序？行次序？9:40 9:40 調(diào)度時(shí)：調(diào)度時(shí)：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)度時(shí)：完成）調(diào)度時(shí)：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ì)和類型將就緒隊(duì)列分為若干子隊(duì)列，每個(gè)就緒按性質(zhì)和類型將就緒隊(duì)列分為若干子隊(duì)列，每個(gè)就緒 進(jìn)程固定地分屬于一個(gè)子隊(duì)列，每個(gè)隊(duì)列有自己的調(diào)進(jìn)程固定地分屬于一個(gè)子隊(duì)列，每個(gè)隊(duì)列有自己的

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

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

23、系統(tǒng)來說最重要的要求就是實(shí)時(shí)操作系統(tǒng)必須有滿足在一個(gè)事先定義好的時(shí)間限制中對外部或內(nèi)部的事件進(jìn)滿足在一個(gè)事先定義好的時(shí)間限制中對外部或內(nèi)部的事件進(jìn)行響應(yīng)和處理的能力。行響應(yīng)和處理的能力。實(shí)時(shí)系統(tǒng)可以定義為實(shí)時(shí)系統(tǒng)可以定義為“一個(gè)能夠在事先指定或確定的時(shí)間一個(gè)能夠在事先指定或確定的時(shí)間內(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í)時(shí)系統(tǒng)的要求一、對實(shí)時(shí)系統(tǒng)的要求由于實(shí)時(shí)系統(tǒng)在設(shè)計(jì)時(shí)與應(yīng)用的關(guān)系非常強(qiáng)，所以有許多由于實(shí)時(shí)系統(tǒng)在設(shè)計(jì)時(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ī)飛入一個(gè)空中交通管制的的或者是突發(fā)事件。比如一架客機(jī)飛入一個(gè)空中交通管制的管制范圍所產(chǎn)生的事件。管制范圍所產(chǎn)生的事件。一、對實(shí)時(shí)系統(tǒng)的要求一、對實(shí)時(shí)系統(tǒng)的要求方法二方法二 分為硬實(shí)時(shí)和軟實(shí)時(shí)（分為硬實(shí)時(shí)和軟實(shí)時(shí)（hard real_timehard real_time和和soft soft realtimerealtime）。硬實(shí)時(shí)系統(tǒng)就是系統(tǒng)必須及時(shí)的對事件作出反）。硬實(shí)時(shí)系統(tǒng)就是系統(tǒng)必須及時(shí)的對事件作出反應(yīng)，絕對不能發(fā)生錯(cuò)過事件處理

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

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

28、算資源的理的響應(yīng)速度，對每個(gè)系統(tǒng)用戶相對公平的進(jìn)行計(jì)算資源的分配。然而在實(shí)時(shí)系統(tǒng)中，以上這些要求都不再適用或者是分配。然而在實(shí)時(shí)系統(tǒng)中，以上這些要求都不再適用或者是不再占重要位置。實(shí)時(shí)系統(tǒng)中系統(tǒng)的一切動作都以實(shí)時(shí)任務(wù)不再占重要位置。實(shí)時(shí)系統(tǒng)中系統(tǒng)的一切動作都以實(shí)時(shí)任務(wù)為中心。為次，系統(tǒng)應(yīng)該向調(diào)度程序提供的一些是信息：為中心。為次，系統(tǒng)應(yīng)該向調(diào)度程序提供的一些是信息：就緒時(shí)間就緒時(shí)間開始截止時(shí)間和完成截止時(shí)間開始截止時(shí)間和完成截止時(shí)間處理時(shí)間處理時(shí)間資源要求資源要求優(yōu)先級優(yōu)先級子任務(wù)結(jié)構(gòu)子任務(wù)結(jié)構(gòu)一、對實(shí)時(shí)系統(tǒng)的要求一、對實(shí)時(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)時(shí)，系統(tǒng)可以及時(shí)響應(yīng)。系統(tǒng)需具有快速緊迫事件出現(xiàn)時(shí)，系統(tǒng)可以及時(shí)響應(yīng)。系統(tǒng)需具有快速硬件中斷機(jī)構(gòu)，使中斷間隔盡量短。硬件中斷機(jī)構(gòu)，使中斷間隔盡量短。z 快速任務(wù)分派快速任務(wù)分派任務(wù)的切換應(yīng)該盡量快速，使得消耗的時(shí)間盡量少任務(wù)的切換應(yīng)該盡量快速，使得消耗的時(shí)間盡量少二、二、實(shí)時(shí)調(diào)度算法實(shí)時(shí)調(diào)度算法

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

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

32、先級隊(duì)列算法。這種算法從FIFOFIFO發(fā)展而來。給每個(gè)任發(fā)展而來。給每個(gè)任務(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ù)很可能無法滿足時(shí)間的正確性。而且對低優(yōu)先級的任務(wù)來說等待能無法滿足時(shí)間的正確性。而且對低優(yōu)先級的任務(wù)來說等待的時(shí)間是無法預(yù)知的。的時(shí)間是無法預(yù)知的。我們無法知道在什么情況下會發(fā)生時(shí)間正確性上的錯(cuò)誤。我們無法知道在什么情況下會發(fā)生時(shí)間正確性上的錯(cuò)誤。而且必須在設(shè)計(jì)時(shí)仔細(xì)的檢查任務(wù)優(yōu)先級的設(shè)定，要保證不而且必須在設(shè)

33、計(jì)時(shí)仔細(xì)的檢查任務(wù)優(yōu)先級的設(shè)定，要保證不會因?yàn)榈蛢?yōu)先級的任務(wù)無法按時(shí)完成而破壞整個(gè)系統(tǒng)的完整會因?yàn)榈蛢?yōu)先級的任務(wù)無法按時(shí)完成而破壞整個(gè)系統(tǒng)的完整性。這個(gè)算法也是與特定應(yīng)用有關(guān)的。當(dāng)環(huán)境或情況變化時(shí)性。這個(gè)算法也是與特定應(yīng)用有關(guān)的。當(dāng)環(huán)境或情況變化時(shí)系統(tǒng)無法隨之變化。系統(tǒng)無法隨之變化。二、二、實(shí)時(shí)調(diào)度算法實(shí)時(shí)調(diào)度算法z 基于時(shí)鐘中斷搶占的優(yōu)先權(quán)算法基于時(shí)鐘中斷搶占的優(yōu)先權(quán)算法這種算法用于搶先式多任務(wù)的實(shí)時(shí)操作系統(tǒng)。該算法的這種算法用于搶先式多任務(wù)的實(shí)時(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)行時(shí)不能搶先；在高優(yōu)先級的任務(wù)運(yùn)行時(shí)不能搶先；CPUCPU由高優(yōu)先級進(jìn)程獨(dú)由高優(yōu)先級進(jìn)程獨(dú)占。占。當(dāng)中斷發(fā)生時(shí)，正在運(yùn)行的任務(wù)被中斷，進(jìn)入中斷處理。當(dāng)中斷發(fā)生時(shí)，正在運(yùn)行的任務(wù)被中斷，進(jìn)入中斷處理。如果中斷引起的操作是屬于一個(gè)較低優(yōu)先級的任務(wù)的，那么如果中斷引起的操作是屬于一個(gè)較低優(yōu)先級的任務(wù)的，那么為了保證中斷被及時(shí)的處理，此低優(yōu)先級進(jìn)程暫時(shí)繼承原來為了保證中斷被及時(shí)的處理，此低優(yōu)先級進(jìn)程暫時(shí)繼承原來當(dāng)中斷發(fā)生時(shí)正在運(yùn)行的高優(yōu)先級任務(wù)的優(yōu)先級。當(dāng)處理完當(dāng)中斷發(fā)生時(shí)正在運(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í)時(shí)調(diào)度算法實(shí)時(shí)調(diào)度算法z 立即搶占的優(yōu)先權(quán)算法立即搶占的優(yōu)先權(quán)算法與算法三的區(qū)別在于立即進(jìn)行調(diào)度，而不等待時(shí)鐘的中與算法三的區(qū)別在于立即進(jìn)行調(diào)度，而不等待時(shí)鐘的中斷發(fā)生。斷發(fā)生。三、實(shí)時(shí)調(diào)度實(shí)例三、實(shí)時(shí)調(diào)度實(shí)例1.具有開始截止時(shí)間的非周期實(shí)時(shí)任務(wù)的調(diào)度具有開始截止時(shí)間的非周期實(shí)時(shí)任務(wù)的調(diào)度 在事先知道各任務(wù)的開始截止時(shí)間，且對調(diào)度時(shí)延不太在事先知道各任務(wù)的開始截止時(shí)間，且對調(diào)度時(shí)延不太嚴(yán)格的請情況下，可采用最早

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

37、來自一次。處理每個(gè)來自A的數(shù)據(jù)樣本需要的數(shù)據(jù)樣本需要10ms,處理每個(gè)來自處理每個(gè)來自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á)時(shí)間到達(dá)時(shí)間執(zhí)行時(shí)間執(zhí)行時(shí)間最后結(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í)時(shí)系統(tǒng)的其他問題實(shí)時(shí)系統(tǒng)的內(nèi)存和外圍設(shè)備管理實(shí)時(shí)系統(tǒng)的內(nèi)存和外圍設(shè)備管理實(shí)時(shí)系統(tǒng)的通信實(shí)時(shí)系統(tǒng)的通信實(shí)時(shí)操作系統(tǒng)的內(nèi)核實(shí)時(shí)操作系統(tǒng)的內(nèi)核一、產(chǎn)生死鎖的原因一、產(chǎn)生死鎖的原因二、二、產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件三、處理死鎖的四種策略三、處理死鎖的四種策略四、鴕鳥算法四、鴕鳥算法.死鎖（死鎖（Deadlock）：）：假若在一個(gè)進(jìn)程集合中的每個(gè)進(jìn)程都在假若在一個(gè)進(jìn)程集合中的每個(gè)進(jìn)程都在 等待只能由該集合中的其它一個(gè)進(jìn)程才能引發(fā)的事件，等待只能由該集合中的其它一個(gè)進(jìn)程才能引發(fā)的事件， 那么這種狀態(tài)被看成是死鎖。那么這種狀態(tài)被看成是死鎖。.多數(shù)情況下，進(jìn)程是在等待該集合中的另

39、一個(gè)進(jìn)程正占有的多數(shù)情況下，進(jìn)程是在等待該集合中的另一個(gè)進(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)生死鎖的原因資源：資源：在任何時(shí)候都只能被一個(gè)進(jìn)程使用的任何對象。在任何時(shí)候都只能被一個(gè)進(jìn)程使用的任何對象。資源分類：資源分類： 可剝奪資源：可從擁有它的進(jìn)程中剝奪而不會產(chǎn)生任何副作

40、用?？蓜儕Z資源：可從擁有它的進(jìn)程中剝奪而不會產(chǎn)生任何副作用。 不可剝奪資源：從擁有它的進(jìn)程中剝奪會產(chǎn)生錯(cuò)誤。不可剝奪資源：從擁有它的進(jìn)程中剝奪會產(chǎn)生錯(cuò)誤。資源使用順序：資源使用順序： 申請資源申請資源使用資源使用資源釋放資源。釋放資源。 l 某進(jìn)程申請資源失敗，則轉(zhuǎn)為阻塞狀態(tài)，進(jìn)入資源等待隊(duì)列。某進(jìn)程申請資源失敗，則轉(zhuǎn)為阻塞狀態(tài)，進(jìn)入資源等待隊(duì)列。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í)行時(shí)，執(zhí)行時(shí)，順序?yàn)轫樞驗(yàn)?234或或3412 不會出錯(cuò)。但為不會出錯(cuò)。但為 1324 時(shí)，會死鎖。時(shí)，會死鎖。進(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í)行時(shí)，執(zhí)行時(shí)，順序?yàn)轫樞驗(yàn)?或或2或或3時(shí)，不會出錯(cuò)。時(shí)，不會出錯(cuò)。但為但為 4 時(shí)，會時(shí)，會死鎖。死鎖。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互斥條件互斥條件 每個(gè)資源要么已分配給了一個(gè)進(jìn)程，要么空閑。每個(gè)資源要么已分配給了一個(gè)進(jìn)程，要么空閑。請求和保持條件請求和保持條件 已經(jīng)得到資源的進(jìn)程可以申請新的資源，申請失敗時(shí)變?yōu)樽枞麪钜呀?jīng)得到資源的進(jìn)程可以申請新的資源，申請失敗時(shí)變?yōu)樽枞麪?態(tài)，此時(shí)它仍然保持著原有資源不放。態(tài)，此時(shí)它仍然保持著原有資源不放。不剝奪條件不剝奪條件 已經(jīng)分配給一個(gè)進(jìn)程的資源不能被剝奪，只能由占有它的進(jìn)程主已經(jīng)分配給一個(gè)進(jìn)程的資源不能被剝奪，只能由占有它的進(jìn)程主 動釋放。動釋放。環(huán)路等待

44、條件環(huán)路等待條件 系統(tǒng)一定有兩個(gè)或兩個(gè)以上的進(jìn)程組成的一條環(huán)路，該環(huán)路中的系統(tǒng)一定有兩個(gè)或兩個(gè)以上的進(jìn)程組成的一條環(huán)路，該環(huán)路中的 每個(gè)進(jìn)程都在等待著相鄰進(jìn)程正占用著的資源。每個(gè)進(jìn)程都在等待著相鄰進(jìn)程正占用著的資源。 4.6 4.6 死鎖的基本概念死鎖的基本概念二、產(chǎn)生死鎖的必要條件二、產(chǎn)生死鎖的必要條件預(yù)防死鎖預(yù)防死鎖 通過破除死鎖的四個(gè)必要條件之一，來防止通過破除死鎖的四個(gè)必要條件之一，來防止 死鎖產(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ā) 生時(shí)又無法知道（因不檢測），造成系統(tǒng)崩潰，需要重生時(shí)又無法知道（因不檢測），造成系

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

49、候只能占用一個(gè)資源。要用第二保證每個(gè)進(jìn)程在任何時(shí)候只能占用一個(gè)資源。要用第二 個(gè)，必須先釋放第一個(gè)。個(gè)，必須先釋放第一個(gè)。方法方法2 2：將系統(tǒng)中所有資源賦予一個(gè)全局編號，進(jìn)程申請資源時(shí)，將系統(tǒng)中所有資源賦予一個(gè)全局編號，進(jìn)程申請資源時(shí)， 必須按編號遞增順序進(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)行資源分配時(shí)，首先檢測一下每次進(jìn)行資源分配時(shí)，首先檢測一下資源分配后資源分配后系統(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)能按某種順序如（稱序列稱序列為安全序列），來為每個(gè)進(jìn)程分配其所需資源，為安全序列），來為每個(gè)進(jìn)程分配其所需資源， 直至最大需求，使每個(gè)進(jìn)程都可順序完成。若系統(tǒng)不存在直至最大需求，使每個(gè)進(jìn)程都可順序完成。若系統(tǒng)不存在 這樣一個(gè)安全序列，則稱系統(tǒng)處于這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)不安全狀態(tài)。例子：例子：系統(tǒng)有三個(gè)進(jìn)程系統(tǒng)有三個(gè)進(jìn)程P1、P2和和P3 ，共用，共用12臺磁帶機(jī)。臺磁帶機(jī)。 在在T0和和T1時(shí)刻，系統(tǒng)的資源分配情況分別如下表時(shí)刻，系統(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時(shí)刻系統(tǒng)處于安全狀態(tài)。（安全序列時(shí)刻系統(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時(shí)刻系統(tǒng)處于不安全狀態(tài)。時(shí)刻系統(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個(gè)進(jìn)程（個(gè)進(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)不安全不安全錯(cuò)誤錯(cuò)誤否否否否進(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)中有五個(gè)進(jìn)程系統(tǒng)中有五個(gè)進(jìn)程 P0 , P1 , P2 , P3 , P4和三類資源和三類資源A , B , C， 每類資源的數(shù)量分別為每類資源的數(shù)量分別為10、5、7，在在T0時(shí)刻的資源分配情時(shí)刻的資源分配情 況如下表。問：況如下表。問：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，用，用 表示，每表示，每 類資源中的一個(gè)單位用一個(gè)類資源中的一個(gè)單位用一個(gè) 表示。表示。 請求邊請求邊 ：進(jìn)程請求一個(gè)單位的資：進(jìn)程請求一個(gè)單位的

60、資 邊集邊集E包括包括 源并正在等待。源并正在等待。 分配邊分配邊 ：一個(gè)單位的資源已分配：一個(gè)單位的資源已分配 給進(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)