基于反饋(Feed-Back-FB)排隊(duì)算法的CPU調(diào)度的模擬實(shí)現(xiàn)資料

1、精選優(yōu)質(zhì)文檔-傾情為你奉上JLU操作系統(tǒng) 課程設(shè)計(jì)基于反饋（Feed Back，F(xiàn)B）排隊(duì)算法的CPU調(diào)度的模擬實(shí)現(xiàn)操作系統(tǒng)課程設(shè)計(jì)報(bào)告姓名學(xué)號(hào)一組實(shí)驗(yàn)室：提交日期成績(jī)指導(dǎo)教師實(shí)驗(yàn)題目：基于反饋（Feed Back，F(xiàn)B）排隊(duì)算法的CPU調(diào)度的模擬實(shí)現(xiàn)實(shí)驗(yàn)要求：功能要求：（1）就緒隊(duì)列設(shè)置（界面） 設(shè)置就緒隊(duì)列個(gè)數(shù)（3）及每個(gè)就緒隊(duì)列優(yōu)先級(jí)和每個(gè)就緒隊(duì)列時(shí)間片；（2）運(yùn)行結(jié)果（界面） 模擬動(dòng)態(tài)創(chuàng)建多個(gè)進(jìn)程，依據(jù)反饋排隊(duì)算法調(diào)度原理，動(dòng)態(tài)顯示就緒隊(duì)列中的進(jìn)程、進(jìn)程的剩余時(shí)間及占有CPU的進(jìn)程； 動(dòng)態(tài)顯示等待隊(duì)列中的進(jìn)程（假設(shè)當(dāng)前只有一個(gè)事件的等待隊(duì)列）； 具體細(xì)節(jié)實(shí)現(xiàn)（1）設(shè)置多個(gè)進(jìn)程（進(jìn)程名、

2、運(yùn)行時(shí)間）進(jìn)入就緒隊(duì)列；（2）依據(jù)反饋排隊(duì)算法的調(diào)度原理，對(duì)就緒隊(duì)列中的進(jìn)程進(jìn)行調(diào)度或使進(jìn)程進(jìn)入相應(yīng)的就緒隊(duì)列；（3）當(dāng)就緒隊(duì)列中進(jìn)程被調(diào)度，要啟動(dòng)一個(gè)相對(duì)時(shí)鐘以反映運(yùn)行的時(shí)間片；（4）一個(gè)進(jìn)程占有CPU運(yùn)行時(shí)，要隨機(jī)產(chǎn)生I/O請(qǐng)求或I/O請(qǐng)求完成；（5）當(dāng)隨機(jī)產(chǎn)生I/O請(qǐng)求時(shí)，占有CPU的進(jìn)程要進(jìn)入等待隊(duì)列；（6）當(dāng)隨機(jī)產(chǎn)生I/O完成時(shí)，等待隊(duì)列的進(jìn)程要進(jìn)入相應(yīng)的就緒隊(duì)列； 所需數(shù)據(jù)結(jié)構(gòu)：typedef struct QNode typedef struct char name5; QueuePtr front;/隊(duì)頭指針 int time; QueuePtr rear; / 隊(duì)尾指針 in

3、t timeType; LinkQueue; struct QNode *next; QNode,*QueuePtr; 算法設(shè)計(jì)：多級(jí)反饋隊(duì)列調(diào)度算法，不必事先知道各進(jìn)程所需的進(jìn)程時(shí)間，而且還可以滿足各種類型進(jìn)程的需要，因而它是目前被公認(rèn)的一種較好的進(jìn)程調(diào)度算法。在采用多級(jí)反饋隊(duì)列調(diào)度算法的系統(tǒng)中，調(diào)度算法的實(shí)施過程如下：1 設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。第一個(gè)隊(duì)列的優(yōu)先權(quán)最高，第二個(gè)的次之，其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低。該算法賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就愈小。例如，第二個(gè)隊(duì)列的時(shí)間片要比第一個(gè)隊(duì)列的時(shí)間片長(zhǎng)

