[操作系统]作业调度

题目描述

1、假设系统中可同时运行两道作业，给出每道作业的到达时间和运行时间，如下表所示：

作业名	A	B	C	D	E	F	G	H	I	J
到达时间	0	2	5	7	12	15	4	6	8	10
运行时间	7	10	20	30	40	8	8	20	10	12

2、分别用先来先服务算法、短作业优先和响应比高者优先三种算法给出作业的调度顺序。

3、计算每一种算法的平均周转时间及平均带权周转时间并比较不同算法的优劣。

(注：①响应比=等待时间/运行时间+1；②周转时间=完成时间-到达时间；③带权周转时间=周转时间/运行时间。)

程序功能及设计思路

程序功能：

程序获取一批作业后，每个作业都记录了作业名、到达时间以及运行时间。用户可以选择先来先服务算法、短作业优先和响应比优先三种算法的一种算法进行作业调度，程序中的系统一次可以同时运行两道作业，程序根据用户选择的算法输出作业的调度顺序及每个作业完成的时间、平均周转时间和平均带权周转时间。

设计思路：

主要是三个算法的设计以及同时运行两道作业的处理方法。

由于系统可以同时处理两道作业，因此不能简单地一个作业一个作业的计算，可以用时间片的方法来处理，程序计算过程中按照时钟一个时间单元一个时间单元的走。在每个时间单元结束时进行判断处理，时钟每增加1，就对两个进程进行处理，运行中的进程运行时间都减少1，如果减少到了0就说明已经完成了，就在就绪队列中根据作业调度算法选择一个到达了的作业顶替上，直到所有作业完成，没有了作业需要完成。

先来先服务算法：用一个链表按到达时间从小到大进行存储，每当有作业完成时，就从已经到达的作业就绪队列中选择第一个作业进行处理。

短作业优先算法：先将所有作业按到达顺序放入一个链表中，每当有作业完成时，就在已经到达的作业就绪队列中通过比较选择一个所需运行时间最短的一个作业进行处理，即选择在到达作业中选择运行时间最短的一个作业。

响应比高者优先算法:将作业按到达顺序放入链表后，计算每一个作业的响应比，再根据响应比从大到小进行排序，初始状态先运行响应比最高的第一个作业。当有作业完成时，根据当前时间重新计算响应比并进行排序，选择排序后的第一个作业进行运行(当前系统时间必须大于该作业的到达时间)，即选择当前响应比最高的作业进行处理。

程序功能及设计思路

数据结构：

//作业节点
struct Job
{
    string name;        
    int arrival;        
    int runTime;        
    int finish;            
    float response;     
    Job() {};
    friend bool operator==(const Job& a, const Job& b) { return a.name == b.name; }
};

作业节点一共有5个数据成员，分别为作业名name，到达时间arrival，运行时间runTime，完成时间finish和响应比response。

//作业状态
struct Execute
{
    bool active;    
    Job job;        
};

作业状态节点的数据成员active标注作业的执行状态，job为正在执行的具体任务。

//作业调度
class Scheduling
{
private:
    vector<Job> jobs;                        //存储所有作业内容
    list<Job> wait;                         //等待运行的作业
    list<Job> finish;                       //完成的作业
    int time;                               //系统时间
    Execute job1;                           //作业执行程序1
    Execute job2;                           //作业执行程序1
    int finishNum;                          //已经完成了的任务数量

    void run(int i);              //对作业执行1个单位时间,参数1代表job1，2代表job2
    void getResponse();          //计算等待运行作业的响应比并排序
public:
    Scheduling(string fileName);            //构造函数
    void getData(string fileName);            //获取作业信息，存储在jobs中 
    void FCFS();                            //先来先服务算法
    void SJF();                             //短作业优先算法
    void HRRN();                            //响应比高者优先算法
    void print();                           //输出程序
    int findJob(string name);               //根据作业名找到jobs中对应的下标                      
};

作业调度为主要的数据结构，包括存储所有作业内容的数组jobs，存储未完成的作业的链表wait，存储已经完成作业的链表finish，还有当前的系统时间time，作业执行程序1的 job1，作业执行程序2的job2，以及已经完成了的作业数量finishNum。函数成员有执行一个单位时间的函数、将未完成作业计算响应比并排序的函数，从文件中读取作业信息的函数，先来先服务算法，短作业优先算法，响应比高者优先算法，根据作业名找作业下标的函数以及输出完成作业状态和顺序的输出函数。

算法设计：

