軟件實現(xiàn)互斥進(jìn)入臨界區(qū)

1、線程考研題：在支持多線程的系統(tǒng)中，進(jìn)程P創(chuàng)建的若干個線程不能共享的是A.進(jìn)程P的代碼段B.進(jìn)程P中打開的文件C.進(jìn)程PD.進(jìn)程P中某線程的棧指針1內(nèi) 容要 求進(jìn)程與線程進(jìn)程概念* * * 進(jìn)程的狀態(tài)與轉(zhuǎn)換* * * 進(jìn)程控制* *進(jìn)程組織*進(jìn)程通信（共享存儲系統(tǒng)；消息傳遞系統(tǒng)；管道通信）*線程概念與多線程模型*進(jìn)程同步進(jìn)程同步的基本概念* * *實現(xiàn)臨界區(qū)互斥的基本方法（軟件實現(xiàn)方法；硬件實現(xiàn)方法）* * *信號量* * *管程*經(jīng)典同步問題（生產(chǎn)者-消費(fèi)者問題；讀者-寫者問題；哲學(xué)家進(jìn)餐問題）* * *2009年為9分，2010年為6分， 2011年為12分 2補(bǔ)充：使用信號量之前，進(jìn)程互斥

2、方法： 軟件方法 硬件方法硬件解法 (1) “測試并設(shè)置”指令硬件解法 (2) “交換”指令硬件解法（3） “開關(guān)中斷”指令 軟件方法基本思路在進(jìn)入?yún)^(qū)檢查和設(shè)置一些標(biāo)志，如果已有進(jìn)程在臨界區(qū)，則在進(jìn)入?yún)^(qū)通過循環(huán)檢查進(jìn)行等待；在退出區(qū)修改標(biāo)志 主要問題是設(shè)置什么標(biāo)志和如何檢查標(biāo)志3 算法1：單標(biāo)志位 設(shè)有兩個進(jìn)程Pi, Pj，其中Pi進(jìn)程設(shè)立一個公用整型變量 turn，用來描述允許進(jìn)入臨界區(qū)的進(jìn)程標(biāo)識。在進(jìn)入?yún)^(qū)循環(huán)檢查是否允許本進(jìn)程進(jìn)入turn為i時，進(jìn)程Pi可進(jìn)入在退出區(qū)修改允許進(jìn)入進(jìn)程標(biāo)識進(jìn)程Pi退出時，改turn為進(jìn)程Pj的標(biāo)識j；4(b)(a)while (TRUE) while (tu

3、rn != 1)/*循環(huán)*/ ;critical_region( );turn = 0;noncritical_region( ); while (TRUE) while (turn != 0)/*循環(huán)*/ ;critical_region( ); turn = 1; noncritical_region( ); 缺點：進(jìn)程強(qiáng)制輪流進(jìn)入臨界區(qū)，容易造成資源利用不充分。如：在Pi讓出臨界區(qū)之后，Pj使用臨界區(qū)之前，Pi不可能再次使用臨界區(qū)。5算法2：雙標(biāo)志法（先檢查） 設(shè)立一個標(biāo)志數(shù)組flag：描述進(jìn)程是否在臨界區(qū)，初值均為FALSE。先檢查，后修改 在進(jìn)入?yún)^(qū)檢查另一個進(jìn)程是否在臨界區(qū)，不在時修

4、改本進(jìn)程在臨界區(qū)的標(biāo)志；在退出區(qū)修改本進(jìn)程在臨界區(qū)的標(biāo)志；6優(yōu)點 不用交替進(jìn)入，可連續(xù)使用缺點 Pi和Pj可能同時進(jìn)入臨界區(qū) 如：按下面序列執(zhí)行時，會同時進(jìn)入：“Pi Pj Pi Pj”。即在檢查對方flag之后和切換自己flag之前有一段時間，結(jié)果都檢查通過。問題出在：檢查和修改操作不能連續(xù)進(jìn)行。7算法3：雙標(biāo)志法（先修改） 類似于算法2，區(qū)別在于先修改后檢查優(yōu)點 防止兩個進(jìn)程同時進(jìn)入臨界區(qū)缺點： Pi和Pj可能都進(jìn)入不了臨界區(qū) 如：按下面序列執(zhí)行時，都進(jìn)不了臨界區(qū)：“Pi Pj Pi Pj”。即在切換自己flag之后和檢查對方flag之前有一段時間，結(jié)果都切換flag，都檢查不通過。8荷蘭

5、數(shù)學(xué)家T. Dekker通過將輪換法和鎖變量以及警告變量的思想相結(jié)合，最先提出了一個不需要嚴(yán)格輪換的互斥算法的軟件方案。關(guān)于Dekker的算法，請參閱(DUkstra，1965)。1981年，G. L. Petterson發(fā)現(xiàn)了一種實現(xiàn)互斥的簡單方法，這使得Dekker的方法遭到廢棄。9算法4：結(jié)合算法1和算法3，是正確的算法 先修改、后檢查、后修改者等待turn=j;描述可進(jìn)入的進(jìn)程（同時修改標(biāo)志時）在進(jìn)入?yún)^(qū)先修改后檢查，并檢查并發(fā)修改的先后檢查對方flag，如果不在臨界區(qū)則自己進(jìn)入空閑則入否則再檢查turn：保存的是較晚的一次賦值，則較晚的進(jìn)程等待，較早的進(jìn)程進(jìn)入先到先入，后到等待Pete

6、rson算法 軟件算法存在如下缺點：忙等待實現(xiàn)過于復(fù)雜，需要高的編程技巧10全國聯(lián)考2010 進(jìn)程P0和P1的共享變量定義及其初值為：boolean falg2;int turn=0;falg0=FALSE; falg1=FALSE;若進(jìn)程P0和P1訪問臨界資源的類C偽代碼實現(xiàn)如下：void P0() /進(jìn)程P0while(TRUE)flag0= TRUE; turn=1; while(flag1&turn=1);臨界區(qū);flag0=FALSE; void P1() /進(jìn)程P1while(TRUE)flag1= TRUE; turn=0; while(flag0&turn=0);臨界區(qū);flag1=FALSE; 則并發(fā)執(zhí)行進(jìn)程P0和P1時產(chǎn)生的情形是A. 不能保證進(jìn)程互