操作系統(tǒng)課件：第6章 進(jìn)程同步

Chap6進(jìn)程同步內(nèi)容背景臨界區(qū)問(wèn)題信號(hào)量經(jīng)典同步問(wèn)題管程同步實(shí)例原子事務(wù)總結(jié)背景對(duì)共享數(shù)據(jù)的并發(fā)訪問(wèn)可能導(dǎo)致數(shù)據(jù)的不一致性.要保持?jǐn)?shù)據(jù)的一致性，就需要一種保證并發(fā)進(jìn)程的正確執(zhí)行順序的機(jī)制.[第4章中]解決有界緩沖區(qū)問(wèn)題的共享內(nèi)存方法在同一時(shí)刻最多允許存放n-1個(gè)產(chǎn)品，所有n個(gè)緩沖區(qū)都被使用的解法不是簡(jiǎn)單的。假設(shè)通過(guò)增加一個(gè)變量counter來(lái)修改這一算法，初始化為0，每次向緩沖區(qū)增加一個(gè)新項(xiàng)時(shí)，counter遞增；每次從緩沖區(qū)中移去一項(xiàng)時(shí)，counter遞減。Shareddata

#defineBUFFER_SIZE10typedefstruct{ ...}item;itembuffer[BUFFER_SIZE];intin=0;intout=0;intcounter=0;有界緩沖區(qū)生產(chǎn)者進(jìn)程 itemnextProduced;

while(1){ while(counter==BUFFER_SIZE) ;/*donothing*/ buffer[in]=nextProduced; in=(in+1)%BUFFER_SIZE; counter++; }有界緩沖區(qū)enter（）消費(fèi)者進(jìn)程 itemnextConsumed;

while(1){ while(counter==0) ;/*donothing*/ nextConsumed=buffer[out]; out=(out+1)%BUFFER_SIZE; counter--; }

有界緩沖區(qū)remove（）下列語(yǔ)句必須被原子性地執(zhí)行

counter++;

counter--;

原子操作意味著一個(gè)操作在整個(gè)執(zhí)行期間沒(méi)有中斷。有界緩沖區(qū)語(yǔ)句“count++”可按如下方式以機(jī)器語(yǔ)言實(shí)現(xiàn)：

register1=counter register1=register1+1

counter=register1

語(yǔ)句“count--”可按如下方式來(lái)實(shí)現(xiàn)：

register2=counter

register2=register2–1

counter=register2有界緩沖區(qū)如果生產(chǎn)者和消費(fèi)者試圖并發(fā)地更新緩沖區(qū)，匯編語(yǔ)言語(yǔ)句可能交叉執(zhí)行。交叉取決于生產(chǎn)者和消費(fèi)者進(jìn)程是如何被調(diào)度的。有界緩沖區(qū)假設(shè)counter初值為5.一種語(yǔ)句的交叉形式如下:

producer:register1=counter(register1=5)

producer:register1=register1+1(register1=6)

consumer:register2=counter(register2=5)

consumer:register2=register2–1(register2=4)

producer:counter=register1(counter=6)

consumer:counter=register2(counter=4)

count

的值可以是4或6，而正確結(jié)果應(yīng)是5。有界緩沖區(qū)競(jìng)爭(zhēng)條件:多個(gè)進(jìn)程并發(fā)訪問(wèn)和操作同一數(shù)據(jù)的情況。共享數(shù)據(jù)的最終結(jié)果取決于最后操作的進(jìn)程。為了防止上述競(jìng)爭(zhēng)條件，并發(fā)進(jìn)程必須同步。競(jìng)爭(zhēng)條件RaceCondition臨界資源和臨界區(qū)criticalresource(臨界資源)系統(tǒng)中某些資源一次只允許一個(gè)進(jìn)程使用，稱這樣的資源為臨界資源或互斥資源或共享變量。Critical-Section(臨界區(qū))涉及到臨界資源的代碼段叫臨界區(qū)。解決臨界區(qū)問(wèn)題1. 互斥(MutualExclusion

)。假定進(jìn)程Pi在其臨界區(qū)內(nèi)執(zhí)行，其他任何進(jìn)程將被排斥在自己的臨界區(qū)之外.2. 有空讓進(jìn)(Progress)。臨界區(qū)雖沒(méi)有進(jìn)程執(zhí)行，但有些進(jìn)程需要進(jìn)入臨界區(qū)，不能無(wú)限期地延長(zhǎng)下一個(gè)要進(jìn)入臨界區(qū)進(jìn)程的等待時(shí)間.有限等待(BoundedWaiting)。在一個(gè)進(jìn)程提出進(jìn)入臨界區(qū)的請(qǐng)求和該請(qǐng)求得到答復(fù)的時(shí)間內(nèi)，其他進(jìn)程進(jìn)入臨界區(qū)前的等待時(shí)間必須是有限的.假定每個(gè)進(jìn)程都以非零的的速率執(zhí)行.沒(méi)有任何關(guān)于這n個(gè)進(jìn)程相對(duì)執(zhí)行速率的假定.同步機(jī)制應(yīng)遵循的準(zhǔn)則空閑則入：其他進(jìn)程均不處于臨界區(qū)；忙則等待：已有進(jìn)程處于其臨界區(qū)；有限等待：等待進(jìn)入臨界區(qū)的進(jìn)程不能"死等"；讓權(quán)等待：不能進(jìn)入臨界區(qū)的進(jìn)程，應(yīng)釋放CPU（如轉(zhuǎn)換到阻塞狀態(tài)）只有2個(gè)進(jìn)程,P0

