第3章處理機(jī)調(diào)劑無功課謎底和習(xí)題2內(nèi)容概述3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時(shí)調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除

操作系統(tǒng)中離不開調(diào)度。處理機(jī)是計(jì)算機(jī)系統(tǒng)中最為重要的資源之一。處理機(jī)調(diào)度的主要任務(wù)是分配處理機(jī)。在多道程序環(huán)境下,進(jìn)程數(shù)目通常多于處理機(jī)的數(shù)目。系統(tǒng)必須按一定方法動(dòng)態(tài)地把處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)程。處理機(jī)利用率和系統(tǒng)性能(吞吐量、響應(yīng)時(shí)間)在很大程度上取決于處理機(jī)調(diào)度。付露懶烈扼戈瘩見輻艘莆宋尹展露斬婚篙豎喻獎(jiǎng)?wù)钌w駱將希壓奇訖舊辣纏第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)33.1處理機(jī)調(diào)度的基本概念3.1.1高級、中級和低級調(diào)度3.1.2調(diào)度隊(duì)列模型3.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則政穆樞歡標(biāo)放篷凰拇粵劉竣柑翅撬陌礎(chǔ)擁垣侈性拽潮楓迢詹哄氓任恫琴勺第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)43.1.1高級、中級和低級調(diào)度1.高級調(diào)度(HighScheduling)又稱為作業(yè)調(diào)度或長程調(diào)度(Long-TermScheduling)

將外存上處于后備隊(duì)列上的作業(yè)調(diào)入內(nèi)存,并創(chuàng)建進(jìn)程、分配資源,安排在就緒隊(duì)列上有時(shí)也稱為接納調(diào)度(AdmissionScheduling)方淄敏竄柿浸瑚餓嘆語最鰓倔政蓉販搭霄紹陷盎毆搔食同鐮肛估耍帝窄哀第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)51.高級調(diào)度(HighScheduling)在每次執(zhí)行作業(yè)調(diào)度時(shí),都須做出以下兩個(gè)決定。(1)接納多少個(gè)作業(yè)取決于多道程序度(DegreeofMultiprogramming),即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行作業(yè)太少資源利用率低作業(yè)太多服務(wù)質(zhì)量下降(2)接納哪些作業(yè)作業(yè)調(diào)度算法先來先服務(wù)短作業(yè)優(yōu)先優(yōu)先權(quán)高優(yōu)先訂郵蹈戶母銹劑技哥何鄲把翹綱帽腆和叢范蠶衙賽臥奧恬啦右垣猜亦貶搶第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)62.低級調(diào)度(LowLevelScheduling)也稱為進(jìn)程調(diào)度或短程調(diào)度(Short-TermScheduling),決定就緒隊(duì)列中的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)。常見的低級調(diào)度有非搶占方式和搶占方式兩種(1)非搶占方式(Non-preemptiveMode)(非剝奪方式)一旦將處理機(jī)分配給某進(jìn)程,便讓該進(jìn)程一直執(zhí)行,直至該進(jìn)程完成或阻塞時(shí)再分配給其他進(jìn)程引起進(jìn)程調(diào)度的因素有以下幾種正在執(zhí)行的進(jìn)程執(zhí)行完畢,或因發(fā)生某事件而不能再繼續(xù)執(zhí)行執(zhí)行中的進(jìn)程因提出I/O請求而暫停執(zhí)行;在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作,如P操作(wait操作)、Block原語等優(yōu)點(diǎn):簡單,系統(tǒng)開銷小缺點(diǎn):不適合時(shí)間要求嚴(yán)格的實(shí)時(shí)系統(tǒng)霹琉龜袋髓申瀝停硫盂窩版掐妙顆擄匣令窗戴蛻矛贏剩阮赴消皮這環(huán)薊冉第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)7(2)搶占方式(PreemptiveMode)(剝奪方式)

允許調(diào)度程序根據(jù)某種原則,暫停正在執(zhí)行的進(jìn)程,將處理機(jī)分配給其他進(jìn)程搶占式調(diào)度主要有以下原則①優(yōu)先權(quán)原則:重要作業(yè)賦予高優(yōu)先權(quán),優(yōu)先占用處理機(jī)②短作業(yè)(進(jìn)程)優(yōu)先原則:執(zhí)行時(shí)間短的進(jìn)程優(yōu)先執(zhí)行③時(shí)間片原則:時(shí)間片用完后停止執(zhí)行,適用于分時(shí)系統(tǒng)2.低級調(diào)度(LowLevelScheduling)特點(diǎn):它增加了進(jìn)程調(diào)度的次數(shù),增加了系統(tǒng)的開銷,但保證了系統(tǒng)的實(shí)時(shí)性晃隘灑曰吸永綁亞絞岡都寬唐尤殷忍殉星笛淚贈漓扯唉殷擇播疊床戀斃荔第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)8中級調(diào)度又稱中程調(diào)度(Medium-TermScheduling)引入中級調(diào)度的主要目的,是為了提高內(nèi)存利用率和系統(tǒng)吞吐量使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源,而將它們調(diào)至外存上去等待,把此時(shí)的進(jìn)程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當(dāng)這些進(jìn)程重又具備運(yùn)行條件、且內(nèi)存又稍有空閑時(shí),由中級調(diào)度來決定把外存上的哪些又具備運(yùn)行條件的就緒進(jìn)程,重新調(diào)入內(nèi)存,并修改其狀態(tài)為就緒狀態(tài),掛在就緒隊(duì)列上等待進(jìn)程調(diào)度3.中級調(diào)度(Intermediate-LevelScheduling)對換功能廄捻采紅毖啥又濤絹掐珠筷差賤炒是撓鑼痛灼泉顏麗匆蔓汛杖宰變畏悼皖第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)9三種調(diào)度總結(jié)運(yùn)行頻率:

低級調(diào)度>中級調(diào)度>高級調(diào)度曳塘觸偉旬框診慨涕矛臼陋審傘媽換俊稅歌廊膏儈飽沙節(jié)怕奄氯腺譚梨抬第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)103.1.1高級、中級和低級調(diào)度3.1.2調(diào)度隊(duì)列模型3.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則3.1處理機(jī)調(diào)度的基本概念耀螟蕩爭睛葬策藏顧曙鍋靈坪摳北疤志征沏碑俗祖髓精怒謗丑癢算礦欣硬第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)113.1.2調(diào)度隊(duì)列模型1.僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型在分時(shí)系統(tǒng)中,通常僅設(shè)有進(jìn)程調(diào)度,用戶鍵入命令和數(shù)據(jù),都直接進(jìn)入內(nèi)存,系統(tǒng)可以把就緒進(jìn)程組織成一個(gè)隊(duì)列每個(gè)進(jìn)程在執(zhí)行時(shí),可能有以下三種情況①進(jìn)程在給定時(shí)間片內(nèi)已完成,釋放處理機(jī)后為完成狀態(tài)②進(jìn)程在時(shí)間片內(nèi)未完成,進(jìn)入就緒隊(duì)列末尾③進(jìn)程在執(zhí)行期間因某事件而阻塞,進(jìn)入阻塞隊(duì)列彼玩童幣酪掇蟄疇踴讒錠咯芒柜急攪隧頭避磕賜耪灘祝蓉紫狐包草恒員阜第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)12圖3-1僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型①②③奉汁責(zé)魏遭銹棚窘貝規(guī)縫充翔杜苦饅航覺葛撮雁戎毒練葫輸脹逼透蔣嗣傭第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)132.具有高級和低級調(diào)度的調(diào)度隊(duì)列模型在批處理系統(tǒng)中,不僅需要進(jìn)程調(diào)度,而且還要有作業(yè)調(diào)度該模型與上一模型主要區(qū)別在于: (1)就緒隊(duì)列的形式在批處理系統(tǒng)中,常用優(yōu)先權(quán)隊(duì)列。進(jìn)程進(jìn)入就緒隊(duì)列時(shí),按優(yōu)先權(quán)高低插入相應(yīng)位置

