靜態(tài)優(yōu)先權(quán)優(yōu)先算法的進(jìn)程調(diào)程序

1、 靜態(tài)優(yōu)先權(quán)優(yōu)先算法的進(jìn)程調(diào)度程序?qū)W 院 專 業(yè) 學(xué) 生 姓 名 學(xué) 號(hào) 指導(dǎo)教師姓名 21014年 3 月 19 日目 錄1.系統(tǒng)需求分析11.1問題描述11.2功能要求12.總體設(shè)計(jì)12.1總體設(shè)計(jì)圖12.2各模塊功能22.3相關(guān)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)33.詳細(xì)設(shè)計(jì)33.1采用C語(yǔ)言定義的相關(guān)數(shù)據(jù)類型33.2調(diào)度算法的主要實(shí)現(xiàn)44.運(yùn)行結(jié)果44.1系統(tǒng)調(diào)試44.2功能實(shí)現(xiàn)界面55.使用說明76.心得體會(huì)87.附錄87.1 源代碼87.2 參考文獻(xiàn)171.系統(tǒng)需求分析1.1問題描述1)設(shè)計(jì)并實(shí)現(xiàn)一個(gè)采用靜態(tài)優(yōu)先權(quán)算法的進(jìn)程調(diào)度演示程序。并且求出每個(gè)進(jìn)程的周轉(zhuǎn)時(shí)間以及帶權(quán)周轉(zhuǎn)時(shí)間。2) 靜態(tài)優(yōu)先權(quán)是在創(chuàng)

2、建進(jìn)程時(shí)確定的,且在進(jìn)程的整個(gè)運(yùn)行期間保持不變.一般地,優(yōu)先權(quán)是利用某一范圍內(nèi)的一個(gè)整數(shù)來表示的,例如,07或0255中的某一整數(shù), 又把該整數(shù)稱為優(yōu)先數(shù).只是具體用法各異:有的系統(tǒng)用"0"表示最高優(yōu)先權(quán),當(dāng)數(shù)值愈大時(shí),其優(yōu)先權(quán)愈低;而有的系統(tǒng)恰恰相反.確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下三個(gè)方面:a.進(jìn)程類型.(系統(tǒng)進(jìn)程/用戶進(jìn)程)b.進(jìn)程對(duì)資源的需求.(需求量的大小)c.用戶要求.(用戶進(jìn)程緊迫程度)3)本程序采用優(yōu)先級(jí)數(shù)字大的優(yōu)先權(quán)大。1.2功能要求1）每一個(gè)進(jìn)程有一個(gè)PCB，其內(nèi)容可以根據(jù)具體情況設(shè)定。2）進(jìn)程數(shù)、進(jìn)入內(nèi)存時(shí)間、要求服務(wù)時(shí)間、優(yōu)先級(jí)等均可以在界面上設(shè)定。3）可

3、讀取樣例數(shù)據(jù)（要求存放在外部文件中）進(jìn)行進(jìn)程數(shù)、進(jìn)入內(nèi)存時(shí)間、進(jìn)程優(yōu)先級(jí)的初始化。4）可以在運(yùn)行中顯示各進(jìn)程的狀態(tài)：就緒、執(zhí)行 （由于不要求設(shè)置互斥資源與進(jìn)程間的同步關(guān)系，故只有兩種狀態(tài)）。5）具有一定的數(shù)據(jù)容錯(cuò)性。2.總體設(shè)計(jì)2.1總體設(shè)計(jì)圖系統(tǒng)總體設(shè)計(jì)如圖2.1所示。0、結(jié)束1、進(jìn)程的創(chuàng)建及模擬輸入進(jìn)程數(shù)輸入優(yōu)先級(jí)輸入進(jìn)入內(nèi)存時(shí)間輸入服務(wù)時(shí)間輸出運(yùn)行結(jié)果靜態(tài)優(yōu)先權(quán)優(yōu)先算法2、讀取文件數(shù)據(jù)及模擬輸出運(yùn)行結(jié)果圖2.1 系統(tǒng)總體設(shè)計(jì) 2.2各模塊功能1) void buildProcess()：手動(dòng)創(chuàng)建進(jìn)程。2) struct PCB * callMemory()：將符合條件的進(jìn)程調(diào)入內(nèi)存。3)

