模擬進(jìn)程調(diào)度算法課程設(shè)計(jì)(20210426143513)

1、課程概述11 設(shè)計(jì)構(gòu)想程序能夠完成以下操作：創(chuàng)建進(jìn)程：先輸入進(jìn)程的數(shù)目，再一次輸入每個(gè)進(jìn)程的進(jìn)程名、 運(yùn)行總時(shí)間和優(yōu)先級(jí)，先到達(dá)的先輸入；進(jìn)程調(diào)度：進(jìn)程創(chuàng)建完成后就選擇進(jìn)程調(diào)度算法，并 單步執(zhí)行，每次執(zhí)行的結(jié)果都從屏幕上輸出來。1.2.需求分析在多道程序環(huán)境下，主存中有著多個(gè)進(jìn)程，其數(shù)目往往多于處理機(jī)數(shù)目，要使這多個(gè)進(jìn)程能夠 并發(fā)地執(zhí)行，這就要求系統(tǒng)能按某種算法，動(dòng)態(tài)地把處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)程，使 之執(zhí)行。分配處理機(jī)的任務(wù)是由處理機(jī)調(diào)度程序完成的。由于處理機(jī)是最重要的計(jì)算機(jī)資源， 提高處理機(jī)的利用率及改善系統(tǒng)必（吞吐量、響應(yīng)時(shí)間），在很大程度上取決于處理機(jī)調(diào)度性 能的好壞，因而，處理

2、機(jī)調(diào)度便成為操作系統(tǒng)設(shè)計(jì)的中心問題之一。本次實(shí)驗(yàn)在VC+6.0環(huán)境下 實(shí)現(xiàn)先來先服務(wù)調(diào)度算法，短作業(yè)優(yōu)先調(diào)度算法，高優(yōu)先權(quán)調(diào)度算法，時(shí)間片輪轉(zhuǎn)調(diào)度算法和 多級(jí)反饋隊(duì)列調(diào)度算法。13理論依據(jù)為了描述和管制進(jìn)程的運(yùn)行，系統(tǒng)為每個(gè)進(jìn)程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)一一進(jìn)程控制塊PCB（Process Control Block） ,PCB中記錄了操作系統(tǒng)所需的、用于描述進(jìn)程的當(dāng)前情況以及控制進(jìn) 程運(yùn)行的全部信息，系統(tǒng)總是通過PCB對(duì)進(jìn)程進(jìn)行控制，亦即，系統(tǒng)是根據(jù)進(jìn)程的PCB而不是 任何別的什么而感知進(jìn)程的存在的，PCB是進(jìn)程存在的惟一標(biāo)志。本次課程設(shè)計(jì)用結(jié)構(gòu)體 Process代替PCB的功能。1.4.課程任務(wù)一

3、、用C語言（或C+）編程實(shí)現(xiàn)操作模擬操作系統(tǒng)進(jìn)程調(diào)度子系統(tǒng)的基本功能；運(yùn)用多種算 法實(shí)現(xiàn)對(duì)進(jìn)程的模擬調(diào)度。二、通過編寫程序?qū)崿F(xiàn)進(jìn)程或作業(yè)先來先服務(wù)、高優(yōu)先權(quán)、按時(shí)間片輪轉(zhuǎn)、短作業(yè)優(yōu)先、多級(jí) 反饋隊(duì)列調(diào)度算法，使學(xué)生進(jìn)一步掌握進(jìn)程調(diào)度的概念和算法，加深對(duì)處理機(jī)分配的理 解。三、實(shí)現(xiàn)用戶界面的開發(fā)15 功能模塊分析:1、進(jìn)程概念：進(jìn)程是被獨(dú)立分配資源的最小單位。進(jìn)程是動(dòng)態(tài)概念，必須程序運(yùn)行才有 進(jìn)程的產(chǎn)生。2、進(jìn)程的狀態(tài)模型：(1) 運(yùn)行：進(jìn)程已獲得處理機(jī)，當(dāng)前處于運(yùn)行狀態(tài)。(2) 就緒：進(jìn)程已經(jīng)準(zhǔn)備好，一旦有處理器就可運(yùn)行。3、處理機(jī)調(diào)度：在多道程序設(shè)計(jì)系統(tǒng)中，內(nèi)存中有多道程序運(yùn)行，他們相互爭奪

