Q1 Describe about Task Scheduling

Ans: Multitasking involves the execution switching among the different tasks.
There should be some mechanism in place to share the CPU among the different tasks and to decide which
process/task is to be executed at a given point of time.
Determining which task/process is to be executed at a given point of time is known as task/process scheduling.
Task scheduling forms the basis of multitasking. Scheduling policies forms the guidelines for determining which
task is to be executed when.
The scheduling policies are implemented in an algorithm and it is run by the kernel as a service.
The kernel service/application, which implements the scheduling algorithm, is known as ‘Scheduler’.
The process scheduling decision may take place when a process switches its state to
1. ‘Ready’ state from ‘Running’ state
2. ‘Blocked/Wait’ state from ‘Running’ state
3. ‘Ready’ state from ‘Blocked/Wait’ state
4. ‘Completed’ state
A process switches to ‘Ready’ state from the ‘Running’ state when it is preempted. Hence, the type of scheduling
in scenario 1 is pre-emptive.
In preemptive/non-preemptive multitasking, the process relinquishes the CPU when it enters the ‘Blocked/Wait’
state or the ‘Completed’ state and switching of the CPU happens at this stage. Scheduling under scenario 2 can
be either preemptive or non-preemptive.
When a high priority process in the ‘Blocked/Wait’ state completes its I/O and switches to the ‘Ready’ state, the
scheduler picks it for execution if the scheduling policy used is priority based preemptive. This is indicated by
scenario 3.
Scheduling under scenario 4 can be preemptive, non-preemptive or co-operative.
Q2 Illustrate the factors should consider for the selection of a scheduling criterion/algorithm.
Ans: CPU Utilization: The scheduling algorithm should always make the CPU utilisation high. CPU utilisation is a
direct measure of how much percentage of the CPU is being utilised.
Throughput: This gives an indication of the number of processes executed per unit of time. The throughput for a
good scheduler should always be higher.
Turnaround Time: It is the amount of time taken by a process for completing its execution. It includes the time
spent by the process for waiting for the main memory, time spent in the ready queue, time spent on completing
the I/O operations, and the time spent in execution. The turnaround time should be a minimal for a good
scheduling algorithm.
Waiting Time: It is the amount of time spent by a process in the ‘Ready’ queue waiting to get the CPU time for
execution. The waiting time should be minimal for a good scheduling algorithm.
Response Time: It is the time elapsed between the submission of a process and the first response. For a good
scheduling algorithm, the response time should be as least as possible.
Note: A good scheduling algorithm has high CPU utilisation, minimum Turn Around Time (TAT), maximum
throughput and least response time.
Q3 Illustrate the process of transition through various queues
Page 1 of 14
 The Operating System maintains various queues in connection with the CPU scheduling, and a process passes
through these queues during the course of its admittance to execution completion.
The various queues maintained by OS in association with CPU scheduling are:
Job Queue: Job queue contains all the processes in the system
Ready Queue: Contains all the processes, which are ready for execution and waiting for CPU to get their turn for
execution. The Ready queue is empty when there is no process ready for running.
Device Queue: Contains the set of processes, which are waiting for an I/O device. A process migrates through all
these queues during its journey from ‘Admitted’ to ‘Completed’ stage.

Illustration of process transition through various queues

Q4 Summarize different categories of Scheduling

Ans: Based on the scheduling algorithm used, the scheduling can be classified into the following categories.
Non-preemptive Scheduling:
Non-preemptive scheduling is employed in systems, which implement non-preemptive multitasking model.
In this scheduling type, the currently executing task/process is allowed to run until it terminates or enters the
‘Wait’ state waiting for an I/O or system resource. The various types of non-preemptive scheduling adopted in
task/process scheduling are listed below.
First-Come-First-Served (FCFS)/ FIFO Scheduling:
First-Come-First-Served (FCFS) scheduling algorithm allocates CPU time to the processes based on the order in
which they enter the ‘Ready’ queue.
The first entered process is serviced first.
It is same as any real world application where queue systems are used; e.g. Ticketing reservation system where
people need to stand in a queue and the first person standing in the queue is serviced first.
FCFS scheduling is also known as First In First Out (FIFO) where the process which is put first into the ‘Ready’

Page 2 of 14
 queue is serviced first.
