模拟进程调度算法课程设计.docx
《模拟进程调度算法课程设计.docx》由会员分享，可在线阅读，更多相关《模拟进程调度算法课程设计.docx（31页珍藏版）》请在冰点文库上搜索。
模拟进程调度算法课程设计
•课程概述
1・1•设计构想
程序能够完成以下操作：
创建进程：
先输入进程的数目，再一次输入每个进程的进程名、运行总时间和优先级，先到达的先输入；进程调度：
进程创建完成后就选择进程调度算法，并单步执行，每次执行的结果都从屏幕上输出来。
1-2.需求分析
在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目，要使这多个进程能够并发地执行，这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。
分配处理机的任务是由处理机调度程序完成的。
由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统必（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。
本次实验在VC++6.0环境下实现先来先服务调度算法，短作业优先调度算法，高优先权调度算法，时间片轮转调度算法和多级反馈队列调度算法。
1.3.理论依据
为了描述和管制进程的运行，系统为每个进程定义了一个数据结构一一进程控制块PCB（ProcessControlBlock）,PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息，系统总是通过PCB对进程进行控制，亦即，系统是根据进程的PCB而不是任何别的什么而感知进程的存在的，PCB是进程存在的惟一标志。
本次课程设计用结构体Process代替PCB的功能。
1.4.课程任务
一、用C语言（或C++）编程实现操作模拟操作系统进程调度子系统的基本功能；运用多种算法实
现对进程的模拟调度。
二、通过编写程序实现进程或作业先来先服务、高优先权、按时间片轮转、短作业优先、多级反馈
队列调度算法，使学生进一步掌握进程调度的概念和算法，加深对处理机分配的理解。
三、实现用户界面的开发
1・5・功能模块分析:
1、进程概念：
进程是被独立分配资源的最小单位。
进程是动态概念，必须程序运行才有进程的产生。
2、进程的状态模型：
（1）运行：
进程已获得处理机，当前处于运行状态。
（2）就绪：
进程已经准备好，一旦有处理器就可运行。
3、处理机调度：
在多道程序设计系统中，内存中有多道程序运行，他们相互争夺处理机这一重要的资源。
处理机调度就是从就绪队列中，按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程并发地执行。
4、进程调度算法的功能：
记录系统中所有进程的执行情况
选择占有处理机的进程
进行进程的上下文切换
5、进程调度的算法：
（1）先来先服务算法：
如果早就绪的进程排在就绪队列的前面，迟就绪的进程排在就绪队列的后面，那么先来先服务总是把当前处于就绪队列之首的那个进程调度到运行状态。
（2）优先数算法：
即进程的执行顺序由高优先级到低优先级。
系统或用户按某种原则为进程指定一个优先级来表示该进程所享有的确调度优先权。
该算法核心是确定进程的优先级。
（3）时间片轮转算法：
固定时间片，每个进程在执行一个时间片后，轮到下一进程执行，知道所有的进程执行完毕。
处理器同一个时间只能处理一个任务。
处理器在处理多任务的时候，就要看请求的时间顺序，如果时间一致，就要进行预测。
挑到一个任务后，需要若干步骤才能做完，这些步骤中有些需要处理器参与，有些不需要（如磁盘控制器的存储过程）。
不需要处理器处理的时候，这部分时间就要分配给其他的进程。
原来的进程就要处于等待的时间段上。
经过周密分配时间，宏观上就象是多个任务一起运行一样，但微观上是有先后的，就是时间片轮换。
（4）多级反馈队列法：
又称反馈循环队列或多队列策略，主要思想是将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列，较高优先级的队列一般分配给较短的时间片。
处理器调度先从高级就绪进程队列中选取可占有处理器的进程，只有在选不到时，才从较低级的就绪进程队列中选取。
（5）短作业优先法：
对短进程优先调度的算法，它是从后备队列中选择一个或者若干个进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。
・设计方案
2.1•先来先服务调度
2.1.1・算法思想
先来先服务调度算法的思想是按照进程进入就绪队列的先后顺序调度并分配处理机执行。
先来先服务调度算法是一种不可抢占的算法，先进入就绪队列的进程，先被处理机运行。
一旦一个进程占有了处理机，它就一直运行下去，直到该进程完成工作或者因为等待某事件而不能继续运行时才释放处理机。
2.1.2・算法流程图
开始
V
图1•先来先服务算法流程图
21.3・程序代码
#include#include#includetypedefstructnode
（
charname[10];/*进程名*/intcputime;广占用cpu时间*/
charstarttime[5];〃进程开始时间intneedtime;广要求运行时间*/
charstate;/*状态*/
structnode*next;/*指针*/
}PCB;
PCB*ready,*run,*finish;//就绪、执行、结束指针intN;〃进程数量voidprint（）//输出函数
（
PCB*p;
printf（HNAMECPUTIMESTARTTIMENEEDTIMEif（run!
=NULL）STATUS'^）;
printf（"%-10s%-10d%-10s%-1Od%c\n",run->name,
run->cputime,run->starttime,run->needtime,run->state）;/*输出执行的进程的信息"7p=ready;
while（p!
=NULL）<
printf（"%-10s%-10d%-10s%-1Od%c\n”，p・>name,p->cputime,p->starttime,p->needtime,p->state）;/*输出就绪进程的信息*/p=p->next;
）p=finish;while（p!
=NULL）
printf（"%-10s%-10d%-10s%-1Od%c\n”，p->name,p->cputime,
getchar（）;/*使用getchar（）函数可以让输出时停留画面，等待人按回车继续*/
}
voidinsert（PCB*q）广插入新进程，把进程按进程到来时间大小排序
（
PCB*p1
intb;
s=q；/*指针s指向新要插入的进程*/
p1=ready;/*指针p1指向原来的进程队列的队首*/r=p1;/*使用指*/针r是指向P1前面的进程*/b=1;
while（（p1!
=NULL）&&b）if（strcmp（p1->starttime,s->starttime）r=p1;p1=p>next;
}广新进程的开始时间大，则P1指向下一个进程继续比else
b=0;
if（r!
=p1）
{
r・>next=s;s・>next=p1;
}/*新进程找到位置，插在r和P1之间*/else
ext=p1;ready=s;
}/*新进程的开始时间按最小，插在队首，并修改就绪队首}
7
voidcreate（）
（
PCB*p;inti;ready=NULL;run=NULL;
finish=NULL;printf（"PleaseenterthenameandtimeandstarttimeofPCB:
\nn）;
广输入进程名、运行时间和开始时间7for（i=0;iP=（PCB*）malloc（sizeof（PCB））;/*为新进程幵辟空间*/
ready指针7
create（）;广模拟创建进程，并输入相尖信息*/FCFS（）;/*先来先服务调度算法*/
21.4•测试结果及说明
首先输入进程个数（为5个），这里命名为A,B,C,D,E，然后分别输入运行时间和开始时间
所有进程都在队列中，并都处于等待状态
其中一个进程执行完毕
所有进程都执行完毕
2.2・优先级调度
2.2.1・算法思想
进程的执行顺序由高优先级到低优先级，系统或用户按某种原则为进程指定
一个优先级来表示该进程所享有的确调度优先权该算法核心是确定进程的优先级。
2.2.2・算法流程图
图2.优先级调度流程图
2.2.3・程序代码
进程名V
优先数V
占用epu时间7
要求运行时间*/
状态*/
#include#include#ineludetypedefstructnode{charname[10];/*intprio;/*inteputime;/*intneedtime;/*charstate;/*structnode*next;
/*}PCB;
intN;voidprt（）/*（
PCB*ready,*run,*finish;指针*7
PCB*p;
输出函数，可以方便看到进程执行的演不*/
/*就绪执行结束指针*/
printf（”NAMECPUTIMENEEDTIMEPRIORITY
STATUS'rT）
if（run!
=NULL）
printf（"%-1Os%-10d%-10d%-1Od%c\n',,run->name,run->cputime,run->needtime,run->prio,run->state）;
/*输出执行的进程的信息*/
p=ready;
while（pkNULL）
{printf（”%-10s%-1Od%-1Od%-1Od%c\n',Jp->name,p->cputime,p->needtime,p->prio,p->state）;/*输出就绪进程的信息*/
p=p->next;}
p=finish;
while（p!
=NULL）{printf（"%-10s%-10d%-1Od%・
10d%c\n,,,p->name,p->cputime,p->needtime,p->prio,p->state）;/*输出结束队列的
信息*/
p=p->next;}
getchar（）;}/*使用getchar（）函数可以让输出时停留画面，等待人按回车继续
7
voidinsert（PCB勺）广插入新进程，把进程按优先数大小排序V
{PCB*p1,*s,*r;
intb;
s=q；/*指针s指向新要插入的进程*/
p1=ready;/*指针p1指向原来的进程队列的队首V
r=p1；/*使用指针r是指向p1前面的进程*/b=1;
while（（p1!
=NULL）&&b）
if（pprio>=s->prio）{r=p1;p1=p1・>next;}
小，则P1指向下一个进程继续比*/else广新进程的优先数新进程找到位
b=0;
if（r!
=p1）{r->next=s;s->next=p1;}/*p1之间
v置，插在r和新进程的优先数最
else{s・>next=p1;ready=s;}}广首，并
修
改就绪队首ready指针7
voidcreate（）
{PCB*p;
inti;
ready=NULL;run=NULL;finish=NULL;printf（"PleaseenterthenameandtimeandpriorityofPCB:
\n”）；
广输入进程名、运行时间和优先级*/for（i=0;i{p=（PCB*）malloc（sizeof（PCB））;/*为新进程开辟空间*/scanf（H%sH,p->name）;
/*输入进程名*/
scanf（,'%dH,&p->needtime）;/*输入进程要求运行时间*/scant（M%dn,&p->prio）;/*输入进程优先数*/p->cputime=O;
p.>state=W;/*表示就绪队列中未在队首先执行，但也是就绪状态*/
if（ready!
=NULL）insert（p）;/*就绪队首不为NULL、插入新进程
7
else{p・>next=ready;ready=p;}}/*printf（"
好，run指向就绪队列队首*/ready=ready->next;广ready指向下一个进程，这样当进程执行时如果优先数小于其他的进程，应该先进行优先数最大的进程
run->state=R1;}/*队首进程的状态为就绪*/voidprio（）{while（run!
=NULL）
{run->cputime=run->cputime+1;/*runoneedtime=run->needtime-1;
run->prio=run->prio;/*if（run->needtime==O）/*{run->hbxt=finish;finish=run;run->state='Ef;run=NULL;if（ready!
=NULL）
运行一次cpu占用时间加一*//*运行一次要求运行时间减一*/运行一次优先数减一*/若要求运行时间为0时*/
/*退出队列*/为结束进程的队列V
广finish修改状态为结束*/释放伽指针7
/*创建新就绪队列的头指针*/
{run=ready;run->state='R*;ready=ready->next;}}elseif（（ready!
=NULL）&&（run->prioprio））
广队首进程的优先数比它下一个小，且下一个进程不为NULL时执行7
{run->state=*W;队首进程退出进程队列V在进程队列中重新
run->next=NULL;/*插入原来的队首进程V重新置就绪队列的头
insert（run）;/*指乍十*/
run=ready;/*run->state='R*;
ready=ready->next;}prt（）;}}
voidmain（）
{printf（”PleaseenterthetotalnumberofPCB:
\nH）；scanf（”％d”,&N）;
create（）;/*模拟创建进程，并输入相尖信息*/prio（）；}/*优先数调度算法V
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-程序代码
#include
#include
#ineludetypedefstructnode
intcount;
charname[10];/*进程名*/
/*计数器，判断是否二时间片的大小*/inteputime;intneedt佝廊稠aff照占就龟询ctnode*next;/*要求运行时间*/广
状态*/
广指针*/
}PCB;
PCB*ready,*run,*finish,*tail;/*就绪执行结束尾指针*/intN,round;
voidprt（）/*输出函数，可以方便看到进程执行的演示{一
PCB*p;
printf（nNAMECPUTIMENEEDTIMEif（run!
=NULL）STATUS'"）;
printf（H%-10s%-10d%-1Od%c\n,,,run->name,run->cputime,run->needtime,run->state）;/*输出执行的进程的信息*7p=ready;
while（p!
=NULL）
printf（f,%-1Os%-1Od%-1Od%c\n,f,p->name,p->cputime,p->needtime,p->
state）;/*输出就绪进程的信息*/
p=p->next;
}
p=finish;
while（p!
=NULL）
printf（H%-10s%-1Od%-1Od%c\nH,p->name,p->cputime,p->needtime,p->
state）;/*输出结束队列的信息*/
p=p->next;
}
getchar（）;
voidinsert（PCB*q）/*在队尾插入新的进程7
PCB*p;
p=ready;
while（p->next!
=NULL）
{
p=ready->next;
}
tail=p;
tail->next=q;q->next=NULL;
1
voidcreate（）
（
PCB*p;
inti;
ready=NULL;run=NULL;finish=NULL;
printf（"PleaseenterthenameandtimeofPCB:
\n"）;/*输入进程名、和
*/
for（i=0;ivN;i++）
p=（PCB*）malloc（sizeof（PCB））;/*为新进程开辟空间7scanf（n%s",p->name）;/*输入进程名*/
scanf「％cT：
&p・>needtime）;/*输入进程要求运行时间*/p->cputime=O;p->state=*W;/*表示就绪队列中未在队首先执行，但也是就绪状态7
if（ready!
=NULL）insert（p）;/*就绪队首不为NULL，插入新进程7else
next=ready;ready=p;tail=p;
）
}
printf（”Displayisgoingtostart:
\n"）;
printf（fm）、
prt（）；
getchar（）;
run=ready;广队列排好，run指向就绪队列队首*/ready=ready->next;/*ready指向下一个进程7
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==O）广若要求运行时间为0时"7
/*退出队列*/
广finish为结束进程的队列7广修改状态为结束*/
/*释放run指针*/
run=ready;run->state=R';ready=ready->next;
“elseif（run->count==round）广如果时间片到*/
（
run->count=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）;
createQ;/*模拟创建进程，并输入相尖信息*/count（）;/*优先数调度算法7
}
2.3.4•测试结果及说明
时间片轮转调度算法运行情况如图1，图2，图3所示
图1所有的进程都在队列中
图2其中一个进程执行完毕
图4所有的进程都执行完毕
2.4・多级反馈队列调度
2.4.1算法思想
允许逬程在队列之间移动。
在系统中设置多个就绪队列,每个队列对应一个优先级,第一个队列的优先级最高，第二队列次之。
以下各队列的优先级逐步低。
各就绪队列中的进程的运行时间片不同，高优先级队列的时间片小，低优先级队列的时间片大。
进程并非总是固定在某一队列中，新进程进入系统后，被存放在第一个队列的末尾。
如果某个进程在规定的时间片内没有完成工作，则把它转入到下一个队列的末尾，直至进入最后一个队列。
系统先运行第一个队列中的进程。
当第一队列为空时，才运行第二个队列中的进程。
依此类推，仅当前面所有的队列都为空时，才运行最后一个队列中的进程。
当处理器正在第i个队列中为某个进程服务时，又有新进程进入优先级最高的队列（第1—（i-1）中的任何一个对列），则此新进程要抢占正在运行进程的处理器，即由调度程序把正在运行的进程放回第i队列的末尾，把处理器分配给新到的高优先级进程。
除最低优先权队列外的所有其他队列，均采用相同的进程调度算法，即按时间片轮转的FIFO（先进先出）算法。
最后一个队列中的进程按按时间片轮转或FCFS策略进行调度。
它是综合了FIFO、RR和剥夺式HPF的一种进程调度算法。
2.4.2算法流程图
2.4.3程序代码
#include#include#include#defineNULL0typedefstructnode
{
charname[10];/*进程名*/
intnum;/*进程所在队列数，也是该队列的时间片*/
intcputime;
intneedtime;
广占用cpu时间*/
/*要求运行时间*/
structnode*next;/*指针*/
}PCB;
PCB*qf1,*ql1;
PCB*qf2,*ql2;
PCB*qf3,*ql3;//定义三个队列的头指针和尾指针
voidinsert（PCB*q,PCB*qf,PCB*ql）num++;if（qf==NULL&&ql==NULL）{//队列为空
intblog1,blog2,blog
升级会员 