計(jì)算機(jī)操作系統(tǒng)第三章處理機(jī)調(diào)度與死鎖課件

第三章處理機(jī)調(diào)度與死鎖要解決的三個(gè)問(wèn)題：WHAT：按什么原則分配CPU？

—進(jìn)程調(diào)度算法WHEN：何時(shí)分配CPU？

—進(jìn)程調(diào)度的時(shí)機(jī)HOW：如何分配CPU？

—CPU調(diào)度過(guò)程（進(jìn)程的上下文切換）1PPT課件第三章處理機(jī)調(diào)度與死鎖要解決的三個(gè)問(wèn)題：1PPT課件主要內(nèi)容

處理機(jī)調(diào)度的層次調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則調(diào)度算法實(shí)時(shí)調(diào)度產(chǎn)生死鎖的原因和必要條件預(yù)防和避免死鎖的辦法死鎖的檢測(cè)與解除2PPT課件主要內(nèi)容處理機(jī)調(diào)度的層次2PPT課件3.1處理機(jī)調(diào)度的層次高級(jí)調(diào)度1作業(yè)和作業(yè)步作業(yè)

不僅包含通常的程序和數(shù)據(jù)，還應(yīng)配備一份作業(yè)說(shuō)明書(shū)，系統(tǒng)根據(jù)作業(yè)說(shuō)明書(shū)對(duì)程序的運(yùn)行進(jìn)程控制。在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存。3PPT課件3.1處理機(jī)調(diào)度的層次高級(jí)調(diào)度1作業(yè)和作業(yè)步3PPT課件

作業(yè)步

作業(yè)運(yùn)行期間，每個(gè)作業(yè)都必須經(jīng)過(guò)若干個(gè)相對(duì)獨(dú)立、又相互關(guān)聯(lián)的順序加工步驟，才能得到結(jié)果，把其中的每一個(gè)加工步驟稱為一個(gè)作業(yè)步。

1）編譯

2）連接裝配

3）運(yùn)行作業(yè)流

若干個(gè)作業(yè)進(jìn)入系統(tǒng)后，被依次存放在外存上，形成輸入的作業(yè)流；在OS的控制下，逐個(gè)作業(yè)進(jìn)行處理，形成了處理作業(yè)流。

編譯程序?qū)υ闯绦蜻M(jìn)行編譯，生成若干個(gè)目標(biāo)程序段。將目標(biāo)程序段裝配成可執(zhí)行的目標(biāo)程序?qū)⒛繕?biāo)程序讀入內(nèi)存并控制其運(yùn)行4PPT課件作業(yè)步編譯程序?qū)υ闯绦蜻M(jìn)行編譯，生成若干個(gè)目標(biāo)程序段。將目2作業(yè)控制塊

多道批處理系統(tǒng)中，為每個(gè)作業(yè)配備一個(gè)作業(yè)控制塊（JCB），它是作業(yè)在系統(tǒng)中存在的標(biāo)志。作業(yè)運(yùn)行期間，系統(tǒng)按照J(rèn)CB中的信息對(duì)作業(yè)進(jìn)行控制。

JCB中保存了系統(tǒng)對(duì)作業(yè)進(jìn)行管理和調(diào)度所需的全部信息。例如：作業(yè)標(biāo)識(shí)、用戶名稱、用戶帳戶、作業(yè)類型、作業(yè)狀態(tài)、調(diào)度信息、資源需求、進(jìn)入系統(tǒng)時(shí)間、開(kāi)始處理時(shí)間、作業(yè)完成時(shí)間、作業(yè)退出時(shí)間、資源使用情況等。

5PPT課件2作業(yè)控制塊5PPT課件3作業(yè)調(diào)度（高級(jí)調(diào)度、長(zhǎng)程調(diào)度、接納調(diào)度）

定義按照一定的算法，從外存的后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源兩個(gè)決定

1決定接納多少個(gè)作業(yè)（多道程序度）

2決定接納哪些作業(yè)數(shù)目過(guò)多：每個(gè)進(jìn)程可以執(zhí)行的時(shí)間片就越小，單個(gè)進(jìn)程的周轉(zhuǎn)時(shí)間越長(zhǎng)；數(shù)目過(guò)少：資源利用率和系統(tǒng)吞吐量下降，應(yīng)考慮調(diào)度新的進(jìn)程進(jìn)入內(nèi)存。選用何種調(diào)度算法：先來(lái)先服務(wù)、短作業(yè)優(yōu)先、基于作業(yè)優(yōu)先級(jí)、響應(yīng)比高者優(yōu)先。6PPT課件3作業(yè)調(diào)度（高級(jí)調(diào)度、長(zhǎng)程調(diào)度、接納調(diào)度）定義數(shù)目過(guò)多：注意

批處理系統(tǒng)中，作業(yè)是首先進(jìn)入外存，然后經(jīng)由作業(yè)調(diào)度分批進(jìn)入內(nèi)存；

分時(shí)系統(tǒng)及實(shí)時(shí)系統(tǒng)中，由于對(duì)響應(yīng)時(shí)間有要求，因此用戶輸入的命令和數(shù)據(jù)等是直接進(jìn)入內(nèi)存的，無(wú)須配置作業(yè)調(diào)度機(jī)制。7PPT課件注意批處理系統(tǒng)中，作業(yè)是首先進(jìn)入外存，然1定義決定就緒隊(duì)列中的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)，然后由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作。低級(jí)調(diào)度是最基本的一種調(diào)度，多道批處理、分時(shí)、實(shí)時(shí)系統(tǒng)中都必須配置。2主要功能保存當(dāng)前進(jìn)程的處理機(jī)現(xiàn)場(chǎng)信息按某種算法（優(yōu)先數(shù)算法、輪轉(zhuǎn)法）選擇進(jìn)程將CPU分配給該進(jìn)程，恢復(fù)新進(jìn)程的處理機(jī)現(xiàn)場(chǎng)，讓其從斷點(diǎn)開(kāi)始執(zhí)行。低級(jí)調(diào)度（進(jìn)程調(diào)度、短程調(diào)度）8PPT課件1定義低級(jí)調(diào)度（進(jìn)程調(diào)度、短程調(diào)度）8PPT課件3進(jìn)程調(diào)度機(jī)制排隊(duì)器

將系統(tǒng)中的所有就緒進(jìn)程按某種方式排成一個(gè)或多個(gè)隊(duì)列，方便調(diào)度程序?qū)ふ?。分派器將選中進(jìn)程從后備隊(duì)列移出，將處理機(jī)分配給它上下文切換機(jī)制

兩次上下文切換：保存當(dāng)前進(jìn)程上下文，裝入dispatcher上下文；移出dispatcher上下文，裝入新選中進(jìn)程的上下文。9PPT課件3進(jìn)程調(diào)度機(jī)制9PPT課件4進(jìn)程調(diào)度方式非搶占方式一旦把處理機(jī)分配給某進(jìn)程后，一直讓它運(yùn)行下去，不能因?yàn)闀r(shí)鐘中斷等原因或由其它進(jìn)程搶占分配給它的處理機(jī)。直至該進(jìn)程完成，或因某事件阻塞，才能重新分配處理機(jī)。

優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，系統(tǒng)開(kāi)銷?。蝗秉c(diǎn)：難以滿足緊急任務(wù)的要求，可能造成難以預(yù)料的后果。實(shí)時(shí)系統(tǒng)中，不宜采用該方式。10PPT課件4進(jìn)程調(diào)度方式10PPT課件

搶占方式允許調(diào)度程序根據(jù)某種原則暫停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。

搶占原則：優(yōu)先權(quán)、短作業(yè)優(yōu)先、時(shí)間片。

優(yōu)點(diǎn)：防止長(zhǎng)進(jìn)程長(zhǎng)時(shí)間占用CPU，為大多數(shù)進(jìn)程提供更公平的服務(wù)，特別是能滿足實(shí)時(shí)任務(wù)的要求。缺點(diǎn)：與非搶占方式相比，開(kāi)銷較大。11PPT課件搶占方式11PPT課件

當(dāng)被掛起的進(jìn)程重新具備運(yùn)行條件且內(nèi)存稍有空閑時(shí)，把外存上的那些具備運(yùn)行條件的進(jìn)程重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上等待進(jìn)程調(diào)度。

中級(jí)調(diào)度12PPT課件當(dāng)被掛起的進(jìn)程重新具備運(yùn)行條件且內(nèi)存稍有3.2

調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型時(shí)間片完就緒隊(duì)列阻塞隊(duì)列CPU交互用戶進(jìn)程調(diào)度進(jìn)程完成等待事件事件發(fā)生FIFO隊(duì)列13PPT課件3.2調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型時(shí)具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型……具有高、低兩級(jí)調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列CPU時(shí)間片完作業(yè)調(diào)度進(jìn)程調(diào)度進(jìn)程完成等待事件1阻塞隊(duì)列阻塞隊(duì)列等待事件2等待事件n事件1發(fā)生事件2發(fā)生事件n發(fā)生后備隊(duì)列優(yōu)先權(quán)隊(duì)列14PPT課件具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列CPU時(shí)間片

