操作系統(tǒng)講義第三章

1、2022年3月17日操作系統(tǒng)講義1第三章第三章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖2022年3月17日第二章 進(jìn)程管理2主要內(nèi)容主要內(nèi)容 3.1 處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次 3.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則 3.3 幾種調(diào)度算法幾種調(diào)度算法 3.4 實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度 3.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法 3.7 死鎖的檢測和解除死鎖的檢測和解除2022年3月17日第二章 進(jìn)程管理33.1 處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次 作業(yè)的基本概念作業(yè)的基本概念1. 高級調(diào)度（高級調(diào)度（High Level Scheduli

2、ng） 主要功能：根據(jù)某種算法，把外存中把處于后備隊(duì)列中的那些作業(yè)調(diào)入內(nèi)存，當(dāng)作業(yè)完成時(shí)做善后處理。 作業(yè)（Job）：包含通常的程序和數(shù)據(jù)，并且配有作業(yè)說明書； 作業(yè)步（Job Step）：“編譯” - “連接裝配” - “運(yùn)行”； 作業(yè)流：若干個(gè)作業(yè)在系統(tǒng)外存形成的輸入流。 作業(yè)控制塊作業(yè)控制塊JCB（Job Control Block） 通常包含：作業(yè)標(biāo)識、用戶名稱、用戶賬戶、作業(yè)類型（CPU繁忙，I/O繁忙，批量型，終端型）、作業(yè)狀態(tài)、調(diào)度信息（優(yōu)先級，作業(yè)運(yùn)行時(shí)間）、資源需求（運(yùn)行時(shí)間，內(nèi)存，I/O類型數(shù)量）、進(jìn)入系統(tǒng)時(shí)間、開始處理時(shí)間、作業(yè)完成時(shí)間、作業(yè)退出時(shí)間、資源使用情況。202

3、2年3月17日第二章 進(jìn)程管理43.1 處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次1. 高級調(diào)度（高級調(diào)度（High Level Scheduling） 作業(yè)調(diào)度：作業(yè)調(diào)度：是根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)能否滿足用戶作業(yè)的資源需求，以及按照一定的算法，從外存后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)存，為它們創(chuàng)建進(jìn)程、分配必要的資源，然后將進(jìn)程插入就緒隊(duì)列，準(zhǔn)備執(zhí)行。 目的：目的：提高內(nèi)存利用率和系統(tǒng)吞吐量，使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用內(nèi)存，把它們調(diào)至外存（存儲管理中的對換功能）。 1）接收多少個(gè)作業(yè)到內(nèi)存：取決于多道程序度 2）接收哪些作業(yè)：取決于調(diào)度算法 最簡單：先來先服務(wù)調(diào)度算法 最常用：短作業(yè)優(yōu)先調(diào)度

4、算法 較常用：優(yōu)先級調(diào)度算法 比較好：響應(yīng)比高者優(yōu)先調(diào)度算法2. 中級調(diào)度中級調(diào)度（Intermediate Level Scheduling）2022年3月17日第二章 進(jìn)程管理53.1 處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次3. 低級調(diào)度（低級調(diào)度（Low Level Scheduling） 它所調(diào)度的對象是進(jìn)程（或內(nèi)核級線程），當(dāng)CPU需要重新分配時(shí)，利用一定的算法把它分配給進(jìn)程，它是最基本的調(diào)度。進(jìn)程調(diào)度的功能進(jìn)程調(diào)度的功能 （1）保存處理機(jī)的現(xiàn)場信息； （2）按照某種算法選擇進(jìn)程（如優(yōu)先數(shù)算法，輪轉(zhuǎn)算法） （3）把處理器分配給進(jìn)程。進(jìn)程調(diào)度的三個(gè)基本機(jī)制進(jìn)程調(diào)度的三個(gè)基本機(jī)制 （1）排隊(duì)器

5、：事先將系統(tǒng)所有就緒進(jìn)程排成一個(gè)或多個(gè)隊(duì)列，方便調(diào)度程序最快找到它； （2）分派器（分派程序）：把進(jìn)程調(diào)度程序選定的進(jìn)程從就緒隊(duì)列移出，切換上下文，然后把CPU分配給它； （3）上下文切換機(jī)制：保存當(dāng)前程序的上下文，裝入分派程序的上下文；移出分派程序，裝入新選進(jìn)程的CPU信息；2022年3月17日第二章 進(jìn)程管理63.1 處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式 3.低級調(diào)度（低級調(diào)度（Low Level Scheduling）l非搶占方式：非搶占方式：一旦處理機(jī)分配給某個(gè)進(jìn)程，不管它要運(yùn)行多長時(shí)間，都讓它一直運(yùn)行下去，決不會因?yàn)槠渌蚨鴵屨颊谶\(yùn)行進(jìn)程的處理機(jī)。這種方式下引

