計(jì)算機(jī)操作系統(tǒng)原理

Page12023/1/31《操作系統(tǒng)原理》第三章處理機(jī)調(diào)度與死鎖3.1處理機(jī)調(diào)度的層次3.2調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則

3.3調(diào)度算法3.4實(shí)時(shí)調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測(cè)與解除Page22023/1/31知識(shí)點(diǎn)處理機(jī)調(diào)度及調(diào)度算法多處理機(jī)環(huán)境下的進(jìn)程（線程）調(diào)度方式產(chǎn)生死鎖的原因和必要條件預(yù)防死鎖的方法，死鎖的檢測(cè)與解除銀行家算法本章內(nèi)容：Page32023/1/31本章內(nèi)容：重點(diǎn)掌握進(jìn)程調(diào)度算法，各適用于何種情況

理解常用的幾種實(shí)時(shí)調(diào)度算法

理解產(chǎn)生死鎖的原因

掌握銀行家算法避免死鎖難點(diǎn)多道程序設(shè)計(jì)中的各種調(diào)度算法

響應(yīng)比高者優(yōu)先調(diào)度算法的計(jì)算過程

銀行家算法

Page42023/1/31導(dǎo)言：處理機(jī)是計(jì)算機(jī)系統(tǒng)中的重要資源在多道程序環(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)度分配處理機(jī)的任務(wù)是由進(jìn)程調(diào)度程序完成的。它是操作系統(tǒng)設(shè)計(jì)的中心問題之一。WHAT：按什么原則分配CPU—進(jìn)程調(diào)度算法WHEN：何時(shí)分配CPU—進(jìn)程調(diào)度的時(shí)機(jī)

HOW：如何分配CPU—CPU調(diào)度過程（進(jìn)程的上下文切換）Page52023/1/313.1處理機(jī)調(diào)度的層次

高級(jí)調(diào)度低級(jí)調(diào)度中級(jí)調(diào)度Page62023/1/31作業(yè)的基本概念作業(yè)：是用戶在一次解題或一個(gè)事務(wù)處理過程中要求計(jì)算機(jī)系統(tǒng)所做工作的集合，包括用戶程序、所需的數(shù)據(jù)及命令等；作業(yè)的狀態(tài)：一個(gè)作業(yè)進(jìn)入系統(tǒng)到運(yùn)行結(jié)束，一般需要經(jīng)歷收容、運(yùn)行、完成三個(gè)階段，與之相對(duì)應(yīng)的是作業(yè)的三種狀態(tài)：后備狀態(tài)運(yùn)行狀態(tài)完成狀態(tài)Page72023/1/31作業(yè)的基本概念作業(yè)步：在作業(yè)運(yùn)行期間，每個(gè)作業(yè)都必修經(jīng)過若干個(gè)相互獨(dú)立，又相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果，把其中的每一個(gè)加工步驟稱為作業(yè)步。作業(yè)控制塊：為了管理和調(diào)度作業(yè)，系統(tǒng)為每個(gè)作業(yè)設(shè)置了一個(gè)作業(yè)控制塊（JCB），它記錄該作業(yè)的有關(guān)信息。不同系統(tǒng)的JCB的組成內(nèi)容有所區(qū)別，主要包括：作業(yè)名、資源要求、資源使用情況、類型級(jí)別、狀態(tài)等。Page82023/1/31運(yùn)行狀態(tài)作業(yè)的基本概念后備狀態(tài)完成狀態(tài)就緒阻塞執(zhí)行I/O完成I/O請(qǐng)求時(shí)間片完作業(yè)注冊(cè)作業(yè)調(diào)度進(jìn)程調(diào)度終止作業(yè)作業(yè)狀態(tài)間轉(zhuǎn)換Page92023/1/31處理機(jī)調(diào)度的層次高級(jí)調(diào)度(HighScheduling)

作業(yè)調(diào)度或長(zhǎng)程調(diào)度（Long-TermScheduling）主要任務(wù)是按一定的原則對(duì)外存上處于后備狀態(tài)的作業(yè)進(jìn)行選擇，給選中的作業(yè)分配內(nèi)存、輸入/輸出設(shè)備等必要的資源，并建立相應(yīng)的進(jìn)程，放入就緒隊(duì)列，以使該作業(yè)的進(jìn)程獲得競(jìng)爭(zhēng)處理機(jī)的權(quán)利也稱為接納調(diào)度（AdmissionScheduling）高級(jí)調(diào)度的時(shí)間尺度通常是分鐘、小時(shí)或天Page102023/1/31處理機(jī)調(diào)度的層次在每次作業(yè)調(diào)度時(shí)，須決定：接納多少個(gè)作業(yè)即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行，取決于多道程序度（DegreeofMultiprogramming）作業(yè)太多服務(wù)質(zhì)量下降作業(yè)太少資源利用率低接納哪些作業(yè)

取決于作業(yè)調(diào)度算法先來先服務(wù)；短作業(yè)優(yōu)先；作業(yè)優(yōu)先權(quán)調(diào)度；響應(yīng)比調(diào)度→系統(tǒng)吞吐量太低

適當(dāng)?shù)恼壑愿呒?jí)調(diào)度(HighScheduling)→周轉(zhuǎn)時(shí)間太長(zhǎng)Page112023/1/31處理機(jī)調(diào)度的層次低級(jí)調(diào)度

進(jìn)程調(diào)度或短程調(diào)度（Short-TermScheduling）主要任務(wù)是按照某種策略和方法選取一個(gè)處于就緒狀態(tài)的進(jìn)程，將處理機(jī)分配給它常見的低級(jí)調(diào)度有非搶占式和搶占式兩種低級(jí)調(diào)度的時(shí)間尺度通常是毫秒級(jí)的。由于低級(jí)調(diào)度算法的頻繁使用，要求在實(shí)現(xiàn)時(shí)做到高效Page122023/1/31處理機(jī)調(diào)度的層次中級(jí)調(diào)度(Intermediate-LevelScheduling)