The major drawback of FCFS algorithm is that it favours monopoly of process. A process, which does not
contain any I/O operation, continues its execution until it finishes its task.
If the process contains any I/O operation, the CPU is relinquished by the process. In general, FCFS favours CPU
bound processes and I/O bound processes may have to wait until the completion of CPU bound process, if the
currently executing process is a CPU bound process. This leads to poor device utilisation. The average waiting
time is not minimal for FCFS scheduling algorithm.
Q5 Three processes with process IDs P1, P2, P3 with estimated completion time 10, 5, 7 milliseconds respectively
enters the ready queue together in the order P1, P2, P3. Calculate the waiting time and Turn Around Time
(TAT) for each process and the average waiting time and Turn Around Time
Ans: Three processes with process IDs P1, P2, P3 with estimated completion time 10, 5, 7 milliseconds respectively
enters the ready queue together in the order P1, P2, P3.
The sequence of execution of the processes by the CPU is represented as

Assuming the CPU is readily available at the time of arrival of P1,

P1 starts executing without any waiting in the ‘Ready’ queue.
Hence the waiting time for P1 is zero.
The waiting time for all processes are given as :
Waiting Time for P1 = 0 ms (P1 starts executing first)
Waiting Time for P2 = 10 ms (P2 starts executing after completing P1)
Waiting Time for P3 = 15 ms (P3 starts executing after completing P1 and P2)
Average waiting time = (Waiting time for all processes) / No. of Processes
= (Waiting time for (P1+P2+P3)) / 3
= (0+10+15)/3 = 25/3 = 8.33 milliseconds
Turn Around Time (TAT) for P1 = 10 ms (Time spent in Ready Queue + Execution Time)
Turn Around Time (TAT) for P2 = 15 ms (-Do-)
Turn Around Time (TAT) for P3 = 22 ms (-Do-)
Average Turn Around Time = (Turn Around Time for all processes) / No. of Processes
= (Turn Around Time for (P1+P2+P3)) / 3
= (10+15+22)/3 = 47/3 = 15.66 milliseconds
Average Turn Around Time (TAT) is the sum of average waiting time and average execution time.
Average Execution Time = (Execution time for all processes)/No. of processes
= (Execution time for (P1+P2+P3))/3
= (10+5+7)/3 = 22/3 = 7.33
Average Turn Around Time = Average waiting time + Average execution time = 8.33 + 7.33 = 15.66 m Sec
Q6 Calculate the waiting time and Turn Around Time (TAT) for each process and the Average waiting time and

Page 3 of 14
 Turn Around Time (Assuming there is no I/O waiting for the processes), if the process enters the ‘Ready’ queue
together in the order P2, P1, P3. The sequence of execution of the processes by the CPU is represented as:

Ans: AssumingtheCPUisreadilyavailableatthetimeofarrivalofP2,P2startsexecutingwithoutanywaitingin the ‘Ready’

queue. Hence the waiting time for P2 is zero. The waiting time for all processes is given as Waiting Time for
P2 = 0 ms (P2 starts executing first)
Waiting Time for P1 = 5 ms (P1 starts executing after completing P2)
WaitingTimeforP3=15ms(P3startsexecutingaftercompletingP2andP1)
Average waiting time= (Waiting time for all processes) / No. of Processes
=(Waitingtimefor(P2+P1+P3))/3
=(0+5+15)/3=20/3
=6.66 milliseconds
Turn Around Time (TAT) for P2 = 5 ms (TimespentinReadyQueue+ExecutionTime)
Turn Around Time (TAT) for P1 = 15 ms (-Do-)
Turn Around Time(TAT)forP3=22ms (-Do-)
AverageTurnAroundTime=(TurnAroundTimeforallprocesses)/No.ofProcesses
=(TurnAroundTimefor(P2+P1+P3))/3
=(5+15+22)/3=42/3
=14 milliseconds
Q7 Define Last-Come-FirstServed(LCFS)/LIFOScheduling
Ans Last-Come-FirstServed(LCFS)/LIFOScheduling:
The Last-Come-First Served (LCFS) scheduling algorithm also allocates CPU time to the processes based
ontheorderinwhichtheyare enteredinthe‘Ready’queue. Thelastenteredprocessisserviced first. LCFS scheduling is
also known as Last In First Out (LIFO) where the process, which is put last into the ‘Ready’ queue, is serviced
first.
Q8 Three processes with process IDs P1, P2, P3 with estimated completion time 10, 5, 7 ms respectively enters the
ready queue together in the order P1, P2, P3. Now a new process P4 with estimated completion time 6 ms enters
the ‘Ready’ queue after 5 ms of scheduling P1. Calculate the waiting time and Turn Around Time (TAT) for
each process and the Average waiting time and Turn Around Time.
Ans: Initially there is only P1 available in the Ready queue and the scheduling sequence will be P1, P3, P2.
P4 enters the queue during the execution of P1 and becomes the last process entered the ‘Ready’ queue. Now the
order of execution changes to P1, P4, P3, and P2 as given below.

