高級(jí)操作系統(tǒng)講義

1、高級(jí)操作系統(tǒng)3一 上課基礎(chǔ)3二 參考書：3三 主要內(nèi)容3四 主要考核內(nèi)容4五 教學(xué)目的4第0章 引言51網(wǎng)絡(luò)操作系統(tǒng)52分布式操作系統(tǒng)53并行操作系統(tǒng)64實(shí)時(shí)操作系統(tǒng)（Real-Time Operating System, RTOS）65三種系統(tǒng)之間的一些不同之處:7第一章 分布式計(jì)算機(jī)系統(tǒng)8第二章 分布式通信1721 消息傳遞1822 組通信2023 遠(yuǎn)程過程調(diào)用 RPC21第三章 分布式協(xié)同處理2431 事件定序與時(shí)間戳2432 分布式互斥2533 選擇算法29第四章 資源管理3141 資源共享3142 資源管理3143 死鎖處理31第五章 進(jìn)程與處理機(jī)管理3651 進(jìn)程和線程3652 進(jìn)

2、程管理3853 處理機(jī)管理38第六章 任務(wù)分配與負(fù)載平衡4061 任務(wù)分配 （task allocation）4062 負(fù)載平衡44第七章 分布式文件系統(tǒng)5071 允許用戶程序直接存取5072 分布式文件系統(tǒng)的組成5073 設(shè)計(jì)策略5074 接口5075 文件系統(tǒng)的實(shí)現(xiàn)技術(shù)51第八章 命名服務(wù)5781 名字5782 一般的命名方式5983 分布式系統(tǒng)中的命名方式5984 名字服務(wù)器（name server）的設(shè)計(jì)6085 分布式系統(tǒng)的透明性60第九章 事務(wù)的并發(fā)控制61916192 鎖機(jī)制6293 樂觀并發(fā)控制6394 時(shí)間戳定序63第十章 分布式事務(wù)64第十一章 恢復(fù)與容錯(cuò)71111 具有容

3、錯(cuò)能力的應(yīng)用程序71112 事務(wù)恢復(fù)71113 容錯(cuò)71第十二章 分布式共享內(nèi)存72121 分布式共享內(nèi)存（Distributed Shared Memory, DSM）72122 設(shè)計(jì)和應(yīng)用72高級(jí)操作系統(tǒng)一 上課基礎(chǔ)學(xué)習(xí)過本科操作系統(tǒng)課程熟悉一種程序設(shè)計(jì)語言二 參考書：1何炎祥 等 高級(jí)操作系統(tǒng) 科學(xué)出版社， 1999年；2何炎祥 分布式操作系統(tǒng) 高等教育出版社，2005年；3Andrew S. Tanenbaum Distributed Operating Systems. 中譯本 分布式操作系統(tǒng) 電子出版社 1999年；本科階段4張堯?qū)W，史美林 計(jì)算機(jī)操作系統(tǒng)教程 清華大學(xué)出版社，20

4、00；5湯子瀛 等 計(jì)算機(jī)操作系統(tǒng) 西安電子科技大學(xué)出版社，1999；6Abraham Silberschatz et al. Operating System Concept 高等教育出版社，2003 2007；7孟祥武 張玉潔等 操作系統(tǒng)考研指導(dǎo) 北京郵電大學(xué)出版社，2002；8張玉潔 孟祥武 操作系統(tǒng)習(xí)題解答與考試復(fù)習(xí)指導(dǎo), 機(jī)械工業(yè)出版社，2012年；三 主要內(nèi)容1分布式計(jì)算機(jī)系統(tǒng)2分布式通信3分布式協(xié)同處理4資源管理5進(jìn)程與處理機(jī)管理6任務(wù)分配與負(fù)載平衡7分布式文件系統(tǒng)8命名服務(wù)9事務(wù)的并發(fā)控制10分布式事務(wù)11恢復(fù)與容錯(cuò)12分布式共享內(nèi)存13Hadoop系統(tǒng)l 主要討論設(shè)計(jì)和構(gòu)造分

5、布式操作系統(tǒng)的基本原理和典型實(shí)現(xiàn)技術(shù)。l 分布式操作系統(tǒng)(Distributed OS, DOS)l 目前，分布式操作系統(tǒng)作為多機(jī)操作系統(tǒng)的高級(jí)表現(xiàn)形式，仍處于研究和發(fā)展階段，在理論和研制方法上仍有待于進(jìn)一步解決和探索的問題。四 主要考核內(nèi)容五 教學(xué)目的1.了解分布式操作系統(tǒng)技術(shù)方面的新成果，了解目前技術(shù)發(fā)展的情況，在實(shí)際應(yīng)用中，科學(xué)、合理選擇產(chǎn)品、系統(tǒng)，避免盲目、為進(jìn)行二次開發(fā)等打下基礎(chǔ)。2.目前操作系統(tǒng)產(chǎn)品正逐步吸收分布式操作系統(tǒng)方面的研究成果，通過學(xué)習(xí)，可以從更高一層看目前的操作系統(tǒng)技術(shù)、產(chǎn)品，可以預(yù)測它的發(fā)展。3.如果做實(shí)際、應(yīng)用項(xiàng)目，可以采用一些新技術(shù)。包括完成系統(tǒng)軟件和應(yīng)用軟件。第

6、0章 引言操作系統(tǒng)（本科基礎(chǔ)）進(jìn)一步：1網(wǎng)絡(luò)操作系統(tǒng)具有網(wǎng)絡(luò)功能的操作系統(tǒng)，無嚴(yán)格定義。l MS-DOS（1） 網(wǎng)絡(luò)通信能力（2） 提供網(wǎng)絡(luò)服務(wù)網(wǎng)絡(luò)上各節(jié)點(diǎn)的主機(jī)運(yùn)行自身的操作系統(tǒng)，它不僅要保證本機(jī)的系統(tǒng)進(jìn)程或用戶進(jìn)程能簡便、有效地使用網(wǎng)絡(luò)中各種資源；同時(shí)，也為網(wǎng)中其它用戶使用本機(jī)資源提供服務(wù)。l OS+網(wǎng)絡(luò)協(xié)議2分布式操作系統(tǒng)每臺(tái)計(jì)算機(jī)沒有各自獨(dú)立的OS，用戶不了解其文件存儲(chǔ)在什么地方，也不了解其程序是由遠(yuǎn)程處理機(jī)執(zhí)行的，分布式OS自動(dòng)管理文件的放置；網(wǎng)絡(luò)OS每臺(tái)計(jì)算機(jī)均有自己的OS；網(wǎng)絡(luò)OS的用戶要訪問資源，用戶必須了解資源的位置，用“文件傳輸”命令在計(jì)算機(jī)之間移動(dòng)文件。分布式操作系統(tǒng)是為

