操作系統(tǒng)課件(第四章)

操作系統(tǒng)

OperatingSystems

操作系統(tǒng)課程組南京郵電大學(xué)WINDOWSUNIXLINUXOS2VxWorksMacOS教材：《操作系統(tǒng)教程》，人民郵電出版社

，2009年出版第三章并發(fā)進(jìn)程

4.1并發(fā)進(jìn)程4.2臨界區(qū)管理4.3信號(hào)量與P、V操作4.4進(jìn)程間通信4.5死鎖4.6管程4.1并發(fā)進(jìn)程4.1.1順序程序與并發(fā)進(jìn)程4.1.2與時(shí)間有關(guān)的錯(cuò)誤4.1.3進(jìn)程間的聯(lián)系4.1.1順序程序與并發(fā)進(jìn)程1、順序程序順序程序：指令或語句序列，體現(xiàn)了某種算法，所有程序是順序的順序環(huán)境：在計(jì)算機(jī)系統(tǒng)中只有一個(gè)程序在運(yùn)行，這個(gè)程序獨(dú)占系統(tǒng)中所有資源，其執(zhí)行不受外界影響4.1.1順序程序與并發(fā)進(jìn)程1、順序程序的特征：順序性執(zhí)行封閉性，獨(dú)占資源確定性，即可再現(xiàn)性4.1.1順序程序與并發(fā)進(jìn)程2、并發(fā)進(jìn)程并發(fā)環(huán)境：

在一定時(shí)間內(nèi)物理機(jī)器上有兩個(gè)或兩個(gè)以上的程序同處于開始運(yùn)行但尚未結(jié)束的狀態(tài)，并且次序不是事先確定的BAABBAAB4.1.1順序程序與并發(fā)進(jìn)程2、并發(fā)進(jìn)程的特征：間斷性執(zhí)行，執(zhí)行--停--執(zhí)行資源共享，多個(gè)進(jìn)程共享使用系統(tǒng)資源不可再現(xiàn)性，執(zhí)行結(jié)果不確定獨(dú)立性和制約性程序和進(jìn)程不再一一對應(yīng)4.1并發(fā)進(jìn)程4.1.1順序程序與并發(fā)進(jìn)程4.1.2與時(shí)間有關(guān)的錯(cuò)誤4.1.3進(jìn)程間的聯(lián)系4.1.2與時(shí)間有關(guān)的錯(cuò)誤1、并發(fā)進(jìn)程交替使用共享資源時(shí)可能出現(xiàn)的錯(cuò)誤：例如：P1和P2是兩個(gè)并發(fā)進(jìn)程P1:①R1=C; ②R1=R1+1; ③C=R1;P2:④R2=C; ⑤R2=R2+1; ⑥C=R2;P1全部執(zhí)行完畢后再執(zhí)行P2，則C增加2若P2中的④在P1中的③之前執(zhí)行，則C增加1原因是沒有正確地控制對共享變量C的訪問4.1.2與時(shí)間有關(guān)的錯(cuò)誤2、飛機(jī)訂票問題：P1和P2是兩個(gè)并發(fā)的終端訂票進(jìn)程，x=10P1:①Read(x); ②ifx>=1thenx:=x-1; ③write(x);P2:④Read(x); ⑤ifx>=1thenx:=x-1; ⑥write(x);

P1全部執(zhí)行完畢后再執(zhí)行P2，則x=8若P2中的④在P1中的③之前執(zhí)行，則x=9出現(xiàn)了1張票賣給2個(gè)客戶的情況，原因是沒有正確地控制對共享變量x的訪問4.1.2與時(shí)間有關(guān)的錯(cuò)誤3、緩沖區(qū)讀寫問題：get、copy、put是3個(gè)并發(fā)進(jìn)程getcopyputfstg4.1并發(fā)進(jìn)程4.1.1順序程序與并發(fā)進(jìn)程4.1.2與時(shí)間有關(guān)的錯(cuò)誤4.1.3進(jìn)程間的聯(lián)系4.1.3進(jìn)程間的聯(lián)系1、間接式與直接式制約：直接式制約：一程序段等待另一程序段的執(zhí)行結(jié)果間接式制約：并發(fā)程序段競爭同一資源2、相交進(jìn)程與無關(guān)進(jìn)程：相交進(jìn)程：并發(fā)進(jìn)程在邏輯上有某種聯(lián)系無關(guān)進(jìn)程：邏輯上無任何聯(lián)系的并發(fā)進(jìn)程直接作用只發(fā)生在相交進(jìn)程之間；間接作用可以發(fā)生在相交進(jìn)程之間，也可發(fā)生在無關(guān)進(jìn)程之間4.1.3進(jìn)程間的聯(lián)系3、進(jìn)程的同步與互斥：進(jìn)程同步（直接作用）：根據(jù)一定的時(shí)序關(guān)系合作完成一項(xiàng)任務(wù)并發(fā)進(jìn)程因直接制約而互相等待，彼此相互發(fā)送消息進(jìn)行合作，使得各進(jìn)程按一定的速度執(zhí)行進(jìn)程互斥（間接作用）：各進(jìn)程競爭使用臨界資源臨界資源：一次只允許一個(gè)進(jìn)程使用的系統(tǒng)資源進(jìn)程互斥是進(jìn)程同步的一種特殊情況第三章并發(fā)進(jìn)程

4.1并發(fā)進(jìn)程4.2臨界區(qū)管理4.3信號(hào)量與P、V操作4.4進(jìn)程間通信4.5死鎖4.6管程4.2臨界區(qū)管理4.2.1臨界區(qū)及其使用原則4.2.2實(shí)現(xiàn)臨界區(qū)管理的軟件方法4.2.3實(shí)現(xiàn)臨界區(qū)管理的硬件方法4.2.1臨界區(qū)及其使用原則臨界區(qū)：進(jìn)程中涉及臨近資源的程序段為臨界區(qū)/互斥區(qū)，多個(gè)進(jìn)程的臨界區(qū)為相關(guān)臨界區(qū)臨界區(qū)的使用原則：有空讓進(jìn) 無空等待多中擇一有限等待讓權(quán)等待解決進(jìn)程互斥的兩種做法：由競爭各方平等協(xié)商解決，包括硬件、軟件兩類方法。引入進(jìn)程管理者來協(xié)調(diào)競爭各方對互斥資源的使用

4.2臨界區(qū)管理4.2.1臨界區(qū)及其使用原則4.2.2實(shí)現(xiàn)臨界區(qū)管理的軟件方法4.2.3實(shí)現(xiàn)臨界區(qū)管理的硬件方法4.2.2實(shí)現(xiàn)臨界區(qū)管理的軟件方法1、兩個(gè)失敗的嘗試（1）boolinside1=false;boolinside2=false;cobeginprocessP1 processP2 while(inside2)do while(inside1)do beginend; beginend; inside1:=true; inside2:=true;

臨界區(qū)； 臨界區(qū); inside1=false; inside2=false;} }coend4.2.2實(shí)現(xiàn)臨界區(qū)管理的軟件方法1、兩個(gè)失敗的嘗試（2）boolinside1:=false;boolinside2:=false;cobeginprocessP1 processP2begin begin inside1:=true; inside2=true; while(inside2)do while(inside1)do beginend; beginend;

臨界區(qū)； 臨界區(qū); inside1:=false; inside2:=false;end endcoend4.2.2實(shí)現(xiàn)臨界區(qū)管理的軟件方法2、成功解決方法（Dekker算法）varinside:array[1..2]ofBoolean;inside[1]=false;inside[2]=false;turn:integer;turn:=1or2;cobeginprocessP1 begininside[1]:=true;whileinside[2]doifturn=2thenbegininside[1]:=false;whileturn=2dobeginend;inside[1]:=true;end

臨界區(qū);turn:=2；

inside[1]:=false;end;coendprocessP2 begininside[2]:=true;whileinside[1]doifturn=1thenbegininside[2]:=false;whileturn=1dobeginend;inside[2]:=true;end

臨界區(qū);turn:=1；

inside[2]:=false;end;4.2臨界區(qū)管理4.2.1臨界區(qū)及其使用原則4.2.2實(shí)現(xiàn)臨界區(qū)管理的軟件方法4.2.3實(shí)現(xiàn)臨界區(qū)管理的硬件方法4.2.3實(shí)現(xiàn)臨界區(qū)管理的硬件方法通過專門提供的硬件指令管理臨界區(qū)1、測試并建立指令TS s代表臨界資源狀態(tài)，由TS指令控制s:boolean; s:=true;processPi/*i=1,2,…,n*/pi:boolean;beginrepeatpi:=TS(s)untilpi；臨界區(qū);s:=true；end;

