使用PV操作解決列車(chē)調(diào)度問(wèn)題的改進(jìn)算法

于占虎

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

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

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

1 引言

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

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

2 列車(chē)調(diào)度問(wèn)題的描述

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

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

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

經(jīng)過(guò)A站開(kāi)往B站的列車(chē):

經(jīng)過(guò)B站開(kāi)往A站的列車(chē):

processPAi processPBi

beginbegin

…………

P(Mutex); P(Mutex);

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

V(Mutex); V(Mutex);

…………

endend

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

4 提高效率的算法

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

經(jīng)過(guò)A站開(kāi)往B站的列車(chē):

經(jīng)過(guò)B站開(kāi)往A站的列車(chē):

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站開(kāi)出;

從B站開(kāi)出;

十分鐘后;

十分鐘后;

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)了新的問(wèn)題:當(dāng)某一方向上有列車(chē)行駛時(shí),在這個(gè)方向上其它的列車(chē)也可以依次跟在后面行駛,如果這個(gè)方向上源源不斷的有列車(chē)駛出時(shí),對(duì)面方向上的列車(chē)將長(zhǎng)時(shí)間處于等待狀態(tài)而不能駛出,此現(xiàn)象叫做進(jìn)程的“餓死”。

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

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

經(jīng)過(guò)A站開(kāi)往B站的列車(chē):

經(jīng)過(guò)B站開(kāi)往A站的列車(chē):

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站開(kāi)出; 從B站開(kāi)出;

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é)語(yǔ)

P、V操作可以實(shí)現(xiàn)進(jìn)程的同步和共享資源的互斥使用,避免產(chǎn)生“與時(shí)間有關(guān)的錯(cuò)誤”,但卻不能避免死鎖。當(dāng)申請(qǐng)和釋放信號(hào)量的次序安排不當(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.