第2章處理器管理課件

1、第二章 處理器管理計(jì)算機(jī)系統(tǒng)中，最寶貴的資源是CPU。為了提高它的利用率，需要引入多道程序設(shè)計(jì)的概念。12.1 多道程序設(shè)計(jì)2.1.1 程序的順序執(zhí)行程序：是一個(gè)在時(shí)間上嚴(yán)格有序的指令集合。一個(gè)計(jì)算問題往往按照一定的順序執(zhí)行，執(zhí)行的順序由編制的程序確定。輸入數(shù)據(jù)處 理輸出結(jié)果23例 如：423輸出342處理354輸入數(shù)據(jù)三數(shù)據(jù)二數(shù)據(jù)一數(shù)據(jù)過程4程序的順序執(zhí)行，資源利用率低t數(shù)據(jù)三數(shù)據(jù)二數(shù)據(jù)一0469141820232630程序的順序執(zhí)行圖黑線：表示輸入紅線：表示處理灰線：表示輸出52.1.2 程序的并行執(zhí)行tt1t2數(shù)據(jù)1數(shù)據(jù)2數(shù)據(jù)3t3t46423輸出342處理354輸入數(shù)據(jù)三數(shù)據(jù)二數(shù)據(jù)一t

2、0469131215162072.1.3 多道程序設(shè)計(jì) 多道程序設(shè)計(jì)：讓多個(gè)程序（作業(yè)）同時(shí)進(jìn)入主存儲(chǔ)器并行執(zhí)行8在多道程序設(shè)計(jì)環(huán)境下，系統(tǒng)具有如下特點(diǎn)：資源利用率高系統(tǒng)吞吐量大 程序間制約性t046913121516209 舉例說明：有A、B兩個(gè)任務(wù)需要計(jì)算機(jī)完成，各自流程：A: 計(jì)算50ms ，打印100ms，再計(jì)算50ms打印100ms結(jié)束B: 計(jì)算50ms，輸入數(shù)據(jù)80ms，再計(jì)算100ms，打印100ms結(jié)束0tBA50150200300350430530630CPU利用率=250/630*100%=39.7%0tBA5015010018020030040010 多道程序設(shè)計(jì)環(huán)境：內(nèi)

3、存中允許有多個(gè)程序存在，它們輪流地使用著CPU。11執(zhí)行的并發(fā)性：從宏觀上看，同時(shí)在內(nèi)存的多個(gè)程序都在執(zhí)行著，在按照自己程序規(guī)定的步驟向前推進(jìn)；從微觀上看，由于CPU在任何時(shí)刻只能執(zhí)行一個(gè)程序，因此這些程序輪流占用CPU，交替地執(zhí)行著。122009-44一個(gè)計(jì)算問題的程序分成三個(gè)可以獨(dú)立執(zhí)行的程序模塊：輸入程序、處理程序和打印程序，每一批數(shù)據(jù)都需順序被這些模塊執(zhí)行。當(dāng)有多批數(shù)據(jù)時(shí)，這三個(gè)程序模塊中可以并行運(yùn)行的是（ ）A輸入程序、處理程序和打印程序B輸入程序和處理程序C處理程序和打印程序D打印程序和輸入程序A132010-4 5.多道程序設(shè)計(jì)的意義是（）A.允許多個(gè)作業(yè)同時(shí)入駐主存儲(chǔ)器，中央處

4、理器輪流執(zhí)行各個(gè)作業(yè)，各個(gè)作業(yè)有可能同時(shí)使用所需的外圍設(shè)備B.允許多個(gè)作業(yè)輪流入駐主存儲(chǔ)器，中央處理器輪流執(zhí)行各個(gè)作業(yè)，各個(gè)作業(yè)同時(shí)使用所需的外圍設(shè)備C.允許多個(gè)作業(yè)輪流入駐主存儲(chǔ)器，中央處理器輪流執(zhí)行各個(gè)作業(yè)，各個(gè)作業(yè)輪流使用所需的外圍設(shè)備D.允許多個(gè)作業(yè)同時(shí)入駐主存儲(chǔ)器，中央處理器輪流執(zhí)行各個(gè)作業(yè)，各個(gè)作業(yè)不同時(shí)使用所需的外圍設(shè)備A142010-4 6.采用多道程序設(shè)計(jì)方法的計(jì)算機(jī)系統(tǒng)，（）A.提高了處理器的利用率和增加了完成計(jì)算所需的總時(shí)間，提高了單位時(shí)間內(nèi)的算題能力B.提高了處理器的利用率和增加了完成計(jì)算所需的總時(shí)間，降低了單位時(shí)間內(nèi)的算題能力C.降低了處理器的利用率和單位時(shí)間內(nèi)的算題

5、能力，增加了完成計(jì)算所需的總時(shí)間D.提高了處理器的利用率和單位時(shí)間內(nèi)的算題能力，可能延長(zhǎng)完成某算題所需的總時(shí)間D152.2 進(jìn)程的概念“進(jìn)程（Process）”是現(xiàn)代操作系統(tǒng)設(shè)計(jì)中的一個(gè)基本概念，也是一個(gè)管理實(shí)體。它最早被用于美國(guó)麻省理工學(xué)院的MULTICS系統(tǒng)和IBM的CTSS/360系統(tǒng)，不過那里稱其為“任務(wù)（Task）”，其實(shí)是兩個(gè)等同的概念。16 進(jìn)程是一個(gè)程序關(guān)于某個(gè)數(shù)據(jù)集合的一次執(zhí)行過程。172.2.2 為什么引入進(jìn)程提高資源利用率正確描述程序的執(zhí)行情況18192.2.3 進(jìn)程的屬性（1）進(jìn)程是動(dòng)態(tài)概念，而程序是靜態(tài)概念20（2）程序和進(jìn)程無一一對(duì)應(yīng)關(guān)系，一個(gè)程序可能對(duì)應(yīng)多個(gè)進(jìn)程；

