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

第三章處理機(jī)調(diào)度與死鎖2023/2/31操作系統(tǒng)講義主要內(nèi)容

3.1處理機(jī)調(diào)度的層次

3.2調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則

3.3幾種調(diào)度算法

3.4實(shí)時(shí)調(diào)度

3.5產(chǎn)生死鎖的原因和必要條件

3.6預(yù)防死鎖的方法

3.7

死鎖的檢測(cè)和解除2023/2/32第二章進(jìn)程管理3.1處理機(jī)調(diào)度的層次作業(yè)的基本概念1.高級(jí)調(diào)度（HighLevelScheduling）主要功能：根據(jù)某種算法，把外存中把處于后備隊(duì)列中的那些作業(yè)調(diào)入內(nèi)存，當(dāng)作業(yè)完成時(shí)做善后處理。

作業(yè)（Job）：包含通常的程序和數(shù)據(jù)，并且配有作業(yè)說(shuō)明書；作業(yè)步（JobStep）：“編譯”

->“連接裝配”->“運(yùn)行”；作業(yè)流：若干個(gè)作業(yè)在系統(tǒng)外存形成的輸入流。

作業(yè)控制塊JCB（JobControlBlock）通常包含：作業(yè)標(biāo)識(shí)、用戶名稱、用戶賬戶、作業(yè)類型（CPU繁忙，I/O繁忙，批量型，終端型）、作業(yè)狀態(tài)、調(diào)度信息（優(yōu)先級(jí)，作業(yè)運(yùn)行時(shí)間）、資源需求（運(yùn)行時(shí)間，內(nèi)存，I/O類型數(shù)量）、進(jìn)入系統(tǒng)時(shí)間、開(kāi)始處理時(shí)間、作業(yè)完成時(shí)間、作業(yè)退出時(shí)間、資源使用情況。2023/2/33第二章進(jìn)程管理3.1處理機(jī)調(diào)度的層次1.高級(jí)調(diào)度（HighLevelScheduling）作業(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)至外存（存儲(chǔ)管理中的對(duì)換功能）。

1）接收多少個(gè)作業(yè)到內(nèi)存：取決于多道程序度

2）接收哪些作業(yè)：取決于調(diào)度算法最簡(jiǎn)單：先來(lái)先服務(wù)調(diào)度算法最常用：短作業(yè)優(yōu)先調(diào)度算法較常用：優(yōu)先級(jí)調(diào)度算法比較好：響應(yīng)比高者優(yōu)先調(diào)度算法2.中級(jí)調(diào)度（IntermediateLevelScheduling）2023/2/34第二章進(jìn)程管理3.1處理機(jī)調(diào)度的層次3.低級(jí)調(diào)度（LowLevelScheduling）它所調(diào)度的對(duì)象是進(jìn)程（或內(nèi)核級(jí)線程），當(dāng)CPU需要重新分配時(shí)，利用一定的算法把它分配給進(jìn)程，它是最基本的調(diào)度。進(jìn)程調(diào)度的功能

（1）保存處理機(jī)的現(xiàn)場(chǎng)信息；（2）按照某種算法選擇進(jìn)程（如優(yōu)先數(shù)算法，輪轉(zhuǎn)算法）

（3）把處理器分配給進(jìn)程。進(jìn)程調(diào)度的三個(gè)基本機(jī)制（1）排隊(duì)器：事先將系統(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信息；2023/2/35第二章進(jìn)程管理3.1處理機(jī)調(diào)度的層次進(jìn)程調(diào)度方式

3.低級(jí)調(diào)度（LowLevelScheduling）非搶占方式：一旦處理機(jī)分配給某個(gè)進(jìn)程，不管它要運(yùn)行多長(zhǎng)時(shí)間，都讓它一直運(yùn)行下去，決不會(huì)因?yàn)槠渌蚨鴵屨颊谶\(yùn)行進(jìn)程的處理機(jī)。這種方式下引起進(jìn)程調(diào)度的因素包括：執(zhí)行完畢或者發(fā)生某事件不能再執(zhí)行執(zhí)行進(jìn)程提出I/O請(qǐng)求而暫停執(zhí)行在進(jìn)程通信或者同步過(guò)程中執(zhí)行了某種原語(yǔ)操作，如P，Block等優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，系統(tǒng)開(kāi)銷小，適用于大多數(shù)批處理系統(tǒng)；缺點(diǎn)：難以滿足緊急任務(wù)要求，可能造成難以預(yù)料的后果。2023/2/36第二章進(jìn)程管理3.1處理機(jī)調(diào)度的層次進(jìn)程調(diào)度方式