中程調(diào)度(Medium-TermScheduling)引入目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待主要任務(wù)是按照給定的原則和策略，將處于外存對(duì)換區(qū)中的重又具備運(yùn)行條件的就緒進(jìn)程調(diào)入內(nèi)存，或?qū)⑻幱趦?nèi)存就緒狀態(tài)或內(nèi)存阻塞狀態(tài)的進(jìn)程交換到外存對(duì)換區(qū)Page132023/1/313.2調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則Page142023/1/31調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型Page152023/1/31調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型在分時(shí)系統(tǒng)中，通常僅設(shè)有進(jìn)程調(diào)度系統(tǒng)把這些進(jìn)程組織成一個(gè)就緒隊(duì)列每個(gè)進(jìn)程在執(zhí)行時(shí)，可能有以下幾種情況:進(jìn)程獲得CPU正在執(zhí)行任務(wù)在給定時(shí)間片內(nèi)已完成，釋放處理機(jī)后為完成狀態(tài)任務(wù)在時(shí)間片內(nèi)未完成，進(jìn)入就緒隊(duì)列末尾在執(zhí)行期間因某事件而阻塞Page162023/1/31調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列進(jìn)程調(diào)度CPU進(jìn)程完成等待事件交互用戶事件出現(xiàn)時(shí)間片完P(guān)age172023/1/31調(diào)度隊(duì)列模型具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型在批處理系統(tǒng)中，不僅需要進(jìn)程調(diào)度，而且還要有作業(yè)調(diào)度就緒隊(duì)列的形式在批處理系統(tǒng)中，常用高優(yōu)先權(quán)隊(duì)列。進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，按優(yōu)先權(quán)高低插入相應(yīng)位置，調(diào)度程序總是把處理機(jī)分配給就緒隊(duì)首進(jìn)程設(shè)置多個(gè)阻塞隊(duì)列根據(jù)事件的不同設(shè)置多個(gè)隊(duì)列提高效率Page182023/1/31調(diào)度隊(duì)列模型進(jìn)程調(diào)度CPU進(jìn)程完成時(shí)間片完就緒隊(duì)列…12等待事件等待事件等待事件n12n事件出現(xiàn)事件出現(xiàn)…事件出現(xiàn)后備隊(duì)列作業(yè)調(diào)度……與上一模型的主要區(qū)別：就緒隊(duì)列的形式；設(shè)置多個(gè)阻塞隊(duì)列阻隊(duì)列塞2阻隊(duì)列塞n阻隊(duì)列塞1Page192023/1/31調(diào)度隊(duì)列模型同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列進(jìn)程調(diào)度就緒，掛起隊(duì)列中級(jí)調(diào)度阻塞，掛起隊(duì)列阻塞隊(duì)列等待事件進(jìn)程完成時(shí)間片完作業(yè)調(diào)度交互型作業(yè)后備隊(duì)列批量作業(yè)掛起掛起事件出現(xiàn)事件出現(xiàn)CPUPage202023/1/31調(diào)度準(zhǔn)則

面向用戶的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則（1）如果你是用戶，你希望系統(tǒng)如何為你服務(wù)，如何考慮？（2）如果你是調(diào)度者，從系統(tǒng)整體角度出發(fā)，如何考慮？Page212023/1/31選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向用戶的準(zhǔn)則周轉(zhuǎn)時(shí)間短平均周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間：進(jìn)程（或作業(yè)）的周轉(zhuǎn)時(shí)間T與系統(tǒng)為它提供服務(wù)的時(shí)間TS之比，即W=T/TS。而平均帶權(quán)周轉(zhuǎn)時(shí)間則可表示為:Page222023/1/31選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向用戶的準(zhǔn)則響應(yīng)時(shí)間快響應(yīng)時(shí)間是指從用戶通過鍵盤提交一個(gè)請(qǐng)求開始，直至系統(tǒng)中首次產(chǎn)生響應(yīng)為止的時(shí)間交互式系統(tǒng)用周轉(zhuǎn)時(shí)間衡量不是最佳截止時(shí)間保證截止時(shí)間是指某任務(wù)必須開始執(zhí)行的最遲時(shí)間或必須完成的最遲時(shí)間截止時(shí)間是實(shí)時(shí)系統(tǒng)中的重要指標(biāo)Page232023/1/31選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向用戶的準(zhǔn)則周轉(zhuǎn)時(shí)間短響應(yīng)時(shí)間快截止時(shí)間保證批處理系統(tǒng)分時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng)等待時(shí)間短優(yōu)先權(quán)Page242023/1/31選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向用戶的準(zhǔn)則等待時(shí)間短等待時(shí)間是在就緒隊(duì)列中等待所花的時(shí)間調(diào)度算法并不影響進(jìn)程運(yùn)行和執(zhí)行I/O的時(shí)間量；只影響進(jìn)程在就緒隊(duì)列中等待所花費(fèi)的時(shí)間優(yōu)先權(quán)準(zhǔn)則在批處理、實(shí)時(shí)和分時(shí)系統(tǒng)中都可以選擇優(yōu)先權(quán)準(zhǔn)則，以便讓緊急任務(wù)先處理有時(shí)還選擇搶占式調(diào)度方式Page252023/1/31選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐量高吞吐量指單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)作業(yè)調(diào)度的方式和算法對(duì)吞吐量的大小有較大影響處理機(jī)利用率高各類資源的平衡利用使內(nèi)存、外存和I/O設(shè)備的利用率高基于這樣的準(zhǔn)則，你設(shè)計(jì)操作系統(tǒng)的調(diào)度策略應(yīng)如何？Page262023/1/313.3調(diào)度算法在OS中調(diào)度的實(shí)質(zhì)是一種資源分配，因而調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法問題提出如何制定分配策略：對(duì)不同的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的算法，如短作業(yè)優(yōu)先，時(shí)間片輪轉(zhuǎn)等有些算法適用于作業(yè)調(diào)度，有些適用于進(jìn)程調(diào)度，有些兩者皆可Page272023/1/31調(diào)度算法

先來先服務(wù)和短作業(yè)優(yōu)先算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法Page282023/1/31先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)(FCFS)/先進(jìn)先出(FIFO)調(diào)度算法按照作業(yè)/進(jìn)程進(jìn)入系統(tǒng)的先后次序進(jìn)行調(diào)度，先進(jìn)入系統(tǒng)者先調(diào)度；即啟動(dòng)等待時(shí)間最長(zhǎng)的作業(yè)/進(jìn)程是一種最簡(jiǎn)單的調(diào)度算法，即可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度幾個(gè)術(shù)語到達(dá)時(shí)間、服務(wù)時(shí)間、開始時(shí)間完成時(shí)間、等待時(shí)間周轉(zhuǎn)時(shí)間：完成時(shí)間-到達(dá)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間①Page292023/1/31先來先服務(wù)和短作業(yè)優(yōu)先算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均04A13B25C32D44E044476先來先服務(wù)（先進(jìn)先出）：712101214111418141225.53.592.8AAAABBBCCCCCDDEEEE05101518tPage302023/1/31先來先服務(wù)和短作業(yè)優(yōu)先算法

先來先服務(wù)（先進(jìn)先出）優(yōu)缺點(diǎn)：

比較有利于長(zhǎng)作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）有利于CPU繁忙型作業(yè)（進(jìn)程），而不利于I/O繁忙型作業(yè)（進(jìn)程）用于批處理系統(tǒng)，不適于分時(shí)系統(tǒng)Page312023/1/31先來先服務(wù)和短作業(yè)優(yōu)先算法短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F，以要求運(yùn)行時(shí)間長(zhǎng)短進(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)度②Page322023/1/31先來先服務(wù)和短作業(yè)優(yōu)先算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均04A13B25C32D44E0441短作業(yè)/短進(jìn)程優(yōu)先（SJF/SPF）：4633/26988/391399/413181616/582.1AAAABBBCCCCCDDEEEE05101518tPage332023/1/31FCFS/SJF調(diào)度算法的性能先來先服務(wù)和短作業(yè)優(yōu)先算法SJF能有效地降低作業(yè)的平均等待時(shí)間，提高系統(tǒng)吞吐量

