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

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

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

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

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

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

一般說(shuō)來(lái)，在操作系統(tǒng)中，一個(gè)進(jìn)程相對(duì)于另一進(jìn)程的運(yùn)行速度是不確定的，但是相互合作的幾個(gè)進(jìn)程需要在某些確定點(diǎn)上協(xié)調(diào)它們的工作。所謂進(jìn)程同步是指多個(gè)相互合作的進(jìn)程，在一些關(guān)鍵點(diǎn)上可能需要相互等待或相互交換信息，這種相互制約關(guān)系稱(chēng)為進(jìn)程同步。

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

P、V操作在1965年由荷蘭計(jì)算機(jī)大師Dijkstra引入，他用荷蘭語(yǔ)中的單詞passeren（通過(guò)）、vrijgeven（釋放）的首字母來(lái)為這兩種操作命名。

P、V操作由P操作原語(yǔ)和V操作原語(yǔ)組成（原語(yǔ)是不可中斷的過(guò)程），對(duì)信號(hào)量進(jìn)行操作，具體定義如下：

P（S）：①將信號(hào)量S的值減1，即S=S-1；

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

V（S）：①將信號(hào)量S的值加1，即S=S+1；

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

利用信號(hào)量和P、V操作可以有效的解決進(jìn)程的同步和互斥問(wèn)題。

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

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

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

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

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

解：在本題中，應(yīng)設(shè)置5個(gè)信號(hào)量ST，TS K，L，M，信號(hào)量ST表示是否允許自行車(chē)從南開(kāi)大學(xué)去天津大學(xué)，其初值為1;信號(hào)量TS表示是否允許自行車(chē)從天津大學(xué)去南開(kāi)大學(xué)，其初值為1;信號(hào)量K表示是否允許自行車(chē)通過(guò)路段S到K，其初值為1;信號(hào)量L表示是否允許自行車(chē)通過(guò)路段T到L，其初值為1;信號(hào)量M表示安全島上還可停放自行車(chē)的數(shù)目;其初值為2。其控制過(guò)程描述如下：

semaphore ST=1;

semaphore TS=1;

semaphoreK=1;

semaphore L=1;

semaphore M=2;

totianjin() /*從南開(kāi)大學(xué)去天津大學(xué) */

{

p(ST);

p(K);

從S走到K;

p(M);

進(jìn)入安全島;

v(K);

p(L);

從L走到T;

v(M);

v(L);

v(ST);

}

tonankai() /*從無(wú)津大學(xué)去南開(kāi)大學(xué) */

{

p(TS);

p(L);

從T走到L;

p(M);

進(jìn)入安全島;

v(L);

P(K);

從K走到S;

v(M);

v(K);

v(TS);

}

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

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

3 該題目正確的算法

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

由P、V操作的定義可知，這種方法是對(duì)資源進(jìn)行封鎖，當(dāng)下一個(gè)進(jìn)程進(jìn)行P操作時(shí)會(huì)因?yàn)闆](méi)有可用的資源而被阻塞。因此，現(xiàn)在問(wèn)題轉(zhuǎn)化為在什么情況下應(yīng)該對(duì)后來(lái)的自行車(chē)進(jìn)行阻塞的問(wèn)題。

為方便說(shuō)明，引入兩個(gè)變量i、j。i表示本方向已進(jìn)入小路的自行車(chē)數(shù)量，j表示對(duì)面方向進(jìn)入小路的自行車(chē)數(shù)量。分情況討論，當(dāng)i>0，j=0時(shí)，本方可以任意進(jìn)入，對(duì)方可以進(jìn)一輛車(chē)，無(wú)需封鎖；當(dāng)i=1，j=1時(shí)本方或?qū)Ψ蕉伎梢赃M(jìn)一輛車(chē)，雙方在安全島錯(cuò)車(chē)，因此也無(wú)需封鎖；當(dāng)i>1，j=1時(shí)，本方可以進(jìn)車(chē)，而對(duì)方不能進(jìn)入，因此要封鎖對(duì)方后續(xù)自行車(chē)進(jìn)入；i=0，j>0時(shí)，本方可以進(jìn)一輛車(chē)，對(duì)方也可以進(jìn)入，無(wú)需封鎖；i=1，j>1時(shí)，本方不能再進(jìn)，對(duì)方可以進(jìn)入，因此需要封鎖己方后續(xù)進(jìn)入；i>1，j>1，這種情況不可能出現(xiàn)，如果出現(xiàn)意味著算法失敗。

再考慮解鎖，由于在封鎖時(shí)可以封鎖對(duì)方，也可以封鎖本方，因此，解鎖時(shí)也要考慮，解鎖的時(shí)機(jī)應(yīng)該放在本方向最后一輛自行車(chē)離開(kāi)小路時(shí)。是否解鎖要根據(jù)是否封鎖來(lái)確定，由于信號(hào)量只能由P、V操作訪(fǎng)問(wèn)，因此，應(yīng)該設(shè)置一個(gè)共享變量來(lái)表示當(dāng)前加鎖情況。

以上是對(duì)于整個(gè)路徑的封鎖情況，由于每個(gè)路段都只能單向行駛，因此，當(dāng)一輛自行車(chē)進(jìn)入后，應(yīng)當(dāng)阻塞對(duì)面方向的自行車(chē)進(jìn)入該路段，本方向的自行車(chē)可以依次進(jìn)入，在最后一輛自行車(chē)離開(kāi)時(shí)，進(jìn)行解鎖。

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

設(shè)置信號(hào)量如下：

wait：控制兩個(gè)方向的自行車(chē)只能依次進(jìn)入小路，不能有兩輛自行車(chē)同時(shí)由小路兩端進(jìn)入。

s-entry，t-entry：表示是否允許兩個(gè)方向的自行車(chē)進(jìn)入小路。

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

variety：用來(lái)封鎖共享變量，避免兩個(gè)進(jìn)程同時(shí)訪(fǎng)問(wèn)共享變量，為避免復(fù)雜性，程序中只提供一個(gè)這樣的信號(hào)量，它對(duì)所有共享變量提供保護(hù)。

設(shè)置共享變量countSK，countKS，countTL，countLT表示路段內(nèi)某方向的自行車(chē)數(shù)量；block記錄當(dāng)前對(duì)s-entry和t-entry的封鎖情況，block=0表示兩個(gè)方向都沒(méi)有封鎖，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()/*從南開(kāi)大學(xué)去天津大學(xué)*/

{

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);

進(jìn)入安全島;

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()/*從天津大學(xué)去南開(kāi)大學(xué)*/

{

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);

進(jìn)入安全島;

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);

}

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

參考文獻(xiàn)：

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

[2]安徽理工大學(xué)網(wǎng)站的解法 star.aust.edu.cn/~ypsheng/os/ch0604-c12.htm.

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