pv

進程通信的兩種操作

P,V原語是操作系統里進程之間通信用到的兩種操作,在我們研究進程間的互斥的時候經常會引入這個概念,將P,V操作方法與加鎖的方法相比較,來解決進程間的互斥問題。實際上,他的應用範圍很廣,他不但可以解決進程管理當中的互斥問題,而且我們還可以利用此方法解決進程同步與進程通信的問題。

[一]理論


闡述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) V(sem)
進程B:P(sem) 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原語的應用。當然關於這一部分的應用是十分廣泛的。比如操作系統文化史上非常經典的哲學家就餐問題,生產-消費問題,讀者-寫者問題,理髮師問題等等。大家不妨嘗試一下用信號量的方法進行實現。
主要參考書目:
《計算機操作系統教程》清華大學出版社 張堯學