操作系統(tǒng)課件第3章 進(jìn)程同步與通信

第3章進(jìn)程同步與通信●進(jìn)程同步與互斥

●經(jīng)典進(jìn)程同步問題

●管程

●AND信號(hào)量

●進(jìn)程通信本章要點(diǎn)●3.1進(jìn)程的同步與互斥同步與互斥的引入●OS引入進(jìn)程后，由于進(jìn)程的異步性，可能會(huì)導(dǎo)致程序執(zhí)行結(jié)果的不確定性，使程序執(zhí)行時(shí)出現(xiàn)不可再現(xiàn)性。●進(jìn)程互斥與同步的主要任務(wù)是使并發(fā)執(zhí)行的諸進(jìn)程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。進(jìn)程同步的基本概念●同步：指多個(gè)進(jìn)程中發(fā)生的事件存在著某種時(shí)序關(guān)系，它們必須按規(guī)定時(shí)序執(zhí)行，以共同完成一項(xiàng)任務(wù)?！窕コ猓憾鄠€(gè)進(jìn)程不能同時(shí)使用同一資源?！衽R界資源：某段時(shí)間內(nèi)僅允許一個(gè)進(jìn)程使用的資源。●臨界區(qū)：每個(gè)進(jìn)程中訪問臨界資源的那段代碼。例：P1，P2兩進(jìn)程共享變量COUNT（COUNT的初值為5）P1:{R1=COUNT;R1=R1+1;COUNT=R1;}P2:{R2=COUNT;R2=R2+1;

COUNT=R2;}分析：●1》執(zhí)行順序P2→P1執(zhí)行結(jié)果P1：COUNT為7，P2：COUNT為6?！?》執(zhí)行順序P1：{R1=COUNT}P2：{R2=COUNT}P1：{R1=R1+1；COUNT=R1}P2：{R2=R2=1；COUNT=R2}執(zhí)行結(jié)果P1：COUNT為6，P2：COUNT為6。臨界資源實(shí)例？例：P1，P2兩線程共享變量COUNT（COUNT的初值為5）P1:{R1=COUNT;R1=R1+1;COUNT=R1;}P2:{R2=COUNT;R2=R2+1;

COUNT=R2;}用Bernstein條件考察R（P1）={R1，COUNT}W（P1）={R1，COUNT}R（P2）={R2，COUNT}W（P2）={R2，COUNT}R（P1）∩W（P2）<>{}臨界資源實(shí)例！●

P1、P2不符合Bernstein條件●必須對(duì)程序的執(zhí)行順序施加某種限制P1:{R1=COUNT;R1=R1+1;COUNT=R1;}進(jìn)入?yún)^(qū)退出區(qū)P2:{R2=COUNT;R2=R2+1;COUNT=R2;}進(jìn)入?yún)^(qū)退出區(qū)While(1){●空閑讓進(jìn)

當(dāng)無進(jìn)程處于臨界區(qū)時(shí)，臨界資源處于空閑狀態(tài)。此時(shí)允許進(jìn)程進(jìn)入臨界區(qū)?！衩t等待當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時(shí)，臨界資源正在被訪問，其他想進(jìn)入臨界區(qū)的進(jìn)程必須等待?！裼邢薜却龑?duì)于要求訪問臨界資源的進(jìn)程，應(yīng)保證在有效的時(shí)間內(nèi)進(jìn)入，以免進(jìn)入“死等”狀態(tài)?！褡寵?quán)等待當(dāng)進(jìn)程不能進(jìn)入臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)程進(jìn)入“忙等”。進(jìn)入?yún)^(qū)臨界區(qū)退出區(qū)剩余區(qū)}同步機(jī)制應(yīng)遵循的準(zhǔn)則訪問臨界資源的進(jìn)程描述為互斥實(shí)現(xiàn)的硬件方法●禁止中斷●專用機(jī)器指令

●TS（TestandSet）指令

●Swap指令//TS指令： booleanTS(lock); booleanlock; { booleantemp; temp=lock; lock=true; returntemp;}●Lock有兩種狀態(tài)： ●當(dāng)lock=false時(shí)，表示資源空閑;

