操作系統(tǒng)中P、V操作實(shí)現(xiàn)進(jìn)程的同步與互斥

常靜

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

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

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

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

1 信號量的含義

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

2 P、V原語的含義

信號量的值可以修改，但只能由P和V操作來訪問，對信號量的操作由P、V操作原語來實(shí)現(xiàn)。P操作和V操作在執(zhí)行時(shí)是不可中斷的過程。

P操作P（s）

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

V操作V（s）

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

P、V操作原語是一種阻塞等待的同步原語，若進(jìn)程通過該原語的調(diào)用而不允許繼續(xù)執(zhí)行時(shí)，它將被阻塞或掛起，在此期間就沒有機(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)程同步問題時(shí)首先要分清哪些是互斥問題（互斥訪問臨界資源的），哪些是同步問題（具有前后執(zhí)行順序要求的）。

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

在每個(gè)進(jìn)程中用于實(shí)現(xiàn)互斥的P、V操作必須成對出現(xiàn)；用于實(shí)現(xiàn)同步的P、V操作也必須成對出現(xiàn)，但可以分別出現(xiàn)在不同的進(jìn)程中；在某個(gè)進(jìn)程中如果同時(shí)存在互斥與同步的操作，則其順序不能顛倒，必須先執(zhí)行對同步信號量的P操作，再執(zhí)行對互斥信號量的P操作，但V操作的順序沒有嚴(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）信號量個(gè)數(shù)的設(shè)置，并給信號量賦初值。一般情況下，在進(jìn)程互斥中，信號量都為一個(gè)；在同步中，要根據(jù)進(jìn)程間的同步關(guān)系來設(shè)置信號量的個(gè)數(shù)， 有一個(gè)也可能是多個(gè)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3）畫出工作流程圖，如圖3所示。

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

5 總結(jié)

本文通過實(shí)例，對利用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)程的同步與互斥了，希望對學(xué)習(xí)者理解和解決這一難點(diǎn)問題有一定的幫助。

參考文獻(xiàn)：

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

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