FCFS (First Come First Serve)

Lists of Questions Answers and Short Study Notes on OS Process Scheduling Algorithm

  • (1). Explain FCFS Scheduling algorithms with illustration.

 

Question-1 Explain First Come First Serve – FCFS scheduling algorithms with illustration.

Selection criteria :

The process that request first is served first. It means that processes are served in the exact order of their arrival.

 

Decision Mode :

Non preemptive: Once a process is selected, it runs until it is blocked for an I/O or some event, or it is terminated.

 

Implementation:

This strategy can be easily implemented by using FIFO queue, FIFO means First In First Out. When CPU becomes free, a process from the first position in a queue is selected to run.

 

Example :

Consider the following set of four processes. Their arrival time and time required to complete the execution are given in following table. Consider all time values in milliseconds.

Process Arrival Time (T0) Time required for completion (∆T)(CPU Burst Time)
P0 0 10
P1 1 6
P2 3 2
P3 5 4

 

Gantt Chart :

P0 P1 P2 P3
0 10 16 18

                                                                                                        22
Initially only process P0 is present and it is allowed to run. But, when P0 completes, all other processes are present. So, next process P1 from ready queue is selected and allowed to run till it completes. This procedure is repeated till all processes completed their execution.

 

Statistics:

Process Arrival Time(T0) CPU Burst Time(∆T) Finish Time(T1) Turnaround Time(TAT=T1-T0) Waiting Time (WT=TAT-∆T)
P0 0 10 10 10 0
P1 1 6 16 15 9
P2 3 2 18 15 13
P3 5 4 22 17 13

 

Average Turnaround Time: (10+15+15+17)/4 = 57/4 = 14.25 ms.

Average Waiting Time: (0+9+13+13)/4 = 35/4 = 8.75 ms.

 

Advantages:

  • Simple, fair, no starvation.
  • Easy to understand, easy to implement.

 

Disadvantages :

  • Not efficient. Average waiting time is too high.
  • Convoy effect is possible. All small I/O bound processes wait for one big CPU bound process to acquire CPU.
  • CPU utilization may be less efficient especially when a CPU bound process is running with many I/O bound processes.