chap3處理機(jī)調(diào)度與死鎖

1、一、處理機(jī)的多級(jí)調(diào)度策略第三章 處理機(jī)的調(diào)度與死鎖處理機(jī)調(diào)度是操作系統(tǒng)的主要功能之一，它的實(shí)現(xiàn)策略決定了操作系統(tǒng)的類型，處理機(jī)調(diào)度是操作系統(tǒng)的主要功能之一，它的實(shí)現(xiàn)策略決定了操作系統(tǒng)的類型，其調(diào)度算法的優(yōu)劣直接影響整個(gè)系統(tǒng)的性能其調(diào)度算法的優(yōu)劣直接影響整個(gè)系統(tǒng)的性能。處理機(jī)處理機(jī)調(diào)度的任務(wù)調(diào)度的任務(wù)是選出待分派的作業(yè)或進(jìn)程，為之分配處理機(jī)。是選出待分派的作業(yè)或進(jìn)程，為之分配處理機(jī)。一般來(lái)說(shuō)，處理機(jī)調(diào)度可分為三個(gè)級(jí)別，分別是高級(jí)調(diào)度、中級(jí)調(diào)度和低級(jí)調(diào)度。一般來(lái)說(shuō)，處理機(jī)調(diào)度可分為三個(gè)級(jí)別，分別是高級(jí)調(diào)度、中級(jí)調(diào)度和低級(jí)調(diào)度。1、高級(jí)調(diào)度又稱作業(yè)調(diào)度、高級(jí)調(diào)度又稱作業(yè)調(diào)度，作業(yè)就是用戶程序及其所需

2、的數(shù)據(jù)和命令的集合，作業(yè)就是用戶程序及其所需的數(shù)據(jù)和命令的集合，作業(yè)管理就是對(duì)作業(yè)的執(zhí)行情況進(jìn)行系統(tǒng)管理的程序的集合。作業(yè)調(diào)度程序的主作業(yè)管理就是對(duì)作業(yè)的執(zhí)行情況進(jìn)行系統(tǒng)管理的程序的集合。作業(yè)調(diào)度程序的主要功能是審查系統(tǒng)是否能滿足用戶作業(yè)的資源要求以及按照一定的算法來(lái)選取作要功能是審查系統(tǒng)是否能滿足用戶作業(yè)的資源要求以及按照一定的算法來(lái)選取作業(yè)。業(yè)。2、引入、引入中級(jí)調(diào)度中級(jí)調(diào)度的主要目的是為了提高內(nèi)存的利用率和系統(tǒng)吞吐量，使得暫時(shí)的主要目的是為了提高內(nèi)存的利用率和系統(tǒng)吞吐量，使得暫時(shí)不運(yùn)行的進(jìn)程從內(nèi)存對(duì)換到外存上。不運(yùn)行的進(jìn)程從內(nèi)存對(duì)換到外存上。 3、低級(jí)調(diào)度又稱進(jìn)程調(diào)度、低級(jí)調(diào)度又稱進(jìn)程調(diào)

3、度，其主要功能是根據(jù)一定的算法將，其主要功能是根據(jù)一定的算法將CPU分派給就緒隊(duì)分派給就緒隊(duì)列中的一個(gè)進(jìn)程。進(jìn)程調(diào)度是操作系統(tǒng)中最基本的一種調(diào)度，其調(diào)度策略的優(yōu)劣列中的一個(gè)進(jìn)程。進(jìn)程調(diào)度是操作系統(tǒng)中最基本的一種調(diào)度，其調(diào)度策略的優(yōu)劣直接影響整個(gè)系統(tǒng)的性能。直接影響整個(gè)系統(tǒng)的性能。n幾點(diǎn)說(shuō)明：在多道批處理系統(tǒng)中，既有高級(jí)調(diào)度，又有低級(jí)調(diào)度，也可以采用中級(jí)調(diào)度。在分時(shí)系統(tǒng)中，一般沒(méi)有高級(jí)調(diào)度，只有低級(jí)調(diào)度，一般會(huì)采用中級(jí)調(diào)度在實(shí)時(shí)系統(tǒng)中，只有低級(jí)調(diào)度在支持多道程序的操作系統(tǒng)中，一般存在進(jìn)程調(diào)度有的操作系統(tǒng)采用中級(jí)調(diào)度，有的操作系統(tǒng)沒(méi)有中級(jí)調(diào)度二、處理機(jī)的調(diào)度隊(duì)列模型1、僅有進(jìn)程調(diào)度的處理高度隊(duì)形模

4、型（分時(shí)系統(tǒng)中）、僅有進(jìn)程調(diào)度的處理高度隊(duì)形模型（分時(shí)系統(tǒng)中）就 緒隊(duì) 列阻 塞隊(duì)列進(jìn)程調(diào)度CPU進(jìn)程完成等待事件交互用戶事件出現(xiàn)時(shí)間片完2、具有兩級(jí)調(diào)度的處理機(jī)調(diào)度隊(duì)列模型（多道批處理系統(tǒng)中）、具有兩級(jí)調(diào)度的處理機(jī)調(diào)度隊(duì)列模型（多道批處理系統(tǒng)中）就緒隊(duì)列進(jìn)程調(diào)度CPU進(jìn)程完成等待事件1作業(yè)調(diào)度事件 1出現(xiàn)時(shí)間片完等待事件2事件 2出現(xiàn)等待事件n事件 n 出現(xiàn)后備隊(duì)列該模型與上一模型的主要區(qū)別在于如下兩個(gè)方面： (1)就緒隊(duì)列的形式。 (2) 設(shè)置多個(gè)阻塞隊(duì)列。3、具有三級(jí)調(diào)度的處理機(jī)調(diào)度隊(duì)列模型（多道批處理和分時(shí)系統(tǒng)中）、具有三級(jí)調(diào)度的處理機(jī)調(diào)度隊(duì)列模型（多道批處理和分時(shí)系統(tǒng)中）就緒隊(duì)列進(jìn)程

