操作系統(tǒng)_第三章處理器調(diào)度20160930

1、l 調(diào)度是系統(tǒng)將計(jì)算機(jī)資源分配給進(jìn)程。調(diào)度是系統(tǒng)將計(jì)算機(jī)資源分配給進(jìn)程。l 在單道程序環(huán)境下，只有一個(gè)進(jìn)程存在，計(jì)算機(jī)在單道程序環(huán)境下，只有一個(gè)進(jìn)程存在，計(jì)算機(jī)的所有資源由一個(gè)進(jìn)程獨(dú)占，沒(méi)有資源競(jìng)爭(zhēng)問(wèn)題。的所有資源由一個(gè)進(jìn)程獨(dú)占，沒(méi)有資源競(jìng)爭(zhēng)問(wèn)題。l 在多道程序環(huán)境下，多個(gè)進(jìn)程并發(fā)運(yùn)行，各進(jìn)程在多道程序環(huán)境下，多個(gè)進(jìn)程并發(fā)運(yùn)行，各進(jìn)程之間存在資源的相互競(jìng)爭(zhēng)，特別是對(duì)處理器資源之間存在資源的相互競(jìng)爭(zhēng)，特別是對(duì)處理器資源的競(jìng)爭(zhēng)，從而影響到系統(tǒng)性能。的競(jìng)爭(zhēng)，從而影響到系統(tǒng)性能。l 處理器調(diào)度指在多道程序環(huán)境下將處理器分配給處理器調(diào)度指在多道程序環(huán)境下將處理器分配給各進(jìn)程。在處理器調(diào)度中，合理的調(diào)度算

2、法能夠各進(jìn)程。在處理器調(diào)度中，合理的調(diào)度算法能夠提高處理器的處理能力和系統(tǒng)性能，滿足用戶需提高處理器的處理能力和系統(tǒng)性能，滿足用戶需求。求。2/1363.1 3.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念3.2 3.2 調(diào)度算法調(diào)度算法3.3 3.3 實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度3.4 3.4 多處理機(jī)系統(tǒng)中的調(diào)度多處理機(jī)系統(tǒng)中的調(diào)度3.5 3.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件3.6 3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法3.7 3.7 死鎖的檢測(cè)和解除死鎖的檢測(cè)和解除3.1 處理器調(diào)度的層次l 在內(nèi)存中并發(fā)的進(jìn)程之間構(gòu)成的是一種競(jìng)爭(zhēng)使用在內(nèi)存中并發(fā)的進(jìn)程之間構(gòu)成的是一種競(jìng)爭(zhēng)使用處理器

3、的關(guān)系。處理器的關(guān)系。l 低級(jí)調(diào)度將處理器分配給進(jìn)程。低級(jí)調(diào)度將處理器分配給進(jìn)程。l 低級(jí)調(diào)度受到內(nèi)存中用戶作業(yè)數(shù)的影響，處理器低級(jí)調(diào)度受到內(nèi)存中用戶作業(yè)數(shù)的影響，處理器調(diào)度不只是低級(jí)調(diào)度問(wèn)題，還與內(nèi)存中能夠接納調(diào)度不只是低級(jí)調(diào)度問(wèn)題，還與內(nèi)存中能夠接納用戶作業(yè)的個(gè)數(shù)有關(guān)，與作業(yè)調(diào)度有關(guān)，作業(yè)調(diào)用戶作業(yè)的個(gè)數(shù)有關(guān)，與作業(yè)調(diào)度有關(guān)，作業(yè)調(diào)度為高級(jí)調(diào)度。度為高級(jí)調(diào)度。l 為了減輕內(nèi)存的負(fù)擔(dān)，外存作為內(nèi)存的補(bǔ)充，進(jìn)為了減輕內(nèi)存的負(fù)擔(dān)，外存作為內(nèi)存的補(bǔ)充，進(jìn)程可以在外存與內(nèi)存之間對(duì)換。對(duì)換到外存的進(jìn)程可以在外存與內(nèi)存之間對(duì)換。對(duì)換到外存的進(jìn)程調(diào)入內(nèi)存為中級(jí)調(diào)度，中級(jí)調(diào)度也會(huì)影響內(nèi)存程調(diào)入內(nèi)存為中級(jí)調(diào)度

4、，中級(jí)調(diào)度也會(huì)影響內(nèi)存中進(jìn)程的調(diào)度，處理器調(diào)度與中級(jí)調(diào)度有關(guān)。中進(jìn)程的調(diào)度，處理器調(diào)度與中級(jí)調(diào)度有關(guān)。 3.1 處理器調(diào)度的層次l 處理器調(diào)度劃分為處理器調(diào)度劃分為3個(gè)層次：高級(jí)調(diào)度、中級(jí)調(diào)度個(gè)層次：高級(jí)調(diào)度、中級(jí)調(diào)度和低級(jí)調(diào)度。進(jìn)程調(diào)度是處理器調(diào)度的核心。和低級(jí)調(diào)度。進(jìn)程調(diào)度是處理器調(diào)度的核心。l 用戶作業(yè)從提交給系統(tǒng)開(kāi)始，直到運(yùn)行結(jié)束退出用戶作業(yè)從提交給系統(tǒng)開(kāi)始，直到運(yùn)行結(jié)束退出系統(tǒng)為止，將經(jīng)歷高級(jí)調(diào)度、中級(jí)調(diào)度和低級(jí)調(diào)系統(tǒng)為止，將經(jīng)歷高級(jí)調(diào)度、中級(jí)調(diào)度和低級(jí)調(diào)度。度。3.1.1 高級(jí)調(diào)度高級(jí)調(diào)度1 1作業(yè)及作業(yè)分類作業(yè)及作業(yè)分類 作業(yè)由一組統(tǒng)一管理和操作的進(jìn)程集合構(gòu)成，是作業(yè)由一組統(tǒng)一管

5、理和操作的進(jìn)程集合構(gòu)成，是用戶要求計(jì)算機(jī)系統(tǒng)完成的一項(xiàng)相對(duì)獨(dú)立的工作。用戶要求計(jì)算機(jī)系統(tǒng)完成的一項(xiàng)相對(duì)獨(dú)立的工作。l 作業(yè)可以是完成了編譯、鏈接之后的一個(gè)用戶程序，作業(yè)可以是完成了編譯、鏈接之后的一個(gè)用戶程序，也可以是用各種命令構(gòu)成的一個(gè)腳本。也可以是用各種命令構(gòu)成的一個(gè)腳本。l 根據(jù)需要處理工作的類型，作業(yè)分為計(jì)算型作業(yè)和根據(jù)需要處理工作的類型，作業(yè)分為計(jì)算型作業(yè)和I/OI/O型作業(yè)。型作業(yè)。l 在操作系統(tǒng)中，將需要在操作系統(tǒng)中，將需要CPUCPU處理為主的作業(yè)稱為計(jì)算處理為主的作業(yè)稱為計(jì)算型作業(yè)；將以型作業(yè)；將以I/OI/O過(guò)程為主的作業(yè)稱為過(guò)程為主的作業(yè)稱為I/OI/O型作業(yè)。型作業(yè)。l

6、 一般情況下，操作系統(tǒng)管理會(huì)對(duì)這兩種作業(yè)進(jìn)行區(qū)別一般情況下，操作系統(tǒng)管理會(huì)對(duì)這兩種作業(yè)進(jìn)行區(qū)別對(duì)待：對(duì)待：I/OI/O為主的作業(yè)，由于等待為主的作業(yè)，由于等待I/OI/O過(guò)程需要更多的過(guò)程需要更多的時(shí)間，執(zhí)行更慢；計(jì)算型為主的作業(yè)等待時(shí)間，執(zhí)行更慢；計(jì)算型為主的作業(yè)等待I/OI/O過(guò)程需過(guò)程需要的時(shí)間更短，執(zhí)行更快。要的時(shí)間更短，執(zhí)行更快。 3.1.1 高級(jí)調(diào)度高級(jí)調(diào)度l 作業(yè)也可以按照提交方式不同分為批處理作業(yè)和作業(yè)也可以按照提交方式不同分為批處理作業(yè)和終端型作業(yè)。終端型作業(yè)。l 在多道程序環(huán)境下，用戶的批處理作業(yè)被提交到在多道程序環(huán)境下，用戶的批處理作業(yè)被提交到系統(tǒng)的磁盤(pán)上，以批處理后備隊(duì)

7、列的形式進(jìn)行組系統(tǒng)的磁盤(pán)上，以批處理后備隊(duì)列的形式進(jìn)行組織，這樣的作業(yè)為批處理作業(yè)?？棧@樣的作業(yè)為批處理作業(yè)。l 批處理作業(yè)需要作業(yè)調(diào)度將后備隊(duì)列上的作業(yè)調(diào)批處理作業(yè)需要作業(yè)調(diào)度將后備隊(duì)列上的作業(yè)調(diào)度到內(nèi)存才能執(zhí)行。度到內(nèi)存才能執(zhí)行。l 對(duì)終端型作業(yè)用戶通過(guò)終端登錄到系統(tǒng)，直接將對(duì)終端型作業(yè)用戶通過(guò)終端登錄到系統(tǒng)，直接將作業(yè)置于內(nèi)存中。終端型作業(yè)不需要作業(yè)調(diào)度便作業(yè)置于內(nèi)存中。終端型作業(yè)不需要作業(yè)調(diào)度便能執(zhí)行。能執(zhí)行。3.1.1 3.1.1 高級(jí)調(diào)度（續(xù)）高級(jí)調(diào)度（續(xù)）l作業(yè)調(diào)度按照操作系統(tǒng)預(yù)先規(guī)定的作業(yè)調(diào)度策略，從磁盤(pán)作業(yè)調(diào)度按照操作系統(tǒng)預(yù)先規(guī)定的作業(yè)調(diào)度策略，從磁盤(pán)的作業(yè)后備隊(duì)列中選擇作

