高級操作系統(tǒng)advancedoperatingsystem-中國科學技術大學

1、高級操作系統(tǒng)Advanced Operating System,熊焰yxiong@ustc.edu.cn0551-3600689中國科學技術大學計算機系,第六章 分布式程序設計,分布式程序設計的特點分布式進程分布式進程遷移,6.1 分布式程序設計的特點分布式程序設計的特點,在分布式計算機系統(tǒng)出現(xiàn)后，為了應用這種系統(tǒng)，在七十年代后期提出了分布式程序設計的概念，即設計運行于分布式計算機系統(tǒng)上的分布式程序。分布式程序設計有三個

2、特點：分布性、通信性和魯棒性。一個分布式程序由若干可以獨立執(zhí)行的程序模塊組成，這些程序模塊分布于一個分布式計算機系統(tǒng)中若干臺計算機上同時執(zhí)行。分布于各臺計算機上的程序模塊是相互關聯(lián)的，它們在執(zhí)行中需要交換數(shù)據(jù)（即通信）。只有通過通信，各程序模塊才能協(xié)調執(zhí)行，以完成一個共同的計算任務。此外，進行分布式程序設計時，還常常要考慮魯棒性，當某幾臺計算機發(fā)生故障時，程序仍可以執(zhí)行下去。,6.1 分布式程序設計的特點分布式程序設計語言,為了

3、進行分布式程序設計，必須提供分布式程序設計語言。分布式程序設計語言和其它程序設計語言的主要區(qū)別：它具有程序分布和通信的功能。有時它還具有便于實現(xiàn)魯棒性的一些功能。一般來說，一種順序程序設計語言或并發(fā)程序設計語言,增加了分布和通信功能后，就可以成為分布式程序設計語言了。,6.1 分布式程序設計的特點分布式程序,分布式功能可使程序分為若干個可獨立執(zhí)行的程序模塊。這些程序模塊的產(chǎn)生方式：可以在程序開始執(zhí)行前就按要求分布于各臺計算機上

4、，也可以在程序執(zhí)行過程中逐個產(chǎn)生出來，即開始執(zhí)行時只有一個程序模塊，它在執(zhí)行中不斷產(chǎn)生出新的程序模塊，被產(chǎn)生的程序模塊在執(zhí)行中又可以產(chǎn)生程序模塊。由于不同的程序模塊是在不同的計算機上執(zhí)行的，故它們之間不能有共享數(shù)據(jù)或公用變量。程序模塊之間的數(shù)據(jù)交換只能依靠通信。分布式程序設計的通信功能就是用來實現(xiàn)程序模塊間的數(shù)據(jù)交換的。目前已有十幾種分布式程序設計語言的建議。,6.2 分布式進程基于Pascal的分布式程序設計語言,漢森于197

5、8年提出了分布式進程的概念。它將并發(fā)PASCAL語言作了一些修改，并增加了分布式進程的概念，從而構成了一個分布式程序設計語言。分布式進程是分布于系統(tǒng)的若干臺計算機上的進程，它們之間沒有公用變量。一個程序是由數(shù)量固定的若干分布式進程組成，它們同時被啟動，并行地在各臺計算機上執(zhí)行。,6.2 分布式進程進程定義,一個進程定義了自己的變量、公用過程和初始語句序列：Process（進程名）一個進程執(zhí)行兩類操作：執(zhí)行初始語句序列和由

6、其它進程提出的外需求（即調用它定義的公用過程）。,6.2 分布式進程分布式進程的執(zhí)行,一個進程被啟動后，1）先執(zhí)行初始語句序列，直至執(zhí)行完畢。2）在進程執(zhí)行中因為等待某個條件而暫時不能執(zhí)行下去時，如果有外需求，它就執(zhí)行相應的公用過程。當此過程執(zhí)行完畢或執(zhí)行到等待某個條件而暫時不能繼續(xù)執(zhí)行時，它或者去執(zhí)行初始語句序列，或者執(zhí)行另一個外需求的過程。一個進程在執(zhí)行初始語句序列或某個過程時，總是連續(xù)地執(zhí)行下去，除非它因為等待某個條件而暫

