武秀川　翟一鳴　任滿杰

摘要:本文對集中式操作系統(tǒng)和分布式操作系統(tǒng)中的同步互斥機制進行了對比分析,并對這兩種系統(tǒng)中的互斥策略通過比較教學(xué)法進行了進一步研究。

關(guān)鍵詞:操作系統(tǒng);集中式系統(tǒng);分布式操作系統(tǒng);同步;互斥

中圖分類號:G642 文獻標(biāo)識碼:B

1引言

分布計算系統(tǒng)中的各種資源是在地理上和物理上分布的,這種分布會造成信號傳播過程中的延遲以及部分失效,因此與單機操作系統(tǒng)相比,分布計算系統(tǒng)的資源管理和資源調(diào)度更加復(fù)雜。

在研究生的“分布式操作系統(tǒng)”和本科生的“操作系統(tǒng)”教學(xué)過程中,通過分布式系統(tǒng)和集中式系統(tǒng)中對資源的同步互斥機制進行比較教學(xué),使得學(xué)生對互斥算法的了解更為透徹,分別取得了較好的教學(xué)效果。

2系統(tǒng)中的同步

無論集中式系統(tǒng)還是分布式系統(tǒng)中,為了實現(xiàn)多進程有效共享系統(tǒng)中的各類資源,都需要用同步機構(gòu)進行互斥控制系統(tǒng)進行資源的調(diào)度和管理。在單機集中式系統(tǒng)中通常使用信號燈以及P-V操作進行同步控制并實現(xiàn)互斥算法,而在分布式系統(tǒng)中使用報文進行通信以實現(xiàn)互斥控制。由于集中式系統(tǒng)和分布式系統(tǒng)所采用的同步機構(gòu)不同,因此要求也不同。

集中式系統(tǒng)和分布式系統(tǒng)中實現(xiàn)同步均可以用硬件方法也可以用軟件方法,通過比較教學(xué)使學(xué)生加深理解。

2.1集中式系統(tǒng)中的同步

集中式系統(tǒng)中同步的硬件實現(xiàn)方法是借助于TS(Test and Set)、Compare-and-Swap以及Fetch-and-Add等硬件機器指令,具體做法是通過為每個可共享的資源設(shè)置一個鎖,通過進入臨界區(qū)時的關(guān)鎖和退出臨界區(qū)時的開鎖以達到對共享的臨界資源的互斥同步控制。該方法雖然可以實現(xiàn)互斥且實現(xiàn)簡單,但是不符合“讓權(quán)等待”的同步機制準(zhǔn)則。

集中式系統(tǒng)中同步的軟件實現(xiàn)方法通常是采用信號量機制。最簡單的是整型信號量機制,通過兩個標(biāo)準(zhǔn)的P、V操作實現(xiàn)資源的互斥使用。為了使得多個同類資源能夠被有效的互斥使用,在信號量機制的概念中引入記錄型信號量加以實現(xiàn)。采用AND型信號量可以較為有效的避免多個進程同時要求多種共享資源時發(fā)生死鎖的問題。為了讓進程能夠一次使用多個同類資源而且不用進行多次等待操作(P操作),又使用信號量集機制進行控制。

實際上互斥是一種特殊的同步,軟件方法中還經(jīng)常使用Dekker算法和Peterson等算法簡單的實現(xiàn)進程間的互斥。此外還有管程等同步控制機制。

2.2分布式系統(tǒng)中的同步

在分布式系統(tǒng)中由于沒有共享的主存,因此主要使用報文進行通信以實現(xiàn)同步?？偟膩碚f,分布式系統(tǒng)中的同步系統(tǒng)其本質(zhì)就是使得各種使用共享資源的操作或活動形成一個有序序列,或者說同步機構(gòu)的目的就是給使用資源的多個進程提供某種方法和手段使分布式系統(tǒng)保持一個一致的狀態(tài),如多副本文件系統(tǒng)的一致性等。

分布式系統(tǒng)中實現(xiàn)硬件同步的方法一般是采用物理時鐘、事件計數(shù)器、順序器等。物理時鐘方法中,時鐘服務(wù)器從WWV或GEOS處獲得UTC,根據(jù)系統(tǒng)和用戶的需要以集中式物理時鐘的方式或分布式物理時鐘的方式實現(xiàn)同步控制。在教學(xué)的過程中,要給學(xué)生著重說明這里的集中式物理時鐘方式中的集中式與單機系統(tǒng)中的集中式的不同。這里所謂的集中式物理方式是指在分布式系統(tǒng)中由時鐘服務(wù)器統(tǒng)一的以基于廣播的方式和請求驅(qū)動的方式向整個分布式系統(tǒng)提供同步所需要的時鐘。在基于廣播的方式中,集中的時鐘服務(wù)員定期的向分布式系統(tǒng)中的各個成員廣播當(dāng)前的時間,由接收到廣播時間的各個成員對時間進行處理。與此不同的是在集中式物理時鐘的請求驅(qū)動方式中,由系統(tǒng)中的各個成員向集中式的時鐘服務(wù)員發(fā)出請求以求獲得當(dāng)前的時間。分布式系統(tǒng)中的集中式物理時鐘服務(wù)員的可靠性差,同時也是系統(tǒng)的瓶頸,因為時鐘服務(wù)員的崩潰可能導(dǎo)致系統(tǒng)的崩潰。分布式系統(tǒng)中的分布式物理時鐘與上述集中式物理時鐘的方法不同,它是由系統(tǒng)中的各個成員在規(guī)定的時間內(nèi)向其它成員廣播它的當(dāng)前時間并按照約定的方法進行時間的校正。