The waiting time for all the processes is given as WaitingTimeforP1=0ms(P1startsexecutingfirst)

WaitingTimeforP4=5ms(P4startsexecutingaftercompletingP1.ButP4arrivedafter5msofexecutionof P1.

Page 4 of 14
 Henceitswaitingtime=Executionstarttime–ArrivalTime=10–5=5)
Waiting Time for P3 = 16 ms (P3 starts executing after completing P1 and P4)
WaitingTimeforP2=23ms(P2startsexecutingaftercompletingP1,P4andP3)
Average waiting time = (Waiting time for all processes) / No. of Processes
= (Waitingtimefor(P1+P4+P3+P2))/4
= (0+5+16+23)/4 =44/4
= 11 milliseconds
TurnAroundTime(TAT)forP1=10ms (TimespentinReadyQueue+ExecutionTime)
TurnAroundTime(TAT)forP4=11ms (TimespentinReadyQueue+ExecutionTime=(Execution
Start Time – Arrival Time) + Estimated ExecutionTime =
(10 – 5) + 6 = 5 + 6)
Turn Around Time (TAT) for P3 = 23 ms (Time spent in Ready Queue + Execution Time)
Turn Around Time (TAT) for P2 = 28 ms (Time spent in Ready Queue + Execution Time)
Average Turn Around Time= (Turn Around Time for all processes) / No. of Processes
=(TurnAroundTimefor(P1+P4+P3+P2))/4
=(10+11+23+28)/4= 72/4
=18 milliseconds
LCFS scheduling is not optimal and it also possesses the same drawback as that of FCFS
algorithm.
Q9 Define Shortest Job First (SJF) algorithm
Ans Scheduling Shortest Job First (SJF) scheduling algorithm ‘sorts the ‘Ready’ queue’ each time a process
relinquishes the CPU (either the process terminates or enters the ‘Wait’ state waiting for I/O or system resource)
to pick the process with shortest (least) estimated completion/run time. In SJF, the process with the shortest
estimated run time is scheduled first, followed by the next shortest process, and so on.
Q10 Three processes with process IDs P1, P2, P3 with estimated completion time 10, 5, 7 milliseconds respectively
enters the ready queue together. Calculate the waiting time and Turn Around Time (TAT) for each process and
the Average waiting time and Turn Around Time (Assuming there is no I/O waiting for the processes) in SJF
algorithm.
Ans The scheduler sorts the ‘Ready’ queue based on the shortest estimated completion time and schedules the process
with the least estimated completion time first and the next least one as second, and so on. The order in which the
processes are scheduled for execution is represented as

The estimated execution time of P2 is the least(5 ms) followedbyP3(7ms)andP1(10ms). The waiting
time for all processes are given as
WaitingTimeforP2=0ms(P2startsexecutingfirst)
WaitingTimeforP3=5ms(P3startsexecutingaftercompletingP2)
WaitingTimeforP1=12ms(P1startsexecutingaftercompletingP2andP3) Average waiting time=

Page 5 of 14
 (Waiting time for all processes) / No. of Processes
