操作系統(tǒng)課件Chapter6

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

為作業(yè)I的周轉(zhuǎn)時(shí)間為作業(yè)I的提交時(shí)間為作業(yè)I的完成時(shí)間ti=tci-tsi面向用戶的調(diào)度性能準(zhǔn)則平均周轉(zhuǎn)時(shí)間t:為作業(yè)I的周轉(zhuǎn)時(shí)間24面向用戶的調(diào)度性能準(zhǔn)則平均帶權(quán)周轉(zhuǎn)時(shí)間w為： tri為作業(yè)i的實(shí)際執(zhí)行時(shí)間 一般來說，系統(tǒng)應(yīng)選擇使作業(yè)的平均周轉(zhuǎn)時(shí)間（或帶權(quán)周轉(zhuǎn)時(shí)間）短的某種算法。因?yàn)?，作業(yè)的平均周轉(zhuǎn)時(shí)間越短，意味著這些作業(yè)在系統(tǒng)內(nèi)停留的時(shí)間越短，因而系統(tǒng)資源的利用率也就越高。面向用戶的調(diào)度性能準(zhǔn)則平均帶權(quán)周轉(zhuǎn)時(shí)間w為：252.面向系統(tǒng)的調(diào)度性能準(zhǔn)則吞吐量：單位時(shí)間內(nèi)所完成的作業(yè)數(shù)，跟作業(yè)本身特性和調(diào)度算法都有關(guān)系－－批處理系統(tǒng)平均周轉(zhuǎn)時(shí)間不是吞吐量的倒數(shù)，因?yàn)椴l(fā)執(zhí)行的作業(yè)在時(shí)間上可以重疊。如：在2小時(shí)內(nèi)完成4個(gè)作業(yè)，而每個(gè)周轉(zhuǎn)時(shí)間是1小時(shí)，則吞吐量是2個(gè)作業(yè)/小時(shí)處理機(jī)利用率：－－大中型主機(jī)各種設(shè)備的均衡利用：如CPU繁忙的作業(yè)和I/O繁忙（指次數(shù)多，每次時(shí)間短）的作業(yè)搭配－－大中型主機(jī)3.調(diào)度算法本身的調(diào)度性能準(zhǔn)則易于實(shí)現(xiàn)執(zhí)行開銷比2.面向系統(tǒng)的調(diào)度性能準(zhǔn)則吞吐量：單位時(shí)間內(nèi)所完成的作業(yè)數(shù)26處理器調(diào)度的兩種方式非搶占方式：采用該方式，一旦將處理器分配給某進(jìn)程后，便讓進(jìn)程一直執(zhí)行，直到該進(jìn)程完成和其因等待某事件而阻塞時(shí)，才將處理器分配給其他進(jìn)程。優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，系統(tǒng)開銷小缺點(diǎn)：難以滿足緊急任務(wù)的要求處理器調(diào)度的兩種方式非搶占方式：27處理器調(diào)度的兩種方式搶占方式采用這種方式，允許調(diào)度程序根據(jù)某種原則停止正在處理器上運(yùn)行的進(jìn)程，將處理器重新分配給其他進(jìn)程。優(yōu)點(diǎn)：能滿足及時(shí)響應(yīng)緊急任務(wù)缺點(diǎn)：增加了系統(tǒng)開銷處理器調(diào)度的兩種方式搶占方式286.4單處理調(diào)度算法先進(jìn)先出調(diào)度算法優(yōu)先級(jí)調(diào)度算法時(shí)間片輪轉(zhuǎn)算法最短進(jìn)程優(yōu)先調(diào)度算法最短剩余時(shí)間優(yōu)先調(diào)度算法最高響應(yīng)比優(yōu)先調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法調(diào)度實(shí)質(zhì)就是一種資源分配，調(diào)度算法是指根據(jù)系統(tǒng)的資源分配策略分配資源的算法。有的算法適用于作業(yè)調(diào)度，有的算法適用于進(jìn)程調(diào)度，有的兩者都適應(yīng)。6.4單處理調(diào)度算法先進(jìn)先出調(diào)度算法調(diào)度實(shí)質(zhì)就是一種資源分29先進(jìn)先出調(diào)度算法基本原則：按照作業(yè)提交或進(jìn)程進(jìn)入就緒隊(duì)列的先后次序來選擇。調(diào)度方式：不可搶占。缺點(diǎn)：比較有利于長作業(yè)，而不利于短作業(yè)。有利于CPU繁忙的作業(yè)，而不利于I/O繁忙的作業(yè)。應(yīng)用：不作為主要的調(diào)度策略，尤其不能用于分時(shí)和實(shí)時(shí)系統(tǒng)。常結(jié)合其他調(diào)度策略使用?？捎糜谧鳂I(yè)調(diào)度和進(jìn)程調(diào)度先進(jìn)先出調(diào)度算法基本原則：按照作業(yè)提交或進(jìn)程進(jìn)入就緒隊(duì)列的先30先進(jìn)先出調(diào)度算法作業(yè)提交時(shí)間執(zhí)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間18.002.008.0010.002.00128.500.5010.0010.502.00439.000.1010.5010.601.601649.500.2010.6010.801.306.5平均周轉(zhuǎn)時(shí)間t＝1.725平均帶權(quán)周轉(zhuǎn)時(shí)間w＝6.875先進(jìn)先出調(diào)度算法作業(yè)提交時(shí)間執(zhí)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間31優(yōu)先級(jí)調(diào)度算法原則： 按照進(jìn)程的優(yōu)先級(jí)大小來調(diào)度，高優(yōu)先級(jí)進(jìn)程得到優(yōu)先處理。應(yīng)用：可用于作業(yè)調(diào)度和進(jìn)程調(diào)度（主要）用于進(jìn)程調(diào)度時(shí)，可分為：“非搶占”的優(yōu)先級(jí)調(diào)度法“可搶占”的優(yōu)先級(jí)調(diào)度法：UNIX系統(tǒng)進(jìn)程調(diào)度算法。優(yōu)先級(jí)調(diào)度算法原則： 按照進(jìn)程的優(yōu)先級(jí)大小來調(diào)32優(yōu)先級(jí)調(diào)度算法優(yōu)先級(jí)的確定方式：靜態(tài)優(yōu)先級(jí)：優(yōu)先級(jí)在進(jìn)程創(chuàng)建時(shí)確定，且在進(jìn)程整個(gè)運(yùn)行期間保持不變。動(dòng)態(tài)優(yōu)先級(jí)：在創(chuàng)建進(jìn)程時(shí)賦予優(yōu)先級(jí)，在進(jìn)程運(yùn)行過程中可以自動(dòng)改變，以便獲得更好的調(diào)度性能。在就緒隊(duì)列中，等待時(shí)間延長則優(yōu)先級(jí)提高，從而使優(yōu)先級(jí)較低的進(jìn)程在等待足夠的時(shí)間后，其優(yōu)先級(jí)提高到可被調(diào)度執(zhí)行；進(jìn)程每執(zhí)行一個(gè)時(shí)間片，就降低其優(yōu)先級(jí)，從而一個(gè)進(jìn)程持續(xù)執(zhí)行時(shí)，其優(yōu)先級(jí)降低到出讓CPU。優(yōu)先級(jí)調(diào)度算法優(yōu)先級(jí)的確定方式：33時(shí)間片輪轉(zhuǎn)算法原則：將系統(tǒng)中所有的就緒進(jìn)程按照FIFO原則，排成一個(gè)隊(duì)列。每次調(diào)度時(shí)將CPU分派給隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片。時(shí)間片的長度從幾個(gè)ms到幾百ms。在一個(gè)時(shí)間片結(jié)束時(shí)，發(fā)生時(shí)鐘中斷。調(diào)度程序據(jù)此暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾，并通過上下文切換執(zhí)行當(dāng)前的隊(duì)首進(jìn)程。進(jìn)程可以未使用完一個(gè)時(shí)間片，就出讓CPU（如阻塞）。調(diào)度方式：可搶占策略應(yīng)用：用于進(jìn)程調(diào)度，特別適用于分時(shí)系統(tǒng)時(shí)間片輪轉(zhuǎn)算法原則：34時(shí)間片長度的確定時(shí)間片長度變化的影響過長－>退化為FIFO算法，進(jìn)程在一個(gè)時(shí)間片內(nèi)都執(zhí)行完，響應(yīng)時(shí)間長。過短－>用戶的一次請(qǐng)求需要多個(gè)時(shí)間片才能處理完，上下文切換次數(shù)增加，響應(yīng)時(shí)間長。對(duì)響應(yīng)時(shí)間的要求：T(響應(yīng)時(shí)間)=N(進(jìn)程數(shù)目)*q(時(shí)間片)時(shí)間片長度的影響因素：就緒進(jìn)程的數(shù)目：數(shù)目越多，時(shí)間片越小（當(dāng)響應(yīng)時(shí)間一定時(shí)）系統(tǒng)的處理能力：應(yīng)當(dāng)使用戶輸入通常在一個(gè)時(shí)間片內(nèi)能處理完，否則使響應(yīng)時(shí)間，平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間延長。時(shí)間片長度的確定時(shí)間片長度變化的影響35最短進(jìn)程優(yōu)先調(diào)度算法原則：從就緒隊(duì)列中挑選所需運(yùn)行時(shí)間最短的進(jìn)程進(jìn)入主存運(yùn)行。調(diào)度方式：“非搶占”策略。 應(yīng)用：不適用于分時(shí)系統(tǒng)優(yōu)點(diǎn)：比FCFS改善平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，缺點(diǎn)：對(duì)長作業(yè)非常不利，可能長時(shí)間得不到執(zhí)行；未能依據(jù)作業(yè)的緊迫程度來劃分執(zhí)行的優(yōu)先級(jí)；難以準(zhǔn)確估計(jì)作業(yè)的執(zhí)行時(shí)間，從而影響調(diào)度性能。最短進(jìn)程優(yōu)先調(diào)度算法原則：從就緒隊(duì)列中挑選所需運(yùn)行時(shí)間最短的36最短進(jìn)程優(yōu)先調(diào)度算法作業(yè)提交時(shí)間執(zhí)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間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)時(shí)間t＝1.55平均帶權(quán)周轉(zhuǎn)時(shí)間t＝5.15最短進(jìn)程優(yōu)先調(diào)度算法作業(yè)提交時(shí)間執(zhí)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)37最短剩余時(shí)間優(yōu)先算法短作業(yè)優(yōu)先調(diào)度算法的變型。原則：讓運(yùn)行到作業(yè)完成時(shí)所需運(yùn)行時(shí)間最短的進(jìn)程優(yōu)先得到處理，包括新進(jìn)入系統(tǒng)的進(jìn)程。調(diào)度方式：“可搶占”策略（新進(jìn)入系統(tǒng)的進(jìn)程有可能搶占處理機(jī)）。優(yōu)點(diǎn)：降低作業(yè)的平均等待時(shí)間； 缺點(diǎn)：估計(jì)運(yùn)行時(shí)間；系統(tǒng)開銷大。應(yīng)用：可用于分時(shí)系統(tǒng)。最短剩余時(shí)間優(yōu)先算法短作業(yè)優(yōu)先調(diào)度算法的變型。38最高響應(yīng)比優(yōu)先調(diào)度算法原則：引入動(dòng)態(tài)優(yōu)先級(jí)機(jī)制，響應(yīng)比高者得到優(yōu)先調(diào)度。動(dòng)態(tài)優(yōu)先數(shù)為：

