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

1、Operating SystemOperating SystemPage 12021-7-9 Operating SystemOperating SystemPage 22021-7-9 q知識(shí)點(diǎn)知識(shí)點(diǎn) v處理機(jī)調(diào)度及調(diào)度算法處理機(jī)調(diào)度及調(diào)度算法 v多處理機(jī)環(huán)境下的進(jìn)程（線程）調(diào)度方式多處理機(jī)環(huán)境下的進(jìn)程（線程）調(diào)度方式 v產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件 v預(yù)防死鎖的方法，死鎖的檢測(cè)與解除預(yù)防死鎖的方法，死鎖的檢測(cè)與解除 v銀行家算法銀行家算法 Operating SystemOperating SystemPage 32021-7-9 q重點(diǎn)重點(diǎn) v掌握掌握進(jìn)程調(diào)度進(jìn)程調(diào)度

2、算法，各適用于何種情況算法，各適用于何種情況 v理解常用的幾種理解常用的幾種實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度算法算法 v理解產(chǎn)生理解產(chǎn)生死鎖死鎖的原因的原因 v掌握掌握銀行家算法銀行家算法避免避免死鎖死鎖 q難點(diǎn)難點(diǎn) v多道程序設(shè)計(jì)中的各種調(diào)度算法多道程序設(shè)計(jì)中的各種調(diào)度算法 v響應(yīng)比高者優(yōu)先調(diào)度算法的計(jì)算過(guò)程響應(yīng)比高者優(yōu)先調(diào)度算法的計(jì)算過(guò)程 v銀行家算法銀行家算法 Operating SystemOperating SystemPage 42021-7-9 q處理機(jī)是計(jì)算機(jī)系統(tǒng)中的處理機(jī)是計(jì)算機(jī)系統(tǒng)中的重要資源重要資源 q在多道程序環(huán)境下，進(jìn)程數(shù)目通常在多道程序環(huán)境下，進(jìn)程數(shù)目通常多于處多于處 理機(jī)的數(shù)目理

3、機(jī)的數(shù)目 q系統(tǒng)必須按一定方法系統(tǒng)必須按一定方法動(dòng)態(tài)地動(dòng)態(tài)地把處理機(jī)把處理機(jī)分配分配 給給就緒隊(duì)列中的一個(gè)進(jìn)程就緒隊(duì)列中的一個(gè)進(jìn)程 q處理機(jī)處理機(jī)利用率和系統(tǒng)性能利用率和系統(tǒng)性能（吞吐量、響應(yīng)（吞吐量、響應(yīng) 時(shí)間）在很大程度上時(shí)間）在很大程度上取決于取決于處理機(jī)處理機(jī)調(diào)度調(diào)度 分配處理機(jī)的任務(wù)是由進(jìn)程調(diào)度程序完成分配處理機(jī)的任務(wù)是由進(jìn)程調(diào)度程序完成 的。它是操作系統(tǒng)設(shè)計(jì)的中心問(wèn)題之一。的。它是操作系統(tǒng)設(shè)計(jì)的中心問(wèn)題之一。 WHAT：按什么原則分配：按什么原則分配CPU進(jìn)程調(diào)度算法進(jìn)程調(diào)度算法 WHEN：何時(shí)分配：何時(shí)分配CPU 進(jìn)程調(diào)度的時(shí)機(jī)進(jìn)程調(diào)度的時(shí)機(jī) HOW：如何分配：如何分配CPU C

4、PU調(diào)度過(guò)程（進(jìn)程調(diào)度過(guò)程（進(jìn)程 的上下文切換）的上下文切換） Operating SystemOperating SystemPage 52021-7-9 q高級(jí)調(diào)度高級(jí)調(diào)度 q低級(jí)調(diào)度低級(jí)調(diào)度 q中級(jí)調(diào)度中級(jí)調(diào)度 Operating SystemOperating SystemPage 62021-7-9 q作業(yè)：作業(yè)：是用戶在一次解題或一個(gè)事務(wù)處理是用戶在一次解題或一個(gè)事務(wù)處理 過(guò)程中過(guò)程中要求計(jì)算機(jī)系統(tǒng)所做工作的集合要求計(jì)算機(jī)系統(tǒng)所做工作的集合， 包括用戶程序、所需的數(shù)據(jù)及命令等；包括用戶程序、所需的數(shù)據(jù)及命令等； q作業(yè)的狀態(tài)：作業(yè)的狀態(tài)：一個(gè)作業(yè)進(jìn)入系統(tǒng)到運(yùn)行結(jié)一個(gè)作業(yè)進(jìn)入系統(tǒng)到運(yùn)

5、行結(jié) 束，一般需要經(jīng)歷收容、運(yùn)行、完成三個(gè)束，一般需要經(jīng)歷收容、運(yùn)行、完成三個(gè) 階段，與之相對(duì)應(yīng)的是作業(yè)的三種狀態(tài)：階段，與之相對(duì)應(yīng)的是作業(yè)的三種狀態(tài)： v后備狀態(tài)后備狀態(tài) v運(yùn)行狀態(tài)運(yùn)行狀態(tài) v完成狀態(tài)完成狀態(tài) Operating SystemOperating SystemPage 72021-7-9 q作業(yè)步：作業(yè)步：在作業(yè)運(yùn)行期間，每個(gè)作業(yè)都必修經(jīng)在作業(yè)運(yùn)行期間，每個(gè)作業(yè)都必修經(jīng) 過(guò)若干個(gè)相互獨(dú)立，又相互關(guān)聯(lián)的順序加工步驟過(guò)若干個(gè)相互獨(dú)立，又相互關(guān)聯(lián)的順序加工步驟 才能得到結(jié)果，把其中的每一個(gè)加工步驟稱(chēng)為作才能得到結(jié)果，把其中的每一個(gè)加工步驟稱(chēng)為作 業(yè)步。業(yè)步。 q作業(yè)控制塊：作業(yè)控制

6、塊：為了管理和調(diào)度作業(yè)，系統(tǒng)為每為了管理和調(diào)度作業(yè)，系統(tǒng)為每 個(gè)作業(yè)設(shè)置了一個(gè)作業(yè)控制塊（個(gè)作業(yè)設(shè)置了一個(gè)作業(yè)控制塊（JCBJCB），它記錄），它記錄 該作業(yè)的有關(guān)信息。不同系統(tǒng)的該作業(yè)的有關(guān)信息。不同系統(tǒng)的JCBJCB的組成內(nèi)容的組成內(nèi)容 有所區(qū)別，主要包括：作業(yè)名、資源要求、資源有所區(qū)別，主要包括：作業(yè)名、資源要求、資源 使用情況、類(lèi)型級(jí)別、狀態(tài)等。使用情況、類(lèi)型級(jí)別、狀態(tài)等。 Operating SystemOperating SystemPage 82021-7-9 運(yùn)行狀態(tài)運(yùn)行狀態(tài) 后備狀態(tài)后備狀態(tài) 完成狀態(tài)完成狀態(tài) 就緒就緒 阻塞阻塞 執(zhí)行執(zhí)行 I/O完成完成I/O請(qǐng)求請(qǐng)求 時(shí)間片

7、完時(shí)間片完 作業(yè)作業(yè) 注冊(cè)注冊(cè) 作業(yè)作業(yè) 調(diào)度調(diào)度 進(jìn)程進(jìn)程 調(diào)度調(diào)度 終止終止 作業(yè)作業(yè) q作業(yè)作業(yè)狀態(tài)間轉(zhuǎn)換狀態(tài)間轉(zhuǎn)換 Operating SystemOperating SystemPage 92021-7-9 q高級(jí)調(diào)度高級(jí)調(diào)度(High Scheduling) 作業(yè)調(diào)度作業(yè)調(diào)度或或長(zhǎng)程調(diào)度長(zhǎng)程調(diào)度（Long-Term Scheduling） v主要任務(wù)是按一定的原則對(duì)外存上處于后備主要任務(wù)是按一定的原則對(duì)外存上處于后備 狀態(tài)的作業(yè)進(jìn)行選擇，給選中的作業(yè)狀態(tài)的作業(yè)進(jìn)行選擇，給選中的作業(yè)分配分配內(nèi)內(nèi) 存、輸入存、輸入/ /輸出設(shè)備等輸出設(shè)備等必要的資源必要的資源，并，并建立建立相相 應(yīng)的

8、應(yīng)的進(jìn)程進(jìn)程，放入放入就緒就緒隊(duì)列隊(duì)列，以使該作業(yè)的進(jìn)，以使該作業(yè)的進(jìn) 程獲得競(jìng)爭(zhēng)處理機(jī)的權(quán)利程獲得競(jìng)爭(zhēng)處理機(jī)的權(quán)利 v也稱(chēng)為也稱(chēng)為接納調(diào)度（接納調(diào)度（Admission SchedulingAdmission Scheduling） v高級(jí)調(diào)度的時(shí)間尺度通常是分鐘、小時(shí)或天高級(jí)調(diào)度的時(shí)間尺度通常是分鐘、小時(shí)或天 Operating SystemOperating SystemPage 102021-7-9 在每次作業(yè)調(diào)度時(shí)，須決定：在每次作業(yè)調(diào)度時(shí)，須決定： v接納多少個(gè)作業(yè)接納多少個(gè)作業(yè) 即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行，取決于即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行，取決于多多 道程序度道程序度

9、（Degree of Multiprogramming） 作業(yè)太多作業(yè)太多 服務(wù)質(zhì)量下降服務(wù)質(zhì)量下降 作業(yè)太少作業(yè)太少 資源利用率低資源利用率低 v接納哪些作業(yè)接納哪些作業(yè) 取決于作業(yè)調(diào)度算法取決于作業(yè)調(diào)度算法 先來(lái)先服務(wù)；短作業(yè)優(yōu)先；先來(lái)先服務(wù)；短作業(yè)優(yōu)先； 作業(yè)優(yōu)先權(quán)調(diào)度；響應(yīng)比調(diào)度作業(yè)優(yōu)先權(quán)調(diào)度；響應(yīng)比調(diào)度 系統(tǒng)吞吐量太低 適當(dāng)?shù)恼壑赃m當(dāng)?shù)恼壑?q高級(jí)調(diào)度高級(jí)調(diào)度(High Scheduling) 周轉(zhuǎn)時(shí)間太長(zhǎng) Operating SystemOperating SystemPage 112021-7-9 q 低級(jí)調(diào)度低級(jí)調(diào)度 進(jìn)程調(diào)度進(jìn)程調(diào)度或或短程調(diào)度短程調(diào)度（Short-Term

10、Scheduling） v主要任務(wù)是按照某種主要任務(wù)是按照某種策略和方法策略和方法選取選取一個(gè)處一個(gè)處 于于就緒就緒狀態(tài)的進(jìn)程，將處理機(jī)狀態(tài)的進(jìn)程，將處理機(jī)分配分配給它給它 v常見(jiàn)的低級(jí)調(diào)度有常見(jiàn)的低級(jí)調(diào)度有非搶占式非搶占式和和搶占式搶占式兩種兩種 v低級(jí)調(diào)度的時(shí)間尺度通常是低級(jí)調(diào)度的時(shí)間尺度通常是毫秒級(jí)毫秒級(jí)的。由于的。由于 低級(jí)調(diào)度算法的低級(jí)調(diào)度算法的頻繁使用頻繁使用，要求在實(shí)現(xiàn)時(shí)做，要求在實(shí)現(xiàn)時(shí)做 到到高效高效 Operating SystemOperating SystemPage 122021-7-9 q 中級(jí)調(diào)度中級(jí)調(diào)度(Intermediate-Level Scheduling)

11、 中程調(diào)度中程調(diào)度(Medium-Term Scheduling) v引入目的引入目的是為了提高是為了提高內(nèi)存利用率內(nèi)存利用率和和系統(tǒng)吞系統(tǒng)吞 吐量。吐量。使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占 用寶貴的內(nèi)存資源，而將它們調(diào)至外存上用寶貴的內(nèi)存資源，而將它們調(diào)至外存上 去等待去等待 v主要任務(wù)主要任務(wù)是按照給定的是按照給定的原則和策略原則和策略，將處，將處 于外存于外存對(duì)換區(qū)對(duì)換區(qū)中的重又具備運(yùn)行條件的就中的重又具備運(yùn)行條件的就 緒進(jìn)程緒進(jìn)程調(diào)入內(nèi)存調(diào)入內(nèi)存，或?qū)⑻幱趦?nèi)存就緒狀態(tài)，或?qū)⑻幱趦?nèi)存就緒狀態(tài) 或內(nèi)存阻塞狀態(tài)的進(jìn)程或內(nèi)存阻塞狀態(tài)的進(jìn)程交換到外存交換到外存對(duì)換區(qū)對(duì)換

12、區(qū) Operating SystemOperating SystemPage 132021-7-9 q 調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型 q 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則 Operating SystemOperating SystemPage 142021-7-9 q 僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 q 具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型 q 同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型 Operating SystemOperating SystemPage 152021-7-9 q 僅有進(jìn)程調(diào)

13、度的調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 v在分時(shí)系統(tǒng)中，通常僅設(shè)有進(jìn)程調(diào)度在分時(shí)系統(tǒng)中，通常僅設(shè)有進(jìn)程調(diào)度 v系統(tǒng)把這些進(jìn)程組織成一個(gè)系統(tǒng)把這些進(jìn)程組織成一個(gè)就緒隊(duì)列就緒隊(duì)列 v每個(gè)進(jìn)程在執(zhí)行時(shí)，可能有以下幾種情況每個(gè)進(jìn)程在執(zhí)行時(shí)，可能有以下幾種情況: : 進(jìn)程獲得進(jìn)程獲得CPUCPU正在執(zhí)行正在執(zhí)行 任務(wù)在給定時(shí)間片內(nèi)任務(wù)在給定時(shí)間片內(nèi)已完成已完成，釋放處理，釋放處理 機(jī)后為完成狀態(tài)機(jī)后為完成狀態(tài) 任務(wù)在時(shí)間片內(nèi)任務(wù)在時(shí)間片內(nèi)未完成未完成，進(jìn)入就緒隊(duì)列，進(jìn)入就緒隊(duì)列 末尾末尾 在執(zhí)行期間因某事件而阻塞在執(zhí)行期間因某事件而阻塞 Operating SystemOperating Syste

14、mPage 162021-7-9 q僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 就就 緒緒隊(duì)隊(duì) 列列 阻阻 塞塞隊(duì)隊(duì)列列 進(jìn)程調(diào)度進(jìn)程調(diào)度 CPU 進(jìn)程完成進(jìn)程完成 等待事件等待事件 交互用戶交互用戶 事事 件件 出出 現(xiàn)現(xiàn) 時(shí)間片完時(shí)間片完 Operating SystemOperating SystemPage 172021-7-9 q 具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型 v在批處理系統(tǒng)中，不僅需要在批處理系統(tǒng)中，不僅需要進(jìn)程調(diào)度進(jìn)程調(diào)度，而，而 且還要有且還要有作業(yè)調(diào)度作業(yè)調(diào)度 v就緒隊(duì)列的形式就緒隊(duì)列的形式 在批處理系統(tǒng)中，常用在批處理系統(tǒng)中，常

15、用高優(yōu)先權(quán)隊(duì)列高優(yōu)先權(quán)隊(duì)列。 進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，按優(yōu)先權(quán)高低插進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，按優(yōu)先權(quán)高低插 入相應(yīng)位置，調(diào)度程序總是把處理機(jī)分入相應(yīng)位置，調(diào)度程序總是把處理機(jī)分 配給就緒隊(duì)首進(jìn)程配給就緒隊(duì)首進(jìn)程 v設(shè)置多個(gè)阻塞隊(duì)列設(shè)置多個(gè)阻塞隊(duì)列 根據(jù)事件的不同設(shè)置多個(gè)隊(duì)列提高效率根據(jù)事件的不同設(shè)置多個(gè)隊(duì)列提高效率 Operating SystemOperating SystemPage 182021-7-9 進(jìn)程調(diào)度進(jìn)程調(diào)度 CPU 進(jìn)程完成進(jìn)程完成 時(shí)間片完時(shí)間片完 就就 緒緒隊(duì)隊(duì)列列 1 2 等待事件等待事件 等待事件等待事件 等待事件等待事件n 1 2 n 事件事件 出現(xiàn)出現(xiàn) 事件事件 出現(xiàn)出

16、現(xiàn) 事件事件 出現(xiàn)出現(xiàn) 后后備備 隊(duì)隊(duì)列列 作業(yè)作業(yè) 調(diào)度調(diào)度 與上一模型的主要區(qū)別：就緒隊(duì)列的形式；與上一模型的主要區(qū)別：就緒隊(duì)列的形式； 設(shè)置多個(gè)阻塞隊(duì)列設(shè)置多個(gè)阻塞隊(duì)列 阻阻隊(duì)隊(duì)列列塞塞2 2 阻阻隊(duì)隊(duì)列列塞塞n n 阻阻隊(duì)隊(duì)列列塞塞1 1 Operating SystemOperating SystemPage 192021-7-9 q同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型 就緒隊(duì)列就緒隊(duì)列 進(jìn)程調(diào)度進(jìn)程調(diào)度 就緒，掛起隊(duì)列就緒，掛起隊(duì)列 中級(jí)調(diào)度中級(jí)調(diào)度 阻塞，掛起隊(duì)列阻塞，掛起隊(duì)列 阻塞隊(duì)列阻塞隊(duì)列 等待事件等待事件 進(jìn)程完成進(jìn)程完成 時(shí)間片完時(shí)間片完作業(yè)調(diào)度

17、作業(yè)調(diào)度 交互型作業(yè)交互型作業(yè) 后備隊(duì)列后備隊(duì)列 批量作業(yè)批量作業(yè) 掛起掛起 掛起掛起 事事 件件 出出 現(xiàn)現(xiàn) 事件出現(xiàn)事件出現(xiàn) CPU Operating SystemOperating SystemPage 202021-7-9 q 面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則 q 面向系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則 （1）如果你是用戶，你希望系統(tǒng)如何為你服務(wù)，）如果你是用戶，你希望系統(tǒng)如何為你服務(wù)， 如何考慮？如何考慮？ （2）如果你是調(diào)度者，從系統(tǒng)整體角度出發(fā)，）如果你是調(diào)度者，從系統(tǒng)整體角度出發(fā)， 如何考慮？如何考慮？ Operating SystemOperating SystemPage 212021

18、-7-9 q 面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則 v周轉(zhuǎn)時(shí)間短周轉(zhuǎn)時(shí)間短 平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間 n i i T n T 1 1 n i Si i T T n W 1 1 帶權(quán)周轉(zhuǎn)時(shí)間：帶權(quán)周轉(zhuǎn)時(shí)間：進(jìn)程（或作業(yè)）的進(jìn)程（或作業(yè)）的周轉(zhuǎn)時(shí)周轉(zhuǎn)時(shí) 間間T T與系統(tǒng)為它與系統(tǒng)為它提供服務(wù)的時(shí)間提供服務(wù)的時(shí)間T TS S之比，即之比，即 W=T/TW=T/TS S 。而 。而平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間則可表示為則可表示為: : Operating SystemOperating SystemPage 222021-7-9 q面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則 v響應(yīng)時(shí)間快響應(yīng)時(shí)間快 響應(yīng)時(shí)間響應(yīng)時(shí)間是指

19、從用戶通過(guò)鍵盤(pán)提交一個(gè)請(qǐng)求是指從用戶通過(guò)鍵盤(pán)提交一個(gè)請(qǐng)求 開(kāi)始，直至系統(tǒng)中開(kāi)始，直至系統(tǒng)中首次首次產(chǎn)生產(chǎn)生響應(yīng)響應(yīng)為止的時(shí)間為止的時(shí)間 交互式系統(tǒng)用周轉(zhuǎn)時(shí)間衡量不是最佳交互式系統(tǒng)用周轉(zhuǎn)時(shí)間衡量不是最佳 v截止時(shí)間保證截止時(shí)間保證 截止時(shí)間截止時(shí)間是指某任務(wù)必須開(kāi)始執(zhí)行的最遲時(shí)是指某任務(wù)必須開(kāi)始執(zhí)行的最遲時(shí) 間或必須完成的最遲時(shí)間間或必須完成的最遲時(shí)間 截止時(shí)間是截止時(shí)間是實(shí)時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng)中的重要指標(biāo)中的重要指標(biāo) Operating SystemOperating SystemPage 232021-7-9 q面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則 v 周轉(zhuǎn)時(shí)間短周轉(zhuǎn)時(shí)間短 v 響應(yīng)時(shí)間快響應(yīng)時(shí)間快 v

20、截止時(shí)間保證截止時(shí)間保證 批處理系統(tǒng)批處理系統(tǒng) 分時(shí)系統(tǒng)分時(shí)系統(tǒng) 實(shí)時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng) 等待時(shí)間短等待時(shí)間短 優(yōu)先權(quán)優(yōu)先權(quán) Operating SystemOperating SystemPage 242021-7-9 q面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則 v等待時(shí)間短等待時(shí)間短 等待時(shí)間等待時(shí)間是在就緒隊(duì)列中等待所花的時(shí)間是在就緒隊(duì)列中等待所花的時(shí)間 調(diào)度算法并不影響進(jìn)程運(yùn)行和執(zhí)行調(diào)度算法并不影響進(jìn)程運(yùn)行和執(zhí)行I/O的時(shí)的時(shí) 間量；只影響進(jìn)程在就緒隊(duì)列中等待所花費(fèi)間量；只影響進(jìn)程在就緒隊(duì)列中等待所花費(fèi) 的時(shí)間的時(shí)間 v優(yōu)先權(quán)準(zhǔn)則優(yōu)先權(quán)準(zhǔn)則 在在批處理批處理、實(shí)時(shí)實(shí)時(shí)和和分時(shí)系統(tǒng)分時(shí)系統(tǒng)中都可以選擇優(yōu)中

21、都可以選擇優(yōu) 先權(quán)準(zhǔn)則，以便讓緊急任務(wù)先處理先權(quán)準(zhǔn)則，以便讓緊急任務(wù)先處理 有時(shí)還選擇搶占式調(diào)度方式有時(shí)還選擇搶占式調(diào)度方式 Operating SystemOperating SystemPage 252021-7-9 q面向系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則 v系統(tǒng)吞吐量高系統(tǒng)吞吐量高 吞吐量吞吐量指單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)指單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù) 作業(yè)調(diào)度的方式和算法對(duì)吞吐量的大小有較作業(yè)調(diào)度的方式和算法對(duì)吞吐量的大小有較 大影響大影響 v處理機(jī)利用率高處理機(jī)利用率高 v各類(lèi)資源的平衡利用各類(lèi)資源的平衡利用 使內(nèi)存、外存和使內(nèi)存、外存和I/OI/O設(shè)備的利用率高設(shè)備的利用率高 基于這樣的

22、準(zhǔn)則，你設(shè)計(jì)操作系統(tǒng)的調(diào)度策略應(yīng)如何？基于這樣的準(zhǔn)則，你設(shè)計(jì)操作系統(tǒng)的調(diào)度策略應(yīng)如何？ Operating SystemOperating SystemPage 262021-7-9 q在在OS中中調(diào)度的實(shí)質(zhì)是一種資源分配調(diào)度的實(shí)質(zhì)是一種資源分配，因而，因而 調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略 所規(guī)定的資源分配算法所規(guī)定的資源分配算法 q問(wèn)題提出問(wèn)題提出 q如何制定分配策略：對(duì)不同的系統(tǒng)和系統(tǒng)如何制定分配策略：對(duì)不同的系統(tǒng)和系統(tǒng) 目標(biāo)，通常采用不同的算法，如短作業(yè)優(yōu)目標(biāo)，通常采用不同的算法，如短作業(yè)優(yōu) 先，時(shí)間片輪轉(zhuǎn)等先，時(shí)間片輪轉(zhuǎn)等 q有些算法適用于作業(yè)

23、調(diào)度，有些適用于進(jìn)有些算法適用于作業(yè)調(diào)度，有些適用于進(jìn) 程調(diào)度，有些兩者皆可程調(diào)度，有些兩者皆可 Operating SystemOperating SystemPage 272021-7-9 q 先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法 q 高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法 q 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 Operating SystemOperating SystemPage 282021-7-9 q 先來(lái)先服務(wù)先來(lái)先服務(wù)(FCFS)/先進(jìn)先出先進(jìn)先出(FIFO)調(diào)度算法調(diào)度算法 v按照作業(yè)按照作業(yè)/進(jìn)程進(jìn)入系統(tǒng)的進(jìn)程進(jìn)入系統(tǒng)的先后次序先后次序進(jìn)行

24、調(diào)度，進(jìn)行調(diào)度， 先進(jìn)入系統(tǒng)者先調(diào)度；即啟動(dòng)等待時(shí)間最長(zhǎng)先進(jìn)入系統(tǒng)者先調(diào)度；即啟動(dòng)等待時(shí)間最長(zhǎng) 的作業(yè)的作業(yè)/進(jìn)程進(jìn)程 v是一種最簡(jiǎn)單的調(diào)度算法，即可用于是一種最簡(jiǎn)單的調(diào)度算法，即可用于作業(yè)調(diào)作業(yè)調(diào) 度度，也可用于，也可用于進(jìn)程調(diào)度進(jìn)程調(diào)度 q 幾個(gè)術(shù)語(yǔ)幾個(gè)術(shù)語(yǔ) v到達(dá)時(shí)間、服務(wù)時(shí)間、開(kāi)始時(shí)間到達(dá)時(shí)間、服務(wù)時(shí)間、開(kāi)始時(shí)間 v完成時(shí)間、等待時(shí)間完成時(shí)間、等待時(shí)間 v周轉(zhuǎn)時(shí)間：完成時(shí)間周轉(zhuǎn)時(shí)間：完成時(shí)間-到達(dá)時(shí)間到達(dá)時(shí)間 v帶權(quán)周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間服務(wù)時(shí)間 Operating SystemOperating SystemPage 292021-7-9 進(jìn)程名進(jìn)程名到達(dá)

25、時(shí)間到達(dá)時(shí)間 服務(wù)時(shí)間服務(wù)時(shí)間 開(kāi)始時(shí)間開(kāi)始時(shí)間 完成時(shí)間完成時(shí)間 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 帶權(quán)周帶權(quán)周 轉(zhuǎn)時(shí)間轉(zhuǎn)時(shí)間 平均平均 04A 13B 25C 32D 44E 044 476 先來(lái)先服務(wù)（先進(jìn)先出）：先來(lái)先服務(wù)（先進(jìn)先出）： 71210 121411 141814 1 2 2 5.5 3.5 92.8 A A A A B B B C C C C C D D E E E E 05101518 t Operating SystemOperating SystemPage 302021-7-9 q 先來(lái)先服務(wù)先來(lái)先服務(wù)（先進(jìn)先出）（先進(jìn)先出）優(yōu)缺點(diǎn)：優(yōu)缺點(diǎn)： v 比較有利于比較有利于長(zhǎng)作業(yè)（進(jìn)程

26、）長(zhǎng)作業(yè)（進(jìn)程），而不利于，而不利于短作短作 業(yè)（進(jìn)程）業(yè)（進(jìn)程） v 有利于有利于CPU繁忙型作業(yè)（進(jìn)程）繁忙型作業(yè)（進(jìn)程） ，而不利于，而不利于 I/O繁忙型作業(yè)（進(jìn)程）繁忙型作業(yè)（進(jìn)程） v 用于批處理系統(tǒng)，不適于分時(shí)系統(tǒng)用于批處理系統(tǒng)，不適于分時(shí)系統(tǒng) Operating SystemOperating SystemPage 312021-7-9 q短作業(yè)短作業(yè)( (進(jìn)程進(jìn)程) )優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法SJ(P)FSJ(P)F v短作業(yè)短作業(yè)( (進(jìn)程進(jìn)程) )優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法SJ(P)FSJ(P)F，以要求，以要求運(yùn)運(yùn) 行時(shí)間長(zhǎng)短行時(shí)間長(zhǎng)短進(jìn)行調(diào)度，即啟動(dòng)要求運(yùn)行時(shí)間最進(jìn)行調(diào)

27、度，即啟動(dòng)要求運(yùn)行時(shí)間最 短的作業(yè)短的作業(yè) v可以分別用于可以分別用于作業(yè)調(diào)度作業(yè)調(diào)度和和進(jìn)程調(diào)度進(jìn)程調(diào)度 v短作業(yè)優(yōu)先短作業(yè)優(yōu)先(SJF)(SJF)的調(diào)度算法，是從后備隊(duì)列的調(diào)度算法，是從后備隊(duì)列 中選擇一個(gè)或若干個(gè)中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間估計(jì)運(yùn)行時(shí)間最短的作業(yè)，最短的作業(yè)， 將它們調(diào)入內(nèi)存運(yùn)行；而短進(jìn)程優(yōu)先將它們調(diào)入內(nèi)存運(yùn)行；而短進(jìn)程優(yōu)先(SPF)(SPF)調(diào)調(diào) 度算法，則是從就緒隊(duì)列中選出一度算法，則是從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)估計(jì)運(yùn)行時(shí) 間間最短的進(jìn)程，將處理機(jī)分配給它，使它立即最短的進(jìn)程，將處理機(jī)分配給它，使它立即 執(zhí)行并一直執(zhí)行到完成執(zhí)行并一直執(zhí)行到完成，或，或發(fā)生某事件發(fā)

28、生某事件而被阻而被阻 塞放棄處理機(jī)時(shí)，再重新調(diào)度塞放棄處理機(jī)時(shí)，再重新調(diào)度 Operating SystemOperating SystemPage 322021-7-9 進(jìn)程名進(jìn)程名到達(dá)時(shí)間到達(dá)時(shí)間 服務(wù)時(shí)間服務(wù)時(shí)間 開(kāi)始時(shí)間開(kāi)始時(shí)間 完成時(shí)間完成時(shí)間 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 帶權(quán)周帶權(quán)周 轉(zhuǎn)時(shí)間轉(zhuǎn)時(shí)間 平均平均 04A 13B 25C 32D 44E 0441 短作業(yè)短作業(yè)/短進(jìn)程優(yōu)先（短進(jìn)程優(yōu)先（SJF/SPF）：）： 4633/2 6988/3 91399/4 13181616/5 82.1 A A A AB B BC C C C CD DE E E E 05101518 t Operati

29、ng SystemOperating SystemPage 332021-7-9 qFCFS/SJF調(diào)度算法的性能調(diào)度算法的性能 SJFSJF能有效地降低作業(yè)的平均等待時(shí)間，提高系統(tǒng)吞吐量能有效地降低作業(yè)的平均等待時(shí)間，提高系統(tǒng)吞吐量 作業(yè)作業(yè) 調(diào)度調(diào)度 情況情況 算法算法 進(jìn)程名進(jìn)程名ABCDE平均平均 到達(dá)時(shí)間到達(dá)時(shí)間01234 服務(wù)時(shí)間服務(wù)時(shí)間43524 FCFS 完成時(shí)間完成時(shí)間47121418 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間461011149 帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間1225.53.52.8 SJF 完成時(shí)間完成時(shí)間4918613 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間4816398 帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間12.67

30、3.11.52.252.1 SJFSJF平均周轉(zhuǎn)平均周轉(zhuǎn) 時(shí)間和平均帶時(shí)間和平均帶 權(quán)周轉(zhuǎn)時(shí)間明權(quán)周轉(zhuǎn)時(shí)間明 顯改善顯改善 Operating SystemOperating SystemPage 342021-7-9 qSJ(P)F調(diào)度算法也存在不容忽視的缺點(diǎn)調(diào)度算法也存在不容忽視的缺點(diǎn) v對(duì)對(duì)長(zhǎng)作業(yè)不利長(zhǎng)作業(yè)不利。嚴(yán)重的是，若一長(zhǎng)作業(yè)。嚴(yán)重的是，若一長(zhǎng)作業(yè)(進(jìn)程進(jìn)程)進(jìn)進(jìn) 入系統(tǒng)的后備隊(duì)列入系統(tǒng)的后備隊(duì)列(就緒隊(duì)列就緒隊(duì)列)，由于調(diào)度程序總，由于調(diào)度程序總 是優(yōu)先調(diào)度那些是優(yōu)先調(diào)度那些(即使是后進(jìn)來(lái)的即使是后進(jìn)來(lái)的)短作業(yè)短作業(yè)(進(jìn)程進(jìn)程)， 將導(dǎo)致長(zhǎng)作業(yè)將導(dǎo)致長(zhǎng)作業(yè)(進(jìn)程進(jìn)程)長(zhǎng)期不被調(diào)

31、度長(zhǎng)期不被調(diào)度饑餓饑餓 v完全未考慮作業(yè)完全未考慮作業(yè)(進(jìn)程進(jìn)程)的的緊迫程度緊迫程度，因而不能保，因而不能保 證證緊迫性緊迫性作業(yè)作業(yè)(進(jìn)程進(jìn)程)會(huì)被會(huì)被及時(shí)處理及時(shí)處理 v根據(jù)根據(jù)用戶用戶所提供的所提供的估計(jì)執(zhí)行時(shí)間確定作業(yè)（進(jìn)程）估計(jì)執(zhí)行時(shí)間確定作業(yè)（進(jìn)程） 長(zhǎng)短長(zhǎng)短，致使該算法不一定能真正做到短作業(yè)優(yōu)先，致使該算法不一定能真正做到短作業(yè)優(yōu)先 調(diào)度。調(diào)度。 Operating SystemOperating SystemPage 352021-7-9 q先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法 q高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法 q基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法基于時(shí)間片的

32、輪轉(zhuǎn)調(diào)度算法 Operating SystemOperating SystemPage 362021-7-9 q優(yōu)先權(quán)調(diào)度算法的類(lèi)型優(yōu)先權(quán)調(diào)度算法的類(lèi)型 v非搶占式非搶占式優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法 v搶占式搶占式優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法 Operating SystemOperating SystemPage 372021-7-9 q優(yōu)先權(quán)調(diào)度算法的類(lèi)型優(yōu)先權(quán)調(diào)度算法的類(lèi)型 v非搶占式非搶占式優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法 特點(diǎn)：系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)特點(diǎn)：系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì) 列中列中優(yōu)先權(quán)最高優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便的進(jìn)程后，該進(jìn)程便一一 直執(zhí)行直執(zhí)行下去，直至完成

33、，或因發(fā)生某事下去，直至完成，或因發(fā)生某事 件使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)才將處件使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)才將處 理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程 主要主要用于批處理系統(tǒng)用于批處理系統(tǒng)中，也可用于某些中，也可用于某些 對(duì)實(shí)時(shí)性對(duì)實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中中 Operating SystemOperating SystemPage 382021-7-9 q優(yōu)先權(quán)調(diào)度算法的類(lèi)型優(yōu)先權(quán)調(diào)度算法的類(lèi)型 v搶占式搶占式優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法 把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，但在執(zhí)行把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，但在執(zhí)行 期間，只要出現(xiàn)另一個(gè)優(yōu)

34、先權(quán)更高的進(jìn)程，則期間，只要出現(xiàn)另一個(gè)優(yōu)先權(quán)更高的進(jìn)程，則 進(jìn)程調(diào)度程序就進(jìn)程調(diào)度程序就立即停止立即停止當(dāng)前進(jìn)程的執(zhí)行，并當(dāng)前進(jìn)程的執(zhí)行，并 將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程 注意注意：只要只要系統(tǒng)中系統(tǒng)中出現(xiàn)出現(xiàn)一個(gè)新的就緒進(jìn)程，一個(gè)新的就緒進(jìn)程，就就 進(jìn)行進(jìn)行優(yōu)先權(quán)優(yōu)先權(quán)比較比較 該調(diào)度算法，能更好地該調(diào)度算法，能更好地滿足緊迫作業(yè)滿足緊迫作業(yè)的要求，的要求， 故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，以及故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，以及 對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中 Operating SystemOper

35、ating SystemPage 392021-7-9 q優(yōu)先權(quán)的類(lèi)型優(yōu)先權(quán)的類(lèi)型 v靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán) v動(dòng)態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán) Operating SystemOperating SystemPage 402021-7-9 q優(yōu)先權(quán)的類(lèi)型優(yōu)先權(quán)的類(lèi)型 v靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán) 靜態(tài)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時(shí)確定，且在進(jìn)程的整個(gè)靜態(tài)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時(shí)確定，且在進(jìn)程的整個(gè) 運(yùn)行期間運(yùn)行期間保持不變保持不變。一般地，優(yōu)先權(quán)是利用某一。一般地，優(yōu)先權(quán)是利用某一 范圍內(nèi)的一個(gè)整數(shù)來(lái)表示的，例如，范圍內(nèi)的一個(gè)整數(shù)來(lái)表示的，例如，0 0 7 7或或0 0 255255， 又把該整數(shù)稱(chēng)為又把該整數(shù)稱(chēng)為優(yōu)先數(shù)優(yōu)先數(shù)

36、v確定進(jìn)程靜態(tài)優(yōu)先權(quán)的依據(jù)確定進(jìn)程靜態(tài)優(yōu)先權(quán)的依據(jù) 進(jìn)程類(lèi)型進(jìn)程類(lèi)型: :系統(tǒng)進(jìn)程，用戶進(jìn)程系統(tǒng)進(jìn)程，用戶進(jìn)程 進(jìn)程對(duì)資源的需求進(jìn)程對(duì)資源的需求 用戶要求用戶要求 v靜態(tài)優(yōu)先權(quán)特點(diǎn)靜態(tài)優(yōu)先權(quán)特點(diǎn) 系統(tǒng)開(kāi)銷(xiāo)小、不夠精確、一般用在要求不高的系系統(tǒng)開(kāi)銷(xiāo)小、不夠精確、一般用在要求不高的系 統(tǒng)中統(tǒng)中 問(wèn)題：用戶將優(yōu)先權(quán)設(shè)的較高，對(duì)其他進(jìn)程不利！問(wèn)題：用戶將優(yōu)先權(quán)設(shè)的較高，對(duì)其他進(jìn)程不利！ 短進(jìn)程優(yōu)先對(duì)長(zhǎng)進(jìn)程不利！短進(jìn)程優(yōu)先對(duì)長(zhǎng)進(jìn)程不利！ Operating SystemOperating SystemPage 412021-7-9 v動(dòng)態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán) 隨隨進(jìn)程的推進(jìn)進(jìn)程的推進(jìn)或隨其或隨其等待時(shí)間等待

37、時(shí)間的增加而改變，以獲的增加而改變，以獲 得更好的調(diào)度性能得更好的調(diào)度性能 可規(guī)定，在可規(guī)定，在就緒隊(duì)列中的進(jìn)程就緒隊(duì)列中的進(jìn)程，隨其，隨其等待時(shí)間的增等待時(shí)間的增 長(zhǎng)長(zhǎng)，其優(yōu)先權(quán)，其優(yōu)先權(quán)以速率以速率a提高提高 具有具有相同相同優(yōu)先權(quán)優(yōu)先權(quán)初值初值的進(jìn)程，則的進(jìn)程，則最先進(jìn)入最先進(jìn)入就緒就緒 隊(duì)列，其將因其動(dòng)態(tài)優(yōu)先權(quán)變得最高而隊(duì)列，其將因其動(dòng)態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲優(yōu)先獲 得得處理機(jī)，此即處理機(jī)，此即FCFS算法算法 具有各不相同的優(yōu)先權(quán)初值的就緒進(jìn)程，則具有各不相同的優(yōu)先權(quán)初值的就緒進(jìn)程，則優(yōu)優(yōu) 先權(quán)初值低先權(quán)初值低的進(jìn)程，在的進(jìn)程，在等待了足夠的時(shí)間等待了足夠的時(shí)間后，后， 其其優(yōu)先權(quán)便

38、可能升為最高優(yōu)先權(quán)便可能升為最高，從而可以獲得處理，從而可以獲得處理 機(jī)機(jī) 當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時(shí)，如果再當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時(shí)，如果再規(guī)定當(dāng)前規(guī)定當(dāng)前 進(jìn)程進(jìn)程的優(yōu)先權(quán)的優(yōu)先權(quán)以速率以速率b下降下降，則可防止一個(gè)長(zhǎng)作業(yè)，則可防止一個(gè)長(zhǎng)作業(yè) 長(zhǎng)期地長(zhǎng)期地壟斷壟斷處理機(jī)處理機(jī) Operating SystemOperating SystemPage 422021-7-9 q高響應(yīng)比優(yōu)先調(diào)度算法（高響應(yīng)比優(yōu)先調(diào)度算法（HRF） v是是FCFS和和SJF的結(jié)合，克服了兩種算法的的結(jié)合，克服了兩種算法的 缺點(diǎn)缺點(diǎn) v調(diào)度策略調(diào)度策略：響應(yīng)比：響應(yīng)比最高的作業(yè)優(yōu)先啟動(dòng)最高的作業(yè)優(yōu)先啟動(dòng) v因

39、因等待時(shí)間等待時(shí)間+服務(wù)時(shí)間服務(wù)時(shí)間=該作業(yè)的該作業(yè)的響應(yīng)時(shí)間響應(yīng)時(shí)間， 故該優(yōu)先權(quán)又相當(dāng)于故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比響應(yīng)比RP。據(jù)此，又。據(jù)此，又 可表示為可表示為 時(shí)時(shí)間間務(wù)務(wù)時(shí)時(shí)間間 權(quán)權(quán) 務(wù)務(wù)時(shí)時(shí)間間 等等待待+ + 要要求求服服 優(yōu)優(yōu)先先= = 要要求求服服 時(shí)間務(wù)時(shí)間響應(yīng)時(shí)間 權(quán) 務(wù)時(shí)間務(wù)時(shí)間 等等待待+ + 要要求求服服 優(yōu)優(yōu)先先= = = 要要求求服服要要求求服服 Operating SystemOperating SystemPage 432021-7-9 q 對(duì)對(duì)HRF的小結(jié)的小結(jié) v等待時(shí)間相同等待時(shí)間相同的作業(yè)，則的作業(yè)，則要求服務(wù)的時(shí)間愈要求服務(wù)的時(shí)間愈 短短，其，其優(yōu)

40、先權(quán)愈高優(yōu)先權(quán)愈高， v要求服務(wù)的時(shí)間相同要求服務(wù)的時(shí)間相同的作業(yè)，則的作業(yè)，則等待時(shí)間愈等待時(shí)間愈 長(zhǎng)長(zhǎng)，其，其優(yōu)先權(quán)愈高優(yōu)先權(quán)愈高， v長(zhǎng)作業(yè)，優(yōu)先權(quán)長(zhǎng)作業(yè)，優(yōu)先權(quán)隨等待時(shí)間的增加隨等待時(shí)間的增加而提高，而提高， 其等待時(shí)間足夠長(zhǎng)時(shí)，其優(yōu)先權(quán)便可升到很其等待時(shí)間足夠長(zhǎng)時(shí)，其優(yōu)先權(quán)便可升到很 高，高， 從而也可獲得處理機(jī)從而也可獲得處理機(jī) v是一種折衷，既照顧了短作業(yè)，又考慮了作是一種折衷，既照顧了短作業(yè)，又考慮了作 業(yè)到達(dá)的先后次序，又不會(huì)使長(zhǎng)作業(yè)長(zhǎng)期得業(yè)到達(dá)的先后次序，又不會(huì)使長(zhǎng)作業(yè)長(zhǎng)期得 不到服務(wù)。不到服務(wù)。 缺點(diǎn)：要進(jìn)行響應(yīng)比計(jì)算，增加了系統(tǒng)開(kāi)銷(xiāo)缺點(diǎn)：要進(jìn)行響應(yīng)比計(jì)算，增加了系統(tǒng)開(kāi)銷(xiāo)

41、 時(shí)間務(wù)時(shí)間響應(yīng)時(shí)間 權(quán) 務(wù)時(shí)間務(wù)時(shí)間 等等待待+ + 要要求求服服 優(yōu)優(yōu)先先= = = 要要求求服服要要求求服服 對(duì)短作業(yè)有利對(duì)短作業(yè)有利 是先來(lái)先服務(wù)是先來(lái)先服務(wù) 對(duì)長(zhǎng)作業(yè)有利對(duì)長(zhǎng)作業(yè)有利 Operating SystemOperating SystemPage 442021-7-9 q先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法先來(lái)先服務(wù)和短作業(yè)優(yōu)先算法 q高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法 q基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 Operating SystemOperating SystemPage 452021-7-9 q 簡(jiǎn)單的時(shí)間片輪轉(zhuǎn)法簡(jiǎn)單的時(shí)間片輪轉(zhuǎn)法(RRRound Ro

42、bin) v系統(tǒng)將所有的就緒進(jìn)程按先來(lái)先服務(wù)的原則排系統(tǒng)將所有的就緒進(jìn)程按先來(lái)先服務(wù)的原則排 成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把CPU分配給隊(duì)首分配給隊(duì)首 進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片 v當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)時(shí) 鐘中斷鐘中斷請(qǐng)求，調(diào)度程序便停止該進(jìn)程的執(zhí)行，請(qǐng)求，調(diào)度程序便停止該進(jìn)程的執(zhí)行， 并將其放就緒隊(duì)列尾；然后，再把處理機(jī)分配并將其放就緒隊(duì)列尾；然后，再把處理機(jī)分配 給就緒隊(duì)列中新的隊(duì)首給就緒隊(duì)列中新的隊(duì)首 v時(shí)間片的大小從幾時(shí)間片的大小從幾ms到幾百到幾百ms 優(yōu)點(diǎn)：公平。保證就緒隊(duì)列中

43、所有進(jìn)程在一給定的優(yōu)點(diǎn)：公平。保證就緒隊(duì)列中所有進(jìn)程在一給定的 時(shí)間內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間時(shí)間內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間 缺點(diǎn)：緊迫任務(wù)響應(yīng)慢。缺點(diǎn)：緊迫任務(wù)響應(yīng)慢。 UNIX中采用：時(shí)間片中采用：時(shí)間片+優(yōu)先權(quán)優(yōu)先權(quán) Operating SystemOperating SystemPage 462021-7-9 進(jìn)程名進(jìn)程名到達(dá)時(shí)間到達(dá)時(shí)間 服務(wù)時(shí)間服務(wù)時(shí)間 開(kāi)始時(shí)間開(kāi)始時(shí)間 完成時(shí)間完成時(shí)間 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 帶權(quán)周帶權(quán)周 轉(zhuǎn)時(shí)間轉(zhuǎn)時(shí)間 平均平均 A B C D E A B C D E A B C E A C E C 05101518 t 04A 03B 05C 0

44、2D 04E 0 1 2 3 4 9 12 15 17 18 1515/4 1212/3 1818/5 99/2 1717/4 14.24.02 若到達(dá)時(shí)間若到達(dá)時(shí)間 為為0 0、1 1、2 2、 3 3、4 4，又如，又如 何？何？ Operating SystemOperating SystemPage 472021-7-9 q就緒隊(duì)列的變化就緒隊(duì)列的變化: A AB CAB C B D A B D A E C A B C D E q=1 q=4 A BE C E C 05101518 t A C B D A E C B D AE C Operating SystemOperating S

45、ystemPage 482021-7-9 進(jìn)程名進(jìn)程名 到達(dá)時(shí)到達(dá)時(shí) 間間 服務(wù)時(shí)間服務(wù)時(shí)間開(kāi)始時(shí)間開(kāi)始時(shí)間 完成時(shí)間完成時(shí)間 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 帶權(quán)周帶權(quán)周 轉(zhuǎn)時(shí)間轉(zhuǎn)時(shí)間 平均平均 04A 13B 25C 32D 44E 0 1 3 5 7 11 10 12 17 18 1212/4 99/3 1616/5 88/2 1313/4 11.63.29 Operating SystemOperating SystemPage 492021-7-9 v分時(shí)系統(tǒng)中常用時(shí)間片輪轉(zhuǎn)法分時(shí)系統(tǒng)中常用時(shí)間片輪轉(zhuǎn)法 時(shí)間片選擇時(shí)間片選擇問(wèn)題問(wèn)題 固定時(shí)間片固定時(shí)間片 可變時(shí)間片可變時(shí)間片 時(shí)間片大小時(shí)間片大小

46、 與與時(shí)間片大小時(shí)間片大小有關(guān)的因素有關(guān)的因素 系統(tǒng)響應(yīng)時(shí)間系統(tǒng)響應(yīng)時(shí)間 就緒進(jìn)程個(gè)數(shù)就緒進(jìn)程個(gè)數(shù) CPUCPU能力能力 Operating SystemOperating SystemPage 502021-7-9 q多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法 v設(shè)置設(shè)置多個(gè)就緒隊(duì)列多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予，并為各個(gè)隊(duì)列賦予不同不同 的優(yōu)先級(jí)的優(yōu)先級(jí) 第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二個(gè)隊(duì)列次第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二個(gè)隊(duì)列次 之，其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低之，其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低 該算法賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行該算法賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的時(shí)間片的 大小也各不相同大小也各不相同，

47、在，在優(yōu)先權(quán)愈高優(yōu)先權(quán)愈高的隊(duì)列中，的隊(duì)列中， 為每個(gè)進(jìn)程所規(guī)定的執(zhí)行為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就愈小時(shí)間片就愈小。 Operating SystemOperating SystemPage 512021-7-9 就緒隊(duì)列就緒隊(duì)列1 1 就緒隊(duì)列就緒隊(duì)列2 2 就緒隊(duì)列就緒隊(duì)列3 3 就緒隊(duì)列就緒隊(duì)列n n S1 S2 S3 至至CPU 至至CPU 至至CPU 至至CPU ( (時(shí)間片：時(shí)間片：S1 S2 S3) ) v調(diào)度方式調(diào)度方式 高高 低低 優(yōu)先級(jí)優(yōu)先級(jí) 時(shí)間片時(shí)間片 小小 大大 Sn 按按FIFO原則原則 排隊(duì)等待調(diào)排隊(duì)等待調(diào) 度度 尚未完成轉(zhuǎn)入第二尚未完成轉(zhuǎn)入第二 隊(duì)列的末尾，按

48、隊(duì)列的末尾，按 FIFO原則等待調(diào)原則等待調(diào) 度度 采取按時(shí)間片輪采取按時(shí)間片輪 轉(zhuǎn)的方式運(yùn)行轉(zhuǎn)的方式運(yùn)行 因等待而放棄因等待而放棄CPU后，后， 進(jìn)入阻塞隊(duì)列，一旦進(jìn)入阻塞隊(duì)列，一旦 等待的事件發(fā)生，則等待的事件發(fā)生，則 回到原來(lái)的就緒隊(duì)列回到原來(lái)的就緒隊(duì)列 Operating SystemOperating SystemPage 522021-7-9 v注意：注意： 僅當(dāng)?shù)趦H當(dāng)?shù)?(i-1) 隊(duì)列均空時(shí)，才會(huì)調(diào)度第隊(duì)列均空時(shí)，才會(huì)調(diào)度第i隊(duì)列隊(duì)列 中的進(jìn)程運(yùn)行中的進(jìn)程運(yùn)行 第第i隊(duì)列隊(duì)列中某進(jìn)程正在運(yùn)行時(shí)，又有中某進(jìn)程正在運(yùn)行時(shí)，又有新新進(jìn)程進(jìn)進(jìn)程進(jìn) 入入優(yōu)先權(quán)較高優(yōu)先權(quán)較高的隊(duì)列的隊(duì)列(

49、第第1(i-1)中的任何一個(gè)中的任何一個(gè) 隊(duì)列隊(duì)列)，則此時(shí)，則此時(shí)新進(jìn)程將搶占新進(jìn)程將搶占正在運(yùn)行進(jìn)程的正在運(yùn)行進(jìn)程的 處理機(jī)，調(diào)度程序把正在運(yùn)行的進(jìn)程處理機(jī)，調(diào)度程序把正在運(yùn)行的進(jìn)程放回到放回到 第第i隊(duì)列隊(duì)列的末尾的末尾 第第i隊(duì)列隊(duì)列中某進(jìn)程正在運(yùn)行時(shí)，該進(jìn)程因等待中某進(jìn)程正在運(yùn)行時(shí)，該進(jìn)程因等待 事件發(fā)生而進(jìn)入阻塞隊(duì)列，等待事件發(fā)生后，事件發(fā)生而進(jìn)入阻塞隊(duì)列，等待事件發(fā)生后， 調(diào)度程序把進(jìn)程調(diào)度程序把進(jìn)程放回到第放回到第i隊(duì)列隊(duì)列的末尾的末尾 Operating SystemOperating SystemPage 532021-7-9 q1.為了使系統(tǒng)中各部分資源得到均衡使用，就必

50、須選 擇對(duì)資源需求不同的作業(yè)進(jìn)行合理搭配。這項(xiàng)工作是 由（ ）完成的。 qA作業(yè)調(diào)度 B中級(jí)調(diào)度 C進(jìn)程調(diào)度 D內(nèi)存調(diào)度 答案：答案： A Operating SystemOperating SystemPage 542021-7-9 q2.進(jìn)程狀態(tài)從就緒態(tài)到運(yùn)行態(tài)的轉(zhuǎn)化工作是由（ ）完 成的。 qA作業(yè)調(diào)度 B中級(jí)調(diào)度 C進(jìn)程調(diào)度 D設(shè)備調(diào)度 答案：答案： C Operating SystemOperating SystemPage 552021-7-9 q3.作業(yè)調(diào)度程序從處于（）狀態(tài)的隊(duì)列中選取適當(dāng) 的作業(yè)投入運(yùn)行。 qA運(yùn)行 B提交 C完成 D后備 答案：答案： D Operating

51、 SystemOperating SystemPage 562021-7-9 q4（）是作業(yè)存在的唯一標(biāo)志。 q作業(yè)名B進(jìn)程控制塊C作業(yè)控制塊D程序名 答案：答案： C Operating SystemOperating SystemPage 572021-7-9 q5.若進(jìn)程P1正在運(yùn)行，操作系統(tǒng)強(qiáng)行撤下P1進(jìn)程所占 用的CPU，讓具有更高優(yōu)先級(jí)的進(jìn)程P2運(yùn)行，這種調(diào) 度方式稱(chēng)為（1），此時(shí)P1進(jìn)程處于（2）狀態(tài)。 q（1）A中斷方式B搶占方式 qC非搶占方式D查詢方式 q（2）A等待B結(jié)束C善后處理 D就緒 答案：答案： （1）B（2）D Operating SystemOperating

52、 SystemPage 582021-7-9 q6作業(yè)調(diào)度算法的選擇常考慮因素之一是使系統(tǒng)有最 高的吞吐率，為此應(yīng)（） qA.不讓處理機(jī)空閑B能夠處理盡可能多的作業(yè)C使 各類(lèi)用戶都滿意D不使系統(tǒng)過(guò)于復(fù)雜 答案：答案： B Operating SystemOperating SystemPage 592021-7-9 q7.填空： q對(duì)于FCFS，時(shí)間片輪轉(zhuǎn)，多級(jí)反饋隊(duì)列三個(gè)高級(jí)調(diào)度 算法，他們對(duì)短作業(yè)的優(yōu)先程度升高排序 為： 。 答案：答案： FCFS，時(shí)間片輪轉(zhuǎn)，多級(jí)反饋隊(duì)列，時(shí)間片輪轉(zhuǎn)，多級(jí)反饋隊(duì)列 Operating SystemOperating SystemPage 602021-7

53、-9 q 8.假設(shè)下列四個(gè)作業(yè)同時(shí)到達(dá)，當(dāng)使用最高優(yōu)先數(shù)優(yōu)先調(diào) 度算法時(shí)，作業(yè)的平均周轉(zhuǎn)時(shí)間為（ ）小時(shí)。 q A4.5 B10.5 C4.75 D10.25 答案：答案： D Operating SystemOperating SystemPage 612021-7-9 9.作業(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)的開(kāi)銷(xiāo)） 答案：答案：C A Operating SystemOperating SystemPage 622021-7-9 答案：答案：B Operating

54、SystemOperating SystemPage 632021-7-9 11.系統(tǒng)中的四個(gè)作業(yè)，它們的到達(dá)時(shí)間、運(yùn)行時(shí)間、開(kāi)始時(shí)間、完 成時(shí)間和周轉(zhuǎn)時(shí)間如下表所示，該系統(tǒng)采用的作業(yè)調(diào)度算法是 （A）。 A：（1）先來(lái)先服務(wù) （2）短作業(yè)優(yōu)先 （3）響應(yīng)比高者優(yōu)先 （4）不能確定 答案：答案：3 Operating SystemOperating SystemPage 642021-7-9 q12既考慮作業(yè)等待時(shí)間，又考慮作業(yè)執(zhí)行時(shí)間的調(diào) 度算法是（） qA.最高響應(yīng)比優(yōu)先B短作業(yè)優(yōu)先C優(yōu)先級(jí)調(diào)度 D先來(lái)先服務(wù) 答案：答案： A Operating SystemOperating Syste

55、mPage 652021-7-9 q13作業(yè)從進(jìn)入后備隊(duì)列到被調(diào)度程序選中的時(shí)間間 隔稱(chēng)為（） q周轉(zhuǎn)時(shí)間B響應(yīng)時(shí)間C等待時(shí)間D觸發(fā)時(shí)間 答案：答案： C Operating SystemOperating SystemPage 662021-7-9 q14下述作業(yè)調(diào)度算法中，（）調(diào)度算法與作業(yè)的估 計(jì)運(yùn)行時(shí)間有關(guān)。 qA.先來(lái)先服務(wù)B短作業(yè)優(yōu)先C均衡D時(shí)間片輪轉(zhuǎn) 答案：答案： B Operating SystemOperating SystemPage 672021-7-9 q15在各種作業(yè)調(diào)度算法中，若有作業(yè)同時(shí)到達(dá)，則 平均等待時(shí)間最短的算法是（） qA.先來(lái)先服務(wù)B優(yōu)先數(shù)C最高響應(yīng)比優(yōu)

56、先D短作 業(yè)優(yōu)先 答案：答案： D Operating SystemOperating SystemPage 682021-7-9 q證明： 若有三個(gè)作業(yè)J1，J2，J3同時(shí)在后備作業(yè)隊(duì)列中等 待運(yùn)行，其運(yùn)行時(shí)間分別為t1,t2,t3，且滿足關(guān)系 t1t20。命題得證。命題得證。 Operating SystemOperating SystemPage 692021-7-9 q證明： 給定一組作業(yè)J1，J2Jn,他們的運(yùn)行時(shí)間分別為 t1,t2tn，假定這些作業(yè)同時(shí)到達(dá)，并且將在一臺(tái)CPU 上按單道方式運(yùn)行。試證明按最短的作業(yè)優(yōu)先調(diào)度算 法運(yùn)行這些作業(yè)，則平均周轉(zhuǎn)時(shí)間最小。 證明：不失一般性，

57、假定按最短的作業(yè)優(yōu)先調(diào)度算法，調(diào)度順證明：不失一般性，假定按最短的作業(yè)優(yōu)先調(diào)度算法，調(diào)度順 序分別為序分別為J1，J2Jn，其運(yùn)行時(shí)間分別為：，其運(yùn)行時(shí)間分別為： t1,t2tn。則作業(yè)。則作業(yè)Ji的周的周 轉(zhuǎn)時(shí)間為：轉(zhuǎn)時(shí)間為： Ti = t 1 + t 2 + + t i 。 所 以 ， 全 部 作 業(yè) 的 平 均 周 轉(zhuǎn) 時(shí) 間 為 ：。 所 以 ， 全 部 作 業(yè) 的 平 均 周 轉(zhuǎn) 時(shí) 間 為 ： T=T1+T2+Tn/n=t1+(t1+t2) +（t1+t2+t3） + (t1+t2 +tn) /n顯然，當(dāng)顯然，當(dāng)t1t2tn時(shí)，每個(gè)時(shí)，每個(gè)Ti達(dá)到最小值（達(dá)到最小值（i=1,2,

58、n）。）。 因此，因此，T最小，命題得證。最小，命題得證。 Operating SystemOperating SystemPage 702021-7-9 q證明： 給定一組作業(yè)J1，J2Jn,他們的運(yùn)行時(shí)間分別為 t1,t2tn，假定這些作業(yè)同時(shí)到達(dá)，并且將在一臺(tái)CPU 上按單道方式運(yùn)行。試證明短作業(yè)優(yōu)先的調(diào)度算法使 得作業(yè)的平均等待時(shí)間最短。 證明：不失一般性，假定按最短的作業(yè)優(yōu)先調(diào)度算法證明：不失一般性，假定按最短的作業(yè)優(yōu)先調(diào)度算法,調(diào)度順序調(diào)度順序 為為 J 1 ， J 2 J n ， 其 運(yùn) 行 時(shí) 間 分 別 為， 其 運(yùn) 行 時(shí) 間 分 別 為 : t 1 , t 2 t n 。

59、 顯 然 有。 顯 然 有 t1t2tnt1t2tn 。根據(jù)題意得。根據(jù)題意得:作業(yè)作業(yè)Ji的等待時(shí)間為的等待時(shí)間為: :Wi= t 1 + t 2 + ti - 1 。所 以 ， 全 部 作 業(yè) 的 平 均 等 待 時(shí) 間 為 ：所 以 ， 全 部 作 業(yè) 的 平 均 等 待 時(shí) 間 為 ： W=W1+W2+Wn/n=t1+(t1+t2) +（t1+t2+t3） + (t1+t2 +tn-1) /n 顯然，當(dāng)顯然，當(dāng)t1t2tn時(shí)，每一個(gè)時(shí)，每一個(gè)Wi達(dá)到最小值達(dá)到最小值 （i=1,2, n）。因此，）。因此，W最小，這樣結(jié)論得證。最小，這樣結(jié)論得證。 Operating SystemOpe

60、rating SystemPage 712021-7-9 q 實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件 q 實(shí)時(shí)調(diào)度算法的分類(lèi)實(shí)時(shí)調(diào)度算法的分類(lèi) q 常用的幾種實(shí)時(shí)調(diào)度算法常用的幾種實(shí)時(shí)調(diào)度算法 Operating SystemOperating SystemPage 722021-7-9 q提供必要的信息：提供必要的信息： v開(kāi)始截止時(shí)間開(kāi)始截止時(shí)間 v完成截止時(shí)間完成截止時(shí)間 v就緒時(shí)間就緒時(shí)間 v處理時(shí)間處理時(shí)間 v資源要求資源要求 v優(yōu)先級(jí)優(yōu)先級(jí) Operating SystemOperating SystemPage 732021-7-9 q系統(tǒng)處理能力強(qiáng)系統(tǒng)處理能力強(qiáng) v在實(shí)時(shí)