系統(tǒng)進(jìn)程同步處理與管程

韓都衣舍淘寶店

/

潮州新聞網(wǎng)

韓都衣舍童裝時(shí)尚女裝

/

網(wǎng)購(gòu)韓都衣舍首選麥考林

/

韓都衣舍官方旗艦店

/

金彩

/1系統(tǒng)進(jìn)程同步處理與管程背景臨界區(qū)域問(wèn)題同步硬件信號(hào)量經(jīng)典同步問(wèn)題臨界區(qū)域管程2背景有限緩沖問(wèn)題的共享內(nèi)存解決方案（自學(xué)，增加計(jì)數(shù)變量count）設(shè)count當(dāng)前值為5，則：R1=counter……R1=5R1=R1+1……R1=6counter=R1……c=6R2=counter……R2=6R2=R2-1……R2=5counter=R2……c=5R1=counter……R1=5R1=R1+1……R1=6

R2=counter……R2=5R2=R2-1……R2=4counter=R1……c=6counter=R2……c=43競(jìng)爭(zhēng)條件（racecondition）：多個(gè)進(jìn)程并發(fā)訪問(wèn)和操作同一數(shù)據(jù)且執(zhí)行結(jié)果與訪問(wèn)發(fā)生的特定順序有關(guān)防止競(jìng)爭(zhēng)條件：確保一段時(shí)間內(nèi)只有一個(gè)進(jìn)程能操作共享變量——進(jìn)程同步（processsynchronization）補(bǔ)充：并發(fā)與并行并發(fā)（concurrency）：多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生并行（parallel）：多個(gè)事件在同一時(shí)刻發(fā)生單CPU系統(tǒng)中，程序在宏觀上并發(fā)，微觀上串行執(zhí)行多CPU系統(tǒng)中，程序在宏觀上并發(fā)，微觀上并行執(zhí)行4臨界區(qū)域問(wèn)題臨界區(qū)（criticalsection）：進(jìn)程的代碼段臨界區(qū)問(wèn)題：設(shè)計(jì)一個(gè)進(jìn)程用來(lái)協(xié)作的協(xié)議進(jìn)入?yún)^(qū)（entrysection）退出區(qū)（exitsection）剩余區(qū)（remaindersection）臨界區(qū)問(wèn)題的解答必須滿足三項(xiàng)要求互斥有空讓進(jìn)（前進(jìn)要求）有限等待典型進(jìn)程Pi的通用結(jié)構(gòu)do{

臨界區(qū)剩余區(qū)}while(1)進(jìn)入?yún)^(qū)退出區(qū)51、兩進(jìn)程解法算法1算法2do{

臨界區(qū)剩余區(qū)}while(1)flag[i]=true;while(flag[j]);flag[i]=false;do{

臨界區(qū)剩余區(qū)}while(1)while(turn!=i);turn=j;分析：滿足互斥要求不滿足前進(jìn)要求（嚴(yán)格交替）分析：滿足互斥要求不滿足前進(jìn)要求（精確時(shí)序）6do{

臨界區(qū)剩余區(qū)}while(1)flag[i]=true;turn=j;while(flag[j]&&turn==j);flag[i]=false;