4.2.3實(shí)現(xiàn)臨界區(qū)管理的硬件方法2、交換指令SWAP

交換指令將交換兩個(gè)字的內(nèi)容。公共變量lock表臨界區(qū)是否上鎖，每個(gè)進(jìn)程的私有變量key用于與lock交換。voidSWAP(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}key=true;do{SWAP(&lock,key);}while(key);臨界區(qū)lock:=false;4.2.3實(shí)現(xiàn)臨界區(qū)管理的硬件方法3、開關(guān)中斷指令進(jìn)入臨界區(qū)前執(zhí)行“關(guān)中斷”指令；離開臨界區(qū)后，執(zhí)行“開中斷”指令，從而控制進(jìn)程互斥進(jìn)入臨界區(qū)硬件方法解決臨界區(qū)的管理較為簡單有效，其缺點(diǎn)主要在于會(huì)導(dǎo)致“忙等待”會(huì)導(dǎo)致“饑餓”中斷屏蔽方法代價(jià)較高，不適應(yīng)多處理器第三章并發(fā)進(jìn)程

4.1并發(fā)進(jìn)程4.2臨界區(qū)管理4.3信號(hào)量與P、V操作4.4進(jìn)程間通信4.5死鎖4.6管程4.3信號(hào)量與P、V操作4.3.1信號(hào)量定義4.3.2P、V操作定義4.3.3信號(hào)量的使用4.3.4信號(hào)量及P、V操作討論4.3.5信號(hào)量與P、V操作經(jīng)典問題4.3.6POSIX信號(hào)量4.3.7Linux中的信號(hào)量機(jī)制4.3.1信號(hào)量定義1、信號(hào)量的提出1965年荷蘭學(xué)者Dijkstra提出信號(hào)量（semaphore）與P、V操作機(jī)制，這一機(jī)制是系統(tǒng)用于管理公有資源的有效手段信號(hào)量是一個(gè)數(shù)據(jù)結(jié)構(gòu)，負(fù)責(zé)協(xié)調(diào)各個(gè)進(jìn)程，以保證它們能夠正確、合理的使用公共資源2、信號(hào)量定義Structsemaphore{intvalue; //信號(hào)量的值

pointerPCBqueue; //信號(hào)量隊(duì)列指針

}信號(hào)量說明：semaphores4.3.1信號(hào)量定義3、信號(hào)量的特性信號(hào)量代表對某種公共資源的管理（如停車場的看門人），其值是一個(gè)非負(fù)整數(shù)（如停車場內(nèi)的車位數(shù)）要使用資源的進(jìn)程（如要進(jìn)入停車場的車）需通過信號(hào)量，有資源時(shí)順利通過（有車位時(shí)，看門人打開車欄）；若沒有資源可用（如空車位為0），則所有進(jìn)程都將進(jìn)入對應(yīng)信號(hào)量的等待隊(duì)列（如車子在看門人看守的車欄外排隊(duì)等待）當(dāng)一個(gè)進(jìn)程歸還資源（如車開出停車場）時(shí)，此時(shí)若信號(hào)量隊(duì)列有等待進(jìn)程則釋放一個(gè)（如讓一輛車進(jìn)入停車場）4.3信號(hào)量與P、V操作4.3.1信號(hào)量定義4.3.2P、V操作定義4.3.3信號(hào)量的使用4.3.4信號(hào)量及P、V操作討論4.3.5信號(hào)量與P、V操作經(jīng)典問題4.3.6POSIX信號(hào)量4.3.7Linux中的信號(hào)量機(jī)制4.3.2P、V操作定義1、什么是P、V操作P、V操作是能對信號(hào)量進(jìn)行處理的唯一兩個(gè)操作，是不可分割的一段程序，為原語操作（執(zhí)行過程中不允許被中斷）P操作用于申請信號(hào)量管理的資源（如停車場一例中需要進(jìn)入停車場使用車位的車就應(yīng)執(zhí)行P操作）V操作用于釋放資源（如停車場一例中需要開出停車場歸還車位的車就應(yīng)執(zhí)行V操作）4.3.2P、V操作定義2、P操作P(s){

s.value=s.value－－; //s.value減1if(s.value<0) //該進(jìn)程被阻塞，進(jìn)入相應(yīng)隊(duì)列，然后轉(zhuǎn)進(jìn)程調(diào)度

{

該進(jìn)程狀態(tài)置為等待狀態(tài);

將該進(jìn)程的PCB插入相應(yīng)的等待隊(duì)列s.queue的末尾;} //若s.value減1后仍大于或等于零，則進(jìn)程繼續(xù)執(zhí)行

}

4.3.2P、V操作定義3、V操作V(s){

s.value=s.value++; //s.value加1if(s.value<=0)//從隊(duì)列中喚醒一等待進(jìn)程，然后繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度

{

喚醒相應(yīng)等待隊(duì)列s.queue中等待的一個(gè)進(jìn)程;

改變其狀態(tài)為就緒態(tài)，并將其插入就緒隊(duì)列;}//若相加結(jié)果大于零，則進(jìn)程繼續(xù)執(zhí)行}4.3信號(hào)量與P、V操作4.3.1信號(hào)量定義4.3.2P、V操作定義4.3.3信號(hào)量的使用4.3.4信號(hào)量及P、V操作討論4.3.5信號(hào)量與P、V操作經(jīng)典問題4.3.6POSIX信號(hào)量4.3.7Linux中的信號(hào)量機(jī)制4.3.3信號(hào)量的使用1、使用注意事項(xiàng)：必須置一次且只能置一次初值，且初值不能為負(fù)數(shù)；只能執(zhí)行P、V操作

2、用信號(hào)量及P、V操作解決進(jìn)程間互斥問題

mutex:semaphore;mutex:=1;cobegin

processPibegin…

P(mutex);臨界區(qū)；V(mutex);…end;coend;4.3.3信號(hào)量的使用用信號(hào)量及P、V操作解決機(jī)票問題varA:ARRAY[1..m]OFinteger;mutex:semaphore;mutex:=1;cobegin

processPi

varXi:integer;begin

L1:

按旅客要求找到A[j];

P(mutex)Xi:=A[j];Coend

ifXi>=1thenbeginXi:=Xi-1;A[j]:=Xi;

V(mutex);輸出一張票;end;elsebegin

V(mutex);輸出票已售完;end;

gotoL1;end;

4.3.3信號(hào)量的使用3、用信號(hào)量及P、V操作解決進(jìn)程間同步問題

生產(chǎn)者-消費(fèi)者問題問題描述：生產(chǎn)者往緩沖區(qū)中放產(chǎn)品，消費(fèi)者從緩沖區(qū)中取產(chǎn)品，如下圖所示生產(chǎn)者P進(jìn)程不能往“滿”的緩沖區(qū)中放產(chǎn)品，設(shè)置信號(hào)量為S1，初值為1，代表緩沖區(qū)有1個(gè)空閑空間消費(fèi)者Q進(jìn)程不能從“空”的緩沖區(qū)中取產(chǎn)品，設(shè)置信號(hào)量S2

，初值為0，代表緩沖區(qū)有0個(gè)產(chǎn)品4.3.3信號(hào)量的使用3、用信號(hào)量及P、V操作解決進(jìn)程間同并不斥問題P //生產(chǎn)者進(jìn)程while(true){

生產(chǎn)一個(gè)產(chǎn)品;

P(s1); //初值為1

送產(chǎn)品到緩沖區(qū);

V(s2);};C //消費(fèi)者進(jìn)程while(true){

P(s2); //初值為0

從緩沖區(qū)取產(chǎn)品;

V(s1);

消費(fèi)產(chǎn)品;};4.3信號(hào)量與P、V操作4.3.1信號(hào)量定義4.3.2P、V操作定義4.3.3信號(hào)量的使用4.3.4信號(hào)量及P、V操作討論4.3.5信號(hào)量與P、V操作經(jīng)典問題4.3.6POSIX信號(hào)量4.3.7Linux中的信號(hào)量機(jī)制4.3.4信號(hào)量及P、V操作討論1、信號(hào)量及P、V操作的物理含義①

