FCFS Scheduling

In CPU-scheduling problems some terms are used while solving the problems, so for
conceptual purpose the terms are discussed as follows −

 Arrival time (AT) − Arrival time is the time at which the process arrives in ready
queue.
 Burst time (BT) or CPU time of the process − Burst time is the unit of time in
which a particular process completes its execution.
 Completion time (CT) − Completion time is the time at which the process has been
terminated.
 Turn-around time (TAT) − The total time from arrival time to completion time is
known as turn-around time. TAT can be written as,
 Waiting time (WT) Waiting time is the time at which the process waits for its
allocation while the previous process is in the CPU for execution. WT is written as,

Turn-around time (TAT) = Completion time (CT) − Arrival time (AT) or TAT = Burst
time (BT) + Waiting time (WT)

Waiting time (WT) = Turn-around time (TAT) − Burst time (BT)

 Response time (RT) − Response time is the time at which CPU has been allocated to
a particular process first time.
 In case of non-preemptive scheduling, generally Waiting time and Response time is
same.
 Gantt chart − Gantt chart is a visualization which helps to scheduling and managing
particular tasks in a project. It is used while solving scheduling problems, for a
concept of how the processes are being allocated in different algorithms.

Problem 1

Consider the given table below and find Completion time (CT), Turn-around time (TAT),
Waiting time (WT), Response time (RT), Average Turn-around time and Average Waiting
time.

Process ID Arrival time Burst time

P1 2 2
P2 5 6
P3 0 4
P4 0 7
P5 7 4

Solution

Gantt chart
For this problem CT, TAT, WT, RT is shown in the given table

Process ID Arrival time Burst time CT TAT=CT-AT WT=TAT-BT RT

P1 2 2 13 13-2= 11 11-2= 9 9
P2 5 6 19 19-5= 14 14-6= 8 8
P3 0 4 4 4-0= 4 4-4= 0 0
P4 0 7 11 11-0= 11 11-7= 4 4
P5 7 4 23 23-7= 16 16-4= 12 12

Average Waiting time = (9+8+0+4+12)/5 = 33/5 = 6.6 time unit (time unit can be
considered as milliseconds)

Average Turn-around time = (11+14+4+11+16)/5 = 56/5 = 11.2 time unit (time unit can be
considered as milliseconds)

Problem 2

Consider the given table below and find Completion time (CT), Turn-around time (TAT),
Waiting time (WT), Response time (RT), Average Turn-around time and Average Waiting
time.

Process ID Arrival time Burst time

P1 2 2
P2 0 1
P3 2 3
P4 3 5
P5 4 5

Solution

Gantt chart

For this problem CT, TAT, WT, RT is shown in the given table

Process ID Arrival time Burst time CT TAT=CT-AT WT=TAT-BT RT

P1 2 2 4 4-2= 2 2-2= 0 0
P2 0 1 1 1-0= 1 1-1= 0 0
 P3 2 3 7 7-2= 5 5-3= 2 2
P4 3 5 12 12-3= 9 9-5= 4 4
P5 4 5 17 17-4= 13 13-5= 8 8

Average Waiting time = (0+0+2+4+8)/5 = 14/5 = 2.8 time unit (time unit can be considered
as milliseconds)

Average Turn-around time = (2+1+5+9+13)/5 = 30/5 = 6 time unit (time unit can be
considered as milliseconds)

*In idle (not-active) CPU period, no process is scheduled to be terminated so in this time it
remains void for a little time.

Advantages Of FCFS Scheduling

 It is an easy algorithm to implement since it does not include any complex way.
 Every task should be executed simultaneously as it follows FIFO queue.
 FCFS does not give priority to any random important tasks first so its a fair
scheduling.

Disadvantages Of FCFS Scheduling

 FCFS results in convoy effect which means if a process with higher burst time comes
first in the ready queue then the processes with lower burst time may get blocked and
that processes with lower burst time may not be able to get the CPU if the higher burst
time task takes time forever.
 If a process with long burst time comes in the line first then the other short burst time
process have to wait for a long time, so it is not much good as time-sharing systems.
 Since it is non-preemptive, it does not release the CPU before it completes its task
execution completely.

*Convoy effect and starvation sounds similar but there is slight difference, so it is advised to
not treat these both terms as same words.

Conclusion