=(Waitingtimefor(P2+P3+P1))/3
=(0+5+12)/3=17/3
=5.66 milliseconds
Turn Around Time (TAT) for P2 = 5 ms (TimespentinReadyQueue+ExecutionTime) Turn Around
Time (TAT) for P3 = 12 ms (-Do-)
TurnAroundTime(TAT)forP1=22ms (-Do-)
AverageTurnAroundTime=(TurnAroundTimeforallprocesses)/No.ofProcesses
=(TurnAroundTimefor(P2+P3+P1))/3
=(5+12+22)/3=39/3
=13 milliseconds
AverageTurnAroundTime(TAT)isthesumofaveragewaitingtimeandaverageexecutiontime.
The average Execution time= (Execution time for all processes)/No. of processes
=(Executiontimefor(P1+P2+P3))/3
=(10+5+7)/3=22/3=7.33
AverageTurnAroundTime=AverageWaitingtime+AverageExecutiontime
=5.66 +7.33
=13 milliseconds
Q11 Three processes with process IDs P1, P2, P3 with estimated completion time 10, 5, 7 milliseconds respectively
enters the ready queue together. Now a new process P4 with estimated completion time 2 ms enters the ‘Ready’
queue after 2 ms of execution of P2. Calculate the waiting time and Turn Around Time (TAT) for each process
and the Average waiting time and Turn Around Time in SJF algorithm.
Ans Assume all the processes contain only CPU operation and no I/O operations are involved. At the beginning, there
are only three processes (P1, P2 and P3) available in the ‘Ready’ queue and the SJF scheduler picks up the
process with the least execution completion time (In this example P2 with execution completion time 5 ms) for
scheduling. Now process P4 with estimated execution completion time 2 ms enters the ‘Ready’ queue after 2 ms
of start of execution of P2. Since the SJF algorithm is non-preemptive and process P2 does not contain any I/O
operations, P2 continues its execution. After 5 ms of scheduling, P2 terminates and now the scheduler again sorts
the ‘Ready’ queue for process with least execution completion time. Since the execution completion time for P4
(2 ms) is less than that of P3 (7 ms), which was supposed to be run after the completion of P2 as per the ‘Ready’
queue available at the beginning of execution scheduling, P4 is picked up for executing. Due to the arrival of the
process P4 with execution time 2 ms, the ‘Ready’ queue is re-sorted in the order P2, P4, P3, P1. At the beginning
it was P2, P3, P1. The execution sequence now changes as per the following diagram:

The waiting time for all the processes are given as

Waiting time for P2=0ms(P2startsexecuting first)

Page 6 of 14
 Waiting time forP4=3 ms(P4 startsexecutingaftercompletingP2.ButP4arrived after 2 msofexecution of P2.
Hence its waiting time = Execution start time – Arrival Time = 5 – 2 = 3)
Waiting time for P3 = 7 ms (P3 starts executing after completing P2 and P4)
Waiting time for P1=14ms(P1startsexecutingaftercompletingP2,P4andP3)
Average waiting time= (Waiting time for all processes) / No. of Processes
=(Waitingtimefor(P2+P4+P3+P1))/4
=(0 +3+7 +14)/4=24/4
=6 milliseconds
Turn Around Time(TAT)forP2=5ms(TimespentinReadyQueue+ExecutionTime)
TurnAroundTime(TAT)forP4=5ms(TimespentinReadyQueue+ExecutionTime=(ExecutionStart
Time– ArrivalTime) +EstimatedExecutionTime= (5 –2)+ 2
=3 +2)
Turn Around Time (TAT) for P3 = 14 ms (Time spent in Ready Queue + Execution Time) Turn
Around Time (TAT) for P1 = 24 ms (Time spent in Ready Queue + Execution Time) Average Turn
Around Time= (Turn Around Time for all Processes) / No. of Processes
=(TurnAroundTimefor(P2+P4+P3+P1))/4
=(5+5+14+24)/4= 48/4
=12 milliseconds
Q12 Define Priority Based Scheduling Algorithm
Ans The Turn Around Time (TAT) and waiting time for processes in non-preemptive scheduling varies with the type
of scheduling algorithm. Priority based non-preemptive scheduling algorithm ensures that a process with high
priority is serviced at the earliest compared to other low priority processes in the ‘Ready’ queue. The priority of a
task/process can be indicated through various mechanisms. The Shortest Job First (SJF) algorithm can be viewed
as a priority based scheduling where each task is prioritised in the order of the time required to complete the task.
The lower the time required for completing a process the higher is its priority in SJF algorithm. Another way of
priority assigning is associating a priority to the task/process at the time of creation of the task/process. The
priority is a number ranging from 0 to the maximum priority supported by the OS. The maximum level of
priority is OS dependent. For Example, Windows CE supports 256 levels of priority (0 to 255 priority numbers).
While creating the process/task, the priority can be assigned to it. The priority number associated with a
task/process is the direct indication of its priority. The priority variation from high to low is represented by
numbers from 0 to the maximum priority or by numbers from maximum priority to 0. For Windows CE
operating system a priority number 0 indicates the highest priority and 255 indicates the lowest priority. This
convention need not be universal and it depends on the kernel level implementation of the priority structure. The
non-preemptive priority based scheduler sorts the ‘Ready’ queue based on priority and picks the process with the
highest level of priority for execution.

Q13 Three processes with process IDs P1, P2, P3 with estimated completion time 10, 5, 7 milliseconds and priorities
0, 3, 2 (0—highest priority, 3—lowest priority) respectively enters the ready queue together. Calculate the
waiting time and Turn Around Time (TAT) for each process and the Average waiting time and Turn Around

