第四章 互斥與同步

第四章同步與通信4.1概論4.2臨界段4.3互斥4.4信號量4.5管程4.6進(jìn)程間的通信4.7線程的同步與通信4.8案例：UNIX的進(jìn)程同步與通信4.1概述系統(tǒng)中諸進(jìn)程之間協(xié)同合作關(guān)系直接制約關(guān)系（同步）：指完成同一任務(wù)的伙伴進(jìn)程，因需要在某些位置上協(xié)調(diào)它們的工作而等待、傳遞信息所產(chǎn)生的制約關(guān)系。如：計(jì)算進(jìn)程與輸入進(jìn)程共享一個(gè)緩沖區(qū)的情況。間接制約關(guān)系（互斥）：即進(jìn)程間因相互競爭使用獨(dú)占型資源（互斥資源）所產(chǎn)生的制約關(guān)系。4.2臨界區(qū)例：假設(shè)兩個(gè)進(jìn)程P1，P2分別在C1和C2兩個(gè)處理器上運(yùn)行，異步地對公共變量X進(jìn)行加1操作。假設(shè)兩個(gè)進(jìn)程的推進(jìn)順序如下：（1）P1：…，R1=X；R1=R1+1；X=R1；…P2：….R2=X；R2=R2+1；X=R2；…（2）P1：…，R1=X；R1=R1+1；X=R1；…P2：…，R2=X；R2=R2+1；X=R2；…問：設(shè)X的初值為V，以上兩種情況下，X的值最后分別是多少？（1）：V+1；（2）：V+2；對公共變量的讀寫操作必須互斥地進(jìn)行。例1：同步問題如果進(jìn)程P1執(zhí)行S1，S3，進(jìn)程P2執(zhí)行S2，則P1在執(zhí)行S3之前必須等待P2執(zhí)行完S2。S1S3S2例2：互斥問題

P1、P2兩進(jìn)程使用同一打印機(jī)。如果不互斥使用會交叉輸出Entrycodeexitcode使用打印機(jī)P1Entrycodeexitcode使用打印機(jī)P24.2臨界區(qū)（criticalsection)一、基本概念

進(jìn)程同步與互斥的主要任務(wù)就是保證多個(gè)并發(fā)執(zhí)行的進(jìn)程之間能有效地合作并共享系統(tǒng)資源，使程序的執(zhí)行具有可再現(xiàn)性。

1.臨界資源（criticalresource）

臨界資源是指在一段時(shí)間內(nèi)只允許一個(gè)進(jìn)程訪問的資源。它可是某個(gè)變量或某種硬件資源（如：打印機(jī)，公共變量等。）

2.臨界區(qū)（criticalsection，也稱臨界段)臨界區(qū)：是指進(jìn)程地址空間中訪問臨界資源的那段代碼。一個(gè)進(jìn)程在臨界區(qū)中運(yùn)行時(shí)，其他進(jìn)程不能進(jìn)入臨界區(qū)。進(jìn)入?yún)^(qū)：是指臨界區(qū)之前，檢查臨界資源閑忙標(biāo)志的那段代碼。退出區(qū)：在臨界區(qū)后面，將臨界資源釋放的那段代碼。如：whiletrue{…

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

臨界區(qū)

（如例中P1，P2的：R=X；R=R+1；X=R；）

退出區(qū)

…}競爭條件：多各進(jìn)程或線程在讀寫一個(gè)公共數(shù)據(jù)時(shí)，結(jié)果依賴于它們執(zhí)行的相對時(shí)間，這種情形稱做競爭。饑餓：一個(gè)可以運(yùn)行的進(jìn)程無限期地被調(diào)度器忽視，不能被調(diào)度的狀態(tài)。死鎖：兩個(gè)或兩個(gè)以上進(jìn)程因互相等待，使得每個(gè)進(jìn)程都不能繼續(xù)向前推進(jìn)的狀態(tài)。三個(gè)概念

進(jìn)程的交互知道進(jìn)程關(guān)系一個(gè)進(jìn)程對其他進(jìn)程的影響潛在的控制問題進(jìn)程之間不知道對方存在競爭一個(gè)進(jìn)程結(jié)果與其他進(jìn)程的活動無關(guān)互斥、死鎖、饑餓間接知道對方存在（共享資源）共享合作一個(gè)進(jìn)程的結(jié)果可能依賴于從其他進(jìn)程獲得的信息互斥、死鎖、饑餓、數(shù)據(jù)一致性直接知道對方存在（知道對方PID）通信合作一個(gè)進(jìn)程的結(jié)果可能依賴從其他進(jìn)程獲得的信息死鎖、饑餓空閑讓進(jìn)：任何時(shí)間臨界區(qū)內(nèi)只能有一個(gè)進(jìn)程。忙則等待。有限等待：等待有限時(shí)間，避免“死等”發(fā)生。讓權(quán)等待：當(dāng)正在執(zhí)行的進(jìn)程自己不能進(jìn)入臨界區(qū)時(shí)，應(yīng)立即釋放CPU。二、進(jìn)程同步遵循的原則