4、 void ListAllPCB(struct PCB *h)：打印所有進(jìn)程到屏幕上。4) void Menu()：菜單以及執(zhí)行。5) void newPCB()：創(chuàng)建進(jìn)程。在1）中被調(diào)用。6) void readFromFile()：從文件中讀取數(shù)據(jù)。7) void readyList(struct PCB *pcb)：就緒列表。8) void release(struct PCB *pcb)，void releaseR(struct PCB *pcb)：釋放進(jìn)程。9) void run()：執(zhí)行靜態(tài)優(yōu)先級(jí)進(jìn)程調(diào)度算法。10)struct PCB * runTheProcess()：標(biāo)識(shí)要執(zhí)

5、行的進(jìn)程。11)void setNewPCB(char *name,int pri,int entime,int sertime)：創(chuàng)建進(jìn)程。在6）中被調(diào)用。12) int timeOfData(FILE *f)：計(jì)算文件中進(jìn)程數(shù)量。在6）中被調(diào)用。2.3相關(guān)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)結(jié)構(gòu)體：struct PCB *head,*readyHead;3.詳細(xì)設(shè)計(jì)3.1采用C語(yǔ)言定義的相關(guān)數(shù)據(jù)類型struct PCBint ArrivalTime;int ServiceTime;char number10;struct PCB *head,*thisP,*newP;/動(dòng)態(tài)接收進(jìn)程及詳細(xì)struct PCB *r

6、eadyHead;/動(dòng)態(tài)存儲(chǔ)就緒隊(duì)列采用結(jié)構(gòu)體數(shù)組，創(chuàng)建一個(gè)進(jìn)程，包含進(jìn)程相關(guān)信息：進(jìn)程名稱、進(jìn)程優(yōu)先級(jí)、進(jìn)程到達(dá)時(shí)間、進(jìn)程服務(wù)時(shí)間。3.2調(diào)度算法的主要實(shí)現(xiàn)struct PCB * callMemory()/調(diào)入內(nèi)存，返回調(diào)入內(nèi)存的鏈表節(jié)點(diǎn)。將達(dá)到進(jìn)程進(jìn)入內(nèi)存時(shí)間的所有進(jìn)程調(diào)入內(nèi)存。void readyList(struct PCB *pcb)/單鏈表的形式創(chuàng)建就緒隊(duì)列。將進(jìn)入內(nèi)存的進(jìn)程調(diào)入就緒列表。struct PCB * runTheProcess()/執(zhí)行的進(jìn)程，返回要執(zhí)行進(jìn)程的節(jié)點(diǎn)。將就緒列表中滿足運(yùn)行條件的進(jìn)程標(biāo)識(shí)下來并返回節(jié)點(diǎn)。void run()/靜態(tài)優(yōu)先權(quán)算法。將執(zhí)行的程序釋

7、放。調(diào)入新的滿足執(zhí)行條件的進(jìn)程。就緒列表釋放。4.運(yùn)行結(jié)果4.1系統(tǒng)調(diào)試 在程序設(shè)計(jì)初期。本想采用冒泡排序?qū)⑦M(jìn)入內(nèi)存的進(jìn)程進(jìn)行優(yōu)先級(jí)排序，不過最后總是排序失敗。最后想到我進(jìn)行的是進(jìn)程調(diào)度模擬，應(yīng)該就有進(jìn)程調(diào)入內(nèi)存以及調(diào)入CPU，因此之后設(shè)計(jì)其他函數(shù)進(jìn)行調(diào)入內(nèi)存、CPU的模擬。而且最后選擇新建就緒列表，進(jìn)行選擇插入就緒列表中。以及隨時(shí)使用屏幕打印語(yǔ)句printf來測(cè)試程序各個(gè)階段執(zhí)行狀態(tài)。4.2功能實(shí)現(xiàn)界面（1）主菜單：如圖4.1所示。圖4.1主菜單（2）進(jìn)程調(diào)度模擬。圖4.2創(chuàng)建進(jìn)程2)圖4.3進(jìn)程運(yùn)行過程3)進(jìn)程在調(diào)度算法中，計(jì)算出的具體的完成時(shí)間，周轉(zhuǎn)時(shí)間，帶權(quán)時(shí)間。如圖4.4所示。圖4.

