【操作系统实验】 c++模拟实现作业调度

模拟实现了FSFC、SJF、PSA三种作业调度算法。

代码：

#pragma warning (disable:4996)
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#define inf 0X3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int MAXJOBNUM = 50;

class Job {
public:
	int num;//编号
	string name;//名字
	string submitTime;//提交时间
	int runTime;//运行时间
	string beginTime;//开始时间
	string endTime;//结束时间
	int waitTime;//等待时间
	int turnaroundTime;//周转时间
	bool exed;//是否已经执行过

	friend bool operator<(const Job& x, const Job& y) {
		if (x.runTime == y.runTime)
			return true;
		return x.runTime > y.runTime;
	}

};

bool cmp_submitTime(Job& x, Job& y) {
	if (x.submitTime == y.submitTime)
		return x.runTime < y.runTime;//如果提交时间相同则按照运行时间排序
	return x.submitTime < y.submitTime;
}

bool cmp_turnaroundTime(Job& x, Job& y) {//按照响应时间排序的倒序
	if (x.turnaroundTime == y.turnaroundTime)
		return false;
	return x.turnaroundTime > y.turnaroundTime;
}

class jobScheduling {
private:
	Job jobs[MAXJOBNUM];
	priority_queue<Job> que;//进程就绪队列
	int jobSize;//作业数
	int avg_turnaroundTime;//平均周转时间
	int avgWeighted_turnaroundTime;//平均带权周转时间
public:
	void input();
	void output();
	string addTime(string, int);

	void FCFSschedule();
	void SJFschedule();
	void PSAschedule();

};

void jobScheduling::input() {
	cout << "请输入作业信息（Ctrl+Z 表示输入结束）\n";
	cout << "作业编号 | 作业名称 | 提交时间 | 要求服务运行时间\n";
	Job tmp;
	while (cin >> tmp.num >> tmp.name >> tmp.submitTime >> tmp.runTime) {
		jobs[jobSize++] = tmp;
		que.push(tmp);
	}
}

string jobScheduling::addTime(string now, int time) {
	int hour = (now[0] - '0') * 10 + now[1] - '0';
	int minute = (now[3] - '0') * 10 + now[4] - '0';

	minute += time;
	while (minute >= 60) {
		hour++;
		minute -= 60;
	}
	string res = "";
	res = res + char((hour / 10) + '0') + char(hour % 10 + '0');
	res = res + ':';
	res = res + char((minute / 10) + '0') + char(minute % 10 + '0');
	return res;
}

void jobScheduling::FCFSschedule() {
	int pos = 0;
	string nowTime = que.top().submitTime;//当前时间
	int sumWaitTime = 0;//累计运行时间
	while (que.size()) {
		Job nowJob = que.top();
		que.pop();
		nowJob.beginTime = nowTime;
		nowJob.endTime = addTime(nowTime, nowJob.runTime);
		nowJob.waitTime = sumWaitTime;
		nowJob.turnaroundTime = nowJob.runTime + sumWaitTime;
		jobs[pos++] = nowJob;
		nowTime = addTime(nowTime, nowJob.runTime);
		sumWaitTime += nowJob.runTime;
	}
}

