完成臨界區互斥的根本辦法

軟體完成辦法

在進入區設定和檢討一些标記來标明能否有過程在臨界區中，假如已有過程在臨界區，則在進入區經過輪回檢討停止等候，過程分開臨界區後則在加入區修正标記。

1) 算法一：單标記法。

該算法設定一個公用整型變量turn,用于指導被許可進入臨界區的過程編号，即若turn=0，則許可P0過程進入臨界區。該算法可確定每次隻許可一個過程進入臨界區。但兩個過程必需瓜代進入臨界區，假如某個過程不再進入臨界區了，那麼另一個過程也将進入臨界區（違犯“閑暇讓進”）如許很輕易形成資本應用的不充沛。

// P0過程 while(turn!=0); critical section; turn=1; remainder section;      

// P1過程 while(turn!=1); // 進入區 critical section; // 臨界區 turn = 0; // 加入區 remainder section; // 殘剩區      

2) 算法二：雙标記法先檢討。

該算法的根本思惟是在每個過程拜訪臨界區資本之前，先檢查一下臨界資本能否正被拜訪，若正被拜訪，該過程需等候；不然，過程才進入本人的臨界區。為此，設定了一個資料flag[i]，如第i個元素值為FALSE，表現Pi過程未進入臨界區，值為TRUE，表現Pi過程進入臨界區。

// Pi 過程 while(flag[j]); // ①  flag[i]=TRUE; // ③  critical section; flag[i] = FALSE; remainder section;      

// Pj 過程 while(flag[i]); // ② 進入區 flag[j] =TRUE; // ④ 進入區 critical section; // 臨界區 flag[j] = FALSE; // 加入區 remainder section; // 殘剩區      

長處：不必瓜代進入，可延續運用；缺陷：Pi和Pj能夠同時進入臨界區。順次列①②③④ 履行時，會同時進入臨界區（違犯“忙則等候”)。即在檢討對方flag之後和切換本人flag 之前有一段工夫，後果都檢討經過。這裡的成績出在檢討和修正操作不克不及一次停止。

3) 算法三：雙标記法後檢討。

算法二是先檢測對方過程形态标記後，再置本人标記，因為在檢測和放置中可拔出另一個過程抵達時的檢測操作，會形成兩個過程在辨識檢測後，同時進入臨界區。為此，算法三釆用先設定本人标記為TRUE後,再檢測對方形态标記，若對方标記為TURE，則過程等候；不然進入臨界區。

// Pi過程 flag[i] =TRUE; while(flag[j]); critical section; flag[i] =FLASE; remainder section;      

// Pj過程 flag[j] =TRUE; // 進入區 while(flag[i]); // 進入區 critical section; // 臨界區 flag [j] =FLASE; // 加入區 remainder section; // 殘剩區      

當兩個過程簡直同時都想進入臨界區時，它們辨識将本人的标記值flag設定為TRUE，而且同時檢測對方的形态（履行while語句），發現對方也要進入臨界區，于是單方互相辭讓，後果誰也進不了臨界區，進而招緻“饑餓”景象。

4)算法四：Peterson’s Algorithm。

為了避免兩個過程為進入臨界區而有限期等候，又設定變量turn，指導不許可進入臨界區的過程編号，每一個過程在先設定本人标記後再設定turn 标記，不許可另一個過程進入。這時，再同時檢測另一個過程形态标記和不許可進入标記，如許可以包管當兩個過程同時請求進入臨界區，隻許可一個過程進入臨界區。

// Pi過程 flag[i]=TURE; turn=j; while(flag[j]&&turn==j); critical section; flag[i]=FLASE; remainder section;      

// Pj過程 flag[j] =TRUE;turn=i; // 進入區 while(flag[i]&&turn==i); // 進入區 critical section; // 臨界區 flag[j]=FLASE; // 加入區 remainder section; // 殘剩區      

本算法的根本思惟是算法一和算法三的聯合。應用flag處理臨界資本的互斥拜訪，而應用turn處理“饑餓”景象。

硬體完成辦法

本節對硬體完成的詳細了解對前面的旌旗燈号量的進修很有協助。盤算機供給了特别的硬體指令，許可對一個字中的内容停止檢測和修改，或許是對兩個字的内容停止交流等。經過硬體支撐完成臨界段成績的初級辦法或稱為元辦法。

1) 中綴屏障辦法

當一個過程正在運用處置機履行它的臨界區代碼時，要避免其他過程再進入其臨界區拜訪的最複雜辦法是制止一切中綴發作，或稱之為屏障中綴、關中綴。由于CPU隻在發作中綴時惹起過程切換，如許屏障中綴就能包管以後運轉過程将臨界區代碼順遂地履行完，進而包管了互斥的準确完成，然後再履行開中綴。其典型形式為：

…

關中綴;

臨界區;

開中綴;

這種辦法限制了處置機瓜代履行程式的才能，因而履行的效力将會分明下降。對核心來說，當它履行更新變量或清單的幾條指令時期關中綴是很便利的，但将關中綴的權利交給使用者則很不明智，若一個過程關中綴之後不再開中綴，則零碎能夠會因而終止。

2) 硬體指令辦法

TestAndSet指令：這條指令是原子操作，即履行該代碼時不許可被中綴。其功用是讀出指定标記後把該标記設定為真。指令的功用描繪如下：

boolean TestAndSet(boolean *lock){ boolean old; old = *lock; *lock=true; return old; }      

可認為每一個臨界資本設定一個共享布爾變量lock，表現資本的兩種形态：true表現正被占用，初值為false。在過程拜訪臨界資本之前，應用TestAndSet檢討和修正标記lock；如有過程在臨界區，則反複檢討，直到過程加入。應用該指令完成過程互斥的算法描繪如下：

while TestAndSet (& 1 ock); // 過程的臨界區代碼段; lock=false; // 過程的其他代碼      

Swap指令：該指令的功用是交流兩個位元組的内容。其功用描繪如下。

Swap(boolean *a, boolean *b){ boolean temp; Temp=*a; *a = *b; *b = temp; }      

key=true; while(key!=false) Swap(&lock, &key); // 過程的臨界區代碼段； lock=false; // 過程的其他代碼；