6、一個(gè)進(jìn)程可以包含多個(gè)程序21（3）多個(gè)進(jìn)程可并發(fā)執(zhí)行 并發(fā)： 兩個(gè)或以上進(jìn)程在同一時(shí)間段內(nèi)都向前推進(jìn)。22（4）進(jìn)程的存在是暫時(shí)的，因?yàn)樗幸粋€(gè)從創(chuàng)建到撤銷，有一個(gè)生命周期；程序存在是永久的。23（5） 進(jìn)程的狀態(tài)通常在操作系統(tǒng)中，進(jìn)程至少要有三種基本狀態(tài)(進(jìn)程控制狀態(tài))：運(yùn)行態(tài)、就緒態(tài)和等待態(tài)（等待態(tài)）。 2425 （1） 運(yùn)行態(tài)(running) 運(yùn)行狀態(tài)是指當(dāng)進(jìn)程已經(jīng)分配到CPU，它所在的程序正在處理機(jī)上執(zhí)行時(shí)的狀態(tài)。 （2） 就緒態(tài)(ready) 就緒態(tài)是指進(jìn)程已具備了運(yùn)行條件，因?yàn)槠渌M(jìn)程正占用CPU，所以暫時(shí)不能運(yùn)行而處于等待分配CPU的狀態(tài)。在操作系統(tǒng)中，處于就緒態(tài)的進(jìn)程數(shù)目可以

7、是多個(gè)。26（3） 等待態(tài) 等待狀態(tài)是指進(jìn)程等待某種事件的發(fā)生（例如等待某一輸入、輸出操作的完成，等待其它進(jìn)程發(fā)來的信號(hào)等）而暫時(shí)不能運(yùn)行的狀態(tài)。27進(jìn)程在其生存期內(nèi)不斷發(fā)生狀態(tài)轉(zhuǎn)化從一種狀態(tài)轉(zhuǎn)化成為另一種狀態(tài)282010-4 7.進(jìn)程有三種基本狀態(tài)，不可能的狀態(tài)轉(zhuǎn)換是（）A.運(yùn)行態(tài)到就緒態(tài)、運(yùn)行態(tài)到等待態(tài)B.就緒態(tài)到運(yùn)行態(tài)、等待態(tài)到就緒態(tài)C.運(yùn)行態(tài)到就緒態(tài)、等待態(tài)到就緒態(tài)D.運(yùn)行態(tài)到就緒態(tài)、等待態(tài)到運(yùn)行態(tài)D29應(yīng)注意的問題：進(jìn)程從等待態(tài)不能直接轉(zhuǎn)換到運(yùn)行態(tài)。一個(gè)進(jìn)程由運(yùn)行態(tài)轉(zhuǎn)換為等待態(tài)一般是由進(jìn)程自己主動(dòng)提出的。一個(gè)進(jìn)程由等待態(tài)變?yōu)榫途w態(tài)總是由外界事件引起的而不是有該進(jìn)程自己引起的。主動(dòng)等待

8、被喚醒30思考進(jìn)程所請(qǐng)求的一次打印輸出結(jié)束后，將使進(jìn)程狀態(tài)從（ ） A、運(yùn)行態(tài)變?yōu)榫途w態(tài) B、運(yùn)行態(tài)變?yōu)榈却龖B(tài) C、就緒態(tài)變?yōu)檫\(yùn)行態(tài) D、等待態(tài)變?yōu)榫途w態(tài) D312. 下列進(jìn)程狀態(tài)轉(zhuǎn)換中，哪一個(gè)是不正確的（ ） A. 就緒運(yùn)行 B. 運(yùn)行等待 C. 就緒等待 D. 等待就緒C32 3.某進(jìn)程在運(yùn)行過程中需要等待從磁盤上讀入數(shù)據(jù)，此時(shí)該進(jìn)程的狀態(tài)將（ ）。A.從就緒變?yōu)檫\(yùn)行 B.從運(yùn)行變?yōu)榫途w C.從運(yùn)行變?yōu)榈却?D.從等待變?yōu)榫途w C334.在單CPU環(huán)境下，存在10個(gè)進(jìn)程，這些進(jìn)程中處于運(yùn)行態(tài)的進(jìn)程最多有（ ）個(gè)，最少（ ）個(gè)；處于就緒態(tài)的進(jìn)程最多有（ ）個(gè)，最少（ ）個(gè)；處于等待態(tài)的進(jìn)程最

