進(jìn)程同步習(xí)題全課件

設(shè)有n個(gè)進(jìn)程共享一個(gè)程序段，對(duì)如下兩種情況：（1)如果每次只允許一個(gè)進(jìn)程進(jìn)入該程序段；(2)如果每次最多允許m個(gè)進(jìn)程(M＜＝n)同時(shí)進(jìn)入該程序段。試問：所采用的信號(hào)量初值是否相同?信號(hào)量值的變化范圍如何?所采用信號(hào)量的初值不相同。在情況(1)中，信號(hào)量的初值為1，信號(hào)量值的變化范圍是l，0，-1…-(n-1)。在情況(2)中，信號(hào)量的初值為M，信號(hào)量值的變化范圍是M，m-1，m-2…(m-n)。進(jìn)程同步習(xí)題設(shè)有n個(gè)進(jìn)程共享一個(gè)程序段，對(duì)如下兩種情況：所采用信號(hào)量的初【例】一個(gè)buffer,一個(gè)生產(chǎn)者，一個(gè)消費(fèi)者，生產(chǎn)者只生產(chǎn)一個(gè)東西，消費(fèi)者只進(jìn)行一次消費(fèi)，即：生產(chǎn)者只進(jìn)行一次putdata操作，消費(fèi)者只進(jìn)行一次getdata操作?！纠恳粋€(gè)buffer,一個(gè)生產(chǎn)者，一個(gè)消費(fèi)者，生產(chǎn)者只生產(chǎn)【解答】設(shè)置信號(hào)量full,表示buffer是否有數(shù)據(jù),初值為0生產(chǎn)者消費(fèi)者putdataP(full)V(full)getdata【解答】【例】一個(gè)buffer,一個(gè)生產(chǎn)者，一個(gè)消費(fèi)者，生產(chǎn)者不斷進(jìn)行putdata操作，消費(fèi)者不斷進(jìn)行g(shù)etdata操作，即生產(chǎn)者不斷生產(chǎn)，消費(fèi)者不斷消費(fèi)?！窘獯稹縝uffer為空時(shí)，才能進(jìn)行putdata操作，只有buffer有數(shù)據(jù)時(shí)，才能進(jìn)行g(shù)etdata操作信號(hào)量full:是否有數(shù)據(jù)初值為0empty:是否為空，初值為1【例】一個(gè)buffer,一個(gè)生產(chǎn)者，一個(gè)消費(fèi)者，生產(chǎn)者不斷進(jìn)生產(chǎn)者：repeatP(empty)putdataV(full)消費(fèi)者：repeatP(full)getdataV(empty)生產(chǎn)者：消費(fèi)者：【例】一個(gè)buffer,多個(gè)生產(chǎn)者，多個(gè)消費(fèi)者，多個(gè)生產(chǎn)者和消費(fèi)者都在不斷地存取buffer，即生產(chǎn)者不斷地進(jìn)行putdata操作，消費(fèi)者不斷進(jìn)行g(shù)etdata操作?！窘獯稹恐挥衎uffer為空時(shí)能進(jìn)行putdata操作，只有buffer有數(shù)據(jù)時(shí)能進(jìn)行putdata操作。不允許多個(gè)進(jìn)程同時(shí)操作buffer,即不允許多個(gè)消費(fèi)者同時(shí)進(jìn)行g(shù)etdata,不允許多個(gè)生產(chǎn)者進(jìn)行putdata操作信號(hào)量full:buffer是否有數(shù)據(jù)，初值為0empty:buffer是否為空，初值為1mutex:buffer是否可操作，初值為1【例】一個(gè)buffer,多個(gè)生產(chǎn)者，多個(gè)消費(fèi)者，多個(gè)生產(chǎn)者和生產(chǎn)者irepeatP(empty)P(mutex)putdataV(mutex)V(full)消費(fèi)者irepeatP(full)P(mutex)getdataV(mutex)V(empty)生產(chǎn)者i消費(fèi)者i【例】多個(gè)生產(chǎn)者，多個(gè)消費(fèi)者，N個(gè)buffer，多次循環(huán)存取buffer,即多個(gè)生產(chǎn)者不斷進(jìn)行putdata操作，多個(gè)消費(fèi)者不斷進(jìn)行g(shù)etdata操作【解答】只有buffer有空間時(shí)才能進(jìn)行putdata操作只有buffer有數(shù)據(jù)時(shí)才能進(jìn)行g(shù)etdata操作不允許多個(gè)消費(fèi)者和多個(gè)生產(chǎn)者同時(shí)操作信號(hào)量full:表示buffer是否有數(shù)據(jù)，初值為0empty:表示buffer是否為空，初值為nmutex:表示buffer是否可操作，初值為1【例】多個(gè)生產(chǎn)者，多個(gè)消費(fèi)者，N個(gè)buffer，多次循環(huán)存取生產(chǎn)者irepeatP(empty)P(mutex)putdataV(mutex)V(full)消費(fèi)者jrepeatP(full)P(mutex)putdataV(mutex)V(empty)生產(chǎn)者i消費(fèi)者j【改進(jìn)】putdata和getdata操作都在臨界區(qū)中，因此多個(gè)進(jìn)程對(duì)多個(gè)buffer的操作不能并行進(jìn)行的，進(jìn)程間并行操作的程度很低。實(shí)際上只要保證多個(gè)進(jìn)程同時(shí)操作不同buffer就可以實(shí)現(xiàn)對(duì)整個(gè)buffer的并行操作。getEBuffer()返回空的buffer號(hào)getEBuffer()return(pbuffer+1)modngetDBuffer()返回有數(shù)據(jù)的buffer號(hào)getDBuffer()return(pdata+1)modn【改進(jìn)】putdata和getdata操作都在臨界區(qū)中，因此semaphoremutex,empty,full=1,n,0integerpbuff,pdata=0,0生產(chǎn)者i消費(fèi)者jrepeatrepeatP(empty)P(full)P(mutex)P(mutex)in=getEBuffer()out=getDBuffer()V(mutex)V(mutex)putdata(in)getdata(out)V(full)V(empty)semaphoremutex,empty,full=1,【練習(xí)】如圖，有多個(gè)PUT操作同時(shí)向Buff1放數(shù)據(jù)，有一個(gè)MOVE操作不斷地將Buff1的數(shù)據(jù)移到Buff2,有多個(gè)GET操作不斷地從Buff2中將數(shù)據(jù)取走。Buff1的容量是m,Buff2的容量是n,PUT,MOVE,GET每次操作一個(gè)數(shù)據(jù)，在操作的過程中要保證數(shù)據(jù)不丟失。試用P,V原語協(xié)調(diào)PUT,MOVE操作，并說明每個(gè)信號(hào)量的含義和初值?！揪毩?xí)】如圖，有多個(gè)PUT操作同時(shí)向Buff1放數(shù)據(jù)，有一個(gè)Buff1Buff2MOVEPUTGETBuff1Buff2MOVEPUTGET【解答】三類進(jìn)程：多個(gè)PUT類進(jìn)程，一個(gè)MOVE類進(jìn)程，多個(gè)GET類進(jìn)程操作規(guī)則1只有buff1有空間才能進(jìn)行PUT操作2只有buff1有數(shù)據(jù)，buff2有空間才能進(jìn)行MOVE操作3只有buff2有數(shù)據(jù)才能進(jìn)行GET操作4不允許多個(gè)進(jìn)程同時(shí)操作buff15不允許多個(gè)進(jìn)程同時(shí)操作buff2【解答】三類進(jìn)程：多個(gè)PUT類進(jìn)程，一個(gè)MOVE類進(jìn)程，多個(gè)操作流程<PUT類進(jìn)程>repeat判斷buff1是否有空間，沒有則等待是否可操作buff1PUT設(shè)置buff1可操作標(biāo)志設(shè)置buff1有數(shù)據(jù)的標(biāo)志untilfalse操作流程<MOVE類進(jìn)程>repeat判斷buff1是否有數(shù)據(jù)，沒有則等待判斷buff2是否有空間，沒有則等待是否可操作buff1是否可操作buff2MOVE設(shè)置buff1可操作標(biāo)志設(shè)置buff2可操作標(biāo)志設(shè)置buff1有空間標(biāo)志設(shè)置buff2有空間標(biāo)志<MOVE類進(jìn)程><GET類進(jìn)程>repeat判斷buff2是否有數(shù)據(jù)，沒有則等待是否可操作buff2GET設(shè)置buff1可操作標(biāo)志設(shè)置buff1有空間標(biāo)志<GET類進(jìn)程>4信號(hào)量設(shè)置6個(gè)信號(hào)量full1:buff1是否有數(shù)據(jù)，初值為0empty1:buff1有空間，初值為mmutex1:buff1是否可操作，初值為1full2:buff2是否有數(shù)據(jù)，初值為0empty2:buff2有空間，初值為nmutex2:buff2是否可操作，初值為14信號(hào)量5PV操作實(shí)現(xiàn)<PUT類進(jìn)程>repeatp(empty1);//判斷buff1是否有空間，沒有則等待p(mutex1);//是否可操作buff1PUT;v(mutex1);//設(shè)置buff1可操作標(biāo)志v(full);//設(shè)置buff1有數(shù)據(jù)標(biāo)志5PV操作實(shí)現(xiàn)<MOVE類進(jìn)程>repeatP(full1）；判斷buff1是否有數(shù)據(jù)，沒有則等待P(empty2);//判斷buff2是否有空間，沒有則等待P(mutex1);//是否可操作buff1P(mutex2);//是否可操作buff2MOVE;V(mutex1);//設(shè)置buff1可操作標(biāo)志V(mutex2);//設(shè)置buff2可操作標(biāo)志V(empty1);//設(shè)置buff1有空間標(biāo)志V(full2);//設(shè)置buff2有數(shù)據(jù)標(biāo)志<MOVE類進(jìn)程><GET類進(jìn)程>repeatP(empty2);//判斷buff2是否有空間，沒有則等待P(mutex2);//是否可操作buff2GETV(mutex2);//設(shè)置buff2可操作標(biāo)記V(full2);//設(shè)置buff2有數(shù)據(jù)標(biāo)記<GET類進(jìn)程>【例】現(xiàn)有4個(gè)進(jìn)程R1，R2，W1，W2。它們共享可以存放一個(gè)數(shù)據(jù)的緩沖器B。進(jìn)程R1每次把磁盤上讀出的一個(gè)數(shù)據(jù)存到緩沖器B中，供進(jìn)程W1打印輸出；進(jìn)程R2每次從鍵盤上讀一個(gè)數(shù)據(jù)存放到緩沖器B，供W2打印輸出。當(dāng)一個(gè)進(jìn)程把數(shù)據(jù)存放到緩沖器后，在該數(shù)據(jù)還沒有打印輸出之前不準(zhǔn)任何進(jìn)程再想緩沖器中存數(shù)據(jù)。當(dāng)一個(gè)進(jìn)程已把緩沖器中的數(shù)據(jù)打印輸出后，在緩沖器中還沒有存如新數(shù)據(jù)之前不準(zhǔn)任何進(jìn)程再從緩沖器中取數(shù)打印。問怎樣用PV操作使這4個(gè)進(jìn)程并發(fā)執(zhí)行時(shí)能相互協(xié)作地工作？【例】現(xiàn)有4個(gè)進(jìn)程R1，R2，W1，W2。它們共享可以存放一R1R2W1W2R1R2W1W2【解答】4個(gè)進(jìn)程互斥，R1，W1同步，R2，W2同步mutex：表示能否把數(shù)據(jù)存如緩沖器，初始化時(shí)緩沖器為空，故初值為1S1：進(jìn)程R1是否已向緩沖器存入一個(gè)數(shù)據(jù)，初值為0S2：進(jìn)程R2是否已向緩沖器存入一個(gè)數(shù)據(jù)，初值為0【解答】4個(gè)進(jìn)程互斥，R1，W1同步，R2，W2同步beginmutex,s1,s2:semaphore;s:=1;s2:=0;s2:=0;cobeginprocessR1beginL1:從磁盤上讀數(shù)據(jù)送x1;P(mutex);B:=x1;V(s1);gotoL1end;processW1beginL3:P(s1);y:=B;V(mutex);打印ygotoL3end;begin