6、起進(jìn)程調(diào)度的因素包括：執(zhí)行完畢或者發(fā)生某事件不能再執(zhí)行執(zhí)行進(jìn)程提出I/O請求而暫停執(zhí)行在進(jìn)程通信或者同步過程中執(zhí)行了某種原語操作，如P，Block等優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，系統(tǒng)開銷小，適用于大多數(shù)批處理系統(tǒng)；優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，系統(tǒng)開銷小，適用于大多數(shù)批處理系統(tǒng)；缺點(diǎn)：難以滿足緊急任務(wù)要求，可能造成難以預(yù)料的后果。缺點(diǎn)：難以滿足緊急任務(wù)要求，可能造成難以預(yù)料的后果。2022年3月17日第二章 進(jìn)程管理73.1 處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式 3.低級調(diào)度（低級調(diào)度（Low Level Scheduling）l搶占方式：搶占方式：允許調(diào)度程序根據(jù)某種原則某種原則去暫停某個(gè)正在執(zhí)行的

7、進(jìn)程，這些原則主要包括：優(yōu)先權(quán)原則：優(yōu)先權(quán)高的進(jìn)程可以搶占當(dāng)前優(yōu)先權(quán)低的進(jìn)程的CPU；短作業(yè)（進(jìn)程）優(yōu)先原則：短作業(yè)（進(jìn)程）可以搶占當(dāng)前較長作業(yè)（進(jìn)程的）CPU；時(shí)間片原則：時(shí)間片輪轉(zhuǎn)；優(yōu)點(diǎn)：防止一個(gè)長進(jìn)程長時(shí)間占用處理機(jī)，公平服務(wù)，適優(yōu)點(diǎn)：防止一個(gè)長進(jìn)程長時(shí)間占用處理機(jī)，公平服務(wù)，適合實(shí)時(shí)任務(wù)的需求；合實(shí)時(shí)任務(wù)的需求；缺點(diǎn)：需要付出較大的開銷。缺點(diǎn)：需要付出較大的開銷。2022年3月17日第二章 進(jìn)程管理83.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 通常在分時(shí)系統(tǒng)分時(shí)系統(tǒng)中只設(shè)置進(jìn)程調(diào)度，每個(gè)用戶建立一個(gè)進(jìn)程，系統(tǒng)利用堆棧、樹或者

8、鏈表來管理就緒進(jìn)程隊(duì)列，就緒進(jìn)程以就緒進(jìn)程以FIFO隊(duì)列隊(duì)列形式組織形式組織。 1. 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型進(jìn)程執(zhí)行時(shí)可能出現(xiàn)的三種情況：進(jìn)程執(zhí)行時(shí)可能出現(xiàn)的三種情況：在給定時(shí)間片完成，釋放處理機(jī)進(jìn)入完成狀態(tài)；本次時(shí)間片內(nèi)未完成，放入就緒隊(duì)列尾部；因?yàn)槟呈录蛔枞?，放入阻塞?duì)列。就 緒 隊(duì) 列CPU阻 塞 隊(duì) 列交互用戶時(shí)間片完進(jìn)程調(diào)度等待事件進(jìn)程完成事件出現(xiàn)2022年3月17日第二章 進(jìn)程管理93.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則具有高級和低級調(diào)度的調(diào)度隊(duì)列模型具有高級和低級調(diào)度的調(diào)度隊(duì)列模型 在批處理系統(tǒng)批處理系統(tǒng)中，作業(yè)調(diào)度按照一定的算法從外存的后備隊(duì)列選擇一批作業(yè)調(diào)入

9、內(nèi)存，建立進(jìn)程，送入就緒隊(duì)列，然后按照一定的進(jìn)程調(diào)度算法選擇進(jìn)程，分配CPU。 1. 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型就 緒 隊(duì) 列CPU阻 塞 隊(duì) 列作業(yè)調(diào)度時(shí)間片完進(jìn)程調(diào)度等待事件1進(jìn)程完成事件1出現(xiàn)隊(duì) 列后 備阻 塞 隊(duì) 列阻 塞 隊(duì) 列等待事件2等待事件n事件2出現(xiàn)事件n出現(xiàn)隊(duì)2022年3月17日第二章 進(jìn)程管理103.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則 1. 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型具有高級和低級調(diào)度的調(diào)度隊(duì)列模型的特點(diǎn)具有高級和低級調(diào)度的調(diào)度隊(duì)列模型的特點(diǎn)：（1）采用優(yōu)先權(quán)就緒隊(duì)列，優(yōu)先權(quán)就緒隊(duì)列，隊(duì)首進(jìn)程優(yōu)先權(quán)最高，或者采用無序 鏈表方式；（2）設(shè)置多個(gè)阻塞隊(duì)列，每個(gè)隊(duì)列對

10、應(yīng)于某一種進(jìn)程阻塞事件；2022年3月17日第二章 進(jìn)程管理113.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則同時(shí)具有三級調(diào)度的調(diào)度隊(duì)列模型同時(shí)具有三級調(diào)度的調(diào)度隊(duì)列模型 可把進(jìn)程的就緒狀態(tài)分成內(nèi)存就緒和外存就緒，類似地，阻塞狀態(tài)也可進(jìn)一步分成內(nèi)存阻塞和外存阻塞，調(diào)出操作調(diào)出操作可使進(jìn)程狀態(tài)由內(nèi)存就緒轉(zhuǎn)為外存就緒，內(nèi)存阻塞轉(zhuǎn)為外存阻塞；中級調(diào)度中級調(diào)度可使外存就緒轉(zhuǎn)為內(nèi)存就緒。 1. 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型就 緒 隊(duì) 列CPU緒 掛 起隊(duì) 列就作業(yè)調(diào)度時(shí)間片完進(jìn)程調(diào)度進(jìn)程完成事件出現(xiàn)隊(duì) 列后 備塞掛 隊(duì)隊(duì) 列阻阻 塞 隊(duì) 列等待事件起批量作業(yè)掛起事件出現(xiàn)中級調(diào)度中級調(diào)度2022年3月1

