第三章處理機(jī)調(diào)度與死鎖操作系統(tǒng)劉剛12/17/20221第三章處理機(jī)調(diào)度與死鎖操作系統(tǒng)劉剛12/17/2022第三章處理機(jī)調(diào)度與死鎖重點(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ì)算過(guò)程

銀行家算法

12/17/20222第三章處理機(jī)調(diào)度與死鎖重點(diǎn)12/17/20222第三章處理機(jī)調(diào)度與死鎖知識(shí)點(diǎn)處理機(jī)調(diào)度及調(diào)度算法多處理機(jī)環(huán)境下的進(jìn)程（線程）調(diào)度方式產(chǎn)生死鎖的原因和必要條件預(yù)防死鎖的方法，死鎖的檢測(cè)與解除銀行家算法12/17/20223第三章處理機(jī)調(diào)度與死鎖知識(shí)點(diǎn)12/17/20223第三章處理機(jī)調(dià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)度過(guò)程（進(jìn)程的上下文切換）12/17/20224第三章處理機(jī)調(diào)度與死鎖處理機(jī)是計(jì)算機(jī)系統(tǒng)中的重要資源分配處第三章處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度的基本概念調(diào)度算法實(shí)時(shí)調(diào)度多處理機(jī)系統(tǒng)中的調(diào)度產(chǎn)生死鎖的原因和必要條件預(yù)防死鎖的方法死鎖的檢測(cè)與解除12/17/20225第三章處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度的基本概念12/17/處理機(jī)調(diào)度的基本概念

高級(jí)、中級(jí)和低級(jí)調(diào)度進(jìn)程調(diào)度的任務(wù)確定算法的原則進(jìn)程調(diào)度方式調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則12/17/20226處理機(jī)調(diào)度的基本概念高級(jí)、中級(jí)和低級(jí)調(diào)度12/17/202處理機(jī)調(diào)度的基本概念作業(yè)是用戶在一次解題或一個(gè)事務(wù)處理過(guò)程中要求計(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)12/17/20227處理機(jī)調(diào)度的基本概念作業(yè)是用戶在一次解題或一個(gè)事務(wù)處理過(guò)程中運(yùn)行狀態(tài)處理機(jī)調(diào)度的基本概念后備狀態(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)換12/17/20228運(yùn)行狀態(tài)處理機(jī)調(diào)度的基本概念后備狀態(tài)完成狀態(tài)就緒阻塞執(zhí)行I/3.1處理機(jī)調(diào)度的基本概念3.1.1高級(jí)、中級(jí)和低級(jí)調(diào)度1.高級(jí)調(diào)度(HighScheduling)2.低級(jí)調(diào)度(LowLevelScheduling)3.中級(jí)調(diào)度(Intermediate-LevelScheduling)12/17/202293.1處理機(jī)調(diào)度的基本概念3.1.1高級(jí)、中級(jí)和低級(jí)高級(jí)、中級(jí)和低級(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í)或天12/17/202210高級(jí)、中級(jí)和低級(jí)調(diào)度高級(jí)調(diào)度(HighScheduling高級(jí)、中級(jí)和低級(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)度算法先來(lái)先服務(wù)短作業(yè)優(yōu)先作業(yè)優(yōu)先權(quán)調(diào)度響應(yīng)比調(diào)度→周轉(zhuǎn)時(shí)間太長(zhǎng)→系統(tǒng)吞吐量太低適當(dāng)?shù)恼壑远嗟莱绦蚨龋杭丛试S多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行。周轉(zhuǎn)時(shí)間：從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時(shí)間間隔。吞吐量：是指在單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。12/17/202211高級(jí)、中級(jí)和低級(jí)調(diào)度在每次作業(yè)調(diào)度時(shí)，須決定：→周轉(zhuǎn)時(shí)間太長(zhǎng)高級(jí)、中級(jí)和低級(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í)做到高效12/17/202212高級(jí)、中級(jí)和低級(jí)調(diào)度低級(jí)調(diào)度12/17/202212高級(jí)、中級(jí)和低級(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ū)12/17/202213高級(jí)、中級(jí)和低級(jí)調(diào)度中級(jí)調(diào)度(Intermediate-Le處理機(jī)調(diào)度的基本概念

高級(jí)、中級(jí)和低級(jí)調(diào)度進(jìn)程調(diào)度的任務(wù)確定算法的原則進(jìn)程調(diào)度方式調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則12/17/202214處理機(jī)調(diào)度的基本概念高級(jí)、中級(jí)和低級(jí)調(diào)度12/17/20進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù)是控制、協(xié)調(diào)進(jìn)程對(duì)CPU的競(jìng)爭(zhēng),即按一定的調(diào)度算法從就緒隊(duì)列中選中一個(gè)進(jìn)程，把CPU的使用權(quán)交給被選中的進(jìn)程12/17/202215進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù)12/17/202215處理機(jī)調(diào)度的基本概念

高級(jí)、中級(jí)和低級(jí)調(diào)度進(jìn)程調(diào)度的任務(wù)

確定算法的原則進(jìn)程調(diào)度方式調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則12/17/202216處理機(jī)調(diào)度的基本概念高級(jí)、中級(jí)和低級(jí)調(diào)度12/17/20確定算法的原則具有公平性資源利用率高（特別是CPU利用率）在交互式系統(tǒng)情況下要追求響應(yīng)時(shí)間（越短越好）在批處理系統(tǒng)情況下要追求系統(tǒng)吞吐量12/17/202217確定算法的原則具有公平性12/17/202217處理機(jī)調(diào)度的基本概念

高級(jí)、中級(jí)和低級(jí)調(diào)度進(jìn)程調(diào)度的任務(wù)確定算法的原則

