華東理工815操作系統(tǒng)第9講

1、課程主要內(nèi)容課程主要內(nèi)容操作系統(tǒng)引論（第操作系統(tǒng)引論（第1 1章）章）進(jìn)程管理（第進(jìn)程管理（第2-32-3章）章）存儲(chǔ)管理（第存儲(chǔ)管理（第4 4章）章）設(shè)備管理（第設(shè)備管理（第5 5章）章）文件管理（第文件管理（第6 6章）章）操作系統(tǒng)接口（第操作系統(tǒng)接口（第7 7章）章）UnixUnix操作系統(tǒng)（第操作系統(tǒng)（第1010章）章）Process Management Process Management 進(jìn)程管理進(jìn)程管理u進(jìn)程的基本概念與控制進(jìn)程的基本概念與控制v進(jìn)程的基本概念進(jìn)程的基本概念v進(jìn)程控制進(jìn)程控制v線程的基本概念線程的基本概念vUNIXUNIX中進(jìn)程的描述與控制中進(jìn)程的描述與控制u進(jìn)

2、程同步與通信進(jìn)程同步與通信v進(jìn)程同步進(jìn)程同步v經(jīng)典進(jìn)程的同步問(wèn)題經(jīng)典進(jìn)程的同步問(wèn)題v管程機(jī)制管程機(jī)制v進(jìn)程通信進(jìn)程通信vUNIXUNIX中進(jìn)程的同步與通信中進(jìn)程的同步與通信u處理機(jī)調(diào)度與死鎖（第處理機(jī)調(diào)度與死鎖（第3 3章）章）第第3 3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖 在多道程序環(huán)境下，一個(gè)作業(yè)從提交到執(zhí)行，通常在多道程序環(huán)境下，一個(gè)作業(yè)從提交到執(zhí)行，通常都要經(jīng)歷多級(jí)調(diào)度，如都要經(jīng)歷多級(jí)調(diào)度，如高級(jí)調(diào)度高級(jí)調(diào)度、低級(jí)調(diào)度低級(jí)調(diào)度、中級(jí)調(diào)度中級(jí)調(diào)度等。而系統(tǒng)的運(yùn)行性能在很大程度上取決于調(diào)度，因此等。而系統(tǒng)的運(yùn)行性能在很大程度上取決于調(diào)度，因此調(diào)度便成為多道程序的關(guān)鍵。調(diào)度便成為多道程序的

3、關(guān)鍵。 在多道程序環(huán)境下，由于多個(gè)進(jìn)程的并發(fā)執(zhí)行，改在多道程序環(huán)境下，由于多個(gè)進(jìn)程的并發(fā)執(zhí)行，改善了系統(tǒng)資源的利用率并提高了系統(tǒng)的處理能力，然而，善了系統(tǒng)資源的利用率并提高了系統(tǒng)的處理能力，然而，多個(gè)進(jìn)程的并發(fā)執(zhí)行也帶來(lái)了新的問(wèn)題多個(gè)進(jìn)程的并發(fā)執(zhí)行也帶來(lái)了新的問(wèn)題-死鎖。死鎖。第第3 3章章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖u處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次u調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則u調(diào)度算法調(diào)度算法u實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度uUNIXUNIX系統(tǒng)中進(jìn)程的調(diào)度系統(tǒng)中進(jìn)程的調(diào)度v產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件v預(yù)防死鎖的方法預(yù)防死鎖的方法v死鎖的避免死鎖的避免v死鎖