Page 7 of 14
 Time (Assuming there is no I/O waiting for the processes) in priority based scheduling algorithm.
Ans The scheduler sorts the ‘Ready’ queue based on the priority and schedules the process with the highest priority
(P1 with priority number 0) first and the next high priority process (P3 with priority number 2) as second, and so
on. The order in which the processes are scheduled for execution is represented as

The waiting time for all the processes are given as

WaitingtimeforP1=0ms(P1startsexecutingfirst)
Waiting time for P3 = 10 ms (P3 starts executing after completing P1)
WaitingtimeforP2=17ms(P2startsexecutingaftercompletingP1andP3) Average waiting time=
(Waiting time for all processes) / No. of Processes
=(Waitingtimefor(P1+P3+P2))/3
=(0+10+17)/3=27/3
=9 milliseconds
Turn Around Time (TAT) for P1 = 10 ms (TimespentinReadyQueue+ExecutionTime) Turn Around
Time (TAT) for P3 = 17 ms(-Do-)
TurnAroundTime(TAT)forP2=22ms (-Do-)
AverageTurnAroundTime=(TurnAroundTimeforallprocesses)/No.ofProcesses
=(TurnAroundTimefor(P1+P3+P2))/3
=(10+17+22)/3= 49/3
=16.33 milliseconds

Q14 Calculate the waiting time and Turn Around Time (TAT) for each process and the Average waiting time and
Turn Around Time, if a new process P4 with estimated completion time 6 ms and priority 1 enters the ‘Ready’
queue after 5 ms of execution of P1.
Ans Assume all the processes contain only CPU operation and no I/O operations are involved. At the beginning, there
are only three processes (P1, P2 and P3) available in the ‘Ready’ queue and the scheduler picks up the process
with the highest priority (In this example P1 with priority 0) for scheduling. The execution sequence diagram for
this is same as that of Example 1. Now process P4 with estimated execution completion time 6 ms and priority 1
enters the ‘Ready’ queue after 5 ms of execution of P1. Since the scheduling algorithm is non-preemptive and
process P1 does not contain any I/O operations, P1 continues its execution. After 10 ms of scheduling, P1
terminates and now the scheduler again sorts the ‘Ready’ queue for process with highest priority. Since the
priority for P4 (priority 1) is higher than that of P3 (priority 2), which was supposed to be run after the
completion of P1 as per the ‘Ready’ queue available at the beginning of execution scheduling, P4 is picked up
for executing. Due to the arrival of the process P4 with priority 1, the ‘Ready’ queue is resorted in the order P1,
P4, P3, P2. At the beginning it was P1, P3, P2.
The execution sequence now changes as:

Page 8 of 14
 The waiting time for all the processes are given as
WaitingtimeforP1=0ms(P1startsexecutingfirst)
WaitingtimeforP4=5ms(P4startsexecutingaftercompletingP1.ButP4arrivedafter5msofexecutionof P1. Hence its
waiting time = Execution start time – Arrival Time = 10 – 5 = 5)
Waiting time for P3 = 16 ms (P3 starts executing after completing P1 and P4)
WaitingtimeforP2=23ms(P2startsexecutingaftercompletingP1,P4andP3) Average waiting time=
(Waiting time for all processes) / No. of Processes
=(Waitingtimefor(P1+P4+P3+P2))/4
=(0+5+16+23)/4 =44/4
=11 milliseconds
Turn Around Time (TAT) for P1 = 10 ms (TimespentinReadyQueue+ExecutionTime) Turn Around
Time (TAT) for P4 = 11 ms(Time spent in Ready Queue + Execution Time = (Execution Start Time
– Arrival Time) + Estimated Execution Time = (10 – 5) + 6 = 5 + 6)
Turn Around Time (TAT) for P3 = 23 ms (Time spent in Ready Queue + Execution Time)
Turn Around Time (TAT) for P2 = 28 ms (Time spent in Ready Queue + Execution Time) Average
Turn Around Time= (Turn Around Time for all processes) / No. of Processes
=(TurnAroundTimefor(P2+P4+P3+P1))/4
=(10 +11+23 +28)/4=72/4
=18 milliseconds

Q15 Define Preemptive Scheduling