//获取作业信息，存储在jobs中 
void Scheduling::getData(string fileName)
{
    fstream outFile;
    string line;
    string a, b, c;
    outFile.open(fileName, ios::in);        //打开文件
    if (!outFile.is_open())
    {    //判断文件能否打开
        cout << "文件无法打开！" << endl;
        return;
    }

    while (!outFile.eof())
    {
        getline(outFile, line);
        stringstream input(line);
        input >> a >> b >> c;

        Job* temp = new Job;
        temp->name = a;
        temp->arrival = stoi(b);
        temp->runTime = stoi(c);
        jobs.push_back(*temp);
    }
    outFile.close();
}

算法思想:主要是将文件的作业信息读到内存中去，打开文件后逐行读取，一行为一个作业信息，每行的第一个字符串为作业名，第二个为到达时间，第三个为运行时间，切片字符串并且进行相关处理后存入作业链表jobs中。

//根据作业名找到jobs中对应的下标
int Scheduling::findJob(string name)
{
    for (int i = 0;i < jobs.size();i++)
    {
        if (jobs[i].name == name) return i;
    }
    return -1;
}

算法思想：参数为作业名，通过作业名在作业链表jobs中一一查找，如果有名字相同的作业就返回所在位置的下标，如果整个链表没有同名的就说明查找失败。

//对这个作业执行1个单位时间
void Scheduling::run(int i)
{
    if (i == 1)
    {
        if (!job1.active) return;   //空闲不需要走
        job1.job.runTime--;
        if (job1.job.runTime == 0)
        {//说明执行完毕了
            job1.job.finish = time;
            finish.push_back(job1.job);
            job1.active = false;

        }
    }

    else if (i == 2)
    {
        if (!job2.active) return;   //空闲不需要走
        job2.job.runTime--;
        if (job2.job.runTime == 0)
        {//说明执行完毕了
            job2.job.finish = time;
            finish.push_back(job2.job);
            job2.active = false;
        }
    }
    else return;
}

算法思想:参数为需要运行的作业处理程序编号(本题为1或者2)系统运行一个时间片，对该作业处理程序进行处理，如果当前作业处理程序处于空闲状态就不需要运行，直接返回；否则正在运行的作业运行时间减少1。再运行时间进行判断，如果运行时间为0说明这个作业处理完了，放入作业完成链表中，将作业处理程序的状态设置为false。

//数组中所有的LRUNode成员时间均增加1
void timeAdd(vector<LRUNode>& v)
{
    for (int i = 0;i < v.size();i++)
    {
        v[i].time++;
    }
}

算法思想：对数组中的所有元素的时间成员增加1。

//先来先服务算法，按时间片走
void Scheduling::FCFS()
{
    time = 0;    //系统时间设置为0  
    //把作业内容转移到等待队列中
    for (int i = 0;i < jobs.size();i++)
    {
        wait.push_back(jobs[i]);
    }
    //按进入时间排序
    wait.sort(tmp1());

    Job temp;
    while (finish.size() != jobs.size())
    {//说明还有任务没有完成
        if (!job1.active && !wait.empty())
        {//执行程序空闲并且等待区有任务,且作业已经到达接入作业
            temp = wait.front();
            if (temp.arrival <= time)
            {
                job1.job = temp;
                job1.active = true;
                wait.pop_front();
            }
        }
        if (!job2.active && !wait.empty())
        {//执行程序空闲并且等待区有任务,接入作业
            temp = wait.front();
            if (temp.arrival <= time)
            {
                job2.job = temp;
                job2.active = true;
                wait.pop_front();
            }
        }

        time++;
        //作业执行程序1（2）同时走一个单位时间
        run(1);
        run(2);
    }
}

算法思想：先把系统时间初始化为0，将所有的作业复制到等待队列中，然后按照进入系统时间进行排序。当还有作业未完成时，对两个作业处理程序分别进行处理，如果处理作业程序的状态为空闲，并且等待队列的第一个作业到达时间小于系统时间，就把这个作业放入作业处理系统中运行，并从等待队列中弹出。两个处理程序判断完后系统时间增加1，两个处理系统也分别走一个时间片。