3.低級(jí)調(diào)度（LowLevelScheduling）搶占方式：允許調(diào)度程序根據(jù)某種原則去暫停某個(gè)正在執(zhí)行的進(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)前較長(zhǎng)作業(yè)（進(jìn)程的）CPU；時(shí)間片原則：時(shí)間片輪轉(zhuǎn)；優(yōu)點(diǎn)：防止一個(gè)長(zhǎng)進(jìn)程長(zhǎng)時(shí)間占用處理機(jī)，公平服務(wù)，適合實(shí)時(shí)任務(wù)的需求；缺點(diǎn)：需要付出較大的開(kāi)銷。2023/2/37第二章進(jìn)程管理3.2

調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型通常在分時(shí)系統(tǒng)中只設(shè)置進(jìn)程調(diào)度，每個(gè)用戶建立一個(gè)進(jìn)程，系統(tǒng)利用堆棧、樹(shù)或者鏈表來(lái)管理就緒進(jìn)程隊(duì)列，就緒進(jìn)程以FIFO隊(duì)列形式組織。

1.調(diào)度隊(duì)列模型進(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)2023/2/38第二章進(jìn)程管理3.2

調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型在批處理系統(tǒng)中，作業(yè)調(diào)度按照一定的算法從外存的后備隊(duì)列選擇一批作業(yè)調(diào)入內(nèi)存，建立進(jìn)程，送入就緒隊(duì)列，然后按照一定的進(jìn)程調(diào)度算法選擇進(jìn)程，分配CPU。

1.調(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ì)……2023/2/39第二章進(jìn)程管理3.2

調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則

1.調(diào)度隊(duì)列模型具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型的特點(diǎn)：（1）采用優(yōu)先權(quán)就緒隊(duì)列，隊(duì)首進(jìn)程優(yōu)先權(quán)最高，或者采用無(wú)序鏈表方式；（2）設(shè)置多個(gè)阻塞隊(duì)列，每個(gè)隊(duì)列對(duì)應(yīng)于某一種進(jìn)程阻塞事件；2023/2/310第二章進(jìn)程管理3.2

調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型可把進(jìn)程的就緒狀態(tài)分成內(nèi)存就緒和外存就緒，類似地，阻塞狀態(tài)也可進(jìn)一步分成內(nèi)存阻塞和外存阻塞，調(diào)出操作可使進(jìn)程狀態(tài)由內(nèi)存就緒轉(zhuǎn)為外存就緒，內(nèi)存阻塞轉(zhuǎn)為外存阻塞；中級(jí)調(diào)度可使外存就緒轉(zhuǎn)為內(nèi)存就緒。

1.調(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)中級(jí)調(diào)度2023/2/311第二章進(jìn)程管理3.2

調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則面向用戶的準(zhǔn)則

（1）周轉(zhuǎn)時(shí)間短（批處理系統(tǒng)）

平均周轉(zhuǎn)時(shí)間T的計(jì)算如下：平均帶權(quán)周轉(zhuǎn)時(shí)間W的計(jì)算如下：

（2）響應(yīng)時(shí)間快（分時(shí)系統(tǒng)）：是指從用戶通過(guò)鍵盤提交一個(gè)請(qǐng)求開(kāi)始，直到系統(tǒng)首次響應(yīng)為止的時(shí)間必須快；

（3）截止時(shí)間的保證（實(shí)時(shí)系統(tǒng)）：是指某任務(wù)必須開(kāi)始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間必須有保證；