具有高、低、中三級(jí)調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列緒就、掛起隊(duì)列CPU時(shí)間片完作業(yè)調(diào)度進(jìn)程調(diào)度進(jìn)程完成事件出現(xiàn)阻塞隊(duì)列掛起等待事件中級(jí)調(diào)度事件發(fā)生后備隊(duì)列塞阻、掛起隊(duì)列掛起同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型15PPT課件就緒隊(duì)列緒就、掛起隊(duì)列CPU時(shí)間片完作業(yè)進(jìn)程調(diào)度進(jìn)程完成事件面向用戶的準(zhǔn)則周轉(zhuǎn)時(shí)間短（批處理）響應(yīng)時(shí)間快（分時(shí)）截止時(shí)間保證（實(shí)時(shí)）優(yōu)先權(quán)準(zhǔn)則（all）選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則帶權(quán)周轉(zhuǎn)時(shí)間：作業(yè)的周轉(zhuǎn)時(shí)間與系統(tǒng)為它提供服務(wù)的時(shí)間之比周轉(zhuǎn)時(shí)間——作業(yè)被提交給系統(tǒng)開(kāi)始，到作業(yè)完成為止的這段時(shí)間間隔。包括：在外存后備隊(duì)列等待調(diào)度的時(shí)間；在內(nèi)存就緒隊(duì)列等待調(diào)度的時(shí)間；在CPU上執(zhí)行的時(shí)間；等待I/O操作的時(shí)間。響應(yīng)時(shí)間：用戶通過(guò)鍵盤(pán)提交請(qǐng)求開(kāi)始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止。包括：請(qǐng)求信息傳送到CPU的時(shí)間，CPU處理請(qǐng)求的時(shí)間，將響應(yīng)信息回送到終端顯示器的時(shí)間16PPT課件面向用戶的準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則帶權(quán)周轉(zhuǎn)時(shí)間：面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐量高處理機(jī)利用率好各類資源的平衡利用吞吐量：?jiǎn)挝粫r(shí)間內(nèi)，系統(tǒng)完成的作業(yè)數(shù)處理機(jī)利用率：一般在40%—90%各類資源：內(nèi)存、外存和外設(shè)的平衡利用17PPT課件面向系統(tǒng)的準(zhǔn)則吞吐量：?jiǎn)挝粫r(shí)間內(nèi)，系統(tǒng)完成的作業(yè)數(shù)處理機(jī)利用3.3

調(diào)度算法

根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法先來(lái)先服務(wù)算法短作業(yè)優(yōu)先算法高優(yōu)先權(quán)優(yōu)先算法時(shí)間片輪轉(zhuǎn)調(diào)度算法18PPT課件3.3調(diào)度算法根據(jù)系統(tǒng)的資源分配策略所先來(lái)先服務(wù)（FCFS）主要用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。用于作業(yè)調(diào)度：每次從后備作業(yè)隊(duì)列中選擇最先進(jìn)入的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后掛到就緒進(jìn)程隊(duì)列上。有利于長(zhǎng)作業(yè)，而不利于短作業(yè)。用于進(jìn)程調(diào)度：每次從就緒進(jìn)程隊(duì)列中選擇最先進(jìn)入的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。直到運(yùn)行完成進(jìn)程才會(huì)讓出處理機(jī)--非搶占式。性能評(píng)價(jià)：周轉(zhuǎn)時(shí)間

=完成時(shí)間–到達(dá)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間

=周轉(zhuǎn)時(shí)間/服務(wù)（運(yùn)行）時(shí)間19PPT課件先來(lái)先服務(wù)（FCFS）主要用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。1先來(lái)先服務(wù)（FCFS）20PPT課件先來(lái)先服務(wù)（FCFS）20PPT課件短作業(yè)/進(jìn)程優(yōu)先（SJ/PF）短作業(yè)優(yōu)先（SJF）從后備隊(duì)列中選擇估計(jì)運(yùn)行時(shí)間最短的作業(yè)，調(diào)入內(nèi)存運(yùn)行。短進(jìn)程優(yōu)先（SPF）從就緒隊(duì)列中選出估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行。直到運(yùn)行完成進(jìn)程才會(huì)讓出處理機(jī)--非搶占式。缺點(diǎn)：對(duì)長(zhǎng)作業(yè)不利，有可能長(zhǎng)期不被調(diào)度；完全沒(méi)考慮作業(yè)的緊迫程度（某些特殊的）；用戶做出的估計(jì)時(shí)間帶有很大的主觀性。21PPT課件短作業(yè)/進(jìn)程優(yōu)先（SJ/PF）短作業(yè)優(yōu)先（SJF）21P短作業(yè)/進(jìn)程優(yōu)先（SJ/PF）22PPT課件短作業(yè)/進(jìn)程優(yōu)先（SJ/PF）22PPT課件優(yōu)先級(jí)（FPF）既能用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。調(diào)度思想：從隊(duì)列中選擇優(yōu)先權(quán)最高的調(diào)度單元，裝入內(nèi)存或分配給處理機(jī)。對(duì)進(jìn)程調(diào)度而言，有非搶占式和搶占式兩種。把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程，直至完成或因某種原因阻塞，才讓出處理機(jī)。主要用于批處理系統(tǒng)中同樣是把CPU分給優(yōu)先權(quán)最高的進(jìn)程，但在該進(jìn)程執(zhí)行過(guò)程中，如有優(yōu)先級(jí)更高的進(jìn)程到來(lái)，則立即停止當(dāng)前進(jìn)程的執(zhí)行，將CPU分配給新到的優(yōu)先級(jí)最高的進(jìn)程。常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中。23PPT課件優(yōu)先級(jí)（FPF）既能用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。把處理機(jī)優(yōu)先權(quán)(0-255)靜態(tài)優(yōu)先權(quán)、動(dòng)態(tài)優(yōu)先權(quán)。優(yōu)先權(quán)在創(chuàng)建進(jìn)程時(shí)即確定，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，隨進(jìn)程的推進(jìn)或等待時(shí)間的增加而改變例如規(guī)定：就緒隊(duì)列中的進(jìn)程，隨等待時(shí)間的延長(zhǎng)，優(yōu)先權(quán)以速率α增長(zhǎng)；執(zhí)行中的進(jìn)程，隨執(zhí)行時(shí)間的延長(zhǎng)，優(yōu)先權(quán)以速率β下降。24PPT課件優(yōu)先權(quán)(0-255)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時(shí)即確定，且在進(jìn)程的整個(gè)高響應(yīng)比優(yōu)先調(diào)度算法動(dòng)態(tài)優(yōu)先權(quán)，與作業(yè)等待時(shí)間相關(guān)。

優(yōu)先權(quán)=響應(yīng)比（Rp）

=（等待時(shí)間+要求服務(wù)時(shí)間）/要求服務(wù)時(shí)間

=響應(yīng)時(shí)間/要求服務(wù)時(shí)間

分析：等待時(shí)間相同，要求服務(wù)時(shí)間越短，優(yōu)先級(jí)越高。有利于短作業(yè)。要求服務(wù)時(shí)間相同，等待時(shí)間越長(zhǎng)，優(yōu)先級(jí)越高。即FCFS。對(duì)于長(zhǎng)作業(yè)，優(yōu)先級(jí)隨等待時(shí)間的延長(zhǎng)而升高，終能獲得處理機(jī)。因此，該算法是一種折衷算法。缺點(diǎn)：頻繁計(jì)算響應(yīng)比，增加了系統(tǒng)開(kāi)銷。25PPT課件高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)先權(quán)=響應(yīng)比（Rp）分析：2時(shí)間片輪轉(zhuǎn)特別適用于分時(shí)系統(tǒng)的調(diào)度算法。實(shí)現(xiàn)方法：由計(jì)時(shí)器發(fā)出時(shí)鐘中斷，引起一次輪轉(zhuǎn)調(diào)度。26PPT課件時(shí)間片輪轉(zhuǎn)特別適用于分時(shí)系統(tǒng)的調(diào)度算法。26PPT課件基本思想：基于時(shí)鐘的剝奪。

以一定的時(shí)間間隔周期性產(chǎn)生一個(gè)時(shí)鐘中斷，當(dāng)中斷發(fā)生時(shí)，當(dāng)前正在運(yùn)行的進(jìn)程被置于就緒隊(duì)列末尾，然后基于FCFS選擇下一個(gè)就緒進(jìn)程運(yùn)行。保證就緒隊(duì)列中的所有進(jìn)程在給定的時(shí)間內(nèi)都能獲得一時(shí)間片（timeslice）的處理機(jī)執(zhí)行時(shí)間。27PPT課件基本思想：基于時(shí)鐘的剝奪。27PPT課件執(zhí)行過(guò)程1將系統(tǒng)中所有的就緒進(jìn)程按照FCFS原則，排成一個(gè)隊(duì)列。2每次調(diào)度時(shí)將CPU分派給隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片。時(shí)間片的長(zhǎng)度從幾個(gè)ms到幾百ms。3在一個(gè)時(shí)間片結(jié)束時(shí)，發(fā)生時(shí)鐘中斷。4調(diào)度程序據(jù)此暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾，并通過(guò)上下文切換執(zhí)行當(dāng)前的隊(duì)首進(jìn)程。5進(jìn)程可以未使用完一個(gè)時(shí)間片，就出讓CPU。28PPT課件執(zhí)行過(guò)程28PPT課件ABCD…FCPU完成超時(shí)阻塞時(shí)間片輪轉(zhuǎn)調(diào)度算法示意圖29PPT課件ABCD…FCPU完成超時(shí)阻塞時(shí)間片輪轉(zhuǎn)調(diào)度算法示意圖29P

最佳時(shí)間片的確定時(shí)間片的選取是實(shí)現(xiàn)各種調(diào)度算法的關(guān)鍵之處，而時(shí)間片的選定通常應(yīng)考慮終端數(shù)目，處理機(jī)能力、各終端任務(wù)的急迫程度、外存?zhèn)鬏斔俣鹊确矫娴囊蛩亍?/p>

①當(dāng)時(shí)間片很大時(shí)，大到一個(gè)進(jìn)程足以完成其全部運(yùn)行工作所需的時(shí)間，此時(shí)輪轉(zhuǎn)調(diào)度模式退化為FCFS模式。

②當(dāng)時(shí)間片非常小時(shí)，調(diào)度程序剝奪處理機(jī)的次數(shù)增多，這將加重了系統(tǒng)開(kāi)銷，系統(tǒng)性能降低，大多數(shù)時(shí)間都消耗在處理機(jī)的轉(zhuǎn)換上。30PPT課件最佳時(shí)間片的確定時(shí)間片的選多級(jí)反饋隊(duì)列調(diào)度算法

以上介紹的算法，都存在一定的局限性?，F(xiàn)在主流的操作系統(tǒng)，如UNIX、WindowsNT、Linux等，都使用一種綜合性的調(diào)度算法——多級(jí)反饋隊(duì)列調(diào)度算法。該算法綜合了上述三種算法以及多隊(duì)列調(diào)度算法的思想和優(yōu)點(diǎn)，總體調(diào)度性能優(yōu)越，適于各種類型的作業(yè)，但其實(shí)現(xiàn)也比較復(fù)雜。31PPT課件多級(jí)反饋隊(duì)列調(diào)度算法以上介紹的算法，都存在一定的局限性。3算法的基本思想是：