7、分布式計(jì)算機(jī)系統(tǒng)配置的一種操作系統(tǒng)。分布式OS在這種多機(jī)系統(tǒng)環(huán)境下:- 負(fù)責(zé)控制和管理以協(xié)同方式工作的各類系統(tǒng)資源；- 負(fù)責(zé)分布式進(jìn)程的同步與執(zhí)行，處理機(jī)間的通信、調(diào)度與分配等控制事務(wù)，自動(dòng)實(shí)行全系統(tǒng)范圍內(nèi)的任務(wù)分配和負(fù)載平衡；- 具有高度并行性以及故障檢測和重構(gòu)能力。3并行操作系統(tǒng)并行機(jī) > 并行操作系統(tǒng)è 并行DBMS > è 并行算法 > è 并行程序設(shè)計(jì)語言及其開發(fā)環(huán)境（并行編譯）：國內(nèi)的：銀河機(jī)、曙光機(jī)等；PVM (parallel machine)；NOW 工作站機(jī)群系統(tǒng)；CPU 10 > 40 > 20 20 >

8、80 > 404實(shí)時(shí)操作系統(tǒng)（Real-Time Operating System, RTOS）支持實(shí)時(shí)系統(tǒng)工作的操作系統(tǒng)，響應(yīng)時(shí)間有明確的規(guī)定；- 執(zhí)行效率高、快速、實(shí)時(shí)性強(qiáng)- 系統(tǒng)小，可剪裁，核心部分更?。? 主要應(yīng)用于實(shí)時(shí)控制領(lǐng)域；5三種系統(tǒng)之間的一些不同之處:項(xiàng) 目網(wǎng)絡(luò)操作系統(tǒng)分布式操作系統(tǒng)多處理機(jī)操作系統(tǒng)看起來是否像一個(gè)虛擬的單處理機(jī)系統(tǒng)?否是是所有的機(jī)器只運(yùn)行相同的操作系統(tǒng)?否是是有多少操作系統(tǒng)的拷貝?NN1怎樣通信?共享文件消息共享存儲(chǔ)器需要共同一致的網(wǎng)絡(luò)協(xié)議?是是否是否只有一個(gè)運(yùn)行隊(duì)列?否否是文件共享是否有良好的語義定義?通常沒有是是推動(dòng)操作系統(tǒng)發(fā)展的因素：- 硬件升級(jí)、

9、或者出現(xiàn)了新的硬件類型；- GUI取代字符界面；- 用戶、系統(tǒng)管理者的需求，新的功能、工具不斷加入到OS中；- bug 維護(hù)、修補(bǔ)；第一章 分布式計(jì)算機(jī)系統(tǒng)下一步的技術(shù)發(fā)展很難準(zhǔn)確預(yù)測，我們要在網(wǎng)絡(luò)、分布式環(huán)境下開發(fā)，需要掌握分布式計(jì)算機(jī)系統(tǒng)的原理，也需要了解他們的實(shí)現(xiàn)原理。分布式操作系統(tǒng)是為分布式計(jì)算機(jī)系統(tǒng)配置的一種操作系統(tǒng)。分布式系統(tǒng)需要與集中式系統(tǒng)完全不同的軟件。分布式計(jì)算機(jī)系統(tǒng)：- 從硬件角度來講，各個(gè)計(jì)算機(jī)都是自治的；- 從軟件角度來講，用戶將整個(gè)系統(tǒng)看作是一臺(tái)計(jì)算機(jī)。這兩者都是必需的，缺一不可。分布式系統(tǒng)由許多獨(dú)立的CPU組成，它們在一起工作使得整個(gè)系統(tǒng)看上去像一臺(tái)計(jì)算機(jī)。任務(wù)分布

10、: 把一個(gè)任務(wù)分解成多個(gè)可并行執(zhí)行的子任務(wù)，分散給各場點(diǎn)協(xié)同完成。功能分布: 把系統(tǒng)的總功能劃分成若干子功能，分配給各場點(diǎn)分別承擔(dān)。分布式系統(tǒng)的特征：1 資源共享：硬件資源、軟件資源；2開放性：可伸縮性、可移植性、互操作性；數(shù)據(jù)是可以交換的、對外接口是公開的、系統(tǒng)提供統(tǒng)一的通信機(jī)制、提供統(tǒng)一的用戶界面。3并發(fā)性：同時(shí)工作沒有沖突；有沖突，通過相應(yīng)算法解決；并發(fā)控制；4容錯(cuò)性： 兩個(gè)基本方法，硬件冗余、軟件恢復(fù)（數(shù)據(jù)備份、日志）；5透明性：實(shí)際上比其表面要微妙得多的含糊概念之一種 類含 義位置透明用戶不知道資源位于何處遷移透明資源可以不改名地隨意移動(dòng)復(fù)制透明用戶不知道有多少個(gè)拷貝存在并發(fā)透明多個(gè)

11、用戶可以自動(dòng)的共享資源并行透明系統(tǒng)活動(dòng)可以在用戶沒有感覺的情況下并行發(fā)生分布式系統(tǒng)的優(yōu)點(diǎn)：1性能價(jià)格比高 2速度 3內(nèi)在的分布性4可擴(kuò)充性 5可靠性 6適用于多種環(huán)境分布式系統(tǒng)的不足：1管理復(fù)雜 2性能和可靠性依賴于網(wǎng)絡(luò) 3保密性差4應(yīng)用軟件少項(xiàng)目描 述軟件目前為分布式系統(tǒng)開發(fā)的軟件還很少網(wǎng)絡(luò)網(wǎng)絡(luò)可能飽和和引起其它的問題安全容易造成對保密數(shù)據(jù)的訪問分布式系統(tǒng)的資源管理方式：1全集中管理方式 一個(gè)資源由一個(gè)管理機(jī)制管理。2分擔(dān)管理方式一個(gè)資源雖由幾個(gè)管理機(jī)制管理，但各分擔(dān)一種管理職能。3輪流管理方式 一個(gè)資源可由幾個(gè)管理機(jī)制管理，但輪流執(zhí)行管理職責(zé)。4全分散管理方式一個(gè)資源由多個(gè)管理機(jī)制在協(xié)商致

12、的原則下共同管理。性能比較：- 基本開銷：連接系統(tǒng)中的各個(gè)站點(diǎn)要多少花費(fèi)？- 通信開銷：從站點(diǎn)A發(fā)送信息到站點(diǎn)B需要多少時(shí)間?- 可靠性：分布式系統(tǒng)的拓?fù)浣Y(jié)構(gòu)：1全互連結(jié)構(gòu) 優(yōu)點(diǎn)：各場點(diǎn)間消息傳遞快，可靠性較高。缺點(diǎn)：開銷高。2部分互連結(jié)構(gòu)其開銷比全互連結(jié)構(gòu)低，但通信速度較全互連結(jié)構(gòu)慢?？煽啃砸蚕鄬^低。 3層次結(jié)構(gòu)通常情況下，其中的任何中間節(jié)點(diǎn)故障都可能將這種結(jié)構(gòu)分割成若干不相交的子樹。因此，可靠性較低。4星形結(jié)構(gòu) 這種結(jié)構(gòu)的基本開銷與場點(diǎn)個(gè)數(shù)成正比，這種通信速度卻是沒有保障的，因?yàn)橹醒雸鳇c(diǎn)可能變成瓶頸。5環(huán)形結(jié)構(gòu) 基本開銷較低，但通信代價(jià)可能較高。 6總線結(jié)構(gòu)這類結(jié)構(gòu)的開銷同場點(diǎn)成正比，通

