PV操作

1962年，狄克斯特拉離開數學中心進入位於荷蘭南部的艾恩德霍芬技術大學(EindhovenTechnicalUniversity）任數學教授。在這裡，他參加了X86計算機的開發，設計與實現了具有多道程序運行能力的操作系統——THEMultiprogrammingSystem。

THE是艾恩德霍芬技術大學的荷蘭文TchnischeHoogeschoolEindhov–en的詞頭縮寫。狄克斯特拉在THE這個系統中所提出的一系統方法和技術奠定了計算機現代操作系統的基礎，尤其是關於多層體系結構，順序進程之間的同步和互斥機制這樣一些重要的思想和概念都是狄克斯特拉在THE中首先提出並為以後的操作系統如UNⅨ等所採用的。

為了在單處理機的情況下確定進程(process）能否佔有處理機，狄克斯特拉將每個進程分為“就緒”（ready）、“運行”（running）和“阻塞”（blocking）三個工作狀態。由於在任一時刻最多只有一個進程可以使用處理機，佔用著處理機的進程稱為“運行”進程。當某進程已具備了使用處理機的條件，而當前又沒有處理機供其使用，則使該進程處於“就緒”狀態。當運行進程由於某種原因無法繼續運行下去時，就停止其佔用處理機，使之進入“阻塞”狀態，待造成其退出運行的條件解除，再進入“就緒”狀態。而對系統中所有同時運行的進程之間所存在的相互制約的同步(synchronization，指為了避免錯誤，在一個進程訪問共享數據時，另一個進程不訪問該數據)和互斥(mutually-exclusive，指兩個進程不能同時在一個臨界區中使用同一個可重複使用的資源，諸如讀寫緩衝區)兩個關係，狄克斯特拉巧妙地利用火車運行控制系統中的“信號燈”(semaphore，或叫“信號量”)概念加以解決。

所謂信號燈，實際上就是用來控制進程狀態的一個代表某一資源的信號燈存儲單元。例如，P1和P2是分別將數據送入緩衝B和從緩衝B讀出數據的兩個進程，為了防止這兩個進程併發時產生錯誤，狄克斯特拉設計了一種同步機制叫“PV操作”，P操作和V操作是執行時不被打斷的兩個操作系統原語。執行P操作P（S）時信號量S的值減1，若結果不為負則P（S）執行完畢，否則執行P操作的進程暫停以等待釋放。執行V操作V（S）時，S的值加1，若結果大於0則釋放一個因執行P（S）而等待的進程。對P1和P2可定義兩個信號量S1和S2，初值分別為1和0。進程P1在向緩衝B送入數據前執行P操作P（S1），在送入數據后執行V操作V（S2）。進程P2在從緩衝B讀取數據前先執行P操作P（S2），在讀出數據后執行V操作V（S1）。當P1往緩衝B送入一數據后信號量S1之值變為0，在該數據讀出后S1之值才又變為1，因此在前一數未讀出前後一數不會送入，從而保證了P1和P2之間的同步。

中國讀者常常不明白這一同步機制為什麼叫PV操作，原來這是狄克斯特拉用荷蘭文定義的，因為在荷蘭文中，通過叫passeren，釋放叫vrijgeven，PV操作因此得名。這是在計算機術語中不是用英語表達的極少數的例子之一。

1．信號量的類型定義

信號量（semaphore）的數據結構為一個值和一個指針，指針指向等待該信號量的下一個進程。信號量的值與相應資源的使用情況有關。當它的值大於0時，表示當前可用資源的數量；當它的值小於0時，其絕對值表示等待使用該資源的進程個數。注意，信號量的值僅能由PV操作來改變。

一般來說，信號量S>=0時，S表示可用資源的數量。執行一次P操作意味著請求分配一個單位資源，因此S的值減1；當S<0時，表示已經沒有可用資源，請求者必須等待別的進程釋放該類資源，它才能運行下去。而執行一個V操作意味著釋放一個單位資源，因此S的值加1；若S<0，表示有某些進程正在等待該資源，因此要喚醒一個等待狀態的進程，使之運行下去。

2．PV原語

PV操作是典型的同步機制之一。用一個信號量與一個消息聯繫起來，當信號量的值為0時，表示期望的消息尚未產生；當信號量的值非0時，表示期望的消息已經存在。用PV操作實現進程同步時，調用P操作測試消息是否到達，調用V操作發送消息。

對一個信號量變數可以進行兩種原語操作：P操作和V操作，定義如下：

{procedureP(vars:semaphore);s.value=s.value-1;if(s.value<0)asleep(s.queue);procedureV(vars:semaphore);}

{s.value=s.value+1;if(s.value<=0)wakeup(s.queue);}

其中用到兩個標準過程：

asleep(s.queue）；執行此操作的進程的PCB進入s.queue尾部，進程變成等待狀態

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

s.value初值為1時，可以用來實現進程的互斥。

p操作和v操作是不可中斷的程序段，稱為原語。如果將信號量看作共享變數，則pv操作為其臨界區，多個進程不能同時執行，一般用硬體方法保證。一個信號量只能置一次初值，以後只能對之進行p操作或v操作。

由此也可以看到，信號量機制必須有公共內存，不能用於分散式操作系統，這是它最大的弱點。

V原語的主要操作是：

⑴sem加1；

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

⑶若相加結果小於或等於零，則喚醒一阻塞在該信號量上的進程，然後再返回原進程繼續執行或轉進程調度。

利用信號量和PV操作實現進程互斥的一般模型是：

進程P1進程P2進程Pn

P（S）；　P（S）；　P（S）；

臨界區；臨界區；臨界區；

V（S）；　V（S）；　V（S）；

其中信號量S用於互斥，初值為1。

三個問題：

一，以V原語的1、2步來做，Sem不就永遠大於0，那進程不就一直循環執行成為死循環了？

二，Sem大於0那就表示有臨界資源可供使用，為什麼不喚醒進程？

三，Sem小於0應該是說沒有臨界資源可供使用，為什麼還要喚醒進程？

析疑：

一，P操作對sem減1的。P、V原語必須成對使用！從而不會造成死循環。

二，Sem大於0的確表示有臨界資源可供使用，而且這個時候沒有進程被阻塞在這個資源上，也就是說沒有進程因為得不到這類資源而阻塞，所以沒有被阻塞的進程，自然不需要喚醒。

三，V原語操作的本質在於：一個進程使用完臨界資源后，釋放臨界資源，使Sem加1，以通知其它的進程，這個時候如果Sem<0，表明有進程阻塞在該類資源上，因此要從阻塞隊列里喚醒一個進程來“轉手”該類資源。比如，有兩個某類資源，四個進程A、B、C、D要用該類資源，最開始Sem=2，當A進入，Sem=1，當B進入Sem=0，表明該類資源剛好用完，當C進入時Sem=-1，表明有一個進程被阻塞了，D進入，Sem=-2。當A用完該類資源時，進行V操作，Sem=-1，釋放該類資源，而這時Sem<0，表明有進程阻塞在該類資源上，於是喚醒一個。

為了進一步加深理解，再引入二個問題：

四，如果是互斥信號量的話，應該設置信號量Sem=1，但是當有5個進程都訪問的話，最後在該信號量的鏈表里會有4個在等待，也是說S=-4，那麼第一個進程執行了V操作使S加1，釋放了資源，下一個應該能夠執行，但喚醒的這個進程在執行P操作時因S〈0，也還是執行不了，這是怎麼回事呢？

五，Sem的絕對值表示等待的進程數，同時又表示臨界資源，這到底是怎麼回事？

析疑：

四，當一個進程阻塞了的時候，它已經執行過了P操作，並卡在臨界區那個地方。當喚醒它時就立即進入它自己的臨界區，並不需要執行P操作了，當執行完了臨界區的程序后，就執行V操作。

五，當信號量Sem小於0時，其絕對值表示系統中因請求該類資源而被阻塞的進程數目.S大於0時表示可用的臨界資源數。注意在不同情況下所表達的含義不一樣。當等於0時，表示剛好用完。

用PV操作來管理共享資源時，首先要確保PV操作自身執行的正確性。由於P(S)和V(S)都是在同一個信號量S上操作，為了使得它們在執行時不發生因交叉訪問信號量S而可能出現的錯誤，約定P(S)和V(S)必須是兩個不可被中斷的過程，即讓它們在屏蔽中斷下執行。把不可被中斷的過程稱為原語。於是，P操作和V操作實際上應該是P操作原語和V操作原語。

P操作的主要動作是：

①S減1；

②若S減1后仍大於或等於0，則進程繼續執行；

③若S減1后小於0，則該進程被阻塞後放入等待該信號量的等待隊列中，然後轉進程調度。

V操作的主要動作是：

①S加1；

②若相加后結果大於0，則進程繼續執行；

③若相加后結果小於或等於0，則從該信號的等待隊列中釋放一個等待進程，然後再返回原進程繼續執行或轉進程調度。

PV操作對於每一個進程來說，都只能進行一次，而且必須成對使用。在PV原語執行期間不允許有中斷髮生。原語不能被中斷執行，因為原語對變數的操作過程如果被打斷，可能會去運行另一個對同一變數的操作過程，從而出現臨界段問題。如果能夠找到一種解決臨界段問題的方法，就可以實現對共享變數操作的原子性。

實現進程的同步

要實現進程的同步就必須提供一種機制，該機制能把其他進程需要的消息發送出去，也能測試自己需要的消息是否到達。把能實現進程同步的機制稱為同步機制。不同的同步機制實現同步的方法也不同。PV操作和管程是兩種典型的同步機制。在這裡，只介紹怎樣用PV操作實現進程間的同步。

我們已經知道怎樣用PV操作來實現進程的互斥。事實上，PV操作不僅是實現進程互斥的有效工具，而且還是一個簡單而方便的同步工具。用一個信號量與一個消息聯繫起來，信號量的值為0表示期望的消息尚未產生；信號量的值為非0表示期望的消息已經存在。假定用信號量S表示某個消息，現在來看看怎樣用PV操作達到進程同步的目的。

(1)調用P操作測試消息是否到達

任何進程調用P操作可測試到自己所期望的消息是否已經到達。若消息尚未產生，則S=0，調用P(s)后，P(S)一定讓調用者成為等待信號量S的狀態，即調用者此時必定等待直到消息到達；若消息已經存在，則S≠0，調用P(S)后，進程不會成為等待狀態而可繼續執行，即進程測試到自己期望的消息已經存在。

(2)調用V操作發送消息

任何進程要向其他進程發送消息時可調用V操作。若調用V操作之前S=0，表示消息尚未產生且無等待消息的進程，則調用V(S)后，V(s)執行S:=S+1使S≠0，即意味著消息已存在；若調用V操作之前S<0，表示消息未產生前已有進程在等待消息，則調用V(S)后將釋放一個等待消息者，即表示該進程等待的消息已經到達，可以繼續執行。

在用PV操作實現同步時，一定要根據具體的問題來定義信號量和調用P操作或V操作。一個信號量與一個消息聯繫在一起，當有多個消息時必須定義多個信號量；測試不同的消息是否到達或發送不同的消息時，應對不同的信號量調用P操作或V操作。

實現進程互斥

用PV操作可實現併發進程的互斥，其步驟如下。

(1)設立一個互斥信號量S，表示臨界區，其取值為1，0，-1，…其中，S=1表示無併發進程進入S臨界區；S=0表示已有一個併發進程進入了S臨界區；S等於負數表示已有一個併發進程進入S臨界區，且有|S|個進程等待進入S臨界區，S的初值為1。

(2)用PV操作表示對S臨界區的申請和釋放。在進入臨界區之前，通過P操作進行申請，在退出臨界區之後，通過V操作釋放。

S的初值可定義為0、1或其他整數，在系統初始化時確定。從信號量和PV操作的定義可以獲得如下推論。

推論1：若信號量S為正值，則該值等於在阻塞進程之前對信號量S可施行的P操作數，亦即等於S所代表的實際還可以使用的物理資源數。

推論2：若信號量s為負值，則其絕對值等於登記排列在該信號量S等待隊列之中的進程個數，亦即恰好等於對信號量S實施P操作而被阻塞並進入信號量S等待隊列的進程數。

推論3：通常，P操作意味著請求一個資源，V操作意味著釋放一個資源。在一定條件下，P操作代表阻塞進程的操作，而V操作代表喚醒被阻塞進程的操作。

1、使用PV操作實現進程互斥時應該注意的是：

⑴每個程序中用戶實現互斥的P、V操作必須成對出現，先做P操作，進臨界區，后做V操作，出臨界區。若有多個分支，要認真檢查其成對性。

⑵P、V操作應分別緊靠臨界區的頭尾部，臨界區的代碼應儘可能短，不能有死循環。

⑶互斥信號量的初值一般為1。

2、使用PV操作實現進程同步時應該注意的是：

⑴分析進程間的制約關係，確定信號量種類。在保持進程間有正確的同步關係情況下，哪個進程先執行，哪些進程后執行，彼此間通過什麼資源（信號量）進行協調，從而明確要設置哪些信號量。

⑵信號量的初值與相應資源的數量有關，也與P、V操作在程序代碼中出現的位置有關。

⑶同一信號量的P、V操作要成對出現，但它們分別在不同的進程代碼中。