8、業(yè)調(diào)入內(nèi)存，為作業(yè)分配所需要的的作業(yè)后備隊(duì)列中選擇作業(yè)調(diào)入內(nèi)存，為作業(yè)分配所需要的資源并建立與作業(yè)相對(duì)應(yīng)的進(jìn)程。資源并建立與作業(yè)相對(duì)應(yīng)的進(jìn)程。l當(dāng)作業(yè)運(yùn)行的準(zhǔn)備工作完成后，作業(yè)調(diào)度啟動(dòng)作業(yè)運(yùn)行。當(dāng)作業(yè)運(yùn)行的準(zhǔn)備工作完成后，作業(yè)調(diào)度啟動(dòng)作業(yè)運(yùn)行。在作業(yè)運(yùn)行結(jié)束后，作業(yè)調(diào)度歸還并釋放作業(yè)占用的資源，在作業(yè)運(yùn)行結(jié)束后，作業(yè)調(diào)度歸還并釋放作業(yè)占用的資源，結(jié)束作業(yè)。結(jié)束作業(yè)。l作業(yè)調(diào)度也稱為高級(jí)調(diào)度或長(zhǎng)程調(diào)度。作業(yè)調(diào)度也稱為高級(jí)調(diào)度或長(zhǎng)程調(diào)度。l作業(yè)調(diào)度模型如圖作業(yè)調(diào)度模型如圖3.13.1所示。所示。圖圖3.1 3.1 作業(yè)調(diào)度模型作業(yè)調(diào)度模型提交提交作業(yè)后備隊(duì)列作業(yè)后備隊(duì)列用戶作業(yè)用戶作業(yè)進(jìn)程就緒隊(duì)列

9、進(jìn)程就緒隊(duì)列處理器處理器進(jìn)程阻塞隊(duì)列進(jìn)程阻塞隊(duì)列高級(jí)調(diào)度高級(jí)調(diào)度終端交互用戶終端交互用戶3.1.1 3.1.1 高級(jí)調(diào)度（續(xù)）高級(jí)調(diào)度（續(xù)）l作業(yè)與進(jìn)程之間存在著緊密的關(guān)系：作業(yè)與進(jìn)程之間存在著緊密的關(guān)系： 一個(gè)作業(yè)可能由一個(gè)進(jìn)程組成，運(yùn)行在一個(gè)進(jìn)程下；一個(gè)作業(yè)可能由一個(gè)進(jìn)程組成，運(yùn)行在一個(gè)進(jìn)程下；也可能由多個(gè)進(jìn)程組成，運(yùn)行在多個(gè)進(jìn)程下。作業(yè)是也可能由多個(gè)進(jìn)程組成，運(yùn)行在多個(gè)進(jìn)程下。作業(yè)是計(jì)算機(jī)處理任務(wù)的實(shí)體，進(jìn)程是計(jì)算機(jī)處理任務(wù)的執(zhí)計(jì)算機(jī)處理任務(wù)的實(shí)體，進(jìn)程是計(jì)算機(jī)處理任務(wù)的執(zhí)行體。沒(méi)有作業(yè)，進(jìn)程無(wú)事可做；沒(méi)有進(jìn)程，作業(yè)不行體。沒(méi)有作業(yè)，進(jìn)程無(wú)事可做；沒(méi)有進(jìn)程，作業(yè)不能完成。一個(gè)作業(yè)中創(chuàng)建多

10、少個(gè)進(jìn)程，有多少個(gè)進(jìn)程能完成。一個(gè)作業(yè)中創(chuàng)建多少個(gè)進(jìn)程，有多少個(gè)進(jìn)程運(yùn)行由作業(yè)的擁有者根據(jù)需要決定。運(yùn)行由作業(yè)的擁有者根據(jù)需要決定。l一個(gè)系統(tǒng)能夠接納作業(yè)的個(gè)數(shù)由系統(tǒng)的資源決定，特一個(gè)系統(tǒng)能夠接納作業(yè)的個(gè)數(shù)由系統(tǒng)的資源決定，特別是處理器和內(nèi)存資源。別是處理器和內(nèi)存資源。l一個(gè)系統(tǒng)能夠接納作業(yè)的個(gè)數(shù)稱為系統(tǒng)的多道度，也一個(gè)系統(tǒng)能夠接納作業(yè)的個(gè)數(shù)稱為系統(tǒng)的多道度，也稱為系統(tǒng)的多道程序度。稱為系統(tǒng)的多道程序度。3.1.1 3.1.1 高級(jí)調(diào)度（續(xù)）高級(jí)調(diào)度（續(xù)）l當(dāng)內(nèi)存中運(yùn)行的作業(yè)太多時(shí)，會(huì)影響到系統(tǒng)的服當(dāng)內(nèi)存中運(yùn)行的作業(yè)太多時(shí)，會(huì)影響到系統(tǒng)的服務(wù)質(zhì)量，影響到程序的正常執(zhí)行。操作系統(tǒng)為了務(wù)質(zhì)量，影響

11、到程序的正常執(zhí)行。操作系統(tǒng)為了保證進(jìn)入系統(tǒng)的用戶作業(yè)能夠順利運(yùn)行，會(huì)限制保證進(jìn)入系統(tǒng)的用戶作業(yè)能夠順利運(yùn)行，會(huì)限制系統(tǒng)的多道度。當(dāng)多道度達(dá)到限值時(shí)，只有完成系統(tǒng)的多道度。當(dāng)多道度達(dá)到限值時(shí)，只有完成一個(gè)作業(yè)后另一個(gè)作業(yè)才能進(jìn)入。一個(gè)作業(yè)后另一個(gè)作業(yè)才能進(jìn)入。3.1.1 3.1.1 高級(jí)調(diào)度（續(xù)）高級(jí)調(diào)度（續(xù)）作業(yè)調(diào)度中操作系統(tǒng)需要完成的工作：作業(yè)調(diào)度中操作系統(tǒng)需要完成的工作：l 確定作業(yè)的數(shù)據(jù)結(jié)構(gòu)。確定作業(yè)的數(shù)據(jù)結(jié)構(gòu)。 操作系統(tǒng)為每個(gè)進(jìn)入系統(tǒng)的作業(yè)分配一個(gè)與操作系統(tǒng)為每個(gè)進(jìn)入系統(tǒng)的作業(yè)分配一個(gè)與進(jìn)程控制塊（進(jìn)程控制塊（PCBPCB）類似的作業(yè)控制塊（）類似的作業(yè)控制塊（JCBJCB），），作業(yè)

12、控制塊中包括：作業(yè)的名稱、作業(yè)對(duì)資源的作業(yè)控制塊中包括：作業(yè)的名稱、作業(yè)對(duì)資源的需求信息、作業(yè)的資源使用信息、作業(yè)的控制方需求信息、作業(yè)的資源使用信息、作業(yè)的控制方式、作業(yè)類型、作業(yè)優(yōu)先級(jí)和作業(yè)狀態(tài)。式、作業(yè)類型、作業(yè)優(yōu)先級(jí)和作業(yè)狀態(tài)。 作業(yè)控制塊是作業(yè)的標(biāo)志，存在于作業(yè)的整作業(yè)控制塊是作業(yè)的標(biāo)志，存在于作業(yè)的整個(gè)過(guò)程中，只有作業(yè)完成或退出系統(tǒng)時(shí)，作業(yè)控個(gè)過(guò)程中，只有作業(yè)完成或退出系統(tǒng)時(shí)，作業(yè)控制塊才被撤銷。操作系統(tǒng)根據(jù)作業(yè)控制塊中的信制塊才被撤銷。操作系統(tǒng)根據(jù)作業(yè)控制塊中的信息對(duì)作業(yè)進(jìn)行調(diào)度和管理。息對(duì)作業(yè)進(jìn)行調(diào)度和管理。 作業(yè)名稱由用戶提供，系統(tǒng)將其寫(xiě)到作業(yè)控作業(yè)名稱由用戶提供，系統(tǒng)將其寫(xiě)

13、到作業(yè)控制塊中。制塊中。3.1.1 3.1.1 高級(jí)調(diào)度（續(xù)）高級(jí)調(diào)度（續(xù)） 作業(yè)對(duì)資源的需求信息包括估計(jì)作業(yè)執(zhí)行時(shí)作業(yè)對(duì)資源的需求信息包括估計(jì)作業(yè)執(zhí)行時(shí)間、作業(yè)最遲完成時(shí)間、作業(yè)要求的內(nèi)存量、作間、作業(yè)最遲完成時(shí)間、作業(yè)要求的內(nèi)存量、作業(yè)要求輸入輸出設(shè)備的類型和臺(tái)數(shù)、作業(yè)要求的業(yè)要求輸入輸出設(shè)備的類型和臺(tái)數(shù)、作業(yè)要求的文件量和輸出量，這些信息由用戶提供。文件量和輸出量，這些信息由用戶提供。 作業(yè)的資源使用信息包括作業(yè)進(jìn)入系統(tǒng)時(shí)間、作業(yè)的資源使用信息包括作業(yè)進(jìn)入系統(tǒng)時(shí)間、作業(yè)開(kāi)始執(zhí)行時(shí)間、作業(yè)已經(jīng)執(zhí)行時(shí)間、作業(yè)在作業(yè)開(kāi)始執(zhí)行時(shí)間、作業(yè)已經(jīng)執(zhí)行時(shí)間、作業(yè)在內(nèi)存中的地址、作業(yè)被分配的輸入輸出設(shè)備臺(tái)

14、號(hào)，內(nèi)存中的地址、作業(yè)被分配的輸入輸出設(shè)備臺(tái)號(hào)，這些信息由操作系統(tǒng)寫(xiě)入。這些信息由操作系統(tǒng)寫(xiě)入。 作業(yè)的控制方式分為聯(lián)機(jī)和脫機(jī)兩種，表示作業(yè)的控制方式分為聯(lián)機(jī)和脫機(jī)兩種，表示該作業(yè)是聯(lián)機(jī)操作還是脫機(jī)操作。該作業(yè)是聯(lián)機(jī)操作還是脫機(jī)操作。 作業(yè)類型分為作業(yè)類型分為CPUCPU繁忙型作業(yè)和繁忙型作業(yè)和I/OI/O繁忙型作繁忙型作業(yè)，或批處理輸入作業(yè)和終端作業(yè)。業(yè)，或批處理輸入作業(yè)和終端作業(yè)。3.1.1 3.1.1 高級(jí)調(diào)度（續(xù)）高級(jí)調(diào)度（續(xù)） 作業(yè)優(yōu)先級(jí)反映作業(yè)運(yùn)行的緊急程度，可由作業(yè)優(yōu)先級(jí)反映作業(yè)運(yùn)行的緊急程度，可由用戶指定，也可由系統(tǒng)根據(jù)作業(yè)類型、作業(yè)對(duì)資用戶指定，也可由系統(tǒng)根據(jù)作業(yè)類型、作業(yè)對(duì)