13、信代價(jià)也很低。7 立方體結(jié)構(gòu)計(jì)算機(jī)支持的協(xié)同工作系統(tǒng)（CSCW，Computer Supported Cooperative Work），也是一種分布式系統(tǒng)。- CSCW特點(diǎn)： 群體性、交互性、分布性、協(xié)同性。- CSCW具體類型：（1） 電子郵件系統(tǒng) （2） 電子布告欄系統(tǒng)（BBS， Bulletin Board System） （3） 群體決策支持系統(tǒng) （4） 協(xié)同編輯系統(tǒng) （5） 計(jì)算機(jī)會(huì)議系統(tǒng) （6） 協(xié)同計(jì)算機(jī)開發(fā)環(huán)境- 多機(jī)OS的基本結(jié)構(gòu): 主從式 獨(dú)立式 分布式分布式OS分布式計(jì)算機(jī)系統(tǒng)(Distributed Computing Systems)是由多個(gè)分散的計(jì)算機(jī)經(jīng)互連網(wǎng)絡(luò)連

14、結(jié)而成的計(jì)算機(jī)系統(tǒng)。其中各個(gè)資源單元(物理或邏輯的)既相互協(xié)同又高度自治。能在全系統(tǒng)范圍內(nèi)實(shí)現(xiàn)資源管理，動(dòng)態(tài)地進(jìn)行任務(wù)分配或功能分配而且能夠并行地運(yùn)行分布式程序。分布式操作系統(tǒng)是為分布式計(jì)算機(jī)系統(tǒng)配置的操作系統(tǒng)。系統(tǒng)任務(wù)可以在系統(tǒng)中任何別的處理機(jī)上運(yùn)行。并提供高度的并行性和有效地同步算法和通信機(jī)制，自動(dòng)實(shí)行全系統(tǒng)范圍的任務(wù)分配并自動(dòng)調(diào)節(jié)各處理機(jī)的工作負(fù)載為用戶提供一個(gè)方便、友善的用機(jī)環(huán)境。分布式系統(tǒng)與網(wǎng)絡(luò)系統(tǒng)是有區(qū)別的。從操作系統(tǒng)的角度來看，網(wǎng)絡(luò)操作系統(tǒng)是為計(jì)算機(jī)網(wǎng)絡(luò)配置的操作系統(tǒng)，網(wǎng)絡(luò)中的各臺(tái)計(jì)算機(jī)配置各自的操作系統(tǒng)，而網(wǎng)絡(luò)操作系統(tǒng)把它們有機(jī)地聯(lián)系起來。操作系統(tǒng)的形成和發(fā)展階段：1手工操作階

15、段每個(gè)程序員都必須親自動(dòng)手操作計(jì)算機(jī)：裝入卡片或紙帶，按電鈕，查看存儲(chǔ)單元等。2批量處理階段用戶不用與計(jì)算機(jī)直接打交道，而是通過專門的操作員來完成作業(yè)的輸入和輸出。3操作系統(tǒng)形成階段多道程序和分時(shí)系統(tǒng)的出現(xiàn)，標(biāo)志著操作系統(tǒng)的正式形成。1) 多道程序設(shè)計(jì)的定義 所謂多道程序設(shè)計(jì)，是指同時(shí)把若干個(gè)作業(yè)存放在內(nèi)存中，并且同時(shí)處于執(zhí)行過程中。但是在某時(shí)刻只能有一個(gè)程序占用CPU執(zhí)行。2) 分時(shí)系統(tǒng)所謂分時(shí)系統(tǒng)，就是在一臺(tái)計(jì)算機(jī)上，連接若干個(gè)終端，用戶通過這些聯(lián)機(jī)終端設(shè)備采用交互方式把他的程序和數(shù)據(jù)輸入到計(jì)算機(jī)中，并同時(shí)控制程序的執(zhí)行。操作系統(tǒng)分類：1單用戶操作系統(tǒng)在這種操作系統(tǒng)控制下，計(jì)算機(jī)系統(tǒng)串行地

16、執(zhí)行用戶程序，即在執(zhí)行完一個(gè)用戶程序后才接受另一個(gè)用戶程序。一些微機(jī)上配置的操作系統(tǒng)大多數(shù)就屬這種類型。2批處理操作系統(tǒng)在這種操作系統(tǒng)的控制下，計(jì)算機(jī)系統(tǒng)可以同時(shí)接受多個(gè)多用戶程序，一批批地進(jìn)行處理。批處理操作系統(tǒng)一般都提供多道程序設(shè)計(jì)功能，允許多個(gè)程序同時(shí)裝入內(nèi)存執(zhí)行。3分時(shí)操作系統(tǒng)分時(shí)操作系統(tǒng)又稱多用戶操作系統(tǒng)，在這種操作系統(tǒng)的控制下，多個(gè)用戶可以通過各自的終端同時(shí)使用一臺(tái)計(jì)算機(jī)。分時(shí)操作系統(tǒng)有三個(gè)明顯的特點(diǎn)：多路性，交互性和獨(dú)占性。4實(shí)時(shí)操作系統(tǒng)實(shí)時(shí)操作系統(tǒng)是為實(shí)時(shí)計(jì)算機(jī)系統(tǒng)配置的一種操作系統(tǒng)，在這種操作系統(tǒng)的控制下，計(jì)算機(jī)系統(tǒng)能及時(shí)地響應(yīng)外部事件的請求，在規(guī)定的時(shí)間內(nèi)盡快地完成對該事件

17、的處理，并有效地控制所有實(shí)時(shí)設(shè)備和實(shí)時(shí)任務(wù)協(xié)調(diào)地進(jìn)行。在設(shè)計(jì)這類操作系統(tǒng)時(shí)，首先要考慮系統(tǒng)的實(shí)時(shí)性和可靠性，其次才是效率。5網(wǎng)絡(luò)操作系統(tǒng)網(wǎng)絡(luò)操作系統(tǒng)是為計(jì)算機(jī)網(wǎng)絡(luò)配置的操作系統(tǒng)。網(wǎng)絡(luò)中的各臺(tái)計(jì)算機(jī)配置有各自的操作系統(tǒng)，而網(wǎng)絡(luò)操作系統(tǒng)把它們有機(jī)地聯(lián)系起來，因此，它除了具有常規(guī)操作系統(tǒng)所應(yīng)具備的存貯管理、處理機(jī)管理、設(shè)備管理、信息管理和作業(yè)管理等功能外，還具有以下網(wǎng)絡(luò)管理功能：高效可靠地網(wǎng)絡(luò)通信能力以及多種網(wǎng)絡(luò)服務(wù)功能。6分布式操作系統(tǒng) 分布式操作系統(tǒng)是為分布式計(jì)算機(jī)系統(tǒng)配置的操作系統(tǒng)。系統(tǒng)任務(wù)可以在系統(tǒng)中任何別的處理機(jī)上運(yùn)行。并提供高度的并行性和有效地同步算法和通信機(jī)制，自動(dòng)實(shí)行全系統(tǒng)范圍的任務(wù)