進(jìn)入臨界段之前要申請，獲得批準(zhǔn)方可進(jìn)入退出臨界段之后要聲明，以便其他進(jìn)程進(jìn)入解決臨界段問題的軟件算法必須遵循：準(zhǔn)則1：不能虛設(shè)硬件指令或假設(shè)處理機(jī)數(shù)目。準(zhǔn)則2：不能假設(shè)n個(gè)進(jìn)程的相對速度。準(zhǔn)則3：當(dāng)一個(gè)進(jìn)程未處于其臨界段時(shí)，不應(yīng)阻止其它進(jìn)程進(jìn)入臨界段。準(zhǔn)則4：當(dāng)若干進(jìn)程欲進(jìn)入臨界段時(shí)，應(yīng)能在有限時(shí)間內(nèi)選出一個(gè)進(jìn)程進(jìn)入其臨界段。4.3互斥實(shí)現(xiàn)互斥的軟件算法互斥也是一種同步，它使異步事件能按照要求的時(shí)序進(jìn)行，以使各合作進(jìn)程能協(xié)調(diào)一致地工作。1.互斥的軟件解決方法(1)用標(biāo)志位flag[i]來標(biāo)識進(jìn)程Pi是否在臨界區(qū)中執(zhí)行。Pi:

while(true){…

while(flag[j]);//執(zhí)行空語句等待

flag[i]=true;

執(zhí)行csi

//進(jìn)程Pi的臨界區(qū)

flag[i]=false;//釋放臨界資源

…}4.3互斥問：該方法是否遵循“忙則等待”的原則？不滿足互斥要求：當(dāng)flag[]初值為0，兩進(jìn)程同時(shí)執(zhí)行while語句時(shí)。1.互斥的軟件解決方法(2)設(shè)一個(gè)共享的整型變量turn（0，1）表示輪流進(jìn)入，turn=i表示pi可以進(jìn)入臨界區(qū)。Pi:While(true){…while(turn!=i);//執(zhí)行空語句等待執(zhí)行csi;//臨界區(qū)turn=j;//(j!=i)釋放臨界資源…}不能滿足空閑讓進(jìn)的原則！可能出現(xiàn)turn=j,但pj不在臨界區(qū)。(3)Dekker的解決方法初始化：flag[i]=flag[j]=false;turn可以為i或j；turn=j;flag[i]=false；whileturn==jdoskip；flag[i]=true；whileflag[j]dobeginflag[i]=false；flag[i]=true；end;ifturn==jthenCriticalsectionDekker算法

OK！Pi:2.互斥的硬件解決方法(1)中斷屏蔽方法/中斷禁用(單處理機(jī))當(dāng)一個(gè)進(jìn)程正在執(zhí)行臨界區(qū)代碼時(shí)，關(guān)閉一切中斷。（只適應(yīng)單處理機(jī)系統(tǒng)why?）(2)硬件指令的方法（多處理機(jī)）TS（Test-andSet）指令Swap指令不存在主從關(guān)系的多處理器之間沒有支持互斥的中斷機(jī)制。例1：中斷屏蔽方法(單處理機(jī))Parbegin

A(amount){//存款

disableInterrupt();R1=balance; R2=amount;R1=R1+R2;balance=R1;

enableInterrupt();

};B(amount){//取款

disableInterrupt();R1=balance;R2=amount;R1=R1-R2;balance=R1;

enableInterrupt();

};Parend;TS指令（或TSL）boolTS(boolflag){TS=flag;flag=true;//關(guān)閉臨界區(qū)}硬件指令的方法Swap指令voidSwap(bool

a,b){booltemp;temp=a;a=b;b=temp;}TS和Swap都是一條專用的機(jī)器指令，功能相同，因此在一個(gè)系統(tǒng)中只需要一種。原理：在硬件級別上，對存儲單元的訪問排斥對相同單元的其他訪問。while(true){while(TS(lock));//忙等待執(zhí)行csilock=false;……}硬件指令要求在一個(gè)指令周期內(nèi)完成，公共數(shù)據(jù)的完整性和正確性不會受到中斷的影響。但該類指令存在“忙等待”的缺點(diǎn)。使用硬件指令互斥時(shí)臨界區(qū)不宜過長，否則影響系統(tǒng)效率。用TS硬件指令方法實(shí)現(xiàn)互斥設(shè)Lock為全局布爾變量，利用Test&Set指令，即可實(shí)現(xiàn)對臨界區(qū)的加鎖與解鎖：使用Swap指令實(shí)現(xiàn)互斥設(shè)Lock為全局布爾變量（初值為假），每個(gè)進(jìn)程設(shè)一個(gè)局部布爾變量Key。利用Swap指令，可實(shí)現(xiàn)對臨界區(qū)的加鎖與解鎖。Repeatkey=true;repeatSwap(lock,key);untilkey=false;

criticalsectionlock=false;non-criticalsectionUntilfalse;1.什么是信號量？信號量是荷蘭計(jì)算機(jī)科學(xué)家Dijkstra于1965年提出的一種有效的進(jìn)程同步工具，可分為：整型信號量、結(jié)構(gòu)型信號量、信號量集等。信號量是實(shí)現(xiàn)進(jìn)程同步的一種變量。2.二元信號量和一般信號量二元信號量：取值僅為“0”或“1”，主要用作互斥同步變量；一般信號量：初值為物理資源的總數(shù)，用于進(jìn)程間的協(xié)作同步問題。4.4信號量3.整型信號量（1）整型信號量是一個(gè)整型變量,如S，和兩個(gè)標(biāo)準(zhǔn)的原子操作wait(s)和signal(s)對S進(jìn)行減1和增1操作，實(shí)現(xiàn)對臨界資源的訪問進(jìn)行控制。這兩個(gè)操作習(xí)慣上分別被稱為P操作和V操作。（2）同步原語的兩種實(shí)現(xiàn)方式：忙等待方式阻塞等待方式4.4信號量信號量必須置一次初值且只能置一次初值。信號量的初值不能為負(fù)數(shù)，且對信號量只能執(zhí)行P、V操作!!int(semaphore)S=N;//N為同類資源的總數(shù)

Wait(s):while(S≤0）;//執(zhí)行空語句等待,

//等待的含義是什么？

S=S-1;

Signal(s):S=S+1;

(4)

整型信號量的忙等待同步原語intS=1；//定義一個(gè)信號量

Wait(S):while(S==0）;

//執(zhí)行空語句等待

S=S-1;Signal(S):S=S+1;S為一二元整型信號量S初值為1（5）二元整型信號量的忙等待同步原語：整型信號量機(jī)制是一種“忙等待”方式，存在較大的CPU浪費(fèi)！Why?如何改進(jìn)?。?010研究生試題（互斥）27、進(jìn)行P0和P1的共享變量定義及其初值為（D）booleanflag[2]；intturn=0；flag[0]=FALSE；flag[1]=FALSE；若進(jìn)行P0和P1訪問臨界資源的類C代碼實(shí)現(xiàn)如下：Voidp0()//進(jìn)程p0 {while(TURE){ Flag[0]=TURE;turn=1; While(flag[1]&&(turn==1));

臨界區(qū)：Flag[0]=FALSE;} } Voidp1()//進(jìn)程p1 {while(TURE){ Flag[1]=TURE;turn=0; While(flag[0]&&(turn==0));

臨界區(qū)：Flag[1]=FALSE;} } 則并發(fā)執(zhí)行進(jìn)程P0和P1時(shí)產(chǎn)生的情況是：A：不能保證進(jìn)程互斥進(jìn)入臨界區(qū)，會出現(xiàn)“饑餓”現(xiàn)象B：不能保證進(jìn)程互斥進(jìn)入臨界區(qū)，不會出現(xiàn)“饑餓”現(xiàn)象C：能保證進(jìn)程互斥進(jìn)入臨界區(qū)，會出現(xiàn)“饑餓”現(xiàn)象D：能保證進(jìn)程互斥進(jìn)入臨界區(qū)，不會出現(xiàn)“饑餓”現(xiàn)象答案：D。