算法3分析：滿足互斥要求滿足前進(jìn)要求滿足有限等待要求72、多進(jìn)程解法面包店算法思想：小號(hào)碼客戶先得到服務(wù)，相同號(hào)碼取名稱小者數(shù)據(jù)結(jié)構(gòu)booleanchoosing[n];(初值為false)intnumber[n];(初值為0)約定符號(hào)若a<c或a==c&&b<d則記為(a,b)<(c,d)max(a0,…,an-1)是數(shù)k，表示k>=ai對(duì)i=0,…,n-1成立8面包店算法中進(jìn)程Pi的結(jié)構(gòu)do{

臨界區(qū)剩余區(qū)}while(1)choosing[i]=true;number[i]=max(number[0],number[1],…,number[n-1])+1;choosing[i]=false;for(j=0;j<n;j++){while(choosing[j]);while((number[j]!=0)&&(number[j],j)<(number[i],i));}number[i]=0;上述四種算法都要忙等待（循環(huán)測(cè)試）！9同步硬件（簡(jiǎn)單了解）單處理器環(huán)境在修改共享變量時(shí)禁止中斷出現(xiàn)多處理器環(huán)境使用特殊硬件指令，提供原子操作TestAndSetSwap10信號(hào)量信號(hào)量（semaphore，S）整數(shù)變量，除了初始化，只能由wait和signal訪問(wèn)wait的經(jīng)典定義signal的經(jīng)典定義對(duì)信號(hào)量整數(shù)值的修改必須不可分的執(zhí)行——原子操作wait(S){while(s<=0);//no-opS--;}signal(S){S++;}111、用法解決n個(gè)進(jìn)程的臨界區(qū)問(wèn)題——互斥設(shè)n個(gè)進(jìn)程共享一個(gè)信號(hào)量mutex，初始化為1進(jìn)程Pi的組織結(jié)構(gòu)如下do{

臨界區(qū)剩余區(qū)}while(1)wait(mutex);signal(mutex);使用信號(hào)量解決各種同步問(wèn)題——同步122、實(shí)現(xiàn)自旋鎖（spinlock）－忙等待克服忙等，重新定義信號(hào)量和wati、signal操作信號(hào)量定義typedefstruct{intvalue;structprocess*L;}semaphore;整數(shù)值進(jìn)程鏈表13wait操作signal操作voidwait(semaphoreS){S.value--;if(S.value<0){addthisprocesstoS.L;block();}}voidsignal(semaphoreS){S.value++;if(S.value<=0){removeaprocessfromS.L;wakeup(P);}}若S.value<0，則其絕對(duì)值是等待信號(hào)量S的進(jìn)程個(gè)數(shù)信號(hào)量原子執(zhí)行143、死鎖與饑餓（了解概念）死鎖（deadlocked）兩個(gè)或多個(gè)進(jìn)程無(wú)限地等待一個(gè)事件，而該事件只能由這些等待進(jìn)程之一來(lái)產(chǎn)生饑餓（starvation）或無(wú)限期阻塞（indefiniteblocking）進(jìn)程在信號(hào)量?jī)?nèi)無(wú)窮等待157.5經(jīng)典同步問(wèn)題1、有限緩沖問(wèn)題（生產(chǎn)者－消費(fèi)者問(wèn)題）數(shù)據(jù)結(jié)構(gòu)semaphoremutex,empty,fullmutex：提供對(duì)緩沖池訪問(wèn)的互斥要求，初值1empty：空緩沖項(xiàng)，初值nfull：滿緩沖項(xiàng)，初值016do{…produceaniteminnextp;…wait(empty);wait(mutex);…addnextptobuffer…signal(mutex);signal(full);}while(1);do{wait(full);wait(mutex);…removeanitemfrombuffertonextc;…signal(mutex);signal(empty);…consumetheiteminnextc…}while(1);生產(chǎn)者進(jìn)程結(jié)構(gòu)消費(fèi)者進(jìn)程結(jié)構(gòu)172、讀者－作者問(wèn)題第一讀者－作者問(wèn)題（V）：讀者不需等待第二讀者－作者問(wèn)題：若有作者等待，新讀者需等待數(shù)據(jù)結(jié)構(gòu)semaphoremutex,wrt;intreadcount;mutex：確保在更新變量readcount時(shí)的互斥，初值1wrt：供寫(xiě)者及第一個(gè)進(jìn)入臨界區(qū)和最后一個(gè)離開(kāi)臨界區(qū)的讀者使用，初值1readcount：用來(lái)跟蹤有多少進(jìn)程正在讀對(duì)象18作者進(jìn)程結(jié)構(gòu)讀者進(jìn)程結(jié)構(gòu)wait(wrt);…writingisperformed…signal(wrt);wait(mutex);readcount++;If(readcount==1)wait(wrt);signal(mutex);…readingisperformed…wait(mutex);readcount--;if(readcount==0)signal(wrt);signal(mutex);第一個(gè)進(jìn)入臨界區(qū)的讀者最后一個(gè)離開(kāi)臨界區(qū)的讀者193、哲學(xué)家就餐問(wèn)題數(shù)據(jù)結(jié)構(gòu)semaphorechopstick[5];chopstick[i]：第i個(gè)哲學(xué)家身邊的筷子，初值1食物20哲學(xué)家i的結(jié)構(gòu)do{wait(chopstick[i]);wait(chopstick[(i+1)%5]);…eat…signal(chopstick[i]);signal(chopstick[(i+1)%5]);…think…}while(1);分析：確保沒(méi)有兩個(gè)相鄰哲學(xué)家同時(shí)進(jìn)餐可能會(huì)導(dǎo)致死鎖（例如5個(gè)哲學(xué)家同時(shí)拿起左邊的筷子）21解決死鎖問(wèn)題的方案最多只允許4個(gè)哲學(xué)家同時(shí)坐在桌子上只有兩只筷子都可用時(shí)才允許一個(gè)哲學(xué)家拿起它們使用非對(duì)稱解決，即奇數(shù)哲學(xué)家先拿起他左邊的筷子，接著拿他右邊的筷子，而偶數(shù)哲學(xué)家先拿起他右邊的筷子，接著拿起他左邊的筷子餓死問(wèn)題無(wú)法確保22臨界區(qū)域（簡(jiǎn)單了解）信號(hào)量使用時(shí)可能出現(xiàn)一些錯(cuò)誤若交換了wait和signal的執(zhí)行順序，多個(gè)進(jìn)程可能在臨界區(qū)內(nèi)同時(shí)執(zhí)行，違反互斥要求若wait替代了signal，會(huì)發(fā)生死鎖若省略了wait或signal或兩者，可能會(huì)死鎖或違反互斥針對(duì)上述問(wèn)題－高級(jí)語(yǔ)言構(gòu)造臨界區(qū)域（條件臨界區(qū)域）管程（monitor）23臨界區(qū)域需要定義的數(shù)據(jù)結(jié)構(gòu)v：類型為T的共享數(shù)據(jù)（v:sharedT）B：布爾邏輯表達(dá)式S：與v關(guān)聯(lián)的執(zhí)行語(yǔ)句regionvwhen(B)S;當(dāng)語(yǔ)句S在執(zhí)行時(shí)，沒(méi)有其他進(jìn)程能訪問(wèn)變量v當(dāng)進(jìn)程試圖進(jìn)入臨界區(qū)時(shí)，先計(jì)算布爾邏輯表達(dá)式B，若為真，執(zhí)行語(yǔ)句S；否則，進(jìn)程放棄互斥并延遲到B為真，并且沒(méi)有其他進(jìn)程位于與v相關(guān)聯(lián)的區(qū)域內(nèi)24管程（monitor）管程的語(yǔ)法monitormonitor-name{sharedvariabledeclarationsprocedurebodyp1(…){…}procedurebodyp2(…){…}…procedurebodypn(…){…}{initializationcode}}管程：由程序員定義的一組操作符，管程構(gòu)造確保一次只有一個(gè)進(jìn)程能在管程內(nèi)活動(dòng)條件變量conditionx,y;x.wait();調(diào)用操作的進(jìn)程會(huì)暫停直到另一進(jìn)程調(diào)用x.signal();重新啟動(dòng)一個(gè)懸掛的進(jìn)程251、管程－哲學(xué)家就餐問(wèn)題的無(wú)死鎖解答數(shù)據(jù)結(jié)構(gòu)enum{thinking,hungry,eating}state[5];conditionself[5];管程dp控制筷子的分布哲學(xué)家i的操作dp.pickup(i);…eat…dp.putdown(i);26哲學(xué)家就餐問(wèn)題的管程解法monitordp{enum{thinking,hungry,eating}state[5];conditionself[5];voidpickup(inti){state[i]=hungry;test(i);if(state[i]!=eating)self[i].wait();}voidputdown(inti){state[i]=thinking;test((i+4)%5);test((I+1)%5);}27voidtest(inti){if(state[(i+4)%5]!=eating)&&(state[i]==hungry)&&(state[(i+1)%5]!=eating){state[i]=eating;self[i].signal();}}voidinit(){for(inti=0;i<5;i++)state[i]=thinking;}}282、用信號(hào)量實(shí)現(xiàn)管程數(shù)據(jù)結(jié)構(gòu)semaphoremutex,next;intnext_count;mutex：互斥，初值1next：供信號(hào)進(jìn)程掛起自己，初值0next_count：對(duì)掛起在next上的進(jìn)程數(shù)量計(jì)數(shù)wait(mutex);…bodyofF…if(next_count>0)signal(next);elsesignal(mutex);外部程序293、條件變量的實(shí)現(xiàn)semaphorex_sem;//初值為0intx_count;//初值為0x.waitx.signalx_count++;if(next_count>0)signal(next);elsesignal(mutex);wait(x-sem);x_count--;if(x_count>0){next_count++;signal(x_sem);wait(next);signal(mutex);next_count--;}30總結(jié)補(bǔ)充信號(hào)量小結(jié)wait、signal操作小結(jié)前驅(qū)關(guān)系的信號(hào)量解答針對(duì)信號(hào)量問(wèn)題的補(bǔ)充練習(xí)311、信號(hào)量小結(jié)一個(gè)信號(hào)量可用于n個(gè)進(jìn)程的同步互斥；且只能由wait、signal操作修改。用于互斥時(shí)，S初值為1，取值為1~-(n-1)（相當(dāng)于臨界區(qū)的通行證，實(shí)際上也是資源個(gè)數(shù)）

