算法描述:
短作业(进程)优先调度算法(SJF),是指对短作业或短进程优先调度的算法。它们可以分 别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个 估计运行时间最短的作业,将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队 列中选出一个估计运行时间最短的进程,将处理机分配给它,使它立即执行并一直执行到完 成,或发生某事件而被阻塞放弃处理机时再重新调度
代码:
#include <iostream>
#include<iomanip>
#include<queue>
#include<list>
#include<algorithm>
using namespace std;
class PCB
{
public:
int pid;
int arrivalTime;
int needTime;
int leaveTime;
PCB()
{
}
PCB(int pid,int arriveTime,int needTime)
{
this->pid=pid;
this->arrivalTime=arriveTime;
this->needTime=needTime;
leaveTime=0;
}
bool operator < (const PCB &a)const
{
return needTime>a.needTime;
}
bool operator == (const PCB &a)const
{
//// if(pid==a.pid){
//// return true;
//// }
//// else
//// return false;
return pid==a.pid?true:false;
}
};
class SJF
{
public:
priority_queue<PCB> pq;
list<PCB> allNeedList;
list<PCB> allFinishList;
void prepareProcess(int pid,int arriveTime,int needTime);
void schedule();
void printFinishList();
};
void SJF::schedule()
{
int currentTime=0,finishTime=-1;
bool isBusy=false;
PCB currentProcess;
while (true)
{
if(currentTime==finishTime) //这里是每秒都做。currentTime++,故==
{
isBusy=false;
currentProcess.leaveTime=currentTime;
allFinishList.push_back(currentProcess);
cout<<"已结束 ";
cout<<"周转时间:"<<finishTime-currentProcess.arrivalTime;
cout<<"带权周转时间:"<<(finishTime-currentProcess.arrivalTime)/(double)currentProcess.needTime<<endl;
}
//从链表中把到达的进程假如有先队列
for(list<PCB>::iterator i=allNeedList.begin(); i!=allNeedList.end();)
{
if((*i).arrivalTime<=currentTime)
{
pq.push(*i);
allNeedList.erase(i++);
}
else
{
i++;
}
}
if(!isBusy&&!pq.empty())
{
currentProcess=pq.top();
pq.pop();
finishTime=currentProcess.needTime+currentTime;
isBusy=true;
cout<<"进程"<<currentProcess.pid<<"开始占用处理机,到达时间:"<<currentProcess.arrivalTime<<",需要时间:"<<currentProcess.needTime<<",开始时间:"<<currentTime<<"\n";
}
currentTime++;
//最后所有进程结束,退出
if(allNeedList.empty()&&pq.empty()&&!isBusy)
break;
}
}
void SJF::prepareProcess(int pid,int arriveTime,int needTime)
{
PCB newProcess(pid,arriveTime,needTime);
allNeedList.push_back(newProcess);
}
void SJF::printFinishList()
{
allFinishList.sort();
setiosflags(ios::left);
cout<<setw(15)<<"进程"<<setw(15)<<"到达时间"<<setw(15)<<"服务时间"<<setw(15)<<"周转时间"<<setw(15)<<"带权周转时间\n";
for (list<PCB>::iterator i=allFinishList.begin(); i!=allFinishList.end(); i++)
{
cout<<setw(15)<<(*i).pid<<setw(15)<<(*i).arrivalTime<<setw(15)<<(*i).needTime<<setw(15)<<(*i).leaveTime-(*i).arrivalTime<<setw(15)<<((*i).leaveTime-(*i).arrivalTime)/(double)(*i).needTime<<"\n";
}
}
int main()
{
SJF one;
// one.prepareProcess(1,1,4);
// one.prepareProcess(2,2,3);
// one.prepareProcess(3,3,7);
// one.prepareProcess(4,4,2);
// one.prepareProcess(5,5,1);
// one.prepareProcess(6,6,4);
// one.prepareProcess(7,7,2);
// one.prepareProcess(8,8,2);
one.prepareProcess(1,2,4);
one.prepareProcess(2,2,3);
one.prepareProcess(3,1,7);
one.prepareProcess(4,4,2);
one.prepareProcess(5,6,1);
one.prepareProcess(6,8,4);
one.prepareProcess(7,11,2);
one.prepareProcess(8,13,2);
one.schedule();
one.printFinishList();
return 0;
}
注意事项
1.将程序信息使用PCB的类存储,接近操作系统工作原理
2.程序写的比较顺,但是对基本的语法有些不熟,比如stl中的priority_queue,list。优先队列是从大到小排列,要从小到大排列故重载<运算符,用erase函数,故重载==运算符
3.#include<iomanip> setw \n不一样
网友评论