5、調(diào)度CPU就緒，掛起隊(duì)列中級(jí)調(diào)度阻塞，掛起隊(duì)列阻塞隊(duì)列等待事件進(jìn)程完成時(shí)間片完作業(yè)調(diào)度交互型作業(yè)后備隊(duì)列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn)三、調(diào)度性能的衡量指標(biāo)對(duì)批處理系統(tǒng)應(yīng)盡量提高各種資源的利用率和增加系統(tǒng)的吞吐量分時(shí)系統(tǒng)應(yīng)保證對(duì)用戶的響應(yīng)時(shí)間的要求實(shí)時(shí)系統(tǒng)必須及時(shí)和可靠的處理衡量作業(yè)調(diào)度和進(jìn)程調(diào)度性能的指標(biāo)如下： （1）CPU利用率（2）吞吐量-單位時(shí)間內(nèi)CPU完成作業(yè)的數(shù)量。（3）周轉(zhuǎn)時(shí)間-從作業(yè)提交到作業(yè)完成的時(shí)間間隔。（4）等待時(shí)間作業(yè)或進(jìn)程從進(jìn)入系統(tǒng)到被調(diào)度并開(kāi)始執(zhí)行所經(jīng)歷的時(shí)間 （5）響應(yīng)時(shí)間-從提交第一個(gè)請(qǐng)求到產(chǎn)生第一個(gè)響應(yīng)所用的時(shí)間 （6）平均帶權(quán)周轉(zhuǎn)時(shí)間 作業(yè)i周轉(zhuǎn)時(shí)間作業(yè)i執(zhí)行

6、時(shí)間作業(yè)總數(shù)作業(yè)調(diào)度：就是要按一定的策略選取一個(gè)或多個(gè)作業(yè)，為它們分配必需的資源（內(nèi)存空間、I/O設(shè)備等），使它們能夠并發(fā)執(zhí)行。作業(yè)調(diào)度的必要條件是：系統(tǒng)現(xiàn)有尚未分配的資源可以滿足該作業(yè)的資源需求。作業(yè)分類批量型作業(yè)終端型作業(yè)一、批量型作業(yè)的組織1、作業(yè)申請(qǐng)（作業(yè)情況、資源要求）2、作業(yè)實(shí)體（作業(yè)操作說(shuō)明書(shū)、源程序或目標(biāo)模塊程序、數(shù)據(jù)集合、修改信息（可沒(méi)有）3.2 調(diào)度算法作業(yè)調(diào)度二、批處理系統(tǒng)中作業(yè)的狀態(tài)及其轉(zhuǎn)換四種狀態(tài)：提交、后備、執(zhí)行和完成3.2 調(diào)度算法作業(yè)調(diào)度三、實(shí)現(xiàn)作業(yè)狀態(tài)轉(zhuǎn)換的程序1、SPOOLing系統(tǒng)程序包括輸入程序、輸出程序、井管理程序（讀子程序、寫(xiě)子程序）2、作業(yè)調(diào)度程序

7、作業(yè)調(diào)度程序負(fù)責(zé)作業(yè)從“后備狀態(tài)”到“執(zhí)行狀態(tài)”以及從“執(zhí)行狀態(tài)”到“完成狀態(tài)”的轉(zhuǎn)換，作業(yè)調(diào)度程序?yàn)樽鳂I(yè)分配的是一臺(tái)虛擬的邏輯處理機(jī)。n作業(yè)調(diào)度：作業(yè)調(diào)度：按照某種調(diào)度算法從后備作業(yè)隊(duì)列中挑選一個(gè)/幾個(gè)作業(yè)進(jìn)入內(nèi)存，參加運(yùn)行。同時(shí)分配資源，做好運(yùn)行前的準(zhǔn)備。3.2 調(diào)度算法作業(yè)調(diào)度3、進(jìn)程調(diào)度程序進(jìn)程調(diào)度程序的主要任務(wù)：實(shí)現(xiàn)進(jìn)程從“就緒狀態(tài)”到“運(yùn)行狀態(tài)”的轉(zhuǎn)變。它總是按照確定的調(diào)度算法從就緒隊(duì)列中選擇一個(gè)進(jìn)程，讓它占有CPU運(yùn)行，進(jìn)程調(diào)度程序?yàn)樽鳂I(yè)分配的是一臺(tái)真實(shí)的物理處理機(jī)。4、交通控制程序交通控制程序負(fù)責(zé)進(jìn)程狀態(tài)的轉(zhuǎn)換和進(jìn)程之間的通信。3.2 調(diào)度算法作業(yè)調(diào)度四、作業(yè)調(diào)度所需的數(shù)據(jù)結(jié)構(gòu)

8、及其組織1、作業(yè)控制塊2、作業(yè)后備隊(duì)列3.2 調(diào)度算法作業(yè)調(diào)度五、作業(yè)調(diào)度算法的設(shè)計(jì)原則n面向用戶的準(zhǔn)則：周轉(zhuǎn)時(shí)間短；響應(yīng)時(shí)間快；截止時(shí)間的保證；優(yōu)先權(quán)準(zhǔn)則n面向系統(tǒng)的準(zhǔn)則：系統(tǒng)吞吐量高；處理機(jī)利用率好；各類資源的平衡利用3.2 調(diào)度算法作業(yè)調(diào)度六、常用的作業(yè)調(diào)度算法n先來(lái)先服務(wù)調(diào)度算法（先來(lái)先服務(wù)調(diào)度算法（FCFS）特點(diǎn)：簡(jiǎn)單容易實(shí)現(xiàn)，有利于長(zhǎng)作業(yè)，但不利于短作業(yè)特點(diǎn)：簡(jiǎn)單容易實(shí)現(xiàn)，有利于長(zhǎng)作業(yè)，但不利于短作業(yè)3.2 調(diào)度算法作業(yè)調(diào)度2、最短作業(yè)優(yōu)先調(diào)度算法（、最短作業(yè)優(yōu)先調(diào)度算法（SJF）特點(diǎn)：易于實(shí)現(xiàn)，會(huì)使系統(tǒng)平均周轉(zhuǎn)時(shí)間最短，系統(tǒng)吞吐量大。特點(diǎn)：易于實(shí)現(xiàn)，會(huì)使系統(tǒng)平均周轉(zhuǎn)時(shí)間最短，系統(tǒng)