進(jìn)程調(diào)度方式調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則12/17/202218處理機(jī)調(diào)度的基本概念高級(jí)、中級(jí)和低級(jí)調(diào)度12/17/20進(jìn)程調(diào)度方式非搶占方式(Non-preemptiveMode)搶占方式(PreemptiveMode)12/17/202219進(jìn)程調(diào)度方式非搶占方式(Non-preemptiveMod進(jìn)程調(diào)度方式非搶占方式(Non-preemptiveMode)

當(dāng)某一進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，即使有某個(gè)更為重要或緊迫的進(jìn)程進(jìn)入就緒隊(duì)列，該進(jìn)程仍繼續(xù)執(zhí)行，直到其完成或發(fā)生某種事件而進(jìn)入完成或阻塞狀態(tài)時(shí)，才把處理機(jī)分配給更為重要或緊迫的進(jìn)程引起進(jìn)程調(diào)度的因素正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行執(zhí)行中的進(jìn)程因提出I/O請(qǐng)求而暫停執(zhí)行；在進(jìn)程通信或同步過(guò)程中執(zhí)行了某種原語(yǔ)操作，如wait、Block、Wakeup原語(yǔ)優(yōu)點(diǎn)：算法簡(jiǎn)單，系統(tǒng)開銷小缺點(diǎn)：緊急任務(wù)不能及時(shí)響應(yīng)；短進(jìn)程到達(dá)要等待長(zhǎng)進(jìn)程運(yùn)行結(jié)束12/17/202220進(jìn)程調(diào)度方式非搶占方式(Non-preemptiveMod進(jìn)程調(diào)度方式搶占方式(PreemptiveMode)

當(dāng)某一進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，若有某個(gè)更為重要或緊迫的進(jìn)程進(jìn)入就緒隊(duì)列，則立即暫停正在執(zhí)行的進(jìn)程，將處理機(jī)分配給這個(gè)更為重要或緊迫的進(jìn)程搶占式調(diào)度主要有以下原則優(yōu)先權(quán)原則允許高優(yōu)先權(quán)的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)短作業(yè)(進(jìn)程)優(yōu)先原則允許執(zhí)行時(shí)間短的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)時(shí)間片原則時(shí)間片用完后停止執(zhí)行，重新進(jìn)行調(diào)度，適用于分時(shí)系統(tǒng)

優(yōu)點(diǎn)：適于時(shí)間要求嚴(yán)格的實(shí)時(shí)系統(tǒng)缺點(diǎn)：調(diào)度算法復(fù)雜，系統(tǒng)開銷大12/17/202221進(jìn)程調(diào)度方式搶占方式(PreemptiveMode)優(yōu)點(diǎn)：處理機(jī)調(diào)度的基本概念

高級(jí)、中級(jí)和低級(jí)調(diào)度進(jìn)程調(diào)度的任務(wù)確定算法的原則進(jìn)程調(diào)度方式

調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則12/17/202222處理機(jī)調(diào)度的基本概念高級(jí)、中級(jí)和低級(jí)調(diào)度12/17/20調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型12/17/202223調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型12/17/20222調(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í)行期間因某事件而阻塞12/17/202224調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型12/17/20222調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列進(jìn)程調(diào)度CPU進(jìn)程完成等待事件交互用戶事件出現(xiàn)時(shí)間片完12/17/202225調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列進(jìn)程調(diào)調(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ì)列提高效率12/17/202226調(diào)度隊(duì)列模型具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型12/17/20調(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ì)列塞112/17/202227調(diào)度隊(duì)列模型進(jìn)程調(diào)度CPU進(jìn)程完成時(shí)間片完就緒隊(duì)列…12等待調(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)事件出現(xiàn)CPU12/17/202228調(diào)度隊(duì)列模型同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列進(jìn)程調(diào)度就處理機(jī)調(diào)度的基本概念

高級(jí)、中級(jí)和低級(jí)調(diào)度進(jìn)程調(diào)度的任務(wù)確定算法的原則進(jìn)程調(diào)度方式調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則如果你是用戶，你希望系統(tǒng)如何為你服務(wù)，如何考慮？？如果你是調(diào)度者，從系統(tǒng)整體角度出發(fā)，應(yīng)如何考慮？？12/17/202229處理機(jī)調(diào)度的基本概念高級(jí)、中級(jí)和低級(jí)調(diào)度如果你是用戶，你3.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1.面向用戶的準(zhǔn)則2.面向系統(tǒng)的準(zhǔn)則12/17/2022303.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1.面向用戶3.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1.面向用戶的準(zhǔn)則(1)周轉(zhuǎn)時(shí)間短。

(2)響應(yīng)時(shí)間快。(3)截止時(shí)間的保證。(4)優(yōu)先權(quán)準(zhǔn)則。12/17/2022313.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1.面向用戶選擇調(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í)間則可表示為:12/17/202232選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向用戶的準(zhǔn)則帶權(quán)周轉(zhuǎn)時(shí)間：選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向用戶的準(zhǔn)則響應(yīng)時(shí)間快響應(yīng)時(shí)間是指從用戶通過(guò)鍵盤提交一個(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)12/17/202233選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向用戶的準(zhǔn)則12/17/2選擇調(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)度方式12/17/202234選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向用戶的準(zhǔn)則12/17/2選擇調(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)如何？12/17/202235選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向系統(tǒng)的準(zhǔn)則基于這樣的準(zhǔn)則第三章處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度的基本概念

調(diào)度算法

實(shí)時(shí)調(diào)度多處理機(jī)系統(tǒng)中的調(diào)度產(chǎn)生死鎖的原因和必要條件預(yù)防死鎖的方法死鎖的檢測(cè)與解除12/17/202236第三章處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度的基本概念12/17/2調(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)度，有些兩者皆可12/17/202237調(diào)度算法在OS中調(diào)度的實(shí)質(zhì)是一種資源分配，因而調(diào)度算法是指：調(diào)度算法

