数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++ 最短作业优先 (SJF) 调度算法 (非抢占式)
给定进程及其各自的突发时间和时间片限制；任务是使用非抢占式最短作业优先调度方法查找并打印等待时间、周转时间及其各自的平均时间。
什么是最短作业优先调度？
最短作业优先调度是一种作业或进程调度算法，它遵循非抢占式调度规则。在此调度中，调度程序从等待队列中选择完成时间最短的进程，并将 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 个时间单位。因此，它们的平均等待时间将是：
算法
Start
Step 1-> In function swap(int *a, int *b)
Set temp = *a
Set *a = *b
Set *b = temp
Step 2-> In function arrangeArrival(int num, int mat[][3])
Loop For i=0 and i<num and i++
Loop For j=0 and j<num-i-1 and j++
If mat[1][j] > mat[1][j+1] then,
For k=0 and k<5 and k++
Call function swap(mat[k][j], mat[k][j+1])
Step 3-> In function completionTime(int num, int mat[][3])
Declare temp, val
Set mat[3][0] = mat[1][0] + mat[2][0]
Set mat[5][0] = mat[3][0] - mat[1][0]
Set mat[4][0] = mat[5][0] - mat[2][0]
Loop For i=1 and i<num and i++
Set temp = mat[3][i-1]
Set low = mat[2][i]
Loop For j=i and j<num and j++
If temp >= mat[1][j] && low >= mat[2][j] then,
Set low = mat[2][j]
Set val = j
Set mat[3][val] = temp + mat[2][val]
Set mat[5][val] = mat[3][val] - mat[1][val]
Set mat[4][val] = mat[5][val] - mat[2][val]
Loop For k=0; k<6; k++
Call function swap(mat[k][val], mat[k][i])
Step 4-> In function int main()
Declare and set num = 3, temp
Declare and set mat[6][3] = {1, 2, 3, 3, 6, 4, 2, 3, 4}
Print Process ID, Arrival Time, Burst Time
Loop For i=0 and i<num and i++
Print the values of mat[0][i], mat[1][i], mat[2][i]
Call function arrangeArrival(num, mat)
Call function completionTime(num, mat)
Print Process ID, Arrival Time, Burst Time, Waiting Time, Turnaround Time
Loop For i=0 and i<num and i++
Print the values of mat[0][i], mat[1][i], mat[2][i], mat[4][i], mat[5][i]
Stop示例
// C++ program to implement Shortest Job first with Arrival Time
#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";
}
}输出
更新于：2019-12-23
6K+ 次浏览
广告