華中科技大學(xué) 操作系統(tǒng)課件全集

第六章多處理器系統(tǒng)(xìtǒng)和處理器管理精品資料掌握多處理器分類調(diào)度的層次調(diào)度算法的性能(xìngnéng)評價各種調(diào)度算法的基本思想了解多處理器硬件組織結(jié)構(gòu)Windows2000/XP的調(diào)度思想精品資料 無論是在操作系統(tǒng)控制下執(zhí)行的程序，還是操作系統(tǒng)程序自己(zìjǐ)，都最終是要在處理器上執(zhí)行，以便實現(xiàn)其功能。計算機系統(tǒng)的核心是中央處理器。如果一個計算機系統(tǒng)只包括一個中央處理器，稱之為單處理器系統(tǒng)。如果有多個中央處理器，則稱之為多處理器系統(tǒng)。精品資料6.1多處理器系統(tǒng)(xìtǒng) 隨著信息和網(wǎng)絡(luò)技術(shù)的發(fā)展，進入信息時代，帶給計算機領(lǐng)域的一個重要(zhòngyào)的趨勢是越來越普遍的使用多重處理，即配置一個有幾個甚至幾百個處理器的計算機系統(tǒng)。主要原因是由于人們要求處理的信息越來越龐大，要求具有更高性能更高處理速度的計算機系統(tǒng)。精品資料多處理器系統(tǒng)(xìtǒng)的優(yōu)點可靠性；高度并行性；多處理(chǔlǐ)器可增強單處理(chǔlǐ)器計算機系統(tǒng)的能力，而又不比顯著增加費用、價格；建立多重處理(chǔlǐ)，既增強了系統(tǒng)的處理(chǔlǐ)能力，又不必增強完整的額外系統(tǒng)；多處理(chǔlǐ)器系統(tǒng)提供了重要的靈活性。精品資料多處理器的硬件(yìnɡjiàn)組織總線(zǒnɡxiàn)式結(jié)構(gòu)單總線(zǒnɡxiàn)結(jié)構(gòu)多總線(zǒnɡxiàn)結(jié)構(gòu)交叉開關(guān)結(jié)構(gòu)多端口存儲器結(jié)構(gòu)精品資料單總線結(jié)構(gòu)(jiégòu)MI/OI/OCPUCPU精品資料多總線結(jié)構(gòu)SBCSBCSBCSBCM1MmI/OC1I/OC2P1Pn精品資料交叉開關(guān)式結(jié)構(gòu)(jiégòu)M1M2MmP1PnI/OI/O精品資料多端口存儲器結(jié)構(gòu)(jiégòu)核心(héxīn)：多端口存儲器模塊M1M2MmP1PnI/OI/O精品資料6.2多處理器系統(tǒng)(xìtǒng)的分類多處理器簇（Cluster，又稱分布式系統(tǒng)）多處理器簇是指每個處理器都有自己專用的存儲器，每個單元都有自包含的計算機，計算機之間的通信或者經(jīng)由(jīngyóu)專用的線路，或者通過網(wǎng)絡(luò)。共享存儲器的多處理器系統(tǒng)多個處理器共享公用存儲器，每個處理器共享對公用存儲器中的程序和數(shù)據(jù)的訪問。 這種多處理器系統(tǒng)常分為： 主從式多處理器結(jié)構(gòu)和對稱式多處理器結(jié)構(gòu)精品資料主/從式處理器系統(tǒng)(xìtǒng)在主從式處理器系統(tǒng)中，指定一個處理器作為主處理器，其他處理器皆為從處理器，由于(yóuyú)處理器地位是不平等的，所以又稱為非對稱。只有主處理器可運行操作系統(tǒng)，從處理器僅可執(zhí)行用戶程序。精品資料主/從處理器系統(tǒng)(xìtǒng)的缺點主處理負(fù)載過重；主處理器故障(gùzhàng)將引起整個系統(tǒng)故障(gùzhàng)，可靠性差；若主處理器不能充分有效地滿足從處理器的服務(wù)請求，從處理器的利用率會降低。精品資料對稱(duìchèn)式多處理器系統(tǒng)系統(tǒng)中有多個處理器，所有的處理器處于同等地位每個處理器都可以運行操作系統(tǒng)和內(nèi)核程序處理中斷、調(diào)度進程等；每個處理器都同樣(tóngyàng)可以控制I/O設(shè)備和系統(tǒng)中其他資源；系統(tǒng)中所有處理器共享主存儲器，沒有自己私用的存儲器精品資料SMP的組織(zǔzhī)處理器緩存處理器緩存處理器緩存存儲器I/OI/O精品資料6.3調(diào)度(diàodù)的層次 從處理機調(diào)度(diàodù)的對象、時間、功能等不同角度，我們可把處理機調(diào)度(diàodù)分成不同類型。按照調(diào)度(diàodù)的層次，調(diào)度(diàodù)可分為三級：長期調(diào)度(diàodù)按照某種原則從磁盤某些盤區(qū)的作業(yè)隊列和交互作業(yè)中選取作業(yè)進入主存，并為作業(yè)做好運行前的準(zhǔn)備工作和作業(yè)完成后的善后工作。中期調(diào)度(diàodù)決定哪些進程被允許參與競爭處理資源。將進程的部分或全部換出到外存上，將當(dāng)前所需部分換入到內(nèi)存。短期調(diào)度(diàodù)按照某種原則將處理器分配給就緒進程或線程精品資料處理機調(diào)度(diàodù)的層次精品資料1.作業(yè)(zuòyè)調(diào)度作業(yè)的狀態(tài)：提交狀態(tài)作業(yè)被提交給機房后或用戶(yònghù)通過終端鍵盤向計算機中鍵入其作業(yè)時所處的狀態(tài)。后備狀態(tài)作業(yè)的全部信息都已通過輸入設(shè)備輸入，并由操作系統(tǒng)將其存放在磁盤的某些盤區(qū)中等待運行。運行狀態(tài)作業(yè)調(diào)度程序選中而被送入主存，并建立進程投入運行。完成狀態(tài)作業(yè)完成其全部運行，釋放其所占用的全部資源。精品資料作業(yè)(zuòyè)調(diào)度作業(yè)調(diào)度由作業(yè)調(diào)度程序來完成作業(yè)調(diào)度時的兩個決定接納多少個作業(yè)：作業(yè)調(diào)度每次要接納多少個作業(yè)進入內(nèi)存(nèicún)，取決于多道程序度。應(yīng)根據(jù)系統(tǒng)的規(guī)模和運行速度等因素。接納哪些作業(yè)：即應(yīng)將哪些作業(yè)從外存調(diào)入內(nèi)存(nèicún)，這取決于所采用的調(diào)度算法。精品資料作業(yè)(zuòyè)調(diào)度程序的功能按照某種調(diào)度算法從后備作業(yè)(zuòyè)隊列中挑選作業(yè)(zuòyè)為選中的作業(yè)(zuòyè)分配主存和外設(shè)資源為選中的作業(yè)(zuòyè)建立相應(yīng)的進程為選中的作業(yè)(zuòyè)運行時所需的有關(guān)表格，如作業(yè)(zuòyè)表等作業(yè)(zuòyè)結(jié)束時完成該作業(yè)(zuòyè)的善后處理作業(yè)(zuòyè)精品資料選擇(xuǎnzé)調(diào)度算法時考慮的問題設(shè)計目標(biāo)資源利用率均衡地處理系統(tǒng)和用戶地要求在使用優(yōu)先級地系統(tǒng)中，每個進程都有一個(yīɡè)優(yōu)先級，調(diào)度算法應(yīng)優(yōu)先運行高優(yōu)先級進程在使用優(yōu)先數(shù)的系統(tǒng)中，調(diào)度策略還可分為“可搶占”和“不可搶占”兩種方式精品資料調(diào)度的性能(xìngnéng)準(zhǔn)則我們可從不同的角度來判斷(pànduàn)處理機調(diào)度算法的性能，如用戶的角度、處理機的角度和算法實現(xiàn)的角度。實際的處理機調(diào)度算法選擇是一個綜合的判斷(pànduàn)結(jié)果。面向用戶的調(diào)度性能準(zhǔn)則面向系統(tǒng)的調(diào)度性能準(zhǔn)則調(diào)度算法本身的調(diào)度性能準(zhǔn)則精品資料周轉(zhuǎn)時間：作業(yè)從提交到完成（得到結(jié)果）所經(jīng)歷的時間。包括：在收容隊列中等待，CPU上執(zhí)行，就緒隊列和阻塞隊列中等待，結(jié)果輸出等待－－批處理系統(tǒng)平均周轉(zhuǎn)時間t平均帶權(quán)周轉(zhuǎn)時間（帶權(quán)周轉(zhuǎn)時間W是t(周轉(zhuǎn))/t(CPU執(zhí)行)〕響應(yīng)時間：用戶輸入(shūrù)一個請求（如擊鍵）到系統(tǒng)給出首次響應(yīng)（如屏幕顯示）的時間－－分時系統(tǒng)截止時間：開始截止時間和完成截止時間－－實時系統(tǒng)，與周轉(zhuǎn)時間有些相似。公平性：不因作業(yè)或進程本身的特性而使上述指標(biāo)過分惡化。如長作業(yè)等待很長時間。優(yōu)先級：可以使關(guān)鍵任務(wù)達(dá)到更好的指標(biāo)。面向用戶的調(diào)度(diàodù)性能準(zhǔn)則精品資料面向用戶的調(diào)度性能(xìngnéng)準(zhǔn)則平均(píngjūn)周轉(zhuǎn)時間t:

