處理機管理課件

2.2處理機管理進程的概念進程的控制進程的調(diào)度進程的互斥與同步進程的通信死鎖多道程序系統(tǒng)程序A程序BOS調(diào)度I/OAI/OBt1t2如何把CPU合理地分配給某個需要的程序，并在其用完后予以回收。合理利用及減少開銷!分配回收處理機管理的核心問題CPU2.2.1進程的概念

一、程序與進程程序：由若干條具有一定功能的機器指令所組成的解題順序和步驟。順序執(zhí)行（單道系統(tǒng)）并發(fā)執(zhí)行（多道系統(tǒng)）順序性封閉性可再現(xiàn)性程序執(zhí)行嚴格按照一定順序，不受外界因素影響，結(jié)果只由初始條件決定相互約束資源爭奪與共享程序執(zhí)行是相互交替穿插進行，執(zhí)行次序每次變化；受外界影響，結(jié)果與速度有關(guān)前驅(qū)圖有向無環(huán)圖節(jié)點：表示一條語句，或一段程序有向線段：表示語句之間的順序關(guān)系無環(huán)：當程序中出現(xiàn)循環(huán)時，一般將整個循環(huán)作為一個節(jié)點a1=5;b1=a1+5;print(b1);I1C1P1InputCalculatePrint前驅(qū)圖a1=5;b1=a1+5;print(b1)；a3=5;b3=a3–10;print(b3)；a2=5;b2=a2+6;print(b2)；I1C1P1程序1程序2程序3I2C2P2I3C3P3程序1程序2程序3I1輸入處理機打印機I2C1I3C2P1C3P2t1t2t3t4t7程序順序執(zhí)行：t5t6t8P3t9x=3y=x+2printf(y)x=1y=x+5printf(y)順序執(zhí)行t2t1t3t4t5t6順序執(zhí)行結(jié)果：y=5y=6并發(fā)執(zhí)行（一）x=3y=x+2printf(y)x=1y=x+5printf(y)并發(fā)執(zhí)行t2t1t3t4t5t6結(jié)果：y=3y=3并發(fā)執(zhí)行（二）x=3y=x+2printf(y)y=x＋5x=1printf(y)并發(fā)執(zhí)行t2t1t3t4t5t6結(jié)果：y=？y=3可見：

