自考操作系統(tǒng)概論-

1、第二章 處理器管理2.1 多道程序設(shè)計(jì)首先描述程序的順序和并發(fā)執(zhí)行方式2.1.1 程序的順序執(zhí)行 一個(gè)程序由假設(shè)干個(gè)程序段組成，而這些程序段的執(zhí)行必須是順序的，這種程序執(zhí)行的方式就稱為程序的順序執(zhí)行。2.1.1 程序的順序執(zhí)行例：討論單道系統(tǒng)的工作情況 對(duì)用戶作業(yè)的處理 首先輸入用戶的程序和數(shù)據(jù) 然后進(jìn)行計(jì)算 最后打印計(jì)算結(jié)果 即有三個(gè)順序執(zhí)行的操作 I：輸入操作 C：計(jì)算操作 P：輸出操作P2C2 I2P1C1 I1輸入機(jī)CPU打印機(jī)2.1 多道程序設(shè)計(jì)2.1.2 程序的并發(fā)執(zhí)行程序的并發(fā)執(zhí)行例： 在系統(tǒng)中有n個(gè)作業(yè)，每個(gè)作業(yè)都有三個(gè)處理步驟，輸入數(shù)據(jù)、處理、輸出，即Ii,Ci,Pi (i=

2、1,2,3,.,n)。 這些作業(yè)系統(tǒng)中執(zhí)行時(shí)是對(duì)時(shí)間的偏序，有些操作必須在其它操作之前執(zhí)行，這是有序的，但有些操作是可以同時(shí)執(zhí)行的。2.1.2 程序的并發(fā)執(zhí)行 I1 I2 I3 I4C1C3C2P1P2例如: I1、C1、P1的執(zhí)行必須嚴(yán)格按照I1，C1，P1的順序，而P1與I2，C1與I2，I3與P1是可以同時(shí)執(zhí)行的。.2.1.3 多道程序設(shè)計(jì)P152.2 進(jìn)程的概念 操作系統(tǒng)的特性之一是并發(fā)與共享，即在系統(tǒng)中內(nèi)存同時(shí)存在幾個(gè)相互獨(dú)立的程序，這些程序在系統(tǒng)中既交叉地運(yùn)行，又要共享系統(tǒng)中的資源，這就會(huì)引起一系列的問(wèn)題，包括：對(duì)資源的競(jìng)爭(zhēng)、運(yùn)行程序之間的通信、程序之間的合作與協(xié)同等符。 要解決這

3、些問(wèn)題，用程序的概念已經(jīng)不能描述程序在內(nèi)存中運(yùn)行的狀態(tài)，必須引入新的概念進(jìn)程2.2.1 進(jìn)程的定義行為的一個(gè)規(guī)那么叫做程序，程序在處理機(jī)上執(zhí)行時(shí)所發(fā)生的活動(dòng)稱為進(jìn)程Dijkstra)。進(jìn)程是這樣的計(jì)算局部，它是可以和其它計(jì)算并行的一個(gè)計(jì)算。(Donovan)進(jìn)程有時(shí)稱為任務(wù)是一個(gè)程序與其數(shù)據(jù)一道通過(guò)處理機(jī)的執(zhí)行所發(fā)生的活動(dòng)。Alan.C. Shaw)進(jìn)程是執(zhí)行中的程序。Ken Thompson and Dennis Ritchie )進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過(guò)程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。 進(jìn)程的定義：把一個(gè)程序在一個(gè)數(shù)據(jù)集上的一次執(zhí)行 稱為一個(gè)進(jìn)程process)。2.2.2 為什

