一道關于Ｐ、Ｖ操作的操作系統(tǒng)經典題目的正確算法

[摘要]本文介紹了操作系統(tǒng)中P、V操作的有關概念，分析了應用PV操作的一道經典題目并給出了正確的解法。

[關鍵詞]操作系統(tǒng) P、V操作 算法

1操作系統(tǒng)中的P、V操作簡介

現(xiàn)代操作系統(tǒng)基本上都是多進程的操作系統(tǒng)，系統(tǒng)中有多個進程并發(fā)執(zhí)行，這些并發(fā)執(zhí)行的進程之間存在著不同的相互制約關系，為了協(xié)調進程之間的這種相互制約關系，需要實現(xiàn)進程的同步與互斥。

在操作系統(tǒng)中存在著各種資源供進程使用，如果某個資源一次只能供一個進程使用，則稱其為臨界資源。計算機中許多物理設備如打印機、掃描儀等都屬于臨界資源，除物理設備外，許多變量、數據等都可以被若干進程共享，但不允許多個進程同時進行修改操作，它們也可視為臨界資源。

在每個進程中，訪問臨界資源的那段程序稱為臨界區(qū)，在操作系統(tǒng)中，當一個進程進入臨界區(qū)使用臨界資源時，另一個進程必須等待，當占用臨界資源的進程退出臨界區(qū)后，另一進程才允許去訪問此臨界資源，這種進程間的相互制約關系稱為互斥。

一般說來，在操作系統(tǒng)中，一個進程相對于另一進程的運行速度是不確定的，但是相互合作的幾個進程需要在某些確定點上協(xié)調它們的工作。所謂進程同步是指多個相互合作的進程，在一些關鍵點上可能需要相互等待或相互交換信息，這種相互制約關系稱為進程同步。

在操作系統(tǒng)中解決進程同步和互斥問題的一種重要方法是信號量機制和P、V操作。信號量是一個確定的二元組（S，Q），其中S是一個具有非負初值的整形變量，Q是一個初始狀態(tài)為空的隊列。整形變量S表示系統(tǒng)中某類資源的數目，當其值大于0時，表示系統(tǒng)中當前可用資源的數目；當其值小于0時，其絕對值表示系統(tǒng)中因其請求該類資源而被阻塞的進程數目。除信號量的初值外，信號量的值僅能由P操作和V操作改變。

P、V操作在1965年由荷蘭計算機大師Dijkstra引入，他用荷蘭語中的單詞passeren（通過）、vrijgeven（釋放）的首字母來為這兩種操作命名。

P、V操作由P操作原語和V操作原語組成（原語是不可中斷的過程），對信號量進行操作，具體定義如下：

P（S）：①將信號量S的值減1，即S=S-1；

②如果S30，則該進程繼續(xù)執(zhí)行；否則該進程置為等待狀態(tài)，排入等待隊列。

V（S）：①將信號量S的值加1，即S=S+1；

②如果S>0，則該進程繼續(xù)執(zhí)行；否則釋放隊列中第一個等待信號量的進程。

利用信號量和P、V操作可以有效的解決進程的同步和互斥問題。

2 一道考察PV操作的經典操作系統(tǒng)試題

P、V操作是操作系統(tǒng)課程中的重點內容，其考察形式并不僅限于計算機中進程的互斥和同步，而更多的將現(xiàn)實中的某些事務納入，要求使用P、V操作來處理這些事務。許多操作系統(tǒng)教材中都有諸如哲學家進餐問題、理發(fā)師問題、生產者－消費者問題等經典例題，就是這種情況的體現(xiàn)。本文所要講述的這道題目也是這種類型的。

在南開大學和天津大學之間有一條彎曲的小路，其中從S到T一段路每次只允許一輛自行車通過，但其中有一個小的安全島M(同時允許兩輛自行車停留)，可供兩輛自行車已從兩端進人小路情況下錯車使用，如圖1所示。試設計一個算法使來往的自行車均可順利通過。

該題目是南開大學1997年研究生入學考試的操作系統(tǒng)科目的一道試題，在很多操作系統(tǒng)的參考書和習題集中都有收錄，其解法一般如下：

分析及相關知識：在本題中，需要控制路段T到L，路段S到K及安全島M的使用。路段T到L及路段S到K同時只允許一輛自行車通過。而安全島M允許兩輛自行車使用，因此可以用三個信號量來管理它們、另一方面，同一方向上的自行車最多只能有一輛通過這段路(兩個方向上有兩輛)，因此還應該用兩個信號量來控制。

