# 算法设计：循环调度算法程序详细实现S1

2021年4月6日19:11:40 发表评论 854 次浏览

## 本文概述

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

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

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

``````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``````

## 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 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 ;
}
}

// 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;

// 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 scheduling

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 )
{
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 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 ;
}
}

// 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 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

# 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 ( "Processes    Burst Time     Waiting" , "Time    Turn-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#

``````// 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.``````

``````Processes  Burst time  Waiting time  Turn around time
1        10     13         23
2        5     10         15
3        8     13         21
Average waiting time = 12
Average turn around time = 19.6667`````` 