S=1：臨界區(qū)可用

S=0：已有一進(jìn)程進(jìn)入臨界區(qū)

S<0：臨界區(qū)已被占用，|S|個(gè)進(jìn)程正等待進(jìn)入用于同步時(shí)，S初值>=0

S>=0:表示可用資源個(gè)數(shù)

S<0:表示該資源的等待隊(duì)列長(zhǎng)度322、wait、signal操作小結(jié)wait(S)：請(qǐng)求分配一個(gè)資源。

signal(S)：釋放一個(gè)資源。

wait、signal操作必須成對(duì)出現(xiàn)。用于互斥時(shí)，位于同一進(jìn)程內(nèi)；用于同步時(shí)，交錯(cuò)出現(xiàn)于兩個(gè)合作進(jìn)程內(nèi)。多個(gè)wait操作的次序不能顛倒，否則可能導(dǎo)致死鎖。多個(gè)signal操作的次序可任意。333、補(bǔ)充例題（前驅(qū)關(guān)系）如圖所示的優(yōu)先圖，要求用信號(hào)量實(shí)現(xiàn)S1S3S4S5S6S7S234Semaphorea,b,c,d,e,f,g;//初值為0{{S1;signal(a);signal(b);}{wait(a);S2;S4;signal(c);signal(d);}{wait(b);S3;signal(e);}{wait(c);wait(e);S5;signal(f);}{wait(d);S6;signal(g);}{wait(f);wait(g);S7}}35補(bǔ)充題目練習(xí)S1S3S4S5S6S236Semaphorea,b,c,d,e,f,g;//初值為0{{S1;signal(a);signal(b);}{wait(a);S2;signal(c);signal(d);}{wait(b);S3;signal(e);}{wait(c);S4;signal(f);}{wait(d);S5;signal(g);}{wait(e);wait(f);wait(g);S6;}}374、針對(duì)信號(hào)量問(wèn)題的補(bǔ)充練習(xí)桌子上有一個(gè)盤子，可以存放一個(gè)水果。父親總是放蘋(píng)果到盤子中，而母親總是放香蕉到盤子中；兒子專等吃盤中的香蕉，而女兒專等吃盤中的蘋(píng)果。分析：生產(chǎn)者－消費(fèi)者問(wèn)題的一種變形，生產(chǎn)者、消費(fèi)者以及放入緩沖區(qū)的產(chǎn)品都有兩類，但每類消費(fèi)者只消費(fèi)其中固定的一種產(chǎn)品。數(shù)據(jù)結(jié)構(gòu)：semaphoredish，apple，banana;dish：表示盤子是否為空，初值為1apple：表示盤中是否有蘋(píng)果，初值為0banana：表示盤中是否有香蕉，初值為038father:do{wait(dish);

將蘋(píng)果放到盤中；signal(apple);}while(1);mother:do{wait(dish);

將香蕉放到盤中；signal(banana);}while(1);son:do{wai