4、一倍，第I+1個(gè)隊(duì)列的時(shí)間片要比第I個(gè)隊(duì)列的時(shí)間片長(zhǎng)一倍。2 一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放在第一隊(duì)列的末尾，按FCFS原則排隊(duì)等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如它能在該時(shí)間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)，如果它在一個(gè)時(shí)間片結(jié)束時(shí)尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊(duì)列的末尾，再同樣地按FCFS原則等待調(diào)度執(zhí)行；如果它在第二隊(duì)列中運(yùn)行一個(gè)時(shí)間片后仍未完成，再依次將它放入第三隊(duì)列，如此下去，當(dāng)一個(gè)長(zhǎng)作業(yè)（進(jìn)程）從第一隊(duì)列依次降到第n隊(duì)列后，在第n隊(duì)列中便采取按時(shí)間片輪轉(zhuǎn)的方式進(jìn)行。3 僅當(dāng)?shù)谝魂?duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行；僅當(dāng)?shù)?（I-1）隊(duì)列均空時(shí)，才會(huì)調(diào)度第I隊(duì)列中為某進(jìn)程服務(wù)

5、時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊(duì)列（第1（I-1）中的任何一個(gè)隊(duì)列），則此時(shí)新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第I隊(duì)列的末尾，把處理機(jī)分配給新到的高優(yōu)先權(quán)進(jìn)程。開始流程圖：創(chuàng)建四級(jí)就緒隊(duì)列及等待隊(duì)列 輸入若干進(jìn)程信息新進(jìn)程入就緒第一隊(duì)列該進(jìn)程插入本隊(duì)列隊(duì)尾取對(duì)頭進(jìn)程執(zhí)行一次操作運(yùn)行原進(jìn)程 否撤離系統(tǒng)任務(wù)是否完成 當(dāng)前隊(duì)列是否為第一對(duì)隊(duì)列 是 是 否入下個(gè)隊(duì)列隊(duì)尾 是否有新進(jìn)程到達(dá)新進(jìn)程入第一對(duì)列 按FCFS 執(zhí)行本隊(duì)列中的進(jìn)程 否 否執(zhí)行中是否有新進(jìn)程來 是 否進(jìn)程是否完成 是 否 下隊(duì)列是否為最后隊(duì)列 否 是入該隊(duì)列且進(jìn)程按時(shí)間片輪轉(zhuǎn)法執(zhí)行 時(shí)間片內(nèi)是否完成

6、 否 是 完成 圖一執(zhí)行中選擇阻塞進(jìn)程 進(jìn)程進(jìn)入阻塞隊(duì)列 選擇喚醒進(jìn)程 是進(jìn)程進(jìn)入第一級(jí)等待隊(duì)列末尾隊(duì)列 完成 圖二 執(zhí)行中選擇撤銷進(jìn)程 進(jìn)程被撤銷隊(duì)列 刪除當(dāng)前運(yùn)行進(jìn)程 完成 圖三 多級(jí)反饋隊(duì)列算法實(shí)現(xiàn)流程圖圖解：圖一：展示了程序的具體流程。首先輸入進(jìn)程首先將它放在第一隊(duì)列的末尾，按FCFS原則排隊(duì)等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如它能在該時(shí)間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)，如果它在一個(gè)時(shí)間片結(jié)束時(shí)尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊(duì)列的末尾，再同樣地按FCFS原則等待調(diào)度執(zhí)行，以此類推得出結(jié)果； 圖二：展示了進(jìn)程阻塞喚醒的過程 圖三：展示了進(jìn)程撤銷的過程。任務(wù)分工及各分工實(shí)現(xiàn)方法：組長(zhǎng)學(xué)號(hào)及姓

7、名：分工：一直以來?yè)?dān)任組長(zhǎng)，要做的事很多，既要給組員分排任務(wù)，安排每個(gè)人的在課程設(shè)計(jì)要完成的任務(wù)，又要協(xié)調(diào)各個(gè)之間的分歧與合作，盡量融合大家的各種想法，匯總好的建議，好的做法，達(dá)到我們組的團(tuán)體合作精神，這樣才能把課程設(shè)計(jì)做的更好。負(fù)責(zé)算法的總體設(shè)計(jì)程序的全局變量和編寫多級(jí)調(diào)度函數(shù)，整理每個(gè)人的工作，組合成整個(gè)算法。聽取大家提出的問題和建議，完善算法。 組員1學(xué)號(hào)及姓名：分工：設(shè)計(jì)程序中主要的進(jìn)程控制塊信息及其需要的變量，交由組討論決定。編寫系統(tǒng)中模塊的程序進(jìn)程插入進(jìn)程到隊(duì)尾、取對(duì)頭進(jìn)程函數(shù)。參與程序的調(diào)試。組員2學(xué)號(hào)及姓名：分工：設(shè)計(jì)程序多級(jí)反饋隊(duì)列的具體實(shí)現(xiàn)方式，由組共同討論決定。編寫就緒隊(duì)