7、時不能繼續(xù)執(zhí)行下去，或者它向其它進程提出了過程調用。 當一個進程由于上述原因不能執(zhí)行語句序列或某個過程時，它就可以接收其它進程的需求，執(zhí)行相應的一個過程。因此，一個進程從執(zhí)行某一個過程轉向另一個過程，這不是由時鐘來控制的，而是由程序本身的執(zhí)行來確定的。,因此，一個分布式進程的執(zhí)行過程可用下圖來表示：,(a)簡單情況 （b) 復雜情況,6.2 分布式進程過程的

8、定義:,一個進程可以定義若干個過程。一個過程定義了它的輸入輸出參量、局部變量和語句序列：Proc（#）當執(zhí)行一個過程時，相應的語句序列就被執(zhí)行。,6.2 分布式進程過程的調用,一個進程可用call語句來調用另一個進程所定義的過程，例如進程p可以用以下形式的call語句來調用進程Q定義的過程R： call Q.R（，變量）在進程Q開始執(zhí)行過程R時，call語句中表達式的值就賦給了輸入?yún)⒘俊?/p>

9、當過程執(zhí)行完畢后，輸出參量的值就賦給了call語句中的變量實現(xiàn)上述過程調用時，1）調用進程先要將輸入?yún)⒘康闹祩鹘o被調用者，2）過程執(zhí)行完畢后，被調用者要將輸出參量的值送回給調用者。所以，一次過程調用要兩次通信才能實現(xiàn)。,,進程對過程的調用可以加以限制。例如，規(guī)定進程可以定義兩類過程：公用過程和局部過程。一個進程只能調用其它進程所定義的公用過程。局部過程只能為它所屬進程來調用。為了易于驗證和實現(xiàn)，可規(guī)定不許遞歸調用。,6

10、.2 分布式進程衛(wèi)式命令,在漢森提出的分布式程序設計語言建議中，還定義了一些稱之為衛(wèi)式命令和衛(wèi)式區(qū)域的語句來控制進程執(zhí)行的同步。這些語句是：1. if語句 if B1:S1|B2:S2|……end其意思是：當B1，B2，……中某個條件為真時，選擇某個相應的語句執(zhí)行之，否則停止執(zhí)行程序。例如，執(zhí)行語句 if B1:S1|B2:S2|B3:S3 end時，若B1，B3為真，則執(zhí)行完S1或S3后，這個語句就執(zhí)

11、行完了。究竟執(zhí)行S1還是S3，語法不作規(guī)定，也就是說，這是不確定的。如果執(zhí)行這個語句時，B1，B2和B3均為假，那么就停止執(zhí)行相應的程序。這往往意味著有錯誤發(fā)生了。,,2.    do語句 do B1:S1|B2:S2|……end其意思是：只要B1，B2，…中某個條件為真，就選擇某個相應的語句執(zhí)行之，直到所有條件均為假時這個語句才執(zhí)行完畢。顯然 do B:S end和While B

12、 do S end是一樣的。所以do語句是while語句的擴充。,,3. When語句 When B1:S1|B2:S2|……end其意思是等到B1，B2，…中某個條件為真時，就執(zhí)行某個相應的語句。如果多個條件為真，則選擇某個相應的條件來執(zhí)行。,,4.  cycle語句 cycle B1:S1|B2:S2|……end其意思是：不斷地重復執(zhí)行When語句 When B1:S1|B2:S2|…

13、…end因此上面的cycle語句等價于 Do true: When B1:S1|B2:S2|……end end,,5. for語句 for x in y:S end其意思是：對數(shù)組或集合y中的每個元素x執(zhí)行語句S。在這個程序設計語言中，除字符型。布爾型和整數(shù)型三種基本數(shù)據(jù)類型外，還有集合型、序列型和數(shù)組型。集合型 set[n]T是指n個T類數(shù)據(jù)的集合。 序列型 seq[n]

