美文网首页
操作系统:C++实现SJF(短作业优先调度算法)

操作系统:C++实现SJF(短作业优先调度算法)

作者: mztkenan | 来源:发表于2017-04-30 21:09 被阅读470次

    算法描述:

    短作业(进程)优先调度算法(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不一样

    相关文章

      网友评论

          本文标题:操作系统:C++实现SJF(短作业优先调度算法)

          本文链接:https://www.haomeiwen.com/subject/sibxtxtx.html