淺析PV操作在多道程序系統中的應用

[摘 要]在多道程序系統中,若干個進程可以同時執行,各進程之間可以是無關的,也可以是有交往的。有交往的并發進程由于共享內部資源,因此導致進程執行速度上的制約,這種制約分為:間接制約與直接制約。間接制約引起進程之間的互斥執行,直接制約引起進程的同步執行。如果并發進程對資源竟爭不當會導致各種并發問題,我們可用PV操作來管理相關臨界區,實現進程的互斥和同步。

[關鍵詞]PV操作 多道系統 臨界區 互斥 同步

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

并發進程在訪問資源時可能有兩種關系:一種是競爭關系,另一種是協作關系。當并發進程存在競爭關系時必須互斥地使用共享資源;當并發進程存在協作關系時必須互通消息。把這兩種關系分別稱為“進程互斥”和“進程的同步”,正確應用PV操作,可實現進程互斥和同步。

一、PV原語和多道程序系統

(一)為了確保PV操作自身執行的正確性,約定PV操作必須由兩個不可中斷的過程,我們把不可被中斷的過程稱為“原語”。我們設置信號量sem,sem大于等于零時代表可供并發進程使用的資源實體數,但sem小于零時則表示正在等待使用臨界區的進程數。

PV操作是由兩個操作,即P操作和V操作組成。P操作和V操作是兩個在信號量上進行的過程。

(二)讓多個計算機問題同時裝入一個計算機系統的主存儲器并行執行,這種設計技術稱“多道程序設計”,這種計算機系統稱“多道程序設計系統”或簡稱“多道系統”。多道程序設計系統是在計算機內存中同時存放幾道相互獨立的程序,使它們在管理程序控制之下,相互穿插的運行。兩個或兩個以上的程序在計算機系統中同處于開始和結束之間的狀態。多道程序技術運行的特征:多道、宏觀上運行、微觀上串行。

在多道程序設計中,若干個進程可以同時執行,并發進程之間可以是無關的,也可以有交往的。例如只有一個教室,這個公有資源使得每個班只能互斥使用它,這就是間接制約。進程的互斥與同步可以很好的通過信號量和PV原語來實現。并發進程的資源競爭不當還會導致共享沖突。進程間正確的互斥和同步能避免出現與時間有關的錯誤。

二、PV操作

如果在并發進程中,有進程在相關臨界區執行時,不讓另一個進程進入相關的臨界區執行就不會形成多個進程對相同的共享變量交叉訪問。于是可避免出現與時間有關的錯誤。即只要涉及相同變量的若干個進程的相關臨界區互斥執行,就不會造成與時間有關的錯誤。

(一)用PV操作實現進程的互斥。

進程的互斥是指:當若干個進程都要使用某一共享變量時,任何時刻最多只允許一個進程去使用其他要使用該變量的進程必須等待,直到占用資源者釋放了該資源。用PV操作實現對相關臨界區的管理,只要用一個信號量與一組涉及共享變量的相關臨界區聯系起來,讓并發進程互斥進入自己的臨界區。

1.PV操作可確保共享數據的一致性。

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

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;

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

2.調用PV操作時要注意確保并發效率,同時避免出現并發問題。上述程序段要注意以下不良的管理方法,寫成:

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;

上述程序把不屬于臨界區的語句“{按旅客要求找到Aj};”也放進了臨界區,降低了系統并發執行的能力。我們的原則是能并發執行部分要保持其并發性,只有涉及到共享變量的程序段才是需要互斥執行臨界區,臨界區的代碼應盡量小,同時確保不會出現死循環。

(二)用PV操作實現進程的同步。

進程的同步是指并發進程之間存在一種制約關系,一個進程的執行依賴另一個進程的消息,當一個進程沒有得到另一個進程的消息時應等待,直到消息到達才能被喚醒。

在計算機系統中為了完成某個任務,進程之間有時要協作,由于各進程的執行速率可能不同,于是可能導致各進程在并發執行過程中出現數據覆蓋和重復讀取數據的錯誤,針對上述情況我們同樣可以用PV操作來實現進程間互通消息的辦法控制進程的執行速度。

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

三、用PV操作實現并發進程互斥和同步應該注意的問題

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

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

參考文獻

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