14、T是指n個T類型數(shù)據(jù)的序列。 數(shù)組型 array[n]T是指由n個T類數(shù)據(jù)所組成的數(shù)組。,,6. Skip語句什么也不做的空操作。 下面給出4個例子1) 信件緩沖2) 字符串發(fā)送3) 文件的讀寫4) 哲學家問題,【例1】 信件緩沖,一個稱為buffer的進程為進程間交換信息提供緩沖。它定義了兩個過程：Send和Receive。當企圖將信件存入緩沖時，調用過程Send。當企圖將信件從緩

15、沖中取走時，調用過程Receive。定義如下: Process Buffer; B:array[1…128]char;{一封信由128個字符組成} Full:Boolean; {緩沖中有信時Full為真},Proc Send (M:array[1..128]char); begin When not Full:B:=M;Full:=true end; end; Proc Re

16、ceive(#M:array[1..128]char); begin When Full:M:=B;Full:=false end; end; begin Full:=false end;,【例2】 字符串傳送,一個為Stream的進程從鍵盤輸入設備讀入一行字符串，經(jīng)加工后送入例1所定義的Buffer進程的緩沖。Process Stream;B:array[1..128]cha

17、r; {一行最多128個字符} i:int;begin do true： i:=1; Read(B[1]); {從鍵盤輸入設備讀入一個字符} do B[i]!=“換行字符”and i<128: i:=i+1;Read(B[i]) | i=128:skip end; do i<128:i:=i+1;B[i]:=“空格”；

18、{將“換行字符”后補上空格} call Buffer.Send(B);{將讀入的一行字符送入緩沖} end；,【例3】文件的讀寫,一個稱為Resource的進程管理一個共享文件。當一個進程要讀（寫）這個文件時，它先調用過程Startread（Startwrite）取得讀（寫）的權力，然后就可以不斷地調用過程Read（W

19、rite）來讀（寫文件）。當讀寫完畢后，它調用過程Endread（Endwrite）以歸還讀（寫）權。 Process Resource;S:int;Proc Startread;begin when S>=1:S:=S+1 endend; Proc Endread;begin if S>1:S:=S-1 endend;,,Proc Startwrite;begin when S=

20、1:S:=0 endend; Proc Endwritebegin if S=0:S:=1 endend;Proc Read(B:int;#R:array[1..256] char);begin ReadBlock(B,R){將第B塊中的256個字符讀入R}end；,,Proc Write(B:int;M:array[1..256] char);begin WriteBlock(B,M){將M中

21、的256個字符寫入第B塊} end; begin S:=1 end; 變量S的值表明文件所處的狀態(tài)，它的含義如下：S＝0，有一個寫文件的進程占用文件S＝1，沒有進程占用文件S＝2，有一個讀文件的進程占用文件……S＝k（≥2）,有k－1個讀文件的進程占用文件。,,顯然，文件在Resource控制下可以同時為幾個讀文件的進程占用，而最多只可能為一個寫文件的

22、進程占有。一個進程用語 call Resource.startread 或 call Resource.startwrite來占用文件。然后用 call Resource.Read(B,R)或 call Resource.Write(B,M)來讀或寫文件。最后，用 call Resource.Endre

23、ad 或 call Resource.Endwrite來歸還文件。,按上述方法編制的程序不能避免餓死。例如：當兩個進程交替地讀文件時，在一個進程歸還文件前另一個就調用了過程Startread，而在一個進程調用了過程Startread后另一個才調用過程Endread，這時調用過程Startwrite的進程就無法獲得寫文件的權力。為了避免餓死，上述進程可作以下的修改：Process Resouce;S:i

24、nt;Proc Startread;begin When S>=1:S:=S+1 end end;,,Proc Startwritebegin if S>1:S:=2-S|S1:S:= S-1|S<1:S:=S+1 end end; Proc Endwritebegin if S=0:S:=1 endend; ……{以下程序不變},,此時，變量S除原來含義

25、以外，S＝－k（k>0）表示有k＋1個進程在讀文件，而至少有一個進程在等待寫文件。S＝0表示有一個進程在寫文件或有一個進程在讀文件，而有一個進程在等待寫文件。經(jīng)過上述修改后，只要有進程在等待寫文件時就不再接受進程讀文件了。顯然，餓死現(xiàn)象就不會產(chǎn)生了。,【例4】哲學家用餐問題,5個哲學家圍坐一圓桌。桌上有5把叉子，每人旁邊有兩把。每個哲學家不斷地思考和進餐。當他要進餐時，他必須得到左邊和右邊的叉子才行。當他食畢，放下兩叉，從而

26、他的兩鄰者可得到他們的左或右邊的叉子。為了描述這個問題，引入一個稱為數(shù)組進程的概念。一個數(shù)組進程 Process[i:1…n]表示n個進程。例如 Process Philosopher[i:1…5] 表示5個進程，它們是：,,Process Philosopher[1] Process Philosopher[2] ……

27、Process Philosopher[5] 解決5個哲學家用餐問題的程序由6個進程組成。一個哲學家的活動由一個進程來描述。叉子由一個稱為Table的進程來管理,,Process Philosopher[i:1…5];begin do true: thinking; call Table.Join(i);{第i個哲學家要求進餐} call Table.Lea

28、ve(i);{第i個哲學家食畢} end；end;,,Process Tableeating:array[1…5]Boolean;{第i個哲學家在進餐時,eating[i]=true}Proc Join(i:int);begin When eating[left(i)]=false and eating[right(i)] =false:eating[i]:=true end

29、 {當左右的哲學家均不在進餐時，即左 右叉都空閑時，他就可以加入進餐} end； Proc Leave(i:int);begin eating[i]:=falseend;,begin j:int; f

30、or j:=1 to 5 do eating[j]:=falseend; 程序中函數(shù)left和right定義如下：Left(i) = i－1 i>1left(i) = 5 i=1right(i) =i+1 i<5right(i) =1 i=5不難驗證，采用上述解法不會產(chǎn)生死鎖，但是可能出現(xiàn)餓死現(xiàn)象。當一個哲學家的左右二人

31、交替進餐時，他就可能得不到叉而“餓死”。如果修改一下，就可以既避免死鎖又避免餓死。這作為作業(yè)留給同學課后自己去做。,6.3 分布式進程遷移,在計算機網(wǎng)絡中，允許程序或數(shù)據(jù)從一個結點遷移到另一個結點，在分布式計算機系統(tǒng)中，更是允許將一個進程從一個計算機遷移到另一個計算機中。計算和數(shù)據(jù)的遷移：數(shù)據(jù)遷移（Data Migration）：假如系統(tǒng)A中的用戶欲去訪問系統(tǒng)B中文件的數(shù)據(jù)，可以采用以下兩種方法來實現(xiàn)數(shù)據(jù)傳送。第一種方法，是將

32、系統(tǒng)B中的整個文件送到系統(tǒng)A中，,,這樣，凡是系統(tǒng)A中的用戶要訪問該文件時，都變成了本地訪問。當用戶不再需要此文件時，若文件拷貝已被修改，則必須把已修改過的拷貝送回系統(tǒng)B；若未被修改，便不必將文件回送。如果文件比較大，系統(tǒng)A中用戶用到的文件數(shù)據(jù)又比較少，采用這種來回傳送整個文件的方法，系統(tǒng)的效率較低。第二種方法，是僅把文件中用戶當前要使用的部分從系統(tǒng)B傳送到系統(tǒng)A，若以后用戶又要用到其它部分,再從系統(tǒng)B傳送到系統(tǒng)A。當用戶不再需要使用

33、此文件時，則只需把修改過的部分傳回系統(tǒng)B。Sun公司的網(wǎng)絡文件系統(tǒng)NFS 和Microsoft 的NETBU 便使用了這種方法。,計算遷移（Computation Migration）：在有些情況下，傳送計算要比傳遞數(shù)據(jù)效率高。例如，有一個應用，它需要訪問多個駐留在不同系統(tǒng)中的大型文件，以獲得有關數(shù)據(jù)。此時，若采用數(shù)據(jù)遷移方式，則需將駐留在不同系統(tǒng)上的所需文件傳送到用戶應用所在的系統(tǒng)中。這樣，要傳送的數(shù)據(jù)量相當大，可以采計算遷移來解

34、決這個問題。計算遷移可以有多種不同的執(zhí)行方式。1）可以通過RPC調用不同系統(tǒng)上的例行程序來處理文件，并把處理后的結果傳給自己；2）也可以發(fā)送多個消息給各個駐留了文件的系統(tǒng)，這些機器上的操作系統(tǒng)將創(chuàng)建一個進程來處理相應文件，進程處理完畢后再把結果傳遞回請求進程。,,必須注意：在第二種方式中請求進程和執(zhí)行請求的進程是在不同的機器上并發(fā)執(zhí)行的。上述兩種方法，經(jīng)過網(wǎng)絡傳輸?shù)臄?shù)據(jù)相當少。如果傳輸數(shù)據(jù)的時間長于這段命令的執(zhí)行時間，則計算遷

