操作系統(tǒng)中進程的同步與通信

內容進程同步的基本概念信號量機制經典進程同步問題管程機制進程通信信號量舉例第三章進程的同步與通信目的及要求理解臨界資源和臨界區(qū)的概念，初步領會進程同步機制應遵循的準則；理解和掌握整型信號量和記錄型信號量機制；熟練掌握利用信號量機制解決經典進程同步問題；領會管程的基本概念，掌握利用管程解決經典進程同步問題；了解進程通信的類型，理解消息傳遞系統(tǒng)中的發(fā)送和接受原語。第三章進程的同步與通信重點臨界資源和臨界區(qū)的概念；記錄型信號量機制；利用信號量機制解決經典進程同步問題；管程的基本概念；利用管程解決經典進程同步問題。難點利用軟件方法解決進程互斥問題；利用信號量機制解決經典進程同步問題；管程的概念。第三章進程的同步與通信資源共享關系 （CooperationAmongProcessesbySharing）

多進程共享資源，例如各進程爭用一臺打印機，這時各進程使用這臺打印機時有一定的限制。每次只允許一個進程使用一段時間打印機，等該進程使用完畢后再將打印機分配給其它進程。這種使用原則稱為互斥使用。相互合作關系 （CooperationAmongProcessesbyCommunication）

在某些進程之間還存在合作關系，例如一個程序的輸入、計算、打印三個程序段作為三個進程并發(fā)執(zhí)行，由于這三個進程間存在著相互合作的關系，即先輸入再計算、最后再打印的關系，所以這三個進程在并發(fā)執(zhí)行時推進序列受到限制，要保證其合作關系正確，進程間這種關系稱為同步關系3.1

進程同步的基本概念3.1.1

臨界資源3.1.2臨界區(qū)3.1.3利用軟件方法解決進程互斥問題3.1.4利用硬件方法解決進程互斥問題3.1

進程同步的基本概念象打印機這類資源一次只允許一個進程使用的資源稱為臨界資源。屬于臨界資源有硬件打印機、磁帶機等，軟件在消息緩沖隊列、變量、數(shù)組、緩沖區(qū)等。當然還有一類象磁盤等資源，它允許進程間共享，即可交替使用，所以它稱為共享資源，而臨界資源又稱獨享資源。 進程在并發(fā)執(zhí)行時為了保證結果的可再現(xiàn)性，各進程執(zhí)行序列必須加以限制以保證互斥地使用臨界資源，相互合作完成任務。3.1.1

臨界資源(CriticalResources)3.1.2

臨界區(qū)(criticalsections)臨界區(qū)的定義與進入臨界區(qū)(criticalsection)：進程中訪問臨界資源的一段代碼。進入區(qū)(entrysection)：在進入臨界區(qū)之前，檢查可否進入臨界區(qū)的一段代碼。如果可以進入臨界區(qū)，通常設置相應“正在訪問臨界區(qū)”標志退出區(qū)(exitsection)：用于將“正在訪問臨界區(qū)”標志清除。剩余區(qū)(remaindersection)：代碼中的其余部分。同步機制應遵循的準則

用于保證多個進程在執(zhí)行次序上的協(xié)調關系的相應機制稱為進程同步機制?？臻e讓進當無進程進入臨界區(qū)時，相應的臨界資源處于空閑狀態(tài)，因而允許一個請求進入臨界區(qū)的進程立即進入自己的臨界區(qū)。忙則等待當已有進程進入自己的臨界區(qū)時，即相應的臨界資源正被訪問，因而其它試圖進入臨界區(qū)的進程必須等待，以保證進程互斥地訪問臨界資源。3.1.2

臨界區(qū)(criticalsections)有限等待對要求訪問臨界資源的進程，應保證進程能在有限時間進入臨界區(qū)，以免陷入“饑餓”狀態(tài)。讓權等待當進程不能進入自己的臨界區(qū)時，應立即釋放處理機，以免進程陷入忙等。3.1.2

臨界區(qū)(criticalsections)3.1.3

利用軟件方法解決進程互斥問題問題：有二個進程Pi和Pj互斥共享臨界資源R，beginparbegin Pi; Pj;parendend3.1.3

利用軟件方法解決進程互斥問題算法1：單標志

設置一個公用整型變量turn，用于指示被允許進入臨界區(qū)的進程的編號，即若turn=i，表示允許進程Pi進入臨界區(qū)。Pi進程:Pj進程:

repeatrepeatwhileturn≠idonoop;

whileturn≠jdonoop;CriticalsectionCriticalsectionturn:=j;turn:=i;RemainSectionRemainSectionuntilfalseuntilfalse3.1.3

利用軟件方法解決進程互斥問題該算法可確保每次只允許一個進程進入臨界區(qū)。但是，強制兩個進程輪流地進入臨界區(qū)，很容易造成資源利用不充分。例如，當進程只退出臨界區(qū)后將turn置為j，以便允許Pj進入臨界區(qū)。但如果進程Pj暫時并未要求訪問該臨界資源，而Pi又想再次訪問該資源，但它卻無法進入臨界區(qū)?？梢姡怂惴ú荒鼙ＷC實現(xiàn)“空閑讓進”的準則l。3.1.3

利用軟件方法解決進程互斥問題算法2：雙標志先檢查 算法2的基本思想是：在每一個進程訪問臨界資源之前，先去查看一下臨界資源是否正被訪問。若正被訪問，該進程需等待；否則才進人自己的臨界區(qū)。為此，設置了一個數(shù)組，使其中每個元素的初值為false，表示所有進程都未進入臨界區(qū)；而當其中的第i個元素值true時，即若flag[i]=true時，表示進程Pi正在臨界區(qū)內執(zhí)行。