由于分布式系統(tǒng)中資源的廣泛分布性,很難準(zhǔn)確地獲得系統(tǒng)中每個機器確切的時鐘值,因此實際上很難做到準(zhǔn)確地同步,所以一般在分布式系統(tǒng)中更多的采用基于Lamport“在先發(fā)生關(guān)系”的邏輯時鐘進行邏輯時鐘校正以給分布式系統(tǒng)中的各個事件一個惟一的排序,從而達到同步的目的。

分布式系統(tǒng)中實現(xiàn)互斥同步控制的最簡單的方法是在并發(fā)執(zhí)行的各個進程中選定一個進程作為協(xié)調(diào)者。當(dāng)任一個進程想進入臨界區(qū)時,首先要向協(xié)調(diào)者進程發(fā)送請求報文申請臨界區(qū)進入許可。協(xié)調(diào)者進程根據(jù)目前臨界區(qū)中的進程情況或者同意或者拒絕請求者進程進入臨界區(qū)。這樣的過程是通過報文的傳遞進行的。如果目前臨界區(qū)內(nèi)已有進程的話協(xié)調(diào)者或者拒絕或者不回答請求的進程。無論是哪種方式,系統(tǒng)都要設(shè)置一個緩沖隊列用來存放被阻塞的請求進程。當(dāng)臨界區(qū)被退出后,由退出進程向協(xié)調(diào)者進程發(fā)送一個釋放報文,協(xié)調(diào)者進程將進入臨界區(qū)許可報文發(fā)送給相應(yīng)的被阻塞隊列中的第一個進程,使其退出等待隊列進入臨界區(qū)。顯然該算法的實現(xiàn)機制保證不會出現(xiàn)餓死和死鎖現(xiàn)象。該方法實際上是在分布式系統(tǒng)中模仿單機集中式系統(tǒng)的實現(xiàn)方式,存在同樣的問題即性能效率低,可靠性差。

分布式互斥算法中的所有進程都是平等的,沒有協(xié)調(diào)者進程的角色?；コ馑惴ㄒ话惴譃榛诹钆频暮头腔诹钆频膬纱箢?。

在教學(xué)過程中主要介紹具有代表性的兩個算法,以使學(xué)生對分布式互斥算法有清晰的理解。

非基于令牌的分布式互斥算法,典型的是Lamport時間戳算法。為了討論上的簡單,假定消息是按它們被發(fā)送的順序被接收,而且發(fā)出的消息最后一定會被接收到。每個進程均可向其他任何進程直接發(fā)送報文,每個進程均有一個申請隊列,隊列中最初只有一項T0:P0申請,這里的P0是最初獲得資源的進程,T0是比其他任何邏輯時鐘值均小的初值。

Lamport時間戳分布式互斥算法由以下5條規(guī)則組成。

(1) 一個進程Pi如果為了申請資源,它向其它各個進程發(fā)送具有時間戳Tm:Pi的申請資源的報文,并把此報文也放到自己的申請隊列中;

(2) 一個進程Pj如果收到具有時間戳Tm:Pi的申請資源的報文,它把此報文放到自己的申請隊列中,并將向Pi發(fā)送一個帶有時間戳的承認報文。如果Pj正在臨界區(qū)或正在發(fā)送自己的申請報文,則此承認報文要等到Pj從臨界區(qū)中退出之后或Pj發(fā)送完自己的申請報文之后再發(fā)送,否則立即發(fā)送;

(3) 一個進程Pi如果想釋放資源,它先從自己的申請隊列中刪除對應(yīng)的Tm:Pi申請報文,并向所有其他進程發(fā)送具有時間戳的Pi釋放資源的報文;

(4) 一個進程Pj如果收到Pi釋放資源的報文,它從自己的申請隊列中刪除Tm:Pi申請報文;

(5) 當(dāng)滿足下述兩個條件時,申請資源的進程Pi獲得資源:

①Pi的申請隊列中有Tm:Pi申請報文,并且根據(jù)時間戳它排在所有其它進程發(fā)來的申請報文前面;

②Pi收到所有其它進程的承認報文,其上面的時間戳值大于Tm。