在結(jié)構(gòu)型信號量機(jī)制中定義了兩個(gè)變量單元，一是用于表示臨界資源數(shù)目的整型變量value,另一個(gè)是等待進(jìn)入臨界區(qū)的進(jìn)程所組成的阻塞隊(duì)列的指針L（指向PCB隊(duì)列的指針）。4.結(jié)構(gòu)型信號量（阻塞等待方式）（1）一般結(jié)構(gòu)型信號量的數(shù)據(jù)結(jié)構(gòu)：

typedef

Struct{intvalue;//Value的初值為系統(tǒng)中該類臨界資源的總數(shù)目

strcutPCB*L;//等待該臨界資源的進(jìn)程阻塞隊(duì)列的指針

}semaphore;wait(semaphores){s.value--;if(s.value<0)//代表的含義是什么？

{Insert(caller,s.L);block(caller);}}一般記錄型信號量的同步原語：記錄型信號量機(jī)制能有效地實(shí)現(xiàn)遵守“讓權(quán)等待”原則。signal(semaphores){s.value++;if(s.value≤0)//Why？

{Remove(s.L,id)wakeup(id);}}（1）二元記錄型信號量的數(shù)據(jù)結(jié)構(gòu)：

typedef

Struct{intvalue;//Value的值為0或1

strcutPCB*L;

//等待該臨界資源的進(jìn)程阻塞隊(duì)列的指針

}semaphore；4.結(jié)構(gòu)型信號量（阻塞等待方式）課堂練習(xí)：請大家自己設(shè)計(jì)二元結(jié)構(gòu)型信號量的P，V操作原語。wait(semaphores){if（s.value==1）s.value=0;else{Insert(caller,s.L);block(caller);}}signal(semaphores){if（s.L==NULL）

s.value=1;else{Remove(s.L,id)wakeup(id);}}二元信號量上的同步元語用于進(jìn)程之間的互斥同步情況一般信號量上的同步元語用于進(jìn)程間互相合作的同步情況對信號量進(jìn)行操作的代碼段用原語實(shí)現(xiàn).同步原語只能互斥使用（why?）.（對原語的互斥使用可以使用硬件指令的方法實(shí)現(xiàn)）同步原語在執(zhí)行過程中具有整體性，不能被中斷。

