短作业优先调度和时间片轮转调度算法
电子科技大学
实 验 报 告
学生姓名：胡钟文 学号：2823103010 指导教师：罗惠琼
一、实验室名称： 主楼A2-412
二、实验项目名称：进程调度算法的设计
三、实验原理：
短作业（进程）优先调度算法：短作业调度算法是从后备队列中选择一个或者若干个估计运行时间最短的作业，将他们调入内存运行。而短进程优先调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或者发生某事件而被阻塞放弃处理机时再重新调度。
时间片轮转法：系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的队尾；然后，再把处理机分配给就绪队列中的新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一个给定的时间内均能获得一时间片的处理机执行时间。
四、实验目的：
通过对进程调度算法的设计，深入理解进程调度的原理
五、实验内容：
1．编写程序实现SJ（P）F算法
2．编写程序实现RR算法
六、实验器材（设备、元器件）：
装有VC++6.0的PC机一台
七、实验步骤：
1．打开VC，设计编写程序的源代码
2．编译运行程序的源代码
3．分析检验程序的结果是否正确
4．总结实验结果及结论
短进程优先调度源代码：
#include "stdio.h"
struct sjf{
char name[10];
float arrivetime;
float servicetime;
float starttime;
float finishtime;
float zztime;
float dqzztime;
};
sjf a[100];
void input(sjf *p,int N)
{ int i;
printf("intput the process's name & arrivetime & servicetime:\nfor exmple: a 0 100\n");
for(i=0;i<=N-1;i++)
{
printf("input the %dth process's information:\n",i+1);
scanf("%s%f%f",&p[i].name,&p[i].arrivetime,&p[i].servicetime);
}
}
void Print(sjf *p,float arrivetime,float servicetime,float starttime,float finishtime,float zztime,float dqzztime,int N)
{int k;
printf("run order:");
printf("%s",p[0].name);
for(k=1;k<N;k++)
{printf("-->%s",p[k].name);
}
printf("\nthe process's information:\n");
printf("\nname\tarrive\tservice\tstart\tfinish\tzz\tdqzz\n");
for(k=0;k<=N-1;k++)
{ printf("%s\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t\n",p[k].name,p[k].arrivetime,p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime);
}
}
//排序
void sort(sjf *p,int N)
{
for(int i=0;i<=N-1;i++)
for(int j=0;j<=i;j++)
if(p[i].arrivetime<p[j].arrivetime)
{
sjf temp;
temp=p[i];
p[i]=p[j];
p[j]=temp;
}
}
//运行阶段
void deal(sjf *p, float arrivetime,float servicetime,float starttime,float finishtime,float &zztime,float &dqzztime,int N)
{ int k;
for(k=0;k<=N-1;k++)
{
if(k==0)
{
p[k].starttime=p[k].arrivetime;
p[k].finishtime=p[k].arrivetime+p[k].servicetime;}
else
{
p[k].starttime=p[k-1].finishtime;
p[k].finishtime=p[k-1].finishtime+p[k].servicetime;}
}
for(k=0;k<=N-1;k++)
{
p[k].zztime=p[k].finishtime-p[k].arrivetime;
p[k].dqzztime=p[k].zztime/p[k].servicetime;
}
}
void sjff(sjf *p,int N)
{float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0;//对结构进行初始化
sort(p,N);
for(int m=0;m<N-1;m++)
{if(m==0)
p[m].finishtime=p[m].arrivetime+p[m].servicetime;
else
p[m].finishtime=p[m-1].finishtime+p[m].servicetime;
int i=0;
for(int n=m+1;n<=N-1;n++)
{if(p[n].arrivetime<=p[m].finishtime)//判断内存中每次完成之后有多少到达的进程
i++;
}
float min=p[m+1].servicetime;
int next=m+1;//m+1=n
for(int k=m+1;k<m+i;k++) //找出到达后的进程中最小的进程
{
if(p[k+1].servicetime<min)
{min=p[k+1].servicetime;
next=k+1;}
}
sjf temp;
temp=p[m+1];
p[m+1]=p[next];
p[next]=temp;
}
deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);
Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);
}
void main()
{ int N;
printf("------短作业优先调度算法------\n");
printf("input the process's number:\n");
scanf("%d",&N);
input(a,N);
sjf *b=a;
sjf *c=a;
sjff(b,N);
}
时间片轮转法源代码：
#include <stdio.h>
#define M 5 //物理页数
#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n")
typedef struct PCB
{
int ID;
int ReachTime;
int TotalTime;
}PCB; //进程号，到达时间和服务时间
typedef struct NOTE //备份
{
int ID;
int TotalTime;
}NOTE;
PCB A[M]; //5个进程
PCB a[M];
NOTE temp;
int queue[50]; //记录调度的进程
int K=0; //调度进程数组的标识
void INIT()//初始化
{
int i;
for(i=0;i<M;i++)
{
A[i].ID=-1;
}
}
int GetNum()//计算进程数
{
int i,j=0;
for(i=0;i<M;i++)
{
if(A[i].ID!=-1)
{
j++;
}
}
return j;
}
int GetReach(int time)//找出到达进程号
{
int i;
for(i=0;i<M;i++)
{
if(a[i].ReachTime<=time)
{
a[i].ReachTime=100;
return i;
}
}
return -1;
}
int GetInsert()//找出插入位置
{
int i;
for(i=0;i<M;i++)
{
if(A[i].ID==-1)
return i;
}
return -1;
}
void Forward(int num)//前移
{
int i;
for(i=0;i<num-1;i++)
{
A[i].ID=A[i+1].ID;
A[i].TotalTime=A[i+1].TotalTime;
}
A[num-1].ID=-1;
}
void Process()//执行进程
{
queue[K]=A[0].ID;
K++;
A[0].TotalTime--;
temp.ID=A[0].ID;
temp.TotalTime=A[0].TotalTime;
}
void main()
{
int i;
int time;
int t=0;
int reach;
int insert;
int num;
printf("RR算法\n\n");
INIT();
for(i=0;i<M;i++)
{
printf("请输入进程ID：");
scanf("%d",&a[i].ID);
printf("请输入到达时间：");
scanf("%d",&a[i].ReachTime);
printf("请输入服务时间：");
scanf("%d",&a[i].TotalTime);
}
for(i=0;i<M;i++)//运行时间
{
t=t+a[i].TotalTime;
}
for(i=0;i<50;i++)//初始化
{
queue[i]=-1;
}
for(time=0;time<=t;time++)
{
reach=GetReach(time);
if(reach!=-1)//有进程到达
{
insert=GetInsert();
A[insert].ID=a[reach].ID;
A[insert].TotalTime=a[reach].TotalTime;
num=GetNum();
if(num==1)
continue;//进程数为1
else
{
//进程数不为1
Process();
Forward(num);
if(temp.TotalTime!=0)
{
A[num-1].ID=temp.ID;
A[num-1].TotalTime=temp.TotalTime;
}
}
}
else//没有进程到达
{
num=GetNum();
if(num==1)
{//进程数为1
Process();
if(temp.TotalTime==0)
{
A[0].ID=-1;
}
}
else if(num==0)
continue;//进程数为0
else
{
Process();
Forward(num);
if(temp.TotalTime!=0)
{
A[num-1].ID=temp.ID;
A[num-1].TotalTime=temp.TotalTime;
}
}
}
}
printf("\n");
printf("调度顺序为：\n");
Myprintf;
for(i=0;i<50;i++)
{
if(queue[i]!=-1)
printf("|%2d ",queue[i]);
}
printf("|\n");
Myprintf;
printf("\n");
}
八、实验数据及结果分析：
短作业优先调度算法的实验结果：
时间片轮转调度算法结果：
九、实验结论：
本次实验成功的完成了短作业优先调度算法和轮转时间片调度算法的模拟，通过本次实验我们了解到短作业优先调度算法不利于长作业的处理，因为长作业将长期得不到处理，而轮转时间片调度算法则解决了这一问题。短长作业均能在每一个周期内分得一个时间片处理自己的任务。
十、总结及心得体会：
通过本次实验对短作业优先调度算法和时间片轮转调度算法有了更深入的理解，同时，对程序算法能力有了进一步的提高，同时对模块化编程有了更深入得理解，代码的模块化会使程序的代码复用率提高，提高编程的效率。
十一、对本实验过程及方法、手段的改进建议：
本次实验的时间片轮转调度算法由于教材版本不一样有两种结果，本次实验本人采取的新教材的版本，新版本的难度较老教材要大很多，实验时候可以根据具体情况选择一个适合自己的来做。
报告评分：
指导教师签字：
第二篇：短作业优先调度和时间片轮转调度算法
实 验 报 告
学生姓名： 学 号： 指导教师：
一、实验室名称：
二、实验项目名称：进程调度算法的设计
三、实验原理：
短作业（进程）优先调度算法：短作业调度算法是从后备队列中选择一个或者若干个估计运行时间最短的作业，将他们调入内存运行。而短进程优先调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或者发生某事件而被阻塞放弃处理机时再重新调度。
时间片轮转法：系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的队尾；然后，再把处理机分配给就绪队列中的新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一个给定的时间内均能获得一时间片的处理机执行时间。
四、实验目的：
通过对进程调度算法的设计，深入理解进程调度的原理
五、实验内容：
1．编写程序实现SJ（P）F算法
2．编写程序实现RR算法
六、实验器材（设备、元器件）：
装有VC++6.0的PC机一台
七、实验步骤：
1．打开VC，设计编写程序的源代码
2．编译运行程序的源代码
3．分析检验程序的结果是否正确
4．总结实验结果及结论
短进程优先调度源代码：
#include "stdio.h"
struct sjf{
char name[10];
float arrivetime;
float servicetime;
float starttime;
float finishtime;
float zztime;
float dqzztime;
};
sjf a[100];
void input(sjf *p,int N)
{ int i;
printf("intput the process's name & arrivetime & servicetime:\nfor exmple: a 0 100\n"); for(i=0;i<=N-1;i++)
{
printf("input the %dth process's information:\n",i+1);
scanf("%s%f%f",&p[i].name,&p[i].arrivetime,&p[i].servicetime);
}
}
void Print(sjf *p,float arrivetime,float servicetime,float starttime,float finishtime,float zztime,float dqzztime,int N)
{int k;
printf("run order:");
printf("%s",p[0].name);
for(k=1;k<N;k++)
{printf("-->%s",p[k].name);
}
printf("\nthe process's information:\n");
printf("\nname\tarrive\tservice\tstart\tfinish\tzz\tdqzz\n");
for(k=0;k<=N-1;k++)
{ printf("%s\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t\n",p[k].name,p[k].arrivetime,p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime);
}
}
//排序
void sort(sjf *p,int N)
{
for(int i=0;i<=N-1;i++)
for(int j=0;j<=i;j++)
if(p[i].arrivetime<p[j].arrivetime)
{
sjf temp;
temp=p[i];
p[i]=p[j];
p[j]=temp;
}
}
//运行阶段
void deal(sjf *p, float arrivetime,float servicetime,float starttime,float finishtime,float &zztime,float &dqzztime,int N)
{ int k;
for(k=0;k<=N-1;k++)
{
if(k==0)
{
p[k].starttime=p[k].arrivetime;
p[k].finishtime=p[k].arrivetime+p[k].servicetime;}
else
{
p[k].starttime=p[k-1].finishtime;
p[k].finishtime=p[k-1].finishtime+p[k].servicetime;}
}
for(k=0;k<=N-1;k++)
{
p[k].zztime=p[k].finishtime-p[k].arrivetime;
p[k].dqzztime=p[k].zztime/p[k].servicetime;
}
}
void sjff(sjf *p,int N)
{float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0;//对结构进行初始化
sort(p,N);
for(int m=0;m<N-1;m++)
{if(m==0)
p[m].finishtime=p[m].arrivetime+p[m].servicetime;
else
p[m].finishtime=p[m-1].finishtime+p[m].servicetime;
int i=0;
for(int n=m+1;n<=N-1;n++)
{if(p[n].arrivetime<=p[m].finishtime)//判断内存中每次完成之后有多少到达的进程 i++;
}
float min=p[m+1].servicetime;
int next=m+1;//m+1=n
for(int k=m+1;k<m+i;k++) //找出到达后的进程中最小的进程
{
if(p[k+1].servicetime<min)
{min=p[k+1].servicetime;
next=k+1;}
}
sjf temp;
temp=p[m+1];
p[m+1]=p[next];
p[next]=temp;
}
deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);
Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);
}
void main()
{ int N;
printf("------短作业优先调度算法------\n");
printf("input the process's number:\n");
scanf("%d",&N);
input(a,N);
sjf *b=a;
sjf *c=a;
sjff(b,N);
}
时间片轮转法源代码：
#include <stdio.h>
#define M 5 //物理页数
#define
printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n")
typedef struct PCB
{
int ID;
int ReachTime;
int TotalTime;
}PCB; //进程号，到达时间和服务时间
typedef struct NOTE //备份
{ Myprintf
int ID;
int TotalTime;
}NOTE;
PCB A[M]; //5个进程
PCB a[M];
NOTE temp;
int queue[50]; //记录调度的进程 int K=0; //调度进程数组的标识 void INIT()//初始化
{
int i;
for(i=0;i<M;i++)
{
A[i].ID=-1;
}
}
int GetNum()//计算进程数
{
int i,j=0;
for(i=0;i<M;i++)
{
if(A[i].ID!=-1)
{
j++;
}
}
return j;
}
int GetReach(int time)//找出到达进程号 {
int i;
for(i=0;i<M;i++)
{
if(a[i].ReachTime<=time) {
a[i].ReachTime=100; return i;
}
}
return -1;
}
int GetInsert()//找出插入位置 {
int i;
for(i=0;i<M;i++)
{
if(A[i].ID==-1)
return i;
}
return -1;
}
void Forward(int num)//前移
{
int i;
for(i=0;i<num-1;i++)
{
A[i].ID=A[i+1].ID;
A[i].TotalTime=A[i+1].TotalTime; }
A[num-1].ID=-1;
}
void Process()//执行进程
{
queue[K]=A[0].ID;
K++;
A[0].TotalTime--;
temp.ID=A[0].ID;
temp.TotalTime=A[0].TotalTime; }
void main()
{
int i;
int time;
int t=0;
int reach;
int insert;
int num;
printf("RR算法\n\n");
INIT();
for(i=0;i<M;i++)
{
printf("请输入进程ID："); scanf("%d",&a[i].ID);
printf("请输入到达时间："); scanf("%d",&a[i].ReachTime); printf("请输入服务时间："); scanf("%d",&a[i].TotalTime);
} for(i=0;i<M;i++)//运行时间 { t=t+a[i].TotalTime; } for(i=0;i<50;i++)//初始化 { queue[i]=-1; } for(time=0;time<=t;time++) { reach=GetReach(time); if(reach!=-1)//有进程到达 { insert=GetInsert(); A[insert].ID=a[reach].ID; A[insert].TotalTime=a[reach].TotalTime; num=GetNum(); if(num==1) continue;//进程数为1 else { //进程数不为1 Process(); Forward(num); if(temp.TotalTime!=0) { A[num-1].ID=temp.ID; A[num-1].TotalTime=temp.TotalTime; } } } else//没有进程到达 { num=GetNum(); if(num==1) {//进程数为1 Process(); if(temp.TotalTime==0) { A[0].ID=-1; } } else if(num==0)
}
continue;//进程数为0 else { Process(); Forward(num); if(temp.TotalTime!=0) { A[num-1].ID=temp.ID; A[num-1].TotalTime=temp.TotalTime; } } } } printf("\n"); printf("调度顺序为：\n"); Myprintf; for(i=0;i<50;i++) { if(queue[i]!=-1) printf("|%2d ",queue[i]); } printf("|\n"); Myprintf; printf("\n");
八、实验数据及结果分析： 短作业优先调度算法的实验结果：
时间片轮转调度算法结果：
九、实验结论：
本次实验成功的完成了短作业优先调度算法和轮转时间片调度算法的模拟，通过本次实验我们了解到短作业优先调度算法不利于长作业的处理，因为长作业将长期得不到处理，而轮转时间片调度算法则解决了这一问题。短长作业均能在每一个周期内分得一个时间片处理自己的任务。
十、总结及心得体会：
通过本次实验对短作业优先调度算法和时间片轮转调度算法有了更深入的理解，同时，对程序算法能力有了进一步的提高，同时对模块化编程有了更深入得理解，代码的模块化会使程序的代码复用率提高，提高编程的效率。
十一、对本实验过程及方法、手段的改进建议：
本次实验的时间片轮转调度算法由于教材版本不一样有两种结果，本次实验本人采取的新教材的版本，新版本的难度较老教材要大很多，实验时候可以根据具体情况选择一个适合自己的来做。
报告评分： 指导教师签字：
-
时间片轮转调度算法实验报告
实验报告说明1实验项目名称要用最简练的语言反映实验的内容要求与实验指导书中相一致2实验类型一般需说明是验证型实验还是设计型实验是创…
-
操作系统实验报告——时间片调度轮转算法
操作系统实验报告第一次实验时间片调度轮转算法实验时间20xx117院系计算机科学与技术学院班级软件2班实验要求1实验选题时间片调度…
-
操作系统实验报告 时间片轮转调度算法
网络协议分析实验4实验名称用Ethereal研究DNS和HTTP协议实验目的通过对捕获分组的分析和研究加深对DNS协议和HTTP协…
-
操作系统实验二报告-时间片轮转进程调度算法
操作系统实验报告实验二时间片轮转进程调度算法学号班级姓名实验题目时间片轮转进程调度算法实验目的通过这次实验加深对进程概念的理解进一…
-
优先数和轮转法进程调度实验报告
实验二进程调度报告一基本信息123实验题目进程调度完成人报告日期二实验内容简要描述1实验目标进程调度是处理机管理的核心内容本实验要…
-
优先数和轮转法进程调度实验报告
实验二进程调度报告一基本信息123实验题目进程调度完成人报告日期二实验内容简要描述1实验目标进程调度是处理机管理的核心内容本实验要…
-
时间片轮转调度算法实验报告
实验报告说明1实验项目名称要用最简练的语言反映实验的内容要求与实验指导书中相一致2实验类型一般需说明是验证型实验还是设计型实验是创…
-
操作系统实验报告——时间片调度轮转算法
操作系统实验报告第一次实验时间片调度轮转算法实验时间20xx117院系计算机科学与技术学院班级软件2班实验要求1实验选题时间片调度…
-
操作系统实验报告 时间片轮转调度算法
网络协议分析实验4实验名称用Ethereal研究DNS和HTTP协议实验目的通过对捕获分组的分析和研究加深对DNS协议和HTTP协…
-
操作系统实验二报告-时间片轮转进程调度算法
操作系统实验报告实验二时间片轮转进程调度算法学号班级姓名实验题目时间片轮转进程调度算法实验目的通过这次实验加深对进程概念的理解进一…