教學(xué)過程中請同學(xué)思考:在上述算法中,某進程進入一次臨界區(qū)需要交換多少個報文?了解了上述互斥算法的過程,學(xué)生很容易得出結(jié)論:任何進程進入一次臨界區(qū)需要3*(n-1)個報文。進而可以啟發(fā)學(xué)生根據(jù)規(guī)則對上述算法進行改進從而使得任何一個進程進入一次臨界區(qū)最多需要3*(n-1)個報文,如果互斥使用臨界資源的進程數(shù)目很多時,可以大大地降低交換報文的通信開銷。

基于令牌的分布式互斥算法中對于各進程更具公平性的是基于時間戳的令牌互斥算法。令牌是一個特殊的報文,該報文中包含了發(fā)送該令牌的進程的進程狀態(tài)表。每個進程保持一張進程狀態(tài)表,記錄它所知的進程狀態(tài),進程狀態(tài)包括該進程是否為請求進程,以及得到該狀態(tài)的時間。

算法如下:

(1) 初始化時,每個進程的狀態(tài)表中各個進程均為非請求狀態(tài),時鐘值為0,并任意指定一個進程為令牌的持有者。

(2) 請求時,一個進程請求進入臨界區(qū)時,如果它持有令牌,它不發(fā)送任何請求報文,將自己的進程狀態(tài)表中相應(yīng)于自己一欄的狀態(tài)改為請求態(tài),并記錄該狀態(tài)的時鐘值,直接進入臨界區(qū)。如果它不持有令牌,則它向所有其它進程發(fā)送帶有時間戳的請求報文。發(fā)出請求報文后,將自己的進程狀態(tài)表中相應(yīng)于自己一欄的狀態(tài)改為請求態(tài),并記錄該狀態(tài)的時鐘值。

(3) 收到請求時,當(dāng)進程A收到進程B的請求報文時,A將B的請求報文中的時間戳同A的進程狀態(tài)表中B的時間值進行比較。若B的請求報文中的時間戳大于A的進程狀態(tài)表中B的時間值,則A修改自己的進程狀態(tài)表。將A的進程狀態(tài)表中對應(yīng)于B的一欄改為請求狀態(tài),并記錄此狀態(tài)的時間。

(4) 退出臨界區(qū)時,進程A退出臨界區(qū)后,將自己的進程狀態(tài)表中關(guān)于自己的一欄改為非請求狀態(tài),時鐘值加1,并將該時鐘值作為該狀態(tài)的時間。然后檢查其進程狀態(tài)表中是否記錄有某個進程處于請求狀態(tài),若有,則從處于請求狀態(tài)的進程中選取一個請求最早的進程B(具有最小的時間戳),將令牌傳送給它,并在令牌中附上A的進程狀態(tài)表。

(5) 收到令牌時,收到令牌的進程把隨令牌傳來的進程狀態(tài)表和自己的進程狀態(tài)表進行比較。若隨令牌傳來的進程狀態(tài)表中某進程的時間戳大于自己的進程狀態(tài)表中相應(yīng)進程的時間戳,則將自己的進程狀態(tài)表中相應(yīng)進程的狀態(tài)和時間戳改成隨令牌傳來的進程狀態(tài)表中相應(yīng)的狀態(tài)和時間戳。

在該算法中,當(dāng)進程不持有令牌時算法需要交換n個報文,其中的n-1個為請求報文,一個用于傳送令牌。而當(dāng)請求進入臨界區(qū)的進程持有令牌時,互斥算法顯然不需要交換報文。

3結(jié)束語

通過研究生“分布式操作系統(tǒng)”和本科生“操作系統(tǒng)”的教學(xué)實踐表明,在教學(xué)過程中通過這樣的比較教學(xué)容易引起學(xué)生的興趣,從而能夠激發(fā)學(xué)生的學(xué)習(xí)熱情和對問題的較為深入的思考,收到了較好的教學(xué)效果。

參考文獻:

[1] 徐高潮,胡亮,鞠九濱. 分布計算系統(tǒng)[M]. 北京:高等教育出版社,2004.

[2] 張堯?qū)W,史美林,張高. 計算機操作系統(tǒng)教程[M]. 3版. 北京:清華大學(xué)出版社,2006.

[3] 龐麗萍. 操作系統(tǒng)原理[M].3版.武漢:華中科技大學(xué)出版社,2000.

[4] Andrew S. Tanenbaum. Distributed Operating Systems[M]. 陸麗娜,伍衛(wèi)國,劉隆國,等譯. 北京:電子工業(yè)出版社,1999.

[5] 湯子氵贏,哲鳳屏,湯小丹. 計算機操作系統(tǒng)教程(修訂版)[M]. 西安:西安電子科技大學(xué)出版社,2001.

[6] 任滿杰,劉樹剛,李軍紅.操作系統(tǒng)原理實用教程[M].北京:電子工業(yè)出版社,2006.

[7] Andrew S. Tanenbaum,Albert S. Woodhull. Operating Systems Design and Implementation[M]. 2nd ed. Upper Saddle River,NJ. Prentice- Hall International,Inc. 1996.

[8] Lamport L. Time,clock,and the order of events in a distributed system[J]. Communications of the ACM,July 1978,21(7):558-568.