先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法12/17/202238調(diào)度算法先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法12/17/202238先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法先來(lái)先服務(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ù)語(yǔ)到達(dá)時(shí)間、服務(wù)時(shí)間、開始時(shí)間完成時(shí)間、等待時(shí)間周轉(zhuǎn)時(shí)間：完成時(shí)間-到達(dá)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間①12/17/202239先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法先來(lái)先服務(wù)(FCFS)/先進(jìn)先出(先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均04A13B25C32D44E044476先來(lái)先服務(wù)（先進(jìn)先出）：712101214111418141225.53.592.8AAAABBBCCCCCDDEEEE05101518t12/17/202240先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法先來(lái)先服務(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)12/17/202241先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法先來(lái)先服務(wù)（先進(jìn)先出）優(yōu)缺點(diǎn)比先來(lái)先服務(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)度②12/17/202242先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P先來(lái)先服務(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/540/52.1AAAABBBCCCCCDDEEEE05101518t12/17/202243先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成FCFS/SJF調(diào)度算法的性能先來(lái)先服務(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í)間明顯改善12/17/202244FCFS/SJF調(diào)度算法的性能先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法SJ先來(lái)先服務(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)來(lái)的)短作業(yè)(進(jìn)程)，將導(dǎo)致長(zhǎng)作業(yè)(進(jìn)程)長(zhǎng)期不被調(diào)度——饑餓完全未考慮作業(yè)(進(jìn)程)的緊迫程度，因而不能保證緊迫性作業(yè)(進(jìn)程)會(huì)被及時(shí)處理由于作業(yè)(進(jìn)程)的長(zhǎng)短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會(huì)有意或無(wú)意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。12/17/202245先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法SJ(P)F調(diào)度算法也存在不容忽視調(diào)度算法先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法12/17/202246調(diào)度算法先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法12/17/202246高優(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)度算法③12/17/202247高優(yōu)先權(quán)優(yōu)先（HPF，HighestPriorityFi高優(yōu)先權(quán)優(yōu)先（HPF，HighestPriorityFirst）調(diào)度算法優(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)中12/17/202248高優(yōu)先權(quán)優(yōu)先（HPF，HighestPriorityFi高優(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)中12/17/202249高優(yōu)先權(quán)優(yōu)先（HPF—HighestPriorityFi高優(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)12/17/202250高優(yōu)先權(quán)優(yōu)先調(diào)度算法優(yōu)先權(quán)的類型12/17/202250高優(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ù)來(lái)表示的，例如，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ì)資源的需求用戶要求12/17/202251高優(yōu)先權(quán)優(yōu)先調(diào)度算法優(yōu)先權(quán)的類型12/17/202251確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下三個(gè)方面：進(jìn)程類型。系統(tǒng)進(jìn)程的優(yōu)先權(quán)高于一般用戶進(jìn)程。

(2)進(jìn)程對(duì)資源的需求。如進(jìn)程的估計(jì)執(zhí)行時(shí)間及內(nèi)存需要量少的進(jìn)程，應(yīng)賦予較高的優(yōu)先權(quán)。(3)用戶要求。由用戶進(jìn)程的緊迫程度和用戶所付費(fèi)用的多少來(lái)確定優(yōu)先權(quán)。