（4）優(yōu)先權(quán)準(zhǔn)則：遵循優(yōu)先權(quán)準(zhǔn)則讓某些緊急的作業(yè)得到及時(shí)處理。2.選擇調(diào)度方式和算法的若干準(zhǔn)則2023/2/312第二章進(jìn)程管理3.2

調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則面向系統(tǒng)的準(zhǔn)則

2.選擇調(diào)度方式和算法的若干準(zhǔn)則（1）系統(tǒng)吞吐量高：這個(gè)是評(píng)價(jià)批處理系統(tǒng)性能的另一個(gè)重要指標(biāo)，因此是選擇批處理作業(yè)調(diào)度的重要準(zhǔn)則。吞吐量是指單位時(shí)間內(nèi)系統(tǒng)完成的作業(yè)數(shù)，它直接和作業(yè)的平均長(zhǎng)度有關(guān)；（2）處理機(jī)利用率好：CPU價(jià)格昂貴，利用率成為衡量系統(tǒng)性能的重要指標(biāo)；（3）各類資源的平衡利用：不僅要使處理機(jī)利用率高，還要有效地利用其它各類資源，如內(nèi)存、外存和I/O設(shè)備，適當(dāng)?shù)恼{(diào)度方式和算法可以使系統(tǒng)中的各類資源處于忙碌狀態(tài)。2023/2/313第二章進(jìn)程管理3.3

調(diào)度算法是一種最簡(jiǎn)單的調(diào)度算法，適用于作業(yè)調(diào)度和進(jìn)程調(diào)度，每次調(diào)度都是從后備隊(duì)列中選擇一個(gè)或者多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，分配資源，創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。

1.先來(lái)先服務(wù)調(diào)度算法FCFS（FirstComeFirstService）FCFS算法比較有利于長(zhǎng)作業(yè)（進(jìn)程），不利于短作業(yè)（進(jìn)程）進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開(kāi)始執(zhí)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A010111B110011011001C21101102100100D31001022021991.992023/2/314第二章進(jìn)程管理3.3

調(diào)度算法是指對(duì)短作業(yè)或者短進(jìn)程優(yōu)先調(diào)度的算法，適用于作業(yè)調(diào)度和進(jìn)程調(diào)度，SJF算法就是從后備隊(duì)列中選擇一個(gè)運(yùn)行時(shí)間最短的作業(yè)，然后把它們調(diào)入內(nèi)存運(yùn)行。

2.短作業(yè)優(yōu)先調(diào)度算法SJF（ShortJobFirst）SJF的優(yōu)點(diǎn)：能有效地降低作業(yè)的平均等待時(shí)間，提高系統(tǒng)吞吐量；進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開(kāi)始執(zhí)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A030331B145982C223531.5D35914112.2SJF的缺點(diǎn)：1）對(duì)長(zhǎng)作業(yè)不利；2）未考慮作業(yè)的緊迫度；3）用戶估計(jì)執(zhí)行時(shí)間的不準(zhǔn)確性。2023/2/315第二章進(jìn)程管理3.3

調(diào)度算法

3.FCFS和SJF的性能比較算法進(jìn)程名ABCDE平均到達(dá)時(shí)間01234服務(wù)時(shí)間43524FCFS完成時(shí)間47121418周轉(zhuǎn)時(shí)間461011149帶權(quán)周轉(zhuǎn)時(shí)間1225.53.52.8SJF完成時(shí)間4918613周轉(zhuǎn)時(shí)間4816398帶權(quán)周轉(zhuǎn)時(shí)間12.673.21.52.252.12023/2/316第二章進(jìn)程管理3.3

調(diào)度算法是為了照顧緊迫型作業(yè)，使之在進(jìn)入系統(tǒng)后便獲得優(yōu)先處理，該算法會(huì)把處理機(jī)分配給優(yōu)先級(jí)最高的作業(yè)（或者進(jìn)程）。1）非搶占式優(yōu)先權(quán)調(diào)度算法，適用于批處理系統(tǒng)或?qū)崟r(shí)性要求不高的系統(tǒng)；