9、吞吐量大。但忽視了作業(yè)的等待時(shí)間，不利于長(zhǎng)作業(yè)，會(huì)出現(xiàn)但忽視了作業(yè)的等待時(shí)間，不利于長(zhǎng)作業(yè)，會(huì)出現(xiàn)“餓死餓死”現(xiàn)象?，F(xiàn)象。3.2 調(diào)度算法作業(yè)調(diào)度3、響應(yīng)比高者優(yōu)先（HRRF）特點(diǎn)：算法較為復(fù)雜，每當(dāng)調(diào)度作業(yè)時(shí)都需要進(jìn)行響應(yīng)比的計(jì)特點(diǎn)：算法較為復(fù)雜，每當(dāng)調(diào)度作業(yè)時(shí)都需要進(jìn)行響應(yīng)比的計(jì)算。但它既照顧了用戶作業(yè)到來(lái)的先后，又考慮了要求系統(tǒng)服算。但它既照顧了用戶作業(yè)到來(lái)的先后，又考慮了要求系統(tǒng)服務(wù)時(shí)間的長(zhǎng)短。務(wù)時(shí)間的長(zhǎng)短。3.2 調(diào)度算法作業(yè)調(diào)度3.2 調(diào)度算法作業(yè)調(diào)度例子：分析n在多道批處理系統(tǒng)中，有下列1、2、3、4四個(gè)作業(yè)，提交時(shí)間分別是6.0、6.5、7.0、7.5，執(zhí)行時(shí)間分別是2.0、0

10、.5、0.1、0.2，用先來(lái)先服務(wù)調(diào)度算法和短作業(yè)調(diào)度算法進(jìn)行調(diào)度，哪一種算法調(diào)度性能好些？為什么？ 若后備作業(yè)隊(duì)列中等待運(yùn)行的同時(shí)有三個(gè)作業(yè)J1 、J2、J3 ，已知它們各自的運(yùn)行時(shí)間為a 、b 、c，且滿足a 退化為FCFS算法，進(jìn)程在一個(gè)時(shí)間片內(nèi)都執(zhí)行完，響應(yīng)時(shí)間長(zhǎng)。q過(guò)短用戶的一次請(qǐng)求需要多個(gè)時(shí)間片才能處理完，CPU現(xiàn)場(chǎng)切換次數(shù)增加，響應(yīng)時(shí)間長(zhǎng)?！緦?duì)響應(yīng)時(shí)間的要求】： T(響應(yīng)時(shí)間)=N(進(jìn)程數(shù)目)*q(時(shí)間片)【時(shí)間片長(zhǎng)度的影響因素】：q就緒進(jìn)程的數(shù)目：數(shù)目越多，時(shí)間片越小（當(dāng)響應(yīng)時(shí)間一定時(shí)）。q系統(tǒng)的處理能力：應(yīng)當(dāng)使用戶輸入通常在一個(gè)時(shí)間片內(nèi)能處理完，否則使響應(yīng)時(shí)間，平均周轉(zhuǎn)時(shí)間和

11、平均帶權(quán)周轉(zhuǎn)時(shí)間延長(zhǎng)。3.2 調(diào)度算法進(jìn)程調(diào)度3.2 調(diào)度算法進(jìn)程調(diào)度3.2 調(diào)度算法進(jìn)程調(diào)度3、多隊(duì)列輪轉(zhuǎn)調(diào)度算法 將系統(tǒng)內(nèi)進(jìn)程按各自屬性分為若干類，每一類組織一個(gè)就緒隊(duì)列，并為每一個(gè)就緒隊(duì)列規(guī)定一個(gè)調(diào)度優(yōu)先級(jí)，且還可以為不同的隊(duì)列規(guī)定不同的調(diào)度算法。多隊(duì)列算法首先將CPU分配給高優(yōu)先級(jí)隊(duì)列中的進(jìn)程。只有當(dāng)高優(yōu)先級(jí)隊(duì)列為空時(shí)，再將CPU分配給較低優(yōu)先級(jí)隊(duì)列中的進(jìn)程。各隊(duì)列需采用的調(diào)度算法也應(yīng)根據(jù)系統(tǒng)設(shè)計(jì)目標(biāo)而具體確定。例：分時(shí)批處理系統(tǒng)中，前臺(tái)作業(yè)（終端）、后臺(tái)作業(yè)（批處理作業(yè)）3.2 調(diào)度算法進(jìn)程調(diào)度4、多級(jí)反饋隊(duì)列調(diào)度算法q設(shè)置設(shè)置多個(gè)就緒隊(duì)列多個(gè)就緒隊(duì)列，分別賦予，分別賦予不同的優(yōu)先級(jí)