S>0表示有S個(gè)資源可用②S=0表示無資源可用③S<0則|S|表示S等待隊(duì)列中的進(jìn)程個(gè)數(shù)④P(S)表示申請一個(gè)資源⑤V(S)表示釋放一個(gè)資源4.3.4信號(hào)量及P、V操作討論2、P、V操作必須成對出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作①當(dāng)為互斥操作時(shí)，它們處于同一進(jìn)程②當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn)③如果P(S1)和P(S2)兩個(gè)操作在一起，那么P操作的順序至關(guān)重要，一個(gè)同步P操作與一個(gè)互斥P操作在一起時(shí)，同步P操作在互斥P操作前，而兩個(gè)V操作無關(guān)緊要4.3.4信號(hào)量及P、V操作討論3、信號(hào)量及P、V的優(yōu)缺點(diǎn)①優(yōu)點(diǎn)：簡單且表達(dá)能力強(qiáng)，用P、V操作可解決任何同步、互斥問題②缺點(diǎn)：不夠安全，P、V操作使用不當(dāng)會(huì)出現(xiàn)死鎖；遇到復(fù)雜同步互斥問題時(shí)實(shí)現(xiàn)復(fù)雜4.3信號(hào)量與P、V操作4.3.1信號(hào)量定義4.3.2P、V操作定義4.3.3信號(hào)量的使用4.3.4信號(hào)量及P、V操作討論4.3.5信號(hào)量與P、V操作經(jīng)典問題4.3.6POSIX信號(hào)量4.3.7Linux中的信號(hào)量機(jī)制4.3.5信號(hào)量與P、V操作經(jīng)典問題1、哲學(xué)家吃通心面問題問題描述：5個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心面，每人面前有一只空盤于，每兩人之間放一把叉子。每個(gè)哲學(xué)家思考、饑餓、然后吃通心面。每個(gè)哲學(xué)家必須直接從自己左邊和右邊同時(shí)獲得兩把叉子才能吃面解決思路：5位哲學(xué)家看作5個(gè)進(jìn)程，需要互斥使用5把叉子，這5把叉子是共享資源，用5個(gè)信號(hào)量表示4.3.5信號(hào)量與P、V操作經(jīng)典問題varfork[I]:array[0..4]ofsemaphore;fork[i]:=1;cobegin

processPi//i=0,1,2,3,4,beginL1:思考；

P(fork[i]);//叉子逆時(shí)針編號(hào)，先拿左邊叉子

P(fork[(i+1)mod5]);//再拿右邊叉子吃通心面;

V(fork[i]); //歸還左邊叉子

V(fork[(i+1)mod5]); //歸還右邊叉子

gotoL1;end;coend

4.3.5信號(hào)量與P、V操作經(jīng)典問題上述解法保證了對叉子的互斥使用，但可能出現(xiàn)每位哲學(xué)家均拿起左邊叉子而同時(shí)又等待拿右邊叉子的情況，發(fā)生死鎖，可通過下列幾種辦法避免死鎖：至多允許4個(gè)哲學(xué)家同時(shí)吃奇數(shù)號(hào)先取左手邊的叉子，偶數(shù)號(hào)先取右手邊的叉子每個(gè)哲學(xué)家取到手邊的兩把叉子才吃，否則一把叉子也不取

4.3.5信號(hào)量與P、V操作經(jīng)典問題2、生產(chǎn)者消費(fèi)者問題問題描述：若干進(jìn)程通過K個(gè)有限共享緩沖區(qū)交換數(shù)據(jù)。其中，“生產(chǎn)者”進(jìn)程不斷寫入，而“消費(fèi)者”進(jìn)程不斷讀出。任何時(shí)刻只能有一個(gè)進(jìn)程可對共享緩沖區(qū)進(jìn)行操作。且滿足條件：①消費(fèi)者想接收數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是滿的；②生產(chǎn)者想發(fā)送數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是空的解決思路：設(shè)置3個(gè)信號(hào)量full表示“滿”數(shù)目，即產(chǎn)品數(shù)，初值為0

empty表示“空”數(shù)目，初值為K；full+empty==K

mutex用于訪問緩沖區(qū)時(shí)的互斥，初值是1

4.3.5信號(hào)量與P、V操作經(jīng)典問題varB:array[0..k-1]ofitem;in,out:integer:=0;//緩沖區(qū)讀寫指針empty,full,mutex:semaphore;empty:=k;full:=0;mutex:=1;cobegin

processproducer_ibeginL1:produceaproduct;

P(empty);P(mutex);

B[in]:=product;In:=(in+1)modk;

V(mutex);V(full);

GotoL1;end;

coend

processconsumer_j

beginL2:P(full);P(mutex);Product:=B[out];out:=(out+1)modk;

V(mutex);V(empty);Consumeaproduct;

GotoL2;end;

4.3.5信號(hào)量與P、V操作經(jīng)典問題varB:array[0..k-1]ofitem;in,out:integer:=0;//緩沖區(qū)讀寫指針empty,full,mutex:semaphore;empty:=k;full:=0;mutex:=1;cobegin

processproducer_ibeginL1:produceaproduct;

P(mutex);P(empty);?

B[in]:=product;In:=(in+1)modk;

V(mutex);V(full);

GotoL1;end;

coend

processconsumer_j

beginL2:P(full);P(mutex);?Product:=B[out];out:=(out+1)modk;

V(mutex);V(empty);Consumeaproduct;

GotoL2;end;

4.3.5信號(hào)量與P、V操作經(jīng)典問題3、蘋果桔子問題問題描述：桌上有一只盤子，每次只能放入一只水果；爸爸專向盤子中放蘋果（apple），媽媽專向盤子中放桔于（orange）；一個(gè)兒子專等吃盤子中的桔子，一個(gè)女兒專等吃盤子里的蘋果解決思路：生產(chǎn)者消費(fèi)者問題的變形，有兩類生產(chǎn)者和兩類消費(fèi)者，仍然設(shè)置3個(gè)信號(hào)量sp表示盤子能放的水果數(shù)目，初值為1sg1表示盤子里有無桔子，初值為0Sg2表示盤子里有無蘋果，初值為0

4.3.5信號(hào)量與P、V操作經(jīng)典問題sp,sg1,sg2:semaphore;sp:=1;sg1,:=0;sg2:=0;cobegin

processfatherbeginL1:削一個(gè)蘋果；

P(sp);放蘋果; V(sg2);gotoL1;end;processmotherbeginL2:剝一個(gè)桔子；

P(sp);放桔子；

V(sg1);gotoL2;end;coend

processdaughterbeginL4:P(sg2);取蘋果；

V(sp);吃蘋果；

gotoL4;end;processsonbeginL3:P(sg1);取桔子；

V(sp);吃桔子；

gotoL3;end;4.3.5信號(hào)量與P、V操作經(jīng)典問題4、讀者和寫者問題問題描述：讀者和寫者兩組并發(fā)進(jìn)程共享一個(gè)文件F，要求允許多個(gè)讀者同時(shí)執(zhí)行讀操作，任一寫者在完成寫操作之前不允許其他讀者或?qū)懻吖ぷ鳎瑢懻邎?zhí)行寫操作前，應(yīng)讓已有的寫者和讀者全部退出

解決思路：設(shè)置2個(gè)信號(hào)量W和R，1個(gè)控制變量rcW控制讀寫進(jìn)程對文件的互斥訪問，初值為1R控制各個(gè)讀進(jìn)程對rc的互斥訪問，初值為1rc記錄正在讀文件的進(jìn)程數(shù)，初值為04.3.5信號(hào)量與P、V操作經(jīng)典問題varrc:integer;rc:=0;W，R:semaphore;W:=1;R:=1;cobegin

procedureread;begin

P(R);

rc:=rc+1;

ifrc=1thenP(W)；

V(R);

讀文件；

P(R);

rc:=rc-1;

ifrc=0thenV(W)；

V(R);end;coend

procedurewrite;begin

P(W);

寫文件;

V(W);end;

