李潔

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

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

1 互斥描述

多個(gè)程序在并發(fā)執(zhí)行時(shí)，由于共享系統(tǒng)資源，如CPU、I/O設(shè)備等會(huì)形成相互制約的間接關(guān)系，這種間接制約關(guān)系稱之為互斥。為了保證這些進(jìn)程能有序地運(yùn)行，對(duì)于系統(tǒng)中的這類共享資源，必須由系統(tǒng)實(shí)施統(tǒng)一分配，即用戶在要使用這些資源之前應(yīng)先提出申請(qǐng)，而不能直接使用[1]，使用結(jié)束后要釋放資源。

1.1 信號(hào)量機(jī)制

信號(hào)量機(jī)制指兩個(gè)或兩個(gè)以上進(jìn)程利用彼此之間收發(fā)的簡(jiǎn)單信號(hào)來實(shí)現(xiàn)并發(fā)執(zhí)行，是一種卓有成效的進(jìn)程同步機(jī)制，被廣泛應(yīng)用于各種系統(tǒng)[2]。信號(hào)量被定義為含有整型數(shù)據(jù)項(xiàng)的結(jié)構(gòu)變量，其數(shù)據(jù)結(jié)構(gòu)定義如下：

typedef struct semaphore

{

int value;

PCB*pointer;

};

其中value 是信號(hào)量的值，pointer 是信號(hào)量的等待隊(duì)列指針。其值大于等于零表示可供并發(fā)進(jìn)程使用的某類資源數(shù)量，其值小于零表示該類資源已分配完，請(qǐng)求該資源的進(jìn)程被阻塞，其絕對(duì)值表示等待該資源的進(jìn)程數(shù)。

1.2 P、V原語(yǔ)

信號(hào)量的值僅能通過兩個(gè)標(biāo)準(zhǔn)的原子操作來訪問，即P操作和V 操作。P 操作和V 操作是兩條原語(yǔ)，執(zhí)行時(shí)是不可中斷的。每執(zhí)行一次P 操作，就是請(qǐng)求一個(gè)單位的該類資源，系統(tǒng)中可供分配的該類資源數(shù)減少一個(gè)；每執(zhí)行一個(gè)V 操作，就是釋放一個(gè)單位的源源，系統(tǒng)中可供分配的該類資源數(shù)增加一個(gè)。使用信號(hào)量機(jī)制和P、V原語(yǔ)描述進(jìn)程同步互斥關(guān)系時(shí)，首先要分析進(jìn)程間存在的哪些同步和互斥關(guān)系；其次，針對(duì)分析的同步和互斥分別設(shè)定同步和互斥信號(hào)量，并且說明各信號(hào)量的含義和初值；最后使用P、V原語(yǔ)描述進(jìn)程的活動(dòng)。

1.3 描述進(jìn)程間互斥關(guān)系所遵循的規(guī)律

使用信號(hào)量和P、V原語(yǔ)可以方便有效地解決臨界區(qū)問題。進(jìn)程間存在互斥關(guān)系，進(jìn)程活動(dòng)用P、V 原語(yǔ)描述時(shí)，先執(zhí)行P操作，后執(zhí)行V操作，臨界區(qū)在P、V操作中間，同一個(gè)互斥信號(hào)量的P、V操作必須成對(duì)出現(xiàn)在同一個(gè)進(jìn)程的代碼中，缺少P操作將會(huì)導(dǎo)致系統(tǒng)混亂，無法保證對(duì)臨界資源的互斥訪問；缺少V操作將會(huì)導(dǎo)致資源永遠(yuǎn)不被釋放，從而使因等待改資源而阻塞的進(jìn)程不能被喚醒[3]。

1.4 互斥信號(hào)量初值

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

2 互斥信號(hào)量不同取值情況分析

2.1 初值為1的情況舉例

進(jìn)程間互斥最典型的例子就是多個(gè)進(jìn)程共享一臺(tái)打印機(jī)，打印機(jī)是臨界資源，多個(gè)進(jìn)程之間的關(guān)系就是互斥，假定互斥信號(hào)量為mutex，每次只允許一個(gè)進(jìn)程使用，由信號(hào)量的物理含義可知，mutex初值應(yīng)為1，各并發(fā)進(jìn)程的程序描述如下：

semaphore mutex;

mutex=1;

…

Process Pi

{…

P(mutex);

進(jìn)程Pi的臨界區(qū)代碼；

V(mutex);

…}

分析此進(jìn)程活動(dòng)描述，互斥信號(hào)量mutex初值為1，表示共享的打印機(jī)只有一臺(tái)，第一個(gè)進(jìn)程要打印，首先申請(qǐng)打印機(jī)，執(zhí)行P(mutex)，信號(hào)量值減1，mutex=0，若此時(shí)又一進(jìn)程申請(qǐng)打印機(jī)，仍執(zhí)行P(mutex)，信號(hào)量值再減1，mutex=-1，表示此進(jìn)程進(jìn)入等待狀態(tài)，符合進(jìn)程互斥的關(guān)系。

2.2 初值不為1 的情況舉例

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

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

void philosopher(inti)

{

while(true)

{

P(c[i]);

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

…;

進(jìn)餐；

…;

V(c[i]);

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

…;

}}

在上述描述中，雖然解決了兩個(gè)相鄰的哲學(xué)家不會(huì)同時(shí)進(jìn)餐的問題，但若五位哲學(xué)家同時(shí)拿起左邊的筷子，再拿右邊的筷子時(shí)，都將因無筷子可用而陷入死鎖狀態(tài)?？梢杂迷黾右粋€(gè)互斥信號(hào)量的方法來解決此死鎖問題。設(shè)互斥信號(hào)量count，表示最多允許4位哲學(xué)家同時(shí)申請(qǐng)左邊的筷子，從而保證任何情況下至少有一位哲學(xué)家能同時(shí)拿到兩邊的筷子進(jìn)餐，使得每個(gè)哲學(xué)家均有進(jìn)餐的可能，所以count 初值為4，此時(shí)改進(jìn)的算法描述如下：

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]);

…;

進(jìn)餐；

…;

V(c[i]);

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

V(count);

…;

}}

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

3 結(jié)束語(yǔ)

在多道程序環(huán)境下，對(duì)于同處于一個(gè)系統(tǒng)中的多個(gè)進(jìn)程，在訪問臨界資源時(shí)必須保證互斥訪問，互斥信號(hào)量的初值決定著該臨界資源能同時(shí)為一個(gè)還是多個(gè)進(jìn)程訪問，通過實(shí)例得出互斥信號(hào)量初值有兩種情況，一次僅允許一個(gè)進(jìn)程訪問則信號(hào)量初值為1，一次為n個(gè)進(jìn)程訪問則信號(hào)量初值為n。