进程模拟调度算法课程设计.docx
《进程模拟调度算法课程设计.docx》由会员分享，可在线阅读，更多相关《进程模拟调度算法课程设计.docx（38页珍藏版）》请在冰点文库上搜索。
进程模拟调度算法课程设计
一．课程概述
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．算法流程图
图1.先来先服务算法流程图
2.1.3．程序代码
#include
#include
#include
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,
run->cputime,
run->starttime,
run->needtime,
run->state）;/*输出执行的进程的信息*/
p=ready;
while（p!
=NULL）
{
printf（"%-10s%-10d%-10s%-10d%c\n",
p->name,
p->cputime,
p->starttime,
p->needtime,
p->state）;/*输出就绪进程的信息*/
p=p->next;
}
p=finish;
while（p!
=NULL）
{
printf（"%-10s%-10d%-10s%-10d%c\n",
p->name,
p->cputime,
p->starttime,
p->needtime,
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（strcmp（p1->starttime,s->starttime）<0）
{
r=p1;p1=p1->next;
}/*新进程的开始时间大，则p1指向下一个进程继续比*/
else
b=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（"PleaseenterthenameandtimeandstarttimeofPCB:
\n"）;
/*输入进程名、运行时间和开始时间*/
for（i=0;i{
p=（PCB*）malloc（sizeof（PCB））;/*为新进程开辟空间*/
scanf（"%s",p->name）;/*输入进程名*/
scanf（"%d",&p->needtime）;/*输入进程要求运行时间*/
scanf（"%s",p->starttime）;//输入进程开始时间
p->cputime=0;
p->state='W';/*表示就绪队列中未在队首先执行，但也是就绪状态*/
if（ready!
=NULL）
insert（p）;/*就绪队首不为NULL，插入新进程*/
else
{/*否则先插在NULL前*/
p->next=ready;
ready=p;
}
}
printf（"Displayisgoingtostart:
\n"）;
printf（"***********************************************\n"）;
print（）;
getchar（）;
run=ready;/*队列排好，run指向就绪队列队首*/
ready=ready->next;/*ready指向下一个进程*/
run->state='R';/*队首进程的状态为就绪*/
}
voidFCFS（）
{
while（run!
=NULL）
{
run->cputime=run->cputime+run->needtime;
run->needtime=0;
run->next=finish;
finish=run;
run->state='E';
run=NULL;
if（ready!
=NULL）
{
run=ready;
run->state='R';
ready=ready->next;
}
print（）;
}
}
voidmain（）
{
printf（"PleaseenterthetotalnumberofPCB:
\n"）;
scanf（"%d",&N）;
create（）;/*模拟创建进程，并输入相关信息*/
FCFS（）;/*先来先服务调度算法*/
}
2.1.4．测试结果及说明
首先输入进程个数（为5个），这里命名为A,B,C,D,E，然后分别输入运行时间和开始时间
所有进程都在队列中，并都处于等待状态
其中一个进程执行完毕
所有进程都执行完毕
2.2．优先级调度
2.2.1．算法思想
进程的执行顺序由高优先级到低优先级，系统或用户按某种原则为进程指定一个优先级来表示该进程所享有的确调度优先权。
该算法核心是确定进程的优先级。
2.2.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．时间片轮转调度
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;/*运行一次要求运行时间减一*/
升级会员 