9、多（ ）個(gè)，最少（ ）個(gè)1090100345進(jìn)程的基本屬性是（ ）A進(jìn)程是動(dòng)態(tài)的、多個(gè)進(jìn)程可以含有相同的程序和多個(gè)進(jìn)程可以并發(fā)運(yùn)行B進(jìn)程是動(dòng)態(tài)的、多個(gè)進(jìn)程對(duì)應(yīng)的程序必須是不同的和多個(gè)進(jìn)程可以并發(fā)運(yùn)行C進(jìn)程是動(dòng)態(tài)的、多個(gè)進(jìn)程可以含有相同的程序和多個(gè)進(jìn)程不能并發(fā)運(yùn)行D進(jìn)程是靜態(tài)的、多個(gè)進(jìn)程可以含有相同的程序和多個(gè)進(jìn)程可以并發(fā)運(yùn)行A3527讓多個(gè)程序同時(shí)進(jìn)入計(jì)算機(jī)系統(tǒng)的主存儲(chǔ)器并行執(zhí)行，這種程序設(shè)計(jì)方法稱為_。28一個(gè)程序在一個(gè)數(shù)據(jù)集上的一次執(zhí)行稱為一個(gè)_。多道程序設(shè)計(jì) 進(jìn)程 3622、引入進(jìn)程的原因是( )A、提高資源的利用率B、提高程序運(yùn)行的速度C、概念“程序”不能正確描述程序的執(zhí)行情況D、使多

10、個(gè)程序能并發(fā)運(yùn)行E、概念“進(jìn)程”能正確描述程序的執(zhí)行情況ACE372.3 進(jìn)程控制塊一、 進(jìn)程的組成部分 進(jìn)程包括三部分：程序、數(shù)據(jù)、進(jìn)程控制塊，這三部分統(tǒng)稱為“進(jìn)程映象” “進(jìn)程控制塊”PCB（Process Control Block）：用于表示一個(gè)進(jìn)程相關(guān)信息的數(shù)據(jù)結(jié)構(gòu)。它是進(jìn)程存在的唯一標(biāo)志。38 進(jìn)程控制塊一般應(yīng)包括如下內(nèi)容：（1）標(biāo)識(shí)信息（進(jìn)程名） 它是惟一的對(duì)應(yīng)進(jìn)程的一個(gè)標(biāo)志符或數(shù)字。（2）說明信息進(jìn)程狀態(tài)、等待原因、進(jìn)程程序及數(shù)據(jù)存放位置39（3）現(xiàn)場(chǎng)信息 保留進(jìn)程讓出CPU時(shí)，CPU內(nèi)的各種信息，以便能繼續(xù)運(yùn)行時(shí)得以恢復(fù) 主要指各種寄存器中的內(nèi)容（psw寄存器）書簽40（4）

11、管理信息如進(jìn)程優(yōu)先權(quán)，隊(duì)列指針等 表示進(jìn)程獲取CPU的優(yōu)先級(jí)別41二、 PCB的作用（1）PCB是進(jìn)程存在的惟一標(biāo)志 系統(tǒng)創(chuàng)建進(jìn)程時(shí)，就為之創(chuàng)建一個(gè)PCB；進(jìn)程結(jié)束時(shí)，系統(tǒng)又回收其PCB，進(jìn)程便隨之消亡。 42（2）操作系統(tǒng)依據(jù)進(jìn)程控制塊對(duì)進(jìn)程進(jìn)行控制和管理。 例如，當(dāng)進(jìn)程因某種原因而暫停運(yùn)行時(shí)，其斷點(diǎn)現(xiàn)場(chǎng)信息要保存在PCB中。 431、每個(gè)進(jìn)程都有一個(gè)進(jìn)程控制塊，用以記錄各個(gè)進(jìn)程執(zhí)行時(shí)的情況，保存在各個(gè)進(jìn)程控制塊中的信息允許（ ）A、本進(jìn)程查閱B、編譯進(jìn)程讀取C、操作系統(tǒng)修改D、當(dāng)前運(yùn)行進(jìn)程修改C44三、 進(jìn)程控制 系統(tǒng)創(chuàng)建、撤消進(jìn)程，完成進(jìn)程各種狀態(tài)的轉(zhuǎn)換等功能是通過進(jìn)程控制原語實(shí)現(xiàn)的 原

12、語：執(zhí)行過程不可中斷的，具有特定功能的程序段。45 用于進(jìn)程控制的原語有：創(chuàng)建原語、撤消原語、阻塞原語、喚醒原語。46（1）創(chuàng)建原語 主要工作：為一個(gè)程序分配一個(gè)工作區(qū)和建立一個(gè)進(jìn)程控制塊，并置狀態(tài)為就緒狀態(tài) （2）撤銷原語 主要工作：進(jìn)程完成后，收回其工作區(qū)和進(jìn)程控制塊47(3)阻塞原語 進(jìn)程運(yùn)行過程中發(fā)生等待事件時(shí)，將進(jìn)程狀態(tài)改為等待態(tài)。（4）喚醒進(jìn)程原語當(dāng)進(jìn)程所等待的事件出現(xiàn)時(shí)，把進(jìn)程狀態(tài)改為就緒態(tài)482010-721.控制進(jìn)程的原語有（）A.創(chuàng)建原語B.撤銷原語C.等待原語D.喚醒原語E.延遲原語ABCD492.4 進(jìn)程隊(duì)列 為了對(duì)系統(tǒng)中的進(jìn)程控制塊進(jìn)行有效的管理，通常把所有的PCB統(tǒng)