作業(yè)調(diào)度情況算法進(jìn)程名ABCDE平均到達(dá)時(shí)間01234服務(wù)時(shí)間43524FCFS完成時(shí)間47121418周轉(zhuǎn)時(shí)間461011149帶權(quán)周轉(zhuǎn)時(shí)間1225.53.52.8SJF完成時(shí)間4918613周轉(zhuǎn)時(shí)間4816398帶權(quán)周轉(zhuǎn)時(shí)間12.673.11.52.252.1SJF平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間明顯改善Page342023/1/31先來先服務(wù)和短作業(yè)優(yōu)先算法SJ(P)F調(diào)度算法也存在不容忽視的缺點(diǎn)對(duì)長(zhǎng)作業(yè)不利。嚴(yán)重的是，若一長(zhǎng)作業(yè)(進(jìn)程)進(jìn)入系統(tǒng)的后備隊(duì)列(就緒隊(duì)列)，由于調(diào)度程序總是優(yōu)先調(diào)度那些(即使是后進(jìn)來的)短作業(yè)(進(jìn)程)，將導(dǎo)致長(zhǎng)作業(yè)(進(jìn)程)長(zhǎng)期不被調(diào)度——饑餓完全未考慮作業(yè)(進(jìn)程)的緊迫程度，因而不能保證緊迫性作業(yè)(進(jìn)程)會(huì)被及時(shí)處理根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間確定作業(yè)（進(jìn)程）長(zhǎng)短，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。Page352023/1/31調(diào)度算法先來先服務(wù)和短作業(yè)優(yōu)先算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法Page362023/1/31高優(yōu)先權(quán)優(yōu)先（HPF，HighestPriorityFirst）調(diào)度算法優(yōu)先權(quán)調(diào)度算法的類型非搶占式優(yōu)先權(quán)調(diào)度算法搶占式優(yōu)先權(quán)調(diào)度算法③Page372023/1/31優(yōu)先權(quán)調(diào)度算法的類型非搶占式優(yōu)先權(quán)調(diào)度算法特點(diǎ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)中，也可用于某些對(duì)實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中高優(yōu)先權(quán)優(yōu)先（HPF，HighestPriorityFirst）調(diào)度算法Page382023/1/31高優(yōu)先權(quán)優(yōu)先（HPF，HighestPriorityFirst）調(diào)度算法優(yōu)先權(quán)調(diào)度算法的類型搶占式優(yōu)先權(quán)調(diào)度算法把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，但在執(zhí)行期間，只要出現(xiàn)另一個(gè)優(yōu)先權(quán)更高的進(jìn)程，則進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程的執(zhí)行，并將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程注意：只要系統(tǒng)中出現(xiàn)一個(gè)新的就緒進(jìn)程，就進(jìn)行優(yōu)先權(quán)比較該調(diào)度算法，能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中Page392023/1/31高優(yōu)先權(quán)優(yōu)先調(diào)度算法優(yōu)先權(quán)的類型靜態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán)Page402023/1/31高優(yōu)先權(quán)優(yōu)先調(diào)度算法優(yōu)先權(quán)的類型靜態(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ù)來表示的，例如，07或0255，又把該整數(shù)稱為優(yōu)先數(shù)確定進(jìn)程靜態(tài)優(yōu)先權(quán)的依據(jù)進(jìn)程類型:系統(tǒng)進(jìn)程，用戶進(jìn)程進(jìn)程對(duì)資源的需求用戶要求靜態(tài)優(yōu)先權(quán)特點(diǎn)系統(tǒng)開銷小、不夠精確、一般用在要求不高的系統(tǒng)中問題：用戶將優(yōu)先權(quán)設(shè)的較高，對(duì)其他進(jìn)程不利?。《踢M(jìn)程優(yōu)先對(duì)長(zhǎng)進(jìn)程不利??！Page412023/1/31高優(yōu)先權(quán)優(yōu)先調(diào)度算法動(dòng)態(tài)優(yōu)先權(quán)隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變，以獲得更好的調(diào)度性能可規(guī)定，在就緒隊(duì)列中的進(jìn)程，隨其等待時(shí)間的增長(zhǎng)，其優(yōu)先權(quán)以速率a提高具有相同優(yōu)先權(quán)初值的進(jìn)程，則最先進(jìn)入就緒隊(duì)列，其將因其動(dòng)態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲得處理機(jī)，此即FCFS算法具有各不相同的優(yōu)先權(quán)初值的就緒進(jì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è)長(zhǎng)作業(yè)長(zhǎng)期地壟斷處理機(jī)Page422023/1/31高優(yōu)先權(quán)優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法（HRF）是FCFS和SJF的結(jié)合，克服了兩種算法的缺點(diǎn)調(diào)度策略：響應(yīng)比最高的作業(yè)優(yōu)先啟動(dòng)因等待時(shí)間+服務(wù)時(shí)間=該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為④Page432023/1/31高優(yōu)先權(quán)優(yōu)先調(diào)度算法對(duì)HRF的小結(jié)等待時(shí)間相同的作業(yè)，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，要求服務(wù)的時(shí)間相同的作業(yè)，則等待時(shí)間愈長(zhǎng)，其優(yōu)先權(quán)愈高，長(zhǎng)作業(yè)，優(yōu)先權(quán)隨等待時(shí)間的增加而提高，其等待時(shí)間足夠長(zhǎng)時(shí)，其優(yōu)先權(quán)便可升到很高，從而也可獲得處理機(jī)是一種折衷，既照顧了短作業(yè)，又考慮了作業(yè)到達(dá)的先后次序，又不會(huì)使長(zhǎng)作業(yè)長(zhǎng)期得不到服務(wù)。缺點(diǎn)：要進(jìn)行響應(yīng)比計(jì)算，增加了系統(tǒng)開銷——對(duì)短作業(yè)有利——是先來先服務(wù)——對(duì)長(zhǎng)作業(yè)有利Page442023/1/31調(diào)度算法先來先服務(wù)和短作業(yè)優(yōu)先算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法Page452023/1/31基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法簡(jiǎn)單的時(shí)間片輪轉(zhuǎn)法(RR—RoundRobin)系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷請(qǐng)求，調(diào)度程序便停止該進(jìn)程的執(zhí)行，并將其放就緒隊(duì)列尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首時(shí)間片的大小從幾ms到幾百ms優(yōu)點(diǎn)：公平。保證就緒隊(duì)列中所有進(jìn)程在一給定的時(shí)間內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間缺點(diǎn)：緊迫任務(wù)響應(yīng)慢。UNIX中采用：時(shí)間片+優(yōu)先權(quán)⑤Page462023/1/31基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均ABCDEABCDEABCEACEC05101518t04A03B05C02D04E012349121517181515/41212/31818/599/21717/414.24.02若到達(dá)時(shí)間為0、1、2、3、4，又如何？Page472023/1/31就緒隊(duì)列的變化:基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法AABCABCBDABDAECABCDEq=1q=4ABECEC05101518tACBDAECBDAECPage482023/1/31基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均04A13B25C32D44E0135711101217181212/499/31616/588/21313/411.63.29Page492023/1/31基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法分時(shí)系統(tǒng)中常用時(shí)間片輪轉(zhuǎn)法時(shí)間片選擇問題固定時(shí)間片可變時(shí)間片時(shí)間片大小與時(shí)間片大小有關(guān)的因素系統(tǒng)響應(yīng)時(shí)間就緒進(jìn)程個(gè)數(shù)CPU能力