5.同步原語(1)同步原語使用特性例：使用中斷屏蔽實(shí)現(xiàn)對P（s）和V（s）的原子性P（s）{

DisableInterrupt();while（s≤0）do{

enableInterrupt();

DisableInterrupt(); }

s=s-1；

enableInterrupt(); } V（s）{

DisableInterrupt(); s=s+1；

enableInterrupt();}Wait(s):while(TS(lock));while(s≤0);s=s-1;lock=false;Signal(s):

while(TS(lock));s=s+1;//同步原語代碼lock=false;同步原語代碼(2)用硬件指令實(shí)現(xiàn)同步原語的互斥:例：使用硬件指令實(shí)現(xiàn)對P（s）和V（s）的原子性用P、V操作解決進(jìn)程間互斥問題P(mutex)V(mutex)P1P2P3互斥區(qū)P(mutex)P(mutex)V(mutex)V(mutex)6.用信號量實(shí)現(xiàn)進(jìn)程間的互斥例1：設(shè)兩個(gè)可以并發(fā)執(zhí)行的進(jìn)程process1和process2，在執(zhí)行的過程中需要訪問某臨界資源，為此我們設(shè)一整型互斥信號量mutex,請看下面的類代碼：Semaphoremutex=1;intX=0；{parbegainprocess1:{…

wait(mutex);

X=X+1;

signal(mutex);

…}process2:{…

wait(mutex);

printf(“%d”,X);

signal(mutex);

…

}

parend注：Wait操作和signal操作必須成對出現(xiàn)?。±?：問題：在測量控制系統(tǒng)中，某數(shù)據(jù)采集進(jìn)程把所采集的數(shù)據(jù)送入一個(gè)單緩沖區(qū)中；某計(jì)算進(jìn)程從該單緩沖區(qū)取出數(shù)據(jù)進(jìn)行計(jì)算。試寫出利用信號量機(jī)制實(shí)現(xiàn)兩者共享緩沖區(qū)的同步算法。單緩沖數(shù)據(jù)采集進(jìn)程Get()計(jì)算進(jìn)程Compute()臨界資源思考：為解決Get()和Compute()兩個(gè)進(jìn)程之間的同步問題，應(yīng)設(shè)置幾個(gè)信號量，其初值各應(yīng)置為幾？若有多個(gè)Get()進(jìn)程和多個(gè)Compute()，則又應(yīng)如何設(shè)置信號量？為什么？設(shè)兩個(gè)信號量：empty和full。

