进程调度模拟实现.doc

操作系统课程设计报告

题目： 进程调度算法的模拟实现

专业
计算机科学与技术
学生姓名
刘远强
班级
计算机131
学号
1310704109
指导教师
韩 立 毛
完成日期
2015.7.10

信 息 工 程 学 院

23

操作系统课程设计（2015）
目 录
1 概述 2
1.1 设计目的 2
1.2 设计要求 2
2 设计原理 2
2.1 先来先服务算法 2
2.2 短进程优先算法 2
2.3高优先权优先算法 2
2.4高响应比优先算法 3
3 概要设计 3
3.1 功能结构 3
4 详细设计 4
4.1 用户界面模块设计 4
4.2 算法模块设计 4
5 测试与分析 12
5.1 测试方案 12
5.2 测试结果 12
5.3 结果分析 14
6 设计小结 15
7 参考文献 15
附录 源程序代码 16
题目：进程调度算法的模拟实现
1 概述
1.1 设计目的
在多道程序和多任务系统中，系统内同时处于就绪状态的进程可能有若干个，也就是说能运行的进程数大于处理机个数。为了使系统中的进程能有条不紊地工作，必须选用某种调度策略，选择一进程占用处理机。要求学生设计一个模拟处理机调度算法，以巩固和加深处理机调度的概念。
1.2 设计要求
a)至少有四种作业调度算法；
b)能根据不同的调度算法算出每个作业的周转时间和带权周转时间，并通过一组作业算出系统的平均周转时间和平均带权周转时间，比较各种算法的优缺点；
c)设计一个实用的用户界面，以便选择不同的作业调度算法。
2 设计原理
2.1 先来先服务算法
每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源创建进程，然后放入就绪队列。
2.2 短进程优先算法
短进程优先调度算法是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。
2.3高优先权优先算法
a）当该算法用于作业调度时，系统从后备作业队列中选择若干个优先级最高的，且系统能满足资源要求的作业装入内存运行。
b）当该算法用于进程调度时，将把处理机分配给就绪进程队列中优先级最高的进程。
2.4高响应比优先算法
高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。
3 概要设计
3.1 功能结构
函数调用流程图如图3—1

图3—1
4 详细设计
4.1 用户界面模块设计
用户界面包含4种算法的选择项及退出项，并能根据对应选项做出相应反应。选择算法则进入所选算法进行进一步计算，选择退出则关闭界面，输入其他错误字符会显示错误提示。
void main()
{
int choice;
cout<<" *进程调度算法模拟实现*"<"<>choice;
JCB *head=NULL;
switch(choice)
{
case 1:head=create(head);FCFS(head);goto l1;
case 2:head=create(head);SJF(head,jnum);goto l1;
case 3:head=create(head);SUPER(head,jnum);goto l1;
case 4:head=createhead);HRN(head,jnum);goto l1;
case 5:break;
default:cout<<"输入错误！\n请重新输入："<next;
cout<<"作业执行顺序为：";
while(p!=NULL)

{
cout<<"--"<name;
p=p->next;
}
cout<next;
while(s!=NULL)
{
cout<name<htime<starttime<ftime<zhouzhuan<daiquan<next;
}
cout<共复制HEAD链表长度的LENGTH次，就复制完毕。这样形成的最短作业优先链表就刚刚好是按作业所需运行时间按从小到大的顺序排列的了。
void SJF(JCB *head,int n)
{
JCB *p,*p1;
JCB *flag=NULL;
JCB *q=NULL;
double time=0,j=0,runTime=0, drunTime=0;
int xuhao=0;
string pname[MAX_NUM];
for(int ss=0;ss cout<next;
p=head;
while(head)
{
q=head;
if(time < p->htime) //如果该作业提交时间早于其它作业，则先执行该作业
time=p->htime;
flag=head; //用于暂存将要执行的作业
while(q && q->htime <= time)
{
if(q->ntimentime)
flag=q;
q=q->next;
}
//输出当前执行作业的信息
cout<name;
cout<ntime;
cout<ntime);
cout<htime + flag->ntime);
cout<<" "<g->htime + flag->ntime)/flag->ntime)<htime+flag->ntime); //当前执行作业的周转时间
runTime +=j; //记录周转时间
time+=flag->ntime;
drunTime+=j/flag->ntime; //带权周转时间
pname[xuhao]=flag->name;
xuhao++;
//将执行过的作业从链表中删除
if(flag==head) //在链表头
head=head->next;
else
{ //在链表中
p1=head;
while(p1->next!=flag)
p1=p1->next;
p1->next=flag->next;
delete flag; //删除这个作业所占的节点
}
}
cout<<"作业执行顺序为：";
for(ss=0;ss"")
cout<<" -> ";
}
cout<nt n)
{
JCB *p,*p1;
JCB *flag=NULL;
JCB *q=NULL;
double time=0,j=0,runTime=0, drunTime=0;
int xuhao=0;
string pname[MAX_NUM];
for(int ss=0;ssnext;
phead;
while(head)
{
q=head;
if(time < p->htime) //如果该作业提交时间早于其它作业，则先执行该作业
time=p->htime;
flag=head; //用于暂存将要执行的作业
while(q && q->htime <= time)
{
if(q->super>flag->super)
flag=q;
q=q->next;
}
//输出当前执行作业的信息
cout<8)<name;
cout<ntime;
cout<ntime);
cout<htime + flag->ntime);
cout<<" "<htime + flag->ntime)/flag->ntime)<htime+flag>ntime); //当前执行作业的周转时间
runTime +=j; //记录周转时间
time+=flag->ntime;
drunTime+=j/flag->ntime; //带权周转时间
pname[xuhao]=flag->name;
xuhao++;
//将执行过的作业从链表中删除
if(flag==head) //在链表头
head=head->next;
else
{ //在链表中
p1=head;
while(p1->next!=flag)
p1=p1->next;
p1->next=flag->next;
delete flag; //删除这个作业所占的节点
}
}
cout<<"作业执行顺序为：";
for(ss=0;ss ";
}
cout<out<<"平均带权周转时间为："<NULL;
JCB *q=NULL;
double time=0,j=0,runTime=0, drunTime=0;
int xuhao=0;
string pname[MAX_NUM];
for(int ss=0;ssnext;
p=head;
while(head)
{
q=head;
if(time < p->htime) //如果该作业提交时间早于其它作业，则先执行该作业
time=p->htime;
flag=head; //用于暂存将要执行的作业
//计算当前链表中作业的响应比
while(q && q->htime <= time)
{
if((time - q->htime)/(q->ntime) > (time - flag->htime)/(flag->ntime))
flag=q;
q=q->next;
}
if(timehtime)//如果上一次结束时间比当前选中要执行作业的结束时间小
time=flag->htime; //则当前作业开始时间为提交时间
//输出当前执行作业的信息
cout<name;
cout<ntime;
cout<ntime);
cout<htime + flag->ntime);
cout<<" "<htime + flag->ntime)/flag->ntime)<htime+flag->ntime); //当前执行作业的周转时间
runTime +=j; //记录周转时间
time+=flag->ntime;
drunTime+=j/flag->ntime; //带权周转时间
pname[xuhao]=flag->name;
xuhao++;
//将执行过的作业从链表中删除
if(flag==head) //在链表头
head=head->next;
else
{ //在链表中
p1=head;
while(p1->next!=flag)
p1=p1->next;
p1->next=flag->next;
delete flag; //删除这个作业所占的节点
}
}
cout<<"作业执行顺序为：";
for(ss=0;ssame[ss];
if(pname[ss+1] !="")
cout<<" -> ";
}
cout<结束时间 、周转时间、带权周转时间。通过四种算法之间的比较了解他们的优缺点。
5.2 测试结果
a)用户界面如图5.2.1

