操作系統(tǒng)課件(第四章)_第1頁
操作系統(tǒng)課件(第四章)_第2頁
操作系統(tǒng)課件(第四章)_第3頁
操作系統(tǒng)課件(第四章)_第4頁
操作系統(tǒng)課件(第四章)_第5頁
已閱讀5頁,還剩141頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

操作系統(tǒng)

OperatingSystems

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

,2009年出版第三章并發(fā)進程

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

在一定時間內物理機器上有兩個或兩個以上的程序同處于開始運行但尚未結束的狀態(tài),并且次序不是事先確定的BAABBAAB4.1.1順序程序與并發(fā)進程2、并發(fā)進程的特征:間斷性執(zhí)行,執(zhí)行--停--執(zhí)行資源共享,多個進程共享使用系統(tǒng)資源不可再現(xiàn)性,執(zhí)行結果不確定獨立性和制約性程序和進程不再一一對應4.1并發(fā)進程4.1.1順序程序與并發(fā)進程4.1.2與時間有關的錯誤4.1.3進程間的聯(lián)系4.1.2與時間有關的錯誤1、并發(fā)進程交替使用共享資源時可能出現(xiàn)的錯誤:例如:P1和P2是兩個并發(fā)進程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與時間有關的錯誤2、飛機訂票問題:P1和P2是兩個并發(fā)的終端訂票進程,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個客戶的情況,原因是沒有正確地控制對共享變量x的訪問4.1.2與時間有關的錯誤3、緩沖區(qū)讀寫問題:get、copy、put是3個并發(fā)進程getcopyputfstg4.1并發(fā)進程4.1.1順序程序與并發(fā)進程4.1.2與時間有關的錯誤4.1.3進程間的聯(lián)系4.1.3進程間的聯(lián)系1、間接式與直接式制約:直接式制約:一程序段等待另一程序段的執(zhí)行結果間接式制約:并發(fā)程序段競爭同一資源2、相交進程與無關進程:相交進程:并發(fā)進程在邏輯上有某種聯(lián)系無關進程:邏輯上無任何聯(lián)系的并發(fā)進程直接作用只發(fā)生在相交進程之間;間接作用可以發(fā)生在相交進程之間,也可發(fā)生在無關進程之間4.1.3進程間的聯(lián)系3、進程的同步與互斥:進程同步(直接作用):根據(jù)一定的時序關系合作完成一項任務并發(fā)進程因直接制約而互相等待,彼此相互發(fā)送消息進行合作,使得各進程按一定的速度執(zhí)行進程互斥(間接作用):各進程競爭使用臨界資源臨界資源:一次只允許一個進程使用的系統(tǒng)資源進程互斥是進程同步的一種特殊情況第三章并發(fā)進程

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