等待時(shí)間+要求的服務(wù)時(shí)間 要求的服務(wù)時(shí)間調(diào)度方式：“非搶占”策略。缺點(diǎn)：調(diào)度前，需計(jì)算優(yōu)先數(shù)，開銷大。最高響應(yīng)比優(yōu)先調(diào)度算法原則：引入動(dòng)態(tài)優(yōu)先級(jí)機(jī)制，響應(yīng)比高者得39最高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)點(diǎn)：是一種較好的折中算法。如果作業(yè)的等待時(shí)間相同，則要求的服務(wù)時(shí)間越短，其優(yōu)先數(shù)越高，因此，有利于短作業(yè)。當(dāng)要求的服務(wù)時(shí)間相同時(shí)，作業(yè)的優(yōu)先數(shù)取決于等待時(shí)間，因而實(shí)現(xiàn)了FIFO。對(duì)長作業(yè)，當(dāng)其等待時(shí)間越長，其優(yōu)先數(shù)會(huì)越高。最高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)點(diǎn)：是一種較好的折中算法。40最高響應(yīng)比優(yōu)先調(diào)度算法作業(yè)提交時(shí)間執(zhí)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間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)時(shí)間t＝1.625平均帶權(quán)周轉(zhuǎn)時(shí)間t＝5.675最高響應(yīng)比優(yōu)先調(diào)度算法作業(yè)提交時(shí)間執(zhí)行時(shí)間開始時(shí)間完成時(shí)間周41最高響應(yīng)比優(yōu)先調(diào)度算法開始時(shí)只有作業(yè)1，作業(yè)1被選中，執(zhí)行時(shí)間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í)間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í)間0.5;作業(yè)2完成，作業(yè)4執(zhí)行0.2.最高響應(yīng)比優(yōu)先調(diào)度算法開始時(shí)只有作業(yè)1，作業(yè)1被選中，執(zhí)行時(shí)42多級(jí)反饋隊(duì)列算法多級(jí)反饋隊(duì)列算法是時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級(jí)算法的綜合和發(fā)展。優(yōu)點(diǎn)：為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時(shí)間而照顧短進(jìn)程為獲得較好的I/O設(shè)備利用率和縮短響應(yīng)時(shí)間而照顧I/O型進(jìn)程不必估計(jì)進(jìn)程的執(zhí)行時(shí)間，動(dòng)態(tài)調(diào)節(jié)多級(jí)反饋隊(duì)列算法多級(jí)反饋隊(duì)列算法是時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級(jí)算法43基本實(shí)現(xiàn)設(shè)置多個(gè)就緒隊(duì)列，分別賦予不同的優(yōu)先級(jí)，如逐級(jí)降低，隊(duì)列1的優(yōu)先級(jí)最高。優(yōu)先級(jí)和時(shí)間片相結(jié)合：每個(gè)隊(duì)列執(zhí)行時(shí)間片的長度不同，規(guī)定優(yōu)先級(jí)越低則時(shí)間片越長。按FIFO原則調(diào)度；新進(jìn)程進(jìn)入內(nèi)存后，先投入隊(duì)列1的末尾。動(dòng)態(tài)優(yōu)先級(jí)：若按隊(duì)列1一個(gè)時(shí)間片未能執(zhí)行完，則降低投入到隊(duì)列2的末尾，同樣按FIFO算法調(diào)度；如此下去，降低到最后的隊(duì)列，則按"時(shí)間片輪轉(zhuǎn)"算法調(diào)度直到完成。僅當(dāng)較高優(yōu)先級(jí)的隊(duì)列為空，才調(diào)度較低優(yōu)先級(jí)的隊(duì)列中的進(jìn)程執(zhí)行。如果進(jìn)程執(zhí)行時(shí)有新進(jìn)程進(jìn)入較高優(yōu)先級(jí)的隊(duì)列，則搶先執(zhí)行新進(jìn)程，并把被搶先的進(jìn)程投入原隊(duì)列的末尾?；緦?shí)現(xiàn)設(shè)置多個(gè)就緒隊(duì)列，分別賦予不同的優(yōu)先級(jí)，如逐級(jí)降低，44多級(jí)反饋隊(duì)列多級(jí)反饋隊(duì)列45幾點(diǎn)說明I/O型進(jìn)程：讓其進(jìn)入最高優(yōu)先級(jí)隊(duì)列，以及時(shí)響應(yīng)I/O交互。通常執(zhí)行一個(gè)小時(shí)間片，要求可處理完一次I/O請(qǐng)求的數(shù)據(jù)，然后轉(zhuǎn)入到阻塞隊(duì)列。計(jì)算型進(jìn)程：每次都執(zhí)行完時(shí)間片，進(jìn)入更低級(jí)隊(duì)列。最終采用最大時(shí)間片來執(zhí)行，減少調(diào)度次數(shù)。I/O次數(shù)不多，而主要是CPU處理的進(jìn)程：在I/O完成后，放回優(yōu)先I/O請(qǐng)求時(shí)離開的隊(duì)列，以免每次都回到最高優(yōu)先級(jí)隊(duì)列后再逐次下降。為適應(yīng)一個(gè)進(jìn)程在不同時(shí)間段的運(yùn)行特點(diǎn)，I/O完成時(shí)，提高優(yōu)先級(jí)；時(shí)間片用完時(shí)，降低優(yōu)先級(jí)；幾點(diǎn)說明I/O型進(jìn)程：讓其進(jìn)入最高優(yōu)先級(jí)隊(duì)列，以及時(shí)響應(yīng)I/46低級(jí)就緒隊(duì)列高級(jí)就緒隊(duì)列中級(jí)就緒隊(duì)列等待磁盤磁帶等待其他外設(shè)運(yùn)行選中,時(shí)間片500ms超過時(shí)間片啟動(dòng)磁盤磁帶啟動(dòng)其他外設(shè)選中,時(shí)間片200ms選中,時(shí)間片100ms低級(jí)就緒隊(duì)列高級(jí)就緒隊(duì)列中級(jí)就緒隊(duì)列等待磁等待其運(yùn)行選中,時(shí)47多級(jí)反饋隊(duì)列調(diào)度算法具有較好的性能，能滿足各類用戶的需要。對(duì)分時(shí)交互型短作業(yè)，系統(tǒng)通常可在第一隊(duì)列規(guī)定的時(shí)間片內(nèi)讓其完成工作，使終端型用戶都感到滿意；對(duì)短的批處理作業(yè)，通常，只需在第一或第一、第二隊(duì)列中各執(zhí)行一個(gè)時(shí)間片就能完成工作，周轉(zhuǎn)時(shí)間仍然很短；對(duì)長的批處理作業(yè)，它將依次在第一、第二、．．．隊(duì)列中獲得時(shí)間片并運(yùn)行，決不會(huì)出現(xiàn)得不到處理的情況。