●當(dāng)lock=true時(shí)，表示資源正在被使用?！駷榱藢?shí)現(xiàn)互斥，設(shè)布爾變量lock，其初值為false,表示資源空閑。利用TS指令實(shí)現(xiàn)互斥?！袢秉c(diǎn)：沒有做到：“讓權(quán)等待”。//TS指令的使用

while(TS(lock)) /*什么也不做*/;

臨界區(qū); lock=false;

剩余區(qū);TS（TestandSet）指令互斥實(shí)現(xiàn)的軟件方法//進(jìn)程0while(turn!=0)

//什么都不做;

臨界區(qū);turn=

1;剩余區(qū);

//進(jìn)程1while(turn!=1)do

//什么都不做‘;

臨界區(qū);turn=0;剩余區(qū);●設(shè)置公共整型變量turn，用于指示進(jìn)入臨界區(qū)的進(jìn)程編號(hào)i(i=0,1)。使P0、P1輪流訪問臨界資源?！袢秉c(diǎn)：強(qiáng)制性輪流進(jìn)入臨界區(qū)，不能保證“空閑讓進(jìn)”。——單標(biāo)志算法！//進(jìn)程0

while(flag[1])

//什么都不做; flag[0]=true;

臨界區(qū);

flag[0]=false;

剩余區(qū);//進(jìn)程1 while(flag[0])

//什么都不做; flag[1]=true;

臨界區(qū);

flag[1]=false;

剩余區(qū);●設(shè)置數(shù)組flag，初始時(shí)設(shè)每個(gè)元素為false,表示所有進(jìn)程都未進(jìn)入臨界區(qū)。若flag[i]=true,表示進(jìn)程進(jìn)入臨界區(qū)執(zhí)行?！裨诿總€(gè)進(jìn)程進(jìn)入臨界區(qū)時(shí)，先查看臨界資源是否被使用，若正在使用，該進(jìn)程等待，否則才可進(jìn)入。解決了“空閑讓進(jìn)”問題?！袢秉c(diǎn)：可能同時(shí)進(jìn)入臨界區(qū)，不能保證“忙則等待”。用軟件方法解決互斥問題——雙標(biāo)志、先檢查算法！//進(jìn)程0

flag[0]=true; while(flag[1])

//什么也不做;

臨界區(qū); flag[0]=false;

剩余區(qū);●兩進(jìn)程先后同時(shí)作 flag[i]=true;●缺點(diǎn)：保證了不同時(shí)進(jìn)入臨界區(qū)，但又可能都進(jìn)不去。不能保證“有空讓進(jìn)”。//進(jìn)程1 flag[1]=true; while(flag[0])

//什么也不做;

臨界區(qū); flag[1]=false;

剩余區(qū);——雙標(biāo)志、先修改后檢查算法用軟件方法解決互斥問題！//進(jìn)程0 flag[0]=true; turn=1; while(flag[1])&&(turn==1)

//什么也不做;

臨界區(qū); flag[0]=false;

剩余區(qū);保證了“有空讓進(jìn)”和“忙則等待”。//進(jìn)程1 flag[1]=true; turn=0; while(flag[0])&&(turn==0)

//什么也不做;

臨界區(qū); flag[1]=false;

剩余區(qū);——先修改、后檢查、后修改算法用軟件方法解決互斥問題！信號(hào)量和PV操作●

1965年，荷蘭學(xué)者Dijkstra提出了信號(hào)燈機(jī)制，卓有成效地解決了進(jìn)程同步問題?！裼涗浶托盘?hào)燈的定義structsemaphore{

intvalue;

structPCB*queue;}信號(hào)燈的PV操作voidwait(semaphores){s.value=s.value-1;

if(s.value<0)block(s.queue);/*將進(jìn)程阻塞，并將其投入等待隊(duì)列s.queue*/}voidsignal(semaphores){s.value=s.value+1;

if(s.value<=0)wackup(s.queue);/*喚醒阻塞進(jìn)程，將其從等待隊(duì)列s.queue取出，投入就緒隊(duì)列*/}從資源的觀點(diǎn)看信號(hào)燈的意義:●

