醫(yī)軟11大三第一學(xué)期第5章處理機(jī)管理

第五章操作系統(tǒng)的資源管理操作系統(tǒng)的資源管理gdpu5.1資源管理的機(jī)制與策略5.2死鎖及其解決方法5.3處理機(jī)管理（2學(xué)時(shí)）5.4主存管理（4學(xué)時(shí)）5.5設(shè)備管理（2學(xué)時(shí)）1操作系統(tǒng)的資源管理——主要內(nèi)容gdpu5.3.1處理機(jī)的多級(jí)調(diào)度5.3.2作業(yè)調(diào)度5.3.3進(jìn)程調(diào)度3操作系統(tǒng)的資源管理(2)——主要內(nèi)容

gdpu41.處理機(jī)調(diào)度的功能確定數(shù)據(jù)結(jié)構(gòu)

確定調(diào)度策略(調(diào)度原則)

給出調(diào)度算法

實(shí)施處理機(jī)分派

不同類型的操作系統(tǒng)往往采用不同的處理機(jī)分配方法

操作系統(tǒng)的資源管理(2)——5.3.1處理機(jī)的多級(jí)調(diào)度

52.批處理系統(tǒng)中的處理機(jī)調(diào)度

處理機(jī)調(diào)度分為兩級(jí)：作業(yè)調(diào)度和進(jìn)程調(diào)度作業(yè)調(diào)度——宏觀調(diào)度任務(wù)——對(duì)存放在輔存設(shè)備上的大量作業(yè)，以一定的策略進(jìn)行挑選，分配主存等必要的資源，建立作業(yè)對(duì)應(yīng)的進(jìn)程，使其投入運(yùn)行。進(jìn)程調(diào)度——微觀調(diào)度任務(wù)——對(duì)進(jìn)入主存的所有進(jìn)程，確定哪個(gè)進(jìn)程在什么時(shí)候獲得處理機(jī)，使用多長(zhǎng)時(shí)間。操作系統(tǒng)的資源管理(2)——處理機(jī)的多級(jí)調(diào)度

63.多任務(wù)操作系統(tǒng)中的處理機(jī)調(diào)度多進(jìn)程的產(chǎn)生

在分時(shí)系統(tǒng)或支持多任務(wù)并發(fā)執(zhí)行個(gè)人計(jì)算機(jī)操作系統(tǒng)中，系統(tǒng)將用戶提交的任務(wù)處理為進(jìn)程，一個(gè)進(jìn)程又可以創(chuàng)建多個(gè)子進(jìn)程，形成可以并發(fā)執(zhí)行的多進(jìn)程。進(jìn)程調(diào)度的任務(wù)當(dāng)處理機(jī)空閑時(shí)，以某種策略選擇一個(gè)就緒進(jìn)程去運(yùn)行，并分配處理機(jī)的時(shí)間。操作系統(tǒng)的資源管理(2)——處理機(jī)的多級(jí)調(diào)度

8

作業(yè)在整個(gè)活動(dòng)期間有如下狀態(tài)。后備狀態(tài)作業(yè)已存放在磁盤上，等待調(diào)度。運(yùn)行狀態(tài)作業(yè)進(jìn)入主存開始運(yùn)行。完成狀態(tài)

作業(yè)計(jì)算完成開始，退出系統(tǒng)。 1.作業(yè)的狀態(tài)操作系統(tǒng)的資源管理(2)——5.3.2作業(yè)調(diào)度

9作業(yè)狀態(tài)變遷圖運(yùn)行就緒

完成等待后備作業(yè)調(diào)度作業(yè)調(diào)度執(zhí)行操作系統(tǒng)的資源管理(2)——作業(yè)調(diào)度

10確定數(shù)據(jù)結(jié)構(gòu)建立作業(yè)控制塊jcb(jobcontrolblock)。作業(yè)控制塊記錄了每個(gè)作業(yè)類型、狀態(tài)、資源請(qǐng)求及分配情況。確定調(diào)度策略與調(diào)度算法分配資源為選中的作業(yè)分配所需要的系統(tǒng)資源。善后處理收回該作業(yè)所占用的全部資源，撤消作業(yè)控制塊以及與該作業(yè)有關(guān)的全部進(jìn)程資源。

