时间片轮转算法和优先级调度算法C语言模拟实现.docx
《时间片轮转算法和优先级调度算法C语言模拟实现.docx》由会员分享,可在线阅读,更多相关《时间片轮转算法和优先级调度算法C语言模拟实现.docx(13页珍藏版)》请在冰点文库上搜索。
时间片轮转算法和优先级调度算法C语言模拟实现
时间片轮转算法与优先级调度算法C语言模拟实现收藏
一、I」得与要求亠进程调度就是处理机管理得核心内容。
本实验要求用高级语言编写模拟进程调度程序,以便加深理解有关进程控制快、进程队列等概念,并体会与了解优先数算法与时间片轮转算法得具体实施办法。
二、实验内容
1、设il•进程控制块PCB得结构,通常应包括如下信息:
进程名、进程优先数(或轮转时间片数)、进程已占用得CPU时间、进程到完成还需要得时间、进程得状态、当前队列指针等。
2、编写两种调度算法程序:
优先数调度算法程疗工循环轮转调度算法程序
3、按要求输出结果。
a三、提示与说明
分别用两种调度算法对伍个进程进行调度。
每个进程可有三种状态;执行状态(RUN)、就绪状态(READY,包括等待状态)与完成状态(FINISH),并假定初始状态为就绪状态。
丄
(一)进程控制块结构如下:
aNAME一一进程标示符
PRIO/ROUND一一进程优先数/进程每次轮转得时间片数(设为常数2)aCPUTIME——进程累计•占用CPU得时间片数亠NEEDTIME——进程到完成还需要得时间片数
STATE——进程状态aNEXT一一链指针亠注:
I、为了便于处理,程序中进程得得运行时间以时间片为单位进行计算;
2、各进程得优先数或轮转时间片数,以及进程运行时间片数得初值,均由用户在程序运行时给定。
金
(二)进程得就绪态与等待态均为链表结构,共有四个指针如下:
aRUN一一当前运行进程指针
READY就需队列头指针
TAIL一一就需队列尾指针
FINISH—一完成队列头指针
(三)程序说明1必、在优先数算法中,进程优先数得初值设为:
50—NEEDTIM&每执行一次,优先数减1,CPU时间片数加1,进程还需要得时间片数减1。
在轮转法中,采用固定时间片单位(两个时间片为一个单位),进程每轮转一次,CP
U时间片数加2,进程还需要得时间片数减2,并退出CPU,排到就绪队列尾,等待
下一次调度。
2a、程序得模块结构提示如下:
整个程序可由主程序与如下7个过程组成)INSERT1一一在优先数算法中,将尚未完成得PCB按优先数顺序插入到就绪队列中A
(2)INSERT2-一在轮转法中,将执行了一个时间片单位(为2),但尚未完成得进程得PCB,插到就绪队列得队尾;
(3)FIRSTIN一一调度就绪队列得第一个进程投入运行;a(4)PRINT一一显示每执行一次后所有进程得状态及有关信息“(5)CREATE一一创建新进程,并将它得PCB插入就绪队列;
(6)PRISCH一一按优先数算法调度进程;a(7)R0UNDSCH一一按时间片轮转法调度进程。
主程序定义PCB结构与其她有关变量。
»(四)运行与显示
程序开始运行后,首先提示:
请用户选择算法,输入进程名与相应得NEEDTIME值。
每次显示结果均为如下5个字段:
namecputimeneedtimeprioritystate*注:
1a.在state字段中,“R”代表执行态,"W”代表就绪(等待)态,“F”代表完成态。
厶•应先显示”R”态得,再显示态得,再显示态得。
a3•在"W"态中,以优先数高低或轮转顺序排队;在”F"态中,以完成先后顺序排队。
viewpIaincopytoc1ipboardprint?
1./*
2.操作系统实验之时间片轮转算法与优先级调度算法
3.ByVisualC++6、0
4.*/
#includevstdio、h>
#inelude
#inelude
typedefstructnode
{
charname[20];/*进程得划字*/
intprio;/次进程得优先级*/
intround;/*分配CPU得时间片*/
intcputime;/*cPU执行时间*/
intneedtime;/*进程执行所需要得时间*/
charstate;/*进程得状态,W—一就绪态,R——执行态,F——完成态*
/
intcount;/*记录执行得次数*/
structnode*next:
/*链表指针*/
}PCB;
PCB*ready=NULL,*run=NULL,*finish=NULL;/*定义三个队列,就绪
队列,执行队列与完成队列=7
intnum;
voidGetFirst();/*从就绪队列取得第一个节点*/
voidOutput();/*输出队列信息*/
voidInsertPrio(PCB*in);/*创建优先级队列,规左优先数越小,优先级越
高*/
voidInsertTime(PCB*in);/*时间片队列*/
voidInsertFinish(PCB*in):
/*时间片队列*/
voidPrioCreate();/*优先级输入函数*/
voidTimeCreate();/*时间片输入函数*/
voidPriority();/*按照优先级调度*/
voidRoundRun():
/*时间片轮转调度*/
intmain(void)
{
charchose;
printf(”请输入要创建得进程数目:
\n”);
Scanf("%d蔦&num):
getchar();
printf(”输入进程得调度方法:
(P/R)\n");
scanf(H%cHz&chose);
switch(chose)
{
Case'P':
case1p
PrioCreate();
Priority():
break:
caseR:
case'r
TimeCreate();
RoundRun();
break;
default:
break;
}
Output();
return0:
}
voidGetFirst()/*取得第一个就绪队列节点*/
<
run=ready;
if(ready!
=NULL)
{
run->state=;
ready=ready->next;
run->next=NULL;
}
}
voidOutput()/*输出队列信息*/
PCB*P;
P=ready;
prlntf(HiS程名\t优先级\t轮数\tcpu时间\t需要时间\t进程状态\t计数器\nH):
while(p!
=NULL)
<
printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,
P->prio,p->round,p—>cputime,p—>needtime,p->state,p->count);
p=p->next;
}
p=finish;
whiIe(p!
=NULL)
{
printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p—>name,p->prio,p->round,p—>cputime,p->needtime,p->state,p->count):
p=p->next;
}
p=run;
whi1e(p!
=NULL)
{
Printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p—>cputime,p->needtime,p->state>p->count);
P=p->next;
}
VOldInsertPrio(PCB*in)/*创建优先级队列,规泄优先数越小,优先级越
低*/
{
PCB*fst,*nxt:
fst=nxt=ready;
if(ready==NULL)/*如果队列为空,则为第一个元素*/
{
in->next=ready;
ready=in;
}
eIse/*查到合适得位置进行插入*/
{
if(in->prio>=fst->prio)/*比第一个还要大,则插入到队头*
/
{
in->next=ready:
ready=in;
}
eIse
{
whi1e(fst->next!
=NULL)/*務动指针查找第一个别它小得元素得位置进行插入*/
{
nxt=fst;
fst=fst->next;
}
if(fst->next==NULL)/*已经搜索到队尾,则其优先级数最小,将
英插入到队尾即可*/
in—>next=fst->next;
fst・>next=in;
}
else/*插入到队列中*/
{
nxt=in;
in—>next=fst;
}
}
}
}
VOidInsertTime(PCB*in)/*将进程插入到就绪队列尾部*/
{
PCB*fst;
fst=ready;
if(ready==NULL)
{
in->next=ready;
ready=in;
}
eIse
{
while(fst->next!
=NULL)
{
fst=fst->next;
}
in->next=fst->next;
fst->next=in;
VoidInsertFinish(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;
}
}
voidPrioCreate()/*优先级调度输入函数*/
<
PCB*tmp;
inti:
printf(u输入进程名字与进程所需时间:
\nM);for(i=0:
iif((tmp=(PCB*)malloc(sizeof(PCB)))==NULL)
perror("malloc");
exit
(1);
}
scanf("%s”,tmp—>name);
getchar();/*吸收回车符号*/
scanf(M%cT,&(tmp->needtime)):
tmp->cputime=0:
tmp->state=/W';
tmp->pri0=50—tmp->needtime;/*设置其优先级,需要得时间越多,优先级越低*/
tmp->round=0;
tmp->count=0;
InsertPrio(tmp);/*按照优先级从髙到低,插入到就绪队列*/
}
}
voidTimeCreate()/*时间片输入函数*/
{
PCB*tmp;
inti;
printf(“输入进程名字与进程时间片所需时间:
\n");
for(i=0;ii++)
{
if((tmp=(PCB*)malloc(sizeof(PCB)))==NULL)
{
perrorCmalloc1');
exit(l):
scanf("%s",tmp・>name):
getchar();
scanf(”%dH,&(tmp・>needtime));
tmp->cputime=0:
tmp->state=W;
tmp->prio=0;
tmp->round=2;/*假设每个进程所分配得时间片就是2*/
tmp->count=0:
InsertTime(tmp);
}
}
voidPriority()/*按照优先级调度,每次执行一个时间片*/
{
intflag=1;
GetFirst();
while(run!
=NULL)/次当就绪队列不为空时,则调度进程如执行队列执
行*/
{
Output():
/*输出每次调度过程中各个节点得状态*/
whiIe(flag)
{
run->prio-=3;/*优先级减去三*/
run->cputime++;/*CPU时间片加一*/
run->needtime-;/*进程执行完成得剩余时间减一*/
if(run->needtime==0)/*如果进程执行完毕,将进程状态垃为F,将其插入到完成队列=7
{
run->state=F;
run—〉count++;/*进程执行得次数加一*/
InsertFinish(run);
f1ag=0;
}
else/水将进程状态置为W,入就绪队列*/
{
run->state='w';
run->count+-l-;/*进程执行得次数加一夫/
InsertTime(run);
flag=0;
}
}
flag=1;
GetFirst();/*继续取就绪队列队头进程进入执行队列*/
}
}
voidRoundRun()/*时间片轮转调度算法*/
{
intf1ag=1;
GetFirst():
whi1e(run!
=NULL)
<
Output();
whi1e(flag)
{
run—>count++;
run->cputime++;
run->needtime——;
if(run—>needtime==0)/*进程执行完毕*/
「un・>state='F';
InsertFinish(run);
flag=0;
}
elseif(run->count==「un->「ound)/*时间片用完*/
{
「un->state=W;
run->count=0;/*讣数器淸零,为下次做准备*/
InsertTime(「un);
flag=0;
}
}
f1ag=1;
GetFirst();
}