資料結構
網路
關係資料庫管理系統 (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+ 次瀏覽
廣告