Operating Systems | Scheduling Algorithms : FCFS


First Come First Serve(FCFS)

FCFS algorithm schedules first created process among the processes available on main memory in ready state.

Example: Consider the following timing table of processes and calculate completion time, turn around time and waiting time using FCFS algorithm with the following assumptions. Also find average of turn around time and waiting time.

  • No preemption
  • No I/O request will be there from any process
  • Arrival time is relative to CPU on time

Hint

  • TAT= CT- AT
  • WT= TAT- BT

Process Number AT BT
1 1 4
2 2 3
3 3 1
4 4 2
5 5 5

NOTE: In case of non-preemptive algorithms the Response time and Waiting time are same. But in case of preemptive algorithms since the waiting time may shuffled across turn around time it may be different




Convoy Effect

It is a disadvantage of FCFS algorithm which happens due to arrival of process with longer burst time(BT) before shorter jobs, which leads to a larger average waiting time or starvation.

Consider the following pattern of entry of processes.

Table 1

Process Number AT BT CT TAT WT
P1 0 40 40 40 0
P2 1 4 44 43 39
P3 1 3 47 44 41

Average WT = (0+39+41)/3="80/3"

Table 2

Process Number AT BT CT TAT WT
P1 0 40 40 40 0
P2 1 4 44 43 39
P3 1 3 47 44 41

Average WT = (6+0+4)/3="10/3"

  • Average waiting time of process with similar burst time changes with order of creation of processes.
  • The entry of longest job before shorter jobs increases the average waiting time (Convoy effect).



Context Switching Time

While changing state of a process from ready to run state after calling of scheduler, the scheduler has to call dispatcher and dispatcher should change the context. The time taken for theses sequence of procedure is called context switching time

Example : The following table give the arrival time and burst time of process with a unit context switching time

Process Number AT BT
1 1 3
2 2 3
3 3 1
4 4 4

The timing diagram for the processes listed will be as shown. A unit context switching time will be lapsed before execution of every process by FCFS algorithm scheduling algorithm with no preemption.

Comments