12、不同的優(yōu)先級(jí)，隊(duì)列，隊(duì)列1的優(yōu)先的優(yōu)先級(jí)最高，其他逐級(jí)降低。每隊(duì)列分配級(jí)最高，其他逐級(jí)降低。每隊(duì)列分配不同的時(shí)間片不同的時(shí)間片，規(guī)定優(yōu)，規(guī)定優(yōu)先級(jí)越低則時(shí)間片越長(zhǎng)。先級(jí)越低則時(shí)間片越長(zhǎng)。q新進(jìn)程就緒后，新進(jìn)程就緒后，先投入隊(duì)列先投入隊(duì)列1的末尾的末尾，按，按FCFS算法調(diào)度。若算法調(diào)度。若一個(gè)時(shí)間片未能執(zhí)行完，則一個(gè)時(shí)間片未能執(zhí)行完，則降低降低投入到隊(duì)列投入到隊(duì)列2的末尾；依此的末尾；依此類推，類推，降低到最后的隊(duì)列降低到最后的隊(duì)列，則按，則按“時(shí)間片輪轉(zhuǎn)時(shí)間片輪轉(zhuǎn)”算法調(diào)度直算法調(diào)度直到完成。到完成。q 進(jìn)程由于等待事件而放棄進(jìn)程由于等待事件而放棄CPU后后, 進(jìn)入等待隊(duì)列進(jìn)入等待隊(duì)列, 一

13、旦等待一旦等待的事件發(fā)生的事件發(fā)生, 則回到原來(lái)的就緒隊(duì)列。則回到原來(lái)的就緒隊(duì)列。q僅當(dāng)僅當(dāng)較高優(yōu)先級(jí)的隊(duì)列為空較高優(yōu)先級(jí)的隊(duì)列為空，才調(diào)度較低優(yōu)先級(jí)的隊(duì)列中的，才調(diào)度較低優(yōu)先級(jí)的隊(duì)列中的進(jìn)程執(zhí)行。如果進(jìn)程執(zhí)行時(shí)有新進(jìn)程進(jìn)入較高優(yōu)先級(jí)的隊(duì)列，進(jìn)程執(zhí)行。如果進(jìn)程執(zhí)行時(shí)有新進(jìn)程進(jìn)入較高優(yōu)先級(jí)的隊(duì)列，則則搶先搶先執(zhí)行新進(jìn)程，并把執(zhí)行新進(jìn)程，并把被搶先的進(jìn)程投入原隊(duì)列的末尾被搶先的進(jìn)程投入原隊(duì)列的末尾。3.2 調(diào)度算法進(jìn)程調(diào)度進(jìn)程調(diào)度進(jìn)程調(diào)度多級(jí)反饋隊(duì)列調(diào)度算法的特點(diǎn)多級(jí)反饋隊(duì)列調(diào)度算法的特點(diǎn) 合理地考慮了分時(shí)系統(tǒng)平均響應(yīng)時(shí)間，考慮了批處理系統(tǒng)短進(jìn)程優(yōu)先，能使I/O為主的進(jìn)程優(yōu)先于CPU為主的進(jìn)程。這

14、種調(diào)度算法能適用于同時(shí)支持分時(shí)、實(shí)時(shí)、批處理的通用操作系統(tǒng)。3.2 調(diào)度算法進(jìn)程調(diào)度n5、實(shí)時(shí)調(diào)度算法、實(shí)時(shí)調(diào)度算法實(shí)時(shí)調(diào)度的基本要求：保證計(jì)算機(jī)在規(guī)定的時(shí)間內(nèi)對(duì)外部事件的實(shí)時(shí)調(diào)度的基本要求：保證計(jì)算機(jī)在規(guī)定的時(shí)間內(nèi)對(duì)外部事件的請(qǐng)求作出響應(yīng)。請(qǐng)求作出響應(yīng)。強(qiáng)實(shí)時(shí)系統(tǒng)：計(jì)算機(jī)對(duì)事件的響應(yīng)必須在規(guī)定的時(shí)間內(nèi)（最終期強(qiáng)實(shí)時(shí)系統(tǒng)：計(jì)算機(jī)對(duì)事件的響應(yīng)必須在規(guī)定的時(shí)間內(nèi)（最終期限）限）弱實(shí)時(shí)系統(tǒng)：允許偶爾的失誤弱實(shí)時(shí)系統(tǒng)：允許偶爾的失誤實(shí)時(shí)調(diào)度策略（動(dòng)態(tài)調(diào)度和靜態(tài)調(diào)度）實(shí)時(shí)調(diào)度策略（動(dòng)態(tài)調(diào)度和靜態(tài)調(diào)度）靜態(tài)調(diào)度：進(jìn)程的調(diào)度順序是預(yù)先規(guī)定好的靜態(tài)調(diào)度：進(jìn)程的調(diào)度順序是預(yù)先規(guī)定好的動(dòng)態(tài)調(diào)度：進(jìn)程的調(diào)度順序是動(dòng)

15、態(tài)變化的且在運(yùn)行時(shí)決定動(dòng)態(tài)調(diào)度：進(jìn)程的調(diào)度順序是動(dòng)態(tài)變化的且在運(yùn)行時(shí)決定等級(jí)單調(diào)算法：它根據(jù)各個(gè)進(jìn)程的觸發(fā)事件的發(fā)生順序給每個(gè)進(jìn)等級(jí)單調(diào)算法：它根據(jù)各個(gè)進(jìn)程的觸發(fā)事件的發(fā)生順序給每個(gè)進(jìn)程賦予一個(gè)優(yōu)先權(quán)，運(yùn)行時(shí)，調(diào)度者總是運(yùn)行優(yōu)先權(quán)最高的可程賦予一個(gè)優(yōu)先權(quán)，運(yùn)行時(shí)，調(diào)度者總是運(yùn)行優(yōu)先權(quán)最高的可執(zhí)行進(jìn)程，調(diào)度方式可以采用搶先式。執(zhí)行進(jìn)程，調(diào)度方式可以采用搶先式。最早最終期限優(yōu)先法：進(jìn)程調(diào)度的優(yōu)先級(jí)根據(jù)相應(yīng)事件的最終期最早最終期限優(yōu)先法：進(jìn)程調(diào)度的優(yōu)先級(jí)根據(jù)相應(yīng)事件的最終期限的時(shí)間來(lái)確定，最終期限的時(shí)間越短，其優(yōu)先級(jí)越高。限的時(shí)間來(lái)確定，最終期限的時(shí)間越短，其優(yōu)先級(jí)越高。最小松弛時(shí)間優(yōu)先：系統(tǒng)首先為