11、7日第二章 進(jìn)程管理123.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則 面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則 （1）周轉(zhuǎn)時(shí)間短（批處理系統(tǒng)）周轉(zhuǎn)時(shí)間短（批處理系統(tǒng)） 平均周轉(zhuǎn)時(shí)間T的計(jì)算如下： 平均帶權(quán)周轉(zhuǎn)時(shí)間W的計(jì)算如下： （2）響應(yīng)時(shí)間快（分時(shí)系統(tǒng)）：）響應(yīng)時(shí)間快（分時(shí)系統(tǒng)）：是指從用戶通過鍵盤提交一個(gè)請求開始，直到系統(tǒng)首次響應(yīng)為止的時(shí)間必須快； （3）截止時(shí)間的保證（實(shí)時(shí)系統(tǒng)）：）截止時(shí)間的保證（實(shí)時(shí)系統(tǒng)）：是指某任務(wù)必須開始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間必須有保證； （4）優(yōu)先權(quán)準(zhǔn)則：）優(yōu)先權(quán)準(zhǔn)則：遵循優(yōu)先權(quán)準(zhǔn)則讓某些緊急的作業(yè)得到及時(shí)處理。 2. 選擇調(diào)度方式和算法的若干準(zhǔn)則選擇

12、調(diào)度方式和算法的若干準(zhǔn)則niiTnT11nisiTTnW112022年3月17日第二章 進(jìn)程管理133.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則面向系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則 2. 選擇調(diào)度方式和算法的若干準(zhǔn)則選擇調(diào)度方式和算法的若干準(zhǔn)則（1）系統(tǒng)吞吐量高：）系統(tǒng)吞吐量高：這個(gè)是評價(jià)批處理系統(tǒng)性能的另一個(gè)重要指標(biāo)，因此是選擇批處理作業(yè)調(diào)度的重要準(zhǔn)則。吞吐量是指單位時(shí)間內(nèi)系統(tǒng)完成的作業(yè)數(shù)，它直接和作業(yè)的平均長度有關(guān)；（2）處理機(jī)利用率好：）處理機(jī)利用率好：CPU價(jià)格昂貴，利用率成為衡量系統(tǒng)性能的重要指標(biāo)；（3）各類資源的平衡利用：）各類資源的平衡利用：不僅要使處理機(jī)利用率高，還要有效地利用