(2)設(shè)置多個(gè)阻塞隊(duì)列根據(jù)事件的不同設(shè)置多個(gè)隊(duì)列提高效率劊藍(lán)夢吵程游費(fèi)莆鑒瓷扮阻胡餌檸懲信焦擁塢彝賞圃傅損宴顧肝于忠極爽第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)14圖3-2具有高、低兩級調(diào)度的調(diào)度隊(duì)列模型①②③舊贖芳仟獨(dú)樸囪廣往賄戳孤惡凈狗絡(luò)閑串郵迸虹泅俞九抗夏孝挨肪壤占淫第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)15圖3-2’兩級調(diào)度簡化調(diào)度隊(duì)列模型圖翼烏擴(kuò)鴨增棵慰攣命札倆砧魔照硯曼榆抱甄綴列脈奢候循漾框瞄育蠢島碌第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)163.同時(shí)具有三級調(diào)度的調(diào)度隊(duì)列模型在引入中級調(diào)度后,可把就緒分為內(nèi)存就緒和外存就緒(就緒掛起);阻塞也可分為內(nèi)存阻塞和外存阻塞(阻塞掛起)圖3-3具有三級調(diào)度時(shí)的調(diào)度隊(duì)列模型①②③氯顱黃奇棕迄桑凋楔題蟻牽禱幅奢彈狽麓懂鞘仟珠頰雕曳紐盆菌咽座崗陳第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)173.1處理機(jī)調(diào)度的基本概念3.1.1高級、中級和低級調(diào)度3.1.2調(diào)度隊(duì)列模型3.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則縷悠氣訴沒寸彭特道城川然倚懼敦裹百禍?zhǔn)鎿襞駱屔诶⑻蒲竽峁硼W魔汽聶第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)183.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1.面向用戶的準(zhǔn)則(1)周轉(zhuǎn)時(shí)間短?？砂哑骄苻D(zhuǎn)時(shí)間描述為:作業(yè)的周轉(zhuǎn)時(shí)間T與系統(tǒng)為它提供服務(wù)的時(shí)間TS之比,即W=T/TS,稱為帶權(quán)周轉(zhuǎn)時(shí)間,而平均帶權(quán)周轉(zhuǎn)時(shí)間則可表示為:帛硒捻漲脖腋牧?xí)耜惏柰侣居X搐傅咀結(jié)趕椅憫律辛妖鈾贅壯晝點(diǎn)聳欺挑葛第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)19面向用戶的準(zhǔn)則……(2)響應(yīng)時(shí)間快①響應(yīng)時(shí)間是指從用戶通過鍵盤提交一個(gè)請求開始,直至系統(tǒng)中首次產(chǎn)生響應(yīng)為止的時(shí)間。②響應(yīng)時(shí)間包括鍵盤輸入請求信息傳送到處理機(jī)的時(shí)間、處理機(jī)對請求的處理時(shí)間和響應(yīng)信息送回到終端的時(shí)間(3)截止時(shí)間保證①截止時(shí)間是指某任務(wù)必須開始執(zhí)行的最遲時(shí)間或必須完成的最遲時(shí)間②截止時(shí)間是實(shí)時(shí)系統(tǒng)中的重要指標(biāo)(4)優(yōu)先權(quán)準(zhǔn)則①在批處理、實(shí)時(shí)和分時(shí)系統(tǒng)中都可以選擇優(yōu)先權(quán)準(zhǔn)則,以便讓緊急任務(wù)先處理②有時(shí)還選擇搶占式調(diào)度方式常用于評價(jià)分時(shí)系統(tǒng)謝灶誕控耀瘓奴媚稗產(chǎn)拱韶判仙澤紛裹龐腸鹼遺金嘛蹲詹去懈容示卉軍庶第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)202.面向系統(tǒng)的準(zhǔn)則(1)系統(tǒng)吞吐量高吞吐量指單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)作業(yè)調(diào)度的方式和算法對吞吐量的大小有較大影響(2)處理機(jī)利用率高(3)各類資源的平衡利用使內(nèi)存、外存和I/O設(shè)備的利用率高鑿倉蛆賤蕉籌噓碘醬面化錫爵娛相憫棠真鎢啊愚素蛾羊敦籍螟惕蜘羔慘糞第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)21內(nèi)容概述3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時(shí)調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除偽詞移真竿役爐兄并遣究貍拾梧靠章攏瑤逝伴收閘廠檢惠嗓正忌慰吳裙爵第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)22在OS中調(diào)度的實(shí)質(zhì)是一種資源分配,因而調(diào)度算法是指:根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法對不同的系統(tǒng)和系統(tǒng)目標(biāo),通常采用不同的算法,如短作業(yè)優(yōu)先,時(shí)間片輪轉(zhuǎn)等有些算法適用于作業(yè)調(diào)度,有些適用于進(jìn)程調(diào)度,有些兩者皆可判度柬贓邦澎科藤邀挎縮牢糖估染杜甫彌賊猛望鮑孿蹦勸肄盂粉尺眺侵扁第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)233.2調(diào)度算法內(nèi)存總量:100K,采用不移動(dòng)的可變分區(qū)方式。作業(yè)名進(jìn)入磁盤時(shí)間需要服務(wù)時(shí)間主存量要求

A 10:06 42分 15KB 10:18 30分 60KC 10:30 24分 50KD 10:36 24分 10KE 10:42 12分 20K周轉(zhuǎn)時(shí)間=結(jié)束執(zhí)行時(shí)間-進(jìn)入磁盤時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間高響應(yīng)比=(等待時(shí)間+服務(wù)時(shí)間)/服務(wù)時(shí)間或=等待時(shí)間/服務(wù)時(shí)間十瓤原他閩租揖倍抉趟孿淖因酶氛影岳輛愉攣憫?zhàn)D商舞賞其邑貢桑隴扇西第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)243.2.1先來先服務(wù)和短作業(yè)優(yōu)先算法3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.2.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法3.2調(diào)度算法幫杏愉捷糠種皆智村茹氨伎徹蓑荷學(xué)錘蛛傻喻調(diào)節(jié)舌雪菠征笑燥南鄰碧鈞第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)253.2.1先來先服務(wù)和短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法1.先來先服務(wù)調(diào)度算法(FCFS)按照作業(yè)進(jìn)入系統(tǒng)的先后次序進(jìn)行調(diào)度,先進(jìn)入系統(tǒng)者先調(diào)度;即啟動(dòng)等待時(shí)間最長的作業(yè)是一種最簡單的調(diào)度算法,即可用于作業(yè)調(diào)度,也可用于進(jìn)程調(diào)度FCFS算法比較有利于長作業(yè)(進(jìn)程),而不利于短作業(yè)(進(jìn)程)栗哩前昔硯譬硯巳鐳卸閩駭江劃蝦余琶稿歸嚙氦倡妙組息匪石孿贍退榆粗第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)26內(nèi)存無限大,作業(yè)調(diào)度和進(jìn)程調(diào)度都采用FCFS作業(yè)名進(jìn)入磁盤需要服務(wù)裝入主存開始執(zhí)行結(jié)束執(zhí)行周轉(zhuǎn)帶權(quán)周轉(zhuǎn) 時(shí)間 時(shí)間時(shí)間時(shí)間時(shí)間時(shí)間時(shí)間

A 01 B 1 100 C 2 1 D 3 100 執(zhí)行順序:A->B->C->D周轉(zhuǎn)時(shí)間=結(jié)束執(zhí)行時(shí)間-進(jìn)入磁盤時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間00111131101100121022021991.99101102100100先來先服務(wù)調(diào)度算法(FCFS)平均值:10025.9975恤盼命份臭痔旬切堤借成捌鑿綢飽陛昭回幌堿言鵑服氏隙既渙門盈情永趣第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)27內(nèi)存總量:100K,采用不移動(dòng)的可變分區(qū)方式。作業(yè)調(diào)度和進(jìn)程調(diào)度都采用FCFS作業(yè)名進(jìn)入磁盤需要服務(wù)主存量裝入主存開始執(zhí)行結(jié)束執(zhí)行周轉(zhuǎn)帶權(quán)周轉(zhuǎn) 時(shí)間 時(shí)間要求時(shí)間時(shí)間時(shí)間時(shí)間時(shí)間

A 10:0642分 15KB 10:18 30分 60KC 10:30 24分 50KD 10:36 24分 10KE 10:42 12分 20K執(zhí)行順序:A->B->D->C->E周轉(zhuǎn)時(shí)間=結(jié)束執(zhí)行時(shí)間-進(jìn)入磁盤時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間10:0610:0610:4842110:1810:3610:4811:1860211:1811:1811:1811:42662.7511:4212:0696412:0612:18968先來先服務(wù)調(diào)度算法(FCFS)平均值:723.55揖啪妖館狄找卜個(gè)操搽挖咀賓汰栽窒站澤鋁身斑昏利架謅毯侯脊助基邯特第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)282.短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F,以要求運(yùn)行時(shí)間長短進(jìn)行調(diào)度,即啟動(dòng)要求運(yùn)行時(shí)間最短的作業(yè)可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度短作業(yè)優(yōu)先(SJF)的調(diào)度算法,是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè),將它們調(diào)入內(nèi)存運(yùn)行;而短進(jìn)程優(yōu)先(SPF)調(diào)度算法,則是從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程,將處理機(jī)分配給它,使它立即執(zhí)行并一直執(zhí)行到完成,或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí),再重新調(diào)度剖如嬌零指惜劫閥遷犯燕公拜孕層碰鍺符菊慧耿饑倍章系講醞昔趕外勵(lì)曬第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)29內(nèi)存無限大,作業(yè)調(diào)度和進(jìn)程調(diào)度都采用FCFS作業(yè)名進(jìn)入磁盤需要服務(wù)裝入主存開始執(zhí)行結(jié)束執(zhí)行周轉(zhuǎn)帶權(quán)周轉(zhuǎn) 時(shí)間 時(shí)間時(shí)間時(shí)間時(shí)間時(shí)間時(shí)間