s.value的初值表示系統(tǒng)中某種資源數(shù)目。●

wait(s)表示要申請(qǐng)一個(gè)資源?！?/p>

signal(s)表示要釋放一個(gè)資源?！?/p>

s.value<0時(shí)，|s.value|表示等待隊(duì)列的進(jìn)程數(shù)。信號(hào)燈的物理意義用信號(hào)燈解決互斥問題

semaphoremutex=1;

P1:

while(1){

P(mutex); 臨界區(qū);

V(mutex);

剩余區(qū);

};

P2: while(1){

P(mutex); 臨界區(qū)

V(mutex);

剩余區(qū);

};用信號(hào)燈解決同步問題semaphorea,b=0,0;{s1;V(a);V(b)}{P(a);

s2}{P(b);

s3}●生產(chǎn)者——消費(fèi)者問題●讀者——寫者問題●哲學(xué)家進(jìn)餐問題●打磕睡的理發(fā)師問題●3.2經(jīng)典進(jìn)程同步問題生產(chǎn)者-消費(fèi)者問題●指有兩組進(jìn)程共享一個(gè)環(huán)形的緩沖池。一組進(jìn)程被稱為生產(chǎn)者，另一組進(jìn)程被稱為消費(fèi)者。●緩沖池是由若干個(gè)大小相等的緩沖區(qū)組成的，每個(gè)緩沖區(qū)可以容納一個(gè)產(chǎn)品?！裆a(chǎn)者進(jìn)程不斷地將生產(chǎn)的產(chǎn)品放入緩沖池，消費(fèi)者進(jìn)程不斷地將產(chǎn)品從緩沖池中取出。用信號(hào)量解決“生產(chǎn)者-消費(fèi)者”問題voidconsumer()//消費(fèi)者進(jìn)程{while(true){P(full);P(mutex);data_c=buffer[j];j=(j+1)%n;V(mutex);V(empty);consumetheitemindata_c;}}semaphoremutex=1;

semaphoreempty=n;

semaphorefull=0;inti,j;

ITEMbuffer[n];

ITEMdata_p,data_c;

voidproducer()//生產(chǎn)者進(jìn)程{while(true){produceanitemindata_p;P(empty);P(mutex);buffer[i]=data_p;i=(i+1)%n;V(mutex);V(full);}}讀者-寫者問題●一個(gè)數(shù)據(jù)對(duì)象若被多個(gè)并發(fā)進(jìn)程所共享，且其中一些進(jìn)程只要求讀該數(shù)據(jù)對(duì)象的內(nèi)容，而另一些進(jìn)程則要求寫操作，對(duì)此，我們把只想讀的進(jìn)程稱為“讀者”，而把要求寫的進(jìn)程稱為“寫者”。

●問題描述：●讀者可同時(shí)讀；●讀者讀時(shí)，寫者不可寫；●寫者寫時(shí)，其他的讀者、寫者均不可進(jìn)入。

讀者進(jìn)程： while(true) {

‘有人要讀’P(Wmutex); 讀;

‘無人讀了’

V(Wmutex); }寫者進(jìn)程：while(true){

P(Wmutex); 寫;

V(Wmutex);

}