图5.2.1
b)先来先服务算法如图5.2.2

图5.2.2
c)短作业优先算法如图5.2.3

图5.2.3
d)高优先权算法如图5.2.4

图5.2.4
f）高响应比优先算法如图5.2.5

图5.2.5
e）错误界面如图5.2.6

图5.2.6
5.3 结果分析
由测试结果可知每种算法的优缺点：
a）先来先服务算法：有利于长作业（进程）而不利于短作业（进程）
有利于CPU繁忙型作业（进程）而不利于I/O繁忙型作业（进程）。
b)短作业优先算法：
比FCFS改善平均周转时间和平均带权周转时间短作业的等待时间；
提高系统的吞吐量；对长作业非常不利，可能长时间得不到执行；
未能依据作业的紧迫程度来划分执行的优先级；
c)难以准确估计作业（进程）的执行时间，从而影响调度性能。c)高优先权算法：动态优先级优点是使相应的优先级调度算法比较灵活、科学，可防止有些进程一直得不到调度，也可防止有些进程长期垄断处理机。动态优先级缺点是需要花费相当多的执行程序时间，因而花费的系统开销比较大。d)高响应比优先算法：短作业与先后次序的兼顾，且不会使长作业长期得不到服务响应比计算系统开销，增加系统开销。
6 设计小结
通过改程序对操作系统的基础知识了解得更透彻了，同时对磁盘调度的四种算法——先来先服务算法，短进程优先调度算法，优先权算法，高响应比调度算法有了更深刻的理解和掌握，使我能够为进程调度选择适当的算法，提高CPU工作效率。进行进程调度程序设计的过程中，得到老师的大力指导和同学的支持，在此向他们表示感谢。经过自己的动手操作和同学老师的指导我成功的做出了课程设自己感到很高兴。在整个过程中自己也感受到了集体团结的力量，今后无论是在工作还是学习中我都会发样这种精神。
7 参考文献
[1] 韩立毛，李先锋. 计算机操作系统实践教程[M]，南京：南京大学出版社，2011.10.
[2] 严蔚敏，吴伟民. 数据结构[M]，北京：清华大学出版社，1997.4
[3] 张尧学，史美林. 计算机操作系统教程[M]，北京：清华大学出版社，2000.8.
[4] 孙静宇. 计算机操作系统课程设计指导书[M]，山西：太原理工出版社，2006.4.
附录 源程序代码
#include
#include
#include
using namespace std;
#define MAX_NUM 15
typedef struct JCB
{
char name[10];//作业名
float htime;//作业到达时间
float ntime;//作业估计运行的时间
float starttime;//作业开始运行时间
float ftime;//作业完成的时间
float zhouzhuan;//周转时间
float daiquan;//带权周转时间
float xiangyingbi;//相应比
int super;//优先级
JCB *next;//定义指向下一个作业的指针
}JCB;
int jnum;//定义作业数为jnum
float total;//记录所有作业的总时间
double weight;//记录所有作业的带权周转时间