16、每個(gè)進(jìn)程計(jì)算它可以讓出的時(shí)間最小松弛時(shí)間優(yōu)先：系統(tǒng)首先為每個(gè)進(jìn)程計(jì)算它可以讓出的時(shí)間（松弛時(shí)間），調(diào)度時(shí)系統(tǒng)選取松弛時(shí)間最小的運(yùn)行。（松弛時(shí)間），調(diào)度時(shí)系統(tǒng)選取松弛時(shí)間最小的運(yùn)行。練習(xí)題：n 在所學(xué)的調(diào)度算法中，對(duì)所有進(jìn)程和作業(yè)都是公平合理的調(diào)度算法是 A ；最有利于提高系統(tǒng)吞吐量的作業(yè)調(diào)度算法是 B ；能兼顧作業(yè)等待時(shí)間和作業(yè)執(zhí)行時(shí)間調(diào)度算法是 C ；最有利于提高資源的使用率、能使短作業(yè)、長(zhǎng)作業(yè)及交互作業(yè)用戶都比較滿意的調(diào)度算法是 D ；為實(shí)現(xiàn)人機(jī)交互作用應(yīng)采用調(diào)度算法是 E ；能對(duì)緊急作業(yè)進(jìn)行及時(shí)處理的調(diào)度算法是 F 。nAF：(1)FCFS調(diào)度算法； (2)短作業(yè)優(yōu)先調(diào)度算法；n (3)

17、時(shí)間片輪轉(zhuǎn)法； (4)多級(jí)反饋隊(duì)列調(diào)度算法；n (5)高響應(yīng)比優(yōu)先算法；n (6)基于優(yōu)先權(quán)的剝奪調(diào)度算法。練習(xí)題：n1操作系統(tǒng)的主要性能參數(shù)：操作系統(tǒng)的主要性能參數(shù)： A 指的是單位時(shí)間內(nèi)系統(tǒng)處理的作業(yè)量。指的是單位時(shí)間內(nèi)系統(tǒng)處理的作業(yè)量。A：（：（1）周轉(zhuǎn)時(shí)間；）周轉(zhuǎn)時(shí)間； （2）處理時(shí)間；）處理時(shí)間； （3）消逝時(shí)間；）消逝時(shí)間； （4）利用率；）利用率； （5）生產(chǎn)率；生產(chǎn)率； （6）吞吐量。）吞吐量。n2在所學(xué)的調(diào)度算法中，為實(shí)現(xiàn)人機(jī)交互作用應(yīng)采用調(diào)度算法是在所學(xué)的調(diào)度算法中，為實(shí)現(xiàn)人機(jī)交互作用應(yīng)采用調(diào)度算法是 A 。A：（：（1）FCFS調(diào)度算法；調(diào)度算法； （2）短作業(yè)優(yōu)先調(diào)度算

18、法；）短作業(yè)優(yōu)先調(diào)度算法； （3）時(shí)間片輪轉(zhuǎn)法；）時(shí)間片輪轉(zhuǎn)法； （4）多級(jí)反饋隊(duì)列調(diào)度算法；）多級(jí)反饋隊(duì)列調(diào)度算法； （5）高響應(yīng)比優(yōu)先算法；）高響應(yīng)比優(yōu)先算法； （6）基于優(yōu)先）基于優(yōu)先權(quán)的剝奪調(diào)度算法。權(quán)的剝奪調(diào)度算法。n3. 時(shí)間片輪轉(zhuǎn)算法中時(shí)間片足夠大時(shí)，該算法退化為時(shí)間片輪轉(zhuǎn)算法中時(shí)間片足夠大時(shí)，該算法退化為 A 。 A： （1）時(shí)間片輪轉(zhuǎn)算法）時(shí)間片輪轉(zhuǎn)算法 （2）先進(jìn)先出調(diào)度算法）先進(jìn)先出調(diào)度算法 (3)高響應(yīng)比優(yōu)先算法高響應(yīng)比優(yōu)先算法 （4）短作業(yè)優(yōu)先算法）短作業(yè)優(yōu)先算法n4.作業(yè)調(diào)度是按某種算法從磁盤(pán)輸入井的作業(yè)調(diào)度是按某種算法從磁盤(pán)輸入井的 A 中選一個(gè)作業(yè)裝入主存運(yùn)行。

19、中選一個(gè)作業(yè)裝入主存運(yùn)行。 A：（：（1）就緒隊(duì)列）就緒隊(duì)列 （2）等待隊(duì)列）等待隊(duì)列 （3）作業(yè)后備隊(duì)列）作業(yè)后備隊(duì)列 （4）提交隊(duì)列）提交隊(duì)列n5.作業(yè)調(diào)度與進(jìn)程調(diào)度的主要區(qū)別是：作業(yè)調(diào)度與進(jìn)程調(diào)度的主要區(qū)別是： A 。A：（：（1）作業(yè)調(diào)度比進(jìn)程調(diào)度頻繁）作業(yè)調(diào)度比進(jìn)程調(diào)度頻繁 （2）兩種調(diào)度的算法完全不同）兩種調(diào)度的算法完全不同 （3）兩種調(diào)度的性能指標(biāo)完全不同）兩種調(diào)度的性能指標(biāo)完全不同 (4)進(jìn)程調(diào)度比作業(yè)調(diào)度頻繁進(jìn)程調(diào)度比作業(yè)調(diào)度頻繁3.3 死鎖死鎖：指多個(gè)進(jìn)程在運(yùn)行的時(shí)候因?yàn)楦?jìng)爭(zhēng)資源而陷入的一種僵局，陷入這種僵局的進(jìn)程，若無(wú)外力的作用將無(wú)法再向前推進(jìn)。產(chǎn)生死鎖的原因：1、進(jìn)程對(duì)

