操作系統(tǒng)-進程調(diào)度模擬算法(附源碼)

1、進程調(diào)度模擬算法課程名稱：計算機操作系統(tǒng) 班級：信1501-2實驗者姓名：李琛 實驗日期：2018年5月1日評分： 教師簽名：一、實驗?zāi)康倪M程調(diào)度是處理機管理的核心內(nèi)容。本實驗要求用高級語言編寫模擬進程調(diào)度程序，以 便加深理解有關(guān)進程控制快、進程隊列等概念，并體會和了解優(yōu)先數(shù)算法和時間片輪轉(zhuǎn)算法 的具體實施辦法。二、實驗要求1.設(shè)計進程控制塊 PCB 的結(jié)構(gòu)，通常應(yīng)包括如下信息：進程名、進程優(yōu)先數(shù)（或輪轉(zhuǎn)時間片數(shù)）、進程已占用的 CPU 時間、進程到完成還需要的時間、進程的狀態(tài)、當(dāng)前隊列指針等。2.編寫兩種調(diào)度算法程序：優(yōu)先數(shù)調(diào)度算法程序循環(huán)輪轉(zhuǎn)調(diào)度算法程序3.按要求輸出結(jié)果。三、實驗過程分別

2、用兩種調(diào)度算法對伍個進程進行調(diào)度。每個進程可有三種狀態(tài)；執(zhí)行狀態(tài)（RUN）、就緒狀態(tài)（READY,包括等待狀態(tài)）和完成狀態(tài)（FINISH），并假定初始狀態(tài)為就緒狀態(tài)。 （一）進程控制塊結(jié)構(gòu)如下： NAME進程標(biāo)示符 PRIO/ROUND進程優(yōu)先數(shù)/進程每次輪轉(zhuǎn)的時間片數(shù)（設(shè)為常數(shù) 2） CPUTIME進程累計占用 CPU 的時間片數(shù) NEEDTIME進程到完成還需要的時間片數(shù) STATE進程狀態(tài) NEXT鏈指針 注： 1.為了便于處理，程序中進程的的運行時間以時間片為單位進行計算； 2.各進程的優(yōu)先數(shù)或輪轉(zhuǎn)時間片數(shù)，以及進程運行時間片數(shù)的初值，均由用戶在程序運行時給定。（二）進程的就緒態(tài)和等待

3、態(tài)均為鏈表結(jié)構(gòu)，共有四個指針如下： RUN當(dāng)前運行進程指針 READY就需隊列頭指針 TAIL 就需隊列尾指針 FINISH 完成隊列頭指針（三）程序說明 1. 在優(yōu)先數(shù)算法中，進程優(yōu)先數(shù)的初值設(shè)為： 50-NEEDTIME每執(zhí)行一次，優(yōu)先數(shù)減 1，CPU 時間片數(shù)加 1，進程還需要的時間片數(shù)減 1。在輪轉(zhuǎn)法中，采用固定時間片單位（兩個時間片為一個單位），進程每輪轉(zhuǎn)一次，CPU時間片數(shù)加 2，進程還需要的時間片數(shù)減 2，并退出 CPU，排到就緒隊列尾，等待下一次調(diào)度。 2. 程序的模塊結(jié)構(gòu)如下： 整個程序可由主程序和如下 7 個過程組成： 2 （1）INSERT1在優(yōu)先數(shù)算法中，將尚未完成的

4、PCB 按優(yōu)先數(shù)順序插入到就緒隊列中； （2）INSERT2在輪轉(zhuǎn)法中，將執(zhí)行了一個時間片單位（為 2），但尚未完成的進程的 PCB，插到就緒隊列的隊尾； （3）FIRSTIN調(diào)度就緒隊列的第一個進程投入運行； （4）PRINT顯示每執(zhí)行一次后所有進程的狀態(tài)及有關(guān)信息。 （5）CREATE創(chuàng)建新進程，并將它的 PCB 插入就緒隊列； （6）PRISCH按優(yōu)先數(shù)算法調(diào)度進程； （7）ROUNDSCH按時間片輪轉(zhuǎn)法調(diào)度進程。 主程序定義 PCB 結(jié)構(gòu)和其他有關(guān)變量。實驗代碼：Main.cpp#include#includeusing namespace std;typedef struct nod

5、echar name20; /進程名int prio; /進程優(yōu)先級int round; /分配CPU的時間片int cputime; /CPU執(zhí)行時間int needtime; /進程執(zhí)行所需時間char state; /進程狀態(tài)int count; /記錄執(zhí)行次數(shù)struct node *next; /鏈表指針PCB;int num;/定義三個隊列，就緒隊列，執(zhí)行隊列，完成隊列PCB *ready = NULL; /就緒隊列PCB *run = NULL; /執(zhí)行隊列PCB *finish = NULL; /完成隊列/取得第一個就緒節(jié)點void GetFirst()run = ready;

6、if (ready != NULL)run-state = R;ready = ready-next;run-next = NULL;/優(yōu)先級輸出隊列void Output1()PCB *p;p = ready;while (p != NULL)cout name t prio t cputime t needtime t state t count next;p = finish;while (p != NULL)cout name t prio t cputime t needtime t state t count next;p = run;while (p != NULL)cout n

