[数据结构与算法]操作系统第一次实验-短作业优先调度算法

一、实验目的：

目的：了解并掌握作业调度的功能，熟悉并掌握各种作业调度算法。
任务：模拟实现先来先服务或者短作业优先调度算法。

二、实验内容：

模拟实现SJF调度。
设置作业体：作业名，作业的到达时间，服务时间，作业状态（W——等待,R——运行,F——完成），作业间的链接指针；
作业初始化：由用户输入作业名、服务时间、到达时间进行初始化，同时，初始化作业的状态为W。
显示函数：在作业调度前、调度中和调度后进行显示。
排序函数：对等待状态的作业按照调度算法排序（不同的调度算法排序方式不同），注意考虑到达时间。
调度函数：每次从等待队列队首调度已到达的适合的作业执行，状态变化。当服务结束时，状态变为F。
删除函数：撤销状态为F的作业。
实验要求
（1）测试数据可以随即输入或从文件中读入；
（2）必须要考虑到作业的到达时间；
（3）最终能够计算每一个作业的周转时间、带权周转时间。

三、实验代码：

#include<iostream>
#include<iomanip>
#include<algorithm>

using namespace std;
const int MAX = 1e5;

#define W "waitting"
#define R "running"
#define F "finished"

typedef struct WORK
{
    string work_name; // 作业名
    int serve_time; // 服务时间
    int arrive_time; // 到达时间
    int start_time;//开始时间
    int finish_time; // 完成时间
    string work_state; // 作业状态
    int turnover_time; // 周转时间
}WORK;

WORK work[MAX]; // 作业
int n; // 作业数量

bool cmp_SJF(WORK x, WORK y) // 排序函数
{
    if (x.serve_time != y.serve_time) // 服务时间不同时，较短的优先
        return x.serve_time < y.serve_time;
    else // 服务时间相同时，先到达的优先
        return x.arrive_time < y.arrive_time;
}

bool cmp_arr_time(WORK x, WORK y) // 按到达时间从小到大排序
{
    return x.arrive_time < y.arrive_time;
}


 

int init()
{
    cout << "请输入要调度的作业：" << endl;
    cout << "要调度的作业的数量：";
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cout << "作业名： ";
        cin >> work[i].work_name;

        cout << "作业到达时间： ";
        cin >> work[i].arrive_time;

        cout << "作业服务时间： ";
        cin >> work[i].serve_time;

        work[i].work_state = W;
        work[i].finish_time = -1;
    }
  
    system("cls");
    return n;

}

void show(WORK work[],int n)
{
    cout << "                                          作业状态" << endl;
    cout << "-----------------------------------------------------------------------------------------------"
         << endl;
    cout << "    作业名    " << "    到达时间    "
        << "   服务时间    " << "    开始时间    "
        <<"    完成时间     "<<"     当前状态    " << endl;
    for (int i = 1; i <= n; i++)
    {
        cout << setw(8) << work[i].work_name 
            << setw(16)<< work[i].arrive_time
            << setw(15) << work[i].serve_time
            <<setw(15)<<work[i].start_time
            << setw(18)<<work[i].finish_time
            << setw(20) << work[i].work_state << endl;
    }
    cout << endl;
}

void deal(WORK work[],int n)
{
    for (int i = 1; i <= n; i++)
    {
        if (i == 1)
        {
            work[i].start_time = work[i].arrive_time;
            work[i].finish_time = work[i].arrive_time + work[i].serve_time;
        }
        else
        {
            work[i].start_time = work[i-1].finish_time;
            work[i].finish_time = work[i - 1].finish_time + work[i].serve_time;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        work[i].turnover_time = work[i].finish_time - work[i].arrive_time;
        cout << work[i].work_name << ":";
        cout << "周转时间:" << work[i].turnover_time;
        cout << "   带权周转时间:" << work[i].turnover_time / work[i] .serve_time<< endl;
    }
   
}

void sjfDispatch(WORK work[], int n)
{
    sort(work + 1, work + 1 + n, cmp_arr_time); 
    show(work,n);
    for (int i = 1; i <=n; i++)
    {
        show(work, n);
        //执行调度程序....
        work[i].work_state = R;//调度队列中的第一个作业

        cout << "作业" << work[i].work_name << "调度中：" << endl;
        show(work, n);

        if (i == 1)
        {
            work[i].start_time = work[i].arrive_time;
            work[i].finish_time = work[i].arrive_time + work[i].serve_time;
        }
        else
        {
            work[i].start_time = work[i - 1].finish_time;
            work[i].finish_time = work[i - 1].finish_time + work[i].serve_time;
        }//该部分用来计算各个作业的完成时间
        if (i != n)
        {
            int workcount = 0;
            for (int j = i + 1; j <= n; j++)
            {
                if (work[j].arrive_time <= work[i].finish_time)
                {
                    workcount++;
                }
            }
            sort(work + 1 + i, work + 1 + i + workcount, cmp_SJF);//对等待队列中的作业按SJF算法进行排序，一共有workcount个
        }
        work[i].work_state = F; //撤销正在调度的作业
        cout << "作业" << work[i].work_name << "调度后：" << endl;
        show(work, n); 
      
    }   
    deal(work, n);
    
}

int main()
{   
    int n=init();
    sjfDispatch(work, n);
    return 0;
}

四、实验结果：

数据样本：

输入数据：





作业执行顺序及周转时间和带权周转时间与预期结果相符。

五、实验总结：

通过本次短作业优先调度算法实验我实际认识到了系统在执行作业调度的具体过程，对SJF短作业优先调度算法有了更加深入的认识，SJF的基本思想是以作业的长度来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。
代码的主体思路主要是三步：1.找出最先到达的作业（该作业的完成时间=到达时间+服务时间）；2.根据上一作业的完成时间，找到在这个完成时间内所有到达的作业，并找到这些作业中服务时间最短的那个，然后计算它的完成时间（该作业的完成时间=上一作业的完成时间+该作业服务时间）；3.重复步骤2直至完成所有作业的计算。
由于我采用的编程语言是C++，因此对于排序算法的处理可以简单地调用STL中的sort函数，这使得编码得到了进一步的简便。但要注意第三个形参cmp函数，该函数是该SJF算法的关键。