4.3.5信號(hào)量與P、V操作經(jīng)典問題5、理發(fā)師問題問題描述：理發(fā)店有一位理發(fā)師、一把理發(fā)椅和n把供等候理發(fā)的顧客坐的椅子。沒顧客時(shí)理發(fā)師在理發(fā)椅上睡覺，顧客來時(shí)必須叫醒理發(fā)師，如果其正在理發(fā)則坐下來等待，沒有空椅子坐就離開解決思路：設(shè)置1個(gè)控制變量waiting和3個(gè)信號(hào)量waiting記錄等候理發(fā)的顧客數(shù)，初值為0customers表等候理發(fā)的顧客數(shù)，可阻塞理發(fā)師進(jìn)程，初值為0barbers表正在等候顧客的理發(fā)師數(shù)，可阻塞顧客進(jìn)程，初值為0mutex用于互斥修改waiting，初值為14.3信號(hào)量與P、V操作4.3.1信號(hào)量定義4.3.2P、V操作定義4.3.3信號(hào)量的使用4.3.4信號(hào)量及P、V操作討論4.3.5信號(hào)量與P、V操作經(jīng)典問題4.3.6POSIX信號(hào)量4.3.7Linux中的信號(hào)量機(jī)制4.3.6POSIX信號(hào)量1、POSIX有兩種信號(hào)量的實(shí)現(xiàn)機(jī)制：無名信號(hào)量：可以用在共享內(nèi)存的情況下，如實(shí)現(xiàn)進(jìn)程中各個(gè)線程之間的互斥和同步命名信號(hào)量：通常用于不共享內(nèi)存的情況下，如不共享內(nèi)存的進(jìn)程之間本節(jié)所介紹的函數(shù)和數(shù)據(jù)結(jié)構(gòu)需要引用頭文件semaphore.h

4.3.6POSIX信號(hào)量2、POSIX無名信號(hào)量sem_init

函數(shù)：初始化指定的信號(hào)量int

sem_init(sem_t*sem,int

pshared,unsignedvalue);sem

指向要初始化的信號(hào)量value為信號(hào)量的初始值pshared

用于說明信號(hào)量的共享范圍如果成功，sem_init

返回0，如果不成功，sem_init

返回-1并設(shè)置errno

4.3.6POSIX信號(hào)量sem_destroy函數(shù)：銷毀一個(gè)指定的信號(hào)量intsem_destroy(sem_t*sem);sem：指向要銷毀的信號(hào)量的指針如果成功sem_destroy

返回0，如果不成功返回-1并設(shè)置errno

。如果*sem

不是有效的信號(hào)量，sem_destroy

就將errno

置為EINVALsem_post

函數(shù)：實(shí)現(xiàn)對指定信號(hào)量的signal操作int

sem_post(sem_t*sem);如果成功sem_post

返回0。如果不成功

返回-1并設(shè)置errno

。如果*sem

不是有效的信號(hào)量，sem_post

就將errno

置為EINVAL4.3.6POSIX信號(hào)量sem_wait

函數(shù)：實(shí)現(xiàn)對指定信號(hào)量的wait操作int

sem_wait(sem_t*sem);sem_trywait

函數(shù)與sem_wait

類似，只是在試圖對一個(gè)為零的信號(hào)量進(jìn)行操作時(shí)，它不會(huì)阻塞調(diào)用線程，而是立即返回int

sem_trywait(sem_t*sem);如果成功這兩個(gè)函數(shù)返回0，如果不成功這些函數(shù)返回-1并設(shè)置errno

sem_post、sem_wait

和sem_trywait

同樣可用于命名信號(hào)量

4.3.6POSIX信號(hào)量3、POSIX命名信號(hào)量命名信號(hào)量有一個(gè)名字、一個(gè)用戶ID、一個(gè)組ID和權(quán)限，它們是提供給那些不共享內(nèi)存進(jìn)程的使用接口命名信號(hào)量的名字是一個(gè)遵守路徑名構(gòu)造規(guī)則的字符串sem_open

函數(shù)：創(chuàng)建或打開一個(gè)命名信號(hào)量sem_t*sem_open(constchar*name,int

oflag);name是一個(gè)標(biāo)識(shí)信號(hào)量的字符串oflag

用來確定是創(chuàng)建信號(hào)量還是連接已有信號(hào)量。如設(shè)置了oflag

的O_CREAT比特位，則會(huì)創(chuàng)建一個(gè)新的信號(hào)量4.3.6POSIX信號(hào)量sem_close

函數(shù)：關(guān)閉命名信號(hào)量int

sem_close(sem_t*sem);sem指向要關(guān)閉的信號(hào)量的指針成功返回0，不成功返回-1并設(shè)置errno單個(gè)程序可以用sem_close

函數(shù)關(guān)閉命名信號(hào)量，但是這樣做并不能將信號(hào)量從系統(tǒng)中刪除，因?yàn)槊盘?hào)量在單個(gè)程序的執(zhí)行之外是具有持久性的當(dāng)進(jìn)程調(diào)用_exit、exit、exec或從main返回時(shí)，進(jìn)程打開的命名信號(hào)量同樣會(huì)被關(guān)閉4.3.6POSIX信號(hào)量sem_unlink

函數(shù)：在所有進(jìn)程關(guān)閉了命名信號(hào)量之后，將信號(hào)量從系統(tǒng)中刪除int

sem_unlink(constchar*name);name為要?jiǎng)h除的命名信號(hào)量的名字如果成功，sem_unlink返回0，如果不成功，sem_unlink返回-1并設(shè)置errno4.3信號(hào)量與P、V操作4.3.1信號(hào)量定義4.3.2P、V操作定義4.3.3信號(hào)量的使用4.3.4信號(hào)量及P、V操作討論4.3.5信號(hào)量與P、V操作經(jīng)典問題4.3.6POSIX信號(hào)量4.3.7Linux中的信號(hào)量機(jī)制4.3.7Linux中的信號(hào)量機(jī)制1、Linux中的基本信號(hào)量機(jī)制Linux內(nèi)核的信號(hào)量在概念和原理上和用戶態(tài)的SystemV的IPC機(jī)制信號(hào)量相同，但它絕不可能在內(nèi)核外使用只有一個(gè)持有者的信號(hào)量叫二值信號(hào)量或互斥信號(hào)量允許有多個(gè)持有者的信號(hào)量叫計(jì)數(shù)信號(hào)量，在初始化時(shí)要說明最多允許有多少個(gè)持有者（Count值）當(dāng)任務(wù)訪問完被信號(hào)量保護(hù)的共享資源后，必須釋放信號(hào)量，釋放信號(hào)量通過把信號(hào)量的值加1實(shí)現(xiàn)，假如信號(hào)量的值為非正數(shù)，表明有任務(wù)等待當(dāng)前信號(hào)量，因此它也喚醒任何等待該信號(hào)量的任務(wù)4.3.7Linux中的信號(hào)量機(jī)制2、信號(hào)量聲明StaticDECLARE_SEMAPHORE_GENERIC(name,count);聲明互斥信號(hào)量的快捷方法：

StaticDECLARE_MUTEX(name);DECLARE_MUTEX(name)：該宏聲明一個(gè)信號(hào)量name并初始化它的值為0，即聲明一個(gè)互斥鎖DECLARE_MUTEX_LOCKED(name)：該宏聲明一個(gè)互斥鎖name，但其初始值配置為0，即鎖在創(chuàng)建時(shí)就處在已鎖狀態(tài)。因此對于這種鎖，一般是先釋放后獲得4.3.7Linux中的信號(hào)量機(jī)制3、信號(hào)量初始化voidsema_init(structsemaphore*sem,int

val);將信號(hào)量sem初始值配置為valvoidinit_MUTEX(structsemaphore*sem);初始化一個(gè)互斥鎖，將信號(hào)量sem的值配置為1voidinit_MUTEX_LOCKED(structsemaphore*sem);也用于初始化一個(gè)互斥鎖，但將信號(hào)量sem的值配置為0，即一開始就處在已鎖狀態(tài)

4.3.7Linux中的信號(hào)量機(jī)制4、信號(hào)量獲取voiddown(structsemaphore*sem);會(huì)導(dǎo)致睡眠，不能在中斷上下文使用。該函數(shù)將把sem的值減1，非負(fù)就直接返回，否則掛起調(diào)用者，等待別的任務(wù)釋放該信號(hào)量int

down_interruptable(structsemaphore*sem);可能被信號(hào)打斷，可通過有返回值來區(qū)分是正常返回（返回0）還是被信號(hào)中斷（返回-EINTR）int

down_trylock(structsemaphore*sem);嘗試獲得信號(hào)量sem，假如能夠立即獲得，它就獲得該信號(hào)量并返回0，否則，返回值為非0值。它不會(huì)導(dǎo)致調(diào)用者睡眠，能夠在中斷上下文使用

4.3.7Linux中的信號(hào)量機(jī)制5、信號(hào)量釋放voidup(structsemaphore*sem);釋放信號(hào)量sem，即把sem的值加1，假如sem的值為非正數(shù)，表明有任務(wù)等待該信號(hào)量，則將喚醒這些等待者4.3.7Linux中的信號(hào)量機(jī)制6、SystemV信號(hào)量的幾個(gè)主要函數(shù)key_t

