處理機(jī)管理課件

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

一、程序與進(jìn)程程序：由若干條具有一定功能的機(jī)器指令所組成的解題順序和步驟。順序執(zhí)行（單道系統(tǒng)）并發(fā)執(zhí)行（多道系統(tǒng)）順序性封閉性可再現(xiàn)性程序執(zhí)行嚴(yán)格按照一定順序，不受外界因素影響，結(jié)果只由初始條件決定相互約束資源爭(zhēng)奪與共享程序執(zhí)行是相互交替穿插進(jìn)行，執(zhí)行次序每次變化；受外界影響，結(jié)果與速度有關(guān)前驅(qū)圖有向無(wú)環(huán)圖節(jié)點(diǎn)：表示一條語(yǔ)句，或一段程序有向線段：表示語(yǔ)句之間的順序關(guān)系無(wú)環(huán)：當(dāng)程序中出現(xiàn)循環(huán)時(shí)，一般將整個(gè)循環(huán)作為一個(gè)節(jié)點(diǎn)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輸入處理機(jī)打印機(jī)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可見(jiàn)：

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

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

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

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

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

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

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

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

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