35、移方式更可?。环粗?，數(shù)據(jù)遷移方式更有效。,進程遷移（Process Migration）：進程遷移是計算遷移的一種延伸，當一個新進程被啟動執(zhí)行后，并不一定始終都在同一處理機上運行，也可以被遷移到另一臺機器上繼續(xù)運行。引入進程遷移的理由是：(1)負載均衡:分布式系統(tǒng)中，各個結點的負荷經(jīng)常不均勻，此時，可以通過進程遷移的方法來均衡各個系統(tǒng)的負荷。把重負荷系統(tǒng)中的進程遷移到輕負荷的系統(tǒng)中去，以改善系統(tǒng)性能；(2)通信性能:對于分布在不同系

36、統(tǒng)中，而彼此交互性又很強的一些進程，應將它們遷移到同一系統(tǒng)中，以減少由于它們之間頻繁地交互而加大通信開銷。類似地，當某進程在執(zhí)行數(shù)據(jù)分析時，如果它們所需的文件遠遠大于進程，則此時應該把該進程遷移到文件所在駐留的系統(tǒng)中去，能進一步降低通信開銷；,,,(3) 加速計算:對于一個大型應用，如果始終在一臺處理機上執(zhí)行，可能要化費較多時間，使作業(yè)周轉時間延長。但如果能為該作業(yè)建立多個進程，并把這些進程遷移到多臺處理器上執(zhí)行，會大大加快該作業(yè)的完成

