淺析PV操作在多道程序系統(tǒng)中的應(yīng)用

[摘 要]在多道程序系統(tǒng)中,若干個(gè)進(jìn)程可以同時(shí)執(zhí)行,各進(jìn)程之間可以是無關(guān)的,也可以是有交往的。有交往的并發(fā)進(jìn)程由于共享內(nèi)部資源,因此導(dǎo)致進(jìn)程執(zhí)行速度上的制約,這種制約分為:間接制約與直接制約。間接制約引起進(jìn)程之間的互斥執(zhí)行,直接制約引起進(jìn)程的同步執(zhí)行。如果并發(fā)進(jìn)程對(duì)資源竟?fàn)幉划?dāng)會(huì)導(dǎo)致各種并發(fā)問題,我們可用PV操作來管理相關(guān)臨界區(qū),實(shí)現(xiàn)進(jìn)程的互斥和同步。

[關(guān)鍵詞]PV操作 多道系統(tǒng) 臨界區(qū) 互斥 同步

作者簡(jiǎn)介:劉羽鵬(1981-),男,江西吉安人,南昌理工學(xué)院教師,助教,主要研究方向:計(jì)算機(jī)科學(xué)與技術(shù)。

并發(fā)進(jìn)程在訪問資源時(shí)可能有兩種關(guān)系:一種是競(jìng)爭(zhēng)關(guān)系,另一種是協(xié)作關(guān)系。當(dāng)并發(fā)進(jìn)程存在競(jìng)爭(zhēng)關(guān)系時(shí)必須互斥地使用共享資源;當(dāng)并發(fā)進(jìn)程存在協(xié)作關(guān)系時(shí)必須互通消息。把這兩種關(guān)系分別稱為“進(jìn)程互斥”和“進(jìn)程的同步”,正確應(yīng)用PV操作,可實(shí)現(xiàn)進(jìn)程互斥和同步。

一、PV原語和多道程序系統(tǒng)

(一)為了確保PV操作自身執(zhí)行的正確性,約定PV操作必須由兩個(gè)不可中斷的過程,我們把不可被中斷的過程稱為“原語”。我們?cè)O(shè)置信號(hào)量sem,sem大于等于零時(shí)代表可供并發(fā)進(jìn)程使用的資源實(shí)體數(shù),但sem小于零時(shí)則表示正在等待使用臨界區(qū)的進(jìn)程數(shù)。

PV操作是由兩個(gè)操作,即P操作和V操作組成。P操作和V操作是兩個(gè)在信號(hào)量上進(jìn)行的過程。

(二)讓多個(gè)計(jì)算機(jī)問題同時(shí)裝入一個(gè)計(jì)算機(jī)系統(tǒng)的主存儲(chǔ)器并行執(zhí)行,這種設(shè)計(jì)技術(shù)稱“多道程序設(shè)計(jì)”,這種計(jì)算機(jī)系統(tǒng)稱“多道程序設(shè)計(jì)系統(tǒng)”或簡(jiǎn)稱“多道系統(tǒng)”。多道程序設(shè)計(jì)系統(tǒng)是在計(jì)算機(jī)內(nèi)存中同時(shí)存放幾道相互獨(dú)立的程序,使它們?cè)诠芾沓绦蚩刂浦?相互穿插的運(yùn)行。兩個(gè)或兩個(gè)以上的程序在計(jì)算機(jī)系統(tǒng)中同處于開始和結(jié)束之間的狀態(tài)。多道程序技術(shù)運(yùn)行的特征:多道、宏觀上運(yùn)行、微觀上串行。

在多道程序設(shè)計(jì)中,若干個(gè)進(jìn)程可以同時(shí)執(zhí)行,并發(fā)進(jìn)程之間可以是無關(guān)的,也可以有交往的。例如只有一個(gè)教室,這個(gè)公有資源使得每個(gè)班只能互斥使用它,這就是間接制約。進(jìn)程的互斥與同步可以很好的通過信號(hào)量和PV原語來實(shí)現(xiàn)。并發(fā)進(jìn)程的資源競(jìng)爭(zhēng)不當(dāng)還會(huì)導(dǎo)致共享沖突。進(jìn)程間正確的互斥和同步能避免出現(xiàn)與時(shí)間有關(guān)的錯(cuò)誤。

二、PV操作

如果在并發(fā)進(jìn)程中,有進(jìn)程在相關(guān)臨界區(qū)執(zhí)行時(shí),不讓另一個(gè)進(jìn)程進(jìn)入相關(guān)的臨界區(qū)執(zhí)行就不會(huì)形成多個(gè)進(jìn)程對(duì)相同的共享變量交叉訪問。于是可避免出現(xiàn)與時(shí)間有關(guān)的錯(cuò)誤。即只要涉及相同變量的若干個(gè)進(jìn)程的相關(guān)臨界區(qū)互斥執(zhí)行,就不會(huì)造成與時(shí)間有關(guān)的錯(cuò)誤。

(一)用PV操作實(shí)現(xiàn)進(jìn)程的互斥。

進(jìn)程的互斥是指:當(dāng)若干個(gè)進(jìn)程都要使用某一共享變量時(shí),任何時(shí)刻最多只允許一個(gè)進(jìn)程去使用其他要使用該變量的進(jìn)程必須等待,直到占用資源者釋放了該資源。用PV操作實(shí)現(xiàn)對(duì)相關(guān)臨界區(qū)的管理,只要用一個(gè)信號(hào)量與一組涉及共享變量的相關(guān)臨界區(qū)聯(lián)系起來,讓并發(fā)進(jìn)程互斥進(jìn)入自己的臨界區(qū)。