processR2beginL2:從鍵盤上讀數(shù)據(jù)送x2;P(mutex);B:=x2;V(s2);gotoL2end;processW2beginL4:P(s2);z:=B;V(mutex);打印z;gotoL4end;processW2【例】假定有3個(gè)進(jìn)程R，W1，W2共享一個(gè)緩沖器，而B中每次只能存放一個(gè)數(shù)，當(dāng)緩沖器中無數(shù)時(shí)，進(jìn)程R可將M輸入設(shè)備上讀入的數(shù)存放到緩存器B中，若存放到緩存器中的是奇數(shù)，則允許進(jìn)程W1將其取出打??；若存放到緩沖器中的是偶數(shù)，則允許進(jìn)程W2將取出打印。同時(shí)規(guī)定：進(jìn)程R必須等緩沖器中的數(shù)被取出打印后才能再存放一個(gè)數(shù)；進(jìn)程W1或W2對(duì)每次存入緩沖器中的數(shù)只能打印一次；W1和W2都不能從空的緩沖器中取數(shù)。寫出這3個(gè)并發(fā)進(jìn)程能正確工作的程序?！纠考俣ㄓ?個(gè)進(jìn)程R，W1，W2共享一個(gè)緩沖器，而B中每次【分析】把進(jìn)程R看作是生產(chǎn)者，把進(jìn)程W1和W2看作是消費(fèi)者?，F(xiàn)在有一個(gè)生產(chǎn)者（進(jìn)程R)能生產(chǎn)不同的產(chǎn)品（讀入奇數(shù)或偶數(shù)），把生產(chǎn)的產(chǎn)品存放在緩沖器B中，供不同的消費(fèi)者（進(jìn)程W1和進(jìn)程W2）取用?？梢钥闯?，當(dāng)進(jìn)程R讀入的是整數(shù)，則要把有奇數(shù)的消息發(fā)送給進(jìn)程W1；當(dāng)進(jìn)程R讀入的是偶數(shù)，則要把有偶數(shù)的消息發(fā)送給W2，在進(jìn)程W1或進(jìn)程W2從緩沖器中取出數(shù)后，應(yīng)把緩沖器中又可有一個(gè)數(shù)的消息告訴進(jìn)程R，于是，可以定義如下3個(gè)信號(hào)量：S表示是否可以把數(shù)存入緩沖器，由于緩沖器中每次只能放一個(gè)數(shù)，所以其初值取為”1“SO：表示緩沖器中是否有奇數(shù)，初值為”0“，表示無奇數(shù)SE：表示緩沖器是否偶數(shù)，初值為0，表示無偶數(shù)【分析】把進(jìn)程R看作是生產(chǎn)者，把進(jìn)程W1和W2看作是消費(fèi)者?！窘獯稹縤ntegerB;semaphoreS,SO,SESO=0;SE=0:

