操作系统——短作业优先调度算法

实验内容

模拟实现FCFS/SJF调度。

设置作业体：作业名，作业的到达时间，服务时间，作业状态（W——等待,R——运行,F——完成），作业间的链接指针；

作业初始化：由用户输入作业名、服务时间、到达时间进行初始化，同时，初始化作业的状态为W。

显示函数：在作业调度前、调度中和调度后进行显示。

排序函数：对等待状态的作业按照调度算法排序（不同的调度算法排序方式不同），注意考虑到达时间。

调度函数：每次从等待队列队首调度已到达的适合的作业执行，状态变化。当服务结束时，状态变为F。

删除函数：撤销状态为F的作业。

实验要求

（1）测试数据可以随即输入或从文件中读入；
（2）必须要考虑到作业的到达时间；
（3）最终能够计算每一个作业的周转时间、带权周转。

实验要求做先来先服务或者短作业优先都可以，这里我做的是抢占式的短作业优先算法，一些函数没有按着实验内容里给的函数来，但是实验要求的内容基本都实现了。

先看一下实验结果：
输入的数据是之前我们学校慕课上的一个题目的数据：



先显示作业的初始状态：

显示调度情况：




计算出的各个作业的周转时间和带权周转时间：

可以自己算一下，程序运行出来的结果是对的，我只测试了慕课上的样例，其他的样例没测，如有错误，欢迎指正。
代码如下：

#include <bits/stdc++.h>

using namespace std;
const int MAX = 1e5;

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

struct WORK
{
    string work_name; // 作业名
    int serve_time; // 剩余服务时间
    int r_serve_time; // 服务时间
    int arrive_time; // 到达时间
    string work_state; // 作业状态
    int end_time; // 结束时间
    int turnover_time; // 周转时间
};

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 count_work(int t) // 计算某一时间有多少个作业进入
{
    int cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        if(work[i].arrive_time <= t)
            cnt++;
    }
    return cnt;
}

void update_work(int num, int c_time) // 更新当前每个作业的状态
{
    int t = 0;
    for(int i = 1; i <= num; i++)
    {
        if(work[i].serve_time <= 0) // 作业已经结束
        {
            work[i].serve_time = 0;
            work[i].work_state = F;
        }
        else if(work[i].serve_time > 0) // 作业还没结束
        {
            work[i].serve_time --;
            work[i].work_state = R;
            t = i;
            break;
        }
    }

    for(int i = 1; i <= n; i++) // 更新状态
    {
        if(i != t)
        {
            if(work[i].work_state != F)
                work[i].work_state = W;
        }
        if(work[i].work_state == F && work[i].end_time == -1)
            work[i].end_time = c_time;
    }

}

bool judge_over() // 判断作业是否全部完成
{
    for(int i = 1; i <= n; i++)
        if(work[i].work_state != F)
            return false;
    return true;
}

int main()
{
    cout << "请输入要调度的作业：" << endl;
    cout << "要调度的作业的数量：" ;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cout << "作业名： " << endl;
        cin >> work[i].work_name;
        cout << "作业服务时间： " << endl;
        cin >> work[i].serve_time;
        cout << "作业到达时间： " << endl;
        cin >> work[i].arrive_time;
        work[i].work_state = W;
        work[i].end_time = -1;
        work[i].r_serve_time = work[i].serve_time;
    }

    sort(work + 1, work + 1 + n, cmp_arr_time); // 先按到达时间排序

    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(13) << work[i].serve_time
        << setw(21)  << work[i].work_state << endl;
    }
    cout << endl;

    int arrive_num = 0; // 已到达的作业数量
    int current_time = 0; // 当前时间

    cout << "作业调度情况如下：" << endl;


    bool is_over = false;

    while(!is_over)
    {
        cout << "    时刻    " << "    作业名    " << "    到达时间    "
        << "    剩余服务时间    " << "    当前状态    " << endl;
        arrive_num = count_work(current_time);
        sort(work + 1, work + 1 + arrive_num, cmp_SJF); // 排序

        update_work(arrive_num, current_time);

        for(int i = 1; i <= arrive_num; i++)
        {
            cout  << setw(6) << current_time << setw(13) << work[i].work_name
            << setw(15) << work[i].arrive_time << setw(15) << work[i].serve_time
            << setw(24)  << work[i].work_state << endl;
        }

        current_time ++;
        is_over = judge_over();
        cout << endl;
    }

    cout << "各作业的周转时间和带权周转时间如下：" << endl;
    cout << "    作业名    " << "    周转时间    " << "    带权周转时间    " << endl;
    for(int i = 1; i <= n; i++)
    {
        work[i].turnover_time = work[i].end_time - work[i].arrive_time; // 周转时间
        double wight_time = 1.0 * work[i].turnover_time / work[i].r_serve_time; // 带权周转时间

        cout << setw(6) << work[i].work_name << setw(15) << work[i].turnover_time << setw(18);
        cout.precision(4);
        cout << wight_time << endl;
    }
    return 0;
}