ftok(char*pathname，charproj);根據(jù)pathname和proj來創(chuàng)建一個(gè)關(guān)鍵字

int

semget(key_tkey，int

nsems，int

semflg);創(chuàng)建一個(gè)信號(hào)量。成功時(shí)返回返回信號(hào)量句柄（信號(hào)的ID），失敗則返回-1key是一個(gè)關(guān)鍵字，可以是用ftok創(chuàng)建的也可以是IPC_PRIVATE表明由系統(tǒng)選用一個(gè)關(guān)鍵字nsems表明創(chuàng)建的信號(hào)個(gè)數(shù)semflg是創(chuàng)建的權(quán)限標(biāo)志，和創(chuàng)建一個(gè)文件的標(biāo)志相同4.3.7Linux中的信號(hào)量機(jī)制int

semctl(int

semid，int

semnum，int

cmd，unionsemun

arg);對信號(hào)量進(jìn)行一系列的控制semid是要操作的信號(hào)標(biāo)志semnum是信號(hào)的個(gè)數(shù)cmd是操作的命令int

semop(int

semid，struct

sembuf*spos，int

nspos);對信號(hào)進(jìn)行操作semid是信號(hào)標(biāo)志spos是一個(gè)操作數(shù)組表明要進(jìn)行什么操作。struct

sembuf{shortsem_num;/*使用哪一個(gè)信號(hào)*/shortsem_op;/*進(jìn)行什么操作*/shortsem_flg;/*操作的標(biāo)志*/};

nspos表明數(shù)組個(gè)數(shù)第三章并發(fā)進(jìn)程

4.1并發(fā)進(jìn)程4.2臨界區(qū)管理4.3信號(hào)量與P、V操作4.4進(jìn)程間通信4.5死鎖4.6管程4.4進(jìn)程間通信4.4.1進(jìn)程間通信概念4.4.2進(jìn)程間通信方式4.4.3Linux中的進(jìn)程間通信機(jī)制4.4.1進(jìn)程間通信概念1、進(jìn)程間通信（Inter-ProcessCommunication/IPC）：進(jìn)程之間互相交換信息的工作。進(jìn)程間的通信根據(jù)通信的內(nèi)容可以劃分為兩種控制信息的傳送：只傳遞簡單的信號(hào)，不能傳遞交換大量信息，如信號(hào)量機(jī)制及P、V操作（低級(jí)通信原語）控制的進(jìn)程同步和互斥大批量數(shù)據(jù)傳送：用Send/Receive原語（高級(jí)通信原語）4.4進(jìn)程間通信4.4.1進(jìn)程間通信概念4.4.2進(jìn)程間通信方式4.4.3Linux中的進(jìn)程間通信機(jī)制4.4.2進(jìn)程間通信方式1、主從式（Master-Servant）通信：主進(jìn)程-從進(jìn)程主進(jìn)程可自由地使用從進(jìn)程的資源或數(shù)據(jù)從進(jìn)程的動(dòng)作受主進(jìn)程的控制主進(jìn)程和從進(jìn)程關(guān)系固定典型例子是終端控制進(jìn)程和終端進(jìn)程4.4.2進(jìn)程間通信方式2、會(huì)話式（Dialogue）通信：使用進(jìn)程-服務(wù)進(jìn)程使用進(jìn)程調(diào)用服務(wù)進(jìn)程提供的服務(wù)使用進(jìn)程在使用服務(wù)進(jìn)程所提供的服務(wù)之前，必須得到服務(wù)進(jìn)程的許可服務(wù)進(jìn)程根據(jù)使用進(jìn)程的要求提供服務(wù)，但對所提供服務(wù)的控制由服務(wù)進(jìn)程自身完成使用進(jìn)程和服務(wù)進(jìn)程在進(jìn)行通信時(shí)有固定連接關(guān)系4.4.2進(jìn)程間通信方式3、消息隊(duì)列或郵箱（MessageQueueorMailbox）：發(fā)送進(jìn)程-接收進(jìn)程消息用于表示所交換的數(shù)據(jù)，傳遞大量信息之外，還意味著兩個(gè)互相通信的進(jìn)程地位平等緩沖區(qū)或郵箱專門存放被傳送消息只要存在空緩沖區(qū)或郵箱，無論接收進(jìn)程是否已準(zhǔn)備好接收消息，發(fā)送進(jìn)程都將把所要發(fā)送的消息送入緩沖區(qū)隊(duì)列或郵箱發(fā)送進(jìn)程相接收進(jìn)程之間無直接連接關(guān)系4.4.2進(jìn)程間通信方式4、共享存儲(chǔ)區(qū)(SharedMemory):讀進(jìn)程-寫進(jìn)程兩個(gè)需要互相交換信息的進(jìn)程通過對同一共享數(shù)據(jù)區(qū)的操作來達(dá)到互相通信的目的不要求數(shù)據(jù)移動(dòng)4.4.2進(jìn)程間通信方式5、上述方式可以分為如下兩類：直接通信：信息直接傳遞給接收方在發(fā)送時(shí)，指定接收方的地址或標(biāo)識(shí)，也可以指定多個(gè)接收方或廣播式地址在接收時(shí)，允許接收來自任意發(fā)送方的消息，并在讀出消息的同時(shí)獲取發(fā)送方的地址接收方可接收來自任意發(fā)送方的消息，并在讀出消息的同時(shí)獲取發(fā)送方的地址4.4.2進(jìn)程間通信方式5、上述方式可以分為如下兩類：間接通信：借助于收發(fā)雙方進(jìn)程之外的共享數(shù)據(jù)結(jié)構(gòu)作為通信中轉(zhuǎn)如消息隊(duì)列或是信箱接收方和發(fā)送方的數(shù)目可以是任意的4.4.2進(jìn)程間通信方式6、通信過程中的其他特征通信鏈路特征鏈路是點(diǎn)對點(diǎn)還是廣播鏈路通信鏈路是否帶緩沖區(qū)鏈路是單向還是雙向等4.4.2進(jìn)程間通信方式數(shù)據(jù)格式字節(jié)流格式：接收方不保留各次發(fā)送之間的分界報(bào)文格式：接收方保留各次發(fā)送之間的分界。報(bào)文方式還可進(jìn)一步分成定長報(bào)文/不定長報(bào)文和可靠報(bào)文/不可靠報(bào)文收發(fā)操作的同步方式阻塞操作：指操作方要等待操作結(jié)束不阻塞操作：指操作提交后立即返回4.4進(jìn)程間通信4.4.1進(jìn)程間通信概念4.4.2進(jìn)程間通信方式4.4.3Linux中的進(jìn)程間通信機(jī)制4.4.3Linux中的進(jìn)程間通信機(jī)制1、信號(hào)通信機(jī)制每個(gè)信號(hào)都對應(yīng)一個(gè)正整數(shù)常量（即信號(hào)編號(hào)

signalnumber），代表同一用戶的諸進(jìn)程之間傳送事先約定的信息的類型，用于通知某進(jìn)程發(fā)生了某異常事件每個(gè)進(jìn)程在運(yùn)行時(shí)，都要通過信號(hào)機(jī)制來檢查是否有信號(hào)到達(dá)。若有，便中斷正在執(zhí)行的程序，轉(zhuǎn)向與該信號(hào)相對應(yīng)的處理程序；處理結(jié)束后再返回到原來的斷點(diǎn)繼續(xù)執(zhí)行信號(hào)機(jī)制是對中斷機(jī)制的一種模擬，又稱為軟中斷

