- 先来先服务
- 短过程优先算法
- 优先级调度（抢占）
- 优先级调度
#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;
}