Pi: Pj： repeatrepeat whileflag[j]dono_op; whileflag[i]dono_op; flag[i]:=true; flag[j]:=true; critical_section; critical_section; flag[i]:=false; flag[j]:=false; remaindersection; remaindersection; untilfalseuntilfalse3.1.3

利用軟件方法解決進程互斥問題算法3：雙標志、后檢查

為了解決這一問題，在算法3中仍然使用了數(shù)flag[n]，但令flag[i]=true表示進程Pi希望進入臨界區(qū)，即每當進程Pi要進入臨界區(qū)前，先將flag[i]置為ture，表示進程Pi已要求進入臨界區(qū)。然后再去查看Pj的標志。若此時flag[j]=true，則pi等待；否則，Pi進入臨界區(qū)。換言之，算法3是使要進入臨界區(qū)的進程先設置其要求進入的標志，然后，再去查看其它進程的標志。3.1.3

利用軟件方法解決進程互斥問題Pi: Pj:repeatrepeat flag[i]:=true; flag[j]:=true;

whileflag[j]dono_op;

whileflag[i]dono_op; critical_section;critical_section; flag[i]:=false;flag[j]:=false; remaindersection;remaindersection;untilfalseuntilfalse3.1.3

利用軟件方法解決進程互斥問題算法4：先修改、后檢查、后修改者等待該算法是組合了算法1和算法3中的關鍵概念而形成的新算法為每個進程設置了相應的標志位flag[i]，當flag[i]=true時，表示進程Pi要求進入臨界區(qū)。此外，還設置了一個turn變量，用于指示允許進入臨界區(qū)的進程編號。進程Pi為了進入臨界區(qū)先置flag[i]為true，并置turn為j，表示應輪到進程j進入臨界區(qū)。接下去再判別flag[j]andturn=j的條件是否滿足。若未滿足即false，則可進入臨界區(qū)；否則等待?；蛘哒f，當flag[j]=false或者turn=i時，進程pi可以進入臨界區(qū)。前者表示pj未要求進入臨界區(qū)，后者表示僅允許Pi進入臨界區(qū)。

3.1.3

利用軟件方法解決進程互斥問題Pi:repeatflag[i]:=true;turn:=j;while(flag[j]andturn=j)dono_op;critical_section;flag[i]:=false;remaindersection;untilfalse

Pj:repeatflag[j]:=true;turn:=i;while(flag[i]andturn=i)dono_op;critical_section;flag[j]:=false;remaindersection;untilfalse

3.1.3

利用軟件方法解決進程互斥問題假如過程Pi和Pj幾乎同時要求進入臨界區(qū)，它們將分別將標志flag[i]和flag[j]置為true。Pi先將turn置j，當它去執(zhí)行While語句時，flag[j]andturn=j條件成立，故又等待；但立即Pj又將turn置成I；這樣，Pi便可進入臨界區(qū)，而進程PJ執(zhí)行while語句時，flag[i]andturn=i條件成立，使Pj等待；當Pi退出臨界區(qū)時，將flag[i]置為false后，將使flag[i]andturn=j條件不再成立，從而使Pj進入臨界區(qū)。這樣，既保證了“忙則等待”，又實現(xiàn)了“有空讓進”。3.1.4

利用硬件方法解決進程互斥問題

完全利用軟件方法來解決諸進程互斥進入臨界區(qū)的問題，有一定難度，且有很大局限性，因而現(xiàn)代已很少采用此方法。 針對這一點，現(xiàn)在有許多計算機已提供了一些特殊的硬件指令，這些指令允許對一個字中的內容進行檢測和修正，或交換兩個字的內容等。可利用這些特殊的指令來解決臨界區(qū)問題。 下面介紹兩條特殊硬件指令，以及利用它們來解決臨界區(qū)問題的方法。3.1.4

利用硬件方法解決進程互斥問題利用Test－and－Set指令實現(xiàn)互斥Test－and－Set指令在許多機器中都有這樣的指令，不同機器的相應指令的功能是相同的，因而我們不局限于某特定的機器去定義Test－and－set指令為functionTS（varlock：boolean）：boolean；

beginTS:=lock；

lock:=true；

end其中，lock有兩種狀態(tài)：當lock=false時，表示該資源空閑；當lock=true時，表示該資源正在被使用。3.1.4

利用硬件方法解決進程互斥問題利用TS實現(xiàn)進程互斥

為了實現(xiàn)諸進程對臨界資源的互斥訪問，可為每個臨界資源設置一個布爾變量lock，并賦予其初值為false，以表示資源空閑。 利用TS指令實現(xiàn)互斥的Pi進程可描述為：

repeatwhileTS(lock)dono－loop；

criticalsection;lock:=false;remaindersectionuntilfalse；3.1.4

利用硬件方法解決進程互斥問題利用Swap指令實現(xiàn)進程互斥Swap指令

該指令稱為交換指令。在微型機中該指令又稱為XCHG指令，用于交換兩個字的內容，可描述如下：

ProcedureSwap（vara,b：boolean）

vartemp：boolean；

begintemp:=a；

a:=b；

b:=temp；

end3.1.4

利用硬件方法解決進程互斥問題利用Swap實現(xiàn)進程互斥 在利用Swap實現(xiàn)進程互斥時，可為臨界資源設置一個全局布爾變量lock，其初值為false(表示可用)，在每個進程中再利用一個局部布爾變量key。利用Swap指令實現(xiàn)進程互斥的Pi進程可描述為：repeatkey:=true;repeat Swap(lock,key);untilkey=false;criticalsection;lock:=false;remaindersectionuntilfalse；利用硬件指令能有效地實現(xiàn)過程互斥，但它卻不能滿足“讓權等待”的準則，造成處理機時間的浪費，而且也很難將它用于解決較復雜的進程同步問題。

