于占虎

[摘 要]以進(jìn)程的同步與互斥中的列車調(diào)度問題為例,分析了傳統(tǒng)的解決方法及存在的問題,提出了一種高效的、防止“餓死”的改進(jìn)算法。

[關(guān)鍵詞]進(jìn)程 P、V操作 信號量 餓死

[中圖分類號]R-05[文獻(xiàn)標(biāo)識碼]A[文章編號]1007-9416(2009)12-0108-02

1 引言

在多道程序設(shè)計(jì)的系統(tǒng)中,當(dāng)處理器的數(shù)量少于進(jìn)程的數(shù)量時(shí),多個進(jìn)程就會輪流使用處理器,即一個進(jìn)程的工作沒有全部完成之前,另一個進(jìn)程就開始工作。如果并發(fā)執(zhí)行的多個進(jìn)程共享了相同的資源,而進(jìn)程的調(diào)度又不加以控制,則不同的調(diào)度次序?qū)a(chǎn)生不同的結(jié)果,即系統(tǒng)會發(fā)生“與時(shí)間有關(guān)的錯誤”[1]。

荷蘭學(xué)者Dijkstra發(fā)明的信號量機(jī)制是一種卓有成效的進(jìn)程同步工具,它通過P、V兩個操作原語來保證進(jìn)程之間的同步與互斥,進(jìn)而可以避免產(chǎn)生與時(shí)間有關(guān)的錯誤[2]。信號量機(jī)制雖然能避免產(chǎn)生與時(shí)間有關(guān)的錯誤,但在使用時(shí),如果考慮不嚴(yán)密則會使系統(tǒng)效率大大降低,或者出現(xiàn)進(jìn)程長時(shí)間得不到服務(wù)的“餓死”現(xiàn)象。筆者結(jié)合列車調(diào)度問題,分析傳統(tǒng)解決方法的不足,并給出了既能提高效率,又能防止進(jìn)程“餓死”的改進(jìn)算法。

2 列車調(diào)度問題的描述

如圖1所示,假設(shè)A、B兩個火車站之間是單軌連接的,現(xiàn)有許多列車需經(jīng)過A站開往B站,也有許多列車需經(jīng)過B站開往A站,為確保行駛安全,必須保證在同一時(shí)刻兩站之間不能有相對行駛的列車,即當(dāng)有列車從某一車站開往另一個車站時(shí),從另一個車站開往本站的列車只能等待,當(dāng)有兩列列車分別從兩個車站出發(fā)相對行駛時(shí),系統(tǒng)就發(fā)生了與時(shí)間有關(guān)的錯誤。

3 傳統(tǒng)的解決方法及存在的問題

解決列車調(diào)度問題的最簡單的方法是使用P、V操作。將每列列車看作是一個進(jìn)程,將兩個車站之間的單軌鐵路看作是共享資源,設(shè)置一個互斥信號量Mutex,其初值為1,用于對共享資源的互斥訪問。多個進(jìn)程并發(fā)執(zhí)行的P、V操作算法如下:

經(jīng)過A站開往B站的列車:

經(jīng)過B站開往A站的列車:

processPAi processPBi

beginbegin

…………

P(Mutex); P(Mutex);

經(jīng)過A站到達(dá)B站;經(jīng)過B站到達(dá)A站;

V(Mutex); V(Mutex);

…………

endend

上述算法雖然避免了與時(shí)間有關(guān)的錯誤,但要求同一時(shí)刻在兩站之間只能有一列列車行駛,在這種情況下,系統(tǒng)的效率將大大降低。事實(shí)上,當(dāng)某列列車從一個車站開往另一個車站時(shí),同方向的列車也可以依次(但不可以同時(shí)出站)跟在后面同向行駛。因此,只需要某一方向的第一列列車申請共享資源的信號量Mutex即可,其它同向行駛的列車不必申請共享資源信號量,當(dāng)同一方向的所有列車均通過后再釋放共享資源信號量Mutex。

4 提高效率的算法