4、么要引入進(jìn)程提高資源利用率正確描述程序的執(zhí)行情況2.2.3 進(jìn)程的屬性1.進(jìn)程是動(dòng)態(tài)的，它包含了數(shù)據(jù)和運(yùn)行在數(shù)據(jù)集上的程序2.多個(gè)進(jìn)程可以含有相同的程序3.多個(gè)進(jìn)程可以并發(fā)執(zhí)行4.進(jìn)程有三種根本狀態(tài)2.2.3 進(jìn)程的屬性4. 進(jìn)程的三種根本狀態(tài)(1)就緒狀態(tài)(Ready) 進(jìn)程已獲得除CPU之外的所有必需的資源，一旦得到CPU控制權(quán)，立即可以運(yùn)行。(2)運(yùn)行狀態(tài)(Running) 該進(jìn)程已獲得運(yùn)行所必需的資源，它的程序正在處理機(jī)上執(zhí)行。 (3)等待阻塞狀態(tài)(Waiting,Blocked) 正在執(zhí)行的進(jìn)程由于發(fā)生某事件而暫時(shí)無(wú)法執(zhí)行時(shí)，便放棄處理機(jī)而處于暫停狀態(tài)，那么稱該進(jìn)程處于阻塞狀態(tài)或等待

5、狀態(tài)。就緒隊(duì)列與阻塞隊(duì)列2.2.3 進(jìn)程的屬性執(zhí) 行阻 塞就 緒時(shí)間片完I/O請(qǐng)求進(jìn)程調(diào)度I/O完成進(jìn)程的三種根本狀態(tài)以及各狀態(tài)之間的轉(zhuǎn)換關(guān)系2.2.3 進(jìn)程的屬性進(jìn)程的特征進(jìn)程的特征CPB據(jù)數(shù)段程序段進(jìn)程實(shí)體動(dòng)態(tài)性-最根本特征進(jìn)程：進(jìn)程實(shí)體的一次執(zhí)行過(guò)程，有生命周期。程序：程序是一組有序指令的集合，是靜態(tài)的概念。 并發(fā)性異步性多個(gè)進(jìn)程實(shí)體同存于內(nèi)存中，在一段時(shí)間內(nèi)同時(shí)運(yùn)行 程序不能并發(fā)執(zhí)行進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)2.3 進(jìn)程控制塊1. 進(jìn)程控制塊的作用 存放進(jìn)程的管理和控制信息的數(shù)據(jù)結(jié)構(gòu)稱為進(jìn)程控制塊。它是進(jìn)程管理和控制的最重要的數(shù)據(jù)結(jié)構(gòu)，在創(chuàng)立時(shí)，建立PCB，并伴隨進(jìn)程運(yùn)行

6、的全過(guò)程，直到進(jìn)程撤消而撤消。PCB就象我們的戶口。 進(jìn)程控制塊是進(jìn)程存在的唯一標(biāo)志。 系統(tǒng)的所有PCB組織成鏈表或隊(duì)列，常駐內(nèi)存的PCB區(qū)。2.3 進(jìn)程控制塊2. 進(jìn)程控制塊中的信息1) 進(jìn)程標(biāo)示符 每個(gè)進(jìn)程都必須有一個(gè)唯一的標(biāo)識(shí)符內(nèi)部標(biāo)示符外部標(biāo)示符2) 處理機(jī)狀態(tài) 處理機(jī)狀態(tài)信息主要由處理機(jī)的各種存放器中的內(nèi)容組成。處理機(jī)運(yùn)行時(shí)的信息存放在存放器中，當(dāng)被中斷時(shí)這些信息要存放在PCB中。唯一的數(shù)字標(biāo)識(shí)符用戶（進(jìn)程）訪問(wèn)該進(jìn)程使用通用存放器 指令計(jì)數(shù)器程序狀態(tài)字PSW 用戶棧指針2.3 進(jìn)程控制塊3) 進(jìn)程調(diào)度信息進(jìn)程狀態(tài)進(jìn)程優(yōu)先級(jí)進(jìn)程調(diào)度所需的其他信息事件4) 進(jìn)程控制信息程序和數(shù)據(jù)的地址