4、處理機(jī) 這一重要的資源。處理機(jī)調(diào)度就是從就緒隊(duì)列中，按照一定的算法選擇一個(gè)進(jìn)程并將處 理機(jī)分配給它運(yùn)行，以實(shí)現(xiàn)進(jìn)程并發(fā)地執(zhí)行。4、進(jìn)程調(diào)度算法的功能：記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況選擇占有處理機(jī)的進(jìn)程進(jìn)行進(jìn)程的上下文切換5、進(jìn)程調(diào)度的算法：(1) 先來先服務(wù)算法：如果早就緒的進(jìn)程排在就緒隊(duì)列的前而，遲就緒的進(jìn)程排在就緒 隊(duì)列的后面，那么先來先服務(wù)總是把當(dāng)前處于就緒隊(duì)列之首的那個(gè)進(jìn)程調(diào)度到運(yùn) 行狀態(tài)。(2) 優(yōu)先數(shù)算法：即進(jìn)程的執(zhí)行順序由高優(yōu)先級(jí)到低優(yōu)先級(jí)。系統(tǒng)或用戶按某種原則為 進(jìn)程指定一個(gè)優(yōu)先級(jí)來表示該進(jìn)程所享有的確調(diào)度優(yōu)先權(quán)。該算法核心是確定進(jìn) 程的優(yōu)先級(jí)。(3) 時(shí)間片輪轉(zhuǎn)算法：固定時(shí)間片

5、，每個(gè)進(jìn)程在執(zhí)行一個(gè)時(shí)間片后，輪到下一進(jìn)程執(zhí) 行，知道所有的進(jìn)程執(zhí)行完畢。處理器同一個(gè)時(shí)間只能處理一個(gè)任務(wù)。處理器在 處理多任務(wù)的時(shí)候，就要看請(qǐng)求的時(shí)間順序，如果時(shí)間一致，就要進(jìn)行預(yù)測(cè)。挑 到一個(gè)任務(wù)后，需要若干步驟才能做完，這些步驟中有些需要處理器參與，有些 不需要(如磁盤控制器的存儲(chǔ)過程)。不需要處理器處理的時(shí)候，這部分時(shí)間就 要分配給其他的進(jìn)程。原來的進(jìn)程就要處于等待的時(shí)間段上。經(jīng)過周密分配時(shí) 間，宏觀上就象是多個(gè)任務(wù)一起運(yùn)行一樣，但微觀上是有先后的，就是時(shí)間片輪 換。(4) 多級(jí)反饋隊(duì)列法：又稱反饋循環(huán)隊(duì)列或多隊(duì)列策略，主要思想是將就緒進(jìn)程分為 兩級(jí)或多級(jí)，系統(tǒng)相應(yīng)建立兩個(gè)或多個(gè)就緒進(jìn)

6、程隊(duì)列，較高優(yōu)先級(jí)的隊(duì)列一般分 配給較短的時(shí)間片。處理器調(diào)度先從高級(jí)就緒進(jìn)程隊(duì)列中選取可占有處理器的進(jìn) 程，只有在選不到時(shí)，才從較低級(jí)的就緒進(jìn)程隊(duì)列中選取。(5) 短作業(yè)優(yōu)先法：對(duì)短進(jìn)程優(yōu)先調(diào)度的算法，它是從后備隊(duì)列中選擇一個(gè)或者若干個(gè) 進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被 阻塞放棄處理機(jī)時(shí)再重新調(diào)度。設(shè)計(jì)方案2.1 先來先服務(wù)調(diào)度2.1.1. 算法思想先來先服務(wù)調(diào)度算法的思想是按照進(jìn)程進(jìn)入就緒隊(duì)列的先后順序調(diào)度并分配處理機(jī)執(zhí)行。 先來先服務(wù)調(diào)度算法是一種不可搶占的算法，先進(jìn)入就緒隊(duì)列的進(jìn)程，先被處理機(jī)運(yùn)行。一旦 一個(gè)進(jìn)程占有了處理機(jī)，它就一直運(yùn)行下去，直到該