1965年，荷蘭學者Dijkstra提出的信號量機制是一種卓有成效的進程同步工具。在長期且廣泛的應用中，信號量機制又得到了很大的發(fā)展，它從整型信號量經記錄型信號量，進而發(fā)展為“信號量集”機制。現(xiàn)在信號量機制已被廣泛地應用于單處理機和多處理機系統(tǒng)，以及計算機網絡中。3.2.1整型信號量機制3.2.2記錄型信號量機制3.2.3信號量集機制3.2

信號量機制

整型信號量最初信號量S是一個整型變量，除初始化外，對信號量僅能執(zhí)行兩個原子操作，即wait(s)和signal(s),這兩個原子操作以前多稱為P（s）和V(s)操作。wait(s){ whiles<=0dono-loop s:=s-1;}signal(s){ s:=s+1;}3.2.1

整型信號量機制

利用信號量實現(xiàn)互斥

進程P1 進程P2 ┊ ┊

wait（mutex）； wait（mutex）；

criticalsection

criticalsection

signal（mutex）； signal（mutex）； remaindersection remaindersection

┊ ┊ 信號量mutex的初值為1，每個進程在進入臨界區(qū)時對信號量執(zhí)行wait操作，待臨界區(qū)執(zhí)行完后執(zhí)行signal操作。3.2.1

整型信號量機制

利用信號量來描述前趨關系 信號量s的初值為0，當進程P2先執(zhí)行必定阻塞，只有在P1執(zhí)行完S1；signal(s)，P2才被喚醒。

進程P1 進程P2 ┊ ┊ S1; wait(s) signal(s)

S2;

┊

┊3.2.1

整型信號量機制

3.2.1

整型信號量機制

S1S2S4S6S5S3abcdefgvara,b,c,d,e,f,g:semaphore=0;beginparbeginbegins1；signal(a)；signal(b)；end；beginwait(a)；s2；signal(c)；signal(d)；end；beginwait(b)；s3；signal(e)；end；beginwait(c)；s4；signal(f)；end；beginwait(d)；s5；signal(g)；end；beginwait(e)；wait(f)；wait(g)；s6；end；parendend

習題（P94-8）：我們?yōu)槟撑R界區(qū)設置一把鎖W，當W=1時，表示關鎖；W=0表示鎖已打開。試寫出開鎖原語和關鎖原語，并利用它們去實現(xiàn)互斥。3.2.1

整型信號量機制

解： 開鎖原語

unlock(W): W:=0;

關鎖原語

lock(W): whileW=1dono_op;

W=1;

利用開關鎖原語實現(xiàn)互斥:

varW:semaphore:=0;

begin

parbegin

process:

begin

repeat

lock(W);

criticalsection

unlock(W);

remaindersection

untilfalse;

3.2.1

整型信號量機制

每個信號量s除一個整數(shù)值s.count（計數(shù)）外，還有一個進程等待隊列s.queue，其中是阻塞在該信號量的各個進程的標識s.count初始化指定一個非負整數(shù)值，表示系統(tǒng)中某類資源的數(shù)目（又稱為“資源信號量“）若為非負值，表示當前的空閑資源數(shù)若為負值，其絕對值表示當前等待臨界區(qū)的進程數(shù)typesemaphore=record count:integer;

queue:listofprocess:endvars:semaphore;3.2.2

記錄型信號量機制procedurewait(s)begins.count:=s.count-1;ifs.count<0thenBlock(s.queue)endproceduresignal(s)begins.count:=s.count+1;ifs.count<=0thenWakeup(s.queue);end3.2.2

記錄型信號量機制ifs.count<0thenWakeup(s.queue);s.count:=s.count+1;AND型信號量集機制上述的進程的互斥問題，是針對進程間共享一個臨界資源。但在某些應用場合，進程需要共享兩個或更多的臨界資源。例如，兩個進程A和B共享臨界資源D和E，則設置兩個互斥信號量Dmutex和Emutex，初值為1。 ProcessA ProcessB wait(Dmutex) wait(Emutex) wait(Emutex) wait(Dmutex)

若進程A和B按下列次序交替wait操作：

ProcessA：wait(Dmutex)－>Dmutex=0 ProcessB:wait(Emutex)－>Emutex=0 ProcessA：wait(Emutex)－>Emutex=-1堵塞 ProcessB:wait(Dmutex)－>Dmutex=-1堵塞3.2.3

信號量集機制

最后進程A和B處在僵持狀態(tài)，在無外力作用下，無法解脫，即死鎖狀態(tài)。AND同步機制基本思想：在一個原語中，對多個臨界資源的分配采用原子操作方式，要么全部分配給它，要么一個都不分配。稱為Swait(SimultaneousWait)。AND型信號量集用于同時需要多種資源且每種占用一個時的信號量操作；3.2.3

信號量集機制

Swait(s1,s2,....sn) if（s1＞=1ands2＞=1and....andsn＞=1） fori:=1tondo Si:=Si-1; endfor else

把調用P操作的進程置為等待狀態(tài)，并插入到 第一次滿足si<1的信號量的等待隊列中；設置程序計數(shù)器指向Swait。

endif；3.2.3

信號量集機制

Ssignal(s1,s2,....sn)fori:=1tondoSi:=Si+1;

從等待隊列Si.queue中取出進程P,進入就緒隊列;endfor；3.2.3

信號量集機制

一般“信號量集”機制

一般信號量集用于同時需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個臨界值時的處理；一次需要N個某類臨界資源時，就要進行N次wait操作－－低效又可能死鎖基本思想在AND型信號量集的基礎上進行擴充進程對信號量Si的測試值為ti，用于信號量的判斷，即Si>=ti，表示資源數(shù)量低于ti時，便不予分配占用值為di，用于信號量的增減，即Si=Si-di和Si=Si+diSwait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);3.2.3

信號量集機制

Swait(s1,t1,d1;s2,t2,d2;....sn,tn,dn)