2）搶占式優(yōu)先權(quán)調(diào)度算法，能更好地滿足緊迫作業(yè)，適合于嚴(yán)格的實(shí)時(shí)系統(tǒng)或者對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中。

4.高優(yōu)先權(quán)優(yōu)先調(diào)度算法（PriorityJobFirst）2023/2/317第二章進(jìn)程管理3.3

調(diào)度算法

4.高優(yōu)先權(quán)優(yōu)先調(diào)度算法（PriorityJobFirst）優(yōu)先權(quán)的類型靜態(tài)優(yōu)先權(quán)：創(chuàng)建進(jìn)程時(shí)確定，在整個(gè)運(yùn)行期間保持不變；進(jìn)程類型，系統(tǒng)進(jìn)程要比用戶進(jìn)程優(yōu)先級(jí)高；進(jìn)程對(duì)資源的要求，要求少的優(yōu)先級(jí)高；用戶要求，用戶進(jìn)程的緊迫程度。優(yōu)點(diǎn)：簡(jiǎn)單易行，系統(tǒng)開(kāi)銷小缺點(diǎn)：不夠精確，可能使優(yōu)先權(quán)低的作業(yè)（進(jìn)程）長(zhǎng)期得不到調(diào)度動(dòng)態(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)開(kāi)銷稍大2023/2/318第二章進(jìn)程管理3.3

調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法

每個(gè)作業(yè)的優(yōu)先級(jí)動(dòng)態(tài)計(jì)算，作業(yè)的優(yōu)先級(jí)隨等待時(shí)間的增加而不斷提高。

4.高優(yōu)先權(quán)優(yōu)先調(diào)度算法（PriorityJobFirst）結(jié)論：如果作業(yè)等待時(shí)間相同，要求服務(wù)時(shí)間越短，優(yōu)先級(jí)越高，該算法利于短作業(yè)；如果要求服務(wù)時(shí)間相同，那么等待時(shí)間越長(zhǎng)，優(yōu)先權(quán)越高，它實(shí)現(xiàn)的是先來(lái)先服務(wù)；對(duì)于長(zhǎng)作業(yè)，作業(yè)的優(yōu)先級(jí)隨著等待時(shí)間的增加而提高，如果等待時(shí)間足夠長(zhǎng)也可以獲得處理機(jī)。優(yōu)點(diǎn)：既照顧了短作業(yè)，又考慮了作業(yè)的先后順序，使長(zhǎng)作業(yè)也可以得到服務(wù)；缺點(diǎn)：但優(yōu)先級(jí)的計(jì)算增加了系統(tǒng)的開(kāi)銷。響應(yīng)比RP=等待時(shí)間+要求服務(wù)時(shí)間要求服務(wù)時(shí)間=響應(yīng)時(shí)間要求服務(wù)時(shí)間2023/2/319第二章進(jìn)程管理3.3

調(diào)度算法基本原理系統(tǒng)將所有就緒進(jìn)程按照先來(lái)先服務(wù)的原則排成一個(gè)隊(duì)列，每次調(diào)度把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片，當(dāng)執(zhí)行時(shí)間片用完，調(diào)度程序停止其執(zhí)行，并把它送到隊(duì)列尾部。

5.基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法（RoundRobin）時(shí)間片大小如果太小利于短作業(yè)，但是會(huì)頻繁中斷，進(jìn)程上下文切換，增加系統(tǒng)開(kāi)銷；如果太大則每個(gè)進(jìn)程都能在時(shí)間片內(nèi)完成，則退化為FCFS算法，無(wú)法滿足交互式用戶的需求。2023/2/320第二章進(jìn)程管理3.3

調(diào)度算法

5.基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法（RoundRobin）(a)q=1(b)q=4123456789101112131415161718ABACBDAECBDAECABCDEECECC2023/2/321第二章進(jìn)程管理3.3