首先：系統(tǒng)按進(jìn)程優(yōu)先級(jí)設(shè)置了多級(jí)（比如n級(jí)，n≥2）就緒進(jìn)程隊(duì)列，從第一級(jí)隊(duì)列到最后一級(jí)隊(duì)列，優(yōu)先級(jí)越來(lái)越低。其次：每一級(jí)就緒隊(duì)列對(duì)應(yīng)一個(gè)不同的時(shí)間片。優(yōu)先權(quán)越高的隊(duì)列，進(jìn)程的時(shí)間片越小。再次：當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先被放到第一級(jí)隊(duì)列的隊(duì)尾。按照FCFS原則排隊(duì)等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如能在時(shí)間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)；如果在時(shí)間片內(nèi)未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊(duì)列的末尾，再依次按照FCFS原則等待調(diào)度。32PPT課件算法的基本思想是：首先：系統(tǒng)按進(jìn)程優(yōu)先級(jí)設(shè)置了多級(jí)（比如n最后：僅當(dāng)?shù)谝患?jí)隊(duì)列為空時(shí)，才調(diào)度第二級(jí)隊(duì)列中的進(jìn)程；如此下去，僅當(dāng)前面的n-1級(jí)隊(duì)列全部為空時(shí)，才去調(diào)度最后第n級(jí)隊(duì)列中的進(jìn)程。如果處理機(jī)正在第i隊(duì)列中為某進(jìn)程服務(wù)時(shí)，又有新的進(jìn)程進(jìn)入優(yōu)先權(quán)高的隊(duì)列（第1～(i-1)中任何一隊(duì)列），則系統(tǒng)搶占正在運(yùn)行的進(jìn)程的處理機(jī)，由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到剛才所在第i隊(duì)列的隊(duì)尾，重新進(jìn)行處理機(jī)調(diào)度。33PPT課件最后：僅當(dāng)?shù)谝患?jí)隊(duì)列為空時(shí)，才調(diào)度第二級(jí)隊(duì)列中的進(jìn)程；如此下多級(jí)反饋隊(duì)列調(diào)度算法的性能能較好地滿足各種類型用戶（進(jìn)程）的需要。終端（交互）型作業(yè)用戶短批處理作業(yè)用戶長(zhǎng)批處理作業(yè)用戶……

多級(jí)反饋隊(duì)列調(diào)度算法示意圖CPU時(shí)間片完進(jìn)程調(diào)度進(jìn)程完成就緒隊(duì)列一就緒隊(duì)列二就緒隊(duì)列三就緒隊(duì)列n時(shí)間片完時(shí)間片完34PPT課件多級(jí)反饋隊(duì)列調(diào)度算法的性能CPU時(shí)間進(jìn)程進(jìn)程完成就緒隊(duì)列一就習(xí)題

設(shè)有兩個(gè)優(yōu)先級(jí)相同的進(jìn)程P、Q，各自運(yùn)行的程序如下進(jìn)程PP1Y：=1；P2Y：=Y+Z；P3V（S1）；P4Z：=Y+3；P5P（S2）；P6Y：=Z+Y；進(jìn)程QQ1X：=1；Q2X：=X+1；Q3P（S1）；Q4X：=X+Y；Q5V（S2）；Q6Z：=X+Z；35PPT課件習(xí)題設(shè)有兩個(gè)優(yōu)先級(jí)相同的進(jìn)程P、Q，各自

其中，S1、S2為信號(hào)量，初值為0，已知Z=2，若調(diào)度程序執(zhí)行的策略為FIFO，試問(wèn)執(zhí)行序列和運(yùn)行結(jié)果是什么？X=5，Y=14，Z=1136PPT課件其中，S1、S2為信號(hào)量，初值為0，已知3.5產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因產(chǎn)生死鎖的必要條件處理死鎖的基本方法37PPT課件3.5產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因37PPT課死鎖

多個(gè)進(jìn)程在運(yùn)行過(guò)程中因爭(zhēng)奪資源而造成的一種僵局，當(dāng)進(jìn)程處于這種僵持狀態(tài)時(shí)，若無(wú)外力作用，它們都將無(wú)法向前推進(jìn)。

一組進(jìn)程中，每個(gè)進(jìn)程都無(wú)限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無(wú)法得到資源，這種現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱為死鎖進(jìn)程。38PPT課件死鎖多個(gè)進(jìn)程在運(yùn)行過(guò)程中因爭(zhēng)奪資源而造成的一種僵局，當(dāng)進(jìn)程3.5.1產(chǎn)生死鎖的原因

１資源不足導(dǎo)致的資源競(jìng)爭(zhēng)：多個(gè)進(jìn)程所共享的資源不足，引起它們對(duì)資源的競(jìng)爭(zhēng)而產(chǎn)生死鎖。２并發(fā)執(zhí)行的順序不當(dāng)：進(jìn)程運(yùn)行過(guò)程中，請(qǐng)求和釋放資源的順序不當(dāng)，而導(dǎo)致進(jìn)程死鎖.如P,V操作的順序不當(dāng)39PPT課件3.5.1產(chǎn)生死鎖的原因

１資源不足導(dǎo)致的資源競(jìng)爭(zhēng)：多個(gè)進(jìn)死鎖現(xiàn)象舉例40PPT課件死鎖現(xiàn)象舉例40PPT課件一競(jìng)爭(zhēng)資源引起死鎖

1．資源的分類：可剝奪和非剝奪性資源可剝奪性資源：CPU和主存例如：優(yōu)先權(quán)高的程可以剝奪低優(yōu)先權(quán)進(jìn)程的處理機(jī)。存儲(chǔ)器管理程序把進(jìn)程從一個(gè)存儲(chǔ)區(qū)移至另外一個(gè)存儲(chǔ)區(qū)，甚至將一進(jìn)程從內(nèi)存調(diào)出到外存上。不可剝奪性資源：磁帶機(jī)、打印機(jī)等當(dāng)系統(tǒng)把這類資源分配給某進(jìn)程后，再不能強(qiáng)行收回，只能在進(jìn)程用完后自動(dòng)釋放。41PPT課件一競(jìng)爭(zhēng)資源引起死鎖1．資源的分類：可剝奪和非剝奪性資源4

兩個(gè)進(jìn)程分別準(zhǔn)備打印一個(gè)非常大的磁帶文件（雙方都擁有部分資源，同時(shí)在請(qǐng)求對(duì)方已占有的資源。）打印機(jī)R1磁帶機(jī)R2P1P22．競(jìng)爭(zhēng)非剝奪性資源

42PPT課件兩個(gè)進(jìn)程分別準(zhǔn)備打印一個(gè)非常大的磁帶文件（雙方都擁有部分3．競(jìng)爭(zhēng)臨時(shí)性資源永久性資源：打印機(jī)資源屬于可順序重復(fù)使用的資源。臨時(shí)性資源：由一個(gè)進(jìn)程產(chǎn)生，被另一個(gè)進(jìn)程使用一短暫時(shí)間后便無(wú)用的資源。例如進(jìn)程通信時(shí)的消息。43PPT課件3．競(jìng)爭(zhēng)臨時(shí)性資源43PPT課件R1P1R2P2S1P1S2P3S3P244PPT課件R1P1R2P2S1P1S2P3S3P244PPT課件二進(jìn)程推進(jìn)順序不當(dāng)引起死鎖

資源少未必一定產(chǎn)生死鎖。就如同兩個(gè)人過(guò)獨(dú)木橋，如果兩個(gè)人都要先過(guò)，在獨(dú)木橋上僵持不肯后退，必然會(huì)因競(jìng)爭(zhēng)資源產(chǎn)生死鎖；但是，如果兩個(gè)人上橋前先看一看有無(wú)對(duì)方的人在橋上，當(dāng)無(wú)對(duì)方的人在橋上時(shí)自己才上橋，那么問(wèn)題就解決了。所以，如果程序設(shè)計(jì)得不合理，造成進(jìn)程推進(jìn)的順序不當(dāng)，也會(huì)出現(xiàn)死鎖。

45PPT課件二進(jìn)程推進(jìn)順序不當(dāng)引起死鎖資源少如果執(zhí)行序列為:P0、P1、q0、q1、P2、q2，則發(fā)生死鎖46PPT課件如果執(zhí)行序列為:P0、P1、q0、q1、P2、q2，則發(fā)生死p1Req(R1)p1Req(R2)p1ReL(R1)p1ReL(R2)p2Req(R2)p2Req(R1)p2ReL(R2)p2ReL(R1)p1p247PPT課件p1Req(R1)p1Req(R2)p1ReL(R1)p1R思考題：（北大95研）一個(gè)OS有20個(gè)進(jìn)程，競(jìng)爭(zhēng)使用65個(gè)同類資源，申請(qǐng)方式是逐個(gè)進(jìn)行的，一旦某個(gè)進(jìn)程獲得它所需要的全部資源，則立即歸還所有資源。每個(gè)進(jìn)程最多使用三個(gè)資源。若僅考慮這類資源，該系統(tǒng)有無(wú)可能產(chǎn)生死鎖，為什么？48PPT課件思考題：（北大95研）一個(gè)OS有20個(gè)進(jìn)程，競(jìng)爭(zhēng)使用65個(gè)同答：不可能。因?yàn)樗梨i產(chǎn)生的原因有兩點(diǎn)：系統(tǒng)資源不足或推進(jìn)順序不當(dāng)，在本題中，進(jìn)程所需的最大資源數(shù)為60，而系統(tǒng)共有該類資源65個(gè)，其資源數(shù)已足夠系統(tǒng)內(nèi)各進(jìn)程使用。49PPT課件答：不可能。49PPT課件互斥條件指進(jìn)程對(duì)所分配到的資源進(jìn)行排它性使用,即在一段時(shí)間內(nèi)某資源只能由一個(gè)進(jìn)程占有。如果此時(shí)還有其它進(jìn)程申請(qǐng)?jiān)撡Y源,則它只能阻塞,直至占有該資源的進(jìn)程釋放。占有且等待（請(qǐng)求和保持條件）進(jìn)程已經(jīng)保持了至少一個(gè)資源,但又提出了新的資源要求,而該資源又已被其它進(jìn)程占有,此時(shí)請(qǐng)求進(jìn)程阻塞,但又對(duì)已經(jīng)獲得的其它資源保持不放。3.5.2產(chǎn)生死鎖的必要條件