integerxL1:從輸入設(shè)備讀入一個(gè)數(shù)X=讀入的數(shù)P(S);B=Xif(B=偶數(shù)）V(SO)elseV(SE)gotoL1【解答】進(jìn)程同步習(xí)題全課件【例】設(shè)有一個(gè)具有N個(gè)信息元素的環(huán)形緩沖區(qū)，A進(jìn)程順序地把信息寫入緩沖區(qū)，B進(jìn)程依次從緩沖區(qū)讀出信息?；卮鹣铝袉栴}：1敘述A，B兩進(jìn)程的相互制約關(guān)系2判別下列用PV操作表示的同步算法是否正確？如不正確，試說明理由，并修改成正確的算法。設(shè)置信號(hào)量初值:S1＝0，S2＝N;設(shè)置變量初值：in=out=0;【例】設(shè)有一個(gè)具有N個(gè)信息元素的環(huán)形緩沖區(qū)，A進(jìn)程順序地把信【例】進(jìn)程P1使用緩沖區(qū)buffer向進(jìn)程P2,P3,P4發(fā)送消息，要求每當(dāng)P1向buffer中發(fā)消息時(shí)，只有當(dāng)P2,P3,P4進(jìn)程都讀取這條消息后才可再向buffer中發(fā)送消息。利用PV原語描述進(jìn)程的動(dòng)作序列P1bufferP2P3P4【例】進(jìn)程P1使用緩沖區(qū)buffer向進(jìn)程P2,P3,P4發(fā)【解答】設(shè)置信號(hào)量初值S1=S2=S3=0,S=3進(jìn)程P1進(jìn)程P2進(jìn)程P3進(jìn)程P4P(S)P(S1)P(S2)P(S3)P(S)讀消息讀消息讀消息P(S)V(S)V(S)V(S)發(fā)送消息到BufferV(S1)V(S2)V(S3)【解答】設(shè)置信號(hào)量初值S1=S2=S3=0,S=3【例】設(shè)A，B為兩個(gè)并發(fā)進(jìn)程，它們共享一個(gè)臨界區(qū)，其執(zhí)行臨界區(qū)的算法框圖如下。試判斷該算法是否有錯(cuò)？請(qǐng)說明理由。如果有錯(cuò)，請(qǐng)改正。S1，S2的初值為0，CSA,CSB為臨界區(qū)。CSAV(S1)P(S2)A進(jìn)程P(S1)CSBV(S2)B進(jìn)程【例】設(shè)A，B為兩個(gè)并發(fā)進(jìn)程，它們共享一個(gè)臨界區(qū)，其執(zhí)行臨界【分析】系統(tǒng)啟動(dòng)時(shí)，S1,S2為0，則B執(zhí)行P(S1)被阻塞，而A進(jìn)程可直接訪問臨界資源。故A，B兩個(gè)并發(fā)進(jìn)程不可能同時(shí)操作臨界資源，該算法是可以保證互斥的。按題目要求，兩個(gè)進(jìn)程對(duì)臨界資源的操作是沒有先后順序的，但是，在上面的實(shí)現(xiàn)中，只有A進(jìn)程先操作完資源后，B資源才能操作?！痉治觥肯到y(tǒng)啟動(dòng)時(shí)，S1,S2為0，則B執(zhí)行P(S1)被阻塞【解答】該算法錯(cuò)誤若A進(jìn)程用不要求訪問臨界資源，則不會(huì)折行V(S1),意味著B進(jìn)程的申請(qǐng)永遠(yuǎn)得不到操作臨界資源的機(jī)會(huì)；同理，若B不要求訪問臨界資源，則不會(huì)執(zhí)行V(S2),意味著進(jìn)程A下次也得不到操作臨界資源的機(jī)會(huì)。所以，問題在于本應(yīng)該互斥控制而使用的卻是同步控制。實(shí)現(xiàn)改正：【解答】該算法錯(cuò)誤信號(hào)量mutex=1A進(jìn)程B進(jìn)程repeatrepeatP(mutex);P(mutex);CSA;CSB;V(mutex);V(mutex);信號(hào)量mutex=1【例】當(dāng)進(jìn)程X和進(jìn)程Y共享某個(gè)資源r,進(jìn)程并發(fā)執(zhí)行時(shí)的程序如下：semaphore=1ProcessXProcessYL1:P(S)L2:P(S)使用資源r使用資源rV(S)V(S)gotoL1gotoL2【例】當(dāng)進(jìn)程X和進(jìn)程Y共享某個(gè)資源r,進(jìn)程并發(fā)執(zhí)行時(shí)的程序如請(qǐng)回答：1兩個(gè)進(jìn)程并發(fā)執(zhí)行時(shí)，能否保證互斥使用資源？為什么？2若要使兩個(gè)進(jìn)程交替使用資源，仍使用PV操作來進(jìn)行管理，寫出應(yīng)定義的信號(hào)量機(jī)器初值3修改上述程序，使兩個(gè)進(jìn)程能交替使用資源r請(qǐng)回答：【解答】1能保證互斥使用資源。因?yàn)樵趦蓚€(gè)進(jìn)程中，“使用資源r”都是作為臨界區(qū)，由P(S)和V(S)操作保證互斥執(zhí)行，S的初值定義為1，符合要求。2要使兩個(gè)進(jìn)程交替使用資源，僅僅保證互斥使用是不夠的，必須要兩個(gè)進(jìn)程相互等待互相通知。為此，必須定義新的信號(hào)量。定義兩個(gè)私有信號(hào)量S1和S2。假定進(jìn)程X先使用資源，那么進(jìn)程X的私有信號(hào)量S1的初值定義為1，進(jìn)程Y的私有信號(hào)量S2的初值為0.輪流使用可以保證互斥，因此信號(hào)量S可以不要?！窘獯稹?兩個(gè)進(jìn)程可以改為semaphoreS1=1semaphoreS2=0ProcessXProcessYL1:P(s1)L2:P(S2)使用資源r使用資源rV(S2)V(S1)gotoL1gotoL23兩個(gè)進(jìn)程可以改為【例】桌上有一空盤，只允許存放一個(gè)水果。爸爸可向盤中放蘋果，也可向盤中放橘子。兒子專等吃盤中的橘子，女兒專等吃盤中的蘋果。規(guī)定當(dāng)盤中空時(shí)一次只能放一只水果供吃者取用，請(qǐng)用PV原語實(shí)現(xiàn)爸爸，兒子，女兒三個(gè)并發(fā)進(jìn)程的同步【例】桌上有一空盤，只允許存放一個(gè)水果。爸爸可向盤中放蘋果，【解答】信號(hào)量mutex:盤子是否為空信號(hào)量So:盤中是否有橘子信號(hào)量Sa:盤中是否有蘋果Sempahoremutex=1,So=0,Sa=0【解答】fatherP(mutex);將水果放入盤中if(放入的是橘子)V(So)elseV(Sa)兒子P(So);從盤中取橘子V(mutex)吃橘子女兒P(Sa);從盤中取蘋果V(mutex)吃蘋果father兒子女兒讀者－寫者介紹讀者寫者（readerwriter)，共享文件要求：1允許多個(gè)讀者同時(shí)對(duì)文件執(zhí)行讀操作2只允許一個(gè)寫者對(duì)文件執(zhí)行寫操作3任何寫者在完成寫操作前不允許其他讀者或?qū)懻吖ぷ?寫者在執(zhí)行寫操作前，應(yīng)讓已有的寫者和讀者全部退出讀者－寫者介紹讀者寫者（readerwriter)，共享文單純使用信號(hào)量不能解決問題，引入計(jì)數(shù)器readcount對(duì)讀進(jìn)程計(jì)算，mutex是用于對(duì)計(jì)數(shù)器readcount操作的互斥信號(hào)量，writeblock表示是否允許寫的信號(hào)量單純使用信號(hào)量不能解決問題，引入計(jì)數(shù)器readcount對(duì)讀intreadcount=0semaphorewriteblock,mutex;writeblock=1;mutex=1intreadcount=0讀者iP(mutex)readcount++if(readcount==1)P(writeblock)V(mutex)讀文件P(mutex);readcount—if(readcount==0)V(writeblock)V(mutex)寫者jP(writeblock)寫文件V(writeblock)讀者i寫者j進(jìn)程同步習(xí)題一條小河上有一座獨(dú)木橋，規(guī)定每次只允許一人過橋。如果把每個(gè)過橋這看作一個(gè)進(jìn)程，為保證安全，請(qǐng)用信號(hào)量操作實(shí)現(xiàn)正確管理。進(jìn)程同步習(xí)題一條小河上有一座獨(dú)木橋，規(guī)定每次只允許一人過橋。進(jìn)程同步習(xí)題begins:semaphore;s：=1;cobeginbeginwait(s);過橋；signal(s)；end Coend end 進(jìn)程同步習(xí)題begin練習(xí)a,b兩點(diǎn)間是一段東西向的單行車道，現(xiàn)要設(shè)計(jì)一個(gè)自動(dòng)管理系統(tǒng)，管理規(guī)則如下：當(dāng)ab間有車輛在行駛時(shí)同方向的車可以同時(shí)駛?cè)隺b段，但另一方向的車必須在ab段外等待；當(dāng)ab之間無車時(shí)，到達(dá)a（或b）的車輛可以進(jìn)入ab段，但不能從a，b點(diǎn)同時(shí)駛?cè)?；?dāng)某方向在ab段行駛的車輛使出了ab段且無車輛進(jìn)入ab段時(shí)，應(yīng)讓另一方向等待的車輛進(jìn)入ab段行駛。請(qǐng)用wait,signal工具對(duì)ab段實(shí)現(xiàn)正確管理。練習(xí)a,b兩點(diǎn)間是一段東西向的單行車道，現(xiàn)要設(shè)計(jì)一個(gè)自動(dòng)管答案：Semaphores,mutexab,mutexbaPab：Wait(mutexab)Countab++Ifcountab=1thenwait(s);Signal(mutexab)