程序的概念已無法描述動態(tài)執(zhí)行過程中的并發(fā)活動，解決辦法？——引入進程來描述程序的一次執(zhí)行，使并發(fā)執(zhí)行的程序保持“可再現(xiàn)性”。進程包括：執(zhí)行現(xiàn)場的保留、資源的分配情況、程序的執(zhí)行位置等。進程的定義：進程是可并發(fā)執(zhí)行的程序在給定數(shù)據(jù)集合上的一次執(zhí)行過程；是系統(tǒng)進行資源分配和調(diào)度的一個獨立的基本單位和實體；是指執(zhí)行一個映象程序的總環(huán)境。1、程序是指令的集合，是靜態(tài)概念進程是程序的執(zhí)行過程，是動態(tài)概念2、程序可作為軟件資源長期保存進程只是一次短暫活動或過程3、一個程序可對應(yīng)多個進程一個進程可包含多段程序程序與進程比較二、進程的特征動態(tài)性并發(fā)性獨立性異步性具備生命周期，可以被建立、掛起、撤銷進程執(zhí)行時間時間重疊資源分配的基本單位，相對獨立速度不可預(yù)知，“走走停停”三、進程的描述PCB數(shù)據(jù)程序進程的結(jié)構(gòu)：進程控制塊（ProcessControlBlock）：操作系統(tǒng)用來描述進程執(zhí)行情況和狀態(tài)變化的一種專門數(shù)據(jù)結(jié)構(gòu)。內(nèi)容：調(diào)度信息和現(xiàn)場信息典型的進程控制塊PCB結(jié)構(gòu)進程標識符進程狀態(tài)CPU現(xiàn)場（程序狀態(tài)字、寄存器內(nèi)容等）資源清單優(yōu)先級隊列指針、家族關(guān)系通信機制（信箱或消息隊列）同步機制（信號量）存儲位置一串數(shù)值，供計算機系統(tǒng)使用PCB的作用PCB可唯一標識一個進程PCB中的信息為進程的控制提供依據(jù)PCB將程序變成了進程PCB是進程在系統(tǒng)中存在的唯一標志。PCB進程一一對應(yīng)PCBs的組織方式系統(tǒng)如何管理多個進程的?將各進程的PCB以一定的方式組織起來鏈接方式索引方式1241015四、進程的三種基本狀態(tài)就緒狀態(tài)(Ready)執(zhí)行狀態(tài)(Executing)等待狀態(tài)(Wait)獲得了除了CPU外的一切所需資源，具備執(zhí)行條件占有CPU，正在執(zhí)行。（唯一的）因等待某種事件而暫時不能執(zhí)行進程狀態(tài)的轉(zhuǎn)換新進程就緒執(zhí)行結(jié)束阻塞接納進程調(diào)度中斷或時間片用完完成I/O請求或等待某事件I/O完成或事件發(fā)生狀態(tài)轉(zhuǎn)換原因圖狀態(tài)轉(zhuǎn)換執(zhí)行圖新進程就緒執(zhí)行結(jié)束阻塞進入就緒隊列分配CPU使用權(quán)強制放棄CPU回到就緒隊列釋放所有資源進程主動放棄CPU進入阻塞等待隊列進程被釋放回到就緒隊列進程狀態(tài)轉(zhuǎn)換歸納：新進程就緒狀態(tài)事件動作接納進入就緒隊列就緒執(zhí)行進程調(diào)度分配CPU執(zhí)行結(jié)束完成釋放資源執(zhí)行阻塞時間片到時高優(yōu)先中斷系統(tǒng)剝奪CPU執(zhí)行就緒I/O請求等待某事件進程放棄CPU進入阻塞等待隊列阻塞就緒阻塞事件釋放進程進入就緒隊列注意：就緒阻塞阻塞執(zhí)行執(zhí)行就緒進程從執(zhí)行態(tài)到阻塞態(tài)是主動的進程發(fā)現(xiàn)需要等待某一事件，主動向系統(tǒng)申請進入阻塞態(tài)進程從阻塞態(tài)到就緒態(tài)是被動的當系統(tǒng)（或其它進程）發(fā)現(xiàn)阻塞進程阻塞的條件已釋放，向系統(tǒng)申請將該阻塞進程置為就緒態(tài)2.2.2進程的控制進程的控制——控制進程在其生命周期的各種活動及狀態(tài)轉(zhuǎn)換。通過操作系統(tǒng)的原語（primitive）來實現(xiàn)。原語：用以完成特定功能的不可分割的一段程序，原語的執(zhí)行過程是不可中斷的。創(chuàng)建原語撤銷原語阻塞原語喚醒原語一、創(chuàng)建原語：

實質(zhì)是創(chuàng)建進程控制塊申請空閑PCB1向PCB填入信息2設(shè)置進程為就緒狀態(tài)3進程進入就緒隊列4進程創(chuàng)建步驟二、撤銷原語進程撤銷步驟檢索PCB，找到1撤銷改進程及其子進程2釋放資源3撤銷PCB4進程完成任務(wù)或異常中斷三、阻塞原語阻塞執(zhí)行阻塞原語引發(fā)阻塞的事件啟動I/O操作等待新數(shù)據(jù)無工作可做請求系統(tǒng)服務(wù)中斷CPU工作1保存CPU信息到PCB中2設(shè)為阻塞態(tài)3PCB進入阻塞隊列4進程阻塞步驟四、喚醒原語就緒等待喚醒原語引發(fā)喚醒的事件服務(wù)完成新數(shù)據(jù)到達新任務(wù)下達I/O操作完成在等待隊列查找1設(shè)置進程PCB為就緒態(tài)2從等待隊列撤銷3PCB進入就緒隊列4進程喚醒步驟2.2.3進程的調(diào)度含義：目的：對象：處理機調(diào)度。為各個進程分配處理機使每個進程都能合理的使用處理機，得到及時的響應(yīng)處于就緒隊列的進程

