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

1、一課程概述1.1.設(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)度性能的好壞，因而，處理機(jī)調(diào)度

2、便成為操作系統(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)度算法。 1.3.理論依據(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ù)一、 用C語言（

3、或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ā)1.5.功能模塊分析：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)行，他們相互爭(zhēng)奪處理機(jī) 這一

4、重要的資源。處理機(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í)間片，每個(gè)進(jìn)程在執(zhí)行一個(gè)時(shí)

5、間片后，輪到下一進(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)程隊(duì)列， 較高優(yōu)先級(jí)的隊(duì)列一般分配

6、給較短的時(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)度算法思想先來先服務(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)行下去，直到該進(jìn)程完成工作或者因?yàn)榈却呈录荒芾^續(xù)運(yùn)行時(shí)才釋

7、放處理機(jī)。算法流程圖圖1.先來先服務(wù)算法流程圖程序代碼#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct node char name10; /*進(jìn)程名*/int cputime; /*占用cpu時(shí)間*/char starttime5; /進(jìn)程開始時(shí)間int needtime; /*要求運(yùn)行時(shí)間*/char state; /*狀態(tài)*/struct node *next; /*指針*/PCB;PCB *ready, *run, *finish; /就緒、執(zhí)行、結(jié)束指針in

8、t N; /進(jìn)程數(shù)量void print() /輸出函數(shù)PCB *p;printf(" NAME CPUTIME STARTTIME NEEDTIME STATUSn");if(run != NULL)printf(" %-10s%-10d%-10s%-10d %cn",run->name,run->cputime,run->starttime,run->needtime,run->state); /*輸出執(zhí)行的進(jìn)程的信息*/p=ready;while(p != NULL)printf(" %-10s%-10d%-

9、10s%-10d %cn",p->name,p->cputime,p->starttime,p->needtime,p->state); /*輸出就緒進(jìn)程的信息*/p=p->next; p=finish;while(p != NULL)printf(" %-10s%-10d%-10s%-10d %cn",p->name,p->cputime,p->starttime,p->needtime,p->state); /*輸出結(jié)束隊(duì)列的信息*/ p=p->next; getchar(); /*使用g

10、etchar()函數(shù)可以讓輸出時(shí)停留畫面， 等待人按回車?yán)^續(xù)*/ void insert(PCB *q) /*插入新進(jìn)程，把進(jìn)程按進(jìn)程到來時(shí)間大小排序*/ PCB *p1,*s,*r;int b;s=q; /*指針s指向新要插入的進(jìn)程*/p1=ready; /*指針p1指向原來的進(jìn)程隊(duì)列的隊(duì)首*/r=p1; /*使用指針r是指向p1前面的進(jìn)程*/b=1;while(p1!=NULL)&&b)if(strcmp(p1->starttime,s->starttime)<0) r=p1; p1=p1->next; /*新進(jìn)程的開始時(shí)間大，則p1 指向下一個(gè)進(jìn)程

11、繼續(xù)比*/ else b=0; if(r!=p1) r->next=s; s->next=p1; /*新進(jìn)程找到位置，插在r和p1之間*/elses->next=p1; ready=s; /*新進(jìn)程的開始時(shí)間按最小，插在隊(duì)首，并修改就緒隊(duì)首ready指針*/ void create() PCB *p;int i;ready=NULL; run=NULL; finish=NULL;printf("Please enter the name and time and starttime of PCB:n"); /*輸入進(jìn)程名、運(yùn)行時(shí)間和開始時(shí)間*/for(i=

12、0;i<N;i+) p=(PCB *)malloc(sizeof(PCB); /*為新進(jìn)程開辟空間*/scanf("%s",p->name); /*輸入進(jìn)程名*/scanf("%d",&p->needtime); /*輸入進(jìn)程要求運(yùn)行時(shí)間*/scanf("%s",p->starttime); /輸入進(jìn)程開始時(shí)間p->cputime=0; p->state='W' /*表示就緒隊(duì)列中未在隊(duì)首先執(zhí)行，但也是就緒狀態(tài)*/if (ready!=NULL) insert(p); /*就

13、緒隊(duì)首不為NULL，插入新進(jìn)程*/else /*否則先插在NULL前*/p->next=ready;ready=p; printf(" Display is going to start: n");printf("*n");print(); getchar();run=ready; /*隊(duì)列排好，run指向就緒隊(duì)列隊(duì)首*/ready=ready->next; /*ready指向下一個(gè)進(jìn)程*/run->state='R' /*隊(duì)首進(jìn)程的狀態(tài)為就緒*/void FCFS()while(run != NULL)run->

14、cputime=run->cputime+run->needtime;run->needtime=0;run->next=finish;finish = run;run->state='E'run = NULL;if(ready != NULL)run = ready;run->state='R'ready=ready->next;print();void main() printf("Please enter the total number of PCB:n");scanf("%d&qu

15、ot;,&N);create(); /*模擬創(chuàng)建進(jìn)程，并輸入相關(guān)信息*/FCFS(); /*先來先服務(wù)調(diào)度算法*/測(cè)試結(jié)果及說明首先輸入進(jìn)程個(gè)數(shù)（為5個(gè)），這里命名為A,B,C,D,E，然后分別輸入運(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)度優(yōu)先權(quán)。該算法核心是確定進(jìn)程的優(yōu)先級(jí)。2.2.2算法流程圖圖2.優(yōu)先級(jí)調(diào)度流程圖2.2.3程序代碼#include <stdio.h>#include &

16、lt;stdlib.h>#include <string.h>typedef struct node char name10; /*進(jìn)程名*/ int prio; /*優(yōu)先數(shù)*/ int cputime; /*占用cpu時(shí)間*/ int needtime; /*要求運(yùn)行時(shí)間*/ char state; /*狀態(tài)*/ struct node *next; /*指針*/PCB;PCB *ready,*run,*finish; /*就緒 執(zhí)行 結(jié)束指針*/int N;void prt() /*輸出函數(shù)，可以方便看到進(jìn)程執(zhí)行的演示*/ PCB *p; printf(" NA

17、ME CPUTIME NEEDTIME PRIORITY STATUSn"); if(run!=NULL) printf(" %-10s%-10d%-10d%-10d %cn",run->name,run->cputime,run->needtime,run->prio,run->state); /*輸出執(zhí)行的進(jìn)程的信息*/ p=ready; while(p!=NULL) printf(" %-10s%-10d%-10d%-10d %cn",p->name,p->cputime,p->needti

18、me,p->prio,p->state); /*輸出就緒進(jìn)程的信息*/ p=p->next; p=finish; while(p!=NULL) printf(" %-10s%-10d%-10d%-10d %cn",p->name,p->cputime,p->needtime,p->prio,p->state); /*輸出結(jié)束隊(duì)列的信息*/ p=p->next; getchar(); /*使用getchar()函數(shù)可以讓輸出時(shí)停留畫面，等待人按回車?yán)^續(xù)*/void insert(PCB *q) /*插入新進(jìn)程，把進(jìn)程按優(yōu)先

19、數(shù)大小排序*/ PCB *p1,*s,*r; int b; s=q; /*指針s指向新要插入的進(jìn)程*/ p1=ready; /*指針p1指向原來的進(jìn)程隊(duì)列的隊(duì)首*/ r=p1; /*使用指針r是指向p1前面的進(jìn)程*/ b=1; while(p1!=NULL)&&b) if(p1->prio>=s->prio) r=p1; p1=p1->next; /*新進(jìn)程的優(yōu)先數(shù)小，則p1 指向下一個(gè)進(jìn)程繼續(xù)比*/ else b=0; if(r!=p1) r->next=s; s->next=p1; /*新進(jìn)程找到位置，插在r和p1之間*/ else s-