semaphoreWmutex=1;用信號(hào)量解決讀者-寫者問題voidreader()/*讀者進(jìn)程*/{while(true){P(Rmutex);

if(Rcount==0)P(Wmutex);

Rcount=Rcount+1; V(Rmutex); read;/*執(zhí)行讀操作*/

P(Rmutex); Rcount=Rcount-1; if(Rcount==0)V(Wmutex); V(Rmutex);}}SemaphoreWmutex,Rmutex=1,1;intRcount;用信號(hào)量解決讀者-寫者問題voidwriter()/*寫者進(jìn)程*/{while(true){P(Wmutex); write;/*執(zhí)行寫操作*/V(Wmutex);}}哲學(xué)家進(jìn)餐問題●五個(gè)哲學(xué)家，他們的生活方式是交替地思考和進(jìn)餐?！裾軐W(xué)家們共用一張圓桌，圍繞著圓桌而坐，在圓桌上有五個(gè)碗和五支筷子，平時(shí)哲學(xué)家進(jìn)行思考，饑餓時(shí)拿起其左、右的兩支筷子，試圖進(jìn)餐，進(jìn)餐完畢又進(jìn)行思考?！襁@里的問題是哲學(xué)家只有拿到靠近他的兩支筷子才能進(jìn)餐，而拿到兩支筷子的條件是他的左、右鄰居此時(shí)都沒有進(jìn)餐。semaphorechopstick[5]={1,1,1,1,1};voidphilosopher(inti)/*哲學(xué)家進(jìn)程*/{while(true) {P(chopstick[i]); P(chopstick[(i+1)%5]); eating;/*進(jìn)餐*/ V(chopstick[i]); V(chopstick[(i+1)%5]); thinking;/*思考*/}}用信號(hào)量解決哲學(xué)家進(jìn)餐問題哲學(xué)家能順利地吃到飯嗎？打磕睡的理發(fā)師問題

理發(fā)店有一名理發(fā)師，一把理發(fā)椅，還有N把供等候理發(fā)的顧客坐的普通椅子。如果沒有顧客到來，理發(fā)師就坐在理發(fā)椅上打磕睡。當(dāng)顧客到來時(shí)，就喚醒理發(fā)師。如果顧客到來時(shí)理發(fā)師正在理發(fā)，顧客就坐下來等待。如果N把椅子都坐滿了，顧客就離開該理發(fā)店去別處理發(fā)。用信號(hào)量解決打磕睡的理發(fā)師問題voidcustomer() //顧客進(jìn)程{P(mutex);if(waiting<CHAIRS)//如果有空位，顧客等待 {waiting++; V(customers); //如果有必要，喚醒理發(fā)師

V(mutex); P(barners);//如果理發(fā)師正在理發(fā)，則顧客等待 get_haircut(); }else //如果沒有空位，則顧客離開

V(mutex); }#defineCHAIRS5 //為等候的顧客準(zhǔn)備的座椅數(shù)

semaphorecustomers=0;

semaphorebarners=0;

semaphoremutex=1;

intwaiting;voidbarber() //理發(fā)師進(jìn)程{while(true){P(customers);//如果沒有顧客，理發(fā)師就打磕睡

P(mutex);//互斥進(jìn)入臨界區(qū)

waiting--;V(barners);//理發(fā)師準(zhǔn)備理發(fā)了

V(mutex);cut_hair();//理發(fā)}}用信號(hào)量解決了很多同步和互斥問題，但在解決問題的過程中，我們也發(fā)現(xiàn)還存在一些問題，如在生產(chǎn)者和消費(fèi)者問題中兩個(gè)P操作的位置不能顛倒；哲學(xué)家進(jìn)餐問題中的死鎖現(xiàn)象等。這些問題的出現(xiàn)促使AND信號(hào)量的產(chǎn)生?！?.3AND信號(hào)量

Swait(s1,s2,…,sn){if(s1>=1&&s2>=1&&…&&sn>=1){/*滿足資源要求時(shí)*/

for(i=1;i<=n;i=i+1) si=si-1;}

else{/*某些資源不能滿足要求時(shí)*/ block(si.queue)/*將進(jìn)程投入第一個(gè)小于1的信號(hào)量的等待隊(duì)列si.queue*/; }}AND信號(hào)量定義AND信號(hào)量定義Ssignal(s1,s2,…,sn){for(i=1;i<=n;i=i+1) {si=si+1; for(等待隊(duì)列si.queue中的每個(gè)進(jìn)程P)

if(進(jìn)程P通過Swait中的測試) {/*通過檢查，即資源夠用*/

wackup(p);//喚醒進(jìn)程P；}

else {/*未通過檢查，即資源不夠用*/ 進(jìn)程P繼續(xù)等待；} }}用AND信號(hào)量解決哲學(xué)家進(jìn)餐問題semaphorechopstick[5]={1,1,1,1,1};voidphilosopher(inti)/*哲學(xué)家進(jìn)程*/{while(true) {Swait(chopstick[i],chopstick[(i+1)%5]); eat();/*進(jìn)餐*/ Ssignal(chopstick[i],chopstick[(i+1)%5]); think();/*思考*/ }}管程機(jī)制引入的原因：

●信號(hào)燈機(jī)制雖然既方便又有效地解決了進(jìn)程同步問題，但要求訪問臨界資源的進(jìn)程自備同步操作wait(s)、signal(s)，使得大量的同步操作分散在各個(gè)進(jìn)程中，給進(jìn)程的管理帶來不便，并會(huì)因同步操作使用不當(dāng)導(dǎo)致死鎖?！馠oare和Hanson提出了管程的概念把分散在各個(gè)進(jìn)程中的與同一共享資源有關(guān)的同步處理從各進(jìn)程中抽出并集中起來?！褚粋€(gè)管程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一組操作，這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù)。●管程