4、的檢測(cè)與解除死鎖的檢測(cè)與解除v本章作業(yè)本章作業(yè)3.1 3.1 處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次 在多道程序環(huán)境下，一個(gè)作業(yè)從提交直到完成，在多道程序環(huán)境下，一個(gè)作業(yè)從提交直到完成，往往要經(jīng)歷多級(jí)調(diào)度。往往要經(jīng)歷多級(jí)調(diào)度。 在不同操作系統(tǒng)中所采用的調(diào)度層次不完全相在不同操作系統(tǒng)中所采用的調(diào)度層次不完全相同。同。 有些系統(tǒng)中：僅采用一級(jí)調(diào)度；有些系統(tǒng)中：僅采用一級(jí)調(diào)度； 另一些系統(tǒng)：可能采用兩級(jí)或三級(jí)調(diào)度。另一些系統(tǒng)：可能采用兩級(jí)或三級(jí)調(diào)度。 在執(zhí)行調(diào)度時(shí)所采用的調(diào)度算法也可能不同。在執(zhí)行調(diào)度時(shí)所采用的調(diào)度算法也可能不同。一、調(diào)度的層次一、調(diào)度的層次 如圖所示。如圖所示。中級(jí)調(diào)度中級(jí)調(diào)度新建態(tài)新建

5、態(tài)掛起就緒掛起就緒態(tài)態(tài)掛起等待掛起等待態(tài)態(tài)高級(jí)調(diào)度高級(jí)調(diào)度低級(jí)調(diào)度低級(jí)調(diào)度運(yùn)行態(tài)運(yùn)行態(tài)就緒態(tài)就緒態(tài)等待態(tài)等待態(tài)終止終止態(tài)態(tài)二、高級(jí)調(diào)度（二、高級(jí)調(diào)度（1 1） 一個(gè)作業(yè)從提交開(kāi)始，往往要經(jīng)歷三級(jí)調(diào)一個(gè)作業(yè)從提交開(kāi)始，往往要經(jīng)歷三級(jí)調(diào)度：度：高級(jí)調(diào)度高級(jí)調(diào)度、低級(jí)調(diào)度低級(jí)調(diào)度、中級(jí)調(diào)度中級(jí)調(diào)度。有關(guān)作業(yè)的幾個(gè)基本概念有關(guān)作業(yè)的幾個(gè)基本概念（1 1）作業(yè)）作業(yè)（2 2）作業(yè)步）作業(yè)步（3 3）作業(yè)流）作業(yè)流（4 4）作業(yè)控制塊（）作業(yè)控制塊（JCBJCB） 是作業(yè)在系統(tǒng)中存在的標(biāo)志，其中保存了系是作業(yè)在系統(tǒng)中存在的標(biāo)志，其中保存了系統(tǒng)對(duì)作業(yè)進(jìn)行管理和調(diào)度所需的全部信息。統(tǒng)對(duì)作業(yè)進(jìn)行管理和調(diào)度所需的

6、全部信息。二、高級(jí)調(diào)度（二、高級(jí)調(diào)度（2 2）高級(jí)調(diào)度高級(jí)調(diào)度（長(zhǎng)程（長(zhǎng)程/ /作業(yè)作業(yè)/ /宏觀調(diào)度）宏觀調(diào)度）（1 1）用于決定把外存上處于后備隊(duì)列中的哪些作）用于決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，排在就緒隊(duì)列上。資源，排在就緒隊(duì)列上。（2 2）在批處理系統(tǒng)中）在批處理系統(tǒng)中, ,大多配有作業(yè)調(diào)度大多配有作業(yè)調(diào)度, ,但在分但在分時(shí)系統(tǒng)及實(shí)時(shí)系統(tǒng)中時(shí)系統(tǒng)及實(shí)時(shí)系統(tǒng)中, ,一般不配置一般不配置. .（3 3）作業(yè)調(diào)度執(zhí)行頻率很低）作業(yè)調(diào)度執(zhí)行頻率很低, ,通常為幾分鐘一次通常為幾分鐘一次, ,甚至更久。甚至

7、更久。u高級(jí)調(diào)度需解決的問(wèn)題高級(jí)調(diào)度需解決的問(wèn)題（1 1）主要任務(wù)是從外存后備隊(duì)列中）主要任務(wù)是從外存后備隊(duì)列中選擇多少作業(yè)選擇多少作業(yè)進(jìn)入就緒隊(duì)進(jìn)入就緒隊(duì)列，即允許多少作業(yè)同時(shí)在內(nèi)存中運(yùn)行（多道程序的列，即允許多少作業(yè)同時(shí)在內(nèi)存中運(yùn)行（多道程序的“道道或度或度” ）。若作業(yè)太多，則可能會(huì)影響系統(tǒng)的服務(wù)質(zhì)量）。若作業(yè)太多，則可能會(huì)影響系統(tǒng)的服務(wù)質(zhì)量（如周轉(zhuǎn)時(shí)間太長(zhǎng)），若太少，又將導(dǎo)致系統(tǒng)資源利用率（如周轉(zhuǎn)時(shí)間太長(zhǎng)），若太少，又將導(dǎo)致系統(tǒng)資源利用率和吞吐量的下降。因此，應(yīng)根據(jù)系統(tǒng)的規(guī)模和運(yùn)行速度來(lái)和吞吐量的下降。因此，應(yīng)根據(jù)系統(tǒng)的規(guī)模和運(yùn)行速度來(lái)確定，同時(shí)確定，同時(shí)要求要求I/OI/O型進(jìn)程型進(jìn)

8、程與與CPUCPU型進(jìn)程型進(jìn)程中和中和調(diào)度。調(diào)度。（2 2）應(yīng)）應(yīng)將哪些作業(yè)從外存調(diào)入內(nèi)存將哪些作業(yè)從外存調(diào)入內(nèi)存，將取決于調(diào)度算法（先，將取決于調(diào)度算法（先來(lái)先服務(wù)、短作業(yè)優(yōu)先等）。來(lái)先服務(wù)、短作業(yè)優(yōu)先等）。 二、高級(jí)調(diào)度（二、高級(jí)調(diào)度（3 3）三、低級(jí)調(diào)度三、低級(jí)調(diào)度( (短程短程/CPU/CPU/進(jìn)程進(jìn)程/ /微觀調(diào)度微觀調(diào)度) )（1 1）主要任務(wù)是從就緒隊(duì)列中選擇）主要任務(wù)是從就緒隊(duì)列中選擇一個(gè)一個(gè)進(jìn)程來(lái)執(zhí)行并分配處理機(jī)。進(jìn)程來(lái)執(zhí)行并分配處理機(jī)。（2 2）是）是OSOS中最基本的調(diào)度。中最基本的調(diào)度。（3 3）調(diào)度頻率非常高，一般幾十毫秒一次。）調(diào)度頻率非常高，一般幾十毫秒一次。（4

9、 4）常采用）常采用非搶占（非剝奪）方式非搶占（非剝奪）方式和和搶占搶占（剝奪剝奪）方式方式兩種。兩種。（5 5）引起進(jìn)程調(diào)度的因素：）引起進(jìn)程調(diào)度的因素：v進(jìn)程正常終止或異常終止進(jìn)程正常終止或異常終止v正在執(zhí)行的進(jìn)程因某種原因而阻塞正在執(zhí)行的進(jìn)程因某種原因而阻塞v在引入時(shí)間片的系統(tǒng)中，時(shí)間片用完。在引入時(shí)間片的系統(tǒng)中，時(shí)間片用完。v在搶占調(diào)度方式中，就緒隊(duì)列中某進(jìn)程的優(yōu)先權(quán)變得比當(dāng)在搶占調(diào)度方式中，就緒隊(duì)列中某進(jìn)程的優(yōu)先權(quán)變得比當(dāng)前正執(zhí)行的進(jìn)程高。前正執(zhí)行的進(jìn)程高。調(diào)度方式調(diào)度方式-非搶占式進(jìn)程調(diào)度、搶占式進(jìn)程調(diào)度非搶占式進(jìn)程調(diào)度、搶占式進(jìn)程調(diào)度u非搶占方式非搶占方式：一旦把處理機(jī)分配給某進(jìn)

10、程后，便讓該進(jìn)：一旦把處理機(jī)分配給某進(jìn)程后，便讓該進(jìn)程程一直執(zhí)行一直執(zhí)行，直到該進(jìn)程完成或因某事件而被阻塞，才，直到該進(jìn)程完成或因某事件而被阻塞，才再把處理機(jī)分配給其它進(jìn)程，決不允許某進(jìn)程搶占已分再把處理機(jī)分配給其它進(jìn)程，決不允許某進(jìn)程搶占已分配出去的處理機(jī)。配出去的處理機(jī)。 實(shí)現(xiàn)簡(jiǎn)單，系統(tǒng)開(kāi)銷(xiāo)小，常用于批處理系統(tǒng)；但不利實(shí)現(xiàn)簡(jiǎn)單，系統(tǒng)開(kāi)銷(xiāo)小，常用于批處理系統(tǒng)；但不利于處理緊急任務(wù)，故實(shí)時(shí)、分時(shí)系統(tǒng)不宜采用。于處理緊急任務(wù)，故實(shí)時(shí)、分時(shí)系統(tǒng)不宜采用。u搶占方式搶占方式: : 允許調(diào)度程序根據(jù)某種原則（時(shí)間片、優(yōu)先允許調(diào)度程序根據(jù)某種原則（時(shí)間片、優(yōu)先權(quán)、短進(jìn)程優(yōu)先），權(quán)、短進(jìn)程優(yōu)先），停止停止

11、正在執(zhí)行正在執(zhí)行的進(jìn)程，而將處理機(jī)的進(jìn)程，而將處理機(jī)重新分配給另一進(jìn)程。重新分配給另一進(jìn)程。 有利于處理緊急任務(wù)，故實(shí)時(shí)與分時(shí)系統(tǒng)中常采用。有利于處理緊急任務(wù)，故實(shí)時(shí)與分時(shí)系統(tǒng)中常采用。四、中級(jí)調(diào)度（中程四、中級(jí)調(diào)度（中程/ /交換調(diào)度）交換調(diào)度） 在內(nèi)存和外存對(duì)換區(qū)之間按照給定的原則和在內(nèi)存和外存對(duì)換區(qū)之間按照給定的原則和策略策略選擇進(jìn)程對(duì)換選擇進(jìn)程對(duì)換，以解決內(nèi)存緊張問(wèn)題，從，以解決內(nèi)存緊張問(wèn)題，從而提高內(nèi)存的利用率和系統(tǒng)吞吐量，常用于分而提高內(nèi)存的利用率和系統(tǒng)吞吐量，常用于分時(shí)系統(tǒng)或具有虛擬存儲(chǔ)器的系統(tǒng)中。時(shí)系統(tǒng)或具有虛擬存儲(chǔ)器的系統(tǒng)中。3.23.2 調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則調(diào)度隊(duì)列模型和

12、調(diào)度準(zhǔn)則 在在OSOS中的任何一種調(diào)度中，都將涉及中的任何一種調(diào)度中，都將涉及到到進(jìn)程隊(duì)列進(jìn)程隊(duì)列，由此形成了三種類型的調(diào)度，由此形成了三種類型的調(diào)度隊(duì)列模型。隊(duì)列模型。v僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型v具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型v同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型一、僅有進(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)度時(shí)間片完時(shí)間片完CPU進(jìn)程完成進(jìn)程完成等待事件等待事件事事件件出出現(xiàn)現(xiàn)交互用戶交互用戶二、具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型二、具

13、有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型就就 緒緒 隊(duì)隊(duì) 列列阻阻 塞塞 隊(duì)隊(duì) 列列時(shí)間片完時(shí)間片完后后備備隊(duì)隊(duì)列列進(jìn)程調(diào)度進(jìn)程調(diào)度CPU進(jìn)程完成進(jìn)程完成事事件件出出現(xiàn)現(xiàn)等待事件等待事件1等待事件等待事件2等待事件等待事件n作業(yè)作業(yè)調(diào)度調(diào)度 就就 緒緒 隊(duì)隊(duì) 列列掛掛 起起 就就 緒緒 隊(duì)隊(duì) 列列時(shí)間片完時(shí)間片完阻阻 塞塞 隊(duì)隊(duì) 列列后后備備隊(duì)隊(duì)列列進(jìn)程調(diào)度進(jìn)程調(diào)度CPU進(jìn)程完成進(jìn)程完成事事件件出出現(xiàn)現(xiàn)等待事件等待事件作業(yè)作業(yè)調(diào)度調(diào)度掛掛 起起 阻阻 塞塞 隊(duì)隊(duì) 列列中級(jí)調(diào)度中級(jí)調(diào)度事件出現(xiàn)事件出現(xiàn)掛起掛起掛起掛起交互型作業(yè)交互型作業(yè)批量作業(yè)批量作業(yè)三、同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型三、同時(shí)具有三級(jí)調(diào)度

14、的調(diào)度隊(duì)列模型四、選擇調(diào)度方式和算法的若干準(zhǔn)則（四、選擇調(diào)度方式和算法的若干準(zhǔn)則（1 1） 在一個(gè)操作系統(tǒng)的設(shè)計(jì)中，應(yīng)如何選擇調(diào)度方式和在一個(gè)操作系統(tǒng)的設(shè)計(jì)中，應(yīng)如何選擇調(diào)度方式和算法，在很大程度上取決于操作系統(tǒng)的類型及其目標(biāo)，算法，在很大程度上取決于操作系統(tǒng)的類型及其目標(biāo)，選擇調(diào)度方式和算法的準(zhǔn)則有：選擇調(diào)度方式和算法的準(zhǔn)則有：u 面向用戶的準(zhǔn)則面向用戶的準(zhǔn)則v周轉(zhuǎn)時(shí)間短周轉(zhuǎn)時(shí)間短v響應(yīng)時(shí)間快響應(yīng)時(shí)間快v截止時(shí)間的保證截止時(shí)間的保證v優(yōu)先權(quán)準(zhǔn)則優(yōu)先權(quán)準(zhǔn)則u 面向系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則v系統(tǒng)吞吐量系統(tǒng)吞吐量v處理機(jī)利用率好處理機(jī)利用率好v各類資源平衡利用各類資源平衡利用u 最優(yōu)準(zhǔn)則最優(yōu)準(zhǔn)則v

15、 最大的最大的CPUCPU利用率利用率v 最大的吞吐量最大的吞吐量v 最短的周轉(zhuǎn)時(shí)間最短的周轉(zhuǎn)時(shí)間v 最短的等待時(shí)間最短的等待時(shí)間v 最短的響應(yīng)時(shí)間最短的響應(yīng)時(shí)間四、選擇調(diào)度方式和算法的若干準(zhǔn)則（四、選擇調(diào)度方式和算法的若干準(zhǔn)則（2 2）CPUCPU利用率利用率=CPU=CPU有效工作時(shí)間有效工作時(shí)間/CPU/CPU總的運(yùn)行時(shí)間，總的運(yùn)行時(shí)間， CPU CPU總的運(yùn)行時(shí)間總的運(yùn)行時(shí)間=CPU=CPU有效工作時(shí)間有效工作時(shí)間+CPU+CPU空閑等待時(shí)空閑等待時(shí)間。間。響應(yīng)時(shí)間響應(yīng)時(shí)間-交互式進(jìn)程從提交一個(gè)請(qǐng)求交互式進(jìn)程從提交一個(gè)請(qǐng)求( (命令命令) )到接收到接收到響應(yīng)之間的時(shí)間間隔稱響應(yīng)時(shí)間。

16、到響應(yīng)之間的時(shí)間間隔稱響應(yīng)時(shí)間。周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間-批處理用戶從作業(yè)提交給系統(tǒng)開(kāi)始，到作批處理用戶從作業(yè)提交給系統(tǒng)開(kāi)始，到作業(yè)完成為止的時(shí)間間隔稱作業(yè)周轉(zhuǎn)時(shí)間，實(shí)際上它業(yè)完成為止的時(shí)間間隔稱作業(yè)周轉(zhuǎn)時(shí)間，實(shí)際上它是作業(yè)在系統(tǒng)里的等待時(shí)間與運(yùn)行時(shí)間之和。應(yīng)使是作業(yè)在系統(tǒng)里的等待時(shí)間與運(yùn)行時(shí)間之和。應(yīng)使作業(yè)周轉(zhuǎn)時(shí)間或平均作業(yè)周轉(zhuǎn)時(shí)間盡可能短。作業(yè)周轉(zhuǎn)時(shí)間或平均作業(yè)周轉(zhuǎn)時(shí)間盡可能短。四、選擇調(diào)度方式和算法的若干準(zhǔn)則（四、選擇調(diào)度方式和算法的若干準(zhǔn)則（3 3）帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間/ /進(jìn)程要求運(yùn)行時(shí)進(jìn)程要求運(yùn)行時(shí)間間吞吐量吞吐量-單位時(shí)間內(nèi)處理的作業(yè)數(shù)。單位時(shí)間內(nèi)處理的作業(yè)數(shù)。公平性

17、公平性-確保每個(gè)用戶每個(gè)進(jìn)程獲得合理的確保每個(gè)用戶每個(gè)進(jìn)程獲得合理的CPUCPU份額或其他資源份額，不會(huì)出現(xiàn)餓死份額或其他資源份額，不會(huì)出現(xiàn)餓死情況。情況。3.3 3.3 調(diào)度算法調(diào)度算法u先來(lái)先服務(wù)調(diào)度算法先來(lái)先服務(wù)調(diào)度算法u短作業(yè)短作業(yè)/ /進(jìn)程優(yōu)先調(diào)度算法進(jìn)程優(yōu)先調(diào)度算法u時(shí)間片輪轉(zhuǎn)調(diào)度算法時(shí)間片輪轉(zhuǎn)調(diào)度算法u優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法u高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法u多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法 進(jìn)程調(diào)度的核心問(wèn)題就是采用什么樣的算法進(jìn)程調(diào)度的核心問(wèn)題就是采用什么樣的算法將處理機(jī)分配給進(jìn)程，常用的進(jìn)程調(diào)度算法有：將處理機(jī)分配給進(jìn)程，常用的進(jìn)程調(diào)度算法有：一、先來(lái)

18、先服務(wù)調(diào)度算法一、先來(lái)先服務(wù)調(diào)度算法FCFSFCFSu 基本思想基本思想: :按照進(jìn)程進(jìn)入就緒隊(duì)列的先后次序來(lái)分配處理機(jī)。按照進(jìn)程進(jìn)入就緒隊(duì)列的先后次序來(lái)分配處理機(jī)。 一般采用非剝奪的調(diào)度方式。一般采用非剝奪的調(diào)度方式。u ExampleExample: :進(jìn)程名進(jìn)程名 到達(dá)時(shí)間到達(dá)時(shí)間 服務(wù)時(shí)間服務(wù)時(shí)間 A 0 1 B 1 100 C 2 1 D 3 100u 該調(diào)度的該調(diào)度的GanttGantt（甘特）圖為（甘特）圖為: :u 平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間=(=(1-0)+(101-1)+(102-2)+(202-3)(1-0)+(101-1)+(102-2)+(202-3)）/4=100/4

19、=100u 平均等待時(shí)間平均等待時(shí)間=(0-0)+(1-1)+(101-2)+(102-3)/4 = 49.5=(0-0)+(1-1)+(101-2)+(102-3)/4 = 49.5u 平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間= =？DBCA0 1 2 3 101 102 202 0 1 2 3 101 102 202 甘特圖甘特圖(Gantt)是作業(yè)排序中是作業(yè)排序中最常用的一種工具，最早由最常用的一種工具，最早由Henry L. Gantt于于1917年提年提出。這種方法基于作業(yè)排序的出。這種方法基于作業(yè)排序的目的，是將任務(wù)與時(shí)間聯(lián)系起目的，是將任務(wù)與時(shí)間聯(lián)系起來(lái)的表現(xiàn)形式之一來(lái)的表現(xiàn)形式之一。

20、 一、一、FCFSFCFS調(diào)度算法（續(xù)）調(diào)度算法（續(xù)）u改變到達(dá)順序改變到達(dá)順序: : 進(jìn)程名進(jìn)程名 到達(dá)時(shí)間到達(dá)時(shí)間 服務(wù)時(shí)間服務(wù)時(shí)間 A 0 1 B 1 100 D 2 100 C 3 1u該調(diào)度的該調(diào)度的GanttGantt圖為圖為: :u平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間= =(1-0)+(101-1)+(202-3)+(201-2)/4=124.25u平均等待時(shí)間平均等待時(shí)間= =(0-0)+(1-1)+(201-3)+(101-2)/4 = 74.25u平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間= =？周轉(zhuǎn)周轉(zhuǎn)T100100124.25124.25等待等待T49.549.574.2574.25CBDA

21、0 1 2 3 101 201 202 0 1 2 3 101 201 202 FCFSFCFS調(diào)度算法存在的問(wèn)題調(diào)度算法存在的問(wèn)題 從表面上，先來(lái)先服務(wù)對(duì)于所有作業(yè)是公平的，從表面上，先來(lái)先服務(wù)對(duì)于所有作業(yè)是公平的，即按照它們到來(lái)的先后次序進(jìn)行服務(wù)。但如果一個(gè)長(zhǎng)即按照它們到來(lái)的先后次序進(jìn)行服務(wù)。但如果一個(gè)長(zhǎng)作業(yè)先到達(dá)系統(tǒng)，就會(huì)使許多短作業(yè)等待很長(zhǎng)的時(shí)間，作業(yè)先到達(dá)系統(tǒng)，就會(huì)使許多短作業(yè)等待很長(zhǎng)的時(shí)間，從而引起許多短作業(yè)用戶的不滿。從而引起許多短作業(yè)用戶的不滿。 所以，現(xiàn)在操作系統(tǒng)中，已很少用該算法作為主所以，現(xiàn)在操作系統(tǒng)中，已很少用該算法作為主要調(diào)度策略，尤其是在分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)中。但它要

22、調(diào)度策略，尤其是在分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)中。但它常被結(jié)合在其它調(diào)度策略中使用。常被結(jié)合在其它調(diào)度策略中使用。二、短作業(yè)二、短作業(yè)/ /進(jìn)程優(yōu)先調(diào)度算法進(jìn)程優(yōu)先調(diào)度算法SJF/SPFSJF/SPFu 短作業(yè)優(yōu)先調(diào)度算法（短作業(yè)優(yōu)先調(diào)度算法（SJFSJF）v用于作業(yè)調(diào)度用于作業(yè)調(diào)度v主要任務(wù)是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最主要任務(wù)是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。u 短進(jìn)程優(yōu)先調(diào)度算法（短進(jìn)程優(yōu)先調(diào)度算法（SPFSPF）v用于進(jìn)程調(diào)度用于進(jìn)程調(diào)度v主要任務(wù)是從就緒隊(duì)列中選出一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，主要任務(wù)是從就緒隊(duì)列

23、中選出一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它。將處理機(jī)分配給它。v可采用搶占（剝奪）（有時(shí)稱為可采用搶占（剝奪）（有時(shí)稱為最短剩余時(shí)間優(yōu)先最短剩余時(shí)間優(yōu)先（shortest-remaining-time-firstshortest-remaining-time-first）調(diào)度）或者非搶占）調(diào)度）或者非搶占（非剝奪）調(diào)度方式。（非剝奪）調(diào)度方式。二、二、SJ(P)F -SJ(P)F -非搶占式非搶占式u到達(dá)順序到達(dá)順序: : 進(jìn)程名進(jìn)程名 到達(dá)時(shí)間到達(dá)時(shí)間 服務(wù)時(shí)間服務(wù)時(shí)間 A 0 1 B 1 100 D 2 100 C 3 1u該調(diào)度的該調(diào)度的GanttGantt圖為圖為: :u平均周

24、轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間= =(1-0)+(101-1)+(102-3)+(202-2)/4=100u平均等待時(shí)間平均等待時(shí)間= =(0-0)+(1-1)+(101-3)+(102-2)/4 = 49.5u平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間=？FCFSFCFSSPFSPF周轉(zhuǎn)周轉(zhuǎn)T124.25124.25100100等待等待T74.2574.2549.549.50 1 2 3 101 102 202 0 1 2 3 101 102 202 DBCA二、短作業(yè)二、短作業(yè)/ /進(jìn)程優(yōu)先調(diào)度算法進(jìn)程優(yōu)先調(diào)度算法- -搶占式搶占式u 到達(dá)順序到達(dá)順序: : 進(jìn)程名進(jìn)程名 到達(dá)時(shí)間到達(dá)時(shí)間 服務(wù)時(shí)間服務(wù)時(shí)間 A