7、進(jìn)程通信和同步機(jī)制資源清單鏈接指針進(jìn)程控制P21 對(duì)系統(tǒng)中的全部進(jìn)程實(shí)施有效的管理，負(fù)責(zé)進(jìn)程狀態(tài)的改變。進(jìn)程的創(chuàng)立1. 進(jìn)程圖 描述進(jìn)程的家族關(guān)系的有向樹(shù) 進(jìn)程Pi創(chuàng)立了進(jìn)程Pj，那么Pi是Pj的父進(jìn)程， Pj是Pi的子進(jìn)程，用一條由進(jìn)程Pi指向進(jìn)程Pj的有向邊來(lái)描述。 創(chuàng)立父進(jìn)程的進(jìn)程為祖進(jìn)程，由此形成進(jìn)程樹(shù)，樹(shù)根為進(jìn)程家族的祖先。ABDKEFLMJIHGC內(nèi)核完成進(jìn)程控制2. 引起創(chuàng)立進(jìn)程的事件3. 進(jìn)程的創(chuàng)立用戶登錄提供服務(wù)作業(yè)調(diào)度應(yīng)用請(qǐng)求在多道程序環(huán)境中，只有進(jìn)程才能在系統(tǒng)中運(yùn)行。操作系統(tǒng)發(fā)現(xiàn)要求創(chuàng)立新進(jìn)程的事件后，調(diào)用進(jìn)程創(chuàng)立原語(yǔ)Creat()創(chuàng)立新進(jìn)程。創(chuàng)立過(guò)程(1) 申請(qǐng)空白PC

8、B(2) 為新進(jìn)程分配資源(3) 初始化進(jìn)程控制塊(4) 將新進(jìn)程插入就緒隊(duì)列進(jìn)程控制進(jìn)程的撤銷1. 引起進(jìn)程終止的事件正常結(jié)束異常結(jié)束外界干預(yù)越界錯(cuò)誤、保護(hù)錯(cuò)、非法指令、特權(quán)指令錯(cuò)、運(yùn)行超時(shí)、等待超時(shí)、算術(shù)運(yùn)算錯(cuò)、I/O故障操作員或操作系統(tǒng)干預(yù)父進(jìn)程請(qǐng)求父進(jìn)程中止2. 進(jìn)程的終止過(guò)程(1) 根據(jù)被終止進(jìn)程的標(biāo)示符，從PCB集合中檢索出該進(jìn)程的PCB，從中讀出該進(jìn)程的狀態(tài)。(2) 假設(shè)被終止進(jìn)程正處于執(zhí)行狀態(tài)，應(yīng)立即終止該進(jìn)程的執(zhí)行，置調(diào)度標(biāo)志為真，用于指示該進(jìn)程被終止后應(yīng)重新進(jìn)行調(diào)度。(3) 假設(shè)該進(jìn)程有子孫進(jìn)程，應(yīng)將其所有子孫進(jìn)程予以終止，以防他們成為不可控的進(jìn)程。(4) 將被終止進(jìn)程所擁

9、有的全部資源，或歸還其父進(jìn)程，或歸還系統(tǒng)。(5) 將被終止進(jìn)程的PCB從所在隊(duì)列或鏈表中移出，等待其他程序搜索信息。進(jìn)程控制進(jìn)程的阻塞與喚醒1. 引起進(jìn)程阻塞和喚醒的事件1) 請(qǐng)求系統(tǒng)服務(wù)2) 啟動(dòng)某種操作3) 新數(shù)據(jù)尚未到達(dá)4) 無(wú)新工作可做2. 進(jìn)程阻塞過(guò)程調(diào)用阻塞原語(yǔ)BLOCK()阻塞自己中止調(diào)用進(jìn)程的執(zhí)行，將PCB中的狀態(tài)改為阻塞，并參加到阻塞隊(duì)列中；最后轉(zhuǎn)進(jìn)程調(diào)度。3. 進(jìn)程喚醒過(guò)程阻塞進(jìn)程等待的事件發(fā)生，有關(guān)進(jìn)程調(diào)用喚醒原語(yǔ)WAKEUP()把等待該事件的進(jìn)程喚醒。 喚醒原語(yǔ)的執(zhí)行：把阻塞進(jìn)程從等待該事件的阻塞隊(duì)列中移出，將其PCB中的現(xiàn)行狀態(tài)改為就緒，將PCB插入到就緒隊(duì)列中阻塞原

