互斥信號量初值不同情況分析

李潔

(宿遷學院信息工程學院，江蘇宿遷223800)

進程中存在兩種制約關系，一種為直接制約關系即同步，主要是由于執行時序上的限制而形成的相互合作的制約關系；另一種為間接制約關系即互斥，主要是由于共享資源而形成的關系，這種共享的資源其特殊性在于一次僅允許一個進程使用，稱為臨界資源，訪問臨界資源的程序代碼稱為臨界區。在進程互斥關系中，信號量初值一般為1，含義為使用的臨界資源的數量為1 個，一次僅允許一個進程使用，但也存在特殊情況其初值不為1，下面就來討論下互斥信號量的不同取值情況。

1 互斥描述

多個程序在并發執行時，由于共享系統資源，如CPU、I/O設備等會形成相互制約的間接關系，這種間接制約關系稱之為互斥。為了保證這些進程能有序地運行，對于系統中的這類共享資源，必須由系統實施統一分配，即用戶在要使用這些資源之前應先提出申請，而不能直接使用[1]，使用結束后要釋放資源。

1.1 信號量機制

信號量機制指兩個或兩個以上進程利用彼此之間收發的簡單信號來實現并發執行，是一種卓有成效的進程同步機制，被廣泛應用于各種系統[2]。信號量被定義為含有整型數據項的結構變量，其數據結構定義如下：

typedef struct semaphore

{

int value;

PCB*pointer;

};

其中value 是信號量的值，pointer 是信號量的等待隊列指針。其值大于等于零表示可供并發進程使用的某類資源數量，其值小于零表示該類資源已分配完，請求該資源的進程被阻塞，其絕對值表示等待該資源的進程數。

1.2 P、V原語

信號量的值僅能通過兩個標準的原子操作來訪問，即P操作和V 操作。P 操作和V 操作是兩條原語，執行時是不可中斷的。每執行一次P 操作，就是請求一個單位的該類資源，系統中可供分配的該類資源數減少一個；每執行一個V 操作，就是釋放一個單位的源源，系統中可供分配的該類資源數增加一個。使用信號量機制和P、V原語描述進程同步互斥關系時，首先要分析進程間存在的哪些同步和互斥關系；其次，針對分析的同步和互斥分別設定同步和互斥信號量，并且說明各信號量的含義和初值；最后使用P、V原語描述進程的活動。

1.3 描述進程間互斥關系所遵循的規律

使用信號量和P、V原語可以方便有效地解決臨界區問題。進程間存在互斥關系，進程活動用P、V 原語描述時，先執行P操作，后執行V操作，臨界區在P、V操作中間，同一個互斥信號量的P、V操作必須成對出現在同一個進程的代碼中，缺少P操作將會導致系統混亂，無法保證對臨界資源的互斥訪問；缺少V操作將會導致資源永遠不被釋放，從而使因等待改資源而阻塞的進程不能被喚醒[3]。

1.4 互斥信號量初值

互斥信號量初值一般情況下為1，表示一次僅允許一個進程使用，比如n個進程互斥訪問共享資源，只能有1個進程獲得資源，剩余進程將進入等待狀態，信號量取值范圍為-n~1[4]。若有特殊說明即允許多個進程共享一個互斥段，比如n個進程共享資源，允許m個進程進入該互斥段，則信號量的初值為m，取值范圍為-(n-m)~m。

2 互斥信號量不同取值情況分析

2.1 初值為1的情況舉例

進程間互斥最典型的例子就是多個進程共享一臺打印機，打印機是臨界資源，多個進程之間的關系就是互斥，假定互斥信號量為mutex，每次只允許一個進程使用，由信號量的物理含義可知，mutex初值應為1，各并發進程的程序描述如下：

semaphore mutex;

mutex=1;

…

Process Pi

{…

P(mutex);

進程Pi的臨界區代碼；

V(mutex);

…}

分析此進程活動描述，互斥信號量mutex初值為1，表示共享的打印機只有一臺，第一個進程要打印，首先申請打印機，執行P(mutex)，信號量值減1，mutex=0，若此時又一進程申請打印機，仍執行P(mutex)，信號量值再減1，mutex=-1，表示此進程進入等待狀態，符合進程互斥的關系。

2.2 初值不為1 的情況舉例

在經典的同步問題——哲學家進餐問題出現的死鎖情況可以用互斥信號量來解決。哲學家進餐問題描述五位哲學家圍坐在一張圓桌前用餐，分別在其周圍放置五只筷子，且每只筷子只允許一個人使用。當一位哲學家需要用餐時，就去取其左右兩邊的筷子，只有拿到兩只筷子，方可就餐[5]。假設五位哲學家用五個進程表示，五只筷子為臨界資源，設互斥信號量為c[i](i=0,…,4)，左邊筷子為c[i]，右邊筷子為c[(i+1)%5]，初始值為1，表示每只筷子只允許一個人使用。哲學家進餐問題的算法描述如下：

struct semaphore c[5]={1,1,1,1,1};

void philosopher(inti)

{

while(true)

{

P(c[i]);

P(c[(i+1)%5]);

…;

進餐；

…;

V(c[i]);

V(c[(i+1)%5]);

…;

}}

在上述描述中，雖然解決了兩個相鄰的哲學家不會同時進餐的問題，但若五位哲學家同時拿起左邊的筷子，再拿右邊的筷子時，都將因無筷子可用而陷入死鎖狀態。可以用增加一個互斥信號量的方法來解決此死鎖問題。設互斥信號量count，表示最多允許4位哲學家同時申請左邊的筷子，從而保證任何情況下至少有一位哲學家能同時拿到兩邊的筷子進餐，使得每個哲學家均有進餐的可能，所以count 初值為4，此時改進的算法描述如下：

struct semaphore c[5]={1,1,1,1,1};

struct semaphore count=4;

void philosopher(int i)

{

while(true)

{P(count);

P(c[i]);

P(c[(i+1)%5]);

…;

進餐；

…;

V(c[i]);

V(c[(i+1)%5]);

V(count);

…;

}}

分析此改進算法，在原先算法基礎上只加了兩句原語P(count)和V(count)。count 和c[i]均為互斥信號量，c[i]初值為1，表示每只筷子只允許一位哲學家使用，count 初值為4，表示最多允許4 位哲學家同時使用，假設第一位哲學家想進餐，在申請左邊筷子之前，首先執行P(count)，count 值減1，count 值從4變為3，表示還允許3位哲學家執行，其他哲學家同樣申請左邊筷子之前都要先執行P(count)，執行P 操作，count 值減1 ，當count 值為0 時，若再有哲學家申請，執行P(count)，count 值從0變為-1，說明此哲學家進入等待狀態，這樣就可以保證只能有4位哲學家同時執行，一位哲學家可以拿到左右兩邊的筷子，結束后釋放資源，從而保證其他所有哲學家都可以執行。

3 結束語

在多道程序環境下，對于同處于一個系統中的多個進程，在訪問臨界資源時必須保證互斥訪問，互斥信號量的初值決定著該臨界資源能同時為一個還是多個進程訪問，通過實例得出互斥信號量初值有兩種情況，一次僅允許一個進程訪問則信號量初值為1，一次為n個進程訪問則信號量初值為n。