进程模拟调度算法课程设计Word格式.docx
- 文档编号:7810990
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:16
- 大小:27.31KB
进程模拟调度算法课程设计Word格式.docx
《进程模拟调度算法课程设计Word格式.docx》由会员分享,可在线阅读,更多相关《进程模拟调度算法课程设计Word格式.docx(16页珍藏版)》请在冰点文库上搜索。
记录系统中所有进程的执行情况
选择占有处理机的进程
进行进程的上下文切换
5、进程调度的算法:
(1)先来先服务算法:
如果早就绪的进程排在就绪队列的前面,迟就绪的进程排在
就绪队列的后面,那么先来先服务总是把当前处于就绪队列之首的那个进程调
度到运行状态。
(2)优先数算法:
即进程的执行顺序由高优先级到低优先级。
系统或用户按某种原则为进程指定一个优先级来表示该进程所享有的确调度优先权。
该算法核心是确定进程的优先级。
(3)时间片轮转算法:
固定时间片,每个进程在执行一个时间片后,轮到下一进程执行,知道所有的进程执行完毕。
处理器同一个时间只能处理一个任务。
处理器在处理多任务的时候,就要看请求的时间顺序,如果时间一致,就要进行预测。
挑到一个任务后,需要若干步骤才能做完,这些步骤中有些需要处理器参与,有些不需要(如磁盘控制器的存储过程)。
不需要处理器处理的时候,这部分时间就要分配给其他的进程。
原来的进程就要处于等待的时间段上。
经过周密分配时间,宏观上就象是多个任务一起运行一样,但微观上是有先后的,就是时间片轮换。
(4)多级反馈队列法:
又称反馈循环队列或多队列策略,主要思想是将就绪进程分为两级或多级,系统相应建立两个或多个就绪进程队列,较高优先级的队列一般分配给较短的时间片。
处理器调度先从高级就绪进程队列中选取可占有处理器的进程,只有在选不到时,才从较低级的就绪进程队列中选取。
(5)短作业优先法:
对短进程优先调度的算法,它是从后备队列中选择一个或者若干个进程,将处理机分配给它,使它立即执行并一直执行到完成,或发生某事件而被阻塞放弃处理机时再重新调度。
二.设计方案
.先来先服务调度
2.1.1.算法思想
先来先服务调度算法的思想是按照进程进入就绪队列的先后顺序调度并分配处理机执行。
先来先服务调度算法是一种不可抢占的算法,先进入就绪队列的进程,先被处理机运行。
一旦一个进程占有了处理机,它就一直运行下去,直到该进程完成工作或者因为等待某事件而不能继续运行时才释放处理机。
2.1.2.算法流程图
图1.先来先服务算法流程图
2.1.3.程序代码
#include<
>
typedefstructnode
{
charname[10];
/*进程名*/
intcputime;
/*占用cpu时间*/
charstarttime[5];
2.1.42.2.12.2.2先级调度流程图
2.2.3.程序代码
{charname[10];
intprio;
/*优先数*/
intneedtime;
/*要求运行时间*/
charstate;
/*状态*/
structnode*next;
/*指针*/
}PCB;
PCB*ready,*run,*finish;
/*就绪执行结束指针*/
intN;
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->
state);
/*输出执行的进程的信息*/
p=ready;
while(p!
{printf("
p->
name,p->
cputime,p->
needtime,p->
prio,p->
/*输出就绪进程的信息*/
p=p->
next;
}
p=finish;
=NULL)
{printf("
/*输出结束队列的信息*/
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(p1->
prio>
=s->
prio){r=p1;
p1=p1->
}/*新进程的优先数小,则p1指向下一个进程继续比*/
elseb=0;
if(r!
=p1){r->
next=s;
s->
next=p1;
}/*新进程找到位置,插在r和p1之间*/
else{s->
ready=s;
}}/*新进程的优先数最大,插在队首,并
修改就绪队首ready指针*/
voidcreate()
{PCB*p;
inti;
ready=NULL;
run=NULL;
finish=NULL;
PleaseenterthenameandtimeandpriorityofPCB:
\n"
/*输入进程名、运行时间和优先级*/
for(i=0;
i<
N;
i++)
{p=(PCB*)malloc(sizeof(PCB));
/*为新进程开辟空间*/
scanf("
%s"
name);
/*输入进程名*/
%d"
&
p->
needtime);
/*输入进程要求运行时间*/
prio);
/*输入进程优先数*/
p->
cputime=0;
state='
W'
;
/*表示就绪队列中未在队首先执行,但也是就绪状态*/
if(ready!
=NULL)insert(p);
/*就绪队首不为NULL,插入新进程*/
else{p->
next=ready;
ready=p;
}}/*否则先插在NULL前*/
Displayisgoingtostart:
\n"
***********************************************\n"
prt();
run=ready;
/*队列排好,run指向就绪队列队首*/
ready=ready->
/*ready指向下一个进程,这样当进程执行时如果优先数小于其他的进程,应该先进行优先数最大的进程*/
run->
R'
}/*队首进程的状态为就绪*/
voidprio()
{while(run!
{run->
cputime=run->
cputime+1;
/*运行一次cpu占用时间加一*/
needtime=run->
needtime-1;
/*运行一次要求运行时间减一*/
prio=run->
prio-1;
/*运行一次优先数减一*/
if(run->
needtime==0)/*若要求运行时间为0时*/
next=finish;
/*退出队列*/
finish=run;
/*finish为结束进程的队列*/
E'
/*修改状态为结束*/
/*释放run指针*/
=NULL)/*创建新就绪队列的头指针*/
{run=ready;
}}
else
if((ready!
(run->
prio<
ready->
prio))
/*队首进程的优先数比它下一个小,且下一个进程不为NULL时执行*/
next=NULL;
/*队首进程退出进程队列*/
insert(run);
/*在进程队列中重新插入原来的队首进程*/
/*重新置就绪队列的头指针*/
voidmain()
{printf("
PleaseenterthetotalnumberofPCB:
N);
create();
/*模拟创建进程,并输入相关信息*/
prio();
}/*优先数调度算法*/
2.2.4.测试结果及说明
优先级调度算法运行情况如图1,图2,图3,图4所示
图1.输入进程块的数量
图2.输入每个进程的名称、时间、优先级
图3.输入所有的进程的相关信息
图4.所有进程调度算法完成
.时间片轮转调度
2.3.1.算法思想
所有就绪进程按先来先服务的原则排成一个队列,将新来的进程加到就绪对列的末尾,每当执行进程调度时,总是把处理机分配给队首的进程,各进程占用CPU的时间片相同。
也就是说CPU的处理时间划分成一个个相同的时间片,就绪队列的所有进程轮流运行一个时间片。
当一个时间片结束时,如果运行进程用完它的时间片后还未完成,就强迫运行进程让出CPU,就把它送回到就绪队列的末尾,等待下一次调度。
同时,进程调度又去选择就绪队列中的队首进程,分配给它一时间片,以投入运行。
直至所有的进程运行完毕。
2.3.2.算法流程图
2.3.3.程序代码
intcount;
/*计数器,判断是否=时间片的大小*/
PCB*ready,*run,*finish,*tail;
/*就绪执行结束尾指针*/
intN,round;
NAMECPUTIMENEEDTIMESTATUS\n"
printf("
%-10s%-10d%-10d%c\n"
/*输出执行的进程的信息*/
{
}
voidinsert(PCB*q)/*在队尾插入新的进程*/
while(p->
next!
{
p=ready->
tail=p;
tail->
next=q;
q->
ready=NULL;
PleaseenterthenameandtimeofPCB:
/*输入进程名、和*/
for(i=0;
p=(PCB*)malloc(sizeof(PCB));
else
{
p->
}
}
/*ready指向下一个进程*/
}/*队首进程的状态为就绪*/
voidcount()
while(run!
run->
count=run->
count+1;
/*运行一次计数器加一*/
if(run->
{
run->
finish=run;
run=NULL;
if(ready!
{
run=ready;
}
}
else
if(run->
count==round)/*如果时间片到*/
{
run->
count=0;
/*计数器置0*/
if(ready!
=NULL)/*如就绪队列不空*/
{
run->
insert(run);
/*在进程队列中重新插入原来进程,插入队尾*/
run=ready;
ready=ready->
}
}
prt();
count();
/*优先数调度算法*/
2.3.4.测试结果及说明
时间片轮转调度算法运行情况如图1,图2,图3所示
图1所有的进程都在队列中
图2其中一个进程执行完毕
图4所有的进程都执行完毕
.多级反馈队列调度
2.4.1算法思想
允许进程在队列之间移动。
在系统中设置多个就绪队列,每个队列对应一个优先级,第一个队列的优先级最高,第二队列次之。
以下各队列的优先级逐步低。
各就绪队列中的进程的运行时间片不同,高优先级队列的时间片小,低优先级队列的时间片大。
进程并非总是固定在某一队列中,新进程进入系统后,被存放在第一个队列的末尾。
如果某个进程在规定的时间片内没有完成工作,则把它转入到下一个队列的末尾,直至进入最后一个队列。
系统先运行第一个队列中的进程。
当第一队列为空时,才运行第二个队列中的进程。
依此类推,仅当前面所有的队列都为空时,才运行最后一个队列中的进程。
当处理器正在第i个队列中为某个进程服务时,又有新进程进入优先级最高的队列(第1—(i-1)中的任何一个对列),则此新进程要抢占正在运行进程的处理器,即由调度程序把正在运行的进程放回第i队列的末尾,把处理器分配给新到的高优先级进程。
除最低优先权队列外的所有其他队列,均采用相同的进程调度算法,即按时间片轮转的FIFO(先进先出)算法。
最后一个队列中的进程按按时间片轮转或FCFS策略进行调度。
它是综合了FIFO、RR和剥夺式HPF的一种进程调度算法。
2.4.2算法流程图
2.4.3程序代码
#include<
#defineNULL0
intnum;
/*进程所在队列数,也是该队列的时间片*/
PCB*qf1,*ql1;
PCB*qf2,*ql2;
PCB*qf3,*ql3;
2.4.42.5.12.5.22.5.32.5.4作业优先调度算法运行情况如4-7到4-9所示
。
图4-7所有作业都在队列中,并都处于等待状态
图4-8其中一个作业执行完毕
图4-9所有进程执行完毕
三.测试分析
1.先来先服务算法比较有利于长作业(进程),而不利于短作业(进程)。
因为短作业运行时间很短,如果让它等待较长时间才得到服务,那么,它的带权周转时间就会很高;
先来先服务调度算法有利于CPU繁忙型的作业,不利于I/O繁忙型的作业,而目前大多数事务处理都属于I/O繁忙型作业。
2.短作业优先调度算法能有效地降低作业的平均等待时间,提高系统吞吐量。
然而该算法对长作业不利,因为调度程序总是优先调度那些短作业,将导致长作业长期不被调度,该算法完全未考虑作业的紧迫程度,因而不能保证紧迫性作业会被及时处理,由于作业的长短只是根据用户提供的估计执行时间而定的,而用户又可能有意无意地缩短其作业的估计运行时间,致使该算法不能真正做到短作业优先调度;
3.优先级调度算法则保证了紧迫进程,而那些优先级较低的则可能长时间得不到调度;
静态优先级调度算法简单易行,系统开销小,但是不太灵活,很可能出现低优先级的作业,长期得不到调度而等待的情况;
静态优先级法仅适合于实现要求不太高的系统。
动态优先级调度算法比较灵活科学,可防止有一些进程一直得不到调度,也可防止有些进程长期垄断处理机,但是需要花费相当多的执行程序时间,因而花费的系统开销比较大。
4.时间片轮转算法则算是对每个进程都是公平的,减少了进程的等待时间,但是时间片设得太短会导致过多的进程切换,降低了CPU效率;
而设得太长又可能引起对短的交互请求的响应变差。
将时间片设为100毫秒通常是一个比较合理的折衷;
5.多级反馈队列调度算法则是综合先来先服务,短作业优先,时间片轮转和优先级调度算法的优点,故多级反馈队列调度对大多数进程调度来说是一种最佳的调度算法,但具体算法则应根据实际需求选择。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 进程 模拟 调度 算法 课程设计