10、語(yǔ)與喚醒原語(yǔ)作用相反，成對(duì)使用2.4 進(jìn)程隊(duì)列進(jìn)程控制塊的組織方式1) 鏈接方式把具有統(tǒng)一狀態(tài)的PCB用其中的鏈接字鏈接成一個(gè)隊(duì)列。就緒隊(duì)列 假設(shè)干個(gè)阻塞隊(duì)列 空白隊(duì)列 2) 索引方式系統(tǒng)根據(jù)所有進(jìn)程的狀態(tài)建立幾張索引表，把各表的內(nèi)存首地址記錄在內(nèi)存的專用單元中。索引表的表目中記錄了相應(yīng)狀態(tài)的某個(gè)PCB在PCB表中的地址。 1 PCB9 0 PCB8 9 PCB7 7 PCB6 PCB5 8 PCB4 0 PCB3 3 PCB2 4 PCB1就緒隊(duì)列指針阻塞隊(duì)列指針空閑隊(duì)列指針執(zhí)行指針鏈接方式：PCB7PCB6PCB5PCB4PCB3PCB2PCB1執(zhí)行指針就緒表指針阻塞表指針就緒索引表阻塞索

11、引表索引方式：2.5 中斷和中斷處理2.5.1 中斷2.5.2 中斷類型中斷響應(yīng)中斷處理2.5.1 中斷由于某些事件的出現(xiàn)，中止現(xiàn)行進(jìn)程的運(yùn)行，而由操作系統(tǒng)去處理出現(xiàn)的事件，待適當(dāng)?shù)臅r(shí)候讓被中止的進(jìn)程繼續(xù)運(yùn)行，這個(gè)過(guò)程稱為中斷。引起中斷的事件稱為中斷源。對(duì)出現(xiàn)的事件進(jìn)行處理的程序稱為中斷處理程序。2.5.2 中斷類型1硬件故障中斷2程序中斷3外部中斷4輸入/輸出中斷5訪管中斷強(qiáng)迫性中斷事件自愿性中斷事件中斷響應(yīng)P24硬件故障中斷程序中斷外部事件輸入/輸出事件訪管中斷事件當(dāng)前PSW舊 PSW硬件故障中斷程序中斷外部事件輸入/輸出事件訪管中斷事件新 PSW中斷處理P251硬件故障中斷事件的處理-?

12、人工干預(yù)，輸出故障信息。2程序中斷事件的處理-?轉(zhuǎn)交用戶自行處理3外部中斷事件的處理-?例行程序4輸入/輸出中斷事件的處理-?IO正常結(jié)束、IO異常結(jié)束5訪管中斷事件的處理-?系統(tǒng)功能調(diào)用2.6 處理器調(diào)度P26在多道程序環(huán)境下，進(jìn)程數(shù)目往往多于處理機(jī)數(shù)目。這就要求系統(tǒng)能夠按某種算法，動(dòng)態(tài)的把處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)程，使之執(zhí)行。分配處理機(jī)的任務(wù)是由處理機(jī)調(diào)度程序完成的。由于處理機(jī)是最重要的計(jì)算機(jī)資源，提高處理機(jī)的利用率及改善系統(tǒng)性能，在很大程度上取決于處理機(jī)調(diào)度的性能。因此，處理機(jī)調(diào)度便成為OS設(shè)計(jì)的中心問(wèn)題之一。高級(jí)、中級(jí)和低級(jí)調(diào)度 一個(gè)批處理型作業(yè)，從進(jìn)入系統(tǒng)并駐留在外存的后備隊(duì)列