8、4進(jìn)程運(yùn)行結(jié)果（3）選擇2：從文件讀取數(shù)據(jù)。如圖4.5。在f:test.txt中，數(shù)據(jù)如下。/從文件讀取數(shù)據(jù)/*數(shù)據(jù)格式如下進(jìn)程名優(yōu)先級(jí)到達(dá)時(shí)間服務(wù)時(shí)間proc12110proc22111proc3322*/運(yùn)行結(jié)果。如圖4.6圖4.6 文件讀取數(shù)據(jù)及運(yùn)行結(jié)果5.使用說明根據(jù)屏幕提示輸入即可。需要用戶注意的是優(yōu)先級(jí)（整數(shù)表示）越大優(yōu)先權(quán)越大。6.心得體會(huì)本次課程設(shè)計(jì)，第一天上午去拿課程設(shè)計(jì)題目采用靜態(tài)優(yōu)先權(quán)優(yōu)先算法的進(jìn)程調(diào)度程序，下午開始查找資料并且構(gòu)思。在網(wǎng)上看到一些課程設(shè)計(jì)用到的有數(shù)據(jù)結(jié)構(gòu)體struct，便再度拿出C語(yǔ)言書本以及數(shù)據(jù)結(jié)構(gòu)課本，主要看了數(shù)據(jù)結(jié)構(gòu)體和單鏈表方面的知識(shí)。上面也曾說

9、到，程序設(shè)計(jì)初期打算在單鏈表中直接使用冒泡排序法進(jìn)程優(yōu)先級(jí)的排序，總是失敗。后來意識(shí)到，進(jìn)程調(diào)度不僅要考慮到進(jìn)程優(yōu)先級(jí)，同時(shí)還有進(jìn)入內(nèi)存的時(shí)間。因?yàn)橹挥械竭_(dá)進(jìn)入內(nèi)存的時(shí)間，進(jìn)程才會(huì)被調(diào)入內(nèi)存中，進(jìn)一步通過滿足條件被調(diào)入CPU中執(zhí)行，或者說分配CPU進(jìn)而執(zhí)行。所以索性模擬出調(diào)入內(nèi)存方法以及調(diào)入CPU方法，與此有極大關(guān)系的是單鏈表就緒列表的建立。進(jìn)行代碼編寫以及測(cè)試，從而模擬進(jìn)程調(diào)度算法完成。7.附錄7.1 源代碼#include<stdio.h>#include<stdlib.h>#include<string.h>int SequenceNumber=1;/

10、進(jìn)程編號(hào)int ProcessAmount;/進(jìn)程數(shù)量int StartCount=0;/調(diào)入內(nèi)存進(jìn)程計(jì)數(shù)struct PCB/進(jìn)程控制塊int No;/進(jìn)程號(hào)char name16;/進(jìn)程名int enterMemoryTime;/進(jìn)入內(nèi)存時(shí)間int serviceTime;/服務(wù)時(shí)間int priority;/優(yōu)先級(jí)struct PCB *next;struct PCB *head,*thisP,*newP;/動(dòng)態(tài)接收進(jìn)程及詳細(xì)struct PCB *readyHead;/動(dòng)態(tài)存儲(chǔ)就緒隊(duì)列/函數(shù)聲明int getch();int timeOfData(FILE *);void ListAl