50PPT課件互斥條件3.5.2產(chǎn)生死鎖的必要條件

50PPT課件非搶占（非剝奪）條件進(jìn)程已獲得的資源,在未使用完之前,不能被剝奪,只能在使用完時(shí)由自己釋放。循環(huán)等待條件在發(fā)生死鎖時(shí),必然存在一個(gè)進(jìn)程-資源的封閉的環(huán)形鏈。即進(jìn)程集合{P0,P1,P2,…,Pn}中的P0正在等待一個(gè)P1占用的資源;P1正在等待P2占用的資源,……,Pn正在等待已被P0占用的資源.51PPT課件非搶占（非剝奪）條件51PPT課件①

死鎖的預(yù)防；

②

死鎖的避免；

③

死鎖的檢測(cè)和解除；

④

鴕鳥(niǎo)算法當(dāng)死鎖在計(jì)算機(jī)中很少出現(xiàn)時(shí)，比如說(shuō)每五年或更長(zhǎng)時(shí)間才出現(xiàn)一次時(shí)，人們就不必花費(fèi)更多的精力去解決它，而是采用類似鴕鳥(niǎo)一樣的辦法忽略它。3.5.3處理死鎖的基本方法

52PPT課件①

死鎖的預(yù)防；3.5.3處理死鎖的基本方法

52P預(yù)防死鎖

通過(guò)設(shè)置某些限制條件，破壞產(chǎn)生死鎖的４個(gè)必要條件中的一個(gè)或幾個(gè)條件，來(lái)預(yù)防發(fā)生死鎖。53PPT課件預(yù)防死鎖通過(guò)設(shè)置某些限制條件，破壞產(chǎn)生死鎖的４個(gè)必要條件中避免死鎖在資源的動(dòng)態(tài)分配過(guò)程中，用某種方法防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免發(fā)生死鎖。54PPT課件避免死鎖在資源的動(dòng)態(tài)分配過(guò)程中，用某種方法防止系統(tǒng)進(jìn)入不安全預(yù)防死鎖與避免死鎖的差別

預(yù)防死鎖所施加的限制條件比較嚴(yán)格，往往會(huì)限制進(jìn)程的并發(fā)執(zhí)行避免死鎖所施加的限制條件比較寬松，給進(jìn)程的并發(fā)執(zhí)行提供了較好的環(huán)境。55PPT課件預(yù)防死鎖與避免死鎖的差別預(yù)防死鎖所施加的限制條件比較嚴(yán)格，檢測(cè)死鎖事先并不采取任何限制性措施，允許系統(tǒng)在運(yùn)行過(guò)程中發(fā)生死鎖。但系統(tǒng)的檢測(cè)機(jī)構(gòu)應(yīng)能及時(shí)地檢測(cè)出死鎖的發(fā)生，并精確地確定與死鎖有關(guān)的進(jìn)程和資源。56PPT課件檢測(cè)死鎖事先并不采取任何限制性措施，允許系統(tǒng)在運(yùn)行過(guò)程中發(fā)生解除死鎖與死鎖的檢測(cè)措施配合使用。當(dāng)檢測(cè)到死鎖發(fā)生時(shí)，應(yīng)能夠?qū)⑦M(jìn)程從死鎖狀態(tài)解脫出來(lái)。常用的方法是撤消或掛起一切進(jìn)程，以便回收部分資源，再將這些資源分配給被阻塞的進(jìn)程，使之能繼續(xù)運(yùn)行。57PPT課件解除死鎖與死鎖的檢測(cè)措施配合使用。57PPT課件3.6預(yù)防和避免死鎖的方法死鎖的預(yù)防死鎖的避免１系統(tǒng)安全狀態(tài)２利用銀行家算法避免死鎖58PPT課件3.6預(yù)防和避免死鎖的方法死鎖的預(yù)防58PPT課件3.6.1死鎖的預(yù)防保證互斥條件由設(shè)備（非共享資源）的固有特性所決定,不能被破壞,應(yīng)加以保證。如打印機(jī)。59PPT課件3.6.1死鎖的預(yù)防保證互斥條件59PPT課件摒棄“請(qǐng)求和保持”條件采用靜態(tài)資源分配法

系統(tǒng)規(guī)定每一個(gè)進(jìn)程在開(kāi)始運(yùn)行前，都必須一次性地申請(qǐng)其在整個(gè)運(yùn)行過(guò)程所需的全部資源。若系統(tǒng)有足夠的資源，便把進(jìn)程想要的全部資源一次性地分配給它；若不能全部滿足進(jìn)程的資源請(qǐng)求，則一個(gè)資源也不分給它。因此，進(jìn)程在運(yùn)行過(guò)程中就不會(huì)再提出資源請(qǐng)求，從而破壞了“請(qǐng)求和保持”條件。60PPT課件摒棄“請(qǐng)求和保持”條件采用靜態(tài)資源分配法60PPT課件優(yōu)點(diǎn)：簡(jiǎn)單、安全、易實(shí)現(xiàn)。缺點(diǎn)：

（1）資源被嚴(yán)重浪費(fèi)（因?yàn)橐粋€(gè)進(jìn)程一次獲得其所需的全部資源并且獨(dú)占，其中有可能有些資源很少使用，嚴(yán)重惡化了資源利用率）。（2）進(jìn)程延遲運(yùn)行。（當(dāng)且僅當(dāng)進(jìn)程獲得其所需的全部資源后，才能開(kāi)始運(yùn)行，但有可能有些資源長(zhǎng)期被其他進(jìn)程占用，致使需要該資源的進(jìn)程遲遲不能運(yùn)行）

61PPT課件優(yōu)點(diǎn)：簡(jiǎn)單、安全、易實(shí)現(xiàn)。61PPT課件摒棄“不可剝奪條件”進(jìn)程逐個(gè)提出對(duì)資源的請(qǐng)求。即：一個(gè)已經(jīng)保持了某些資源的進(jìn)程，當(dāng)它再提出新的資源要求而不能立即得到滿足時(shí)，必須釋放它已經(jīng)保持的所有資源，待以后再需要時(shí)再重新申請(qǐng)。

實(shí)現(xiàn)復(fù)雜、代價(jià)大,反復(fù)申請(qǐng)/釋放資源,系統(tǒng)開(kāi)銷大,降低系統(tǒng)吞吐量

62PPT課件摒棄“不可剝奪條件”進(jìn)程逐個(gè)提出對(duì)資源的請(qǐng)求。即：一個(gè)已經(jīng)保摒棄“循環(huán)等待條件”（有序資源使用法）系統(tǒng)中的所有資源按類型都被賦予一個(gè)唯一的編號(hào)，每個(gè)進(jìn)程只能按編號(hào)的升序申請(qǐng)資源。對(duì)同一個(gè)進(jìn)程而言，它一旦申請(qǐng)了一個(gè)編號(hào)為i的資源，就不允許再申請(qǐng)編號(hào)比i小的資源了，因此，破壞了循環(huán)等待條件。63PPT課件摒棄“循環(huán)等待條件”（有序資源使用法）系統(tǒng)中的所有資源優(yōu)點(diǎn)：安全，資源利用率比靜態(tài)資源分配法有所提高。缺點(diǎn)：實(shí)現(xiàn)較困難，因?yàn)殡y給出合適的資源編號(hào)，不便于系統(tǒng)增添新設(shè)備，不便于用戶編程，且仍有一定的資源浪費(fèi)現(xiàn)象。64PPT課件優(yōu)點(diǎn)：安全，資源利用率比靜態(tài)資源分配法有所提高。64PPT課3.6.2死鎖的避免死鎖的避免是這樣一種對(duì)付死鎖的辦法：系統(tǒng)在運(yùn)行過(guò)程中采取動(dòng)態(tài)的資源分配策略，保證系統(tǒng)不進(jìn)入可能導(dǎo)致系統(tǒng)陷入死鎖狀態(tài)的所謂不安全狀態(tài)，以避免死鎖發(fā)生。

65PPT課件3.6.2死鎖的避免死鎖的避免是這樣一種對(duì)付死鎖的辦法死鎖的避免與死鎖預(yù)防策略不同：它不對(duì)進(jìn)程申請(qǐng)資源加任何限制，而是對(duì)進(jìn)程提出的每一次資源請(qǐng)求進(jìn)行動(dòng)態(tài)檢查，并根據(jù)檢查結(jié)果決定是否分配資源以滿足進(jìn)程的請(qǐng)求。由于采用了動(dòng)態(tài)的資源分配策略，所以資源利用率比死鎖的防止辦法高。

66PPT課件死鎖的避免與死鎖預(yù)防策略不同：它不對(duì)進(jìn)程申請(qǐng)資源加任何限一系統(tǒng)安全狀態(tài)１安全狀態(tài)若在某一時(shí)刻，系統(tǒng)中存在某種進(jìn)程序列，如<P1,P2,…,Pn>，如果系統(tǒng)按此序列為每個(gè)進(jìn)程分配其所需的資源，直至最大需求，每個(gè)進(jìn)程均可順利完成。稱此時(shí)系統(tǒng)的狀態(tài)為安全狀態(tài)，稱這樣的一個(gè)進(jìn)程序列<P1,P2,…,Pn>為安全序列。

67PPT課件一系統(tǒng)安全狀態(tài)１安全狀態(tài)67PPT課件安全序列的實(shí)質(zhì)是：序列中的每一個(gè)進(jìn)程Pi（i=1,2,…,n）到以后運(yùn)行完成尚需要的資源量不超過(guò)系統(tǒng)當(dāng)前剩余的資源量與所有在序列中排在它前面的進(jìn)程當(dāng)前所占有的資源量之和。

68PPT課件安全序列的實(shí)質(zhì)是：序列中的每一個(gè)進(jìn)程Pi（i=1,2,…

不安全狀態(tài)

若在某一時(shí)刻，系統(tǒng)中不存在一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。安全狀態(tài)與死鎖的關(guān)系只要系統(tǒng)處于安全狀態(tài),必定不會(huì)進(jìn)入死鎖狀態(tài)；死鎖狀態(tài)是不安全狀態(tài)不安全狀態(tài)不一定是死鎖狀態(tài)（不安全狀態(tài)可能導(dǎo)致死鎖）；