13、其它各類資源，如內(nèi)存、外存和I/O設(shè)備，適當(dāng)?shù)恼{(diào)度方式和算法可以使系統(tǒng)中的各類資源處于忙碌狀態(tài)。2022年3月17日第二章 進(jìn)程管理143.3 調(diào)度算法調(diào)度算法是一種最簡單的調(diào)度算法，適用于作業(yè)調(diào)度和進(jìn)程調(diào)度，每次調(diào)度是一種最簡單的調(diào)度算法，適用于作業(yè)調(diào)度和進(jìn)程調(diào)度，每次調(diào)度都是從后備隊(duì)列中選擇一個(gè)或者多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它都是從后備隊(duì)列中選擇一個(gè)或者多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，分配資源，創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。們調(diào)入內(nèi)存，分配資源，創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。 1. 先來先服務(wù)調(diào)度算法先來先服務(wù)調(diào)度算法FCFS（First Come First Service）FC

14、FS算法比較有利于長作業(yè)（進(jìn)程），不利于短作業(yè)（進(jìn)程）算法比較有利于長作業(yè)（進(jìn)程），不利于短作業(yè)（進(jìn)程）進(jìn)程名進(jìn)程名到達(dá)到達(dá) 時(shí)間時(shí)間服務(wù)服務(wù) 時(shí)間時(shí)間開始執(zhí)開始執(zhí)行時(shí)間行時(shí)間完成完成 時(shí)間時(shí)間周轉(zhuǎn)周轉(zhuǎn) 時(shí)間時(shí)間帶權(quán)周帶權(quán)周轉(zhuǎn)時(shí)間轉(zhuǎn)時(shí)間A010111B110011011001C21101102100100D31001022021991.992022年3月17日第二章 進(jìn)程管理153.3 調(diào)度算法調(diào)度算法是指對短作業(yè)或者短進(jìn)程優(yōu)先調(diào)度的算法，適用于作業(yè)調(diào)度和是指對短作業(yè)或者短進(jìn)程優(yōu)先調(diào)度的算法，適用于作業(yè)調(diào)度和進(jìn)程調(diào)度，進(jìn)程調(diào)度，SJF算法就是從后備隊(duì)列中選擇一個(gè)運(yùn)行時(shí)間最短的算法就是從后備隊(duì)列

15、中選擇一個(gè)運(yùn)行時(shí)間最短的作業(yè)，然后把它們調(diào)入內(nèi)存運(yùn)行。作業(yè)，然后把它們調(diào)入內(nèi)存運(yùn)行。 2. 短作業(yè)優(yōu)先調(diào)度算法短作業(yè)優(yōu)先調(diào)度算法SJF（Short Job First）SJF的優(yōu)點(diǎn)：能有效地降低作業(yè)的平均等待時(shí)間，提高系統(tǒng)吞吐量；的優(yōu)點(diǎn)：能有效地降低作業(yè)的平均等待時(shí)間，提高系統(tǒng)吞吐量；進(jìn)程名進(jìn)程名到達(dá)到達(dá) 時(shí)間時(shí)間服務(wù)服務(wù) 時(shí)間時(shí)間開始執(zhí)開始執(zhí)行時(shí)間行時(shí)間完成完成 時(shí)間時(shí)間周轉(zhuǎn)周轉(zhuǎn) 時(shí)間時(shí)間帶權(quán)周帶權(quán)周轉(zhuǎn)時(shí)間轉(zhuǎn)時(shí)間A030331B145982C223531.5D35914112.2SJF的缺點(diǎn)的缺點(diǎn)： 1）對長作業(yè)不利；）對長作業(yè)不利；2）未考慮作業(yè)的緊迫度；）未考慮作業(yè)的緊迫度；3）用戶）用

16、戶估計(jì)執(zhí)行時(shí)間的不準(zhǔn)確性。估計(jì)執(zhí)行時(shí)間的不準(zhǔn)確性。2022年3月17日第二章 進(jìn)程管理163.3 調(diào)度算法調(diào)度算法 3. FCFS和和SJF的性能比較的性能比較算法算法進(jìn)程名進(jìn)程名ABCDE平平 均均到達(dá)時(shí)間到達(dá)時(shí)間01234服務(wù)時(shí)間服務(wù)時(shí)間43524FCFS完成時(shí)間完成時(shí)間47121418周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間461011149帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間1225.53.52.8SJF完成時(shí)間完成時(shí)間4918613周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間4816398帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間12.673.21.52.252.12022年3月17日第二章 進(jìn)程管理173.3 調(diào)度算法調(diào)度算法是為了照顧緊迫型緊迫型作業(yè)，使之在進(jìn)

17、入系統(tǒng)后便獲得優(yōu)先處理，該算法會把處理機(jī)分配給優(yōu)先級最高優(yōu)先級最高的作業(yè)（或者進(jìn)程）。 1）非搶占式優(yōu)先權(quán)調(diào)度算法）非搶占式優(yōu)先權(quán)調(diào)度算法，適用于批處理系統(tǒng)或?qū)崟r(shí)性要求不高的系統(tǒng)； 2）搶占式優(yōu)先權(quán)調(diào)度算法）搶占式優(yōu)先權(quán)調(diào)度算法，能更好地滿足緊迫作業(yè)，適合于嚴(yán)格的實(shí)時(shí)系統(tǒng)或者對性能要求較高的批處理和分時(shí)系統(tǒng)中。 4. 高優(yōu)先權(quán)優(yōu)先調(diào)度算法（高優(yōu)先權(quán)優(yōu)先調(diào)度算法（Priority Job First）2022年3月17日第二章 進(jìn)程管理183.3 調(diào)度算法調(diào)度算法 4. 高優(yōu)先權(quán)優(yōu)先調(diào)度算法（高優(yōu)先權(quán)優(yōu)先調(diào)度算法（Priority Job First）優(yōu)先權(quán)的類型靜態(tài)優(yōu)先權(quán)：靜態(tài)優(yōu)先權(quán)：創(chuàng)建進(jìn)程

18、時(shí)確定，在整個(gè)運(yùn)行期間保持不變；進(jìn)程類型，系統(tǒng)進(jìn)程要比用戶進(jìn)程優(yōu)先級高；進(jìn)程對資源的要求，要求少的優(yōu)先級高；用戶要求，用戶進(jìn)程的緊迫程度。優(yōu)點(diǎn)：簡單易行，系統(tǒng)開銷小缺點(diǎn)：不夠精確，可能使優(yōu)先權(quán)低的作業(yè)（進(jìn)程）長期得不到調(diào)度動態(tài)優(yōu)先權(quán)：動態(tài)優(yōu)先權(quán)：創(chuàng)建時(shí)賦予，可以隨著進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變，以便獲得更好的調(diào)度性能。優(yōu)點(diǎn)：使調(diào)度更加公平，調(diào)度性能高缺點(diǎn)：系統(tǒng)開銷稍大2022年3月17日第二章 進(jìn)程管理193.3 調(diào)度算法調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法 每個(gè)作業(yè)的優(yōu)先級動態(tài)計(jì)算，作業(yè)的優(yōu)先級隨等待時(shí)間的增加而不斷提高。 4. 高優(yōu)先權(quán)優(yōu)先調(diào)度算法（高優(yōu)先權(quán)優(yōu)先調(diào)度算法

