435 lines
16 KiB
C++
435 lines
16 KiB
C++
#include <iostream>
|
||
#include <vector>
|
||
#include <queue>
|
||
#include <algorithm>
|
||
#include <iomanip>
|
||
#include <climits>
|
||
using namespace std;
|
||
|
||
// 进程结构体
|
||
struct Process {
|
||
int pid; // 进程ID
|
||
int arrivalTime; // 到达时间
|
||
int burstTime; // 服务时间
|
||
int priority; // 优先级(数值越小优先级越高)
|
||
int remainingTime; // 剩余时间
|
||
int finishTime; // 完成时间
|
||
int turnaroundTime; // 周转时间
|
||
int waitingTime; // 等待时间
|
||
double responseRatio; // 响应比(用于HRRN)
|
||
|
||
Process(int p, int a, int b, int pr = 0) {
|
||
pid = p;
|
||
arrivalTime = a;
|
||
burstTime = b;
|
||
priority = pr;
|
||
remainingTime = b;
|
||
finishTime = 0;
|
||
turnaroundTime = 0;
|
||
waitingTime = 0;
|
||
responseRatio = 0.0;
|
||
}
|
||
};
|
||
|
||
class CPUScheduler {
|
||
private:
|
||
vector<Process> processes;
|
||
vector<Process> originalProcesses;
|
||
|
||
public:
|
||
// 添加进程
|
||
void addProcess(int pid, int arrivalTime, int burstTime, int priority = 0) {
|
||
processes.push_back(Process(pid, arrivalTime, burstTime, priority));
|
||
originalProcesses.push_back(Process(pid, arrivalTime, burstTime, priority));
|
||
}
|
||
|
||
// 重置进程状态
|
||
void resetProcesses() {
|
||
processes = originalProcesses;
|
||
for (auto& p : processes) {
|
||
p.remainingTime = p.burstTime;
|
||
p.finishTime = 0;
|
||
p.turnaroundTime = 0;
|
||
p.waitingTime = 0;
|
||
p.responseRatio = 0.0;
|
||
}
|
||
}
|
||
|
||
// 先来先服务(FCFS)算法
|
||
void FCFS() {
|
||
cout << "\n========== 先来先服务(FCFS)调度算法 ==========\n";
|
||
resetProcesses();
|
||
|
||
// 按到达时间排序
|
||
sort(processes.begin(), processes.end(),
|
||
[](const Process& a, const Process& b) {
|
||
return a.arrivalTime < b.arrivalTime;
|
||
});
|
||
|
||
int currentTime = 0;
|
||
cout << "执行顺序: ";
|
||
|
||
for (auto& p : processes) {
|
||
// 如果当前时间小于进程到达时间，CPU空闲
|
||
if (currentTime < p.arrivalTime) {
|
||
currentTime = p.arrivalTime;
|
||
}
|
||
|
||
cout << "P" << p.pid << " ";
|
||
currentTime += p.burstTime;
|
||
p.finishTime = currentTime;
|
||
p.turnaroundTime = p.finishTime - p.arrivalTime;
|
||
p.waitingTime = p.turnaroundTime - p.burstTime;
|
||
}
|
||
cout << "\n";
|
||
|
||
printResults();
|
||
}
|
||
|
||
// 最短作业优先(SJF)算法
|
||
void SJF() {
|
||
cout << "\n========== 最短作业优先(SJF)调度算法 ==========\n";
|
||
resetProcesses();
|
||
|
||
vector<Process> readyQueue;
|
||
vector<Process> completed;
|
||
int currentTime = 0;
|
||
cout << "执行顺序: ";
|
||
|
||
while (completed.size() < processes.size()) {
|
||
// 将已到达的进程加入就绪队列
|
||
for (auto& p : processes) {
|
||
if (p.arrivalTime <= currentTime && p.finishTime == 0) {
|
||
bool inQueue = false;
|
||
for (const auto& q : readyQueue) {
|
||
if (q.pid == p.pid) {
|
||
inQueue = true;
|
||
break;
|
||
}
|
||
}
|
||
if (!inQueue) {
|
||
readyQueue.push_back(p);
|
||
}
|
||
}
|
||
}
|
||
|
||
if (!readyQueue.empty()) {
|
||
// 选择服务时间最短的进程
|
||
auto shortestJob = min_element(readyQueue.begin(), readyQueue.end(),
|
||
[](const Process& a, const Process& b) {
|
||
return a.burstTime < b.burstTime;
|
||
});
|
||
|
||
cout << "P" << shortestJob->pid << " ";
|
||
currentTime += shortestJob->burstTime;
|
||
|
||
// 更新原进程信息
|
||
for (auto& p : processes) {
|
||
if (p.pid == shortestJob->pid) {
|
||
p.finishTime = currentTime;
|
||
p.turnaroundTime = p.finishTime - p.arrivalTime;
|
||
p.waitingTime = p.turnaroundTime - p.burstTime;
|
||
completed.push_back(p);
|
||
break;
|
||
}
|
||
}
|
||
|
||
// 从就绪队列中移除已完成的进程
|
||
readyQueue.erase(shortestJob);
|
||
} else {
|
||
currentTime++;
|
||
}
|
||
}
|
||
cout << "\n";
|
||
|
||
printResults();
|
||
}
|
||
|
||
// 最短剩余时间优先(SRTF)算法
|
||
void SRTF() {
|
||
cout << "\n========== 最短剩余时间优先(SRTF)调度算法 ==========\n";
|
||
resetProcesses();
|
||
|
||
int currentTime = 0;
|
||
int completed = 0;
|
||
vector<int> executionOrder;
|
||
|
||
while (completed < processes.size()) {
|
||
int shortestIdx = -1;
|
||
int shortestTime = INT_MAX;
|
||
|
||
// 找到当前时间已到达且剩余时间最短的进程
|
||
for (int i = 0; i < processes.size(); i++) {
|
||
if (processes[i].arrivalTime <= currentTime &&
|
||
processes[i].remainingTime > 0 &&
|
||
processes[i].remainingTime < shortestTime) {
|
||
shortestTime = processes[i].remainingTime;
|
||
shortestIdx = i;
|
||
}
|
||
}
|
||
|
||
if (shortestIdx == -1) {
|
||
currentTime++;
|
||
continue;
|
||
}
|
||
|
||
// 执行选中的进程1个时间单位
|
||
executionOrder.push_back(processes[shortestIdx].pid);
|
||
processes[shortestIdx].remainingTime--;
|
||
currentTime++;
|
||
|
||
// 如果进程完成
|
||
if (processes[shortestIdx].remainingTime == 0) {
|
||
processes[shortestIdx].finishTime = currentTime;
|
||
processes[shortestIdx].turnaroundTime =
|
||
processes[shortestIdx].finishTime - processes[shortestIdx].arrivalTime;
|
||
processes[shortestIdx].waitingTime =
|
||
processes[shortestIdx].turnaroundTime - processes[shortestIdx].burstTime;
|
||
completed++;
|
||
}
|
||
}
|
||
|
||
// 输出执行顺序(去重连续相同的进程)
|
||
cout << "执行顺序: ";
|
||
if (!executionOrder.empty()) {
|
||
cout << "P" << executionOrder[0];
|
||
for (int i = 1; i < executionOrder.size(); i++) {
|
||
if (executionOrder[i] != executionOrder[i-1]) {
|
||
cout << " P" << executionOrder[i];
|
||
}
|
||
}
|
||
}
|
||
cout << "\n";
|
||
|
||
printResults();
|
||
}
|
||
|
||
// 最高响应比优先(HRRN)算法
|
||
void HRRN() {
|
||
cout << "\n========== 最高响应比优先(HRRN)调度算法 ==========\n";
|
||
resetProcesses();
|
||
|
||
vector<Process> completed;
|
||
int currentTime = 0;
|
||
cout << "执行顺序: ";
|
||
|
||
while (completed.size() < processes.size()) {
|
||
vector<int> readyQueue;
|
||
|
||
// 找到所有已到达且未完成的进程
|
||
for (int i = 0; i < processes.size(); i++) {
|
||
if (processes[i].arrivalTime <= currentTime && processes[i].finishTime == 0) {
|
||
readyQueue.push_back(i);
|
||
}
|
||
}
|
||
|
||
if (!readyQueue.empty()) {
|
||
// 计算响应比并选择最高的
|
||
int selectedIdx = -1;
|
||
double highestRatio = 0.0;
|
||
|
||
for (int idx : readyQueue) {
|
||
int waitTime = currentTime - processes[idx].arrivalTime;
|
||
processes[idx].responseRatio =
|
||
(double)(waitTime + processes[idx].burstTime) / processes[idx].burstTime;
|
||
|
||
if (processes[idx].responseRatio > highestRatio) {
|
||
highestRatio = processes[idx].responseRatio;
|
||
selectedIdx = idx;
|
||
}
|
||
}
|
||
|
||
cout << "P" << processes[selectedIdx].pid << " ";
|
||
currentTime += processes[selectedIdx].burstTime;
|
||
processes[selectedIdx].finishTime = currentTime;
|
||
processes[selectedIdx].turnaroundTime =
|
||
processes[selectedIdx].finishTime - processes[selectedIdx].arrivalTime;
|
||
processes[selectedIdx].waitingTime =
|
||
processes[selectedIdx].turnaroundTime - processes[selectedIdx].burstTime;
|
||
completed.push_back(processes[selectedIdx]);
|
||
} else {
|
||
currentTime++;
|
||
}
|
||
}
|
||
cout << "\n";
|
||
|
||
printResults();
|
||
}
|
||
|
||
// 时间片轮转(RR)算法
|
||
void RR(int timeQuantum = 2) {
|
||
cout << "\n========== 时间片轮转(RR)调度算法 (时间片=" << timeQuantum << ") ==========\n";
|
||
resetProcesses();
|
||
|
||
queue<int> readyQueue;
|
||
vector<bool> inQueue(processes.size(), false);
|
||
int currentTime = 0;
|
||
int completed = 0;
|
||
cout << "执行顺序: ";
|
||
|
||
// 将时间0到达的进程加入队列
|
||
for (int i = 0; i < processes.size(); i++) {
|
||
if (processes[i].arrivalTime <= currentTime) {
|
||
readyQueue.push(i);
|
||
inQueue[i] = true;
|
||
}
|
||
}
|
||
|
||
while (completed < processes.size()) {
|
||
if (readyQueue.empty()) {
|
||
currentTime++;
|
||
// 检查是否有新进程到达
|
||
for (int i = 0; i < processes.size(); i++) {
|
||
if (processes[i].arrivalTime <= currentTime &&
|
||
!inQueue[i] && processes[i].remainingTime > 0) {
|
||
readyQueue.push(i);
|
||
inQueue[i] = true;
|
||
}
|
||
}
|
||
continue;
|
||
}
|
||
|
||
int currentProcess = readyQueue.front();
|
||
readyQueue.pop();
|
||
inQueue[currentProcess] = false;
|
||
|
||
cout << "P" << processes[currentProcess].pid << " ";
|
||
|
||
// 执行时间片或直到进程完成
|
||
int executeTime = min(timeQuantum, processes[currentProcess].remainingTime);
|
||
currentTime += executeTime;
|
||
processes[currentProcess].remainingTime -= executeTime;
|
||
|
||
// 将在执行期间到达的进程加入队列
|
||
for (int i = 0; i < processes.size(); i++) {
|
||
if (processes[i].arrivalTime <= currentTime &&
|
||
!inQueue[i] && processes[i].remainingTime > 0 && i != currentProcess) {
|
||
readyQueue.push(i);
|
||
inQueue[i] = true;
|
||
}
|
||
}
|
||
|
||
// 如果当前进程还未完成，重新加入队列
|
||
if (processes[currentProcess].remainingTime > 0) {
|
||
readyQueue.push(currentProcess);
|
||
inQueue[currentProcess] = true;
|
||
} else {
|
||
// 进程完成
|
||
processes[currentProcess].finishTime = currentTime;
|
||
processes[currentProcess].turnaroundTime =
|
||
processes[currentProcess].finishTime - processes[currentProcess].arrivalTime;
|
||
processes[currentProcess].waitingTime =
|
||
processes[currentProcess].turnaroundTime - processes[currentProcess].burstTime;
|
||
completed++;
|
||
}
|
||
}
|
||
cout << "\n";
|
||
|
||
printResults();
|
||
}
|
||
|
||
// 优先级调度算法(非抢占)
|
||
void PriorityScheduling() {
|
||
cout << "\n========== 优先级调度算法(非抢占) ==========\n";
|
||
resetProcesses();
|
||
|
||
vector<Process> completed;
|
||
int currentTime = 0;
|
||
cout << "执行顺序: ";
|
||
|
||
while (completed.size() < processes.size()) {
|
||
vector<int> readyQueue;
|
||
|
||
// 找到所有已到达且未完成的进程
|
||
for (int i = 0; i < processes.size(); i++) {
|
||
if (processes[i].arrivalTime <= currentTime && processes[i].finishTime == 0) {
|
||
readyQueue.push_back(i);
|
||
}
|
||
}
|
||
|
||
if (!readyQueue.empty()) {
|
||
// 选择优先级最高的进程(数值最小)
|
||
int selectedIdx = readyQueue[0];
|
||
for (int idx : readyQueue) {
|
||
if (processes[idx].priority < processes[selectedIdx].priority) {
|
||
selectedIdx = idx;
|
||
}
|
||
}
|
||
|
||
cout << "P" << processes[selectedIdx].pid << " ";
|
||
currentTime += processes[selectedIdx].burstTime;
|
||
processes[selectedIdx].finishTime = currentTime;
|
||
processes[selectedIdx].turnaroundTime =
|
||
processes[selectedIdx].finishTime - processes[selectedIdx].arrivalTime;
|
||
processes[selectedIdx].waitingTime =
|
||
processes[selectedIdx].turnaroundTime - processes[selectedIdx].burstTime;
|
||
completed.push_back(processes[selectedIdx]);
|
||
} else {
|
||
currentTime++;
|
||
}
|
||
}
|
||
cout << "\n";
|
||
|
||
printResults();
|
||
}
|
||
|
||
// 打印结果
|
||
void printResults() {
|
||
cout << "\n进程调度结果:\n";
|
||
cout << "进程ID\t到达时间\t服务时间\t完成时间\t周转时间\t等待时间\n";
|
||
cout << "--------------------------------------------------------------\n";
|
||
|
||
double totalTurnaround = 0, totalWaiting = 0;
|
||
|
||
for (const auto& p : processes) {
|
||
cout << "P" << p.pid << "\t" << p.arrivalTime << "\t\t"
|
||
<< p.burstTime << "\t\t" << p.finishTime << "\t\t"
|
||
<< p.turnaroundTime << "\t\t" << p.waitingTime << "\n";
|
||
totalTurnaround += p.turnaroundTime;
|
||
totalWaiting += p.waitingTime;
|
||
}
|
||
|
||
cout << "--------------------------------------------------------------\n";
|
||
cout << fixed << setprecision(2);
|
||
cout << "平均周转时间: " << totalTurnaround / processes.size() << "\n";
|
||
cout << "平均等待时间: " << totalWaiting / processes.size() << "\n";
|
||
}
|
||
|
||
// 显示所有进程信息
|
||
void displayProcesses() {
|
||
cout << "\n当前进程信息:\n";
|
||
cout << "进程ID\t到达时间\t服务时间\t优先级\n";
|
||
cout << "----------------------------------------\n";
|
||
for (const auto& p : originalProcesses) {
|
||
cout << "P" << p.pid << "\t" << p.arrivalTime << "\t\t"
|
||
<< p.burstTime << "\t\t" << p.priority << "\n";
|
||
}
|
||
}
|
||
};
|
||
|
||
int main() {
|
||
CPUScheduler scheduler;
|
||
|
||
cout << "处理机调度算法实验\n";
|
||
cout << "==================\n";
|
||
|
||
// 示例进程数据
|
||
cout << "使用示例进程数据进行测试:\n";
|
||
scheduler.addProcess(1, 0, 8, 3); // 进程P1: 到达时间0, 服务时间8, 优先级3
|
||
scheduler.addProcess(2, 1, 4, 1); // 进程P2: 到达时间1, 服务时间4, 优先级1
|
||
scheduler.addProcess(3, 2, 2, 4); // 进程P3: 到达时间2, 服务时间2, 优先级4
|
||
scheduler.addProcess(4, 3, 1, 2); // 进程P4: 到达时间3, 服务时间1, 优先级2
|
||
scheduler.addProcess(5, 4, 3, 5); // 进程P5: 到达时间4, 服务时间3, 优先级5
|
||
|
||
scheduler.displayProcesses();
|
||
|
||
// 执行各种调度算法
|
||
scheduler.FCFS();
|
||
scheduler.SJF();
|
||
scheduler.SRTF();
|
||
scheduler.HRRN();
|
||
scheduler.RR(2);
|
||
scheduler.PriorityScheduling();
|
||
|
||
return 0;
|
||
} |