8、列創(chuàng)建函數(shù)，以及將就緒隊(duì)列鏈棧起來。參與測(cè)試程序。測(cè)試結(jié)果：總結(jié)（對(duì)所作程序進(jìn)行分析、評(píng)價(jià)運(yùn)行效果，總結(jié)遇到的問題和解決辦法）本程序基本上實(shí)現(xiàn)了多級(jí)反饋隊(duì)列調(diào)度算法，能夠創(chuàng)建新進(jìn)程進(jìn)入系統(tǒng)，系統(tǒng)按照設(shè)定的調(diào)度策略選擇進(jìn)程執(zhí)行。新進(jìn)程全部入第一級(jí)就緒隊(duì)列，按FCFS取對(duì)頭進(jìn)程執(zhí)行，在時(shí)間片沒有完成插入下一個(gè)隊(duì)列隊(duì)尾，在執(zhí)行的過程中可以插入新進(jìn)程。新進(jìn)程可以搶的當(dāng)前進(jìn)程的執(zhí)行；如果所有進(jìn)程都進(jìn)入了第四級(jí)隊(duì)列，便按時(shí)間片輪轉(zhuǎn)法執(zhí)行。 經(jīng)過了一周的設(shè)計(jì)時(shí)間，我們?nèi)w組員共同的努力下，終于完成了多級(jí)反饋隊(duì)列調(diào)度算法的從設(shè)計(jì)到編程測(cè)試再到提交設(shè)計(jì)報(bào)告，完成了我們小組的課程設(shè)計(jì)任務(wù)。通過對(duì)多級(jí)反饋隊(duì)列調(diào)度算

9、法的模擬，大家一起討論。一起設(shè)計(jì)。編寫程序，在一起合作中，編程的能力得到增強(qiáng)，培養(yǎng)了自己的團(tuán)隊(duì)合作精神。最難的還是多級(jí)調(diào)度，剛開始不知道具體該怎樣做的，各個(gè)模塊在一個(gè)大的模塊中實(shí)現(xiàn)多級(jí)調(diào)度，把一些其他的功能分別按照不同的作用，設(shè)置成一個(gè)個(gè)模塊，進(jìn)程的創(chuàng)建，取對(duì)頭進(jìn)程，進(jìn)程插入隊(duì)尾等等。把整個(gè)程序的主要部分集中在一個(gè)模塊中，其中使用其他部分的模塊組合成功能齊全的多級(jí)調(diào)度實(shí)施算法。主程序中調(diào)用這樣的模塊，便可實(shí)現(xiàn)了基本的調(diào)度模擬。 在實(shí)際編寫程序，有時(shí)想的和做的是不很一樣的，在設(shè)計(jì)時(shí)函數(shù)功能是這樣實(shí)現(xiàn)，但實(shí)際時(shí)，又往往不是這樣，還有多方面考慮。有些功能需要反復(fù)多次使用，如果把它單獨(dú)編寫成一個(gè)功能模

10、塊完，這樣便可實(shí)現(xiàn)全局的應(yīng)用，減少代碼的長(zhǎng)度。不足與改進(jìn)：設(shè)計(jì)的模擬算法還不是很好的，有需要完善的地方，程序中創(chuàng)建新進(jìn)程是，感覺只輸入進(jìn)程的名字也不太好，還有創(chuàng)建的新進(jìn)程名重復(fù)沒把它考慮進(jìn)去，導(dǎo)致輸入已有的進(jìn)程名，程序不能識(shí)別，仍然可以執(zhí)行插入。隨機(jī)有新進(jìn)程的到來，沒能完全做到，我們只是沒間隔固定的時(shí)間，就可以輸入新進(jìn)程，模擬新進(jìn)程的隨機(jī)到來?？梢园呀缑孀龅母烙^一些，演示出每次執(zhí)行的動(dòng)態(tài)變化的結(jié)果，能夠使程序的運(yùn)行更加清晰明了。程序代碼：/ 223.cpp : Defines the entry point for the console application./#include &quo

11、t;stdafx.h"#include <STRING.H> /Definitions for memory and string functions. #include <CTYPE.H> /Defines the ctype macros. #include <MALLOC.H> /memory management functions and variables. #include <STDIO.H> #include <STDLIB.H> #include <IO.H> /Definitions for

12、low level I/O functions. #include <PROCESS.H> /Symbols and structures for process management. #include <CONIO.H> /Direct MSDOS console input/output. #include <WINDOWS.H> #include <TIME.H> / Struct and function declarations for dealing with time. #include <DOS.H> /Define