解：在本題中，應設置5個信號量ST，TS K，L，M，信號量ST表示是否允許自行車從南開大學去天津大學，其初值為1;信號量TS表示是否允許自行車從天津大學去南開大學，其初值為1;信號量K表示是否允許自行車通過路段S到K，其初值為1;信號量L表示是否允許自行車通過路段T到L，其初值為1;信號量M表示安全島上還可停放自行車的數目;其初值為2。其控制過程描述如下：

semaphore ST=1;

semaphore TS=1;

semaphoreK=1;

semaphore L=1;

semaphore M=2;

totianjin() /*從南開大學去天津大學 */

{

p(ST);

p(K);

從S走到K;

p(M);

進入安全島;

v(K);

p(L);

從L走到T;

v(M);

v(L);

v(ST);

}

tonankai() /*從無津大學去南開大學 */

{

p(TS);

p(L);

從T走到L;

p(M);

進入安全島;

v(L);

P(K);

從K走到S;

v(M);

v(K);

v(TS);

}

以上是一般參考書中給出的解法。后來筆者又在網上找到了安徽理工大學操作系統(tǒng)課程網站上給出的另一種解法，如下所示：

由于小路中間的安全島M僅允許兩輛自行車停留，本應該作為臨界資源而設置信號量， 但仔細分析可以發(fā)現(xiàn)：在任何時刻進入小路的自行車最多不會超過兩輛(南開和天大方向各一輛)，因此，無需為安全島M設置信號量。在路口S處，南開出發(fā)的若干自行車應進行進入小路權的爭奪，以決定誰能夠進入小路SK段，為此，設置信號量S(初值為1)來控制南開路口資源的爭奪。同理，設置信號量T(初值為1)來控制天大路口資源的爭奪。此外，小路SK段僅允許一輛自行車通過，所以設置信號量SK(初值為1)來進行控制，而對于LT 段則設置信號量LT(初值為1)進行控制。(控制過程描述略)

3 該題目正確的算法

下面我們拋棄掉這個錯誤的前提，看一下真實情況下的小路，能夠容許什么樣的交通。當對面沒有來車的情況下，小路應該允許多輛自行車單向行駛；若一個方向有多輛自行車進入，另一方向僅有一輛自行車，則可以在安全島錯車，單獨的自行車要在安全島里等待對面自行車全部通過安全島后方可進入第二路段；若兩個方向都有超過一輛的自行車進入，則雙方都無法通過，出現(xiàn)死鎖。另外，兩個路段中都只允許單個方向的自行車進入，不能有兩個方向的自行車同時存在；兩個路段可以分別有不同方向的自行車。

由P、V操作的定義可知，這種方法是對資源進行封鎖，當下一個進程進行P操作時會因為沒有可用的資源而被阻塞。因此，現(xiàn)在問題轉化為在什么情況下應該對后來的自行車進行阻塞的問題。

為方便說明，引入兩個變量i、j。i表示本方向已進入小路的自行車數量，j表示對面方向進入小路的自行車數量。分情況討論，當i>0，j=0時，本方可以任意進入，對方可以進一輛車，無需封鎖；當i=1，j=1時本方或對方都可以進一輛車，雙方在安全島錯車，因此也無需封鎖；當i>1，j=1時，本方可以進車，而對方不能進入，因此要封鎖對方后續(xù)自行車進入；i=0，j>0時，本方可以進一輛車，對方也可以進入，無需封鎖；i=1，j>1時，本方不能再進，對方可以進入，因此需要封鎖己方后續(xù)進入；i>1，j>1，這種情況不可能出現(xiàn)，如果出現(xiàn)意味著算法失敗。

再考慮解鎖，由于在封鎖時可以封鎖對方，也可以封鎖本方，因此，解鎖時也要考慮，解鎖的時機應該放在本方向最后一輛自行車離開小路時。是否解鎖要根據是否封鎖來確定，由于信號量只能由P、V操作訪問，因此，應該設置一個共享變量來表示當前加鎖情況。

以上是對于整個路徑的封鎖情況，由于每個路段都只能單向行駛，因此，當一輛自行車進入后，應當阻塞對面方向的自行車進入該路段，本方向的自行車可以依次進入，在最后一輛自行車離開時，進行解鎖。

