[科普中國]-PV操作

PV操作是一種實(shí)現(xiàn)進(jìn)程互斥與同步的有效方法。PV操作與信號(hào)量的處理相關(guān)，P表示通過的意思，V表示釋放的意思。

PV操作是典型的同步機(jī)制之一。用一個(gè)信號(hào)量與一個(gè)消息聯(lián)系起來，當(dāng)信號(hào)量的值為0時(shí)，表示期望的消息尚未產(chǎn)生；當(dāng)信號(hào)量的值非0時(shí)，表示期望的消息已經(jīng)存在。用PV操作實(shí)現(xiàn)進(jìn)程同步時(shí)，調(diào)用P操作測(cè)試消息是否到達(dá)，調(diào)用V操作發(fā)送消息。

簡(jiǎn)介1962年，狄克斯特拉離開數(shù)學(xué)中心進(jìn)入位于荷蘭南部的艾恩德霍芬技術(shù)大學(xué)(Eindhoven Technical University）任數(shù)學(xué)教授。在這里，他參加了X86計(jì)算機(jī)的開發(fā)，設(shè)計(jì)與實(shí)現(xiàn)了具有多道程序運(yùn)行能力的操作系統(tǒng)——THE Multiprogramming System。

THE 是艾恩德霍芬技術(shù)大學(xué)的荷蘭文Tchnische Hoogeschool Eindhov –en的詞頭縮寫。狄克斯特拉在THE這個(gè)系統(tǒng)中所提出的一系統(tǒng)方法和技術(shù)奠定了計(jì)算機(jī)現(xiàn)代操作系統(tǒng)的基礎(chǔ)，尤其是關(guān)于多層體系結(jié)構(gòu)，順序進(jìn)程之間的同步和互斥機(jī)制這樣一些重要的思想和概念都是狄克斯特拉在THE中首先提出并為以后的操作系統(tǒng)如UNIX等所采用的。

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

中國讀者常常不明白這一同步機(jī)制為什么叫PV操作，原來這是狄克斯特拉用荷蘭文定義的，因?yàn)樵诤商m文中，通過叫passeren，釋放叫vrijgeven，PV操作因此得名。這是在計(jì)算機(jī)術(shù)語中不是用英語表達(dá)的極少數(shù)的例子之一。

信號(hào)量信號(hào)量的概念和PV操作是荷蘭科學(xué)家E.W.Dijkstra提出來的。信號(hào)是鐵路交通管理中的一種常用設(shè)備，交通管理人員利用信號(hào)顏色的變化來實(shí)現(xiàn)交通管理。在操作系統(tǒng)中，信號(hào)量S是一整數(shù)。S大于或等于零，代表可供并發(fā)進(jìn)程使用的資源實(shí)體數(shù)；在S小于零時(shí)，ISl表示正在等待使用資源實(shí)體的進(jìn)程數(shù)。建立一個(gè)信號(hào)量必須說明此信號(hào)量所代表的意義并且賦初值。除賦初值外，信號(hào)量?jī)H能通過PV操作來訪問。1

信號(hào)量按其用途可分為兩種。1

①公用信號(hào)量。聯(lián)系一組并發(fā)進(jìn)程，相關(guān)的進(jìn)程均可在此信號(hào)量上執(zhí)行P操作和V操作，初值常常為1，用于實(shí)現(xiàn)進(jìn)程互斥。1

②私有信號(hào)量。聯(lián)系一組并發(fā)進(jìn)程，僅允許擁有此信號(hào)量的進(jìn)程執(zhí)行P操作，而其他相關(guān)進(jìn)程可在其上施行V操作。初值常常為0或正整數(shù)，多用于實(shí)現(xiàn)進(jìn)程同步。1

PV操作是由兩個(gè)操作，即P操作和V操作組成的。P操作和V操作是兩個(gè)在信號(hào)量上進(jìn)行操作的過程，假定用S表示信號(hào)量，則把這兩個(gè)過程記作P(S)和V(S)。1