15、資源的需求、作業(yè)要求的運(yùn)行時(shí)間和系統(tǒng)當(dāng)前狀況源的需求、作業(yè)要求的運(yùn)行時(shí)間和系統(tǒng)當(dāng)前狀況動(dòng)態(tài)指定。動(dòng)態(tài)指定。 作業(yè)狀態(tài)指作業(yè)當(dāng)前所處的狀態(tài)，可分為提作業(yè)狀態(tài)指作業(yè)當(dāng)前所處的狀態(tài)，可分為提交狀態(tài)、后備狀態(tài)、運(yùn)行狀態(tài)及完成狀態(tài)。交狀態(tài)、后備狀態(tài)、運(yùn)行狀態(tài)及完成狀態(tài)。 當(dāng)作業(yè)運(yùn)行結(jié)束時(shí)，首先釋放作業(yè)所占用的當(dāng)作業(yè)運(yùn)行結(jié)束時(shí)，首先釋放作業(yè)所占用的全部資源，再由作業(yè)調(diào)度程序調(diào)用存儲(chǔ)器管理程全部資源，再由作業(yè)調(diào)度程序調(diào)用存儲(chǔ)器管理程序收回該作業(yè)的作業(yè)控制塊空間，從而撤銷作業(yè)。序收回該作業(yè)的作業(yè)控制塊空間，從而撤銷作業(yè)。l 確定作業(yè)的調(diào)度算法。操作系統(tǒng)調(diào)度程序在調(diào)度確定作業(yè)的調(diào)度算法。操作系統(tǒng)調(diào)度程序在調(diào)度作

16、業(yè)前需要確定作業(yè)的調(diào)度算法，然后再按照確作業(yè)前需要確定作業(yè)的調(diào)度算法，然后再按照確定的作業(yè)調(diào)度算法從磁盤(pán)的作業(yè)后備隊(duì)列中選擇定的作業(yè)調(diào)度算法從磁盤(pán)的作業(yè)后備隊(duì)列中選擇作業(yè)進(jìn)入內(nèi)存。作業(yè)進(jìn)入內(nèi)存。3.1.1 3.1.1 高級(jí)調(diào)度（續(xù)）高級(jí)調(diào)度（續(xù)）l 為作業(yè)分配資源。為作業(yè)分配資源。 作業(yè)運(yùn)行需要各種資源，包括硬件資源和軟件作業(yè)運(yùn)行需要各種資源，包括硬件資源和軟件資源。硬件資源有內(nèi)存、處理器和各種輸入輸出設(shè)資源。硬件資源有內(nèi)存、處理器和各種輸入輸出設(shè)備。軟件資源有各種共享變量等。作業(yè)的資源分配備。軟件資源有各種共享變量等。作業(yè)的資源分配策略主要考慮的是作業(yè)所包含的進(jìn)程所需要的資源，策略主要考慮的

17、是作業(yè)所包含的進(jìn)程所需要的資源，在一般情況下，資源按照進(jìn)程需求進(jìn)行分配。資源在一般情況下，資源按照進(jìn)程需求進(jìn)行分配。資源分配中需要避免由進(jìn)程之間的資源競(jìng)爭(zhēng)而造成的死分配中需要避免由進(jìn)程之間的資源競(jìng)爭(zhēng)而造成的死鎖等現(xiàn)象。鎖等現(xiàn)象。l 回收作業(yè)資源?；厥兆鳂I(yè)資源。 作業(yè)完成后，作業(yè)調(diào)度程序除了要輸出相關(guān)的作業(yè)完成后，作業(yè)調(diào)度程序除了要輸出相關(guān)的作業(yè)信息之外，還要回收作業(yè)所占用的全部資源，作業(yè)信息之外，還要回收作業(yè)所占用的全部資源，撤銷與作業(yè)相關(guān)的進(jìn)程和作業(yè)控制塊。撤銷與作業(yè)相關(guān)的進(jìn)程和作業(yè)控制塊。3.1.1 3.1.1 高級(jí)調(diào)度（續(xù)）高級(jí)調(diào)度（續(xù)） 在作業(yè)調(diào)度工作中，大多數(shù)工作由作業(yè)的調(diào)度在作業(yè)調(diào)

18、度工作中，大多數(shù)工作由作業(yè)的調(diào)度程序完成。但是，內(nèi)存和輸入輸出設(shè)備的分配和釋程序完成。但是，內(nèi)存和輸入輸出設(shè)備的分配和釋放不是由作業(yè)調(diào)度程序完成，而是由存儲(chǔ)器管理和放不是由作業(yè)調(diào)度程序完成，而是由存儲(chǔ)器管理和設(shè)備管理程序完成的。設(shè)備管理程序完成的。 作業(yè)調(diào)度程序只是將作業(yè)對(duì)內(nèi)存的要求和對(duì)設(shè)作業(yè)調(diào)度程序只是將作業(yè)對(duì)內(nèi)存的要求和對(duì)設(shè)備的要求轉(zhuǎn)交給相應(yīng)的內(nèi)存管理程序和設(shè)備管理程備的要求轉(zhuǎn)交給相應(yīng)的內(nèi)存管理程序和設(shè)備管理程序，由內(nèi)存管理程序和設(shè)備管理程序完成內(nèi)存和設(shè)序，由內(nèi)存管理程序和設(shè)備管理程序完成內(nèi)存和設(shè)備的分配與回收。備的分配與回收。3.1.1 3.1.1 高級(jí)調(diào)度（續(xù)）高級(jí)調(diào)度（續(xù)）3 3作業(yè)

19、的狀態(tài)作業(yè)的狀態(tài) 為了更好地描述作業(yè)，可以將作業(yè)分為不同的狀為了更好地描述作業(yè)，可以將作業(yè)分為不同的狀態(tài)。作業(yè)的狀態(tài)包括：提交狀態(tài)、后備狀態(tài)、執(zhí)行狀態(tài)。作業(yè)的狀態(tài)包括：提交狀態(tài)、后備狀態(tài)、執(zhí)行狀態(tài)和完成狀態(tài)。態(tài)和完成狀態(tài)。l 提交狀態(tài)提交狀態(tài): :用戶將作業(yè)提交給操作系統(tǒng)，等待輸入用戶將作業(yè)提交給操作系統(tǒng)，等待輸入程序和數(shù)據(jù)到磁盤(pán)。程序和數(shù)據(jù)到磁盤(pán)。l 后備狀態(tài)后備狀態(tài): :系統(tǒng)接收輸入的用戶作業(yè)，并將其放入系統(tǒng)接收輸入的用戶作業(yè)，并將其放入計(jì)算機(jī)磁盤(pán)。作業(yè)在磁盤(pán)上以后備隊(duì)列形式進(jìn)行組織，計(jì)算機(jī)磁盤(pán)。作業(yè)在磁盤(pán)上以后備隊(duì)列形式進(jìn)行組織，等待作業(yè)調(diào)度程序?qū)⒆鳂I(yè)調(diào)度到內(nèi)存。等待作業(yè)調(diào)度程序?qū)⒆鳂I(yè)調(diào)

20、度到內(nèi)存。l 執(zhí)行狀態(tài)執(zhí)行狀態(tài): :作業(yè)被調(diào)度到內(nèi)存，為作業(yè)分配資源并作業(yè)被調(diào)度到內(nèi)存，為作業(yè)分配資源并為其創(chuàng)建與之對(duì)應(yīng)的進(jìn)程，進(jìn)程獲得為其創(chuàng)建與之對(duì)應(yīng)的進(jìn)程，進(jìn)程獲得CPUCPU，開(kāi)始運(yùn)行。，開(kāi)始運(yùn)行。3.1.1 3.1.1 高級(jí)調(diào)度（續(xù)）高級(jí)調(diào)度（續(xù)）l 完成狀態(tài)完成狀態(tài): :從作業(yè)的第一個(gè)進(jìn)程完成開(kāi)始，直到作從作業(yè)的第一個(gè)進(jìn)程完成開(kāi)始，直到作業(yè)所有的進(jìn)程完成，釋放作業(yè)所占用的資源，退出系業(yè)所有的進(jìn)程完成，釋放作業(yè)所占用的資源，退出系統(tǒng)的整個(gè)進(jìn)程。統(tǒng)的整個(gè)進(jìn)程。 作業(yè)狀態(tài)及其轉(zhuǎn)換如圖作業(yè)狀態(tài)及其轉(zhuǎn)換如圖3.23.2所示。所示。執(zhí)行狀態(tài)執(zhí)行狀態(tài)就緒就緒運(yùn)行運(yùn)行阻塞阻塞后備狀態(tài)后備狀態(tài)提交狀態(tài)

21、提交狀態(tài)完成狀態(tài)完成狀態(tài)圖圖3.2 3.2 作業(yè)狀態(tài)及其轉(zhuǎn)換作業(yè)狀態(tài)及其轉(zhuǎn)換3.1.1 3.1.1 高級(jí)調(diào)度（續(xù)）高級(jí)調(diào)度（續(xù)）l 作業(yè)狀態(tài)的劃分比進(jìn)程狀態(tài)的劃分更粗，進(jìn)程是作業(yè)狀態(tài)的劃分比進(jìn)程狀態(tài)的劃分更粗，進(jìn)程是作業(yè)全部狀態(tài)中的一個(gè)階段體現(xiàn)。作業(yè)全部狀態(tài)中的一個(gè)階段體現(xiàn)。l 作業(yè)調(diào)度將作業(yè)從后備狀態(tài)轉(zhuǎn)換到內(nèi)存執(zhí)行狀態(tài)。作業(yè)調(diào)度將作業(yè)從后備狀態(tài)轉(zhuǎn)換到內(nèi)存執(zhí)行狀態(tài)。作業(yè)執(zhí)行狀態(tài)包含作業(yè)所對(duì)應(yīng)進(jìn)程的就緒、運(yùn)行作業(yè)執(zhí)行狀態(tài)包含作業(yè)所對(duì)應(yīng)進(jìn)程的就緒、運(yùn)行和阻塞狀態(tài)。和阻塞狀態(tài)。l 在分時(shí)操作系統(tǒng)和實(shí)時(shí)操作系統(tǒng)中，終端用戶的在分時(shí)操作系統(tǒng)和實(shí)時(shí)操作系統(tǒng)中，終端用戶的作業(yè)直接送入到內(nèi)存，不需要作業(yè)調(diào)度。