项目名称：短作业优先调度算法（非抢占式）

短作业优先调度算法（SJF）是以作业的长度来计算优先级，作业越短，优先度越高。作业的长短是作业的运行时间来衡量的。

具体可以看https://blog.csdn.net/weixin_41931278/article/details/106025095?utm_source=app

源程序

（源程序C++编写，由老师提供的参考、网上查询、同学之间讨论之后完善，非诚勿扰！！！）

#include<iostream>
using namespace std;
struct Node {
	char name;		//进程编号 
	int Tarrive;	//到达时间
	int Tservice;	//服务时间
	int Tsurplus;	//剩余时间
	int Tstart;		//开始时间
	int Taccomplish;//完成时间
	int if_finish;	//进程是否完成
	int num;		//进程个数
}job[10];

//按服务时间排序
void Service_sort(int num)
{
	int temp1, temp2, temp3;
	for (int i = 1; i < num; i++)
	{
		for (int j = i + 1; j < num; j++)
		{
			if (job[i].Tservice > job[j].Tservice)
			{
				temp1 = job[j].name;
				job[j].name = job[i].name;
				job[i].name = temp1;
				temp2 = job[j].Tarrive;
				job[j].Tarrive = job[i].Tarrive;
				job[i].Tarrive = temp2;
				temp3 = job[j].Tservice;
				job[j].Tservice = job[i].Tservice;
				job[i].Tservice = temp3;
			}
		}
	}
}

//如果 到达时间相等，服务时间 按 从小到大排序
void Arrive_Short_sort(int num)
{
	int temp1, temp2, temp3;
	for (int i = 0; i < num; i++)
	{
		for (int j = i + 1; j < num; j++)
		{
			if (job[i].Tarrive >= job[j].Tarrive)
			{
				if (job[i].Tarrive > job[j].Tarrive)
				{
					temp1 = job[j].name;
					job[j].name = job[i].name;
					job[i].name = temp1;
					temp2 = job[j].Tarrive;
					job[j].Tarrive = job[i].Tarrive;
					job[i].Tarrive = temp2;
					temp3 = job[j].Tservice;
					job[j].Tservice = job[i].Tservice;
					job[i].Tservice = temp3;
				}
				else
				{
					if (job[i].Tservice > job[j].Tservice)
					{
						temp1 = job[j].name;
						job[j].name = job[i].name;
						job[i].name = temp1;
						temp2 = job[j].Tarrive;
						job[j].Tarrive = job[i].Tarrive;
						job[i].Tarrive = temp2;
						temp3 = job[j].Tservice;
						job[j].Tservice = job[i].Tservice;
						job[i].Tservice = temp3;
					}
				}
			}
		}
	}
}

void sjf(int num){//最短作业优先算法
 	int i;
	for(i=0;i<=num;i++){
		if(i==0){
			job[i].Tstart=job[i].Tarrive;
			job[i].Taccomplish=job[i].Tarrive+job[i].Tservice;
		}
		else{
			if(job[i].Tarrive<=job[i-1].Taccomplish){
				job[i].Tstart=job[i-1].Taccomplish;
				job[i].Taccomplish=job[i-1].Taccomplish+job[i].Tservice;
			}
			else{
				job[i].Tstart=job[i-1].Taccomplish;
				job[i].Taccomplish=job[i-1].Taccomplish+job[i].Tservice+job[i].Tarrive;
			}
		}
		
	}
	  
} 

//输出
void print(int num)
{
	cout << "进程名" << "\t" << "到达时间" << "\t" << "服务时间" << "\t" << "完成时间" << endl;
 
	for (int i = 0; i < num; i++)
	{
		cout << job[i].name << "\t" << job[i].Tarrive << "\t\t" << job[i].Tservice << "\t\t" << job[i].Taccomplish << endl;
	}
}

//选择即将执行的算法
void display(int num)
{
	int ch = 0;
	cout << "-------------------------" << endl;
	cout << "----------2、SJF算法----------" << endl;
	cout << "----------3、退出 -----------" << endl;
	cout << "-------------------------" << endl;
	do {
		cout << "请选择：" << endl;
		cin >> ch;
		switch (ch) {
		case 2:
			Service_sort(num); 
			Arrive_Short_sort(num);
			sjf(num);
			print(num);
			break;
		
		case 3:
			exit(1);
		}
	} while (ch != 3);
}

int main() //主函数
{
	int num;
	char jname;
	int arrive;
	int service;
	cout << "请输入进程个数：" << endl;
	cin >> num;
	for (int i = 0; i < num; i++)
	{
		cout << "请输入进程名、到达时间、服务时间" << endl;
		cin >> jname;
		job[i].name = jname;
		cin >> arrive;
		job[i].Tarrive = arrive;
		cin >> service;
		job[i].Tservice = service;
	}
	display(num);
	return 0;
}

在Bloodshed Dev-C++ 运行，结果如下：