Page502023/1/31基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二個(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í)間片就愈小。⑥Page512023/1/31就緒隊(duì)列1基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法就緒隊(duì)列2就緒隊(duì)列3就緒隊(duì)列nS1S2S3至CPU至CPU至CPU至CPU(時(shí)間片：S1＜S2＜S3)調(diào)度方式高低優(yōu)先級(jí)時(shí)間片小大Sn按FIFO原則排隊(duì)等待調(diào)度尚未完成轉(zhuǎn)入第二隊(duì)列的末尾，按FIFO原則等待調(diào)度采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行因等待而放棄CPU后，進(jìn)入阻塞隊(duì)列，一旦等待的事件發(fā)生，則回到原來的就緒隊(duì)列Page522023/1/31基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法注意：僅當(dāng)?shù)?~(i-1)隊(duì)列均空時(shí)，才會(huì)調(diào)度第i隊(duì)列中的進(jìn)程運(yùn)行第i隊(duì)列中某進(jìn)程正在運(yùn)行時(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ì)列的末尾第i隊(duì)列中某進(jìn)程正在運(yùn)行時(shí)，該進(jìn)程因等待事件發(fā)生而進(jìn)入阻塞隊(duì)列，等待事件發(fā)生后，調(diào)度程序把進(jìn)程放回到第i隊(duì)列的末尾Page532023/1/311.為了使系統(tǒng)中各部分資源得到均衡使用，就必須選擇對(duì)資源需求不同的作業(yè)進(jìn)行合理搭配。這項(xiàng)工作是由（）完成的。A．作業(yè)調(diào)度B．中級(jí)調(diào)度C．進(jìn)程調(diào)度D．內(nèi)存調(diào)度

答案：A

課堂練習(xí)Page542023/1/312.進(jìn)程狀態(tài)從就緒態(tài)到運(yùn)行態(tài)的轉(zhuǎn)化工作是由（）完成的。A．作業(yè)調(diào)度B．中級(jí)調(diào)度C．進(jìn)程調(diào)度D．設(shè)備調(diào)度

答案：C

課堂練習(xí)Page552023/1/313.作業(yè)調(diào)度程序從處于（）狀態(tài)的隊(duì)列中選取適當(dāng)?shù)淖鳂I(yè)投入運(yùn)行。A．運(yùn)行B．提交C．完成D．后備

答案：D

課堂練習(xí)Page562023/1/314．（）是作業(yè)存在的唯一標(biāo)志。作業(yè)名B．進(jìn)程控制塊C．作業(yè)控制塊D．程序名

答案：C課堂練習(xí)Page572023/1/315.若進(jìn)程P1正在運(yùn)行，操作系統(tǒng)強(qiáng)行撤下P1進(jìn)程所占用的CPU，讓具有更高優(yōu)先級(jí)的進(jìn)程P2運(yùn)行，這種調(diào)度方式稱為（1），此時(shí)P1進(jìn)程處于（2）狀態(tài)。（1）A．中斷方式B．搶占方式C．非搶占方式D．查詢方式（2）A．等待B．結(jié)束C．善后處理D．就緒

答案：（1）B（2）D

課堂練習(xí)Page582023/1/316．作業(yè)調(diào)度算法的選擇?？紤]因素之一是使系統(tǒng)有最高的吞吐率，為此應(yīng)（）A.不讓處理機(jī)空閑B．能夠處理盡可能多的作業(yè)C．使各類用戶都滿意D．不使系統(tǒng)過于復(fù)雜

答案：B課堂練習(xí)Page592023/1/317.填空：對(duì)于FCFS，時(shí)間片輪轉(zhuǎn)，多級(jí)反饋隊(duì)列三個(gè)高級(jí)調(diào)度算法，他們對(duì)短作業(yè)的優(yōu)先程度升高排序?yàn)椋?/p>

。

答案：

FCFS，時(shí)間片輪轉(zhuǎn)，多級(jí)反饋隊(duì)列課堂練習(xí)Page602023/1/31課堂練習(xí)8.假設(shè)下列四個(gè)作業(yè)同時(shí)到達(dá)，當(dāng)使用最高優(yōu)先數(shù)優(yōu)先調(diào)度算法時(shí)，作業(yè)的平均周轉(zhuǎn)時(shí)間為（）小時(shí)。A．4.5B．10.5C．4.75D．10.25

答案：D

Page612023/1/319.作業(yè)J1，J2，J3，J4的提交時(shí)間和運(yùn)行時(shí)間如下表所示。若采用短作業(yè)優(yōu)先調(diào)度算法，則作業(yè)調(diào)度次序?yàn)椋?8），平均周轉(zhuǎn)時(shí)間為（19）分鐘（這里不考慮操作系統(tǒng)的開銷）

答案：CA

課堂練習(xí)Page622023/1/31

答案：B課堂練習(xí)Page632023/1/3111.系統(tǒng)中的四個(gè)作業(yè)，它們的到達(dá)時(shí)間、運(yùn)行時(shí)間、開始時(shí)間、完成時(shí)間和周轉(zhuǎn)時(shí)間如下表所示，該系統(tǒng)采用的作業(yè)調(diào)度算法是（A）。A：（1）先來先服務(wù)（2）短作業(yè)優(yōu)先（3）響應(yīng)比高者優(yōu)先（4）不能確定

答案：3課堂練習(xí)Page642023/1/3112．既考慮作業(yè)等待時(shí)間，又考慮作業(yè)執(zhí)行時(shí)間的調(diào)度算法是（）A.最高響應(yīng)比優(yōu)先B．短作業(yè)優(yōu)先C．優(yōu)先級(jí)調(diào)度D．先來先服務(wù)

答案：A課堂練習(xí)Page652023/1/3113．作業(yè)從進(jìn)入后備隊(duì)列到被調(diào)度程序選中的時(shí)間間隔稱為（）周轉(zhuǎn)時(shí)間B．響應(yīng)時(shí)間C．等待時(shí)間D．觸發(fā)時(shí)間