if（s1＞=t1ands2＞=t2and....andsn＞=tn）

fori:=1tondo si=si-di; endforelse 把調用P操作的進程置為等待狀態(tài)，并插入到第一次滿足 si<ti的信號量的等待隊列中；

endif；Ssignal(s1,d1;s2,d2;....sn,dn)

fori:=1tondo si=si+di; 從si等待隊列中取出進程，轉為就緒狀態(tài)； endfor；3.2.3

信號量集機制一般“信號量集”的幾種特定情況：Swait(S,d,d) 表示每次申請d個資源，當少于d個時，便不分配；Swait(S,1,1)S>1 蛻化為記錄型信號量；S=1 蛻化為互斥信號量；Swait(S,1,0) 作為一個可控開關當S>=1時，允許任何進程進入臨界區(qū)；當S=0時，禁止任何進程進入臨界區(qū)；3.2.3

信號量集機制

3.3

經典進程同步問題

3.3.1生產者－消費者問題

(theproducer-consumerproblem)3.3.2讀者－寫者問題 (thereaders-writersproblem)3.3.3哲學家進餐問題(thediningphilosophersproblem)

3.3.1生產者－消費者問題

問題描述：生產者-消費者問題是最著名的同步問題。若干進程通過有限的共享緩沖區(qū)交換數(shù)據。其中，“生產者”進程不斷寫入，而“消費者”進程不斷讀出；共享緩沖區(qū)共有N個；任何時刻只能有一個進程可對公用緩沖池進行操作。3.3.1生產者－消費者問題

利用記錄型信號量解決生產者-消費者問題任何時刻只能有一個進程可對公用緩沖池進行操作。

互斥信號量mutex用于互斥訪問公用緩沖池，初值是1資源信號量full表示“滿”緩沖區(qū)的數(shù)目，初值為0，資源信號量empty表示"空"緩沖區(qū)的數(shù)目，初值為N。full+empty=N varmutex,empty,full:semaphore:1,n,0;3.3.1生產者－消費者問題

varmutex,empty,full:semaphore:1,n,0;buffer:array[0,…,n-1]ofitem;in,out:integer:=0,0;beginparbegin producer:begin repeat produceaniteminnextp;

wait(empty); wait(mutex); buffer[in]:=nextp; in:=(in+l)modn; signal(mutex); signal(full); untilfalse; end3.3.1生產者－消費者問題

consumer:begin repeat wait(full); wait(mutex); nextc:=buffer(out); out:=(out+l)modn; signal(mutex); signal(empty); consumeaniteminnextc; untilfalse; end parendend3.3.1生產者－消費者問題

在進程同步時管理一個共享資源可能要設二個信號量，而在進程互斥管理時只要設一個信號量；每個程序中的互斥信號量mutex的wait與signal操作必須成對出現(xiàn)；資源信號量的wait與signal操作，也成對出現(xiàn)，但分別出現(xiàn)在不同的程序中；每個程序中的wait操作不能顛倒，必須先執(zhí)行對資源信號量的wait操作，然后執(zhí)行互斥信號量的wait操作，否則可能引起進程死鎖;3.3.1生產者－消費者問題

利用AND信號集解決生產者-消費者問題Swait(empty,mutex)wait(empty);wait(mutex);Ssignal(mutex,full) signal(mutex);signal(full);

Swait(full,mutex)wait(full);wait(mutex);Ssignal(mutex,empty)signal(mutex);signal(empty);3.3.1生產者－消費者問題

varmutex,empty,full:semaphore:1,n,0;buffer:array[0,…,n-1]ofitem;in,out:integer:=0,0;beginparbegin producer:begin repeat produceaniteminnextp; Swait(empty,mutex); buffer[in]:=nextp; in:=(in+l)modn; Ssignal(mutex,full); untilfalse; end3.3.1生產者－消費者問題

consumer:begin repeat Swait(full,mutex); nextc:=buffer(out); out:=(out+l)modn; Ssignal(mutex,empty); consumeaniteminnextc; untilfalse; end parendend3.3.1生產者－消費者問題

習題（P94-6): 在生產者－消費者問題中，如果缺少了signal(full)或signal(empty),對執(zhí)行結果會有何影響?解：生產者－消費者問題可描述如下:

wait(empty); wait(full);

wait(mutex); wait(mutex);

buffer(in):=nextp; nextc:=buffer(out);

in:=(in+1)modn; out:=(out+1)modn;

signal(mutex); signal(mutex);

signal(empty);3.3.1生產者－消費者問題

wait(empty); wait(full);

wait(mutex); wait(mutex);

buffer(in):=nextp; nextc:=buffer(out);

in:=(in+1)modn; out:=(out+1)modn;

signal(mutex); signal(mutex);

signal(full); 3.3.1生產者－消費者問題

習題（P94-7): 在生產者－消費者問題中，如果將兩個wait操作即wait(full)和wait(mutex)互換位置；或者是將signal(mutex)與signal(full)互換位置結果會如何?解：生產者－消費者問題可描述如下:

wait(empty); wait(mutex);

wait(mutex); wait(full);

buffer(in):=nextp; nextc:=buffer(out);

in:=(in+1)modn; out:=(out+1)modn;

signal(mutex); signal(mutex);

signal(full); signal(empty);

3.3.1生產者－消費者問題

wait(mutex); wait(full);

wait(empty); wait(mutex);

buffer(in):=nextp; nextc:=buffer(out);

in:=(in+1)modn; out:=(out+1)modn;

signal(mutex); signal(mutex);

signal(full); signal(empty);

3.3.1生產者－消費者問題

wait(empty); wait(full);

wait(mutex); wait(mutex);

buffer(in):=nextp; nextc:=buffer(out);

in:=(in+1)modn; out:=(out+1)modn;