多級(jí)反饋隊(duì)列調(diào)度算法具有較好的性能，能滿足各類用戶的需要。48Windows2000/XP調(diào)度算法

Windows2000/XP的調(diào)度是基于內(nèi)核級(jí)線程的；它支持搶占式調(diào)度，包括多個(gè)優(yōu)先數(shù)層次，在某些層次線程的優(yōu)先數(shù)是固定的，在另一些層次線程的優(yōu)先數(shù)將根據(jù)執(zhí)行的情況動(dòng)態(tài)調(diào)整。它的調(diào)度策略是一個(gè)多級(jí)反饋隊(duì)列，每一個(gè)優(yōu)先數(shù)都對(duì)應(yīng)于一個(gè)就緒隊(duì)列，而每一個(gè)進(jìn)程隊(duì)列中的進(jìn)程按照時(shí)間片方式調(diào)度。

Windows2000/XP調(diào)度算法Windows2049Windows2000/XP有兩個(gè)優(yōu)先級(jí)層次

實(shí)時(shí)優(yōu)先級(jí)層次（優(yōu)先數(shù)為31-16）：用于通信任務(wù)和實(shí)時(shí)任務(wù)。當(dāng)一個(gè)線程被賦予一個(gè)實(shí)時(shí)優(yōu)先數(shù)，在執(zhí)行過程中這一優(yōu)先數(shù)是不可變的。2000/XP支持優(yōu)先數(shù)驅(qū)動(dòng)的搶占式調(diào)度，一旦一個(gè)就緒線程的實(shí)時(shí)優(yōu)先數(shù)比運(yùn)行線程高，它將搶占處理器運(yùn)行。