為作業(yè)I的周轉(zhuǎn)時間為作業(yè)I的提交時間為作業(yè)I的完成時間ti=tci-tsi精品資料面向用戶的調(diào)度性能(xìngnéng)準(zhǔn)則平均帶權(quán)周轉(zhuǎn)時間w為： tri為作業(yè)(zuòyè)i的實際執(zhí)行時間 一般來說，系統(tǒng)應(yīng)選擇使作業(yè)(zuòyè)的平均周轉(zhuǎn)時間（或帶權(quán)周轉(zhuǎn)時間）短的某種算法。因為，作業(yè)(zuòyè)的平均周轉(zhuǎn)時間越短，意味著這些作業(yè)(zuòyè)在系統(tǒng)內(nèi)停留的時間越短，因而系統(tǒng)資源的利用率也就越高。精品資料2.面向(miànxiànɡ)系統(tǒng)的調(diào)度性能準(zhǔn)則吞吐量：單位時間內(nèi)所完成的作業(yè)數(shù)，跟作業(yè)本身特性和調(diào)度算法都有關(guān)系－－批處理系統(tǒng)平均周轉(zhuǎn)時間不是吞吐量的倒數(shù)，因為并發(fā)執(zhí)行的作業(yè)在時間上可以重疊。如：在2小時內(nèi)完成4個作業(yè)，而每個周轉(zhuǎn)時間是1小時，則吞吐量是2個作業(yè)/小時處理機利用率：－－大中型主機各種設(shè)備的均衡利用：如CPU繁忙的作業(yè)和I/O繁忙（指次數(shù)多，每次時間短）的作業(yè)搭配－－大中型主機3.調(diào)度算法本身的調(diào)度性能(xìngnéng)準(zhǔn)則易于實現(xiàn)執(zhí)行開銷比精品資料處理器調(diào)度(diàodù)的兩種方式非搶占方式：采用(cǎiyòng)該方式，一旦將處理器分配給某進程后，便讓進程一直執(zhí)行，直到該進程完成和其因等待某事件而阻塞時，才將處理器分配給其他進程。優(yōu)點：實現(xiàn)簡單，系統(tǒng)開銷小缺點：難以滿足緊急任務(wù)的要求精品資料處理器調(diào)度(diàodù)的兩種方式搶占方式采用這種方式，允許調(diào)度程序根據(jù)某種原則停止正在處理器上運行的進程，將處理器重新分配給其他進程。優(yōu)點：能滿足及時響應(yīng)緊急任務(wù)缺點：增加(zēngjiā)了系統(tǒng)開銷精品資料6.4單處理(chǔlǐ)調(diào)度算法先進先出調(diào)度算法(suànfǎ)優(yōu)先級調(diào)度算法(suànfǎ)時間片輪轉(zhuǎn)算法(suànfǎ)最短進程優(yōu)先調(diào)度算法(suànfǎ)最短剩余時間優(yōu)先調(diào)度算法(suànfǎ)最高響應(yīng)比優(yōu)先調(diào)度算法(suànfǎ)多級反饋隊列調(diào)度算法(suànfǎ)調(diào)度實質(zhì)就是一種資源分配，調(diào)度算法是指根據(jù)系統(tǒng)的資源分配策略分配資源的算法。有的算法適用于作業(yè)調(diào)度，有的算法適用于進程調(diào)度，有的兩者都適應(yīng)。精品資料先進先出調(diào)度(diàodù)算法基本原則：按照作業(yè)提交或進程進入就緒隊列的先后次序來選擇。調(diào)度方式：不可搶占。缺點：比較有利于長作業(yè)，而不利于短作業(yè)。有利于CPU繁忙的作業(yè)，而不利于I/O繁忙的作業(yè)。應(yīng)用：不作為主要的調(diào)度策略(cèlüè)，尤其不能用于分時和實時系統(tǒng)。常結(jié)合其他調(diào)度策略(cèlüè)使用?？捎糜谧鳂I(yè)調(diào)度和進程調(diào)度精品資料先進先出調(diào)度(diàodù)算法作業(yè)提交時間執(zhí)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間18.002.008.0010.002.00128.500.5010.0010.502.00439.000.1010.5010.601.601649.500.2010.6010.801.306.5平均周轉(zhuǎn)時間t＝1.725平均帶權(quán)周轉(zhuǎn)時間w＝6.875精品資料優(yōu)先級調(diào)度(diàodù)算法原則： 按照進程的優(yōu)先級大小來調(diào)度(diàodù)，高優(yōu)先級進程得到優(yōu)先處理。應(yīng)用：可用于作業(yè)調(diào)度(diàodù)和進程調(diào)度(diàodù)（主要）用于進程調(diào)度(diàodù)時，可分為：“非搶占”的優(yōu)先級調(diào)度(diàodù)法“可搶占”的優(yōu)先級調(diào)度(diàodù)法：UNIX系統(tǒng)進程調(diào)度(diàodù)算法。精品資料優(yōu)先級調(diào)度(diàodù)算法優(yōu)先級的確定方式：靜態(tài)優(yōu)先級：優(yōu)先級在進程創(chuàng)建時確定，且在進程整個運行(yùnxíng)期間保持不變。動態(tài)優(yōu)先級：在創(chuàng)建進程時賦予優(yōu)先級，在進程運行(yùnxíng)過程中可以自動改變，以便獲得更好的調(diào)度性能。在就緒隊列中，等待時間延長則優(yōu)先級提高，從而使優(yōu)先級較低的進程在等待足夠的時間后，其優(yōu)先級提高到可被調(diào)度執(zhí)行；進程每執(zhí)行一個時間片，就降低其優(yōu)先級，從而一個進程持續(xù)執(zhí)行時，其優(yōu)先級降低到出讓CPU。精品資料時間(shíjiān)片輪轉(zhuǎn)算法原則：將系統(tǒng)中所有的就緒進程按照FIFO原則，排成一個隊列。每次調(diào)度時將CPU分派給隊首進程，讓其執(zhí)行一個時間(shíjiān)片。時間(shíjiān)片的長度從幾個ms到幾百ms。在一個時間(shíjiān)片結(jié)束時，發(fā)生時鐘中斷。調(diào)度程序據(jù)此暫停當(dāng)前進程的執(zhí)行，將其送到就緒隊列的末尾，并通過上下文切換執(zhí)行當(dāng)前的隊首進程。進程可以未使用完一個時間(shíjiān)片，就出讓CPU（如阻塞）。調(diào)度方式：可搶占策略應(yīng)用：用于進程調(diào)度，特別適用于分時系統(tǒng)精品資料時間片長度(chángdù)的確定時間片長度變化(biànhuà)的影響過長－>退化為FIFO算法，進程在一個時間片內(nèi)都執(zhí)行完，響應(yīng)時間長。過短－>用戶的一次請求需要多個時間片才能處理完，上下文切換次數(shù)增加，響應(yīng)時間長。對響應(yīng)時間的要求：T(響應(yīng)時間)=N(進程數(shù)目)*q(時間片)時間片長度的影響因素：就緒進程的數(shù)目：數(shù)目越多，時間片越?。ó?dāng)響應(yīng)時間一定時）系統(tǒng)的處理能力：應(yīng)當(dāng)使用戶輸入通常在一個時間片內(nèi)能處理完，否則使響應(yīng)時間，平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間延長。精品資料最短進程優(yōu)先調(diào)度(diàodù)算法原則：從就緒隊列中挑選所需運行時間最短的進程進入主存運行。調(diào)度方式：“非搶占”策略。 應(yīng)用：不適用于分時系統(tǒng)優(yōu)點：比FCFS改善平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間，缺點：對長作業(yè)非常不利，可能(kěnéng)長時間得不到執(zhí)行；未能依據(jù)作業(yè)的緊迫程度來劃分執(zhí)行的優(yōu)先級；難以準(zhǔn)確估計作業(yè)的執(zhí)行時間，從而影響調(diào)度性能。精品資料最短進程優(yōu)先(yōuxiān)調(diào)度算法作業(yè)提交時間執(zhí)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間18.002.008.0010.002.00128.500.5010.3010.802.304.639.000.1010.0010.10.1.101149.500.2010.1010.300.804平均周轉(zhuǎn)時間t＝1.55平均帶權(quán)周轉(zhuǎn)時間t＝5.15精品資料最短剩余時間優(yōu)先(yōuxiān)算法短作業(yè)優(yōu)先調(diào)度算法的變型。原則：讓運行到作業(yè)完成時所需運行時間最短的進程優(yōu)先得到(dédào)處理，包括新進入系統(tǒng)的進程。調(diào)度方式：“可搶占”策略（新進入系統(tǒng)的進程有可能搶占處理機）。優(yōu)點：降低作業(yè)的平均等待時間； 缺點：估計運行時間；系統(tǒng)開銷大。應(yīng)用：可用于分時系統(tǒng)。精品資料最高響應(yīng)比優(yōu)先(yōuxiān)調(diào)度算法原則：引入動態(tài)優(yōu)先級機制，響應(yīng)比高者得到優(yōu)先調(diào)度。動態(tài)優(yōu)先數(shù)為： 等待時間+要求(yāoqiú)的服務(wù)時間 要求(yāoqiú)的服務(wù)時間調(diào)度方式：“非搶占”策略。缺點：調(diào)度前，需計算優(yōu)先數(shù)，開銷大。精品資料最高響應(yīng)比優(yōu)先(yōuxiān)調(diào)度算法優(yōu)點：是一種較好的折中算法。如果(rúguǒ)作業(yè)的等待時間相同，則要求的服務(wù)時間越短，其優(yōu)先數(shù)越高，因此，有利于短作業(yè)。當(dāng)要求的服務(wù)時間相同時，作業(yè)的優(yōu)先數(shù)取決于等待時間，因而實現(xiàn)了FIFO。對長作業(yè)，當(dāng)其等待時間越長，其優(yōu)先數(shù)會越高。精品資料最高響應(yīng)比優(yōu)先調(diào)度(diàodù)算法作業(yè)提交時間執(zhí)行時間開始時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間18.002.008.0010.002.00128.500.5010.110.62.104.239.000.1010.010.11.101149.500.2010.610.81.306.5平均周轉(zhuǎn)時間t＝1.625平均帶權(quán)周轉(zhuǎn)時間t＝5.675精品資料最高響應(yīng)(xiǎngyìng)比優(yōu)先調(diào)度算法開始時只有作業(yè)1，作業(yè)1被選中，執(zhí)行時間(shíjiān)2.0作業(yè)1完成后，響應(yīng)比依次為(1.5+0.5)/0.5,(1+0.1)/0.1,(0.5+0.2)/0.2;因此作業(yè)3響應(yīng)比最高，作業(yè)3被選中，執(zhí)行時間(shíjiān)0.1；作業(yè)3完成后，響應(yīng)比依次為：(1.6+0.5)/0.5,(0.6+0.2)/0.2;作業(yè)2響應(yīng)比最高。作業(yè)2被選中，執(zhí)行時間(shíjiān)0.5;作業(yè)2完成，作業(yè)4執(zhí)行0.2.精品資料多級反饋(fǎnkuì)隊列算法多級反饋隊列算法是時間片輪轉(zhuǎn)算法和優(yōu)先級算法的綜合和發(fā)展。優(yōu)點：為提高系統(tǒng)吞吐量和縮短(suōduǎn)平均周轉(zhuǎn)時間而照顧短進程為獲得較好的I/O設(shè)備利用率和縮短(suōduǎn)響應(yīng)時間而照顧I/O型進程不必估計進程的執(zhí)行時間，動態(tài)調(diào)節(jié)精品資料基本(jīběn)實現(xiàn)設(shè)置多個就緒隊列，分別賦予不同的優(yōu)先級，如逐級降低，隊列1的優(yōu)先級最高。優(yōu)先級和時間片相結(jié)合：每個隊列執(zhí)行時間片的長度不同，規(guī)定優(yōu)先級越低則時間片越長。按FIFO原則調(diào)度；新進程進入(jìnrù)內(nèi)存后，先投入隊列1的末尾。動態(tài)優(yōu)先級：若按隊列1一個時間片未能執(zhí)行完，則降低投入到隊列2的末尾，同樣按FIFO算法調(diào)度；如此下去，降低到最后的隊列，則按"時間片輪轉(zhuǎn)"算法調(diào)度直到完成。僅當(dāng)較高優(yōu)先級的隊列為空，才調(diào)度較低優(yōu)先級的隊列中的進程執(zhí)行。如果進程執(zhí)行時有新進程進入(jìnrù)較高優(yōu)先級的隊列，則搶先執(zhí)行新進程，并把被搶先的進程投入原隊列的末尾。精品資料多級反饋(fǎnkuì)隊列精品資料幾點說明(shuōmíng)I/O型進程：讓其進入最高優(yōu)先級隊列，以及時響應(yīng)I/O交互。通常執(zhí)行一個小時間片，要求可處理完一次I/O請求的數(shù)據(jù)，然后轉(zhuǎn)入到阻塞隊列。計算型進程：每次都執(zhí)行完時間片，進入更低級隊列。最終采用最大時間片來執(zhí)行，減少調(diào)度次數(shù)。I/O次數(shù)不多，而主要是CPU處理的進程：在I/O完成后，放回優(yōu)先I/O請求時離開的隊列，以免每次都回到最高優(yōu)先級隊列后再逐次下降。為適應(yīng)(shìyìng)一個進程在不同時間段的運行特點，I/O完成時，提高優(yōu)先級；時間片用完時，降低優(yōu)先級；精