22、操作系作業(yè)直接送入到內(nèi)存，不需要作業(yè)調(diào)度。操作系統(tǒng)需要完成的功能是決定是否能夠?yàn)樽鳂I(yè)創(chuàng)建進(jìn)統(tǒng)需要完成的功能是決定是否能夠?yàn)樽鳂I(yè)創(chuàng)建進(jìn)程。程。l 分時(shí)操作系統(tǒng)和實(shí)時(shí)操作系統(tǒng)也支持批處理作業(yè)，分時(shí)操作系統(tǒng)和實(shí)時(shí)操作系統(tǒng)也支持批處理作業(yè)，在批處理作業(yè)存在時(shí)，也能夠完成作業(yè)調(diào)度。在批處理作業(yè)存在時(shí)，也能夠完成作業(yè)調(diào)度。3.1.2 中級(jí)調(diào)度l 中級(jí)調(diào)度又稱為中程調(diào)度，是為了提高內(nèi)存利用中級(jí)調(diào)度又稱為中程調(diào)度，是為了提高內(nèi)存利用率和平衡系統(tǒng)負(fù)載而采取的一種利用外存補(bǔ)充內(nèi)率和平衡系統(tǒng)負(fù)載而采取的一種利用外存補(bǔ)充內(nèi)存的措施。存的措施。l 在多進(jìn)程環(huán)境下，內(nèi)存中的多個(gè)進(jìn)程，其中有些在多進(jìn)程環(huán)境下，內(nèi)存中的多個(gè)進(jìn)

23、程，其中有些進(jìn)程可能需要掛起，這些進(jìn)程暫時(shí)不參與對(duì)處理進(jìn)程可能需要掛起，這些進(jìn)程暫時(shí)不參與對(duì)處理器的競(jìng)爭(zhēng)。為了充分利用內(nèi)存資源，系統(tǒng)會(huì)采用器的競(jìng)爭(zhēng)。為了充分利用內(nèi)存資源，系統(tǒng)會(huì)采用進(jìn)程對(duì)換的方法將進(jìn)程換出到外存，將這些進(jìn)程進(jìn)程對(duì)換的方法將進(jìn)程換出到外存，將這些進(jìn)程占用的內(nèi)存空間釋放，讓內(nèi)存能夠接納新的進(jìn)程占用的內(nèi)存空間釋放，讓內(nèi)存能夠接納新的進(jìn)程或使得內(nèi)存中的進(jìn)程能夠更快推進(jìn)。當(dāng)被換出到或使得內(nèi)存中的進(jìn)程能夠更快推進(jìn)。當(dāng)被換出到外存中的進(jìn)程掛起時(shí)間到時(shí)，又需要將這些進(jìn)程外存中的進(jìn)程掛起時(shí)間到時(shí)，又需要將這些進(jìn)程換入到內(nèi)存。中級(jí)調(diào)度是在換出內(nèi)存的進(jìn)程中確換入到內(nèi)存。中級(jí)調(diào)度是在換出內(nèi)存的進(jìn)程中確

24、定需要進(jìn)入內(nèi)存的進(jìn)程。定需要進(jìn)入內(nèi)存的進(jìn)程。3.1.2 中級(jí)調(diào)度l 當(dāng)進(jìn)程需要換入內(nèi)存，而內(nèi)存資源不充足時(shí)，則當(dāng)進(jìn)程需要換入內(nèi)存，而內(nèi)存資源不充足時(shí)，則系統(tǒng)需要選擇內(nèi)存中的進(jìn)程換出外存，讓出內(nèi)存系統(tǒng)需要選擇內(nèi)存中的進(jìn)程換出外存，讓出內(nèi)存空間給進(jìn)入內(nèi)存的進(jìn)程?？臻g給進(jìn)入內(nèi)存的進(jìn)程。l 中級(jí)調(diào)度根據(jù)內(nèi)存中能夠接納的進(jìn)程數(shù)來(lái)平衡系中級(jí)調(diào)度根據(jù)內(nèi)存中能夠接納的進(jìn)程數(shù)來(lái)平衡系統(tǒng)負(fù)載，起到在一定時(shí)間內(nèi)平滑和調(diào)整系統(tǒng)負(fù)載統(tǒng)負(fù)載，起到在一定時(shí)間內(nèi)平滑和調(diào)整系統(tǒng)負(fù)載的作用。的作用。1 1低級(jí)調(diào)度低級(jí)調(diào)度 低級(jí)調(diào)度又稱為進(jìn)程調(diào)度、短程調(diào)度，是按照一低級(jí)調(diào)度又稱為進(jìn)程調(diào)度、短程調(diào)度，是按照一定的調(diào)度算法從內(nèi)存的就緒

25、進(jìn)程隊(duì)列中選擇進(jìn)程，定的調(diào)度算法從內(nèi)存的就緒進(jìn)程隊(duì)列中選擇進(jìn)程，為進(jìn)程分配處理器。為進(jìn)程分配處理器。l 進(jìn)程調(diào)度發(fā)生在內(nèi)存中的就緒進(jìn)程，被調(diào)度的進(jìn)進(jìn)程調(diào)度發(fā)生在內(nèi)存中的就緒進(jìn)程，被調(diào)度的進(jìn)程從內(nèi)存就緒到處理器中執(zhí)行的過(guò)程，該過(guò)程很短，程從內(nèi)存就緒到處理器中執(zhí)行的過(guò)程，該過(guò)程很短，被稱為短程調(diào)度。被稱為短程調(diào)度。l中級(jí)調(diào)度位于高級(jí)調(diào)度與低級(jí)調(diào)度之間，被稱為中中級(jí)調(diào)度位于高級(jí)調(diào)度與低級(jí)調(diào)度之間，被稱為中程調(diào)度。中級(jí)調(diào)度主要用于內(nèi)存管理，特別是虛擬程調(diào)度。中級(jí)調(diào)度主要用于內(nèi)存管理，特別是虛擬存儲(chǔ)器管理。存儲(chǔ)器管理。 3.1.3 3.1.3 低級(jí)調(diào)度低級(jí)調(diào)度l 作業(yè)調(diào)度發(fā)生進(jìn)程位于外存與進(jìn)入計(jì)算機(jī)內(nèi)存

26、之作業(yè)調(diào)度發(fā)生進(jìn)程位于外存與進(jìn)入計(jì)算機(jī)內(nèi)存之間，經(jīng)過(guò)的過(guò)程最長(zhǎng)，因此，作業(yè)調(diào)度被稱為長(zhǎng)程間，經(jīng)過(guò)的過(guò)程最長(zhǎng)，因此，作業(yè)調(diào)度被稱為長(zhǎng)程調(diào)度。調(diào)度。l 進(jìn)程調(diào)度與作業(yè)調(diào)度和中級(jí)調(diào)度比較，進(jìn)程調(diào)度進(jìn)程調(diào)度與作業(yè)調(diào)度和中級(jí)調(diào)度比較，進(jìn)程調(diào)度發(fā)生的頻率最高，作業(yè)調(diào)度發(fā)生的頻率最低。發(fā)生的頻率最高，作業(yè)調(diào)度發(fā)生的頻率最低。3.1.3 3.1.3 低級(jí)調(diào)度低級(jí)調(diào)度處理器調(diào)度的三級(jí)模型如圖處理器調(diào)度的三級(jí)模型如圖3.33.3所示。所示。3.1.3 3.1.3 低級(jí)調(diào)度低級(jí)調(diào)度圖圖3.3 3.3 處理器三級(jí)調(diào)度模型處理器三級(jí)調(diào)度模型進(jìn)程掛起就緒隊(duì)列進(jìn)程掛起就緒隊(duì)列進(jìn)程阻塞隊(duì)列進(jìn)程阻塞隊(duì)列進(jìn)程掛起阻塞隊(duì)列進(jìn)程掛起

27、阻塞隊(duì)列進(jìn)程就緒隊(duì)列進(jìn)程就緒隊(duì)列完成完成中級(jí)調(diào)度中級(jí)調(diào)度低級(jí)調(diào)度低級(jí)調(diào)度處理器處理器高級(jí)調(diào)度高級(jí)調(diào)度作業(yè)后備隊(duì)列作業(yè)后備隊(duì)列交互式用戶交互式用戶提交提交用戶作業(yè)用戶作業(yè)3.1.3 3.1.3 低級(jí)調(diào)度（續(xù)）低級(jí)調(diào)度（續(xù)）2 2引起進(jìn)程調(diào)度的主要原因引起進(jìn)程調(diào)度的主要原因 （1 1）處理器執(zhí)行的進(jìn)程完成任務(wù)，處理器空閑；）處理器執(zhí)行的進(jìn)程完成任務(wù)，處理器空閑； （2 2）處理器執(zhí)行的進(jìn)程轉(zhuǎn)入阻塞狀態(tài)，此時(shí)處理）處理器執(zhí)行的進(jìn)程轉(zhuǎn)入阻塞狀態(tài)，此時(shí)處理器空閑；器空閑； （3 3）處理器執(zhí)行的進(jìn)程被其它進(jìn)程搶占；）處理器執(zhí)行的進(jìn)程被其它進(jìn)程搶占； （4 4）處理器執(zhí)行的進(jìn)程被掛起。）處理器執(zhí)行的進(jìn)程被

28、掛起。3.1.3 3.1.3 低級(jí)調(diào)度（續(xù)）低級(jí)調(diào)度（續(xù)）3 3進(jìn)程調(diào)度中的基本機(jī)制進(jìn)程調(diào)度中的基本機(jī)制（1 1）排隊(duì)器。為使進(jìn)程調(diào)度時(shí)能夠快速有效地找到）排隊(duì)器。為使進(jìn)程調(diào)度時(shí)能夠快速有效地找到就緒隊(duì)列中的每個(gè)進(jìn)程，首先應(yīng)該按照一定的方式就緒隊(duì)列中的每個(gè)進(jìn)程，首先應(yīng)該按照一定的方式將進(jìn)程就緒隊(duì)列排成一個(gè)或多個(gè)隊(duì)列。將進(jìn)程就緒隊(duì)列排成一個(gè)或多個(gè)隊(duì)列。（2 2）分派程序。分派程序?qū)⒏鶕?jù)進(jìn)程調(diào)度策略將所）分派程序。分派程序?qū)⒏鶕?jù)進(jìn)程調(diào)度策略將所選中的進(jìn)程從就緒隊(duì)列中移出，然后進(jìn)行進(jìn)程上下選中的進(jìn)程從就緒隊(duì)列中移出，然后進(jìn)行進(jìn)程上下文的切換，并將處理器分配給進(jìn)程。文的切換，并將處理器分配給進(jìn)程。（3

