pv

闡述P,V原語的理論不得不提到的一個人便是赫赫有名的荷蘭科學家E.W.Dijkstra。如果你對這位科學家沒有什麼印象的話，提起解決圖論中最短路徑問題的Dijkstra算法應當是我們再熟悉不過的了。P,V原語的概念以及P,V操作當中需要使用到的信號量的概念都是由他在1965年提出的。

信號量是最早出現的用來解決進程同步與互斥問題的機制，包括一個稱為信號量的變量及對它進行的兩個原語操作。信號量為一個整數，我們設這個信號量為：sem。很顯然，我們規定在sem大於等於零的時候代表可供併發進程使用的資源實體數，sem小於零的時候，表示正在等待使用臨界區的進程的個數。根據這個原則，在給信號量附初值的時候，我們顯然就要設初值大於零。

p操作和v操作是不可中斷的程序段，稱為原語。P,V原語中P是荷蘭語的Passeren，相當於英文的pass, V是荷蘭語的Verhoog,相當於英文中的increment。

P原語操作的動作是：

（1） sem減1；

（2） 若sem減1後仍大於或等於零，則進程繼續執行；

（3） 若sem減1後小於零，則該進程被阻塞後進入與該信號相對應的隊列中，然後轉進程調度。

V原語操作的動作是：

（1） sem加1；

（2） 若相加結果大於零，則進程繼續執行；

（3） 若相加結果小於或等於零，則從該信號的等待隊列中喚醒一等待進程，然後再返回原進程繼續執行或轉進程調度。

需要提醒大家一點就是P,V操作對於每一個進程來説，都只能進行一次。而且必須成對使用。且在P,V原語執行期間不允許有中斷的發生。

對於具體的實現，方法非常多，可以用硬件實現，也可以用軟件實現。我們採用如下的定義：

procedure p(var s:samephore);

{

s.value=s.value-1;

if (s.value<0) asleep(s.queue);

}

procedure v(var s:samephore);

{

s.value=s.value+1;

if (s.value<=0) wakeup(s.queue);

}

其中用到兩個標準過程：

asleep(s.queue);執行此操作的進程控制塊進入s.queue尾部，進程變成等待狀態

wakeup(s.queue);將s.queue頭進程喚醒插入就緒隊列

對於這個過程，s.value初值為1時，用來實現進程的互斥。

雖然説信號量機制比加鎖方法要好得多，但是也不是説它沒有任何的缺陷。由此我們也可以清晰地看到，這種信號量機制必須有公共內存，不能用於分佈式操作系統，這是它最大的弱點。

正如我們在文中最開始的時候提到的，P,V原語不但可以解決進程管理當中的互斥問題，而且我們還可以利用此方法解決進程同步與進程通信的問題。

把臨界區置於P(sem) 和V(sem)之間。當一個進程想要進入臨界區時，它必須先執行P原語操作以將信號量sem減1，在進程完成對臨界區的操作後，它必須執行V原語操作以釋放它所佔用的臨界區。從而就實現了進程的互斥：

具體的過程我們可以簡單的描述如下：

進程A：P（sem）<S> V（sem）

進程B：P（sem）<S> V（sem）

我們把異步環境下的一組併發進程因直接制約而互相發送消息、進行互相合作、互相等待，使得各進程按一定的速度執行的過程稱為進程間的同步。具有同步關係的一組併發進程稱為合作進程，合作進程間互相發送的信號稱為消息或事件。 如果我們對一個消息或事件賦以唯一的消息名，則我們可用過程　wait (消息名)　 表示進程等待合作進程發來的消息，而用過程　signal (消息名) 表示向合作進程發送消息。

我們以郵箱通信為例説明問題：

郵箱通信滿足的條件是：

;發送進程發送消息的時候，郵箱中至少要有一個空格能存放該消息。

;接收進程接收消息時，郵箱中至少要有一個消息存在。

發送進程和接收進程我們可以進行如下的描述：

Deposit(m)為發送進程，接收進程是remove(m). Fromnum為發送進程的私用信號量，信箱空格數n。mesnum為接收進程的私用信號量，初值為0.

Deposit(m):

Begin local x

P(fromnum)

選擇空格x

將消息m放入空格x中

置格x的標誌為滿

V(mesnum)

end

Remove(m)

Begin local x

P(mesnum)

選擇滿格x

把滿格x中的消息取出放m中

置格x標誌為空

V(fromnum)

end

筆者僅從最基本的進程問題上論述P,V原語的應用。當然關於這一部分的應用是十分廣泛的。比如操作系統文化史上非常經典的哲學家就餐問題，生產-消費問題，讀者-寫者問題，理髮師問題等等。大家不妨嘗試一下用信號量的方法進行實現。

主要參考書目：

《計算機操作系統教程》清華大學出版社 張堯學 ^[1]