13、上開(kāi)始，直至作業(yè)運(yùn)行完畢，可能要經(jīng)歷下述三級(jí)調(diào)度。高級(jí)調(diào)度High Scheduling 又稱為作業(yè)調(diào)度或長(zhǎng)程調(diào)度Long-Term Scheduling，用于決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)立進(jìn)程、分配必要的資源，然后，再將新創(chuàng)立的進(jìn)程排在就緒隊(duì)列上，準(zhǔn)備執(zhí)行。因此有時(shí)也稱作業(yè)調(diào)度為接納調(diào)度Admission Scheduling。高級(jí)調(diào)度High Scheduling作業(yè)作業(yè)步典型的作業(yè)可分成三個(gè)作業(yè)步：編譯-鏈接裝配-運(yùn)行作業(yè)流后備隊(duì)列作業(yè)控制塊JCB(job control block)高級(jí)調(diào)度High Scheduling 在批處理系統(tǒng)中，因作業(yè)進(jìn)入系統(tǒng)后先駐

14、留在外存，故需要有作業(yè)調(diào)度。在分時(shí)系統(tǒng)中為做到及時(shí)響應(yīng)，作業(yè)被直接送入內(nèi)存，故不需作業(yè)調(diào)度。在實(shí)時(shí)系統(tǒng)中，通常也不需作業(yè)調(diào)度。高級(jí)調(diào)度作業(yè)調(diào)度在每次執(zhí)行作業(yè)調(diào)度時(shí)，都須作出兩個(gè)決定：接納多少作業(yè)每次接納多少作業(yè)進(jìn)入內(nèi)存，取決于多道程序度，即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行。多道程序度確實(shí)定應(yīng)根據(jù)系統(tǒng)的規(guī)模和運(yùn)行速度等情況綜合考慮。接納哪些作業(yè)應(yīng)接納哪些作業(yè)從外存調(diào)入內(nèi)存，取決于所采用的調(diào)度算法。如先來(lái)先效勞，短作業(yè)優(yōu)先等。低級(jí)調(diào)度Low Level Scheduling 通常也稱為進(jìn)程調(diào)度或短程調(diào)度Short-Term Scheduling，用來(lái)決定就緒隊(duì)列中的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)，然后再由分派

15、程序把處理機(jī)分配給該進(jìn)程。進(jìn)程調(diào)度是最根本的一種調(diào)度，在三種OS中都有。低級(jí)調(diào)度的功能1保存處理機(jī)的現(xiàn)場(chǎng)信息。2按某種算法選取進(jìn)程3把處理器分配給進(jìn)程進(jìn)程調(diào)度的三個(gè)根本機(jī)制1排隊(duì)器2分派器分派程序3上下文切換機(jī)制低級(jí)調(diào)度Low Level Scheduling搶占方式Preemptive Mode 這種調(diào)度方式允許調(diào)度程序根據(jù)某種原那么，去暫停某個(gè)正在執(zhí)行的進(jìn)程，將以分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。搶占的原那么有：優(yōu)先權(quán)原那么。優(yōu)先權(quán)高的可以搶占優(yōu)先級(jí)低的進(jìn)程的處理機(jī)。短作業(yè)進(jìn)程優(yōu)先原那么。短作業(yè)進(jìn)程可以搶占長(zhǎng)作業(yè)進(jìn)程的處理機(jī)。時(shí)間片原那么。各進(jìn)程按時(shí)間片運(yùn)行，一個(gè)時(shí)間片用完時(shí)，停止該

