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.
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:
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
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
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.
/*
* FCFS Scheduling Program in C
*/
#include <stdio.h>
int main()
{
int pid[15];
int bt[15];
int n;
printf("Enter the number of processes: ");
scanf("%d",&n);
printf("Enter process id of all the processes: ");
for(int i=0;i<n;i++)
{
scanf("%d",&pid[i]);
}
printf("Enter burst time of all the processes: ");
for(int i=0;i<n;i++)
{
scanf("%d",&bt[i]);
}
int i, wt[n];
wt[0]=0;
//for calculating waiting time of each process
for(i=1; i<n; i++)
{
wt[i]= bt[i-1]+ wt[i-1];
}
printf("Process ID Burst Time Waiting Time TurnAround Time\n");
float twt=0.0;
float tat= 0.0;
for(i=0; i<n; i++)
{
printf("%d\t\t", pid[i]);
printf("%d\t\t", bt[i]);
printf("%d\t\t", wt[i]);
//calculating and printing turnaround time of each process
printf("%d\t\t", bt[i]+wt[i]);
printf("\n");
//for calculating total waiting time
twt += wt[i];
//for calculating total turnaround time
tat += (wt[i]+bt[i]);
}
float att,awt;
//for calculating average waiting time
awt = twt/n;
//for calculating average turnaround time
att = tat/n;
printf("Avg. waiting time= %f\n",awt);
printf("Avg. turnaround time= %f",att);
}
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.
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.
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”.
- Get Free Certificate of Merit in C Programming
- Participate in C Programming Certification Contest
- Become a Top Ranker in C Programming
- Take C Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Practice Computer Science MCQs
- Buy C Books
- Apply for C Internship
- Buy Computer Science Books
- Practice BCA MCQs