29、 3）上下文切換機(jī)制。上下文切換機(jī)制是指在操作）上下文切換機(jī)制。上下文切換機(jī)制是指在操作系統(tǒng)分派程序的執(zhí)行下完成處理器的切換過(guò)程，實(shí)系統(tǒng)分派程序的執(zhí)行下完成處理器的切換過(guò)程，實(shí)現(xiàn)進(jìn)程上下文切換現(xiàn)進(jìn)程上下文切換3.1.3 3.1.3 低級(jí)調(diào)度（續(xù)）低級(jí)調(diào)度（續(xù)）4 4進(jìn)程切換的實(shí)現(xiàn)進(jìn)程切換的實(shí)現(xiàn) 進(jìn)程切換需要完成進(jìn)程上下文切換，進(jìn)程狀態(tài)、進(jìn)程等進(jìn)程切換需要完成進(jìn)程上下文切換，進(jìn)程狀態(tài)、進(jìn)程等待時(shí)間等信息的改變。新、老進(jìn)程切換如圖待時(shí)間等信息的改變。新、老進(jìn)程切換如圖3.43.4所示。所示。老進(jìn)程老進(jìn)程新進(jìn)程新進(jìn)程CPUCPU圖圖3.4 3.4 進(jìn)程調(diào)度中的進(jìn)程切換進(jìn)程調(diào)度中的進(jìn)程切換進(jìn)程切換過(guò)程

30、描述？進(jìn)程切換過(guò)程描述？3.1.3 3.1.3 低級(jí)調(diào)度（續(xù)）低級(jí)調(diào)度（續(xù)）進(jìn)程切換需要完成以下工作：進(jìn)程切換需要完成以下工作：l保存并恢復(fù)處理器信息。保存并恢復(fù)處理器信息。 處理器中的寄存器保存了當(dāng)前正在執(zhí)行進(jìn)程的相處理器中的寄存器保存了當(dāng)前正在執(zhí)行進(jìn)程的相關(guān)數(shù)據(jù)和狀態(tài)，在進(jìn)程被切換時(shí)，必須將進(jìn)程的關(guān)數(shù)據(jù)和狀態(tài)，在進(jìn)程被切換時(shí)，必須將進(jìn)程的這些信息保存到進(jìn)程控制塊中，以便進(jìn)程被處理這些信息保存到進(jìn)程控制塊中，以便進(jìn)程被處理器再次執(zhí)行時(shí)，能夠?qū)⑦M(jìn)程的斷點(diǎn)信息從進(jìn)程控器再次執(zhí)行時(shí)，能夠?qū)⑦M(jìn)程的斷點(diǎn)信息從進(jìn)程控制塊拷貝回處理器寄存器中，保證處理器能夠從制塊拷貝回處理器寄存器中，保證處理器能夠從進(jìn)程

31、的上次斷點(diǎn)開(kāi)始繼續(xù)向前推進(jìn)。進(jìn)程的上次斷點(diǎn)開(kāi)始繼續(xù)向前推進(jìn)。 處理器中寄存器信息寫(xiě)到老進(jìn)程的進(jìn)程控制塊中，處理器中寄存器信息寫(xiě)到老進(jìn)程的進(jìn)程控制塊中，新進(jìn)程的進(jìn)程控制塊信息被拷貝到處理器的寄存新進(jìn)程的進(jìn)程控制塊信息被拷貝到處理器的寄存器中。器中。3.1.3 3.1.3 低級(jí)調(diào)度（續(xù)）低級(jí)調(diào)度（續(xù)）l 更新進(jìn)程控制塊中的進(jìn)程狀態(tài)、進(jìn)程達(dá)到時(shí)間、進(jìn)更新進(jìn)程控制塊中的進(jìn)程狀態(tài)、進(jìn)程達(dá)到時(shí)間、進(jìn)程等待時(shí)間、進(jìn)程優(yōu)先級(jí)變化等信息，并將進(jìn)程控程等待時(shí)間、進(jìn)程優(yōu)先級(jí)變化等信息，并將進(jìn)程控制塊移到相應(yīng)的進(jìn)程隊(duì)列。制塊移到相應(yīng)的進(jìn)程隊(duì)列。 被切換的進(jìn)程狀態(tài)從執(zhí)行改為就緒或阻塞，其進(jìn)程控被切換的進(jìn)程狀態(tài)從執(zhí)行改為

32、就緒或阻塞，其進(jìn)程控制塊也被插入就緒隊(duì)列或阻塞隊(duì)列。同樣，被分配制塊也被插入就緒隊(duì)列或阻塞隊(duì)列。同樣，被分配處理器的進(jìn)程，其狀態(tài)從就緒改為執(zhí)行，進(jìn)程控制處理器的進(jìn)程，其狀態(tài)從就緒改為執(zhí)行，進(jìn)程控制塊從就緒隊(duì)列中移出。塊從就緒隊(duì)列中移出。l 更新存儲(chǔ)器管理數(shù)據(jù)結(jié)構(gòu)，維護(hù)進(jìn)程的代碼段和數(shù)更新存儲(chǔ)器管理數(shù)據(jù)結(jié)構(gòu)，維護(hù)進(jìn)程的代碼段和數(shù)據(jù)段。據(jù)段。3.1.3 3.1.3 低級(jí)調(diào)度（續(xù)）低級(jí)調(diào)度（續(xù)）5 5進(jìn)程調(diào)度中的非搶占（進(jìn)程調(diào)度中的非搶占（nonpreemptivenonpreemptive）調(diào)度和）調(diào)度和搶占（搶占（preemptivepreemptive）調(diào)度）調(diào)度 l 非搶占式調(diào)度是一種通常的

33、調(diào)度方式，在非搶占非搶占式調(diào)度是一種通常的調(diào)度方式，在非搶占調(diào)度中，處理器分配給進(jìn)程后，一直到進(jìn)程結(jié)束調(diào)度中，處理器分配給進(jìn)程后，一直到進(jìn)程結(jié)束或進(jìn)程阻塞，進(jìn)程才自動(dòng)放棄處理器。或進(jìn)程阻塞，進(jìn)程才自動(dòng)放棄處理器。l 非搶占調(diào)度存在什么問(wèn)題？非搶占調(diào)度存在什么問(wèn)題？l 若執(zhí)行進(jìn)程正好在執(zhí)行一個(gè)沒(méi)有資源的無(wú)限循環(huán)，若執(zhí)行進(jìn)程正好在執(zhí)行一個(gè)沒(méi)有資源的無(wú)限循環(huán)，則執(zhí)行進(jìn)程不會(huì)放棄處理器，所有的就緒進(jìn)程會(huì)則執(zhí)行進(jìn)程不會(huì)放棄處理器，所有的就緒進(jìn)程會(huì)永久等待，系統(tǒng)進(jìn)入了一種僵持的狀態(tài)。永久等待，系統(tǒng)進(jìn)入了一種僵持的狀態(tài)。l 解決方法解決方法?l 如果此時(shí)系統(tǒng)能夠自身定期強(qiáng)制執(zhí)行進(jìn)程中斷，如果此時(shí)系統(tǒng)能夠自身

34、定期強(qiáng)制執(zhí)行進(jìn)程中斷，則可以避免這種僵持狀態(tài)。則可以避免這種僵持狀態(tài)。3.1.3 3.1.3 低級(jí)調(diào)度（續(xù)）低級(jí)調(diào)度（續(xù)）l 強(qiáng)制執(zhí)行進(jìn)程中斷的調(diào)度方式為搶占調(diào)度方式，強(qiáng)制執(zhí)行進(jìn)程中斷的調(diào)度方式為搶占調(diào)度方式，又稱為剝奪調(diào)度方式，是指一個(gè)進(jìn)程正在處理器又稱為剝奪調(diào)度方式，是指一個(gè)進(jìn)程正在處理器中運(yùn)行時(shí)，操作系統(tǒng)可以根據(jù)規(guī)定的搶占原則，中運(yùn)行時(shí)，操作系統(tǒng)可以根據(jù)規(guī)定的搶占原則，將已經(jīng)分配給進(jìn)程的處理器從進(jìn)程剝奪，并分配將已經(jīng)分配給進(jìn)程的處理器從進(jìn)程剝奪，并分配給其他的進(jìn)程。給其他的進(jìn)程。l 在系統(tǒng)允許搶占調(diào)度，并滿足搶占條件的情況下，在系統(tǒng)允許搶占調(diào)度，并滿足搶占條件的情況下，系統(tǒng)才可以采用搶占

35、調(diào)度方式。滿足搶占條件的系統(tǒng)才可以采用搶占調(diào)度方式。滿足搶占條件的進(jìn)程能夠搶占當(dāng)前正在執(zhí)行進(jìn)程的處理器。被搶進(jìn)程能夠搶占當(dāng)前正在執(zhí)行進(jìn)程的處理器。被搶占的進(jìn)程狀態(tài)從執(zhí)行狀態(tài)變?yōu)榫途w狀態(tài)，其進(jìn)程占的進(jìn)程狀態(tài)從執(zhí)行狀態(tài)變?yōu)榫途w狀態(tài)，其進(jìn)程控制塊進(jìn)入到進(jìn)程就緒隊(duì)列。控制塊進(jìn)入到進(jìn)程就緒隊(duì)列。3.1.3 3.1.3 低級(jí)調(diào)度（續(xù)）低級(jí)調(diào)度（續(xù)）l 具有搶占的進(jìn)程狀態(tài)如圖具有搶占的進(jìn)程狀態(tài)如圖3.53.5所示。所示。圖圖3.5 3.5 進(jìn)程的搶占與非搶占調(diào)度進(jìn)程的搶占與非搶占調(diào)度阻塞態(tài)阻塞態(tài)就緒態(tài)就緒態(tài)運(yùn)行態(tài)運(yùn)行態(tài)終止態(tài)終止態(tài)搶占搶占非搶占非搶占進(jìn)程調(diào)度進(jìn)程調(diào)度非搶占非搶占3.1.3 3.1.3 低級(jí)調(diào)