4.4.3Linux中的進(jìn)程間通信機(jī)制信號(hào)與中斷的相似點(diǎn)主要包括：①相同異步通信方式②檢測出有信號(hào)或中斷請求時(shí)，都暫停正在執(zhí)行的程序而轉(zhuǎn)去執(zhí)行相應(yīng)的處理程序③處理完畢后返回到原來的斷點(diǎn)④對信號(hào)或中斷都可進(jìn)行屏蔽4.4.3Linux中的進(jìn)程間通信機(jī)制信號(hào)與中斷的區(qū)別主要包括：①信號(hào)沒有優(yōu)先級(jí)，所有的信號(hào)都平等；而中斷有優(yōu)先級(jí)②信號(hào)處理程序在用戶態(tài)下運(yùn)行；而中斷處理程序是在核心態(tài)下運(yùn)行；③信號(hào)響應(yīng)通常都有較大的時(shí)間延遲；而中斷響應(yīng)是及時(shí)的4.4.3Linux中的進(jìn)程間通信機(jī)制信號(hào)機(jī)制的基本功能發(fā)送信號(hào)：由發(fā)送進(jìn)程把信號(hào)送到指定進(jìn)程的信號(hào)域的某一位上預(yù)置對信號(hào)的處理方式，一般有忽略、退出、執(zhí)行預(yù)知程序三種方式收受信號(hào)的進(jìn)程按事先的規(guī)定完成對相應(yīng)事件的處理4.4.3Linux中的進(jìn)程間通信機(jī)制2、共享存儲(chǔ)區(qū)機(jī)制通信速度最高的一種通信機(jī)制共享存儲(chǔ)區(qū)為內(nèi)存中的某一個(gè)區(qū)域，映射在若干需通過該區(qū)域通信的進(jìn)程的虛地址空間中一個(gè)進(jìn)程的虛地址空間中可以連接多個(gè)共享存儲(chǔ)區(qū)4.4.3Linux中的進(jìn)程間通信機(jī)制進(jìn)程間欲利用共享存儲(chǔ)區(qū)進(jìn)行通信時(shí)，必須先在內(nèi)存中建立一共享存儲(chǔ)區(qū)，然后將它附接到自己的虛地址空間上。此后，進(jìn)程對該區(qū)的訪問操作，與對其虛地址空間的其他部分的操作完全相同，通過對共享存儲(chǔ)區(qū)中數(shù)據(jù)的讀、寫來進(jìn)行直接通信共享存儲(chǔ)區(qū)機(jī)制并未提供對該區(qū)進(jìn)行互斥訪問及進(jìn)程同步的措施。因而當(dāng)用戶需要使用該機(jī)制時(shí)，必須自己設(shè)置同步和互斥措施才能保證實(shí)現(xiàn)正確的通信4.4.3Linux中的進(jìn)程間通信機(jī)制共享存儲(chǔ)區(qū)涉及的系統(tǒng)調(diào)用#include<sys/types.h>#include<sys/ipc.h>#include<sys/shm.h>shmget()創(chuàng)建、獲得一個(gè)共享存儲(chǔ)區(qū)：shmid=shmget(key,size,flag)shmat()從邏輯上將一個(gè)共享存儲(chǔ)區(qū)附接到進(jìn)程的虛擬地址空間上：virtaddr=shmat(shmid,addr,flag)shmdt()

把一個(gè)共享存儲(chǔ)區(qū)從指定進(jìn)程的虛地址空間斷開：shmdt(addr)shmctl()

對其狀態(tài)信息進(jìn)行讀取和修改：shmctl(shmid,cmd,buf)4.4.3Linux中的進(jìn)程間通信機(jī)制3、消息通信機(jī)制消息是一個(gè)格式化的可變長的信息單元消息通信機(jī)制允許由一個(gè)進(jìn)程給其他任意的進(jìn)程發(fā)送一個(gè)消息當(dāng)一個(gè)進(jìn)程收到多個(gè)消息時(shí)，可將它們排成一個(gè)消息隊(duì)列每一個(gè)消息隊(duì)列都有一個(gè)稱為關(guān)鍵字（key）的名字，即消息隊(duì)列描述符，由用戶指定，其作用與用戶文件描述符一樣，是為了方便用戶和系統(tǒng)對消息隊(duì)列的訪問4.4.3Linux中的進(jìn)程間通信機(jī)制相關(guān)數(shù)據(jù)結(jié)構(gòu)消息首部：記錄與消息有關(guān)的信息，如消息的類型、大小、指向消息數(shù)據(jù)區(qū)的指針、消息隊(duì)列的鏈接指針等消息隊(duì)列頭表：消息隊(duì)列頭表每一個(gè)表項(xiàng)作為一個(gè)消息隊(duì)列的消息頭，記錄消息隊(duì)列的有關(guān)信息，如指向消息隊(duì)列中第一個(gè)消息和指向最后一個(gè)消息的指針、隊(duì)列中消息的數(shù)目、隊(duì)列中消息數(shù)據(jù)的總字節(jié)數(shù)、隊(duì)列所允許消息數(shù)據(jù)的最大字節(jié)總數(shù)，還有最近一次執(zhí)行發(fā)送操作的進(jìn)程標(biāo)識(shí)符和時(shí)間、最近一次執(zhí)行接收操作的進(jìn)程標(biāo)識(shí)符和時(shí)間等4.4.3Linux中的進(jìn)程間通信機(jī)制消息通信涉及系統(tǒng)調(diào)用需引用頭文件#include<sys/types.h>#include<sys/ipc.h>#include<sys/msg.h>msgget()：創(chuàng)建一個(gè)消息，獲得一個(gè)消息的描述符調(diào)用格式msgqid=msgget(key,flag);key：用戶指定的消息隊(duì)列的名字flag：用戶設(shè)置的標(biāo)志和訪問方式msgqid

：該系統(tǒng)調(diào)用返回的描述符，失敗則返回-1主要工作：搜索消息隊(duì)列頭表查看是否有指定名字的消息隊(duì)列，有則檢查許可權(quán)并返回；無則分配新消息隊(duì)列頭并初始化，然后向用戶返回消息隊(duì)列描述符4.4.3Linux中的進(jìn)程間通信機(jī)制msgsnd()：向指定的消息隊(duì)列發(fā)送一個(gè)消息，并將該消息鏈接到該消息隊(duì)列的尾部

調(diào)用格式msgsnd(msgqid,msgp,size,flag);msgqid：返回消息隊(duì)列的描述符msgp：指向用戶消息緩沖區(qū)的一個(gè)結(jié)構(gòu)體指針，包括消息類型（長整型）和消息正文

（字符數(shù)組）size：msgp指向結(jié)構(gòu)體中字符數(shù)組的長度，即消息長度flag：規(guī)定當(dāng)核心用盡內(nèi)部緩沖空間時(shí)應(yīng)執(zhí)行的動(dòng)作：等待或立即返回4.4.3Linux中的進(jìn)程間通信機(jī)制主要工作：對消息隊(duì)列的描述符和許可權(quán)及消息長度等進(jìn)行檢查，不合法則返回；否則為消息分配消息數(shù)據(jù)區(qū)，將用戶消息緩沖區(qū)中的消息正文，拷貝到消息數(shù)據(jù)區(qū)；分配消息首部，并將它鏈入消息隊(duì)列的末尾，在消息首部中須填寫消息類型、消息大小和指向消息數(shù)據(jù)區(qū)的指針等數(shù)據(jù)；修改消息隊(duì)列頭中的數(shù)據(jù)，如隊(duì)列中的消息數(shù)、字節(jié)總數(shù)等；最后，喚醒等待消息的進(jìn)程

4.4.3Linux中的進(jìn)程間通信機(jī)制msgrcv()：從指定消息隊(duì)列中接收指定類型的消息

調(diào)用格式msgrcv(msgqid,msgp,size,type,flag);msgqid,msgp,size與msgsnd中的對應(yīng)參數(shù)相似type：規(guī)定要讀的消息類型flag：規(guī)定倘若該隊(duì)列無消息，核心應(yīng)作的操作主要工作：對消息隊(duì)列的描述符和許可權(quán)等進(jìn)行檢查，不合法則返回；否則①type=0，接收該隊(duì)列的第一個(gè)消息；②type>0，接收類型type的第一個(gè)消息；③type<0，接收小于等于type絕對值的最低類型的第一個(gè)消息。當(dāng)所返回消息大小等于或小于用戶的請求時(shí)，將消息正文拷貝到用戶區(qū)，并從消息隊(duì)列中刪除此消息，然后喚醒睡眠的發(fā)送進(jìn)程。但如果消息長度比用戶要求的大時(shí)，則作出錯(cuò)返回