13、一組織起來，形成若干個(gè)隊(duì)列50 一般把具有相同狀態(tài)的進(jìn)程的PCB組成隊(duì)列，形成運(yùn)行隊(duì)列、就緒隊(duì)列、等待隊(duì)列等5152出隊(duì)入隊(duì)隊(duì)列管理一個(gè)進(jìn)程從所在隊(duì)列中退出一個(gè)進(jìn)程排入到一個(gè)指定的隊(duì)列系統(tǒng)中負(fù)責(zé)進(jìn)程入隊(duì)和出隊(duì)的工作53PCB10模擬：PCB1進(jìn)程等待，歸于等待隊(duì)列1的過程PCB20542.5 中斷和中斷處理2.5.1 中斷聚精會(huì)神看書中，聽到敲門聲晚上12點(diǎn)熟睡中，鬧鐘響起某程序段執(zhí)行過程中，執(zhí)行到x=y/0指令時(shí)中 斷55中 斷 由于某些事件的出現(xiàn)，中止現(xiàn)行進(jìn)程的運(yùn)行，而由操作系統(tǒng)去處理出現(xiàn)的事件，待適當(dāng)?shù)臅r(shí)候讓被中止的進(jìn)程繼續(xù)運(yùn)行，這個(gè)過程稱為中斷56中斷源引起中斷的事件中斷處理程序 對(duì)出

14、現(xiàn)的事件進(jìn)行處理的程序572.5.2 中斷類型 從中斷事件的性質(zhì)來說，一般分為成下述幾類：硬件故障中斷 程序中斷 外部中斷 輸入/輸出中斷 訪管中斷 58硬件故障中斷 由機(jī)器故障造成的，如電源故障，主存出錯(cuò)等 59 由于程序執(zhí)行到某條機(jī)器指時(shí)可能出現(xiàn)的各種問題而引起的中斷。 如：定點(diǎn)操作數(shù)溢出，除數(shù)為0，地址越界等程序中斷 60有各種外部事件引起的中斷 ，如：按中斷鍵，定時(shí)時(shí)鐘的時(shí)間周期到外部中斷 61 輸入輸出控制系統(tǒng)發(fā)現(xiàn)外圍設(shè)備完成了輸入輸出操作而引起的中斷，或在執(zhí)行輸入輸出操作時(shí)通道或外圍設(shè)備產(chǎn)生錯(cuò)誤而引起的中斷 輸入/輸出中斷 62 正在運(yùn)行的進(jìn)程為了請(qǐng)求調(diào)用操作系統(tǒng)的某個(gè)功能而執(zhí)行一

15、條訪管指令所引起的中斷 訪管中斷 6322.中斷有若干類型，它們是（）A.硬件故障中斷B.軟件中斷C.外部中斷D.輸入/輸出中斷E.程序中斷ACDE64總 結(jié)： 硬件故障中斷、程序中斷、外部中斷 輸入/輸出中斷這四類中斷是由于外界原因迫使正在運(yùn)行的程序被打斷，稱為強(qiáng)迫性中斷事件。 而訪管中斷為正在運(yùn)行的進(jìn)程所期待的，故稱為自愿性中斷事件652.5.3 中斷響應(yīng) 自愿中斷事件是由處理器執(zhí)行指令時(shí)根據(jù)指令中的操作碼捕俘到的。強(qiáng)迫性中斷事件是由硬件的中斷裝置發(fā)現(xiàn)的 中斷發(fā)生時(shí)，硬件的中斷裝置暫?，F(xiàn)行進(jìn)程的運(yùn)行，而讓操作系統(tǒng)的中斷處理程序占用CPU,此過程稱為中斷響應(yīng)66指令n指令n+1中斷處理程序斷

16、 點(diǎn)程序A67程序狀態(tài)字（Program Status Word：PSW) : 用來控制指令執(zhí)行順序并且保留和指示與程序有關(guān)的系統(tǒng)狀態(tài)。1.5.3 程序狀態(tài)字程序基本狀態(tài)中斷碼中斷屏蔽位68程序狀態(tài)字PSW存放與寄存器中，該寄存器被稱為“程序狀態(tài)字寄存器”69當(dāng)前psw 存放在程序狀態(tài)字寄存器中的，當(dāng)前正在運(yùn)行的進(jìn)程的PSW舊 psw保護(hù)好的被中斷進(jìn)程的PSW新 psw中斷處理程序的PSW705、一個(gè)正在運(yùn)行的進(jìn)程由于某個(gè)事件被中斷后，中斷裝置都要進(jìn)行交換PSW的工作，以完成（ ）A、中斷檢查B、中斷響應(yīng)C、中斷處理D、中斷請(qǐng)求B712.5.4 中斷處理 中斷處理程序?qū)χ袛嗍录奶幚矸謨刹竭M(jìn)行

17、：保護(hù)被中斷進(jìn)程的現(xiàn)場(chǎng)信息根據(jù)中斷事件轉(zhuǎn)入相應(yīng)的中斷處理程序進(jìn)行具體處理721.硬件故障處理2.程序中斷處理3.外部中斷處理4.輸入/輸出中斷處理5.訪管中斷事件處理必須進(jìn)行人工干預(yù)與程序的具體編制有關(guān)，不同用戶往往有不同處理要求，所以可轉(zhuǎn)交給用戶自行處理根據(jù)中斷鍵的編號(hào)把處理轉(zhuǎn)交給一個(gè)特定的例行程序分為“I/O正常結(jié)束”和“I/O異常結(jié)束”732009-421進(jìn)程控制塊是對(duì)進(jìn)程進(jìn)行管理和調(diào)度的信息集合，所含信息是（ ）A標(biāo)識(shí)信息B說明信息C網(wǎng)絡(luò)信息D現(xiàn)場(chǎng)信息E管理信息22操作系統(tǒng)中有許多進(jìn)程隊(duì)列，它們是（ ）A就緒隊(duì)列B掛起隊(duì)列C運(yùn)行隊(duì)列D要求使用設(shè)備的等待隊(duì)列E等待其他資源的隊(duì)列ABDEA