對上面的算法加以改進(jìn)。設(shè)置2個變量count1、count2分別對兩邊的列車進(jìn)行計(jì)數(shù),其初值均為0。由于每列列車均使用變量count1或count2,因此,設(shè)置信號量S1、S2分別用于對變量count1、count2的互斥訪問,其初值均為1,信號量S1和S2可以防止同一方向有兩列列車同時(shí)出站行駛。為安全起見,設(shè)置兩列列車從同一車站駛出的時(shí)間間隔不低于十分鐘,即每列列車在出站十分鐘后再釋放可以喚醒下列列車的信號量S1或S2。改進(jìn)后的P、V操作算法如下:

經(jīng)過A站開往B站的列車:

經(jīng)過B站開往A站的列車:

processPAi

processPBi

begin begin

…………

P(S1); P

(S2);

count1=count1+1;count2=count2+1;

if count1=1 then P(Mutex);if count2=1 then P(Mutex);

從A站開出;

從B站開出;

十分鐘后;

十分鐘后;

V(S1); V(S2);

…… ……

到達(dá)B站;

到達(dá)A站;

P(S1);

P(S2);

count1=count1-1;

Count2=count2-1;

if count1=0 then V(Mutex);if count2=0 then V(Mutex);

V(S1);V(S2);

…… ……

end end

改進(jìn)的算法可以充分的利用系統(tǒng)資源,提高了系統(tǒng)的效率,但又出現(xiàn)了新的問題:當(dāng)某一方向上有列車行駛時(shí),在這個方向上其它的列車也可以依次跟在后面行駛,如果這個方向上源源不斷的有列車駛出時(shí),對面方向上的列車將長時(shí)間處于等待狀態(tài)而不能駛出,此現(xiàn)象叫做進(jìn)程的“餓死”。

5 防止“餓死”的改進(jìn)算法

為了解決進(jìn)程的“餓死”現(xiàn)象,體現(xiàn)公平性原則,對算法做進(jìn)一步改進(jìn):當(dāng)某一方向的多列列車連續(xù)通過時(shí),如果對面方向有列車等待通過,則本方向上后到的列車將被阻塞。按照這一原則,可以在算法中增加一個信號量P,其初值為1,每列列車在通過之前,都需先爭奪信號量P,這樣,系統(tǒng)按照申請信號量S的順序進(jìn)行調(diào)度,這樣可以阻止對面后來的列車的通過機(jī)會,從而消除“餓死”現(xiàn)象。消除“餓死”現(xiàn)象的P、V操作算法如下:

經(jīng)過A站開往B站的列車:

經(jīng)過B站開往A站的列車:

processPAi

processPBi

begin begin

…… ……

P(S); P(S);

P(S1);P(S2);

count1=count1+1;

count2=count2+1;

if count1=1 then P(Mutex);

if count2=1 then P(Mutex);

從A站開出; 從B站開出;

V(S); V(S);

十分鐘后;十分鐘后;

V(S1);V(S2);

…………

到達(dá)B站; 到達(dá)A站;

P(S1); P(S2);

count1=count1-1;

Count2=count2-1;

if count1=0 then V(Mutex);

if count2=0 then V(Mutex);

V(S1); V(S2);

…………

end end

6 結(jié)語

P、V操作可以實(shí)現(xiàn)進(jìn)程的同步和共享資源的互斥使用,避免產(chǎn)生“與時(shí)間有關(guān)的錯誤”,但卻不能避免死鎖。當(dāng)申請和釋放信號量的次序安排不當(dāng)時(shí),系統(tǒng)即有可能發(fā)生死鎖。因此,合理的P、V操作次序也是確保算法正確、高效執(zhí)行的重要基礎(chǔ)。

[參考文獻(xiàn)]

[1] 譚耀銘.操作系統(tǒng)概論[M].北京:經(jīng)濟(jì)科學(xué)出版社,2000.4.

[2] 湯子瀛.計(jì)算機(jī)操作系統(tǒng)[M].西安:西安電子科技大學(xué)出版社,2002.7.