和P1Pi進(jìn)程的通用結(jié)構(gòu)

do{

進(jìn)入?yún)^(qū) criticalsection

退出區(qū) remindersection }while(1);進(jìn)程可以共享一些公共變量來(lái)同步它們的行為。解決問(wèn)題的初始嘗試共享變量:intturn;

初始turn=0turn==i

Pi

能進(jìn)入臨界區(qū)j=1-i進(jìn)程Pi

do{

while(turn!=i);

臨界區(qū)

turn=j;

剩余區(qū) }while(1);滿足互斥條件，但不滿足有空讓進(jìn)算法1共享變量booleanflag[2];

初始flag[0]=flag[1]=false.flag[i]=true

Pi

準(zhǔn)備進(jìn)入臨界區(qū)進(jìn)程Pi

do{ flag[i]:=true;

while(flag[j]); criticalsection flag[i]=false;

remaindersection }while(1);滿足互斥，但不滿足有空讓進(jìn)需求。算法2合并算法1和2的共享變量.進(jìn)程Pi

do{

flag[i]:=true;

turn=j;

while(flag[j]andturn=j); criticalsection

flag[i]=false; remaindersection }while(1);滿足三個(gè)需求；解決了兩個(gè)進(jìn)程的臨界區(qū)問(wèn)題。算法3在進(jìn)入臨界區(qū)前，每個(gè)進(jìn)程接收一個(gè)號(hào)碼。具有最小號(hào)碼的進(jìn)程進(jìn)入臨界區(qū)。如果進(jìn)程Pi和Pj接收到同樣的號(hào)碼，如果i<j

，則Pi先得到服務(wù)，否則Pj先得到服務(wù)。這種號(hào)碼方案總是以遞增序列產(chǎn)生號(hào)碼；如：1,2,3,3,3,3,4,5...多進(jìn)程臨界區(qū)問(wèn)題：面包店算法定義如下符合，按字典順序(ticket#,processid#)若a<c

，(a,b)<(c,d)，或若

a=c

和b<dmax(a0,…,an-1)是數(shù)字

k,從而k

ai，對(duì)

i=0,…,n–1共享數(shù)據(jù)：

booleanchoosing[n]; intnumber[n];這些數(shù)據(jù)結(jié)構(gòu)分別被初始化為false和0

面包店算法do{

choosing[i]=true; number[i]=max(number[0],number[1],…,number[n–1])+1; choosing[i]=false;

for(j=0;j<n;j++){ while(choosing[j]); while((number[j]!=0)&&(number[j,j]<number[i,i])); } criticalsection

number[i]=0; remaindersection}while(1);面包店算法原子地檢查和修改字的內(nèi)容.

booleanTestAndSet(boolean&target){ booleanrv=target; tqrget=true; returnrv; }硬件同步共享數(shù)據(jù):

booleanlock=false;

進(jìn)程Pi

do{ while(TestAndSet(lock));

criticalsection lock=false;

remaindersection }

Test-and-Set指令實(shí)現(xiàn)互斥原子地交換兩個(gè)變量：

voidSwap(boolean&a,boolean&b){ booleantemp=a; a=b; b=temp; }硬件同步共享數(shù)據(jù)(初始化為

false):

booleanlock; booleanwaiting[n];

進(jìn)程Pi

do{ key=true; while(key==true) Swap(lock,key);

criticalsection lock=false;

remaindersection }Swap指令實(shí)現(xiàn)互斥信號(hào)量Semaphore一種不需要忙等待的同步工具.信號(hào)量S–整型變量?jī)H能通過(guò)兩個(gè)不可分割的[原子]操作訪問(wèn)

P(S):whileS0dono-op;

S--;