Although FCFS is simple to implement and understand, FCFS is not good for interactive
system and not used in modern operating systems. The Convoy effect in the FCFS can be
prevented using other CPU-scheduling preemptive algorithms such as Round-robin
scheduling.

Shortest Job First (SJF) Scheduling

A CPU scheduling strategy is a procedure that selects one process in the waiting state and
assigns it to the CPU so that it can be executed. There are a number of scheduling algorithms.
In this section, we will learn about Shortest Job First or SJF scheduling algorithm.

SJF (SHORTEST JOB FIRST) Scheduling

In the Shortest Job First scheduling algorithm, the processes are scheduled in ascending order
of their CPU burst times, i.e. the CPU is allocated to the process with the shortest execution
time.

Variants of SJF Scheduling

SJF non-preemptive scheduling

In the non-preemptive version, once a process is assigned to the CPU, it runs into completion.
Here, the short term scheduler is invoked when a process completes its execution or when a
new process(es) arrives in an empty ready queue.

SJF preemptive scheduling

This is the preemptive version of SJF scheduling and is also referred as Shortest Remaining
Time First (SRTF) scheduling algorithm. Here, if a short process enters the ready queue
while a longer process is executing, process switch occurs by which the executing process is
swapped out to the ready queue while the newly arrived shorter process starts to execute.
Thus the short term scheduler is invoked either when a new process arrives in the system or
an existing process completes its execution.

Features of SJF Algorithm

 SJF allocates CPU to the process with shortest execution time.

 In cases where two or more processes have the same burst time, arbitration is done
among these processes on first come first serve basis.
 There are both preemptive and non-premptive versions.
 It minimises the average waiting time of the processes.
 It may cause starvation of long processes if short processes continue to come in the
system.

Example 1

Suppose that we have a set of four processes that have arrived at the same time in the order
P1, P2, P3 and P4. The burst time in milliseconds of each process is given by the following
table −

Process CPU Burst Time in ms

P1 6
P2 10
P3 4
P4 6
Let us draw the GANTT chart and find the average turnaround time and average waiting time
using non-preemptive SJF algorithm.

GANTT Chart for the set of processes using SJF

Process P3 has the shortest burst time and so it executes first. Then we find that P1 and P4
have equal burst time of 6ms. Since P1 arrived before, CPU is allocated to P1 and then to P4.
Finally P2 executes. Thus the order of execution is P3, P1, P4, P2 and is given by the
following GANTT chart −

Let us compute the average turnaround time and average waiting time from the above chart.

Average Turnaround Time

=Sum of Turnaround Time of each Process / Number of Processes

= (TATP1 + TATP2 + TATP3 + TATP4) / 4

= (10 + 26 + 4 + 16) / 4 = 14 ms

Average Waiting Time

= Sum of Waiting Time of Each Process / Number of processes

= (WTP1 + WTP2 + WTP3 + WTP4) / 4

= (4 + 16 + 0 + 10) / 4 = 7.5 ms

Example 2

In the previous example, we had assumed that all the processes had arrived at the same time,
a situation which is practically impossible. Here, we consider circumstance when the
processes arrive at different times. Suppose we have set of four processes whose arrival times
and CPU burst times are as follows −

Process Arrival Time CPU Burst Time

P1 0 6
P2 4 10
P3 4 4
P4 8 3

Let us draw the GANTT chart and find the average turnaround time and average waiting time
using non-preemptive SJF algorithm.

GANTT Chart

While drawing the GANTT chart, we will consider which processes have arrived in the
system when the scheduler is invoked. At time 0ms, only P1 is there and so it is assigned to
CPU. P1 completes execution at 6ms and at that time P2 and P3 have arrived, but not P4. P3
is assigned to CPU since it has the shortest burst time among current processes. P3 completes
execution at time 10ms. By that time P4 has arrived and so SJF algorithm is run on the
processes P2 and P4. Hence, we find that the order of execution is P1, P3, P4, P2 as shown in
the following GANTT chart −

Let us calculate the turnaround time of each process and hence the average.

Turnaround Time of a process = Completion Time Arrival Time

TATP1 = CTP1 - ATP1 = 6 - 0 = 6 ms

TATP2 = CTP2 - ATP2 = 23 - 4 = 19 ms

TATP3 = CTP3 - ATP3 = 10 - 4 = 6 ms