Ans Preemptive scheduling is employed in systems, which implements preemptive multitasking model. In preemptive
scheduling, every task in the ‘Ready’ queue gets a chance to execute. When and how often each process gets a
chance to execute (gets the CPU time) is dependent on the type of preemptive scheduling algorithm used for
scheduling the processes. In this kind of scheduling, the scheduler can preempt (stop temporarily) the currently
executing task/process and select another task from the ‘Ready’ queue for execution. When to pre-empt a task
and which task is to be picked up from the ‘Ready’ queue for execution after preempting the current task is
purely dependent on the scheduling algorithm. A task which is preempted by the scheduler is moved to the
‘Ready’ queue. The act of moving a ‘Running’ process/task into the ‘Ready’ queue by the scheduler, without the
processes requesting for it is known as ‘Preemption’. Preemptive scheduling can be implemented in different
approaches. The two important approaches adopted in preemptive scheduling are time-based preemption and
priority-based preemption. The various types of preemptive scheduling adopted in task/process scheduling are
explained below.
Q15 Define Preemptive SJF Scheduling/Shortest Remaining Time (SRT):
Ans Preemptive SJF Scheduling/Shortest Remaining Time (SRT):

Page 9 of 14
 The non-preemptive SJF scheduling algorithm sorts the ‘Ready’ queue only after completing the execution of the
current process or when the process enters ‘Wait’ state, whereas the preemptive SJF scheduling algorithm sorts
the ‘Ready’ queue when a new process enters the ‘Ready’ queue and checks whether the execution time of the
new process is shorter than the remaining of the total estimated time for the currently executing process. If the
execution time of the new process is less, the currently executing process is preempted and the new process is
scheduled for execution. Thus preemptive SJF scheduling always compares the execution completion time (It is
same as the remaining time for the new process) of a new process entered the ‘Ready’ queue with the remaining
time for completion of the currently executing process and schedules the process with shortest remaining time for
execution. Preemptive SJF scheduling is also known as Shortest Remaining Time (SRT) scheduling.
Q16 Three processes with process IDs P1, P2, P3 with estimated completion time 10, 5, 7 milliseconds respectively
enters the ready queue together. A new process P4 with estimated completion time 2 ms enters the ‘Ready’
queue after 2 ms. Assume all the processes contain only CPU operation and no I/O operations are involved. At
the beginning, there are only three processes (P1, P2 and P3) available in the ‘Ready’ queue and the SRT
scheduler picks up the process with the shortest remaining time for execution completion (P2 with remaining
time 5 ms) for scheduling. The execution sequence diagram for this is same as that of example 1 under non-
preemptive SJF scheduling. Now process P4 with estimated execution completion time 2 ms enters the ‘Ready’
queue after 2 ms of start of execution of P2. Since the SRT algorithm is preemptive, the remaining time for
completion of process P2 is checked with the remaining time for completion of process P4. The remaining time
for completion of P2 is 3 ms which is greater than that of the remaining time for completion of the newly entered
process P4 (2 ms). Hence P2 is preempted and P4 is scheduled for execution. P4 continues its execution to finish
since there is no new process entered in the ‘Ready’ queue during its execution. After 2 ms of scheduling P4
terminates and now the scheduler again sorts the ‘Ready’ queue based on the remaining time for completion of
the processes present in the ‘Ready’ queue. Since the remaining time for P2 (3 ms), which is preempted by P4 is
less than that of the remaining time for other processes in the ‘Ready’ queue, P2 is scheduled for execution. Due
to the arrival of the process P4 with execution time 2 ms, the ‘Ready’ queue is re-sorted in the order P2, P4, P2,
P3, P1. At the beginning it was P2, P3, P1. The execution sequence now changes as per the following diagram

Ans Thewaitingtimeforalltheprocessesaregiven as
WaitingtimeforP2=0ms+ (4 –2)ms=2 ms(P2startsexecutingfirstandisinterruptedbyP4andhasto wait till the
completion of P4 to get the next CPU slot)
Waiting time for P4 = 0 ms (P4 starts executing by preempting P2 since the execution time for completion of
P4 (2 ms) is less than that of the Remaining time for execution completion of P2 (Here it is 3
ms))
Waiting time for P3 = 7 ms (P3 starts executing after completing P4 and P2)
WaitingtimeforP1=14ms(P1startsexecutingaftercompletingP4,P2andP3) Average waiting time=

Page 10 of 14
 (Waiting time for all the processes) / No. of Processes
