FCFS Scheduling Program in C

Problem Description:

Write an FCFS Scheduling Program in C to determine the average waiting time and average turnaround time has given n processes and their burst times.

FCFS Scheduling Algorithm:

The CPU scheduling algorithm First Come, First Served (FCFS), also known as First In, First Out (FIFO), allocates the CPU to the processes in the order they are queued in the ready queue.

FCFS uses non-preemptive scheduling, which means that once a CPU has been assigned to a process, it stays assigned to that process until it is either not terminated or may be interrupted by an I/O interrupt.

Problem Solution

1. Enter all the processes and their burst time.
2. Find waiting time, WT of all the processes.
3. For the 1st process, WT = 0.
4. For all the next processes i, WT[i] = BT[i-1] + WT[i-1].
5. Calculate Turnaround time = WT + BT for all the processes.
6. Calculate average waiting time = total waiting time/no. of processes.
7. Calculate average turnaround time = total turnaround time/no. of processes.

Example:

Process Arrival Time Burst Time
P1 0 5
P2 0 11
P3 0 11

Gantt Chart:
FCFS Scheduling Example

advertisement
advertisement

Waiting Time: Time Difference between turnaround time and burst time.

Waiting Time = Turnaround Time – Burst Time

P1 waiting time: 0
P2 waiting time: 5
P3 waiting time: 16

Average Waiting Time = (0 + 5 + 16)/3 = 21/3 = 7

Note: Join free Sanfoundry classes at Telegram or Youtube

Turnaround Time: Difference between completion time and arrival time.

Turnaround Time = Completion Time – Arrival Time

P1 turnaround time: 5-0 = 5
P2 turnaround time: 16-0 = 16
P3 turnaround time: 27-0 = 27

Average Turnaround Time = (5+16+27)/3 = 16

Program/Source Code

Here is the source code of the C program for the FCFS Scheduling. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

advertisement
  1. /*
  2.  * FCFS Scheduling Program in C
  3.  */
  4.  
  5. #include <stdio.h>
  6. int main()
  7. {
  8.     int pid[15];
  9.     int bt[15];
  10.     int n;
  11.     printf("Enter the number of processes: ");
  12.     scanf("%d",&n);
  13.  
  14.     printf("Enter process id of all the processes: ");
  15.     for(int i=0;i<n;i++)
  16.     {
  17.         scanf("%d",&pid[i]);
  18.     }
  19.  
  20.     printf("Enter burst time of all the processes: ");
  21.     for(int i=0;i<n;i++)
  22.     {
  23.         scanf("%d",&bt[i]);
  24.     }
  25.  
  26.     int i, wt[n];
  27.     wt[0]=0;
  28.  
  29.     //for calculating waiting time of each process
  30.     for(i=1; i<n; i++)
  31.     {
  32.         wt[i]= bt[i-1]+ wt[i-1];
  33.     }
  34.  
  35.     printf("Process ID     Burst Time     Waiting Time     TurnAround Time\n");
  36.     float twt=0.0;
  37.     float tat= 0.0;
  38.     for(i=0; i<n; i++)
  39.     {
  40.         printf("%d\t\t", pid[i]);
  41.         printf("%d\t\t", bt[i]);
  42.         printf("%d\t\t", wt[i]);
  43.  
  44.         //calculating and printing turnaround time of each process
  45.         printf("%d\t\t", bt[i]+wt[i]);
  46.         printf("\n");
  47.  
  48.         //for calculating total waiting time
  49.         twt += wt[i];
  50.  
  51.         //for calculating total turnaround time
  52.         tat += (wt[i]+bt[i]);
  53.     }
  54.     float att,awt;
  55.  
  56.     //for calculating average waiting time
  57.     awt = twt/n;
  58.  
  59.     //for calculating average turnaround time
  60.     att = tat/n;
  61.     printf("Avg. waiting time= %f\n",awt);
  62.     printf("Avg. turnaround time= %f",att);
  63. }
Program Explanation

1. Initialize two array pid[] and bt[] of size 15.
2. Ask the user for number of processes n.
3. Ask the user for process id and burst time for all n processes and store them into pid[] and bt[] respectively.
4. Calculate waiting time of each process by the formula wt[i] = wt[i-1] + bt[i-1].
5. Print Process Id, Burst Time, waiting time and Turnaround time of each process in tabular manner.
6. Calculate and print turnaround time of each process = bt[i] + wt[i].
7. Add waiting time of all the processes and store it in the variable twt.
8. Add turnaround time of all the processes and store it in the variable tat.
9. Calculate average waiting time as awt = twt/n.
10. Calculate average turnaround time as att = tat/n;
11. Print average waiting time and average turnaround time.
12. Exit.

Time Complexity: O(n)
Time complexity of the FCFS Scheduling program is O(n), as the for loop runs for n number of processes.

Space Complexity: O(n)
In the above program, space complexity is O(n) as arrays of size n have been initialized to store the values in it.

Run Time Testcases

In this case, we enter “3” as the number of processes, and the burst time are “p1: 5”, “p2: 11”, and “p3: 11” to find average waiting time and average turnaround time using FCFS Scheduling algorithm.

advertisement
Enter the number of processes: 3
Enter process id of all the processes: 1 2 3
Enter burst time of all the processes: 5 11 11
Process ID     Burst Time     Waiting Time     TurnAround Time
1               5               0               5
2               11              5               16
3               11              16              27
Avg. waiting time= 7.000000
Avg. turnaround time= 16.000000

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.