操作系統(tǒng)-進程調度模擬算法(附源碼)（完整版）

進程調度模擬算法課程名稱：計算機操作系統(tǒng)實驗者姓名：李琛評分：班級：信 1501-2實驗日期： 2018年 5月 1日教師簽名：一、實驗目的進程調度是處理機管理的核心內容。本實驗要求用高級語言編寫模擬進程調度程序，以便加深理解有關進程控制快、進程隊列等概念，并體會和了解優(yōu)先數(shù)算法和時間片輪轉算法的具體實施辦法。二、實驗要求1.設計進程控制塊 PCB的結構，通常應包括如下信息：進程名、進程優(yōu)先數(shù)（或輪轉時間片數(shù)）、進程已占用的 CPU 時間、進程到完成還需要的時間、進程的狀態(tài)、當前隊列指針等。2.編寫兩種調度算法程序：優(yōu)先數(shù)調度算法程序循環(huán)輪轉調度算法程序3.按要求輸出結果。三、實驗過程分別用兩種調度算法對伍個進程進行調度。每個進程可有三種狀態(tài)；執(zhí)行狀態(tài)（RUN）、就緒狀態(tài)（ READY,包括等待狀態(tài)）和完成狀態(tài)（FINISH），并假定初始狀態(tài)為就緒狀態(tài)。（一）進程控制塊結構如下：NAME 進程標示符PRIO/ROUND進程優(yōu)先數(shù) /進程每次輪轉的時間片數(shù)（設為常數(shù)CPUTIME進程累計占用 CPU的時間片數(shù)NEEDTIME 進程到完成還需要的時間片數(shù)STATE 進程狀態(tài)2）NEXT 鏈指針注：1.為了便于處理，程序中進程的的運行時間以時間片為單位進行計算；2.各進程的優(yōu)先數(shù)或輪轉時間片數(shù)，以及進程運行時間片數(shù)的初值，均由用戶在程序運行時給定。 （二）進程的就緒態(tài)和等待態(tài)均為鏈表結構，共有四個指針如下：RUN 當前運行進程指針READY 就需隊列頭指針TAIL 就需隊列尾指針FINISH 完成隊列頭指針（三）程序說明1.在優(yōu)先數(shù)算法中，進程優(yōu)先數(shù)的初值設為：50-NEEDTIME每執(zhí)行一次，優(yōu)先數(shù)減1，CPU時間片數(shù)加 1，進程還需要的時間片數(shù)減1。在輪CPU時2，并退出 CPU，排到就緒隊列尾，等待下轉法中，采用固定時間片單位（兩個時間片為一個單位），進程每輪轉一次，間片數(shù)加 2，進程還需要的時間片數(shù)減一次調度。2.程序的模塊結構如下：整個程序可由主程序和如下7個過程組成：2（1）INSERT1 在優(yōu)先數(shù)算法中，將尚未完成的PCB按優(yōu)先數(shù)順序插入到就緒隊列中；（2）INSERT2 在輪轉法中，將執(zhí)行了一個時間片單位（為進程2），但尚未完成的的 PCB，插到就緒隊列的隊尾；（3）FIRSTIN 調度就緒隊列的第一個進程投入運行；（4）PRINT 顯示每執(zhí)行一次后所有進程的狀態(tài)及有關信息。（5）CREATE創(chuàng)建新進程，并將它的（6）PRISCH 按優(yōu)先數(shù)算法調度進程；PCB插入就緒隊列；（7）ROUNDSCH按時間片輪轉法調度進程。主程序定義 PCB結構和其他有關變量。實驗代碼：Main.cpp#include<iostream>#include<string>using namespace std;typedef struct nodechar name20;/進程名int prio;/進程優(yōu)先級int round;int cputime;int needtime;/分配 CPU的時間片執(zhí)行時間/CPU/進程執(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;if (ready != NULL)run->state = R;ready = ready->next;run->next = NULL;/優(yōu)先級輸出隊列void Output1()PCB *p;p = ready;while (p != NULL)cout << p->name << "t" << p->prio << "t" << p->cputime << "t" << p->needtime << "t " <<p->state << " t " << p->count << endl;p = p->next;p = finish;while (p != NULL)cout << p->name << "t" << p->prio << "t" << p->cputime << "t" << p->needtime << "t " <<p->state << " t " << p->count << endl;p = p->next;p = run; while (p != NULL)cout << p->name << "t" << p->prio << "t" << p->cputime << "t" << p->needtime << "t " <<p->state << " t " << p->count << endl;p = p->next;/輪轉法輸出隊列void Output2()PCB *p;p = ready;while (p != NULL)cout << p->name << "t" << p->round << "t" << p->cputime << "t" << p->needtime << "t " <<p->state << "t " << p->count << endl;p = p->next;p = finish;while (p != NULL)cout << p->name << "t" << p->round << "t" << p->cputime << "t" << p->needtime << "t " <<p->state << "t " << p->count << endl;p = p->next;p = run;while (p != NULL)cout << p->name << "t" << p->round << "t" << p->cputime << "t" << p->needtime << "t " <<p->state << "t " << p->count << endl;p = p->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 != NULL) /移動指針查找第一個比它小的元素的位置進行插入nxt = fst;fst = fst->next;if (fst->next = NULL) /已經搜索到隊尾，則其優(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)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)先級調度輸入函數(shù)void PrioCreate()PCB *tmp; int i;cout << "Enter the name and needtime：" << endl;for (i = 0; i < num; i+)if (tmp = (PCB *)malloc(sizeof(PCB) = NULL)cerr << "malloc" << endl;exit(1);cin >> tmp->name;getchar();cin >> tmp->needtime;tmp->cputime = 0;tmp->state = W;tmp->prio = 50 - tmp->needtime; /tmp->round = 0;設置其優(yōu)先級，需要的時間越多，優(yōu)先級越低tmp->count = 0;InsertPrio(tmp);/按照優(yōu)先級從高到低，插入到就緒隊列cout << "進程名t優(yōu)先級 tcpu時間t需要時間進程狀態(tài)計數(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" << endl;exit(1);cin >> 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需要時間進程狀態(tài)計數(shù)器 " << endl;/按照優(yōu)先級調度，每次執(zhí)行一個時間片void Priority()int flag = 1;GetFirst();while (run != NULL)Output1();while (flag)run->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+; /InsertTime(run);flag = 0;進程執(zhí)行的次數(shù)加一flag = 1;GetFirst(); /繼續(xù)取就緒隊列隊頭進程進入執(zhí)行隊列 void RoundRun() /時間片輪轉調度算法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; /InsertTime(run);計數(shù)器清零，為下次做準備flag = 0;flag = 1;GetFirst();int main(void)int n;cout << "輸入進程個數(shù)： " << endl;cin >> num;getchar(); cout << "-進程調度算法模擬 -" << endl;、優(yōu)先級調度算法 " << endl;cout << "cout << "12、循環(huán)輪轉調度算法" << endl;cout << "-" << endl;cout << "輸入選擇序號： " << endl;cin >> n;switch (n)case 1:cout << "優(yōu)先級調度 :" << endl;PrioCreate();Priority();Output1();break;case 2:cout << "循環(huán)輪轉算法 :" << endl;TimeCreate();RoundRun();Output2();break;case 0:exit(1);break;default:cout << "Enter error!" << endl;break;cout << endl;return 0;四、實驗結果優(yōu)先級調度 時間片輪轉法 五、實驗總結通過本次實驗，我學到了進程調度算法，了解了進程調度是CPU管理的核心，不同的,這就會有一個算法選擇的問題 .,以及對進程調度算法的理解。調度算法會使得進程運行時間不同,運行的先后順序也不同掌握了用 C語言實現(xiàn)進程調度算法的模擬，提高了編程能力在思考上出現(xiàn)的一個問題是,隊列是先進先出的 ,在優(yōu)先級算法中怎么來向鏈表中插入新的進程,使其能夠按優(yōu)先級排序 .第一想到的是用數(shù)組，后來發(fā)現(xiàn)不如鏈表方便，所以換成鏈表，但是發(fā)現(xiàn)自己用鏈表有待提高.