進程調(diào)度的任務(wù)是控制協(xié)調(diào)進程對CPU的競爭，即按一定的調(diào)度算法從就緒隊列中選中一個進程，把CPU的使用權(quán)交給被選中的進程。一、進程調(diào)度的原因進程執(zhí)行完畢；進程等待某個事件阻塞；進程的時間片用完；有新進程（高優(yōu)先級或其他）進入就緒隊列；剝奪式（搶占式）非剝奪式（非搶占式）系統(tǒng)按照某種原則剝奪現(xiàn)行進程的CPU使用權(quán)，并交給其他進程現(xiàn)行進程的CPU使用權(quán)無法剝奪，除非由于時間片完或者進程自身原因才能交出CPU使用權(quán)。高優(yōu)先權(quán)短進程二、進程調(diào)度的方式三、進程調(diào)度的功能記錄系統(tǒng)中所有進程的執(zhí)行情況1確定分配處理機的原則2處理機的分配與回收3記錄系統(tǒng)中各進程的執(zhí)行情況和環(huán)境狀態(tài)，以便在處理機空閑的時候選擇合適的進程執(zhí)行。選擇合適的調(diào)度算法以選擇合適的進程執(zhí)行。在執(zhí)行（撤銷）進程時裝入（釋放）PCB信息。四、進程調(diào)度的過程記錄進程的相關(guān)信息選取適當?shù)倪M程執(zhí)行為進程分配處理機進程本身信息和環(huán)境信息進程調(diào)度算法恢復(fù)進程的現(xiàn)場信息五、進程調(diào)度的算法算法設(shè)計的準則：用戶周轉(zhuǎn)時間響應(yīng)時間優(yōu)先權(quán)系統(tǒng)系統(tǒng)吞吐量處理機效率資源利用的平衡截止時間簡單的調(diào)度算法先來先服務(wù)算法短進程優(yōu)先輪轉(zhuǎn)法等時間片輪轉(zhuǎn)不等時間片輪轉(zhuǎn)優(yōu)先權(quán)法搶占式優(yōu)先權(quán)非搶占式優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)多級反饋隊列算法算法的分類：（1）先到先服務(wù)（FCFS）算法常用算法

按照就緒進程進入就緒隊列的先后順序調(diào)度，先進入先服務(wù)。算法簡單，易于實現(xiàn)對長進程有利短進程服務(wù)質(zhì)量差（2）短進程優(yōu)先（SCBF）算法按照就緒進程對系統(tǒng)服務(wù)時間的需求確定優(yōu)先權(quán)，服務(wù)時間需求短的進程優(yōu)先被調(diào)度。需要進行進程時間估計對短進程有利長進程可能得不到調(diào)度n+1nnt?＝＋（1－）?其中?n為估計的第n個CPU周期。tn為實際值為控制值，0≤≤1，常取0.5調(diào)度算法評價指標周轉(zhuǎn)時間（TT）進程第一次進入就緒隊列到進程運行結(jié)束的時間間隔TT＝等待時間(WT)＋服務(wù)時間(ST)平均周轉(zhuǎn)時間（ATT）系統(tǒng)各進程周轉(zhuǎn)時間的平均值A(chǔ)TT＝ΣTT/N帶權(quán)周轉(zhuǎn)時間（QTT）進程周轉(zhuǎn)時間與系統(tǒng)服務(wù)時間的比值QTT=TT/服務(wù)時間平均帶權(quán)周轉(zhuǎn)時間（AQTT）例AQTT=ΣQTT/N