36、度（續(xù)）低級(jí)調(diào)度（續(xù)）搶占條件也稱為搶占原則，可歸納為如下：搶占條件也稱為搶占原則，可歸納為如下：l 時(shí)間片時(shí)間片 在分時(shí)系統(tǒng)中，當(dāng)進(jìn)程運(yùn)行的時(shí)間片到時(shí)，進(jìn)程在分時(shí)系統(tǒng)中，當(dāng)進(jìn)程運(yùn)行的時(shí)間片到時(shí)，進(jìn)程會(huì)被搶占，處理器被分配給其他的就緒進(jìn)程。分時(shí)操會(huì)被搶占，處理器被分配給其他的就緒進(jìn)程。分時(shí)操作系統(tǒng)采用了基于時(shí)間片的搶占調(diào)度方法，如作系統(tǒng)采用了基于時(shí)間片的搶占調(diào)度方法，如UNIXUNIX操操作系統(tǒng)和作系統(tǒng)和LinuxLinux操作系統(tǒng)。操作系統(tǒng)。l 優(yōu)先級(jí)優(yōu)先級(jí) 當(dāng)就緒隊(duì)列上有優(yōu)先級(jí)比當(dāng)前正在處理器運(yùn)行的當(dāng)就緒隊(duì)列上有優(yōu)先級(jí)比當(dāng)前正在處理器運(yùn)行的進(jìn)程的優(yōu)先級(jí)高的進(jìn)程時(shí)，系統(tǒng)將處理器從當(dāng)前進(jìn)程進(jìn)程

37、的優(yōu)先級(jí)高的進(jìn)程時(shí)，系統(tǒng)將處理器從當(dāng)前進(jìn)程剝奪，優(yōu)先級(jí)高的進(jìn)程得到處理器。基于優(yōu)先級(jí)的進(jìn)剝奪，優(yōu)先級(jí)高的進(jìn)程得到處理器?；趦?yōu)先級(jí)的進(jìn)程搶占調(diào)度被很多操作系統(tǒng)所采用，特別是實(shí)時(shí)操作程搶占調(diào)度被很多操作系統(tǒng)所采用，特別是實(shí)時(shí)操作系統(tǒng)。系統(tǒng)。 在在UNIXUNIX操作系統(tǒng)中，當(dāng)用戶態(tài)進(jìn)程完成系統(tǒng)調(diào)用操作系統(tǒng)中，當(dāng)用戶態(tài)進(jìn)程完成系統(tǒng)調(diào)用后從核心態(tài)返回用戶態(tài)繼續(xù)運(yùn)行時(shí)，處理器可能被處后從核心態(tài)返回用戶態(tài)繼續(xù)運(yùn)行時(shí)，處理器可能被處于核心態(tài)執(zhí)行的其他進(jìn)程搶占。于核心態(tài)執(zhí)行的其他進(jìn)程搶占。3.1.3 3.1.3 低級(jí)調(diào)度（續(xù)）低級(jí)調(diào)度（續(xù)）l 短進(jìn)程短進(jìn)程 當(dāng)就緒隊(duì)列中有進(jìn)程的執(zhí)行時(shí)間比當(dāng)前正在當(dāng)就緒隊(duì)列中

38、有進(jìn)程的執(zhí)行時(shí)間比當(dāng)前正在處理器運(yùn)行的進(jìn)程需要的執(zhí)行時(shí)間更短時(shí)，當(dāng)前處理器運(yùn)行的進(jìn)程需要的執(zhí)行時(shí)間更短時(shí)，當(dāng)前進(jìn)程被搶占，系統(tǒng)將處理器分配給更短的進(jìn)程。進(jìn)程被搶占，系統(tǒng)將處理器分配給更短的進(jìn)程。 搶占是一種靈活和有效的處理進(jìn)程調(diào)度方法，搶占是一種靈活和有效的處理進(jìn)程調(diào)度方法，避免了進(jìn)程永遠(yuǎn)不放棄處理器的現(xiàn)象，也為緊急避免了進(jìn)程永遠(yuǎn)不放棄處理器的現(xiàn)象，也為緊急情況下的進(jìn)程運(yùn)行創(chuàng)造了機(jī)會(huì)。情況下的進(jìn)程運(yùn)行創(chuàng)造了機(jī)會(huì)。3.1.3 3.1.3 低級(jí)調(diào)度（續(xù)）低級(jí)調(diào)度（續(xù)）搶占帶來(lái)的問(wèn)題：搶占帶來(lái)的問(wèn)題：l 增加系統(tǒng)開(kāi)銷增加系統(tǒng)開(kāi)銷l 進(jìn)程間共享數(shù)據(jù)不一致問(wèn)題進(jìn)程間共享數(shù)據(jù)不一致問(wèn)題 在進(jìn)程之間存在數(shù)據(jù)

39、共享時(shí)，如果一個(gè)進(jìn)程在進(jìn)程之間存在數(shù)據(jù)共享時(shí)，如果一個(gè)進(jìn)程的數(shù)據(jù)更新尚未結(jié)束而被搶占，得到處理器的進(jìn)的數(shù)據(jù)更新尚未結(jié)束而被搶占，得到處理器的進(jìn)程恰好又要讀取這部分共享數(shù)據(jù)，此時(shí)讀取的數(shù)程恰好又要讀取這部分共享數(shù)據(jù)，此時(shí)讀取的數(shù)據(jù)可能存在不一致的問(wèn)題。這樣，操作系統(tǒng)必須據(jù)可能存在不一致的問(wèn)題。這樣，操作系統(tǒng)必須采取一定的措施保證數(shù)據(jù)的一致性。采取一定的措施保證數(shù)據(jù)的一致性。l 影響操作系統(tǒng)內(nèi)核程序設(shè)計(jì)問(wèn)題影響操作系統(tǒng)內(nèi)核程序設(shè)計(jì)問(wèn)題 如果搶占發(fā)生在操作系統(tǒng)內(nèi)核程序執(zhí)行期如果搶占發(fā)生在操作系統(tǒng)內(nèi)核程序執(zhí)行期間，如系統(tǒng)調(diào)用期間，核心程序可能正在改變核間，如系統(tǒng)調(diào)用期間，核心程序可能正在改變核心中的重

40、要數(shù)據(jù)時(shí)被搶占，從而造成操作系統(tǒng)核心中的重要數(shù)據(jù)時(shí)被搶占，從而造成操作系統(tǒng)核心出現(xiàn)問(wèn)題，影響系統(tǒng)的穩(wěn)定性。心出現(xiàn)問(wèn)題，影響系統(tǒng)的穩(wěn)定性。3.1.3 3.1.3 低級(jí)調(diào)度（續(xù)）低級(jí)調(diào)度（續(xù)） 在操作系統(tǒng)設(shè)計(jì)時(shí)應(yīng)考慮避免核心調(diào)用時(shí)被搶在操作系統(tǒng)設(shè)計(jì)時(shí)應(yīng)考慮避免核心調(diào)用時(shí)被搶占的情況。如占的情況。如UNIXUNIX操作系統(tǒng)在設(shè)計(jì)時(shí)規(guī)定系統(tǒng)調(diào)用操作系統(tǒng)在設(shè)計(jì)時(shí)規(guī)定系統(tǒng)調(diào)用期間不能搶占。期間不能搶占。 內(nèi)核程序執(zhí)行時(shí)不能被搶占又影響系統(tǒng)實(shí)時(shí)性，內(nèi)核程序執(zhí)行時(shí)不能被搶占又影響系統(tǒng)實(shí)時(shí)性，特別是在此期間系統(tǒng)不能接收中斷，造成輸入信息特別是在此期間系統(tǒng)不能接收中斷，造成輸入信息丟失，輸出信息被重寫(xiě)。丟失，輸出

41、信息被重寫(xiě)。 UNIX UNIX、LinuxLinux、微軟公司的、微軟公司的WindowsWindows操作系統(tǒng)、蘋(píng)果操作系統(tǒng)、蘋(píng)果公司的公司的MacOSMacOS都采用了搶占調(diào)度方式。都采用了搶占調(diào)度方式。3.2 評(píng)價(jià)調(diào)度算法的準(zhǔn)則l 處理器調(diào)度算法也稱為調(diào)度策略，用于控制對(duì)處處理器調(diào)度算法也稱為調(diào)度策略，用于控制對(duì)處理器的分配，是處理器調(diào)度中非常重要的環(huán)節(jié)。理器的分配，是處理器調(diào)度中非常重要的環(huán)節(jié)。l 不同的調(diào)度策略，對(duì)系統(tǒng)性能的影響不同。不同的調(diào)度策略，對(duì)系統(tǒng)性能的影響不同。l 適合操作系統(tǒng)的調(diào)度算法，能夠提高系統(tǒng)的性能。適合操作系統(tǒng)的調(diào)度算法，能夠提高系統(tǒng)的性能。l 評(píng)價(jià)調(diào)度算法從系

42、統(tǒng)性能、用戶滿意兩方面進(jìn)行評(píng)價(jià)調(diào)度算法從系統(tǒng)性能、用戶滿意兩方面進(jìn)行考慮，充分體現(xiàn)對(duì)用戶的公平性和系統(tǒng)的高效性，考慮，充分體現(xiàn)對(duì)用戶的公平性和系統(tǒng)的高效性，既保證每個(gè)用戶有合理的處理器時(shí)間，又保證系既保證每個(gè)用戶有合理的處理器時(shí)間，又保證系統(tǒng)的處理器利用率高。統(tǒng)的處理器利用率高。3.2 3.2 評(píng)價(jià)調(diào)度算法的準(zhǔn)則（續(xù)）評(píng)價(jià)調(diào)度算法的準(zhǔn)則（續(xù)）評(píng)價(jià)調(diào)度算法的準(zhǔn)則如下：評(píng)價(jià)調(diào)度算法的準(zhǔn)則如下：l 處理器利用率（處理器利用率（CPU utilizationCPU utilization） 處理器利用率為處理器利用率為CPUCPU有效工作時(shí)間與有效工作時(shí)間與CPUCPU總的運(yùn)行時(shí)間總的運(yùn)行時(shí)間之比，即

43、：之比，即： CPU CPU利用率利用率 = = CPUCPU有效工作時(shí)間有效工作時(shí)間/CPU/CPU總的運(yùn)行時(shí)間總的運(yùn)行時(shí)間 CPU CPU總的運(yùn)行時(shí)間總的運(yùn)行時(shí)間 = = CPUCPU的有效工作時(shí)間的有效工作時(shí)間 + + CPUCPU的空閑時(shí)的空閑時(shí)間間思考：理想情況下思考：理想情況下CPUCPU的利用率是多少？的利用率是多少？100%100% 實(shí)際應(yīng)用中，總會(huì)存在進(jìn)程切換等工作，而進(jìn)程切實(shí)際應(yīng)用中，總會(huì)存在進(jìn)程切換等工作，而進(jìn)程切換需要時(shí)間。對(duì)于輕負(fù)載系統(tǒng)，換需要時(shí)間。對(duì)于輕負(fù)載系統(tǒng)，CPUCPU的利用率大約為的利用率大約為40%40%；對(duì)于重負(fù)載系統(tǒng)，；對(duì)于重負(fù)載系統(tǒng)，CPUCPU的利