12/17/202252確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下三個(gè)方面：12/17/20225高優(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ù)來(lái)表示的，例如，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)程不利！！短進(jìn)程優(yōu)先對(duì)長(zhǎng)進(jìn)程不利??！12/17/202253高優(yōu)先權(quán)優(yōu)先調(diào)度算法優(yōu)先權(quán)的類型問題：用戶將優(yōu)先權(quán)設(shè)的較高，高優(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ī)12/17/202254高優(yōu)先權(quán)優(yōu)先調(diào)度算法動(dòng)態(tài)優(yōu)先權(quán)12/17/202254進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間靜態(tài)優(yōu)先權(quán)開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均靜態(tài)優(yōu)先權(quán)，非搶占式（1為高優(yōu)先權(quán)）高優(yōu)先權(quán)優(yōu)先調(diào)度算法04A413B225C332D544E1044148418111010/311161414/516181515/29.42.93考慮一下?lián)屨际?，情況如何？12/17/202255進(jìn)程到達(dá)服務(wù)靜態(tài)優(yōu)先權(quán)開始完成周轉(zhuǎn)帶權(quán)周平均靜態(tài)優(yōu)先權(quán)，非搶高優(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ù)此，又可表示為④12/17/202256高優(yōu)先權(quán)優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法（HRF）④12/1高優(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è)有利——是先來(lái)先服務(wù)——對(duì)長(zhǎng)作業(yè)有利12/17/202257高優(yōu)先權(quán)優(yōu)先調(diào)度算法對(duì)HRF的小結(jié)缺點(diǎn)：要進(jìn)行響應(yīng)比計(jì)算，增調(diào)度算法先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法12/17/202258調(diào)度算法先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法12/17/202258基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法簡(jiǎn)單的時(shí)間片輪轉(zhuǎn)法(RR—RoundRobin)系統(tǒng)將所有的就緒進(jìn)程按先來(lái)先服務(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)⑤12/17/202259基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法簡(jiǎn)單的時(shí)間片輪轉(zhuǎn)法(RR—Round基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均ABCDEABCDEABCEACEC05101518t04A03B05C02D04E012349121517181515/41111/31616/566/21313/412.22.12若到達(dá)時(shí)間為0、1、2、3、4，又如何？12/17/202260基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)基于時(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能力

12/17/202261基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法分時(shí)系統(tǒng)中常用時(shí)間片輪轉(zhuǎn)法12/173.2.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法2.時(shí)間片大小的確定（1）系統(tǒng)對(duì)響應(yīng)時(shí)間的要求

數(shù)目N和時(shí)間片q成反比，即T=Nq，因此在進(jìn)程數(shù)一定時(shí)，作為分時(shí)系統(tǒng)首先就是必須滿足系統(tǒng)對(duì)響應(yīng)時(shí)間的要求。時(shí)間片的長(zhǎng)短將正比于系統(tǒng)所要求的響應(yīng)時(shí)間。（2）就緒隊(duì)列中進(jìn)程的數(shù)目

在分時(shí)系統(tǒng)中，就緒隊(duì)列上所有的進(jìn)程數(shù)，是隨著在終端上機(jī)的用戶數(shù)目而改變的，但系統(tǒng)應(yīng)保證，當(dāng)所有終端用戶上機(jī)時(shí)，獲得較好的響應(yīng)時(shí)間。（3）系統(tǒng)的處理能力

系統(tǒng)的處理能力是必須保證用戶鍵入的常用命令能在一個(gè)時(shí)間片內(nèi)處理完畢，否則將無(wú)法保證得到滿意的響應(yīng)時(shí)間，而且會(huì)使平均周轉(zhuǎn)時(shí)間及帶權(quán)周轉(zhuǎn)時(shí)間都很長(zhǎng)。

12/17/2022623.2.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法2.2.多級(jí)隊(duì)列調(diào)度前臺(tái)的就緒隊(duì)列是交互性作業(yè)的進(jìn)程，采用時(shí)間片輪轉(zhuǎn)。后臺(tái)的就緒隊(duì)列是批處理作業(yè)的進(jìn)程，采用優(yōu)先權(quán)或短作業(yè)優(yōu)先算法。調(diào)度方式有兩種：(1)優(yōu)先調(diào)度前臺(tái)，若前臺(tái)無(wú)可運(yùn)行進(jìn)程，才調(diào)度后臺(tái)。(2)分配占用CPU的時(shí)間比例，如：前臺(tái)80%，后臺(tái)20%。3.2.3基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法⑥12/17/2022632.多級(jí)隊(duì)列調(diào)度前臺(tái)的就緒隊(duì)列是交互性作業(yè)的進(jìn)程，采用時(shí)間基于時(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í)間片就愈小。例如，第二個(gè)隊(duì)列的時(shí)間片要比第一個(gè)隊(duì)列的時(shí)間片長(zhǎng)一倍，……，第i+1個(gè)隊(duì)列的時(shí)間片要比第i個(gè)隊(duì)列的時(shí)間片長(zhǎng)一倍⑦12/17/202264基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法⑦12/17/就緒隊(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ā)生，則回到原來(lái)的就緒隊(duì)列12/17/202265就緒隊(duì)列1基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法就緒隊(duì)列2就緒隊(duì)列3就緒隊(duì)基于時(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ì)列的末尾12/17/202266基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法注意12/17/202266基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法的性能終端型作業(yè)用戶終端型作業(yè)用戶所提交的作業(yè)多屬于交互型作業(yè)，通常較小，系統(tǒng)只要能使這些作業(yè)在第一隊(duì)列所規(guī)定的時(shí)間片內(nèi)完成即可短批處理作業(yè)用戶若在第1隊(duì)列中執(zhí)行一個(gè)時(shí)間片即可完成，便可獲得與終端型作業(yè)一樣的響應(yīng)時(shí)間如在第一個(gè)隊(duì)列中不能完成，只需在第2、3隊(duì)列中各執(zhí)行一個(gè)時(shí)間片長(zhǎng)批處理作業(yè)用戶長(zhǎng)作業(yè)將依次在第1，2，3…，n隊(duì)列中執(zhí)行，最終按輪轉(zhuǎn)方式運(yùn)行12/17/202267基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法的性能12/17進(jìn)程調(diào)度的時(shí)機(jī)當(dāng)一個(gè)進(jìn)程運(yùn)行完畢或由于某種錯(cuò)誤而終止運(yùn)行當(dāng)一個(gè)進(jìn)程在運(yùn)行中處于等待狀態(tài)（等待I/O）分時(shí)系統(tǒng)中時(shí)間片到當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒（可搶占式）例如：新創(chuàng)建一個(gè)進(jìn)程，一個(gè)阻塞進(jìn)程變成就緒在進(jìn)程通信中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語(yǔ)操作（P操作，阻塞原語(yǔ)，喚醒原語(yǔ)）12/17/202268進(jìn)程調(diào)度的時(shí)機(jī)當(dāng)一個(gè)進(jìn)程運(yùn)行完畢或由于某種錯(cuò)誤而終止運(yùn)行12何時(shí)切換進(jìn)程只要OS取得對(duì)CPU的控制，進(jìn)程切換就可能發(fā)生:超級(jí)用戶調(diào)用來(lái)自程序的顯式請(qǐng)求(如：打開文件)，該進(jìn)程通常會(huì)被阻塞陷阱最末一條指令導(dǎo)致出錯(cuò)，會(huì)引起進(jìn)程移至退出狀態(tài)中斷外部因素影響當(dāng)前指令的執(zhí)行，控制被轉(zhuǎn)移至IH（中斷處理程序）12/17/202269何時(shí)切換進(jìn)程只要OS取得對(duì)CPU的控制，進(jìn)程切換就可能發(fā)生:引起進(jìn)程調(diào)度的原因正在執(zhí)行的進(jìn)程執(zhí)行完畢或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；執(zhí)行中的進(jìn)程因提出I/O請(qǐng)求而暫停執(zhí)行；在進(jìn)程通信或同步過(guò)程中執(zhí)行了某種原語(yǔ)操作如P操作、阻塞、掛起原語(yǔ)等；在可剝奪式調(diào)度中，有比當(dāng)前進(jìn)程優(yōu)先權(quán)更高的進(jìn)程進(jìn)入就緒隊(duì)列；在時(shí)間片輪轉(zhuǎn)法中，時(shí)間片完。通常系統(tǒng)是按先來(lái)先服務(wù)或優(yōu)先權(quán)形式來(lái)組織調(diào)度隊(duì)列。12/17/202270引起進(jìn)程調(diào)度的原因正在執(zhí)行的進(jìn)程執(zhí)行完畢或因發(fā)生某事件而不能進(jìn)程調(diào)度算法—優(yōu)先權(quán)、搶占式其中，RQ為就緒隊(duì)列指針，EP為運(yùn)行隊(duì)列指針。12/17/202271進(jìn)程調(diào)度算法—優(yōu)先權(quán)、搶占式其中，RQ為就緒隊(duì)列指針，EP為TheEnd12/17/202272TheEnd12/17/202272aI7F3C0y)v&s#pXmUiRfNcK9H5E2B+x(u$rZoWkThQeMbJ7G4D1z-w*t!qYmVjSgOdLaI6F3B0y)v%s#pXlUiQfNcK8H5E2A+x(u$rZnWkThPeMbJ7G4C1z-w&t!qYmVjRgOdL9I6F3B0y(v%s#oXlUiQfNbK8H5D2A+x*u$qZnWkShPeMaJ7F4C1z)w&t!pYmVjRgOcL9I6E3B0y(v%r#oXlTiQfNbK8G5D2A-x*u$qZnVkShPdMaJ7F4C0z)w&s!pYmUjRfOcL9H6E3B+y(u%r#oWlTiQeNbJ8G5D1A-x*t$qZnVkSgPdMaI7F4C0z)v&s!pXmUjRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G4D1A-w*t$qYnVjSgPdLaI7F3C0y)v&s#pXmUiRfOcK9H5E2B+x(u%rZoWkThQeMbJ8G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v%s#pXlUiRfNcK8H5E2A+x(u$rZnWkThPeMbJ7G4D1z-w&t!qYmVjSgOdL9I6F3B0y)v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z)w&t!pYmVjRgOcL9I6E3B0y(v%r#oXlTiQfNbK8H5D2A-x*u$qZnWkShPdMaJ7F4C1z)w&s!pYmUjRgOcL9H6E3B+y(v%r#oWlTiQeNbK8G5D1A-x*t$qZnVkSgPdMaI7F4C0z)w&s!pXmUjRfOcL9H6E2B+y(u%r#oWlThQeNbJ8G5D1A-w*t$qYnVkSgPdLaI7F3C0z)v&s#pXmUiRfOcK9H5E2B+x(u%rZoWkThQeMbJ8G4D1A-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXlUiRfNcK9H5E2A+x(u$rZoWkThPeMbJ7G4D1z-w&t!qYmVjOcK9H6E2B+x(u%rZoWlThQeMbJ8G4D1A-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXlUiRfNcK9H5E2A+x(u$rZoWkThPeMbJ7G4D1z-w&t!qYmVjSgOdLaI6F3B0y)v%s#pXlUiQfNcK8H5E2A+x*u$rZnWkThPeMaJ7G4C1z-w&t!pYmVjRgOdL9I6E3B0y(v%s#oXlTiQfNbK8H5D2A+x*u$qZnWkShPeMaJ7F4C1z)w&t!pYmUjRgOcL9I6E3B+y(v%r#oXlTiQeNbK8G5D2A-x*t$qZnVkShPdMaI7F4C0z)w&s!pYmUjRfOcL9H6E3B+y(u%r#oWlTiQeNbJ8G5D1A-x*t$qYnVkSgPdMaI7F3C0z)v&s!pXmUiRfOcK9H6E2B+x(u%rZoWlThQeMbJ8G4D1A-w*t$qYnVjSgPdLaI7F3C0y)v&s#pXmUiRfNcK9H5E2B+x(u$rZoWkThQeMbJ7G4D1z-w*t!qYmVjSgOdLaI6F3B0y)v%s#pXlUiRfNcK8H5E2A+x(u$rZnWkThPeMbJ7G4C1z-w&t!qYmVjRgOdL9I6F3B0y(v%s#oXlUiQfNbK8H5D2A+x*u$qZnWkShPeMaJ7G4C1z)w&t!pYmVjRgOcL9I6E3B0y(v%r#oXlTiQfNbK8G5D2A-x*u$qZnVkShPdMaJ7F4C0z)w&s!pYmUjRfOcL9H6E3B+y(u%r#oWlTiQeNbK8G5D1A-x*t$qZnVkSgPdMaI7F4C0z)v&s!pXmUjRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G4D1A-w*t$qYnVjSgPdLaI7F3C0z)v&s#pXmUiRfOcK9H5E2B+x(u%rZoWkThQeMbJ8G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v%s#pXlUiRfNcK8H5E2A+x(u$rZnWkThPeMbJ7G4D1z-w&t!qYmVjSgOdL9I6F3B0y)v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z)w&t!pYmVjRgOcL9I6E3B0y(v%s#oXlTiQfNbK8H5D2A-x*u$qZnWOdL9I6F3B0y)v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z-w&t!pYmVjRgOdL9I6E3B0y(v%s#oXlTiQfNbK8H5D2A-x*u$qZnWkShPdMaJ7F4C1z)w&s!pYmUjRgOcL9H6E3B+y(v%r#oWlTiQeNbK8G5D2A-x*t$qZnVkShPdMaI7F4C0z)w&s!pXmUjRfOcL9H6E2B+y(u%r#oWlThQeNbJ8G5D1A-w*t$qYnVkSgPdLaI7F3C0z)v&s!pXmUiRfOcK9H6E2B+x(u%rZoWlThQeMbJ8G4D1A-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXlUiRfNcK9H5E2A+x(u$rZoWkThPeMbJ7G4D1z-w*t!qYmVjSgOdLaI6F3B0y)v%s#pXlUiQfNcK8H5E2A+x*u$rZnWkThPeMaJ7G4C1z-w&t!pYmVjRgOdL9I6E3B0y(v%s#oXlUiQfNbK8H5D2A+x*u$qZnWkShPeMaJ7F4C1z)w&t!pYmUjRgOcL5E2A+x*u$rZnWkThPeMaJ7G4C1z-w&t!pYmVjRgOdL9I6F3B0y(v%s#oXlUiQfNbK8H5D2A+x*u$qZnWkShPeMaJ7F4C1z)w&t!pYmUjRgOcL9I6E3B+y(v%r#oXlTiQeNbK8G5D2A-x*u$qZnVkShPdMaJ7F4C0z)w&s!pYmUjRfOcL9H6E3B+y(u%r#oWlTiQeNbJ8G5D1A-x*t$qYnVkSgPdMaI7F3C0z)v&s!pXmUjRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G4D1A-w*t$qYnVjSgPdLaI7F3C0y)v&s#pXmUiRfNcK9H5E2B+x(u$rZoWkThQeMbJ7G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v%s#pXlUiRfNcK8H5E2A+x(u$rZnWkThPeMbJ7G4C1z-w&t!qYmVjRgOdL9I6F3B0y(v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z)w&t!pYmVjRgOcL9I6E3B0y(v%r#oXlTiQfNbK8G5D2A-x*u$qZnVkShPdMaJ7F4C1z)w&s!pYmUjRgOcL9H6E3B+y(v%r#oWlTiQeNbK8C1z)w&t!pYmVjRgOcL9I6E3B0y(v%r#oXlTiQfNbK8G5D2A-x*u$qZnWkShPdMaJ7F4C1z)w&s!pYmUjRgOcL9H6E3B+y(v%r#oWlTiQeNbK8G5D1A-x*t$qZnVkSgPdMaI7F4C0z)v&s!pXmUjRfOcL9H6E2B+y(u%r#oWlThQeNbJ8G5D1A-w*t$qYnVkSgPdLaI7F3C0z)v&s#pXmUiRfOcK9H5E2B+x(u%rZoWkThQeMbJ8G4D1z-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXlUiRfNcK9H5E2A+x(u$rZoWkThPeMbJ7G4D1z-w&t!qYmVjSgOdL9I6F3B0y)v%s#oXlUiQfNcK8H5E2A+x*u$rZnWkThPeMaJ7G4C1z-w&t!pYmVjRgOdL9I6E3B0y(v%s#oXlTiQfNb4D1z-w&t!qYmVjSgOdL9I6F3B0y)v%s#pXlUiQfNcK8H5E2A+x*u$rZnWkThPeMaJ7G4C1z-w&t!pYmVjRgOdL9I6E3B0y(v%s#oXlTiQfNbK8H5D2A-x*u$qZnWkShPeMaJ7F4C1z)w&t!pYmUjRgOcL9I6E3B+y(v%r#oXlTiQeNbK8G5D2A-x*t$qZnVkShPdMaI7F4C0z)w&s!pXmUjRfOcL9H6E3B+y(u%r#oWlTiQeNbJ8G5D1A-x*t$qYnVkSgPdMaI7F3C0z)v&s!pXmUiRfOcK9H6E2B+x(u%rZoWlThQeMbJ8G4D1A-w*t!qYnVjSgPdLaI7F3C0y)v&s#pXmUiRfN8G5D1A-x*t$qYnVkSgPdMaI7F3C0z)v&s!pXmUiRfOcK9H6E2B+x(u%rZoWlThQeNbJ8G4D1A-w*t$qYnVjSgPdLaI7F3C0y)v&s#pXmUiRfNcK9H5E2B+x(u$rZoWkThQeMbJ7G4D1z-w*t!qYmVjSgOdLaI6F3B0y)v%s#pXlUiRfNcK8H5E2A+x(u$rZnWkThPeMbJ7G4C1z-w&t!qYmVjRgOdL9I6F3B0y(v%s#oXlUiQfNbK8H5D2A+x*u$qZnWkShPeMaJ7G4C1z)w&t!pYmVjRgOcL9I6E3B0y(v%r#oXlTiQfNbK8G5D2A-x*u$qZnVkShPdMaJ7F4C0z)w&s!pYmUjRfOcL9H6E3B+y(v%r#oWlTiQeNbK8G5D1A-x*t$qZnVkSgPdMaI7F4C0z)v&s!pXmUjRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G4D1A-w*t$qYnVjSgPdLaIB+y(v%r#oWlTiQeNbK8G5D1A-x*t$qZnVkSgPdMaI7F4C0z)v&s!pXmUjRfOcK9H6E2B+y(u%rZoWlThQeNbJ8G5D1A-w*t$qYnVkSgPdLaI7F3C0z)v&s#pXmUiRfOcK9H5E2B+x(u%rZoWkThQeMbJ8G4D1z-w*t!qYnVjSgOdLaI6F3C0y)v%s#pXlUiRfNcK9H5E2A+x(u$rZoWkThPeMbJ7G4D1z-w&t!qYmVjSgOdL9I6F3B0y)v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkShPeMaJ7G4C1z-w&t!pYmVjRgOdL5E2A+x(u$rZoWkThPeMbJ7G4D1z-w&t!qYmVjSgOdL9I6F3B0y)v%s#oXlUiQfNcK8H5D2A+x*u$rZnWkThPeMaJ7G4C1z-w&t!pYmVjRgOdL9I6E3B0y(v%s#oXlTiQfNbK8H5D2A-x*u$qZnWkShPdMaJ7F4C1z)w&s!pYmUjRgOcL9I6E3B+y(v%r#oXlTiQeNbK8G5D2A-x*t$qZnVkShPdMaI7F4C0z)w&s!pXmUjRfOcL9H6E2B+y(u%r#oWlThQeNbJ8G5D1A-x*t$qYnVkSgPdMaI7F3C0z)v&s!pXmUiRfOcK9H6E2B+x(u%rZoWlThQeMbJ8G4D1A-w*t!qYnVjSgPdLaI6F3C0y)v&s#pXleNbJ8G5D1A-x*t$qYnVkSgPdMaI7F3C0z)v&s!pXmUiRfOcK9H6E2B+x(aI7F3C0y)v&s#pXmUiRfNcK9H5E2B+第三章處理機(jī)調(diào)度與死鎖操作系統(tǒng)劉剛12/17/202274第三章處理機(jī)調(diào)度與死鎖操作系統(tǒng)劉剛12/17/2022第三章處理機(jī)調(diào)度與死鎖重點(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ì)算過(guò)程

銀行家算法

12/17/202275第三章處理機(jī)調(diào)度與死鎖重點(diǎn)12/17/20222第三章處理機(jī)調(diào)度與死鎖知識(shí)點(diǎn)處理機(jī)調(diào)度及調(diào)度算法多處理機(jī)環(huán)境下的進(jìn)程（線程）調(diào)度方式產(chǎn)生死鎖的原因和必要條件預(yù)防死鎖的方法，死鎖的檢測(cè)與解除銀行家算法12/17/202276第三章處理機(jī)調(diào)度與死鎖知識(shí)點(diǎn)12/17/20223第三章處理機(jī)調(dià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)度過(guò)程（進(jìn)程的上下文切換）12/17/202277第三章處理機(jī)調(diào)度與死鎖處理機(jī)是計(jì)算機(jī)系統(tǒng)中的重要資源分配處第三章處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度的基本概念調(diào)度算法實(shí)時(shí)調(diào)度多處理機(jī)系統(tǒng)中的調(diào)度產(chǎn)生死鎖的原因和必要條件預(yù)防死鎖的方法死鎖的檢測(cè)與解除12/17/202278第三章處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度的基本概念12/17/處理機(jī)調(diào)度的基本概念

高級(jí)、中級(jí)和低級(jí)調(diào)度進(jìn)程調(diào)度的任務(wù)確定算法的原則進(jìn)程調(diào)度方式調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則12/17/202279處理機(jī)調(diào)度的基本概念高級(jí)、中級(jí)和低級(jí)調(diào)度12/17/202處理機(jī)調(diào)度的基本概念作業(yè)是用戶在一次解題或一個(gè)事務(wù)處理過(guò)程中要求計(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)12/17/202280處理機(jī)調(diào)度的基本概念作業(yè)是用戶在一次解題或一個(gè)事務(wù)處理過(guò)程中運(yùn)行狀態(tài)處理機(jī)調(diào)度的基本概念后備狀態(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)換12/17/202281運(yùn)行狀態(tài)處理機(jī)調(diào)度的基本概念后備狀態(tài)完成狀態(tài)就緒阻塞執(zhí)行I/3.1處理機(jī)調(diào)度的基本概念3.1.1高級(jí)、中級(jí)和低級(jí)調(diào)度1.高級(jí)調(diào)度(HighScheduling)2.低級(jí)調(diào)度(LowLevelScheduling)3.中級(jí)調(diào)度(Intermediate-LevelScheduling)12/17/2022823.1處理機(jī)調(diào)度的基本概念3.1.1高級(jí)、中級(jí)和低級(jí)高級(jí)、中級(jí)和低級(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í)或天12/17/202283高級(jí)、中級(jí)和低級(jí)調(diào)度高級(jí)調(diào)度(HighScheduling高級(jí)、中級(jí)和低級(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)度算法先來(lái)先服務(wù)短作業(yè)優(yōu)先作業(yè)優(yōu)先權(quán)調(diào)度響應(yīng)比調(diào)度→周轉(zhuǎn)時(shí)間太長(zhǎng)→系統(tǒng)吞吐量太低適當(dāng)?shù)恼壑远嗟莱绦蚨龋杭丛试S多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行。周轉(zhuǎn)時(shí)間：從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時(shí)間間隔。吞吐量：是指在單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。12/17/202284高級(jí)、中級(jí)和低級(jí)調(diào)度在每次作業(yè)調(diào)度時(shí)，須決定：→周轉(zhuǎn)時(shí)間太長(zhǎng)高級(jí)、中級(jí)和低級(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í)做到高效12/17/202285高級(jí)、中級(jí)和低級(jí)調(diào)度低級(jí)調(diào)度12/17/202212高級(jí)、中級(jí)和低級(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ū)12/17/202286高級(jí)、中級(jí)和低級(jí)調(diào)度中級(jí)調(diào)度(Intermediate-Le處理機(jī)調(diào)度的基本概念

高級(jí)、中級(jí)和低級(jí)調(diào)度進(jìn)程調(diào)度的任務(wù)確定算法的原則進(jìn)程調(diào)度方式調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則12/17/202287處理機(jī)調(diào)度的基本概念高級(jí)、中級(jí)和低級(jí)調(diào)度12/17/20進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù)是控制、協(xié)調(diào)進(jìn)程對(duì)CPU的競(jìng)爭(zhēng),即按一定的調(diào)度算法從就緒隊(duì)列中選中一個(gè)進(jìn)程，把CPU的使用權(quán)交給被選中的進(jìn)程12/17/202288進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù)12/17/202215處理機(jī)調(diào)度的基本概念

高級(jí)、中級(jí)和低級(jí)調(diào)度進(jìn)程調(diào)度的任務(wù)

確定算法的原則進(jìn)程調(diào)度方式調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則12/17/202289處理機(jī)調(diào)度的基本概念高級(jí)、中級(jí)和低級(jí)調(diào)度12/17/20確定算法的原則具有公平性資源利用率高（特別是CPU利用率）在交互式系統(tǒng)情況下要追求響應(yīng)時(shí)間（越短越好）在批處理系統(tǒng)情況下要追求系統(tǒng)吞吐量12/17/202290確定算法的原則具有公平性12/17/202217處理機(jī)調(diào)度的基本概念

高級(jí)、中級(jí)和低級(jí)調(diào)度進(jìn)程調(diào)度的任務(wù)確定算法的原則

進(jìn)程調(diào)度方式調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則12/17/202291處理機(jī)調(diào)度的基本概念高級(jí)、中級(jí)和低級(jí)調(diào)度12/17/20進(jìn)程調(diào)度方式非搶占方式(Non-preemptiveMode)搶占方式(PreemptiveMode)12/17/202292進(jìn)程調(diào)度方式非搶占方式(Non-preemptiveMod進(jìn)程調(diào)度方式非搶占方式(Non-preemptiveMode)

當(dāng)某一進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，即使有某個(gè)更為重要或緊迫的進(jìn)程進(jìn)入就緒隊(duì)列，該進(jìn)程仍繼續(xù)執(zhí)行，直到其完成或發(fā)生某種事件而進(jìn)入完成或阻塞狀態(tài)時(shí)，才把處理機(jī)分配給更為重要或緊迫的進(jìn)程引起進(jìn)程調(diào)度的因素正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行執(zhí)行中的進(jìn)程因提出I/O請(qǐng)求而暫停執(zhí)行；在進(jìn)程通信或同步過(guò)程中執(zhí)行了某種原語(yǔ)操作，如wait、Block、Wakeup原語(yǔ)優(yōu)點(diǎn)：算法簡(jiǎn)單，系統(tǒng)開銷小缺點(diǎn)：緊急任務(wù)不能及時(shí)響應(yīng)；短進(jìn)程到達(dá)要等待長(zhǎng)進(jìn)程運(yùn)行結(jié)束12/17/202293進(jìn)程調(diào)度方式非搶占方式(Non-preemptiveMod進(jìn)程調(diào)度方式搶占方式(PreemptiveMode)

當(dāng)某一進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，若有某個(gè)更為重要或緊迫的進(jìn)程進(jìn)入就緒隊(duì)列，則立即暫停正在執(zhí)行的進(jìn)程，將處理機(jī)分配給這個(gè)更為重要或緊迫的進(jìn)程搶占式調(diào)度主要有以下原則優(yōu)先權(quán)原則允許高優(yōu)先權(quán)的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)短作業(yè)(進(jìn)程)優(yōu)先原則允許執(zhí)行時(shí)間短的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)時(shí)間片原則時(shí)間片用完后停止執(zhí)行，重新進(jìn)行調(diào)度，適用于分時(shí)系統(tǒng)

優(yōu)點(diǎn)：適于時(shí)間要求嚴(yán)格的實(shí)時(shí)系統(tǒng)缺點(diǎn)：調(diào)度算法復(fù)雜，系統(tǒng)開銷大12/17/202294進(jìn)程調(diào)度方式搶占方式(PreemptiveMode)優(yōu)點(diǎn)：處理機(jī)調(diào)度的基本概念

高級(jí)、中級(jí)和低級(jí)調(diào)度進(jìn)程調(diào)度的任務(wù)確定算法的原則進(jìn)程調(diào)度方式

調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則12/17/202295處理機(jī)調(diào)度的基本概念高級(jí)、中級(jí)和低級(jí)調(diào)度12/17/20調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型12/17/202296調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型12/17/20222調(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í)行期間因某事件而阻塞12/17/202297調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型12/17/20222調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列進(jìn)程調(diào)度CPU進(jìn)程完成等待事件交互用戶事件出現(xiàn)時(shí)間片完12/17/202298調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列進(jìn)程調(diào)調(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ì)列提高效率12/17/202299調(diào)度隊(duì)列模型具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型12/17/20調(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ì)列塞112/17/2022100調(diào)度隊(duì)列模型進(jìn)程調(diào)度CPU進(jìn)程完成時(shí)間片完就緒隊(duì)列…12等待調(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)事件出現(xiàn)CPU12/17/2022101調(diào)度隊(duì)列模型同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列進(jìn)程調(diào)度就處理機(jī)調(diào)度的基本概念