//短作业优先算法
void Scheduling::SJF()
{
    time = 0;    //系统时间设置为0  
    //把作业内容转移到等待队列中
    for (int i = 0;i < jobs.size();i++)
    {
        wait.push_back(jobs[i]);
    }
    //按进入时间排序
    wait.sort(tmp1());
    list<Job>::iterator it;

    while (finish.size() != jobs.size())
    {//说明还有任务没有完成
        if (!job1.active && !wait.empty())
        {//执行程序空闲并且等待区有任务,且作业已经到达接入作业
            it = wait.begin();
            if (it->arrival <= time)
            {
                job1.job = *it;
                for (it = wait.begin();it != wait.end();++it)
                {
                    if (it->runTime < job1.job.runTime&& it->arrival <= time)
                    {
                        job1.job = *it;
                    }
                }
                job1.active = true;
                wait.remove(job1.job);
            }
        }
        if (!job2.active && !wait.empty())
        {//执行程序空闲并且等待区有任务,且作业已经到达接入作业
            it = wait.begin();
            if (it->arrival <= time)
            {
                job2.job = *it;
                for (it = wait.begin();it != wait.end();++it)
                {
                    if (it->runTime < job2.job.runTime && it->arrival <= time)
                    {
                        job2.job = *it;
                    }
                }
                job2.active = true;
                wait.remove(job2.job);
            }
        }

        time++;
        //作业执行程序1（2）同时走一个单位时间
        run(1);
        run(2);
    }
}

算法思想：程序大体框架和先来先服务算法算法类似，但是核心不同，主要差别在于当执行程序空闲并且等待区有任务时选择接下来运行的作业的策略不同，短进程优先算法的选择策略是遍历等待队列，找到一个运行时间最短并且到达时间小于系统时间的作业作为下一个需要处理的作业。

//计算等待运行作业的响应比并排序
void Scheduling::getResponse()
{
    list<Job>::iterator it = wait.begin();
    for (it;it != wait.end();it++)
    {
        it->response = float((time - it->arrival)) / float(it->runTime) + 1;
    }
    wait.sort(tmp2());
}

算法思想：用公式响应比=等待时间/运行时间+1计算响应比，并根据响应比的值从大到小将进行排序，返回排序后的链表。

//响应比高者优先算法
void Scheduling::HRRN()
{
    time = 0;    //系统时间设置为0  
   //把作业内容转移到等待队列中
    for (int i = 0;i < jobs.size();i++)
    {
        wait.push_back(jobs[i]);
    }
    //按进入时间排序
    wait.sort(tmp1());
    getResponse();
    Job temp;
    while (finish.size() != jobs.size())
    {//说明还有任务没有完成
        if (!job1.active && !wait.empty())
        {//执行程序空闲并且等待区有任务,且作业已经到达接入作业
            getResponse();
            temp = wait.front();

            if (temp.arrival <= time)
            {
                job1.job = temp;
                job1.active = true;
                wait.pop_front();
            }
        }
        if (!job2.active && !wait.empty())
        {//执行程序空闲并且等待区有任务,接入作业
            getResponse();
            temp = wait.front();
            if (temp.arrival <= time)
            {
                job2.job = temp;
                job2.active = true;
                wait.pop_front();
            }
        }

        time++;
        //作业执行程序1（2）同时走一个单位时间
        run(1);
        run(2);
    }
}

算法思想：程序大体框架和先来先服务算法算法与短进程优先算法类似类似，但是对作业的选择策略不同，每次选择新的作业前都会重新计算响应比并且排序，然后在等待队列中选择第一个作业进行运行，到达时间必须小于当前系统时间。其他内容和前面两个算法一样。

//输出程序
void Scheduling::print()
{
    Job curPtr;
    int tempTime;
    int turnaroundTime = 0;             //总周转时间
    float weightedTurnaroundTime = 0;     //总带权周转时间
    int des;
    list<Job>::iterator it = finish.begin();
    while (!finish.empty())
    {
        curPtr = finish.front();
        finish.pop_front();
        des = findJob(curPtr.name);
        tempTime = curPtr.finish - curPtr.arrival;
        turnaroundTime += tempTime;
        weightedTurnaroundTime += (float(tempTime) / float(jobs[des].runTime));
        cout << "进程名称：" << curPtr.name << "\t\t完成时间为:" << curPtr.finish << endl;
    }
    cout << "平均周转时间为：" << float(turnaroundTime) / float(jobs.size()) << endl;
    cout << "平均带权周转时间为：" << float(weightedTurnaroundTime) / float(jobs.size()) << endl;
}

算法思想：遍历完成队列，按顺序逐个输出每个作业的完成情况，顺序就是作业完成的顺序，同时计算平均周转时间和平均带权周转时间。作业完成情况输出完毕后后再输出平均周转时间和平均带权周转时间。