2.作業(yè)調(diào)度的功能操作系統(tǒng)的資源管理(2)——作業(yè)調(diào)度

11主要內(nèi)容作業(yè)名資源要求估計(jì)執(zhí)行時(shí)間、最遲完成時(shí)間、要求的主存量、要求外設(shè)的類型及臺(tái)數(shù)、要求文件量和輸出量資源使用情況進(jìn)入系統(tǒng)時(shí)間、開始執(zhí)行時(shí)間、已執(zhí)行時(shí)間、主存地址、外設(shè)臺(tái)號(hào)類型、優(yōu)先級(jí)、作業(yè)狀態(tài)等等3.作業(yè)控制塊

操作系統(tǒng)的資源管理(2)——作業(yè)調(diào)度

12周轉(zhuǎn)時(shí)間

一個(gè)作業(yè)提交給計(jì)算機(jī)系統(tǒng)到該作業(yè)的結(jié)果返回給用戶所需要的時(shí)間。定義ti=tci-tsiti—作業(yè)i的周轉(zhuǎn)時(shí)間tsi—作業(yè)i的提交時(shí)間

tci—作業(yè)i的完成時(shí)間意義說明作業(yè)i在系統(tǒng)中停留時(shí)間的長(zhǎng)短平均周轉(zhuǎn)時(shí)間t=4.作業(yè)調(diào)度算法性能的衡量的功能

采用平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間衡量作業(yè)調(diào)度算法性能的好壞。操作系統(tǒng)的資源管理(2)——作業(yè)調(diào)度

13帶權(quán)周轉(zhuǎn)時(shí)間定義：一個(gè)作業(yè)的周轉(zhuǎn)時(shí)間與其運(yùn)行時(shí)間的比值

wi=意義說明作業(yè)i在系統(tǒng)中相對(duì)等待時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間w=操作系統(tǒng)的資源管理(2)——作業(yè)調(diào)度

用于衡量同一調(diào)度算法對(duì)不同作業(yè)流的調(diào)度性能：平均帶權(quán)周轉(zhuǎn)時(shí)間越小，作業(yè)調(diào)度算法對(duì)該作業(yè)流的調(diào)度性能越好。