答案：C課堂練習(xí)Page662023/1/3114．下述作業(yè)調(diào)度算法中，（）調(diào)度算法與作業(yè)的估計(jì)運(yùn)行時(shí)間有關(guān)。A.先來先服務(wù)B．短作業(yè)優(yōu)先C．均衡D．時(shí)間片輪轉(zhuǎn)

答案：B課堂練習(xí)Page672023/1/3115．在各種作業(yè)調(diào)度算法中，若有作業(yè)同時(shí)到達(dá)，則平均等待時(shí)間最短的算法是（）A.先來先服務(wù)B．優(yōu)先數(shù)C．最高響應(yīng)比優(yōu)先D．短作業(yè)優(yōu)先

答案：D課堂練習(xí)Page682023/1/31證明：若有三個(gè)作業(yè)J1，J2，J3同時(shí)在后備作業(yè)隊(duì)列中等待運(yùn)行，其運(yùn)行時(shí)間分別為t1,t2,t3，且滿足關(guān)系t1<t2<t3,試證明按最短的作業(yè)優(yōu)先調(diào)度算法運(yùn)行這些作業(yè)，則總周轉(zhuǎn)時(shí)間最小。

證明：由于按最短的作業(yè)優(yōu)先調(diào)度算法運(yùn)行這些作業(yè)，所也三個(gè)作業(yè)的總周轉(zhuǎn)時(shí)間為：T1=t1+（t1+t2）+（t1+t2+t3）（1）若不按最短作業(yè)優(yōu)先調(diào)度算法運(yùn)行這些作業(yè)，不失一般性，可以假定調(diào)度順序?yàn)镴2，J1，J3，則總周轉(zhuǎn)時(shí)間為：T2=t2+（t1+t2）+（t1+t2+t3）（2）由（2）-（1）得：t2-t1>0。命題得證。課堂練習(xí)Page692023/1/31證明：給定一組作業(yè)J1，J2…Jn,他們的運(yùn)行時(shí)間分別為t1,t2…tn，假定這些作業(yè)同時(shí)到達(dá)，并且將在一臺(tái)CPU上按單道方式運(yùn)行。試證明按最短的作業(yè)優(yōu)先調(diào)度算法運(yùn)行這些作業(yè)，則平均周轉(zhuǎn)時(shí)間最小。

證明：不失一般性，假定按最短的作業(yè)優(yōu)先調(diào)度算法，調(diào)度順序分別為J1，J2…Jn，其運(yùn)行時(shí)間分別為：t1,t2…tn。則作業(yè)Ji的周轉(zhuǎn)時(shí)間為：Ti=t1+t2+…+ti。所以，全部作業(yè)的平均周轉(zhuǎn)時(shí)間為：T=[T1+T2+…+Tn]/n=[t1+(t1+t2)+（t1+t2+t3）+…+(t1+t2+…+tn)]/n顯然，當(dāng)t1≤t2≤…≤tn時(shí)，每個(gè)Ti達(dá)到最小值（i=1,2,…n）。因此，T最小，命題得證。課堂練習(xí)Page702023/1/31證明：給定一組作業(yè)J1，J2…Jn,他們的運(yùn)行時(shí)間分別為t1,t2…tn，假定這些作業(yè)同時(shí)到達(dá)，并且將在一臺(tái)CPU上按單道方式運(yùn)行。試證明短作業(yè)優(yōu)先的調(diào)度算法使得作業(yè)的平均等待時(shí)間最短。

證明：不失一般性，假定按最短的作業(yè)優(yōu)先調(diào)度算法,調(diào)度順序?yàn)镴1，J2…Jn，其運(yùn)行時(shí)間分別為:t1,t2…tn。顯然有t1≤t2≤…≤tn

。根據(jù)題意得:作業(yè)Ji的等待時(shí)間為:Wi=

t1+t2…+ti-1。所以，全部作業(yè)的平均等待時(shí)間為：W=[W1+W2+…+Wn]/n=[t1+(t1+t2)+（t1+t2+t3）+…+(t1+t2+…+tn-1)]/n顯然，當(dāng)t1≤t2≤…≤tn時(shí)，每一個(gè)Wi達(dá)到最小值（i=1,2,…n）。因此，W最小，這樣結(jié)論得證。課堂練習(xí)Page712023/1/313.4實(shí)時(shí)調(diào)度

實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)時(shí)調(diào)度算法的分類常用的幾種實(shí)時(shí)調(diào)度算法Page722023/1/31實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件提供必要的信息：開始截止時(shí)間完成截止時(shí)間就緒時(shí)間處理時(shí)間資源要求優(yōu)先級(jí)Page732023/1/31實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件系統(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ī)情況下，必須滿足下面的限制條件：例：一個(gè)周期為10ms，執(zhí)行5ms,

一個(gè)周期為15ms,執(zhí)行10ms,

則：(5/10)+(10/15)=35/30Page742023/1/31實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件系統(tǒng)處理能力強(qiáng)若上式不能滿足，則系統(tǒng)是不可調(diào)度的解決的方法是提高系統(tǒng)的處理能力采用單處理機(jī)系統(tǒng)但須增強(qiáng)其處理能力，以顯著地減少對(duì)每一個(gè)任務(wù)的處理時(shí)間采用多處理機(jī)系統(tǒng)假定系統(tǒng)中的處理機(jī)數(shù)為N，則應(yīng)將上述的限制條件改為Page752023/1/31實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件采用搶占式調(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ù)對(duì)截止時(shí)間的要求。但這種調(diào)度機(jī)制比較復(fù)雜小的實(shí)時(shí)系統(tǒng)，若能預(yù)知任務(wù)的開始截止時(shí)間，則可采用非搶占調(diào)度機(jī)制，以簡(jiǎn)化調(diào)度程序和對(duì)任務(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ù)Page762023/1/31實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件具有快速切換機(jī)制該機(jī)制應(yīng)具有如下兩方面的能力：對(duì)外部中斷的快速響應(yīng)能力為使在緊迫的外部事件請(qǐng)求中斷時(shí)系統(tǒng)能及時(shí)響應(yīng)，要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu)，還應(yīng)使禁止中斷的時(shí)間間隔盡量短，以免耽誤時(shí)機(jī)(其它緊迫任務(wù))快速的任務(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í)間開銷Page772023/1/31實(shí)時(shí)調(diào)度實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)時(shí)調(diào)度算法的分類常用的幾種實(shí)時(shí)調(diào)度算法Page782023/1/31實(shí)時(shí)調(diào)度算法的分類非搶占式調(diào)度算法（實(shí)時(shí)任務(wù)小）非搶占式輪轉(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ōu)先調(diào)度算法為時(shí)間要求嚴(yán)格的任務(wù)分配較高優(yōu)先級(jí)當(dāng)優(yōu)先權(quán)高的實(shí)時(shí)任務(wù)到來時(shí)，排在就緒隊(duì)列的隊(duì)首等待調(diào)度Page792023/1/31實(shí)時(shí)調(diào)度算法的分類搶占式調(diào)度算法基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法某實(shí)時(shí)任務(wù)到達(dá)后，若優(yōu)先級(jí)高于當(dāng)前正在執(zhí)行任務(wù)的優(yōu)先級(jí)，并不立即搶占當(dāng)前任務(wù)的處理機(jī)，而是等到時(shí)鐘中斷到來后調(diào)度程序才剝奪當(dāng)前任務(wù)的執(zhí)行立即搶占(ImmediatePreemption)的優(yōu)先權(quán)調(diào)度算法一旦有外部中斷，只要當(dāng)前任務(wù)不在臨界區(qū)內(nèi)，便立即剝奪當(dāng)前任務(wù)的執(zhí)行，交處理機(jī)分配給要求中斷的緊迫任務(wù)Page802023/1/31實(shí)時(shí)調(diào)度算法的分類(a)非搶占輪轉(zhuǎn)調(diào)度調(diào)度時(shí)間進(jìn)程