18、CDE742009-429訪管中斷是進(jìn)程為請(qǐng)求調(diào)用操作系統(tǒng)的某個(gè)功能，執(zhí)行 _ 所引起的中斷。48說明中斷發(fā)生和中斷響應(yīng)的處理過程。（需說明程序狀態(tài)字在此過程中是如何變化的。）訪管指令752009-73、進(jìn)程控制塊中的說明信息是( )A、進(jìn)程狀態(tài)、進(jìn)程等待原因、進(jìn)程程序存放位置、進(jìn)程數(shù)據(jù)存放位置B、進(jìn)程狀態(tài)、通用寄存器內(nèi)容、控制寄存器內(nèi)容、進(jìn)程程序存放位置C、通用寄存器內(nèi)容、控制寄存器內(nèi)容、進(jìn)程程序存放位置、進(jìn)程數(shù)據(jù)存放位置D、進(jìn)程狀態(tài)、進(jìn)程等待原因、通用寄存器內(nèi)容、控制寄存器內(nèi)容A764、等待狀態(tài)的進(jìn)程是處于隊(duì)列中的，設(shè)備的等待隊(duì)列的組織方式是( )A、系統(tǒng)有一個(gè)等待隊(duì)列B、系統(tǒng)為每個(gè)設(shè)備各

19、建立一個(gè)隊(duì)列C、系統(tǒng)為每個(gè)設(shè)備類各建立一個(gè)隊(duì)列D、系統(tǒng)為每個(gè)設(shè)備類和設(shè)備各建立一個(gè)隊(duì)列B775、關(guān)于中斷的分類，屬于強(qiáng)迫性中斷的是( )A、硬件故障中斷、程序中斷、外部中斷、輸入/輸出中斷B、訪管中斷、程序中斷、外部中斷、輸入/輸出中斷c、硬件故障中斷、訪管中斷、外部中斷、輸入輸出中斷D、硬件故障中斷、程序中斷、訪管中斷、輸入/輸出中斷A7830.計(jì)算機(jī)系統(tǒng)有多種中斷事件，其中的硬件故障中斷事件的處理必須_。人工干預(yù)792.6 處理器調(diào)度 在系統(tǒng)運(yùn)行過程中，就緒進(jìn)程的數(shù)目往往多于CPU的數(shù)目，這就將導(dǎo)致它們爭(zhēng)奪資源。此時(shí)就要求系統(tǒng)根據(jù)一定的算法，由進(jìn)程調(diào)度程序從就緒隊(duì)列中選擇一個(gè)進(jìn)程，使之在C

20、PU上運(yùn)行。80磁盤CPU一批作業(yè)小貼士：CPU不能直接訪問外存內(nèi)存條需要選擇若干個(gè)調(diào)入內(nèi)存作業(yè)調(diào)度進(jìn)程A進(jìn)程B進(jìn)程C進(jìn)程D進(jìn)程調(diào)度分配CPU的調(diào)度81調(diào)度的層次 高級(jí)調(diào)度（作業(yè)調(diào)度、宏觀調(diào)度）按一定原則對(duì)外存上的作業(yè)進(jìn)行調(diào)度，并建立進(jìn)程PCB。它決定允許哪些作業(yè)競(jìng)爭(zhēng)系統(tǒng)資源。由于這種調(diào)度決定哪些作業(yè)可以進(jìn)入系統(tǒng)，所以也稱收容調(diào)度。82 低級(jí)調(diào)度（進(jìn)程調(diào)度、處理機(jī)調(diào)度）它決定了存在就緒進(jìn)程時(shí)，哪一個(gè)就緒進(jìn)程將分配到中央處理機(jī)，并且把中央處理機(jī)實(shí)際分配給這個(gè)進(jìn)程（即低級(jí)調(diào)度是將處理機(jī)分配給進(jìn)程）。83作業(yè)流進(jìn)程“運(yùn)行”作業(yè)進(jìn)入“輸入井”等待執(zhí)行作業(yè)被裝入主存儲(chǔ)器，作業(yè)進(jìn)程“就緒”預(yù)輸入進(jìn)程調(diào)度作

21、業(yè)調(diào)度外存的一片存儲(chǔ)區(qū)域圖2-11 作業(yè)調(diào)度與進(jìn)程調(diào)度的層次關(guān)系842011-446、請(qǐng)給出處理器的兩級(jí)調(diào)度的名稱。請(qǐng)說明兩級(jí)調(diào)度的過程。852.6.2 作業(yè)調(diào)度算法 在設(shè)計(jì)調(diào)度算法時(shí)，原則：公平性平衡資源使用極大的流量（吞吐量）862.調(diào)度算法周轉(zhuǎn)時(shí)間：假定作業(yè)i提交給系統(tǒng)的時(shí)間為Si，其完成的時(shí)間為Ei。那么該作業(yè)的周轉(zhuǎn)時(shí)間Ti為 Ti=EiSi平均周轉(zhuǎn)時(shí)間：對(duì)于一批n個(gè)作業(yè)而言，它們的平均周轉(zhuǎn)時(shí)間T為 T=(T1+T2+Tn)/n87“先來先服務(wù)”作業(yè)調(diào)度算法以作業(yè)提交（到達(dá)外存輸入井）的先后次序，作為作業(yè)調(diào)度程序挑選作業(yè)的依據(jù)，這就是先來先服務(wù)作業(yè)調(diào)度算法的基本思想。88思考：有3個(gè)作