20、資源的競(jìng)爭(zhēng) 當(dāng)若干進(jìn)程需求資源的總數(shù)大于系統(tǒng)能提供的資源數(shù)時(shí)，進(jìn)程間就會(huì)出現(xiàn)競(jìng)爭(zhēng)資源的現(xiàn)象，若管理不當(dāng)就可能引起死鎖。2、資源分配策略 如果按某種資源分配策略分配資源時(shí)使得某些進(jìn)程各自占用了部分資源后又都在等待其他進(jìn)程所占的資源，且互不相讓，則出會(huì)引起死鎖。3、并發(fā)進(jìn)程執(zhí)行速度 并發(fā)進(jìn)程執(zhí)行的速度不能由進(jìn)程自己來(lái)控制，如果協(xié)調(diào)不好的話也會(huì)出現(xiàn)循環(huán)等待資源的情況。 例：系統(tǒng)有打印機(jī)、讀卡機(jī)各一臺(tái)，被進(jìn)程P、Q共享。兩個(gè)進(jìn)程并發(fā)執(zhí)行，按以下順序請(qǐng)求和釋放資源：進(jìn)程PA1：請(qǐng)求讀卡機(jī) A2：請(qǐng)求打印機(jī) A3：釋放讀卡機(jī) A4：釋放打印機(jī)進(jìn)程QB1：請(qǐng)求打印機(jī) B2：請(qǐng)求讀卡機(jī) B3：釋放讀卡機(jī) B4

21、：釋放打印機(jī)A1、A2、A3、A4、B1、B2、B3、B4B1、B2、B3、B4、A1、A2、A3、A4A1、A2、B1、B2、A3、A4、B3、B4A1、B1、A2、B2、A3、B3、A4、B4 分析上面四種執(zhí)行順序哪個(gè)可能會(huì)產(chǎn)生死鎖分析上面四種執(zhí)行順序哪個(gè)可能會(huì)產(chǎn)生死鎖產(chǎn)生死鎖的必要條件n 從以上分析可見(jiàn)，如果在計(jì)算機(jī)系統(tǒng)中同時(shí)具備同時(shí)具備下面四個(gè)必要條件時(shí)，那麼會(huì)發(fā)生死鎖。換句話說(shuō)，只要下面四個(gè)條件有一個(gè)不具備，系統(tǒng)就不會(huì)出現(xiàn)死鎖。n 1互斥條件?；コ鈼l件。即某個(gè)資源在一段時(shí)間內(nèi)只能由一個(gè)進(jìn)程占有，不能同時(shí)被兩個(gè)或兩個(gè)以上的進(jìn)程占有。這種獨(dú)占資源如CD-ROM驅(qū)動(dòng)器，打印機(jī)等等，必須在占

22、有該資源的進(jìn)程主動(dòng)釋放它之后，其它進(jìn)程才能占有該資源。這是由資源本身的屬性所決定的。如獨(dú)木橋就是一種獨(dú)占資源，兩方的人不能同時(shí)過(guò)橋。n 2不可搶占條件。不可搶占條件。進(jìn)程所獲得的資源在未使用完畢之前，資源申請(qǐng)者不能強(qiáng)行地從資源占有者手中奪取資源，而只能由該資源的占有者進(jìn)程自行釋放。如過(guò)獨(dú)木橋的人不能強(qiáng)迫對(duì)方后退，也不能非法地將對(duì)方推下橋，必須是橋上的人自己過(guò)橋后空出橋面（即主動(dòng)釋放占有資源），對(duì)方的人才能過(guò)橋。n 3占有且申請(qǐng)條件。占有且申請(qǐng)條件。進(jìn)程至少已經(jīng)占有一個(gè)資源，但又申請(qǐng)新的資源；由于該資源已被另外進(jìn)程占有，此時(shí)該進(jìn)程阻塞；但是，它在等待新資源之時(shí)，仍繼續(xù)占用已占有的資源。還以過(guò)獨(dú)木

23、橋?yàn)槔?，甲乙兩人在橋上相遇。甲走過(guò)一段橋面（即占有了一些資源），還需要走其余的橋面（申請(qǐng)新的資源），但那部分橋面被乙占有（乙走過(guò)一段橋面）。甲過(guò)不去，前進(jìn)不能，又不后退；乙也處于同樣的狀況。n 4循環(huán)等待條件。循環(huán)等待條件。存在一個(gè)進(jìn)程等待序列P1，P2，.，Pn，其中P1等待P2所占有的某一資源，P2等待P3所占有的某一源，.，而Pn等待P1所占有的的某一資源，形成一個(gè)進(jìn)程循環(huán)等待環(huán)。就像前面的過(guò)獨(dú)木橋問(wèn)題，甲等待乙占有的橋面，而乙又等待甲占有的橋面，從而彼此循環(huán)等待。n 上面我們提到的這四個(gè)條件在死鎖時(shí)會(huì)同時(shí)發(fā)生。也就是說(shuō)，只要有一個(gè)必要條件不滿足，則死鎖就可以排除。解決死鎖的對(duì)策1、設(shè)計(jì)

24、無(wú)死鎖的系統(tǒng)兩種途徑：預(yù)防死鎖、避免死鎖2、允許系統(tǒng)出現(xiàn)死鎖然后設(shè)法排除它加死鎖檢測(cè)手段-一旦發(fā)現(xiàn)死鎖能夠進(jìn)行排除的死鎖解除手段1、靜態(tài)分配資源策略 每個(gè)進(jìn)程在開(kāi)始執(zhí)行前就申請(qǐng)它所需要的全部資源，僅當(dāng)系統(tǒng)能滿足進(jìn)程的資源申請(qǐng)要求且把資源分配給進(jìn)程后，該進(jìn)程才能開(kāi)始執(zhí)行。（打破了（3）占有并申請(qǐng)） 特點(diǎn)：簡(jiǎn)單安全，資源利用率低2、按序分配資源策略 把系統(tǒng)中所有資源排一個(gè)順序，對(duì)第一個(gè)資源給一個(gè)確定的編號(hào)，規(guī)定任何一個(gè)進(jìn)程申請(qǐng)兩個(gè)以上資源時(shí)總是先申請(qǐng)編號(hào)小的資源，后申請(qǐng)編號(hào)大的資源。（打中4循環(huán)等待條件）循環(huán)等待條件） 特點(diǎn)：可以提高資源利用率，但資源的使用與實(shí)際使用順序不一致，給用戶編制程序帶來(lái)

