FCFS CPU调度算法程序实现|S1

2021年3月30日15:44:04 发表评论 1,669 次浏览

本文概述

给定n个进程的突发时间, 任务是使用FCFS调度算法查找平均等待时间和平均周转时间。

最先进的调度算法是先进先出(FIFO), 也称为先来先服务(FCFS)。 FIFO只是按照进程到达就绪队列的顺序对其进行排队。

这样, 首先执行的进程将首先执行, 而下一个进程只有在前一个进程完全执行后才开始。

在这里, 我们考虑所有进程的到达时间为0。

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

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

在这篇文章中, 我们假设到达时间为0, 因此转身和完成时间相同。

FCFS CPU调度程序|S11

实现

1-  Input the processes along with their burst time (bt).
2-  Find waiting time (wt) for all processes.
3-  As first process that comes need not to wait so 
    waiting time for process 1 will be 0 i.e. wt[0] = 0.
4-  Find waiting time for all other processes i.e. for
     process i -> 
       wt[i] = bt[i-1] + wt[i-1] .
5-  Find turnaround time = waiting_time + burst_time 
    for all processes.
6-  Find average waiting time = 
                 total_waiting_time / no_of_processes.
7-  Similarly, find average turnaround time = 
                 total_turn_around_time / no_of_processes.

C ++

// C++ program for implementation of FCFS 
// 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[])
{
     // waiting time for first process is 0
     wt[0] = 0;
  
     // calculating waiting time
     for ( int  i = 1; i < n ; i++ )
         wt[i] =  bt[i-1] + wt[i-1] ;
}
  
// 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 wt[n], tat[n], total_wt = 0, total_tat = 0;
  
     //Function to find waiting time of all processes
     findWaitingTime(processes, n, bt, wt);
  
     //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};
  
     findavgTime(processes, n, burst_time);
     return 0;
}

C

// C program for implementation of FCFS  
// scheduling 
#include<stdio.h> 
// Function to find the waiting time for all  
// processes 
void findWaitingTime( int processes[], int n, int bt[], int wt[]) 
{ 
     // waiting time for first process is 0 
     wt[0] = 0; 
    
     // calculating waiting time 
     for ( int  i = 1; i < n ; i++ ) 
         wt[i] =  bt[i-1] + wt[i-1] ; 
} 
    
// 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 wt[n], tat[n], total_wt = 0, total_tat = 0; 
    
     //Function to find waiting time of all processes 
     findWaitingTime(processes, n, bt, wt); 
    
     //Function to find turn around time for all processes 
     findTurnAroundTime(processes, n, bt, wt, tat); 
    
     //Display processes along with all details 
     printf ( "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]; 
         printf ( "   %d " , (i+1));
         printf ( "       %d " , bt[i] );
         printf ( "       %d" , wt[i] );
         printf ( "       %d\n" , tat[i] ); 
     } 
     int s=( float )total_wt / ( float )n;
     int t=( float )total_tat / ( float )n;
     printf ( "Average waiting time = %d" , s);
     printf ( "\n" );
     printf ( "Average turn around time = %d " , t); 
} 
    
// 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}; 
    
     findavgTime(processes, n, burst_time); 
     return 0; 
} 
// This code is contributed by Shivi_Aggarwal

Java

// Java program for implementation of FCFS 
// scheduling 
  
import java.text.ParseException;
  
class GFG {
  
     // Function to find the waiting time for all 
     // processes 
     static void findWaitingTime( int processes[], int n, int bt[], int wt[]) {
         // waiting time for first process is 0 
         wt[ 0 ] = 0 ;
  
         // calculating waiting time 
         for ( int i = 1 ; i < n; i++) {
             wt[i] = bt[i - 1 ] + wt[i - 1 ];
         }
     }
  
     // Function 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];
         }
     }
  
     //Function to calculate average time 
     static void findavgTime( int processes[], int n, int bt[]) {
         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);
  
         //Function to find turn around time for all processes 
         findTurnAroundTime(processes, n, bt, wt, tat);
  
         //Display processes along with all details 
         System.out.printf( "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];
             System.out.printf( " %d " , (i + 1 ));
             System.out.printf( "     %d " , bt[i]);
             System.out.printf( "     %d" , wt[i]);
             System.out.printf( "     %d\n" , tat[i]);
         }
         float s = ( float )total_wt /( float ) n;
         int t = total_tat / n;
         System.out.printf( "Average waiting time = %f" , s);
         System.out.printf( "\n" );
         System.out.printf( "Average turn around time = %d " , t);
     }
  
     // Driver code 
     public static void main(String[] args) throws ParseException {
         //process id's 
         int processes[] = { 1 , 2 , 3 };
         int n = processes.length;
  
         //Burst time of all processes 
         int burst_time[] = { 10 , 5 , 8 };
  
         findavgTime(processes, n, burst_time);
  
     }
}
// This code is contributed by 29ajaykumar