25、 0 1 B 1 100 D 2 100 C 3 1u 該調(diào)度的該調(diào)度的GanttGantt圖為圖為: :u 平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間=(1-0)+(102-1)+(4-3)+(202-2)=(1-0)+(102-1)+(4-3)+(202-2)）/4=75.75/4=75.75u 平均等待時(shí)間平均等待時(shí)間=(0-0)+(4-3)+(3-3)+(102-2)/4 = 25.25=(0-0)+(4-3)+(3-3)+(102-2)/4 = 25.25u 平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間= =？BCDBBA0 1 2 3 4 102 202 0 1 2 3 4 102 202 FCFSFCFSSP

26、F-SPF-非非SPF-SPF-搶搶周轉(zhuǎn)周轉(zhuǎn)T124.25124.2510010075.7575.75等待等待T74.2574.2549.549.525.2525.25uEgEg： 進(jìn)程進(jìn)程 到達(dá)時(shí)間到達(dá)時(shí)間 服務(wù)時(shí)間服務(wù)時(shí)間P P1 10.00.07 7 P P2 22.02.04 4 P P3 34.04.01 1 P P4 45.05.04 4uSPF (SPF (非搶占式非搶占式) )u平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間=(7-0)+(12-2)+(8-4)+(16-5)/4=8=(7-0)+(12-2)+(8-4)+(16-5)/4=8u平均等待時(shí)間平均等待時(shí)間 =(0-0)+(8-2)+(7

27、-4)+(12-5)/4 = 4=(0-0)+(8-2)+(7-4)+(12-5)/4 = 4u平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間= =？SPFSPF（非搶占式）調(diào)度（非搶占式）調(diào)度73160812P1P3P2P4SPFSPF搶占式調(diào)度搶占式調(diào)度進(jìn)程進(jìn)程到達(dá)時(shí)間到達(dá)時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間P P1 10.00.07 7 P P2 22.02.04 4 P P3 34.04.01 1 P P4 45.05.04 4uSPF (SPF (搶占式搶占式) )u平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間=(16-0)+(7-2)+(5-4)+(11-5)/4=7=(16-0)+(7-2)+(5-4)+(11-5)/4=7u平

28、均等待時(shí)間平均等待時(shí)間=(11-2)+(5-4)+(4-4)+(7-5)/4=3=(11-2)+(5-4)+(4-4)+(7-5)/4=3u平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間= =？P1P3P242110P457P2P116FCFSFCFS先來(lái)先服務(wù)調(diào)度先來(lái)先服務(wù)調(diào)度進(jìn)程進(jìn)程到達(dá)時(shí)間到達(dá)時(shí)間服務(wù)時(shí)間服務(wù)時(shí)間P P1 10.00.07 7 P P2 22.02.04 4 P P3 34.04.01 1 P P4 45.05.04 4uFCFSFCFSu平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間=(7-0)+(11-2)+(12-4)+(16-5)/4=8.75=(7-0)+(11-2)+(12-4)+(16-5)/

29、4=8.75u平均等待時(shí)間平均等待時(shí)間 =(0+(7-2)+(11-4)+(12-5)/4 =4.75=(0+(7-2)+(11-4)+(12-5)/4 =4.75u平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間= =？P142110P257P41612P3SPFSPF與與FCFSFCFS的比較的比較FCFSFCFS非搶占非搶占SPFSPF搶占搶占SPFSPF吞吐量吞吐量0-7ms0-7ms1 11 12 2平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間8.758.758 87 7平均等待時(shí)間平均等待時(shí)間4.754.754 43 3SJ(P)FSJ(P)F短作業(yè)短作業(yè)/ /進(jìn)程優(yōu)先調(diào)度的優(yōu)缺點(diǎn)進(jìn)程優(yōu)先調(diào)度的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)：優(yōu)點(diǎn)： 1 1）能有效降低作業(yè)的平均等待時(shí)間；