可變優(yōu)先級(jí)層次（優(yōu)先數(shù)為15-0）：用于用戶提交的交互式任務(wù)。具有這一層次優(yōu)先數(shù)的線程，可以根據(jù)執(zhí)行過程中的具體情況動(dòng)態(tài)地調(diào)整優(yōu)先數(shù)，但是15這個(gè)優(yōu)先數(shù)是不能被突破的。

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

為作業(yè)I的周轉(zhuǎn)時(shí)間為作業(yè)I的提交時(shí)間為作業(yè)I的完成時(shí)間ti=tci-tsi面向用戶的調(diào)度性能準(zhǔn)則平均周轉(zhuǎn)時(shí)間t:為作業(yè)I的周轉(zhuǎn)時(shí)間77面向用戶的調(diào)度性能準(zhǔn)則平均帶權(quán)周轉(zhuǎn)時(shí)間w為： tri為作業(yè)i的實(shí)際執(zhí)行時(shí)間 一般來說，系統(tǒng)應(yīng)選擇使作業(yè)的平均周轉(zhuǎn)時(shí)間（或帶權(quán)周轉(zhuǎn)時(shí)間）短的某種算法。因?yàn)?，作業(yè)的平均周轉(zhuǎn)時(shí)間越短，意味著這些作業(yè)在系統(tǒng)內(nèi)停留的時(shí)間越短，因而系統(tǒng)資源的利用率也就越高。面向用戶的調(diào)度性能準(zhǔn)則平均帶權(quán)周轉(zhuǎn)時(shí)間w為：782.面向系統(tǒng)的調(diào)度性能準(zhǔn)則吞吐量：單位時(shí)間內(nèi)所完成的作業(yè)數(shù)，跟作業(yè)本身特性和調(diào)度算法都有關(guān)系－－批處理系統(tǒng)平均周轉(zhuǎn)時(shí)間不是吞吐量的倒數(shù)，因?yàn)椴l(fā)執(zhí)行的作業(yè)在時(shí)間上可以重疊。如：在2小時(shí)內(nèi)完成4個(gè)作業(yè)，而每個(gè)周轉(zhuǎn)時(shí)間是1小時(shí)，則吞吐量是2個(gè)作業(yè)/小時(shí)處理機(jī)利用率：－－大中型主機(jī)各種設(shè)備的均衡利用：如CPU繁忙的作業(yè)和I/O繁忙（指次數(shù)多，每次時(shí)間短）的作業(yè)搭配－－大中型主機(jī)3.調(diào)度算法本身的調(diào)度性能準(zhǔn)則易于實(shí)現(xiàn)執(zhí)行開銷比2.面向系統(tǒng)的調(diào)度性能準(zhǔn)則吞吐量：單位時(shí)間內(nèi)所完成的作業(yè)數(shù)79處理器調(diào)度的兩種方式非搶占方式：采用該方式，一旦將處理器分配給某進(jìn)程后，便讓進(jìn)程一直執(zhí)行，直到該進(jìn)程完成和其因等待某事件而阻塞時(shí)，才將處理器分配給其他進(jìn)程。優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，系統(tǒng)開銷小缺點(diǎn)：難以滿足緊急任務(wù)的要求處理器調(diào)度的兩種方式非搶占方式：80處理器調(diào)度的兩種方式搶占方式采用這種方式，允許調(diào)度程序根據(jù)某種原則停止正在處理器上運(yùn)行的進(jìn)程，將處理器重新分配給其他進(jìn)程。優(yōu)點(diǎn)：能滿足及時(shí)響應(yīng)緊急任務(wù)缺點(diǎn)：增加了系統(tǒng)開銷處理器調(diào)度的兩種方式搶占方式816.4單處理調(diào)度算法先進(jìn)先出調(diào)度算法優(yōu)先級(jí)調(diào)度算法時(shí)間片輪轉(zhuǎn)算法最短進(jìn)程優(yōu)先調(diào)度算法最短剩余時(shí)間優(yōu)先調(diào)度算法最高響應(yīng)比優(yōu)先調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法調(diào)度實(shí)質(zhì)就是一種資源分配，調(diào)度算法是指根據(jù)系統(tǒng)的資源分配策略分配資源的算法。有的算法適用于作業(yè)調(diào)度，有的算法適用于進(jìn)程調(diào)度，有的兩者都適應(yīng)。6.4單處理調(diào)度算法先進(jìn)先出調(diào)度算法調(diào)度實(shí)質(zhì)就是一種資源分82先進(jìn)先出調(diào)度算法基本原則：按照作業(yè)提交或進(jìn)程進(jìn)入就緒隊(duì)列的先后次序來選擇。調(diào)度方式：不可搶占。缺點(diǎn)：比較有利于長作業(yè)，而不利于短作業(yè)。有利于CPU繁忙的作業(yè)，而不利于I/O繁忙的作業(yè)。應(yīng)用：不作為主要的調(diào)度策略，尤其不能用于分時(shí)和實(shí)時(shí)系統(tǒng)。常結(jié)合其他調(diào)度策略使用?？捎糜谧鳂I(yè)調(diào)度和進(jìn)程調(diào)度先進(jìn)先出調(diào)度算法基本原則：按照作業(yè)提交或進(jìn)程進(jìn)入就緒隊(duì)列的先83先進(jìn)先出調(diào)度算法作業(yè)提交時(shí)間執(zhí)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間18.002.008.0010.002.00128.500.5010.0010.502.00439.000.1010.5010.601.601649.500.2010.6010.801.306.5平均周轉(zhuǎn)時(shí)間t＝1.725平均帶權(quán)周轉(zhuǎn)時(shí)間w＝6.875先進(jìn)先出調(diào)度算法作業(yè)提交時(shí)間執(zhí)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間84優(yōu)先級(jí)調(diào)度算法原則： 按照進(jìn)程的優(yōu)先級(jí)大小來調(diào)度，高優(yōu)先級(jí)進(jìn)程得到優(yōu)先處理。應(yīng)用：可用于作業(yè)調(diào)度和進(jìn)程調(diào)度（主要）用于進(jìn)程調(diào)度時(shí)，可分為：“非搶占”的優(yōu)先級(jí)調(diào)度法“可搶占”的優(yōu)先級(jí)調(diào)度法：UNIX系統(tǒng)進(jìn)程調(diào)度算法。優(yōu)先級(jí)調(diào)度算法原則： 按照進(jìn)程的優(yōu)先級(jí)大小來調(diào)85優(yōu)先級(jí)調(diào)度算法優(yōu)先級(jí)的確定方式：靜態(tài)優(yōu)先級(jí)：優(yōu)先級(jí)在進(jìn)程創(chuàng)建時(shí)確定，且在進(jìn)程整個(gè)運(yùn)行期間保持不變。動(dòng)態(tài)優(yōu)先級(jí)：在創(chuàng)建進(jìn)程時(shí)賦予優(yōu)先級(jí)，在進(jìn)程運(yùn)行過程中可以自動(dòng)改變，以便獲得更好的調(diào)度性能。在就緒隊(duì)列中，等待時(shí)間延長則優(yōu)先級(jí)提高，從而使優(yōu)先級(jí)較低的進(jìn)程在等待足夠的時(shí)間后，其優(yōu)先級(jí)提高到可被調(diào)度執(zhí)行；進(jìn)程每執(zhí)行一個(gè)時(shí)間片，就降低其優(yōu)先級(jí)，從而一個(gè)進(jìn)程持續(xù)執(zhí)行時(shí)，其優(yōu)先級(jí)降低到出讓CPU。優(yōu)先級(jí)調(diào)度算法優(yōu)先級(jí)的確定方式：86時(shí)間片輪轉(zhuǎn)算法原則：將系統(tǒng)中所有的就緒進(jìn)程按照FIFO原則，排成一個(gè)隊(duì)列。每次調(diào)度時(shí)將CPU分派給隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片。時(shí)間片的長度從幾個(gè)ms到幾百ms。在一個(gè)時(shí)間片結(jié)束時(shí)，發(fā)生時(shí)鐘中斷。調(diào)度程序據(jù)此暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾，并通過上下文切換執(zhí)行當(dāng)前的隊(duì)首進(jìn)程。進(jìn)程可以未使用完一個(gè)時(shí)間片，就出讓CPU（如阻塞）。調(diào)度方式：可搶占策略應(yīng)用：用于進(jìn)程調(diào)度，特別適用于分時(shí)系統(tǒng)時(shí)間片輪轉(zhuǎn)算法原則：87時(shí)間片長度的確定時(shí)間片長度變化的影響過長－>退化為FIFO算法，進(jìn)程在一個(gè)時(shí)間片內(nèi)都執(zhí)行完，響應(yīng)時(shí)間長。過短－>用戶的一次請(qǐng)求需要多個(gè)時(shí)間片才能處理完，上下文切換次數(shù)增加，響應(yīng)時(shí)間長。對(duì)響應(yīng)時(shí)間的要求：T(響應(yīng)時(shí)間)=N(進(jìn)程數(shù)目)*q(時(shí)間片)時(shí)間片長度的影響因素：就緒進(jìn)程的數(shù)目：數(shù)目越多，時(shí)間片越小（當(dāng)響應(yīng)時(shí)間一定時(shí)）系統(tǒng)的處理能力：應(yīng)當(dāng)使用戶輸入通常在一個(gè)時(shí)間片內(nèi)能處理完，否則使響應(yīng)時(shí)間，平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間延長。時(shí)間片長度的確定時(shí)間片長度變化的影響88最短進(jìn)程優(yōu)先調(diào)度算法原則：從就緒隊(duì)列中挑選所需運(yùn)行時(shí)間最短的進(jìn)程進(jìn)入主存運(yùn)行。調(diào)度方式：“非搶占”策略。 應(yīng)用：不適用于分時(shí)系統(tǒng)優(yōu)點(diǎn)：比FCFS改善平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，缺點(diǎn)：對(duì)長作業(yè)非常不利，可能長時(shí)間得不到執(zhí)行；未能依據(jù)作業(yè)的緊迫程度來劃分執(zhí)行的優(yōu)先級(jí)；難以準(zhǔn)確估計(jì)作業(yè)的執(zhí)行時(shí)間，從而影響調(diào)度性能。最短進(jìn)程優(yōu)先調(diào)度算法原則：從就緒隊(duì)列中挑選所需運(yùn)行時(shí)間最短的89最短進(jìn)程優(yōu)先調(diào)度算法作業(yè)提交時(shí)間執(zhí)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間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)時(shí)間t＝1.55平均帶權(quán)周轉(zhuǎn)時(shí)間t＝5.15最短進(jìn)程優(yōu)先調(diào)度算法作業(yè)提交時(shí)間執(zhí)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)90最短剩余時(shí)間優(yōu)先算法短作業(yè)優(yōu)先調(diào)度算法的變型。原則：讓運(yùn)行到作業(yè)完成時(shí)所需運(yùn)行時(shí)間最短的進(jìn)程優(yōu)先得到處理，包括新進(jìn)入系統(tǒng)的進(jìn)程。調(diào)度方式：“可搶占”策略（新進(jìn)入系統(tǒng)的進(jìn)程有可能搶占處理機(jī)）。優(yōu)點(diǎn)：降低作業(yè)的平均等待時(shí)間； 缺點(diǎn)：估計(jì)運(yùn)行時(shí)間；系統(tǒng)開銷大。應(yīng)用：可用于分時(shí)系統(tǒng)。最短剩余時(shí)間優(yōu)先算法短作業(yè)優(yōu)先調(diào)度算法的變型。91最高響應(yīng)比優(yōu)先調(diào)度算法原則：引入動(dòng)態(tài)優(yōu)先級(jí)機(jī)制，響應(yīng)比高者得到優(yōu)先調(diào)度。動(dòng)態(tài)優(yōu)先數(shù)為：