18、分配并自動(dòng)調(diào)節(jié)各處理機(jī)的工作負(fù)載為用戶提供一個(gè)方便、友善的用機(jī)環(huán)境。7多處理機(jī)操作系統(tǒng)多處理機(jī)系統(tǒng)是由多臺(tái)處理器組成的計(jì)算機(jī)系統(tǒng)。多處理機(jī)系統(tǒng)可分成兩大類：基于共享存儲(chǔ)的多處理機(jī)系統(tǒng)和基于分布存儲(chǔ)的多處理機(jī)系統(tǒng)。前者稱為緊耦合多處理機(jī)系統(tǒng)，而后者稱為松耦合多處理機(jī)系統(tǒng)。也稱為并行計(jì)算機(jī)系統(tǒng)。并行機(jī)上使用的操作系統(tǒng)稱為并行操作系統(tǒng)。分布式OS的控制策略：集中決策 分布決策信息交換 合作分布式OS設(shè)計(jì)中的關(guān)鍵問題（目標(biāo)）：1透明性 2靈活性 3可靠性4性能 5可擴(kuò)展性分布式操作系統(tǒng)主要特點(diǎn)：- 進(jìn)程通信不能借助于公共存儲(chǔ)器，常采用信息傳遞方式；- 系統(tǒng)中的資源分布于多個(gè)站點(diǎn)，進(jìn)程調(diào)度、資源分配、系

19、統(tǒng)管理必須滿足分布式處理要求，采用一致性、強(qiáng)健性的分布式算法；- 適時(shí)地協(xié)調(diào)各站點(diǎn)的負(fù)載；- 故障檢測、恢復(fù)、系統(tǒng)重構(gòu)；- 分布式系統(tǒng)，首先必須有一個(gè)單一的、全局的進(jìn)程間的通信機(jī)制，從而使任何進(jìn)程都可以和其它進(jìn)程進(jìn)行通信。- 不同機(jī)器上，進(jìn)程管理也相同。進(jìn)程建立、撤消、啟動(dòng)、停止都相同。- 文件系統(tǒng)也必須看起來是相同的。同時(shí)，每個(gè)文件應(yīng)該是在所有地方都是可見的，當(dāng)然，這必須遵守保護(hù)和安全性約束的限制。需要一個(gè)全局的文件系統(tǒng)。- 在系統(tǒng)的所有地方都使用相同的系統(tǒng)調(diào)用接口?；诳偩€的多處理機(jī)：在CPU和總線之間增加一個(gè)高速緩沖存儲(chǔ)器（cache memory），如圖1-5所示。緩沖存儲(chǔ)器保留著最近

20、剛存取過的字。所有的內(nèi)存訪問請求都要經(jīng)過它。如果請求的字在緩沖存儲(chǔ)器中，緩沖存儲(chǔ)器就會(huì)直接響應(yīng)CPU，而不產(chǎn)生總線請求。如果緩沖存儲(chǔ)器足夠大的話，那么成功的可能性，稱為命中率，將是很高的。而且每個(gè)CPU的總線通信量也會(huì)急劇下降，系統(tǒng)中也就能夠容納更多的CPU。通常，緩沖存儲(chǔ)器的大小從64K到1M，命中率經(jīng)?？梢赃_(dá)到90%或更高。 Bus 圖1-5基于總線的多處理機(jī)Cache 的一致性問題：第二章 分布式通信單處理機(jī)系統(tǒng)中：共享存儲(chǔ)器分布式系統(tǒng)實(shí)現(xiàn)進(jìn)程間通信注意的問題：1 無共享存儲(chǔ)器，不能借助共享變量的方法；2機(jī)器間消息傳遞的可靠性低于機(jī)器內(nèi)信息傳遞的可靠性；3系統(tǒng)內(nèi)任意兩臺(tái)機(jī)器未必直接連接，

21、往往需要中轉(zhuǎn)；4 系統(tǒng)內(nèi)的各臺(tái)機(jī)器型號(hào)可能不同；5通信的實(shí)現(xiàn)與系統(tǒng)結(jié)構(gòu)、通信線路結(jié)構(gòu)、通信介質(zhì)的物理性能等有密切關(guān)系。進(jìn)程間通信：進(jìn)程間通信的實(shí)現(xiàn)方法：可以是低級(jí)的，涉及系統(tǒng)調(diào)用，或者通過語言級(jí)的支持實(shí)現(xiàn)進(jìn)程間通信方法主要有：1消息傳遞2管道3sockets4RPC（Remote Procedure Call Protocol 遠(yuǎn)程過程調(diào)用協(xié)議）5共享內(nèi)存對象之間的通信手段：CORBA（Common Object Request Broker Architecture 公共對象請求代理體系結(jié)構(gòu)，通用對象請求代理體系結(jié)構(gòu)）DCOM（Microsoft Distributed Component

22、Object Model分布式組件對象模型）選擇進(jìn)程間通信方法主要考慮的問題：- 程序員對所選方法的熟悉程度；- 進(jìn)程間通信機(jī)制的透明性，程序員知道得細(xì)節(jié)越少，出錯(cuò)得機(jī)會(huì)也就越少；- 系統(tǒng)所支持的方法；- 考慮系統(tǒng)的擴(kuò)充；- 支持進(jìn)程的遷移，不同文件系統(tǒng)的進(jìn)程間通信；- 通信機(jī)制的標(biāo)準(zhǔn)化問題；- 通信機(jī)制的有效性；21 消息傳遞消息傳遞，物理上復(fù)制要共享的數(shù)據(jù)到另外一個(gè)進(jìn)程的地址空間。下列情況，一般不常用消息傳遞：- 兩進(jìn)程不共享內(nèi)存空間；- 在不同的系統(tǒng)中；- 在同一系統(tǒng)中，每個(gè)進(jìn)程有自己的內(nèi)存；消息通常是用消息包或幀的形式發(fā)送的，通過OS提供的基本通信原語。異步型 同步型阻塞原語實(shí)現(xiàn)進(jìn)程不

23、再阻塞，一般有2種方法：- 輪詢：利用測試原語，測試緩沖區(qū)的相關(guān)信息（狀態(tài)），忙等待。- 中斷：也可以在非阻塞原語種利用。輪詢一直不成功，或者一直無中斷，這樣會(huì)無限阻塞下去。要有計(jì)時(shí)器，缺省的設(shè)置，或者程序員控制阻塞send & receiveProcedure ABeginInstructions send (B, message) / where B is the destination / waiting for acknowledgment / received send acknowledgmentnext instructions EndProcedure BBeginIn

24、structions receive (A, message) / where A is the source/ waiting for message/ received messagenext instructions End消息傳遞（同步）適合于C/S模型C/S模型的幾個(gè)設(shè)計(jì)問題：1尋址2阻塞和非阻塞原語3有緩沖和無緩沖原語4可靠和非可靠原語管道：兩進(jìn)程間的通信通過內(nèi)核在有限大小的緩沖區(qū)上實(shí)現(xiàn)，這類原語通過系統(tǒng)調(diào)用實(shí)現(xiàn)。當(dāng)緩沖區(qū)滿時(shí)，引起阻塞。Sockets：通過網(wǎng)絡(luò)的通信，不是共享數(shù)據(jù)結(jié)構(gòu)或文件。22 組通信用途：- 具有冗余結(jié)構(gòu)的系統(tǒng)；- 在分布式系統(tǒng)中查找；- 多副本的更新；- 各