調(diào)度算法——隊(duì)列（q=1）時(shí)間隊(duì)列狀態(tài)時(shí)間隊(duì)列狀態(tài)0A10DAECB完成1BA11AECD完成2ACB12ECA完成3CBDA13CE4BDAEC14EC5DAECB15CE6AECBD16EC7ECBDA17CE完成8CBDAE18C完成9BDAEC2023/2/322第二章進(jìn)程管理3.3

調(diào)度算法——隊(duì)列（q=4）時(shí)間隊(duì)列狀態(tài)0A4BCDEA完成7CDEB完成11DEC13ECD完成17CE完成18C完成2023/2/323第二章進(jìn)程管理3.3

調(diào)度算法

5.時(shí)間片輪轉(zhuǎn)法RR算法進(jìn)程名ABCDE平均到達(dá)時(shí)間01234服務(wù)時(shí)間43524RRq=1完成時(shí)間1210181117周轉(zhuǎn)時(shí)間1291681311.6帶權(quán)周轉(zhuǎn)時(shí)間333.243.253.29RRq=4完成時(shí)間47181317周轉(zhuǎn)時(shí)間461610139.8帶權(quán)周轉(zhuǎn)時(shí)間123.253.252.892023/2/324第二章進(jìn)程管理3.3

調(diào)度算法調(diào)度算法的實(shí)施過(guò)程設(shè)置多個(gè)就緒隊(duì)列，賦予不同的優(yōu)先級(jí)，各個(gè)隊(duì)列優(yōu)先級(jí)遞減，時(shí)間片遞增；新進(jìn)程放入第一個(gè)隊(duì)列尾部，F(xiàn)CFS原則排隊(duì)調(diào)度，時(shí)間片內(nèi)完成則撤離系統(tǒng)，如果沒(méi)完則轉(zhuǎn)入下個(gè)隊(duì)列尾部，以此類推，在第n個(gè)隊(duì)列采取時(shí)間片輪轉(zhuǎn)調(diào)度；第一隊(duì)列空閑，調(diào)度第二隊(duì)列，以此類推，新進(jìn)程如果優(yōu)先級(jí)高，可搶占處理機(jī)。

6.多級(jí)反饋隊(duì)列調(diào)度算法（RoundRobinWithMultipleFeedback）2023/2/325第二章進(jìn)程管理3.3

調(diào)度算法

6.多級(jí)反饋隊(duì)列調(diào)度算法（RoundRobinWithMultipleFeedback）算法的性能終端型作業(yè)用戶，大多屬于交互型作業(yè)，作業(yè)??；短批處理作業(yè)用戶，周轉(zhuǎn)時(shí)間短；長(zhǎng)批處理用戶，不用擔(dān)心作業(yè)長(zhǎng)期得不到處理。就緒隊(duì)列1就緒隊(duì)列2就緒隊(duì)列3就緒隊(duì)列4至CPU至CPU至CPU至CPUS1S2S3（時(shí)間片：S1<S2<

S3）新進(jìn)程2023/2/326第二章進(jìn)程管理3.4

實(shí)時(shí)調(diào)度提供必要的信息就緒時(shí)間，任務(wù)就緒的起始時(shí)間；開(kāi)始截止時(shí)間和完成截止時(shí)間；處理時(shí)間，一個(gè)任務(wù)從開(kāi)始執(zhí)行直至完成所需的時(shí)間；資源要求，任務(wù)執(zhí)行的時(shí)候需要的一組資源；優(yōu)先級(jí)，對(duì)緊迫任務(wù)設(shè)置“絕對(duì)”優(yōu)先級(jí)，松弛任務(wù)設(shè)置“相對(duì)”優(yōu)先級(jí)。

1.實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件2023/2/327第二章進(jìn)程管理3.4

實(shí)時(shí)調(diào)度

1.實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件具有快速切換機(jī)制對(duì)外部中斷的快速響應(yīng)能力；快速的任務(wù)分派能力。系統(tǒng)處理能力強(qiáng)采用搶占式調(diào)度機(jī)制采用單處理機(jī)系統(tǒng)，增強(qiáng)處理能力，減少每個(gè)任務(wù)處理時(shí)間；采用多處理機(jī)調(diào)度單處理機(jī)實(shí)時(shí)調(diào)度條件：2023/2/328第二章進(jìn)程管理3.4

實(shí)時(shí)調(diào)度非搶占式調(diào)度算法非搶占式輪轉(zhuǎn)調(diào)度算法；非搶占式優(yōu)先級(jí)調(diào)度算法。搶占式調(diào)度算法基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法立即搶占的優(yōu)先權(quán)調(diào)度算法

2.實(shí)時(shí)調(diào)度算法分類最早截止時(shí)間優(yōu)先EDF（EarliestDeadlineFirst）算法

3.常用的幾種實(shí)時(shí)調(diào)度算法最低松弛度優(yōu)先級(jí)LLF（LeastLaxityFirst）算法

任務(wù)的松弛度=必須完成時(shí)間-其本身運(yùn)行時(shí)間-當(dāng)前時(shí)間

松弛度=0表示該任務(wù)必須馬上執(zhí)行，否則會(huì)造成嚴(yán)重后果。2023/2/329第二章進(jìn)程管理3.5

產(chǎn)生死鎖的原因和必要條件競(jìng)爭(zhēng)資源：多個(gè)進(jìn)程共享資源，資源數(shù)目不足所引起進(jìn)程對(duì)資源的競(jìng)爭(zhēng)；可剝奪資源和非剝奪性資源競(jìng)爭(zhēng)非剝奪性資源競(jìng)爭(zhēng)臨時(shí)性資源

1.產(chǎn)生死鎖的原因死鎖（Deadlock）：是指多個(gè)進(jìn)程在運(yùn)行過(guò)程中因爭(zhēng)奪資源而造成的一種僵局（DeadlyEmbrace），當(dāng)進(jìn)程出現(xiàn)這種僵持狀態(tài)時(shí)，若無(wú)外力作用，它們將無(wú)法再向前推進(jìn)。2023/2/330第二章進(jìn)程管理3.5

產(chǎn)生死鎖的原因和必要條件

1.產(chǎn)生死鎖的原因進(jìn)程推進(jìn)順序非法：請(qǐng)求和釋放資源順序不當(dāng)。1）進(jìn)程推進(jìn)順序合法2）進(jìn)程推進(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);P1P2R1R22023/2/331第二章進(jìn)程管理3.5

產(chǎn)生死鎖的原因和必要條件（1）互斥條件，一段時(shí)間內(nèi)某資源只能由一個(gè)進(jìn)程占用；（2）請(qǐng)求和保持條件，部分分配資源；（3）不剝奪條件，進(jìn)程已獲得資源不能被剝奪，直至使用完畢；（4）環(huán)路等待條件，發(fā)生死鎖時(shí)必然存在進(jìn)程-資源的環(huán)形鏈。

2.產(chǎn)生死鎖的必要條件（1）預(yù)防死鎖：通過(guò)設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或者幾個(gè)，預(yù)防死鎖的發(fā)生；（2）避免死鎖：在資源的動(dòng)態(tài)分配過(guò)程中，用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免發(fā)生死鎖；（3）檢測(cè)死鎖：通過(guò)系統(tǒng)所設(shè)置的檢測(cè)機(jī)制，及時(shí)地檢測(cè)出死鎖的發(fā)生，并精確地確定與死鎖有關(guān)的進(jìn)程和資源；（4）解除死鎖：與死鎖檢測(cè)配合，通過(guò)撤銷和掛起一些進(jìn)程，以便回收一些資源，再將這些資源分配給處于阻塞狀態(tài)的進(jìn)程，使之就緒，以繼續(xù)運(yùn)行。

3.處理死鎖的基本方法2023/2/332第二章進(jìn)程管理3.6

