NO IMAGE

   引用

     闡述P,V原語的理論不得不提到的一個人便是赫赫有名的荷蘭科學家 E.W.Dijkstra。如果你對這位科學家沒有什麼印象的話,提起解決圖論中最短路徑問題的Dijkstra演算法應當是我們再熟悉不過的了。P,V原 語的概念以及P,V操作當中需要使用到的訊號量的概念都是由他在1965年提出的。 

訊號量是最早出現的用來解決程序同步與互斥問題的機制(也可實現程序通訊),包括一個稱為信 號量的變數及對它進行的兩個原語操作。訊號量為一個整數,我們設這個訊號量為:sem。很顯然,我們規定在sem大於等於零的時候代表可供併發程序使用的 資源實體數,sem小於零的時候,表示正在等待使用臨界區的程序的個數。根據這個原則,在給訊號量附初值的時候,我們顯然就要設初值大於零。

p操作和v操作是不可中斷的程式段,稱為原語。P,V原語中P是荷蘭語的Passeren,相當於英文的pass, V是荷蘭語的Verhoog,相當於英文中的incremnet。

且在P,V願語執行期間不允許有中斷的發生。

對於具體的實現,方法非常多,可以用硬體實現,也可以用軟體實現。這種訊號量機制必須有公共記憶體,不能用於分散式作業系統,這是它最大的弱點。

————————————————————-

首先應弄清PV操作的含義:PV操作由P操作原語和V操作原語組成(原語是不可中斷的過程),對訊號量進行操作,具體定義如下:

  P(S):①將訊號量S的值減1,即S=S-1;

  ②如果S>=0,則該程序繼續執行;否則該程序置為等待狀態,排入等待佇列。

  V(S):①將訊號量S的值加1,即S=S 1;

  ②如果S>0,則該程序繼續執行;否則釋放佇列中第一個等待訊號量的程序。

PV操作的意義:我們用訊號量及PV操作來實現程序的同步和互斥。PV操作屬於程序的低階通訊。

什麼是訊號量?訊號量(semaphore)的資料結構為一個值和一個指標,指標指向等待該 訊號量的下一個程序。訊號量的值與相應資源的使用情況有關。當它的值大於0時,表示當前可用資源的數量;當它的值小於0時,其絕對值表示等待使用該資源的 程序個數。注意,訊號量的值僅能由PV操作來改變。

一般來說,訊號量S>=0時,S表示可用資源的數量。執行一次P操作意味著請求分配一個單位資源,因此S的值減1;

當S<0時,表示已經沒有可用資源,請求者必須等待別的程序釋放該類資源,它才能執行下去。而執行一個V操作意味著釋放一個單位資源,因此S的值加1;

若S<=0,表示有某些程序正在等待該資源,因此要喚醒一個等待狀態的程序,使之執行下去。

  利用訊號量和PV操作實現程序互斥的一般模型是:

程序P1 程序P2 …… 程序Pn

…… …… ……

P(S); P(S); P(S);

臨界區; 臨界區; 臨界區;

V(S); V(S); V(S);

…… …… …… ……

  其中訊號量S用於互斥,初值為1。

  使用PV操作實現程序互斥時應該注意的是:

(1)每個程式中使用者實現互斥的P、V操作必須成對出現,先做P操作,進臨界區,後做V操作,出臨界區。若有多個分支,要認真檢查其成對性。

(2)P、V操作應分別緊靠臨界區的頭尾部,臨界區的程式碼應儘可能短,不能有死迴圈。

(3)互斥訊號量的初值一般為1。

  利用訊號量和PV操作實現程序同步

PV操作是典型的同步機制之一。用一個訊號量與一個訊息聯絡起來,當訊號量的值為0時,表示期望的訊息尚未產生;當訊號量的值非0時,表示期望的訊息已經存在。用PV操作實現程序同步時,呼叫P操作測試訊息是否到達,呼叫V操作傳送訊息。

  使用PV操作實現程序同步時應該注意的是:

(1)分析程序間的制約關係,確定訊號量種類。在保持程序間有正確的同步關係情況下,哪個程序先執行,哪些程序後執行,彼此間通過什麼資源(訊號量)進行協調,從而明確要設定哪些訊號量。

(2)訊號量的初值與相應資源的數量有關,也與P、V操作在程式程式碼中出現的位置有關。

(3)同一訊號量的P、V操作要成對出現,但它們分別在不同的程序程式碼中。

【例1】生產者-消費者問題

在多道程式環境下,程序同步是一個十分重要又令人感興趣的問題,而生產者-消費者問題是其中一個有代表性的程序同步問題。下面我們給出了各種情況下的生產者-消費者問題,深入地分析和透徹地理解這個例子,對於全面解決作業系統內的同步、互斥問題將有很大幫助。

(1)一個生產者,一個消費者,公用一個緩衝區。

定義兩個同步訊號量:

empty——表示緩衝區是否為空,初值為1。

full——表示緩衝區中是否為滿,初值為0。

生產者程序

while(TRUE){

  生產一個產品;

  P(empty);

  產品送往Buffer;

  V(full);

  }

消費者程序

while(TRUE){

  P(full);

  從Buffer取出一個產品;

  V(empty);

  消費該產品;

  }

(2)一個生產者,一個消費者,公用n個環形緩衝區。

定義兩個同步訊號量:

empty——表示緩衝區是否為空,初值為n。

full——表示緩衝區中是否為滿,初值為0。

  設緩衝區的編號為1~n&61485;1,定義兩個指標in和out,分別是生產者程序和消費者程序使用的指標,指向下一個可用的緩衝區。