25、種通知；組通信的特性： - 原子性； - 定序；組通信最簡單的實(shí)現(xiàn)方式就是不可靠組播，即簡單地向每個(gè)目標(biāo)發(fā)送一條消息?？煽拷M播：一種實(shí)現(xiàn)方式是發(fā)送者向一個(gè)組中所有成員發(fā)送消息，然后等待每一個(gè)成員的回復(fù)。23 遠(yuǎn)程過程調(diào)用 RPCRPC使用過程調(diào)用實(shí)現(xiàn)遠(yuǎn)程通信，在傳統(tǒng)的過程化程序設(shè)計(jì)語言環(huán)境中，它的語義類似于本地過程調(diào)用的語義，因此，它可向應(yīng)用層用戶提供良好的接口。Client進(jìn)程 Clients Stub Servers Stub Server進(jìn)程程序員不知道調(diào)用的是一個(gè)遠(yuǎn)程過程，還是一個(gè)本地過程，這需要有相應(yīng)的支持機(jī)制，將一臺(tái)計(jì)算機(jī)上語言級(jí)調(diào)用自動(dòng)轉(zhuǎn)化為另一臺(tái)計(jì)算機(jī)上相應(yīng)的語言級(jí)調(diào)用，實(shí)現(xiàn)變

26、量和結(jié)果的傳送。調(diào)用者阻塞，等待返回值，而不是僅僅一個(gè)確認(rèn)值。與各種程序設(shè)計(jì)語言一樣，對參數(shù)的數(shù)目和數(shù)據(jù)類型有限制。RPC與本地調(diào)用的區(qū)別：1數(shù)據(jù)表示問題：如果RPC是在兩種異構(gòu)的機(jī)器上進(jìn)行的，不同機(jī)器數(shù)據(jù)表示可能不同，包括機(jī)器的字長等。2指針：在不具備共享地址空間的情況下，RPC不可能允許在網(wǎng)絡(luò)范圍內(nèi)傳遞指針。3故障：調(diào)用者和被調(diào)用者都可能在調(diào)用期間發(fā)生故障。對于故障，由于調(diào)用者無法知道到底出現(xiàn)了那種情況，因此，系統(tǒng)需要提供一些基本的保護(hù)機(jī)制來確保RPC的正確效果。不同RPC實(shí)現(xiàn)方案定義的這種效果或RPC語義是有差別的。常用的RPC調(diào)用語義:1At- Most -Once (最多一次)相同R

27、PC的重復(fù)調(diào)用，服務(wù)器不處理。2At- least -Once (至少一次)RPC將被執(zhí)行至少一次，可能多次。3Last -of-Many-Call （最近調(diào)用）每個(gè)調(diào)用包含一個(gè)標(biāo)識(shí)，client接收最近調(diào)用者的返回值。RPC系統(tǒng)的實(shí)現(xiàn)問題：1. RPC協(xié)議族(1)面向連接的&面向非連接的 (2)選擇標(biāo)準(zhǔn)的通用協(xié)議，還是專門為RPC設(shè)計(jì)的協(xié)議(3)信包和報(bào)文的長度2. 確認(rèn)- 停等協(xié)議（stop and wait protocol）- 爆發(fā)協(xié)議（blast protocol）3. 緩沖區(qū) 緩沖池4. 計(jì)時(shí)管理失敗情況下的PRC語義，可能出現(xiàn)的問題及其解決方法：1. Client無法定位

28、Server2. 客戶請求消息丟失3. Server應(yīng)答消息丟失4. Server崩潰5. Client崩潰RPC存在的問題：- 服務(wù)器必須被正確定位；- 指針與復(fù)雜的數(shù)據(jù)結(jié)構(gòu)難以傳送；- 全局變量很難使用；- 很難有精確的RPC語義；第三章 分布式協(xié)同處理全局時(shí)間為進(jìn)程和數(shù)據(jù)提供時(shí)間戳。31 事件定序與時(shí)間戳計(jì)算機(jī)上運(yùn)行的應(yīng)用程序只關(guān)心事件發(fā)生的次序，而不是事件發(fā)生的絕對時(shí)間，即只需要用計(jì)數(shù)器的值去給事件打上相應(yīng)的時(shí)間戳。對于集中的物理時(shí)間：請求類和廣播類難點(diǎn)： request for time -àclient time server ß- current time (

29、delay)有延遲，而且是不確定的，因?yàn)榫W(wǎng)絡(luò)故障，可能會(huì)傳送多次。時(shí)間同步算法：集中式系統(tǒng)：Cristian算法；Berkeley算法分布式系統(tǒng)：網(wǎng)絡(luò)時(shí)間協(xié)議（NTP）；統(tǒng)一協(xié)調(diào)時(shí)間（UTC）時(shí)間的質(zhì)量、精確性與時(shí)間提供者的價(jià)格等相關(guān)； 物理時(shí)間：人的時(shí)間；邏輯時(shí)鐘：是一種單調(diào)增長的軟件計(jì)數(shù)器，對事件集進(jìn)行部分排序。相對時(shí)間: 邏輯上是一致的。定序：（1） 若兩個(gè)事件發(fā)生在同一進(jìn)程中，則可用觀察到的次序來確定它們發(fā)生的次序；（2） 無論何時(shí)在進(jìn)程間傳遞消息，發(fā)送消息的事件先于接收同一消息的事件；先決條件：兩個(gè)事件之間，邏輯時(shí)鐘至少變一次，兩個(gè)事件不會(huì)精確地同時(shí)發(fā)生。32 分布式互斥要求： （1

30、） 安全性 （2） 可用性 （3） 定序在單機(jī)系統(tǒng)中，使用信號(hào)量（semaphores）、管程（monitors）等來保護(hù)臨界區(qū)。S P(S) V(S) Wait(s) Signal(s)1集中式算法2分布式算法要求：系統(tǒng)中所有的事件都是全序的當(dāng)一個(gè)進(jìn)程接受到另一個(gè)進(jìn)程請求消息（Request）時(shí):(1) 若接受者不在臨界區(qū)中，也不想進(jìn)入臨界區(qū)，它就向發(fā)送者送Reply消息；(2) 若接受者已在臨界區(qū)中，它就不回答（推遲）；(3) 若接受者要進(jìn)入臨界區(qū)，但還沒有進(jìn)入，它就將自己的請求消息（Request）時(shí)間戳與收到的時(shí)間戳比較，若收到的小，回Reply消息，否則，推遲； 0 8 8 8 12

31、 2 1 12 12 8 12 為時(shí)間戳 0 Reply Reply 1 2 Reply 當(dāng)進(jìn)程0完成時(shí)，進(jìn)程0返回Reply 0 Reply 2 1 在產(chǎn)生請求沖突時(shí)，遵守按時(shí)間戳排序，小時(shí)間戳優(yōu)先的規(guī)則。每次進(jìn)入臨界區(qū)需要2(n-1)條消息， n為系統(tǒng)中的進(jìn)程數(shù)目。相對集中式算法，慢、復(fù)雜、貴、不健壯3令牌算法系統(tǒng)中所有的進(jìn)程可組成一個(gè)虛擬或邏輯環(huán)，每個(gè)進(jìn)程要知道誰在它的下一個(gè)位置。算法：令牌環(huán)被初始化后，進(jìn)程0首先獲得令牌，這樣令牌開始繞環(huán)運(yùn)動(dòng)，它從進(jìn)程k傳遞k+1，以點(diǎn)到點(diǎn)方式若一個(gè)進(jìn)程得到了它相鄰進(jìn)程傳遞來的令牌，但它并不想進(jìn)入臨界區(qū)，就將該令牌往下傳遞。僅擁有令牌的進(jìn)程才有權(quán)進(jìn)入臨

