高級操作系統(tǒng)課件

第一章

，第一，從硬件角度來講，各個計(jì)算機(jī)都是自治的；第二，從軟件角度來講，用戶將整個系統(tǒng)看作是一臺計(jì)算機(jī)。這兩者都是必需的。分布式系統(tǒng)由許多獨(dú)立的CPU組成，，任務(wù)分布:把一個任務(wù)分解成多個可并行執(zhí)行的子任務(wù)，分散給各場點(diǎn)協(xié)同完成。功能分布:把系統(tǒng)的總功能劃分成若干子功能，分配給各場點(diǎn)分別承擔(dān)。同時工作沒有；有，通過相應(yīng)算法解決；并發(fā)控制兩個基本方法，硬件冗余、軟件恢復(fù)（數(shù)據(jù)備份、日志 系統(tǒng)活動可以在用戶沒有感覺的情況下并行發(fā)生 性 描述AB需要多少時間?這種結(jié)構(gòu)的基本開銷與場點(diǎn)個數(shù)成正比，這種通信速度卻是沒有保障的，因?yàn)閳鳇c(diǎn)可計(jì)算機(jī)支持的協(xié)同工作系統(tǒng)（CSCW，ComputerSupported ork，CSCW特點(diǎn)：、交互性、分布性、協(xié)同性CSCW電子布告欄系統(tǒng)（BBSBulletinBoardOS主從 獨(dú)立 分布分布式計(jì)算機(jī)系統(tǒng)(DistributedComputingSystems)是由多個分散的計(jì)算機(jī)經(jīng)互連網(wǎng)分布式操作系統(tǒng)是為分布式計(jì)算機(jī)系統(tǒng)配置的操作系統(tǒng)。系統(tǒng)任務(wù)可以在系統(tǒng)中任何別的處理機(jī)上運(yùn)行。并提供高度的并行性和有效地同步算法和通信機(jī)制，自動實(shí)行全系統(tǒng)分布式系統(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ò)中的各臺計(jì)算機(jī)配置各自的操作系統(tǒng)，而網(wǎng)絡(luò)操作系統(tǒng)把它們有機(jī)地聯(lián)系起來。CPU終端同時使用一臺計(jì)算機(jī)。分時操作系統(tǒng)有三個明顯的特點(diǎn)：多路互性和獨(dú)占性。計(jì)算機(jī)系統(tǒng)地響應(yīng)外部事件的請求，在規(guī)定的時間內(nèi)盡快地完成對該事件的處理，分布式操作系統(tǒng)是為分布式計(jì)算機(jī)系統(tǒng)配置的操作系統(tǒng)。系統(tǒng)任務(wù)可以在系統(tǒng)中任何別的處理機(jī)上運(yùn)行。并提供高度的并行性和有效地同步算法和通信機(jī)制，自動實(shí)行全系統(tǒng)多處理機(jī)系統(tǒng)是由多臺處理器組成的計(jì)算機(jī)系統(tǒng)。多處理機(jī)系統(tǒng)可分成兩大類：基于共享的多處理機(jī)系統(tǒng)和基于分布的多處理機(jī)系統(tǒng)前者稱為緊耦合多處理機(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)12 45進(jìn)程通信不能借助于公共器，常采用信息傳遞方式基于總線的多處理CPU和總線之間增加一個高速緩沖器（cachememory1-5所示。緩沖器保留著最近剛存取過的字。所有的內(nèi)存請求都要經(jīng)過它。如果請求的字在緩沖器中，緩沖器就會直接響應(yīng)CPU，而不產(chǎn)生總線請求。如果緩沖器足夠大的話，那么成功的可能性，稱為，將是很高的。而且每個CPU的總線通信量也會急劇下降，系統(tǒng)中也就能夠容納的CPU。通常，緩沖器的大小從64K到1M，經(jīng)?？?0%或更高。Cache的一致性問題；第二章分布式通信過程調(diào) 單處理機(jī)系統(tǒng)中共 無共享器，不能借助共享變量的方法 對象之間的通信：CORBA，DCOM消息傳遞，物理上要共享的數(shù)據(jù)到另外一個進(jìn)程的地址空間。下列情況，一般不常用消息通常是用消息包或幀的形式發(fā)送的，通過OS提供的基本通信原語。 2輪詢：利用測試原語，測試緩沖區(qū)的相關(guān)信息（狀態(tài)send&receiveProcedureA…send(B,//whereBisthe//waitingfor receivedsendacknowledgmentnextinstructions……ProcedureB…receive(A,//whereAisthe//waitingfor receivedmessagenextinstructions…消息傳遞（同步）C/SC/S用途 具有冗余結(jié)構(gòu)的系組通信的特 原子 定過程調(diào) RPC使用過程調(diào)用實(shí)現(xiàn)通信，在傳統(tǒng)的過程化程序設(shè)計(jì)語言環(huán)境中，它的語義類似于Client進(jìn)程←→Client’s ←→Server’sStub←→Server進(jìn)程序員不知道調(diào)用的是一個過程，還是一個本地過程，這需要有相應(yīng)的支持機(jī)制，將RPCRPC在不具備共享地址空間的情況下，RPCRPCRPCRPC語義是有差別RPCRPCAtMost (最多一次)RPCAtleast (至少一次)：RPC-RPCRPC面向連接 面向非連接RPC停等協(xié)議（stopandwaitprotocol）爆發(fā)協(xié)議（blastprotocol）緩沖 緩沖PRCClientServerServerClientRPC很難有精確的RPC語義； requestfor→ timecurrenttimeBerkeley算法網(wǎng)絡(luò)時間協(xié)議 安全 可用 定（semaphores Reply已 ，它就不回答（推遲 到的時間戳比較，若收到的小，回Reply消息，否則，條消息，n0k傳k+1就將該令牌往下傳遞。僅擁有令牌的進(jìn)程才進(jìn)入臨界區(qū)。Bully（算法Pi若無進(jìn)程響應(yīng)，Pi(2)PiPkPkPi基于環(huán)結(jié)構(gòu)的算法（基于沒有令牌的環(huán)響應(yīng)時間和吞吐量 充分利用系統(tǒng)的分布性，獲得高的吞吐量和小的響應(yīng)時間容錯性 具有幸免于故障的能力開銷大小 算法需要的一些額外開銷，消息的數(shù)目和大小等可擴(kuò)充性 容易加入新的結(jié)點(diǎn)和新的進(jìn)程恢復(fù) 對錯誤恢復(fù)的能力如何實(shí)用性 對其使用作了多少限制 第四章整個文件部分文 通過文件或數(shù)據(jù)庫的水平分割、垂直分 但分割較麻煩顯式：用戶指明作業(yè)如何遷移；局部集中管 分散式管 分級式管4個條件：互斥；2非搶占資源分配；3持有和等待；4循環(huán)等待4resourceallocationgraphrealtime物理資源：CPU、主存、I/O設(shè)備、設(shè)備、外存等底層資源和資安全管理（Security）提供安全機(jī)制，對系統(tǒng)資源進(jìn)行安全的和使用帳戶管理（Account）收源的使用情況等（接受系統(tǒng)提供的資源，并能組成資源池（。具有一定的，最終可以收回資源。第五章3運(yùn)行 等待到 時 傳送結(jié)理 片就緒 掛起無盤工作站（無本地磁盤：文件系統(tǒng)由一個或多個優(yōu)點(diǎn)：容易，使用靈活，共享信息容易，成本低本地磁盤僅用于分頁和是臨時的、不能共享的、需要更新二進(jìn)制（可執(zhí)行）本地磁盤用來作緩沖區(qū)，用戶能從文件服務(wù)器文件第六章任務(wù)分配與負(fù)載平衡任務(wù)分配（taskIMC任務(wù)：在各個處理機(jī)節(jié)點(diǎn)上任務(wù)來降低通信開銷容量無 每個處理機(jī)節(jié)點(diǎn)有相同的處理能 忽略網(wǎng)絡(luò)擁CPU的利用率最大化，平均響應(yīng)時間最小化0-1 閾值啟發(fā)式分配算法遺傳算法求解方編碼方法nInitialize來實(shí)現(xiàn)，方法是隨機(jī)生成初始化的串群體。在串群體中，串長度都是相同選擇串進(jìn)行。用適應(yīng)度函數(shù)計(jì)算每個串的適應(yīng)值，選擇適應(yīng)值高的串，生成下一代，去掉交叉是兩個串按照一定的概率()機(jī)的選擇兩個串，成為一對串，變成多對串后，對每對串隨機(jī)的選擇一個交叉點(diǎn)，例如串n+1i0i≤ni0i01之c則發(fā)生交叉，否則保持原狀。c也是根據(jù)經(jīng)驗(yàn)或?qū)?.5左右。 1011 1011 突變二進(jìn)制串的某一位按照一定的概率(Pm)發(fā)生反轉(zhuǎn)，01，10PmPm適應(yīng)度函數(shù)(FitnessEvaluation連續(xù)若干代，群體中的不再變化 第1 While(nottermination-condition)do方法有以下幾個優(yōu)點(diǎn)CPU隊(duì)列的長度（比如進(jìn)程的數(shù)目CPU隊(duì)列的平均長度可用內(nèi)存的大小、上下文切換的速率、系統(tǒng)調(diào)用的速率、CPU轉(zhuǎn)移策 收集的范圍：全局還是局部（CPUK的一些不同的組系統(tǒng)大?。喝缣幚頇C(jī)的個數(shù)CPU隊(duì)列長度來衡量系統(tǒng)負(fù)載。一般是：對資源的要求、任務(wù)類型（I/O多，還是CPU多、要求、數(shù)據(jù)文件要求等CPU當(dāng)前負(fù)載的測量、CPU決策用的負(fù)載信息、決策發(fā)生的位置、CPUCPU間尋找，但是尋找過多，通信成本太高。動態(tài)負(fù)載平衡算法（3個主要因素網(wǎng)絡(luò)拓?fù)浣Y(jié) 結(jié)點(diǎn)的度數(shù)Davg= 執(zhí)行動態(tài)負(fù)載平衡代碼的頻率（確定負(fù)載平衡的粒度LinuxVirtualServer(LVSLinuxLinuxbalancer 輪詢調(diào)度（Round-Robin 輪詢調(diào)度（WeightedRound-Robin 最小連接調(diào)度（Least-Connection 最小連接調(diào)度（WeightedLeast-ConnectionScheduling）基于局部性的最少連接調(diào)度（Locality-BasedLeastConnectionsScheduling將相同目標(biāo)IP地址的請求調(diào)度到同一臺服務(wù)器提高各臺服務(wù)器的局部性和主存帶的基于局部性最少連接調(diào)度（Locality-BasedLeastConnectionswithReplicationSchedulingIP地址的請求調(diào)度到同一組服務(wù)器。目標(biāo)地址散列調(diào)度（DestinationHashing通過一個散列（Hash）函數(shù)將一個目標(biāo)IP地址到一臺服務(wù)器上源地址散列調(diào)度（SourceHashingIP可伸縮的web服務(wù)、可伸縮的服務(wù)（音頻、可伸縮的郵件服務(wù) 6.1LVSTurboLinuxLinux集群產(chǎn)品。第七章分布式文件系統(tǒng)7． 性能透明 透明 遷移透明 展開文件服 服 客戶組Read(File,i, inWrite(File,i,data)dataiTruncate(File,l)分布式系統(tǒng)中用于文件 命名的三種常見方法機(jī)器+安裝文件系統(tǒng)到本地文件分層結(jié)責(zé)所有名字集合的特定子集。用一個服務(wù)器位置表來查詢，以確定系統(tǒng)中哪個服務(wù)器操作系統(tǒng)可以用各種方式來文件結(jié)構(gòu)化文件：以記錄結(jié)構(gòu)來表示數(shù)據(jù)。Unix大多數(shù)文件比較?。▽ξ募淖x寫是順序進(jìn)行的，隨機(jī)非常大多數(shù)文件比較 的權(quán)限、改變 創(chuàng)建文件、刪除文件、重命名文件、移動文件、查找文件、文文件服務(wù)器可以配置幾十個GB的內(nèi)存這樣文件系統(tǒng)可以儲留在內(nèi)存而不需要磁盤。每個文件在內(nèi)存中是連續(xù)存放的，而不是將它們打散成若干塊，連續(xù)文件易于和Cachecache可以提高系統(tǒng)的性能，解決一致性 文件 、其他服務(wù)器是否要維持客戶的狀態(tài)信息第八章OS負(fù)責(zé)實(shí)現(xiàn)各個對象（如進(jìn)程、信箱、結(jié)點(diǎn)、I/O設(shè)備、文件、地址）之間的消息傳遞，這就要求的系統(tǒng)對象都有一個名字。對應(yīng)是一個關(guān)系，通過名字對對象進(jìn)行和標(biāo)識。對于計(jì)算機(jī)本身，用數(shù)字標(biāo)識符（二進(jìn)制數(shù)最適合表示OS支持且易名字：規(guī)定了一個尋找的對象即欲的對象；從分布式OS和應(yīng)用的角度，對資源進(jìn)行現(xiàn)有的一些計(jì)算機(jī)系統(tǒng)，對不同類型的對象使用獨(dú)立名原則，如文件名與其它對 命名機(jī)制應(yīng)允許多個不同的對象共用同一個標(biāo)識符（進(jìn)程組DEC系統(tǒng)開發(fā)的全名字服務(wù)（GlobalNameService,Lampson,1986）故障 懷一般名方一個是由系統(tǒng)使用的名。由于系統(tǒng)可以有多個用戶，常常組織成層次結(jié)構(gòu)。大多數(shù)系統(tǒng)允許用戶設(shè)置一個默認(rèn)或當(dāng)前。分布式系統(tǒng)中名方式分布式系統(tǒng)中常用名方案有（name功能：將一個符號串成系統(tǒng)內(nèi)唯一的物理地址。名字服務(wù)器管理著包含有“名字方式：全系統(tǒng)僅有一個名字服務(wù)器；方式：每個場點(diǎn)都有一個名字服務(wù)器的透明性與下面幾點(diǎn)要求相局部由于強(qiáng)調(diào)透明性而犧牲了（部分）第九章事務(wù)的并發(fā)控制對事務(wù)的調(diào)度要保證對共享數(shù)據(jù)的執(zhí)行效果與其串行調(diào)度等價，服務(wù)器可通過串行數(shù)據(jù)實(shí)現(xiàn)串行等價。當(dāng)事務(wù)完成時，當(dāng)一數(shù)據(jù)項(xiàng)被加鎖，則只有加鎖的事務(wù)可它，其它事務(wù)或者等待鎖被解開，或者在某種情況下共享鎖。使用鎖會導(dǎo)致死鎖，即事務(wù)彼此等待。 時間戳，以決定操作是否可立即執(zhí)行、或被延遲、被。 不 寫鎖：寫之前獲得，不能讀或?qū)懀ㄔ賹?UnLock操需要的鎖，這樣開銷也就越大，也就更容易導(dǎo)致死鎖?；A(chǔ)：在大多數(shù)應(yīng)用中，兩客戶的事務(wù)同一數(shù)據(jù)項(xiàng)的可能性很小。CloseTransaction數(shù)據(jù)項(xiàng)上的操作發(fā)生，若驗(yàn)證通過，則事務(wù)提交，若驗(yàn)證失敗，則要采用某種形式若事務(wù)通過驗(yàn)證，它的試用性質(zhì)版本中的所有修改記錄將設(shè)置成的事務(wù)驗(yàn)證即驗(yàn)證采用讀/寫規(guī)則保證其特定事務(wù)的調(diào)度關(guān)于所有其他的事務(wù)是串行事務(wù)驗(yàn)證：是基于一對事務(wù)Ti和Tj的操作間的，事務(wù)Tj關(guān)于一個事務(wù)Ti是可串1.第十章分布式事務(wù)ACID特性：原子 一致 獨(dú)立 持久事務(wù)的第一個服務(wù)器成為事務(wù)的協(xié)調(diào)者，負(fù)責(zé)終止或提交事務(wù)，以及增加其他被稱為參與closetransaction給協(xié)調(diào)者，參與者只能檢測到這種情況：長時間沒有特定事中途退出（domino如果其他事務(wù)看到了與退出的事務(wù)有關(guān)的結(jié)果，這個事務(wù)的退出可能dominoeffect。暫時拷貝可以保存在本地的易失器中，如果一直不進(jìn)入提交階段，則刪除暫時拷貝。如果進(jìn)入提交階段，則把暫時拷貝到的不易丟失的器中。行合理的調(diào)度。分布式系統(tǒng)中的服務(wù)器共同負(fù)