抢占式SJF算法c++代码
时间: 2024-04-02 21:29:33 浏览: 27
抢占式短作业优先(Shortest Job First, SJF)算法是一种调度算法,它根据作业的执行时间来确定优先级,执行时间越短的作业优先级越高。而抢占式SJF算法则是在作业执行过程中,如果有更短的作业到达,则可以抢占当前正在执行的作业。
以下是一个简单的抢占式SJF算法的C++代码示例:
```cpp
#include <iostream>
#include <queue>
using namespace std;
struct Process {
int id; // 进程ID
int arrival; // 到达时间
int burst; // 执行时间
};
// 按到达时间排序的比较函数
struct CompareArrival {
bool operator()(const Process& p1, const Process& p2) {
return p1.arrival > p2.arrival;
}
};
// 按执行时间排序的比较函数
struct CompareBurst {
bool operator()(const Process& p1, const Process& p2) {
return p1.burst > p2.burst;
}
};
void preemptiveSJF(vector<Process>& processes) {
priority_queue<Process, vector<Process>, CompareBurst> readyQueue; // 就绪队列
int currentTime = 0; // 当前时间
int n = processes.size();
int completed = 0; // 已完成的进程数量
while (completed < n) {
// 将到达时间小于等于当前时间的进程加入就绪队列
for (int i = 0; i < n; i++) {
if (processes[i].arrival <= currentTime && processes[i].burst > 0) {
readyQueue.push(processes[i]);
processes[i].burst = 0; // 标记为已加入就绪队列
}
}
if (!readyQueue.empty()) {
Process currentProcess = readyQueue.top();
readyQueue.pop();
cout << "执行进程 " << currentProcess.id << ",执行时间:" << currentTime << " - " << currentTime + 1 << endl;
currentProcess.burst--;
if (currentProcess.burst == 0) {
completed++;
cout << "进程 " << currentProcess.id << " 执行完毕" << endl;
} else {
readyQueue.push(currentProcess);
}
} else {
cout << "当前时间:" << currentTime << ",无进程执行" << endl;
}
currentTime++;
}
}
int main() {
vector<Process> processes = {
{1, 0, 6},
{2, 2, 4},
{3, 4, 2},
{4, 6, 8},
{5, 8, 10}
};
preemptiveSJF(processes);
return 0;
}
```
这段代码实现了一个简单的抢占式SJF调度算法。它使用了两个优先队列,一个按到达时间排序,一个按执行时间排序。在每个时间片内,根据当前时间和到达时间将进程加入就绪队列,并选择执行时间最短的进程执行。如果有更短的进程到达,则抢占当前正在执行的进程。输出结果显示了每个时间片内执行的进程。