25、麻煩。3、搶奪式分配資源策略 僅當(dāng)一個(gè)進(jìn)程已經(jīng)占有了某些資源又要申請(qǐng)新資源，而系統(tǒng)這時(shí)又不能滿足其他資源的要求（已被其他進(jìn)程占用）必須等待時(shí)，系統(tǒng)才可以搶奪該進(jìn)程已占有的資源。（適用于CPU、內(nèi)存，不能完全防止死鎖）1、系統(tǒng)的安全與不安全狀態(tài) 系統(tǒng)能按某種進(jìn)程順序(P1, P2, ，Pn)(稱P1, P2, , Pn序列為安全序列)，來(lái)為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都可順利地完成。如果系統(tǒng)無(wú)法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。只要系統(tǒng)處于安全狀態(tài)，系統(tǒng)就不會(huì)發(fā)生死鎖在系統(tǒng)處于不安全狀態(tài)下未必一定發(fā)生死鎖，但是安全狀態(tài)下的系統(tǒng)是一定不會(huì)發(fā)生

26、死鎖的。我們通過(guò)一個(gè)例子來(lái)說(shuō)明安全性。假定系統(tǒng)中有三個(gè)進(jìn)程P1、 P2和P3，共有12臺(tái)磁帶機(jī)。進(jìn)程P1總共要求10臺(tái)磁帶機(jī)，P2和P3分別要求4臺(tái)和9臺(tái)。假設(shè)在T0時(shí)刻，進(jìn)程P1、P2和P3已分別獲得5臺(tái)、2臺(tái)和2臺(tái)磁帶機(jī)，尚有3臺(tái)空閑未分配，如下表所示：進(jìn) 程 最 大 需 求 已 分 配 可 用 P1P2P310495223n由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換n 如果不按照安全序列分配資源，則系統(tǒng)可能會(huì)由安全狀態(tài)進(jìn)入不安全狀態(tài)。例如，在T0時(shí)刻以后，P3又請(qǐng)求1臺(tái)磁帶機(jī)，若此時(shí)系統(tǒng)把剩余3臺(tái)中的1臺(tái)分配給P3，則系統(tǒng)便進(jìn)入不安全狀態(tài)。 因?yàn)?，此時(shí)也無(wú)法再找到一個(gè)安全序

27、列， 例如，把其余的2臺(tái)分配給P2，這樣，在P2完成后只能釋放出4臺(tái)，既不能滿足P1尚需5臺(tái)的要求，也不能滿足P3尚需6臺(tái)的要求，致使它們都無(wú)法推進(jìn)到完成，彼此都在等待對(duì)方釋放資源，即陷入僵局，結(jié)果導(dǎo)致死鎖?，F(xiàn)有同類資源12個(gè)供3個(gè)進(jìn)程共享，假定進(jìn)程所需資源和已占資源的情況如下表所示。3個(gè)進(jìn)程在執(zhí)行中又都提出申請(qǐng)一個(gè)資源的要求，回答：na.如果先滿足進(jìn)程A的要求，系統(tǒng)將會(huì)出現(xiàn)什么現(xiàn)象？解釋之。 nb.你認(rèn)為應(yīng)按怎樣的次序分配資源才合適？為什么？ n答：a.在當(dāng)前狀態(tài)下，尚余2個(gè)資源可供分配，如果先滿足進(jìn)程A的要求，把其中1個(gè)資源分配給A進(jìn)程，此時(shí)A、B、C進(jìn)程仍未擁有足夠資源完成任務(wù)。系統(tǒng)進(jìn)入

28、不安全狀態(tài)，隨著進(jìn)程的繼續(xù)執(zhí)行，剩余的1個(gè)資源無(wú)論分給哪個(gè)進(jìn)程，均導(dǎo)至所有進(jìn)程進(jìn)入等告待而出現(xiàn)死鎖。nb.根據(jù)目前的資源占用情況，應(yīng)該先滿足B的要求，把剩下的2個(gè)資源分配給他，這樣，B進(jìn)程可執(zhí)行完畢歸還系統(tǒng)6個(gè)資源。這6個(gè)資源可以滿足A和C進(jìn)程的資源需求，從而使系統(tǒng)處于安全狀態(tài)。 2、利用銀行家算法避免死鎖、利用銀行家算法避免死鎖算法：把操作系統(tǒng)比作銀行家，操作系統(tǒng)管理的各種資源比作銀行的周轉(zhuǎn)資金，申請(qǐng)資源的進(jìn)程比作銀行借款的主顧。銀行家占有有限的資金，他不可能滿足所有借款人的請(qǐng)求，但可以滿足一部分人的借款請(qǐng)求，等這些人歸還后，又可把這筆資金借給其他人，其原則是不能使銀行家的錢(qián)被借完，使資金無(wú)