生產者程序

while(TRUE){

  生產一個產品;

  P(empty);

  產品送往buffer(in);

  in=(in 1)mod n;

  V(full);

  }

消費者程序

while(TRUE){

P(full);

  從buffer(out)中取出產品;

  out=(out 1)mod n;

  V(empty);

  消費該產品;

  }

(3)一組生產者,一組消費者,公用n個環形緩衝區

  在這個問題中,不僅生產者與消費者之間要同步,而且各個生產者之間、各個消費者之間還必須互斥地訪問緩衝區。

定義四個訊號量:

empty——表示緩衝區是否為空,初值為n。

full——表示緩衝區中是否為滿,初值為0。

mutex1——生產者之間的互斥訊號量,初值為1。

mutex2——消費者之間的互斥訊號量,初值為1。

  設緩衝區的編號為1~n&61485;1,定義兩個指標in和out,分別是生產者程序和消費者程序使用的指標,指向下一個可用的緩衝區。

生產者程序

while(TRUE){

  生產一個產品;

  P(empty);

  P(mutex1);

  產品送往buffer(in);

  in=(in 1)mod n;

  V(mutex1);

  V(full);

  }

消費者程序

while(TRUE){

P(full);

  P(mutex2);

  從buffer(out)中取出產品;

  out=(out 1)mod n;

  V(mutex2);

  V(empty);

  消費該產品;

  }

  需要注意的是無論在生產者程序中還是在消費者程序中,兩個P操作的次序不能顛倒。應先執行同步訊號量的P操作,然後再執行互斥訊號量的P操作,否則可能造成程序死鎖。

【例2】桌上有一空盤,允許存放一隻水果。爸爸可向盤中放蘋果,也可向盤中放桔子,兒子專等吃盤中的桔子,女兒專等吃盤中的蘋果。規定當盤空時一次只能放一隻水果供吃者取用,請用P、V原語實現爸爸、兒子、女兒三個併發程序的同步。

分析 在本題中,爸爸、兒子、女兒共用一個盤子,盤中一次只能放一個水果。當盤子為空時,爸爸可將一個水果放入果盤中。若放入果盤中的是桔子,則允許兒子吃,女 兒必須等待;若放入果盤中的是蘋果,則允許女兒吃,兒子必須等待。本題實際上是生產者-消費者問題的一種變形。這裡,生產者放入緩衝區的產品有兩類,消費 者也有兩類,每類消費者只消費其中固定的一類產品。

  解:在本題中,應設定三個訊號量S、So、Sa,訊號量S表示盤子是否為空,其初值為l;訊號量So表示盤中是否有桔子,其初值為0;訊號量Sa表示盤中是否有蘋果,其初值為0。同步描述如下:

int S=1;

int Sa=0;

int So=0;

  main()

  {

  cobegin

  father(); /*父親程序*/

  son(); /*兒子程序*/

  daughter(); /*女兒程序*/

  coend

  }

  father()

  {

  while(1)

  {

  P(S);

  將水果放入盤中;

  if(放入的是桔子)V(So);

  else V(Sa);

  }

  }

  son()

  {

  while(1)

  {

  P(So);

  從盤中取出桔子;

  V(S);

  吃桔子;

  }

  }

  daughter()

  {

  while(1)

  {

  P(Sa);

  從盤中取出蘋果;

  V(S);

  吃蘋果;

  }

  }

思考題:

四個程序A、B、C、D都要讀一個共享檔案F,系統允許多個程序同時讀檔案F。但限制是程序A和程序C不能同時讀檔案F,程序B和程序D也不能同時讀檔案F。為了使這四個程序併發執行時能按系統要求使用檔案,現用PV操作進行管理,請回答下面的問題:

  (1)應定義的訊號量及初值: 。

  (2)在下列的程式中填上適當的P、V操作,以保證它們能正確併發工作:

  A() B() C() D()

  { { { {

  [1]; [3]; [5]; [7];

  read F; read F; read F; read F;

  [2]; [4]; [6]; [8];

  } } } }

  思考題解答:

(1)定義二個訊號量S1、S2,初值均為1,即:S1=1,S2=1。其中程序A和C使用訊號量S1,程序B和D使用訊號量S2。

(2)從[1]到[8]分別為:P(S1) V(S1) P(S2) V(S2) P(S1) V(S1) P(S2) V(S2)

訊號量、PV操作是解決程序間的同步與互斥問題的。

★ 做題時尤其要注意隱藏的同步、互斥問題。這些問題通常可以歸入生產者-消費者問題和閱讀者-寫入者問題。

★ PV操作一定是成對出現的,但是這不意味著它會在一個程序內成對出現。

★ 在互斥關係中,PV操作一定是在一個程序內成對出現。而且,訊號一定大於0,具體多少視情況而定。而對於同步關係,則一對PV操作在兩個程序或者更多的程序中出現。

★ 對於同步關係,訊號量可能為0,也可能不為0;用於同步的訊號個數可能1個,也可能是多個。

★ 對訊號量為1的,應該先執行V操作。

★ 在生產者-消費者問題中,要設定三個訊號量:empty-空閒的快取區數量,初值為n;full-已填充的快取區數量,初值為0;mutex-保證只有一個程序在寫入快取區,初值為1。
★ 在閱讀者-寫入者問題中,設定兩個訊號量:訊號量access-控制寫入互斥,初值為1;訊號量rc-控制對共享變數ReadCount(讀者統計值)的互斥訪問。