37、時間，從而，縮短作業(yè)的周轉時間；(4)特殊功能和資源的使用:通過進程遷移來利用特殊結點上的硬件或軟件功能或資源。,,此外，在分布式系統(tǒng)中，如果某個系統(tǒng)發(fā)生了故障，而該系統(tǒng)中的進程又希望繼續(xù)下去，則分布式操作系統(tǒng)可以把這些進程遷移到其它系統(tǒng)中去運行，提高了系統(tǒng)的可用性。為了實現(xiàn)進程遷移，在分布式系統(tǒng)中必須建立相應的進程遷移機制，主要負責解決(1)由誰來啟動進程遷移？(2)如何進行進程遷移？(3)如何處理未完成的信號和消息等問題。

38、,進程遷移的啟動取決于進程遷移機制的目標，如果目標是平衡負載，則由系統(tǒng)中的監(jiān)視模塊負責在適當時刻進行進程遷移。在分布式系統(tǒng)中配置了系統(tǒng)負載監(jiān)視模塊，設定其中一個結點上的監(jiān)視模塊為主模塊。主模塊定時地與各系統(tǒng)的監(jiān)視模塊交互有關系統(tǒng)負荷情況的信息。一旦發(fā)現(xiàn)有些系統(tǒng)忙碌，而有些系統(tǒng)空閑時，主模塊便可啟動進程遷移，向負載沉重的系統(tǒng)發(fā)出命令，讓其把若干進程遷移到負載輕的系統(tǒng)中去。當然，這對用戶是透明的，所有進程遷移工作都由系統(tǒng)完成。類似