=(Waitingtimefor(P4+P2+P3+P1))/4
=(0 +2+7 +14)/4=23/4
=5.75 milliseconds
TurnAroundTime(TAT)forP2=7ms(TimespentinReadyQueue+ExecutionTime)
TurnAroundTime(TAT)forP4=2ms(TimespentinReadyQueue+ExecutionTime=(ExecutionStart
Time–ArrivalTime)+EstimatedExecutionTime=(2 –2)+2) Turn Around Time (TAT)
for P3 = 14 ms(Time spent in Ready Queue + Execution Time)
TurnAround Time(TAT)forP1 =24 ms (Timespentin ReadyQueue+ExecutionTime)
AverageTurnAroundTime=(TurnAroundTimeforalltheprocesses)/No.ofProcesses
=(TurnAroundTimefor(P2+P4+P3+P1))/4
=(7+2+14+24)/4= 47/4
=11.75 milliseconds

Q17 Explain Round Robin (RR) Scheduling:

Ans Round Robin (RR) Scheduling:
The term Round Robin is very popular among the sports and games activities. You might have heard about
‘Round Robin’ league or ‘Knock out’ league associated with any football or cricket tournament. In the ‘Round
Robin’ league each team in a group gets an equal chance to play against the rest of the teams in the same group
whereas in the ‘Knock out’ league the losing team in a match moves out of the tournament ☺. In the process
scheduling context also, ‘Round Robin’ brings the same message “Equal chance to all”. In Round Robin
scheduling, each process in the ‘Ready’ queue is executed for a pre-defined time slot. The execution starts with
picking up the first process in the ‘Ready’ queue (see Fig. 10.13). It is executed for a pre-defined time and when
the pre-defined time elapses or the process completes (before the pre-defined time slice), the next process in the
‘Ready’ queue is selected for execution. This is repeated for all the processes in the ‘Ready’ queue. Once each
process in the ‘Ready’ queue is executed for the pre-defined time period, the scheduler comes back and picks the
first process in the ‘Ready’ queue again for execution. The sequence is repeated. This reveals that the Round
Robin scheduling is similar to the FCFS scheduling and the only difference is that a time slice based preemption
is added to switch the execution between the processes in the ‘Ready’ queue. The ‘Ready’ queue can be
considered as a circular queue in which the scheduler picks up the first process for execution and moves to the
next till the end of the queue and then comes back to the beginning of the queue to pick up the first process.

Page 11 of 14
 The time slice is provided by the timer tick feature of the time management unit of the OS kernel (Refer the Time
management section under the subtopic ‘The Real-Time kernel’ for more details on Timer tick). Time slice is
kernel dependent and it varies in the order of a few microseconds to milliseconds. Certain OS kernels may allow
the time slice as user configurable. Round Robin scheduling ensures that every process gets a fixed amount of
CPU time for execution. When the process gets its fixed time for execution is determined by the FCFS policy
(That is, a process entering the Ready queue first gets its fixed execution time first and so on…). If a process
terminates before the elapse of the time slice, the process releases the CPU voluntarily and the next process in the
queue is scheduled for execution by the scheduler..

Q18 Three processes with process IDs P1, P2, P3 with estimated completion time 6, 4, 2 milliseconds respectively,
enters the ready queue together in the order P1, P2, P3. Calculate the waiting time and Turn Around Time (TAT)
for each process and the Average waiting time and Turn Around Time (Assuming there is no I/O waiting for the
processes) in RR algorithm with Time slice = 2 ms.

The scheduler sorts the ‘Ready’ queue based on the FCFS policy and picks up the first process P1 from the
‘Ready’ queue and executes it for the time slice 2 ms. When the time slice is expired, P1 is preempted and P2 is
scheduled for execution. The Time slice expires after 2ms of execution of P2. Now P2 is preempted and P3 is
picked up for execution. P3 completes its execution within the time slice and the scheduler picks P1 again for
execution for the next time slice. This procedure is repeated till all the processes are serviced. The order in which
the processes are scheduled for execution is represented as

Ans Thewaitingtimeforalltheprocessesaregiven as

Page 12 of 14
 Waitingtime forP1=0 +(6– 2)+(10– 8)=0 +4+2=6 ms