源代码

data.txt

A    0    7
B    2    10
C    5    20
D    7    30
E    12    40
F    15    8
G    4    8
H    6    20
I    8    10
J    10    12

jobScheduling.cpp

#include <iostream>
#include <vector>
#include <list>
#include <fstream>
#include <sstream>

using namespace std;

//作业节点
struct Job
{
    string name;        //作业名
    int arrival;        //到达时间
    int runTime;        //运行时间
    int finish;            //完成时间
    float response;     //响应比
    Job() {};
    friend bool operator==(const Job& a, const Job& b) { return a.name == b.name; }
};


//按到达时间排序
struct tmp1
{
    bool operator()(const Job& a, const Job& b)
    {
        return a.arrival < b.arrival;    
    }
};

//按响应比进行排序
struct tmp2
{
    bool operator()(const Job& a, const Job& b)
    {
        return a.response > b.response;
    }
};
//作业执行
struct Execute
{
    bool active;    //是否有作业正在执行
    Job job;        //正在执行的具体任务
};

//作业调度
class Scheduling
{
private:
    vector<Job> jobs;                        //存储所有作业内容
    list<Job> wait;                         //等待运行的作业
    list<Job> finish;                       //完成的作业
    int time;                               //系统时间
    Execute job1;                           //作业执行程序1
    Execute job2;                           //作业执行程序1
    int finishNum;                          //已经完成了的任务数量

    void run(int i);                        //对作业执行1个单位时间,参数1代表job1，2代表job2
    void getResponse();                     //计算等待运行作业的响应比并排序
public:
    Scheduling(string fileName);            //构造函数
    void getData(string fileName);            //获取作业信息，存储在jobs中 
    void FCFS();                            //先来先服务算法
    void SJF();                             //短作业优先算法
    void HRRN();                            //响应比高者优先算法
    void print();                           //输出程序
    int findJob(string name);               //根据作业名找到jobs中对应的下标                      
};

//构造函数
Scheduling::Scheduling(string fileName)
{
    job1.active = job2.active = false;
    time = 0;
    getData(fileName);
}

//获取作业信息，存储在jobs中 
void Scheduling::getData(string fileName)
{
    fstream outFile;
    string line;
    string a, b, c;
    outFile.open(fileName, ios::in);        //打开文件
    if (!outFile.is_open())
    {    //判断文件能否打开
        cout << "文件无法打开！" << endl;
        return;
    }

    while (!outFile.eof())
    {
        getline(outFile, line);
        stringstream input(line);
        input >> a >> b >> c;

        Job* temp = new Job;
        temp->name = a;
        temp->arrival = stoi(b);
        temp->runTime = stoi(c);
        jobs.push_back(*temp);
    }
    outFile.close();
}

//根据作业名找到jobs中对应的下标
int Scheduling::findJob(string name)
{
    for (int i = 0;i < jobs.size();i++)
    {
        if (jobs[i].name == name) return i;
    }
    return -1;
}

//对这个作业执行1个单位时间
void Scheduling::run(int i)
{
    if (i == 1)
    {
        if (!job1.active) return;   //空闲不需要走
        job1.job.runTime--;
        if (job1.job.runTime == 0)
        {//说明执行完毕了
            job1.job.finish = time;
            finish.push_back(job1.job);
            job1.active = false;

        }
    }

    else if (i == 2)
    {
        if (!job2.active) return;   //空闲不需要走
        job2.job.runTime--;
        if (job2.job.runTime == 0)
        {//说明执行完毕了
            job2.job.finish = time;
            finish.push_back(job2.job);
            job2.active = false;
        }
    }
    else return;
}


//先来先服务算法，按时间片走
void Scheduling::FCFS()
{
    time = 0;    //系统时间设置为0  
    //把作业内容转移到等待队列中
    for (int i = 0;i < jobs.size();i++)
    {
        wait.push_back(jobs[i]);
    }
    //按进入时间排序
    wait.sort(tmp1());

    Job temp;
    while (finish.size() != jobs.size())
    {//说明还有任务没有完成
        if (!job1.active && !wait.empty())
        {//执行程序空闲并且等待区有任务,且作业已经到达接入作业
            temp = wait.front();
            if (temp.arrival <= time)
            {
                job1.job = temp;
                job1.active = true;
                wait.pop_front();
            }
        }
        if (!job2.active && !wait.empty())
        {//执行程序空闲并且等待区有任务,接入作业
            temp = wait.front();
            if (temp.arrival <= time)
            {
                job2.job = temp;
                job2.active = true;
                wait.pop_front();
            }
        }

        time++;
        //作业执行程序1（2）同时走一个单位时间
        run(1);
        run(2);
    }
}

