- 先来先服务
- 短进程优先算法
- 优先级调度（抢占）
- 优先级调度
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct PCB
{
int id; // 进程id
double turnaround_time; // 周转时间
double weighted_turnaround_time; // 带权周转时间
double wait_time; // 等待时间
double start_time; // 开始时间
double coming_time; // 到达时间
double service_time; // 运行时间
double finish_time; // 完成时间
int youxianji; // 优先级
double run_time; // 已运行时间
};
int n; // 进程个数
vector<PCB> process_list; // 输入的进程序列
vector<PCB> res; // 待输出的结果队列
void input_process_count()
{
printf("请输入进程数量：");
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
PCB pcb; // pcb初始化
pcb.id = i + 1;
pcb.run_time = 0; // 初始时已运行时间为零
pcb.start_time = -1; // 为判断是否第一次到达
process_list.push_back(pcb); // 加入已初始化好的pcb
}
}
void input_youxianshu() // 输入优先级
{
for (int i = 0; i < n; i++)
{
printf("请输入进程%d的优先级：", process_list[i].id);
scanf("%d", &process_list[i].youxianji);
}
}
void input_coming_time() // 输入到达时间
{
for (int i = 0; i < n; i++)
{
printf("请输入进程%d的到达时间：", process_list[i].id);
scanf("%lf", &process_list[i].coming_time);
}
}
void input_serve_time() // 输入需要服务时间
{
for (int i = 0; i < n; i++)
{
printf("请输入进程%d所需时间", process_list[i].id);
scanf("%lf", &process_list[i].service_time);
}
}
int choose_method() // 输入选择的算法
{
int select = 0;
cout << "*****************************************\n";
cout << "1 \t 先来先服务算法 *******\n";
cout << "2 \t 短进程优先算法 *******\n";
cout << "3 \t 优先级调度(抢占) *******\n";
cout << "4 \t 优先级调度(非抢占) *******\n";
cout << "请选择: ";
cin >> select;
return select;
}
int cmpByComingTime(PCB a, PCB b) // 按照到达时间从小到大排序
{
return a.coming_time < b.coming_time;
}
int cmpByServiceTime(PCB a, PCB b) // 按照需要服务时间从大到小排序
{
return a.service_time > b.service_time;
}
void FCFS()
{
sort(process_list.begin(), process_list.end(), cmpByComingTime); // 先按照到达时间排序
double time = process_list[0].coming_time; // 初始化时间
for (int i = 0; i < n; i++)
{
PCB pcb = process_list[i]; // 因为已经按照时间排序，所以当前为待运行的进程
// 更新当前进程的信息
pcb.start_time = time;
pcb.wait_time = time - pcb.coming_time;
pcb.finish_time = time + pcb.service_time;
pcb.turnaround_time = pcb.finish_time - pcb.coming_time;
pcb.weighted_turnaround_time = (pcb.turnaround_time) / pcb.service_time;
time = pcb.finish_time; // 以当前进程的时间更新time
process_list[i] = pcb;
res.push_back(pcb); // 加入结果队列
}
}
void SJF()
{
int top = 0;
vector<PCB> short_jobs; // 定义短进程队列 其中数据由大到小
sort(process_list.begin(), process_list.end(), cmpByComingTime); // 按照到达时间初始化
double time = process_list[0].coming_time; // 初始化时间
while (top < n || !short_jobs.empty()) // 如果两个对列里仍然存在元素
{
if (short_jobs.empty()) // 如果队列未空，则加入当前已经到达的进程
short_jobs.push_back(process_list[top++]);
PCB pcb = short_jobs[int(short_jobs.size() - 1)]; // 取出时间最短的
if (pcb.start_time == -1)
pcb.start_time = time;
// 更新pcb的时间
pcb.wait_time = time - pcb.coming_time;
pcb.finish_time = time + pcb.service_time;
pcb.turnaround_time = pcb.finish_time - pcb.coming_time;
pcb.weighted_turnaround_time = (pcb.turnaround_time) / pcb.service_time;
time = pcb.finish_time;
// 加入到运行结束队列
res.push_back(pcb);
short_jobs.pop_back();
// 如果在上个进程运行期间有进程到达则加入short_jobs队列
for (; top < n && process_list[top].coming_time < time; top++)
{
short_jobs.push_back(process_list[top]);
}
// 因为有新的进程加入，所以对short_jobs进行排序
sort(short_jobs.begin(), short_jobs.end(), cmpByComingTime);
}
}
bool cmpByPriority(PCB a, PCB b) // 按照优先级排序
{
if (a.youxianji == b.youxianji)
return a.coming_time > b.coming_time;
return a.youxianji < b.youxianji;
}
void PriorityNo() // 非抢占优先级调度
{
int top = 0; // 定义头指针
vector<PCB> priority_higher;
sort(process_list.begin(), process_list.end(), cmpByComingTime);
double time = process_list[0].coming_time;
while (top < n || !priority_higher.empty()) // 如果仍有进程未运行结束
{
if (priority_higher.empty()) // 为空则加入新的进程
priority_higher.push_back(process_list[top++]);
PCB pcb = priority_higher[int(priority_higher.size() - 1)]; // 取出要运行的进程
if (pcb.start_time == -1) //如果是第一次抵达则更新时间
pcb.start_time = time;
// 更新pcb
pcb.wait_time = time - pcb.coming_time;
pcb.finish_time = time + pcb.service_time;
pcb.turnaround_time = pcb.finish_time - pcb.coming_time;
pcb.weighted_turnaround_time = (pcb.turnaround_time) / pcb.service_time;
time = pcb.finish_time;
res.push_back(pcb); // 运行结束则加入res
priority_higher.pop_back(); // 并删除已运行结束的进程
for (; top < n && process_list[top].coming_time < time; top++)
{ // 加入在此期间到达的进程
priority_higher.push_back(process_list[top]);
}
// 因为有新进程加入，进行排序
sort(priority_higher.begin(), priority_higher.end(), cmpByPriority);
}
}
void PriorityYes()
{
int top = 0;
vector<PCB> priority_higher;
sort(process_list.begin(), process_list.end(), cmpByComingTime);
double time = process_list[0].coming_time; // 初始化时间
while (top < n || !priority_higher.empty()) // 如果仍有进程未结束
{
if (priority_higher.empty()) // 如果为空，则加入新的进程
priority_higher.push_back(process_list[top++]);
PCB pcb = priority_higher[int(priority_higher.size() - 1)]; // 取出优先级最高的进程运行
if (pcb.start_time == -1) // 如果是第一次到达，则记录开始时间
{
pcb.start_time = time;
pcb.wait_time = pcb.start_time - pcb.coming_time;
}
if (top < n && process_list[top].coming_time <= time + pcb.service_time - pcb.run_time) // 如果仍有未加入的进程, 并且在运行期间有新的进程到达
{
pcb.run_time += process_list[top].coming_time - time; // 则先运行距离下个进程到达的时间
time += process_list[top].coming_time - time; // 并更新时间
priority_higher[priority_higher.size() - 1] = pcb; // 更新队列
priority_higher.push_back(process_list[top++]); // 把下一个进程加入
sort(priority_higher.begin(), priority_higher.end(), cmpByPriority); // 并进行排序
if (pcb.run_time == pcb.service_time) // 如果当前进程的运行时间已经够了，则更新pcb信息，并删除进程
{
pcb.finish_time = time;
pcb.turnaround_time = pcb.finish_time - pcb.coming_time;
pcb.weighted_turnaround_time = (pcb.turnaround_time) / pcb.service_time;
res.push_back(pcb);
priority_higher.pop_back();
}
}
else // 如果没有新的进程到达, 则将当前进程运行完毕
{
pcb.finish_time = time + pcb.service_time - pcb.run_time;
pcb.turnaround_time = pcb.finish_time - pcb.coming_time;
pcb.weighted_turnaround_time = (pcb.turnaround_time) / pcb.service_time;
time = time + pcb.service_time - pcb.run_time;
res.push_back(pcb); // 运行完毕则加入res
priority_higher.pop_back();
}
}
}
bool cmpById(PCB a, PCB b)
{
return a.id < b.id;
}
void print_schedulInfo()
{
printf("进程编号\t提交时间\t运行时间\t开始时间\t等待时间\t完成时间\t周转时间\t带权周转时间\n");
// cout << res.size() << endl;
sort(res.begin(), res.end(), cmpById); // 按照ID排序
double start = 0x3f3f3f3f3f, end = 0;
double allTT = 0, allWTT = 0, runTime = 0;
for (int i = 0; i < n; i++)
{
PCB pcb = res[i];
start = min(start, pcb.start_time); // 得到开始时间
end = max(end, pcb.finish_time); // 所有进程结束时间
allTT += pcb.turnaround_time; // 总的周转时间
allWTT += pcb.weighted_turnaround_time; // 总的带权周转时间
runTime += pcb.service_time; // 总的服务时间
printf("%8d\t%8.2f\t%8.2f\t%8.2f\t%8.2f\t%8.2f\t%8.2f\t%8.2f\n", pcb.id, pcb.coming_time, pcb.service_time, pcb.start_time, pcb.wait_time, pcb.finish_time, pcb.turnaround_time, pcb.weighted_turnaround_time);
}
printf("平均周转时间%.2f\t平均带权周转时间%.2f\tCPU利用率%.2f\t系统吞吐量%.2f\n", allTT / n, allWTT / n, (runTime) / (end - start), (n) / (end - start));
}
int main()
{
// 4 1 1 1 1 9 8 8.4 8.8 0.2 2 1 0.5
// 4 2 4 3 1 10 20 30 50 20 30 25 20
// 4 1 2 3 2 0 2 4 5 7 4 1 4
input_process_count(); // 输出进程数量
input_youxianshu(); // 输入优先级数
input_coming_time(); // 输入到达时间
input_serve_time(); // 输入需要服务时间
int choose = choose_method(); // 得到用户选择的数
// printf("%d\n", choose);
switch (choose)
{
case 1:
FCFS(); // 先来先服务
break;
case 2:
SJF(); // 短作业优先
break;
case 3:
PriorityYes(); // 优先级抢占式
break;
default:
PriorityNo(); // 优先级非抢占式
break;
}
print_schedulInfo(); // 打印结果
return 0;
}