19、（Priority Job First）結(jié)論：如果作業(yè)等待時(shí)間相同，要求服務(wù)時(shí)間越短，優(yōu)先級越高，該算法利于短作業(yè)；如果要求服務(wù)時(shí)間相同，那么等待時(shí)間越長，優(yōu)先權(quán)越高，它實(shí)現(xiàn)的是先來先服務(wù)；對于長作業(yè)，作業(yè)的優(yōu)先級隨著等待時(shí)間的增加而提高，如果等待時(shí)間足夠長也可以獲得處理機(jī)。優(yōu)點(diǎn)：既照顧了短作業(yè)，又考慮了作業(yè)的先后順序，使長作業(yè)也可以得到服務(wù)；缺點(diǎn)：但優(yōu)先級的計(jì)算增加了系統(tǒng)的開銷。響應(yīng)比RP=等待時(shí)間+要求服務(wù)時(shí)間要求服務(wù)時(shí)間=響應(yīng)時(shí)間要求服務(wù)時(shí)間2022年3月17日第二章 進(jìn)程管理203.3 調(diào)度算法調(diào)度算法基本原理基本原理 系統(tǒng)將所有就緒進(jìn)程按照先來先服務(wù)的原則排成一個(gè)隊(duì)列，每次調(diào)度把CP

20、U分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片，當(dāng)執(zhí)行時(shí)間片用完，調(diào)度程序停止其執(zhí)行，并把它送到隊(duì)列尾部。 5. 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法（基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法（Round Robin）時(shí)間片大小時(shí)間片大小如果太小利于短作業(yè)，但是會頻繁中斷，進(jìn)程上下文切換，增加系統(tǒng)開銷；如果太大則每個(gè)進(jìn)程都能在時(shí)間片內(nèi)完成，則退化為FCFS算法，無法滿足交互式用戶的需求。2022年3月17日第二章 進(jìn)程管理213.3 調(diào)度算法調(diào)度算法 5. 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法（基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法（Round Robin）(a) q=1(b) q=4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1

21、5 16 17 18ABACBDAECBDAECABCDEECECC2022年3月17日第二章 進(jìn)程管理223.3 調(diào)度算法調(diào)度算法 隊(duì)列（隊(duì)列（q=1） 時(shí)間 隊(duì)列狀態(tài)時(shí)間 隊(duì)列狀態(tài)0A10DAECB完成1BA11AECD完成2ACB12ECA完成3CBDA13CE4BDAEC14EC5DAECB15CE6AECBD16EC7ECBDA17CE完成8CBDAE18C完成9BDAEC2022年3月17日第二章 進(jìn)程管理233.3 調(diào)度算法調(diào)度算法 隊(duì)列（隊(duì)列（q=4）時(shí)間隊(duì)列狀態(tài)0A4BCDEA完成7CDEB完成11DEC13ECD完成17CE完成18C完成2022年3月17日第二章 進(jìn)程管理

22、243.3 調(diào)度算法調(diào)度算法 5. 時(shí)間片輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)法RR算法算法進(jìn)程名進(jìn)程名ABCDE平平 均均到達(dá)時(shí)間到達(dá)時(shí)間01234服務(wù)時(shí)間服務(wù)時(shí)間43524RRq=1完成時(shí)間完成時(shí)間1210181117周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間1291681311.6帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間333.243.253.29RRq=4完成時(shí)間完成時(shí)間47181317周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間461610139.8帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間123.253.252.892022年3月17日第二章 進(jìn)程管理253.3 調(diào)度算法調(diào)度算法調(diào)度算法的實(shí)施過程調(diào)度算法的實(shí)施過程設(shè)置多個(gè)就緒隊(duì)列，賦予不同的優(yōu)先級，各個(gè)隊(duì)列優(yōu)先級遞減，時(shí)間片遞增；新進(jìn)程

23、放入第一個(gè)隊(duì)列尾部，F(xiàn)CFS原則排隊(duì)調(diào)度，時(shí)間片內(nèi)完成則撤離系統(tǒng)，如果沒完則轉(zhuǎn)入下個(gè)隊(duì)列尾部，以此類推，在第n個(gè)隊(duì)列采取時(shí)間片輪轉(zhuǎn)調(diào)度；第一隊(duì)列空閑，調(diào)度第二隊(duì)列，以此類推，新進(jìn)程如果優(yōu)先級高，可搶占處理機(jī)。 6. 多級反饋隊(duì)列調(diào)度算法（多級反饋隊(duì)列調(diào)度算法（Round Robin With Multiple Feedback）2022年3月17日第二章 進(jìn)程管理263.3 調(diào)度算法調(diào)度算法 6. 多級反饋隊(duì)列調(diào)度算法（多級反饋隊(duì)列調(diào)度算法（Round Robin With Multiple Feedback）算法的性能算法的性能終端型作業(yè)用戶，大多屬于交互型作業(yè)，作業(yè)??；短批處理作業(yè)用戶，周

24、轉(zhuǎn)時(shí)間短；長批處理用戶，不用擔(dān)心作業(yè)長期得不到處理。就緒隊(duì)列1就緒隊(duì)列2就緒隊(duì)列3就緒隊(duì)列4至CPU至CPU至CPU至CPUS1S2S3（時(shí)間片：S1S2 S3）新進(jìn)程2022年3月17日第二章 進(jìn)程管理273.4 實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度提供必要的信息提供必要的信息就緒時(shí)間，任務(wù)就緒的起始時(shí)間；開始截止時(shí)間和完成截止時(shí)間；處理時(shí)間，一個(gè)任務(wù)從開始執(zhí)行直至完成所需的時(shí)間；資源要求，任務(wù)執(zhí)行的時(shí)候需要的一組資源；優(yōu)先級，對緊迫任務(wù)設(shè)置“絕對絕對”優(yōu)先級，松弛任務(wù)設(shè)置“相對相對”優(yōu)先級。 1. 實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件2022年3月17日第二章 進(jìn)程管理283.4 實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度 1

