第2章進(jìn)程同步與通信-1

第二章進(jìn)程的描述與控制2.4進(jìn)程同步與互斥1、進(jìn)程同步與互斥

2、信號(hào)量和P、V操作AND信號(hào)量2.5、經(jīng)典進(jìn)程同步與互斥問題2.6、

進(jìn)程通信2.4.1進(jìn)程同步的基本概念間接制約:進(jìn)程間由于共享某種系統(tǒng)資源，而形成的相互制約。直接制約：進(jìn)程間由于合作而形成的相互制約。

進(jìn)程B

資源進(jìn)程A進(jìn)程A進(jìn)程B1、進(jìn)程的兩種制約關(guān)系在多道程序環(huán)境下，當(dāng)程序并發(fā)執(zhí)行時(shí)，由于資源共享和進(jìn)程合作，使同處于一個(gè)系統(tǒng)中的諸進(jìn)程之間可能存在著以下兩種形式的制約關(guān)系：互斥：互斥是并發(fā)執(zhí)行的多個(gè)進(jìn)程由于競(jìng)爭(zhēng)同一資源而產(chǎn)生的相互排斥的關(guān)系。同步：

同步是進(jìn)程間共同完成一項(xiàng)任務(wù)時(shí)直接發(fā)生相互作用的關(guān)系。進(jìn)程的兩大關(guān)系——同步進(jìn)程間具有合作關(guān)系——在執(zhí)行時(shí)間上必須按一定的順序協(xié)調(diào)進(jìn)行。

臨界資源：一次僅允許一個(gè)進(jìn)程使用的共享資源。如：打印機(jī)、磁帶機(jī)、表格。2、臨界資源3、臨界區(qū)在每個(gè)進(jìn)程中訪問臨界資源的那段程序。進(jìn)程必須互斥進(jìn)入臨界區(qū)訪問臨界區(qū)的循環(huán)進(jìn)程描述repeat進(jìn)入?yún)^(qū)臨界區(qū)退出區(qū)剩余區(qū)檢查臨界資源是否能訪問將臨界區(qū)標(biāo)志設(shè)為未訪問untilfalse;進(jìn)入?yún)^(qū)：每個(gè)進(jìn)程在進(jìn)入臨界區(qū)之前，應(yīng)先對(duì)欲訪問的臨界資源進(jìn)行檢查，看它是否正被訪問。如果此刻該臨界資源未被訪問，進(jìn)程便可進(jìn)入臨界區(qū)對(duì)該資源進(jìn)行訪問，并設(shè)置它正被訪問的標(biāo)志；退出區(qū)：在臨界區(qū)后面也要加上一段稱為退出區(qū)(exitsection)的代碼，用于將臨界區(qū)正被訪問的標(biāo)志恢復(fù)為未被訪問的標(biāo)志。剩余區(qū)：進(jìn)程中除上述進(jìn)入?yún)^(qū)、臨界區(qū)及退出區(qū)之外的其它部分的代碼，在這里都稱為剩余區(qū)。這樣，可把一個(gè)訪問臨界資源的循環(huán)進(jìn)程描述如下：

repeat

entrysection

criticalsection；

exitsection

remaindersection；

untilfalse；4、同步機(jī)制遵循的原則(1)空閑讓進(jìn)當(dāng)無進(jìn)程處于臨界區(qū)時(shí)，表明臨界資源處于空閑狀態(tài)，應(yīng)允許一個(gè)請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)，以有效地利用臨界資源。(2)忙則等待當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時(shí)，表明臨界資源正在被訪問，因而其它試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證對(duì)臨界資源的互斥訪問。(3)有限等待對(duì)要求訪問臨界資源的進(jìn)程，應(yīng)保證在有限時(shí)間內(nèi)能進(jìn)入自己的臨界區(qū)，以免陷入“死等”狀態(tài)。(4)讓權(quán)等待當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入“忙等”狀態(tài)。

互斥的實(shí)現(xiàn)方法●禁止中斷●專用機(jī)器指令

●TS（TestandSet）指令

●Swap指令（1）硬件方法2.4.2硬件同步機(jī)制禁止中斷（中斷屏蔽方法）當(dāng)一個(gè)進(jìn)程正在使用處理機(jī)執(zhí)行它的臨界區(qū)代碼時(shí)，要防止其他進(jìn)程再進(jìn)入其臨界區(qū)訪問的最簡(jiǎn)單方法是禁止一切中斷發(fā)生，或稱之為屏蔽中斷、關(guān)中斷。其典型模式為：…….關(guān)中斷;