高級(jí)、中級(jí)和低級(jí)調(diào)度進(jìn)程調(diào)度的任務(wù)確定算法的原則進(jìn)程調(diào)度方式調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則如果你是用戶，你希望系統(tǒng)如何為你服務(wù)，如何考慮？？如果你是調(diào)度者，從系統(tǒng)整體角度出發(fā)，應(yīng)如何考慮？？12/17/2022102處理機(jī)調(diào)度的基本概念高級(jí)、中級(jí)和低級(jí)調(diào)度如果你是用戶，你3.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1.面向用戶的準(zhǔn)則2.面向系統(tǒng)的準(zhǔn)則12/17/20221033.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1.面向用戶3.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1.面向用戶的準(zhǔn)則(1)周轉(zhuǎn)時(shí)間短。

(2)響應(yīng)時(shí)間快。(3)截止時(shí)間的保證。(4)優(yōu)先權(quán)準(zhǔn)則。12/17/20221043.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1.面向用戶選擇調(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í)間則可表示為:12/17/2022105選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向用戶的準(zhǔn)則帶權(quán)周轉(zhuǎn)時(shí)間：選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向用戶的準(zhǔn)則響應(yīng)時(shí)間快響應(yīng)時(shí)間是指從用戶通過(guò)鍵盤提交一個(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)12/17/2022106選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向用戶的準(zhǔn)則12/17/2選擇調(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)度方式12/17/2022107選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向用戶的準(zhǔn)則12/17/2選擇調(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)如何？12/17/2022108選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則面向系統(tǒng)的準(zhǔn)則基于這樣的準(zhǔn)則第三章處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度的基本概念

調(diào)度算法

實(shí)時(shí)調(diào)度多處理機(jī)系統(tǒng)中的調(diào)度產(chǎn)生死鎖的原因和必要條件預(yù)防死鎖的方法死鎖的檢測(cè)與解除12/17/2022109第三章處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度的基本概念12/17/2調(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)度，有些兩者皆可12/17/2022110調(diào)度算法在OS中調(diào)度的實(shí)質(zhì)是一種資源分配，因而調(diào)度算法是指：調(diào)度算法

先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法12/17/2022111調(diào)度算法先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法12/17/202238先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法先來(lái)先服務(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ù)語(yǔ)到達(dá)時(shí)間、服務(wù)時(shí)間、開始時(shí)間完成時(shí)間、等待時(shí)間周轉(zhuǎn)時(shí)間：完成時(shí)間-到達(dá)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間①12/17/2022112先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法先來(lái)先服務(wù)(FCFS)/先進(jìn)先出(先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間平均04A13B25C32D44E044476先來(lái)先服務(wù)（先進(jìn)先出）：712101214111418141225.53.592.8AAAABBBCCCCCDDEEEE05101518t12/17/2022113先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法先來(lái)先服務(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)12/17/2022114先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法先來(lái)先服務(wù)（先進(jìn)先出）優(yōu)缺點(diǎn)比先來(lái)先服務(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)度②12/17/2022115先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P先來(lái)先服務(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/540/52.1AAAABBBCCCCCDDEEEE05101518t12/17/2022116先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始時(shí)間完成FCFS/SJF調(diào)度算法的性能先來(lái)先服務(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í)間明顯改善12/17/2022117FCFS/SJF調(diào)度算法的性能先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法SJ先來(lái)先服務(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)度程序總是