7、進(jìn)程完成工作或者因?yàn)榈却呈录荒?繼續(xù)運(yùn)行時(shí)才釋放處理機(jī)。2.1.2. 算法流程圖圖1先來先服務(wù)算法流程圖2.1.3.程序代碼#include #include #include typedef struct nodename, run-cputime, run-starttime, run-needtime, run-state); /* 輸出執(zhí)行的進(jìn)程的信息 */ p=ready;whilefp != NULL) name, p-cputime, p-starttime, p needtime, p-state); /*輸出就緒進(jìn)程的信息*/ p=p-next;p=finish; wh

8、ile(p != NULL)printf( %-10s%-10d%-10s%-10d %cn p-name, p-cputime,p-starttime, pneedtim巳 p-state); /* 輸出結(jié)束隊(duì)列的信息 */ p=p-next;getchar(); /*使用getcharO函數(shù)可以讓輸出時(shí)停留畫面，等待人按回車?yán)^續(xù)*/void insertfPCB *q)/*插入新進(jìn)程，把進(jìn)程按進(jìn)程到來時(shí)間大小排序PCB *pl/s,*r;int b;s二q;/*指針s指向新要插入的進(jìn)程*/pl=ready; /*指針pl指向原來的進(jìn)程隊(duì)列的隊(duì)首*/ r=pl; /*使用 指針r是指向pl前

9、而的進(jìn)程*/ b=l;while(pl!=NULL)&b) if(strcmp(pl-starttime,s-starttime)O r=pl; pl=p next; /*新進(jìn)程的開始時(shí)間大，則pl指向下一個(gè)進(jìn)程繼續(xù)比else b=0;if(r!=pl)next=s; s-next=pl; /*新進(jìn)程找到位置，插在r和pl之間*/ elsenext二pl; ready二s;/*新進(jìn)程的開始時(shí)間按最小，插在隊(duì)首，并修改就緒隊(duì)首void create0name); /* 輸入進(jìn)程名 */ scanf(%d&p-needtime); /* 輸入進(jìn)程要求運(yùn) 行時(shí)間 */ scanf(%s/p-star

10、ttime); /輸入進(jìn)程開始時(shí)間 p-cputime=O; pstateW; /*表示就緒隊(duì)列中未在隊(duì)首先執(zhí)行，但也是就緒狀態(tài)*/ if (ready!=NULL)insert(p); /*就緒隊(duì)首不為NULL ,插入新進(jìn)程*/else/*否則先插在側(cè)“前*/pnext=ready; ready二p;W)；printff Display is going to start:IVprintQ;getcharQ;run=ready; /*隊(duì)列排好，run指向就緒隊(duì)列隊(duì)首*/ ready=ready-next; /*ready指向下一 個(gè)進(jìn)程*/ rimstate=R; /*隊(duì)首進(jìn)程的狀態(tài)為就緒7

11、void FCFS0while (run != NULL) cputime+ru n needtime;runneedtime=O; run-next=finish; finish = run; run-state=E； run = NULL; iffready != NULL) (run = ready; run-state=R; ready=readynext; print。；void mainQprintf(,rPlease enter the total number of PCB:nir); scanf(n%dr&N);create0；/*模擬創(chuàng)建進(jìn)程，并輸入相關(guān)信息*/FCFSQ；

12、 /*先來先服務(wù)調(diào)度算法*/2丄4 測(cè)試結(jié)果及說明首先輸入進(jìn)程個(gè)數(shù)（為5個(gè)），這里命名為ABCDE,然后分別輸入運(yùn)行時(shí)間和開始時(shí)間所有進(jìn)程都在隊(duì)列中，并都處于等待狀態(tài)其中一個(gè)進(jìn)程執(zhí)行完畢所有進(jìn)程都執(zhí)行完畢2.2優(yōu)先級(jí)調(diào)度2.2.1. 算法思想進(jìn)程的執(zhí)行順序由高優(yōu)先級(jí)到低優(yōu)先級(jí)，系統(tǒng)或用戶按某種原則為進(jìn)程指定一個(gè)優(yōu)先級(jí)來表示該進(jìn)程所享有的確調(diào)度該算法核心是確定進(jìn)程的優(yōu)先 優(yōu)先權(quán)級(jí)。2.2.2. 算法流程圖圖2優(yōu)先級(jí)調(diào)度流程圖2.2.3. 程序代碼#include #include #include typedef struct node char name10; /* int prio; /*