69PPT課件不安全狀態(tài)69PPT課件２安全狀態(tài)實(shí)例例：假定系統(tǒng)有三個(gè)進(jìn)程P1、P2、P3，共有12臺(tái)磁帶機(jī)。進(jìn)程P1總共要求10臺(tái)磁帶機(jī)，P2和P3分別要求4臺(tái)和九臺(tái)。設(shè)在T0時(shí)刻，進(jìn)程P1、P2和P3已經(jīng)獲得5臺(tái)、2臺(tái)和2臺(tái)，還有3臺(tái)空閑沒(méi)有分配。進(jìn)程最大需求已分配可用P11053P2P34229T0時(shí)刻系統(tǒng)時(shí)安全的。這時(shí)存在一個(gè)安全序列<P2，P1，P3>70PPT課件２安全狀態(tài)實(shí)例例：假定系統(tǒng)有三個(gè)進(jìn)程P1、P2、P3，共有1注意：

（1）系統(tǒng)在某一時(shí)刻的安全狀態(tài)可能不唯一，但這不影響對(duì)系統(tǒng)安全性的判斷。（2）安全狀態(tài)是非死鎖狀態(tài)，而不安全狀態(tài)并不一定是死鎖狀態(tài)。即系統(tǒng)處于安全狀態(tài)一定可以避免死鎖，而系統(tǒng)處于不安全狀態(tài)則僅僅可能進(jìn)入死鎖狀態(tài)。

安全狀態(tài)不安全狀態(tài)死鎖狀態(tài)71PPT課件注意：（1）系統(tǒng)在某一時(shí)刻的安全狀態(tài)可能不唯一，但這不影響二利用銀行家算法避免死鎖銀行家算法是最有代表性的避免死鎖算法，是Dijkstra提出的。其模型基于一個(gè)小城鎮(zhèn)的銀行家，他向一群客戶分別承諾了一定金額的貸款，而他知道所有客戶不可能同時(shí)都需要最大的貸款額。我們可將客戶比作進(jìn)程，銀行家比作操作系統(tǒng)。銀行家算法就是對(duì)每一個(gè)客戶的請(qǐng)求進(jìn)行檢查，檢查如果滿足它是否會(huì)引起不安全狀態(tài)。假如是，那么不滿足該請(qǐng)求；否，那么便滿足。72PPT課件二利用銀行家算法避免死鎖銀行家算法是最有代表性的避免死鎖算銀行家算法的實(shí)質(zhì)就是:要設(shè)法保證系統(tǒng)動(dòng)態(tài)分配資源后不進(jìn)入不安全狀態(tài)，以避免可能產(chǎn)生的死鎖。即：每當(dāng)進(jìn)程提出資源請(qǐng)求且系統(tǒng)的資源能夠滿足該請(qǐng)求時(shí)，系統(tǒng)將判斷如果滿足此次資源請(qǐng)求系統(tǒng)狀態(tài)是否安全，如果判斷結(jié)果為安全，則給該進(jìn)程分配資源，否則不分配資源，申請(qǐng)資源的進(jìn)程將阻塞。

73PPT課件銀行家算法的實(shí)質(zhì)就是:要設(shè)法保證系統(tǒng)動(dòng)態(tài)分配資源后不進(jìn)入不銀行家算法的執(zhí)行有個(gè)前提條件，即要求進(jìn)程預(yù)先提出自己的最大資源請(qǐng)求，并且假設(shè)系統(tǒng)擁有固定的資源總量。銀行家算法中所用的主要的數(shù)據(jù)結(jié)構(gòu)如下：(1)可利用資源向量Available

（剩余或可用資源量），記錄系統(tǒng)中各類資源的當(dāng)前可利用數(shù)目。如果Available[j]=k，

表示系統(tǒng)中現(xiàn)有Rj類資源k個(gè)。74PPT課件銀行家算法的執(zhí)行有個(gè)前提條件，即要求進(jìn)程預(yù)先提出自己的最大資(2)最大需求矩陣Max

每個(gè)進(jìn)程對(duì)各類資源的最大需求量Max[i,j](3)Allocation

已為每個(gè)進(jìn)程分配的數(shù)量或者說(shuō)每個(gè)進(jìn)程對(duì)各類資源當(dāng)前的占有量Allocation[i,j]。

(4)需求矩陣Need某進(jìn)程對(duì)各類資源尚需要的數(shù)目。

Need[i,j]=Max[i,j]－Allocation[i,j](5)請(qǐng)求向量Request

Requesti記錄進(jìn)程Pi當(dāng)前對(duì)各類資源的申請(qǐng)量，是銀行家算法的入口參數(shù)。

75PPT課件(2)最大需求矩陣Max75PPT課件當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：1.如果Requesti［j］

>

Need[i,j],則出錯(cuò)。2.如果Requesti［j］

>Available[i,j],則Pi阻塞；

3.系統(tǒng)試探把要求的資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Available[j]=Available[j]-Requesti［j］;Allocation[i,j]=Allocation[i,j]+Requesti［j］Need[i,j]

=Need[i,j]-Requesti［j］

;4.

系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將試探分配作廢，恢復(fù)原來(lái)的資源分配狀態(tài)，讓進(jìn)程Pi等待。

銀行家算法描述76PPT課件當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：銀行家算法描述1.設(shè)置兩個(gè)向量

①工作向量Work.

表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需要的各類資源的數(shù)目，開(kāi)始時(shí)，Work:=Available。

②Finish.

它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開(kāi)始時(shí)先做Finish[i]:=false；當(dāng)有足夠的資源分配給進(jìn)程時(shí)，令Finish[i]:=true.安全性子算法描述77PPT課件1.設(shè)置兩個(gè)向量安全性子算法描述77PPT課件執(zhí)行過(guò)程的描述：(1)初始化：work=available；finish［i］=false；(2)若按進(jìn)程編號(hào)順序找到了一個(gè)可加入安全序列的進(jìn)程即：滿足條件finish［i］=false且need[i,j]≤work[j]的進(jìn)程Pi

則①假設(shè)該進(jìn)程不久將完成任務(wù)歸還資源，置

work[j]=work[j]+allocation[i,j]finish[i]=true②重復(fù)執(zhí)行這一步；(3)若所有進(jìn)程的可完成標(biāo)志finish[i]為真，則返回邏輯真值（表示系統(tǒng)處于安全狀態(tài)）；(4)否則，返回邏輯假值（表示不安全）；

78PPT課件執(zhí)行過(guò)程的描述：(1)初始化：work=available；可以看出：銀行家算法從避免死鎖的角度上說(shuō)是非常有效的但是，從某種意義上說(shuō)，它缺乏實(shí)用價(jià)值，因?yàn)楹苌儆羞M(jìn)程能夠在運(yùn)行前就知道其所需資源的最大值，而且進(jìn)程數(shù)也不是固定的，往往在不斷地變化（如新用戶登錄或退出），況且原本可用的資源也可能突然間變成不可用（如磁帶機(jī)可能壞掉）。因此，在實(shí)際中，如果有，也只有極少的系統(tǒng)使用銀行家算法來(lái)避免死鎖。

79PPT課件可以看出：銀行家算法從避免死鎖的角度上說(shuō)是非常有效的79PP銀行家算法之例假定系統(tǒng)中有四個(gè)進(jìn)程{P1、P2、P3、P4}和三種類型的資源{R1，R2，R3}，資源的數(shù)量分別為9、3、6，在T0時(shí)刻的資源分配情況如圖:資源情況進(jìn)程MaxR1R2R3AllocationR1R2R3NeedR1R2R3AvailableR1R2R3P1322100222112P2613511102P3314211103P4422002420T0時(shí)刻是否安全？80PPT課件銀行家算法之例假定系統(tǒng)中有四個(gè)進(jìn)程{P1、P2、P3、P4}資源情況進(jìn)程MaxR1R2R3AllocationR1R2R3NeedR1R2R3AvailableR1R2R3P1322100222112P2613511102P3314211103P4422002420資源情況進(jìn)程WorkR1R2R3NeedR1R2R3AllocaR1R2R3Work’R1R2R3P2112102511623P1623222100723P3723103211934P493442000293681PPT課件資源情況進(jìn)程MaxAllocationNeedAvailabP2發(fā)出請(qǐng)求向量request2（1,0,1），系統(tǒng)按銀行家算法進(jìn)行檢查：

①request2（1,0,1）≤need2（1,0,2）；

②request2（1,0,1）≤available（1,1,2）；

③系統(tǒng)先假定可為P2分配資源，并修改available、allocation2和need2向量

資源情況進(jìn)程MaxR1R2R3AllocationR1R2R3NeedR1R2R3AvailableR1R2R3P1322100222011P2613612001P3314211103P4422002420表2-2為P2試分配資源后的有關(guān)資源數(shù)據(jù)

82PPT課件P2發(fā)出請(qǐng)求向量request2（1,0,1），系統(tǒng)按銀行家④再利用安全性檢測(cè)子算法檢查此時(shí)系統(tǒng)是否安全。如表2-3所示。

資源進(jìn)程WorkR1R2R3NeedR1R2R3AllocaR1R2R3Work’R1R2R3P1012001612623P2623222100723P3723103211934P4934420002936FinishTrueTrueTrueTrue83PPT課件④再利用安全性檢測(cè)子算法檢查此時(shí)系統(tǒng)是否安全。如表2-3所示例2.9

某系統(tǒng)有同類互斥資源m個(gè)，供n個(gè)進(jìn)程共享使用。如果每個(gè)進(jìn)程最多申請(qǐng)x個(gè)資源（1≤x≤m），

證明：當(dāng)n(x-1)+1≤m時(shí)，系統(tǒng)不會(huì)發(fā)生死鎖。

84PPT課件例2.9

