操作系統(tǒng)讀書工程報(bào)告

黑龍江大學(xué)操作系統(tǒng)讀書工程報(bào)告操作系統(tǒng)課程設(shè)計(jì)讀書工程報(bào)告學(xué)期 學(xué)院 學(xué)號(hào) 姓名 基本理論闡述在操作系統(tǒng)中調(diào)度實(shí)質(zhì)上是一種資源的分配，因而調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法。對(duì)于不同的操作系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法，例如，在批處理系統(tǒng)中，為了照顧為數(shù)眾多的短作業(yè)，應(yīng)采用短作業(yè)優(yōu)先的調(diào)度算法；又如在分時(shí)系統(tǒng)中，為了保證系統(tǒng)具有合理的相應(yīng)時(shí)間，應(yīng)采用輪轉(zhuǎn)法進(jìn)行調(diào)度。目前存在的多種調(diào)度算法中，有的使用于作業(yè)調(diào)度，也有的適用于進(jìn)程調(diào)度；但也有些算法既可適用于作業(yè)調(diào)度又適用于進(jìn)程調(diào)度。1.先來先服務(wù)(FCFS)先來先服務(wù)（FCFS,FirstComeFirstServe）是最簡單的調(diào)度算法，按先后順序進(jìn)行調(diào)度。1.1FCFS算法按照作業(yè)提交或進(jìn)程變?yōu)榫途w狀態(tài)的先后次序，分派CPU；當(dāng)前作業(yè)或進(jìn)程占用CPU，直到執(zhí)行完或阻塞，才出讓CPU（非搶占方式）。在作業(yè)或進(jìn)程喚醒后（如I/O完成），并不立即恢復(fù)執(zhí)行，通常等到當(dāng)前作業(yè)或進(jìn)程出讓CPU。最簡單的算法。1.2FCFS的特點(diǎn)比較有利于長作業(yè)，而不利于短作業(yè)。有利于CPU繁忙的作業(yè)，而不利于I/O繁忙的作業(yè)。2.短作業(yè)優(yōu)先短作業(yè)優(yōu)先（SJF,ShortestJobFirst）又稱為“短進(jìn)程優(yōu)先”SPN(ShortestProcessNext)；這是對(duì)FCFS算法的改進(jìn)，其目標(biāo)是減少平均周轉(zhuǎn)時(shí)間。對(duì)預(yù)計(jì)執(zhí)行時(shí)間短的作業(yè)（進(jìn)程）優(yōu)先分派處理機(jī)。通常后來的短作業(yè)不搶先正在執(zhí)行的作業(yè)。2.1SJF的特點(diǎn)(1)優(yōu)點(diǎn)：比FCFS改善平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，縮短作業(yè)的等待時(shí)間；提高系統(tǒng)的吞吐量；(2)缺點(diǎn)：對(duì)長作業(yè)非常不利，可能長時(shí)間得不到執(zhí)行；未能依據(jù)作業(yè)的緊迫程度來劃分執(zhí)行的優(yōu)先級(jí)；難以準(zhǔn)確估計(jì)作業(yè)（進(jìn)程）的執(zhí)行時(shí)間，從而影響調(diào)度性能。2.2SJF的變型“最短剩余時(shí)間優(yōu)先”SRT(ShortestRemainingTime)（允許比當(dāng)前進(jìn)程剩余時(shí)間更短的進(jìn)程來搶占）“最高響應(yīng)比優(yōu)先”HRRN(HighestResponseRatioNext)（響應(yīng)比R=(等待時(shí)間+要求執(zhí)行時(shí)間)/要求執(zhí)行時(shí)間，是FCFS和SJF的折衷）3優(yōu)先級(jí)法優(yōu)先級(jí)算法（PriorityScheduling）是多級(jí)隊(duì)列算法的改進(jìn)，平衡各進(jìn)程對(duì)響應(yīng)時(shí)間的要求。適用于作業(yè)調(diào)度和進(jìn)程調(diào)度，可分成搶先式和非搶先式。3.1靜態(tài)優(yōu)先級(jí)作業(yè)調(diào)度中的靜態(tài)優(yōu)先級(jí)大多按以下原則確定：由用戶自己根據(jù)作業(yè)的緊急程度輸入一個(gè)適當(dāng)?shù)膬?yōu)先級(jí)。由系統(tǒng)或操作員根據(jù)作業(yè)類型指定優(yōu)先級(jí)。系統(tǒng)根據(jù)作業(yè)要求資源情況確定優(yōu)先級(jí)。進(jìn)程的靜態(tài)優(yōu)先級(jí)的確定原則：按進(jìn)程的類型給予不同的優(yōu)先級(jí)。將作業(yè)的情態(tài)優(yōu)先級(jí)作為它所屬進(jìn)程的優(yōu)先級(jí)。3.2動(dòng)態(tài)優(yōu)先級(jí)進(jìn)程的動(dòng)態(tài)優(yōu)先級(jí)一般根據(jù)以下原則確定：根據(jù)進(jìn)程占用有CPU時(shí)間的長短來決定。根據(jù)就緒進(jìn)程等待CPU的時(shí)間長短來決定。4高響應(yīng)比優(yōu)先最高響應(yīng)比優(yōu)先法(HRN，HighestResponse_ratioNext)是對(duì)FCFS方式和SJF方式的一種綜合平衡。FCFS方式只考慮每個(gè)作業(yè)的等待時(shí)間而未考慮執(zhí)行時(shí)間的長短，而SJF方式只考慮執(zhí)行時(shí)間而未考慮等待時(shí)間的長短。因此，這兩種調(diào)度算法在某些極端情況下會(huì)帶來某些不便。HRN調(diào)度策略同時(shí)考慮每個(gè)作業(yè)的等待時(shí)間長短和估計(jì)需要的執(zhí)行時(shí)間長短，從中選出響應(yīng)比最高的作業(yè)投入執(zhí)行。響應(yīng)比R定義如下：R=(W+T)/T=1+W/T其中T為該作業(yè)估計(jì)需要的執(zhí)行時(shí)間，W為作業(yè)在后備狀態(tài)隊(duì)列中的等待時(shí)間。每當(dāng)要進(jìn)行作業(yè)調(diào)度時(shí)，系統(tǒng)計(jì)算每個(gè)作業(yè)的響應(yīng)比，選擇其中R最大者投入執(zhí)行。這樣，即使是長作業(yè)，隨著它等待時(shí)間的增加，W/T也就隨著增加，也就有機(jī)會(huì)獲得調(diào)度執(zhí)行。這種算法是介于FCFS和SJF之間的一種折中算法。由于長作業(yè)也有機(jī)會(huì)投入運(yùn)行，在同一時(shí)間內(nèi)處理的作業(yè)數(shù)顯然要少于SJF法，從而采用HRN方式時(shí)其吞吐量將小于采用SJF法時(shí)的吞吐量。另外，由于每次調(diào)度前要計(jì)算響應(yīng)比，系統(tǒng)開銷也要相應(yīng)增加。5時(shí)間片輪轉(zhuǎn)輪轉(zhuǎn)法(RoundRobin)是讓每個(gè)進(jìn)程在就緒隊(duì)列中的等待時(shí)間與享受服務(wù)的時(shí)間成正比例。將系統(tǒng)中所有的就緒進(jìn)程按照FCFS原則，排成一個(gè)隊(duì)列。每次調(diào)度時(shí)將CPU分派給隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片。時(shí)間片的長度從幾個(gè)ms到幾百ms。在一個(gè)時(shí)間片結(jié)束時(shí)，發(fā)生時(shí)鐘中斷。調(diào)度程序據(jù)此暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾，并通過上下文切換執(zhí)行當(dāng)前的隊(duì)首進(jìn)程。進(jìn)程可以未使用完一個(gè)時(shí)間片，就出讓CPU（如阻塞）。長度的確定時(shí)間片長度變化的影響：過長－>退化為FCFS算法，進(jìn)程在一個(gè)時(shí)間片內(nèi)都執(zhí)行完，響應(yīng)時(shí)間長。過短－>用戶的一次請(qǐng)求需要多個(gè)時(shí)間片才能處理完，上下文切換次數(shù)增加，響應(yīng)時(shí)間長。對(duì)響應(yīng)時(shí)間的要求：T(響應(yīng)時(shí)間)=N(進(jìn)程數(shù)目)*q(時(shí)間片)。就緒進(jìn)程的數(shù)目：數(shù)目越多，時(shí)間片越小系統(tǒng)的處理能力：應(yīng)當(dāng)使用戶輸入通常在一個(gè)時(shí)間片內(nèi)能處理完，否則使響應(yīng)時(shí)間，平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間延長。6多級(jí)反饋隊(duì)列6.1多級(jí)反饋隊(duì)列的原理：1、設(shè)有N個(gè)隊(duì)列（Q1,Q2....QN），其中各個(gè)隊(duì)列對(duì)于處理機(jī)的優(yōu)先級(jí)是不一樣的，也就是說位于各個(gè)隊(duì)列中的作業(yè)(進(jìn)程)的優(yōu)先級(jí)也是不一樣的。一般來說，優(yōu)先級(jí)Priority(Q1)>Priority(Q2)>...>Priority(QN)。怎么講，位于Q1中的任何一個(gè)作業(yè)(進(jìn)程)都要比Q2中的任何一個(gè)作業(yè)(進(jìn)程)相對(duì)于CPU的優(yōu)先級(jí)要高（也就是說，Q1中的作業(yè)一定要比Q2中的作業(yè)先被處理機(jī)調(diào)度），依次類推其它的隊(duì)列。2、對(duì)于某個(gè)特定的隊(duì)列來說，里面是遵循時(shí)間片輪轉(zhuǎn)法。也就是說，位于隊(duì)列Q2中有N個(gè)作業(yè)，它們的運(yùn)行時(shí)間是通過Q2這個(gè)隊(duì)列所設(shè)定的時(shí)間片來確定的（為了便于理解，我們也可以認(rèn)為特定隊(duì)列中的作業(yè)的優(yōu)先級(jí)是按照FCFS來調(diào)度的）。3、各個(gè)隊(duì)列的時(shí)間片是一樣的嗎？不一樣，這就是該算法設(shè)計(jì)的精妙之處。各個(gè)隊(duì)列的時(shí)間片是隨著優(yōu)先級(jí)的增加而減少的，也就是說，優(yōu)先級(jí)越高的隊(duì)列中它的時(shí)間片就越短。同時(shí)，為了便于那些超大作業(yè)的完成，最后一個(gè)隊(duì)列QN(優(yōu)先級(jí)最低的隊(duì)列)的時(shí)間片一般很大(不需要考慮這個(gè)問題)。6.2多級(jí)反饋隊(duì)列調(diào)度算法描述：1、進(jìn)程在進(jìn)入待調(diào)度的隊(duì)列等待時(shí)，首先進(jìn)入優(yōu)先級(jí)最高的Q1等待。2、首先調(diào)度優(yōu)先級(jí)高的隊(duì)列中的進(jìn)程。若高優(yōu)先級(jí)中隊(duì)列中已沒有調(diào)度的進(jìn)程，則調(diào)度次優(yōu)先級(jí)隊(duì)列中的進(jìn)程。例如：Q1,Q2,Q3三個(gè)隊(duì)列，只有在Q1中沒有進(jìn)程等待時(shí)才去調(diào)度Q2，同理，只有Q1,Q2都為空時(shí)才會(huì)去調(diào)度Q3。3、對(duì)于同一個(gè)隊(duì)列中的各個(gè)進(jìn)程，按照時(shí)間片輪轉(zhuǎn)法調(diào)度。比如Q1隊(duì)列的時(shí)間片為N，那么Q1中的作業(yè)在經(jīng)歷了N個(gè)時(shí)間片后若還沒有完成，則進(jìn)入Q2隊(duì)列等待，若Q2的時(shí)間片用完后作業(yè)還不能完成，一直進(jìn)入下一級(jí)隊(duì)列，直至完成。4、在低優(yōu)先級(jí)的隊(duì)列中的進(jìn)程在運(yùn)行時(shí)，又有新到達(dá)的作業(yè)，那么在運(yùn)行完這個(gè)時(shí)間片后，CPU馬上分配給新到達(dá)的作業(yè)（搶占式）。當(dāng)前應(yīng)用現(xiàn)狀linux內(nèi)核的三種調(diào)度方法：1，SCHED_OTHER分時(shí)調(diào)度策略，2，SCHED_FIFO實(shí)時(shí)調(diào)度策略，先到先服務(wù)3，SCHED_RR實(shí)時(shí)調(diào)度策略，時(shí)間片輪轉(zhuǎn)實(shí)時(shí)進(jìn)程將得到優(yōu)先調(diào)用，實(shí)時(shí)進(jìn)程根據(jù)實(shí)時(shí)優(yōu)先級(jí)決定調(diào)度權(quán)值，分時(shí)進(jìn)程則通過nice和counter值決定權(quán)值，nice越小，counter越大，被調(diào)度的概率越大，也就是曾經(jīng)使用了cpu最少的進(jìn)程將會(huì)得到優(yōu)先調(diào)度。SHCED_RR和SCHED_FIFO的不同：當(dāng)采用SHCED_RR策略的進(jìn)程的時(shí)間片用完，系統(tǒng)將重新分配時(shí)間片，并置于就緒隊(duì)列尾。放在隊(duì)列尾保證了所有具有相同優(yōu)先級(jí)的RR任務(wù)的調(diào)度公平。SCHED_FIFO一旦占用cpu則一直運(yùn)行。一直運(yùn)行直到有更高優(yōu)先級(jí)任務(wù)到達(dá)或自己放棄。如果有相同優(yōu)先級(jí)的實(shí)時(shí)進(jìn)程（根據(jù)優(yōu)先級(jí)計(jì)算的調(diào)度權(quán)值是一樣的）已經(jīng)準(zhǔn)備好，F(xiàn)IFO時(shí)必須等待該進(jìn)程主動(dòng)放棄后才可以運(yùn)行這個(gè)優(yōu)先級(jí)相同的任務(wù)。而RR可以讓每個(gè)任務(wù)都執(zhí)行一段時(shí)間。相同點(diǎn)：RR和FIFO都只用于實(shí)時(shí)任務(wù)。創(chuàng)建時(shí)優(yōu)先級(jí)大于0(1-99)。按照可搶占優(yōu)先級(jí)調(diào)度算法進(jìn)行。就緒態(tài)的實(shí)時(shí)任務(wù)立即搶占非實(shí)時(shí)任務(wù)。所有任務(wù)都采用linux分時(shí)調(diào)度策略時(shí)。1，創(chuàng)建任務(wù)指定采用分時(shí)調(diào)度策略，并指定優(yōu)先級(jí)nice值(-20~19)。2，將根據(jù)每個(gè)任務(wù)的nice值確定在cpu上的執(zhí)行時(shí)間(counter)。3，如果沒有等待資源，則將該任務(wù)加入到就緒隊(duì)列中。4，調(diào)度程序遍歷就緒隊(duì)列中的任務(wù)，通過對(duì)每個(gè)任務(wù)動(dòng)態(tài)優(yōu)先級(jí)的計(jì)算(counter+20-nice)結(jié)果，選擇計(jì)算結(jié)果最大的一個(gè)去運(yùn)行，當(dāng)這個(gè)時(shí)間片用完后(counter減至0)或者主動(dòng)放棄cpu時(shí)，該任務(wù)將被放在就緒隊(duì)列末尾(時(shí)間片用完)或等待隊(duì)列(因等待資源而放棄cpu)中。5，此時(shí)調(diào)度程序重復(fù)上面計(jì)算過程，轉(zhuǎn)到第4步。6，當(dāng)調(diào)度程序發(fā)現(xiàn)所有就緒任務(wù)計(jì)算所得的權(quán)值都為不大于0時(shí)，重復(fù)第2步。個(gè)人對(duì)相關(guān)內(nèi)容的體會(huì)通過讀書學(xué)習(xí)學(xué)到了很多的東西，對(duì)于進(jìn)程和作業(yè)的調(diào)度并沒有最好的算法，只有更適合，例如短作業(yè)優(yōu)先，它雖然能在一定程度上照顧短進(jìn)程和短作業(yè)但是如果有較多的短作業(yè)時(shí)長作業(yè)就會(huì)較長時(shí)間地等待，從而有可能造成“饑餓”等待的現(xiàn)象。而如果“饑餓”的進(jìn)程等待到一定的程度后即使進(jìn)程所賦予的任務(wù)完成也不再具有實(shí)際的意義，即為該進(jìn)程已經(jīng)被“餓死”。高響應(yīng)比調(diào)度算法解決了短作業(yè)的缺點(diǎn)，既照顧了短作業(yè)又考慮到了作業(yè)到達(dá)的先后次序，但是每次進(jìn)行調(diào)度前都要進(jìn)行計(jì)算響應(yīng)比，因此也會(huì)造成一定的時(shí)間開銷，尤其對(duì)于較多的進(jìn)程時(shí)時(shí)間的開銷還是很大的。所有的處理機(jī)調(diào)度里面可能比較好的就是多級(jí)反饋隊(duì)列。我在該部分時(shí)也遇到了不少的困難，一個(gè)好的程序不僅要有較高的效率對(duì)容錯(cuò)處理上也要考慮，尤其是在用戶輸入數(shù)據(jù)上，如果用戶輸入的是的是非法的數(shù)據(jù)該怎么處理，如果輸入的文件不存在又該怎么做。最終經(jīng)過不停的實(shí)驗(yàn)調(diào)試后成功了，而且對(duì)于多級(jí)反饋隊(duì)列來說，它不僅柔和了先來先服務(wù)，優(yōu)先權(quán)調(diào)度還有時(shí)間片輪轉(zhuǎn)，例如只有一個(gè)隊(duì)列時(shí)它便是時(shí)間片輪轉(zhuǎn)，當(dāng)時(shí)間片調(diào)整到很大時(shí)又退化到先來先服務(wù)等等。設(shè)計(jì)與實(shí)現(xiàn)思路進(jìn)程調(diào)度各個(gè)數(shù)據(jù)結(jié)構(gòu)首先是對(duì)于進(jìn)程或者說作業(yè)的結(jié)構(gòu)體PCB設(shè)計(jì)，要考慮以后的各個(gè)算法中可能會(huì)用到的需要保存的數(shù)據(jù)，例如進(jìn)程名稱name，進(jìn)程的到達(dá)時(shí)間arrive，進(jìn)程需要服務(wù)的時(shí)間等等，如下即為PCB結(jié)構(gòu)體：typedefstructPCB{stringname;intarrive; intneed; intserver; intstart; intpriority; intfinish; intcycletime; floatweight_cyltime;};其中name為進(jìn)程或作業(yè)名稱；arrive為進(jìn)程或作業(yè)到達(dá)時(shí)間；need為需要服務(wù)的時(shí)間；server為進(jìn)程或作業(yè)已經(jīng)服務(wù)的時(shí)間；start為進(jìn)程或作業(yè)開始時(shí)間，priority為優(yōu)先權(quán)從小到大，finish為進(jìn)程或作業(yè)完成時(shí)間；cycletime為進(jìn)程或作業(yè)的周轉(zhuǎn)時(shí)間，weight_cycletime為進(jìn)程或作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間?；恜rocess類：是其它各個(gè)調(diào)度算法的基類，其他各調(diào)度算法類均由process類派生出來，應(yīng)該有私有成員aver_cycle為平均周轉(zhuǎn)時(shí)間，aver_wct為平均帶權(quán)周轉(zhuǎn)時(shí)間；另外由于FCFS和SJF的調(diào)度上相差并不大，一個(gè)是要獲取進(jìn)程到達(dá)早未服務(wù)的一個(gè)是獲取進(jìn)程到達(dá)而未服務(wù)的因此用get_nextNum（inttime）為提供FCFS和SJF使用獲取下一個(gè)要調(diào)度的作業(yè)。對(duì)于process類基本結(jié)構(gòu)定義如下：classprocess{private: floataver_cycle; floataver_wct;protected: vector<PCB>vproc; voidcalculate_all(); voidresetData();public: process(void); ~process(void); voidadd_process(stringn,inta,intse,intst); PCBget_process_at(intnum); intget_vector_num(vector<PCB>v,stringname); intget_nextNum(inttime); voidshow();};用UML中的類圖表示如下圖所示：圖1process類圖以下為實(shí)現(xiàn)調(diào)度算法的各個(gè)類：先來先服務(wù)FCFS先來先服務(wù)(FirstComeFirstServer)，繼承自process類，除了父類中的函數(shù)和變量外還有使用文件載入數(shù)據(jù)的函數(shù)init_data(file[])；其次便是實(shí)現(xiàn)先來先服務(wù)的調(diào)度算schedul()；FCFS類的定義：classFCFS:publicprocess{public: voidinit_data(charfile[]); voidschedul();};圖2FCFS類圖短作業(yè)優(yōu)先SJF短作業(yè)優(yōu)先(ShortJobFirst)，包含resetPriority()重新設(shè)置優(yōu)先級(jí)，init_data(file)載入數(shù)據(jù)函數(shù)，schedul_grab()搶占調(diào)度，schedul_ngrab()搶占調(diào)度(即最短剩余作業(yè)優(yōu)先調(diào)度算法)；SJF類的定義：classSJF:publicprocess{protected: voidresetPriority();public: voidinit_data(charfile[]); voidschedul_grab();//搶占 voidschedul_ngrab();//非搶占 voidschedul();//調(diào)度算法 };圖3SJF類圖高響應(yīng)比優(yōu)先HRN高響應(yīng)比優(yōu)先(HighestResponse_ratioNext)，vector<float>ratio為與各個(gè)進(jìn)程相對(duì)應(yīng)的相應(yīng)比，除了與FCFS，SJF類似的載入數(shù)據(jù)init_data(file[])外還有calculate_ratio(inttime)即根據(jù)時(shí)間計(jì)算各個(gè)作業(yè)的響應(yīng)比；get_nextNum(inttime,intt)為根據(jù)時(shí)間獲取下一個(gè)要調(diào)度的作業(yè)；shedul_grab()為搶占，shedul_ngrab()為非搶占；HRN類的定義：classHRN:publicprocess{private: vector<float>ratio;//響應(yīng)比protected: voidcalculate_ratio(inttime); intget_nextNum(inttime,intt);public: voidinit_data(charfile[]); voidschedul_grab();//搶占 voidschedul_ngrab();//非搶占 voidschedul();//調(diào)度算法};圖2HRN類圖時(shí)間片輪轉(zhuǎn)RR時(shí)間片輪轉(zhuǎn)調(diào)度算法(RoundRobin)，vector<PCB>ready為已到達(dá)的就緒進(jìn)程；timeslice為輪轉(zhuǎn)的時(shí)間片；tradition()為傳統(tǒng)高響應(yīng)比的調(diào)度算法，而feed_back()為反饋的調(diào)度算法，這兩種調(diào)度算法分別在schedule()中調(diào)用；RR類的定義：classRR:publicprocess{private: vector<PCB>ready; vector<string>line; inttimeslice;//時(shí)間片protected: voidcheck_arrive(inttime);public: voidinit_data(charfile[]); voidtraditon();//傳統(tǒng) voidfeed_back();//反饋 voidschedule();};圖2RR類圖多級(jí)反饋隊(duì)列MFQ多級(jí)反饋隊(duì)列(Multi-levelFeedbackQueues)，私有成員queNum為隊(duì)列的數(shù)量；timeslice為第一個(gè)隊(duì)列的時(shí)間片，其余隊(duì)列的時(shí)間片依次成倍增長；bool*record為記錄對(duì)應(yīng)存儲(chǔ)在vector<PCB>vproc中的進(jìn)程是否已經(jīng)進(jìn)入隊(duì)列當(dāng)中。Release()為釋放鏈表當(dāng)中的各個(gè)結(jié)點(diǎn)及record；queue_empty()用來檢測所有的隊(duì)列里是否已經(jīng)為空；check_arrive(inttime)為檢查在time時(shí)刻到達(dá)的進(jìn)程若已經(jīng)到達(dá)則返回true，并將到達(dá)的進(jìn)程放入第一個(gè)隊(duì)列當(dāng)中。MFQ類的定義：structqueue{ vector<PCB>v; intnum; structqueue*next;};classMFQ:publicprocess{private: intqueNum; inttimeslice;//第一個(gè)隊(duì)列的時(shí)間片 structqueue*execute;//所有的隊(duì)列，以鏈表的形式存放 bool*record;//用于記錄對(duì)應(yīng)的進(jìn)程是否調(diào)度過被protected: boolqueue_empty();//檢查隊(duì)列是否全部為空 voidrelease();//防止內(nèi)存泄露 voidpush_to_next(queue*&p,vector<PCB>::iterator&q);//將q放入p的下一隊(duì)列里public: voidinit_data(charfile[]); boolcheck_arrive(inttime); voidschedule(); voidinit_queue();//初始化隊(duì)列 voidshow_queue(); };圖2MFQ類圖總體設(shè)計(jì)的類圖如下所示：類圖調(diào)度算法FCFS：先來先服務(wù)調(diào)度算法，每次只需找到已經(jīng)到達(dá)的而未服務(wù)進(jìn)程中到達(dá)時(shí)間最早的一個(gè)即可，令p->server=p->need，time+=p->need再進(jìn)入下一次循環(huán)，直到所有的進(jìn)程執(zhí)行完畢再顯示數(shù)據(jù)即可。SJF：短作業(yè)優(yōu)先算法，是對(duì)短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。先從后備隊(duì)列選出一個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)。如果是非搶占的則一直等到進(jìn)程運(yùn)行完畢再進(jìn)行選擇下一個(gè)進(jìn)程，如果是搶占的即最短剩余作業(yè)優(yōu)先則當(dāng)一個(gè)作業(yè)正在運(yùn)行中若檢測到有更短作業(yè)則需要暫?，F(xiàn)在的作業(yè)改換更短的作業(yè)運(yùn)行；HRN：高響應(yīng)比優(yōu)先調(diào)度，當(dāng)需要選擇進(jìn)程時(shí)需要選擇相應(yīng)比高的進(jìn)程，其優(yōu)先權(quán)變化為優(yōu)先權(quán)=（等待時(shí)間+要求服務(wù)的時(shí)間）/要求服務(wù)的時(shí)間對(duì)于非搶占的調(diào)度算法類似短作業(yè)優(yōu)先中的調(diào)度，而搶占的則需要時(shí)間每加一就檢查一遍是否有進(jìn)程的優(yōu)先權(quán)大于當(dāng)前進(jìn)程，對(duì)于搶占的調(diào)度算法其流程圖如下所示：RR：時(shí)間片輪轉(zhuǎn)調(diào)度算法，將所有的就緒進(jìn)程按先來先服務(wù)的原則排成一個(gè)隊(duì)列，每次調(diào)度時(shí)把CPU分配給隊(duì)首進(jìn)程，令其執(zhí)行一個(gè)時(shí)間片，當(dāng)時(shí)間片用完時(shí)