数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律C++ 最短作业优先（SJF）调度（抢占式）程序
给定进程、每个进程的突发时间和一个时间片限制；任务是使用最短作业优先抢占式方法找到并打印等待时间、周转时间及其各自的平均时间。
什么是最短作业优先调度？
最短作业优先调度是一种作业或进程调度算法，它遵循非抢占式调度规则。在这种调度中，调度程序从等待队列中选择完成时间最短的进程，并将 CPU 分配给该作业或进程。最短作业优先比先到先服务算法更受欢迎，因为它更优化，因为它减少了平均等待时间，从而提高了吞吐量。
SJF 算法可以是抢占式的，也可以是非抢占式的。抢占式调度也称为**最短剩余时间优先**调度。在抢占式方法中，当已经有正在执行的进程时，新的进程就会出现。如果新到达进程的突发时间小于正在执行进程的突发时间，则调度程序将抢占具有较短突发时间的进程的执行。
什么是周转时间、等待时间和完成时间？
- **完成时间**是进程完成执行所需的时间。
**周转时间**是进程提交到完成之间的时间间隔。
周转时间 = 进程完成时间 - 进程提交时间
**等待时间**是周转时间和突发时间之间的差值。
等待时间 = 周转时间 - 突发时间
示例
我们给出了进程 P1、P2、P3、P4 和 P5，以及它们相应的突发时间如下所示
| 进程 | 突发时间 | 到达时间 |
|---|---|---|
| P1 | 4 | 0 |
| P2 | 2 | 1 |
| P3 | 8 | 2 |
| P4 | 1 | 3 |
| P5 | 9 | 4 |
由于 P1 的到达时间为 0，因此它将首先执行，直到另一个进程到达。当在 1 时，进程 P2 进入，并且 P2 的突发时间小于 P1 的突发时间，因此调度程序将把 CPU 分配给进程 P2，依此类推。
平均等待时间是根据甘特图计算的。P1 必须等待 (0+4)4，P2 必须等待 1，P3 必须等待 7，P4 必须等待 3，P5 必须等待 15。因此，它们的平均等待时间将为 -
算法
Start
Step 1-> Declare a struct Process
Declare pid, bt, art
Step 2-> In function findTurnAroundTime(Process proc[], int n, int wt[], int tat[])
Loop For i = 0 and i < n and i++
Set tat[i] = proc[i].bt + wt[i]
Step 3-> In function findWaitingTime(Process proc[], int n, int wt[])
Declare rt[n]
Loop For i = 0 and i < n and i++
Set rt[i] = proc[i].bt
Set complete = 0, t = 0, minm = INT_MAX
Set shortest = 0, finish_time
Set bool check = false
Loop While (complete != n)
Loop For j = 0 and j < n and j++
If (proc[j].art <= t) && (rt[j] < minm) && rt[j] > 0 then,
Set minm = rt[j]
Set shortest = j
Set check = true
If check == false then,
Increment t by 1
Continue
Decrement the value of rt[shortest] by 1
Set minm = rt[shortest]
If minm == 0 then,
Set minm = INT_MAX
If rt[shortest] == 0 then,
Increment complete by 1
Set check = false
Set finish_time = t + 1
Set wt[shortest] = finish_time - proc[shortest].bt -proc[shortest].art
If wt[shortest] < 0
Set wt[shortest] = 0
Increment t by 1
Step 4-> In function findavgTime(Process proc[], int n)
Declare and set wt[n], tat[n], total_wt = 0, total_tat = 0
Call findWaitingTime(proc, n, wt)
Call findTurnAroundTime(proc, n, wt, tat)
Loop For i = 0 and i < n and i++
Set total_wt = total_wt + wt[i]
Set total_tat = total_tat + tat[i]
Print proc[i].pid, proc[i].bt, wt[i], tat[i]
Print Average waiting time i.e., total_wt / n
Print Average turn around time i.e., total_tat / n
Step 5-> In function int main()
Declare and set Process proc[] = { { 1, 5, 1 }, { 2, 3, 1 }, { 3, 6, 2 }, { 4, 5, 3 } }
Set n = sizeof(proc) / sizeof(proc[0])
Call findavgTime(proc, n)
Stop示例
#include <bits/stdc++.h>
using namespace std;
//structure for every process
struct Process {
int pid; // Process ID
int bt; // Burst Time
int art; // Arrival Time
};
void findTurnAroundTime(Process proc[], int n, int wt[], int tat[]) {
for (int i = 0; i < n; i++)
tat[i] = proc[i].bt + wt[i];
}
//waiting time of all process
void findWaitingTime(Process proc[], int n, int wt[]) {
int rt[n];
for (int i = 0; i < n; i++)
rt[i] = proc[i].bt;
int complete = 0, t = 0, minm = INT_MAX;
int shortest = 0, finish_time;
bool check = false;
while (complete != n) {
for (int j = 0; j < n; j++) {
if ((proc[j].art <= t) && (rt[j] < minm) && rt[j] > 0) {
minm = rt[j];
shortest = j;
check = true;
}
}
if (check == false) {
t++;
continue;
}
// decrementing the remaining time
rt[shortest]--;
minm = rt[shortest];
if (minm == 0)
minm = INT_MAX;
// If a process gets completely
// executed
if (rt[shortest] == 0) {
complete++;
check = false;
finish_time = t + 1;
// Calculate waiting time
wt[shortest] = finish_time -
proc[shortest].bt -
proc[shortest].art;
if (wt[shortest] < 0)
wt[shortest] = 0;
}
// Increment time
t++;
}
}
// Function to calculate average time
void findavgTime(Process proc[], int n) {
int wt[n], tat[n], total_wt = 0,
total_tat = 0;
// Function to find waiting time of all
// processes
findWaitingTime(proc, n, wt);
// Function to find turn around time for
// all processes
findTurnAroundTime(proc, n, wt, tat);
cout << "Processes " << " Burst time " << " Waiting time " << " Turn around time\n";
for (int i = 0; i < n; i++) {
total_wt = total_wt + wt[i];
total_tat = total_tat + tat[i];
cout << " " << proc[i].pid << "\t\t" << proc[i].bt << "\t\t " << wt[i] << "\t\t " << tat[i] << endl;
}
cout << "\nAverage waiting time = " << (float)total_wt / (float)n; cout << "\nAverage turn around time = " << (float)total_tat / (float)n;
}
// main function
int main() {
Process proc[] = { { 1, 5, 1 }, { 2, 3, 1 }, { 3, 6, 2 }, { 4, 5, 3 } };
int n = sizeof(proc) / sizeof(proc[0]);
findavgTime(proc, n);
return 0;
}输出
更新于： 2019-12-23
17K+ 浏览量
广告