常靜

摘要：操作系統(tǒng)是計(jì)算機(jī)科學(xué)與技術(shù)的專業(yè)基礎(chǔ)課程，進(jìn)程的同步與互斥問(wèn)題是操作系統(tǒng)中的重要內(nèi)容。如何正確使用P、V操作實(shí)現(xiàn)進(jìn)程的同步與互斥是防止死鎖的重要手段，怎樣判斷進(jìn)程是同步還是互斥問(wèn)題，以及如何正確使用P、V操作防止進(jìn)程死鎖，該文通過(guò)具體的實(shí)例給出一種通用的解決模式。

關(guān)鍵詞：進(jìn)程同步；進(jìn)程互斥；信號(hào)量；P、V操作

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044（2012）30-7144-04

操作系統(tǒng)中，可以使用軟件和硬件方法解決臨界區(qū)的問(wèn)題，雖然它們都可以解決互斥問(wèn)題，但是存在一定的缺陷。于是計(jì)算機(jī)科學(xué)家們努力尋找其他更有效地方法。荷蘭著名的計(jì)算機(jī)科學(xué)家E.W.Dijkstra提出了一個(gè)信號(hào)量和P、V操作同步機(jī)構(gòu)。其基本原則是在多個(gè)相互合作的進(jìn)程之間使用簡(jiǎn)單的信號(hào)來(lái)協(xié)調(diào)控制。

1 信號(hào)量的含義

信號(hào)量被定義為含有整型數(shù)據(jù)項(xiàng)的結(jié)構(gòu)變量，其整型值大于等于零代表可供并發(fā)進(jìn)程使用的資源個(gè)數(shù)，小于零時(shí)其絕對(duì)值表示正在等待使用臨界資源的進(jìn)程數(shù)。其數(shù)據(jù)結(jié)構(gòu)表示為：

2 P、V原語(yǔ)的含義

信號(hào)量的值可以修改，但只能由P和V操作來(lái)訪問(wèn)，對(duì)信號(hào)量的操作由P、V操作原語(yǔ)來(lái)實(shí)現(xiàn)。P操作和V操作在執(zhí)行時(shí)是不可中斷的過(guò)程。

P操作P（s）

表示申請(qǐng)一個(gè)資源，將信號(hào)量s的整型值減去1，若結(jié)果小于0，則將調(diào)用P（s）的進(jìn)程插入等待該資源的阻塞隊(duì)列。

V操作V（s）

表示釋放一個(gè)資源，將信號(hào)量s的整型值加上1，若結(jié)果不大于0，則從該資源的阻塞隊(duì)列首部喚醒一個(gè)進(jìn)程插入到就緒隊(duì)列中。

P、V操作原語(yǔ)是一種阻塞等待的同步原語(yǔ)，若進(jìn)程通過(guò)該原語(yǔ)的調(diào)用而不允許繼續(xù)執(zhí)行時(shí)，它將被阻塞或掛起，在此期間就沒(méi)有機(jī)會(huì)獲得CPU執(zhí)行，直到它被喚醒為止。故可使得進(jìn)程在等待進(jìn)入臨界區(qū)時(shí)，將CPU讓給了其他就緒進(jìn)程執(zhí)行。而忙等待的臨界區(qū)管理法，使得進(jìn)程在等待進(jìn)入臨界區(qū)時(shí)，也和其他就緒進(jìn)程一起分享CPU的服務(wù)。

3 P、V操作在進(jìn)程同步中的意義

進(jìn)程同步包括進(jìn)程互斥和進(jìn)程同步兩個(gè)方面，進(jìn)程互斥是同步的一種特例。用P、V操作解決進(jìn)程同步問(wèn)題時(shí)首先要分清哪些是互斥問(wèn)題（互斥訪問(wèn)臨界資源的），哪些是同步問(wèn)題（具有前后執(zhí)行順序要求的）。