TATP4 = CTP4 - ATP4 = 13 - 8 = 5 ms

Average Turnaround Time

=Sum of Turnaround Time of each Process/ Number of Processes

= (6 + 19+ 6 + 5) / 4 = 9 ms

The waiting time is given by the time that each process waits in the ready queue. For a non-
preemptive scheduling algorithm, waiting time of each process can be simply calculated as −

Waiting Time of any process = Time of admission to CPU Arrival Time

WTP1 = 0 - 0 = 0 ms

WTP2 = 13 - 4 = 9 ms

WTP3 = 6 - 4 = 2 ms

WTP4 = 10 - 8 = 2 ms

Average Waiting Time

= Sum of Waiting Time of Each Process/ Number of processes

= (WTP1 + WTP2 + WTP3 + WTP4) / 4

= (0 + 9 + 2 + 2) / 4 = 3.25 ms
Example of Preemptive SJF (SRTF) algorithm

Let us now perform preemptive SJF (SRTN) scheduling on the following processes, draw
GANTT chart and find the average turnaround time and average waiting time.

Process Arrival Time CPU Burst Time

P1 0 8
P2 4 10
P3 4 3
P4 10 4

GANTT Chart

Since this is a preemptive scheduling algorithm, the scheduler is invoked when a process
arrives and when it completes execution. The scheduler computes the remaining time of
completion for each of the processes in the system and selects the process having shortest
remaining time left for execution.

Initially, only P1 arrives and so it is assigned to CPU. At time 4ms, P2 and P3 arrive. The
scheduler computes the remaining time of the processes P1, P2 and P3 as 4ms, 10ms and
3ms. Since, P3 has shortest time, P1 is pre-empted by P3. P3 completes execution at 7ms and
the scheduler is invoked. Among the processes in the system, P1 has shortest time and so it
executes. At time 10ms, P4 arrives and the scheduler again computes the remaining times left
for each process. Since the remaining time of P1 is least, no process switch occurs and P1
continues to execute. In the similar fashion, the rest of the processes complete execution.

From the GANTT chart, we compute the average turnaround time and the average waiting
time.

Average Turnaround Time

=Sum of Turnaround Time of each Process/ Number of Processes

= (TATP1 + TATP2 + TATP3 + TATP4) / 4

= ((11 - 0) + (25 - 4) + (7 - 4) + (15 - 10)) / 4 = 10 ms

Average Waiting Time

= Sum of Waiting Time of Each Process/ Number of processes

 = (WTP1 + WTP2 + WTP3 + WTP4) / 4

= (3 + 11 + 0 + 1) / 4 = 3.75 ms

Advantages of SJF Algorithm

 In both preemptive and non-preemptive methods, the average waiting time is reduced
substantially in SJF when compared to FCFS scheduling.
 SJF optimizes turnaround time to a considerable degree.
 If execution time of each process is estimated precisely, it promises maximum
throughput.

Disadvantages of SJF Algorithm

 In situations where there is an incoming stream of processes with short burst times,
longer processes in the system may be waiting in the ready queue indefinitely leading
to starvation.
 In preemptive SJF, i.e. SRTF, if all processes arrive at different times and at frequent
intervals, the scheduler may be always working and consequently the processor may
be more engaged in process switching than actual execution of the processes.
 Correct estimation of the burst time a process is a complicated process. Since the
effectiveness of the algorithm is entirely based upon the burst times, an erroneous
calculation may cause inefficient scheduling.

Conclusion

Shortest Job First scheduling can be termed as the optimal scheduling algorithm due to its
theoretical best results. However, the implementation is much more complex and the
execution is more unpredictable than First Come First Serve or Round Robin scheduling.

Round Robin (RR) Scheduling Algorithm

Among the CPU scheduling strategies, Round Robin Scheduling is one of the most efficient
and the most widely used scheduling algorithm which finds its employability not only in
process scheduling in operating systems but also in network scheduling.

Round Robin (RR) Scheduling

This scheduling strategy derives its name from an age old round-robin principle which
advocated that all participants are entitled to equal share of assets or opportunities in a turn
wise manner. In RR scheduling, each process gets equal time slices (or time quanta) for
which it executes in the CPU in turn wise manner. When a process gets its turn, it executes
for the assigned time slice and then relinquishes the CPU for the next process in queue. If the
process has burst time left, then it is sent to the end of the queue. Processes enter the queue
on first come first serve basis.