empty表示緩沖區(qū)是否為空；full表示緩沖區(qū)中是否有數(shù)據(jù)。intempty=1,full=0;main(){cobegin

getdata();compute();coend}getdata(){while(采集工作未完)

采集一個(gè)數(shù)據(jù)；

P(empty);將數(shù)據(jù)送入緩沖區(qū)；

V(full);}compute(){while(計(jì)算工作未完)

P(full);從緩沖區(qū)中取一個(gè)數(shù)據(jù)；V(empty);進(jìn)行數(shù)據(jù)計(jì)算；}思考題：如何用P.V操作解決司機(jī)與售票員的同步問題？司機(jī)進(jìn)程：while(true){啟動車輛正常駕駛到站停車}…售票員進(jìn)程：while(true){關(guān)門售票開門}…1.售票員操作的規(guī)則是只有司機(jī)停車后，售票員才能開門讓乘客下車；

2.司機(jī)操作的規(guī)則是只有售票員關(guān)門后，司機(jī)才能啟動開始行駛汽車。

driver(){while(T){

P(close);

啟動行車;

到站停車;

V(stop);}}busman(){while(T){

關(guān)車門;

V(close);

售票;

P(stop);

開門上下乘客;}}問：close,stop的初值分別應(yīng)為多少？7.經(jīng)典進(jìn)程同步問題示例消費(fèi)者生產(chǎn)者（1）生產(chǎn)者-消費(fèi)者問題同步問題：P進(jìn)程不能往“滿”的緩沖區(qū)中放產(chǎn)品，設(shè)置信號量為emptyQ進(jìn)程不能從“空”的緩沖區(qū)中取產(chǎn)品，設(shè)置信號量fullP：Q：while(true){while(true){

生產(chǎn)一個(gè)產(chǎn)品;P(full);

P(empty);從緩沖區(qū)取產(chǎn)品送產(chǎn)品到緩沖區(qū);V(empty);

V(full);消費(fèi)產(chǎn)品;}}單個(gè)生產(chǎn)者和單個(gè)消費(fèi)者情況：semaphoreempty=1,full=0;多個(gè)緩沖區(qū)的生產(chǎn)者和消費(fèi)者情況:semaphoreempty=n,full=0;P：

i=0;

while(true){

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

P(empty);

往Buffer[i]放產(chǎn)品;

V(full);

i=(i+1)%n;};Q：

j=0;while(true){

P(full);

從Buffer[j]取產(chǎn)品;

V(empty);

消費(fèi)產(chǎn)品;j=(j+1)%n;};分析：根據(jù)題意，我們設(shè)3個(gè)信號量：mutex、empty和full。其中，mutex為互斥信號量，empty和full為資源信號量，分別表示緩沖池中，空緩沖區(qū)的數(shù)目和滿緩沖區(qū)的數(shù)目。用信號量方法解決的算法描述見下：c1p1pmck12…np2c2……pici緩沖池多個(gè)緩沖區(qū)、多個(gè)生產(chǎn)者和多個(gè)消費(fèi)者情況:

Semaphoremutex=1;empty=n;full=0;parbeginPi:{do{

生產(chǎn)一數(shù)據(jù)

wait(empty);

wait(mutex);

分配一空緩沖區(qū)并調(diào)整空緩沖隊(duì)列指針的臨界區(qū)；

signal(mutex);

向空緩沖區(qū)中裝入數(shù)據(jù)；

signal(full);}while(true)}Qj:{do{

wait(full);

wait(mutex);

分配給滿緩沖區(qū)并調(diào)整滿緩沖隊(duì)列指針的臨界區(qū)；

signal(mutex);

消費(fèi)數(shù)據(jù)；

signal(empty);

…}while(true)}parend是否要考慮多個(gè)wait操作的執(zhí)行順序？Wait和signal若丟掉一個(gè)會出現(xiàn)什么情況？Qj：

j=0;while(true){

P(full);

P(mutex);

從Buffer[j]取產(chǎn)品;

V(mutex);

V(empty);

消費(fèi)產(chǎn)品;j=(j+1)%n;};另一種描述方式：Pi：

i=0;