(P1 startsexecuting firstand waits for two time slicesto getexecutionbackandagain 1 time slice for
getting CPU time)
Waitingtime forP2=(2–0)+(8–4)=2+4=6ms
(P2 starts executing after P1 executes for 1 time slice and waits for two time slices to get the CPU
time)
Waitingtime forP3=(4–0)=4ms
(P3starts executingafter completing the first time slices for P1 andP2 and completes its execution
in a single time slice)
Averagewaitingtime=(Waitingtimeforalltheprocesses)/No.ofProcesses
=(Waitingtimefor(P1+P2+P3))/3
=(6 +6+4)/3=16/3
=5.33 milliseconds
Turn Around Time (TAT) for P1 = 12 ms (TimespentinReadyQueue+ExecutionTime)
Turn Around Time (TAT) for P2 = 10 ms (-Do-)
TurnAroundTime(TAT)forP3=6ms (-Do-)
AverageTurnAroundTime=(TurnAroundTimeforalltheprocesses)/No.ofProcesses
=(TurnAroundTimefor(P1+P2+P3))/3
=(12 +10 +6)/3=28/3
=9.33 milliseconds
AverageTurnAroundTime(TAT)isthesumofaveragewaitingtimeandaverageexecutiontime.
Average Execution time= (Execution time for all the process)/No. of processes
=(Executiontimefor(P1+P2+P3))/3
=(6+4+2)/3=12/3=4
AverageTurnAroundTime=AverageWaitingtime+AverageExecutiontime
=5.33 +4
=9.33 milliseconds
RR scheduling involves lot of overhead in maintaining the time slice information for every process which is
currently being executed.

Priority Based Scheduling Priority based preemptive scheduling algorithm is same as that of the non-preemptive
priority based scheduling except for the switching of execution between tasks. In preemptive scheduling, any
high priority process entering the ‘Ready’ queue is immediately scheduled for execution whereas in the non-
preemptive scheduling any high priority process entering the ‘Ready’ queue is scheduled only after the currently
executing process completes its execution or only when it voluntarily relinquishes the CPU. The priority of a
task/ process in preemptive scheduling is indicated in the same way as that of the mechanism adopted for non-
preemptive multitasking.
Three processes with process IDs P1, P2, P3 with estimated completion time 10, 5, 7 milliseconds and priorities
1, 3, 2 (0—highest priority, 3—lowest priority) respectively enters the ready queue together. A new process P4
with estimated completion time 6 ms and priority 0 enters the ‘Ready’ queue after 5 ms of start of execution of
P1. Assume all the processes contain only CPU operation and no I/O operations are involved. At the beginning,
there are only three processes (P1, P2 and P3) available in the ‘Ready’ queue and the scheduler picks up the
process with the highest priority (In this example P1 with priority 1) for scheduling. Now process P4 with
estimated execution completion time 6 ms and priority 0 enters the ‘Ready’ queue after 5 ms of start of execution
of P1. Since the scheduling algorithm is preemptive, P1 is preempted by P4 and P4 runs to completion. After 6
ms of scheduling, P4 terminates and now the scheduler again sorts the ‘Ready’ queue for process with highest
priority. Since the priority for P1 (priority 1), which is preempted by P4 is higher than that of P3 (priority 2) and
P2 ((priority 3), P1 is again picked up for execution by the scheduler. Due to the arrival of the process P4 with

Page 13 of 14
priority 0, the ‘Ready’ queue is resorted in the order P1, P4, P1, P3, P2. At the beginning it was P1, P3, P2. The
execution sequence now changes as per the following diagram

Thewaitingtimeforalltheprocessesaregivenas Waitingtime forP1=0+(11–

5)=0+6=6ms
(P1 starts executing first and gets preempted by P4 after 5 ms and again gets the CPU time after
completion of P4)
WaitingtimeforP4=0ms
(P4startsexecutingimmediatelyonenteringthe‘Ready’queue,bypreemptingP1) Waiting time for P3 =
16 ms (P3 starts executing after completing P1 and P4)
WaitingtimeforP2=23ms(P2startsexecutingaftercompletingP1,P4andP3) Average waiting time=
(Waiting time for all the processes) / No. of Processes
=(Waitingtimefor(P1+P4+P3+P2))/4
=(6+0+16+23)/4 =45/4
=11.25 milliseconds
TurnAroundTime(TAT)forP1=16ms (TimespentinReadyQueue+ExecutionTime)
TurnAroundTime(TAT)forP4=6ms
(TimespentinReadyQueue+ExecutionTime=(ExecutionStartTime–ArrivalTime)
+EstimatedExecutionTime=(5–5)+6=0+ 6)
Turn Around Time (TAT) for P3 = 23 ms (Time spent in Ready Queue + Execution Time) Turn
Around Time (TAT) for P2 = 28 ms (Time spent in Ready Queue + Execution Time) Average Turn
Around Time= (Turn Around Time for all the processes) / No. of Processes
=(TurnAroundTimefor(P2+P4+P3+P1))/4
=(16+6+23+28)/4= 73/4
=18.25 milliseconds

Page 14 of 14