1進(jìn)程

2實(shí)時(shí)進(jìn)程要求調(diào)度進(jìn)程

n實(shí)時(shí)進(jìn)程調(diào)度實(shí)時(shí)進(jìn)程運(yùn)行(b)非搶占優(yōu)先權(quán)調(diào)度當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程請(qǐng)求調(diào)度當(dāng)前進(jìn)程運(yùn)行完成調(diào)度時(shí)間在就緒隊(duì)列尾在就緒隊(duì)列首xs--xxsxs--xxxmsPage812023/1/31實(shí)時(shí)調(diào)度算法的分類當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程請(qǐng)求調(diào)度時(shí)鐘中斷到來時(shí)調(diào)度時(shí)間(c)基于時(shí)鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度實(shí)時(shí)進(jìn)程當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程請(qǐng)求調(diào)度實(shí)時(shí)進(jìn)程搶占當(dāng)前進(jìn)程，并立即執(zhí)行(d)立即搶占的優(yōu)先權(quán)調(diào)度調(diào)度時(shí)間xms--xxsPage822023/1/31實(shí)時(shí)調(diào)度實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)時(shí)調(diào)度算法的分類常用的幾種實(shí)時(shí)調(diào)度算法Page832023/1/31常用的幾種實(shí)時(shí)調(diào)度算法最早截止時(shí)間優(yōu)先EDF(EarliestDeadlineFirst)算法根據(jù)任務(wù)的開始截止時(shí)間來確定任務(wù)的優(yōu)先級(jí)，截止時(shí)間越早優(yōu)先級(jí)越高既可用于搶占式調(diào)度也可用于非搶占式調(diào)度方式342開始截止時(shí)間任務(wù)到達(dá)123442任務(wù)執(zhí)行tEDF算法用于非搶占式調(diào)度方式131考慮一下?lián)屨际饺绾握{(diào)度？Page842023/1/31常用的幾種實(shí)時(shí)調(diào)度算法最早截止時(shí)間優(yōu)先EDF(EarliestDeadlineFirst)算法搶占式調(diào)度周期示例：周期性任務(wù)A和B，每個(gè)周期的處理時(shí)間10ms，A的周期為20ms，B的周期為50ms。A的到達(dá)時(shí)間：020406080A1A2A3A4A5B的到達(dá)時(shí)間：050100B1B2B3A1B1A2B1B2A3A4A5B2Page852023/1/31常用的幾種實(shí)時(shí)調(diào)度算法最低松弛度優(yōu)先即LLF(LeastLaxityFirst)算法根據(jù)任務(wù)緊急(或松弛)的程度，來確定任務(wù)的優(yōu)先級(jí)。任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級(jí)就愈高，以使之優(yōu)先執(zhí)行例：一個(gè)任務(wù)在200ms時(shí)必須完成，而它本身所需的運(yùn)行時(shí)間為100ms，因此，調(diào)度程序必須在100ms之前調(diào)度執(zhí)行，則該任務(wù)的緊急程度(松弛程度)為100ms在實(shí)現(xiàn)該算法時(shí)要求系統(tǒng)中有一個(gè)按松弛度排序的實(shí)時(shí)任務(wù)就緒隊(duì)列，松弛度最低的任務(wù)排在隊(duì)列最前面，調(diào)度程序總是選擇就緒隊(duì)列中的隊(duì)首任務(wù)執(zhí)行該算法主要用于可搶占調(diào)度方式中Page862023/1/31常用的幾種實(shí)時(shí)調(diào)度算法實(shí)例：一個(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則處理能力需求：Page872023/1/31常用的幾種實(shí)時(shí)調(diào)度算法A和B任務(wù)每次必須完成的時(shí)間松弛度=必須完成時(shí)間-其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間t1=0，A1的松弛度=20ms-10ms-0ms=10ms

B1的松弛度=50ms-25ms-0ms=25msA1優(yōu)先Page882023/1/31常用的幾種實(shí)時(shí)調(diào)度算法A1(10)1020B1(20)t230t3A2(10)1t404B(5)(10)50A3t560t6B2(15)70A4(10)t780t8B2(10)t10t利用LLF算法進(jìn)行調(diào)度的情況松弛度=必須完成時(shí)間-其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間t2=10，A1結(jié)束，A2未到達(dá)

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

B1的松弛度=50ms-5ms-30ms=15msA2搶占運(yùn)行松弛度=必須完成時(shí)間-其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間t4=40，A3的松弛度=60ms-10ms-40ms=10ms

B1的松弛度=50ms-5ms-40ms=5msB1運(yùn)行松弛度=必須完成時(shí)間-其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間t5=45，A3的松弛度=60ms-10ms-45ms=5ms

B2未到達(dá)A3運(yùn)行松弛度=必須完成時(shí)間-其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間t6=55，A3結(jié)束，A4未到達(dá)

B2運(yùn)行松弛度=必須完成時(shí)間-其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間t7=70，A4的松弛度=80ms-10ms-70ms=0ms

B2的松弛度=100ms-10ms-70ms=10msA4運(yùn)行松弛度=必須完成時(shí)間-其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間t8=80，A5的松弛度=100ms-10ms-80ms=10ms

B2的松弛度=100ms-10ms-80ms=10msB2運(yùn)行（同樣松弛度應(yīng)先來先服務(wù)）Page892023/1/313.5產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因產(chǎn)生死鎖的必要條件處理死鎖的基本方法Page902023/1/31產(chǎn)生死鎖的原因競(jìng)爭(zhēng)資源引起進(jìn)程死鎖可剝奪和非剝奪性資源可剝奪性資源是指進(jìn)程在獲得這類資源后，該資源可以再被其他進(jìn)程或系統(tǒng)剝奪，如處理機(jī)、內(nèi)存等非剝奪性資源是指當(dāng)系統(tǒng)把這類資源分配給某個(gè)進(jìn)程后，再不能強(qiáng)行收回，只能在進(jìn)程用完后自行釋放，如磁帶機(jī)、打印機(jī)等競(jìng)爭(zhēng)非剝奪性資源系統(tǒng)中的非剝奪性資源由于數(shù)量有限而不能滿足進(jìn)程運(yùn)行的需要，進(jìn)程在運(yùn)行過程中因爭(zhēng)奪這些資源而限入僵局競(jìng)爭(zhēng)臨時(shí)性資源Page912023/1/31產(chǎn)生死鎖的原因I/O設(shè)備共享時(shí)的死鎖情況

若系統(tǒng)中只有一臺(tái)打印機(jī)R1和一臺(tái)讀卡機(jī)R2，可供進(jìn)程P1和P2共享。若形成環(huán)路，這樣會(huì)產(chǎn)生死鎖。R1R2P1P2分配分配請(qǐng)求請(qǐng)求Page922023/1/31產(chǎn)生死鎖的原因

進(jìn)程之間通信時(shí)的死鎖S2P1S3P3S1P2產(chǎn)生P2產(chǎn)生P3產(chǎn)生要求接收要求接收要求接收Page932023/1/31產(chǎn)生死鎖的原因進(jìn)程推進(jìn)順序不當(dāng)引起死鎖P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)①②③④D不安全區(qū)Page942023/1/31產(chǎn)生死鎖的原因若并發(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)程死鎖Page952023/1/31產(chǎn)生死鎖的原因和必要條件死鎖的基本概念產(chǎn)生死鎖的原因產(chǎn)生死鎖的必要條件處理死鎖的基本方法Page962023/1/31產(chǎn)生死鎖的必要條件互斥條件

進(jìn)程對(duì)所分配到的資源進(jìn)行排它性的使用請(qǐng)求和保持條件

進(jìn)程已經(jīng)至少保持了一個(gè)資源，但又提出了新的資源請(qǐng)求，而該資源又已被其他進(jìn)程占有不剝奪條件進(jìn)程已獲得的資源在未使用完之前不能被剝奪環(huán)路等待條件在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程--資源循環(huán)等待的環(huán)形鏈Page972023/1/31產(chǎn)生死鎖的原因和必要條件死鎖的基本概念產(chǎn)生死鎖的原因產(chǎn)生死鎖的必要條件處理死鎖的基本方法Page982023/1/31處理死鎖的基本方法預(yù)防死鎖避免死鎖檢測(cè)死鎖解除死鎖Page992023/1/31處理死鎖的基本方法方法資源分配策略各種可能模式主要優(yōu)點(diǎn)主要缺點(diǎn)預(yù)防Prevention保守的；寧可資源閑置（從機(jī)制上使死鎖條件不成立，即摒棄三個(gè)必要條件）一次請(qǐng)求所有資源<條件2>適用于作突發(fā)式處理的進(jìn)程；不必剝奪效率低；進(jìn)程初始化時(shí)間延長(zhǎng)剝奪次數(shù)過多；多次對(duì)資源重新起動(dòng)不便靈活申請(qǐng)新資源資源剝奪<條件3>適用于狀態(tài)可以保存和恢復(fù)的資源資源按序申請(qǐng)<條件4>避免Avoidance是“預(yù)防”和“檢測(cè)”的折衷（在運(yùn)行時(shí)判斷是否可能死鎖）尋找可能的安全的運(yùn)行順序不必進(jìn)行剝奪使用條件：必須知道將來的資源需求；進(jìn)程可能會(huì)長(zhǎng)時(shí)間阻塞檢測(cè)Detection寬松的；只要允許，就分配資源定期檢查死鎖是否已經(jīng)發(fā)生不延長(zhǎng)進(jìn)程初始化時(shí)間；允許對(duì)死鎖進(jìn)行現(xiàn)場(chǎng)處理通過剝奪解除死鎖，造成損失可以在編譯時(shí)（而不必在運(yùn)行時(shí)）就進(jìn)行檢查Page1002023/1/313.6預(yù)防死鎖的方法預(yù)防死鎖系統(tǒng)安全狀態(tài)利用銀行家算法避免死鎖Page1012023/1/31預(yù)防死鎖摒棄“請(qǐng)求和保持”條件所有進(jìn)程在開始運(yùn)行之前必須一次性的申請(qǐng)整個(gè)運(yùn)行過程所需的全部資源簡(jiǎn)單、易于實(shí)現(xiàn)、安全資源浪費(fèi)嚴(yán)重進(jìn)程延遲運(yùn)行Page1022023/1/31預(yù)防死鎖摒棄“不剝奪”條件進(jìn)程逐個(gè)地申請(qǐng)所需資源當(dāng)一個(gè)已經(jīng)保持了某些資源的進(jìn)程申請(qǐng)新資源而不能得到滿足時(shí)，必須放棄所有已保持的資源實(shí)現(xiàn)復(fù)雜、代價(jià)高昂延長(zhǎng)了進(jìn)程的周轉(zhuǎn)時(shí)間，還增加了系統(tǒng)開銷，降低了系統(tǒng)的吞吐量Page1032023/1/31預(yù)防死鎖摒棄“環(huán)路等待”條件系統(tǒng)將所有資源按類型分配序號(hào)并排隊(duì)所有進(jìn)程申請(qǐng)資源必須按序號(hào)遞增的順序資源利用率和系統(tǒng)吞吐量較高但在資源管理和資源申請(qǐng)方面仍有問題Page1042023/1/31預(yù)防死鎖序號(hào)資源1輸入機(jī)2打印機(jī)3磁帶機(jī)進(jìn)程需求資源P1打印機(jī)磁帶機(jī)P2磁帶機(jī)打印機(jī)存在問題：資源的需求順序不等于序號(hào)，仍存在資源浪費(fèi)。Page1052023/1/31預(yù)防死鎖摒棄“環(huán)路等待”條件其資源利用率和系統(tǒng)吞吐量，都有較明顯的改善，但也存在下述嚴(yán)重問題：（1）資源所分配的序號(hào)，必須相對(duì)穩(wěn)定，這就限制了新設(shè)備類型的增加。（2）進(jìn)程使用各資源的順序，與系統(tǒng)規(guī)定的順序不同，造成對(duì)資源的浪費(fèi)。（3）按規(guī)定次序申請(qǐng)資源的方法，必然會(huì)限制了用戶簡(jiǎn)單、自主地編程。Page1062023/1/313.6預(yù)防死鎖的方法預(yù)防死鎖系統(tǒng)安全狀態(tài)利用銀行家算法避免死鎖Page1072023/1/31系統(tǒng)安全狀態(tài)安全狀態(tài)在避免死鎖的方法中，允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源，但系統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計(jì)算此次資源分配的安全性。若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則將資源分配給進(jìn)程；否則，令進(jìn)程等待所謂安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序(P1,P2,…，Pn)(稱〈P1,P2,…,Pn〉序列為安全序列)，來為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都可順利地完成。如果系統(tǒng)無法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)Page1082023/1/31安全狀態(tài)之例