4.2臨界區(qū)管理4.2.1臨界區(qū)及其使用原則4.2.2實現(xiàn)臨界區(qū)管理的軟件方法4.2.3實現(xiàn)臨界區(qū)管理的硬件方法4.2.2實現(xiàn)臨界區(qū)管理的軟件方法1、兩個失敗的嘗試(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實現(xiàn)臨界區(qū)管理的軟件方法1、兩個失敗的嘗試(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實現(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實現(xiàn)臨界區(qū)管理的軟件方法4.2.3實現(xiàn)臨界區(qū)管理的硬件方法4.2.3實現(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實現(xiàn)臨界區(qū)管理的硬件方法2、交換指令SWAP

交換指令將交換兩個字的內容。公共變量lock表臨界區(qū)是否上鎖,每個進程的私有變量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實現(xiàn)臨界區(qū)管理的硬件方法3、開關中斷指令進入臨界區(qū)前執(zhí)行“關中斷”指令;離開臨界區(qū)后,執(zhí)行“開中斷”指令,從而控制進程互斥進入臨界區(qū)硬件方法解決臨界區(qū)的管理較為簡單有效,其缺點主要在于會導致“忙等待”會導致“饑餓”中斷屏蔽方法代價較高,不適應多處理器第三章并發(fā)進程

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

pointerPCBqueue; //信號量隊列指針

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

s.value=s.value--; //s.value減1if(s.value<0) //該進程被阻塞,進入相應隊列,然后轉進程調度

{

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

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

}

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

s.value=s.value++; //s.value加1if(s.value<=0)//從隊列中喚醒一等待進程,然后繼續(xù)執(zhí)行或轉進程調度

{

喚醒相應等待隊列s.queue中等待的一個進程;

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

2、用信號量及P、V操作解決進程間互斥問題

mutex:semaphore;mutex:=1;cobegin

processPibegin…

P(mutex);臨界區(qū);V(mutex);…end;coend;4.3.3信號量的使用用信號量及P、V操作解決機票問題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信號量的使用3、用信號量及P、V操作解決進程間同步問題

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

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

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

P(s1); //初值為1

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

V(s2);};C //消費者進程while(true){

P(s2); //初值為0

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

V(s1);

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

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

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

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

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

gotoL1;end;coend

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

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

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

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

4.3.5信號量與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信號量與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信號量與P、V操作經(jīng)典問題3、蘋果桔子問題問題描述:桌上有一只盤子,每次只能放入一只水果;爸爸專向盤子中放蘋果(apple),媽媽專向盤子中放桔于(orange);一個兒子專等吃盤子中的桔子,一個女兒專等吃盤子里的蘋果解決思路:生產(chǎn)者消費者問題的變形,有兩類生產(chǎn)者和兩類消費者,仍然設置3個信號量sp表示盤子能放的水果數(shù)目,初值為1sg1表示盤子里有無桔子,初值為0Sg2表示盤子里有無蘋果,初值為0

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

processfatherbeginL1:削一個蘋果;

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

P(sp);放桔子;

V(sg1);gotoL2;end;coend

processdaughterbeginL4:P(sg2);取蘋果;

V(sp);吃蘋果;

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

V(sp);吃桔子;

gotoL3;end;4.3.5信號量與P、V操作經(jīng)典問題4、讀者和寫者問題問題描述:讀者和寫者兩組并發(fā)進程共享一個文件F,要求允許多個讀者同時執(zhí)行讀操作,任一寫者在完成寫操作之前不允許其他讀者或寫者工作,寫者執(zhí)行寫操作前,應讓已有的寫者和讀者全部退出

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

4.3.6POSIX信號量2、POSIX無名信號量sem_init

函數(shù):初始化指定的信號量int

sem_init(sem_t*sem,int

pshared,unsignedvalue);sem

指向要初始化的信號量value為信號量的初始值pshared

用于說明信號量的共享范圍如果成功,sem_init

返回0,如果不成功,sem_init

返回-1并設置errno

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

返回0,如果不成功返回-1并設置errno

。如果*sem

不是有效的信號量,sem_destroy

就將errno

置為EINVALsem_post

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

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

返回0。如果不成功

返回-1并設置errno

。如果*sem

不是有效的信號量,sem_post

就將errno

置為EINVAL4.3.6POSIX信號量sem_wait

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

sem_wait(sem_t*sem);sem_trywait

函數(shù)與sem_wait

類似,只是在試圖對一個為零的信號量進行操作時,它不會阻塞調用線程,而是立即返回int

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

sem_post、sem_wait

和sem_trywait

同樣可用于命名信號量

4.3.6POSIX信號量3、POSIX命名信號量命名信號量有一個名字、一個用戶ID、一個組ID和權限,它們是提供給那些不共享內存進程的使用接口命名信號量的名字是一個遵守路徑名構造規(guī)則的字符串sem_open

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

oflag);name是一個標識信號量的字符串oflag

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

的O_CREAT比特位,則會創(chuàng)建一個新的信號量4.3.6POSIX信號量sem_close

函數(shù):關閉命名信號量int

sem_close(sem_t*sem);sem指向要關閉的信號量的指針成功返回0,不成功返回-1并設置errno單個程序可以用sem_close

函數(shù)關閉命名信號量,但是這樣做并不能將信號量從系統(tǒng)中刪除,因為命名信號量在單個程序的執(zhí)行之外是具有持久性的當進程調用_exit、exit、exec或從main返回時,進程打開的命名信號量同樣會被關閉4.3.6POSIX信號量sem_unlink

函數(shù):在所有進程關閉了命名信號量之后,將信號量從系統(tǒng)中刪除int

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

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

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

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

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

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

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

ftok(char*pathname,charproj);根據(jù)pathname和proj來創(chuàng)建一個關鍵字

int

semget(key_tkey,int

nsems,int

semflg);創(chuàng)建一個信號量。成功時返回返回信號量句柄(信號的ID),失敗則返回-1key是一個關鍵字,可以是用ftok創(chuàng)建的也可以是IPC_PRIVATE表明由系統(tǒng)選用一個關鍵字nsems表明創(chuàng)建的信號個數(shù)semflg是創(chuàng)建的權限標志,和創(chuàng)建一個文件的標志相同4.3.7Linux中的信號量機制int

semctl(int

semid,int

semnum,int

cmd,unionsemun

arg);對信號量進行一系列的控制semid是要操作的信號標志semnum是信號的個數(shù)cmd是操作的命令int

semop(int

semid,struct

sembuf*spos,int

nspos);對信號進行操作semid是信號標志spos是一個操作數(shù)組表明要進行什么操作。struct

sembuf{shortsem_num;/*使用哪一個信號*/shortsem_op;/*進行什么操作*/shortsem_flg;/*操作的標志*/};

nspos表明數(shù)組個數(shù)第三章并發(fā)進程

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

signalnumber),代表同一用戶的諸進程之間傳送事先約定的信息的類型,用于通知某進程發(fā)生了某異常事件每個進程在運行時,都要通過信號機制來檢查是否有信號到達。若有,便中斷正在執(zhí)行的程序,轉向與該信號相對應的處理程序;處理結束后再返回到原來的斷點繼續(xù)執(zhí)行信號機制是對中斷機制的一種模擬,又稱為軟中斷

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

把一個共享存儲區(qū)從指定進程的虛地址空間斷開:shmdt(addr)shmctl()

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

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

調用格式msgsnd(msgqid,msgp,size,flag);msgqid:返回消息隊列的描述符msgp:指向用戶消息緩沖區(qū)的一個結構體指針,包括消息類型(長整型)和消息正文

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

4.4.3Linux中的進程間通信機制msgrcv():從指定消息隊列中接收指定類型的消息

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

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

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

:調用格式pipe(filedes);建立一無名管道,為管道文件分配磁盤和內存索引結點、為讀進程分配文件表項、為寫進程分配文件表項、分配用戶文件描述符。read()

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

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

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

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

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

4.5.2死鎖的預防

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

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

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

4.5.3死鎖的避免

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

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

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

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

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

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

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

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

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

4.5.3死鎖的避免

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

4.5.3死鎖的避免

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

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

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論