void jobScheduling::SJFschedule() {
	priority_queue<Job> que;//优先队列
	int cnt = 0;//计数
	Job sortedJobs[MAXJOBNUM];//作业调度顺序
	int pos = 0;

	for (int i = 0; i < jobSize; i++)
		jobs[i].exed = false;
	sort(jobs, jobs + jobSize, cmp_submitTime);

	string nowTime = jobs[0].submitTime;
	jobs[0].exed = true;
	int sumWaitTime = 0;
	que.push(jobs[0]);
	while (cnt < jobSize) {//停止条件是全部作业已经完成
		Job nowJob;

		if (que.empty()) {
			bool flag = 0;
			for (int i = 0; i < jobSize; i++) {
				if (!jobs[i].exed)
					if (jobs[i].submitTime <= nowTime) {
						jobs[i].exed = true;
						que.push(jobs[i]);
						flag = 1;
					}
					else
						break;
			}
			if (flag)
				continue;
			for (int i = 0; i < jobSize; i++)//当前时间没有已经提交的作业，但并未执行完所有的作业
				if (!jobs[i].exed) {
					jobs[i].exed = true;
					nowJob = jobs[i];
					break;
				}
		}
		else {
			nowJob = que.top();
			que.pop();
		}
		nowJob.beginTime = nowTime;
		nowJob.endTime = addTime(nowTime, nowJob.runTime);
		nowJob.waitTime = sumWaitTime;
		nowJob.turnaroundTime = sumWaitTime + nowJob.runTime;
		sortedJobs[pos++] = nowJob;

		nowTime = addTime(nowTime, nowJob.runTime);
		sumWaitTime += nowJob.runTime;
		cnt++;

	}
	for (int i = 0; i < jobSize; i++)
		jobs[i] = sortedJobs[i];
}

void jobScheduling::PSAschedule() {
	vector<Job> vec;//模拟队列
	Job sortedJobs[MAXJOBNUM];
	int pos = 0;
	int cnt = 0;

	for (int i = 0; i < jobSize; i++)
		jobs[i].exed = false;
	sort(jobs, jobs + jobSize, cmp_submitTime);

	string nowTime = jobs[0].submitTime;
	int sumWaitTime = 0;
	while (cnt < jobSize) {
		for (int i = 0; i < jobSize; i++) {//更新响应时间
			jobs[i].waitTime = sumWaitTime;
			jobs[i].turnaroundTime = sumWaitTime + jobs[i].runTime;
			if (jobs[i].submitTime <= nowTime && !jobs[i].exed) {
				vec.push_back(jobs[i]);
				jobs[i].exed = true;
			}
		}

		sort(vec.begin(), vec.end(), cmp_turnaroundTime);//倒序

		Job nowJob;
		if (vec.empty()) {
			for (int i = 0; i < jobSize; i++)//当前时间没有已经提交的作业，但并未执行完所有的作业
				if (!jobs[i].exed) {
					nowJob = jobs[i];
					break;
				}
		}
		else {
			nowJob = vec.back();
			vec.pop_back();
		}

		nowJob.beginTime = nowTime;
		nowJob.endTime = addTime(nowTime, nowJob.runTime);
		nowJob.waitTime = sumWaitTime;
		nowJob.turnaroundTime = sumWaitTime + nowJob.runTime;
		sortedJobs[pos++] = nowJob;

		nowTime = addTime(nowTime, nowJob.runTime);
		sumWaitTime += nowJob.runTime;
		cnt++;
	}
	for (int i = 0; i < jobSize; i++)
		jobs[i] = sortedJobs[i];
}

void jobScheduling::output() {
	cout << "【作业调度信息】\n";
	cout << "作业编号 | 作业名称 | 提交时间 | 要求服务运行时间 | 开始时间 | 完成时间 | 等待时间 | 周转时间\n";
	for (int i = 0; i < jobSize; i++) {
		cout.setf(ios::left);
		cout << "     " << setw(10) << jobs[i].num << setw(8) << jobs[i].name << setw(15) << jobs[i].submitTime << setw(15) << jobs[i].runTime;
		cout << setw(12) << jobs[i].beginTime << setw(12) << jobs[i].endTime << setw(12) << jobs[i].waitTime << jobs[i].turnaroundTime << endl;
	}
}

int main() {

	jobScheduling jobschedule;
	jobschedule.input();
	printf("FSFC：\n");
	jobschedule.FCFSschedule();
	jobschedule.output();
	printf("SJF：\n");
	jobschedule.SJFschedule();
	jobschedule.output();
	printf("PSA：\n");
	jobschedule.PSAschedule();
	jobschedule.output();

	return 0;
}