25、. 實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件具有快速切換機(jī)制具有快速切換機(jī)制對外部中斷的快速響應(yīng)能力；快速的任務(wù)分派能力。系統(tǒng)處理能力強(qiáng)系統(tǒng)處理能力強(qiáng)表示周期時(shí)間表示處理時(shí)間，其中ii1PC1niiiPC采用搶占式調(diào)度機(jī)制采用搶占式調(diào)度機(jī)制采用單處理機(jī)系統(tǒng)，增強(qiáng)處理能力，減少每個(gè)任務(wù)處理時(shí)間；采用多處理機(jī)調(diào)度單處理機(jī)實(shí)時(shí)調(diào)度條件：2022年3月17日第二章 進(jìn)程管理293.4 實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度非搶占式調(diào)度算法非搶占式調(diào)度算法非搶占式輪轉(zhuǎn)調(diào)度算法；非搶占式優(yōu)先級調(diào)度算法。搶占式調(diào)度算法搶占式調(diào)度算法基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法立即搶占的優(yōu)先權(quán)調(diào)度算法 2. 實(shí)時(shí)調(diào)度算法分類實(shí)時(shí)調(diào)度算法

26、分類最早截止時(shí)間優(yōu)先最早截止時(shí)間優(yōu)先EDF（Earliest Deadline First）算法）算法 3. 常用的幾種實(shí)時(shí)調(diào)度算法常用的幾種實(shí)時(shí)調(diào)度算法最低松弛度優(yōu)先級最低松弛度優(yōu)先級LLF（Least Laxity First）算法）算法 任務(wù)的松弛度任務(wù)的松弛度=必須完成時(shí)間必須完成時(shí)間 - 其本身運(yùn)行時(shí)間其本身運(yùn)行時(shí)間 - 當(dāng)前時(shí)間當(dāng)前時(shí)間 松弛度松弛度=0表示該任務(wù)必須馬上執(zhí)行，否則會造成嚴(yán)重后果。表示該任務(wù)必須馬上執(zhí)行，否則會造成嚴(yán)重后果。2022年3月17日第二章 進(jìn)程管理303.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件競爭資源：多個(gè)進(jìn)程共享資源，資源數(shù)目不足所引起進(jìn)

27、競爭資源：多個(gè)進(jìn)程共享資源，資源數(shù)目不足所引起進(jìn)程對資源的競爭；程對資源的競爭；可剝奪資源和非剝奪性資源競爭非剝奪性資源競爭臨時(shí)性資源 1. 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因 死鎖（死鎖（Deadlock）：）：是指多個(gè)進(jìn)程在運(yùn)行過程中因爭奪資源而造成的一種僵局（DeadlyEmbrace），當(dāng)進(jìn)程出現(xiàn)這種僵持狀態(tài)時(shí)，若無外力作用，它們將無法再向前推進(jìn)。2022年3月17日第二章 進(jìn)程管理313.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 1. 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因進(jìn)程推進(jìn)順序非法：請求和釋放資源順序不當(dāng)。進(jìn)程推進(jìn)順序非法：請求和釋放資源順序不當(dāng)。1）進(jìn)程推進(jìn)順序合法 2）進(jìn)程推

28、進(jìn)順序非法P1：Request(R1); Request(R2);P1：Release(R1); Release(R2);P2：Request(R1); Request(R2);P2：Release(R1); Release(R2);P1：Request(R1); P2：Request(R2); P1：Request(R2); P2：Request(R1); P1P2R1R22022年3月17日第二章 進(jìn)程管理323.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件（1） 互斥條件互斥條件，一段時(shí)間內(nèi)某資源只能由一個(gè)進(jìn)程占用；（2） 請求和保持條件請求和保持條件，部分分配資源；（3） 不剝

29、奪條件不剝奪條件，進(jìn)程已獲得資源不能被剝奪，直至使用完畢；（4） 環(huán)路等待條件環(huán)路等待條件，發(fā)生死鎖時(shí)必然存在進(jìn)程-資源的環(huán)形鏈。 2. 產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件（1）預(yù)防死鎖預(yù)防死鎖：通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或者幾個(gè)，預(yù)防死鎖的發(fā)生；（2）避免死鎖：避免死鎖：在資源的動態(tài)分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免發(fā)生死鎖；（3）檢測死鎖：檢測死鎖：通過系統(tǒng)所設(shè)置的檢測機(jī)制，及時(shí)地檢測出死鎖的發(fā)生，并精確地確定與死鎖有關(guān)的進(jìn)程和資源；（4）解除死鎖：解除死鎖：與死鎖檢測配合，通過撤銷和掛起一些進(jìn)程，以便回收一些資源，再將這些資源分配給