在互斥問(wèn)題中，P操作的意義是申請(qǐng)資源，是否能進(jìn)入臨界區(qū)；V操作的意義是退出臨界區(qū)，從而釋放資源；通常只設(shè)置一個(gè)互斥信號(hào)量，且初值為1，代表一次只允許一個(gè)進(jìn)程對(duì)臨界資源進(jìn)行訪問(wèn)。在同步問(wèn)題中，P操作的意義是接受發(fā)來(lái)的信息、通知，表示可以執(zhí)行；V操作的意義是發(fā)送消息、通知，告知對(duì)方。在設(shè)置同步信號(hào)量時(shí)，通常同步信號(hào)量的個(gè)數(shù)與參與同步的進(jìn)程種類有關(guān)，即同步關(guān)系涉及幾類進(jìn)程，就有幾個(gè)同步信號(hào)量。同步信號(hào)量表示該進(jìn)程是否可以開(kāi)始或該進(jìn)程是否已經(jīng)結(jié)束。

在每個(gè)進(jìn)程中用于實(shí)現(xiàn)互斥的P、V操作必須成對(duì)出現(xiàn)；用于實(shí)現(xiàn)同步的P、V操作也必須成對(duì)出現(xiàn)，但可以分別出現(xiàn)在不同的進(jìn)程中；在某個(gè)進(jìn)程中如果同時(shí)存在互斥與同步的操作，則其順序不能顛倒，必須先執(zhí)行對(duì)同步信號(hào)量的P操作，再執(zhí)行對(duì)互斥信號(hào)量的P操作，但V操作的順序沒(méi)有嚴(yán)格要求。

4 實(shí)現(xiàn)P、V操作的具體做法

1）確定進(jìn)程間的關(guān)系以及進(jìn)程的個(gè)數(shù)。這一環(huán)節(jié)非常重要，如果理解不準(zhǔn)確，則之后的操作都將是錯(cuò)誤的。進(jìn)程間的關(guān)系主要指是進(jìn)程同步還是進(jìn)程互斥，它決定了P、V操作在進(jìn)程中存在的意義。進(jìn)程的個(gè)數(shù)主要看題目中需要P、V控制的事件有多少個(gè)，則進(jìn)程個(gè)數(shù)就是幾個(gè)。

2）信號(hào)量個(gè)數(shù)的設(shè)置，并給信號(hào)量賦初值。一般情況下，在進(jìn)程互斥中，信號(hào)量都為一個(gè)；在同步中，要根據(jù)進(jìn)程間的同步關(guān)系來(lái)設(shè)置信號(hào)量的個(gè)數(shù)， 有一個(gè)也可能是多個(gè)。

3）畫(huà)出進(jìn)程的工作流程圖。流程圖時(shí)最好反映題意的一種方法，工作流程圖越準(zhǔn)確，最后的算法就越容易實(shí)現(xiàn)。

4）根據(jù)流程圖使用一門(mén)語(yǔ)言來(lái)描述進(jìn)程之間的關(guān)系。這步主要是看個(gè)人的編程基礎(chǔ)，用不同的語(yǔ)言實(shí)現(xiàn)都可以，最好是用自己掌握較好的一門(mén)語(yǔ)言。

下面就一些典型例子做分析，在分析中理解P、V操作在進(jìn)程同步中的實(shí)際運(yùn)用：

4.1 用PV原語(yǔ)實(shí)現(xiàn)進(jìn)程的互斥

為了正確地解決一組并行進(jìn)程對(duì)臨界資源的競(jìng)爭(zhēng)使用，可以引入一個(gè)互斥信號(hào)量，對(duì)于互斥使用的資源，其信號(hào)量的初值就是系統(tǒng)中這個(gè)資源的數(shù)量。以哲學(xué)家進(jìn)餐問(wèn)題為例：

有四位哲學(xué)家圍著一個(gè)圓桌在思考和進(jìn)餐，每人思考時(shí)手中什么都不拿，當(dāng)需要進(jìn)餐時(shí)，每人需要用刀和叉各一把，餐桌上的布置如圖1所示，共有兩把刀和兩把叉，每把刀或叉供相鄰的兩個(gè)人使用。請(qǐng)用信號(hào)量及PV操作說(shuō)明四位哲學(xué)家的同步過(guò)程。