while(true){

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

P(empty);

P(mutex);

往Buffer[i]放產(chǎn)品;

V(mutex);

V(full);

i=(i+1)%n;};有錯(cuò)誤？若顛倒兩個(gè)P操作的順序？(參考教材P58)注意：應(yīng)先考慮資源信號量，后考慮互斥信號量。Why?pqffffeee如果緩沖池設(shè)置成如下情況，需要設(shè)置幾個(gè)信號量？每個(gè)信號量的作用是什么？思考題：1.假設(shè)桌子上有一個(gè)盤子，可以放一個(gè)水果。父親總是放蘋果到盤子中，而母親則總是放香蕉到盤子中；一個(gè)兒子專等吃盤中的香蕉，一個(gè)女兒專等吃盤中的蘋果。請P、V操作實(shí)現(xiàn)上述問題。Main(){int

empty=1;apple=0;banana=0;ParbeginFather();Mother();Son();Daughter();Parend}Father(){do{…

wait(empty);

放蘋果；

signal(apple);}while(true);}dauthter(){do{…

wait(banana);

取蘋果；

signal(empty);吃蘋果；}while(true);}mother(){do{…

wait(empty);

放香蕉；

signal(banana);}While(true);}son(){do{…

wait(banana);

取香蕉；

signal(empty);吃香蕉；}while(true);}2009研究生試題（互斥與同步）45.（7分）：三個(gè)進(jìn)程p1,p2,p3互斥使用一個(gè)包含N（N>0）個(gè)單元的緩沖區(qū)，p1每次用produce()生成一個(gè)正整數(shù)并用put()送入緩沖區(qū)一個(gè)空單元中；p2每次用getodd從緩沖區(qū)中取一個(gè)奇數(shù)，并用countodd

（）統(tǒng)計(jì)奇數(shù)個(gè)數(shù)；p3每次用geteven從緩沖區(qū)中取一個(gè)偶數(shù)，并用counteven

（）統(tǒng)計(jì)偶數(shù)個(gè)數(shù)；請用信號量機(jī)制實(shí)現(xiàn)這三個(gè)進(jìn)程之間的同步與互斥活動，并說明所定義的信號量的含義。要求用偽代碼描述。設(shè)四個(gè)信號量:semaphoreodd=0,even=0;empty=N;mutex=1ParbeginP1:{X=prodeuce();P(empty);P(mutex);put();if(X%2==0)V(even);elseV(odd);V(mutex);}P3:{P(even);P(mutex);geteven();counteven=counteven+1V(mutex);V(empty);}P2:{P(odd);P(mutex);geteven();countodd=countodd+1V(mutex);V(empty);}Parend（2）讀-寫問題有兩組并發(fā)進(jìn)程:

讀者和寫者,共享一組數(shù)據(jù)區(qū)要求：允許多個(gè)讀者同時(shí)執(zhí)行讀操作不允許讀者、寫者同時(shí)操作不允許多個(gè)寫者同時(shí)操作第一類：讀者優(yōu)先如果讀者來：1）無讀者、寫者，新讀者可以讀2）有寫者等，但有其它讀者正在讀，則新讀者也可以讀3）有寫者寫，新讀者等如果寫者來：1）無讀者，新寫者可以寫2）有讀者，新寫者等待3）有其它寫者，新寫者等待讀者：

while(true){

P(mutexcount);

readcount++;if(readcount==1)P(rw);

V(mutexcount);

讀

P(mutexcount);

readcount--;if(readcount==0)V(rw);

V(mutexcount);}寫者：

while(true){

P(rw);

寫

V(rw);};Semaphoremutexcount=1,rw=1;//mutexcount實(shí)現(xiàn)對讀者計(jì)數(shù)變量的互斥控制，rw實(shí)現(xiàn)對讀、寫操作的互斥控制。條件：1）多個(gè)讀者可以同時(shí)進(jìn)行讀2）寫者必須互斥（只允許一個(gè)寫者寫，也不能讀者寫者同時(shí)進(jìn)行）3）寫者優(yōu)先于讀者（一旦有寫者，則后續(xù)讀者必須等待，喚醒時(shí)優(yōu)先考慮寫者）第二類：寫者優(yōu)先讀者：while(true){

P(write)

P(mutexcount);

readcount++;if(readcount==1)P(rw);

V(mutexcount);

V(write);

讀

P(mutexcount);

readcount--;if(readcount==0)V(rw);

V(mutexcount);}寫者：