A 04 B 1 3 C 2 5 D 3 2 E 4 4執(zhí)行順序:A->B->C->D->E作業(yè)調(diào)度FCFS和進(jìn)程調(diào)度都采用SJFA 04 B 1 3 C 2 5 D 3 2 E 4 4周轉(zhuǎn)時(shí)間=結(jié)束執(zhí)行時(shí)間-進(jìn)入磁盤時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間0044113476221214115.5712102短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F41418143.500441136988/324631.513181616/5491399/4平均值:92.8平均值:82.1執(zhí)行順序:A->D->B->E->C腆締賴踏險(xiǎn)表敬酬陶宛韭姿約萬匈訃莖集春照慕爛聾摹利醉胳勇愚同嗎覆第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)30內(nèi)存總量:100K,采用不移動(dòng)的可變分區(qū)方式。作業(yè)調(diào)度采用SJF和進(jìn)程調(diào)度采用FCFS作業(yè)名進(jìn)入磁盤需要服務(wù)主存量裝入主存開始執(zhí)行結(jié)束執(zhí)行周轉(zhuǎn)帶權(quán)周轉(zhuǎn) 時(shí)間 時(shí)間要求時(shí)間時(shí)間時(shí)間時(shí)間時(shí)間

A 10:0642分 15KB 10:18 30分 60KC 10:30 24分 50KD 10:36 24分 10KE 10:42 12分 20K執(zhí)行順序:A->B->D->E->C周轉(zhuǎn)時(shí)間=結(jié)束執(zhí)行時(shí)間-進(jìn)入磁盤時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間高響應(yīng)比=(等待時(shí)間+服務(wù)時(shí)間)/服務(wù)時(shí)間或=等待時(shí)間/服務(wù)時(shí)間10:0610:0610:4842110:1810:3610:4811:1860211:1811:1811:1811:42662.7511:5412:181084.511:4211:54726短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F平均值:69.63.25芥輛憎聳缺濺舟柄捂硫陜持耳核彭尺車便拇誠揮梗嘛亢入句苛訖沈耳識造第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)31SJ(P)F調(diào)度算法也存在不容忽視的缺點(diǎn):(1)該算法對長作業(yè)不利,如作業(yè)C的周轉(zhuǎn)時(shí)間由10增至16,其帶權(quán)周轉(zhuǎn)時(shí)間由2增至3.2。更嚴(yán)重的是,如果有一長作業(yè)(進(jìn)程)進(jìn)入系統(tǒng)的后備隊(duì)列(就緒隊(duì)列),由于調(diào)度程序總是優(yōu)先調(diào)度那些(即使是后進(jìn)來的)短作業(yè)(進(jìn)程),將導(dǎo)致長作業(yè)(進(jìn)程)長期不被調(diào)度。

(2)該算法完全未考慮作業(yè)的緊迫程度,因而不能保證緊迫性作業(yè)(進(jìn)程)會被及時(shí)處理。

(3)由于作業(yè)(進(jìn)程)的長短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的,而用戶又可能會有意或無意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間,致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。赤宙強(qiáng)琳甥簽處淳訖焰旅烘勝廁悲笑仁株疫思倦呈翁易勿酷臘姐藍(lán)蒼宏南第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)323.2.1先來先服務(wù)和短作業(yè)優(yōu)先算法3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.2.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法3.2調(diào)度算法狄籮蠢劉揮窟活殖吠映葦仕掣據(jù)黔柏蛔擠妝萌肯框廂雷后倦涌汀堯球朱及第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)333.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法1.優(yōu)先權(quán)調(diào)度算法的類型(1)非搶占式優(yōu)先權(quán)算法系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后,該進(jìn)程便一直執(zhí)行下去,直至完成;或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時(shí),系統(tǒng)方可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。主要用于批處理系統(tǒng)中,也可用于某些對實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中。碾夸佩羹資泄碗是殃夸味鐵呀軍勤侖范盡尖慚誓锨耐憨靜北鐳闌成葉徑瑯第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)34 (2)搶占式優(yōu)先權(quán)調(diào)度算法系統(tǒng)同樣是把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程,使之執(zhí)行。但在其執(zhí)行期間,只要又出現(xiàn)了另一個(gè)其優(yōu)先權(quán)更高的進(jìn)程,進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程(原優(yōu)先權(quán)最高的進(jìn)程)的執(zhí)行,重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。在采用這種調(diào)度算法時(shí),每當(dāng)系統(tǒng)中出現(xiàn)一個(gè)新的就緒進(jìn)程i時(shí),就將其優(yōu)先權(quán)Pi與正在執(zhí)行的進(jìn)程j的優(yōu)先權(quán)Pj進(jìn)行比較。如果Pi≤Pj,原進(jìn)程Pj便繼續(xù)執(zhí)行;但如果是Pi＞Pj,則立即停止Pj的執(zhí)行,做進(jìn)程切換,使i進(jìn)程投入執(zhí)行。搶占式的優(yōu)先權(quán)調(diào)度算法,能更好地滿足緊迫作業(yè)的要求,故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中,以及對性能要求較高的批處理和分時(shí)系統(tǒng)中。按慚賃喘腕蹦良撩被繞腔焚效澤揚(yáng)鄧智讕犁殊初亂疲譯淄琺取袖疤堂投減第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)352.優(yōu)先權(quán)的類型1)靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的,且在進(jìn)程的整個(gè)運(yùn)行期間保持不變。一般地,優(yōu)先權(quán)是利用某一范圍內(nèi)的一個(gè)整數(shù)來表示的,例如,0~7或0~255中的某一整數(shù),又把該整數(shù)稱為優(yōu)先數(shù)。只是具體用法各異:有的系統(tǒng)用“0”表示最高優(yōu)先權(quán),當(dāng)數(shù)值愈大時(shí),其優(yōu)先權(quán)愈低;而有的系統(tǒng)恰恰相反。拓愧蠅旨慎堅(jiān)艷標(biāo)脯涌騷邀柔基奔竹竊宣瑞則捧籮爽用厲囤近哼退來眩沽第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)36確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下三個(gè)方面: (1)進(jìn)程類型系統(tǒng)進(jìn)程優(yōu)先級高于用戶進(jìn)程

(2)進(jìn)程對資源的需求執(zhí)行時(shí)間短,內(nèi)存要求小的進(jìn)程,有較高優(yōu)先權(quán)。

(3)用戶要求根據(jù)用戶進(jìn)程緊迫程度及用戶所付費(fèi)用的多少來確定。靜態(tài)優(yōu)先權(quán)特點(diǎn):(1)系統(tǒng)簡單易行。(2)系統(tǒng)開銷小。(3)不夠精確。(4)一般用在要求不高的系統(tǒng)中。痔郴舀堵涪湘券何哮默盜內(nèi)畫赴菱毖詩投辟睦塢烤芬藏輻麗默崗瘴揍搖找第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)372)動(dòng)態(tài)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán),是可以隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變的,以便獲得更好的調(diào)度性能。例如,我們可以規(guī)定,在就緒隊(duì)列中的進(jìn)程,隨其等待時(shí)間的增長,其優(yōu)先權(quán)以速率a提高。若所有的進(jìn)程都具有相同的優(yōu)先權(quán)初值,則顯然是最先進(jìn)入就緒隊(duì)列的進(jìn)程,將因其動(dòng)態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲得處理機(jī),此即先來先服務(wù)FCFS算法。若所有的就緒進(jìn)程具有各不相同的優(yōu)先權(quán)初值,那么,對于優(yōu)先權(quán)初值低的進(jìn)程,在等待了足夠的時(shí)間后,其優(yōu)先權(quán)便可能升為最高,從而可以獲得處理機(jī)當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時(shí),如果再規(guī)定當(dāng)前進(jìn)程的優(yōu)先權(quán)以速率b下降,則可防止一個(gè)長作業(yè)長期地壟斷處理機(jī)。墜誠昆魯啦糾殖籬恥孜畫壩袁揮汝絡(luò)因僅琳董碌鎂腕淑駁啥比柜河墻西擒第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)383.高響應(yīng)比優(yōu)先調(diào)度算法(HRF)該算法是FCFS和SJF的結(jié)合,克服了兩種算法的缺點(diǎn)響應(yīng)比最高的作業(yè)優(yōu)先啟動(dòng)由于等待時(shí)間與服務(wù)時(shí)間之和,就是系統(tǒng)對該作業(yè)的響應(yīng)時(shí)間,故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此,又可表示為謄簍已佳嗎報(bào)舍希掠悶搗趟賞腎醉菊紳痊樂釉蠅尾刊缸橢遜斂猛浴僚憂刨第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)39作業(yè)名進(jìn)入磁盤時(shí)間需要服務(wù)時(shí)間響應(yīng)比1響應(yīng)比2A 8:5090分

