高級操作系統(tǒng)AdvancedOperatingSystem

1、高級操作系統(tǒng)Advanced Operating System熊 焰國科學技術(shù)大學計算機學院分布式系統(tǒng)模型分布式處理機分配分布式進程調(diào)度分布式系統(tǒng)容錯實時分布式系統(tǒng)第四章 分布式進程和處理機管理模型的作用精確地定義要建立或分析的系統(tǒng)的屬性和特征提供檢驗這些屬性的基礎(chǔ)代表性的模型數(shù)學函數(shù)型有限狀態(tài)自動機(FSM)圖模型4.1分布式系統(tǒng)模型數(shù)學函數(shù)型y1,y2,yn=f(x1,x2,xn)f(x1,x2,xn)=f1(f2(f3(x1,x2,x3,xn)特點：分層分層的好處：組織大量數(shù)據(jù)檢查層次間輸入與輸出的一致性缺點：不保存數(shù)據(jù)4.1分布式系統(tǒng)模型有限狀態(tài)自動機 (

2、FSM)4.1分布式系統(tǒng)模型有限狀態(tài)自動機 (FSM)優(yōu)點：對于說明數(shù)據(jù)處理是非常理想的限制：固有地串行化了所有并發(fā)明確假設(shè)一個輸入的所有處理在下一個輸入到達之前完成4.1分布式系統(tǒng)模型圖模型4.1分布式系統(tǒng)模型圖模型局限性：它沒有體現(xiàn)“狀態(tài)”的概念4.1分布式系統(tǒng)模型分布式系統(tǒng)模型的分類工作站模型處理機池模型兩者混合模型4.1分布式系統(tǒng)模型4.1.1 工作站模型工作站模型的優(yōu)點清晰用戶響應(yīng)時間能得到保證每個用戶都有很大的自主權(quán)缺點空閑工作站難以充分利用4.1.1 工作站模型方法利用伯克利UNIX中的rsh程序?qū)ふ铱臻e工作法的算法服務(wù)器端驅(qū)動的算法客戶端驅(qū)動的算法4.1.2 空閑工作站的利用利

3、用伯克利UNIX中的rsh程序rsh machine command第一個參數(shù)指定要使用的工作站第二個參數(shù)表示在指定工作站上運行的命令Rsh程序的功能就是在指定機器上運行指定的命令4.1.2 空閑工作站的利用利用伯克利UNIX中的rsh程序較嚴重的問題：必須由用戶來尋找一臺空閑的機器運行環(huán)境可能不同遠程機器可能非空閑4.1.2 空閑工作站的利用利用空閑工作站得考慮如下問題:怎樣找到一個空閑工作站； 怎樣透明地運行一個遠程進程；如果空閑工作站的主人回來重新使用它，怎么辦？ 4.1.2 空閑工作站的利用尋找一個空閑的工作站工作站空閑的標準沒有用戶登錄？沒有用戶操作且沒有用戶進程運行4.1.2 空閑

4、工作站的利用尋找空閑工作站的算法服務(wù)器端驅(qū)動的算法客戶端驅(qū)動的算法4.1.2 空閑工作站的利用服務(wù)器端驅(qū)動的算法方法1空閑工作站注冊將自己的名字、網(wǎng)址、屬性輸入到一個注冊用戶輸入命令查找remote command4.1.2 空閑工作站的利用服務(wù)器端驅(qū)動的算法方法2空閑工作站向整個網(wǎng)絡(luò)發(fā)一條廣播消息所有的工作站都保存這個消息優(yōu)點尋找空閑工作站的開銷更少，冗余度更高缺點所有的機器都需要維護一個私有的注冊文件潛在的沖突4.1.2 空閑工作站的利用客戶端驅(qū)動的算法客戶端運行remote時，發(fā)送廣播聲明它需要運行哪個程序，需要多少內(nèi)存，是否需要浮點運算等等當收到應(yīng)答后，remote就從中挑選一個啟動命

5、令在選中的空閑工作站上運行Trick: 服務(wù)端應(yīng)答時，讓應(yīng)答的延遲與自己當前負載成正比4.1.2 空閑工作站的利用透明地運行一個遠程進程代碼移動比較容易如何設(shè)置遠程運行環(huán)境？相同的文件系統(tǒng)，工作目錄，環(huán)境變量特殊情況本地運行：讀取鍵盤，寫屏幕遠程調(diào)用：SBRK（調(diào)整數(shù)據(jù)段大?。㎞ICE（設(shè)置CPU調(diào)度優(yōu)先級）PROFIL（程序計數(shù)器計數(shù)）4.1.2 空閑工作站的利用透明地運行一個遠程進程代碼移動比較容易如何設(shè)置遠程運行環(huán)境？相同的文件系統(tǒng)，工作目錄，環(huán)境變量特殊情況時間有關(guān)的系統(tǒng)調(diào)用MAKE4.1.2 空閑工作站的利用如果空閑工作站的主人回來重新使用它，怎么辦？ 方案1：什么都不做方案2：強行

6、取消正在運行的非本地進程遠程通知，然后關(guān)閉方案3：遷移4.1.2 空閑工作站的利用4.1.2 處理機池模型處理機池模型是無盤工作站模型的進一步發(fā)展。實際上，我們是把所有的計算能力轉(zhuǎn)換成了可以動態(tài)訪問的“空閑工作站”。4.1.2 處理機池模型使用排隊論來描述和分析在一個排隊系統(tǒng)中，用戶隨機地向服務(wù)器請求服務(wù)當服務(wù)器忙時，用戶必須排隊等待服務(wù)按順序被服務(wù)4.1.2 處理機池模型4.1.2 處理機池模型排隊系統(tǒng)的定義用來描述顧客到達、等待、被服務(wù)以及離去過程的模型排隊系統(tǒng)的假定顧客源無限大，它意味著排隊顧客非常多也不影響顧客的到達率4.1.2 處理機池模型排隊系統(tǒng)的三大要素到達間隔時間的概率密度函數(shù)

7、服務(wù)時間的概率密度函數(shù)服務(wù)員個數(shù)4.1.2 處理機池模型排隊系統(tǒng)表達方式：A/B/mA是到達間隔時間的概率分布B是服務(wù)時間的概率分布M-指數(shù)型概率分布D-等值型概率分布G-一般分布m是服務(wù)員個數(shù)本課討論M/M/1模型4.1.2 處理機池模型M/M/1系統(tǒng)參數(shù)到達間隔時間的概率密度函數(shù)fA(t)=e-t均值為1/是平均到達率服務(wù)時間的概率密度函數(shù)fs(t)=e-t4.1.2 處理機池模型Littles Result令p= /顧客等待時間的概率密度函數(shù)fw(t)=p(1-p)e-p(1-p)t顧客響應(yīng)時間的概率密度函數(shù)fT(t)= fs(t)fw(t)= (1-p)e- (1-p)t，t=0平均響

8、應(yīng)時間T=fT(t)dt=1/（-）4.1.2 處理機池模型例題：假設(shè)有一個小水坑，鳥兒隨機飛來就浴，平均到達率為3只/分鐘。鳥兒平均洗浴時間為10秒/只，指數(shù)分布。求平均一只鳥需要等待多長時間才能洗上澡？平均到達率=3只/分鐘=0.05只/秒平均服務(wù)率=1/10=0.1只/秒平均響應(yīng)時間T=20秒平均等待時間為20-10=10秒/只4.1.2 處理機池模型排隊論可作為延遲分析的理論工具T=fT(t)dt=1/（-）4.1.2 處理機池模型一個重要的分析結(jié)果：n個獨立排隊系統(tǒng)每一個系統(tǒng)都是一個請求到達速率為處理機處理速率為則，平時響應(yīng)時間為T=1/（-）4.1.2 處理機池模型一個重要的分析結(jié)

9、果：將n個獨立排隊系統(tǒng)集中起來請求到達速率為n處理機處理速率為n則，平時響應(yīng)時間為T1=1/n（-）=T/n4.1.2 處理機池模型這個結(jié)果具有一定普遍性并已應(yīng)用到很多的系統(tǒng)中例：航空公司更愿意每5個小時飛一架300座的747飛機，而不愿意每10分鐘飛一架10座的商業(yè)飛機。當把處理能力分配給多個小服務(wù)器，使得每一個用戶擁有一個，這與隨機到達的請求不相匹配。而處理機池模型可以減少這種時間的浪費，這也是它總體性能更高的原因4.1.2 處理機池模型事實上，排隊論的結(jié)果正是完全否定分布式操作系統(tǒng)的主要理由之一。但是，響應(yīng)時間并不代表一切制造成本響應(yīng)時間的一致性 V.S. 平均響應(yīng)時間之前結(jié)果一個前提假設(shè)所有的請求被