29、法周轉(zhuǎn)。特點(diǎn)：可避免死鎖，比靜態(tài)資源分配法資源利用率高 但資源分配保守，每次分配前均要花較長(zhǎng)時(shí)間計(jì)算時(shí)間，系統(tǒng)開(kāi)銷(xiāo)較大，而且必須知道每個(gè)進(jìn)程對(duì)資源的最大需求量。3、區(qū)分死鎖的避免與死鎖的防止預(yù)防：是在運(yùn)行之前，預(yù)先防止死鎖的產(chǎn)生（主要通過(guò)破壞產(chǎn)生死鎖的四個(gè)必要條件中任何一個(gè)來(lái)實(shí)現(xiàn)的）避免：是系統(tǒng)運(yùn)行過(guò)程中注意避免死鎖的發(fā)生（要求系統(tǒng)每當(dāng)在進(jìn)程申請(qǐng)資源時(shí)，都應(yīng)根據(jù)一定的算法判斷，僅當(dāng)系統(tǒng)處于安全狀態(tài)時(shí)才把資源分配給進(jìn)程，使系統(tǒng)一直處于安全狀態(tài)之中）四、死鎖的檢測(cè)和解除死鎖的檢測(cè)：系統(tǒng)定時(shí)運(yùn)行一個(gè)檢查程序，來(lái)檢測(cè)系統(tǒng)中是否存在死鎖，當(dāng)檢測(cè)到死鎖時(shí)再設(shè)法解除死鎖。1. 資源分配圖資源分配圖凡屬于凡屬

30、于E中的一個(gè)邊中的一個(gè)邊eE，都連接，都連接著著P中的一個(gè)結(jié)點(diǎn)和中的一個(gè)結(jié)點(diǎn)和R中的一個(gè)結(jié)中的一個(gè)結(jié)點(diǎn)，點(diǎn)，e=pi, rj是資源請(qǐng)求邊，由進(jìn)是資源請(qǐng)求邊，由進(jìn)程程pi指向資源指向資源rj， 它表示進(jìn)程它表示進(jìn)程pi請(qǐng)請(qǐng)求一個(gè)單位的求一個(gè)單位的rj資源。資源。e=rj, pi是是資源分配邊，由資源資源分配邊，由資源rj指向進(jìn)程指向進(jìn)程pi, 它表示把一個(gè)單位的資源它表示把一個(gè)單位的資源rj分配給分配給進(jìn)程進(jìn)程pi。2、利用資源圖可以檢測(cè)系統(tǒng)中是否存在死鎖進(jìn)程，判定死鎖的法則、利用資源圖可以檢測(cè)系統(tǒng)中是否存在死鎖進(jìn)程，判定死鎖的法則如下：如下：1）如果進(jìn)程資源圖中無(wú)環(huán)路，則此時(shí)系統(tǒng)內(nèi)不存在死鎖。

31、2）如果進(jìn)程資源圖中有環(huán)路，且處于環(huán)路內(nèi)的每類資源均只有一個(gè)，則此時(shí)系統(tǒng)內(nèi)存在死鎖；處于環(huán)路內(nèi)的進(jìn)程就是卷入死鎖的進(jìn)程。3）如果進(jìn)程資源圖中有環(huán)路，但處于環(huán)路內(nèi)的每類資源個(gè)數(shù)不全為一個(gè)，則此時(shí)系統(tǒng)內(nèi)是否存在死鎖，還要化簡(jiǎn)進(jìn)程資源圖才能判定。3、進(jìn)程資源的化簡(jiǎn)過(guò)程、進(jìn)程資源的化簡(jiǎn)過(guò)程1）找出一個(gè)既不阻塞又非孤立的進(jìn)程節(jié)點(diǎn)Pi2）進(jìn)程Pi所占有的資源全部釋放時(shí)，可喚醒等待此資源而進(jìn)入阻塞的進(jìn)程Pj，使原來(lái)處于阻塞的進(jìn)程可能變成非阻塞進(jìn)程。3）若進(jìn)程資源狀態(tài)圖通過(guò)上述簡(jiǎn)化步驟后，都成為孤立點(diǎn)，則該圖是可完全化簡(jiǎn)的，并且該進(jìn)程資源圖所代表的系統(tǒng)狀態(tài)是安全的。4、死鎖定理對(duì)于較復(fù)雜的資源狀態(tài)圖可能存在著

32、多個(gè)非阻塞點(diǎn)，若我們從不同的點(diǎn)開(kāi)始化簡(jiǎn)是否可以得到同一個(gè)化簡(jiǎn)圖呢？經(jīng)證明：一個(gè)給定的進(jìn)程資源圖的所有化簡(jiǎn)順序?qū)?dǎo)致同一個(gè)不可化簡(jiǎn)圖。所以我們進(jìn)一步可得到如下的死鎖定理：若S是死鎖狀態(tài)的話，當(dāng)且僅當(dāng)S的進(jìn)程資源圖是不可完全化簡(jiǎn)的。如果得到一個(gè)可完全化簡(jiǎn)的進(jìn)程資源狀態(tài)圖，我們就稱該狀態(tài)為安全態(tài)，反之為死鎖狀態(tài)。3、死鎖的解除當(dāng)死鎖檢測(cè)程序檢測(cè)到有死鎖存在時(shí)，一般采用兩種方式來(lái)解除死鎖。1）刪除法：即終止一個(gè)或幾個(gè)涉及死鎖的進(jìn)程的執(zhí)行，收回它們所占的資源進(jìn)程再分配，以破壞循環(huán)等2）剝奪法：即從涉及死鎖的一個(gè)或幾個(gè)進(jìn)程中搶奪資源，把奪來(lái)的資源再分配給卷入死鎖的其他進(jìn)程，直至死鎖解除11.某系統(tǒng)中有10臺(tái)打印機(jī)，有三個(gè)進(jìn)程P1，P2，P3分別需要8臺(tái)，7臺(tái)和4臺(tái)。若P1，P2，P3已申請(qǐng)到4臺(tái)，2臺(tái)和2臺(tái)。試問(wèn)：按銀行家算法能安全分配嗎？請(qǐng)說(shuō)明分配過(guò)程。 系統(tǒng)能為進(jìn)程P3分配二臺(tái)打印機(jī)。因?yàn)楸M管此時(shí)10臺(tái)打印機(jī)已分配給進(jìn)程P1 4臺(tái)，P2 2臺(tái)和P3 4臺(tái)，全部分配