FCFS CPU Scheduling | Operating System - Computer Science Engineering (CSE) PDF Download

Program for FCFS CPU Scheduling

Given n processes with their burst times, the task is to find average waiting time and average turn around time using FCFS scheduling algorithm.
First in, first out (FIFO), also known as first come, first served (FCFS), is the simplest scheduling algorithm. FIFO simply queues processes in the order that they arrive in the ready queue.
In this, the process that comes first will be executed first and next process starts only after the previous gets fully executed.
Here we are considering that arrival time for all processes is 0.

How to compute below times in Round Robin using a program? 

1. Completion Time: Time at which process completes its execution.
2. Turn Around Time: Time Difference between completion time and arrival time. Turn Around Time = Completion Time – Arrival Time
3. Waiting Time(W.T): Time Difference between turn around time and burst time.
   Waiting Time = Turn Around Time – Burst Time

In this post, we have assumed arrival times as 0, so turn around and completion times are same.

Implementation

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.

Processes with different arrival times

Given n processes with their burst times and arrival times, the task is to find average waiting time and average turn around time using FCFS scheduling algorithm.
FIFO simply queues processes in the order they arrive in the ready queue. Here, the process that comes first will be executed first and next process will start only after the previous gets fully executed. 

1. Completion Time: Time at which process completes its execution.
2. Turn Around Time: Time Difference between completion time and arrival time. Turn Around Time = Completion Time – Arrival Time
3. Waiting Time(W.T): Time Difference between turn around time and burst time. Waiting Time = Turn Around Time – Burst Time.

Service Time: Service time means amount of time after which a process can start execution. It is summation of burst time of previous processes (Processes that came before)

Changes in code as compare to code of FCFS with same arrival time: 
To find waiting time: Time taken by all processes before the current process to be started
(i.e. burst time of all previous processes) – arrival time of current process
wait_time[i] = (bt[0] + bt[1] +…… bt[i - 1] ) – arrival_time[i]

Implementation

1. Input the processes along with their burst time(bt) and arrival time(at)
2. 2- Find waiting time for all other processes i.e. for a given process  i: wt[i] = (bt[0] + bt[1] +...... bt[i - 1]) - at[i] 
3. Now find turn around time = waiting_time + burst_time for all processes
4. Average waiting time = total_waiting_time / no_of_processes
5. Average turn around time = total_turn_around_time / no_of_processes

Convoy Effect in Operating Systems

Convoy Effect is phenomenon associated with the First Come First Serve (FCFS) algorithm, in which the whole Operating System slows down due to few slow processes.

The Convey Effect, Visualized

FCFS algorithm is non-preemptive in nature, that is, once CPU time has been allocated to a process, other processes can get CPU time only after the current process has finished. This property of FCFS scheduling leads to the situation called Convoy Effect.
Suppose there is one CPU intensive (large burst time) process in the ready queue, and several other processes with relatively less burst times but are Input/Output (I/O) bound (Need I/O operations frequently).

Steps are as following below:

• The I/O bound processes are first allocated CPU time. As they are less CPU intensive, they quickly get executed and goto I/O queues.
• Now, the CPU intensive process is allocated CPU time. As its burst time is high, it takes time to complete.
• While the CPU intensive process is being executed, the I/O bound processes complete their I/O operations and are moved back to ready queue.
• However, the I/O bound processes are made to wait as the CPU intensive process still hasn’t finished. This leads to I/O devices being idle.
• When the CPU intensive process gets over, it is sent to the I/O queue so that it can access an I/O device.
• Meanwhile, the I/O bound processes get their required CPU time and move back to I/O queue.
• However, they are made to wait because the CPU intensive process is still accessing an I/O device. As a result, the CPU is sitting idle now.

Hence in Convoy Effect, one slow process slows down the performance of the entire set of processes, and leads to wastage of CPU time and other devices.
To avoid Convoy Effect, preemptive scheduling algorithms like Round Robin Scheduling can be used – as the smaller processes don’t have to wait much for CPU time – making their execution faster and leading to less resources sitting idle.