B 9:00 24分

C 9:30 60分

高響應(yīng)比1=等待時(shí)間/服務(wù)時(shí)間高響應(yīng)比2=(等待時(shí)間+服務(wù)時(shí)間)/服務(wù)時(shí)間40/90=4/9高響應(yīng)比優(yōu)先調(diào)度算法(40+90)/90=4/9+130/24=5/4(30+24)/24=5/4+10/60=0(0+60)/60=1設(shè)9:30進(jìn)行調(diào)度:作業(yè)名進(jìn)入磁盤時(shí)間需要服務(wù)時(shí)間響應(yīng)比1響應(yīng)比2A 8:5090分

C 9:30 60分 64/90=32/45(64+90)/90=32/45+124/60=2/5(24+60)/60=2/5+1當(dāng)B執(zhí)行完后,又要在9:54進(jìn)行調(diào)度:√√夢嶺赤若束模掠參害肚艾此經(jīng)蓋滴飾前縮倘忙柱切頌澳拯錯(cuò)弓鍬峻龍?zhí)攤サ?章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)40對高響應(yīng)比優(yōu)先調(diào)度算法(HRF)的解釋

(1)如果作業(yè)的等待時(shí)間相同,則要求服務(wù)的時(shí)間愈短,其優(yōu)先權(quán)愈高,因而該算法有利于短作業(yè)。

(2)當(dāng)要求服務(wù)的時(shí)間相同時(shí),作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間,等待時(shí)間愈長,其優(yōu)先權(quán)愈高,因而它實(shí)現(xiàn)的是先來先服務(wù)。

(3)對于長作業(yè),作業(yè)的優(yōu)先級可以隨等待時(shí)間的增加而提高,當(dāng)其等待時(shí)間足夠長時(shí),其優(yōu)先級便可升到很高,從而也可獲得處理機(jī)。高響應(yīng)比1=等待時(shí)間/服務(wù)時(shí)間孩兩馴務(wù)偏哩炮熙碉茂抉顧橇配籽情非慣扳盆負(fù)弓誦戌褂熊騰腥錫滔搔遙第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)413.2.1先來先服務(wù)和短作業(yè)優(yōu)先算法3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.2.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法3.2調(diào)度算法泥迎開疑諱蜘全惟抨檬帖倉阮預(yù)駐串賴取揉凱逝燼抒修杠竹迫莢壤惱鳳鹿第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)423.2.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法1.時(shí)間片輪轉(zhuǎn)法在早期的時(shí)間片輪轉(zhuǎn)法中,系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則,排成一個(gè)隊(duì)列,每次調(diào)度時(shí),把CPU分配給隊(duì)首進(jìn)程,并令其執(zhí)行一個(gè)時(shí)間片,時(shí)間片的大小從幾ms到幾百ms當(dāng)執(zhí)行的時(shí)間片用完時(shí),由一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷請求,調(diào)度程序便據(jù)此信號來停止該進(jìn)程的執(zhí)行,并將它送往就緒隊(duì)列的末尾;然后,再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程,同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片可以保證就緒隊(duì)列中的所有進(jìn)程,在一給定的時(shí)間內(nèi),均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間軟伺拈民懶峽掃怎案辛澈屈鴛亢額疹炸筐叭端氮煉升沼累霹矮防逛蒙康特第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)43內(nèi)存無限大。作業(yè)調(diào)度采用FCFS和進(jìn)程調(diào)度采用時(shí)間片的輪轉(zhuǎn)q=1作業(yè)進(jìn)入需要裝入開始執(zhí)行執(zhí)行開始執(zhí)行執(zhí)行開始執(zhí)行執(zhí)行開始執(zhí)行執(zhí)行完成周轉(zhuǎn)帶權(quán)名 磁盤服務(wù)主存執(zhí)行時(shí)間后執(zhí)行時(shí)間后執(zhí)行時(shí)間后執(zhí)行時(shí)間后周轉(zhuǎn)A04 B13 C24 D32 E44 完成順序:D->B->A->C->E周轉(zhuǎn)時(shí)間=結(jié)束執(zhí)行時(shí)間-進(jìn)入磁盤時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間高響應(yīng)比=(等待時(shí)間+服務(wù)時(shí)間)/服務(wù)時(shí)間或=等待時(shí)間/服務(wù)時(shí)間001131124312141時(shí)間片的輪轉(zhuǎn)平均值:11.83.431243556879111116798101011121311111112131414151611115161796312113.6715153.7517133.2516143.5潘為碧幅務(wù)爾雪軒餒琶柬呸洋梭輾葉焚諸釘杰悍朗琶喇淳星咳彥袁喊暇紫第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)44內(nèi)存無限大。作業(yè)調(diào)度采用FCFS和進(jìn)程調(diào)度采用時(shí)間片的輪轉(zhuǎn)q=4作業(yè)進(jìn)入需要裝入開始執(zhí)行執(zhí)行開始執(zhí)行執(zhí)行開始執(zhí)行執(zhí)行開始執(zhí)行執(zhí)行完成周轉(zhuǎn)帶權(quán)名 磁盤服務(wù)主存執(zhí)行時(shí)間后執(zhí)行時(shí)間后執(zhí)行時(shí)間后執(zhí)行時(shí)間后周轉(zhuǎn)A04 B13 C24 D32 E44 完成順序:A->B->C->D->E周轉(zhuǎn)時(shí)間=結(jié)束執(zhí)行時(shí)間-進(jìn)入磁盤時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間高響應(yīng)比=(等待時(shí)間+服務(wù)時(shí)間)/服務(wù)時(shí)間或=等待時(shí)間/服務(wù)時(shí)間00413432411274134時(shí)間片的輪轉(zhuǎn)平均值:8.42.7471311171310576244117133.251192.25昨隙迭翁乎川開賜略誣撈宴味咋喜淫輥綸遣愛怕斷奸屆瓣潭坡囪常邁便帥第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)45圖3-5多級反饋隊(duì)列調(diào)度算法2.多級反饋隊(duì)列調(diào)度算法優(yōu)先級高歷吭帥迂趁俘辛進(jìn)雕乙箕許豫冉珍纏狂銹悄蚜望演猿聶吭謊頸記底奢倫膳第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)46設(shè)置多個(gè)就緒隊(duì)列,并為各個(gè)隊(duì)列賦予不同的優(yōu)先級第一個(gè)隊(duì)列的優(yōu)先級最高,第二個(gè)隊(duì)列次之,其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低。該算法賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不相同,在優(yōu)先權(quán)愈高的隊(duì)列中,為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就愈小。例如,第二個(gè)隊(duì)列的時(shí)間片要比第一個(gè)隊(duì)列的時(shí)間片長一倍,……,第i+1個(gè)隊(duì)列的時(shí)間片要比第i個(gè)隊(duì)列的時(shí)間片長一倍。調(diào)度方式當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后,首先將它放入第一隊(duì)列的末尾,按FCFS原則排隊(duì)等待調(diào)度當(dāng)輪到該進(jìn)程執(zhí)行時(shí),如它能在該時(shí)間片內(nèi)完成,便可準(zhǔn)備撤離系統(tǒng);如果它在一個(gè)時(shí)間片結(jié)束時(shí)尚未完成,調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊(duì)列的末尾,再同樣地按FCFS原則等待調(diào)度執(zhí)行;如果它在第二隊(duì)列中運(yùn)行一個(gè)時(shí)間片后仍未完成,再依次將它放入第三隊(duì)列,……,如此下去,當(dāng)一個(gè)長作業(yè)(進(jìn)程)從第一隊(duì)列依次降到第n隊(duì)列后,在第n隊(duì)列中便采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行。還軀跑借把暇蛋魚配鄖澇頻徘啤統(tǒng)影繼竭日劇吩滅傀狐所存識晝嗣闊沉邦第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)47僅當(dāng)?shù)谝魂?duì)列空閑時(shí),調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行;僅當(dāng)?shù)?~(i-1)隊(duì)列均空時(shí),才會調(diào)度第i隊(duì)列中的進(jìn)程運(yùn)行。如果處理機(jī)正在第i隊(duì)列中為某進(jìn)程服務(wù)時(shí),又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊(duì)列(第1~(i-1)中的任何一個(gè)隊(duì)列),則此時(shí)新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī),即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第i隊(duì)列的末尾,把處理機(jī)分配給新到的高優(yōu)先權(quán)進(jìn)程。邵縱蟹除頸蛤插顏敦繭鈔末覓錐搗署泥歌自端循疚藹塌篷治倍拖傣返厚熏第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)483.多級反饋隊(duì)列調(diào)度算法的性能(1)終端型作業(yè)用戶終端型作業(yè)用戶所提交的作業(yè)多屬于交互型作業(yè),通常較小,系統(tǒng)只要能使這些作業(yè)在第一隊(duì)列所規(guī)定的時(shí)間片內(nèi)完成即可(2)短批處理作業(yè)用戶若在第1隊(duì)列中執(zhí)行一個(gè)時(shí)間片即可完成,便可獲得與終端型作業(yè)一樣的響應(yīng)時(shí)間如在第一個(gè)隊(duì)列中不能完成,只需在第2、3隊(duì)列中各執(zhí)行一個(gè)時(shí)間片(3)長批處理作業(yè)用戶長作業(yè)將依次在第1,2,3…,n隊(duì)列中執(zhí)行,最終按輪轉(zhuǎn)方式運(yùn)行穆灸魔浦硫怔危財(cái)寓思徊屑珍嫂盔俘桓綜途鐐慌帛魂桐央擠隊(duì)芽紐嶺鐐沸第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)49內(nèi)容概述3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時(shí)調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除他恃鼻守塹棒顛愛籽官鰓戌擂瘁逸表岡每檔鄙靛戍批敷布象關(guān)渝吊撐畸跳第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)503.3實(shí)時(shí)調(diào)度3.3.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件3.3.2實(shí)時(shí)調(diào)度算法的分類3.3.3常用的幾種實(shí)時(shí)調(diào)度算法凡素糞瓣捻賣惑柑路勺尋芹淑返崔當(dāng)板溫嘿棠孩廄疊糧塑豫疆嘗千丈渺蜀第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)513.3.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件1.提供必要的信息(1)就緒時(shí)間 該任務(wù)成為就緒狀態(tài)的起始時(shí)間。(2)開始截止時(shí)間和完成截止時(shí)間(3)處理時(shí)間 指一個(gè)任務(wù)從開始執(zhí)行直至完成所需要的時(shí)間。(4)資源要求 執(zhí)行時(shí)所需資源。(5)優(yōu)先級 重大任務(wù),賦予“絕對”優(yōu)先級,無重大影響,可賦予“相對”優(yōu)先級。始又瘩蛤鷗鹼媳棉踐盼桐羊社緯屎油狙惋打殿隸抹迅溉嗆叢翰底隆悅場飯第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)522.系統(tǒng)處理能力強(qiáng)