signal(full); signal(mutex);

signal(mutex); signal(empty);3.3.1生產者－消費者問題

wait(empty); wait(full);

wait(mutex); wait(mutex);

buffer(in):=nextp; nextc:=buffer(out);

in:=(in+1)modn; out:=(out+1)modn;

signal(mutex); signal(empty);

signal(full); signal(mutex);

3.3.2

讀者－寫者問題

問題描述：有一數(shù)據區(qū)為多個進程所共享。假設一些進程只能對該數(shù)據區(qū)完成讀操作（讀者），而另一些進程只能對其完成寫操作（寫者），讀者和寫者要遵守以下約束：允許多個讀者同時從數(shù)據區(qū)中讀數(shù)據；任何時候只允許一個寫者向數(shù)據區(qū)中寫數(shù)據；當有讀者正在讀數(shù)據時，不允許寫者寫數(shù)據；若有寫者正在寫數(shù)據區(qū)，不允許讀者讀數(shù)據。3.3.2

讀者－寫者問題

利用記錄型信號量解決讀者－寫者問題互斥信號量wmutex：初值是1。公共變量readcount：表示“正在讀”的進程數(shù)，初值是0；互斥信號量rmutex：表示對readcount的互斥操作，初值是1。3.3.2

讀者－寫者問題Varrmutex,wmutex:semaphore:=1,1;readcount:integer:=0;beginparbeginreader:begin ／*讀者進程*／ repeat wait(rmutex)； ifreadcount=0thenwait(wmutex); readcunt：=readcount+1; signal(rmutex); ReadText wait(rmutex); readcount=readcount-1; ifreadcount=0thensignal(wmutex); signal(rmutex); untilfalse;end

3.3.2

讀者－寫者問題

writer:begin repeat wait(wmutex);／*寫者進程*／ WriteText; signal(wmutex); untilfalse endparendend3.3.2

讀者－寫者問題

討論信號量WRmutex用于讀者和寫者、寫者和寫者之間互斥訪問數(shù)據區(qū)。允許多個讀者同時訪問數(shù)據區(qū)。第一個讀者進入時要用信號量Wmutex與寫者互斥。變量readcount用于記錄正在讀數(shù)據區(qū)的讀者數(shù)量。由于該變量能夠被多個進程共享，也屬于臨界資源，所以使用信號量Rmutex對其實施互斥訪問。允許多個讀者同時讀數(shù)據區(qū)，當至少有一個讀者正在讀時，其他讀者無須等待就可以讀數(shù)據。在本例中，一旦有一個讀者開始訪問數(shù)據區(qū)，其后，只要至少有一個讀者正在訪問數(shù)據區(qū)，讀者將一直保持對數(shù)據區(qū)的控制權，這樣可能會造成寫者的餓死。3.3.2

讀者－寫者問題

利用信號量集機制解決讀者－寫者問題L,mx:semaphore:=RN,1;

/*規(guī)定最多只能有RN個讀者同時讀*/beginparbeginreader:begin ／*讀者進程*／ repeat Swait(L,1,1);/*L>=1表示讀者數(shù)不滿RN個，本讀者可讀*/ Swait(mx,1,0);/*mx=1表示無寫者在寫，本讀者可讀*/ performreadoperation Ssignal(L,1); untilfalse;end3.3.2

讀者－寫者問題writer:begin ／*寫者進程*／repeatSwait(mx,1,1,L,RN,0);/*mx=1表示無寫者在寫，同時L=RN表示無讀者在讀*/performwriteoperationSsignal(mx,1); untilfalse;endparendend3.3.3哲學家進餐問題

