进程模拟调度算法课程设计Word文件下载.doc
《进程模拟调度算法课程设计Word文件下载.doc》由会员分享，可在线阅读，更多相关《进程模拟调度算法课程设计Word文件下载.doc（26页珍藏版）》请在冰点文库上搜索。
（1）先来先服务算法：
如果早就绪的进程排在就绪队列的前面，迟就绪的进程排在
就绪队列的后面，那么先来先服务总是把当前处于就绪队列之首的那个进程调
度到运行状态。
（2）优先数算法：
即进程的执行顺序由高优先级到低优先级。
系统或用户按某种原则为进程指定一个优先级来表示该进程所享有的确调度优先权。
该算法核心是确定进程的优先级。
（3）时间片轮转算法：
固定时间片，每个进程在执行一个时间片后，轮到下一进程执行，知道所有的进程执行完毕。
处理器同一个时间只能处理一个任务。
处理器在处理多任务的时候，就要看请求的时间顺序，如果时间一致，就要进行预测。
挑到一个任务后，需要若干步骤才能做完，这些步骤中有些需要处理器参与，有些不需要（如磁盘控制器的存储过程）。
不需要处理器处理的时候，这部分时间就要分配给其他的进程。
原来的进程就要处于等待的时间段上。
经过周密分配时间，宏观上就象是多个任务一起运行一样，但微观上是有先后的，就是时间片轮换。
（4）多级反馈队列法：
又称反馈循环队列或多队列策略，主要思想是将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列，较高优先级的队列一般分配给较短的时间片。
处理器调度先从高级就绪进程队列中选取可占有处理器的进程，只有在选不到时，才从较低级的就绪进程队列中选取。
（5）短作业优先法：
对短进程优先调度的算法，它是从后备队列中选择一个或者若干个进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。
二．设计方案
2.1．先来先服务调度
2.1.1．算法思想
先来先服务调度算法的思想是按照进程进入就绪队列的先后顺序调度并分配处理机执行。
先来先服务调度算法是一种不可抢占的算法，先进入就绪队列的进程，先被处理机运行。
一旦一个进程占有了处理机，它就一直运行下去，直到该进程完成工作或者因为等待某事件而不能继续运行时才释放处理机。
2.1.2．算法流程图
图1.先来先服务算法流程图
2.1.3．程序代码
#include<
stdio.h>
stdlib.h>
string.h>
typedefstructnode
{
charname[10];
/*进程名*/
intcputime;
/*占用cpu时间*/
charstarttime[5];
//进程开始时间
intneedtime;
/*要求运行时间*/
charstate;
/*状态*/
structnode*next;
/*指针*/
}PCB;
PCB*ready,*run,*finish;
//就绪、执行、结束指针
intN;
//进程数量
voidprint（）//输出函数
{
PCB*p;
printf（"
NAMECPUTIMESTARTTIMENEEDTIMESTATUS\n"
）;
if（run!
=NULL）
printf（"
%-10s%-10d%-10s%-10d%c\n"
run->
name,
cputime,
starttime,
needtime,
state）;
/*输出执行的进程的信息*/
p=ready;
while（p!
{
p->
/*输出就绪进程的信息*/
p=p->
next;
}
p=finish;
/*输出结束队列的信息*/
p=p->
getchar（）;
/*使用getchar（）函数可以让输出时停留画面，
等待人按回车继续*/
}
voidinsert（PCB*q）/*插入新进程，把进程按进程到来时间大小排序*/
{
PCB*p1,*s,*r;
intb;
s=q;
/*指针s指向新要插入的进程*/
p1=ready;
/*指针p1指向原来的进程队列的队首*/
r=p1;
/*使用指针r是指向p1前面的进程*/
b=1;
while（（p1!
=NULL）&
&
b）
if（strcmp（p1->
starttime,s->
starttime）<
0）
{
r=p1;
p1=p1->
}/*新进程的开始时间大，则p1指向下一个进程继续比*/
else
b=0;
if（r!
=p1）
r->
next=s;
s->
next=p1;
}/*新进程找到位置，插在r和p1之间*/
else
s->
ready=s;
}/*新进程的开始时间按最小，插在队首，并修改就绪队首ready指针*/
}
voidcreate（）
inti;
ready=NULL;
run=NULL;
finish=NULL;
PleaseenterthenameandtimeandstarttimeofPCB:
\n"
/*输入进程名、运行时间和开始时间*/
for（i=0;
i<
N;
i++）
{
p=（PCB*）malloc（sizeof（PCB））;
/*为新进程开辟空间*/
scanf（"
%s"
p->
name）;
/*输入进程名*/
%d"
&
p->
needtime）;
/*输入进程要求运行时间*/
starttime）;
//输入进程开始时间
p->
cputime=0;
state='
W'
;
/*表示就绪队列中未在队首先执行，但也是就绪状态*/
if（ready!
=NULL）
insert（p）;
/*就绪队首不为NULL，插入新进程*/
{/*否则先插在NULL前*/
next=ready;
ready=p;
}
}
Displayisgoingtostart:
\n"
***********************************************\n"
print（）;
run=ready;
/*队列排好，run指向就绪队列队首*/
ready=ready->
/*ready指向下一个进程*/
run->
R'
/*队首进程的状态为就绪*/
}
voidFCFS（）
while（run!
cputime=run->
cputime+run->
needtime;
needtime=0;
next=finish;
finish=run;
E'
run=NULL;
if（ready!
run=ready;
run->
ready=ready->
}
print（）;
voidmain（）
PleaseenterthetotalnumberofPCB:
scanf（"
N）;
create（）;
/*模拟创建进程，并输入相关信息*/
FCFS（）;
/*先来先服务调度算法*/
2.1.4．测试结果及说明
首先输入进程个数（为5个），这里命名为A,B,C,D,E，然后分别输入运行时间和开始时间
所有进程都在队列中，并都处于等待状态
其中一个进程执行完毕
所有进程都执行完毕
2.2．优先级调度
2.2.1．算法思想
进程的执行顺序由高优先级到低优先级，系统或用户按某种原则为进程指定一个优先级来表示该进程所享有的确调度优先权。
2.2.2．算法流程图
图2.优先级调度流程图
2.2.3．程序代码
{charname[10];
intprio;
/*优先数*/
intcputime;
intneedtime;
charstate;
structnode*next;
PCB*ready,*run,*finish;
/*就绪执行结束指针*/
voidprt（）/*输出函数，可以方便看到进程执行的演示*/
PCB*p;
printf（"
NAMECPUTIMENEEDTIMEPRIORITYSTATUS\n"
if（run!
=NULL）
printf（"
%-10s%-10d%-10d%-10d%c\n"
run->
name,run->
cputime,run->
needtime,run->
prio,run->
/*输出执行的进程的信息*/
p=ready;
while（p!
=NULL）
{printf（"
name,p->
cputime,p->
needtime,p->
prio,p->
}
p=finish;
=NULL）
{printf（"
}
getchar（）;
}/*使用getchar（）函数可以让输出时停留画面，等待人按回车继续*/
voidinsert（PCB*q）/*插入新进程，把进程按优先数大小排序*/
{PCB*p1,*s,*r;
intb;
s=q;
p1=ready;
r=p1;
b=1;
while（（p1!
if（p1->
prio>
=s->
prio）{r=p1;
}/*新进程的优先数小，则p1指向下一个进程继续比*/
elseb=0;
if（r!
=p1）{r->
}/*新进程找到位置，插在r和p1之间*/
else{s->
}}/*新进程的优先数最大，插在队首，并
修改就绪队首ready指针*/
{PCB*p;
inti;
ready=NULL;
run=NULL;
finish=NULL;
PleaseenterthenameandtimeandpriorityofPCB:
/*输入进程名、运行时间和优先级*/
for（i=0;
{p=（PCB*）malloc（sizeof（PCB））;
scanf（"
prio）;
/*输入进程优先数*/
p->
if（ready!
=NULL）insert（p）;
else{p->
ready=p;
}}/*否则先插在NULL前*/
printf（"
prt（）;
run=ready;
ready=ready->
/*ready指向下一个进程，这样当进程执行时如果优先数小于其他的进程，应该先进行优先数最大的进程*/
run->
}/*队首进程的状态为就绪*/
voidprio（）
{while（run!
{run->
cputime+1;
/*运行一次cpu占用时间加一*/
run->
needtime=run->
needtime-1;
/*运行一次要求运行时间减一*/
prio=run->
prio-1;
/*运行一次优先数减一*/
if（run->
needtime==0）/*若要求运行时间为0时*/
{run->
/*退出队列*/
finish=run;
/*finish为结束进程的队列*/
run->
/*修改状态为结束*/
run=NULL;
/*释放run指针*/
if（ready!
=NULL）/*创建新就绪队列的头指针*/
{run=ready;
run->
ready=ready->
}}
else
if（（ready!
（run->
prio<
ready->
prio））
/*队首进程的优先数比它下一个小，且下一个进程不为NULL时执行*/
{run->
run->
next=NULL;
/*队首进程退出进程队列*/
insert（run）;
/*在进程队列中重新插入原来的队首进程*/
run=ready;
/*重新置就绪队列的头指针*/
ready=ready->
prt（）;
{printf（"
scanf（"
create（）;
prio（）;
}/*优先数调度算法*/
2.2.4．测试结果及说明
优先级调度算法运行情况如图1，图2，图3，图4所示
图1.输入进程块的数量
图2.输入每个进程的名称、时间、优先级
图3.输入所有的进程的相关信息
图4.所有进程调度算法完成
2.3．时间片轮转调度
2.3.1．算法思想
所有就绪进程按先来先服务的原则排成一个队列，将新来的进程加到就绪对列的末尾，每当执行进程调度时，总是把处理机分配给队首的进程，各进程占用CPU的时间片相同。
也就是说CPU的处理时间划分成一个个相同的时间片，就绪队列的所有进程轮流运行一个时间片。
当一个时间片结束时，如果运行进程用完它的时间片后还未完成，就强迫运行进程让出CPU，就把它送回到就绪队列的末尾，等待下一次调度。
同时，进程调度又去选择就绪队列中的队首进程，分配给它一时间片，以投入运行。
直至所有的进程运行完毕。
2.3.2．算法流程图
2.3.3．程序代码
intcount;
/*计数器，判断是否=时间片的大小*/
PCB*ready,*run,*finish,*tail;
/*就绪执行结束尾指针*/
intN,round;
NAMECPUTIMENEEDTIMESTATUS\n"
if（run!
%-10s%-10d%-10d%c\n"
p=ready;
while（p!
{
p=p->
p=finish;
升级会员 