假定系統(tǒng)中有三個(gè)進(jìn)程P1、P2和P3，共有12臺(tái)磁帶機(jī)。進(jìn)程P1總共要求10臺(tái)磁帶機(jī)，P2和P3分別要求4臺(tái)和9臺(tái)。假設(shè)在T0時(shí)刻，進(jìn)程P1、P2和P3已分別獲得5臺(tái)、2臺(tái)和2臺(tái)磁帶機(jī)，尚有3臺(tái)空閑未分配，如下表所示：

29P324P23510P1可用已分配最大需求進(jìn)程415100109312存在安全序列：P2-P1-P3，系統(tǒng)處于安全狀態(tài)。系統(tǒng)安全狀態(tài)Page1092023/1/31由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換

如果不按照安全序列分配資源，則系統(tǒng)可能會(huì)由安全狀態(tài)進(jìn)入不安全狀態(tài)。例如，在T0時(shí)刻以后，P3又請(qǐng)求1臺(tái)磁帶機(jī)，若此時(shí)系統(tǒng)把剩余3臺(tái)中的1臺(tái)分配給P3，則系統(tǒng)便進(jìn)入不安全狀態(tài)。進(jìn)程最大需求已分配可用P11053P242P39232404不安全狀態(tài)系統(tǒng)安全狀態(tài)Page1102023/1/313.6預(yù)防死鎖的方法預(yù)防死鎖系統(tǒng)安全狀態(tài)利用銀行家算法避免死鎖Page1112023/1/31利用銀行家算法避免死鎖