在實(shí)時(shí)系統(tǒng)中,通常都有著多個(gè)實(shí)時(shí)任務(wù)。若處理機(jī)的處理能力不夠強(qiáng),則有可能因處理機(jī)忙不過來而使某些實(shí)時(shí)任務(wù)不能得到及時(shí)處理,從而導(dǎo)致發(fā)生難以預(yù)料的后果。假定系統(tǒng)中有m個(gè)周期性的硬實(shí)時(shí)任務(wù),它們的處理時(shí)間可表示為Ci,周期時(shí)間表示為Pi,則在單處理機(jī)情況下,必須滿足下面的限制條件,系統(tǒng)才是可調(diào)度的。撅沒賃潘秀側(cè)晴逼帕繞獨(dú)釩刊揩珠腿腋獺硒著瓦橢鄧扳盅宴快常刪蛹喝盲第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)53

假如系統(tǒng)中有6個(gè)硬實(shí)時(shí)任務(wù),它們的周期時(shí)間都是50ms,而每次的處理時(shí)間為10ms,則不難算出,此時(shí)是不能滿足上式的,因而系統(tǒng)是 的。解決的方法是提高系統(tǒng)的處理能力,其途徑有二:其一仍是采用單處理機(jī)系統(tǒng),但須增強(qiáng)其處理能力,以顯著地減少對每一個(gè)任務(wù)的處理時(shí)間;其二是采用多處理機(jī)系統(tǒng)。假定系統(tǒng)中的處理機(jī)數(shù)為N,則應(yīng)將上述的限制條件改為:不可調(diào)度舟芽堡少踞市擒兵碘瞪拯飽奪舅貶示躲切柔戍傭庫蒂痢畸抵戶楚頃讀時(shí)漆第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)543.采用搶占式調(diào)度機(jī)制

當(dāng)一個(gè)優(yōu)先權(quán)更高的任務(wù)到達(dá)時(shí),允許將當(dāng)前任務(wù)暫時(shí)掛起,而令高優(yōu)先權(quán)任務(wù)立即投入運(yùn)行,這樣便可滿足該硬實(shí)時(shí)任務(wù)對截止時(shí)間的要求。但這種調(diào)度機(jī)制比較復(fù)雜。對于一些小的實(shí)時(shí)系統(tǒng),如果能預(yù)知任務(wù)的開始截止時(shí)間,則對實(shí)時(shí)任務(wù)的調(diào)度可采用非搶占調(diào)度機(jī)制,以簡化調(diào)度程序和對任務(wù)調(diào)度時(shí)所花費(fèi)的系統(tǒng)開銷。但在設(shè)計(jì)這種調(diào)度機(jī)制時(shí),應(yīng)使所有的實(shí)時(shí)任務(wù)都比較小,并在執(zhí)行完關(guān)鍵性程序和臨界區(qū)后,能及時(shí)地將自己阻塞起來,以便釋放出處理機(jī),供調(diào)度程序去調(diào)度那種開始截止時(shí)間即將到達(dá)的任務(wù)。繃緊幣繼貝陪搶哉好閥農(nóng)豹榮燥木諱殊遂涸宙樞膿吶攔于臣淄跌級皇韌皺第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)554.具有快速切換機(jī)制

該機(jī)制應(yīng)具有如下兩方面的能力:(1)對外部中斷的快速響應(yīng)能力。為使在緊迫的外部事件請求中斷時(shí)系統(tǒng)能及時(shí)響應(yīng),要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu),還應(yīng)使禁止中斷的時(shí)間間隔盡量短,以免耽誤時(shí)機(jī)(其它緊迫任務(wù))。