例：A請求系統(tǒng)服務(wù)時間5s，B請求系統(tǒng)服務(wù)時間為100s，設(shè)第0到第5秒前，CPU運行C進程。第1秒時B進入系統(tǒng)內(nèi)存，第2秒時A進入內(nèi)存當CPU空閑，需要調(diào)度進程時根據(jù)不同的算法選擇A或B。問：分別計算FCFS算法下和SCBF算法下，A和B的周轉(zhuǎn)時間，帶權(quán)周轉(zhuǎn)時間和系統(tǒng)平均周轉(zhuǎn)時間？BAFCFS算法－－先來先服務(wù)A：周轉(zhuǎn)時間為3+100+5＝108s帶權(quán)周轉(zhuǎn)時間為108/5＝20.4B：周轉(zhuǎn)時間為4+100＝104s帶權(quán)周轉(zhuǎn)時間為104/100＝1.04平均帶權(quán)周轉(zhuǎn)時間為(20.4+1.04)÷2＝10.72SCBF算法－－短進程優(yōu)先A：周轉(zhuǎn)時間為3+5＝8s帶權(quán)周轉(zhuǎn)時間為8/5＝1.6B：周轉(zhuǎn)時間為4+5+100＝109s帶權(quán)周轉(zhuǎn)時間為109/100＝1.09平均帶權(quán)周轉(zhuǎn)時間為(1.6+1.09)÷2＝1.345先調(diào)度B后調(diào)度A先調(diào)度A后調(diào)度B（3）等時間片輪轉(zhuǎn)（ERR）算法按照FCFS算法從就緒隊列調(diào)度調(diào)入進程為每個進程分配相同的時間片，并執(zhí)行時間片完，進程執(zhí)行完，調(diào)度下一個進程時間片完，進程未執(zhí)行完，進程進入就緒隊尾，等待下一次調(diào)度時間片選取原則：q：時間片大小T：響應(yīng)時間N：就緒隊列進程數(shù)qNT=

時間片選取過大或者過小有什么后果？應(yīng)該按什么原則選取時間片？時間片長度公式：公平性的保證響應(yīng)及時性的保證ERR優(yōu)點：（4）不等時間片輪轉(zhuǎn)（ERR）算法在保證及時響應(yīng)的基礎(chǔ)上，為不同的需求分配大小不等的時間片——降低周轉(zhuǎn)時間。長進程短進程I/O頻繁型CPU密集型長時間片短時間片（5）最高優(yōu)先權(quán)（HPF）算法