32、界區(qū)。4算法比較 每次進(jìn)出需要的消息 進(jìn)入前的延遲 問題集中式 3 2 協(xié)調(diào)者崩潰分布式 2(n-1) 2(n-1) 任一進(jìn)程崩潰令牌 1 到 不定 0到n-1 丟失令牌，進(jìn)程崩潰33 選擇算法如果這個(gè)協(xié)調(diào)者進(jìn)程由于它駐留的處理機(jī)故障，而無法正常工作（稱為故障），系統(tǒng)只得通過在另一個(gè)處理機(jī)上重新開始一個(gè)新的協(xié)調(diào)者副本才能運(yùn)行，確定在何處重新開始一個(gè)新的協(xié)調(diào)者算法，就稱為選擇算法。Bully（欺負(fù)算法）：（1）Pi給所有比它優(yōu)先數(shù)大的進(jìn)程發(fā)送消息；（2）若無進(jìn)程響應(yīng)，Pi獲勝成為協(xié)調(diào)者；（3）若有優(yōu)先數(shù)比Pi大的進(jìn)程響應(yīng)Pk，響應(yīng)者Pk接管Pi的工作完成；基于環(huán)結(jié)構(gòu)的算法（基于沒有令牌的環(huán)）：（

33、1）當(dāng)任何一個(gè)進(jìn)程發(fā)現(xiàn)協(xié)調(diào)者進(jìn)程不起作用時(shí)，構(gòu)造一個(gè)包含它自身進(jìn)程號(hào)的消息給后繼者；若后繼者失敗，繼續(xù)下一個(gè)；（2）消息到達(dá)了始發(fā)者的手中，始發(fā)者接收者接收到包含它自身進(jìn)程號(hào)的消息后，將其轉(zhuǎn)化為協(xié)調(diào)者消息；（3）該消息將再一次繞環(huán)運(yùn)行，向所有進(jìn)程通知誰是協(xié)調(diào)者；具有最大優(yōu)先數(shù)的進(jìn)程，將它作為新的協(xié)調(diào)者；評(píng)價(jià)分布式同步互斥算法標(biāo)準(zhǔn)：- 響應(yīng)時(shí)間和吞吐量：充分利用系統(tǒng)的分布性，獲得高的吞吐量和小的響應(yīng)時(shí)間。- 容錯(cuò)性：具有幸免于故障的能力。- 開銷大小：算法需要的一些額外開銷，消息的數(shù)目和大小等。- 收斂和公平：請求進(jìn)入臨界段的進(jìn)程終將進(jìn)入，在臨界段執(zhí)行的進(jìn)程終將離開臨界段。并且對各進(jìn)程公平。-

34、可擴(kuò)充性：容易加入新的結(jié)點(diǎn)和新的進(jìn)程。- 確定性：一定能保證同步、互斥，還是可能保證，如果不是確定的，就是概率性的。- 恢復(fù)：對錯(cuò)誤恢復(fù)的能力如何。- 實(shí)用性：對其使用作了多少限制。- 可理解性：如果一個(gè)算法是簡單的，則很容易給出規(guī)范的正確證明。簡單是很重要的，包括：算法的實(shí)現(xiàn)、測試、維護(hù)、修改等等。第四章 資源管理41 資源共享 資源共享的方法：1數(shù)據(jù)遷移- 整個(gè)文件 - 部分文件 通過文件或數(shù)據(jù)庫的水平分割、垂直分割，但分割較麻煩。2計(jì)算遷移傳遞計(jì)算比傳遞數(shù)據(jù)更有效3作業(yè)遷移- 隱式： 作業(yè)遷移最終由系統(tǒng)實(shí)現(xiàn)；- 顯式： 用戶指明作業(yè)如何遷移；42 資源管理- 局部集中管理- 分散式管理-

35、 分級(jí)式管理43 死鎖處理死鎖的4個(gè)條件：1互斥2非搶占資源分配3持有和等待4循環(huán)等待如果不存在上述的任一條件，就不會(huì)發(fā)生死鎖。死鎖預(yù)防、避免、檢測算法。處理死鎖問題的4種著名策略：1 死鎖忽略：不考慮死鎖問題。2 死鎖檢測：允許死鎖發(fā)生，在檢測后想辦法恢復(fù)。3 死鎖預(yù)防：靜態(tài)的使死鎖在結(jié)構(gòu)上是不可能發(fā)生的。4 死鎖避免：通過仔細(xì)的分配資源以避免死鎖。資源分配圖 ( resource allocation graph ): r1 r38P2P1 P3 r2 r4real time 系統(tǒng)：很難如此構(gòu)造“資源分配圖”。計(jì)算機(jī)系統(tǒng)提供的資源包括：1物理資源：CPU、主存、I/O設(shè)備、內(nèi)部設(shè)備、外存等

36、。2邏輯資源：進(jìn)程、文件、共享的程序和數(shù)據(jù)。在分布式系統(tǒng)中，所有這些資源在物理上是分布的。還可分為：1底層資源和高層資源2可共享和不可共享的資源管理的原則：方便、高效、公平。資源管理的內(nèi)容：1配置管理（Configuration）：通過配置管理，系統(tǒng)資源被放在合適的位置，調(diào)整成合適的狀態(tài)。2故障管理（Fault）：處理各種錯(cuò)誤。3安全管理（Security）：提供安全機(jī)制，對系統(tǒng)資源進(jìn)行安全的訪問和使用。4性能管理（Performance）：對系統(tǒng)資源進(jìn)行協(xié)調(diào)、優(yōu)化，以獲得最大的性能和利用率。5帳戶管理（Account）：收集資源的使用情況等。資源管理的任務(wù)：1接受來自客戶方（用戶、進(jìn)程）申請

37、資源的請求，并從資源中選擇適當(dāng)?shù)馁Y源進(jìn)行分配。2接受系統(tǒng)提供的資源，并能組成資源池（資源庫）。具有一定的監(jiān)控，最終可以收回資源。資源死鎖、通信死鎖：通信死鎖發(fā)生于一組直接通信的進(jìn)程之間，當(dāng)它們受阻于等待來自其它進(jìn)程的消息以開始執(zhí)行，但它們之間沒有消息傳遞時(shí)就發(fā)生死鎖。第五章 進(jìn)程與處理機(jī)管理51 進(jìn)程和線程進(jìn)程都包括一個(gè)執(zhí)行環(huán)境，其中有一個(gè)或多個(gè)線程。一個(gè)線程是操作系統(tǒng)中對一個(gè)處理的抽象。創(chuàng)建新進(jìn)程： （1）選擇目標(biāo)機(jī)；（2）創(chuàng)建一個(gè)新的執(zhí)行環(huán)境；（3）在執(zhí)行環(huán)境中創(chuàng)建一個(gè)線程；進(jìn)程和線程的區(qū)別：線程的創(chuàng)建和管理開銷小，線程間共享資源比進(jìn)程間共享資源更有效地實(shí)現(xiàn)。同一個(gè)進(jìn)程的多個(gè)線程的3種模式