(2)快速的任務(wù)分派能力。在完成任務(wù)調(diào)度后,便應(yīng)進(jìn)行任務(wù)切換。為了提高分派程序進(jìn)行任務(wù)切換時(shí)的速度,應(yīng)使系統(tǒng)中的每個(gè)運(yùn)行功能單位適當(dāng)?shù)男?以減少任務(wù)切換的時(shí)間開銷。疹蟬濕匯郎禮汽塹份矚庚攤沛盲閡幢晚碘叫乳寂誘臣坷師裹磨涅歹決裙餾第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)563.3實(shí)時(shí)調(diào)度3.3.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件3.3.2實(shí)時(shí)調(diào)度算法的分類3.3.3常用的幾種實(shí)時(shí)調(diào)度算法擠墊畜俞輩瓊朝補(bǔ)警康化樞淮巧垛鼎幀吼盾拈墩湛騾漾血撲喲鉗翹鄰凰帕第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)573.3.2實(shí)時(shí)調(diào)度算法的分類根據(jù)實(shí)時(shí)任務(wù)性質(zhì)的不同,可將實(shí)時(shí)調(diào)度算法分為:(1)硬實(shí)時(shí)調(diào)度算法(2)軟實(shí)時(shí)調(diào)度算法按調(diào)度方式的不同,可將實(shí)時(shí)調(diào)度算法分為:(1)非搶占調(diào)度算法(2)搶占調(diào)度算法因調(diào)度程序調(diào)度時(shí)間的不同,可將實(shí)時(shí)調(diào)度算法分為:(1)靜態(tài)調(diào)度算法(2)動(dòng)態(tài)調(diào)度算法在多處理機(jī)環(huán)境下,可將實(shí)時(shí)調(diào)度算法分為:(1)集中式調(diào)度算法(2)分布式調(diào)度算法耙藥遠(yuǎn)翠哨卞咐綱據(jù)去靛剁廓衡扶緬柏鑒諺辟纂瀉扼輾癸狠鹽訃驚遂智佩第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)581.非搶占式調(diào)度算法(1)非搶占式輪轉(zhuǎn)調(diào)度算法常用于工業(yè)生產(chǎn)的群控系統(tǒng)中調(diào)度程序每次選擇隊(duì)列中的第一個(gè)任務(wù)運(yùn)行一個(gè)任務(wù)運(yùn)行后排在輪轉(zhuǎn)隊(duì)列的末尾,等待下次調(diào)度可用于要求不太嚴(yán)格的實(shí)時(shí)控制系統(tǒng)中可獲得僅數(shù)秒至數(shù)十秒的響應(yīng)時(shí)間按調(diào)度方式的不同,可將實(shí)時(shí)調(diào)度算法分為:圖3-6實(shí)時(shí)進(jìn)程調(diào)度純謄盎鎢恰步增怯叮侶署佑浚擎撤韶緝叼督耕廁憋劉克沫滲直埠漣湖耍穆第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)591.非搶占式調(diào)度算法(1)…(2)非搶占式優(yōu)先調(diào)度算法為時(shí)間要求嚴(yán)格的任務(wù)分配較高優(yōu)先級當(dāng)優(yōu)先權(quán)高的實(shí)時(shí)任務(wù)到來時(shí),排在就緒隊(duì)列的隊(duì)首等待調(diào)度有可能獲得僅數(shù)秒至數(shù)百毫秒級的響應(yīng)時(shí)間圖3-6實(shí)時(shí)進(jìn)程調(diào)度就邦捂抉形箕嘯次森根蠕森膀俐捕亥碘名釉歲侮賜纓門查街兄屋羊恤矯兇第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)602.搶占式調(diào)度算法(根據(jù)搶占發(fā)生時(shí)間的不同)(1)基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法某實(shí)時(shí)任務(wù)到達(dá)后,若優(yōu)先級高于當(dāng)前正在執(zhí)行任務(wù)的優(yōu)先級,并不立即搶占當(dāng)前任務(wù)的處理機(jī),而是等到時(shí)鐘中斷到來后調(diào)度程序才剝奪當(dāng)前任務(wù)的執(zhí)行(幾十至幾毫秒)圖3-6實(shí)時(shí)進(jìn)程調(diào)度阜耀飄仟潦諷鉗郭竣棧逾怪疹搐晚縷籽狠該緒犯得盔冊閏鎂裂艘綴舵痹聚第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)612.搶占式調(diào)度算法(根據(jù)搶占發(fā)生時(shí)間的不同)(1)…(2)立即搶占(ImmediatePreemption)的優(yōu)先權(quán)調(diào)度算法一旦有外部中斷,只要當(dāng)前任務(wù)不在臨界區(qū)內(nèi),便立即剝奪當(dāng)前任務(wù)的執(zhí)行,交處理機(jī)分配給要求中斷的緊迫任務(wù)(幾至0.1毫秒…)圖3-6實(shí)時(shí)進(jìn)程調(diào)度祖靴淤停發(fā)竄企貳問荔籍炙益慎輔榆友口嘗息堤慈捆脂瘡重低揀信釩豬蝎第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)623.3實(shí)時(shí)調(diào)度3.3.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件3.3.2實(shí)時(shí)調(diào)度算法的分類3.3.3常用的幾種實(shí)時(shí)調(diào)度算法低亭彌澡勢務(wù)霸彪我嘯唇蒙贛香雄簿傘基檻捎勾真淌謝狡可伴鉆準(zhǔn)邀銑眨第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)633.3.3常用的幾種實(shí)時(shí)調(diào)度算法圖3-7EDF算法用于非搶占調(diào)度方式1.最早截止時(shí)間優(yōu)先EDF(EarliestDeadlineFirst)算法根據(jù)任務(wù)的開始截止時(shí)間來確定任務(wù)的優(yōu)先級,截止時(shí)間越早優(yōu)先級越高既可用于搶占式調(diào)度也可用于非搶占式調(diào)度方式絞涪憨嗎雍婿捐涕萄救管簡疤幀赤韋忽籃鬼案趙沛吱碌鉛購巖銹德半堤蔚第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)642.最低松弛度優(yōu)先即LLF(LeastLaxityFirst)算法根據(jù)任務(wù)緊急(或松弛)的程度,來確定任務(wù)的優(yōu)先級。任務(wù)的緊急程度愈高,為該任務(wù)所賦予的優(yōu)先級就愈高,以使之優(yōu)先執(zhí)行例如,一個(gè)任務(wù)在200ms時(shí)必須完成,而它本身所需的運(yùn)行時(shí)間就有80ms,因此,調(diào)度程序必須在120ms之前調(diào)度執(zhí)行,該任務(wù)的緊急程度(松弛程度)為120ms在實(shí)現(xiàn)該算法時(shí)要求系統(tǒng)中有一個(gè)按松弛度排序的實(shí)時(shí)任務(wù)就緒隊(duì)列,松弛度最低的任務(wù)排在隊(duì)列最前面,調(diào)度程序總是選擇就緒隊(duì)列中的隊(duì)首任務(wù)執(zhí)行該算法主要用于可搶占調(diào)度方式中蔫仕舅捧矛綿持峪足坤廖告淬刁卸賜峽勾立爺牧箱爆戎摟夏變息器捷殲徹第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)65

假如在一個(gè)實(shí)時(shí)系統(tǒng)中,有兩個(gè)周期性實(shí)時(shí)任務(wù)A和B,任務(wù)A要求每20ms執(zhí)行一次,執(zhí)行時(shí)間為10ms;任務(wù)B只要求每50ms執(zhí)行一次,執(zhí)行時(shí)間為25ms處理能力需求:注娛結(jié)凝庸抹滔她叢梨羚括糯恃實(shí)瘍閡撻癸硅旗秒搞雞該砰孤懈慶宮餅監(jiān)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)66在剛開始時(shí)(t1=0),A1必須在20ms時(shí)完成,而它本身運(yùn)行又需10ms,可算出A1的松弛度為10ms;B1必須在50ms時(shí)完成,而它本身運(yùn)行就需25ms,可算出B1的松弛度為25ms,故調(diào)度程序應(yīng)先調(diào)度A1執(zhí)行。在t2=10ms時(shí),A2的松弛度可按下式算出: A2的松弛度=必須完成時(shí)間-其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間

=40ms-10ms-10ms=20ms B1的松弛度=必須完成時(shí)間-其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間

=50ms-25ms-10ms=15ms圖3-8A和B任務(wù)每次必須完成的時(shí)間賃馴相禿嫁盾很繹迂患甩弱掏浪全妥渺菊迎輝曬侖凡做張故耍懊擯戮夯食第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)67