20、>next=p1; ready=s; /*新進(jìn)程的優(yōu)先數(shù)最大，插在隊(duì)首，并 修改就緒隊(duì)首ready指針*/void create() PCB *p; int i;ready=NULL; run=NULL; finish=NULL;printf("Please enter the name and time and priority of PCB:n"); /*輸入進(jìn)程名、運(yùn)行時(shí)間和優(yōu)先級(jí)*/for(i=0;i<N;i+) p=(PCB *)malloc(sizeof(PCB); /*為新進(jìn)程開辟空間*/ scanf("%s",p->na

21、me); /*輸入進(jìn)程名*/ scanf("%d",&p->needtime); /*輸入進(jìn)程要求運(yùn)行時(shí)間*/ scanf("%d",&p->prio); /*輸入進(jìn)程優(yōu)先數(shù)*/ p->cputime=0; p->state='W' /*表示就緒隊(duì)列中未在隊(duì)首先執(zhí)行，但也是就緒狀態(tài)*/ if (ready!=NULL) insert(p); /*就緒隊(duì)首不為NULL，插入新進(jìn)程*/ else p->next=ready; ready=p; /*否則先插在NULL前*/ printf("

22、; Display is going to start: n"); printf("*n"); prt(); run=ready; /*隊(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->state='R' /*隊(duì)首進(jìn)程的狀態(tài)為就緒*/void prio() while(run!=NULL) run->cputime=run->cputime+1; /*運(yùn)行一次cpu占用時(shí)間加一*/ ru

23、n->needtime=run->needtime-1; /*運(yùn)行一次要求運(yùn)行時(shí)間減一*/ run->prio=run->prio-1; /*運(yùn)行一次優(yōu)先數(shù)減一*/ if(run->needtime=0) /*若要求運(yùn)行時(shí)間為0時(shí)*/ run->next=finish; /*退出隊(duì)列*/ finish=run; /*finish為結(jié)束進(jìn)程的隊(duì)列 */ run->state='E' /*修改狀態(tài)為結(jié)束*/ run=NULL; /*釋放run指針*/ if (ready!=NULL) /*創(chuàng)建新就緒隊(duì)列的頭指針*/ run=ready; r

24、un->state='R' ready=ready->next; else if(ready!=NULL)&&(run->prio<ready->prio) /*隊(duì)首進(jìn)程的優(yōu)先數(shù)比它下一個(gè)小，且下一個(gè)進(jìn)程不為NULL時(shí)執(zhí)行*/ run->state='W' run->next=NULL; /*隊(duì)首進(jìn)程退出進(jìn)程隊(duì)列*/ insert(run); /*在進(jìn)程隊(duì)列中重新插入原來的隊(duì)首進(jìn)程*/ run=ready; /*重新置就緒隊(duì)列的頭指針*/ run->state='R' ready=r

25、eady->next; prt(); void main() printf("Please enter the total number of PCB:n"); scanf("%d",&N); create(); /*模擬創(chuàng)建進(jìn)程，并輸入相關(guān)信息*/ prio(); /*優(yōu)先數(shù)調(diào)度算法*/2.2.4測(cè)試結(jié)果及說明優(yōu)先級(jí)調(diào)度算法運(yùn)行情況如圖1，圖2，圖3，圖4所示 圖1.輸入進(jìn)程塊的數(shù)量 圖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)程按先來

26、先服務(wù)的原則排成一個(gè)隊(duì)列，將新來的進(jìn)程加到就緒對(duì)列的末尾，每當(dāng)執(zhí)行進(jìn)程調(diào)度時(shí)，總是把處理機(jī)分配給隊(duì)首的進(jìn)程，各進(jìn)程占用CPU的時(shí)間片相同。也就是說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程序代碼#include <stdio.h>#include <stdlib.h>#inclu

27、de <string.h>typedef struct node char name10; /*進(jìn)程名*/ int count; /*計(jì)數(shù)器，判斷是否=時(shí)間片的大小*/int cputime; /*占用cpu時(shí)間*/int needtime; /*要求運(yùn)行時(shí)間*/char state; /*狀態(tài)*/struct node *next; /*指針*/PCB;PCB *ready,*run,*finish,*tail; /*就緒 執(zhí)行 結(jié)束 尾指針*/int N,round;void prt() /*輸出函數(shù)，可以方便看到進(jìn)程執(zhí)行的演示*/PCB *p; printf(" N

28、AME CPUTIME NEEDTIME STATUSn"); if(run!=NULL) printf(" %-10s%-10d%-10d %cn",run->name,run->cputime,run->needtime,run->state); /*輸出執(zhí)行的進(jìn)程的信息*/ p=ready; while(p!=NULL) printf(" %-10s%-10d%-10d %cn",p->name,p->cputime,p->needtime,p->state); /*輸出就緒進(jìn)程的信息*/

29、p=p->next; p=finish; while(p!=NULL) printf(" %-10s%-10d%-10d %cn",p->name,p->cputime,p->needtime,p->state); /*輸出結(jié)束隊(duì)列的信息*/ p=p->next; getchar(); void insert(PCB *q) /*在隊(duì)尾插入新的進(jìn)程*/ PCB *p;p=ready;while(p->next!=NULL)p=ready->next;tail=p;tail->next=q;q->next=NULL;

30、 void create() PCB *p; int i;ready=NULL; run=NULL; finish=NULL;printf("Please enter the name and time of PCB:n"); /*輸入進(jìn)程名、和*/for(i=0;i<N;i+) p=(PCB *)malloc(sizeof(PCB); /*為新進(jìn)程開辟空間*/ scanf("%s",p->name); /*輸入進(jìn)程名*/ scanf("%d",&p->needtime); /*輸入進(jìn)程要求運(yùn)行時(shí)間*/ p-

31、>cputime=0; p->state='W' /*表示就緒隊(duì)列中未在隊(duì)首先執(zhí)行，但也是就緒狀態(tài)*/ if (ready!=NULL) insert(p); /*就緒隊(duì)首不為NULL，插入新進(jìn)程*/ else p->next=ready; ready=p; tail=p; printf(" Display is going to start: n"); printf("*n"); prt(); getchar(); run=ready; /*隊(duì)列排好，run指向就緒隊(duì)列隊(duì)首*/ ready=ready->next

32、; /*ready指向下一個(gè)進(jìn)程*/ run->state='R' /*隊(duì)首進(jìn)程的狀態(tài)為就緒*/void count() while(run!=NULL) run->cputime=run->cputime+1; /*運(yùn)行一次cpu占用時(shí)間加一*/run->needtime=run->needtime-1; /*運(yùn)行一次要求運(yùn)行時(shí)間減一*/run->count=run->count+1; /*運(yùn)行一次計(jì)數(shù)器加一*/if(run->needtime=0) /*若要求運(yùn)行時(shí)間為0時(shí)*/ run->next=finish; /*退

33、出隊(duì)列*/finish=run; /*finish為結(jié)束進(jìn)程的隊(duì)列 */run->state='E' /*修改狀態(tài)為結(jié)束*/run=NULL; /*釋放run指針*/if (ready!=NULL) /*創(chuàng)建新就緒隊(duì)列的頭指針*/run=ready; run->state='R' ready=ready->next; elseif(run->count=round) /*如果時(shí)間片到*/ run->count=0; /*計(jì)數(shù)器置0*/if(ready!=NULL) /*如就緒隊(duì)列不空*/run->state='W

34、9; insert(run); /*在進(jìn)程隊(duì)列中重新插入原來進(jìn)程,插入隊(duì)尾*/run=ready; /*重新置就緒隊(duì)列的頭指針*/run->state='R'ready=ready->next; prt(); void main() printf("Please enter the total number of PCB:n");scanf("%d",&N);create(); /*模擬創(chuàng)建進(jìn)程，并輸入相關(guān)信息*/count(); /*優(yōu)先數(shù)調(diào)度算法*/2.3.4測(cè)試結(jié)果及說明時(shí)間片輪轉(zhuǎn)調(diào)度算法運(yùn)行情況如圖1，圖2，圖

35、3所示圖1 所有的進(jìn)程都在隊(duì)列中 圖2 其中一個(gè)進(jìn)程執(zhí)行完畢 圖4 所有的進(jìn)程都執(zhí)行完畢2.4多級(jí)反饋隊(duì)列調(diào)度算法思想允許進(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ì)列中的進(jìn)程。當(dāng)?shù)谝魂?duì)列為空時(shí)，才運(yùn)行第二個(gè)隊(duì)列中的進(jìn)程。依此類推，僅當(dāng)前面

36、所有的隊(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-1）中的任何一個(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)度算法。算法流程圖程序代碼#include<stdio.h>#include <stdlib.h

37、>#include <string.h>#define NULL 0typedef 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 *qf1,*ql1;PCB *qf2,*ql2;PCB *qf3,*ql3;/定義三個(gè)隊(duì)列的頭指針和尾指針int blog1,blog2,blog3;/*分別記錄隊(duì)列1,、隊(duì)列2、隊(duì)列3中進(jìn)程數(shù)*/void inse

38、rt(PCB *q,PCB *qf,PCB *ql) q->num+;if(qf=NULL&&ql=NULL) /隊(duì)列為空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);int i;blog1=blog2=blog3=0;/各隊(duì)列中進(jìn)程數(shù)均為0printf("Please enter the name and needtime of PCB:n"); /

39、*輸入進(jìn)程名和所需時(shí)間*/for(i=0;i<n;i+) /p=(PCB *)malloc(sizeof(PCB); /*為新進(jìn)程開辟空間*/scanf("%s",p->name); /*輸入進(jìn)程名*/scanf("%d",&(p->needtime); /*輸入進(jìn)程要求運(yùn)行時(shí)間*/p->cputime=0;p->num=0;insert(p,qf1,ql1);blog1+;/隊(duì)列中進(jìn)程數(shù)加1int run(PCB *q,PCB *qf,PCB *ql)PCB *p,*f,*l;/*p=(PCB *)malloc(s

40、izeof(PCB);f=(PCB *)malloc(sizeof(PCB);l=(PCB *)malloc(sizeof(PCB);*/p=q;f=qf;l=ql;if(q->needtime<=q->num) /*在時(shí)間片內(nèi)完成*/q->cputime+=q->needtime;q->needtime=0;free(q);return 0;else/*不能在時(shí)間片內(nèi)完成*/q->cputime+=q->num;q->needtime-=q->num;if(q->num<3)q->num+;insert(p,f,l

41、);/進(jìn)入下一個(gè)隊(duì)列return 1;void prt() /*輸出函數(shù)，可以方便看到進(jìn)程執(zhí)行的演示*/PCB *p;/p=(PCB *)malloc(sizeof(PCB);int a;printf(" NAME CPUTIME NEEDTIME STATUSn");while(blog1>0|blog2>0|blog3>0)if(blog1>0)/*第一個(gè)隊(duì)列不為空*/p=qf1;qf1=qf1->next;p->next=NULL;blog1-;printf(" %-10s%-10d%n",p->name,

42、p->needtime); a=run(p,qf2,ql2);if(a=1)blog2+;else if(blog2>0)/*第二個(gè)隊(duì)列不為空*/p=qf2;qf2=qf2->next;p->next=NULL;blog2-;printf(" %-10s%-10d%n",p->name,p->needtime); a=run(p,qf3,ql3);if(a=1)blog3+;else if(blog3>0)/*第三個(gè)隊(duì)列不為空*/p=qf3;qf3=qf3->next;p->next=NULL;blog3-;printf

43、(" %-10s%-10d%n",p->name,p->needtime); a=run(p,qf3,ql3);if(a=1)blog3+; /*使用getchar()函數(shù)可以讓輸出時(shí)停留畫面，等待人按回車?yán)^續(xù)*/void main()qf1=ql1=(PCB *)malloc(sizeof(PCB);qf2=ql2=(PCB *)malloc(sizeof(PCB);qf2=ql2=(PCB *)malloc(sizeof(PCB);int n;blog1=blog2=blog3=0;printf("請(qǐng)輸入進(jìn)程的個(gè)數(shù): ");scanf(&

44、quot;%d",&n);create(n);prt();2.4.4測(cè)試結(jié)果及說明2.5短作業(yè)調(diào)度2.5.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算法流程圖：開始輸入進(jìn)程名就緒隊(duì)列空?結(jié)束YN按時(shí)間服務(wù)進(jìn)行排序執(zhí)行程序短作業(yè)優(yōu)先算法流程圖2.5.3程序代碼#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct node char name10; /*進(jìn)程名*/

45、int cputime; /*占用cpu時(shí)間*/int needtime; /*要求運(yùn)行時(shí)間*/char state; /*狀態(tài)*/struct node *next; /*指針*/PCB;PCB *ready, *run, *finish; /就緒、執(zhí)行、結(jié)束指針int N; /進(jìn)程數(shù)量void print() /輸出函數(shù)PCB *p;printf(" NAME CPUTIME NEEDTIME STATUSn");if(run != NULL)printf(" %-10s%-10d%-10d %cn",run->name,run->cpu

46、time,run->needtime,run->state); /*輸出執(zhí)行的進(jìn)程的信息*/p=ready;while(p != NULL)printf(" %-10s%-10d%-10d %cn",p->name,p->cputime,p->needtime,p->state); /*輸出就緒進(jìn)程的信息*/p=p->next; p=finish;while(p != NULL)printf(" %-10s%-10d%-10d %cn",p->name,p->cputime,p->needtim

47、e,p->state); /*輸出結(jié)束隊(duì)列的信息*/ p=p->next; getchar(); /*使用getchar()函數(shù)可以讓輸出時(shí)停留畫面， 等待人按回車?yán)^續(xù)*/ void insert(PCB *q) /*插入新進(jìn)程，把進(jìn)程按進(jìn)程到來時(shí)間大小排序*/ PCB *p1,*s,*r;int b;s=q; /*指針s指向新要插入的進(jìn)程*/p1=ready; /*指針p1指向原來的進(jìn)程隊(duì)列的隊(duì)首*/r=p1; /*使用指針r是指向p1前面的進(jìn)程*/b=1;while(p1!=NULL)&&b)if(p1->needtime<s->needtim

48、e) r=p1; p1=p1->next; /*新進(jìn)程的開始時(shí)間大，則p1 指向下一個(gè)進(jìn)程繼續(xù)比*/ else b=0; if(r!=p1) r->next=s; s->next=p1; /*新進(jìn)程找到位置，插在r和p1之間*/elses->next=p1; ready=s; /*新進(jìn)程的開始時(shí)間按最小，插在隊(duì)首，并修改就緒隊(duì)首ready指針*/ void create() PCB *p;int i;ready=NULL; run=NULL; finish=NULL;printf("Please enter the name and time of PCB:n"); /*輸入進(jìn)程名、運(yùn)行時(shí)間和開始時(shí)間*/for(i=0;i<N;i+) p=(PCB *)malloc(sizeof(PCB); /*為新進(jìn)程開辟空間*/scanf("%s",p->name); /*輸入進(jìn)程名*/scanf("%d",&p->needti