臨界區(qū);

開中斷;

//TS指令：booleanTS(boolean*lock){booleantemp;temp=*lock;*lock=true;returntemp;}●Lock有兩種狀態(tài)： ●當(dāng)lock=false時(shí)，表示資源空閑;

●當(dāng)lock=true時(shí)，表示資源正在被使用?！袢秉c(diǎn)：沒有做到：“讓權(quán)等待”(當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入“忙等”狀態(tài)。)//TS指令的使用whileTS(&lock);臨界區(qū);lock=false;剩余區(qū)；TS（TestandSet）指令互斥實(shí)現(xiàn)的軟件方法//進(jìn)程0while(turn!=0)

//什么都不做;

臨界區(qū);turn=

1;剩余區(qū);

//進(jìn)程1while(turn!=1)do

//什么都不做‘;

臨界區(qū);turn=0;剩余區(qū);●設(shè)置公共整型變量turn，用于指示進(jìn)入臨界區(qū)的進(jìn)程編號(hào)i(i=0,1)。使P0、P1輪流訪問臨界資源。●缺點(diǎn)：強(qiáng)制性輪流進(jìn)入臨界區(qū)，不能保證“空閑讓進(jìn)”?！?、單標(biāo)志算法！//進(jìn)程0

while(flag[1])

//什么都不做; flag[0]=true;

臨界區(qū);

flag[0]=false;

剩余區(qū);//進(jìn)程1 while(flag[0])

//什么都不做; flag[1]=true;

臨界區(qū);

flag[1]=false;

剩余區(qū);●設(shè)置數(shù)組flag，初始時(shí)設(shè)每個(gè)元素為false,表示所有進(jìn)程都未進(jìn)入臨界區(qū)。若flag[i]=true,表示進(jìn)程進(jìn)入臨界區(qū)執(zhí)行?！裨诿總€(gè)進(jìn)程進(jìn)入臨界區(qū)時(shí)，先查看臨界資源是否被使用，若正在使用，該進(jìn)程等待，否則才可進(jìn)入。解決了“空閑讓進(jìn)”問題?！袢秉c(diǎn)：可能同時(shí)進(jìn)入臨界區(qū)，不能保證“忙則等待”。用軟件方法解決互斥問題——2、雙標(biāo)志、先檢查算法！//進(jìn)程0

flag[0]=true; while(flag[1])

//什么也不做;

臨界區(qū); flag[0]=false;

剩余區(qū);●兩進(jìn)程先后同時(shí)作 flag[i]=true;●缺點(diǎn)：保證了不同時(shí)進(jìn)入臨界區(qū)，但又可能都進(jìn)不去。不能保證“有空讓進(jìn)”。//進(jìn)程1 flag[1]=true; while(flag[0])

//什么也不做;

臨界區(qū); flag[1]=false;

剩余區(qū);——3、雙標(biāo)志、先修改后檢查算法用軟件方法解決互斥問題！//進(jìn)程0 flag[0]=true; turn=1; while(flag[1])&&(turn==1)

//什么也不做;

臨界區(qū); flag[0]=false;

剩余區(qū);保證了“有空讓進(jìn)”和“忙則等待”。//進(jìn)程1 flag[1]=true; turn=0; while(flag[0])&&(turn==0)

//什么也不做;

臨界區(qū); flag[1]=false;

剩余區(qū);——先修改、后檢查、后修改算法用軟件方法解決互斥問題！

2.4.3信號(hào)量機(jī)制

信號(hào)量和P、V操作

中心街道樓宇1小區(qū)A小區(qū)B城市公路進(jìn)程信號(hào)量信號(hào)量是一種數(shù)據(jù)結(jié)構(gòu)信號(hào)量的值與相應(yīng)資源的使用情況有關(guān)信號(hào)量的值僅由P、V操作改變1、整型信號(hào)量整型數(shù)SP操作（wait）原語(yǔ)V操作（signal）原語(yǔ)Wait（S）:while（S≤0）；//dono-opS:=S-1;Signal（S）:

S:=S+1;S—表示資源數(shù)目，是個(gè)整型量。wait（s）和signal（S）是原子操作。只要信號(hào)量S≤0就不斷測(cè)試，不滿足讓權(quán)等待。2、記錄型信號(hào)量記錄型結(jié)構(gòu)，包含兩個(gè)數(shù)據(jù)項(xiàng)：