等待時(shí)間+要求的服務(wù)時(shí)間 要求的服務(wù)時(shí)間調(diào)度方式：“非搶占”策略。缺點(diǎn)：調(diào)度前，需計(jì)算優(yōu)先數(shù)，開銷大。最高響應(yīng)比優(yōu)先調(diào)度算法原則：引入動(dòng)態(tài)優(yōu)先級(jí)機(jī)制，響應(yīng)比高者得92最高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)點(diǎn)：是一種較好的折中算法。如果作業(yè)的等待時(shí)間相同，則要求的服務(wù)時(shí)間越短，其優(yōu)先數(shù)越高，因此，有利于短作業(yè)。當(dāng)要求的服務(wù)時(shí)間相同時(shí)，作業(yè)的優(yōu)先數(shù)取決于等待時(shí)間，因而實(shí)現(xiàn)了FIFO。對(duì)長作業(yè)，當(dāng)其等待時(shí)間越長，其優(yōu)先數(shù)會(huì)越高。最高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)點(diǎn)：是一種較好的折中算法。93最高響應(yīng)比優(yōu)先調(diào)度算法作業(yè)提交時(shí)間執(zhí)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間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)時(shí)間t＝1.625平均帶權(quán)周轉(zhuǎn)時(shí)間t＝5.675最高響應(yīng)比優(yōu)先調(diào)度算法作業(yè)提交時(shí)間執(zhí)行時(shí)間開始時(shí)間完成時(shí)間周94最高響應(yīng)比優(yōu)先調(diào)度算法開始時(shí)只有作業(yè)1，作業(yè)1被選中，執(zhí)行時(shí)間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í)間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í)間0.5;作業(yè)2完成，作業(yè)4執(zhí)行0.2.最高響應(yīng)比優(yōu)先調(diào)度算法開始時(shí)只有作業(yè)1，作業(yè)1被選中，執(zhí)行時(shí)95多級(jí)反饋隊(duì)列算法多級(jí)反饋隊(duì)列算法是時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級(jí)算法的綜合和發(fā)展。優(yōu)點(diǎn)：為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時(shí)間