while(true){

P(write)

P(rw);

寫

V(rw);

V(write)};利用write封鎖后續(xù)讀者，達(dá)到提高寫者優(yōu)先級的目的！！Semaphoremutexcount=1,rw=1，write=1;(1)結(jié)構(gòu)型信號量(一般信號量)的物理含義：S>0表示有S個(gè)資源可用S=0表示無資源可用S<0則|S|表示S等待隊(duì)列中的進(jìn)程個(gè)數(shù)8.P.V操作討論P(yáng)(S):表示申請一個(gè)資源V(S)表示釋放一個(gè)資源。信號量的初值應(yīng)該大于等于0(2)P.V操作必須成對出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作?；コ庑盘柫康腜操作和V操作在同一進(jìn)程成對出現(xiàn)。資源信號量用于同步操作時(shí)，則不在同一進(jìn)程中成對出現(xiàn)。兩個(gè)P操作在一起，P操作的順序至關(guān)重要：資源信號量的P操作在互斥信號量的P操作前，V操作的順序無關(guān)緊要。8.P.V操作討論(3)P.V操作的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：簡單，而且表達(dá)能力強(qiáng)（用P.V操作可解決任何同步互斥問題）缺點(diǎn)：不夠安全。P.V操作使用不當(dāng)會出現(xiàn)死鎖，遇到復(fù)雜同步互斥問題時(shí)實(shí)現(xiàn)復(fù)雜。若A、B兩進(jìn)程共享數(shù)據(jù)D和E。A、B同步過程中的P、V操作描述如下：（semaphoreDmutex=1,Emutex=1;）ProcessA:{…Wait(Dmutex);…①Wait(Emutex);….③

…Signal(Emutex);Signal(Dmutex);…}ProcessB:{…Wait(Emutex);….②Wait(Dmutex);….④

…Signal(Dmutex);Signal(Emutex);…}問題：若A、B按所標(biāo)注的序號執(zhí)行，結(jié)果如何？9.信號量集機(jī)制如果并發(fā)執(zhí)行的進(jìn)程在執(zhí)行的過程中，需要互斥訪問多個(gè)不同類的臨界資源，需要設(shè)置多個(gè)信號量。為了更好地解決多個(gè)臨界資源的互斥問題，引入了信號量集機(jī)制。（1）AND型信號量集機(jī)制（一次性分配資源）

原理：將進(jìn)程在運(yùn)行中所需要的臨界資源一次性全部分配給該進(jìn)程，如果有一個(gè)資源不能到位，所有其它資源也都將不再分配給該進(jìn)程。用完后所有的臨界資源一次性釋放。4.4信號量Swait(S1,S2,…Sn){if(S1≥1andS2≥1and…andSn≥1)for(i=1;i≤n；i++)Si=Si-1;else把該進(jìn)程插入相應(yīng)的等待隊(duì)列。

}P、V操作的類代碼如下：Ssignal(S1,S2,…Sn){for(i=1;i≤n；i++)Si=Si+1;

把相關(guān)的等待Si的進(jìn)程從阻塞隊(duì)列轉(zhuǎn)入就緒隊(duì)列，等待調(diào)度。}（2）一般“信號量集”機(jī)制

一般信號量集機(jī)制是針對那些一次申請多個(gè)臨界資源，而且對某類臨界資源的需求可能不止一個(gè)的進(jìn)程之間的互斥情況。P、V操作的類代碼如下：4.4信號量ti表示i類資源的下限值,di表示某進(jìn)程申請的第i類資源的數(shù)目，si的初值應(yīng)設(shè)為系統(tǒng)中i類資源的總數(shù)目。Swait(s1,t1,d1;…;sn,tn,dn){if(s1≥t1and…and

sn≥tn)for(i=1;i≤n;i++)

si=si-di;else把該進(jìn)程插入相應(yīng)的等待隊(duì)列。}Ssignal(s1,d1;…;sn,dn)

{for(i=1;i≤n;i++)

si=si+di;

把等待si的進(jìn)程從等待隊(duì)列移入就緒隊(duì)列，等待調(diào)度。}一般“信號量集”機(jī)制請大家考慮Swait（s,d,d,)、Swait