11、lPCB();void Menu();void printPCB(struct PCB *,int,int,int,double);void printPCBP(struct PCB *);void printField();void printFieldP();void release(struct PCB *);void releaseR(struct PCB *);void setNewPCB(char *,int,int,int);struct PCB * runTheProcess();void newPCB()/建立PCBnewP=(struct PCB *)malloc(size

12、of(struct PCB);if(head=NULL)/判斷頭節(jié)點(diǎn)是否為空head=newP;/為空，頭節(jié)點(diǎn)指向新開辟的內(nèi)存elsethisP=head;while(thisP->next!=NULL)thisP=thisP->next;thisP->next=newP;/遍歷單鏈表，找到最后一個(gè)元素thisP=newP;thisP->No=SequenceNumber;SequenceNumber+;printf("進(jìn)程號(hào) %dn",thisP->No);printf("輸入進(jìn)程名：");scanf("%s&q

13、uot;,thisP->name);printf("輸入優(yōu)先級(jí)：");scanf("%d",&thisP->priority);printf("輸入進(jìn)入內(nèi)存時(shí)間：");scanf("%d",&thisP->enterMemoryTime);printf("輸入服務(wù)時(shí)間：");scanf("%d",&thisP->serviceTime);thisP->next=NULL;void buildProcess()/創(chuàng)建進(jìn)程in

14、t i=0;printf("輸入進(jìn)程數(shù)量：");scanf("%d",&ProcessAmount);while(i<ProcessAmount)newPCB();i+;void readyList(struct PCB *pcb)/單鏈表的形式創(chuàng)建就緒隊(duì)列newP=(struct PCB *)malloc(sizeof(struct PCB);if(readyHead=NULL)readyHead=newP;elsethisP=readyHead;while(thisP->next!=NULL)thisP=thisP->nex

15、t;thisP->next=newP;thisP=newP;strcpy(thisP->name,pcb->name);thisP->No=pcb->No;thisP->priority=pcb->priority;thisP->enterMemoryTime=pcb->enterMemoryTime;thisP->serviceTime=pcb->serviceTime;thisP->next=NULL;struct PCB * callMemory()/調(diào)入內(nèi)存，返回調(diào)入內(nèi)存的鏈表節(jié)點(diǎn)int at;/到達(dá)時(shí)間struc

16、t PCB *markP;if(head=NULL)printf("程序沒有找到。n");elsemarkP=thisP=head;/標(biāo)記指向頭節(jié)點(diǎn)at=thisP->enterMemoryTime;/到達(dá)時(shí)間為頭節(jié)點(diǎn)到達(dá)時(shí)間while(thisP->next!=NULL)/當(dāng)下一節(jié)點(diǎn)不為空if(at>thisP->next->enterMemoryTime)/判斷當(dāng)前時(shí)間是否大于下一節(jié)點(diǎn)時(shí)間markP=thisP->next;/是，標(biāo)記此節(jié)點(diǎn)at=markP->enterMemoryTime;/到達(dá)時(shí)間更改為標(biāo)記時(shí)間thisP=t

17、hisP->next;/向后遍歷return markP;void run()/靜態(tài)優(yōu)先級(jí)算法執(zhí)行。struct PCB *temp;/臨時(shí)節(jié)點(diǎn)用來存儲(chǔ)調(diào)入內(nèi)存節(jié)點(diǎn)struct PCB *runPro;/用來接收?qǐng)?zhí)行的節(jié)點(diǎn)int i;/循環(huán)初始條件int at,srt,runtime=0;/到達(dá)時(shí)間，開始執(zhí)行時(shí)間，運(yùn)行時(shí)間。int turnOverTime;/周轉(zhuǎn)時(shí)間double ptot;/帶權(quán)周轉(zhuǎn)時(shí)間if(head=NULL)printf("沒有發(fā)現(xiàn)進(jìn)程。n");elsefor(i=0;i<ProcessAmount;i+)/循環(huán)進(jìn)程的數(shù)量次while(he

18、ad!=NULL)temp=callMemory();if(i=0)/初始情況下球開始執(zhí)行時(shí)間，完成時(shí)間，周轉(zhuǎn)時(shí)間，帶權(quán)周轉(zhuǎn)時(shí)間srt=at=temp->enterMemoryTime;runtime=at+temp->serviceTime;turnOverTime=runtime-at;ptot=turnOverTime*1.0/temp->serviceTime;readyList(temp);/初始納入就緒列表以及后續(xù)release(temp);/釋放進(jìn)程while(head!=NULL&&(temp=callMemory()->enterMem

19、oryTime<=runtime)readyList(temp);/循環(huán)判斷是否納入就緒列表release(temp);runPro=runTheProcess();if(i>0)/初始之后，計(jì)算各時(shí)間及周轉(zhuǎn)srt=runtime;runtime+=runPro->serviceTime;turnOverTime=runtime-runPro->enterMemoryTime;ptot=turnOverTime*1.0/runPro->serviceTime;printf("當(dāng)前執(zhí)行的進(jìn)程：n");printField();printPCB(r

20、unPro,srt,runtime,turnOverTime,ptot);releaseR(runPro);printf("n就緒進(jìn)程列表：n");ListAllPCB(readyHead);printf("n");struct PCB * runTheProcess()/執(zhí)行的進(jìn)程，返回要執(zhí)行進(jìn)程的節(jié)點(diǎn)int time,pri;struct PCB *markThis;/標(biāo)記要返回的節(jié)點(diǎn)if(readyHead=NULL)printf("沒有可運(yùn)行的進(jìn)程。n");elsemarkThis=thisP=readyHead;time=t

21、hisP->enterMemoryTime;/當(dāng)前到達(dá)時(shí)間pri=thisP->priority;/當(dāng)前進(jìn)程的優(yōu)先級(jí)while(thisP->next!=NULL)if(time=thisP->next->enterMemoryTime)/判斷之后節(jié)點(diǎn)的到達(dá)時(shí)間是否與當(dāng)前一致if(pri<thisP->next->priority)/一致，則判斷優(yōu)先級(jí)決定pri=thisP->next->priority;/更改優(yōu)先級(jí)判斷條件為下一優(yōu)先級(jí)markThis=thisP->next;/標(biāo)記當(dāng)前節(jié)點(diǎn)的下一節(jié)點(diǎn)elsebreak;thi

22、sP=thisP->next;return markThis;void release(struct PCB *pcb)/刪除原單鏈表的進(jìn)程節(jié)點(diǎn)struct PCB *markP,*f;markP=head;if(pcb!=NULL)if(pcb=head)f=head;head=head->next;free(f);elsethisP=head->next;while(thisP!=NULL)if(pcb=thisP)f=thisP;markP->next=thisP->next;free(f);break;elsemarkP=thisP;thisP=thisP

23、->next;void releaseR(struct PCB *pcb)/刪除就緒列表中進(jìn)程節(jié)點(diǎn)struct PCB *markP,*f;markP=readyHead;if(pcb!=NULL)if(pcb=readyHead)f=readyHead;readyHead=readyHead->next;free(f);elsethisP=readyHead->next;while(thisP!=NULL)if(pcb=thisP)f=thisP;markP->next=thisP->next;free(f);break;elsemarkP=thisP;this

24、P=thisP->next;void ListAllPCB(struct PCB *h)/打印所有進(jìn)程printFieldP();if(h=NULL)printf("沒有進(jìn)程。n");elsethisP=h;while(thisP!=NULL)printPCBP(thisP);thisP=thisP->next;printf("n按任意鍵繼續(xù).n");getch();printf("nn");void printPCB(struct PCB *pcb,int a,int b,int c,double d)/打印單個(gè)數(shù)據(jù)結(jié)果

25、if(pcb!=NULL)printf("%-8s%-8d%-8d%-8d%-8d",pcb->name,pcb->No,pcb->priority,pcb->enterMemoryTime,pcb->serviceTime);printf("%-8d%-8d%-8d%-8.2lfn",a,b,c,d);elseprintf("沒有進(jìn)程。n");void printPCBP(struct PCB *pcb)if(pcb!=NULL)printf("%-8s%-8d%-8d%-8d%-8dn&qu

26、ot;,pcb->name,pcb->No,pcb->priority,pcb->enterMemoryTime,pcb->serviceTime);elseprintf("沒有進(jìn)程。n");void printField()/打印表頭，以及周轉(zhuǎn)時(shí)間printf("n");printf("進(jìn)程名t進(jìn)程號(hào)t優(yōu)先級(jí)t到達(dá)時(shí)t服務(wù)時(shí)t開始執(zhí)t完成時(shí)t周轉(zhuǎn)時(shí)t帶權(quán)周n");printf("ttt間t間t行時(shí)間t間t間t轉(zhuǎn)時(shí)間n");void printFieldP()/打印表頭，字段print

27、f("n");printf("進(jìn)程名t進(jìn)程號(hào)t優(yōu)先級(jí)t到達(dá)時(shí)t服務(wù)時(shí)n");printf("ttt間t間n");/從文件讀取數(shù)據(jù)/*數(shù)據(jù)格式如下進(jìn)程名優(yōu)先級(jí)到達(dá)時(shí)間服務(wù)時(shí)間proc12110proc22111proc3322*/void readFromFile()FILE *fp;int times;int i=0;char filePath20,temp8;char name16;int pri,emt,st;printf("輸入文件路徑：");scanf("%s",filePath);fp

28、=fopen(filePath,"r");times=timeOfData(fp);ProcessAmount=times-2;while(i<times-1)if(i=0)/這是用來接收文本格式第一行的漢字。fscanf(fp,"%s",temp);fscanf(fp,"%s",temp);fscanf(fp,"%s",temp);fscanf(fp,"%s",temp);else/以下用來接收進(jìn)程數(shù)據(jù)fscanf(fp,"%s",name);fscanf(fp,&q

29、uot;%d",&pri);fscanf(fp,"%d",&emt);fscanf(fp,"%d",&st);setNewPCB(name,pri,emt,st);i+;fclose(fp);void setNewPCB(char *name,int pri,int entime,int sertime)/賦值建立PCB，用于從文本中獲取數(shù)據(jù)newP=(struct PCB *)malloc(sizeof(struct PCB);if(head=NULL)head=newP;elsethisP=head;while(thisP->next!=NULL)thisP=thisP->next;thisP->next=newP;thisP=newP;thisP->No=SequenceNumber;SequenceNumber+;strcpy(th