故調(diào)度程序應(yīng)選擇B1運(yùn)行。在t3=30ms時(shí),A2的松弛度已減為0(即40-10-30),而B1的松弛度為15ms(即50-5-30),于是調(diào)度程序應(yīng)搶占B1的處理機(jī)而調(diào)度A2運(yùn)行。在t4=40ms時(shí),A3的松弛度為10ms(即60-10-40),而B1的松弛度僅為5ms(即50-5-40),故又應(yīng)重新調(diào)度B1執(zhí)行。在t5=45ms時(shí),B1執(zhí)行完成,而此時(shí)A3的松弛度已減為5ms(即60-10-45),而B2的松弛度為30ms(即100-25-45),于是又應(yīng)調(diào)度A3執(zhí)行。在t6=55ms時(shí),任務(wù)A尚未進(jìn)入第4周期,而任務(wù)B已進(jìn)入第2周期,故再調(diào)度B2執(zhí)行。在t7=70ms時(shí),A4的松弛度已減至0ms(即80-10-70),而B2的松弛度為20ms(即100-10-70),故此時(shí)調(diào)度又應(yīng)搶占B2的處理機(jī)而調(diào)度A4執(zhí)行。t2=10ms肇堤瘓?bào)E肩是齲桃盟牡踴猶旋您庶渙歉壽毖粟鐐碟矩微根須嗡駕銻始小沉第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)68圖3-9利用ELLF算法進(jìn)行調(diào)度的情況戮新粳名析锨而吹趕灣迪錢閘用遺猩儈氓吻施埋癟術(shù)藐剖辰郝符襪纜宮襯第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)69內(nèi)容概述3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時(shí)調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除沉甭力領(lǐng)艷患洛隴墨仙夾叮怯緝敖依屋慰噎窖墜綸初摸該勛潔操貳昔吐性第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)703.4多處理機(jī)系統(tǒng)中的調(diào)度3.4.1多處理機(jī)系統(tǒng)的類型3.4.2進(jìn)程分配方式3.4.3進(jìn)程(線程)調(diào)度方式銷蓬之賭魏隸敝這部榆媽專前凋咎憲瞞協(xié)具寶匪濺耿期缽亞擄常炙軌熬敖第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)713.4.1多處理器系統(tǒng)的類型(1)緊密耦合(TightlyCoupled)MPS(MultiProcessorSystem)通常是通過高速總線或高速交叉開關(guān),來實(shí)現(xiàn)多個(gè)處理器之間的互連共享主存儲器系統(tǒng)和I/O設(shè)備,并要求將主存儲器劃分為若干個(gè)能獨(dú)立訪問的存儲器模塊,以便多個(gè)處理機(jī)能同時(shí)對主存進(jìn)行訪問。系統(tǒng)中的所有資源和進(jìn)程,都由操作系統(tǒng)實(shí)施統(tǒng)一的控制和管理(2)松散耦合(LooselyCoupled)MPS在松散耦合MPS中,通常是通過通道或通信線路,來實(shí)現(xiàn)多臺計(jì)算機(jī)之間的互連每臺計(jì)算機(jī)都有自己的存儲器和I/O設(shè)備,并配置了OS來管理本地資源和在本地運(yùn)行的進(jìn)程。因此,每一臺計(jì)算機(jī)都能獨(dú)立地工作,必要時(shí)可通過通信線路與其它計(jì)算機(jī)交換信息,以及協(xié)調(diào)它們之間的工作1.根據(jù)多處理器之間耦合的緊密程度分為:秒乾晚寂活痢勵(lì)閻扔薪饒督央拂戀摻瀝鞘遼曳退崔艇娶冗柑你雙苫基汕支第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)722.根據(jù)系統(tǒng)中所用處理器的相同與否,可將MPS分為如下兩類(1)對稱多處理器系統(tǒng)SMPS(SymmetricMultiProcessorSystem)在系統(tǒng)中所包含的各處理器單元,在功能和結(jié)構(gòu)上都是相同的,當(dāng)前的絕大多數(shù)MPS都屬于SMP系統(tǒng)例如,IBM公司的SR/6000ModelF50,便是利用4片PowerPC處理器構(gòu)成的。(2)非對稱多處理器系統(tǒng)在系統(tǒng)中有多種類型的處理單元,它們的功能和結(jié)構(gòu)各不相同,其中只有一個(gè)主處理器,有多個(gè)從處理器握潑廄當(dāng)手票盒崎釩艱柏挎咎邪恩攘氓穎母食牛囂緞椰萄甕巢脖奉棒軀拌第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)733.4多處理機(jī)系統(tǒng)中的調(diào)度3.4.1多處理機(jī)系統(tǒng)的類型3.4.2進(jìn)程分配方式3.4.3進(jìn)程(線程)調(diào)度方式執(zhí)蝕繞葫默過鮮邱柔螺董壕揍鄒歸侵挨柱艷木侯貯枝垮汞禍哪蕊置鉻恐體第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)743.4.2進(jìn)程分配方式1.對稱多處理器系統(tǒng)中的進(jìn)程分配方式在SMP系統(tǒng)中,所有的處理器都是相同的,因而可把所有的處理器作為一個(gè)處理器池(Processorpool),由調(diào)度程序或基于處理器的請求,將任何一個(gè)進(jìn)程分配給池中的任何一個(gè)處理器去處理在進(jìn)行進(jìn)程分配時(shí),可采用以下兩種:(1)靜態(tài)分配(StaticAssigenment)方式一個(gè)進(jìn)程從一開始執(zhí)行到完成都被固定地分配到一個(gè)處理器上去執(zhí)行。必須為每個(gè)處理器單獨(dú)安排一個(gè)就緒隊(duì)列。優(yōu)點(diǎn):進(jìn)程調(diào)度的開銷小缺點(diǎn):會使各處理器的忙閑不均霓卒蘿苞樊靠痘進(jìn)焦哩冕曹鐮資淪葬捶兩馳黑道兔墜肅昂騙帝癸橇祭稍米第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)75(2)動(dòng)態(tài)分配(DynamicAssgement)方式在系統(tǒng)中設(shè)置公共就緒隊(duì)列,分配時(shí)可將進(jìn)程分配到任一個(gè)處理器上。消除了各處理器忙閑不均的現(xiàn)象,但對于松耦合系統(tǒng),在一個(gè)處理器A上的進(jìn)程轉(zhuǎn)至B上運(yùn)行時(shí),必須將A處理器所保存的信息傳給B優(yōu)點(diǎn):消除了各個(gè)處理器忙閑不均的現(xiàn)象光個(gè)靴唁幫寨軸砂戮虜標(biāo)葡擺替鑒重詢導(dǎo)茶腰里到拴遇攤依塵潘點(diǎn)緣姜困第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)762.非對稱MPS中的進(jìn)程分配方式對于非對稱MPS,其OS大多采用主—從(Master-Slave)式OS,即OS的核心部分駐留在一臺主機(jī)上(Master),而從機(jī)(Slave)上只是用戶程序,進(jìn)程調(diào)度只由主機(jī)執(zhí)行每當(dāng)從機(jī)空閑時(shí),便向主機(jī)發(fā)送一索求進(jìn)程的信號,然后,便等待主機(jī)為它分配進(jìn)程在主機(jī)中保持有一個(gè)就緒隊(duì)列,只要就緒隊(duì)列不空,主機(jī)便從其隊(duì)首摘下一進(jìn)程分配給請求的從機(jī)從機(jī)接收到分配的進(jìn)程后便運(yùn)行該進(jìn)程,該進(jìn)程結(jié)束后從機(jī)又向主機(jī)發(fā)出請求優(yōu)點(diǎn):系統(tǒng)處理比較簡單缺點(diǎn):有“瓶頸”(主機(jī))伊檢評斥孿未篩婿挽碑曹囊舌得役刪困亮唯灸脖屹啪絮譽(yù)糜埠胺殃敷蜂佯第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)773.4多處理機(jī)系統(tǒng)中的調(diào)度3.4.1多處理機(jī)系統(tǒng)的類型3.4.2進(jìn)程分配方式3.4.3進(jìn)程(線程)調(diào)度方式宜獻(xiàn)刑顛吝臭析準(zhǔn)腋埋氮汞渤寧醞仿艦桐歐彩翼城帆饅向謗過髓杠能寨嘻第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)783.4.3進(jìn)程(線程)調(diào)度方式1.自調(diào)度(Self-Scheduling)方式(1)自調(diào)度機(jī)制自調(diào)度方式是最簡單的一種調(diào)度方式,直接由單處理機(jī)環(huán)境下的調(diào)度方式演變而來在系統(tǒng)中設(shè)置有一個(gè)公共的進(jìn)程或線程就緒隊(duì)列,所有的處理器在空閑時(shí),都可自己到該隊(duì)列中取得一進(jìn)程(或線程)來運(yùn)行在自調(diào)度方式中,可采用在單處理機(jī)環(huán)境下所用的調(diào)度算法,如先來先服務(wù)(FCFS)調(diào)度算法、最高優(yōu)先權(quán)優(yōu)先(FPF)調(diào)度算法和搶占式最高優(yōu)先權(quán)優(yōu)先調(diào)度算法等緬畦鄂羨罰襖邦助妥筏路綽鍵陰褪勉箔仗沏熙撐蔚琢聞手用皺姆瘸臉綁渝第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)79(2)自調(diào)度方式的優(yōu)點(diǎn)系統(tǒng)中的公共就緒隊(duì)列可按照單處理機(jī)系統(tǒng)中所采用的各種方式加以組織;其調(diào)度算法也可沿用單處理機(jī)系統(tǒng)所用的算法,亦即,很容易將單處理機(jī)環(huán)境下的調(diào)度機(jī)制移植到多處理機(jī)系統(tǒng)中,故它仍然是當(dāng)前多處理機(jī)系統(tǒng)中較常用的調(diào)度方式只要系統(tǒng)中有任務(wù),或者說只要公共就緒隊(duì)列不空,就不會出現(xiàn)處理機(jī)空閑的情況,也不會發(fā)生處理器忙閑不均的現(xiàn)象,因而有利于提高處理器的利用率偶或有浚屑乍敏窺肝拱怒涂赦衙褐喲盲肅臭茂敷胚仙五邢鐘懾非批共省喂第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)80(3)自調(diào)度方式的缺點(diǎn)瓶頸問題 整個(gè)系統(tǒng)中只設(shè)一個(gè)就緒隊(duì)列,各處理器必須互斥的訪問低效性 當(dāng)線程阻塞后重新就緒時(shí),只能進(jìn)入這個(gè)就緒隊(duì)列,但卻很少可能在原來的處理器上運(yùn)行,要重新拷貝運(yùn)行數(shù)據(jù)線程切換頻繁 互相合作的線程很難同時(shí)運(yùn)行梨鞘糕銥磚縱遷糯摘崎橇氰液淡山帽椿亥丫奴奢龐渦刑坤拐漫師俄蛆棋酸第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)81圖3-10兩種分配處理器時(shí)間的方法2.成組調(diào)度(GangScheduling)方式將一個(gè)進(jìn)程中的一組線程分配到一組處理器上去執(zhí)行在成組調(diào)度時(shí),如何為應(yīng)用程序分配處理器時(shí)間(1)面向所有應(yīng)用程序平均分配處理器時(shí)間(2)面向所有線程平均分配處理器時(shí)間褥平邢拒鞘碟膝傲吝挖讒太瘸櫻特碰燭怔昭腎僳注憶韓懈閩爪柔乘僳瓤軋第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)823.專用處理器分配(DedicatedProcessorAssignment)方式在一個(gè)應(yīng)用程序執(zhí)行期間,專門為該應(yīng)用程序分配一組處理器,每個(gè)線程一個(gè),這組處理器為該程序?qū)Ｓ?直至完成這種方式的主要理由如下在含有幾百或幾個(gè)處理器的系統(tǒng)中,每個(gè)處理器的投資只占很小一部分,性能的重要性要高于對單個(gè)處理器利用率的考慮每個(gè)進(jìn)程或線程專用一個(gè)處理器可以完全避免進(jìn)程或線程的切換擁佐處盔絆帳浙滾貞竿竄怎狗蟻癬悸烴崔涂卒藝硬擋文歌祟詞庸花梭扶楚第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)83圖3-11線程數(shù)對加速比的影響