4.4.3Linux中的進(jìn)程間通信機(jī)制msgctl()：讀取消息隊(duì)列的狀態(tài)信息并進(jìn)行修改，如查詢消息隊(duì)列描述符、修改它的許可權(quán)及刪除該隊(duì)列等調(diào)用格式msgctl(msgqid,cmd,buf);buf：用戶緩沖區(qū)地址，供用戶存放控制參數(shù)和查詢結(jié)果cmd：規(guī)定的命令，分3類函數(shù)調(diào)用成功時(shí)返回0，不成功則返回-14.4.3Linux中的進(jìn)程間通信機(jī)制共享存儲(chǔ)區(qū)和消息通信機(jī)制的比較①建立：消息隊(duì)列的建立消耗資源更少，它只是一個(gè)軟件上設(shè)定的問題；而共享區(qū)需要對硬件操作，實(shí)現(xiàn)內(nèi)存的映像，控制起來更復(fù)雜。如果每次都重新進(jìn)行隊(duì)列或共享的建立，共享區(qū)的設(shè)立沒有什么優(yōu)勢②使用：共享區(qū)的數(shù)據(jù)傳輸受到系統(tǒng)硬件的支持，不耗費(fèi)多余的資源。而消息傳遞由軟件進(jìn)行控制和實(shí)現(xiàn)，需要消耗一定的cpu的資源。從這個(gè)意義上講，共享區(qū)更適合頻繁和大量的數(shù)據(jù)傳輸③同步：消息的傳遞自身就帶有同步控制。而共享隊(duì)列如果不借助其他機(jī)制進(jìn)行同步，接收數(shù)據(jù)的一方必須進(jìn)行不斷地查詢，浪費(fèi)CPU資源。可見消息方式的使用更加靈活4.4.3Linux中的進(jìn)程間通信機(jī)制4、管道通信機(jī)制管道：能夠連接一個(gè)寫進(jìn)程和一個(gè)讀進(jìn)程的、并允許它們以生產(chǎn)者—消費(fèi)者方式進(jìn)行通信的一個(gè)共享文件，又稱為pipe文件由寫進(jìn)程從管道的寫入端（句柄1）將數(shù)據(jù)寫入管道，而讀進(jìn)程則從管道的讀出端（句柄0）讀出數(shù)據(jù)

4.4.3Linux中的進(jìn)程間通信機(jī)制管道類型有名管道：一個(gè)可以在文件系統(tǒng)中長期存在的、具有路徑名的文件，用系統(tǒng)調(diào)用mknod()建立。其他進(jìn)程可以知道它的存在并利用路徑名來訪問該文件。對有名管道的訪問與訪問其他文件一樣，需先用open()打開無名管道：一個(gè)利用pipe()建立起來臨時(shí)的無名文件（無路徑名）。只用該系統(tǒng)調(diào)用所返回的文件描述符來標(biāo)識(shí)該文件，故只有調(diào)用pipe()的進(jìn)程及其子孫進(jìn)程才能識(shí)別此文件描述符并利用該文件（管道）進(jìn)行通信4.4.3Linux中的進(jìn)程間通信機(jī)制管道通信的互斥問題各進(jìn)程應(yīng)互斥地訪問pipe文件索引結(jié)點(diǎn)中的直接地址項(xiàng)，每次進(jìn)程在訪問pipe文件前都需檢查該索引文件是否已被上鎖。若是，進(jìn)程便睡眠等待，否則，將其上鎖，進(jìn)行讀/寫。操作結(jié)束后解鎖，并喚醒因該索引結(jié)點(diǎn)上鎖而睡眠的進(jìn)程管道通信涉及系統(tǒng)調(diào)用#include<unistd.h>#inlcude<signal.h>#include<stdio.h>4.4.3Linux中的進(jìn)程間通信機(jī)制pipe()

：調(diào)用格式pipe(filedes);建立一無名管道，為管道文件分配磁盤和內(nèi)存索引結(jié)點(diǎn)、為讀進(jìn)程分配文件表項(xiàng)、為寫進(jìn)程分配文件表項(xiàng)、分配用戶文件描述符。read()

：調(diào)用格式read(fd,buf,nbyte);從fd指示的文件中讀出nbyte個(gè)字節(jié)的數(shù)據(jù)，并將它們送至由指針buf所指示的緩沖區(qū)中。如該文件被加鎖，等待，直到鎖打開為止write()：調(diào)用格式write(fd,buf,nbyte);把nbyte

個(gè)字節(jié)的數(shù)據(jù)，從buf所指向的緩沖區(qū)寫到由fd所指向的文件中。如文件加鎖，暫停寫入，直至開鎖第三章并發(fā)進(jìn)程

4.1并發(fā)進(jìn)程4.2臨界區(qū)管理4.3信號(hào)量與P、V操作4.4進(jìn)程間通信4.5死鎖4.6管程4.5死鎖4.5.1死鎖的基本概念4.5.2死鎖的預(yù)防——解決死鎖的靜態(tài)方法4.5.3死鎖的避免——解決死鎖的動(dòng)態(tài)方法4.5.4死鎖的檢測及解除

4.5.1死鎖的基本概念1、死鎖的定義操作系統(tǒng)中多道進(jìn)程的并發(fā)執(zhí)行可以改善系統(tǒng)的資源利用率，但也可能出現(xiàn)若干進(jìn)程都相互等待對方釋放資源才能繼續(xù)運(yùn)行，否則就阻塞的情況死鎖：系統(tǒng)中兩個(gè)或者多個(gè)進(jìn)程無限期地等待永遠(yuǎn)不會(huì)發(fā)生的條件，系統(tǒng)處于停滯狀態(tài)，這種現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱為死鎖進(jìn)程4.5.1死鎖的基本概念2、死鎖產(chǎn)生的例子申請不同類資源P1： P2：… …申請打印機(jī) 申請掃描儀申請掃描儀 申請打印機(jī)使用 使用釋放打印機(jī) 釋放打印機(jī)釋放掃描儀 釋放掃描儀… …申請同類資源內(nèi)存資源有m個(gè)分配單位，n個(gè)進(jìn)程共享，每個(gè)進(jìn)程依次只能申請一個(gè)單位，滿足總量才能使用，使用完后一次性釋放4.5.1死鎖的基本概念3、死鎖產(chǎn)生的原因因?yàn)橄到y(tǒng)資源不足：如果系統(tǒng)資源充足，進(jìn)程的資源請求都能夠得到滿足，死鎖出現(xiàn)的可能性就很低，否則就會(huì)因爭奪有限的資源而陷入死鎖進(jìn)程運(yùn)行推進(jìn)的順序不合適：如上面打印機(jī)和掃描儀申請一例資源分配不當(dāng)：如上面內(nèi)存分配一例4.5.1死鎖的基本概念4、產(chǎn)生死鎖的4個(gè)必要條件：①互斥使用（資源獨(dú)占）：一個(gè)資源每次只能給一個(gè)進(jìn)程使用②不可強(qiáng)占（不可剝奪）：資源申請者不能強(qiáng)行地從資源占有者手中奪取資源，資源只能由占有者自愿釋放③請求和保持（部分分配，占有申請）：一個(gè)進(jìn)程在申請新的資源的同時(shí)保持對原有資源的占有（只有這樣才是動(dòng)態(tài)申請，動(dòng)態(tài)分配）④循環(huán)等待：存在一個(gè)進(jìn)程等待隊(duì)列{P1,P2,…,Pn}，其中P1等待P2占有的資源，P2等待P3占有的資源，…，Pn等待P1占有的資源，形成一個(gè)進(jìn)程等待環(huán)路

4.5死鎖4.5.1死鎖的基本概念4.5.2死鎖的預(yù)防——解決死鎖的靜態(tài)方法4.5.3死鎖的避免——解決死鎖的動(dòng)態(tài)方法4.5.4死鎖的檢測及解除

4.5.2死鎖的預(yù)防

——解決死鎖的靜態(tài)方法1、基本策略在系統(tǒng)設(shè)計(jì)時(shí)確定資源分配算法，保證不發(fā)生死鎖通過破壞產(chǎn)生死鎖的4個(gè)必要條件之一來實(shí)現(xiàn)由于系統(tǒng)存在很多獨(dú)占資源，破壞“互斥使用”這一必要條件不太現(xiàn)實(shí)，重點(diǎn)探討破壞后3種必要條件的方法4.5.2死鎖的預(yù)防

——解決死鎖的靜態(tài)方法2、破壞“不可剝奪”條件在允許進(jìn)程動(dòng)態(tài)申請資源前提下規(guī)定，一個(gè)進(jìn)程在申請新的資源不能立即得到滿足而變?yōu)榈却隣顟B(tài)之前，必須釋放已占有的全部資源，若需要再重新申請3、破壞“請求和保持”條件要求每個(gè)進(jìn)程在運(yùn)行前必須一次性申請它所要求的所有資源，且僅當(dāng)該進(jìn)程所要資源均可滿足時(shí)才給予一次性分配4.5.2死鎖的預(yù)防