按照就緒隊列中進程的優(yōu)先級進行調(diào)度，高優(yōu)先級的進程優(yōu)先被調(diào)度。優(yōu)先級確定原則：進程類型：系統(tǒng)>用戶，前臺>后臺，實時>一般資源需求：需求小>需求大到達時間：先到>后到用戶類型：用戶自己確定靜態(tài)優(yōu)先級算法優(yōu)先級算法靜態(tài)優(yōu)先級算法動態(tài)優(yōu)先級算法進程的優(yōu)先級在進程創(chuàng)建時確定，不再更改。算法簡單系統(tǒng)開銷相對動態(tài)優(yōu)先級小低優(yōu)先級進程可能得不到調(diào)度B.動態(tài)優(yōu)先級算法在創(chuàng)建進程時確定一個基本優(yōu)先級，在進程執(zhí)行過程中按照一定原則動態(tài)改變。*就緒等待進程優(yōu)先級隨等待時間增加而升高*執(zhí)行進程的優(yōu)先級隨CPU占用時間增加而下降算法復(fù)雜系統(tǒng)開銷相對靜態(tài)優(yōu)先級大調(diào)度效果優(yōu)于靜態(tài)優(yōu)先級（6）多級隊列反饋算法設(shè)置多個就緒隊列，各隊列優(yōu)先級不同從高優(yōu)先級隊列開始調(diào)度，采用時間片原則高優(yōu)先級隊列調(diào)度完畢，繼續(xù)調(diào)度下一優(yōu)先級隊列注意：優(yōu)先級越高的隊列，分配越短的時間片1進程的優(yōu)先級是動態(tài)變化的2如果進程的時間片用完而進程還未執(zhí)行完，則進程回到的是下一優(yōu)先級隊列的隊尾3長進程的在等待長時間后將獲得長時間片，使周轉(zhuǎn)時間減少42.2.4進程的互斥與同步進程的并發(fā)執(zhí)行資源的競爭結(jié)果的不可再現(xiàn)進程同步目標：實現(xiàn)資源的有效共享，保證結(jié)果的可再現(xiàn)。進程間的同步關(guān)系例1：正常行車到站停車開車售票開車門關(guān)車門司機售票員合作合作進程間的同步關(guān)系例2：打印進程1打印進程2打印打印互斥獲得打印數(shù)據(jù)獲得打印數(shù)據(jù)進程間的同步關(guān)系例3：計算進程打印進程計算結(jié)果送到Buffer從Buffer中取數(shù)Buffer互斥互斥完成數(shù)據(jù)計算打印通知打印進程打印通知計算進程送下一個數(shù)合作進程同步時面臨的兩種主要關(guān)系：相互合作競爭資源司機與售票員多個打印者計算者與打印者進程的同步：多個進程通過執(zhí)行時序上的某種限制（相互合作）而產(chǎn)生的制約關(guān)系。進程的互斥：由于多個進程共享同一資源而產(chǎn)生的相互制約的關(guān)系。同步機制：實現(xiàn)進程互斥與同步的機制。臨界資源與臨界區(qū)：以互斥關(guān)系共享的資源。臨界資源：criticalsource一次（一個時刻）只允許一個進程訪問（排他性）臨界區(qū)：進程中訪問臨界資源的代碼區(qū)。進入?yún)^(qū)：退出區(qū)：釋放臨界資源申請進入臨界區(qū)剩留區(qū)：代碼的其它部分進程代碼的組成：進入?yún)^(qū)臨界區(qū)退出區(qū)進入?yún)^(qū)臨界區(qū)退出區(qū)........................阻塞等待資源釋放改變資源狀態(tài)釋放資源喚醒等待進程進程1進程2同步機制應(yīng)遵循的原則空閑讓進忙則等待有限等待讓權(quán)等待無進程處于臨界區(qū)，可讓一新進程進入有進程處于臨界區(qū)，其余進程必須等待進程進入臨界區(qū)的要求必須在有限時間內(nèi)滿足等待進入臨界區(qū)的進程，其CPU占用必須釋放臨界資源鎖機制為臨界資源加一個“鎖”鎖變量LockTrue資源在用False資源空閑每個進程必須按照以下過程操作臨界資源：......關(guān)鎖進入臨界區(qū)開鎖......例：............check:if(Lock!=0) gotocheck;elseLock=1;臨界區(qū)Lock進程1進程2unlock(Lock);......check:if(Lock!=0) gotocheck;elseLock=1;臨界區(qū)unlock(Lock);......臨界資源鎖的特點：實現(xiàn)了進程互斥訪問臨界資源。不遵循讓權(quán)等待原則——忙等：不斷調(diào)用TS查詢，占用處理機關(guān)鎖操作不可被打斷原語（例：引入TS指令：關(guān)鎖操作在一個指令周期內(nèi)完成）信號量與P、V操作信號量是對具體共享資源的抽象描述；信號量的值為整數(shù)，表示資源使用情況；不同共享資源可以用不同的信號量表示。P操作——申請分配一個資源V操作——釋放一個資源信號量是比鎖更高級的資源抽象方式PV操作均是原語（1）信號量同步機制通過信號量S和基于S的P、V操作實現(xiàn)P(S)S=S-1S