=數(shù)據(jù)結(jié)構(gòu)+操作+對(duì)數(shù)據(jù)結(jié)構(gòu)中變量的初始化●3.4管程的定義管程的結(jié)構(gòu)條件變量●用管程實(shí)現(xiàn)進(jìn)程同步，設(shè)置兩個(gè)同步操作原語wait,signal●為了區(qū)別等待的原因，引入條件變量condition 其形式為varx,y:condition 條件變量置于wait和signal之前，表示為x.wait和x.signal●例如：由于共享數(shù)據(jù)被占用而使調(diào)用進(jìn)程等待，該條件變量的形式為notbusy; wait原語應(yīng)改為notbusy.waitmonitor_name=monitor variabledeclarationsprocedureP1(……); { }procedureP2(……); { }procedurePn(……); { }{ initcode}管程的語法利用管程解決生產(chǎn)者-消費(fèi)者問題monitormonitor_PC;charbuffer[n];intnextin,nextout;intcount;conditionnotfull,notempty;voidput(charx);/*過程*/{

if(count==n)cwait(notfull);

buffer[nextin]=x;nextin=(nextin+1)%n;count=count+1;csignal(notempty);}voidget(charx);/*過程*/{

if(count==0)cwait(notempty);x=buffer[nextout];nextout=(nextout+1)%n;count=count-1;csignal(notfull);}{/*管程體*/

nextin=0;nextout=0;count=0; /*變量初始化*/}voidproducer()/*生產(chǎn)者進(jìn)程*/{

charx;

while(true) { produceancharinx; monitor_PC.put(x); }}

voidconsumer() /*消費(fèi)者進(jìn)程*/{

charx;

while(true) { monitor_PC.get(x); consumeanx; }}利用管程解決生產(chǎn)者-消費(fèi)者問題●3.5進(jìn)程通信信號(hào)燈作為進(jìn)程同步和互斥工具是卓有成效的。但作為通信工具就不夠理想。其原因?yàn)椋?●效率低——一次只傳一條消息。 ●通信對(duì)用戶不透明。因此必須引入高級(jí)通信工具，解決進(jìn)程之間大量的信息傳遞問題進(jìn)程通信的類型●共享存儲(chǔ)器系統(tǒng)●消息傳遞系統(tǒng)●直接通信方式●間接通信方式●管道通信進(jìn)程通信中的幾個(gè)問題●通信鏈路的建立方式●顯示建立鏈路●隱式建立鏈路●通信方向●通信鏈路連接方式

●通信鏈路的容量●數(shù)據(jù)格式

●同步方式●阻塞方式●不阻塞方式消息緩沖隊(duì)列-示意圖消息緩沖隊(duì)列-數(shù)據(jù)結(jié)構(gòu)定義//消息緩沖區(qū)定義structmessage_buffer{charsender[30]; /*發(fā)送進(jìn)程標(biāo)識(shí)符*/intsize; /*消息長度*/chartext[200]; /*消息正文*/structmessage_buffer*next; //指向下一個(gè)消息緩沖區(qū)的指針}//PCB中有關(guān)通信的數(shù)據(jù)項(xiàng)structprocess_control{structmessage_buffer*mq;/*消息隊(duì)列隊(duì)首指針*/

semaphoremutex