習題課處理機的調(diào)度與死鎖

選擇調(diào)度方式和調(diào)度算法的假設(shè)干準那么一、面向用戶的準那么1．周轉(zhuǎn)時間短2．響應時間快3．截止時間的保證4．優(yōu)先權(quán)準那么二、面向系統(tǒng)的準那么1．系統(tǒng)吞吐量高2．處理機利用率好3．各類資源的平衡利用.衡量標準作業(yè)周轉(zhuǎn)時間如果作業(yè)i提交給系統(tǒng)的時刻是ts，完成時刻是tf，該作業(yè)的周轉(zhuǎn)時間ti為：ti=tf-ts它是作業(yè)在系統(tǒng)里的等待時間與運行時間之和。平均作業(yè)周轉(zhuǎn)時間為了提高系統(tǒng)的性能，要讓假設(shè)干個用戶的平均作業(yè)周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間最小。平均作業(yè)周轉(zhuǎn)時間T=(Σti)/n.衡量標準作業(yè)帶權(quán)周轉(zhuǎn)時間如果作業(yè)i的周轉(zhuǎn)時間為ti，所需運行時間為tk，那么稱wi=ti/tk為該作業(yè)的帶權(quán)周轉(zhuǎn)時間。ti是等待時間與運行時間之和，帶權(quán)周轉(zhuǎn)時間總大于1。平均作業(yè)帶權(quán)周轉(zhuǎn)時間平均作業(yè)帶權(quán)周轉(zhuǎn)時間W=(Σwi)/n.衡量標準響應比作業(yè)進入系統(tǒng)后的等待時間與估計運行時間之比稱作響應比，現(xiàn)定義；響應比＝1+已等待時間/估計運行時間.調(diào)度算法先來先效勞算法最短作業(yè)優(yōu)先算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法時間片輪轉(zhuǎn)法高響應比優(yōu)先調(diào)度算法.調(diào)度算法例：有五個批處理作業(yè)A，B，C，D，E幾乎同時到達一個計算中心，估計的運行時間分別為2，4，6，8，10min，它們的優(yōu)先權(quán)分別為1，2，3，4，5〔5為最高優(yōu)先級〕。請用下面的調(diào)度算法，分別計算作業(yè)的平均周轉(zhuǎn)時間〔忽略作業(yè)的切換開銷〕：優(yōu)先級調(diào)度時間片輪轉(zhuǎn)〔時間片為2min〕FIFO〔作業(yè)的到達順序為C，D，B，E，A〕最短作業(yè)優(yōu)先.調(diào)度算法優(yōu)先級：1018242830==22時間片輪轉(zhuǎn)212202630==18FIFO614182830==19.2短作業(yè)26122030==14.調(diào)度算法例：如下表所示，把作業(yè)交給單道批處理系統(tǒng)，采用最高響應比優(yōu)先調(diào)度算法，分別計算其周轉(zhuǎn)時間T和平均帶權(quán)周轉(zhuǎn)時間W。作業(yè)號1234提交時間/h8.08.68.89.0運行時間/h2.00.60.20.5.調(diào)度算法例：假設(shè)一個系統(tǒng)中有5個進程，它們的到達時間和效勞時間如下表所示，忽略I/O以及其他開銷時間，假設(shè)分別按照先來先效勞〔FCFS〕、非搶占及搶占的短進程優(yōu)先(SPF)、高響應比優(yōu)先〔HRRN〕、時間片輪轉(zhuǎn)〔RR，時間片=1〕、多級反響隊列調(diào)度算法(FB，第i級隊列的時間片=2i-1)以及立即搶占的多級反響隊列調(diào)度算法(FB，第i級隊列的時間片=2i-1)進行CPU調(diào)度，請給出各進程的完成時間、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。.進程到達時間服務時間A03B26C44D65E82.先來先效勞FCFSFirstComeFirstServed短進程優(yōu)先SPF(SPN)ShortestProcessFirst(Next)短作業(yè)優(yōu)先SJFShortestJobFirst高響應比優(yōu)先HRRF(HRRN)HighestResponseRatioFirst(next).SJF算法是非搶占式的，可以改進成搶占式的調(diào)度算法。當一個作業(yè)正在執(zhí)行時，一個新作業(yè)進入就緒狀態(tài)，如果新作業(yè)所需CPU時間比當前正在執(zhí)行的作業(yè)剩余下來還需要的CPU時間短，搶占式短作業(yè)優(yōu)先算法強行趕走當前正在執(zhí)行的作業(yè)，這種方式叫最短剩余時間優(yōu)先〔ShortestRemainingTimeFirst,SRTF〕算法。.