V(S):S++;P(S)和V(S)操作不可中斷。整型信號(hào)量的問(wèn)題：忙等去除忙等的信號(hào)量P(S){ S--; if(S<0){ addthisprocesstolist block }}V(S){ S++; if(S<=0){ removeaprocessPfromlist wakeup(P); }}思考:S值的含義是什么?作為互斥工具的信號(hào)量SemaphoreS;//初始化為1P(S);CriticalSection()//臨界區(qū)V(S);信號(hào)量的使用：S必須置一次且只能置一次初值，初值不能為負(fù)數(shù)除了初始化，只能通過(guò)執(zhí)行P、V操作來(lái)訪問(wèn)S信號(hào)量的用法死鎖和饑餓死鎖–兩個(gè)或多個(gè)進(jìn)程無(wú)限期地等待一個(gè)事件的發(fā)生，而該事件正是由其中的一個(gè)等待進(jìn)程引起的.S和Q是兩個(gè)初值為1的信號(hào)量

P0

P1

P(S); P(Q); P(Q); P(S);

V(S); V(Q); V(Q) V(S);饑餓–無(wú)限期地阻塞。進(jìn)程可能永遠(yuǎn)無(wú)法從它等待的信號(hào)量隊(duì)列中移去.兩種類型信號(hào)量計(jì)數(shù)信號(hào)量–變化范圍沒(méi)有限制的整型值.二進(jìn)制信號(hào)量–變化范圍僅限于0和1的信號(hào)量；容易實(shí)現(xiàn).可以將計(jì)數(shù)信號(hào)量S用作二進(jìn)制信號(hào)量.同步信號(hào)量和互斥信號(hào)量數(shù)據(jù)結(jié)構(gòu): binary-semaphoreS1,S2; intC:初始化:

S1=1 S2=0 C=信號(hào)量

S的初值S作為二進(jìn)制信號(hào)量的實(shí)現(xiàn)wait

操作

wait(S1); C--; if(C<0){ signal(S1); wait(S2); } signal(S1);

signal

操作

wait(S1); C++; if(C<=0) signal(S2); else signal(S1);信號(hào)量的實(shí)現(xiàn)經(jīng)典同步問(wèn)題有限緩沖區(qū)問(wèn)題讀者寫(xiě)者問(wèn)題哲學(xué)家就餐問(wèn)題生產(chǎn)者消費(fèi)者問(wèn)題CONSUMERPRODUCERempty初值為1，full初值為0單緩存生產(chǎn)者消費(fèi)者問(wèn)題解決方案P：Repeat生產(chǎn)一個(gè)產(chǎn)品；P(empty);送產(chǎn)品到緩沖區(qū)；V(full);UntilfalseC：RepeatP(full);從緩沖區(qū)中取產(chǎn)品；V(empty);消費(fèi)產(chǎn)品；Untilfalse共享數(shù)據(jù)

semaphorefull,empty,mutex;

初始化:

full=0,empty=n,mutex=1多緩沖區(qū)問(wèn)題

do{ …

produceaniteminnextp … wait(empty); wait(mutex); …

addnextptobuffer … signal(mutex); signal(full); }while(1);

生產(chǎn)者進(jìn)程