38、：線程的調(diào)度：搶占式調(diào)度， 非搶占式調(diào)度52 進(jìn)程管理 等待事件發(fā)生 運(yùn)行態(tài) 等待態(tài) 分配 到處 時(shí)間 傳送結(jié)束 理機(jī) 片到 就緒態(tài) 掛起態(tài) 事件發(fā)生53 處理機(jī)管理1工作站模型：整個(gè)分布式系統(tǒng)是通過局域網(wǎng)連接的工作站構(gòu)成的。無盤工作站（無本地磁盤）：文件系統(tǒng)由一個(gè)或多個(gè)遠(yuǎn)程文件服務(wù)器實(shí)現(xiàn)，讀寫文件的請求將發(fā)送到文件服務(wù)器，由它執(zhí)行并返回結(jié)果。優(yōu)點(diǎn)：維護(hù)容易，使用靈活，共享信息容易，成本低缺點(diǎn)：網(wǎng)絡(luò)通信頻繁有盤工作站:（1）本地磁盤僅用于分頁和存儲(chǔ)是臨時(shí)的、不能共享的、并在登錄會(huì)話結(jié)束后丟棄文件，減少網(wǎng)絡(luò)通信。（2）本地磁盤可以保存二進(jìn)制（可執(zhí)行）程序，如：編譯程序、文本編輯程序等。需要更新二

39、進(jìn)制（可執(zhí)行）程序。（3）本地磁盤用來作緩沖區(qū)，用戶能從文件服務(wù)器下載文件到本地磁盤，在本地讀寫這些文件，然后在登錄會(huì)話結(jié)束之前上載修改后的文件。一致性問題。（4）每臺(tái)機(jī)器能有自己獨(dú)立完備的文件系統(tǒng)，而且能登錄或存取其它機(jī)器上的文件系統(tǒng)。缺點(diǎn)：共享難，更接近網(wǎng)絡(luò)OS2處理機(jī)池模型：在機(jī)柜中放滿CPU，它們可以根據(jù)需要?jiǎng)討B(tài)地分配給用戶。適用于：大規(guī)模的并行計(jì)算。3混合模型：每個(gè)用戶一個(gè)私有工作站，并附加有處理機(jī)池。第六章 任務(wù)分配與負(fù)載平衡61 任務(wù)分配 （task allocation）若干個(gè)模塊構(gòu)成一個(gè)任務(wù)，一個(gè)任務(wù)是單一的處理實(shí)體。任務(wù)分解：把一個(gè)提交的任務(wù)劃分成若干個(gè)獨(dú)立的，具有最小IM

40、C（integrated memory controller 內(nèi)存控制器）的模型。IMC：每對模塊間的數(shù)據(jù)傳遞。IPC（Inter-Process Communication進(jìn)程間通信）：處理機(jī)間的通信。任務(wù)劃分：粒度大，降低并行度；粒度小，進(jìn)程切換和通信的開銷就會(huì)增加。劃分方法：- 水平或垂直劃分：在給定的任務(wù)優(yōu)先圖中水平或垂直劃分。關(guān)鍵路徑（最長路徑）- 通信延遲最小劃分：把通信頻繁的節(jié)點(diǎn)歸成一類。任務(wù)復(fù)制：在各個(gè)處理機(jī)節(jié)點(diǎn)上復(fù)制任務(wù)來降低通信開銷。任務(wù)分配：把這些模塊分配給處理機(jī)，使得它們由于處理機(jī)間的通信引起的開銷最小。一般算法假設(shè)：- 存儲(chǔ)容量無限- 每個(gè)處理機(jī)節(jié)點(diǎn)有相同的處理能力-

41、 忽略網(wǎng)絡(luò)擁塞CPU的利用率最大化，平均響應(yīng)時(shí)間最小化基于圖論的分配策略0- 1程序設(shè)計(jì)策略合一 - 閾值 啟發(fā)式分配算法隨機(jī)算法進(jìn)化算法（演化） 進(jìn)化規(guī)劃進(jìn)化策略 遺傳算法 螞蟻算法 模擬退火 魚群算法遺傳算法求解方法：1編碼方法(Encoding)用一個(gè)n+1位的二進(jìn)制串來表示。 00000 111112初始化群體用過程Initialize來實(shí)現(xiàn)，方法是隨機(jī)生成初始化的串群體。在串群體中，串長度都是相同的，串長為需要分配的文件數(shù)。群體的大小根據(jù)需要(要求的分配時(shí)間等)，按經(jīng)驗(yàn)或?qū)嶒?yàn)給出。分布均勻的二進(jìn)制串能使算法更加有效。3選擇 (Selection)借用達(dá)爾文的生物進(jìn)化論中的自然選擇(N

42、atural Selection)思想，按照“適者生存”的原則對串進(jìn)行復(fù)制。用適應(yīng)度函數(shù)計(jì)算每個(gè)串的適應(yīng)值，選擇適應(yīng)值高的串，生成下一代，去掉適應(yīng)值差的串。4交叉 (Crossover)交叉是兩個(gè)串按照一定的概率(交叉概率Pc)從某一位開始逐位互換。這里先在串群體中，隨機(jī)的選擇兩個(gè)串，成為一對串，變成多對串后，對每對串隨機(jī)的選擇一個(gè)交叉點(diǎn)，例如串長為n+1，則可選擇一整數(shù)i，0i n，i為交叉點(diǎn)，對兩個(gè)串從第0位到第i位進(jìn)行互換，形成兩個(gè)新串。是否發(fā)生交叉操作，還要受交叉概率的控制，選擇好一對串后，在0、1之間產(chǎn)生一個(gè)隨機(jī)數(shù)，若該隨機(jī)數(shù)大于Pc則發(fā)生交叉，否則保持原狀。Pc也是根據(jù)經(jīng)驗(yàn)或?qū)嶒?yàn)確

43、定，一般可為0.5左右。1010 0101 1110 01111011 1111 1011 11011010 0101 1011 11011011 1111 1110 01115突變 (Mutation)二進(jìn)制串的某一位按照一定的概率(突變概率Pm)發(fā)生反轉(zhuǎn)，0變1，1變0。這里Pm較小，Pm可小于0.001.6適應(yīng)度函數(shù)(Fitness Function)這里我們用Evaluation過程來實(shí)現(xiàn)。7停止條件 可以是以下幾種或其組合：(1) 規(guī)定進(jìn)化代數(shù)，也就是最大迭代次數(shù)。(2) 群體中某個(gè)解的適應(yīng)值達(dá)到某一預(yù)先規(guī)定的范圍內(nèi)。(3) 連續(xù)若干代，群體中的個(gè)體不再變化。8相應(yīng)的遺傳算法描述Pr