…..wait(mutexab)countab--;ifcountab=0thensignal(s)signal(mutexab);答案：Semaphores,mutexab,mutexb答案：Pba:wait(mutexba)countba=countba+1;Ifcountba=1thenwait(s)signal(mutexba)enter; ……wait(mutexba)countba--;ifcountba=0thensignal(s) signal(mutexba);答案：Pba:桌子上有一只盤子，最多可容納兩個(gè)水果，每次只能放入或取出一個(gè)水果。爸爸專向盤子中放蘋果，媽媽專向盤子中放橘子，兩個(gè)兒子專等吃盤子中的橘子，兩個(gè)女兒專等吃盤子中的蘋果。請(qǐng)用信號(hào)量操作來實(shí)現(xiàn)爸爸、媽媽、兒子、女兒之間的同步與互斥關(guān)系。桌子上有一只盤子，最多可容納兩個(gè)水果，每次只能放入或取出一個(gè)ParbeginFather:beginL1:p(empty);p(mutex);放蘋果；v(mutex);v(apple);gotol1;end;Mather:beginL2:p(empty)；p(mutex);放橘子；v(mutex);v(orange);gotol2;end;Daughter:beginL3:p(apple);p(mutex);取蘋果；v(mutex);v(empty);gotol3;end;ParbeginMather:beginDaughter:L4:p(orange);p(mutex);取橘子；v(mutex);v(empty);Gotol4;end;L4:p(orange);桌上有一個(gè)空的水果盤，盤中一次只能放一個(gè)水果，服務(wù)員、男顧客和女顧客共用這個(gè)盤子。服務(wù)員向盤中放草莓和香蕉，男顧客專等吃盤中的草莓，女顧客專等吃盤中的香蕉。規(guī)定每次當(dāng)盤子空時(shí)只能放一個(gè)水果供顧客食用。請(qǐng)用信號(hào)量機(jī)制實(shí)現(xiàn)服務(wù)員、男顧客和女顧客三個(gè)進(jìn)程的同步。桌上有一個(gè)空的水果盤，盤中一次只能放一個(gè)水果，服務(wù)員、男顧客題解：盤子是三個(gè)人的公有信號(hào)量，設(shè)為mutex,初值為1，服務(wù)員的私有信號(hào)量設(shè)為empty初值為1，男顧客的私有信號(hào)量為ba，初值為0，女顧客的私有信號(hào)量為cm，初值為0。waiter:beginL1:p(empty);p(mutex);放香蕉或草莓；v(mutex);如果放香蕉則v(ba);否則v(cm);gotoL1;end;Woman:beginL3:p(cm);p(mutex);取草莓；v(mutex);v(empty);gotoL2;end；Man:beginL2:p(ba);p(mutex);取香蕉；v(mutex);v(empty);gotoL2;end;題解：盤子是三個(gè)人的公有信號(hào)量，設(shè)為mutex,初值為1，服汽車司機(jī)與售票員之間必須協(xié)同工作，一方面只有售票員把車門關(guān)好了司機(jī)才能開車，因此，售票員關(guān)好車門應(yīng)通知司機(jī)開車。另一方面，只有當(dāng)汽車已經(jīng)停下，售票員才能開門上下客，故司機(jī)停車后應(yīng)通知售票員，汽車當(dāng)前正在始發(fā)站停車上客，試設(shè)必要的信號(hào)燈及賦初值，寫出他們的同步過程。汽車司機(jī)與售票員之間必須協(xié)同工作，一方面只有售票員把車門關(guān)好解答：可以用兩個(gè)信號(hào)量s1、s2，分別表示可以開門和可以開車，其初始值都為0，用PV操作實(shí)現(xiàn)為：司機(jī)：售票員：L0:正常行車L1:售票到站停車P(S1)V(S1)開車門P(S2)關(guān)車門啟動(dòng)開車V(S2)gotoL0gotoL1解答：可以用兩個(gè)信號(hào)量s1、s2，分別表示可以開門和可以開車和尚挑水問題：寺廟里有多個(gè)小、老和尚，一水缸。小和尚取水，老和尚飲水。水缸容積10桶水，水取自同一水井，水井每次只容一個(gè)桶取水，桶總數(shù)3個(gè)，每次入、取水缸水僅為一桶。試用P、V操作描述和尚取水、飲水的互斥與同步過程。mutex1=mutex2=1;分別代表水井和水缸empty=10;水缸的入水量full=0;水缸的取水量count=3;水桶個(gè)數(shù)和尚挑水問題：寺廟里有多個(gè)小、老和尚，一水缸。小和尚取水，老打水：begin p(empty) p(count) p(mutex1)從水井打水； v(mutex1)p(mutex2)往缸中放水v(mutex2) v(full) v(count) end取水：begin p(full) p(count) p(mutex2)從水缸取水 v(mutex2) v(count) v(empty)end打水：begin取水：begin

哲學(xué)家進(jìn)餐問題設(shè)有5個(gè)哲學(xué)家，共享一張放有五把椅子的桌子，每人分得一把椅子。但是，桌子上總共只有5支筷子，在每人兩邊分開各放一支。哲學(xué)家們?cè)诙亲羽囸I時(shí)才試圖分兩次從兩邊拾起筷子就餐。條件：(1)只有拿到兩支筷子時(shí)，哲學(xué)家才能吃飯。(2)如果筷子已在他人手上，則該哲學(xué)家必須等待到他人吃完之后才能拿到筷子。(3)任一哲學(xué)家在自己未拿到兩支筷子吃飯之前，決不放下自己手中的筷子。試:哲學(xué)家進(jìn)餐問題(1)描述一個(gè)保證不會(huì)出現(xiàn)兩個(gè)鄰座同時(shí)要求吃飯的通信算法。(2)描述一個(gè)既沒有兩鄰座同時(shí)吃飯，又沒有人餓死（永遠(yuǎn)拿不到筷子）的算法。(3)在什么情況下，5個(gè)哲學(xué)家全部吃不上飯？(1)描述一個(gè)保證不會(huì)出現(xiàn)兩個(gè)鄰座同時(shí)要求吃飯的通信算法。1.begin2.begin3.begin4.begin5.beginP(s1)；p(s2)；p(s3)；p(s4)；p(s5)；P(s2)；p(s3)；p(s4)；p(s5)；p(s1)；吃飯；吃飯；吃飯；吃飯；吃飯；V(s1)；v(s2)；v(s3)；v(s4)；v(s1)；V(s2)；v(s3)；v(s4)；v(s5)；v(s5)；Endendendendend1.begin2.begin3Pi:RepeatThinkforwhilep(mutex);p(s[i]);p(s[(i+1)mod5]);v(mutex);eatforwhile;v(s[i])v(s[(i+1)mod5]);untilfalsePi:Repeat利用AND型信號(hào)量機(jī)制實(shí)現(xiàn):semaphorechopstick[5]={1，1，1，1，1};

while(true)

{

think();

Swait(chopstick[(I+1)]%5,chopstick[I]);

eat();

Ssignal(chopstick[(I+1)]%5,chopstick[I]);

}

利用AND型信號(hào)量機(jī)制實(shí)現(xiàn):限制人數(shù)

semaphorechopstick[5]={1，1，1，1，1};

semaphoremutex=4;