22、業(yè)；它們按照1、2、3的順序，同時(shí)提交給系統(tǒng)，采用先來先服務(wù)的作業(yè)調(diào)度算法。求每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間以及它們的平均周轉(zhuǎn)時(shí)間。（忽略系統(tǒng)調(diào)度所花費(fèi)的時(shí)間及內(nèi)存的使用情況）89作業(yè)J1J2J30242730T90進(jìn)程名到達(dá)時(shí)間執(zhí)行用時(shí)完成時(shí)間周轉(zhuǎn)時(shí)間J102424J20327J30330242730平均周轉(zhuǎn)時(shí)間：（24+27+30）/3=27911、某單道系統(tǒng)中，現(xiàn)有1-4四個(gè)作業(yè)在后備作業(yè)隊(duì)列里等待處理。它們到達(dá)系統(tǒng)和所需的計(jì)算時(shí)間如下表所示：采用先來先服務(wù)作業(yè)調(diào)度算法對(duì)作業(yè)進(jìn)行調(diào)度。試計(jì)算出每個(gè)作業(yè)被選中的順序（忽略系統(tǒng)調(diào)度時(shí)間）。各自的周轉(zhuǎn)時(shí)間是多少？平均周轉(zhuǎn)時(shí)間是多少？作業(yè)到達(dá)時(shí)間所需CPU的

23、時(shí)間19：0070分鐘29：4030分鐘39：5010分鐘410：105分鐘92作業(yè)1239:0010:1010:4010:50T410:5593 注意：不是先進(jìn)入的一定被先選中，只有滿足必要條件的作業(yè)才可能被選中94思考：有5個(gè)作業(yè)（假定都是計(jì)算型的），它們進(jìn)入后備作業(yè)隊(duì)列的到達(dá)時(shí)間如下表所示（注意，不是同時(shí)到達(dá)）。設(shè)供用戶使用的主存空間為100K，作業(yè)調(diào)度和進(jìn)程調(diào)度均采用先來先服務(wù)算法，試求每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間和它們的平均周轉(zhuǎn)時(shí)間。（忽略系統(tǒng)調(diào)度時(shí)間，都沒有輸入/輸出請(qǐng)求）。ABCDE60KB20KB10KB95TABCDE10.1內(nèi)存（100KB)A(15K)15K10.810.310.5

24、B(60K)60K11.3D(10K)10K11.7作業(yè)C、E何時(shí)運(yùn)行？96TABCDE10.1內(nèi)存（100KB)A(15K)15K10.8B(60K)60K11.3D(10K)10K11.7作業(yè)完成時(shí)回收內(nèi)存75KC(50K)E(20K)12.112.397FCFS算法利于長(zhǎng)作業(yè)，而不利于短作業(yè)FCFS算法利于CPU繁忙型作業(yè)，而不利于I/O繁忙型作業(yè)課后12題98短作業(yè)優(yōu)先”作業(yè)調(diào)度算法作業(yè)調(diào)度程序工作時(shí)，總是從后備作業(yè)隊(duì)列中挑選所需計(jì)算時(shí)間最少、且資源能夠得到滿足的作業(yè)進(jìn)入內(nèi)存投入運(yùn)行，這就是“短作業(yè)優(yōu)先”作業(yè)調(diào)度算法的基本思想。99思考：有3個(gè)作業(yè)；它們按照1、2、3的順序，同時(shí)提交給

25、系統(tǒng)，采用短作業(yè)優(yōu)先調(diào)度算法。求每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間以及它們的平均周轉(zhuǎn)時(shí)間。（忽略系統(tǒng)調(diào)度所花費(fèi)的時(shí)間及內(nèi)存的使用情況）100作業(yè)J1J2J303630T101作業(yè)名到達(dá)時(shí)間執(zhí)行用時(shí)完成時(shí)間周轉(zhuǎn)時(shí)間J102430J2033J30363036平均周轉(zhuǎn)時(shí)間：（30+3+6）/3=13102作業(yè)所需CPU的時(shí)間110233845有四個(gè)作業(yè)同時(shí)提交給系統(tǒng)，畫出短作業(yè)優(yōu)先算法下執(zhí)行情況圖12340T3816261031、某單道系統(tǒng)中，現(xiàn)有1-4四個(gè)作業(yè)在后備作業(yè)隊(duì)列里等待處理。它們到達(dá)系統(tǒng)和所需的計(jì)算時(shí)間如下表所示：采用短作業(yè)優(yōu)先作業(yè)調(diào)度算法對(duì)作業(yè)進(jìn)行調(diào)度。試計(jì)算出每個(gè)作業(yè)被選中的順序（忽略系統(tǒng)調(diào)度時(shí)間）

26、。各自的周轉(zhuǎn)時(shí)間是多少？平均周轉(zhuǎn)時(shí)間是多少？作業(yè)到達(dá)時(shí)間所需CPU的時(shí)間19：0070分鐘29：4030分鐘39：5010分鐘410：105分鐘104作業(yè)1239:0010:1010:5510:25T410:15105思考：有5個(gè)作業(yè)（假定都是計(jì)算型的），它們進(jìn)入后備作業(yè)隊(duì)列的到達(dá)時(shí)間如下表所示（注意，不是同時(shí)到達(dá)）。設(shè)供用戶使用的主存空間為100K，作業(yè)調(diào)度和進(jìn)程調(diào)度均采用短作業(yè)算法，試求每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間和它們的平均周轉(zhuǎn)時(shí)間。（忽略系統(tǒng)調(diào)度時(shí)間，都沒有輸入/輸出請(qǐng)求）。ABCDE60KB20KB10KB106TABCDE10.1內(nèi)存（100KB)A(15K)15K10.810.310.55