原理用PV操作來管理共享資源時(shí)，首先要確保PV操作自身執(zhí)行的正確性。由于P(S)和V(S)都是在同一個(gè)信號(hào)量S上操作，為了使得它們?cè)趫?zhí)行時(shí)不發(fā)生因交叉訪問信號(hào)量S而可能出現(xiàn)的錯(cuò)誤，約定P(S)和V(S)必須是兩個(gè)不可被中斷的過程，即讓它們?cè)谄帘沃袛嘞聢?zhí)行。把不可被中斷的過程稱為原語。于是，P操作和V操作實(shí)際上應(yīng)該是P操作原語和V操作原語。1

P操作的主要?jiǎng)幼魇牵?

①S減1；1

②若S減1后仍大于或等于0，則進(jìn)程繼續(xù)執(zhí)行；1

③若S減1后小于0，則該進(jìn)程被阻塞后放入等待該信號(hào)量的等待隊(duì)列中，然后轉(zhuǎn)進(jìn)程調(diào)度。1

V操作的主要?jiǎng)幼魇牵?

①S加1；1

②若相加后結(jié)果大于0，則進(jìn)程繼續(xù)執(zhí)行； 1

③若相加后結(jié)果小于或等于0，則從該信號(hào)的等待隊(duì)列中釋放一個(gè)等待進(jìn)程，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。1

PV操作對(duì)于每一個(gè)進(jìn)程來說，都只能進(jìn)行一次，而且必須成對(duì)使用。在PV原語執(zhí)行期間不允許有中斷發(fā)生。原語不能被中斷執(zhí)行，因?yàn)樵Z對(duì)變量的操作過程如果被打斷，可能會(huì)去運(yùn)行另一個(gè)對(duì)同一變量的操作過程，從而出現(xiàn)臨界段問題。如果能夠找到一種解決臨界段問題的元方法，就可以實(shí)現(xiàn)對(duì)共享變量操作的原子性。2

應(yīng)用實(shí)現(xiàn)進(jìn)程的同步要實(shí)現(xiàn)進(jìn)程的同步就必須提供一種機(jī)制，該機(jī)制能把其他進(jìn)程需要的消息發(fā)送出去，也能測(cè)試自己需要的消息是否到達(dá)。把能實(shí)現(xiàn)進(jìn)程同步的機(jī)制稱為同步機(jī)制。不同的同步機(jī)制實(shí)現(xiàn)同步的方法也不同。PV操作和管程是兩種典型的同步機(jī)制。在這里，只介紹怎樣用PV操作實(shí)現(xiàn)進(jìn)程間的同步。1

我們已經(jīng)知道怎樣用PV操作來實(shí)現(xiàn)進(jìn)程的互斥。事實(shí)上，PV操作不僅是實(shí)現(xiàn)進(jìn)程互斥的有效工具，而且還是一個(gè)簡(jiǎn)單而方便的同步工具。用一個(gè)信號(hào)量與一個(gè)消息聯(lián)系起來，信號(hào)量的值為0表示期望的消息尚未產(chǎn)生；信號(hào)量的值為非0表示期望的消息已經(jīng)存在。假定用信號(hào)量S表示某個(gè)消息，現(xiàn)在來看看怎樣用PV操作達(dá)到進(jìn)程同步的目的。1

(1)調(diào)用P操作測(cè)試消息是否到達(dá)

任何進(jìn)程調(diào)用P操作可測(cè)試到自己所期望的消息是否已經(jīng)到達(dá)。若消息尚未產(chǎn)生，則S=0，調(diào)用P(s)后，P(S)一定讓調(diào)用者成為等待信號(hào)量S的狀態(tài)，即調(diào)用者此時(shí)必定等待直到消息到達(dá)；若消息已經(jīng)存在，則S≠0，調(diào)用P(S)后，進(jìn)程不會(huì)成為等待狀態(tài)而可繼續(xù)執(zhí)行，即進(jìn)程測(cè)試到自己期望的消息已經(jīng)存在。1

(2)調(diào)用V操作發(fā)送消息

任何進(jìn)程要向其他進(jìn)程發(fā)送消息時(shí)可調(diào)用V操作。若調(diào)用V操作之前S=0，表示消息尚未產(chǎn)生且無等待消息的進(jìn)程，則調(diào)用V(S)后，V(s)執(zhí)行S:=S+1使S≠0，即意味著消息已存在；若調(diào)用V操作之前S