13引例:下面有4個(gè)作業(yè),你認(rèn)為它們的運(yùn)行順序會(huì)是怎樣的呢?(單位：小時(shí)，并以十進(jìn)制計(jì)）作業(yè)提交時(shí)間運(yùn)行時(shí)間18.002.0028.500.5039.000.1049.500.2014先來先服務(wù)調(diào)度算法(FCFS)策略：按作業(yè)來到的先后次序進(jìn)行調(diào)度。特點(diǎn)：簡(jiǎn)單，易實(shí)現(xiàn)。缺點(diǎn)：沒有考慮各個(gè)作業(yè)運(yùn)行特征和資源要求的差異，系統(tǒng)效率較低。5.常用的作業(yè)調(diào)度算法

操作系統(tǒng)的資源管理(2)——作業(yè)調(diào)度

14先來先服務(wù)調(diào)度算法(FCFS)討論：先來先服務(wù)調(diào)度算法下的周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間5.常用的作業(yè)調(diào)度算法

作業(yè)提交時(shí)間執(zhí)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間

18.00 2.00 2 8.50 0.503 9.00 0.1049.500.208.0010.002.00110.0010.502.00410.5010.601.601610.6010.801.306.5

平均周轉(zhuǎn)時(shí)間t=

平均帶權(quán)周轉(zhuǎn)時(shí)間w=1.7256.875操作系統(tǒng)的資源管理(2)——作業(yè)調(diào)度

15短作業(yè)優(yōu)先調(diào)度算法(SJ)策略：按作業(yè)請(qǐng)求運(yùn)行的時(shí)間長(zhǎng)短進(jìn)行調(diào)度。特點(diǎn)：易實(shí)現(xiàn)，系統(tǒng)吞吐量高。缺點(diǎn)：只照顧短作業(yè)而不考慮長(zhǎng)作業(yè)的利益。如果系統(tǒng)不斷地接受新的短作業(yè)。則有可能較長(zhǎng)作業(yè)長(zhǎng)時(shí)間等待而不能運(yùn)行。操作系統(tǒng)的資源管理(2)——作業(yè)調(diào)度

5.常用的作業(yè)調(diào)度算法

15短作業(yè)優(yōu)先調(diào)度算法討論：短作業(yè)優(yōu)先調(diào)度算法下的周轉(zhuǎn)時(shí)間與帶權(quán)周轉(zhuǎn)時(shí)間短作業(yè)優(yōu)先調(diào)度算法(SJF)作業(yè)提交時(shí)間執(zhí)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間

18.00 2.00 2 8.50 0.503 9.00 0.1049.500.20

平均周轉(zhuǎn)時(shí)間t=

平均帶權(quán)周轉(zhuǎn)時(shí)間w=8.0010.002.00110.3010.802.304.610.0010.101.101110.1010.300.8041.555.15操作系統(tǒng)的資源管理(2)——作業(yè)調(diào)度

5.常用的作業(yè)調(diào)度算法

FCFS和SJF調(diào)度算法的性能

練習(xí)：??操作系統(tǒng)的資源管理(2)——作業(yè)調(diào)度

高響應(yīng)比優(yōu)先調(diào)度算法

響應(yīng)比是指作業(yè)的響應(yīng)時(shí)間與作業(yè)估計(jì)運(yùn)行時(shí)間的比值。

選擇原則是優(yōu)先選取響應(yīng)比值最大的作業(yè)。即兼顧等待時(shí)間長(zhǎng)和運(yùn)行時(shí)間短的作業(yè)，它是FCFS和SJF算法的結(jié)合。響應(yīng)比＝1＋作業(yè)等待時(shí)間/要求服務(wù)時(shí)間5.常用的作業(yè)調(diào)度算法

操作系統(tǒng)的資源管理(2)——作業(yè)調(diào)度

作業(yè)提交時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間18.002.008.0010.002.00128.500.5010.1010.602.104.239.000.1010.0010.101.101149.500.2010.6010.801.306.5例：高響應(yīng)比優(yōu)先調(diào)度算法（單位：小時(shí)，并以十進(jìn)制計(jì))平均周轉(zhuǎn)時(shí)間T＝1.625，平均帶權(quán)周轉(zhuǎn)時(shí)間W＝5.675

響應(yīng)比＝1＋作業(yè)等待時(shí)間/要求服務(wù)時(shí)間例如：當(dāng)作業(yè)3結(jié)束時(shí)，Rp2=1＋作業(yè)等待時(shí)間/可執(zhí)行時(shí)間=1+(10.10-8.50)/0.5=1+3.2Rp4=1＋作業(yè)等待時(shí)間/可執(zhí)行時(shí)間=1+(10.10-9.50)/0.2=1+3操作系統(tǒng)的資源管理(2)——作業(yè)調(diào)度

16進(jìn)程管理的數(shù)據(jù)結(jié)構(gòu)

決定調(diào)度策略優(yōu)先調(diào)度——就緒隊(duì)列按進(jìn)程優(yōu)先級(jí)高低排序先來先服務(wù)——就緒隊(duì)列按進(jìn)程來到的先后次序排序?qū)嵤┨幚頇C(jī)的分配和回收1.進(jìn)程調(diào)度的功能操作系統(tǒng)的資源管理(2)——5.3.3進(jìn)程調(diào)度

17什么是調(diào)度方式當(dāng)一進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，若有某個(gè)更為“重要而緊迫”的進(jìn)程需要運(yùn)行，系統(tǒng)如何分配處理機(jī)。非剝奪方式讓正在執(zhí)行的進(jìn)程繼續(xù)執(zhí)行，直到該進(jìn)程完成或發(fā)生某事件而進(jìn)入“完成”或“阻塞”狀態(tài)時(shí)，才把處理機(jī)分配給“重要而緊迫”的進(jìn)程。剝奪方式當(dāng)“重要而緊迫”的進(jìn)程一到，便暫停正在執(zhí)行的進(jìn)程，立即把處理機(jī)分配給優(yōu)先級(jí)更高的進(jìn)程。2.進(jìn)程調(diào)度的方式操作系統(tǒng)的資源管理(2)——進(jìn)程調(diào)度