30、處于阻塞狀態(tài)的進(jìn)程，使之就緒，以繼續(xù)運(yùn)行。 3. 處理死鎖的基本方法處理死鎖的基本方法2022年3月17日第二章 進(jìn)程管理333.6 預(yù)防死鎖的方法預(yù)防死鎖的方法（1） 摒棄“請求和保持請求和保持”條件，要么全部分配，要么一個(gè)也不分配；（2） 摒棄“不剝奪不剝奪”條件，資源在進(jìn)程運(yùn)行過程中可被暫時(shí)釋放；（3） 摒棄“環(huán)路等待環(huán)路等待”條件，進(jìn)程對資源的請求按照某種順序依次進(jìn)行。 1. 預(yù)防死鎖預(yù)防死鎖安全狀態(tài)安全狀態(tài) 是指系統(tǒng)能按某種進(jìn)程順序（P1，P2， ，Pn），來為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對資源的最大需求，使每個(gè)進(jìn)程都順利執(zhí)行。安全狀態(tài)實(shí)例安全狀態(tài)實(shí)例:假設(shè)系統(tǒng)中有三

31、個(gè)進(jìn)程P1，P2，P3，共12臺磁帶機(jī)。2. 系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài)進(jìn)程最大需求已分配可用P11053P242P3922022年3月17日第二章 進(jìn)程管理343.6 預(yù)防死鎖的方法預(yù)防死鎖的方法數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 3. 銀行家算法銀行家算法（1）可利用資源向量Available（m個(gè)元素的數(shù)組），其中Availablej = k，表示系統(tǒng)中 Rj 類資源有 k 個(gè)。 （2）最大需求矩陣Max（nm）的矩陣，Maxi,j=k，表示進(jìn)程Pi需要Rj類資源的最大數(shù)目是k個(gè)。（3）分配矩陣Allocation（ nm）的矩陣， Allocationi,j=k，表示Pi已經(jīng)分得Rj類資源的數(shù)目是k個(gè)。（

32、4）需求矩陣Need （ nm）的矩陣， Needi,j=k，表示Pi還需要Rj類資源的數(shù)目是k個(gè)。上述關(guān)系：上述關(guān)系： Needi,j= Maxi,j - Allocationi,j；2022年3月17日第二章 進(jìn)程管理353.6 預(yù)防死鎖的方法預(yù)防死鎖的方法算法描述算法描述 3. 銀行家算法銀行家算法 假設(shè)Request i 是Pi的請求向量，Request i j=k表示Pi請求k個(gè)Rj類資源，Pi申請后，系統(tǒng)進(jìn)行檢查：（1）如果Request i j Need i,j ，則轉(zhuǎn)（2），否則出錯(cuò)（需要資源超過它宣布的最大值）。 （2）如果Request i j Available j ，則

33、轉(zhuǎn)（3），否則尚無足夠的資源，Pi必須等待。 （3）系統(tǒng)為Pi分配資源（試探性的分配試探性的分配）： Availablej:=Availablej - Request i j ; Allocationi,j:=Allocationi,j + Request i j; Needi,j:=Needi,j - Request i j;（4）執(zhí)行安全性算法，若安全則分配（為Pi），否則不分配，令Pi等待。2022年3月17日第二章 進(jìn)程管理363.6 預(yù)防死鎖的方法預(yù)防死鎖的方法安全性算法安全性算法 3. 銀行家算法銀行家算法（1）設(shè)置兩個(gè)向量：工作向量Work，表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類

34、資源數(shù)目，含有m個(gè)元素，初始work := Available；向量Finish，表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成，初始時(shí)Finish:=false，有足夠資源分配時(shí)，F(xiàn)inish:=true； （2）在進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： a）Finishi=false; b）Needi,j Workj；如果找到則轉(zhuǎn)（3），否則轉(zhuǎn)（4）；（3）進(jìn)程Pi獲得資源可順利完成，并釋放資源，則執(zhí)行 Workj:=Workj + Allocationi,j; Finishi:=true; 轉(zhuǎn)（2）；（4）如果所有進(jìn)程的Finishi=true都滿足，表示系統(tǒng)處于安全狀態(tài)，否則系統(tǒng)進(jìn)

35、入不安全狀態(tài)。2022年3月17日第二章 進(jìn)程管理373.6 預(yù)防死鎖的方法預(yù)防死鎖的方法假設(shè)系統(tǒng)中有五個(gè)進(jìn)程假設(shè)系統(tǒng)中有五個(gè)進(jìn)程P0, P1, P2, P3, P4和三類資源和三類資源A, B, C，各，各種資源的數(shù)量分別為種資源的數(shù)量分別為10、5、7，在，在T0時(shí)刻的資源分配情況下表：時(shí)刻的資源分配情況下表： 4. 銀行家算法的實(shí)例銀行家算法的實(shí)例進(jìn)程進(jìn)程/資源資源MaxAllocationNeedAvailableA B CA B CA B CA B CP0P1P2P3P47 5 33 2 29 0 22 2 24 3 30 1 02 0 0(3 0 2)3 0 22 1 10 0 2

36、7 4 31 2 2(0 2 0)6 0 00 1 14 3 13 3 2(2 3 0)2022年3月17日第二章 進(jìn)程管理383.6 預(yù)防死鎖的方法預(yù)防死鎖的方法 4. 銀行家算法的實(shí)例銀行家算法的實(shí)例進(jìn)程進(jìn)程/資源資源WorkNeedAllocationWork+AllocationFinishA B CA B CA B CA B CP1P3P4P2P03 3 25 3 27 4 37 4 5 10 4 71 2 20 1 14 3 16 0 0 7 4 32 0 02 1 10 0 23 0 2 0 1 05 3 27 4 37 4 510 4 710 5 7truetruetruetr