問題描述：5個哲學家圍繞一張圓桌而坐，桌子上放著5支筷子，每兩個哲學家之間放一支；哲學家的動作包括思考和進餐，進餐時需要同時拿起左邊和右邊的兩支筷子，思考時同時將兩支筷子放回原處3.3.3哲學家進餐問題利用記錄型信號量解決哲學家進餐問題varchopstick：array[0,…,4]ofsemaphore:=(1,1,1,1,1)第i個哲學家的活動可描述為：repeat wait(chopstick[i]); wait(chopstick[(i+1)mod5]; eat; signal(chopstick[i]); signal(chopstick[(i+1)mod5]; think;untilfalse；3.3.3哲學家進餐問題

若五個哲學家同時饑餓，而各自拿起左邊的筷子，則造成死鎖。其解決方法：至多只允許四個哲學家同時進餐僅當哲學家的左、右兩支筷子均可用時，才允許拿起筷子進餐規(guī)定奇數(shù)號的哲學家先拿左邊的筷子，再拿右邊的筷子，而偶數(shù)號的哲學家先拿右邊的筷子，再拿左邊的筷子；3.3.3哲學家進餐問題利用AND信號量解決哲學家進餐問題

varchopstick：array[0,…,4]ofsemaphore:=(1,1,1,1,1)第i個哲學家的活動可描述為：

repeat think; Swait（chopstick[i]，chopstick[（i+1）mod5]）; eat; Ssignal（chopstick[i]，chopstick[（i+1）mod5]）;untilfalse；3.4

管程機制

用信號量可實現(xiàn)進程間的同步，但由于信號量的控制分布在整個程序中，其正確性分析很困難。管程是管理進程間同步的機制，它保證進程互斥地訪問共享變量，并方便地阻塞和喚醒進程。管程可以函數(shù)庫的形式實現(xiàn)。相比之下，管程比信號量好控制。3.4.1管程的引入3.4.2管程的基本概念3.4.3利用管程解決生產者――消費者問題3.4.4利用管程解決讀者-寫者問題3.4.1管程的引入

信號量同步的缺點同步操作分散 信號量機制中，同步操作分散在各個進程中，使用不當就可能導致各進程死鎖（如P、V操作的次序錯誤、重復或遺漏）易讀性差 要了解對于一組共享變量及信號量的操作是否正確，必須通讀整個系統(tǒng)或者并發(fā)程序；管程的引入 1973年，Hoare和Hanson所提出；其基本思想是把信號量及其操作原語封裝在一個對象內部。即：將共享變量以及對共享變量能夠進行的所有操作集中在一個模塊中。3.4.2

管程的基本概念

管程的定義 管程是關于共享資源的數(shù)據結構及一組針對該資源的操作過程所構成的軟件模塊。管程的主要特性模塊化 一個管程是一個基本程序單位，可以單獨編譯；抽象數(shù)據類型 管程是一種特殊的數(shù)據類型，其中不僅有數(shù)據，而且有對數(shù)據進行操作的代碼信息封裝 管程中的外部過程（函數(shù)）實現(xiàn)了某些功能，至于這些功能是怎樣實現(xiàn)的，在其外部則是不可見的；3.4.2

管程的基本概念

管程的的組成名稱：為每個共享資源設立一個管程數(shù)據結構說明：一組局部于管程的控制變量操作原語：對控制變量和臨界資源進行操作的一組原語過程（程序代碼），是訪問該管程的唯一途徑。這些原語本身是互斥的，任一時刻只允許一個進程去調用，其余需要訪問的進程就等待。初始化代碼：對控制變量進行初始化的代碼3.4.2

管程的基本概念

條件變量(condition)

管程提供了一種可以允許多進程安全有效地共享抽象數(shù)據類型的機制，管程實現(xiàn)同步機制由“條件結構”（conditionconstruct）所提供。 為實現(xiàn)進程互斥同步，必須定義一些條件變量，（例如：varnotempty，notfull：condition）。這些條件變量是只能被wait和signal操作所訪問。

3.4.2

管程的基本概念

notfull.wait操作意味著調用該操作的進程將被掛起，另至直一個進程執(zhí)行；

notfull.signal操作僅僅是啟動一個被堵塞的進程，如無堵塞進程則notfull.signal操作相當于空操作，不改變notfull狀態(tài)，這不同于v操作。 若Q堵塞，P執(zhí)行notfulll.Signal,執(zhí)行管程中的喚醒切換方法：P等待Q繼續(xù)，直到Q等待或退出；Q等待P繼續(xù)，直到P等待或退出；3.4.3利用管程解決生產者―消費者問題

建立一個管程PC，它包括兩個過程put（item）和get（item），它們分別執(zhí)行將生產的消息放入緩沖池和從緩沖池取出消息的操作，設置一變量count表示緩沖池已存消息數(shù)目。TypePC=monitorvarin,out,count:integer;buffer:array[0,…,n-1]ofitem;notfull,notempty:condition;procedureentryput(item)beginifcount>=nthennotfull.wait;beffer(in):=nextp;in:=(in+1)modn;count=count+1;ifnotempty.queuethennotempty.signal;end3.4.3利用管程解決生產者―消費者問題procedureentryget(item)beginifcount<=0thennotempty.wait;nextc:=buffer(out);out:=(out+1)modn;count:=count-1;ifnotfull.queuethennotfull.signal;endbeginin:=out:=0;count:=0;end

3.4.3利用管程解決生產者―消費者問題生產者和消費者程序為：producer:beginrepeatproduceaniteminnextp;PC.put(item);untilfalse;endconsumer:beginrepeatPC.get(item);consumetheiteminnextc;untilfalse;end3.4.3利用管程解決生產者―消費者問題3.4.4

利用管程解決讀者-寫者問題信號量的C++描述

classSemaphoreClass{public: SemaphoreClass(LONGcInitialValue); voidP(void); voidV(void);private: HANDLEhSemaphore; LONGcMax;};3.4.4

利用管程解決讀者-寫者問

管程的C++描述classMonitorClass{public: MonitorClass(void); voidMonitorEnter(void); voidMonitorLeave(void); voidMonitorWait(SemaphoreClass hSemCondition, int*lpConditionCount); voidMonitorSignal(SemaphoreClass hSemCondition, int*lpConditionCount);

private: SemaphoreClassMonitorMutex;//Initialvalueis1. SemaphoreClassMonitorUrgent;//Initialvalueis0. int UrgentCount; //Monitorurgentsemaphorecounter.};3.4.4

利用管程解決讀者-寫者問

MonitorClass::MonitorClass(void):MonitorMutex(1),MonitorUrgent(0){ UrgentCount=0;}voidMonitorClass::MonitorEnter(void){ MonitorMutex.P();}3.4.4

利用管程解決讀者-寫者問題voidMonitorClass::MonitorLeave(void){ if(UrgentCount>0) { UrgentCount--; MonitorUrgent.V(); } else { MonitorMutex.V(); }}3.4.4

利用管程解決讀者-寫者問題voidMonitorClass::MonitorWait( SemaphoreClasshSemCondition, int*lpConditionCount){(*lpConditionCount)++;if(UrgentCount>0){ UrgentCount--; MonitorUrgent.V();}else{ MonitorMutex.V();}hSemCondition.P();}3.4.4

利用管程解決讀者-寫者問題voidMonitorClass::MonitorSignal( SemaphoreClasshSemCondition, int*lpConditionCount){if((*lpConditionCount)>0){ (*lpConditionCount)--; UrgentCount++; hSemCondition.V(); MonitorUrgent.P();}}3.4.4

利用管程解決讀者-寫者問

讀者-寫者問題

classReaderWriterClass{public: voidStartReader(void); voidFinishReader(void); voidStartWriter(void); voidFinishWriter(void); ReaderWriterClass(void);private: MonitorClass ReaderWriterMonitor; SemaphoreClass rq,wq; //讀寫等待隊列

intr_count,w_count; //讀寫等待計數(shù)

intreading_count,write_count;};3.4.4

利用管程解決讀者-寫者問

ReaderWriterClass::ReaderWriterClass(void):ReaderWriterMonitor(),rq(0),wq(0){reading_count=0;write_count=0;r_count=0;w_count=0;}3.4.4

利用管程解決讀者-寫者問

voidReaderWriterClass::StartReader(void){ ReaderWriterMonitor.MonitorEnter(); if(write_count>0) { ReaderWriterMonitor.MonitorWait(rq, &r_count); } reading_count++; ReaderWriterMonitor.MonitorSignal(rq, &r_count); ReaderWriterMonitor.MonitorLeave();}3.4.4

利用管程解決讀者-寫者問

voidReaderWriterClass::FinishReader(void){ ReaderWriterMonitor.MonitorEnter(); reading_count--;if(reading_count==0) { ReaderWriterMonitor.MonitorSignal(wq, &w_count); } ReaderWriterMonitor.MonitorLeave();}3.4.4

利用管程解決讀者-寫者問

voidReaderWriterClass::StartWriter(void){ ReaderWriterMonitor.MonitorEnter(); write_count++;if((write_count>1)||(reading_count>0)) { ReaderWriterMonitor.MonitorWait(wq, &w_count); } ReaderWriterMonitor.MonitorLeave();}3.4.4

利用管程解決讀者-寫者問

voidReaderWriterClass::FinishWriter(void){ReaderWriterMonitor.MonitorEnter();write_count--;if(write_count>0) { ReaderWriterMonitor.MonitorSignal(wq, &w_count); } else { ReaderWriterMonitor.MonitorSignal(rq, &r_count); }ReaderWriterMonitor.MonitorLeave();}3.4.4

利用管程解決讀者-寫者問

讀者的活動：r_and_w.StartReader();讀操作；r_and_w.FinishReader();寫者的活動：r_and_w.StartWriter();寫操作；r_and_w.FinishWriter();3.5

進程通信

3.5.1進程通信的類型3.5.2共享存儲器系統(tǒng)3.5.3消息傳遞系統(tǒng)3.5.4管道通信3.5.1進程通信的類型

低級通信和高級通信低級通信：只能傳遞狀態(tài)和整數(shù)值（控制信息），包括進程互斥和同步所采用的信號量和管程機制。優(yōu)點是速度快。缺點是：傳送信息量小：效率低，每次通信傳遞的信息量固定，若傳遞較多信息則需要進行多次通信。編程復雜：用戶直接實現(xiàn)通信的細節(jié)，編程復雜，容易出錯。高級通信：能夠傳送任意數(shù)量的數(shù)據，包括三類：共享存儲器系統(tǒng)，消息傳送系統(tǒng)和管道通信系統(tǒng)。3.5.1進程通信的類型

直接通信和間接通信直接通信：信息直接傳遞給接收方，如管道。在發(fā)送時，指定接收方的地址或標識，也可以指定多個接收方或廣播式地址；在接收時，允許接收來自任意發(fā)送方的消息，并在讀出消息的同時獲取發(fā)送方的地址。間接通信：借助于收發(fā)雙方進程之外的共享數(shù)據結構作為通信中轉，如消息隊列。通常收方和發(fā)方的數(shù)目可以是任意的。3.5.1進程通信的類型

高級通信的特征通信鏈路(communicationlink)：顯式/隱式點對點/多點/廣播單向/雙向有容量（鏈路帶緩沖區(qū)）/無容量（發(fā)送方和接收方需自備緩沖區(qū)）數(shù)據格式：字節(jié)流(bytestream)：各次發(fā)送之間的分界，在接收時不被保留，沒有格式；報文(datagram/message)：各次發(fā)送之間的分界，在接收時被保留，通常有格式（如表示類型），定長/不定長報文，可靠報文/不可靠報文。收發(fā)操作的同步方式發(fā)送進程阻塞、接收進程阻塞發(fā)送進程不阻塞、接收進程阻塞發(fā)送進程不阻塞、接收進程不阻塞3.5.2

共享存儲器系統(tǒng)

基于共享數(shù)據結構的通信方式在這種通信方式中，要求諸進程公用某個數(shù)據結構，進程通過它們交換信息。如在生產者-消費者問題中，就是把緩沖池（有界緩沖區(qū)）這種數(shù)據結構用來作通信的。這種通信方式是低效的，只適用傳送少量的數(shù)據?；诠蚕泶鎯^(qū)的通信方式

為了傳送大量的數(shù)據，在存儲器劃分出一塊共享存儲區(qū)，各進程可以通過對共享存儲區(qū)中的數(shù)據，進行讀寫來進行通信3.5.2

共享存儲器系統(tǒng)

UNIX的共享存儲區(qū) 共享存儲區(qū)是UNIX系統(tǒng)V中通信速度最高的一種通信機制，它包含在進程通信軟件包IPC中。創(chuàng)建或打開共享存儲區(qū)(shmget)： 依據用戶給出的整數(shù)值key，創(chuàng)建新區(qū)或打開現(xiàn)有區(qū)，返回一個共享存儲區(qū)ID。連接共享存儲區(qū)(shmat) 連接共享存儲區(qū)到本進程的地址空間，可以指定虛擬地址或由系統(tǒng)分配，返回共享存儲區(qū)首地址。父進程已連接的共享存儲區(qū)可被fork創(chuàng)建的子進程繼承。拆除共享存儲區(qū)連接(shmdt) 拆除共享存儲區(qū)與本進程地址空間的連接。共享存儲區(qū)控制(shmctl) 對共享存儲區(qū)進行控制。如：共享存儲區(qū)的刪除需要顯式調用shmctl(shmid,IPC_RMID,0)；

3.5.2

共享存儲器系統(tǒng)

進程A進程B

虛空間內存空間虛空間

A正文A數(shù)據

A棧

共享存儲器

B正文

B數(shù)據

B棧3.5.2

共享存儲器系統(tǒng)

UNIX的文件映射mmap：建立進程地址空間到文件或共享存儲區(qū)對象的映射，將文件偏移off起的len字節(jié)映射到進程地址addr處

caddr_tmmap(caddr_taddr,size_tlen,intprot,intflags,intfildes,off_toff);munmap：拆除映射

intmunmap(void*addr,size_tlen);優(yōu)點： 提高效率（消除不必要的數(shù)據拷貝）、 降低復雜性（直接讀寫操作而不必管理緩沖區(qū)）、 可直接將內存的數(shù)據類型記錄在文件上（如指針）3.5.2

共享存儲器系統(tǒng)

WindowsNT的文件映射采用文件映射(filemapping)機制：可以將整個文件映射為進程虛擬地址空間的一部分來加以訪問。在CreateFileMapping和OpenFileMapping時可以指定對象名稱。CreateFileMapping為指定文件創(chuàng)建一個文件映射對象，返回對象指針；OpenFileMapping打開一個命名的文件映射對象，返回對象指針；MapViewOfFile把文件映射到本進程的地址空間，返回映射地址空間的首地址；這時可利用首地址進行讀寫；FlushViewOfFile可把映射地址空間的內容寫到物理文件中；UnmapViewOfFile拆除文件映射與本進程地址空間間映射關系；隨后，可利用CloseHandle關閉文件映射對象；3.5.2

共享存儲器系統(tǒng)

3.5.3

消息傳遞系統(tǒng)

消息傳遞系統(tǒng)分為直接通信方式和間接通信方式兩種。直接通信方式

這是指發(fā)送進程利用OS提供的發(fā)送命令直接把消息發(fā)送給接收進程，并將它掛在接收進程的消息緩沖隊列上。接收進程利用OS提供的接收命令直接從消息緩沖隊列中取得消息。此時要求發(fā)送進程和接收進程都以顯示的方式提供對方的標識符，通常系統(tǒng)提供下述兩條通信原語：

Send(Receiver,message)；Receive(Sender,message)；或(Receive(message))；

直接通信的實例-消息緩沖隊列通信機制。3.5.3

消息傳遞系統(tǒng)

消息緩沖隊列通信機制，首先由美國的Hansan提出，并在RC4O00系統(tǒng)上實現(xiàn)，后來被廣泛應用于本地進程之間的通信中。在這種通信機制中，發(fā)送進程利用send原語，將消息直接發(fā)送給接收進程；接收進程則利用Receive原語接收消息。消息緩沖隊列通信機制中的數(shù)據結構消息緩沖區(qū) 在消息緩沖通信方式中，主要利用的數(shù)據結構是消息緩沖區(qū)。它可描述為：typemessagebuffer=record sender； 發(fā)送者進程標識符 size； 消息長度 text； 消息正文 next； 指向下一個消息緩區(qū)的指針 end3.5.3

消息傳遞系統(tǒng)

PCB中有關通信的數(shù)據項在利用消息緩沖隊列通信機制時，在PCB中應增加的數(shù)據項可描述如下：typeprocesscontrolblock＝record ┊ mq； 消息隊列隊前指針 mutex； 消息隊列互斥信號量 sm； 消息隊列資源信號量

┊ end3.5.3

消息傳遞系統(tǒng)

發(fā)送原語procduresend（receiver,a）

begingetbuf(a.size,i);i.sender:=a.sender:i.size:=a.size;i.text:=a.text;i.next:=();getid(PCBset,receiver.j);wait(j.mutex);insert(j.mq,i);signal(j.mutex);signal(j.sm);end3.5.3

消息傳遞系統(tǒng)

接收原語procedurereceive(b)beginj:=internalname:wait(j.sm);wait(j.mutex);remove(j.mq,i);signal(j.mutex);b.sender:=i.sender:b.size:=i.size;b.text:=i.text:end3.5.3

消息傳遞系統(tǒng)3.5.3

消息傳遞系統(tǒng).

mutexsmmq

………...send(B,a);sender:Asize:13text:Howareyou?Nextsend:Asize:13text:Howareyou?Next:sender:Asize:5text:HelloNext:

sender:Asize:13text:Howareyou?Next:0sender:Asize:5text:HelloNext:..receive(b);sender:Asize:5text:Hello 系統(tǒng)管理的－組緩沖區(qū)進程A進程BPCB進程B3.5.3

消息傳遞系統(tǒng)

UNIX系統(tǒng)消息機制 UNIX系統(tǒng)V的進程通信軟件包IPC提供了消息機制。消息機制的數(shù)據結構

UNIX系統(tǒng)將消息分為消息首部和消息數(shù)據兩部分。消息首部 在消息首部中記錄有消息的類型、大小、指向消息數(shù)據區(qū)的指針、消息隊列的鏈接指針等。消息隊列頭表 消息隊列頭表的每一表項是作為一個消息隊列的消息頭。在消息頭中包含了指向消息隊列中第一個消息的指針和指向最后一個消息指針，隊列中消息的數(shù)目、隊列中消息數(shù)據的總字節(jié)數(shù)等。3.5.3

消息傳遞系統(tǒng)

UNIX消息隊列APImsgget依據用戶給出的整數(shù)值key，創(chuàng)建新消息隊列或打開現(xiàn)有消息隊列，返回一個消息隊列ID；msgsnd發(fā)送消息；msgrcv接收消息，可以指定消息類型；沒有消息時，返回-1；msgctl對消息隊列進行控制，如刪除消息隊列；3.5.3

消息傳遞系統(tǒng)

隊列0..隊列i消息首部msgh0消息緩沖區(qū)0消息首部msgh8消息緩沖區(qū)8消息首部msgh