18進(jìn)程優(yōu)先數(shù)調(diào)度算法什么是進(jìn)程優(yōu)先數(shù)調(diào)度算法預(yù)先確定各進(jìn)程的優(yōu)先數(shù)，系統(tǒng)把處理機(jī)的使用權(quán)賦予就緒隊(duì)列中具備最高優(yōu)先權(quán)(優(yōu)先數(shù)和一定的優(yōu)先級(jí)相對(duì)應(yīng))的就緒進(jìn)程。3.進(jìn)程調(diào)度算法操作系統(tǒng)的資源管理(2)——進(jìn)程調(diào)度

19優(yōu)先數(shù)的分類及確定靜態(tài)優(yōu)先數(shù)在進(jìn)程被創(chuàng)建時(shí)確定，且一經(jīng)確定后在整個(gè)進(jìn)程運(yùn)行期間不再改變。靜態(tài)優(yōu)先數(shù)的確定優(yōu)先數(shù)根據(jù)進(jìn)程所需使用的資源來計(jì)算優(yōu)先數(shù)基于程序運(yùn)行時(shí)間的估計(jì)優(yōu)先數(shù)基于進(jìn)程的類型操作系統(tǒng)的資源管理(2)——進(jìn)程調(diào)度

3.進(jìn)程調(diào)度算法19動(dòng)態(tài)優(yōu)先數(shù)進(jìn)程優(yōu)先數(shù)在進(jìn)程運(yùn)行期間可以改變。動(dòng)態(tài)優(yōu)先數(shù)的確定進(jìn)程使用CPU超過一定數(shù)值時(shí)，降低優(yōu)先數(shù)進(jìn)程I/O操作后，增加優(yōu)先數(shù)進(jìn)程等待時(shí)間超過一定數(shù)值時(shí)，提高優(yōu)先數(shù)操作系統(tǒng)的資源管理(2)——進(jìn)程調(diào)度

3.進(jìn)程調(diào)度算法20循環(huán)輪轉(zhuǎn)調(diào)度算法什么是循環(huán)輪轉(zhuǎn)調(diào)度算法

當(dāng)CPU空閑時(shí)，選取就緒隊(duì)列首元素，賦予一個(gè)時(shí)間片，當(dāng)時(shí)間片用完時(shí)，該進(jìn)程轉(zhuǎn)為就緒態(tài)并進(jìn)入就緒隊(duì)列末端。該隊(duì)列結(jié)構(gòu)是什么？pcb1pcb2pcbnCPU完成操作系統(tǒng)的資源管理(2)——進(jìn)程調(diào)度

21簡(jiǎn)單循環(huán)輪轉(zhuǎn)調(diào)度算法就緒隊(duì)列中的所有進(jìn)程以等速度向前進(jìn)展。

q=t/nt為響應(yīng)時(shí)間，n為進(jìn)入系統(tǒng)的進(jìn)程數(shù)目。思考：q值的影響?循環(huán)輪轉(zhuǎn)調(diào)度算法的發(fā)展可變時(shí)間片輪轉(zhuǎn)調(diào)度多重時(shí)間片循環(huán)調(diào)度操作系統(tǒng)的資源管理(2)——進(jìn)程調(diào)度

q=1和q=4時(shí)的進(jìn)程運(yùn)行情況

下圖示出了時(shí)間片分別為q=1和q=4時(shí)，A、B、C、D、E五個(gè)進(jìn)程的運(yùn)行情況，圖中是否有誤?下圖為q=1和q=4時(shí)各進(jìn)程的平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間。圖中的RR(RoundRobin)表示輪轉(zhuǎn)調(diào)度算法。225.調(diào)度用的進(jìn)程狀態(tài)變遷圖

運(yùn)行首先選