銀行家算法中的數(shù)據(jù)結(jié)構(gòu)

可利用資源向量Available

這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果Available[j]=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。

Page1122023/1/31最大需求矩陣Max

一個(gè)n×m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Max[i,j]=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。分配矩陣Allocation

一個(gè)n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation[i,j]=K，表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。

需求矩陣Need

一個(gè)n×m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Need[i,j]=K，則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)。

Need[i,j]=Max[i,j]–Allocation[i,j]利用銀行家算法避免死鎖

銀行家算法中的數(shù)據(jù)結(jié)構(gòu)

Page1132023/1/31設(shè)Requesti是進(jìn)程Pi的請(qǐng)求向量，如果Requesti[j]=K，表示進(jìn)程Pi需要K個(gè)Rj類型的資源。當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：

(1)如果Requesti[j]≤Need[i,j]，便轉(zhuǎn)向步驟(2)；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。

(2)如果Requesti[j]≤Available[j]，便轉(zhuǎn)向步驟(3)；否則，表示尚無足夠資源，Pi須等待。

利用銀行家算法避免死鎖

銀行家算法Page1142023/1/31

(3)系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：

Available[j]:=Available[j]-Requesti[j];Allocation[i,j]:=Allocation[i,j]+Requesti[j];Need[i,j]:=Need[i,j]-Requesti[j];(4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。利用銀行家算法避免死鎖

銀行家算法Page1152023/1/31

(1)設(shè)置兩個(gè)向量：①工作向量Work:它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算法開始時(shí)，Work:=Available;②Finish:它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finish[i]:=false;

當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令Finish[i]:=true。

利用銀行家算法避免死鎖

安全性算法Page1162023/1/31

(2)從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：①Finish[i]=false;②Need[i,j]≤Work[j]；若找到，執(zhí)行步驟(3)，否則，執(zhí)行步驟(4)。

利用銀行家算法避免死鎖

安全性算法Page1172023/1/31

(4)如果所有進(jìn)程的Finish[i]=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。(3)當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：

Work[j]:=Work[i]+Allocation[i,j];Finish[i]:=true;gotostep2;

利用銀行家算法避免死鎖

安全性算法Page1182023/1/31銀行家算法之例

假定系統(tǒng)中有五個(gè)進(jìn)程｛P0,P1,P2,P3,P4｝和三類資源｛A,B,C｝，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖所示。

2C3B11023C31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMaxNeed[i,j]=Max[i,j]–Allocation[i,j]Page1192023/1/31(1)T0時(shí)刻的安全性：truetruetruetruetrueFinish77532C54443B02210C10010B30112C40312B75322C44433B100710P07047P45213P110367P27205P3AAAAWork+AllocationAllocationNeedWork存在安全序列：P1-P3-P4-P2-P0，系統(tǒng)在T0時(shí)刻處于安全狀態(tài)。銀行家算法之例Page1202023/1/31

(2)P1請(qǐng)求資源：P1發(fā)出請(qǐng)求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進(jìn)行檢查：①Request1(1,0,2)≤Need1(1,2,2)②Request1(1,0,2)≤Available1(3,3,2)MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431銀行家算法之例Page1212023/1/31

③系統(tǒng)先假定可為P1分配資源，并修改Available,Allocation1和Need1向量，由此形成的資源變化情況如圖所示。Request1(1，0，2)2C3B11023C31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMax322000032銀行家算法之例Page1222023/1/31

④再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。truetruetruetruetrueFinish75532C55443B20212C01010B03110C04312B55320C54433B10367P27047P45302P17077P07205P3AAAAWork+AllocationAllocationNeedWork存在安全序列：P1-P3-P4-P0-P2，系統(tǒng)處于安全狀態(tài)，可以滿足P1資源分配請(qǐng)求。銀行家算法之例Page1232023/1/31

(3)P4請(qǐng)求資源：P4發(fā)出請(qǐng)求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進(jìn)行檢查：①Request4(3,3,0)≤Need4(4,3,1);②Request4(3,3,0)≤Available(2,3,0)，讓P4等待。MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431銀行家算法之例不滿足，等待Page1242023/1/31(4)P0請(qǐng)求資源：P0發(fā)出請(qǐng)求向量Request0(0，2，0)，系統(tǒng)按銀行家算法進(jìn)行檢查：①Request0(0,2,0)≤Need0(7,4,3);②Request0(0,2,0)≤Available(2,3,0);MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431銀行家算法之例Page1252023/1/31③系統(tǒng)暫時(shí)先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)，如圖所示。Request0(0，2，0)MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431723210030銀行家算法之例進(jìn)入不安全狀態(tài)Page1262023/1/31(5)P0請(qǐng)求資源：P0發(fā)出請(qǐng)求向量改為Request0(0,1,0)，系統(tǒng)按銀行家算法進(jìn)行檢查：①Request0(0,1,0)≤Need0(7,4,3);②Request0(0,1,0)≤Available(2,3,0);MaxAllocationNeedAvailableABCABCABCABCP0753010743230P1322302020P2902302600P3222211011P4433002431銀行家算法之例Page1272023/1/31

③系統(tǒng)先假定可為P0分配資源，并修改Available,Allocation0和Need0向量，由此形成的資源變化情況如圖所示。Request0(0,1,0)0C3B11003C31024B21220C01001B32223C32025B404P4639P22707P0022P3033P1AAAAAvailableNeedAllocationMax733220020銀行家算法之例Pa