預(yù)防死鎖的方法（1）摒棄“請(qǐng)求和保持”條件，要么全部分配，要么一個(gè)也不分配；（2）摒棄“不剝奪”條件，資源在進(jìn)程運(yùn)行過(guò)程中可被暫時(shí)釋放；（3）摒棄“環(huán)路等待”條件，進(jìn)程對(duì)資源的請(qǐng)求按照某種順序依次進(jìn)行。

1.預(yù)防死鎖安全狀態(tài)是指系統(tǒng)能按某種進(jìn)程順序（P1，P2，…，Pn），來(lái)為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都順利執(zhí)行。安全狀態(tài)實(shí)例:假設(shè)系統(tǒng)中有三個(gè)進(jìn)程P1，P2，P3，共12臺(tái)磁帶機(jī)。2.系統(tǒng)安全狀態(tài)進(jìn)程最大需求已分配可用P11053P242P3922023/2/333第二章進(jìn)程管理3.6

預(yù)防死鎖的方法數(shù)據(jù)結(jié)構(gòu)

3.銀行家算法（1）可利用資源向量Available（m個(gè)元素的數(shù)組），其中Available[j]=k，表示系統(tǒng)中Rj類資源有k個(gè)。（2）最大需求矩陣Max（n×m）的矩陣，Max[i,j]=k，表示進(jìn)程Pi需要Rj類資源的最大數(shù)目是k個(gè)。（3）分配矩陣Allocation（n×m）的矩陣，Allocation[i,j]=k，表示Pi已經(jīng)分得Rj類資源的數(shù)目是k個(gè)。（4）需求矩陣Need（n×m）的矩陣，Need[i,j]=k，表示Pi還需要Rj類資源的數(shù)目是k個(gè)。上述關(guān)系：Need[i,j]=Max[i,j]-Allocation[i,j]；2023/2/334第二章進(jìn)程管理3.6

預(yù)防死鎖的方法算法描述

3.銀行家算法假設(shè)Requesti

是Pi的請(qǐng)求向量，Requesti[j]=k表示Pi請(qǐng)求k個(gè)Rj類資源，Pi申請(qǐng)后，系統(tǒng)進(jìn)行檢查：（1）如果Requesti[j]

≤Need

[i,j]

，則轉(zhuǎn)（2），否則出錯(cuò)（需要資源超過(guò)它宣布的最大值）。（2）如果Requesti[j]

≤Available

[j]

，則轉(zhuǎn)（3），否則尚無(wú)足夠的資源，Pi必須等待。（3）系統(tǒng)為Pi分配資源（試探性的分配）：

Available[j]:=Available[j]-Requesti[j]

;Allocation[i,j]:=Allocation[i,j]+Requesti[j];Need[i,j]:=Need[i,j]-Requesti[j];（4）執(zhí)行安全性算法，若安全則分配（為Pi），否則不分配，令Pi等待。2023/2/335第二章進(jìn)程管理3.6

預(yù)防死鎖的方法安全性算法