//短作业优先算法
void Scheduling::SJF()
{
    time = 0;    //系统时间设置为0  
    //把作业内容转移到等待队列中
    for (int i = 0;i < jobs.size();i++)
    {
        wait.push_back(jobs[i]);
    }
    //按进入时间排序
    wait.sort(tmp1());
    list<Job>::iterator it;

    while (finish.size() != jobs.size())
    {//说明还有任务没有完成
        if (!job1.active && !wait.empty())
        {//执行程序空闲并且等待区有任务,且作业已经到达接入作业
            it = wait.begin();
            if (it->arrival <= time)
            {
                job1.job = *it;
                for (it = wait.begin();it != wait.end();++it)
                {
                    if (it->runTime < job1.job.runTime&& it->arrival <= time)
                    {
                        job1.job = *it;
                    }
                }
                job1.active = true;
                wait.remove(job1.job);
            }
        }
        if (!job2.active && !wait.empty())
        {//执行程序空闲并且等待区有任务,且作业已经到达接入作业
            it = wait.begin();
            if (it->arrival <= time)
            {
                job2.job = *it;
                for (it = wait.begin();it != wait.end();++it)
                {
                    if (it->runTime < job2.job.runTime && it->arrival <= time)
                    {
                        job2.job = *it;
                    }
                }
                job2.active = true;
                wait.remove(job2.job);
            }
        }

        time++;
        //作业执行程序1（2）同时走一个单位时间
        run(1);
        run(2);
    }
}

//计算等待运行作业的响应比并排序
void Scheduling::getResponse()
{
    list<Job>::iterator it = wait.begin();
    for (it;it != wait.end();it++)
    {
        it->response = float((time - it->arrival)) / float(it->runTime) + 1;
    }
    wait.sort(tmp2());
}

//响应比高者优先算法
void Scheduling::HRRN()
{
    time = 0;    //系统时间设置为0  
   //把作业内容转移到等待队列中
    for (int i = 0;i < jobs.size();i++)
    {
        wait.push_back(jobs[i]);
    }
    //按进入时间排序
    wait.sort(tmp1());
    getResponse();
    Job temp;
    while (finish.size() != jobs.size())
    {//说明还有任务没有完成
        if (!job1.active && !wait.empty())
        {//执行程序空闲并且等待区有任务,且作业已经到达接入作业
            getResponse();
            temp = wait.front();

            if (temp.arrival <= time)
            {
                job1.job = temp;
                job1.active = true;
                wait.pop_front();
            }
        }
        if (!job2.active && !wait.empty())
        {//执行程序空闲并且等待区有任务,接入作业
            getResponse();
            temp = wait.front();
            if (temp.arrival <= time)
            {
                job2.job = temp;
                job2.active = true;
                wait.pop_front();
            }
        }

        time++;
        //作业执行程序1（2）同时走一个单位时间
        run(1);
        run(2);
    }
}
//输出程序
void Scheduling::print()
{
    Job curPtr;
    int tempTime;
    int turnaroundTime = 0;             //总周转时间
    float weightedTurnaroundTime = 0;     //总带权周转时间
    int des;
    list<Job>::iterator it = finish.begin();
    while (!finish.empty())
    {
        curPtr = finish.front();
        finish.pop_front();
        des = findJob(curPtr.name);
        tempTime = curPtr.finish - curPtr.arrival;
        turnaroundTime += tempTime;
        weightedTurnaroundTime += (float(tempTime) / float(jobs[des].runTime));
        cout << "进程名称：" << curPtr.name << "\t\t完成时间为:" << curPtr.finish << endl;
    }
    cout << "平均周转时间为：" << float(turnaroundTime) / float(jobs.size()) << endl;
    cout << "平均带权周转时间为：" << float(weightedTurnaroundTime) / float(jobs.size()) << endl;
}

int main()
{
    Scheduling obj("data.txt");
    cout << "先进先出算法:" << endl;
    obj.FCFS();
    obj.print();
    cout << "\n短作业优先算法:" << endl;
    obj.SJF();
    obj.print();
    cout << "\n响应比高者优先算法:" << endl;
    obj.HRRN();
    obj.print();
    return 0;
}