16、進(jìn)程執(zhí)行重新進(jìn)行調(diào)度。中級(jí)調(diào)度Intermediate-Level Scheduling 中級(jí)調(diào)度又稱中程調(diào)度Medium-Term Scheduling引入中級(jí)調(diào)度的目的，是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。為此，應(yīng)使那些暫時(shí)不能運(yùn)行的進(jìn)程不再占用珍貴的內(nèi)存資源，而將它們調(diào)之外存去等待，把此時(shí)的進(jìn)程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當(dāng)這些進(jìn)程重又具備運(yùn)行條件、且內(nèi)存又稍有空閑時(shí)，由中級(jí)調(diào)度來(lái)決定把外存上的哪些又具備運(yùn)行條件的就緒進(jìn)程，重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上等待進(jìn)程調(diào)度。中級(jí)調(diào)度實(shí)際上就是存儲(chǔ)器管理中的對(duì)換功能。具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型 在批處理系統(tǒng)中，不僅

17、需要進(jìn)程調(diào)度，而且還需要作業(yè)調(diào)度，由后者按一定的作業(yè)調(diào)度算法，從外存的后備隊(duì)列中選擇一批作業(yè)調(diào)入內(nèi)存，并為它們建立進(jìn)程，送入就緒隊(duì)列，然后才由進(jìn)程調(diào)度算法按照一定的進(jìn)程調(diào)度算法，選擇一個(gè)進(jìn)程，把處理機(jī)分配給該進(jìn)程。以下圖示出具有高、低兩級(jí)調(diào)度的調(diào)度隊(duì)列模型。具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型CPU就 緒 隊(duì) 列時(shí)間片完進(jìn)程調(diào)度等待事件1進(jìn)程完成后備隊(duì)列等待事件2等待事件n事件1出現(xiàn)事件2出現(xiàn)事件n出現(xiàn)作業(yè)調(diào)度具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型 具有上下兩級(jí)調(diào)度的調(diào)度模型與僅有進(jìn)程調(diào)度的調(diào)度模型的主要區(qū)別在于：就緒隊(duì)列的形式。在批處理系統(tǒng)中，最常用的是最高優(yōu)先權(quán)優(yōu)先調(diào)度算法，因此最常用的就緒隊(duì)列形式

18、是優(yōu)先權(quán)隊(duì)列。設(shè)置多個(gè)阻塞隊(duì)列。對(duì)于小型系統(tǒng)可只設(shè)置一個(gè)，但對(duì)于較大系統(tǒng)要設(shè)置多個(gè)阻塞隊(duì)列以保證效率。每個(gè)隊(duì)列對(duì)應(yīng)于某一種進(jìn)程阻塞事件。2.6.1 處理器的兩級(jí)調(diào)度P26作業(yè)調(diào)度進(jìn)程調(diào)度2.6.2 作業(yè)調(diào)度算法設(shè)計(jì)調(diào)度算法的原那么：公平性平衡資源使用極大地流量選擇調(diào)度方式和調(diào)度算法的假設(shè)干準(zhǔn)那么 在一個(gè)OS的設(shè)計(jì)中，應(yīng)如何選擇調(diào)度方式和算法，很大程度上取決于OS的類型和目標(biāo)。如在批處理系統(tǒng)、分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)中，通常都采用不同的調(diào)度方式和算法。選擇的準(zhǔn)那么，有的是面向用戶的，有的是面向系統(tǒng)的。面向用戶的準(zhǔn)那么周轉(zhuǎn)時(shí)間短 周轉(zhuǎn)時(shí)間 平均周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 平均帶權(quán)周轉(zhuǎn)時(shí)間響應(yīng)時(shí)間快 響應(yīng)時(shí)間