37、uetrue(1) T0時(shí)刻的安全性：存在安全序列時(shí)刻的安全性：存在安全序列P1 , P3, P4, P2, P0。2022年3月17日第二章 進(jìn)程管理393.6 預(yù)防死鎖的方法預(yù)防死鎖的方法 4. 銀行家算法的實(shí)例銀行家算法的實(shí)例進(jìn)程進(jìn)程/資源資源WorkNeedAllocationWork+AllocationFinishA B CA B CA B CA B CP1P3P4P0P22 3 05 3 27 4 37 4 5 7 5 50 2 00 1 14 3 17 4 3 6 0 0 3 0 22 1 10 0 20 1 0 3 0 2 5 3 27 4 37 4 57 5 510 5 7

38、truetruetruetruetrue(2) P1請求資源，發(fā)出請求向量請求資源，發(fā)出請求向量Request 1 (1,0,2)，進(jìn)行檢查，進(jìn)行檢查Request 1 (1,0,2) Need 1 (1,2,2); Request 1 (1,0,2) Available 1 (3,3,2);存在存在安全序列安全序列P1 , P3, P4, P0, P2。(3) P4請求資源，發(fā)出請求向量請求資源，發(fā)出請求向量Request 4 (3,3,0)，檢查，檢查Request 4 (3,3,0) Need 4 (4,3,1); Request 4 (3,3,0) Available 4 (2,3,0

39、); 讓讓P4等待。等待。2022年3月17日第二章 進(jìn)程管理403.6 預(yù)防死鎖的方法預(yù)防死鎖的方法 4. 銀行家算法的實(shí)例銀行家算法的實(shí)例進(jìn)程進(jìn)程/資源資源AllocationNeedAvailableA B CA B CA B CP0P1P2P3P40 3 03 0 23 0 22 1 10 0 27 2 30 2 06 0 00 1 14 3 12 1 0(4) P0請求資源，發(fā)出請求向量請求資源，發(fā)出請求向量Request 0 (0,2,0)，進(jìn)行檢查，進(jìn)行檢查Request 0 (0,2,0) Need 0 (7,4,3); Request 0 (0,2,0) Available

40、0 (2,3,0);假定假定為為P0分配資源，修改相關(guān)數(shù)據(jù)如下。分配資源，修改相關(guān)數(shù)據(jù)如下。(5) 進(jìn)行安全性檢查，進(jìn)行安全性檢查，Available(2, 1, 0)已不能滿足任何進(jìn)程需要，故已不能滿足任何進(jìn)程需要，故系統(tǒng)進(jìn)入不安全狀態(tài)。系統(tǒng)進(jìn)入不安全狀態(tài)。2022年3月17日第二章 進(jìn)程管理413.7 死鎖的檢測與解除死鎖的檢測與解除資源分配圖（資源分配圖（Resource Allocation Graph） RAG是由一組結(jié)點(diǎn)N和一組邊E組成的一個(gè)對偶RAG=（N，E），對它的約定如下： （1） P=p1, p2, , pn R=r1, r2, , rn P 和R是兩個(gè)互斥的子集，N=P

41、R （2） eE，它連接P中的一個(gè)結(jié)點(diǎn)和R中的一個(gè)結(jié)點(diǎn) e=（pi, rj) 資源請求邊（ pi指向rj ）表示pi請求一個(gè)單位的rj ； e=（rj, pi) 資源分配邊（ rj 指向pi ）表示pi分配到一個(gè)單位的rj ； 1. 死鎖的檢測死鎖的檢測P1P2R1R22022年3月17日第二章 進(jìn)程管理423.7 死鎖的檢測與解除死鎖的檢測與解除資源分配圖的簡化資源分配圖的簡化 （1）從RAG中找出既不阻塞又不是孤點(diǎn)的進(jìn)程Pi，消去由Pi出發(fā)的和指向Pi的所有邊（請求邊和分配邊），這等價(jià)于Pi獲得它所需的資源，不斷向前推進(jìn)，一直運(yùn)行完畢，釋放出它所占有的全部資源。 （2）進(jìn)程Pi所釋放的資源可以喚醒某些阻塞于該資源的進(jìn)程Pj，消去Pj所有的邊，使之成為孤點(diǎn)。 （3）如此下去，最后，若消去圖中所有的邊，則稱該圖是可完全化簡的。 （4）若有向圖不能通過任何過程予以簡化，則稱該圖是不可完全簡化的。 1. 死鎖的檢測死鎖的檢測死鎖定理死鎖定理 引理：引理：一個(gè)給定的進(jìn)程資源分配圖，對所有的簡化順序，將導(dǎo)致相同的結(jié)果（再也不能簡化）。 死鎖定理：死鎖定理：S是死鎖狀態(tài)的充分條件充分條件是S狀態(tài)的進(jìn)程資源分配圖是不可完全簡化的。2022年3月17日第二章 進(jìn)程管理433.7 死鎖的檢測與解除死鎖的檢測與解除死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)死鎖檢測中的數(shù)據(jù)結(jié)構(gòu) （1）