typedefstruct{ intvalue; Structprocess_control_block*list; }semaphore;ValueLSwait操作：申請(qǐng)一個(gè)單位資源

wait(semaphore*S){

S->value--;

if(S->value<0)block(S->list);

}signal操作：釋放一個(gè)單位資源 signal(semaphore*S){

S->value++；

if(S->value<=0)wakeup(S->list);

S.value為資源信號(hào)量，其初值為某類資源的數(shù)目。S.value≥0：表示系統(tǒng)中可用的資源數(shù)量S.value<0：其絕對(duì)值表示已阻塞的進(jìn)程數(shù)量。（等待使用資源的進(jìn)程個(gè)數(shù)）S.value初值為1時(shí)：只允許一個(gè)進(jìn)程訪問臨界資源，是互斥信號(hào)量。上述的進(jìn)程互斥問題，是針對(duì)各進(jìn)程之間只共享一個(gè)臨界資源而言的。在有些應(yīng)用場(chǎng)合，是一個(gè)進(jìn)程需要先獲得兩個(gè)或更多的共享資源后方能執(zhí)行其任務(wù)。假定現(xiàn)有兩個(gè)進(jìn)程A和B，他們都要求訪問共享數(shù)據(jù)D和E。當(dāng)然，共享數(shù)據(jù)都應(yīng)作為臨界資源。為此，可為這兩個(gè)數(shù)據(jù)分別設(shè)置用于互斥的信號(hào)量Dmutex和Emutex，并令它們的初值都是1。相應(yīng)地，在兩個(gè)進(jìn)程中都要包含兩個(gè)對(duì)Dmutex和Emutex的操作，即processA:

processB:wait(Dmutex)；wait(Emutex)；wait(Emutex)；wait(Dmutex)；若進(jìn)程A和B按下述次序交替執(zhí)行wait操作：

processA:wait(Dmutex)；于是Dmutex=0

processB:wait(Emutex)；于是Emutex=0

processA:wait(Emutex)；于是Emutex=-1A阻塞

processB:wait(Dmutex)；于是Dmutex=-1B阻塞最后，進(jìn)程A和B處于僵持狀態(tài)。在無外力作用下，兩者都將無法從僵持狀態(tài)中解脫出來。我們稱此時(shí)的進(jìn)程A和B已進(jìn)入死鎖狀態(tài)。顯然，當(dāng)進(jìn)程同時(shí)要求的共享資源愈多時(shí)，發(fā)生進(jìn)程死鎖的可能性也就愈大。3、AND型信號(hào)量基本思想：將進(jìn)程在整個(gè)運(yùn)行中需要的所有資源，一次性全部分配給進(jìn)程，待進(jìn)程使用完后一起釋放。由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。

在wait中加入AND條件，又稱AND同步或同時(shí)wait操作。Swait(Simultaneouswait)Swait(S1，S2，…Sn){While(TRUE){if(S1≥1&&…&&Sn≥1){ for(i=1;i<=n;i++)Si--; break;} else

當(dāng)發(fā)現(xiàn)第一個(gè)Si<1就把該進(jìn)程放入等待隊(duì)列，并將其程序計(jì)數(shù)器置于Swait操作的開始位置}}Ssignal(S1，S2，…Sn){while(TRUE){for(i=1;i<=n;i++){Si++;

將所有等待Si的進(jìn)程由等待隊(duì)列取出放入到就緒隊(duì)列}}}2.4.4信號(hào)量的應(yīng)用

用信號(hào)量實(shí)現(xiàn)互斥Varmutex:semaphore:=1;BeginParbeginProcess1:beginrepeatwait(mutex);criticalsectionsignal(mutex);remaindersectionuntilfalse;

end;Process2:beginrepeatwait(mutex);criticalsectionsignal(mutex);remaindersectionuntilfalse;

end;parend在實(shí)現(xiàn)互斥時(shí)應(yīng)注意wait(mutex)和signal(mutex)必須成對(duì)地出現(xiàn)。缺wait(mutex)將會(huì)引起系統(tǒng)混亂，不能保證對(duì)臨界資源的互斥訪問缺signal(mutex)將會(huì)使該臨界資源永久不被釋放初始狀態(tài)mutex:=1沒有并發(fā)進(jìn)程使用臨界區(qū)臨界區(qū)互斥的進(jìn)程一個(gè)進(jìn)程申請(qǐng)臨界區(qū)mutex:=1沒有并發(fā)進(jìn)程使用臨界區(qū)mutex:=申請(qǐng)成功，進(jìn)程使用臨界區(qū)