19、截止時(shí)間的保證 截止時(shí)間優(yōu)先權(quán)準(zhǔn)那么評(píng)價(jià)批處理系統(tǒng)的性能、選擇作業(yè)調(diào)度方式與算法的重要準(zhǔn)那么之一。從作業(yè)被提交給系統(tǒng)開(kāi)始，到作業(yè)完成為止的這段時(shí)間間隔。作業(yè)的周轉(zhuǎn)時(shí)間與系統(tǒng)為他提供效勞的時(shí)間之比評(píng)價(jià)分時(shí)系統(tǒng)的性能、選擇進(jìn)程調(diào)度算法的重要準(zhǔn)那么之一。提交請(qǐng)求到顯示結(jié)果評(píng)價(jià)實(shí)時(shí)系統(tǒng)的性能、選擇實(shí)時(shí)調(diào)度算法的重要準(zhǔn)那么。面向系統(tǒng)的準(zhǔn)那么系統(tǒng)吞吐量高處理機(jī)利用率好各類資源的平衡利用評(píng)價(jià)批處理系統(tǒng)的性能的另一個(gè)重要指標(biāo)、選擇批處理作業(yè)調(diào)度的重要準(zhǔn)那么。單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)衡量系統(tǒng)性能的十分重要的指標(biāo)1、先來(lái)先效勞算法 FCFS是一種最簡(jiǎn)單的調(diào)度算法。當(dāng)在作業(yè)調(diào)度中采用該算法時(shí)，每次調(diào)度都是從后備

20、作業(yè)隊(duì)列中，選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)立進(jìn)程，然后放入就緒隊(duì)列。先來(lái)先效勞算法例題P28作業(yè)名進(jìn)入輸入井時(shí)間需計(jì)算時(shí)間主存量要求A10.1時(shí)42分鐘15KB10.3時(shí)30分鐘60KC10.5時(shí)24分鐘50KD10.6時(shí)24分鐘10KE10.7時(shí)12分鐘20K主存空間為100K作業(yè)名裝入主存時(shí)間開(kāi)始執(zhí)行時(shí)間執(zhí)行結(jié)束時(shí)間周轉(zhuǎn)時(shí)間A10.1時(shí)10.1時(shí)10.8時(shí)0.7小時(shí)B10.3時(shí)10.8時(shí)11.3時(shí)1.0小時(shí)C11.3時(shí)11.7時(shí)12.1時(shí)1.6小時(shí)D10.6時(shí)11.3時(shí)11.7時(shí)1.1小時(shí)E11.3時(shí)12.1時(shí)12.3時(shí)1.6小時(shí)先來(lái)先效勞算法平均周

21、轉(zhuǎn)時(shí)間=1.2作業(yè)名進(jìn)入輸入井時(shí)間需計(jì)算時(shí)間主存量要求A10.1時(shí)42分鐘15KB10.3時(shí)30分鐘60KC10.5時(shí)24分鐘50KD10.6時(shí)24分鐘10KE10.7時(shí)12分鐘20K2、計(jì)算時(shí)間短的作業(yè)優(yōu)先算法短作業(yè)優(yōu)先SJF的調(diào)度算法，是從后備隊(duì)列中選擇一個(gè)或假設(shè)干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。進(jìn)程調(diào)度仍按裝入的次序讓它們依次占用處理器。作業(yè)名裝入主存時(shí)間開(kāi)始執(zhí)行時(shí)間執(zhí)行結(jié)束時(shí)間周轉(zhuǎn)時(shí)間A10.1時(shí)10.1時(shí)10.8時(shí)0.7小時(shí)B10.3時(shí)10.8時(shí)11.3時(shí)1.0小時(shí)C11.3時(shí)11.9時(shí)12.3時(shí)1.8小時(shí)D10.6時(shí)11.3時(shí)11.7時(shí)1.1小時(shí)E11.3時(shí)11.7時(shí)

