多道程序系统的作业调度模拟程序——先来先服务

2、编写并调度一个多道程序系统的作业调度模拟程序。

　　作业调度算法：采用基于先来先服务的调度算法。

　　对于多道程序系统，要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求。

本程序中，我设定CPU最大可运行资源数为10，时间片为0.5，如果输入的作业(单个)占用CPU时间大于10，程序终止，无法调度。

测试样例：

作业名提交时间 CPU运行时间 IO时间

1 5 2 1

2 2 5 3

3 2 4 2

FCFS：

按照提交时间排序：2,3,1

leave time 的次行才是上一行完成的作业。

由于微观上是轮转调度，从作业2开始，运行0.5后交给作业3，再运行0.5后交给作业1，由于作业1的CPU占用时间比较短，因此先运行结束，完成时间是开始时间，CPU服务时间和IO时间的总和。

时间从2开始运行，每个作业使用CPU 0.5后交给下个作业，到作业1完成时，共需要轮转4次，每次相当于消耗1.5，这个作业不占用CPU的时间相当于2(整个开始时间)+ 4*1.5(占用CPU时间完成) = 8。

ex：作业1 先完成，完成时间 2 + 4*1.5(4轮，每轮1.5) + 1(IO时间) = 9

周转时间 9 - 5 = 4

作业3 完成，完成时间 2(整个开始时间) + 6(作业1完成) + 4*1(作业3剩余部分) + 2(IO时间) = 14

作业2 完成，完成时间 2 + 6 + 4 + 2*0.5 + 3 = 16

代码：

#include <iostream>
#include <cmath>
#include <cstdlib>

using namespace std;

struct Box
{
    string ID;                                       //作业号
    double begin_time;                               //提交时间
    double rtime;                                    //已经运行时间
    double turnaround_time;                          //周转时间
    double cpu_service_time;                         //占用CPU的时间
    double io_time;                                  //用于I/O的时间
    double finish_time;                              //完成时间
    double Wturnaround_time;                         //带权周转时间
    Box& operator = (const Box& p2)                 //重载 = 运算符，方便排序
    {
        this->begin_time = p2.begin_time;
        this->rtime = p2.rtime;
        this->finish_time = p2.finish_time;
        this->cpu_service_time = p2.cpu_service_time;
        this->io_time = p2.io_time;
        this->ID = p2.ID;
        this->turnaround_time = p2.turnaround_time;
        this->Wturnaround_time = p2.Wturnaround_time;
        return *this;
    }
};

typedef struct
{
    Box data[100];

} JCB;

const double CPU = 10.0;
const double index = 0.5;
JCB jcb,jcb_1;
int n,number;

void init()                                                        //初始化作业块
{
    cout<<"please input the number of the job:";
    cin>>n;
    number = n;
    for(int i = 0; i<n; i++)
    {
        cout<<"process ID:";
        cin>>jcb.data[i].ID;
        cout<<jcb.data[i].ID<<"'s begin time:";
        cin>>jcb.data[i].begin_time;
        cout<<jcb.data[i].ID<<"'s cpu_service time:";
        cin>>jcb.data[i].cpu_service_time;
        cout<<jcb.data[i].ID<<"'s I/O time:";
        cin>>jcb.data[i].io_time;
        jcb.data[i].rtime = 0;
    }
    for(int i = 0; i<n-1; i++)                                    //按照提交时间从前到后排序
    {
        for(int j = i+1; j<n; j++)
        {
            if(jcb.data[i].begin_time > jcb.data[j].begin_time)
                swap(jcb.data[i],jcb.data[j]);
        }
    }
    for(int i = 0; i<n-1; i++)                        //提交时间相同，序号小的在前
    {
        for(int j = i+1; j<n; j++)
        {
            if(jcb.data[i].begin_time == jcb.data[j].begin_time && jcb.data[i].ID > jcb.data[j].ID)
                swap(jcb.data[i],jcb.data[j]);
        }
    }
}

void FCFS()                                                //先来先服务
{
    int j = 0;
    double running = CPU;
    double bt = jcb.data[0].begin_time;
    double gtt = 0;
    double gwtt = 0;
    double real_begin;
    double record = jcb.data[j].begin_time;
    int num = n-1;
    cout<<"ID     "<<"leave time  "<<"begin time  "<<"turnaround time  "<<"finish time  "<<"wighted turnaround time"<<endl;
    while(1)
    {
        if(jcb.data[j].cpu_service_time > CPU)
        {
            cout<<"over running range!!!"<<endl;
            exit(0);
        }
        jcb.data[j].rtime += index;
        record += index;
        if(running >= 0)
        {
            if (jcb.data[j].rtime >= jcb.data[j].cpu_service_time)
            {
                real_begin = bt;
                jcb.data[j].finish_time = record+ jcb.data[j].io_time;
                jcb.data[j].turnaround_time = jcb.data[j].finish_time - jcb.data[j].begin_time;
                jcb.data[j].Wturnaround_time = jcb.data[j].turnaround_time / jcb.data[j].rtime;
                cout<<jcb.data[j].ID<<"         "<<real_begin<<"                "
                <<jcb.data[j].begin_time<<"                  "<<jcb.data[j].turnaround_time
                <<"              "<<jcb.data[j].finish_time<<"                 "
                <<jcb.data[j].Wturnaround_time<<endl;
                n--;
                running -= jcb.data[j].cpu_service_time;
                bt = record;
                gtt += jcb.data[j].turnaround_time;
                gwtt += jcb.data[j].Wturnaround_time;
            }
            else
            {
                num++;
                swap(jcb.data[num],jcb.data[j]);
            }
        }
        else
        {
            running += jcb.data[j].cpu_service_time;
            num++;
            swap(jcb.data[num],jcb.data[j]);
        }
        if(n == 0)
            break;
        j++;
    }
    cout<<" average of turnaround time:"<<gtt/number<<endl<<"average of wighted turnaround time:"<<gwtt/number<<endl;
}


int main()
{
    init();
    FCFS();
    return 0;
}