某系統(tǒng)有同類互斥資源m個(gè)，供n個(gè)進(jìn)程共享使用。每個(gè)進(jìn)程最多申請(qǐng)x個(gè)資源，所以最壞情況是每個(gè)進(jìn)程都得到了（x-1）個(gè)資源，并且現(xiàn)在均需申請(qǐng)最后一個(gè)資源。此時(shí)，系統(tǒng)剩余資源數(shù)為m-n(x-1)，于是只要系統(tǒng)中至少還有一個(gè)資源可供使用，就可以使這n個(gè)進(jìn)程中某個(gè)進(jìn)程得到其所需要的全部資源，并能夠繼續(xù)執(zhí)行到完成，歸還資源可供其他進(jìn)程使用。因而不會(huì)發(fā)生死鎖。即只要m-n(x-1)≥1時(shí)，系統(tǒng)就一定不會(huì)發(fā)生死鎖。亦即當(dāng)n(x-1)+1≤m時(shí)，系統(tǒng)不會(huì)發(fā)生死鎖。

證明85PPT課件證明85PPT課件3.6死鎖的檢測(cè)與解除

死鎖的檢測(cè)１資源分配圖２死鎖定理

3死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu)死鎖的解除

86PPT課件3.6死鎖的檢測(cè)與解除死鎖的檢測(cè)86PPT課件3.6.1死鎖的檢測(cè)

系統(tǒng)進(jìn)行資源分配時(shí),若未采取任何限制措施,則系統(tǒng)必須提供檢測(cè)和解除死鎖的手段,即必須考慮以下兩個(gè)問(wèn)題:

保存有關(guān)資源的請(qǐng)求和分配信息提供一種算法，檢測(cè)系統(tǒng)是否已經(jīng)進(jìn)入死鎖狀態(tài)

87PPT課件3.6.1死鎖的檢測(cè)系統(tǒng)進(jìn)行資源分配時(shí)1資源分配圖p1p2進(jìn)程資源一個(gè)單位的該類資源資源請(qǐng)求邊資源分配邊88PPT課件1資源分配圖p1p2進(jìn)程資源一個(gè)單位的該類資源資源請(qǐng)求邊資2死鎖定理死鎖定理:S為死鎖狀態(tài)的充分條件是:當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡(jiǎn)化的。89PPT課件2死鎖定理死鎖定理:89PPT課件p1p21找到非孤立不阻塞進(jìn)程結(jié)點(diǎn)

經(jīng)過(guò)一系列化簡(jiǎn)，如果能夠使所有的結(jié)點(diǎn)成為孤立結(jié)點(diǎn)，則稱該圖是可以完全化簡(jiǎn)的所有的簡(jiǎn)化順序，能夠得到相同的不可化簡(jiǎn)圖90PPT課件p1p21找到非孤立不阻塞進(jìn)程結(jié)點(diǎn)經(jīng)過(guò)一系列3死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu)Work:=available;L:={Li|allocationi=0andrequesti=0}forallLi

不屬于Ldobeginforallrequesti<=workdobeginwork:=work+allocationi;Li并入Lendend若不能把所有Li都并入L，則存在死鎖91PPT課件3死鎖檢測(cè)中的數(shù)據(jù)結(jié)構(gòu)Work:=available;91

死鎖的檢測(cè)和恢復(fù)技術(shù)是指定期啟動(dòng)一個(gè)軟件檢測(cè)系統(tǒng)的狀態(tài)，若發(fā)現(xiàn)有死鎖存在，則采取措施恢復(fù)之。

由于死鎖是系統(tǒng)中的惡性小概率事件，死鎖檢測(cè)程序的多次執(zhí)行往往都不會(huì)調(diào)用一次死鎖解除程序，而這卻增加了系統(tǒng)開(kāi)銷，因此在設(shè)計(jì)操作系統(tǒng)時(shí)需要權(quán)衡檢測(cè)精度與時(shí)間開(kāi)銷。92PPT課件死鎖的檢測(cè)和恢復(fù)技術(shù)是指定期啟動(dòng)一個(gè)軟件檢測(cè)系統(tǒng)3.7.2死鎖的解除

常見(jiàn)的死鎖解除方法有以下兩種：

（1）撤消進(jìn)程法

撤消全部死鎖進(jìn)程：代價(jià)太大，該做法很少用。最小代價(jià)撤消法：首先計(jì)算死鎖進(jìn)程的撤消代價(jià)，然后依次選擇撤消代價(jià)最小的進(jìn)程，逐個(gè)撤消死鎖進(jìn)程，回收資源給其他進(jìn)程，直至死鎖不復(fù)存在。93PPT課件3.7.2死鎖的解除常見(jiàn)的死鎖解除方法有以下兩種：93（2）掛起進(jìn)程法

（剝奪資源）

使用掛起/激活機(jī)構(gòu)掛起一些進(jìn)程，剝奪它們的資源以解除死鎖，待條件滿足時(shí)，再激活進(jìn)程。

目前掛起法比較受到重視。

顯然，無(wú)論哪一種解除死鎖的方法，都需要很大的開(kāi)銷。但是死鎖的檢測(cè)與解除辦法不對(duì)系統(tǒng)的資源分配等加任何限制，因此是對(duì)付死鎖的諸辦法中資源利用率最高的一種辦法，在對(duì)安全性要求高的大型系統(tǒng)中常用。

94PPT課件（2）掛起進(jìn)程法（剝奪資源）使用習(xí)題三95PPT課件習(xí)題三95PPT課件1某進(jìn)程被喚醒后,立即投入了執(zhí)行,我們說(shuō)該系統(tǒng)采用了搶先調(diào)度方式,對(duì)嗎?錯(cuò)誤96PPT課件1某進(jìn)程被喚醒后,立即投入了執(zhí)行,我們說(shuō)該系統(tǒng)采用了搶先調(diào)2考慮下列資源分配策略：對(duì)資源的申請(qǐng)和釋放可以在任何時(shí)刻進(jìn)行。如果一進(jìn)程的資源得不到滿足，則檢查所有由于等待資源被阻塞的進(jìn)程。如果它們有申請(qǐng)進(jìn)程所需要的資源，則將這些資源取出分配給申請(qǐng)進(jìn)程。97PPT課件2考慮下列資源分配策略：97PPT課件例如：考慮一個(gè)有3類資源的系統(tǒng)，系統(tǒng)所有可用資源（4，2，2）。進(jìn)程A申請(qǐng)（2，2，1），可滿足；進(jìn)程B請(qǐng)求（1，0，1），可滿足；進(jìn)程A再請(qǐng)求（0，0，1），則被阻塞。此時(shí)，若C請(qǐng)求（2，0，0），它可以分到剩余資源（1，0，0），并從A已分到的資源中獲得一個(gè)資源，于是進(jìn)程A的分配向量變成（1，2，1），而需求向量變成（1，0，1）。98PPT課件例如：98PPT課件請(qǐng)問(wèn)：1這種分配方式會(huì)導(dǎo)致死鎖嗎？如果會(huì)，請(qǐng)舉一個(gè)例子；如果不會(huì)，請(qǐng)說(shuō)明產(chǎn)生死鎖的哪一個(gè)條件不成立？2這種分配方式會(huì)導(dǎo)致某些進(jìn)程的無(wú)限等待嗎？為什么？99PPT課件請(qǐng)問(wèn)：99PPT課件答：1該分配方式不會(huì)產(chǎn)生死鎖，因?yàn)樗粷M足死鎖的第三個(gè)必要條件，即不剝奪條件。進(jìn)程所獲得的資源在未使用完畢之前，可以被其他進(jìn)程剝奪。這樣，系統(tǒng)就不會(huì)產(chǎn)生死鎖。100PPT課件答：100PPT課件2

這種方法會(huì)導(dǎo)致某些進(jìn)程無(wú)限期的等待。因?yàn)楸蛔枞倪M(jìn)程的資源可以被剝奪，所以被阻塞的進(jìn)程所擁有的資源數(shù)量不會(huì)因?yàn)檫M(jìn)程的推進(jìn)而逐漸增加。這樣，隨著進(jìn)程的推進(jìn)，并不能保證進(jìn)程一定能獲得它所需要的全部資源。例如，本題中的進(jìn)程A申請(qǐng)（2，2，1）后再申請(qǐng)（0，0，1）被阻塞。此后，進(jìn)程C又剝奪了進(jìn)程A的一個(gè)資源，使得進(jìn)程A的資源變?yōu)椋?，2，1），其需求向量為（1，0，1）。之后，若再創(chuàng)建的進(jìn)程總是只申請(qǐng)第一和第三類資源，總是占有系統(tǒng)所剩余的第一和第三類資源的全部，且不被阻塞，那么，進(jìn)程A將會(huì)無(wú)限期的等待。101PPT課件2101PPT課件3一臺(tái)計(jì)算機(jī)有8臺(tái)磁帶機(jī)。它們由N個(gè)進(jìn)程競(jìng)爭(zhēng)使用，每個(gè)進(jìn)程可能需要3臺(tái)磁帶機(jī)。請(qǐng)問(wèn)N為多少時(shí)，系統(tǒng)沒(méi)有死鎖的危險(xiǎn)。說(shuō)明其原因？102PPT課件3一臺(tái)計(jì)算機(jī)有8臺(tái)磁帶機(jī)。它們由N個(gè)進(jìn)程競(jìng)爭(zhēng)使用，每個(gè)進(jìn)程答：當(dāng)N<=3的時(shí)候，系統(tǒng)沒(méi)有死鎖的危險(xiǎn)。因?yàn)楫?dāng)N=3時(shí)，最壞的情況下有兩個(gè)進(jìn)程可獲得3臺(tái)磁帶機(jī)，一個(gè)進(jìn)程獲得2臺(tái)磁帶機(jī)，此時(shí)該進(jìn)程只需要等待另兩個(gè)進(jìn)程之一執(zhí)行完畢，釋放其所擁有的磁帶機(jī)即可，所以不會(huì)產(chǎn)生死鎖。當(dāng)N=4時(shí)，最壞的情況下每個(gè)進(jìn)程都獲得2臺(tái)磁帶機(jī)，此時(shí)，沒(méi)有一個(gè)進(jìn)程可以獲得足夠的資源執(zhí)行完畢，所有進(jìn)程均在等待其它進(jìn)程釋放資源，形成死鎖。103PPT課件答：103PPT課件4假定某計(jì)算機(jī)系統(tǒng)有R1設(shè)備3臺(tái)，R2設(shè)備4臺(tái)，它們被P1、P2、P3、P4這4個(gè)進(jìn)程共享，且已知這4個(gè)進(jìn)程均以下面所示的順序使用現(xiàn)有設(shè)備。