Python 3

# Python3 program for implementation 
# of FCFS scheduling
  
# Function to find the waiting 
# time for all processes
def findWaitingTime(processes, n, bt, wt):
  
     # waiting time for 
     # first process is 0
     wt[ 0 ] = 0
  
     # calculating waiting time
     for i in range ( 1 , n ):
         wt[i] = bt[i - 1 ] + wt[i - 1 ] 
  
# Function to calculate turn
# around time
def findTurnAroundTime(processes, n, bt, wt, tat):
  
     # calculating turnaround 
     # time by adding bt[i] + wt[i]
     for i in range (n):
         tat[i] = bt[i] + wt[i]
  
# Function to calculate
# average time
def findavgTime( processes, n, bt):
  
     wt = [ 0 ] * n
     tat = [ 0 ] * n 
     total_wt = 0
     total_tat = 0
  
     # Function to find waiting 
     # time of all processes
     findWaitingTime(processes, n, bt, wt)
  
     # 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" )
  
     # Calculate total waiting time 
     # and total turn around time
     for i in range (n):
      
         total_wt = total_wt + wt[i]
         total_tat = total_tat + tat[i]
         print ( " " + str (i + 1 ) + "\t\t" + 
                     str (bt[i]) + "\t " + 
                     str (wt[i]) + "\t\t " + 
                     str (tat[i])) 
  
     print ( "Average waiting time = " +
                    str (total_wt / n))
     print ( "Average turn around time = " +
                      str (total_tat / n))
  
# Driver code
if __name__ = = "__main__" :
      
     # process id's
     processes = [ 1 , 2 , 3 ]
     n = len (processes)
  
     # Burst time of all processes
     burst_time = [ 10 , 5 , 8 ]
  
     findavgTime(processes, n, burst_time)
  
# This code is contributed 
# by ChitraNayal

C#

// C# program for implementation of FCFS 
// scheduling 
using System;
      
class GFG 
{
  
     // Function to find the waiting time for all 
     // processes 
     static void findWaitingTime( int []processes, int n, int []bt, int [] wt) 
     {
         // waiting time for first process is 0 
         wt[0] = 0;
  
         // calculating waiting time 
         for ( int i = 1; i < n; i++) 
         {
             wt[i] = bt[i - 1] + wt[i - 1];
         }
     }
  
     // Function 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];
         }
     }
  
     // Function to calculate average time 
     static void findavgTime( int []processes, int n, int []bt)
     {
         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);
  
         //Function to find turn around time for all processes 
         findTurnAroundTime(processes, n, bt, wt, tat);
  
         //Display processes along with all details 
         Console.Write( "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];
             Console.Write( " {0} " , (i + 1));
             Console.Write( "     {0} " , bt[i]);
             Console.Write( "     {0}" , wt[i]);
             Console.Write( "     {0}\n" , tat[i]);
         }
         float s = ( float )total_wt /( float ) n;
         int t = total_tat / n;
         Console.Write( "Average waiting time = {0}" , s);
         Console.Write( "\n" );
         Console.Write( "Average turn around time = {0} " , t);
     }
  
     // Driver code 
     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};
  
         findavgTime(processes, n, burst_time);
     }
}
  
// This code contributed by Rajput-Ji

输出如下：

Processes  Burst time  Waiting time  Turn around time
 1        10     0         10
 2        5     10         15
 3        8     15         23
Average waiting time = 8.33333
Average turn around time = 16

重要事项：

非抢先平均等待时间不是最佳的

无法并行利用资源：产生Convoy效果(考虑存在许多IO绑定进程和一个CPU绑定进程的情况。当CPU绑定进程获取CPU时, IO绑定进程必须等待CPU绑定进程。IO绑定进程可能会最好将CPU占用一段时间, 然后再使用IO设备)。

资源 ：

http://web.cse.ohio-state.edu/~agrawal/660/Slides/jan18.pdf

在S2中我们将讨论到达时间不同的过程。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: