首页 > > 程序设计 > C/C++ >

模拟处理机作业调度---短作业优先调度算法

2018-06-18 03:48:47来源：未知阅读 ()

短作业优先调度原理

短作业优先调度算法是指对短作业优先调度的算法。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。

算法流程图

JCB 代表一个作业，JCB 的结构如下：

模拟实现

在屏幕上输出以下作业状态表：

可以通过键盘命令动态地增加作业（即增加一个 JCB 数据结构项）。增加作业后，作业状态表内容可更新查看。

算法代码：

#include "stdafx.h"
#include<iostream>
#include <iomanip>
#include<queue>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;

/*作业的数据结构*/
struct JCB
{
    int ID;//作业ID
    double in_time;//作业进入时间
    double ex_time;//作业执行时间
};
/*执行时间大到下排序*/
bool cmp(pair<JCB, double> first, pair<JCB, double> next)
{
    return first.second > next.second;
}
/*ID从小到大排序*/
bool cmp2(pair<JCB, double> first, pair<JCB, double> next)
{
    return first.first.ID < next.first.ID;
}
/*开始执行时间从早到晚排序*/
bool cmp3(pair<JCB, double> first, pair<JCB, double> next)
{
    return first.second < next.second;
}
/*ID从大到小排序*/
bool cmp4(pair<JCB, double> first, pair<JCB, double> next)
{
    return first.first.ID > next.first.ID;
}

/*显示作业表格*/
void ShowJobChart(vector<pair<JCB, double>>res)
{
    cout<<left;
    cout << "--------------------------------作业状态表-------------------------------------"<<endl;
    cout << setw(10) << "作业ID" << "|"<< setw(10) << "到达时间" << "|" << setw(10) << "执行时间"<<"|" << setw(10) << "开始时间" << "|" <<
        setw(10) << "完成时间" << "|" << setw(10) << "周转时间" << "|" << setw(12) << "带权周转时间" <<"|"<< endl;
    cout << "-------------------------------------------------------------------------------" << endl;
    for (auto it = res.begin();it != res.end();it++)
    {
        cout << setw(10) << it->first.ID << "|" << setw(10) <<it->first.in_time<<"|" << setw(10) << it->first.ex_time << "|" << setw(10) <<it->second<<"|"
            << setw(10) <<it->second+it->first.ex_time<<"|" << setw(10) <<
            it->second + it->first.ex_time -it->first.in_time<< "|"<< setw(12)<< (it->second + it->first.ex_time - it->first.in_time)/it->first.ex_time<<"|"<<endl;
    }
    cout << "-------------------------------------------------------------------------------" << endl;
}
/*作业调度                                       */
/*输入：待调度的作业队列jobs                     */
/*输出：调度好的作业数组res                         */
vector<pair<JCB, double>> JobScheduling(queue<JCB>jobs)
{
    JCB f_job = jobs.front();
    jobs.pop();
    //res数组用于存调度之后的结果，jcb以及对应的作业开始执行时间
    vector<pair<JCB, double>>res;
    //首先将第一个到达的工作直接加入数组
    res.push_back(make_pair(f_job, f_job.in_time));
    vector<pair<JCB, double>>job;
    double finish = f_job.in_time + f_job.ex_time;
    while (!jobs.empty())
    {
        //将到达时间在上一个执行的工作结束时间之前的作业存入job数组
        while (jobs.front().in_time <= finish)
        {
            job.push_back(make_pair(jobs.front(), jobs.front().ex_time));
            jobs.pop();
            if (jobs.empty())break;
        }
        //如果没有到达时间在上一个执行的工作结束时间之前的作业
        if (job.empty())
        {
            res.push_back(make_pair(jobs.front(), jobs.front().in_time));
            finish = jobs.front().in_time + jobs.front().ex_time;
            jobs.pop();
            continue;
        }
        //将到达时间在上一个执行的工作结束时间之前的作业按执行时间从大到小排序
        sort(job.begin(), job.end(), cmp);
        //将最短执行时间的工作存进结果数组
        res.push_back(make_pair(job.rbegin()->first, finish));
        //更新结束时间
        finish += job.rbegin()->second;
        job.pop_back();
    }
    //如果后面几个进入的作业都在上一个执行的作业结束之前进入
        while(!job.empty())
        {
            res.push_back(make_pair(job.rbegin()->first, finish));
            finish += job.rbegin()->second;
            job.pop_back();
        }
        sort(res.begin(), res.end(),cmp2);
        return res;    
}

/*添加作业                                        */
/*输入：待添加的作业job，以及调度好的作业数组res*/
/*输出：添加作业之后的作业数组res               */
vector<pair<JCB, double>> Addjob(JCB job,vector<pair<JCB, double>>res)
{
    double tmp=job.in_time;
    vector<pair<JCB, double>>t_job;
    vector<pair<JCB, double>>res2;
    sort(res.begin(), res.end(), cmp3);
    if (job.in_time > res.rbegin()->second)//如果作业的进入时间比最后执行作业的执行时间还晚
    {
        res.push_back(make_pair(job, job.in_time));
        return res;
    }
    //将作业的执行时间从早到晚排序，将执行时间晚于作业进入时间的作业加入数组并
    //确定第一个执行的作业之后，重新调用作业调度函数
    queue<JCB>jobs;
    for (auto it = res.begin();it != res.end();it++)
    {
        //比较待添加的作业的进入时间和已经调度好的作业的开始执行时间
        //和待添加的作业的执行时间和已经调度好的作业的执行时间
        if (job.in_time > it->second||job.ex_time>=it->first.ex_time)continue;
        else
        {
            job.in_time = it->second;
            jobs.push(job);
            sort(it, res.end(), cmp4);
            for (auto it2 = res.end() - 1;it2 > it;)
            {
                jobs.push(it2->first);
                it2--;
                res.pop_back();
            }
            jobs.push(it->first);
            it--;
            res.pop_back();
            break;
        }
    }
    //重新调用作业调度函数
    res2=JobScheduling(jobs);
    res2.begin()->first.in_time = tmp;
    //将重新调度好的作业与不参与调度的作业连接
    res.insert(res.end(), res2.begin(), res2.end());
    sort(res.begin(), res.end(), cmp2);
    return res;
}
int main()
{
    queue<JCB>jobs;
    JCB job1, job2, job3, job4,job5;
    //初始作业队列
    job1 = { 1,8.00,2 };
    jobs.push(job1);
    job2 = { 2,8.50,0.50 };
    jobs.push(job2);
    job3 = { 3,9.00,0.10 };
    jobs.push(job3);
    job4 = { 4,11.60,0.20 };
    jobs.push(job4);

    //调用作业调度函数
    vector<pair<JCB, double>> res=JobScheduling(jobs);
    //输出作业状态表
    ShowJobChart(res);
    char i ;
    cout << "添加作业?(y/n):";
    cin >> i;
    while (i-'y'==0)
    {
        JCB job;
        cout << "请输入作业ID：";
        cin >> job.ID;
        cout << "请输入作业进入时间：";
        cin >> job.in_time;
        cout << "请输入作业执行时间：";
        cin >> job.ex_time;
        //添加作业
        vector<pair<JCB, double>> res = Addjob(job, JobScheduling(jobs));
        ShowJobChart(res);
        cout << "继续添加作业?(y/n):";
        cin >> i;
    }
}