22、11.9時(shí)1.2小時(shí)計(jì)算時(shí)間短作業(yè)優(yōu)先算法平均周轉(zhuǎn)時(shí)間=1.16作業(yè)名進(jìn)入輸入井時(shí)間需計(jì)算時(shí)間主存量要求A10.1時(shí)42分鐘15KB10.3時(shí)30分鐘60KC10.5時(shí)24分鐘50KD10.6時(shí)24分鐘10KE10.7時(shí)12分鐘20KP30SJF調(diào)度算法的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：有效降低作業(yè)的平均等待時(shí)間，提高系統(tǒng)吞吐量。缺點(diǎn)：1.對(duì)長(zhǎng)作業(yè)不利。2.該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)進(jìn)程會(huì)被及時(shí)處理。3.由于作業(yè)進(jìn)程的長(zhǎng)短含主觀因素，不一定能真正做到短作業(yè)優(yōu)先。3、響應(yīng)比高者優(yōu)先算法響應(yīng)比=等待時(shí)間、計(jì)算時(shí)間調(diào)度在全部作業(yè)到達(dá)輸入井之后開(kāi)始作業(yè)名進(jìn)入輸入井時(shí)間需計(jì)算時(shí)間A8：501.

23、5小時(shí)B9：000.4小時(shí)C9：301.0小時(shí)時(shí)間A響應(yīng)比B響應(yīng)比C響應(yīng)比9:3040/9030/240/609：5464/9024/604、 優(yōu)先級(jí)調(diào)度算法確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下三個(gè)方面：進(jìn)程類型：一般來(lái)說(shuō)系統(tǒng)進(jìn)程高于用戶進(jìn)程。進(jìn)程對(duì)資源的需求：如進(jìn)程的估計(jì)時(shí)間及內(nèi)存需要量的多少，對(duì)要求少的進(jìn)程賦予較高優(yōu)先權(quán)。用戶要求：由用戶進(jìn)程的緊迫程度及用戶所付費(fèi)用的多少來(lái)確定優(yōu)先權(quán)的。5、均衡調(diào)度算法P31)2.6 進(jìn)程調(diào)度算法P31)引起進(jìn)程切換的原因：1一個(gè)進(jìn)程從運(yùn)行狀態(tài)變成等待狀態(tài)2一個(gè)進(jìn)程從運(yùn)行狀態(tài)變成就緒狀態(tài)3一個(gè)進(jìn)程從等待狀態(tài)變成就緒狀態(tài)4一個(gè)進(jìn)程完成工作后撤銷調(diào)度算法： P31-32

24、1 先來(lái)先效勞調(diào)度算法2 最高優(yōu)先級(jí)優(yōu)先調(diào)度算法3 時(shí)間片輪轉(zhuǎn)調(diào)度算法調(diào)度算法例題在單CPU和兩臺(tái)輸入/輸出設(shè)備I1,I2)的多道程序設(shè)計(jì)環(huán)境下，同時(shí)投入3個(gè)作業(yè)JOB1,JOB2,JOB3運(yùn)行。這3個(gè)作業(yè)對(duì)CPU和輸入/輸出設(shè)備的使用順序和時(shí)間如下所示：JOB1:I2(30ms);CPU(10ms);I1(30ms);CPU(10ms);I2(20ms)JOB2:I1(20ms);CPU(20ms);I2(40ms)JOB3:CPU(30ms);I1(20ms);CPU(10ms);I1(10ms)假定CPU，I1，I2都能并行工作，JOB1優(yōu)先級(jí)最高，JOB2次之，JOB3優(yōu)先級(jí)最低，優(yōu)先級(jí)高的作業(yè)可以搶占優(yōu)先級(jí)低的作業(yè)的CPU但不搶占I1和I2。試求：13個(gè)作業(yè)從投入到完成分別需要的時(shí)間；2從投入到完成的CPU的利用率；3I/O設(shè)備利用率。調(diào)度算法例題JOB1從投入到運(yùn)行完成需要110ms, JOB2從投入到運(yùn)行完成需要90ms, JOB3從投入到運(yùn)行完成需要110ms.Cpu利用率： 110-30/110=72.7%I1的利用率： 110-30/110=72.7%I2的利用率： 110-20/110=81