1.PV操作可確保共享數(shù)據(jù)的一致性。

例如:用PV操作管理火車站售票系統(tǒng),可以避免各售票終端同時(shí)賣出同一天同一車次的火車票和把一張票賣給幾個(gè)不同的乘客的錯(cuò)誤。

Begin

S:semaphore;

S:=1;

Cobegin

Process Pi(i=1,2,---,n)

Begin

{按旅客要求找到Aj};

P(s);

Ri=Aj;

IfRi>=1 then begin Ri=Ri-1;

Aj=Ri;

V(s);

{輸出一張票};

End;

Else begin V(s); {輸出“票已售完”};

End;

Coend;

End;

在編寫上述程序時(shí),千萬別忘了 else begin V(s); {輸出“票已售完”},end;這條語句,如果寫成 else{輸出“票已售完”} ,當(dāng)Ri<1時(shí),則會(huì)出現(xiàn)已進(jìn)入臨界區(qū)的進(jìn)程無限地逗留在臨界區(qū)中,而等待進(jìn)入臨界區(qū)的進(jìn)程無限地等待進(jìn)入臨界區(qū),這不符合相關(guān)臨界區(qū)管理應(yīng)滿足的條件,將造成系統(tǒng)癱瘓。

2.調(diào)用PV操作時(shí)要注意確保并發(fā)效率,同時(shí)避免出現(xiàn)并發(fā)問題。上述程序段要注意以下不良的管理方法,寫成:

Process Pi(i=1,2,---,n)

Begin

P(s);

{按旅客要求找到Aj};

Ri=Aj;

IfRi>=1 then begin Ri=Ri-1

Aj=Ri;

V(s);

{輸出一張票};

End;

Else begin v(s);

{輸出“票已售完”}

End;

End;

上述程序把不屬于臨界區(qū)的語句“{按旅客要求找到Aj};”也放進(jìn)了臨界區(qū),降低了系統(tǒng)并發(fā)執(zhí)行的能力。我們的原則是能并發(fā)執(zhí)行部分要保持其并發(fā)性,只有涉及到共享變量的程序段才是需要互斥執(zhí)行臨界區(qū),臨界區(qū)的代碼應(yīng)盡量小,同時(shí)確保不會(huì)出現(xiàn)死循環(huán)。

(二)用PV操作實(shí)現(xiàn)進(jìn)程的同步。

進(jìn)程的同步是指并發(fā)進(jìn)程之間存在一種制約關(guān)系,一個(gè)進(jìn)程的執(zhí)行依賴另一個(gè)進(jìn)程的消息,當(dāng)一個(gè)進(jìn)程沒有得到另一個(gè)進(jìn)程的消息時(shí)應(yīng)等待,直到消息到達(dá)才能被喚醒。

在計(jì)算機(jī)系統(tǒng)中為了完成某個(gè)任務(wù),進(jìn)程之間有時(shí)要協(xié)作,由于各進(jìn)程的執(zhí)行速率可能不同,于是可能導(dǎo)致各進(jìn)程在并發(fā)執(zhí)行過程中出現(xiàn)數(shù)據(jù)覆蓋和重復(fù)讀取數(shù)據(jù)的錯(cuò)誤,針對(duì)上述情況我們同樣可以用PV操作來實(shí)現(xiàn)進(jìn)程間互通消息的辦法控制進(jìn)程的執(zhí)行速度。

在PV操作實(shí)現(xiàn)同步時(shí),一定要根據(jù)具體的問題來定義信號(hào)和調(diào)用P操作或V操作。一個(gè)信號(hào)量與一個(gè)消息聯(lián)系在一起,當(dāng)有多個(gè)消息時(shí)必須定義多個(gè)信號(hào)量;測(cè)量不同的消息是否達(dá)到或發(fā)送不同的消息時(shí),應(yīng)對(duì)不同的信號(hào)量調(diào)用P操作或V操作。

三、用PV操作實(shí)現(xiàn)并發(fā)進(jìn)程互斥和同步應(yīng)該注意的問題

(一)用PV操作實(shí)現(xiàn)并發(fā)進(jìn)程的互斥和同步,要注意以下4個(gè)方面:1.識(shí)別臨界資源:一是看是否被共享,二是看是否有排他性要求。2.劃出臨界區(qū),PV原語操作應(yīng)分別緊靠臨界區(qū)的頭尾部。3.臨界區(qū)代碼應(yīng)盡可能小,且不能有死循環(huán)。4.要保證PV操作在程序相關(guān)的任一執(zhí)行流程上成對(duì)出現(xiàn)。

(二)進(jìn)程同步和進(jìn)程互斥之間有以下的關(guān)系:1.進(jìn)程互斥可在伙伴進(jìn)程之間,也可以在非伙伴進(jìn)程之間;同步發(fā)生在相互有邏輯關(guān)系的伙伴進(jìn)程之間。2.廣義地看,互斥是一種特殊的同步,所以把用來解決進(jìn)程互斥和同步的工具統(tǒng)稱為同步機(jī)制。

參考文獻(xiàn)

[1]孫鐘秀,譚耀銘。操作系統(tǒng)教程(第二版),高等教育出版社,1995