数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法律学C 语言实现循环调度算法
给定 n 个进程及其对应的突发时间和时间片，任务是找到平均等待时间和平均周转时间并显示结果。
什么是循环调度算法？
循环调度是一种 CPU 调度算法，专门为分时系统设计。它类似于先来先服务 (FCFS) 调度算法，但有一点不同：在循环调度中，进程会受到时间片大小的限制。一个时间单位称为时间片或时间量子。时间片可以从 10 到 100 毫秒不等。CPU 将就绪队列视为一个循环队列，以给定的时间片执行进程。它遵循抢占式方法，因为会为进程分配固定时间。它的唯一缺点是上下文切换的开销。
我们需要计算什么？
**完成时间**是进程完成执行所需的时间。
**周转时间**是进程提交到完成之间的时间间隔。
周转时间 = 进程完成时间 – 进程提交时间
等待时间是周转时间和突发时间之间的差值。
等待时间 = 周转时间 – 突发时间
示例
给定 3 个进程 P1、P2 和 P3，其对应的突发时间分别为 24、3 和 3。
| 进程 | 突发时间 |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
由于时间片为 4 毫秒，进程 P1 获得前 4 毫秒，但它还需要另外 20 毫秒才能完成执行，但 CPU 将在第一个时间片后抢占它，并将 CPU 分配给下一个进程 P2。如表所示，进程 P2 仅需 3 毫秒即可完成执行，因此 CPU 将仅分配 3 毫秒的时间片，而不是 4 毫秒。
使用甘特图，平均等待时间计算如下：
平均等待时间 = 17/3 = 5.66 毫秒
算法
Start
Step 1-> In function int turnarroundtime(int processes[], int n, int bt[], int wt[], int tat[])
Loop For i = 0 and i < n and i++
Set tat[i] = bt[i] + wt[i]
return 1
Step 2-> In function int waitingtime(int processes[], int n, int bt[], int wt[], int quantum)
Declare rem_bt[n]
Loop For i = 0 and i < n and i++
Set rem_bt[i] = bt[i]
Set t = 0
Loop While (1)
Set done = true
Loop For i = 0 and i < n and i++
If rem_bt[i] > 0 then,
Set done = false
If rem_bt[i] > quantum then,
Set t = t + quantum
Set rem_bt[i] = rem_bt[i] - quantum
Else
Set t = t + rem_bt[i]
Set wt[i] = t - bt[i]
Set rem_bt[i] = 0
If done == true then,
Break
Step 3->In function int findavgTime(int processes[], int n, int bt[], int quantum)
Declare and initialize wt[n], tat[n], total_wt = 0, total_tat = 0
Call function waitingtime(processes, n, bt, wt, quantum)
Call function turnarroundtime(processes, n, bt, wt, tat)
Print "Processes Burst Time Waiting Time turnaround time "
Loop For i=0 and i<n and i++
Set total_wt = total_wt + wt[i]
Set total_tat = total_tat + tat[i]
Print the value i+1, bt[i], wt[i], tat[i]
Print "Average waiting time = total_wt / n
Print "Average turnaround time =total_tat / n
Step 4-> In function int main()
Delcare and initialize processes[] = { 1, 2, 3}
Declare and initialize n = sizeof processes / sizeof processes[0]
Declare and initialize burst_time[] = {8, 6, 12}
Set quantum = 2
Call function findavgTime(processes, n, burst_time, quantum)示例
#include <stdio.h>
// Function to calculate turn around time
int turnarroundtime(int processes[], int n,
int bt[], int wt[], int tat[]) {
// calculating turnaround time by adding
// bt[i] + wt[i]
for (int i = 0; i < n ; i++)
tat[i] = bt[i] + wt[i];
return 1;
}
// Function to find the waiting time for all
// processes
int waitingtime(int processes[], int n,
int bt[], int wt[], int quantum) {
// Make a copy of burst times bt[] to store remaining
// burst times.
int rem_bt[n];
for (int i = 0 ; i < n ; i++)
rem_bt[i] = bt[i];
int t = 0; // Current time
// Keep traversing processes in round robin manner
// until all of them are not done.
while (1) {
bool done = true;
// Traverse all processes one by one repeatedly
for (int i = 0 ; i < n; i++) {
// If burst time of a process is greater than 0
// then only need to process further
if (rem_bt[i] > 0) {
done = false; // There is a pending process
if (rem_bt[i] > quantum) {
// Increase the value of t i.e. shows
// how much time a process has been processed
t += quantum;
// Decrease the burst_time of current process
// by quantum
rem_bt[i] -= quantum;
}
// If burst time is smaller than or equal to
// quantum. Last cycle for this process
else {
// Increase the value of t i.e. shows
// how much time a process has been processed
t = t + rem_bt[i];
// Waiting time is current time minus time
// used by this process
wt[i] = t - bt[i];
// As the process gets fully executed
// make its remaining burst time = 0
rem_bt[i] = 0;
}
}
}
// If all processes are done
if (done == true)
break;
}
return 1;
}
// Function to calculate average time
int findavgTime(int processes[], int n, int bt[],
int quantum) {
int wt[n], tat[n], total_wt = 0, total_tat = 0;
// Function to find waiting time of all processes
waitingtime(processes, n, bt, wt, quantum);
// Function to find turn around time for all processes
turnarroundtime(processes, n, bt, wt, tat);
// Display processes along with all details
printf("Processes Burst Time Waiting Time turnaround time
");
// Calculate total waiting time and total turn
// around time
for (int i=0; i<n; i++) {
total_wt = total_wt + wt[i];
total_tat = total_tat + tat[i];
printf("\t%d\t\t\t%d\t\t\t%d\t\t\t%d
",i+1, bt[i], wt[i], tat[i]);
}
printf("Average waiting time = %f", (float)total_wt / (float)n);
printf("
Average turnaround time = %f
", (float)total_tat / (float)n);
return 1;
}
// main function
int main() {
// process id's
int processes[] = { 1, 2, 3};
int n = sizeof processes / sizeof processes[0];
// Burst time of all processes
int burst_time[] = {8, 6, 12};
// Time quantum
int quantum = 2;
findavgTime(processes, n, burst_time, quantum);
return 0;
}输出
更新于: 2019-12-23
8K+ 浏览量
广告