27、0K11.0E(20K)20K11.4C(50K)D(20K)11.812.3107思考：若采用短作業(yè)優(yōu)先調(diào)度算法，假定系統(tǒng)內(nèi)有如下耗時(shí)的進(jìn)程：20（分鐘），6（分鐘），1，5，4，3，8然后又有有些用時(shí)小于5分鐘的多個(gè)作業(yè)陸續(xù)進(jìn)入系統(tǒng)。會(huì)導(dǎo)致什么后果？108響應(yīng)比高者優(yōu)先”作業(yè)調(diào)度算法 所謂一個(gè)作業(yè)的響應(yīng)比，響應(yīng)比已等待時(shí)間/計(jì)算時(shí)間“響應(yīng)比高者優(yōu)先”的作業(yè)調(diào)度算法，既照顧到了短作業(yè)的利益，也照顧到了長(zhǎng)作業(yè)的利益，是一種折中的作業(yè)調(diào)度算法。109例如：某單道程序設(shè)計(jì)系統(tǒng)中有三個(gè)作業(yè)A、B、C,具體情況詳見下表：當(dāng)三個(gè)作業(yè)全部到達(dá)輸入井后，系統(tǒng)以響應(yīng)比高者優(yōu)先調(diào)度算法選擇作業(yè)，忽略調(diào)度用時(shí)，分

28、析作業(yè)執(zhí)行情況作業(yè)名需計(jì)算時(shí)間到達(dá)輸入井時(shí)間ABC8:509:009:301.5小時(shí)0.4小時(shí)1.0小時(shí)110作業(yè)ABC9:3012:24TA的響應(yīng)比=40/90=4/9B的響應(yīng)比=30/24=5/4C的響應(yīng)比=0/60=09:30時(shí)各作業(yè)響應(yīng)比9:549:54時(shí)各作業(yè)響應(yīng)比A的響應(yīng)比=64/90=32/45C的響應(yīng)比=24/60=2/511.24111例題4：有4個(gè)作業(yè)，它們進(jìn)入后備作業(yè)隊(duì)列的到達(dá)時(shí)間如下表所示。假設(shè)當(dāng)四個(gè)作業(yè)全部到達(dá)后采用響應(yīng)比高者優(yōu)先的作業(yè)調(diào)度算法，求每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間以及它們的平均周轉(zhuǎn)時(shí)間。（忽略系統(tǒng)調(diào)度時(shí)間）1122011-451、有A、B、C、D、E5個(gè)作業(yè)在某單道

29、計(jì)算機(jī)系統(tǒng)里等待處理。他們需要執(zhí)行的時(shí)間分別為2、8、6、4、10分鐘。首先讓作業(yè)A執(zhí)行，對(duì)其余作業(yè)采用響應(yīng)比高者優(yōu)先算法進(jìn)行調(diào)度。在忽略調(diào)度等所需時(shí)間下，寫出各作業(yè)被選中執(zhí)行時(shí)的次序及被選中時(shí)的響應(yīng)比。1134、優(yōu)先級(jí)調(diào)度算法5、均衡調(diào)度算法114CPU1152.6.3 進(jìn)程調(diào)度算法進(jìn)程切換一個(gè)進(jìn)程讓出CPU由另外一個(gè)進(jìn)程占用CPU的過程116進(jìn)程切換的時(shí)機(jī)進(jìn)程由運(yùn)行狀態(tài)變?yōu)榈却隣顟B(tài)進(jìn)程由運(yùn)行狀態(tài)變?yōu)榫途w狀態(tài)進(jìn)程由等待狀態(tài)變?yōu)榫途w狀態(tài)進(jìn)程結(jié)束后被撤銷中斷117 常用的進(jìn)程調(diào)度算法有：先來先服務(wù)(FCFS)、優(yōu)先數(shù)法、時(shí)間片輪轉(zhuǎn)法118先來先服務(wù)調(diào)度算法 基本思想是：以到達(dá)就緒隊(duì)列的先后次序?yàn)?/p>

30、標(biāo)準(zhǔn)來選擇占用處理機(jī)的進(jìn)程。一個(gè)進(jìn)程一旦占有處理機(jī)，就一直使用下去，直至正常結(jié)束或因等待某事件的發(fā)生而讓出處理機(jī)。 119例題假定在單CPU條件下，有如下要執(zhí)行的進(jìn)程，見下表請(qǐng)用FCFS算法畫出執(zhí)行情況圖并求出平均周轉(zhuǎn)時(shí)間進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間P1010P211P322P431P545120解：根據(jù)FCFS調(diào)度算法的思想，各進(jìn)程調(diào)度順序?yàn)镻1、P2、P3、 P4 、 P5進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間P1010P211P322P431P54510111913141010111115121TP1P5P4P3P20104111314191222優(yōu)先數(shù)調(diào)度算法 基本思想是：為系統(tǒng)中的每個(gè)進(jìn)程規(guī)定

