进程模拟调度算法课程设计.docx
《进程模拟调度算法课程设计.docx》由会员分享，可在线阅读，更多相关《进程模拟调度算法课程设计.docx（16页珍藏版）》请在冰点文库上搜索。
进程模拟调度算法课程设计
一．课程概述
.设计构想
程序能够完成以下操作：
创建进程：
先输入进程的数目，再一次输入每个进程的进程名、运行总时间和优先级，先到达的先输入；进程调度：
进程创建完成后就选择进程调度算法，并单步执行，每次执行的结果都从屏幕上输出来。
.需求分析
在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目，要使这多个进程能够并发地执行，这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。
分配处理机的任务是由处理机调度程序完成的。
由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统必（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。
本次实验在VC++环境下实现先来先服务调度算法，短作业优先调度算法，高优先权调度算法，时间片轮转调度算法和多级反馈队列调度算法。
.理论依据
为了描述和管制进程的运行，系统为每个进程定义了一个数据结构——进程控制块PCB（ProcessControlBlock）,PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息，系统总是通过PCB对进程进行控制，亦即，系统是根据进程的PCB而不是任何别的什么而感知进程的存在的，PCB是进程存在的惟一标志。
本次课程设计用结构体Process代替PCB的功能。
.课程任务
一、用C语言（或C++）编程实现操作模拟操作系统进程调度子系统的基本功能；运用多种算法实现对进程的模拟调度。
二、通过编写程序实现进程或作业先来先服务、高优先权、按时间片轮转、短作业优先、多级反馈队列调度算法，使学生进一步掌握进程调度的概念和算法，加深对处理机分配的理解。
三、实现用户界面的开发
.功能模块分析：
1、进程概念：
进程是被独立分配资源的最小单位。
进程是动态概念，必须程序运行才有
进程的产生。
2、进程的状态模型：
（1）运行：
进程已获得处理机，当前处于运行状态。
（2）就绪：
进程已经准备好，一旦有处理器就可运行。
3、处理机调度：
在多道程序设计系统中，内存中有多道程序运行，他们相互争夺处理机
这一重要的资源。
处理机调度就是从就绪队列中，按照一定的算法选择一个进程并将
处理机分配给它运行，以实现进程并发地执行。
4、进程调度算法的功能：
记录系统中所有进程的执行情况
选择占有处理机的进程
进行进程的上下文切换
5、进程调度的算法：
（1）先来先服务算法：
如果早就绪的进程排在就绪队列的前面，迟就绪的进程排在
就绪队列的后面，那么先来先服务总是把当前处于就绪队列之首的那个进程调
度到运行状态。
（2）优先数算法：
即进程的执行顺序由高优先级到低优先级。
系统或用户按某种原则为进程指定一个优先级来表示该进程所享有的确调度优先权。
该算法核心是确定进程的优先级。
（3）时间片轮转算法：
固定时间片，每个进程在执行一个时间片后，轮到下一进程执行，知道所有的进程执行完毕。
处理器同一个时间只能处理一个任务。
处理器在处理多任务的时候，就要看请求的时间顺序，如果时间一致，就要进行预测。
挑到一个任务后，需要若干步骤才能做完，这些步骤中有些需要处理器参与，有些不需要（如磁盘控制器的存储过程）。
不需要处理器处理的时候，这部分时间就要分配给其他的进程。
原来的进程就要处于等待的时间段上。
经过周密分配时间，宏观上就象是多个任务一起运行一样，但微观上是有先后的，就是时间片轮换。
（4）多级反馈队列法：
又称反馈循环队列或多队列策略，主要思想是将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列，较高优先级的队列一般分配给较短的时间片。
处理器调度先从高级就绪进程队列中选取可占有处理器的进程，只有在选不到时，才从较低级的就绪进程队列中选取。
（5）短作业优先法：
对短进程优先调度的算法，它是从后备队列中选择一个或者若干个进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。
二．设计方案
．先来先服务调度
2.1.1．算法思想
先来先服务调度算法的思想是按照进程进入就绪队列的先后顺序调度并分配处理机执行。
先来先服务调度算法是一种不可抢占的算法，先进入就绪队列的进程，先被处理机运行。
一旦一个进程占有了处理机，它就一直运行下去，直到该进程完成工作或者因为等待某事件而不能继续运行时才释放处理机。
2.1.2．算法流程图
图1.先来先服务算法流程图
2.1.3．程序代码
#include<>
#include<>
#include<>
typedefstructnode
{
charname[10];/*进程名*/
intcputime;/*占用cpu时间*/
charstarttime[5];2.1.42.2.12.2.2先级调度流程图
2.2.3．程序代码
#include<>
#include<>
#include<>
typedefstructnode
{charname[10];/*进程名*/
intprio;/*优先数*/
intcputime;/*占用cpu时间*/
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!
=NULL）
{printf（"%-10s%-10d%-10d%-10d%c\n",p->name,p->cputime,p->needtime,p->prio,p->state）;/*输出就绪进程的信息*/
p=p->next;}
p=finish;
while（p!
=NULL）
{printf（"%-10s%-10d%-10d%-10d%c\n",p->name,p->cputime,p->needtime,p->prio,p->state）;/*输出结束队列的信息*/
p=p->next;}
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->next;}/*新进程的优先数小，则p1指向下一个进程继续比*/
elseb=0;
if（r!
=p1）{r->next=s;s->next=p1;}/*新进程找到位置，插在r和p1之间*/
else{s->next=p1;ready=s;}}/*新进程的优先数最大，插在队首，并
修改就绪队首ready指针*/
voidcreate（）
{PCB*p;
inti;
ready=NULL;run=NULL;finish=NULL;
printf（"PleaseenterthenameandtimeandpriorityofPCB:
\n"）;
/*输入进程名、运行时间和优先级*/
for（i=0;i{p=（PCB*）malloc（sizeof（PCB））;/*为新进程开辟空间*/
scanf（"%s",p->name）;/*输入进程名*/
scanf（"%d",&p->needtime）;/*输入进程要求运行时间*/
scanf（"%d",&p->prio）;/*输入进程优先数*/
p->cputime=0;
p->state='W';/*表示就绪队列中未在队首先执行，但也是就绪状态*/
if（ready!
=NULL）insert（p）;/*就绪队首不为NULL，插入新进程*/
else{p->next=ready;ready=p;}}/*否则先插在NULL前*/
printf（"Displayisgoingtostart:
\n"）;
printf（"***********************************************\n"）;
prt（）;
run=ready;/*队列排好，run指向就绪队列队首*/
ready=ready->next;/*ready指向下一个进程，这样当进程执行时如果优先数小于其他的进程，应该先进行优先数最大的进程*/
run->state='R';}/*队首进程的状态为就绪*/
voidprio（）
{while（run!
=NULL）
{run->cputime=run->cputime+1;/*运行一次cpu占用时间加一*/
run->needtime=run->needtime-1;/*运行一次要求运行时间减一*/
run->prio=run->prio-1;/*运行一次优先数减一*/
if（run->needtime==0）/*若要求运行时间为0时*/
{run->next=finish;/*退出队列*/
finish=run;/*finish为结束进程的队列*/
run->state='E';/*修改状态为结束*/
run=NULL;/*释放run指针*/
if（ready!
=NULL）/*创建新就绪队列的头指针*/
{run=ready;run->state='R';ready=ready->next;}}
else
if（（ready!
=NULL）&&（run->prioprio））
/*队首进程的优先数比它下一个小，且下一个进程不为NULL时执行*/
{run->state='W';
run->next=NULL;/*队首进程退出进程队列*/
insert（run）;/*在进程队列中重新插入原来的队首进程*/
run=ready;/*重新置就绪队列的头指针*/
run->state='R';
ready=ready->next;}
prt（）;}}
voidmain（）
{printf（"PleaseenterthetotalnumberofPCB:
\n"）;
scanf（"%d",&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．程序代码
#include<>
#include<>
#include<>
typedefstructnode
{
charname[10];/*进程名*/
intcount;/*计数器，判断是否=时间片的大小*/
intcputime;/*占用cpu时间*/
intneedtime;/*要求运行时间*/
charstate;/*状态*/
structnode*next;/*指针*/
}PCB;
PCB*ready,*run,*finish,*tail;/*就绪执行结束尾指针*/
intN,round;
voidprt（）/*输出函数，可以方便看到进程执行的演示*/
{
PCB*p;
printf（"NAMECPUTIMENEEDTIMESTATUS\n"）;
if（run!
=NULL）
printf（"%-10s%-10d%-10d%c\n",run->name,run->cputime,run->needtime,run->state）;/*输出执行的进程的信息*/
p=ready;
while（p!
=NULL）
{
printf（"%-10s%-10d%-10d%c\n",p->name,p->cputime,p->needtime,p->state）;/*输出就绪进程的信息*/
p=p->next;
}
p=finish;
while（p!
=NULL）
{
printf（"%-10s%-10d%-10d%c\n",p->name,p->cputime,p->needtime,p->state）;/*输出结束队列的信息*/
p=p->next;
}
getchar（）;
}
voidinsert（PCB*q）/*在队尾插入新的进程*/
{
PCB*p;
p=ready;
while（p->next!
=NULL）
{
p=ready->next;
}
tail=p;
tail->next=q;
q->next=NULL;
}
voidcreate（）
{
PCB*p;
inti;
ready=NULL;run=NULL;finish=NULL;
printf（"PleaseenterthenameandtimeofPCB:
\n"）;/*输入进程名、和*/
for（i=0;i{
p=（PCB*）malloc（sizeof（PCB））;/*为新进程开辟空间*/
scanf（"%s",p->name）;/*输入进程名*/
scanf（"%d",&p->needtime）;/*输入进程要求运行时间*/
p->cputime=0;
p->state='W';/*表示就绪队列中未在队首先执行，但也是就绪状态*/
if（ready!
=NULL）insert（p）;/*就绪队首不为NULL，插入新进程*/
else
{
p->next=ready;ready=p;tail=p;
}
}
printf（"Displayisgoingtostart:
\n"）;
printf（"***********************************************\n"）;
prt（）;
getchar（）;
run=ready;/*队列排好，run指向就绪队列队首*/
ready=ready->next;/*ready指向下一个进程*/
run->state='R';
}/*队首进程的状态为就绪*/
voidcount（）
{
while（run!
=NULL）
{
run->cputime=run->cputime+1;/*运行一次cpu占用时间加一*/
run->needtime=run->needtime-1;/*运行一次要求运行时间减一*/
run->count=run->count+1;/*运行一次计数器加一*/
if（run->needtime==0）/*若要求运行时间为0时*/
{
run->next=finish;/*退出队列*/
finish=run;/*finish为结束进程的队列*/
run->state='E';/*修改状态为结束*/
run=NULL;/*释放run指针*/
if（ready!
=NULL）/*创建新就绪队列的头指针*/
{
run=ready;run->state='R';ready=ready->next;
}
}
else
if（run->count==round）/*如果时间片到*/
{
run->count=0;/*计数器置0*/
if（ready!
=NULL）/*如就绪队列不空*/
{
run->state='W';
insert（run）;/*在进程队列中重新插入原来进程,插入队尾*/
run=ready;/*重新置就绪队列的头指针*/
run->state='R';
ready=ready->next;
}
}
prt（）;
}
}
voidmain（）
{
printf（"PleaseenterthetotalnumberofPCB:
\n"）;
scanf（"%d",&N）;
create（）;/*模拟创建进程，并输入相关信息*/
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<>
#include<>
#include<>
#defineNULL0
typedefstructnode
{
charname[10];/*进程名*/
intnum;/*进程所在队列数,也是该队列的时间片*/
intcputime;/*占用cpu时间*/
intneedtime;/*要求运行时间*/
structnode*next;/*指针*/
}PCB;
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.多级反馈队列调度算法则是综合先来先服务，短作业优先，时间片轮转和优先级调度算法的优点，故多级反馈队列调度对大多数进程调度来说是一种最佳的调度算法，但具体算法则应根据实际需求选择。
升级会员 