（s,1,1)和Swait（s,1,0)三種情況。用AND解決生產(chǎn)者-消費(fèi)者問題parbeginproducer:{do{

生產(chǎn)一數(shù)據(jù)放入nextp

…

Swait(empty,mutex);

buffer(in)=nextp;in=(in+1)modn;

Ssignal(mutex,full);}while(true)}用AND解決生產(chǎn)者-消費(fèi)者問題comuser:{do{

…

Swait(full,mutex);

nextc=buffer(out);out=(out+1)modn;

Ssignal(mutex,empty);}while(true)}parend課堂練習(xí)：請用信號量集機(jī)制實(shí)現(xiàn)下圖程序之間的前趨關(guān)系：p1p2p3p4p5思考題2在南大和天大之間有一條彎曲的小路，其中從S到T一段路每次只允許一輛自行車通過，但中間有一個(gè)小的“安全島”M（同時(shí)允許兩輛自行車停留），可供兩輛自行車已從兩端進(jìn)入小路情況下錯(cuò)車使用，如圖所示。試用P、V操作設(shè)計(jì)相應(yīng)的過程使來往的自行車均可順利通過。MSKLT天津大學(xué)南開大學(xué)分析：Main(){S=1；T=1；//S為南開方向的互斥信號量,T為天大方向的互斥信號量SK=1；LT=1；//兩個(gè)路段都只允許一輛自行車通過ParbeginNanKai();TianDa();Parend}NanKai(){P(S);P(SK);通過SK;進(jìn)入M；V（SK）；P（LT）；通過（LT）；V（LT）；V（S）；}TianDa(){P(T);P(LT);通過LT;進(jìn)入M；V（LT）；P（SK）；通過（SK）；V（SK）；V（T）；}4.5管程一、管程(monitor)定義

管程可定義為：一組相關(guān)的數(shù)據(jù)結(jié)構(gòu)和過程。管程中定義的過程能夠改變管程中的數(shù)據(jù)和同步進(jìn)程。二、管程的結(jié)構(gòu)

管程有三部分組成：管程內(nèi)的共享變量說明，管程中定義的過程和初始的賦值語句。語法如下：

type管程名=monitor

變量說明過程說明（procedure過程名（…）{…}

…//一組過程

{

賦初值的語句}三、管程的基本特性局部于管程的數(shù)據(jù)只能被管程內(nèi)的過程訪問；一個(gè)進(jìn)程只有調(diào)用管程內(nèi)的過程才能進(jìn)入管程，訪問管程內(nèi)的共享數(shù)據(jù)；每次只允許一個(gè)進(jìn)程進(jìn)入管程執(zhí)行它的某個(gè)內(nèi)部過程。四、管程變量

在管程中引入條件變量condition來區(qū)分等待原因的不同，描述格式為condition:x；對條件變量的P、V操作可表示為：x.wait，x.signal。其中，x.wait操作將調(diào)用該過程的進(jìn)程掛起阻塞，并加入到x的掛起阻塞隊(duì)列中；x.signal選擇一個(gè)在條件變量x上被阻塞掛起的進(jìn)程恢復(fù)，若沒有，該操作無效。4.5管程五、用管程實(shí)現(xiàn)生產(chǎn)者——消費(fèi)者進(jìn)程之間的同步4.5管程typepc=monitor//定義一個(gè)管程int

in,out,count;itembuffer[n];conditionnotfull,notempty；管程中的局部變量producerput(item)//放數(shù)據(jù)

{itemnextp;if(count==n)//所有緩沖區(qū)為滿緩沖區(qū)

notfull.wait;//等待空緩沖區(qū)

buffer(in)=nextp;in=(in+1)modn;count=count+1;if(full隊(duì)列不為空)notempty.signal;

//喚醒等待滿緩沖區(qū)隊(duì)列中的進(jìn)程}count定義滿緩沖區(qū)的數(shù)量Procedureget(item)//取數(shù)據(jù)

{itemnextc;if(count==0)//所有緩沖區(qū)為空緩沖區(qū)

notempty.wait;//等待一個(gè)裝滿數(shù)據(jù)的緩沖區(qū)

nextc=buffer(out);out=(out+1)modn;count=count-1;if（empty隊(duì)列不為空）notfull.signal}//喚醒等待空緩沖區(qū)隊(duì)列中的進(jìn)程{in=0;out=0;count=0;}//管程變量初始化直接用管程來同步生產(chǎn)者——消費(fèi)者問題。

Consumer:{do{

pc.get(item);

消費(fèi)itemwhile(true);}注：每次只允許一個(gè)進(jìn)程進(jìn)入管程！Producer:{do{

生產(chǎn)一信息item;

pc.put(item);}while(true)}管程通過條件變量實(shí)現(xiàn)對進(jìn)程的同步！

4.6進(jìn)程通信

進(jìn)程之間的通信是為了實(shí)現(xiàn)進(jìn)程之間的信息交換，根據(jù)交換信息量的多少，進(jìn)程之間的通信方式可分為兩種：低級通信和高級通信。低級通信傳送的信息量少，主要用于控制信息的傳送；而高級通信是指進(jìn)程間大批量的數(shù)據(jù)交換。1.進(jìn)程通信的類型(1)共享存儲器系統(tǒng)的通信基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式（如公用數(shù)據(jù)結(jié)構(gòu)，只適合傳遞少量數(shù)據(jù)，低級）基于共享存儲器的通信方式（如公共內(nèi)存塊，高級）(2)消息傳遞系統(tǒng)（高級）：

進(jìn)程之間的數(shù)據(jù)交換以進(jìn)程為單位。這種通信方式可進(jìn)一步劃分為：

直接通信方式；（通過發(fā)送和接收原語來實(shí)現(xiàn)）間接通信方式。（常見的如：郵箱通信方式）4.6進(jìn)程通信(3)管道（pipe）通信方式