31、一個(gè)優(yōu)先數(shù)，就緒隊(duì)列中具有最高優(yōu)先數(shù)的進(jìn)程有優(yōu)先獲得處理機(jī)的權(quán)利。如果幾個(gè)進(jìn)程的優(yōu)先數(shù)相同，則對(duì)它們實(shí)行先來先服務(wù)的調(diào)度。 123進(jìn)程的調(diào)度方式非搶占式 是指某一進(jìn)程一旦占用CPU，便一直運(yùn)行下去，直到它運(yùn)行結(jié)束或因某種原因被等待才交出CPU，否則不能從該進(jìn)程搶走CPU.特點(diǎn)：簡(jiǎn)單，系統(tǒng)開銷小 對(duì)緊急任務(wù)和短作業(yè)不公平。124可搶占方式 是指某進(jìn)程正在運(yùn)行時(shí)，系統(tǒng)可基于某種原則，將其占用的CPU剝奪，分配給其它進(jìn)程。其原則主要有：優(yōu)先權(quán)高的進(jìn)程可以剝奪優(yōu)先權(quán)低的進(jìn)程的CPU.短進(jìn)程可以剝奪長(zhǎng)進(jìn)程的CPU.時(shí)間片用完后交出CPU重新調(diào)度已確定將CPU交給誰。125 特點(diǎn)：實(shí)時(shí)系統(tǒng)、分時(shí)系統(tǒng)中使用

32、，方式靈活，但系統(tǒng)開銷較大。126例題假定在單CPU條件下，有如下要執(zhí)行的進(jìn)程，見下表,請(qǐng)用非搶占優(yōu)先級(jí)(設(shè)數(shù)字越大，優(yōu)先級(jí)越高）算法畫出執(zhí)行情況圖并求出平均周轉(zhuǎn)時(shí)間進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間優(yōu)先級(jí)P10103P2116P3223P4311P5455127解：根據(jù)優(yōu)先級(jí)高者優(yōu)先調(diào)度算法的思想，各進(jìn)程調(diào)度順序?yàn)镻1、P2、P5、P3、P4進(jìn)程到達(dá)時(shí)間運(yùn)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間P1010P211P322P431P54510111618191010161612128確定進(jìn)程的優(yōu)先數(shù)的因素： 根據(jù)進(jìn)程的類型。 系統(tǒng)進(jìn)程大于用戶進(jìn)程。 根據(jù)進(jìn)程執(zhí)行任務(wù)的重要性。 處理緊急事件的優(yōu)先級(jí)要高。根據(jù)進(jìn)程程序的性質(zhì)。

33、CPU繁忙型作業(yè)，影響系統(tǒng)整體的效率發(fā)揮，給予較低的優(yōu)先數(shù)；I/O繁忙型進(jìn)程給予較高優(yōu)先數(shù)，充分發(fā)揮CPU和外部設(shè)備并行工作能力。129根據(jù)對(duì)資源的要求。 系統(tǒng)有處理機(jī)、內(nèi)存和外部設(shè)備等，占用CPU時(shí)間短，內(nèi)存容量少的進(jìn)程給予的優(yōu)先級(jí)高一些，可以提高系統(tǒng)的吞吐量。根據(jù)用戶的請(qǐng)求。1303.時(shí)間片輪轉(zhuǎn)調(diào)度算法 Round-Robin Scheduling: RR算法 基本思想是：為就緒隊(duì)列中的每一個(gè)進(jìn)程分配一個(gè)稱為“時(shí)間片”的時(shí)間段，在使用完一個(gè)時(shí)間片后，也要強(qiáng)迫其釋放處理機(jī)，讓給另一個(gè)進(jìn)程使用。它自己則返回到就緒隊(duì)列末尾，排隊(duì)等待下一次調(diào)度的到來。 131132例題 有四個(gè)進(jìn)程A，B，C，D，

34、設(shè)他們依次進(jìn)入就緒隊(duì)列，相差時(shí)間很短，可近似認(rèn)為同時(shí)到達(dá)，它們分別需要運(yùn)行12，5，3和6個(gè)時(shí)間單位。請(qǐng)畫出時(shí)間片q=1與q=4時(shí)運(yùn)行的情況133DACB0T11172026134 時(shí)間片輪轉(zhuǎn)調(diào)度算法經(jīng)常用在分時(shí)操作系統(tǒng)中。 在時(shí)間片輪轉(zhuǎn)調(diào)度算法中，時(shí)間片大小的設(shè)定是一個(gè)影響系統(tǒng)效率發(fā)揮的重要因素。 135 太長(zhǎng)： 太短： 確定因素：系統(tǒng)對(duì)響應(yīng)時(shí)間的要求、就緒隊(duì)列進(jìn)程數(shù)目（成反比）、進(jìn)程切換時(shí)間、CPU運(yùn)行速度RR算法退化為FCFS算法CPU頻繁切換，導(dǎo)致系統(tǒng)開銷較大136在分時(shí)系統(tǒng)中，經(jīng)常采用時(shí)間片輪轉(zhuǎn)調(diào)度算法。 例如：某分時(shí)系統(tǒng)用戶數(shù)為10個(gè)，時(shí)間片為100毫秒，若對(duì)于終端用戶的每個(gè)要求處理器需花費(fèi)300毫秒左右的時(shí)間給出應(yīng)答，則相應(yīng)時(shí)間大致為（ ）3秒1372011.46、假定一個(gè)分時(shí)系統(tǒng)允許20個(gè)終端用戶同時(shí)工作。若分配給每個(gè)終端用戶的時(shí)間片為50毫秒，而對(duì)終端用戶的每個(gè)請(qǐng)求需處理200毫秒給出應(yīng)答，那么終端的最長(zhǎng)響應(yīng)時(shí)間