44、用率最高可達(dá)的利用率最高可達(dá)90%90%。3.2 3.2 評(píng)價(jià)調(diào)度算法的準(zhǔn)則（續(xù)）評(píng)價(jià)調(diào)度算法的準(zhǔn)則（續(xù)）l 響應(yīng)時(shí)間（響應(yīng)時(shí)間（response timeresponse time） 響應(yīng)時(shí)間是交互環(huán)境下用戶從鍵盤(pán)提交第響應(yīng)時(shí)間是交互環(huán)境下用戶從鍵盤(pán)提交第1 1個(gè)請(qǐng)求開(kāi)始，到系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間，個(gè)請(qǐng)求開(kāi)始，到系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間，或者是屏幕上顯示出結(jié)果為止的時(shí)間。或者是屏幕上顯示出結(jié)果為止的時(shí)間。 響應(yīng)時(shí)間響應(yīng)時(shí)間 = = 從終端鍵盤(pán)輸入的請(qǐng)求信息傳送到處從終端鍵盤(pán)輸入的請(qǐng)求信息傳送到處理機(jī)的時(shí)間理機(jī)的時(shí)間 + + 處理機(jī)對(duì)請(qǐng)求信息的處理時(shí)間處理機(jī)對(duì)請(qǐng)求信息的處理時(shí)間 + +

45、生生成的響應(yīng)信息回送到終端顯示器的時(shí)間成的響應(yīng)信息回送到終端顯示器的時(shí)間 對(duì)于用戶來(lái)講，希望響應(yīng)時(shí)間越短越好。對(duì)于用戶來(lái)講，希望響應(yīng)時(shí)間越短越好。3.2 3.2 評(píng)價(jià)調(diào)度算法的準(zhǔn)則（續(xù)）評(píng)價(jià)調(diào)度算法的準(zhǔn)則（續(xù)）l 周轉(zhuǎn)時(shí)間（周轉(zhuǎn)時(shí)間（turnaround timeturnaround time） 周轉(zhuǎn)時(shí)間指用戶作業(yè)提交給操作系統(tǒng)開(kāi)始到作周轉(zhuǎn)時(shí)間指用戶作業(yè)提交給操作系統(tǒng)開(kāi)始到作業(yè)完成為止的時(shí)間。業(yè)完成為止的時(shí)間。 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間T Ti i = = 作業(yè)在后備隊(duì)列中的等待調(diào)度時(shí)間作業(yè)在后備隊(duì)列中的等待調(diào)度時(shí)間+ +進(jìn)程進(jìn)程在就緒隊(duì)列上等待調(diào)度的時(shí)間在就緒隊(duì)列上等待調(diào)度的時(shí)間+ +進(jìn)程在進(jìn)程在C

46、PUCPU上的運(yùn)行上的運(yùn)行時(shí)間時(shí)間 + + 進(jìn)程等待進(jìn)程等待I/OI/O或其他事件發(fā)生的時(shí)間或其他事件發(fā)生的時(shí)間l 帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間Tf = 作業(yè)的周轉(zhuǎn)時(shí)間作業(yè)的周轉(zhuǎn)時(shí)間Ti/系統(tǒng)為作業(yè)提系統(tǒng)為作業(yè)提供的服務(wù)時(shí)間供的服務(wù)時(shí)間Tsi 每個(gè)用戶都希望自己作業(yè)的周轉(zhuǎn)時(shí)間越短越好，每個(gè)用戶都希望自己作業(yè)的周轉(zhuǎn)時(shí)間越短越好，計(jì)算機(jī)系統(tǒng)管理希望所有作業(yè)的平均周轉(zhuǎn)時(shí)間越短計(jì)算機(jī)系統(tǒng)管理希望所有作業(yè)的平均周轉(zhuǎn)時(shí)間越短越好，帶權(quán)周轉(zhuǎn)時(shí)間越短越好。越好，帶權(quán)周轉(zhuǎn)時(shí)間越短越好。3.2 3.2 評(píng)價(jià)調(diào)度算法的準(zhǔn)則（續(xù)）評(píng)價(jià)調(diào)度算法的準(zhǔn)則（續(xù)）l 系統(tǒng)吞吐量（系統(tǒng)吞吐量（through

47、putthroughput） 單位時(shí)間內(nèi)處理的進(jìn)程數(shù)目為單位時(shí)間內(nèi)處理的進(jìn)程數(shù)目為CPUCPU的工作成效。的工作成效。 單位時(shí)間內(nèi)完成的進(jìn)程數(shù)目為系統(tǒng)的吞吐量。單位時(shí)間內(nèi)完成的進(jìn)程數(shù)目為系統(tǒng)的吞吐量。 在處理大而長(zhǎng)的進(jìn)程時(shí)，吞吐量可能每小時(shí)在處理大而長(zhǎng)的進(jìn)程時(shí)，吞吐量可能每小時(shí)只有一個(gè)；在處理小而短的進(jìn)程時(shí)，吞吐量達(dá)到只有一個(gè)；在處理小而短的進(jìn)程時(shí)，吞吐量達(dá)到每秒幾十甚至上百個(gè)。每秒幾十甚至上百個(gè)。 在選擇處理器的調(diào)度算法時(shí)，用戶希望在選擇處理器的調(diào)度算法時(shí)，用戶希望CPUCPU利用率和系統(tǒng)吞吐量越大越好，響應(yīng)時(shí)間和周轉(zhuǎn)利用率和系統(tǒng)吞吐量越大越好，響應(yīng)時(shí)間和周轉(zhuǎn)時(shí)間越小越好。時(shí)間越小越好。 對(duì)

48、于實(shí)時(shí)系統(tǒng)，作業(yè)調(diào)度的關(guān)鍵在于能否滿對(duì)于實(shí)時(shí)系統(tǒng)，作業(yè)調(diào)度的關(guān)鍵在于能否滿足作業(yè)的實(shí)時(shí)要求，對(duì)周轉(zhuǎn)時(shí)間等指標(biāo)并不特別足作業(yè)的實(shí)時(shí)要求，對(duì)周轉(zhuǎn)時(shí)間等指標(biāo)并不特別著重。著重。40/136u學(xué)習(xí)目標(biāo)學(xué)習(xí)目標(biāo)：熟練掌握常見(jiàn)的調(diào)度算法，熟練掌握常見(jiàn)的調(diào)度算法， 明確各調(diào)度算法的優(yōu)缺點(diǎn)。明確各調(diào)度算法的優(yōu)缺點(diǎn)。u學(xué)習(xí)難點(diǎn)學(xué)習(xí)難點(diǎn)：理解各調(diào)度算法的思想，將理解各調(diào)度算法的思想，將 算法在實(shí)踐中靈活應(yīng)用。算法在實(shí)踐中靈活應(yīng)用。41/136u先來(lái)先服務(wù)算法先來(lái)先服務(wù)算法(First Come First Served )u最短作業(yè)優(yōu)先算法最短作業(yè)優(yōu)先算法(Shortest Job First)u最高響應(yīng)比優(yōu)先算

49、法最高響應(yīng)比優(yōu)先算法(Highest Response Ratio First)u基于時(shí)間片的調(diào)度算法基于時(shí)間片的調(diào)度算法 時(shí)間片輪轉(zhuǎn)時(shí)間片輪轉(zhuǎn)(Round-Robin) 多隊(duì)列反饋調(diào)度算法多隊(duì)列反饋調(diào)度算法(Multilevel Feedback) 3.3.1 3.3.1 主要的調(diào)度算法主要的調(diào)度算法42/136：按照作業(yè)進(jìn)入系統(tǒng)的先后次序來(lái)挑選作按照作業(yè)進(jìn)入系統(tǒng)的先后次序來(lái)挑選作 業(yè)，業(yè)，先進(jìn)入系統(tǒng)的作業(yè)優(yōu)先被挑選先進(jìn)入系統(tǒng)的作業(yè)優(yōu)先被挑選。 3.3.2 3.3.2 先來(lái)先服務(wù)算法先來(lái)先服務(wù)算法（First Come First Served）cpu43/136：按照作業(yè)進(jìn)入系統(tǒng)的先后次序

50、來(lái)挑選作按照作業(yè)進(jìn)入系統(tǒng)的先后次序來(lái)挑選作 業(yè)，業(yè)，先進(jìn)入系統(tǒng)的作業(yè)優(yōu)先被挑選先進(jìn)入系統(tǒng)的作業(yè)優(yōu)先被挑選。 3.2.2 3.2.2 先來(lái)先服務(wù)算法先來(lái)先服務(wù)算法（First Come First Served）1 12 23 34 45 5cpu44/136單位單位: :小時(shí)，以十進(jìn)制計(jì)）小時(shí)，以十進(jìn)制計(jì)）作作 業(yè)業(yè)提交時(shí)間提交時(shí)間運(yùn)行時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間開(kāi)始時(shí)間完成時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間 A A0 06 6 B B1 13 3 C C2 25 5 D D3 32 2平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間 t=t=平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間 w=w=0 06 66 61

51、16 69 98 82.672.679 9141412122.42.41414161613136.56.59.759.753.143.14=完成時(shí)間-提交時(shí)間=周轉(zhuǎn)時(shí)間/運(yùn)行時(shí)間45/136：p算法容易實(shí)現(xiàn)；算法容易實(shí)現(xiàn)；p適用于作業(yè)調(diào)度和進(jìn)程調(diào)度；適用于作業(yè)調(diào)度和進(jìn)程調(diào)度；p效率不高，只顧及作業(yè)等候時(shí)間，沒(méi)考慮作業(yè)要求服務(wù)效率不高，只顧及作業(yè)等候時(shí)間，沒(méi)考慮作業(yè)要求服務(wù)時(shí)間的長(zhǎng)短；時(shí)間的長(zhǎng)短；p不利于短作業(yè)。不利于短作業(yè)。46/13647/13648/136A(28)B(9)C(3)283740A(28)B(9)C(3)91240A(28)B(9)C(3)3124049/136： SJFSJ