<0?進程繼續(xù)執(zhí)行臨界區(qū)/資源訪問區(qū)進程進入阻塞隊列NYV(S)S=S+1S<=0?進程繼續(xù)執(zhí)行喚醒阻塞隊列進程NYS是資源的數(shù)目（2）用信號量實現(xiàn)互斥實現(xiàn)了讓權(quán)等待…P（S）臨界區(qū)V（S）進程1進程2……P（S）臨界區(qū)V（S）…P（S）訪問資源V（S）狀態(tài)：狀態(tài)：喚醒就緒執(zhí)行就緒執(zhí)行阻塞司機進程正常行車到站停車V（S停車）喝茶P（S關(guān)車門）正常行車售票P（S停車）開車門關(guān)車門V（S關(guān)車門）售票售票員進程同步點同步點兩個信號量初值均為0（3）用信號量實現(xiàn)同步(例1)計算進程計算數(shù)據(jù)P(S空)數(shù)據(jù)入bufferV(S滿)…………P（S滿）從buffer取數(shù)據(jù)V(S空)……打印進程設(shè)一個信號量：S空代表buffer空，初值為：？再設(shè)一信號量：S滿代表buffer滿，初值為：？（3）用信號量實現(xiàn)同步(例2)設(shè)2個信號量：S2,S3空代表buffer1和buffer2是否滿再設(shè)2信號量：S1,S4代表buffer1和buffer2是否空初值分別為：？S1=S4=1；S2=S3=0；（3）用信號量實現(xiàn)同步(教材例2)……P(S1);……將數(shù)據(jù)放入buf1;……V(S2);…P(S2);P(S4);從buf1取數(shù)據(jù)并存入buffer2；V(S1);V(S3);…P(S3);……從buf2取數(shù)據(jù);V(S4);…進程get：進程copy：進程put：公用信號量：私用信號量：一組進程共享，都可進行P、V操作用于進程間資源的競爭擁有信號量的進程只對信號量進行P操作V操作由其他進程進行用于進程間的合作（4）公用信號量與私用信號量（4）經(jīng)典同步問題生產(chǎn)者－消費者問題（Producer－ConsumerProblems）問題描述：多個生產(chǎn)者生產(chǎn)產(chǎn)品多個消費者消費產(chǎn)品進程使用資源進程釋放資源算法分析：生產(chǎn)者生產(chǎn)資源后消費者才能消費消費者消費后生產(chǎn)者才能將生產(chǎn)資源放入資源區(qū)生產(chǎn)者和消費者對資源區(qū)的使用是互斥合作的關(guān)系使用循環(huán)隊列來實現(xiàn)資源區(qū)使用公共信號量控制資源區(qū)的互斥訪問使用私用信號量控制生產(chǎn)者和消費者的合作生產(chǎn)一個資源申請空緩沖區(qū)申請隊列互斥放入消息釋放隊列互斥釋放滿緩沖區(qū)申請滿緩沖區(qū)申請隊列互斥取出消息釋放隊列互斥釋放空緩沖區(qū)生產(chǎn)者消費者生產(chǎn)一個資源P(empty)P(S)放入消息V(S)V(full)P(full)P(S)取出消息V(S)V(empty)思考：生產(chǎn)一個資源P(empty)P(S)放入消息V(S)V(full)P(full)P(S)取出消息V(S)V(empty)生產(chǎn)一個資源P(S)P(empty)放入消息V(S)V(full)P(S)P(full)取出消息V(S)V(empty)信號量與P、V操作總結(jié)信號量S的初值應(yīng)該大于等于0S>0表示有S個資源可用;S=0表示無資源可用;S<0則|S|表示S等待隊列中的進程個數(shù)。P、V操作必須成對出現(xiàn)，有一個P操作就一定有一個V操作；當實現(xiàn)互斥時，它們處于同一進程；當實現(xiàn)同步時，它們則不在同一進程中出現(xiàn)。如果兩個P操作在一起，那么它們的順序至關(guān)重要：一個同步P操作應(yīng)在一個互斥P操作前。兩個V操作順序無關(guān)緊要。優(yōu)點：簡單，而且表達能力強（用P、V操作可解決任何同步互斥問題）缺點：不夠安全；P、V操作使用不當會出現(xiàn)死鎖；遇到復(fù)雜同步互斥問題時實現(xiàn)復(fù)雜。2.2.5進程的通信進程的通信：并發(fā)執(zhí)行的進程之間所進行的信息交換。進程通信低級通信高級通信消息緩沖通信管道通信信箱通信一、消息緩沖通信方式：通過系統(tǒng)的公共消息緩沖區(qū)實現(xiàn)信息交換（1）系統(tǒng)管理空白緩沖區(qū)（2）發(fā)送者向系統(tǒng)申請空白緩沖區(qū)（4）發(fā)送者將填有消息的緩沖區(qū)掛到接收者的消息隊列（5）接收者在適當時候從消息隊列中讀取數(shù)據(jù)（3）發(fā)送者向空白緩沖區(qū)填入信息sendreceive系統(tǒng)提供消息通信原語：Send、ReceiveSend(receiver,m){申請緩沖區(qū)；P(mutex);填入消息；消息插入消息隊列；V(mutex);V(sm);}Receive(n){P(sm)；P(mutex);取消息；釋放緩沖區(qū)；V(mutex);}Send原語Receive原語二、信箱通信進程A進程B進程C進程D進程E中間實體信箱頭：信箱名等相關(guān)信息信箱體：傳遞的信息信箱頭（信箱名、口令）信格信格信格信格信格存放多種格式消息三、管道通信管道：連接接收進程和發(fā)送進程的共享文件管道通信：兩個進程之間利用共享文件進行信息交換對于管道的讀寫是互斥訪問的寫后讀、讀后寫的同步關(guān)系只有在管道雙方都存在時才能通信管道（共享文件）進程2讀出