1）確定進(jìn)程的個(gè)數(shù)及其工作內(nèi)容。本例子涉及四個(gè)進(jìn)程，每個(gè)哲學(xué)家為一個(gè)進(jìn)程。因相鄰的兩個(gè)哲學(xué)家要競(jìng)爭(zhēng)刀或叉，刀或叉就成為了臨界資源，所以屬于互斥關(guān)系。

2）第二步確定互斥信號(hào)量的個(gè)數(shù)、含義及PV操作。設(shè)置4個(gè)互斥信號(hào)量fork1，fork2，knife1，knife2，其初值均為“1”，分別表示叉1，叉2，刀1，刀2是可用的。

3）畫(huà)工作流程圖。一般情況下，進(jìn)程互斥問(wèn)題的工作流程基本相同，所以只要畫(huà)出其中一個(gè)進(jìn)程的流程圖即可。

4）根據(jù)流程圖寫(xiě)出相應(yīng)算法。用類C語(yǔ)言描述互斥關(guān)系，互斥描述如下：

4.3用P、V原語(yǔ)實(shí)現(xiàn)進(jìn)程的同步和互斥

有了上面的分析后，下面來(lái)考慮進(jìn)程同步與互斥的混合問(wèn)題就不難了?；旌蠁?wèn)題當(dāng)中關(guān)鍵就是協(xié)調(diào)同步操作和互斥操作的先后。通過(guò)下面的例子來(lái)說(shuō)明此問(wèn)題：

設(shè)有一個(gè)具有N個(gè)信息元素的環(huán)形緩沖區(qū)，A進(jìn)程順序地把信息寫(xiě)進(jìn)緩沖區(qū)，B進(jìn)程依次地從緩沖區(qū)中讀出信息，請(qǐng)用P、V操作表示A和B進(jìn)程的同步算法。

1）確定進(jìn)程間的關(guān)系。A和B兩個(gè)進(jìn)程對(duì)緩沖區(qū)的訪問(wèn)必須互斥，并且當(dāng)緩沖區(qū)滿時(shí)，A進(jìn)程不能寫(xiě)入，必須等待；當(dāng)緩沖區(qū)空時(shí)，B進(jìn)程不能讀，必須等待。所以這是一個(gè)同步加互斥的問(wèn)題。

2）確定信號(hào)量及其值。可以設(shè)置3個(gè)信號(hào)量：互斥信號(hào)量S=1（表示對(duì)緩沖區(qū)的互斥使用）；同步信號(hào)量Sw（代表緩沖區(qū)是否有空閑，即寫(xiě)進(jìn)程能否寫(xiě)）、Sr（代表緩沖區(qū)是否有數(shù)據(jù)，即讀進(jìn)程能否讀），假設(shè)初始時(shí)緩沖區(qū)沒(méi)有任何數(shù)據(jù)，則Sw=N，Sr=0。

3）畫(huà)出工作流程圖，如圖3所示。

4）根據(jù)流程圖寫(xiě)出相應(yīng)算法。在此就不再詳述。

5 總結(jié)

本文通過(guò)實(shí)例，對(duì)利用P、V操作實(shí)現(xiàn)進(jìn)程互斥與同步給出了一個(gè)一般模型。在具體實(shí)現(xiàn)時(shí)，只需要在模型中的P 操作和V操作間填入適當(dāng)?shù)膶?shí)現(xiàn)代碼，就可以很方便地實(shí)現(xiàn)進(jìn)程的同步與互斥了，希望對(duì)學(xué)習(xí)者理解和解決這一難點(diǎn)問(wèn)題有一定的幫助。

參考文獻(xiàn)：

[1] 馬海波，王德廣.計(jì)算機(jī)操作系統(tǒng)教程[M].北京：清華大學(xué)出版社，2009.

[2] 連衛(wèi)民，徐保民.操作系統(tǒng)原理教程[M].北京：中國(guó)水利水電出版社，2004.