Round Robin scheduling is preemptive, which means that a running process can be
interrupted by another process and sent to the ready queue even when it has not completed its
entire execution in CPU. It is a preemptive version of First Come First Serve (FCFS)
scheduling algorithm.

Features of Round Robin Scheduling

 RR is a fair scheduling strategy where all processes get equal share to execute in turn
wise manner.
 It is a preemptive scheduling method where an executing process must give up its
control of the CPU once its time quantum expires.
 Through RR scheduling strategy, none of the processes go into starvation.
 It is widely used for its simple working principle.
 The performance of RR scheduling is vastly dependent on the chosen time quantum.

Working Principle of Round Robin Scheduling

 Any new process that arrives the system is inserted at the end of the ready queue in
FCFS manner.
 The first process in the queue is removed and assigned to the CPU.
 If the required burst time is less than or equal to the time quantum, the process runs to
completion. The scheduler is invoked when the process completes executing to let in
the next process in the ready queue to the CPU.
 If the required burst time is more than the time quantum, the process executes up to
the allotted time quantum. Then its PCB (process control block) status is updated and
it is added to the end of the queue. Context switch occurs and the next process in the
ready queue is assigned to the CPU.
 The above steps are repeated until there are no more processes in the ready queue.

We can understand the workings RR scheduling algorithm through the aid of the following
example.

Example of Round Robin Scheduling

Let us consider a system that has four processes which have arrived at the same time in the
order P1, P2, P3 and P4. The burst time in milliseconds of each process is given by the
following table −

Process CPU Burst Times in ms

P1 8
P2 10
P3 6
P4 4

Let us consider time quantum of 2ms and perform RR scheduling on this. We will draw
GANTT chart and find the average turnaround time and average waiting time.

GANTT Chart with time quantum of 2ms

Average Turnaround Time

Average TAT = Sum of Turnaround Time of each Process / Number of Processes

=(TATP1+TATP2+TATP3+TATP4)/4

= ( 24 + 28 + 22+ 16) / 4 = 22.5 ms

In order to calculate the waiting time of each process, we multiply the time quantum with the
number of time slices the process was waiting in the ready queue.

Average Waiting Time

Average WT = Sum of Waiting Time of Each Process / Number of processes

=(WTP1+WTP2+WTP3+WTP4)/4
= ( 8*2 + 9*2+ 8*2+ 6*2) / 4 = 15.5 ms

Advantages of Round Robin Scheduling

 Round Robin scheduling is the most a fair scheduling algorithm whereby all processes
are given equal time quantum for execution.
 Starvation of any process caused by indefinite waiting in ready queue is totally
eliminated in RR scheduling.
 It does not require any complicated method to calculate the CPU burst time of each
process prior to scheduling.
 It is pretty simple to implement and so finds application in a wide range of situations.
 Convoy effect does not occur in RR scheduling as in First Come First Serve CPU
(FCFS) scheduling.

Disadvantages of Round Robin Scheduling

 The performance of Round Robin scheduling is highly dependent upon the chosen
time quantum. This requires prudent analysis before implementation, failing which
required results are not received.
 If the chosen time quantum is very large, most of the processes with complete within
the burst time. In effect, RR scheduling will act as FCFS scheduling. Thus, all the
limitations of FCFS will come into the system.
 If the chosen time quantum is too small, the CPU will be very busy in context
switching, i.e. swapping in swapping out processes to and from the CPU and memory.
 This would reduce the throughput of the system since more time will be expended in
context switching rather than actual execution of the processes.
 RR scheduling does not give any scope to assign priorities to processes. So, system
processes which need high priority gets the same preference as background processes.
This may often hamper the overall performance of a system.

Conclusion

Round Robin scheduling, if properly implemented, provide the simplest and the best
solutions to scheduling problems. A number of variations of RR scheduling are being
researched upon and implemented, in order to avoid the disadvantages of this algorithm. One
variant that helps to provide near perfect time quantum is Dynamic Time Quantum
Scheduling. Here, the time quantum dynamically varies according to the behaviour of the
processes in the system. Another variant, the Selfish Round Robin scheduling assigns
priorities to processes and provides more CPU slices to higher priority processes.