39、地，如果進程遷移是為了其它目標，則分布式系統(tǒng)中的其它相應部分成為進程遷移的啟動者。,,在進程進行遷移時，應將系統(tǒng)中已遷移進程撤消，在目標系統(tǒng)中建立一個相同的新進程，因為這是進程的遷移而不是進程的復制。進程遷移時，所遷移的是進程映象，包括進程控制塊、程序、數(shù)據(jù)和棧。此外，被遷移進程與其他進程之間的關聯(lián)應作相應修改。進程遷移的過程并不復雜，但需要花費一定的通信開銷，困難在于進程地址空間和已經(jīng)打開的文件。,,由于現(xiàn)代操作系統(tǒng)均采用虛擬存

40、儲技術，對于進程地址空間可使用如下兩種辦法：一是傳送整個地址空間，把一個進程的所有映象全部從源系統(tǒng)傳遞到目標系統(tǒng)，這種方法簡單，但當?shù)刂房臻g很大，且進程只需要用到一部分程序和數(shù)據(jù)時，會造成浪費；二是僅傳送內存中的且已修改了的那部分地址空間，若程序運行時還需要附加的虛存空間部分信息，則可以通過請求方式予以傳送。這樣，所傳送的數(shù)據(jù)量是最少的，但源系統(tǒng)中仍然必須保存被遷移進程的數(shù)據(jù)及相關信息，源系統(tǒng)并未從對該進程的管理中解脫出來。,,,

41、三是預先復制，進程繼續(xù)在原結點上執(zhí)行，而地址空間被復制到目標結點上，由于原結點上的某些地址空間內容又被修改過，所以，需要有二次遷移，這種方法能減少進程被凍結的時間。如果被遷移的進程還打開了源系統(tǒng)中的某些文件，可用兩種方法來處理，一種方法是將已打開的文件隨進程一起遷移，這里存在的問題是：進程有可能僅僅臨時遷移過去，返回時才需要訪問該文件；第二種方法是暫時不遷移文件，僅當遷移后的進程又提出對該文件的訪問要求時，再進行遷移。如果文件

42、被多個分布式進程所共享，則需要維護對文件的分布式訪問，而不必遷移。,在一個進程由源系統(tǒng)向目標系統(tǒng)遷移期間，可能會有其它進程繼續(xù)向源系統(tǒng)中已遷移進程的進程發(fā)來消息或信號，這時應如何處理？一種可行的方法是在源系統(tǒng)中提供一種機構，用于暫時保存這類信息，還需保存被遷移進程所在目標系統(tǒng)的新地址，當被遷移進程已在目標系統(tǒng)中被建成新進程后，源系統(tǒng)便可將已收到的相關信息轉發(fā)至目標系統(tǒng)。,,,IBM的AIX是一種分布式UNIX操作系統(tǒng)，它提供了一種實用

43、的進程遷移機制。進程遷移的步驟如下：（1）當進程決定遷移自身時，它先選擇一個目標機，發(fā)送一個遠程執(zhí)行任務的消息，該消息運載了進程映象及打開文件的部分信息；（2）在接收端，內核服務進程生成一個子進程，將這些信息交給它；（3）這個新進程收集完成其操作所需的環(huán)境、數(shù)據(jù)、變量和棧信息。如果它是“臟”的就復制程序文件；如果是“干凈”的，則請求從全局文件系統(tǒng)中調頁。（4）遷移完成后發(fā)消息通知源進程，源進程就發(fā)一個最后完成消息給新進程，然后刪