do{ wait(full) wait(mutex); …

removeanitemfrombuffertonextc … signal(mutex); signal(empty); …

consumetheiteminnextc … }while(1);消費(fèi)者進(jìn)程讀者寫(xiě)者問(wèn)題讀者寫(xiě)者問(wèn)題有兩組并發(fā)進(jìn)程:讀者和寫(xiě)者,共享一組數(shù)據(jù)區(qū),要求：允許多個(gè)讀者同時(shí)執(zhí)行讀操作；不允許讀者、寫(xiě)者同時(shí)操作；不允許多個(gè)寫(xiě)者同時(shí)操作。讀者優(yōu)先如果讀者來(lái)：1）無(wú)讀者、寫(xiě)者，新讀者可以讀。2）有寫(xiě)者等，但有其它讀者正在讀，則新讀者也可以讀。3）有寫(xiě)者寫(xiě)，新讀者等如果寫(xiě)者來(lái)：1）無(wú)讀者，新寫(xiě)者可以寫(xiě)。2）有讀者，新寫(xiě)者等待。3）有其它寫(xiě)者，新寫(xiě)者等待。讀者寫(xiě)者問(wèn)題解決方案讀者：RepeatP(mutex);readcount:=readcount+1;ifreadcount=1thenP(w);V(mutex);讀P(mutex);readcount:=readcount-1;ifreadcount=0thenV(w);V(mutex);Untilfalse寫(xiě)者：RepeatP(w);寫(xiě)V(w);Untilfalse思考第二類讀者寫(xiě)者問(wèn)題：寫(xiě)者優(yōu)先條件：1）多個(gè)讀者可以同時(shí)進(jìn)行讀2）寫(xiě)者必須互斥（只允許一個(gè)寫(xiě)者寫(xiě)，也不能讀者寫(xiě)者同時(shí)進(jìn)行）3）寫(xiě)者優(yōu)先于讀者（一旦有寫(xiě)者，則后續(xù)讀者必須等待，喚醒時(shí)優(yōu)先考慮寫(xiě)者）如何用PV操作實(shí)現(xiàn)？Shareddata SemaphorechopStick[]=newSemaphore[5];哲學(xué)家就餐問(wèn)題哲學(xué)家就餐問(wèn)題Philosopheri: while(true){ //getleftchopstick P(chopStick[i]); //getrightchopstick P(chopStick[(i+1)%5]); //eatforawhile

//returnleftchopstick V(chopStick[i]); //returnrightchopstick V(chopStick[(i+1)%5]); //thinkforawhile }哲學(xué)家就餐問(wèn)題 為防止死鎖發(fā)生可采取的措施：最多允許4個(gè)哲學(xué)家同時(shí)坐在桌子周?chē)鷥H當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí)，才允許他拿筷子。給所有哲學(xué)家編號(hào)，奇數(shù)號(hào)的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號(hào)的哲學(xué)家則反之為了避免死鎖，所以把哲學(xué)家分為三種狀態(tài)，思考，饑餓，進(jìn)食，并且一次拿到兩只筷子，否則不拿。哲學(xué)家就餐問(wèn)題state:array[0..4]of(Thinking,hungry,eating)；ph:array[0..4]ofsemaphore;mutex:semaphore;i:0..4;哲學(xué)家就餐問(wèn)題解決方案Proceduretest(i:=0…4);beginif(state[i]=hungry)And(state[(i-1)mod5]<>eating)And(state[(i+1)mod5]<>eating)

thenbeginstate[i]=eating

V(ph[i])endendProcedurephilosopher(i:0～4)BeginRepeatthinking；

state[i]:=hungry；

P(mutex);test(i);V(mutex);P(ph[i]);getleftchopstick；

getrightchopstick；

eating；

returnleftchopstick

returnrightchopstick；

UntileFalse哲學(xué)家就餐問(wèn)題解決方案思考??！以上算法存在一個(gè)問(wèn)題，請(qǐng)思考并提出解決方法。例子1.用P.V操作解決下圖之同步問(wèn)題:getcopyputfstg2.用P.V操作解決司機(jī)與售票員的問(wèn)題司機(jī)進(jìn)程：REPEAT啟動(dòng)車(chē)輛正常駕駛到站停車(chē)UNTIL…售票員進(jìn)程：REPEAT關(guān)門(mén)售票開(kāi)門(mén)UNTIL…例子P.V操作討論

1)信號(hào)量的物理含義：S>0表示有S個(gè)資源可用；S=0表示無(wú)資源可用；S<0則|S|表示S等待隊(duì)列中的進(jìn)程個(gè)數(shù)。P(S):表示申請(qǐng)一個(gè)資源;V(S)表示釋放一個(gè)資源。信號(hào)量的初值應(yīng)該大于等于02)P.V操作必須成對(duì)出現(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操作無(wú)關(guān)緊要。信號(hào)量同步的缺點(diǎn)同步操作分散：信號(hào)量機(jī)制中，同步操作分散在各個(gè)進(jìn)程中，使用不當(dāng)就可能導(dǎo)致各進(jìn)程死鎖（如P、V操作的次序錯(cuò)誤、重復(fù)或遺漏）易讀性差：要了解對(duì)于一組共享變量及信號(hào)量的操作是否正確，必須通讀整個(gè)系統(tǒng)或者并發(fā)程序；不利于修改和維護(hù)：各模塊的獨(dú)立性差，任一組變量或一段代碼的修改都可能影響全局；正確性難以保證：操作系統(tǒng)或并發(fā)程序通常很大，很難保證這樣一個(gè)復(fù)雜的系統(tǒng)沒(méi)有邏輯錯(cuò)誤；管程Monitors

管程是對(duì)提供線程安全機(jī)制的高度抽象.任一時(shí)刻在管程中只有一個(gè)線程是能運(yùn)行的.monitormonitor-name{ //variabledeclarations publicentryp1(…){ … } publicentryp2(…){ … }}條件變量conditionx,y;調(diào)用x.wait的線程將一直等待到有另一個(gè)線程調(diào)用x.signal管程示意圖帶條件變量的管程monitorDP{ enum{THINKING;HUNGRY,EATING)state[5]; conditionself[5]; voidpickup(inti){ state[i]=HUNGRY; test(i); if(state[i]!=EATING)self[i].wait; }

voidputdown(inti){ state[i]=THINKING;//testleftandrightneighbors