44、ocedure GA ProgramBegin Initialize; Evaluation; While (not termination-condition) do Begin Selection; Crossover; Mutation; EvaluationEndEnd.方法有以下幾個(gè)優(yōu)點(diǎn):(1) 具有一定的規(guī)律和隨機(jī)性，不確定性。為了處理這種特性引入了概率分析。(2) 適用于變化的環(huán)境。(3) 能得到多個(gè)解，即可得到多個(gè)分配方案可供選擇。(4) 算法具有良好的并行性，進(jìn)化過程中的群體是一個(gè)可行解的集合。適合于并行計(jì)算。62 負(fù)載平衡負(fù)載CPU隊(duì)列的長度（比如進(jìn)程的數(shù)目）某段時(shí)間內(nèi)CP

45、U隊(duì)列的平均長度可用內(nèi)存的大小上下文切換的速率系統(tǒng)調(diào)用的速率CPU的利用率對系統(tǒng)中的負(fù)載情況進(jìn)行動(dòng)態(tài)調(diào)整，以盡量消除或減少系統(tǒng)中個(gè)場點(diǎn)負(fù)載不均勻的現(xiàn)象。由于任務(wù)到達(dá)的隨機(jī)性，各節(jié)點(diǎn)處理能力上的差異，當(dāng)系統(tǒng)運(yùn)行一段時(shí)間后，就會(huì)出現(xiàn)某些節(jié)點(diǎn)上還有很多任務(wù)沒有完成，而另外一些節(jié)點(diǎn)處于空閑。目的：- 發(fā)揮系統(tǒng)冗余資源- 提高資源利用率- 防止軟件并行性和硬件并行性之間失配負(fù)載平衡算法分類：- 局部和全局- 靜態(tài)和動(dòng)態(tài)動(dòng)態(tài)的算法增加了系統(tǒng)的調(diào)度開銷。動(dòng)態(tài)的算法適應(yīng)了應(yīng)用程序可變化、可伸縮等特點(diǎn)的需要，靜態(tài)的算法由于在編譯時(shí)可以完成調(diào)度，對于大型應(yīng)用程序的性能提高也起著一定的作用?？梢越Y(jié)合使用。- 最優(yōu)和

46、次優(yōu)- 近似和啟發(fā)式- 集中和分散式- 協(xié)作和非協(xié)作的針對單個(gè)應(yīng)用程序 和 多個(gè)應(yīng)用程序的- 搶占式和非搶占式的- 自適應(yīng)和非自適應(yīng)的負(fù)載平衡算法的組成：- 轉(zhuǎn)移策略 T1 T2- 選擇策略 - 定位策略- 信息策略收集信息的方式：集中式（多對一，一對多）和分布式（多對多的指令）收集的時(shí)機(jī)：周期或非周期收集的范圍：全局還是局部（CPU可以劃分為大小為K的一些不同的組）收集的負(fù)載信息內(nèi)容：節(jié)點(diǎn)機(jī)的負(fù)載信息。在運(yùn)行的靜態(tài)和動(dòng)態(tài)階段所收集的負(fù)載信息內(nèi)容應(yīng)該是不同的。負(fù)載平衡使用的參數(shù)：- 系統(tǒng)大?。?如處理機(jī)的個(gè)數(shù)，處理機(jī)多，系統(tǒng)容易找到負(fù)載輕的節(jié)點(diǎn)，但系統(tǒng)消息傳輸量大。- 系統(tǒng)負(fù)載：一般用 CPU

47、 隊(duì)列長度來衡量系統(tǒng)負(fù)載。- 系統(tǒng)通信速率：各個(gè)處理機(jī)上任務(wù)的到達(dá)率- 移動(dòng)閾值- 任務(wù)大?。阂话阏f，移動(dòng)一個(gè)太小的任務(wù)是不合適的，對于一個(gè)太大的任務(wù)，或者涉及到大量數(shù)據(jù)和文件的任務(wù)，也最好在本地處理機(jī)節(jié)點(diǎn)上執(zhí)行。決定任務(wù)的大小一般是：對資源的要求、任務(wù)類型（I/O多，還是CPU多）、存儲(chǔ)要求、數(shù)據(jù)文件要求等。- 管理成本： CPU當(dāng)前負(fù)載的測量、CPU決策用的負(fù)載信息、決策發(fā)生的位置、CPU間的任務(wù)傳遞。矛盾：應(yīng)該從足夠多的CPU間尋找，但是尋找過多，通信成本太高。- 響應(yīng)時(shí)間- 可選擇的目標(biāo)節(jié)點(diǎn)- 資源要求負(fù)載不平衡主要有：1某些算法的迭代大小不是固定的，但迭代的大小在編譯時(shí)卻可以求得。2

48、某些算法的迭代大小不是固定的，但迭代的大小依賴于被處理的數(shù)據(jù)，在編譯時(shí)無法求得。3即使迭代大小是固定的，也會(huì)有許多不定因素導(dǎo)致計(jì)算速度的差異。動(dòng)態(tài)負(fù)載平衡算法（影響效率的3個(gè)主要因素）：- 算法- 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) 結(jié)點(diǎn)的度數(shù)Davg= D(I,j)/N(N-1)- 執(zhí)行動(dòng)態(tài)負(fù)載平衡代碼的頻率 （確定負(fù)載平衡的粒度）負(fù)載平衡中其他相關(guān)因素：- 編碼文件和數(shù)據(jù)文件:比如地理上分布的系統(tǒng)，移動(dòng)所需的代價(jià)。- 系統(tǒng)的穩(wěn)定性- 系統(tǒng)體系結(jié)構(gòu)：總線連接系統(tǒng)中傳遞文件的成本比超立方體的要高。Linux Virtual Server ( LVS )Linux虛擬服務(wù)器，負(fù)載調(diào)度是在Linux內(nèi)核中實(shí)現(xiàn)的。一組服

49、務(wù)器通過網(wǎng)絡(luò)連接，它們的前端有一個(gè)負(fù)載調(diào)度器（load balancer）。負(fù)載調(diào)度器將網(wǎng)絡(luò)請求調(diào)度到真實(shí)的服務(wù)器上。負(fù)載調(diào)度算法：負(fù)載調(diào)度是以連接為粒度的。1輪詢調(diào)度（Round-Robin Scheduling）依次將請求調(diào)度到不同的服務(wù)器上。假定：所有服務(wù)器處理性能相同，請求服務(wù)時(shí)間變化不大。2加權(quán)輪詢調(diào)度（Weighted Round-Robin Scheduling）用相應(yīng)的權(quán)值表示服務(wù)器的處理性能，服務(wù)器的缺省權(quán)值為1?？梢越鉀Q服務(wù)器間性能不一致的情況。3.最小連接調(diào)度（Least-Connection Scheduling）把新的連接請求分配到當(dāng)前連接最小的服務(wù)器。假定：所有服務(wù)器處理性能相同。4.加權(quán)最小連接調(diào)度（Weighted Least-Connection Scheduling）用相應(yīng)的權(quán)值表示服務(wù)器的處理性能。5.基于局部性的最少連接調(diào)度（Locality-Based Least Connections Scheduling ）將相同目標(biāo)IP地址的請求調(diào)度到同一臺(tái)服務(wù)器，提高各臺(tái)服務(wù)器的訪問局部性和主存Cache命中率，從而提高這個(gè)集群系統(tǒng)的處理能力。6帶復(fù)制的基于局部性最少連接調(diào)度（