申請(qǐng)R1

申請(qǐng)R2

申請(qǐng)R1

釋放R1

釋放R2

釋放R1請(qǐng)問(wèn)：1）說(shuō)明系統(tǒng)運(yùn)行過(guò)程中是否有產(chǎn)生死鎖的可能？為什么2）如果有，請(qǐng)舉例，并畫(huà)出該死鎖狀態(tài)的進(jìn)程-資源圖。104PPT課件4假定某計(jì)算機(jī)系統(tǒng)有R1設(shè)備3臺(tái)，R2設(shè)備4臺(tái)，它們被P1答：1）本題中，系統(tǒng)有R1設(shè)備3臺(tái)，R2設(shè)備4臺(tái)。系統(tǒng)的4個(gè)進(jìn)程需要使用的資源數(shù)為R1設(shè)備各2臺(tái)，R2設(shè)備各1臺(tái)。因此，系統(tǒng)資源不足，滿足進(jìn)程死鎖的第一個(gè)原因，因此可能會(huì)產(chǎn)生死鎖。2）當(dāng)3個(gè)進(jìn)程都執(zhí)行完第一步，開(kāi)始執(zhí)行第二步，另一個(gè)進(jìn)程會(huì)因沒(méi)有R1資源而阻塞；當(dāng)3個(gè)進(jìn)程都執(zhí)行完第二步再執(zhí)行第三步時(shí)，全部阻塞，系統(tǒng)進(jìn)入死鎖狀態(tài)。105PPT課件答：105PPT課件P1P4P3P2106PPT課件P1P4P3P2106PPT課件5某系統(tǒng)有R1、R2、R3共3類資源，在T0時(shí)刻，P1、P2、P3、P4這4個(gè)進(jìn)程對(duì)資源的占用和需求情況如下表，此刻系統(tǒng)的可用資源向量為（2，1，2），問(wèn)題：1）將系統(tǒng)中各種資源總數(shù)和此刻各進(jìn)程對(duì)各資源的需求數(shù)目用向量或矩陣表示出來(lái)；2）如果此時(shí)P1和P2均發(fā)出資源請(qǐng)求向量request(1，0，1)，為了保持系統(tǒng)安全性，應(yīng)該如何分配資源給這兩個(gè)進(jìn)程？說(shuō)明你所采用的策略的原因。3）如果2）中兩個(gè)請(qǐng)求立刻得到滿足后，系統(tǒng)此刻是否處于死鎖狀態(tài)？107PPT課件5某系統(tǒng)有R1、R2、R3共3類資源，在T0時(shí)刻，P1、P

Maxidemand

CurrentallocaP1322100P2613411P3314211P4422002108PPT課件Maxidemand6Dijkstra1995年提出的銀行家算法的主要思想是什么？它能夠用來(lái)解決實(shí)際中的死鎖問(wèn)題嗎？為什么？

109PPT課件6Dijkstra1995年提出的銀行家算法的主要思想是

銀行家算法代表解決死鎖問(wèn)題的一種策略。在實(shí)施資源分配之前，先計(jì)算該次分配后摒生的狀態(tài)是否安全，即是否存在一種順序，使得所有的進(jìn)程都能執(zhí)行結(jié)束。若安全則分配，否則拒絕分配。該算法雖然具有很好的理論意義，但在實(shí)際系統(tǒng)中卻很難使用。因?yàn)樗惴ㄋ僭O(shè)的條件，如進(jìn)程預(yù)知申請(qǐng)資源的最大數(shù)目，系統(tǒng)中進(jìn)程數(shù)目固定大呢感，在現(xiàn)實(shí)環(huán)境中并不成立。所以，由不成立的前提導(dǎo)出的結(jié)果很難說(shuō)明其正確性。110PPT課件銀行家算法代表解決死鎖問(wèn)題的一種策略。在7在什么條件下，一個(gè)進(jìn)程的解封（即由狀態(tài)Blocked變遷為Ready)會(huì)立即引起一個(gè)進(jìn)程的被調(diào)度（即由狀態(tài)Ready變遷為Running）?

111PPT課件7在什么條件下，一個(gè)進(jìn)程的解封（即由狀態(tài)Blocked變遷例如，當(dāng)CPU空閑，就緒隊(duì)列為空，那么一個(gè)進(jìn)程由于解除封鎖而進(jìn)入就緒時(shí)，就會(huì)立即引起調(diào)度。又比如，系統(tǒng)實(shí)行的剝奪式調(diào)度策略，當(dāng)一個(gè)比運(yùn)行進(jìn)程優(yōu)先級(jí)高的進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，就進(jìn)行重新調(diào)度。那么如果解封進(jìn)程的優(yōu)先級(jí)高于當(dāng)前運(yùn)行進(jìn)程的優(yōu)先級(jí)，顯然它的解封勢(shì)必引起一次重新調(diào)度112PPT課件例如，當(dāng)CPU空閑，就緒隊(duì)列為空，那么一個(gè)進(jìn)程由于解除封鎖而第三章處理機(jī)調(diào)度與死鎖要解決的三個(gè)問(wèn)題：WHAT：按什么原則分配CPU？

—進(jìn)程調(diào)度算法WHEN：何時(shí)分配CPU？

—進(jìn)程調(diào)度的時(shí)機(jī)HOW：如何分配CPU？

—CPU調(diào)度過(guò)程（進(jìn)程的上下文切換）113PPT課件第三章處理機(jī)調(diào)度與死鎖要解決的三個(gè)問(wèn)題：1PPT課件主要內(nèi)容

處理機(jī)調(diào)度的層次調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則調(diào)度算法實(shí)時(shí)調(diào)度產(chǎn)生死鎖的原因和必要條件預(yù)防和避免死鎖的辦法死鎖的檢測(cè)與解除114PPT課件主要內(nèi)容處理機(jī)調(diào)度的層次2PPT課件3.1處理機(jī)調(diào)度的層次高級(jí)調(diào)度1作業(yè)和作業(yè)步作業(yè)

不僅包含通常的程序和數(shù)據(jù)，還應(yīng)配備一份作業(yè)說(shuō)明書(shū)，系統(tǒng)根據(jù)作業(yè)說(shuō)明書(shū)對(duì)程序的運(yùn)行進(jìn)程控制。在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存。115PPT課件3.1處理機(jī)調(diào)度的層次高級(jí)調(diào)度1作業(yè)和作業(yè)步3PPT課件

作業(yè)步

作業(yè)運(yùn)行期間，每個(gè)作業(yè)都必須經(jīng)過(guò)若干個(gè)相對(duì)獨(dú)立、又相互關(guān)聯(lián)的順序加工步驟，才能得到結(jié)果，把其中的每一個(gè)加工步驟稱為一個(gè)作業(yè)步。

1）編譯

2）連接裝配

3）運(yùn)行作業(yè)流

若干個(gè)作業(yè)進(jìn)入系統(tǒng)后，被依次存放在外存上，形成輸入的作業(yè)流；在OS的控制下，逐個(gè)作業(yè)進(jìn)行處理，形成了處理作業(yè)流。

編譯程序?qū)υ闯绦蜻M(jìn)行編譯，生成若干個(gè)目標(biāo)程序段。將目標(biāo)程序段裝配成可執(zhí)行的目標(biāo)程序?qū)⒛繕?biāo)程序讀入內(nèi)存并控制其運(yùn)行116PPT課件作業(yè)步編譯程序?qū)υ闯绦蜻M(jìn)行編譯，生成若干個(gè)目標(biāo)程序段。將目2作業(yè)控制塊

多道批處理系統(tǒng)中，為每個(gè)作業(yè)配備一個(gè)作業(yè)控制塊（JCB），它是作業(yè)在系統(tǒng)中存在的標(biāo)志。作業(yè)運(yùn)行期間，系統(tǒng)按照J(rèn)CB中的信息對(duì)作業(yè)進(jìn)行控制。

JCB中保存了系統(tǒng)對(duì)作業(yè)進(jìn)行管理和調(diào)度所需的全部信息。例如：作業(yè)標(biāo)識(shí)、用戶名稱、用戶帳戶、作業(yè)類型、作業(yè)狀態(tài)、調(diào)度信息、資源需求、進(jìn)入系統(tǒng)時(shí)間、開(kāi)始處理時(shí)間、作業(yè)完成時(shí)間、作業(yè)退出時(shí)間、資源使用情況等。

117PPT課件2作業(yè)控制塊5PPT課件3作業(yè)調(diào)度（高級(jí)調(diào)度、長(zhǎng)程調(diào)度、接納調(diào)度）

定義按照一定的算法，從外存的后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源兩個(gè)決定

1決定接納多少個(gè)作業(yè)（多道程序度）

2決定接納哪些作業(yè)數(shù)目過(guò)多：每個(gè)進(jìn)程可以執(zhí)行的時(shí)間片就越小，單個(gè)進(jìn)程的周轉(zhuǎn)時(shí)間越長(zhǎng)；數(shù)目過(guò)少：資源利用率和系統(tǒng)吞吐量下降，應(yīng)考慮調(diào)度新的進(jìn)程進(jìn)入內(nèi)存。選用何種調(diào)度算法：先來(lái)先服務(wù)、短作業(yè)優(yōu)先、基于作業(yè)優(yōu)先級(jí)、響應(yīng)比高者優(yōu)先。118PPT課件3作業(yè)調(diào)度（高級(jí)調(diào)度、長(zhǎng)程調(diào)度、接納調(diào)度）定義數(shù)目過(guò)多：注意

批處理系統(tǒng)中，作業(yè)是首先進(jìn)入外存，然后經(jīng)由作業(yè)調(diào)度分批進(jìn)入內(nèi)存；

