一、先来先服务算法
1．程序简介
先来先服务算法按照作业进入系统后备作业队列的先后次序挑选作业,先进入系统的作业将优先被挑选进入主存,创建用户进程,分配所需资源,然后,移入就绪队列.这是一种非剥夺式调度算法,易于实现,但效率不高.只顾及作业的等候时间,未考虑作业要求服务时间的长短,不利于短作业而优待长作业,不利于I/O繁忙型作业而有利于CPU繁忙型作业.有时为了等待场作业执行结束,短作业的周转时间和带全周转时间将变得很大,从而若干作业的平均周转时间和平均带权周转时间也变得很大。
2．分析
1．先定义一个数组代表各作业运行的时间，再定义一个数组代表各作业到达系统的时间，注意到达系统的时间以第一个作业为0基础（注意：若各程序都同时到达系统，则到达系统时间都为0）。
2．输入作业数。
3．然后运用循环结构累积作业周转时间和带权周转时间。
4．最后，作业周转时间和带权周转时间分别除以作业数即可得到平均作业周转时间和平均带权周转时间。
3．详细设计
源程序如下：
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int n,a[100],b[100];
double s[100],m[100],T=0,W=0;
cout<<"请输入作业数:"<<endl;
cin>>n;
cout<<"请分别输入各作业到达系统的时间:"<<endl;
for(int i=0;i<n;i++)
{
cin>>b[i];
}
cout<<"请分别输入各作业所运行的时间:"<<endl;
for(i=0;i<n;i++)
{
cin>>a[i];s[0]=0;
s[i+1]=s[i]+a[i];
m[i+1]=(s[i+1]-b[i])/a[i];
T=T+s[i+1]-b[i];
W=W+m[i+1];
}
cout<<"平均周转时间为:"<<T/n<<endl;
cout<<"平均带权周转时间为:"<<W/n<<endl;
return 0;
}
4．运行与测试
1．运行程序，输入作业数，如A.1所示。
A1 启动界面
2．输入各作业到达系统的时间，如A.2所示。
A2 输入各作业到达系统的时间
3．输入各作业所运行的时间，如A.3所示。
A3 输入各作业运行的时间
二、最短作业优先算法
1. 程序简介
最短作业优先算法以进入系统的作业所要求的CPU运行时间的长短为标准，总是选取预计计算时间最短的作业投入运行。
这是一种非剥夺式调度算法，能克服FCFS算法偏爱长作业的缺点，易于实现，但执行效率也不高。
2. 分析
1. 分两种情况来介绍这种算法，一是各作业到达系统的时间都相同，二是各作业到达系统的时间不同，且以第一个作业到达系统的时间为0作基础。
2. 到达系统时间都相同的情况只要累积CPU运行的时间，最后加一个排序函数即可。
3. 到达系统时间不相同的情况则是要在前面FCFS的基础上加一个排序函数即可。
4. 注意本程序认为第一个作业完成后，其它作业都已经到达系统了。
3. 详细设计
源程序如下：
//SJF(到达系统时间都相同的情况）
#include<iostream>
using namespace std;
void B(float a[],int size)
{
float t;
for(int i=1;i<size;i++)
{
for(int j=0;j<size-1;j++)
if(a[j]>a[j+1])
{
t=a[j];a[j]=a[j+1];a[j+1]=t;}
}
}
int main(void)
{
float n,a[100];
double s[100],m[100],T=0,W=0;
cout<<"请输入作业数:"<<endl;
cin>>n;
cout<<"请分别输入各作业所运行的时间:"<<endl;
for(int i=0;i<n;i++)
cin>>a[i];
B(a,n);
cout<<"作业调度顺序为:"<<endl;
for(i=0;i<n;i++)
{
cout<<a[i]<<" ";
s[0]=0;
s[i+1]=s[i]+a[i];
m[i+1]=s[i+1]/a[i];
T=T+s[i+1];
W=W+m[i+1];
}cout<<endl;
cout<<"平均周转时间为:"<<T/n<<endl;
cout<<"平均带权周转时间为:"<<W/n<<endl;
return 0;
}
//SJF(到达系统时间不相同的情况）
#include<iostream>
using namespace std;
void B(float a[],int size)
{
float t;
for(int i=2;i<size;i++)
{
for(int j=1;j<size-1;j++)
if(a[j]>a[j+1])
{
t=a[j];a[j]=a[j+1];a[j+1]=t;}
}
}
int main(void)
{
float n,a[100],b[100];
double s[100],m[100],T=0,W=0;
cout<<"请输入作业数:"<<endl;
cin>>n;
cout<<"请分别输入各作业所运行的时间:"<<endl;
for(int i=0;i<n;i++)
cin>>a[i];
B(a,n);
cout<<"作业调度顺序为:"<<endl;
for(i=0;i<n;i++)
{
cout<<a[i]<<" ";
}cout<<endl;
cout<<"请分别输入各作业到达系统的时间:"<<endl;
for(i=0;i<n;i++)
{
cin>>b[i];
}
for(i=0;i<n;i++)
{
s[0]=0;
s[i+1]=s[i]+a[i];
m[i+1]=(s[i+1]-b[i])/a[i];
T=T+s[i+1]-b[i];
W=W+m[i+1];
}
cout<<"平均周转时间为:"<<T/n<<endl;
cout<<"平均带权周转时间为:"<<W/n<<endl;
return 0;
}
4．运行与测试
//SJF(到达系统时间都相同的情况）
1. 运行程序，输入作业数，如A.1所示。
A1 启动界面
2. 输入各作业所运行的时间，如A.2所示。
A2 输入各作业所运行的时间
//SJF(到达系统时间不相同的情况）
1. 运行程序，输入作业数，如A.1所示。
A1 启动界面
2. 输入各作业所运行的时间，如A.2所示。
A2 输入各作业所运行的时间
3. 输入各作业到达系统的时间，如A.3所示。
A3 输入各作业到达系统的时间
三、优先级调度算法
1．程序简介
优先级调度算法根据确定的优先级来选取进程/线程，总是选择就绪队列中的优先级最高者投入运行。
本实验介绍的是非剥夺式优先级调度算法，如果在就绪队列中出现优先级更高的就让当前进程/线程继续运行，直到它结束或出现等待事件而主动让出处理器，再调度另一个优先级高的进程/线程运行。
2. 分析
1. 先定义一个二维数组a[i][0]代表各作业的优先级，a[i][1]代表各作业运行的时间。
2. 输入作业数。
3. 根据排序函数得出作业调度顺序。
4. 最后，累积得作业周转时间和带权周转时间后分别除以作业数即可得到平均作业周转时间和平均带权周转时间。
3. 详细设计
源程序如下：
#include<iostream>
using namespace std;
void B(float a[][2],int size)
{
float t,p;
for(int i=0;i<size;i++)
{
for(int j=0;j<size-1;j++)
if(a[j][0]>a[j+1][0])
{
t=a[j][0];a[j][0]=a[j+1][0];a[j+1][0]=t;
p=a[j][1];a[j][1]=a[j+1][1];a[j+1][1]=p;
}
}
}
int main(void)
{
float n,a[100][2];
double s[100][2],m[100][2],T=0,W=0;
cout<<"请输入作业数:"<<endl;
cin>>n;
cout<<"请分别输入各作业优先级和所运行的时间:"<<endl;
for(int i=0;i<n;i++)
{
cin>>a[i][0]>>a[i][1];
}B(a,n);
cout<<"作业调度顺序为:"<<endl;
for(i=0;i<n;i++)
{
cout<<a[i][0]<<a[i][1]<<" ";
s[0][1]=0;
s[i+1][1]=s[i][1]+a[i][1];
m[i+1][1]=s[i+1][1]/a[i][1];
T=T+s[i+1][1];
W=W+m[i+1][1];
}cout<<endl;
cout<<"平均周转时间为:"<<T/n<<endl;
cout<<"平均带权周转时间为:"<<W/n<<endl;
return 0;
}
4. 运行与测试
1. 运行程序，输入作业数，如A.1所示。
A1 启动界面
2．输入各作业优先级和所运行的时间，如A.2所示。
A2 输入各作业的优先级和所运行的时间
四、响应比最高者优先算法
1. 程序简介
响应比最高者优先算法是介乎这两种算法之间的一种折中的非剥夺式算法，既考虑作业的等待时间，又考虑作业的处理时间，这样既照顾短作业又不会使长作业的等待时间过长，有效地改进调度的性能。
HRRF算法的缺点是每次计算各道作业的响应比会导致一定时间的开销，其性能比SJF算法略差。
2. 分析
1. 先定义一个二维数组a[i][0]代表各作业的等待时间，a[i][1]代表各作业运行的时间，a[i][2]代表响应比-1。
2. 输入作业数。
3. 根据排序函数得出作业调度顺序。
4. 最后，累积得作业周转时间和带权周转时间后分别除以作业数即可得到平均作业周转时间和平均带权周转时间。
3. 详细设计
源程序如下：
#include<iostream>
using namespace std;
void B(double a[][3],int size)
{
double t,p,s;
for(int i=2;i<size;i++)
{
for(int j=1;j<size-1;j++)
if(a[j][2]<a[j+1][2])
{
s=a[j][2];a[j][2]=a[j+1][2];a[j+1][2]=s;
t=a[j][0];a[j][0]=a[j+1][0];a[j+1][0]=t;
p=a[j][1];a[j][1]=a[j+1][1];a[j+1][1]=p;
}
}
}
int main(void)
{
double n,a[100][3],s[100][3],m[100][3],T=0,W=0;
cout<<"请输入作业数:"<<endl;
cin>>n;
cout<<"请分别输入各作业等待时间和所运行的时间:"<<endl;
for(int i=0;i<n;i++)
{
cin>>a[i][0]>>a[i][1];
}
for(i=1;i<n;i++)
{
a[i][2]=(a[0][1]-a[i][0])/a[i][1];
}
B(a,n);
cout<<"作业调度顺序为:"<<endl;
for(i=0;i<n;i++)
{
cout<<a[i][0]<<a[i][1]<<" ";
s[0][1]=0;
s[i+1][1]=s[i][1]+a[i][1];
m[i+1][1]=(s[i+1][1]-a[i][0])/a[i][1];
T=T+s[i+1][1]-a[i][0];
W=W+m[i+1][1];
}cout<<endl;
cout<<"平均周转时间为:"<<T/n<<endl;
cout<<"平均带权周转时间为:"<<W/n<<endl;
return 0;
}
4. 运行与测试
1. 运行程序，输入作业数，如A.1所示。
A1 启动界面
3．输入各作业等待时间和所运行的时间，如A.2所示。
A2 输入各作业等待时间和所运行的时间。