13、int cputime; /* int needtime; /* char state; /* struct node *next; /* PCB;PCB *ready/run*finish; int N;進(jìn)程名*/ 優(yōu)先數(shù)*/ 占用cpu時(shí)間*/ 要求運(yùn)行時(shí)間*/ 狀態(tài)*/指針*/void prt() /* namelrun-cputimelrun-need time,ru prio,run-state;/*輸出執(zhí)行的進(jìn)程的信息*/p=ready;while(p!二 NULL)printff %-10s%-10d%-10d%-10d %cnp-namelp-cputimelp-needtim

14、e, p-prio;p-state); /*輸出就緒進(jìn)程的信息*/p=pnext; p=finish;while(p!二NULL) printfC %-10s%-10d%-10d%lOd %cn;p-namelp-cputimelp-needtim e,pprio,pstate); /* 輸出結(jié)束隊(duì) 列的信息*/p=pnext;getchar()； /*使用getcharf)函數(shù)可以讓輸出時(shí)停留ill面,等待人按回 車?yán)^續(xù)*/void insert(PCB *q) /*插入新進(jìn)程，把進(jìn)程按優(yōu)先數(shù)大小排序*/ PCB *pl *s/r;int b;s二q； /*指針s指向新要插入的進(jìn)程*/pl二