寫入管道（共享文件）進程1寫入進程3讀出2.2.6進程的死鎖死鎖：由于資源分配不當，造成多個進程阻塞而無法被喚醒繼續(xù)執(zhí)行的現(xiàn)象。生產(chǎn)一個資源P(S)P(empty)放入消息V(S)V(full)P(S)P(full)取出消息V(S)V(empty)死鎖死鎖的原因：1、資源分配不當；2、進程推進順序不對；產(chǎn)生死鎖的必要條件：1、資源訪問的互斥條件資源一旦獲得后在V(S)之前不放棄3、不剝奪條件進程在需要時才申請資源——進程對資源的申請是分步的2、請求和保持條件（部分分配條件）進程在申請新資源時，對舊資源仍然保持占用4、環(huán)路等待條件存在進程—資源環(huán)形鏈進程—資源環(huán)形鏈：進程1資源2資源1進程21、從資源出發(fā)的箭頭表示已分配該資源2、從進程出發(fā)的箭頭表示進程正在申請資源表示原則：進程1等待進程2占有的資源（資源2）；進程2等待進程1占有的資源（資源1）；形成了一個進程等待資源的環(huán)路。一、死鎖的預(yù)防（方法1）破壞死鎖產(chǎn)生的必要條件，預(yù)防死鎖產(chǎn)生1、破壞請求和保持條件(破壞部分分配條件）資源預(yù)分配2、破壞不剝奪條件阻塞進程釋放所有的資源3、破壞環(huán)路等待條件資源按序分配簡單方便，利用率低，延遲大效率高，復(fù)雜，開銷大資源利用率不高，可能有浪費二、死鎖的避免（方法2）資源預(yù)測分配：分配資源前，檢查分配的安全性系統(tǒng)狀態(tài)不安全：不分配資源系統(tǒng)狀態(tài)安全：分配資源安全狀態(tài)：在當前的狀態(tài)下，能找到一個正確的推進順序滿足所有的進程的資源需求，將它們推進完畢安全狀態(tài)檢測——銀行家算法假設(shè)本次分配，檢測分配后的系統(tǒng)狀態(tài)是否安全例：條件P1、P2、P3三個進程對同類資源競爭。P1最大需要10個該資源，P2最大需要4個，P3為9個。該資源總數(shù)為12個。已知當前時刻，系統(tǒng)狀態(tài)1、當前是否為安全狀態(tài)2、若進程2提出2個資源需求是否可以分配3、若進程3提出2個資源需求是否可以分配進程最大需求已分配剩余12310492P2P1P331245051010存在一個正確的順序推進進程例：條件P1、P2、P3三個進程對同類資源競爭。P1最大需要10個該資源，P2最大需要4個，P3為9個。該資源總數(shù)為12個。已知當前時刻，系統(tǒng)狀態(tài)1、當前是否為安全狀態(tài)2、若進程2提出2個資源需求是否可