操作系统课程设计进程调度模拟算法5种.docx
《操作系统课程设计进程调度模拟算法5种.docx》由会员分享，可在线阅读，更多相关《操作系统课程设计进程调度模拟算法5种.docx（21页珍藏版）》请在冰点文库上搜索。
操作系统课程设计进程调度模拟算法5种
福建农林大学计算机与信息学院
课程设计报告
课程名称：
操作系统
实习题目：
进程调度算法模拟
姓名：
***
系：
计算机
专业：
计算机科学与技术
年级：
2011级
学号：
**
指导教师：
***
职称：
***
2014年1月16日
福建农林大学计算机与信息学院信息工程类
课程设计报告结果评定
评语：
成绩：
指导教师签字：
评定日期：
1.进程调度算法模拟课程设计的目的……………………………………………1
2.进程调度算法模拟课程设计的要求……………………………………………1
3.进程调度算法模拟课程设计报告内容…………………………………………1
3．1前言………………………………………………………………………1
3．2进程调度算法模拟设计的环境…………………………………………1
3．3系统流程图及各模块……………………………………………………2
4．总结…………………………………………………………………………18
参考文献………………………………………………………………………19
参考网站………………………………………………………………………19
进程调度算法模拟
1.进程调度算法模拟课程设计的目的和意义
2013-2014学年，在学习了《操作系统》这门课后，对当中的进程调度算法产生了浓厚的兴趣。
各种调度算法，理论上比较好理解。
为了加深印象，我决定把各种调度算法用C语言写出来。
于是便产生这份从头到尾都让我绞尽脑汁的课程设计。
做这份课程设计，对从事系统开发的人员来说，是必要的，可以在一定程度上为自己以后的发展铺路。
虽然用处不是特别明显，但对加深系统调用算法的理解无疑用处是巨大的。
2.进程调度算法模拟课程设计的要求
1.用C语言写出至少两种进程调度算法。
2.画出大概流程图。
3.对算法过程出现的bug进行调试。
4.展示最后的算法结果
3.1前言：
目前比较常见的几种进程调度算法有：
1.先到先服务（FCFS）
2.短进程优先（非抢占和抢占）算法（SPF）
3.高响应比优先算法
4.时间片轮转算法
我选出其中三种即先到先服务，短进程优先（2种）和时间片轮转算法进行C语言描
述以加深对这三种算法的理解。
3.2进程调度算法模拟设计的环境
VC++6.0及CodeBlocks，32位计算机WIN7操作系统。
3.3流程图
定义进程结构体：
structPro{
intnum;//进程号
inttime_in;//进程到达时间
intwork_time;//进程服务时间
intbtime;//用于抢占式进程优先记录该进程开始时间
intl_w_time;//用于抢占式进程优先记录剩余服务时间
intend_time;//记录该进程结束时间，（需要时时监测）
intjudge;//用于需要时的标记
}pro[10];//进程结构体
1先到先服务
算法描述：
把所有进程按到达先后排序，每次取最先到的进程执行后淘汰，再取下一个，直到所有进程调度完毕。
主要代码：
voidFCFS（）//先到先服务
{
chars[]={"先到先服务"};
printmat（s）;
PT;
inti,j;
intmin;
intt=pro_num;
intbegin_time=0x7fff;
for（i=1;i<=pro_num;i++）
{
if（pro[i].time_inbegin_time=pro[i].time_in;
pro[i].judge=0;//所有进程号查找标志置0，表示还未查找
}
while（t--）
{
for（i=1;i<=pro_num;i++）
{
if（pro[i].judge==0）
{
min=i;//设其为目前最早到达的时间
for（j=i+1;j<=pro_num;j++）
{
if（pro[j].judge==0&&pro[j].time_in<=pro[min].time_in）//该进程号若还未被查找且小于预设
min=j;
}
pro[min].judge=1;//该进程号被查找过
printf（Format2,pro[min].num,pro[min].time_in,pro[min].work_time,
begin_time,begin_time+pro[min].work_time,begin_time+pro[min].work_time-pro[min].time_in）;
begin_time+=pro[min].work_time;
puts（""）;
}
}
}
printmat（s）;
puts（""）;
}
程序截图：
2段进程优先非抢占
算法描述：
每次选出最短的进程进行调度，调度完毕则淘汰，直到所有进程都调度完毕；
voidSJF（）//短进程优先（非抢占）
{
chars[]="非抢占短进程优先";
printmat（s）;
PT;
structPro*p,*q,*head;
intt_num,t_work_time,t_time_in;
head=&pro[1];
/************************按所有进程到达时间排序*************/
p=head;
while（p-head{
for（q=p+1;q-head{
if（q->time_intime_in||（q->work_timework_time&&q->time_in==p->time_in））
{
t_num=p->num,t_time_in=p->time_in,t_work_time=p->work_time;
p->num=q->num,p->time_in=q->time_in,p->work_time=q->work_time;
q->num=t_num,q->time_in=t_time_in,q->work_time=t_work_time;
}
}
p++;
}
/*************************************************************/
/**********找出第一个执行的进程，即最先到达的最短进程*********/
inttime=0;
p=head;
for（q=head;q{
q->judge=0;
if（q->time_intime_in）
p=q;
if（q->time_in==p->time_in&&q->work_timework_time）
p=q;
}
intcnt=pro_num;
p=head;
while（cnt--）
{
time=timetime_in?
p->time_in:
time;
p->judge=1;
p->begin_time=time;
time+=p->work_time;
p->end_time=time;
for（q=head;q{
if（p->judge==1&&q->judge==0）
p=q;
elseif（p->judge==0&&（q->work_timework_time））
{
p=q;
}
}
}
for（p=head;p{
printf（Format2,p->num,p->time_in,p->work_time,p->begin_time,p->end_time,p->end_time-p->time_in）;
puts（""）;
}
printmat（s）;
puts（""）;
}
3短进程优先（抢占）
算法描述：
按时间叠加，当新进程到达时，判断如果比当前执行的进程短，则发生抢占，执行完的淘汰，直到所有进程都调度完毕。
intfind（intpp,inttime）
{
inti;
for（i=1;i<=pro_num;i++）
{
if（pro[pp].l_w_time==0||（pro[i].l_w_time!
=0&&pro[i].l_w_time=pro[i].time_in））
pp=i;
}
returnpp;
}
voidtest（）
{
inti;
for（i=1;i<=pro_num;i++）
{
printf（Format2,pro[i].num,pro[i].time_in,pro[i].work_time,pro[i].btime,pro[i].end_time,pro[i].end_time-pro[i].time_in）;
puts（""）;
}
}
voidSJF2（）//抢占式短进程优先
{
chars[]={"抢占式短进程优先"};
printmat（s）;
PT;
inti;
structPro*p,*q;//先对到达时间进行排序//
structPro*head=&pro[1];
intt_num,t_time_in,t_work_time;
inttime_cnt=0,time;
p=head=&pro[1];
while（p-head{
for（q=p+1;q-head{
if（q->time_intime_in）
{
t_num=p->num,t_time_in=p->time_in,t_work_time=p->work_time;
p->num=q->num,p->time_in=q->time_in,p->work_time=q->work_time;
q->num=t_num,q->time_in=t_time_in,q->work_time=t_work_time;
}
}
p++;
}
for（i=1;i<=pro_num;i++）
{
pro[i].l_w_time=pro[i].work_time;
time_cnt+=pro[i].work_time;
}
intpp=1;
time=pro[pp].time_in;
while（time_cnt--）
{
pro[pp].l_w_time--;
time++;
if（pro[pp].l_w_time==0）{pro[pp].end_time=time;}else;
if（pro[pp].btime==0&&pro[pp].time_in!
=0）pro[pp].btime=time-1;else;
pp=find（pp,time）;
}
test（）;
printmat（s）;
puts（""）;
}
4时间片轮转（以单位1为例）
取当前已经到达的进程，执行一个时间片，跳转至下一个已经到达的进程，再执行一个时间片，直到所有进程都调度完毕。
voidTROT（）
{
char*s="时间片轮转算法";
printmat（s）;
PT;
structPro*p,*q,*head;
intt_num,t_time_in,t_work_time;
head=&pro[1];
p=head;
/************************给所有进程按到达时间排序*************/
while（p-head{
for（q=p+1;q-head{
if（q->time_intime_in）
{
t_num=p->num,t_time_in=p->time_in,t_work_time=p->work_time;
p->num=q->num,p->time_in=q->time_in,p->work_time=q->work_time;
q->num=t_num,q->time_in=t_time_in,q->work_time=t_work_time;
}
}
p++;
}
/*************************************************************/
inttime=pro[1].time_in;
for（p=head;pjudge=0;p->left_work=p->work_time;}
intflag=1;
for（p=head;flag;p++）
{
if（p->time_in<=time&&p->left_work>0）
{
p->left_work--;
if（p->judge==0）{p->judge=1;p->begin_time=time;}
if（p->left_work==0）p->end_time=time+1;
}
elsecontinue;
time++;
for（q=head;q{
if（q->left_work!
=0）break;
}
if（q==head+pro_num）flag=0;
if（p==head+pro_num-1）//设从开头再开始找
p=head-1;
}
for（q=head;q{
printf（Format2,q->num,q->time_in,q->work_time,q->begin_time,q->end_time,q->end_time-q->time_in）;
puts（""）;
}
printmat（s）;
}
5高响应比优先
先对所有进程排序，已经到达的进程，每次选取响应比最高的进程进行调度，直到所有进程调度完毕。
voidFPF（）
{
char*s="高响应比优先算法";
char*ss="****************";
printmat（s）;
PT;
structPro*p,*q,*head;
intt_num,t_time_in,t_work_time;
head=&pro[1];
p=head;
/************************给所有进程按到达时间排序*************/
while（p-head{
for（q=p+1;q-head{
if（q->time_intime_in）
{
t_num=p->num,t_time_in=p->time_in,t_work_time=p->work_time;
p->num=q->num,p->time_in=q->time_in,p->work_time=q->work_time;
q->num=t_num,q->time_in=t_time_in,q->work_time=t_work_time;
}
}
p++;
}
/*************************************************************/
inttime=pro[1].time_in;
intcnt=pro_num;
for（p=head;pjudge=0;p->left_work=p->work_time;}
p=head;
while（cnt--）//查找、打印cnt次
{
p=head;
while
（1）
{
if（p->judge==0）break;
elsep++;
}
time=timetime_in?
p->time_in:
time;
for（q=head;q{
if（q->judge==0&&time>=q->time_in&&（time-q->time_in）*p->work_time>（time-p->time_in）/q->work_time）
p=q;
}
p->judge=1;
p->begin_time=time;
time+=p->work_time;
p->end_time=time;
printf（Format2,p->num,p->time_in,p->work_time,p->begin_time,p->end_time,p->end_time-p->time_in）;
puts（""）;
}
printmat（ss）;
}
4总结：
在本次课程设计过程中，我碰到不少程序调试的问题，但通过不懈努力一一解决了，从中我也学到了很多调试技巧，从而提升了自己在以后程序编写中的技能。
另外，进程调度算法，虽然不是很难，但是再写一次，能加深对算法的理解和运用，好处还是很多的。
参考文献：
《操作系统设计与实现》第三版；电子出版社
《操作系统教程第四版》清华大学出版社
参考网站
升级会员 