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

韓都衣舍淘寶店

/

潮州新聞網(wǎng)

韓都衣舍童裝時尚女裝

/

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

/

韓都衣舍官方旗艦店

/

金彩

/1系統(tǒng)進程同步處理與管程背景臨界區(qū)域問題同步硬件信號量經(jīng)典同步問題臨界區(qū)域管程2背景有限緩沖問題的共享內(nèi)存解決方案（自學(xué)，增加計數(shù)變量count）設(shè)count當前值為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競爭條件（racecondition）：多個進程并發(fā)訪問和操作同一數(shù)據(jù)且執(zhí)行結(jié)果與訪問發(fā)生的特定順序有關(guān)防止競爭條件：確保一段時間內(nèi)只有一個進程能操作共享變量——進程同步（processsynchronization）補充：并發(fā)與并行并發(fā)（concurrency）：多個事件在同一時間間隔內(nèi)發(fā)生并行（parallel）：多個事件在同一時刻發(fā)生單CPU系統(tǒng)中，程序在宏觀上并發(fā)，微觀上串行執(zhí)行多CPU系統(tǒng)中，程序在宏觀上并發(fā)，微觀上并行執(zhí)行4臨界區(qū)域問題臨界區(qū)（criticalsection）：進程的代碼段臨界區(qū)問題：設(shè)計一個進程用來協(xié)作的協(xié)議進入?yún)^(qū)（entrysection）退出區(qū)（exitsection）剩余區(qū)（remaindersection）臨界區(qū)問題的解答必須滿足三項要求互斥有空讓進（前進要求）有限等待典型進程Pi的通用結(jié)構(gòu)do{

臨界區(qū)剩余區(qū)}while(1)進入?yún)^(qū)退出區(qū)51、兩進程解法算法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;分析：滿足互斥要求不滿足前進要求（嚴格交替）分析：滿足互斥要求不滿足前進要求（精確時序）6do{

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

算法3分析：滿足互斥要求滿足前進要求滿足有限等待要求72、多進程解法面包店算法思想：小號碼客戶先得到服務(wù)，相同號碼取名稱小者數(shù)據(jù)結(jié)構(gòu)booleanchoosing[n];(初值為false)intnumber[n];(初值為0)約定符號若a<c或a==c&&b<d則記為(a,b)<(c,d)max(a0,…,an-1)是數(shù)k，表示k>=ai對i=0,…,n-1成立8面包店算法中進程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)測試）！9同步硬件（簡單了解）單處理器環(huán)境在修改共享變量時禁止中斷出現(xiàn)多處理器環(huán)境使用特殊硬件指令，提供原子操作TestAndSetSwap10信號量信號量（semaphore，S）整數(shù)變量，除了初始化，只能由wait和signal訪問wait的經(jīng)典定義signal的經(jīng)典定義對信號量整數(shù)值的修改必須不可分的執(zhí)行——原子操作wait(S){while(s<=0);//no-opS--;}signal(S){S++;}111、用法解決n個進程的臨界區(qū)問題——互斥設(shè)n個進程共享一個信號量mutex，初始化為1進程Pi的組織結(jié)構(gòu)如下do{

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

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

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

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

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

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

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

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

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

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