分時(shí)系統(tǒng)及實(shí)時(shí)系統(tǒng)中，由于對(duì)響應(yīng)時(shí)間有要求，因此用戶輸入的命令和數(shù)據(jù)等是直接進(jìn)入內(nèi)存的，無(wú)須配置作業(yè)調(diào)度機(jī)制。119PPT課件注意批處理系統(tǒng)中，作業(yè)是首先進(jìn)入外存，然1定義決定就緒隊(duì)列中的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)，然后由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作。低級(jí)調(diào)度是最基本的一種調(diào)度，多道批處理、分時(shí)、實(shí)時(shí)系統(tǒng)中都必須配置。2主要功能保存當(dāng)前進(jìn)程的處理機(jī)現(xiàn)場(chǎng)信息按某種算法（優(yōu)先數(shù)算法、輪轉(zhuǎn)法）選擇進(jìn)程將CPU分配給該進(jìn)程，恢復(fù)新進(jìn)程的處理機(jī)現(xiàn)場(chǎng)，讓其從斷點(diǎn)開(kāi)始執(zhí)行。低級(jí)調(diào)度（進(jìn)程調(diào)度、短程調(diào)度）120PPT課件1定義低級(jí)調(diào)度（進(jìn)程調(diào)度、短程調(diào)度）8PPT課件3進(jìn)程調(diào)度機(jī)制排隊(duì)器

將系統(tǒng)中的所有就緒進(jìn)程按某種方式排成一個(gè)或多個(gè)隊(duì)列，方便調(diào)度程序?qū)ふ?。分派器將選中進(jìn)程從后備隊(duì)列移出，將處理機(jī)分配給它上下文切換機(jī)制

兩次上下文切換：保存當(dāng)前進(jìn)程上下文，裝入dispatcher上下文；移出dispatcher上下文，裝入新選中進(jìn)程的上下文。121PPT課件3進(jìn)程調(diào)度機(jī)制9PPT課件4進(jìn)程調(diào)度方式非搶占方式一旦把處理機(jī)分配給某進(jìn)程后，一直讓它運(yùn)行下去，不能因?yàn)闀r(shí)鐘中斷等原因或由其它進(jìn)程搶占分配給它的處理機(jī)。直至該進(jìn)程完成，或因某事件阻塞，才能重新分配處理機(jī)。

優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，系統(tǒng)開(kāi)銷??；缺點(diǎn)：難以滿足緊急任務(wù)的要求，可能造成難以預(yù)料的后果。實(shí)時(shí)系統(tǒng)中，不宜采用該方式。122PPT課件4進(jìn)程調(diào)度方式10PPT課件

搶占方式允許調(diào)度程序根據(jù)某種原則暫停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。

搶占原則：優(yōu)先權(quán)、短作業(yè)優(yōu)先、時(shí)間片。

優(yōu)點(diǎn)：防止長(zhǎng)進(jìn)程長(zhǎng)時(shí)間占用CPU，為大多數(shù)進(jìn)程提供更公平的服務(wù)，特別是能滿足實(shí)時(shí)任務(wù)的要求。缺點(diǎn)：與非搶占方式相比，開(kāi)銷較大。123PPT課件搶占方式11PPT課件

當(dāng)被掛起的進(jìn)程重新具備運(yùn)行條件且內(nèi)存稍有空閑時(shí)，把外存上的那些具備運(yùn)行條件的進(jìn)程重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上等待進(jìn)程調(diào)度。

中級(jí)調(diào)度124PPT課件當(dāng)被掛起的進(jìn)程重新具備運(yùn)行條件且內(nèi)存稍有3.2

調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型時(shí)間片完就緒隊(duì)列阻塞隊(duì)列CPU交互用戶進(jìn)程調(diào)度進(jìn)程完成等待事件事件發(fā)生FIFO隊(duì)列125PPT課件3.2調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型時(shí)具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型……具有高、低兩級(jí)調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列CPU時(shí)間片完作業(yè)調(diào)度進(jìn)程調(diào)度進(jìn)程完成等待事件1阻塞隊(duì)列阻塞隊(duì)列等待事件2等待事件n事件1發(fā)生事件2發(fā)生事件n發(fā)生后備隊(duì)列優(yōu)先權(quán)隊(duì)列126PPT課件具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列CPU時(shí)間片

具有高、低、中三級(jí)調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列緒就、掛起隊(duì)列CPU時(shí)間片完作業(yè)調(diào)度進(jìn)程調(diào)度進(jìn)程完成事件出現(xiàn)阻塞隊(duì)列掛起等待事件中級(jí)調(diào)度事件發(fā)生后備隊(duì)列塞阻、掛起隊(duì)列掛起同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型127PPT課件就緒隊(duì)列緒就、掛起隊(duì)列CPU時(shí)間片完作業(yè)進(jìn)程調(diào)度進(jìn)程完成事件面向用戶的準(zhǔn)則周轉(zhuǎn)時(shí)間短（批處理）響應(yīng)時(shí)間快（分時(shí)）截止時(shí)間保證（實(shí)時(shí)）優(yōu)先權(quán)準(zhǔn)則（all）選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則帶權(quán)周轉(zhuǎn)時(shí)間：作業(yè)的周轉(zhuǎn)時(shí)間與系統(tǒng)為它提供服務(wù)的時(shí)間之比周轉(zhuǎn)時(shí)間——作業(yè)被提交給系統(tǒng)開(kāi)始，到作業(yè)完成為止的這段時(shí)間間隔。包括：在外存后備隊(duì)列等待調(diào)度的時(shí)間；在內(nèi)存就緒隊(duì)列等待調(diào)度的時(shí)間；在CPU上執(zhí)行的時(shí)間；等待I/O操作的時(shí)間。響應(yīng)時(shí)間：用戶通過(guò)鍵盤(pán)提交請(qǐng)求開(kāi)始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止。包括：請(qǐng)求信息傳送到CPU的時(shí)間，CPU處理請(qǐng)求的時(shí)間，將響應(yīng)信息回送到終端顯示器的時(shí)間128PPT課件面向用戶的準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則帶權(quán)周轉(zhuǎn)時(shí)間：面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐量高處理機(jī)利用率好各類資源的平衡利用吞吐量：?jiǎn)挝粫r(shí)間內(nèi)，系統(tǒng)完成的作業(yè)數(shù)處理機(jī)利用率：一般在40%—90%各類資源：內(nèi)存、外存和外設(shè)的平衡利用129PPT課件面向系統(tǒng)的準(zhǔn)則吞吐量：?jiǎn)挝粫r(shí)間內(nèi)，系統(tǒng)完成的作業(yè)數(shù)處理機(jī)利用3.3

調(diào)度算法

根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法先來(lái)先服務(wù)算法短作業(yè)優(yōu)先算法高優(yōu)先權(quán)優(yōu)先算法時(shí)間片輪轉(zhuǎn)調(diào)度算法130PPT課件3.3調(diào)度算法根據(jù)系統(tǒng)的資源分配策略所先來(lái)先服務(wù)（FCFS）主要用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。用于作業(yè)調(diào)度：每次從后備作業(yè)隊(duì)列中選擇最先進(jìn)入的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后掛到就緒進(jìn)程隊(duì)列上。有利于長(zhǎng)作業(yè)，而不利于短作業(yè)。用于進(jìn)程調(diào)度：每次從就緒進(jìn)程隊(duì)列中選擇最先進(jìn)入的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。直到運(yùn)行完成進(jìn)程才會(huì)讓出處理機(jī)--非搶占式。性能評(píng)價(jià)：周轉(zhuǎn)時(shí)間

=完成時(shí)間–到達(dá)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間

=周轉(zhuǎn)時(shí)間/服務(wù)（運(yùn)行）時(shí)間131PPT課件先來(lái)先服務(wù)（FCFS）主要用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。1先來(lái)先服務(wù)（FCFS）132PPT課件先來(lái)先服務(wù)（FCFS）20PPT課件短作業(yè)/進(jìn)程優(yōu)先（SJ/PF）短作業(yè)優(yōu)先（SJF）從后備隊(duì)列中選擇估計(jì)運(yùn)行時(shí)間最短的作業(yè)，調(diào)入內(nèi)存運(yùn)行。短進(jìn)程優(yōu)先（SPF）從就緒隊(duì)列中選出估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行。直到運(yùn)行完成進(jìn)程才會(huì)讓出處理機(jī)--非搶占式。缺點(diǎn)：對(duì)長(zhǎng)作業(yè)不利，有可能長(zhǎng)期不被調(diào)度；完全沒(méi)考慮作業(yè)的緊迫程度（某些特殊的）；用戶做出的估計(jì)時(shí)間帶有很大的主觀性。133PPT課件短作業(yè)/進(jìn)程優(yōu)先（SJ/PF）短作業(yè)優(yōu)先（SJF）21P短作業(yè)/進(jìn)程優(yōu)先（SJ/PF）134PPT課件短作業(yè)/進(jìn)程優(yōu)先（SJ/PF）22PPT課件優(yōu)先級(jí)（FPF）既能用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。調(diào)度思想：從隊(duì)列中選擇優(yōu)先權(quán)最高的調(diào)度單元，裝入內(nèi)存或分配給處理機(jī)。對(duì)進(jìn)程調(diào)度而言，有非搶占式和搶占式兩種。把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程，直至完成或因某種原因阻塞，才讓出處理機(jī)。主要用于批處理系統(tǒng)中同樣是把CPU分給優(yōu)先權(quán)最高的進(jìn)程，但在該進(jìn)程執(zhí)行過(guò)程中，如有優(yōu)先級(jí)更高的進(jìn)程到來(lái)，則立即停止當(dāng)前進(jìn)程的執(zhí)行，將CPU分配給新到的優(yōu)先級(jí)最高的進(jìn)程。常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中。135PPT課件優(yōu)先級(jí)（FPF）既能用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。把處理機(jī)優(yōu)先權(quán)(0-255)靜態(tài)優(yōu)先權(quán)、動(dòng)態(tài)優(yōu)先權(quán)。優(yōu)先權(quán)在創(chuàng)建進(jìn)程時(shí)即確定，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，隨進(jìn)程的推進(jìn)或等待時(shí)間的增加而改變例如規(guī)定：就緒隊(duì)列中的進(jìn)程，隨等待時(shí)間的延長(zhǎng)，優(yōu)先權(quán)以速率α增長(zhǎng)；執(zhí)行中的進(jìn)程，隨執(zhí)行時(shí)間的延長(zhǎng)，優(yōu)先權(quán)以速率β下降。136PPT課件優(yōu)先權(quán)(0-255)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時(shí)即確定，