进程调度程序设计报告源代码资料.docx
《进程调度程序设计报告源代码资料.docx》由会员分享,可在线阅读,更多相关《进程调度程序设计报告源代码资料.docx(23页珍藏版)》请在冰点文库上搜索。
进程调度程序设计报告源代码资料
成绩
课程设计报告
题目进程调度程序设计
课程名称操作系统课程设计
院部名称计算机工程学院
专业计算机科学与技术
班级13计算机科学与技术(单)
(1)
学生姓名周敏健
学号1305201013
课程设计地点A104
课程设计学时20学时
指导教师何健
金陵科技学院教务处制
课程设计课题
进程调度程序设计
摘要
在多道系统中,对批处理作业需要进行作业调度。
作业调度是在资源满足的条件下,将处于就绪状态的作业调入内存,同时生成与作业相对应的进程,并未这些进程提供所需要的资源。
进程调度需要根据进程控制块(PCB)中的信息,检查系统是否满足进程的资源需求。
只有在满足进程的资源需求的情况下,系统才能进行进程调度。
下面是几种常见的作业调度算法:
先来先服务(FCFS)、优先算法、轮换算法、短作业优先算法以及最高响应比优先法等,本文将对前两种算法进行详细的介绍。
关键词:
进程调度,优先级,FCFS,PCB,作业,资源
一、课程设计的目的和要求
1、目的
进程调度是处理机管理的核心内容。
本设计要求用C语言编写和调试一个简单的进程调度程序。
通过设计本可以加深理解有关进程控制块、进程队列的概念,并体会和了解最高优先数优先的调度算法(即把处理机分配给优先数最高的进程)和先来先服务算法的具体实施办法。
2、要求
1)进程调度算法:
采用最高优先数优先的调度算法(即把处理机分配给优先数最高的进程)和先来先服务算法。
2)每个进程有一个进程控制块(PCB)表示。
进程控制块可以包含如下信息:
进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。
3)进程的优先数及需要的运行时间可以事先人为地指定(也可以由随机数产生)。
进程的到达时间为进程输入的时间。
进程的运行时间以时间片为单位进行计算。
4)每个进程的状态可以是就绪W(Wait)、运行R(Run)、或完成F(Finish)三种状态之一。
5)就绪进程获得CPU后都只能运行一个时间片。
用已占用CPU时间加1来表示。
如果运行一个时间片后,进程的已占用CPU时间已达到所需要的运行时间,则撤消该进程,如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间,也就是进程还需要继续运行,此时应将进程的优先数减1(即降低一级),然后把它插入就绪队列等待CPU。
6)每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的PCB,以便进行检查。
7)重复以上过程,直到所要进程都完成为止。
二、系统需求分析
编写一个模拟进程调度的程序,将每个进程抽象成一个进程控制块PCB,PCB用一个结构体描述。
采用两种不同的调度算法来实现功能,主要有如下几大功能模块组成。
(1)创建优先数PCB模块
用循环来实现对每个进程的进程名、进程优先数(随机分配)以及所需时间的录入。
将进程队列存放到就绪队列等待执行。
(2)优先数调度算法模块
从优先级最高(就绪队列的第一个进程)的开始执行,每执行一次优先数减1,并重新放入就绪队列进行排序,对排序完的继续运行直到所有进程都结束。
(3)FCFS创建PCB模块
对N个进程的信息进行输入:
进程名、到达时间、需要时间等。
每输入一个进程,按进程的到达时间进行排序,记下前驱和后继的方法。
(4)FCFS调度算法模块
当系统时间与第一个进程到达时间一致时,将进程状态置为Run,直到这个进程执行完,再判断下个进程的到达时间,若系统时间大于下个进程的到达时间,即上个进程的结束时间就是下个进程的开始时间,反之就等待系统时间。
进程结束后放入完成队列。
(5)主函数及菜单显示
由主菜单进入显示界面,进行算法选择。
三、总体设计
进程是程序在处理机上的执行过程。
进程存在的标识是进程控制块(PCB),所谓系统创建一个进程,就是由系统为某个程序设置一个PCB,用于对该进程进行控制和管理。
进程任务完成,由系统收回其PCB,该进程便消亡。
每个进程可有三个状态:
运行状态、就绪状态和完成状态。
因此设计三个链队列,finish为完成队列的头指针,wait为就绪队列的头指针。
因为每一时刻,CPU只能运行一个进程,所以运行队列只有一个run指针指向当前运行的进程。
考虑到处理的方便,将它们设为全局变量。
总体结构框架图:
四、详细设计
(1)优先数调度算法
优先调度算法要为每一个进程设一个优先数,它总是把处理机给就绪队列中具有最高优先权的进程。
常用的算法有静态优先权法和动态优先权法。
本程序采用了动态优先权法,使进程的优先权随时间而改变。
初始的进程优先数取决于进程运行所需的时间,时间大,则优先数低,所以采取了将进程优先数定位最大的那个进程,随着进程的运行优先数进行调整,每次运行时都是从就绪队列中选取优先数最大的进程运行,所以将就绪队列按照优先数的大小从高到低排序,这样,每次取队头进程即可。
(2)先来先服务调度算法
先来先服务调度算法是按照进程进入就绪队列的先后顺序调度并分配处理机执行。
先来先服务算法是一种不可抢占的算法,先进入就绪队列的进程,先被处理机运行,一旦一个进程占有了处理机,它就一直运行下去,直到该进程完成工作或者因为等待某种事件而不能继续运行时才释放处理机。
五、测试、调试过程
界面
优先数算法输入
优先数算法输出
FCFS算法输入
FCFS算法输出
遇到的问题:
在设计程序时,在算法上面出现了一些错误,优先数不是由大到小排序,而是应该这样理解,当进程执行一个时间片时,优先数减一(使用CPU的时间变少,反而优先级高),因此,优先级高的优先数应该是比较小的,而不是优先数大的优先级大。
在程序调试时,链表发生了错误,该内存不可写或者就是程序直接结束,但最终结果不是我想要的,经过一番折腾,最后发现,头指针和头结点混淆,有些地方没有给指针分配内存,语句的先后顺序不正确,以及没有考虑到链表最后没有设置结束标志。
六、结论与体会
做这个程序我断断续续的算下来应该总共用了2天,主要是花时间在观察别人的算法读别人的程序,然后才开始写自己的程序,期间参考了前人的程序并进行了改善和加工,这让我对进程调度的理解再次加深了,这是在平常学习的基础上,与程序相结合的过程,让我再次感受到编程给我们带来的无穷魅力,只要自己有兴趣,其实编程也是一件有趣的事,为了达到一定的要求,我们必须多次尝试用不同的方法去实现它,比如,进程调度有先来先服务算法,对于这个算法,可以用数组实现,也可以用链表实现,但是到底哪个更好哪个更灵活呢,相信学过C语言的人都知道肯定是用链表实现最好了。
这次设计还是有一些不足之处的,比如在算法和运行效率上还是有些欠缺的,需要进一步去改善程序代码,提高效率,减少冗余和错误,让使用者更清晰的观察和理解进程调度。
七、参考文献
[1]任爱华、罗晓峰.操作系统实用教程(第三版)[M].北京:
清华大学出版社,2009
[2]谌卫军、王浩娟.操作系统[M].北京:
清华大学出版社,2012.5
[3](日)前桥和弥(MaebasiKazuya).征服C指针[M].吴雅明译.北京:
人民邮电出版社,2013.2
附录:
源程序
#include
#include
#include
#include
#include
typedefstructnode
{
charname[10];//进程名
intprio;//进程优先数
intcputime;//进程占用CPU时间
intneedtime;//进程到完成还要的时间
intarrivetime;//进程到达时间
intstarttime;//进程开始时间
intfinishtime;//进程完成时间
intservicetime;//进程服务时间
charstate;//进程的状态
structnode*next;
}PCB;
PCB*finish,*ready,*run;//队列指针
intN;//进程量
voidfirstin()
{
run=ready;//就绪队列头指针赋值给运行头指针
run->state='R';//进程状态变为运行态
ready=ready->next;//就绪对列头指针后移到下一进程
}
voidprt1(chara)
{
switch(a)
{
case1:
/*优先数法*/
printf("名字\t进程占用CPU时间\t需要的时间\t优先级数\t状态\n");break;
case2:
/*先来先服务算法*/
printf("名字\t到达时间\t开始时间\t服务时间\t完成时间\t状态\n");break;
default:
break;
}
}
voidprt2(chara,PCB*q)
{
switch(a)
{
case1:
printf("%s\t%d\t\t%d\t\t%d\t\t%c\n",q->name,q->cputime,q->needtime,q->prio,q->state);
break;
case2:
printf("%s\t%d\t\t%d\t\t%d\t\t%d\t\t%c\n",q->name,q->arrivetime,q->starttime,q->servicetime,q->finishtime,q->state);
break;
default:
break;
}
}
voidprt(charalgo)
{
PCB*p;
prt1(algo);//输出文字格式
if(run!
=NULL)//如果运行指针不空
prt2(algo,run);//输出当前正在运行的PCB
p=ready;//输出就绪队列PCB
while(p!
=NULL)
{
prt2(algo,p);
p=p->next;
}
p=finish;//输出完成队列的PCB
while(p!
=NULL)
{
prt2(algo,p);
p=p->next;
}
getchar();//压任意键继续
}
voidinsert1(PCB*q)
{
PCB*p1,*s,*r;
intb;
s=q;//待插入的PCB指针
p1=ready;//就绪队列头指针
r=p1;//做p1的前驱指针
b=1;
while((p1!
=NULL)&&b)//根据优先数确定插入位置
if(p1->prio>=s->prio)
{
r=p1;
p1=p1->next;
}
else
b=0;
if(r!
=p1)//如果条件成立说明插入在r与p1之间
{
r->next=s;
s->next=p1;
}
else
{
s->next=p1;//否则插入在就绪队列的头
ready=s;
}
}
voidinsert2(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->arrivetimearrivetime)
{
r=p1;
p1=p1->next;
}
else
b=0;
}
if(r!
=p1)
{
r->next=s;
s->next=p1;
}
else
{
s->next=p1;
ready=s;
}
}
voidcreate1(charalg)
{
PCB*p;
inti,time;
charna[10];
ready=NULL;//就绪队列头指针
finish=NULL;//完成队列头指针
run=NULL;//运行队列头指针
//输入N个进程名和所需时间创建PCB
for(i=1;i<=N;i++)
{
printf("请输入第%d个进程的名字和运行时间\n进程名:
",i);
p=(PCB*)malloc(sizeof(PCB));
scanf("%s",na);
printf("所需时间:
");
scanf("%d",&time);
strcpy(p->name,na);
p->cputime=0;
p->needtime=time;
p->state='W';
p->prio=rand()%15+1;//随机分配优先数[1,15]
if(ready!
=NULL)//就绪队列不空则调用插入函数插入
insert1(p);//对新进程插入就绪队列
else
{
p->next=ready;//创建就绪队列的第一个PCB
ready=p;
}
}
system("cls");
printf("优先数算法结果输出\n");
printf("---------------------------------------------------------------------------\n");
prt(alg);//输出进程PCB信息
run=ready;//将就绪队列的第一个进程投入运行
ready=ready->next;
run->state='R';
}
voidcreate2(charalg)
{
PCB*p;
inti;
ready=NULL;
run=NULL;
finish=NULL;
for(i=0;i{
p=(PCB*)malloc(sizeof(PCB));
printf("进程名:
");
scanf("%s",p->name);
printf("到达时间:
");
scanf("%d",&p->arrivetime);
printf("需要时间:
");
scanf("%d",&p->servicetime);
p->starttime=0;
p->finishtime=0;
p->state='W';
if(ready!
=NULL)
insert2(p);//将新进程插入就绪队列
else
{
p->next=ready;//创建就绪队列的第一个
ready=p;
}
}
system("cls");
printf("先来先服务算法结果输出\n");
printf("---------------------------------------------------------------------------\n");
prt(alg);
}
voidpriority(charalg)
{
while(run!
=NULL)//当运行队列不空时,有进程正在运行
{
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
run->prio=run->prio-1;//每运行一次优先数-1
if(run->prio<0)//如果优先数减到小于0,则转换成0
run->prio=0;
if(run->needtime==0)//如果所需时间为0,即完成,将其插入完成队列
{
run->next=finish;
finish=run;
run->state='F';//置状态为完成态
run=NULL;//运行队列头指针为空
if(ready!
=NULL)//如果就绪队列不空
firstin();//将就绪对列的第一个进程投入运行
}
else//没有运行完同时优先数不是最大,则将其变为就绪态插入到就绪队列
if((ready!
=NULL)&&(run->prioprio))
{
run->state='W';//状态改为就绪
insert1(run);//将进程按优先数大小插入
firstin();//将就绪队列的第一个进程投入运行
}
prt(alg);//输出进程PCB信息
}
}
voidFCFS(charalg)
{inttime=0;//系统时间从0开始
do{
run=ready;//就绪序列的第一个进程放入run队列进行执行
run->state='R';//进程开始执行
ready=ready->next;//指向下一个
time=run->arrivetime>time?
run->arrivetime:
time;
run->starttime=time;//进程开始
prt(alg);//显示正在执行的进程
time=time+run->servicetime;//计算下个进程最小可开始时间
run->finishtime=time;//进程结束时间
run->state='F';//结束状态标识
prt(alg);//进程结束再显示
run->next=finish;
finish=run;//进程结束放入结束队列
run=NULL;
}while(ready!
=NULL);
}
/*菜单显示函数*/
voidMenu()
{
system("cls");
printf("\t\t+━━━━━━━━━━━━━━━━━━━━━━+\n");
printf("\t\t|进程调度算法|\n");
printf("\t\t|━━━━━━━━━━━━━━━━━━━━━━|\n");
printf("\t\t||\n");
printf("\t\t|[1]优先数算法|\n");
printf("\t\t||\n");
printf("\t\t|[2]先来先服务算法|\n");
printf("\t\t||\n");
printf("\t\t|[3]退出系统|\n");
printf("\t\t||\n");
printf("\t\t|━━━━━━━━━━━━━━━━━━━━━━|\n");
printf("\t\t|By:
周敏健|\n");
printf("\t\t+━━━━━━━━━━━━━━━━━━━━━━+\n");
printf("\t\t请输入编号:
");
}
intmain()
{
charalgo;//接收算法编号
charmainmenu;//判断是否继续
srand((unsigned)time(NULL));
system("cls");//清屏
do{
Menu();//显示菜单
scanf("%d",&algo);//输入算法编号
switch(algo)
{
case1:
system("cls");
printf("您选择的是优先数算法\n");
printf("请输入进程数目:
");
scanf("%d",&N);//输入进程数
create1(algo);//创建队列
priority(algo);//优先数
break;
case2:
system("cls");
printf("您选择的是先来先服务算法\n");
printf("请输入进程数目:
");
scanf("%d",&N);//输入进程个数
create2(algo);//创建队列
FCFS(algo);//先来先服务
break;
case3:
printf("\t\t再见!
\n");
exit(0);
break;
default:
printf("输入有误\n");
break;
}
printf("\n是否继续操作(Y/N)");
fflush(stdin);
mainmenu=getchar();
}
while(mainmenu=='y'||mainmenu=='Y');
return0;
}