13、s structs, unions, macros, and functions for dealing /with MSDOS and the Intel iAPX86 microprocessor family. / 函數(shù)結(jié)果狀態(tài)代碼 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 / typedef int Status; /指定用Status和Boolean代表int類型typedef int Boolean; / typedef

14、struct QNode char name5; int time; int timeType; struct QNode *next; QNode,*QueuePtr; typedef struct QueuePtr front;/隊(duì)頭指針 QueuePtr rear; / 隊(duì)尾指針 LinkQueue; int count=0; /時(shí)間計(jì)數(shù)變量 LinkQueue qRun,qWait,qReady1,qReady2,qReady3,qReady4; / void menu1(); void menu2(); void gotoxy(int x,int y); void clrscr(vo

15、id); /清屏函數(shù) void clreol(void); /在文本窗口中清除字符到行末 void clreoscr(void); /clear end of screenStatus InitQueue(LinkQueue &Q); Status creatPro(LinkQueue &quePro); void dealTime(); void runPro(void); void run(); void wait(); void wake(); void endPro(); / /DOS界面坐標(biāo)定位函數(shù)/ void gotoxy(int x,int y) CONSOLE_

16、SCREEN_BUFFER_INFO csbiInfo; /variablendklaration HANDLE hConsoleOut; hConsoleOut = GetStdHandle(STD_OUTPUT_HANDLE); GetConsoleScreenBufferInfo(hConsoleOut,&csbiInfo); csbiInfo.dwCursorPosition.X = x; /cursorposition X koordinate festlegen csbiInfo.dwCursorPosition.Y = y; /cursorposition Y koord

