进程调度算法（FCFS、SJF、高响应比）
一、算法描述
1.先来先服务（FCFS）调度算法
（1）FCFS是最简单的调度算法，该算法可用于作业调度，也可用于进程调度。
（2）算法规则：系统按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行时间的长短，从后备队列中选择几个最先进入该队列的作业，将它们调入内存，为他们分配资源和创建进程。然后把它放入就绪队列。
（3）该算法属于非抢占式的。
（4）算法优缺点：对长作业友好，对短作业不友好。
（5）是否会导致饥饿现象：不会导致饥饿现象。
2.短作业优先（SJF）调度算法
（1）在实际情况中，短作业（进程）占有很大比例，为了能使它们能比长作业优先执行，而产生了短作业优先调度算法。
（2）算法规则：SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。可分别用于作业调度和进程调度，在把短作业优先调度算法用于调度算法时，它将从外存的后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存运行。
（3）该算法有抢占式和非抢占式，未说明则默认为非抢占式。
（4）算法优缺点：优点是要求最短的平均等待时间，平均周转时间。缺点是对长作业不友好，会使长作业一直排队。
（5）是否会导致饥饿现象：会导致饥饿现象。
3.高响应比优先（HRRN）调度算法
静态优先级：事先定义好，优先级不可以改变。
动态优先级：随着进程的推进，改变优先级。
（1）优先级调度算法是既考虑了作业的等待时间，又考虑了作业运行时间的调度算法，因此既顾了短作业，又不致使长作业的等待时间过长，从而改善了处理机调度的性能。
（2）算法规则：，由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先级又相当于响应比Rp,据此，优先级又可以表示为
（3）该算法有抢占式和非抢占式，未说明则默认为非抢占式。
（4）算法优缺点：优点是兼顾了长短作业，缺点是做响应比计算，增加了系统开销。
（5）是否会导致饥饿现象：不会导致饥饿现象。
二、代码实现
1.先来先服务（FCFS）调度算法
#include<iostream>
#include<string>
#include<fstream>
#include<iomanip>
using namespace std;
const int MAXN = 100000;
int tasknum;//作业数量
int nowtime; //从第一个到达的作业时间开始
double avgruntime; //平均周转时间
double avgdqzztime; //平均带权周转时间
struct StruTask
{
int id; //序号
int flag=0;
int arrive; //到达时间（输入）
int service; //服务时间（输入）
int start; //开始时间（设置）
int endtime; //结束时间（设置）
int runtime; //周转时间:endtime - arrive
double dqzztime; //带权周转时间runtime/service
}arrayTask[MAXN];
void GetTask()
{
cout<<"请输入任务数:"<<endl;
cin>>tasknum;
if(tasknum <= 0) return;
for(int i = 1; i <= tasknum; ++i)
{
cout<<"请输入第"<<i<<"个任务的到达时间和服务时间: ";
arrayTask[i].id = i;
cin>>arrayTask[i].arrive;
cin>>arrayTask[i].service;
}
}
int GetNextTask(int now)
{
int minx=100000,index=-1;
for(int i=1; i<=tasknum; i++)
if(!arrayTask[i].flag&&arrayTask[i].arrive<=now&&arrayTask[i].arrive<mi)
{
minx=arrayTask[i].arrive;
index=i;
}
//struTask minda=arrayTask[index_];
//arrayTask[index_]=arrayTask[k];
//arrayTask[k]=minda;
return index;
}
void RunTask(int n)
{
arrayTask[n].start = nowtime;
arrayTask[n].endtime = nowtime + arrayTask[n].service;
arrayTask[n].runtime = arrayTask[n].endtime - arrayTask[n].arrive;
avgruntime += arrayTask[n].runtime;
arrayTask[n].dqzztime = arrayTask[n].runtime / arrayTask[n].service;
avgdqzztime += arrayTask[n].dqzztime;
arrayTask[n].flag=1;
}
void PrintResult(int n)
{
cout<<" 序号: "<<arrayTask[n].id
<<" 到达时间: "<<arrayTask[n].arrive<<" 服务时间: "<<arrayTask[n].service;
cout<<" 开始时间: "<<arrayTask[n].runtime<<" 结束时间: "<<arrayTask[n].endtime;
cout<<" 周转时间: "<<arrayTask[n].runtime<<" 带权周转时间: "<<arrayTask[n].dqzztime<<endl;
}
int main()
{
GetTask();
nowtime = 0;
avgruntime = 0;
avgdqzztime = 0;
for(int i = 1; i <= tasknum; ++i)
{
int id = GetNextTask(nowtime);
RunTask(id);
PrintResult(id);
nowtime=arrayTask[id].endtime;
}
avgruntime /= tasknum;
avgdqzztime /= tasknum;
cout<<" 平均周转时间: "<<avgruntime<<" 平均带权周转时间: "<<avgdqzztime<<endl;
return 0;
}
2.短作业优先（SJF）调度算法
#include <iostream>
using namespace std;
const int MAXN = 100000;
int tasknum;
int nowtime; //从第一个到达的作业时间开始
double avgruntime; //平均周转时间
double avgdqzztime; //平均带权周转时间
struct StruTask
{
int id; //序号
int arrive; //到达时间（输入）
int service; //服务时间（输入）
int start; //开始时间（设置）
int endtime; //结束时间（设置）
int runtime; //周转时间:endtime - arrive
double dqzztime; //带权周转时间runtime/service
bool finished;
} arrayTask[MAXN];
int GetTask()
{
cout<<"请输入任务数:"<<endl;
cin>>tasknum;
if(tasknum <= 0) return -1;
int minx = 100000;
for(int i = 1; i <= tasknum; i++)
{
cout<<"请输入第"<<i<<"个任务的到达时间和服务时间:";
arrayTask[i].id = i;
cin>>arrayTask[i].arrive;
minx = min(minx,arrayTask[i].arrive);
cin>>arrayTask[i].service;
}
return minx;
}
int GetNextTask()
{
int minx = 100000;
int aim = 0;
for(int i = 1; i <= tasknum; i++)
{
if(arrayTask[i].arrive<=nowtime && !arrayTask[i].finished)
{
if(arrayTask[i].service < minx)
{
minx = arrayTask[i].service;
aim = i;
}
}
}
return aim;
}
void RunTask(StruTask &task)
{
nowtime = max(nowtime,task.arrive);
task.start = nowtime;//nowtime前一任务运行，后一任务开始运行时间
task.endtime = nowtime + task.service;//完成时间=当前时间+服务时间
nowtime = task.endtime;//当前时间=该任务完成时间
task.runtime = task.endtime - task.arrive;//周转时间=完成时间-到达时间
avgruntime += task.runtime;
task.dqzztime = task.runtime / task.service;//带权周转时间=周转时间/服务时间
avgdqzztime += task.dqzztime;
task.finished = true;
}
void PrintResult(StruTask &task)
{
cout<<" 序号: "<<task.id
<<" 到达时间: "<<task.arrive<<" 服务时间: "<<task.service;
cout<<" 开始时间: "<<task.start<<" 结束时间: "<<task.endtime;
cout<<" 周转时间: "<<task.runtime<<" 带权周转时间: "<<task.dqzztime<<endl;
}
/*SJF 非抢占式
Short Job First
*/
int main()
{
nowtime = GetTask();
avgruntime = 0;
avgdqzztime = 0;
if(nowtime == -1)
return 0;
for(int i = 1; i <= tasknum; i++)
{
int id = GetNextTask();
RunTask(arrayTask[id]);
PrintResult(arrayTask[id]);
}
avgruntime /= tasknum;
avgdqzztime /= tasknum;
cout<<" 平均周转时间: "<<avgruntime<<" 平均带权周转时间: "<<avgdqzztime<<endl;
return 0;
}
3,高响应比优先（HRRN）调度算法
#include <iostream>
using namespace std;
const int MAXN = 100000;
int tasknum;
int nowtime; //从第一个到达的作业时间开始
double avgruntime; //平均周转时间
double avgdqzztime; //平均带权周转时间
struct StruTask
{
int id; //序号
int flag=0;
int arrive; //到达时间（输入）
int service; //服务时间（输入）
int start; //开始时间（设置）
int endtime; //结束时间（设置）
int runtime; //周转时间:endtime - arrive
double dqzztime; //带权周转时间runtime/service
bool finished;
} arrayTask[MAXN];
int GetTask()
{
cout<<"请输入任务数:"<<endl;
cin>>tasknum;
if(tasknum <= 0) return -1;
int minx = 100000;
for(int i = 1; i <= tasknum; i++)
{
cout<<"请输入第"<<i<<"个任务的到达时间和服务时间:";
arrayTask[i].id = i;
cin>>arrayTask[i].arrive;
minx = min(minx,arrayTask[i].arrive);
cin>>arrayTask[i].service;
}
return minx;
}
int GetNextTask(int now)
{
int minx=100000,index=-1;
for(int i=1; i<=tasknum; i++)
if(!arrayTask[i].flag&&arrayTask[i].arrive<=now&&arrayTask[i].arrive<minx)
{
minx=arrayTask[i].arrive;
index=i;
}
return index;
}
int GetNextTask1(int now)
{
int dim = 0;
int minx=100000;
for(int i = 1; i <= tasknum; i++)
{
if(!arrayTask[i].flag&&arrayTask[i].arrive<=now&&arrayTask[i].service<minx)//服务时间最短的进程
{
minx = arrayTask[i].service;
dim = i;
}
}
return dim;
}
int GetNextTask2(int now)
{
double a=0,minx=0;
int gim=0;
for(int i=1;i<=tasknum;i++)
{
if(!arrayTask[i].flag&&arrayTask[i].arrive<=now)//计算还没开始运行但已经到达的进程的响应比
{
a=(now-arrayTask[i].arrive+arrayTask[i].service)/(double)arrayTask[i].service;
if(a>minx)
{
minx=a;
gim=i;
}
}
}
return gim;
}
void RunTask(StruTask &task)
{
nowtime = max(nowtime,task.arrive);
task.start = nowtime;//nowtime前一任务运行，后一任务开始运行时间
task.endtime = nowtime + task.service;//完成时间=当前时间+服务时间
nowtime = task.endtime;//当前时间=该任务完成时间
task.runtime = task.endtime - task.arrive;//周转时间=完成时间-到达时间
avgruntime += task.runtime;
task.dqzztime = task.runtime / task.service;//带权周转时间=周转时间/服务时间
avgdqzztime += task.dqzztime;
task.finished = true;
}
void PrintResult(StruTask &task)
{
cout<<" 序号: "<<task.id
<<" 到达时间: "<<task.arrive<<" 服务时间: "<<task.service;
cout<<" 开始时间: "<<task.start<<" 结束时间: "<<task.endtime;
cout<<" 周转时间: "<<task.runtime<<" 带权周转时间: "<<task.dqzztime<<endl;
}
/*SJF 非抢占式
Short Job First
*/
int main()
{
GetTask();
nowtime = 0;
avgruntime = 0;
avgdqzztime = 0;
cout<<"先来先服务："<<endl;
for(int i = 1; i <= tasknum; ++i)
{
int id = GetNextTask(nowtime);
RunTask(arrayTask[id]);
PrintResult(arrayTask[id]);
nowtime=arrayTask[id].endtime;
}
avgruntime /= tasknum;
avgdqzztime /= tasknum;
cout<<" 平均周转时间: "<<avgruntime<<" 平均带权周转时间: "<<avgdqzztime<<endl;
return 0;
}
三、实验结果
1.先来先服务（FCFS）调度算法
2.短作业优先（SJF）调度算法
3.高响应比优先（HRRN）调度算法
四、实验心得
通过本次实验，我深刻的理解了操作系统中作业资源的分配方式和作业的调度方式及相关的3种算法。操作系统实验重在理解每一个算法的意图和目的，那么就选择适当的数据结构模拟过程就可以完成相关算法了。先来先服务的作业调度，实现最简单。最高响应比优先作业调度，既照顾了短作业，又照顾了作业到来的顺序，不会使长作业长期得不到运行，但是每次调度下一个作业前要计算剩余到来作业的响应比，增加了系统的开销。开始时对作业调度不是很那么地清晰，通过做这个实验，现在对操作系统的作业调度有了清晰的理解，感觉在这个过程中自己就是充当了调度员的角色。