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

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

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

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

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

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

counter++;

counter--;

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

register1=counter register1=register1+1

counter=register1

語句“count--”可按如下方式來實現(xiàn)：

register2=counter

register2=register2–1

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

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

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

和P1Pi進程的通用結構

do{

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

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

初始turn=0turn==i

Pi

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

do{

while(turn!=i);

臨界區(qū)

turn=j;

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

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

Pi

準備進入臨界區(qū)進程Pi

do{ flag[i]:=true;

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

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

do{

flag[i]:=true;

turn=j;

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

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

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

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

a=c

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

k,從而k

ai，對

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

booleanchoosing[n]; intnumber[n];這些數(shù)據(jù)結構分別被初始化為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;

進程Pi

do{ while(TestAndSet(lock));

criticalsection lock=false;

remaindersection }

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

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

false):

booleanlock; booleanwaiting[n];

進程Pi

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

criticalsection lock=false;

remaindersection }Swap指令實現(xiàn)互斥信號量Semaphore一種不需要忙等待的同步工具.信號量S–整型變量僅能通過兩個不可分割的[原子]操作訪問

P(S):whileS0dono-op;

S--;

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

P0

P1

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

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

S1=1 S2=0 C=信號量

S的初值S作為二進制信號量的實現(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);信號量的實現(xiàn)經(jīng)典同步問題有限緩沖區(qū)問題讀者寫者問題哲學家就餐問題生產(chǎn)者消費者問題CONSUMERPRODUCERempty初值為1，full初值為0單緩存生產(chǎn)者消費者問題解決方案P：Repeat生產(chǎn)一個產(chǎn)品；P(empty);送產(chǎn)品到緩沖區(qū)；V(full);UntilfalseC：RepeatP(full);從緩沖區(qū)中取產(chǎn)品；V(empty);消費產(chǎn)品；Untilfalse共享數(shù)據(jù)

semaphorefull,empty,mutex;

初始化:

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

do{ …

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

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

生產(chǎn)者進程

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

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

consumetheiteminnextc … }while(1);消費者進程讀者寫者問題讀者寫者問題有兩組并發(fā)進程:讀者和寫者,共享一組數(shù)據(jù)區(qū),要求：允許多個讀者同時執(zhí)行讀操作；不允許讀者、寫者同時操作；不允許多個寫者同時操作。讀者優(yōu)先如果讀者來：1）無讀者、寫者，新讀者可以讀。2）有寫者等，但有其它讀者正在讀，則新讀者也可以讀。3）有寫者寫，新讀者等如果寫者來：1）無讀者，新寫者可以寫。2）有讀者，新寫者等待。3）有其它寫者，新寫者等待。讀者寫者問題解決方案讀者：RepeatP(mutex);readcount:=readcount+1;ifreadcount=1thenP(w);V(mutex);讀P(mutex);readcount:=readcount-1;ifreadcount=0thenV(w);V(mutex);Untilfalse寫者：RepeatP(w);寫V(w);Untilfalse思考第二類讀者寫者問題：寫者優(yōu)先條件：1）多個讀者可以同時進行讀2）寫者必須互斥（只允許一個寫者寫，也不能讀者寫者同時進行）3）寫者優(yōu)先于讀者（一旦有寫者，則后續(xù)讀者必須等待，喚醒時優(yōu)先考慮寫者）如何用PV操作實現(xiàn)？Shareddata SemaphorechopStick[]=newSemaphore[5];哲學家就餐問題哲學家就餐問題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 }哲學家就餐問題 為防止死鎖發(fā)生可采取的措施：最多允許4個哲學家同時坐在桌子周圍僅當一個哲學家左右兩邊的筷子都可用時，才允許他拿筷子。給所有哲學家編號，奇數(shù)號的哲學家必須首先拿左邊的筷子，偶數(shù)號的哲學家則反之為了避免死鎖，所以把哲學家分為三種狀態(tài)，思考，饑餓，進食，并且一次拿到兩只筷子，否則不拿。哲學家就餐問題state:array[0..4]of(Thinking,hungry,eating)；ph:array[0..4]ofsemaphore;mutex:semaphore;i:0..4;哲學家就餐問題解決方案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哲學家就餐問題解決方案思考??！以上算法存在一個問題，請思考并提出解決方法。例子1.用P.V操作解決下圖之同步問題:getcopyputfstg2.用P.V操作解決司機與售票員的問題司機進程：REPEAT啟動車輛正常駕駛到站停車UNTIL…售票員進程：REPEAT關門售票開門UNTIL…例子P.V操作討論

1)信號量的物理含義：S>0表示有S個資源可用；S=0表示無資源可用；S<0則|S|表示S等待隊列中的進程個數(shù)。P(S):表示申請一個資源;V(S)表示釋放一個資源。信號量的初值應該大于等于02)P.V操作必須成對出現(xiàn)，有一個P操作就一定有一個V操作。當為互斥操作時，它們同處于同一進程。當為同步操作時，則不在同一進程中出現(xiàn)。如果P(S1)和P(S2)兩個操作在一起，那么P操作的順序至關重要,一個同步P操作與一個互斥P操作在一起時同步P操作在互斥P操作前。而兩個V操作無關緊要。信號量同步的缺點同步操作分散：信號量機制中，同步操作分散在各個進程中，使用不當就可能導致各進程死鎖（如P、V操作的次序錯誤、重復或遺漏）易讀性差：要了解對于一組共享變量及信號量的操作是否正確，必須通讀整個系統(tǒng)或者并發(fā)程序；不利于修改和維護：各模塊的獨立性差，任一組變量或一段代碼的修改都可能影響全局；正確性難以保證：操作系統(tǒng)或并發(fā)程序通常很大，很難保證這樣一個復雜的系統(tǒng)沒有邏輯錯誤；管程Monitors

管程是對提供線程安全機制的高度抽象.任一時刻在管程中只有一個線程是能運行的.monitormonitor-name{ //variabledeclarations publicentryp1(…){ … } publicentryp2(…){ … }}條件變量conditionx,y;調用x.wait的線程將一直等待到有另一個線程調用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