《操作系統(tǒng)-進程調度模擬算法(附源碼)（完整版）》由會員分享，可在線閱讀，更多相關《操作系統(tǒng)-進程調度模擬算法(附源碼)（完整版）（12頁珍藏版）》請在裝配圖網上搜索。
1、
進程調度模擬算法
課程名稱：計算機操作系統(tǒng)
實驗者姓名：李琛
評分：
班級：信 1501-2
實驗日期： 2018年 5月 1日
教師簽名：
一、實驗目的
進程調度是處理機管理的核心內容。
本實驗要求用高級語言編寫模擬進程調度程序，
以便加深理解有關進程控制快、進程隊列等概念，并體會和了解優(yōu)先數(shù)算法和時間片
輪轉算法的具體實施辦法。
二、實驗要求
1.設計進程控制塊 PCB的結構，通常應包括如下信息：
進程名、進程優(yōu)先數(shù)（或輪轉時間片數(shù)）、進程已占用的 CPU 時間、進程到完成還需要
的時間、進程的狀態(tài)、當前隊列指針等。
2、
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)
3、
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。在輪
4、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 ——顯示
5、每執(zhí)行一次后所有進程的狀態(tài)及有關信息。
（5）CREATE——創(chuàng)建新進程，并將它的
（6）PRISCH ——按優(yōu)先數(shù)算法調度進程；
PCB插入就緒隊列；
（7）ROUNDSCH——按時間片輪轉法調度進程。
主程序定義 PCB結構和其他有關變量。
實驗代碼：
Main.cpp
#include
#include
using namespace std;
typedef struct node
{
char name[20];
//
進程名
int prio;
//
進程優(yōu)先級
int round;
int cputi
6、me;
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()
7、
{
完成隊列
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 " <<
8、 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 <<
9、 "\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 << "\
10、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 <
11、< "\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;
12、
}
else
{
//
查到合適的位置進行插入
if (in->prio >= fst->prio) //
比第一個還要大，則插入到隊頭
{
in->next = ready;
ready = in;
}
else
{
while (fst->next != NULL) //
移動指針查找第一個比它小的元素的位置進行插入
{
nxt = fst;
fst = fst->next;
}
if (fst->next == NULL) //
{
已經搜索到隊尾，則其優(yōu)先級數(shù)最小，將其插入到隊尾即可
in->next = fst->next;
fst
13、->next = in;
}
else
{
//
插入到隊列中
nxt = in;
in->next = fst;
}
}
}
}
//將進程插入到就緒隊列尾部
void InsertTime(PCB *in)
{
PCB *fst;
fst = ready;
if (ready == NULL)
{
in->next = ready;
ready = in;
}
else
{
while (fst->next != NULL)
{
fst = fst->next;
}
in->next = fst->next;
fst->
14、next = in;
}
}
//將進程插入到完成隊列尾部
void InsertFinish(PCB *in)
{
PCB *fst;
fst = finish;
if (finish == NULL)
{
in->next = finish;
finish = in;
}
else
{
while (fst->next != NULL)
{
fst = fst->next;
}
in->next = fst->next;
fst->next = in;
}
}
//優(yōu)先級調度輸入函數(shù)
void PrioCreate()
{
PCB *tm
15、p;
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 - tm
16、p->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
17、 < 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時間\
18、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í)行完畢，將
19、進程狀態(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() //
{
時間片輪轉調度算法
i
20、nt 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;
21、 //
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 << "
1
2
、
22、循環(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();
23、
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)自己用鏈表有待提高
.
操作系統(tǒng)-進程調度模擬算法(附源碼)（完整版）