——解決死鎖的靜態(tài)方法4、破壞“循環(huán)等待”條件采用資源有序分配法，把系統(tǒng)中所有資源編號(hào)，進(jìn)程在申請資源時(shí)必須嚴(yán)格按資源編號(hào)的遞增次序進(jìn)行，否則操作系統(tǒng)不予分配例如，有資源1，2，3，…，m，現(xiàn)有n個(gè)進(jìn)程來競爭這些資源，則須按下圖所示遞增順序申請資源4.5死鎖4.5.1死鎖的基本概念4.5.2死鎖的預(yù)防——解決死鎖的靜態(tài)方法4.5.3死鎖的避免——解決死鎖的動(dòng)態(tài)方法4.5.4死鎖的檢測及解除

4.5.3死鎖的避免

——解決死鎖的動(dòng)態(tài)方法1、基本策略在系統(tǒng)運(yùn)行過程中，對進(jìn)程發(fā)出的每一個(gè)系統(tǒng)能夠滿足的資源申請進(jìn)行動(dòng)態(tài)檢查，并根據(jù)檢查結(jié)果決定是否分配資源，若分配后系統(tǒng)可能發(fā)生死鎖，則不予分配，否則予以分配關(guān)鍵在于區(qū)分安全狀態(tài)與不安全狀態(tài)，安全狀態(tài)一定沒有死鎖發(fā)生，因而對進(jìn)程的申請進(jìn)行試分配，分配后系統(tǒng)狀態(tài)為安全狀態(tài)則滿足，否則不滿足4.5.3死鎖的避免

——解決死鎖的動(dòng)態(tài)方法2、一個(gè)典型的死鎖避免算法：銀行家算法①銀行家擁有一筆周轉(zhuǎn)資金②客戶要求分期貸款，如果客戶能夠得到各期貸款，就一定能夠歸還貸款，否則就一定不能歸還貸款③銀行家應(yīng)謹(jǐn)慎地貸款，防止出現(xiàn)壞賬④銀行家采用的具體方法是看他是否有足夠的剩余資金滿足某一個(gè)需求的客戶，如此反復(fù)下去⑤如果所有投資最終都被收回，則該狀態(tài)是安全的，最初的請求可以批準(zhǔn)4.5.3死鎖的避免

——解決死鎖的動(dòng)態(tài)方法3、銀行家算法思想在單種資源情況下的應(yīng)用對進(jìn)程的每個(gè)針對該資源的申請進(jìn)行檢查，若會(huì)導(dǎo)致不安全狀態(tài)，則不滿足該申請；否則便滿足安全狀態(tài)的具體定義：安全序列：如果對一個(gè)進(jìn)程序列P1，…，Pn中的每一個(gè)進(jìn)程Pi(1≤i≤n），它以后尚需要的資源量不超過系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj(j<i)當(dāng)前占有資源量之和，則該序列為安全序列安全狀態(tài)：如果系統(tǒng)中的所有進(jìn)程能夠排成一個(gè)安全序列，則系統(tǒng)處于安全狀態(tài)4.5.3死鎖的避免

——解決死鎖的動(dòng)態(tài)方法例1：一個(gè)共有150個(gè)存儲(chǔ)單元的系統(tǒng)，分配給3個(gè)進(jìn)程，P1最大需求70，己占有25；P2最大需求60,己占有40；P3最大需求60，己占有45資源申請：P4進(jìn)程到達(dá)，最大需求60，最初請求25個(gè)試分配：由于系統(tǒng)目前還有150-25-40-45=40個(gè)單元，P4進(jìn)程到達(dá)，若滿足其申請，則系統(tǒng)還余15個(gè)單元分析此時(shí)系統(tǒng)狀態(tài)（尋找安全序列）：可以將15個(gè)單元分給P3，它執(zhí)行完后會(huì)釋放60個(gè)單元，可供P1（還要45個(gè)單元），P2（還要20個(gè)單元），P4（還要35個(gè)單元）任何一個(gè)執(zhí)行。存在P3P1P2P4等6種安全序列決定是否滿足申請：預(yù)分配后系統(tǒng)仍處于安全狀態(tài)，因而可以滿足P4的資源申請4.5.3死鎖的避免

——解決死鎖的動(dòng)態(tài)方法例2：一個(gè)共有150個(gè)存儲(chǔ)單元的系統(tǒng)，分配給3個(gè)進(jìn)程，P1最大需求70，己占有25；P2最大需求60,己占有40；P3最大需求60，己占有45資源申請：P4進(jìn)程到達(dá)，最大需求60，最初請求35試分配：由于系統(tǒng)目前還有150-25-40-45=40個(gè)單元，P4進(jìn)程到達(dá)，若滿足其申請，則系統(tǒng)還余5個(gè)單元分析此時(shí)系統(tǒng)狀態(tài)（尋找安全序列）：不能滿足任何一個(gè)進(jìn)程需求，找不到安全序列決定是否滿足申請：預(yù)分配后系統(tǒng)進(jìn)入不安全狀態(tài)，因而不能滿足P4的資源申請4.5.3死鎖的避免

——解決死鎖的動(dòng)態(tài)方法4、銀行家算法思想在多種資源情況下的應(yīng)用系統(tǒng)有n個(gè)進(jìn)程和m種不同類型的資源，相關(guān)定義如下各類資源總數(shù)向量——Resource=(R1,R2,…,Rm)，其中Ri表示第i類資源總數(shù)各類資源未分配數(shù)向量——Available=(V1,V2,…,Vm)最大需求矩陣——Cij表示進(jìn)程Pi對Rj類資源的最大需求量分配矩陣——Aij表示進(jìn)程Pi已分到Rj類資源的個(gè)數(shù)4.5.3死鎖的避免

——解決死鎖的動(dòng)態(tài)方法下列關(guān)系式確保成立Ri=Vi+∑Aki，對i=1,..,m,k=1,..,n，表示所有資源要么已被分配、要么尚可分配Cki≤Ri，對i=1,...,m,k=1,..,n，表示進(jìn)程申請資源數(shù)不能超過系統(tǒng)擁有的資源總數(shù)。

Aki≤Cki，對i=1,...,m,k=1,..,n，表示進(jìn)程申請任何類資源數(shù)不能超過聲明的最大資源需求數(shù)4.5.3死鎖的避免

——解決死鎖的動(dòng)態(tài)方法系統(tǒng)安全性定義在時(shí)刻T0系統(tǒng)是安全的，僅當(dāng)存在一個(gè)進(jìn)程序列P1,...,Pn，對進(jìn)程Pk(k=1,...,n)滿足公式：則該序列稱安全序列公式左邊表示進(jìn)程Pk尚缺少的各類資源Vi是T0時(shí)刻系統(tǒng)尚可用于分配且為Pk所想要的那類資源數(shù)；∑Aji表示排在進(jìn)程Pk之前的所有進(jìn)程占用的Pk所需要的資源的總數(shù)

4.5.3死鎖的避免

——解決死鎖的動(dòng)態(tài)方法算法基本思想①系統(tǒng)中所有進(jìn)程進(jìn)入進(jìn)程集合；在安全狀態(tài)下系統(tǒng)收到進(jìn)程的資源請求后進(jìn)行試分配（修改Available）②將系統(tǒng)剩余資源和進(jìn)程集合中其他進(jìn)程還需要的資源數(shù)作比較，找出能滿足最大需求量的進(jìn)程Pi（即(Ci1,…Cim)-(Ai1,…Aim)≤Available），找不到則轉(zhuǎn)④③把進(jìn)程Pi從集合中去掉，將其占用資源歸還給系統(tǒng)（即Available+=(Ai1,…Aim)）；集合為空轉(zhuǎn)④，否則轉(zhuǎn)②④檢查進(jìn)程集合，若為空表明本次申請執(zhí)行后系統(tǒng)仍處于安全狀態(tài)，可實(shí)施分配；否則說明該申請將導(dǎo)致系統(tǒng)處于不安全狀態(tài)，則暫不實(shí)施分配，讓申請進(jìn)程等待

4.5.3死鎖的避免

——解決死鎖的動(dòng)態(tài)方法例：系統(tǒng)狀態(tài)如下圖所示，給出了剩余資源Available、最大需求矩陣C、分配矩陣A的情況，試處理進(jìn)程P1發(fā)出的資源請求(1,0,0,0)4.5.3死鎖的避免

——解決死鎖的動(dòng)態(tài)方法例：試分配后，Available=(0,6,2,2)0012075023560652065620000012075023560652065620004.5.3死鎖的避免

——解決死鎖的動(dòng)態(tài)方法例：P0符合條件，歸還資源后，Available=(0,6,2,2)+(0,0,3,2)=(0,6,5,4)0012075023