使用PV操作解決列車調度問題的改進算法

于占虎

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

[關鍵詞]進程 P、V操作 信號量 餓死

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

1 引言

在多道程序設計的系統中,當處理器的數量少于進程的數量時,多個進程就會輪流使用處理器,即一個進程的工作沒有全部完成之前,另一個進程就開始工作。如果并發執行的多個進程共享了相同的資源,而進程的調度又不加以控制,則不同的調度次序將會產生不同的結果,即系統會發生“與時間有關的錯誤”[1]。

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

2 列車調度問題的描述

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

3 傳統的解決方法及存在的問題

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

經過A站開往B站的列車:

經過B站開往A站的列車:

processPAi processPBi

beginbegin

…………

P(Mutex); P(Mutex);

經過A站到達B站;經過B站到達A站;

V(Mutex); V(Mutex);

…………

endend

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

4 提高效率的算法

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

經過A站開往B站的列車:

經過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);

…… ……

到達B站;

到達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

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

5 防止“餓死”的改進算法

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

經過A站開往B站的列車:

經過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);

…………

到達B站; 到達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 結語

P、V操作可以實現進程的同步和共享資源的互斥使用,避免產生“與時間有關的錯誤”,但卻不能避免死鎖。當申請和釋放信號量的次序安排不當時,系統即有可能發生死鎖。因此,合理的P、V操作次序也是確保算法正確、高效執行的重要基礎。

[參考文獻]

[1] 譚耀銘.操作系統概論[M].北京:經濟科學出版社,2000.4.

[2] 湯子瀛.計算機操作系統[M].西安:西安電子科技大學出版社,2002.7.