52、F算法以進(jìn)入系統(tǒng)的作業(yè)所要求的算法以進(jìn)入系統(tǒng)的作業(yè)所要求的CPUCPU時(shí)間為標(biāo)準(zhǔn)，總選取時(shí)間為標(biāo)準(zhǔn)，總選取估計(jì)計(jì)算時(shí)間最短的估計(jì)計(jì)算時(shí)間最短的作業(yè)投入運(yùn)行。作業(yè)投入運(yùn)行。3.3.3 最短作業(yè)優(yōu)先算法（Shortest Job First）cpu50/136： SJFSJF算法以進(jìn)入系統(tǒng)的作業(yè)所要求的算法以進(jìn)入系統(tǒng)的作業(yè)所要求的CPUCPU時(shí)間為標(biāo)準(zhǔn)，總選取時(shí)間為標(biāo)準(zhǔn)，總選取估計(jì)計(jì)算時(shí)間最短的估計(jì)計(jì)算時(shí)間最短的作業(yè)投入運(yùn)行。作業(yè)投入運(yùn)行。3.3.3 最短作業(yè)優(yōu)先算法（Shortest Job First）1 12 23 34 45 5cpu51/136單位單位: :小時(shí)，以十進(jìn)制計(jì)）小時(shí)，以十進(jìn)

53、制計(jì)）作作 業(yè)業(yè)提交時(shí)間提交時(shí)間運(yùn)行時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間開(kāi)始時(shí)間完成時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A A0 06 6B B1 13 3CC2 25 5D D3 32 2平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間 t=t=平均帶權(quán)周轉(zhuǎn)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間 w=w=0 06 66 61 18 8111110103.33.31111161614142.82.86 68 85 52.52.58.758.752.42.4FCFSt=9.75w=3.14SJF的平均作業(yè)周轉(zhuǎn)時(shí)間比FCFS要小，故它的調(diào)度性能 比FCFS好=完成時(shí)間-提交時(shí)間=周轉(zhuǎn)時(shí)間/運(yùn)行時(shí)間52/136：p算法容易實(shí)現(xiàn)；算法容易實(shí)現(xiàn)

54、；p適用于作業(yè)調(diào)度；適用于作業(yè)調(diào)度；p能有效降低作業(yè)的平均等待時(shí)間；能有效降低作業(yè)的平均等待時(shí)間；p忽視了作業(yè)等待時(shí)間，對(duì)長(zhǎng)作業(yè)不利，有可能導(dǎo)致長(zhǎng)作忽視了作業(yè)等待時(shí)間，對(duì)長(zhǎng)作業(yè)不利，有可能導(dǎo)致長(zhǎng)作業(yè)（進(jìn)程）長(zhǎng)期不被調(diào)度（業(yè)（進(jìn)程）長(zhǎng)期不被調(diào)度（出現(xiàn)饑餓現(xiàn)象出現(xiàn)饑餓現(xiàn)象）；）；p要精確知道一個(gè)作業(yè)的運(yùn)行時(shí)間比較困難的。要精確知道一個(gè)作業(yè)的運(yùn)行時(shí)間比較困難的。53/13654/136作作 業(yè)業(yè) 提交時(shí)間提交時(shí)間 運(yùn)行時(shí)間運(yùn)行時(shí)間A A0 06 6B B1 13 3CC2 25 5D D3 32 255/136作業(yè)作業(yè)提交時(shí)間提交時(shí)間運(yùn)行時(shí)間運(yùn)行時(shí)間首次開(kāi)始首次開(kāi)始首次完成首次完成再次開(kāi)始再次開(kāi)始再

55、次完成再次完成周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)帶權(quán)周轉(zhuǎn) A A0 06 6 B B1 13 3 C C2 25 5D D3 32 2平均周轉(zhuǎn)時(shí)間 t=平均帶權(quán)周轉(zhuǎn)時(shí)間 w=56/1363.3.4 最高響應(yīng)比優(yōu)先（Highest Response Ratio First）：p靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時(shí)確定的，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變。p動(dòng)態(tài)優(yōu)先權(quán)動(dòng)態(tài)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時(shí)賦予的優(yōu)先權(quán)，是可以隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變。57/136u最高響應(yīng)比優(yōu)先（Highest Response Ratio First）：要求服務(wù)時(shí)間等待時(shí)間要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間1pR：l等待時(shí)間相近，服

56、務(wù)時(shí)間越短，優(yōu)先權(quán)越高等待時(shí)間相近，服務(wù)時(shí)間越短，優(yōu)先權(quán)越高SJFl服務(wù)時(shí)間相近，等待時(shí)間越長(zhǎng)，優(yōu)先權(quán)越高服務(wù)時(shí)間相近，等待時(shí)間越長(zhǎng)，優(yōu)先權(quán)越高FCFS： HRRF算法在當(dāng)前作業(yè)執(zhí)行完時(shí)算法在當(dāng)前作業(yè)執(zhí)行完時(shí), ,計(jì)算剩計(jì)算剩余作業(yè)的響應(yīng)比，選取余作業(yè)的響應(yīng)比，選取響應(yīng)比最高的響應(yīng)比最高的作業(yè)投入運(yùn)行。作業(yè)投入運(yùn)行。58/136以下四個(gè)作業(yè)先后到達(dá)系統(tǒng)進(jìn)入調(diào)度：p 開(kāi)始只有開(kāi)始只有作業(yè)作業(yè)1 1，被選中執(zhí)行時(shí)間，被選中執(zhí)行時(shí)間20ms20ms；p作業(yè)作業(yè)1 1執(zhí)行完畢，響應(yīng)比依次為執(zhí)行完畢，響應(yīng)比依次為1+15/151+15/15、1+10/51+10/5、1+5/101+5/10，作業(yè)作業(yè)3

57、 3被被 選中，執(zhí)行時(shí)間選中，執(zhí)行時(shí)間5ms5ms；p作業(yè)作業(yè)3 3執(zhí)行完畢，響應(yīng)比依次為執(zhí)行完畢，響應(yīng)比依次為1+20/151+20/15、1+10/101+10/10，作業(yè)作業(yè)2 2被選中，被選中，執(zhí)行時(shí)間執(zhí)行時(shí)間15ms15ms；p作業(yè)作業(yè)2 2執(zhí)行完畢，執(zhí)行完畢，作業(yè)作業(yè)4 4被選中，執(zhí)行時(shí)間被選中，執(zhí)行時(shí)間10ms10ms；平均作業(yè)周轉(zhuǎn)時(shí)間平均作業(yè)周轉(zhuǎn)時(shí)間T T = (20+15+35+35)/4 = = (20+15+35+35)/4 = 26.2526.25平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間平均帶權(quán)作業(yè)周轉(zhuǎn)時(shí)間WW = (20/20+15/5+35/15+35/10)/4 = = (20/20

58、+15/5+35/15+35/10)/4 = 2.462.4659/136：p 算法適用于作業(yè)調(diào)度；算法適用于作業(yè)調(diào)度；p 既考慮作業(yè)等待時(shí)間，又考慮作業(yè)的運(yùn)行時(shí)既考慮作業(yè)等待時(shí)間，又考慮作業(yè)的運(yùn)行時(shí)間間 ；p 既照顧短作業(yè)又不使長(zhǎng)作業(yè)的等待時(shí)間過(guò)既照顧短作業(yè)又不使長(zhǎng)作業(yè)的等待時(shí)間過(guò)長(zhǎng)長(zhǎng) ; ;p 計(jì)算響應(yīng)比需要耗費(fèi)時(shí)間。計(jì)算響應(yīng)比需要耗費(fèi)時(shí)間。60/13661/136： 系統(tǒng)按照系統(tǒng)按照固定的固定的時(shí)間片時(shí)間片依次輪流依次輪流執(zhí)行就執(zhí)行就緒隊(duì)列中的各個(gè)進(jìn)程。緒隊(duì)列中的各個(gè)進(jìn)程。3.3.5 時(shí)間片輪轉(zhuǎn)法（Round-Robin)ABCD62/136有三個(gè)進(jìn)程有三個(gè)進(jìn)程P1P1、P2P2、P3P

59、3先后到達(dá)，它們分別需要先后到達(dá)，它們分別需要2020、4 4和和2 2個(gè)單位時(shí)間運(yùn)行完畢。假如它們按個(gè)單位時(shí)間運(yùn)行完畢。假如它們按P1P1、P2P2、P3P3的順序執(zhí)行，且的順序執(zhí)行，且，則三進(jìn)程各自的，則三進(jìn)程各自的是多少個(gè)時(shí)間單位。是多少個(gè)時(shí)間單位。p假如它們按P1、P2、P3的順序執(zhí)行，且不可剝奪不可剝奪，p則三進(jìn)程各自的周轉(zhuǎn)時(shí)間分別為20、24、 26個(gè)單位時(shí)間，p平均周轉(zhuǎn)時(shí)間是23.33個(gè)時(shí)間單位。63/136有三個(gè)進(jìn)程有三個(gè)進(jìn)程P1P1、P2P2、P3P3先后到達(dá)，分別需要先后到達(dá)，分別需要2020、4 4和和2 2個(gè)個(gè)單位時(shí)間運(yùn)行完畢，假如用時(shí)間片輪轉(zhuǎn)原則的剝奪調(diào)度方式，時(shí)間片

60、單位時(shí)間運(yùn)行完畢，假如用時(shí)間片輪轉(zhuǎn)原則的剝奪調(diào)度方式，時(shí)間片為為2 2個(gè)時(shí)間單位。則各進(jìn)程的周轉(zhuǎn)時(shí)間和平均周轉(zhuǎn)時(shí)間。個(gè)時(shí)間單位。則各進(jìn)程的周轉(zhuǎn)時(shí)間和平均周轉(zhuǎn)時(shí)間。02468101214161820222426p1p2p1p1p1p1p1p1p1p1P1、P2、P3的周轉(zhuǎn)時(shí)間分別為26、10、6平均周轉(zhuǎn)時(shí)間為（26+10+6）/3=1464/136：p 算法主要針對(duì)分時(shí)系統(tǒng)，適用于進(jìn)程調(diào)度；p 對(duì)用戶的響應(yīng)及時(shí)、快速；p 時(shí)間片的長(zhǎng)度確定比較困難；p 進(jìn)程切換開(kāi)銷比較大。65/13666/136 算法FCFSFCFSSJFSJFHRRFHRRFRRRR 項(xiàng)目適用范圍搶占性優(yōu)點(diǎn)缺點(diǎn)作業(yè)、進(jìn)程作業(yè)、