3.銀行家算法（1）設(shè)置兩個(gè)向量：工作向量Work，表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(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）Finish[i]=false;b）Need[i,j]≤Work[j]；如果找到則轉(zhuǎn)（3），否則轉(zhuǎn)（4）；（3）進(jìn)程Pi獲得資源可順利完成，并釋放資源，則執(zhí)行

Work[j]:=Work[j]+Allocation[i,j];Finish[i]:=true;轉(zhuǎn)（2）；（4）如果所有進(jìn)程的Finish[i]=true都滿足，表示系統(tǒng)處于安全狀態(tài)，否則系統(tǒng)進(jìn)入不安全狀態(tài)。2023/2/336第二章進(jìn)程管理3.6

預(yù)防死鎖的方法假設(shè)系統(tǒng)中有五個(gè)進(jìn)程{P0,P1,P2,P3,P4}和三類資源{A,B,C}，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況下表：

4.銀行家算法的實(shí)例進(jìn)程/資源MaxAllocationNeedAvailableABCABCABCABCP0P1P2P3P4753322902222433010200(302)302211002743122(020)600011431332(230)2023/2/337第二章進(jìn)程管理3.6

預(yù)防死鎖的方法

4.銀行家算法的實(shí)例進(jìn)程/資源WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1P3P4P2P0332532743745104712201143160074320021100230201053274374510471057truetruetruetruetrue(1)T0時(shí)刻的安全性：存在安全序列{P1,P3,P4,P2,P0}。2023/2/338第二章進(jìn)程管理3.6

預(yù)防死鎖的方法

4.銀行家算法的實(shí)例進(jìn)程/資源WorkNeedAllocationWork+AllocationFinishABCABCABCABCP1P3P4P0P2230532743745755020011431743600302211002010302

5327437457551057truetruetruetruetrue(2)P1請(qǐng)求資源，發(fā)出請(qǐng)求向量Request1(1,0,2)，進(jìn)行檢查Request1(1,0,2)≤

Need1(1,2,2);Request1(1,0,2)≤

Available1(3,3,2);存在安全序列{P1,P3,P4,P0,P2}。(3)P4請(qǐng)求資源，發(fā)出請(qǐng)求向量Request4(3,3,0)，檢查Request4(3,3,0)≤

Need4(4,3,1);Request4(3,3,0)≤

Available4(2,3,0);讓P4等待。2023/2/339第二章進(jìn)程管理3.6

預(yù)防死鎖的方法

4.銀行家算法的實(shí)例進(jìn)程/資源AllocationNeedAvailableABCABCABCP0P1P2P3P4030302302211002723020600011431210(4)P0請(qǐng)求資源，發(fā)出請(qǐng)求向量Request0(0,2,0)，進(jìn)行檢查Request0(0,2,0)≤

Need0(7,4,3);Request0(0,2,0)≤

Available0(2,3,0);假定為P0分配資源，修改相關(guān)數(shù)據(jù)如下。(5)進(jìn)行安全性檢查，Available(2,1,0)已不能滿足任何進(jìn)程需要，故系統(tǒng)進(jìn)入不安全狀態(tài)。2023/2/340第二章進(jìn)程管理3.7

死鎖的檢測(cè)與解除資源分配圖（ResourceAllocationGraph）RAG是由一組結(jié)點(diǎn)N和一組邊E組成的一個(gè)對(duì)偶RAG=（N，E），對(duì)它的約定如下：

（1）P={p1,p2,…,pn}R={r1,r2,…,rn}P和R是兩個(gè)互斥的子集，N=P∪R

（2）e∈E，它連接P中的一個(gè)結(jié)點(diǎn)和R中的一個(gè)結(jié)點(diǎn)

e=（pi,rj)–資源請(qǐng)求邊（pi指向rj

）表示pi請(qǐng)求一個(gè)單位的rj

；

e=（rj,pi)–資源分配邊（rj

指向pi

）表示pi分配到一個(gè)單位的rj

；

1.死鎖的檢測(cè)P1P2R1R22023/2/341第二章進(jìn)程管理3.7

死鎖的檢測(cè)與解除資源分配圖的簡(jiǎn)化

（1）從RAG中找出既不阻塞又不是孤點(diǎn)的進(jìn)程Pi，消去由Pi出發(fā)的和指向Pi的所有邊（請(qǐng)求邊和分配邊），這等價(jià)于Pi獲得它所需的資源，不斷向前推進(jìn)，一直運(yùn)行完畢，釋放出它所占有的全部資源。（2）進(jìn)程Pi所釋放的資源可以喚醒某些阻塞于該資源的進(jìn)程Pj，消去Pj所有的邊，使之成為孤點(diǎn)。（3）如此下去，最后，若消去圖中所有的邊，則稱該圖是可完全化簡(jiǎn)的。（4）若有向圖不能通過(guò)任何過(guò)程予以簡(jiǎn)化，則稱該圖是不可完全簡(jiǎn)化的。

1.死鎖的檢測(cè)死鎖定理

引理：一個(gè)給定的進(jìn)程資源分配圖，對(duì)所有的簡(jiǎn)化順序，將導(dǎo)致相同的結(jié)果（再也不能簡(jiǎn)化）。