算法设计（循环调度算法程序详细实现S1） _CPU调度算法

本文概述

C/C++
Java
Python3
C#

轮循是一种CPU调度算法，它以循环的方式为每个进程分配一个固定的时隙。

它简单, 易于实现且无饥饿, 因为所有进程都可以公平分配CPU。
以CPU调度为核心的最常用技术之一。
这是抢先的, 因为最多只在固定的时间段内为进程分配CPU。
它的缺点是上下文切换的更多开销。

序列号。	优点	缺点
1.	这是公平的, 因为每个进程都获得相等的CPU份额。	等待时间和响应时间更长。
2.	新创建的进程将添加到就绪队列的末尾。	吞吐量低。
3.	循环调度程序通常使用分时, 为每个作业分配一个时隙或数量。	有上下文切换。
4.	在执行循环调度时, 会将特定的时间量分配给不同的作业。	甘特图似乎太大了(如果调度所需的量子时间较少, 例如：大调度需要1 ms。)
5.	在此调度中的特定量子时间之后, 每个进程都有机会重新调度。	小量子的费时调度。

插图：

文章图片
如何使用程序在Round Robin中计算以下时间？

完成时间：流程完成其执行的时间。
周转时间：完成时间与到达时间之间的时间差。周转时间=完成时间–到达时间
等待时间(W.T)：转向时间和突发时间之间的时间差。
等待时间=周转时间–爆发时间

在这篇文章中, 我们假设到达时间为0, 因此转身和完成时间相同。
棘手的部分是计算等待时间。一旦计算出等待时间, 就可以快速计算周转时间。
查找所有进程的等待时间的步骤：

1- Create an array rem_bt[] to keep track of remaining burst time of processes. This array is initially a copy of bt[] (burst times array) 2- Create another array wt[] to store waiting times of processes. Initialize this array as 0. 3- Initialize time : t = 0 4- Keep traversing the all processes while all processes are not done. Do following for i'th process if it is not done yet. a- If rem_bt[i] > quantum (i)t = t + quantum (ii) bt_rem[i] -= quantum; c- Else // Last cycle for this process (i)t = t + bt_rem[i]; (ii) wt[i] = t - bt[i] (ii) bt_rem[i] = 0; // This process is over

一旦有了等待时间, 我们就可以将进程的周转时间tat [i]计算为等待时间和突发时间之和, 即w??t [i] + bt [i]
以下是上述步骤的实现。
C/C++

// C++ program for implementation of RR scheduling #include< iostream> using namespace std; // Function to find the waiting time for all // processes void findWaitingTime( 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 processif (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 ; } }// Function to calculate turn around time void findTurnAroundTime( 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]; }// Function to calculate average time void 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 findWaitingTime(processes, n, bt, wt, quantum); // Function to find turn around time for all processes findTurnAroundTime(processes, n, bt, wt, tat); // Display processes along with all details cout < < "Processes " < < " Burst time " < < " Waiting time " < < " Turn around time\n" ; // 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]; cout < < " " < < i+1 < < "\t\t" < < bt[i] < < "\t " < < wt[i] < < "\t\t " < < tat[i] < < endl; }cout < < "Average waiting time = " < < ( float )total_wt / ( float )n; cout < < "\nAverage turn around time = " < < ( float )total_tat / ( float )n; }// Driver code 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[] = {10, 5, 8}; // Time quantum int quantum = 2; findavgTime(processes, n, burst_time, quantum); return 0; }

Java