7、ame t prio t cputime t needtime t state t count next;/輪轉(zhuǎn)法輸出隊列void Output2()PCB *p;p = ready;while (p != NULL)cout name t round t cputime t needtime t state t count next;p = finish;while (p != NULL)cout name t round t cputime t needtime t state t count next;p = run;while (p != NULL)cout name t round

8、t cputime t needtime t state t count next;/創(chuàng)建優(yōu)先級隊列/創(chuàng)建優(yōu)先級隊列，規(guī)定優(yōu)先數(shù)越小，優(yōu)先級越低 void InsertPrio(PCB *in)PCB *fst, *nxt;fst = nxt = ready;if (ready = NULL) /如果隊列為空，則為第一個元素 in-next = ready;ready = in;else /查到合適的位置進行插入 if (in-prio = fst-prio) /比第一個還要大，則插入到隊頭in-next = ready;ready = in;elsewhile (fst-next != NU

9、LL) /移動指針查找第一個比它小的元素的位置進行插入 nxt = fst;fst = fst-next;if (fst-next = NULL) /已經(jīng)搜索到隊尾，則其優(yōu)先級數(shù)最小，將其插入到隊尾即可 in-next = fst-next;fst-next = in;else /插入到隊列中nxt = in;in-next = fst;/將進程插入到就緒隊列尾部void InsertTime(PCB *in)PCB *fst;fst = ready;if (ready = NULL)in-next = ready;ready = in;elsewhile (fst-next != NULL)

10、fst = fst-next;in-next = fst-next;fst-next = in;/將進程插入到完成隊列尾部void InsertFinish(PCB *in)PCB *fst;fst = finish;if (finish = NULL)in-next = finish;finish = in;elsewhile (fst-next != NULL)fst = fst-next;in-next = fst-next;fst-next = in;/優(yōu)先級調(diào)度輸入函數(shù) void PrioCreate()PCB *tmp;int i;cout Enter the name and n

11、eedtime： endl;for (i = 0; i num; i+)if (tmp = (PCB *)malloc(sizeof(PCB) = NULL)cerr malloc tmp-name;getchar();cin tmp-needtime;tmp-cputime = 0;tmp-state = W;tmp-prio = 50 - tmp-needtime; /設(shè)置其優(yōu)先級，需要的時間越多，優(yōu)先級越低tmp-round = 0;tmp-count = 0;InsertPrio(tmp); /按照優(yōu)先級從高到低，插入到就緒隊列 cout 進程名t優(yōu)先級tcpu時間t需要時間 進程狀態(tài)

12、 計數(shù)器 endl;/時間片輸入函數(shù) void TimeCreate()PCB *tmp;int i;cout 輸入進程名字和進程時間片所需時間： endl;for (i = 0; i num; i+)if (tmp = (PCB *)malloc(sizeof(PCB) = NULL)cerr malloc tmp-name;getchar();cin tmp-needtime;tmp-cputime = 0;tmp-state = W;tmp-prio = 0;tmp-round = 2;tmp-count = 0;InsertTime(tmp);cout 進程名t輪數(shù)tCPU時間t需要時

13、間 進程狀態(tài) 計數(shù)器 prio -= 3; /優(yōu)先級減去三 run-cputime+; /CPU時間片加一 run-needtime-;/進程執(zhí)行完成的剩余時間減一 if (run-needtime = 0)/如果進程執(zhí)行完畢，將進程狀態(tài)置為F，將其插入到完成隊列 run-state = F;run-count+;InsertFinish(run);flag = 0;else /將進程狀態(tài)置為W，入就緒隊列run-state = W;run-count+; /進程執(zhí)行的次數(shù)加一InsertTime(run);flag = 0;flag = 1;GetFirst(); /繼續(xù)取就緒隊列隊頭進程進

14、入執(zhí)行隊列 void RoundRun() /時間片輪轉(zhuǎn)調(diào)度算法int flag = 1;GetFirst();while (run != NULL)Output2();while (flag)run-count+;run-cputime+;run-needtime-;if (run-needtime = 0) /進程執(zhí)行完畢 run-state = F;InsertFinish(run);flag = 0;else if (run-count = run-round)/時間片用完 run-state = W;run-count = 0; /計數(shù)器清零，為下次做準(zhǔn)備 InsertTime(ru

15、n);flag = 0;flag = 1;GetFirst();int main(void)int n;cout 輸入進程個數(shù)： num;getchar();cout -進程調(diào)度算法模擬- endl;cout 1、優(yōu)先級調(diào)度算法 endl;cout 2、循環(huán)輪轉(zhuǎn)調(diào)度算法 endl;cout - endl;cout 輸入選擇序號： n;switch (n)case 1:cout 優(yōu)先級調(diào)度: endl;PrioCreate();Priority();Output1();break;case 2:cout 循環(huán)輪轉(zhuǎn)算法: endl;TimeCreate();RoundRun();Output2();break;case 0:exit(1);break;default:cout Enter error! endl;break;cout endl;return