JCB *create(JCB *head);//创建作业队列
void dealFCFS(JCB *head);//FCFS记录处理
void sortFCFS(JCB *head);//将作业按到达的先后顺序排列
void FCFS(JCB *head);//先来先服务算法
void SJF(JCB *head,int n);//短作业优先算法
void SUPER(JCB *head,int n);//高优先权优先算法
void HRN(JCB *head,int n);//高响应比优先算法
void main()
{
int choice;
cout<<" *进程调度算法实现*"<"<>choice;
JCB *head=NULL;
switch(choice)
{
case 1:head=create(head);FCFS(head);goto l1;
case 2:head=create(head);SJF(head,jnum);goto l1;
case 3:head=create(head);SUPER(head,jnum);goto l1;
case 4:head=create(head);HRN(head,jnum);goto l1;
case 5:break;
default:cout<<"输入错误！\n请重新输入："<>jnum;
for(int i=0;inext=NULL;
cout<<"请依次输入第"<的信息(作业名、优先级、到达时间、估计运行时间)：";
cin>>p1->name>>p1->super>>p1->htime>>p1->ntime;
p2->next=p1;
}
return head;
}
//FCFS算法
void sortFCFS(JCB *head)//将作业按到达的先后顺序排列
{
JCB *p,*q,*r,*s;
if(head->next!=NULL)
{
p=head->next->next;
head->next->next=NULL;
}
while(p)
{
q=p;
pp->next;
r=head;
s=head->next;
while(s&&s->htime<=q->htime)
{
r=s;
s=s->next;
}
r->next=q;
q->next=s;
}
}
void dealFCFS(JCB *head)//FCFS记录处理
{
sortFCFS(head);
JCB *p,*q;

q=head->next;
q->starttime=q->htime;
q->ftime=q->starttime+q->ntime;
q->zhouzhuan=q->ftime-q->htime;
q->daiquan=q->zhouzhuan/(double)q->ntime;
total+=q->zhouzhuan;
weight+=q->daiquan;
p=q->next;
while(p!=NULL)
{
p->starttime=q->ftime;
p->ftime=p->starttime+p->ntime;
p->zhouzhuan=p->ftime-p->htime;
p->daiquan=p->zhouzhuan/(double)p->ntime;
total+=p->zhouzhuan;
weight+=p->daiquan;
q=p;
p=p->next;
}
}
void FCFS(JCB *head)//先来先服务算法
{
dealFCFS(head);
JCB *p,*q,*s;
p=head->next;
cout<<"作业执行顺序为：";
while(p!=NULL)
{
cout<<"--"<name;
p=p->next;
}
cout< s=head->next;
while(s!=NULL)
{
cout<name<htime<starttime<ftime<zhouzhuan<daiquan<next;
}
cout<num<0;ssnext;
p=head;
while(head)
{
q=head;
if(time < p->htime) //如果该作业提交时间早于其它作业，则先执行该作业
time=p->htime;
flag=head; //用于暂存将要执行的作业
while(q && q->htime <= time)
{
if(q->ntimentime)
flag=q;
q=q->next;
}
//输出当前执行作业的信息
cout<name;
cout<ntime;
cout<ntime);
cout<htime + flag->ntime);
cout<<" "<htime + flag->ntime)/flag->ntime)<htime+flag->ntime); //当前执行作业的周转时间
runTime +=j; //记录周转时间
time+=flag->ntime;
drunTime+=j/flag->ntime; //带权周转时间
pname[xuhao]=flag->name;
xuhao++;
//将执行过的作业从链表中删除
if(flag==head) //在链表头
head=head->next;
else
{ //在链表中
p1=head;
while(p1->next!=flag)
p1=p1->next;
p1->next=flag->next;
delete flag; //删除这个作业所占的节点
}
}
cout<<"作业执行顺序为：";
for(ss=0;ss cout< ";
}
cout<B *flag=NULL;
JCB *q=NULL;
double time=0,j=0,runTime=0, drunTime=0;
int xuhao=0;
string pname[MAX_NUM];
for(int ss=0;ssnext;
p=head;
while(head)
{
q=head;
if(time < p->htime) //如果该作业提交时间早于其它作业，则先执行该作业
time=p->htime;
flag=head; //用于暂存将要执行的作业
while(q && q->htime <= time)
{
if(q->super>flag->super)
flag=q;
q=q->next;
}
//输出当前执行作业的信息
cout<name;
cout<etw(8)<ntime;
cout<ntime);
cout<htime + flag->ntime);
cout<<" "<htime + flag->ntime)/flag->ntime)<htime+flag->ntime); //当前执行作业的周转时间