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

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

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

—進程調(diào)度的時機HOW：如何分配CPU？

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

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

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

作業(yè)步

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

1）編譯

2）連接裝配

3）運行作業(yè)流

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

調(diào)度算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

多個進程在運行過程中因爭奪資源而造成的一種僵局，當進程處于這種僵持狀態(tài)時，若無外力作用，它們都將無法向前推進。

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

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

１資源不足導致的資源競爭：多個進死鎖現(xiàn)象舉例40PPT課件死鎖現(xiàn)象舉例40PPT課件一競爭資源引起死鎖

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

兩個進程分別準備打印一個非常大的磁帶文件（雙方都擁有部分資源，同時在請求對方已占有的資源。）打印機R1磁帶機R2P1P22．競爭非剝奪性資源

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

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

45PPT課件二進程推進順序不當引起死鎖資源少如果執(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研）一個OS有20個進程，競爭使用65個同類資源，申請方式是逐個進行的，一旦某個進程獲得它所需要的全部資源，則立即歸還所有資源。每個進程最多使用三個資源。若僅考慮這類資源，該系統(tǒng)有無可能產(chǎn)生死鎖，為什么？48PPT課件思考題：（北大95研）一個OS有20個進程，競爭使用65個同答：不可能。因為死鎖產(chǎn)生的原因有兩點：系統(tǒng)資源不足或推進順序不當，在本題中，進程所需的最大資源數(shù)為60，而系統(tǒng)共有該類資源65個，其資源數(shù)已足夠系統(tǒng)內(nèi)各進程使用。49PPT課件答：不可能。49PPT課件互斥條件指進程對所分配到的資源進行排它性使用,即在一段時間內(nèi)某資源只能由一個進程占有。如果此時還有其它進程申請該資源,則它只能阻塞,直至占有該資源的進程釋放。占有且等待（請求和保持條件）進程已經(jīng)保持了至少一個資源,但又提出了新的資源要求,而該資源又已被其它進程占有,此時請求進程阻塞,但又對已經(jīng)獲得的其它資源保持不放。3.5.2產(chǎn)生死鎖的必要條件

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

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

死鎖的預防；

②

死鎖的避免；

③

死鎖的檢測和解除；

④

鴕鳥算法當死鎖在計算機中很少出現(xiàn)時，比如說每五年或更長時間才出現(xiàn)一次時，人們就不必花費更多的精力去解決它，而是采用類似鴕鳥一樣的辦法忽略它。3.5.3處理死鎖的基本方法

52PPT課件①

死鎖的預防；3.5.3處理死鎖的基本方法

52P預防死鎖

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

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

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

（1）資源被嚴重浪費（因為一個進程一次獲得其所需的全部資源并且獨占，其中有可能有些資源很少使用，嚴重惡化了資源利用率）。（2）進程延遲運行。（當且僅當進程獲得其所需的全部資源后，才能開始運行，但有可能有些資源長期被其他進程占用，致使需要該資源的進程遲遲不能運行）

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

實現(xiàn)復雜、代價大,反復申請/釋放資源,系統(tǒng)開銷大,降低系統(tǒng)吞吐量

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

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

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

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

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

不安全狀態(tài)

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

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

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

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

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

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

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

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

已為每個進程分配的數(shù)量或者說每個進程對各類資源當前的占有量Allocation[i,j]。

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

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

Requesti記錄進程Pi當前對各類資源的申請量，是銀行家算法的入口參數(shù)。

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

>

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

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

3.系統(tǒng)試探把要求的資源分配給進程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)。若安全，正式將資源分配給進程Pi，以完成本次分配；否則，將試探分配作廢，恢復原來的資源分配狀態(tài)，讓進程Pi等待。

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

①工作向量Work.

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

②Finish.

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

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

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

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

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

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

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

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

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

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

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

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

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

84PPT課件例2.9

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

證明85PPT課件證明85PPT課件3.6死鎖的檢測與解除

死鎖的檢測１資源分配圖２死鎖定理

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

86PPT課件3.6死鎖的檢測與解除死鎖的檢測86PPT課件3.6.1死鎖的檢測

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

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

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

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

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

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

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

常見的死鎖解除方法有以下兩種：

（1）撤消進程法

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

（剝奪資源）

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

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

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

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

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

申請R1

申請R2

申請R1

釋放R1

釋放R2

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

Maxidemand

CurrentallocaP1322100P2613411P3314211P4422002108PPT課件Maxidemand6Dijkstra1995年提出的銀行家算法的主要思想是什么？它能夠用來解決實際中的死鎖問題嗎？為什么？

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

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

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

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

—進程調(diào)度的時機HOW：如何分配CPU？

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

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

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

作業(yè)步

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

1）編譯

2）連接裝配

3）運行作業(yè)流

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

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

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

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

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

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

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

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

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

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

將系統(tǒng)中的所有就緒進程按某種方式排成一個或多個隊列，方便調(diào)度程序?qū)ふ摇７峙善鲗⑦x中進程從后備隊列移出，將處理機分配給它上下文切換機制

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

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

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

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

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

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

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

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

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

調(diào)度算法

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

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

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