系統(tǒng)一共有16個(gè)處理器,當(dāng)兩個(gè)進(jìn)程都各有8個(gè)線程時(shí),正好是每個(gè)線程能分得1臺處理器;當(dāng)超過16個(gè)線程時(shí),就不能保證每個(gè)線程有1臺處理器,因而出現(xiàn)線程切換問題。線程數(shù)愈多時(shí)切換就愈頻繁,反而會使加速比下降。淖鐵秦汾咸仍灣桅夢花轎購仇巨澀迄賣收螞餡遷鞭辛鬧架夸取剩剿宴掛粥第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)84作業(yè)設(shè)有四道作業(yè),它們的提交時(shí)間和運(yùn)行時(shí)間如下表:作業(yè)號提交時(shí)刻(時(shí))運(yùn)行時(shí)間(小時(shí))18.002.0028.500.5039.000.1049.500.20求:試給出下面兩種調(diào)度算法下,作業(yè)的執(zhí)行順序,平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間。(注意:作業(yè)調(diào)度與進(jìn)程調(diào)度均采用該調(diào)度算法,內(nèi)存無限大，作業(yè)為純計(jì)算型。要求寫出每個(gè)作業(yè)的裝入主存時(shí)間、開始執(zhí)行時(shí)間，結(jié)束執(zhí)行時(shí)間，周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間，調(diào)度時(shí)間忽略不計(jì)，保留小數(shù)點(diǎn)后兩位)(1)先來先服務(wù)FCFS調(diào)度算法。(2)短作業(yè)優(yōu)先SJF調(diào)度算法。余柴泊輕肅酶侖羚誡健宛酵篙耿證咖綽委晦墨便謗娜擎藹朗伏榨劫汕自瓦第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)85內(nèi)容概述3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時(shí)調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除蝗旦呀鑼歡鄭雅朱參榜腮贏楞嗅藹堤至嫂晃糟涉耳蚌跟娠較企甭毗虱秒沙第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)863.5產(chǎn)生死鎖的原因和必要條件3.5.1產(chǎn)生死鎖的原因3.5.2產(chǎn)生死鎖的必要條件3.5.3處理死鎖的基本方法誠參悟呢墻貴哮敵民背屋營薊萍虛革雛已益瘋肩院砂瀑爺奢退了塞吠級戊第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)87例:有兩個(gè)進(jìn)程PA和PB,它們在運(yùn)行的過程中要共享使用兩個(gè)獨(dú)占設(shè)備R1和R2。設(shè)SR1為設(shè)備R1的互斥信號量,初值為1;SR2為設(shè)備R2的互斥信號量,初值為1;兩個(gè)進(jìn)程并發(fā)執(zhí)行的程序如下:死鎖的概念:是指多個(gè)進(jìn)程因競爭資源而造成的一種僵局,若無外力的作用,這些進(jìn)程將都不能再繼續(xù)執(zhí)行。撐巷弛淑駛英哇廬鐵吝抵恥牌怎棋倆轉(zhuǎn)犯挎母孽咨僑聽膜蚊汐艘劃監(jiān)髓拂第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)883.5.1產(chǎn)生死鎖的原因(1)競爭資源引起進(jìn)程死鎖可剝奪和非剝奪性資源可剝奪性資源是指進(jìn)程在獲得這類資源后,該資源可以再被其他進(jìn)程或系統(tǒng)剝奪,如處理機(jī)、內(nèi)存等不可剝奪性資源是指當(dāng)系統(tǒng)把這類資源分配給某個(gè)進(jìn)程后,再不能強(qiáng)行收回,只能在進(jìn)程用完后自行釋放,如磁帶機(jī)、打印機(jī)等競爭非剝奪性資源系統(tǒng)中的非剝奪性資源由于數(shù)量有限而不能滿足進(jìn)程運(yùn)行的需要,進(jìn)程在運(yùn)行過程中因爭奪這些資源而限入僵局央避臉吸斂抖擒勃所墾支或賃址溜奇苔汝咯漚魂遮質(zhì)轍吵卒距驟冒鴿寡咆第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)89圖3-12I/O設(shè)備共享時(shí)的死鎖情況請求請求配分已

配分已扇乓昂特括鉤滇札探斗鴦荊瘩歡漁查孤仔鄖伸們炯凌身溝鏟窘皖斃蠟滋宿第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)90圖3-13進(jìn)程之間通信時(shí)的死鎖競爭臨時(shí)性資源臨時(shí)性資源區(qū)別于永久性資源,指由一個(gè)進(jìn)程產(chǎn)生,被另一進(jìn)程使用后就再也無用的資源,也稱為消耗性資源申請釋放申請釋放申請釋放巴珠膛簿柿紊哩橇雇總尸勵(lì)券們滋玄題狐序瘩剁虎憑奎淵昭盲遵玻墩贊獎(jiǎng)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)912.進(jìn)程推進(jìn)順序不當(dāng)引起死鎖圖3-14進(jìn)程推進(jìn)順序?qū)λ梨i的影響P1進(jìn)程進(jìn)度P2進(jìn)程進(jìn)度盆惕雄琶井鑷啞考窩憫萍綿堂躁淘障廓秒熔都胖堵魔策審嚇渡榷氦彼惕薯第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)92若并發(fā)進(jìn)程P1和P2按曲線④所示的順序推進(jìn),它們將進(jìn)入不安全區(qū)D內(nèi)。此時(shí)P1保持了資源R1,P2保持了資源R2,系統(tǒng)處于不安全狀態(tài)。因?yàn)?這時(shí)兩進(jìn)程再向前推進(jìn),便可能發(fā)生死鎖。例如,當(dāng)P1運(yùn)行到P1;Request(R2)時(shí),將因R2已被P2占用而阻塞;當(dāng)P2運(yùn)行到P2;Request(R1)時(shí),也將因R1已被P1占用而阻塞,于是發(fā)生了進(jìn)程死鎖發(fā)面載睡敬峻淡遁擠殿握浸酶耪沏臍粵緞憑桅奮柄槽超憂低娠避誦哼箔禽第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)933.5產(chǎn)生死鎖的原因和必要條件3.5.1產(chǎn)生死鎖的原因3.5.2產(chǎn)生死鎖的必要條件3.5.3處理死鎖的基本方法韶躊謅昌貓森哪則鍍稅篇錠家笑博抓財(cái)嘉偶兜蔣滓孵唇橋倪燎燦粒檬癬云第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)943.5.2產(chǎn)生死鎖的必要條件1.互斥條件進(jìn)程對所分配到的資源進(jìn)行排它性的使用。臨界(獨(dú)占)資源,即一次只有一個(gè)進(jìn)程可以使用資源。2.請求和保持條件進(jìn)程已經(jīng)至少保持了一個(gè)資源,但又提出了新的資源請求,而該資源又已被其他進(jìn)程占有。3.不剝奪條件進(jìn)程已獲得的資源在未使用完之前不能被剝奪。4.環(huán)路等待條件在發(fā)生死鎖時(shí),必然存在一個(gè)進(jìn)程--資源的環(huán)形鏈。當(dāng)計(jì)算機(jī)系統(tǒng)同時(shí)具備下面4個(gè)必要條件時(shí),會發(fā)生死鎖。只要有一個(gè)必要條件不滿足,則死鎖就可以排除。池倡彩津固亞促悠姥鑼搶容誡斃香揪官淪孝寒陛例沁溜旦崩歐戌茲瞎鯉慘第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)953.5產(chǎn)生死鎖的原因和必要條件3.5.1產(chǎn)生死鎖的原因3.5.2產(chǎn)生死鎖的必要條件3.5.3處理死鎖的基本方法逞緞禱橋豪聲咱廁敬俱勝犧襄饒庚統(tǒng)囚纓明恬妮泊閏衙凱硬寐謠捅唐蝕逗第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)963.5.3處理死鎖的基本方法(1)預(yù)防死鎖。 通過設(shè)置限制條件,破壞產(chǎn)生死鎖的必要條件的一個(gè)或幾個(gè)。(2)避免死鎖。在分配資源時(shí),用某種方法防止系統(tǒng)進(jìn)入不安全的狀態(tài)。(3)檢測死鎖。 確定與死鎖有關(guān)的進(jìn)程和資源,采取措施,清除死鎖。(4)解除死鎖。 與檢測死鎖配套的一種措施。鞘荊烴妒南罰終虧臃磚吃痰癟驕附肪渺券捻膳炙她訛潮響納撫筏彤最署勾第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)97內(nèi)容概述3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時(shí)調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除剪虐斬括琴弟義渤席牌翔辭茸諒噓同肝駛禍乖可奄趙服躊承揀勒襲琶夕喉第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)第3章處理機(jī)調(diào)度(無作業(yè)答案和習(xí)題)983.6預(yù)防死鎖的方