最短作业优先 (SJF) 调度(非抢占式)的 C++ 程序
c++server side programmingprogramming更新于 2024/10/5 2:03:00
给定进程、进程的突发时间和量子限制；任务是使用最短作业优先调度非抢占式方法查找并打印等待时间、周转时间及其各自的平均时间。
什么是最短作业优先调度?
最短作业优先调度是遵循非抢占式调度原则的作业或进程调度算法。在此，调度程序从等待队列中选择完成时间最短的进程，并将 CPU 分配给该作业或进程。最短作业优先算法比先进先出算法更可取，因为最短作业优先算法更优化，因为它减少了平均等待时间，从而增加了吞吐量。
什么是周转时间、等待时间和完成时间?
- 完成时间是流程完成执行所需的时间
周转时间是流程提交和完成之间的时间间隔。
周转时间 = 流程完成 – 流程提交
等待时间是周转时间和突发时间之间的差值
等待时间 = 周转时间 –突发时间
示例
我们给出了进程 P1、P2、P3、P4 和 P5，它们对应的突发时间如下所示
| 进程 | 突发时间 |
|---|---|
| P1 | 4 |
| P2 | 2 |
| P3 | 8 |
| P4 | 1 |
| P5 | 9 |
由于进程 P4 的突发时间在所有进程中最小，因此将首先为其分配 CPU。之后，P2 将排队，然后是 P1、P3 和 P5。
平均等待时间是根据甘特图计算的。 P1 必须等待 3，P2 必须等待 1，P3 必须等待 7，P4 必须等待 0，P5 必须等待 15。因此，他们的平均等待时间将是 −
算法
开始
步骤 1-> 在函数 swap(int *a, int *b) 中
设置 temp = *a
设置 *a = *b
设置 *b = temp
步骤 2->在函数 accordionArrival(int num, int mat[][3]) 中
循环 For i=0 and i<num and i++
循环 For j=0 and j<num-i-1 and j++
如果 mat[1][j] > mat[1][j+1] 则，
对于 k=0 and k<5 and k++
调用函数 swap(mat[k][j], mat[k][j+1])
步骤 3->在函数completionTime(int num, int mat[][3])中
声明temp，val
设置mat[3][0] = mat[1][0] + mat[2][0]
设置mat[5][0] = mat[3][0] - mat[1][0]
设置mat[4][0] = mat[5][0] - mat[2][0]
循环For i=1 and i<num and i++
设置temp = mat[3][i-1]
设置low = mat[2][i]
循环For j=i and j<num and j++
如果 temp >= mat[1][j] && low >= mat[2][j] 则，
设置 low = mat[2][j]
设置 val = j
设置 mat[3][val] = temp + mat[2][val]
设置 mat[5][val] = mat[3][val] - mat[1][val]
设置 mat[4][val] = mat[5][val] - mat[2][val]
循环 For k=0; k<6; k++
调用函数 swap(mat[k][val], mat[k][i])
步骤 4-> 在函数 int main() 中
声明并设置 num = 3, temp
声明并设置 mat[6][3] = {1, 2, 3, 3, 6, 4, 2, 3, 4}
打印进程ID、到达时间、爆发时间
循环i=0 and i<num and i++
打印mat[0][i]、mat[1][i]、mat[2][i]的值
调用函数arrangeArrival(num, mat)
调用函数completionTime(num, mat)
打印进程ID、到达时间、爆发时间、等待时间、周转时间
循环i=0 and i<num and i++
打印 mat[0][i]、mat[1][i]、mat[2][i]、mat[4][i]、mat[5][i] 的值
停止
示例
// C++ 程序实现最短作业优先，并设置到达时间
#include<iostream>
using namespace std;
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void arrangeArrival(int num, int mat[][3]) {
for(int i=0; i<num; i++) {
for(int j=0; j<num-i-1; j++) {
if(mat[1][j] > mat[1][j+1]) {
for(int k=0; k<5; k++) {
swap(mat[k][j], mat[k][j+1]);
}
}
}
}
}
void completionTime(int num, int mat[][3]) {
int temp, val;
mat[3][0] = mat[1][0] + mat[2][0];
mat[5][0] = mat[3][0] - mat[1][0];
mat[4][0] = mat[5][0] - mat[2][0];
for(int i=1; i<num; i++) {
temp = mat[3][i-1];
int low = mat[2][i];
for(int j=i; j<num; j++) {
if(temp >= mat[1][j] && low >= mat[2][j]) {
low = mat[2][j];
val = j;
}
}
mat[3][val] = temp + mat[2][val];
mat[5][val] = mat[3][val] - mat[1][val];
mat[4][val] = mat[5][val] - mat[2][val];
for(int k=0; k<6; k++) {
swap(mat[k][val], mat[k][i]);
}
}
}
int main() {
int num = 3, temp;
int mat[6][3] = {1, 2, 3, 3, 6, 4, 2, 3, 4};
cout<<"Before Arrange...\n";
cout<<"Process ID\tArrival Time\tBurst Time\n";
for(int i=0; i<num; i++) {
cout<<mat[0][i]<<"\t\t"<<mat[1][i]<<"\t\t"<<mat[2][i]<<"\n";
}
arrangeArrival(num, mat);
completionTime(num, mat);
cout<<"Final Result...\n";
cout<<"Process ID\tArrival Time\tBurst Time\tWaiting Time\tTurnaround Time\n";
for(int i=0; i<num; i++) {
cout<<mat[0][i]<<"\t\t"<<mat[1][i]<<"\t\t"<<mat[2][i]<<"\t\t"<<mat[4][i]<<"\t\t"<<mat[5][i]<<"\n";
}
}
输出
