第4章進程同步與死鎖什么是進程同步？什么是進程互斥？答：同步是進程間的直接制約關系，這種制約主要源于進程間的合作。進程同步的主要任務就是使并發執行的各進程之間能有效地共享資源和相互合作，從而在執行時間、次序上相互制約，按照一定的協議協調執行，使程序的執行具有可再現性。進程互斥是進程間的間接制約關系，當多個進程需要使用相同的資源，而此類資源在任一時刻卻只能供一個進程使用，獲得資源的進程可以繼續執行，沒有獲得資源的進程必須等待，進程的運行具有時間次序的特征，誰先從系統獲得共享資源，誰就先運行，這種對共享資源的排它性使用所造成的進程間的間接制約關系稱為進程互斥。互斥是一種特殊的同步方式。進程執行時為什么要設置進入區和退出區？答：為了實現多個進程對臨界資源的互斥訪問，必須在臨界區前面增加一段用于檢查欲訪問的臨界資源是否正被訪問的代碼，如果未被訪問，該進程便可進入臨界區對資源進行訪問，并設置正被訪問標志，如果正被訪問，則本進程不能進入臨界區，實現這一功能的代碼成為“進入區”代碼；在退出臨界區后，必須執行“退出區”代碼，用于恢復未被訪問標志。同步機構需要遵循的基本準則是什么？請簡要說明。答：同步機制都應遵循下面的4條準則：空閑讓進。當無進程處于臨界區時，允許進程進入臨界區，并且只能在臨界區運行有限的時間。忙則等待。當有一個進程在臨界區時，其它欲進入臨界區的進程必須等待，以保證進程互斥地訪問臨界資源。有限等待。對要求訪問臨界資源的進程，應保證進程能在有限時間內進入臨界區，以免陷入“饑餓”狀態。讓權等待。當進程不能進入臨界區時，應立即放棄占用CPU，以使其它進程有機會得到CPU的使用權，以免陷入“饑餓”狀態。整型信號量是否能完全遵循同步機構的四條基本準則？為什么？答：不能。在整型信號量機制中，未遵循“讓權等待”的準則。5.在生產者-消費者問題中，若缺少了V(full)或V(empty)，對進程的執行有什么影響？答：如果缺少了V(full)，那么表明從第一個生產者進程開始就沒有對信號量full值改變，即使緩沖池存放的產品已滿了，但full的值還是0，這樣消費者進程在執行P(full)時會認為緩沖池是空的而取不到產品，那么消費者進程則會一直處于等待狀態。如果缺少了V(empty)，例如在生產者進程向n個緩沖區放滿產品后消費者進程才開始從中取產品，這時empty=0，full=n，那么每當消費者進程取走一個產品時empty并沒有被改變，直到緩沖池中的產品都取走了，empty的值也一直是0，即使目前緩沖池有n個空緩沖區，生產者進程要想再往緩沖池中投放產品會因申請不到空緩沖區而被阻塞。6.在生產者-消費者問題中，若將P(full)和P(empty)交換位置，或將V(full)或V(empty)交換位置，對進程執行有什么影響？答：對full和empty信號量的P、V操作應分別出現在合作進程中，這樣做的目的是能正確表征各進程對臨界資源的使用情況，保證正確的進程通信聯絡。7.利用信號量寫出不會出現死鎖的哲學家進餐問題的算法。答：對哲學家按順序從0到4編號，哲學家i左邊的筷子的編號為i，哲學家右邊的筷子的編號為（i+1）%5。semaphorechopstick[5]={1};//定義信號量數組chopstick[5]，由于侉子是臨街資源（互斥），故設置初值均為1。Pi(){//i號哲學家的進程do{if(i<(i+1)%5){wait(chopstick[i]);wait(chopstick[(i+1)%5]);}else{wait(chopstick[(i+1)%5]);wait(chopstick[i]);}eatsignal(chopstick[i]);signal(chopstick[(i+1)%5]);think}while(1);}8.利用AND型信號量和管程解決生產者-消費者問題。答：利用AND信號量解決生產者－消費者問題的算法描述如下：varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,...,n-1]ofitem;inout:integer:=0,0;beginparbeginproducer:duceaniteminnextp;...Swait(empty,mutex);buffer(in):=nextp;in:=(in+1)modn;Ssignal(mutex,full);untilfalse;endconsumer:beginrepeatSwait(full,mutex);nextc:=buffer(out);out:=(out+1)modn;Ssignal(mutex,empty);consumetheiteminnextc;untilfalse;endparendend利用管程機制解決生產者-消費者問題，首先需要建立一個管程ProducerConsumer，其中包含兩個過程insert(item)和consumer(item)。生產者-消費者同步問題可以用偽代碼描述如下：monitorProducerConsumer conditionfull,empty; intcount; voidinsert(intitem) { if(count==N)wait(full); insert(item); count=count+1; if(count==1)signal(empty); } intremover() { if(count==0)wait(empty); remove=remove_item; count=count-1; if(count==N-1)signal(full); } count=0;endmonitorvoidproducer(){ while(true) { item=produce_item; ProducerConsumer.insert(item); }}voidconsumer(){ while(true) { item=ProducerConsumer.remove; consume(item) }}進程的高級通信機制有哪些？請簡要說明。答：進程的高級通信機制分為三大類：共享存儲系統、消息傳遞系統和管道通信系統。共享存儲器系統：在共享存儲器系統中，相互通信的進程通過共享某些數據結構或共享存儲區實現進程之間的通信。該系統又可進一步細分為兩種方式：基于共享數據結構的通信方式和基于共享存儲區的通信方式。消息傳遞系統：消息傳遞機制可以實現不同主機間多個CPU上進程的通信。這種方式需要使用兩條原語send和receive來發送和接收格式化的消息(message)。管道通信系統：管道通信是一種以文件系統為基礎實現的適用于在進程之間實現大量數據傳送的通信方式。什么是死鎖？產生死鎖的原因和必要條件是什么？答：所謂死鎖是指在一個進程集合中的所有進程都在等待只能由該集合中的其它一個進程才能引發的事件而無限期地僵持下去的局面。產生死鎖的原因可以歸結為兩點：1）競爭資源，2）各進程之間的推進順序不當。產生死鎖的必要條件有四個：1）互斥條件，2）不剝奪條件，3）請求和保持條件，4）環路條件。死鎖的預防策略有哪些？請簡要說明。答：死鎖的預防策略有三，說明如下：摒棄請求和保持條件：為摒棄請求和保持條件，系統中需要使用靜態資源分配法，該方法規定每一個進程在開始運行前都必須一次性地申請其在整個運行過程中所需的全部資源。此時，若系統有足夠的資源，就把進程需要的全部資源一次性地分配給它；若不能全部滿足進程的資源請求，則一個資源也不分給它，即使有部分資源處于空閑狀態也不分配給該進程。這樣，當一個進程申請某個資源時，它不能占有其它任何資源，在進程運行過程中也不會再提出資源請求。這種方法破壞了請求和保持條件，從而避免死鎖的發生。摒棄不剝奪條件：要摒棄“不剝奪條件”，可以使用如下策略：進程在需要資源時才提出請求，并且進程是逐個地申請所需資源，如果一個進程已經擁有了部分資源，然后又申請另一個資源而不可得時，其現有資源必須全部釋放。在這種方法中，進程只能在獲得其原有資源和所申請的新資源時才能繼續執行。摒棄環路等待條件：為確保環路等待條件不成立，可以在系統中實行資源有序分配策略，即系統中的所有資源按類型被賦予一個唯一的編號，每個進程只能按編號的升序申請資源。某系統中有A、B、C、D四類資源，且其總數量都是8個。某時刻系統中有5個進程，判斷下列資源狀態是否安全？若進程P2申請資源(1，1，1，1)，能否為其分配？進程NeedABCDAllocationABCDP000430022P126301100P232152103P340202000P405540222答：現在對該時刻的狀態進行安全分析：由于Available向量為（3，4，4，1），所以Work向量初始化為（3，4，4，1）此時的Work小于任意的Need[i]向量，所以系統處于不安全狀態由于Request2(1,1,1,1)<Available（3,4,4,1）且Request2（1,1,1,1）<Need2（1,1,1,2）所以先試著把P2所申請的資源分配給它，Available變為（2,3,3,0）得到系統狀態如下表所示：AllocationNeedAvailableABCDABCDABCDP0002200432330P111002630P232142104P320004020P402220554然后進行安全性檢測：此時Available向量為（2,3,3,0），所以Work向量初始化為（2,3,3,0），此時的Work小于任意的Need[i]向量，所以系統處于不安全狀態，所以不可以為P2分配資源三個進程P1、P2、P3都需要5個同類資源才能正常執行直到終止，且這些進程只有在需要設備時才申請，則該系統中不會發生死鎖的最小資源數量是多少？請說明理由。答：系統中不會發生死鎖的最小資源數量是13，這樣可以保證當每一個進程都占有4個資源的時候，有一個進程可以獲得最后一個資源后被運行，運行完畢后釋放資源，于是其余進程也能順利運行完，所以不會死鎖。在解決死鎖問題的幾個方法中，哪種方法最易于實現，哪種方法使資源的利用率最高？答：預防死鎖這個方法實現簡單，效果突出；避免死鎖這種方法系統吞吐量和資源利用率較高。考慮由n個進程共享的具有m個同類資源的系統，如果對于i=1,2,3,…,n,有Need[i]>0并且所有進程的最大需求量之和小于m+n，試證明系統不會產生死鎖。答：本題中只有一種資源，不妨設Max[i]為第i個進程的資源總共需要量，Need[i]為第i個進程還需要的資源數量，Allocation[i]表示第i個進程已經分配到的資源數量，Available為系統剩余的資源數，其中i=1,2,3,…,n。假設此系統可以發生死鎖。系統剩余的資源數量為Available（Available>=0），由假設，因為系統處于死鎖狀態，所以Available個資源無法分配出去，所以每個進程的Need[i]都大于Available，即Need[i]>=Available+1所以∑Need[i]>=n*(Available+1)=n*Available+n,=1\*GB3①因為剩下的資源數是Available，所以已經分配出去的資源數為m–Available;即∑Allocation[i]=m–Available=2\*GB3②由=1\*GB3①式和=2\*GB3②式可以得到：∑Need[i]+∑Allocation[i]>=n*Available+n+m–Available=（n-1）*Available+m+n=3\*GB3③又因為n>=1，所以（n-1）>=0，又因為Available>=0，所以（n-1）*Available>=0=4\*GB3④由=3\*GB3③式和=4\*GB3④式可以得到∑Need[i]+∑Allocation[i]>=0+m+n=m+n=5\*GB3⑤根據題意知：∑Max[i]<m+n=6\*GB3⑥又因為：Max[i]=Need[i]+Allocation[i],所以∑Max[i]=∑Need[i]+∑Allocation[i]=7\*GB3⑦由=6\*GB3⑥式和=7\*GB3⑦式得：∑Need[i]+∑Allocation[i]<m+n=8\*GB3⑧由假設推出的=5\*GB3⑤式和由題意推出的=8\*GB3⑧式相矛盾，所以假設是錯誤的，即系統不會產生死鎖。某車站售票廳，在任何時刻最多可以容納20名購票者進入，當售票廳中少于20名購票者時，廳外的購票者可立即進入，否則需要在外面等待。若把一個購票者看作一個進程，請回答以下問題：①用信號量管理這些并發進程時，應該怎樣定義信號量，寫出信號量的初值以及信號量的各取值的含義。②根據所定義的信號量，寫出相應的程序來保證進程能夠正確地并發執行。③如果購票者最多為n個人，試寫出信號量取值的可能變化范圍(最大值和最小值)。答：①定義信號量S,初值為20，當s>0時，它表示可以繼續進入購票廳的人數，當s=0時表示廳內已有20人正在購票，當s<0時|s|表示正等待進入的人數。②semaphoreS=20;beginparbeginprocedure:beginrepeatwait(s);Enterandbuyticket;signal(s);untilfalse;endparendend③最大值為20，最小值為20-n在測量控制系統中的數據采集任務時，把所采集的數據送往一單緩沖區；計算任務從該單緩沖區中取出數據進行計算。試寫出利用信號量機制實現兩個任務共享單緩沖區的同步算法。答：semaphoremutex=1;semaphorefull=0;semaphoreempty=1;beginparbegincollect:beginrepeat……collectdatainnextp;wait(empty);wait(mutex);buffer:=nextp;signal(mutex);signal(full);untilfalse;endcompute:beginrepeat……wait(full);wait(mutex);nextc:=buffer;signal(mutex);signal(empty);computedatainnextc;untilfalse;endparendend桌上有一空盤，允許存放一只水果。爸爸可以向盤中放蘋果，也可以向盤中放桔子，兒子專等著吃盤中的桔子，女兒專等著吃盤中的蘋果。規定當盤空時一次只能放一只水果供吃者用，請用信號量實現爸爸、兒子和女兒3個并發進程的同步。答：本題中應設置三個信號量S、So、Sa，信號量S表示盤中是否為空，其初值為1；So表示盤中是否有桔子，其初值為0；Sa表示盤中是否有蘋果，其初值為0。同步描述如下：爸爸:P(S);兒子：P(So);女兒：P(Sa);將水果放入盤中從盤子中取出桔子從盤子中取出蘋果if(放入的是桔子)v(So)；V（S）；V（S）；elsev(Sa)；吃桔子吃蘋果；設某系統中有3個進程Get、Process和Put，共用兩個緩沖區buffer1和buffer2。假設buffer1中最多可以放11個信息，現在已經放入了兩個信息；buffer2最多可以放5個信息。Get進程負責不斷地將輸入信息送入buffer1中，Process進程負責從buffer1中取出信息進行處理，并將處理結果送到buffer2中，Put進程負責從buffer2中讀取結果并輸出。試用信號量機制實現它們的同步與互斥。答：semaphoreempty1=9;//buffer1空的數量semaphorefull1=2;//buffer1滿的數量semaphoreempty2=5;//buffer2空的數量semaphorefull2=0;//buffer2滿的數量in1,in2,out1,out2:integer:=2,0,1,0;Get(){while(1){wait(empty1)in1=(in1+1)mod11signal(full1)}}Process（）{while(1){wait(full1)out1=(out1+1)mod11signal(empty1)signal(empty2)in2=(in2+1)mod5signal(full2)}}Put(){while(1){wait(full2)out2=(out2+1)mod5signal(empty2)}}某寺廟有大、小和尚若干，另有一水缸。由小和尚挑水入缸供大和尚飲用。水缸可以容10桶水，水取自同一井。水井很窄，每次只能容一個水桶取水。水桶總數為3。每次入、取缸水僅為1桶，且不可同時進行。試給出取水、入水的同步算法。答：semaphorewell=1;//保證互斥地訪問水井的信號量semaphorevat=1;//保證互斥地訪問水缸的信號量semaphoreempty=10;//表示水缸中剩余的空間能容納的水的桶數semaphorefull=0;//表示水缸中水的桶數semaphorepail=3;//保證互斥地訪問臨界資源水桶的信號量//大和尚進程big_monk(){while(1){wait(full);wait(pail);wait(vat);usepailtogetwaterfromvatsignal(vat);signal(empty);drinkwaterinthepailsignal(pail);}}//小和尚進程little_monk(){while(1){wait(empty);\wait(pail);wait(well);usepailtogetwaterfromwellsignal(well);wait(vat);pourwatertothevatsignal(vat);signal(full);signal(pail);}}在銀行家算法中，若出現下述資源分配情況：ProcessAllocationNeedAvailableP0003200121622P110001750P213542356P303320652P400140656試問：①該狀態是否安全？②若進程P2提出請求Request(1,2,2,2)后，系統能否將資源分配給它？答:(1)該狀態是安全的,這時可以找到一個安全序列:P0、P3、P4、P1、P2設置兩個向量①工作向量work,它表示系統可提供給進程繼續運行所需的各類資源數目,在執行算法開始時,work:=Available,②finish,它表示系統是否有足夠的資源分配給進程,使其運行完