17、inate festlegen SetConsoleCursorPosition(hConsoleOut,csbiInfo.dwCursorPosition); /den cursor an die festgelegte koordinate setzen Status InitQueue(LinkQueue &Q) / 構(gòu)造一個(gè)空隊(duì)列Q if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode) exit(OVERFLOW); Q.front->next=NULL; return OK; Status EnQueue(LinkQueu

18、e &Q,char e5,int proTime,int tType) / 插入元素e為Q的新的隊(duì)尾元素 QueuePtr p; if(!(p=(QueuePtr)malloc(sizeof(QNode) / 存儲(chǔ)分配失敗 exit(OVERFLOW); strcpy(p->name,e); p->time=proTime; p->timeType=tType; p->next=NULL; Q.rear->next=p; Q.rear=p; return OK; Status DeQueue(LinkQueue &Q,char e5) / 若隊(duì)列不

19、空,刪除Q的隊(duì)頭元素,用e返回其值,并返回OK,否則返回ERROR QueuePtr p; if(Q.front=Q.rear) return ERROR; p=Q.front->next; strcpy(e,p->name); Q.front->next=p->next; if(Q.rear=p) Q.rear=Q.front; free(p); return OK; Status QueueTraverse(LinkQueue &Q,int x,int y) QueuePtr p; p=Q.front->next; while(p) gotoxy(x,

20、y); printf("%s",p->name); gotoxy(x,y+1); printf("%d",p->time); p=p->next; x+=6; printf("n"); return OK; void print() if(qRun.front!=qRun.rear) QueueTraverse(qRun,17,5); if(qWait.front!=qWait.rear) QueueTraverse(qWait,17,8); if(qReady1.front!=qReady1.rear) Queue

21、Traverse(qReady1,17,11); if(qReady2.front!=qReady2.rear) QueueTraverse(qReady2,17,14); if(qReady3.front!=qReady3.rear) QueueTraverse(qReady3,17,17); if(qReady4.front!=qReady4.rear) QueueTraverse(qReady4,17,20); Status creatPro(LinkQueue &quePro) char proName5; int proTime; QueuePtr p; b: gotoxy(

22、22,3); printf("進(jìn)程名: "); gotoxy(36,3); printf("所需時(shí)間: "); gotoxy(30,3); scanf("%s",&proName); gotoxy(46,3); scanf("%d",&proTime); if(proTime<=0) gotoxy(22,3); printf("信息提示: 輸入時(shí)間錯(cuò)誤!請(qǐng)按Enter鍵返回!");gotoxy(15,3); getchar();getchar(); gotoxy(0,0);

23、 menu1(); goto b; getchar(); if(!(p=(QueuePtr)malloc(sizeof(QNode) / 存儲(chǔ)分配失敗 exit(OVERFLOW); strcpy(p->name,proName); p->time=proTime; p->timeType=10; /進(jìn)入時(shí)間片為10的就緒隊(duì)列,即優(yōu)先級(jí)最高的就緒隊(duì)列 p->next=NULL; quePro.rear->next=p; quePro.rear=p; return OK; void dealTime() char e5; int tType=qRun.front-&

24、gt;next->timeType; +count; qRun.front->next->time-; if(qRun.front->next->time=0) DeQueue(qRun,e); runPro(); count=0; else if(qRun.front->next->timeType=count) if(qRun.front->next->timeType=10) EnQueue(qReady2,qRun.front->next->name,qRun.front->next->time,tType+

25、10); if(qRun.front->next->timeType=20) EnQueue(qReady3,qRun.front->next->name,qRun.front->next->time,tType+20); if(qRun.front->next->timeType=40) EnQueue(qReady4,qRun.front->next->name,qRun.front->next->time,80); if(qRun.front->next->timeType=80) EnQueue(qRe

26、ady4,qRun.front->next->name,qRun.front->next->time,80); DeQueue(qRun,e); runPro(); count=0; void runPro(void) char e5; int pTime,f1=0,f2=0,f3=0,f4=0; if(qReady1.front!=qReady1.rear) pTime=qReady1.front->next->time; EnQueue(qRun,qReady1.front->next->name,pTime,qReady1.front-&g

27、t;next->timeType); DeQueue(qReady1,e); f1=1; else if(qReady2.front!=qReady2.rear) pTime=qReady2.front->next->time; EnQueue(qRun,qReady2.front->next->name,pTime,qReady2.front->next->timeType); DeQueue(qReady2,e); f2=1; else if(qReady3.front!=qReady3.rear) pTime=qReady3.front->

28、next->time; EnQueue(qRun,qReady3.front->next->name,pTime,qReady3.front->next->timeType); DeQueue(qReady3,e); f3=1; else if(qReady4.front!=qReady4.rear) pTime=qReady4.front->next->time; EnQueue(qRun,qReady4.front->next->name,pTime,qReady4.front->next->timeType); DeQue

29、ue(qReady4,e); f4=1; gotoxy(0,4); menu2(); if(f1=0 && f2=0 && f3=0 && f4=0) gotoxy(0,0); menu1(); gotoxy(22,3); printf("信息提示:無(wú)就緒進(jìn)程,請(qǐng)輸入其他功能選項(xiàng)!"); gotoxy(0,4); menu2(); void run() if(qRun.front=qRun.rear) runPro(); else dealTime(); void endPro() char e5; if(qRun.front

30、=qRun.rear) gotoxy(0,0); menu1(); gotoxy(22,3); printf("信息提示:無(wú)運(yùn)行進(jìn)程,請(qǐng)按Enter鍵運(yùn)行進(jìn)程!"); gotoxy(15,3); else DeQueue(qRun,e); gotoxy(0,0); menu1(); gotoxy(22,3); printf("信息提示:選擇菜單功能或按Enter鍵執(zhí)行進(jìn)程!"); gotoxy(0,4); menu2(); print(); void wait() char e5; if(qRun.front!=qRun.rear) EnQueue(qW

31、ait,qRun.front->next->name,qRun.front->next->time,qRun.front->next->timeType); DeQueue(qRun,e); gotoxy(0,4); menu2(); print(); gotoxy(22,3); printf("信息提示: 選擇菜單功能或按Enter鍵執(zhí)行進(jìn)程!"); else gotoxy(0,0); menu1(); gotoxy(22,3); printf("信息提示:無(wú)運(yùn)行進(jìn)程,請(qǐng)輸入其他功能選項(xiàng)!"); void wake(

32、) char e5; if(qWait.front!=qWait.rear) EnQueue(qReady1,qWait.front->next->name,qWait.front->next->time,qWait.front->next->timeType); DeQueue(qWait,e); gotoxy(0,4); menu2(); print(); gotoxy(22,3); printf("信息提示: 選擇菜單功能或按Enter鍵執(zhí)行進(jìn)程!"); else gotoxy(0,0); menu1(); gotoxy(22,3)

33、; printf("信息提示:無(wú)等待進(jìn)程,請(qǐng)輸入其他功能選項(xiàng)!"); void menu1() printf(" n"); printf(" 1-> 創(chuàng)建進(jìn)程 2-> 撤銷進(jìn)程3-> 阻塞進(jìn)程4-> 喚醒進(jìn)程0->退出系統(tǒng) n"); printf(" n"); printf(" 菜單選擇: n"); void menu2() printf(" n"); printf(" Run: n"); printf(" Time n"); printf(" n"); printf(" Wait: n"); printf(" Time n"); printf(" n"); printf(" Ready1 n"); printf(" Time:10 n"); printf(&q