安全島可以容納兩輛自行車，因此資源M＝2，但是在i>1，j=1的情況下，有可能出現(xiàn)，本向兩輛自行車進入安全島，等待進入第二路段，而對方自行車卻在第二路段中等待進入安全島的情況，這樣就發(fā)生了死鎖。由于安全島的作用就是錯車（這里我們不考慮同方向自行車利用安全島超車的可能），因此，同時進入安全島的自行車一個方向只能有一輛，我們可以把臨界資源M分成MS和MT兩部分，數量都為1，來表示S→T和T→S兩個方向的安全島資源。通過這種方法，可以避免前述的死鎖問題。

設置信號量如下：

wait：控制兩個方向的自行車只能依次進入小路，不能有兩輛自行車同時由小路兩端進入。

s-entry，t-entry：表示是否允許兩個方向的自行車進入小路。

sk，lt，tl，ks：表示是否允許自行車按方向進入該路段，比如sk＝1表示允許自行車由s端進入sk路段。

variety：用來封鎖共享變量，避免兩個進程同時訪問共享變量，為避免復雜性，程序中只提供一個這樣的信號量，它對所有共享變量提供保護。

設置共享變量countSK，countKS，countTL，countLT表示路段內某方向的自行車數量；block記錄當前對s-entry和t-entry的封鎖情況，block=0表示兩個方向都沒有封鎖，block=1表示封鎖S→T方向，block=2表示封鎖T→S方向。

算法描述如下：

semaphore wait=1;

semaphore s-entry=1;

semaphore t-entry=1;

semaphore sk=1;

semaphore lt=1;

semaphore tl=1;

semaphore ks=1;

semaphore Ms=1;

semaphore Mt=1;

semaphore variety=1;

int countSk=0;

int countKS=0;

int countTL=0;

int countLT=0;

int countMs=0;

int countMt=0;

int block=0;

main()

{

cobegin;

StoT();

TtoS();

coend

}

StoT()/*從南開大學去天津大學*/

{

p(wait);

p(s-entry);

p(sk);

p(variety);

if (countSK==0) p(ks);

countSK++;

if(countTL+countMt<1 or countSK+countMs=1 and countTL+countMt=1) V(s-entry)

else if (countSK+countMs=1 and countTL+countMt>1) block=1;

if (countSK+countMs>1) {p(t-entry);block=2;}

V(variety);

V(sk);

V(wait);

從S走到K；

p(Ms);

進入安全島;

p(variety);

countMs=1;

countSK--;

if (countSK==0) V(ks);

V(variety);

P(lt);

V(Ms);

P(variety);

CountMs=0;

If (countLT==0) p(tl);

CountLT++;

V(variety);

從L走到T;

p(variety);

countLT--;

if (countLT==0) V(tl);

if(countSK+countMs+countLT==0 and block==2) {V(t-entry);block=0;}

V(variety);

}

TtoS()/*從天津大學去南開大學*/

{

p(wait);

p(t-entry);

p(tl);

p(variety);

if (countTL==0) p(lt);

countTL++;

if(countSK+countMs<1 or countTL+countMt=1 and countSK+countMs=1) V(t-entry)

else if (countTL+countMt=1 and countSK+countMs>1) block=2;

if (countTL+countMt>1) {p(s-entry);block=1;}

V(variety);

V(tl);

V(wait);

從T走到L；

p(Mt);

進入安全島;

p(variety);

countMt=1;

countTL--;

if (countTL==0) V(lt);

V(variety);

P(ks);

V(Mt);

P(variety);

CountMt=0;

If (countKS==0) p(ks);

CountKS++;

V(variety);

從K走到S;

p(variety);

countKS--;

if (countKS==0) V(sk);

if(countTL+countMt+countKS==0 and block==1) {V(s-entry);block=0;}

V(variety);

}

該算法通過增加對于本方向和對面方向的進入封鎖，保證了在小路中在反方向沒有或只有一輛自行車的情況下，本方向可以有多輛自行車依次進入，提高了運行效率，更好地模擬了真實的交通情況，作為操作系統(tǒng)的經典題目，該算法應該是較為正確的解法。

參考文獻：

[1]曾平，曾林.操作系統(tǒng)習題與解析（第二版）[M].北京:清華大學出版社，2004.3.

[2]安徽理工大學網站的解法 star.aust.edu.cn/~ypsheng/os/ch0604-c12.htm.

(作者單位：山東泰山學院)