15、ready; /*指針pl指向原來的進(jìn)程隊(duì)列的隊(duì)背*/r=pl; /*枝用指針r是指向pl前面的進(jìn)程*/b二1;while(pl!二 NULL)&b) if(pl-prio=s-prio r=pl;pl=pl-next;小，則pl指向下一個(gè)進(jìn)程/*新進(jìn)程的優(yōu)先數(shù)新進(jìn)程找 繼續(xù)比 */ elseb二0;翡上pl)r-nextnegl;/*pl之到位置，插在和新進(jìn)程的 else snext二pl; remdy二s; /* 首，并優(yōu)先數(shù)最大，插在隊(duì)修改就緒隊(duì)首ready指針*/void create (J PCB *p;int i;ready二NULL; run二NULL; finish=NULL;

16、 printffPlease enter the name and time and priority of PCB:nJ；/*輸入進(jìn)程名、運(yùn)彳亍時(shí)間和優(yōu)先級(jí)*/ for(i二0;ivN;i+)p=(PCB *)malloc(sizeof(PCB); /* 為薪進(jìn)程開辟空間 */ scanf(%sr,/p-name); /* 輸入錘程名 */scanf(%d,&p-needtime); /*輸入進(jìn)程要求運(yùn)行時(shí)間*/ scanf(%d&p-prio; /* 輸入進(jìn)程優(yōu)先數(shù) */ p-cputime=O; p-state=fWr; /*表示就緒隊(duì)列中未在隊(duì)首先執(zhí)行，但也是就緒狀態(tài)就緒隊(duì)首不為NUL

17、L,插入新*/ if (ready!二NULL) insertfp; /* 進(jìn)程else p-next=ready; ready=p; /* printff Displ睹員誨 NSL15術(shù)更/ )； 廣廠 1111 Xa 廠、1v-v r n II I TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT y*%1 y-% I I 1 V*! 1 Vy CJ f| T/*隊(duì)列排好，run指向就緒隊(duì)列隊(duì)首*/ ready=ready-next; /*ready指向下 一個(gè)進(jìn)程，這樣當(dāng)進(jìn)程執(zhí)行時(shí)如果優(yōu)先數(shù)小于其他的進(jìn)程，應(yīng)該先進(jìn) 行優(yōu)先數(shù)最大的進(jìn)程run-

18、state=rRf; /*隊(duì)首進(jìn)程的狀態(tài)為就緒*/ void prioQ while(run!=NULLrun-cputime=run-cputime+1;/*run needtime 二 ru n needtimel;runprio二runpriol; /* if(run-needtime=O) /* run-next=finish;finish=run; run-state=rEr; run二NULL; if (ready!二NULL)運(yùn)行一次cpu占用時(shí)間加一 /* 7運(yùn)行一次要求運(yùn)行時(shí)間減一 V 運(yùn)行一次優(yōu)先數(shù)減一 */若要求運(yùn) 行時(shí)間為0時(shí)*/*退岀隊(duì)列*/為結(jié)束進(jìn)程的隊(duì)/*fini

19、s列*/修改狀態(tài)為結(jié)束*/釋放runh指軒*/*創(chuàng)建新就緒隊(duì)列的頭指針*/ run=ready; runstmte二R; ready=ready-next; elseif(ready!二 NULL)& (run-prioprioJ/*隊(duì)首進(jìn)程的優(yōu)先數(shù)比它下一個(gè)小，且下一個(gè)進(jìn)程不為NULL時(shí)執(zhí) 行*/ run-state=,Wr;run-next=NULL; /*隊(duì)首進(jìn)程退出進(jìn)程隊(duì)列*/在進(jìn)程隊(duì)列insert(run); /*中重新插入原來的隊(duì)首進(jìn)程*/重新置run=ready; /*就緒隊(duì)列的頭指針*/run-state=,R,;ready=readynext; prt(); void mai

20、nQ printffPlease enter the total number of PCB:n； scanf(n%d,&N);create()； /*模擬創(chuàng)建進(jìn)程，并輸入相關(guān)信息7 prio(； /*優(yōu)先數(shù)調(diào)度算 法*/224.測(cè)試結(jié)果及說明優(yōu)先級(jí)調(diào)度算法運(yùn)行情況如圖1,圖2,圖3,圖4所示圖1輸入進(jìn)程塊的圖2輸入每個(gè)進(jìn)程的名稱、時(shí)間、優(yōu)先級(jí)圖3.輸入所有的進(jìn)程的相關(guān)信息圖4所有進(jìn)程調(diào)度算法完成2.3 時(shí)間片輪轉(zhuǎn)調(diào)度2.3.1. 算法思想所有就緒進(jìn)程按先來先服務(wù)的原則排成一個(gè)隊(duì)列，將新來的進(jìn)程 加到就緒對(duì)列的末尾，每當(dāng)執(zhí)行進(jìn)程調(diào)度時(shí)，總是把處理機(jī)分配給 隊(duì)首的進(jìn)程，各進(jìn)程占用CPU的時(shí)間片相

21、同。也就是說CPU的處理 時(shí)間劃分成一個(gè)個(gè)相同的時(shí)間片，就緒隊(duì)列的所有進(jìn)程輪流運(yùn)行一個(gè) 時(shí)間片。當(dāng)一個(gè)時(shí)間片結(jié)束時(shí)，如果運(yùn)行進(jìn)程用完它的時(shí)間片后還 未完成，就強(qiáng)迫運(yùn)行進(jìn)程讓出CPU,就把它送回到就緒隊(duì)列的末尾， 等待下一次調(diào)度。同時(shí)，進(jìn)程調(diào)度又去選擇就緒隊(duì)列中的隊(duì)首進(jìn)程， 分配給它一時(shí)間片，以投入運(yùn)行。直至所有的進(jìn)程運(yùn)行完畢。2.3.2. 算法流程圖2.3.3. 程序代碼#inelude #include #include typed efstruct node char name10; /* 進(jìn)程名 */int count;/*計(jì)數(shù)器，判斷是否二時(shí)間片的大小*/int eputime; in

22、t need佈占;曲朋曲t劇 struct node *next; */ /* 要求運(yùn)行時(shí)間*/*狀態(tài)=7/*指針*/PCB;PCB *ready,*run/finish/tail; /* 就緒執(zhí)行結(jié)束 尾指針 */ int N,round;void prt() /*輸出函數(shù)，可以方便看到進(jìn)程執(zhí)行的演*/示name/run-cputime/run-needti me/run-state); /* 輸出執(zhí)行的進(jìn)程的信息 */ p=ready;while(p!二 NULL)name/p-cputime/p-needtime/p-state);/*輸岀就緒進(jìn)程的信息*/p=p-next;p=fini

23、sh;while(p!二 NULL)name,p-cputime/p-needtime/p- state); /*輸出結(jié)束隊(duì)列的信息*/p=p-next;getcharO；void insert(PCB *q) /*在隊(duì)尾插入新的進(jìn)程*/PCB *p;p 二 ready;while(p-next!=NULL) next;tail=p;tail-next=q; q-next=NULL;void create0name); /* 輸入進(jìn)程名 */scanf(,%d,&p-needtime; /* 輸入進(jìn)程要求運(yùn)行時(shí)間 */ p-cputime=O; pstateW/*表示就緒隊(duì)列中未在隊(duì)首先執(zhí)行，

24、但也是就緒狀態(tài)*/if (ready!二NULL) insert(p); /* 就緒隊(duì)首不為 NULL ,插入新進(jìn)程 */ elsepnext=re3dy; ready=p; tail=p;printffDisplay is going to start:W)；PM；getcharO；run=ready; /*隊(duì)列排好，run指向就緒隊(duì)列隊(duì)首*/ ready=ready-next; /*ready指向下一個(gè) 進(jìn)程*/run-state=,R;/*隊(duì)首進(jìn)程的狀態(tài)為就緒*/ void countQwhile(run!=NULL)next=finish;finish二run; run-state=E

25、; run=NULL;run-cputime=run-cputime+1; /* 運(yùn)行一次 cpu 占用時(shí)間加一 */ run-needtime=run-needtime-l; /* 運(yùn)行一次要求運(yùn)行時(shí)間減一 */ run-count=run-count+l; /* 運(yùn)行一次計(jì)數(shù)器加一 */ if(run-needtime=O) /*右要求運(yùn)彳亍時(shí)間為時(shí)*/*退出隊(duì)列*/*finish為結(jié)束進(jìn)程的隊(duì)列*/*修改狀態(tài)為結(jié)束*/*釋放run指針*/if (ready!二NULL)/*創(chuàng)建新就緒隊(duì)列的頭指針*/nin=ready; ruristate二R; ready=readynext;elsei

26、f(run-count=round) /* 如果時(shí)間片到 */run-count=0; /* 計(jì)數(shù)器置 0*/ if(ready!=NULL /* 如就緒隊(duì)列 不空*/state=W,;insert(run); /*在進(jìn)程隊(duì)列中重新插入原來進(jìn)程，插入隊(duì)尾7run=ready; /*重新置就緒隊(duì)列的頭指針*/ run-state=,R,;void mainO next;PM；printffPlease enter the total number of PCB:nJ; scanf(%d,&N); create()； /*模擬創(chuàng)建進(jìn)程，并輸入相關(guān)信息*/ count。; /*優(yōu)先數(shù)調(diào)度算法 723

27、4測(cè)試結(jié)果及說明時(shí)間片輪轉(zhuǎn)調(diào)度算法運(yùn)行情況如，圖圖2,圖3所示圖1所有的進(jìn)程都在隊(duì)列中圖2其中一個(gè)進(jìn)程執(zhí)行完畢圖4所有的進(jìn)程都執(zhí)行完畢2.4.多級(jí)反饋隊(duì)列調(diào)度2.4.1算法思想允許進(jìn)程在隊(duì)列之間移動(dòng)。在系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列，每個(gè)隊(duì)列對(duì)應(yīng)一個(gè)優(yōu)先級(jí)，第 一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二隊(duì)列次之。以下各隊(duì)列的優(yōu)先級(jí)逐步低。各就緒隊(duì)列中的進(jìn)程的 運(yùn)行時(shí)間片不同，高優(yōu)先級(jí)隊(duì)列的時(shí)間片小，低優(yōu)先級(jí)隊(duì)列的時(shí)間片大。進(jìn)程并非總是固定在 某一隊(duì)列中，新進(jìn)程進(jìn)入系統(tǒng)后，被存放在第一個(gè)隊(duì)列的末尾。如果某個(gè)進(jìn)程在規(guī)定的時(shí)間片 內(nèi)沒有完成工作，則把它轉(zhuǎn)入到下一個(gè)隊(duì)列的末尾，直至進(jìn)入最后一個(gè)隊(duì)列。系統(tǒng)先運(yùn)行第一 個(gè)隊(duì)列中的

28、進(jìn)程。當(dāng)?shù)谝魂?duì)列為空時(shí)，才運(yùn)行第二個(gè)隊(duì)列中的進(jìn)程。依此類推，僅當(dāng)前面所有 的隊(duì)列都為空時(shí)，才運(yùn)行最后一個(gè)隊(duì)列中的進(jìn)程。當(dāng)處理器正在第i個(gè)隊(duì)列中為某個(gè)進(jìn)程服務(wù) 時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先級(jí)最高的隊(duì)列（第1 （i-l）中的任何一個(gè)對(duì)列），則此新進(jìn)程要搶 占正在運(yùn)行進(jìn)程的處理器，即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回第i隊(duì)列的末尾，把處理器分 配給新到的高優(yōu)先級(jí)進(jìn)程。除最低優(yōu)先權(quán)隊(duì)列外的所有其他隊(duì)列，均采用相同的進(jìn)程調(diào)度算 法，即按時(shí)間片輪轉(zhuǎn)的FIFO （先進(jìn)先出）算法。最后一個(gè)隊(duì)列中的進(jìn)程按按時(shí)間片輪轉(zhuǎn)或FCFS 策略進(jìn)行調(diào)度。它是綜合了 FIFO、RR和剝奪式HPF的一種進(jìn)程調(diào)度算法。2.4.2算法流程圖

29、243程序代碼#include #include #include #define NULL 0 typedef struct nodechar name10; /* 進(jìn)程名 */int num;/*進(jìn)程所在隊(duì)列數(shù)，也是該隊(duì)列的時(shí)間片*/int cputime;/* 占用 cpu 時(shí)間 */int needtime;/*要求運(yùn)行時(shí)間*/struct node *next; /* 指針 */PCB;PCB *qfl/qll;PCB *qf2/ql2;PCB *qfVql3;定義三個(gè)隊(duì)列的頭指針和尾指針void insert(PCB *q,PCB *qf,PCB *ql) num+; if(qf=

30、NULL&ql=NULL)/隊(duì)列為空int blogl,blog2,blog3; /*分別記錄隊(duì)列1八隊(duì)列2、隊(duì)列3中進(jìn)程數(shù)*/qf二 ql 二 q;else/隊(duì)列不為空ql-next=q;ql二q;ql-next=NULL;void create(int n)/創(chuàng)建進(jìn)程，剛來的進(jìn)程都進(jìn)入隊(duì)列1PCB*p;p=(PCB *)malloc(sizeof(PCB);inti;blogl=blog2=blog3=0; /各隊(duì)列中進(jìn)程數(shù)均為 0 printf(Please enter the name and needtime ofPCB:nH);/*輸入進(jìn)程名和所需時(shí)間for(i=0;in;i+na

31、me);/* 輸入進(jìn)程名 */scanf(%d,&(p-needtime); /* 輸入進(jìn)程要求運(yùn)行時(shí)間 */ p-cputime=O; pnum=0;insert(p,qfl,qllj;blogl+;/隊(duì)列中進(jìn)程數(shù)加1intrunfPCB *q/PCB *qf,PCB *ql)PCB/*p=(PCB *)malloc(sizeof(PCB); f=(PCB *)malloc(sizeof(PCB);1=(PCB *)malloc(sizeof(PCB);*/p二q；f 二 qf;l=ql; if(q-needtimenum) /* 在時(shí)間片內(nèi)完成 */cputime+=qneedtime;

32、qneedtime=O; free(q);return 0;else /*不能在時(shí)間片內(nèi)完成*/cputime+=qnum; q-needtime-=q-num; if(qnumnum+; insert(p,f);/進(jìn)入下一個(gè)隊(duì)歹ij return 1;void prto /*輸出函數(shù)，可以方便看到進(jìn)程執(zhí)行的演示 70|blog20|blog30)if(blogl0) /*第一個(gè)隊(duì)列不為空*/next; pnext=NULL; blogprintf(n %-10s%-10d%nH/p-name/p-needtime); a=run(p/qf2/ql2); blog2+;else if(blog

33、20) /*第二個(gè)隊(duì)列不為空*/ next;p next 二 NULL;blog2-;printff %-10s%-10d%n,p-name,p- need time;a 二 run(p,qf3,ql3);if(a=lblog3+;else if(blog30) /*第三個(gè)隊(duì)列不為空*/next;p next 二 NULL;blog3-;printf( %-10s%-10d%nlp-name/p-needtime);a 二 run(p,qf3,ql3);if(a=lblog3+;/*使用getchar()函數(shù)可以讓輸出時(shí)停留畫面，等待人按回車?yán)^續(xù)*/void mainOqfl=qll=(PCB

34、 *)malloc(sizeof(PCB);qf2=ql2=(PCB *)malloc(sizeof(PCB);qf2=ql2=(PCB *)malloc(sizeof(PCB)J;int n;blogl=blog2=blog3=0;printfC*請(qǐng)輸入進(jìn)程的個(gè)數(shù):”)；scanf(%d&n);create(n);PM；2.4.4測(cè)試結(jié)果及說明2.5 短作業(yè)調(diào)度25.1算法思想短作業(yè)優(yōu)先調(diào)度算法是指對(duì)短作業(yè)進(jìn)行調(diào)度的算法。它從后備隊(duì)列總選擇一個(gè)或若干個(gè) 運(yùn)行時(shí)間最短的作業(yè)，將他們調(diào)入內(nèi)存運(yùn)行。2.5.2. 算法流程圖:短作業(yè)優(yōu)先算法流程圖2.5.3.程序代碼#include #include

35、 ttinclude node *next;/*進(jìn)程名7/*占用cpu時(shí)間 */*要求運(yùn)行時(shí)間 =7 /*狀態(tài)7/*指針7typedef struct nodechar name10;int cputime; intneedtime;char state; structPCB;PCB *ready, *run, *finish; / 就緒、執(zhí)行、結(jié)束指針int N; 進(jìn)程數(shù)量void printO /輸出函數(shù)name; run-cputime/ run-needtime,run-state); /*輸出執(zhí)行的進(jìn)程的信息*/ p=ready;whilefp != NULL)name, p-cpu

36、time, p-needtime, p-state); /*輸出就緒進(jìn)程的信息*/p=p-next;p二finish; while(p != NULL)printf(n %-10s%-10d%-10d %cnf p-name, p-cputime, p-needtime, p-state); /*輸出結(jié)束隊(duì)列的信息*/ p=p-next;getcharO； /*使用getchar()函數(shù)可以讓輸出時(shí)停留畫面，等待人按回車?yán)^續(xù)*/voidinsert(PCB*q)/*插入新進(jìn)程，把進(jìn)程按進(jìn)程到來時(shí)間大小排序*/PCB *pl,*s,*r;int b;s二q;/*指針s指向新要插入的進(jìn)程*/pl=

37、ready; /*指針pl指向原來的進(jìn)程隊(duì)列的隊(duì)首*/ r=pl; /*使用指針r是指向pl前而的進(jìn) 程*/b=l;while(pl!=NULL)&b) if(pl-needtimeneedtime) next; /*新進(jìn)程的開始時(shí)間大，則pl指向下一個(gè)進(jìn)程繼續(xù)比*/ elseb=0;if(r!=plnext=s; snext二pl;/*新進(jìn)程找到位置，插在r和pl之間*/elsenext二pl; ready二s;/*新進(jìn)程的開始時(shí)間按最小，插在隊(duì)首，并修改就緒隊(duì)首ready指針*/void create0name; /* 輸入進(jìn) 程名 */ scanf(%d/&p-needtime); /*

38、 輸入進(jìn)程要求運(yùn)行時(shí)間 */ p-cputime=O; p-state=W; /*表示就緒隊(duì)列中未在隊(duì)首先執(zhí)行，但也是就緒狀態(tài)*/ if (ready!二NULL)insert(p); /*就緒隊(duì)首不為NULL ,插入新進(jìn)程*/ else /* 否則先插在 NULL 前 */ p-next=ready;printff Display is going to start: n);printQ;getcharf);run二ready; /*隊(duì)列排好，run指向就緒隊(duì)列隊(duì)首*/ ready=ready-next; /*ready指向下一個(gè) 進(jìn)程*/ runstateR1; /*隊(duì)首進(jìn)程的狀態(tài)為就緒7void SJF()whilefrun != NULL) cputime=runcputi