{

Repeatthink();

wait(mutex);//請(qǐng)求進(jìn)餐

wait(chopstick[i]);//請(qǐng)求左手邊的筷子

wait(chopstick[(i+1)%5]);//請(qǐng)求右手邊的筷子

eat();

signal(chopstick[(i+1)%5]);//釋放右手邊的筷子

signal(chopstick[i]);//釋放左手邊的筷子

signal(mutex);//釋放信號(hào)量mutexuntilfalse}

限制人數(shù)

semaphorechopstick[5]={1原理：規(guī)定奇數(shù)號(hào)的哲學(xué)家先拿起他左邊的筷子,然后再去拿他右邊的筷子;而偶數(shù)號(hào)的哲學(xué)家則相反.按此規(guī)定,將是1,2號(hào)哲學(xué)家競(jìng)爭(zhēng)1號(hào)筷子,3,4號(hào)哲學(xué)家競(jìng)爭(zhēng)3號(hào)筷子.即五個(gè)哲學(xué)家都競(jìng)爭(zhēng)奇數(shù)號(hào)筷子,獲得后,再去競(jìng)爭(zhēng)偶數(shù)號(hào)筷子,最后總會(huì)有一個(gè)哲學(xué)家能獲得兩支筷子而進(jìn)餐。而申請(qǐng)不到的哲學(xué)家進(jìn)入阻塞等待隊(duì)列，根FIFO原則，則先申請(qǐng)的哲學(xué)家會(huì)較先可以吃飯，因此不會(huì)出現(xiàn)餓死的哲學(xué)家。

原理：規(guī)定奇數(shù)號(hào)的哲學(xué)家先拿起他左邊的筷子,然后再去拿他右邊semaphorechopstick[5]={1，1，1，1，1};

voidphilosopher(inti)

{

while(true)

{

think();

if(i%2==0)//偶數(shù)哲學(xué)家，先右后左。

{

wait(chopstick[i+1]mod5);

wait(chopstick[i]);

eat();

signal(chopstick[i+1]mod5);

signal(chopstick[i]);

}

Else//奇數(shù)哲學(xué)家，先左后右。

{

wait(chopstick[i]);

wait(chopstick[i+1]mod5);

eat();

signal(chopstick[i]);

signal(chopstick[i+1]mod5);

}

}semaphorechopstick[5]={1，1，1，（經(jīng)典理發(fā)師問題）

假設(shè)后街有家理發(fā)店，店里有一個(gè)理發(fā)師、一把理發(fā)椅和n把等候理發(fā)的顧客椅子。

（1）.如果沒有顧客則理發(fā)師便在理發(fā)椅上看報(bào)紙；

（2）.當(dāng)有一個(gè)顧客到達(dá)時(shí)，首先查看理發(fā)師在干什么，如果在看報(bào)紙則告訴理發(fā)師理發(fā)，然后坐到理發(fā)椅上開始理發(fā)；如果理發(fā)師正在理發(fā)，則查看是否有空的椅子可坐，如果有，他就坐下等待，如果沒有，則離開；

（3）.理發(fā)師為一位顧客理完發(fā)后，查看是否有人等待，如有則喚醒一位為其理發(fā)，如沒有則在理發(fā)椅上看報(bào)紙；

（4）.顧客不分優(yōu)先級(jí)

（經(jīng)典理發(fā)師問題）

假設(shè)后街有家理發(fā)店，店里有一個(gè)理發(fā)師、一有一間酒吧里有3個(gè)音樂愛好者隊(duì)列，第一隊(duì)的音樂愛好者只有隨身聽，第二隊(duì)的音樂愛好者只有音樂磁帶，第三隊(duì)的音樂愛好者只有電池。然而，要聽音樂就必須隨身聽、音樂磁帶和電池三種物品俱全。酒吧老板一次出售這三種物品中的任意兩種。當(dāng)一名音樂愛好者得到這三種物品并聽完一首樂曲后，酒吧老板才能再一次出售這三種物品中的任意兩種，于是第2名音樂愛好者得到這三種物品，并開始聽樂曲。全部買賣就這樣進(jìn)行下去。試用信號(hào)量實(shí)現(xiàn)它們之間的同步關(guān)系。有一間酒吧里有3個(gè)音樂愛好者隊(duì)列，第一隊(duì)的音樂愛好者只有隨身

進(jìn)程同步算法習(xí)題課進(jìn)程同步算法習(xí)題課【例題1】司機(jī)進(jìn)程：while(1){啟動(dòng)車輛正常駕駛到站停車}…售票員進(jìn)程：while(1){關(guān)門售票開門}…用wait、signal操作解決司機(jī)與售票員的問題【例題1】司機(jī)進(jìn)程：售票員進(jìn)程：用wait、signal操作分析：為保證車輛行駛安全，售票員必須關(guān)好車門，然后通知司機(jī)啟動(dòng)車輛，在行駛過程中售票員不能打開車門，待車到站停穩(wěn)后，司機(jī)通知售票員才能打開車門，如此不斷重復(fù)。為此，須設(shè)置兩個(gè)信號(hào)量S1，S2用來控制司機(jī)和售票員的行為，初值都為0。分析：解:

算法如下：司機(jī)進(jìn)程：while(1){

wait(S1)啟動(dòng)車輛正常駕駛

到站停車

signal(S2)}…售票員進(jìn)程：while(1){關(guān)門

signal(S1)售票

wait(S2)開門}…解:

算法如下：司機(jī)進(jìn)程：售票員進(jìn)程：【例題2】1.用wait、signal操作解決下圖之同步問題提示：分別考慮對(duì)緩沖區(qū)S和T的同步，再合并考慮getcopyputst【例題2】1.用wait、signal操作解決下圖之同步問題解:設(shè)置四個(gè)信號(hào)量Sin=1，Sout=0，Tin=1，Tout=0；get：while（1）{

wait(Sin）;將數(shù)放入S;

signal

(Sout);}copy：while（1）{

wait

(Sout）;

wait

(Tin）;將數(shù)從S取出放入T;

signal

(Tout);

signal

(Sin);}put：while（1）{

wait

(Tout）;將數(shù)從T取走;

signal(Tin);}解:設(shè)置四個(gè)信號(hào)量Sin=1，Sout=0，Tin=1，To思考題：如果S和T是由多個(gè)緩沖區(qū)組成的緩沖池，上述算法將如何修改？思考題：【例題3】桌上有一空盤，最多允許存放一只水果。爸爸可向盤中放一個(gè)蘋果或放一個(gè)桔子，兒子專等吃盤中的桔子，女兒專等吃蘋果。 試用wait、signal操作實(shí)現(xiàn)爸爸、兒子、女兒三個(gè)并發(fā)進(jìn)程的同步。【例題3】桌上有一空盤，最多允許存放一

分析：設(shè)置一個(gè)信號(hào)量S表示空盤子數(shù)，一個(gè)信號(hào)量So表示盤中桔子數(shù)，一個(gè)信號(hào)量Sa表示盤中蘋果數(shù)，初值分別為1，0，0。 分析：設(shè)置一個(gè)信號(hào)量S表示空盤子數(shù)，一個(gè)信號(hào)量So表示解:算法如下：Father(){while(1){

wait(S);將水果放入盤中;if(是桔子)signal(So);elsesignal(Sa);}}Son(){while(1){wait(So)取桔子

signal(S);吃桔子;}}Daughter(){while(1){wait(Sa)取蘋果

signal(S);吃蘋果;}}解:算法如下：Father()Son()Daughter(【例題4】有一個(gè)倉庫，可以存放A和B兩種產(chǎn)品，但要求：（1）

每次只能存入一種產(chǎn)品（A或B）（2）

－N＜A產(chǎn)品數(shù)量－B產(chǎn)品數(shù)量＜M。其中，N和M是正整數(shù)。試用wait、signal操作描述產(chǎn)品A與B的入庫過程?！纠}4】有一個(gè)倉庫，可以存放A和B兩種產(chǎn)品，但要求：解:分析：設(shè)兩個(gè)同步信號(hào)量Sa、Sb，其中：Sa表示允許A產(chǎn)品比B產(chǎn)品多入庫的數(shù)量，初值為M-1。Sb表示允許B產(chǎn)品比A產(chǎn)品多入庫的數(shù)量，初值為N-1。設(shè)互斥信號(hào)量mutex，初值為1。解:分析：設(shè)兩個(gè)同步信號(hào)量Sa、Sb，其中：

B產(chǎn)品入庫進(jìn)程：j=0;while(1){

wait(Sb);wait(mutex);B產(chǎn)品入庫

signal(mutex);signal(Sa);消費(fèi)產(chǎn)品;};A產(chǎn)品入庫進(jìn)程：

i=0;

while(1){

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

wait(Sa);

wait(mutex);A產(chǎn)品入庫

signal(mutex);

signal(Sb);

};算法如下：B產(chǎn)品入庫進(jìn)程：A產(chǎn)品入庫進(jìn)程：

i=0;

while例題5

進(jìn)程A1、A2，…An1通過m個(gè)緩沖區(qū)向進(jìn)程B1、B2、…Bn2不斷發(fā)送消息。發(fā)送和接收工作遵循下列規(guī)則：（1）每個(gè)發(fā)送進(jìn)程一次發(fā)送一個(gè)消息，寫入一個(gè)緩沖區(qū)，緩沖區(qū)大小等于消息長(zhǎng)度。（2）對(duì)每個(gè)消息，B1，B2，…Bn2都須各接收一次，讀入各自的數(shù)據(jù)區(qū)內(nèi)。（3）m個(gè)緩沖區(qū)都滿時(shí)，發(fā)送進(jìn)程等待，沒有可讀消息時(shí)，接收進(jìn)程等待。試用wait、signal操作組織正確的發(fā)送和接收工作。例題5

進(jìn)程A1、A2，…An1通過m個(gè)緩沖區(qū)向進(jìn)程B1分析：每個(gè)緩沖區(qū)只要寫一次但要讀n2次，因此，可以看成n2組緩沖區(qū)，每個(gè)發(fā)送者要同時(shí)寫n2個(gè)緩沖區(qū)，而每個(gè)接收者只要讀它自己的緩沖區(qū)。Sin[n2]=m；表示每個(gè)讀進(jìn)程開始有m個(gè)空緩沖區(qū)。Sout[n2]=0；表示每個(gè)讀進(jìn)程開始有0個(gè)可接收的消息。分析：每個(gè)緩沖區(qū)只要寫一次但要讀n2次，因此，可以看成n2組解：先將問題簡(jiǎn)化：設(shè)緩沖區(qū)的大小為1有一個(gè)發(fā)送進(jìn)程A1有二個(gè)接收進(jìn)程B1、B2設(shè)有信號(hào)量Sin[1]、Sin[2]初值為1設(shè)有信號(hào)量Sout[1]、Sout[2]初值為0解：先將問題簡(jiǎn)化：Bi：while(1){

wait(Sout[i]);

從緩沖區(qū)取數(shù)signal(Sin[i]);}A1:

while(1){

wait(Sin[1]);

wait(Sin[2]);

將數(shù)據(jù)放入緩沖區(qū) signal(Sout[1]);signal(Sout[2]);

}Bi：A1:

while(1)向目標(biāo)前進(jìn)一步:設(shè)緩沖區(qū)的大小為m有一個(gè)發(fā)送進(jìn)程A1有二個(gè)接收進(jìn)程B1、B2設(shè)有信號(hào)量Sin[1]、Sin[2]初值為m設(shè)有信號(hào)量Sout[1]、Sout[2]初值為0向目標(biāo)前進(jìn)一步:設(shè)緩沖區(qū)的大小為mBi：while(1){

wait(Sout[i]);

wait(mutex); 從緩沖區(qū)取數(shù)

signal(mutex);signal(Sin[i]);};A1:

while(1){

wait(Sin[1]);

wait(Sin[2]);

wait(mutex); 將數(shù)據(jù)放入緩沖區(qū) signal(mutex); signal(Sout[1]);signal(Sout[2]);

}Bi：A1:

while(1)到達(dá)目標(biāo)設(shè)緩沖區(qū)的大小為m有n1個(gè)發(fā)送進(jìn)程A1….An1有n2個(gè)接收進(jìn)程B1…Bn2設(shè)有n2個(gè)信號(hào)量Sin[n2]初值均為m設(shè)有n2個(gè)信號(hào)量Sout[n2]初值均為0到達(dá)目標(biāo)設(shè)緩沖區(qū)的大小為mBi：while(1){

wait(Sout[i]);

wait(mutex);

從緩沖區(qū)取數(shù)

signal(mutex);signal(Sin[i]);};Aj:while(1){for(i=1;i<=n2;i++)

wait(Sin[i]);

wait(mutex); 將數(shù)據(jù)放入緩沖區(qū)

signal(mutex); for(i=1;i<=n2;i++) signal(Sout[2]);}Bi：Aj:進(jìn)程同步算法補(bǔ)充作業(yè)：設(shè)有兩個(gè)優(yōu)先級(jí)相同的進(jìn)程p1與p2，令信號(hào)量s1、s2的初值為0，已知z=2，試問p1、p2并發(fā)運(yùn)行后x=?,y=?,z=?進(jìn)程p1：y=1;進(jìn)程p2：x=1;y=y+2;x=x+1;signal(s1);wait(s1);z=y+1;x=x+y;wait(s2);signal(s2);y=z+y;z=z+x;2．請(qǐng)按下列方法分別寫出非死鎖的哲學(xué)家進(jìn)餐算法：（1）最多允許4個(gè)哲學(xué)家同時(shí)進(jìn)餐。（2）奇數(shù)號(hào)哲學(xué)家先拿其左邊的筷子，然后再那其右邊的筷子；而偶數(shù)號(hào)哲學(xué)家先拿其右邊的筷子，然后再那其左邊的筷子。進(jìn)程同步算法補(bǔ)充作業(yè)：設(shè)有兩個(gè)優(yōu)先級(jí)相同的進(jìn)程p1與p2，令3.有橋如下圖所示，車流方向如箭頭所示。假設(shè)橋上不允許兩車交會(huì)，但允許同方向多輛車依次通過（即橋上可有多個(gè)相同方向行駛的車輛），試用wait和signal操作實(shí)現(xiàn)橋上的交通管理。4．某銀行人民幣儲(chǔ)蓄業(yè)務(wù)由若干個(gè)柜員負(fù)責(zé)。每個(gè)顧客進(jìn)入銀行后先取一個(gè)號(hào)，并且等著叫號(hào)，當(dāng)一個(gè)柜員空閑下來時(shí)，就叫下一個(gè)號(hào)，持該號(hào)的顧客被服務(wù)。試用wait、signal操作正確編寫柜臺(tái)人員進(jìn)程和顧客進(jìn)程的同步算法。3.有橋如下圖所示，車流方向如箭頭所示。假設(shè)橋上不允許兩設(shè)有n個(gè)進(jìn)程共享一個(gè)程序段，對(duì)如下兩種情況：（1)如果每次只允許一個(gè)進(jìn)程進(jìn)入該程序段；(2)如果每次最多允許m個(gè)進(jìn)程(M＜＝n)同時(shí)進(jìn)入該程序段。試問：所采用的信號(hào)量初值是否相同?信號(hào)量值的變化范圍如何?所采用信號(hào)量的初值不相同。在情況(1)中，信號(hào)量的初值為1，信號(hào)量值的變化范圍是l，0，-1…-(n-1)。在情況(2)中，信號(hào)量的初值為M，信號(hào)量值的變化范圍是M，m-1，m-2…(m-n)。進(jìn)程同步習(xí)題設(shè)有n個(gè)進(jìn)程共享一個(gè)程序段，對(duì)如下兩種情況：所采用信號(hào)量的初【例】一個(gè)buffer,一個(gè)生產(chǎn)者，一個(gè)消費(fèi)者，生產(chǎn)者只生產(chǎn)一個(gè)東西，消費(fèi)者只進(jìn)行一次消費(fèi)，即：生產(chǎn)者只進(jìn)行一次putdata操作，消費(fèi)者只進(jìn)行一次getdata操作?！纠恳粋€(gè)buffer,一個(gè)生產(chǎn)者，一個(gè)消費(fèi)者，生產(chǎn)者只生產(chǎn)【解答】設(shè)置信號(hào)量full,表示buffer是否有數(shù)據(jù),初值為0生產(chǎn)者消費(fèi)者putdataP(full)V(full)getdata【解答】【例】一個(gè)buffer,一個(gè)生產(chǎn)者，一個(gè)消費(fèi)者，生產(chǎn)者不斷進(jìn)行putdata操作，消費(fèi)者不斷進(jìn)行g(shù)etdata操作，即生產(chǎn)者不斷生產(chǎn)，消費(fèi)者不斷消費(fèi)?！窘獯稹縝uffer為空時(shí)，才能進(jìn)行putdata操作，只有buffer有數(shù)據(jù)時(shí)，才能進(jìn)行g(shù)etdata操作信號(hào)量full:是否有數(shù)據(jù)初值為0empty:是否為空，初值為1【例】一個(gè)buffer,一個(gè)生產(chǎn)者，一個(gè)消費(fèi)者，生產(chǎn)者不斷進(jìn)生產(chǎn)者：repeatP(empty)putdataV(full)消費(fèi)者：repeatP(full)getdataV(empty)生產(chǎn)者：消費(fèi)者：【例】一個(gè)buffer,多個(gè)生產(chǎn)者，多個(gè)消費(fèi)者，多個(gè)生產(chǎn)者和消費(fèi)者都在不斷地存取buffer，即生產(chǎn)者不斷地進(jìn)行putdata操作，消費(fèi)者不斷進(jìn)行g(shù)etdata操作?！窘獯稹恐挥衎uffer為空時(shí)能進(jìn)行putdata操作，只有buffer有數(shù)據(jù)時(shí)能進(jìn)行putdata操作。不允許多個(gè)進(jìn)程同時(shí)操作buffer,即不允許多個(gè)消費(fèi)者同時(shí)進(jìn)行g(shù)etdata,不允許多個(gè)生產(chǎn)者進(jìn)行putdata操作信號(hào)量full:buffer是否有數(shù)據(jù)，初值為0empty:buffer是否為空，初值為1mutex:buffer是否可操作，初值為1【例】一個(gè)buffer,多個(gè)生產(chǎn)者，多個(gè)消費(fèi)者，多個(gè)生產(chǎn)者和生產(chǎn)者irepeatP(empty)P(mutex)putdataV(mutex)V(full)消費(fèi)者irepeatP(full)P(mutex)getdataV(mutex)V(empty)生產(chǎn)者i消費(fèi)者i【例】多個(gè)生產(chǎn)者，多個(gè)消費(fèi)者，N個(gè)buffer，多次循環(huán)存取buffer,即多個(gè)生產(chǎn)者不斷進(jìn)行putdata操作，多個(gè)消費(fèi)者不斷進(jìn)行g(shù)etdata操作【解答】只有buffer有空間時(shí)才能進(jìn)行putdata操作只有buffer有數(shù)據(jù)時(shí)才能進(jìn)行g(shù)etdata操作不允許多個(gè)消費(fèi)者和多個(gè)生產(chǎn)者同時(shí)操作信號(hào)量full:表示buffer是否有數(shù)據(jù)，初值為0empty:表示buffer是否為空，初值為nmutex:表示buffer是否可操作，初值為1【例】多個(gè)生產(chǎn)者，多個(gè)消費(fèi)者，N個(gè)buffer，多次循環(huán)存取生產(chǎn)者irepeatP(empty)P(mutex)putdataV(mutex)V(full)消費(fèi)者jrepeatP(full)P(mutex)putdataV(mutex)V(empty)生產(chǎn)者i消費(fèi)者j【改進(jìn)】putdata和getdata操作都在臨界區(qū)中，因此多個(gè)進(jìn)程對(duì)多個(gè)buffer的操作不能并行進(jìn)行的，進(jìn)程間并行操作的程度很低。實(shí)際上只要保證多個(gè)進(jìn)程同時(shí)操作不同buffer就可以實(shí)現(xiàn)對(duì)整個(gè)buffer的并行操作。getEBuffer()返回空的buffer號(hào)getEBuffer()return(pbuffer+1)modngetDBuffer()返回有數(shù)據(jù)的buffer號(hào)getDBuffer()return(pdata+1)modn【改進(jìn)】putdata和getdata操作都在臨界區(qū)中，因此semaphoremutex,empty,full=1,n,0integerpbuff,pdata=0,0生產(chǎn)者i消費(fèi)者jrepeatrepeatP(empty)P(full)P(mutex)P(mutex)in=getEBuffer()out=getDBuffer()V(mutex)V(mutex)putdata(in)getdata(out)V(full)V(empty)semaphoremutex,empty,full=1,【練習(xí)】如圖，有多個(gè)PUT操作同時(shí)向Buff1放數(shù)據(jù)，有一個(gè)MOVE操作不斷地將Buff1的數(shù)據(jù)移到Buff2,有多個(gè)GET操作不斷地從Buff2中將數(shù)據(jù)取走。Buff1的容量是m,Buff2的容量是n,PUT,MOVE,GET每次操作一個(gè)數(shù)據(jù)，在操作的過程中要保證數(shù)據(jù)不丟失。試用P,V原語協(xié)調(diào)PUT,MOVE操作，并說明每個(gè)信號(hào)量的含義和初值?！揪毩?xí)】如圖，有多個(gè)PUT操作同時(shí)向Buff1放數(shù)據(jù)，有一個(gè)Buff1Buff2MOVEPUTGETBuff1Buff2MOVEPUTGET【解答】三類進(jìn)程：多個(gè)PUT類進(jìn)程，一個(gè)MOVE類進(jìn)程，多個(gè)GET類進(jìn)程操作規(guī)則1只有buff1有空間才能進(jìn)行PUT操作2只有buff1有數(shù)據(jù)，buff2有空間才能進(jìn)行MOVE操作3只有buff2有數(shù)據(jù)才能進(jìn)行GET操作4不允許多個(gè)進(jìn)程同時(shí)操作buff15不允許多個(gè)進(jìn)程同時(shí)操作buff2【解答】三類進(jìn)程：多個(gè)PUT類進(jìn)程，一個(gè)MOVE類進(jìn)程，多個(gè)操作流程<PUT類進(jìn)程>repeat判斷buff1是否有空間，沒有則等待是否可操作buff1PUT設(shè)置buff1可操作標(biāo)志設(shè)置buff1有數(shù)據(jù)的標(biāo)志untilfalse操作流程<MOVE類進(jìn)程>repeat判斷buff1是否有數(shù)據(jù)，沒有則等待判斷buff2是否有空間，沒有則等待是否可操作buff1是否可操作buff2MOVE設(shè)置buff1可操作標(biāo)志設(shè)置buff2可操作標(biāo)志設(shè)置buff1有空間標(biāo)志設(shè)置buff2有空間標(biāo)志<MOVE類進(jìn)程><GET類進(jìn)程>repeat判斷buff2是否有數(shù)據(jù)，沒有則等待是否可操作buff2GET設(shè)置buff1可操作標(biāo)志設(shè)置buff1有空間標(biāo)志<GET類進(jìn)程>4信號(hào)量設(shè)置6個(gè)信號(hào)量full1:buff1是否有數(shù)據(jù)，初值為0empty1:buff1有空間，初值為mmutex1:buff1是否可操作，初值為1full2:buff2是否有數(shù)據(jù)，初值為0empty2:buff2有空間，初值為nmutex2:buff2是否可操作，初值為14信號(hào)量5PV操作實(shí)現(xiàn)<PUT類進(jìn)程>repeatp(empty1);//判斷buff1是否有空間，沒有則等待p(mutex1);//是否可操作buff1PUT;v(mutex1);//設(shè)置buff1可操作標(biāo)志v(full);//設(shè)置buff1有數(shù)據(jù)標(biāo)志5PV操作實(shí)現(xiàn)<MOVE類進(jìn)程>repeatP(full1）；判斷buff1是否有數(shù)據(jù)，沒有則等待P(empty2);//判斷buff2是否有空間，沒有則等待P(mutex1);//是否可操作buff1P(mutex2);//是否可操作buff2MOVE;V(mutex1);//設(shè)置buff1可操作標(biāo)志V(mutex2);//設(shè)置buff2可操作標(biāo)志V(empty1);//設(shè)置buff1有空間標(biāo)志V(full2);//設(shè)置buff2有數(shù)據(jù)標(biāo)志<MOVE類進(jìn)程><GET類進(jìn)程>repeatP(empty2);//判斷buff2是否有空間，沒有則等待P(mutex2);//是否可操作buff2GETV(mutex2);//設(shè)置buff2可操作標(biāo)記V(full2);//設(shè)置buff2有數(shù)據(jù)標(biāo)記<GET類進(jìn)程>【例】現(xiàn)有4個(gè)進(jìn)程R1，R2，W1，W2。它們共享可以存放一個(gè)數(shù)據(jù)的緩沖器B。進(jìn)程R1每次把磁盤上讀出的一個(gè)數(shù)據(jù)存到緩沖器B中，供進(jìn)程W1打印輸出；進(jìn)程R2每次從鍵盤上讀一個(gè)數(shù)據(jù)存放到緩沖器B，供W2打印輸出。當(dāng)一個(gè)進(jìn)程把數(shù)據(jù)存放到緩沖器后，在該數(shù)據(jù)還沒有打印輸出之前不準(zhǔn)任何進(jìn)程再想緩沖器中存數(shù)據(jù)。當(dāng)一個(gè)進(jìn)程已把緩沖器中的數(shù)據(jù)打印輸出后，在緩沖器中還沒有存如新數(shù)據(jù)之前不準(zhǔn)任何進(jìn)程再從緩沖器中取數(shù)打印。問怎樣用PV操作使這4個(gè)進(jìn)程并發(fā)執(zhí)行時(shí)能相互協(xié)作地工作？【例】現(xiàn)有4個(gè)進(jìn)程R1，R2，W1，W2。它們共享可以存放一R1R2W1W2R1R2W1W2【解答】4個(gè)進(jìn)程互斥，R1，W1同步，R2，W2同步mutex：表示能否把數(shù)據(jù)存如緩沖器，初始化時(shí)緩沖器為空，故初值為1S1：進(jìn)程R1是否已向緩沖器存入一個(gè)數(shù)據(jù)，初值為0S2：進(jìn)程R2是否已向緩沖器存入一個(gè)數(shù)據(jù)，初值為0【解答】4個(gè)進(jìn)程互斥，R1，W1同步，R2，W2同步beginmutex,s1,s2:semaphore;s:=1;s2:=0;s2:=0;cobeginprocessR1beginL1:從磁盤上讀數(shù)據(jù)送x1;P(mutex);B:=x1;V(s1);gotoL1end;processW1beginL3:P(s1);y:=B;V(mutex);打印ygotoL3end;begin

processR2beginL2:從鍵盤上讀數(shù)據(jù)送x2;P(mutex);B:=x2;V(s2);gotoL2end;processW2beginL4:P(s2);z:=B;V(mutex);打印z;gotoL4end;processW2【例】假定有3個(gè)進(jìn)程R，W1，W2共享一個(gè)緩沖器，而B中每次只能存放一個(gè)數(shù)，當(dāng)緩沖器中無數(shù)時(shí)，進(jìn)程R可將M輸入設(shè)備上讀入的數(shù)存放到緩存器B中，若存放到緩存器中的是奇數(shù)，則允許進(jìn)程W1將其取出打??；若存放到緩沖器中的是偶數(shù)，則允許進(jìn)程W2將取出打印。同時(shí)規(guī)定：進(jìn)程R必須等緩沖器中的數(shù)被取出打印后才能再存放一個(gè)數(shù)；進(jìn)程W1或W2對(duì)每次存入緩沖器中的數(shù)只能打印一次；W1和W2都不能從空的緩沖器中取數(shù)。寫出這3個(gè)并發(fā)進(jìn)程能正確工作的程序?！纠考俣ㄓ?個(gè)進(jìn)程R，W1，W2共享一個(gè)緩沖器，而B中每次【分析】把進(jìn)程R看作是生產(chǎn)者，把進(jìn)程W1和W2看作是消費(fèi)者?，F(xiàn)在有一個(gè)生產(chǎn)者（進(jìn)程R)能生產(chǎn)不同的產(chǎn)品（讀入奇數(shù)或偶數(shù)），把生產(chǎn)的產(chǎn)品存放在緩沖器B中，供不同的消費(fèi)者（進(jìn)程W1和進(jìn)程W2）取用?？梢钥闯?，當(dāng)進(jìn)程R讀入的是整數(shù)，則要把有奇數(shù)的消息發(fā)送給進(jìn)程W1；當(dāng)進(jìn)程R讀入的是偶數(shù)，則要把有偶數(shù)的消息發(fā)送給W2，在進(jìn)程W1或進(jìn)程W2從緩沖器中取出數(shù)后，應(yīng)把緩沖器中又可有一個(gè)數(shù)的消息告訴進(jìn)程R，于是，可以定義如下3個(gè)信號(hào)量：S表示是否可以把數(shù)存入緩沖器，由于緩沖器中每次只能放一個(gè)數(shù)，所以其初值取為”1“SO：表示緩沖器中是否有奇數(shù)，初值為”0“，表示無奇數(shù)SE：表示緩沖器是否偶數(shù)，初值為0，表示無偶數(shù)【分析】把進(jìn)程R看作是生產(chǎn)者，把進(jìn)程W1和W2看作是消費(fèi)者?！窘獯稹縤ntegerB;semaphoreS,SO,SESO=0;SE=0:

integerxL1:從輸入設(shè)備讀入一個(gè)數(shù)X=讀入的數(shù)P(S);B=Xif(B=偶數(shù)）V(SO)elseV(SE)gotoL1【解答】進(jìn)程同步習(xí)題全課件【例】設(shè)有一個(gè)具有N個(gè)信息元素的環(huán)形緩沖區(qū)，A進(jìn)程順序地把信息寫入緩沖區(qū)，B進(jìn)程依次從緩沖區(qū)讀出信息?；卮鹣铝袉栴}：1敘述A，B兩進(jìn)程的相互制約關(guān)系2判別下列用PV操作表示的同步算法是否正確？如不正確，試說明理由，并修改成正確的算法。設(shè)置信號(hào)量初值:S1＝0，S2＝N;設(shè)置變量初值：in=out=0;【例】設(shè)有一個(gè)具有N個(gè)信息元素的環(huán)形緩沖區(qū)，A進(jìn)程順序地把信【例】進(jìn)程P1使用緩沖區(qū)buffer向進(jìn)程P2,P3,P4發(fā)送消息，要求每當(dāng)P1向buffer中發(fā)消息時(shí)，只有當(dāng)P2,P3,P4進(jìn)程都讀取這條消息后才可再向buffer中發(fā)送消息。利用PV原語描述進(jìn)程的動(dòng)作序列P1bufferP2P3P4【例】進(jìn)程P1使用緩沖區(qū)buffer向進(jìn)程P2,P3,P4發(fā)【解答】設(shè)置信號(hào)量初值S1=S2=S3=0,S=3進(jìn)程P1進(jìn)程P2進(jìn)程P3進(jìn)程P4P(S)P(S1)P(S2)P(S3)P(S)讀消息讀消息讀消息P(S)V(S)V(S)V(S)發(fā)送消息到BufferV(S1)V(S2)V(S3)【解答】設(shè)置信號(hào)量初值S1=S2=S3=0,S=3【例】設(shè)A，B為兩個(gè)并發(fā)進(jìn)程，它們共享一個(gè)臨界區(qū)，其執(zhí)行臨界區(qū)的算法框圖如下。試判斷該算法是否有錯(cuò)？請(qǐng)說明理由。如果有錯(cuò)，請(qǐng)改正。S1，S2的初值為0，CSA,CSB為臨界區(qū)。CSAV(S1)P(S2)A進(jìn)程P(S1)CSBV(S2)B進(jìn)程【例】設(shè)A，B為兩個(gè)并發(fā)進(jìn)程，它們共享一個(gè)臨界區(qū)，其執(zhí)行臨界【分析】系統(tǒng)啟動(dòng)時(shí)，S1,S2為0，則B執(zhí)行P(S1)被阻塞，而A進(jìn)程可直接訪問臨界資源。故A，B兩個(gè)并發(fā)進(jìn)程不可能同時(shí)操作臨界資源，該算法是可以保證互斥的。按題目要求，兩個(gè)進(jìn)程對(duì)臨界資源的操作是沒有先后順序的，但是，在上面的實(shí)現(xiàn)中，只有A進(jìn)程先操作完資源后，B資源才能操作。【分析】系統(tǒng)啟動(dòng)時(shí)，S1,S2為0，則B執(zhí)行P(S1)被阻塞【解答】該算法錯(cuò)誤若A進(jìn)程用不要求訪問臨界資源，則不會(huì)折行V(S1),意味著B進(jìn)程的申請(qǐng)永遠(yuǎn)得不到操作臨界資源的機(jī)會(huì)；同理，若B不要求訪問臨界資源，則不會(huì)執(zhí)行V(S2),意味著進(jìn)程A下次也得不到操作臨界資源的機(jī)會(huì)。所以，問題在于本應(yīng)該互斥控制而使用的卻是同步控制。實(shí)現(xiàn)改正：【解答】該算法錯(cuò)誤信號(hào)量mutex=1A進(jìn)程B進(jìn)程repeat