// Java program for implementation of RR schedulingpublic class GFG { // Method to find the waiting time for all // processes static void findWaitingTime( 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[] = new int [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 ( true ) { boolean 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 processif (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 ; } }// Method to calculate turn around time static void findTurnAroundTime( 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]; }// Method to calculate average time static void findavgTime( int processes[], int n, int bt[], int quantum) { int wt[] = new int [n], tat[] = new int [n]; int total_wt = 0 , total_tat = 0 ; // Function to find waiting time of all processes findWaitingTime(processes, n, bt, wt, quantum); // Function to find turn around time for all processes findTurnAroundTime(processes, n, bt, wt, tat); // Display processes along with all details System.out.println( "Processes " + " Burst time " + " Waiting time " + " Turn around 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]; System.out.println( " " + (i+ 1 ) + "\t\t" + bt[i] + "\t " + wt[i] + "\t\t " + tat[i]); }System.out.println( "Average waiting time = " + ( float )total_wt / ( float )n); System.out.println( "Average turn around time = " + ( float )total_tat / ( float )n); }// Driver Method public static void main(String[] args) { // process id's int processes[] = { 1 , 2 , 3 }; int n = processes.length; // Burst time of all processes int burst_time[] = { 10 , 5 , 8 }; // Time quantum int quantum = 2 ; findavgTime(processes, n, burst_time, quantum); } }

Python3

# Python3 program for implementation of # RR scheduling # Function to find the waiting time # for all processes def findWaitingTime(processes, n, bt, wt, quantum): rem_bt = [ 0 ] * n# Copy the burst time into rt[] for i in range (n): rem_bt[i] = bt[i] t = 0 # Current time # Keep traversing processes in round # robin manner until all of them are # not done. while ( 1 ): done = True# Traverse all processes one by # one repeatedly for i in range (n):# 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 processif (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# Function to calculate turn around time def findTurnAroundTime(processes, n, bt, wt, tat):# Calculating turnaround time for i in range (n): tat[i] = bt[i] + wt[i] # Function to calculate average waiting # and turn-around times. def findavgTime(processes, n, bt, quantum): wt = [ 0 ] * n tat = [ 0 ] * n # Function to find waiting time # of all processes findWaitingTime(processes, n, bt, wt, quantum) # Function to find turn around time # for all processes findTurnAroundTime(processes, n, bt, wt, tat) # Display processes along with all details print ( "ProcessesBurst TimeWaiting" , "TimeTurn-Around Time" ) total_wt = 0 total_tat = 0 for i in range (n):total_wt = total_wt + wt[i] total_tat = total_tat + tat[i] print ( " " , i + 1 , "\t\t" , bt[i], "\t\t" , wt[i], "\t\t" , tat[i])print ( "\nAverage waiting time = %.5f " % (total_wt / n) ) print ( "Average turn around time = %.5f " % (total_tat / n)) # Driver code if __name__ = = "__main__" :# Process id's proc = [ 1 , 2 , 3 ] n = 3# Burst time of all processes burst_time = [ 10 , 5 , 8 ] # Time quantum quantum = 2 ; findavgTime(proc, n, burst_time, quantum)# This code is contributed by # Shubham Singh(SHUBHAMSINGH10)

// C# program for implementation of RR // scheduling using System; public class GFG {// Method to find the waiting time // for all processes static void findWaitingTime( 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 = new int [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 ( true ) { 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) {// There is a pending process done = false ; 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 ; } }// Method to calculate turn around time static void findTurnAroundTime( 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]; }// Method to calculate average time static void findavgTime( int []processes, int n, int []bt, int quantum) { int []wt = new int [n]; int []tat = new int [n]; int total_wt = 0, total_tat = 0; // Function to find waiting time of // all processes findWaitingTime(processes, n, bt, wt, quantum); // Function to find turn around time // for all processes findTurnAroundTime(processes, n, bt, wt, tat); // Display processes along with // all details Console.WriteLine( "Processes " + " Burst time " + " Waiting time " + " Turn around 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]; Console.WriteLine( " " + (i+1) + "\t\t" + bt[i] + "\t " + wt[i] + "\t\t " + tat[i]); }Console.WriteLine( "Average waiting time = " + ( float )total_wt / ( float )n); Console.Write( "Average turn around time = " + ( float )total_tat / ( float )n); }// Driver Method public static void Main() { // process id's int []processes = { 1, 2, 3}; int n = processes.Length; // Burst time of all processes int []burst_time = {10, 5, 8}; // Time quantum int quantum = 2; findavgTime(processes, n, burst_time, quantum); } }// This code is contributed by nitin mittal.

输出如下：