Operating System – Module II Notes – Part I Processes, Threads, CPU Scheduling

Process Concept

 A process is a program under execution.

 A process comprises of :
o the program code ( known as text section )
o a data section ( a set of global variables )
o and the process control block (PCB)
o the process stack, which contains temporary data (such as function parameters, return addresses, and
local variables),
o A process heap is memory that is dynamically allocated during process run time.
 The structure of a process in memory is shown in Figure:

Program Vs. Process

 A program is a passive entity, such as a file containing a list of instructions stored on disk (often called an
executable file), whereas a process is an active entity, with a program counter specifying the next instruction to
execute and a set of associated resources.
 A program becomes a process when an executable file is loaded into memory
 There can be either one-to-one or one-to-many relationship between programs and processes. If a single
instance of a program is running on the system, the relationship is one-to-one. If multiple instances of a single
program are running simultaneously, there exists a one-to-may relationship between programs and processes.
Text section of multiple instances will be same but the data section will be different.

Page 1 of 19
Operating System – Module II Notes – Part I Processes, Threads, CPU Scheduling

 Processes can be either CPU-bound ( processes which involve higher computation that I/O, speed of execution
is governed by CPU ) or I/O-bound ( processes involve a lot of I/O operations, speed of execution is governed
by I/O device )

PROCESS STATES

State indicates the nature of current activity in a process. A process may be in one of the following states depending
on its current activity.

 New State : A process is said to be in ‘new’ state if it is being created

 Ready State : A process is said to be in ready state if it is ready for execution and waiting for the CPU to be
allocated to it.
 Running State : A process is said to be in running state if the CPU has been allocated to it and it is being
executed
 Waiting State : A process is said to be in ‘waiting’ state ( blocked state ) if it has been blocked by some
event such as completion of some I/O operation, reception of some signal etc. Processes in waiting state are
unable to run even if CPU is available.
 Terminated State : A process is said to be in terminated state if it has completed its execution normally or it
has been terminated abnormally by the OS or killed by some other process

Process State Transitions

Each process undergoes changes or transitions in state during its lifetime. The possible state transitions and their
causes are as follows :

Fig : Process State transition diagram

New - > Ready :- This transition takes place if a new process has been loaded into the main memory and it
is waiting for the CPU to be allocated to it.
Ready - > Running :- This transition takes place if the CPU has been allocated to a ready process and it has
started its execution
Running - > Ready :- This transition may occur if :
Page 2 of 19
Operating System – Module II Notes – Part I Processes, Threads, CPU Scheduling

 Time slice of the currently running process has expired

 Some higher priority process gets ready for execution etc.

Running - > Waiting :- This transition may take place if the currently running process:

 Needs to perform some I/O operation

 Has to wait for some message to some action from another process
 Requests for some other resources

Running - > Terminated :- This transition takes place if :

 The running process completed its task and requests OS for its termination
 The running process is terminated by its parent process
 The running process is terminated by the kernel because it has exceeded its resource usage limit or
involved in a deadlock

Waiting - > Ready :- This transition takes place if an event for which the process was waiting , has
occurred.

Process control block (PCB) and its general structure

 To keep track of all the processes in the system, the OS maintains a structurally organize table called process
table that includes an entry for each process. This entry is called process control block (PCB) – a data
structure created by OS for representing a process.
 The basic purpose of PCB is to indicate the progress of a process so far.
 A PCB stores descriptive information related to a process such as its state, program counter, memory
management information, information about its scheduling, allocated resources, accounting information etc.
 A PCB structure is shown in figure below :

 Some of the important fields stored in a PCB are as follows:

o Process Number ( PID ) :- Each process is assigned a unique identification number called process
identifier (PID) by the OS at the time of its creation. PID is used to refer the process in the sytem

Page 3 of 19
Operating System – Module II Notes – Part I Processes, Threads, CPU Scheduling

o Process State : It stores the current state of the process that can be new, ready , running, waiting or
terminated
o Program counter: It contains the address of the instruction that is to be executed in the process
next.
o CPU registers : They store the contents of index registers, general purpose registers, condition code
information, etc. at the time when the CPU was last freed from the process or pre-empted from the
process.
o Event Information : If the process is in waiting state then this field contain the information about
the event for which the process is waiting.
o Memory management information: It includes information related to the memory configuration
for a process such as the value of base and limit registers, the page tables etc.
o CPU scheduling information : It includes the information used by scheduling algorithms such as
process priority number, the pointers to appropriate scheduling queues, the time when CPU was last
allocated to the process etc.
o I/O status : It includes information like I/O devices allocated to a process, pointers to the files
opened by the process for I/O, the current position in the files etc.

Thread Concepts

 A thread is defined as the fundamental unit of CPU utilization

 A traditional process includes a single thread of control capable of executing one task at a time and is
referred to as single threaded process.
 For a process to perform multiple tasks simultaneously, multiple threads of a single process can be created
with each thread having its own ID, stack and set of registers. In addition all the threads of the same process
share each other the code section, data section and other resources including open files, child processes,
signals, etc. A process with multiple threads of control is referred to as a multithreaded process.

Fig: Structure of single-threaded and multithreaded process

Page 4 of 19
Operating System – Module II Notes – Part I Processes, Threads, CPU Scheduling

Thread versus Process

Process Thread

1. Concurrent processes within a single A low-cost alternative to achieve concurrency

application incurs high process switching within an application is to use multiple
overhead ( saving the context of current threads.
process and loading the context of new
process) and thus very expensive Thread switching is considerably faster than
process switching, reducing the switching
overhead (The operating system needs to
save only the CPU state and stack pointer
while switching between threads of the same
process.)

2 Processes may be independent units A thread is a subset of a process, that is , it is

dependent on the process

3 Each child process has a separate address Threads belonging to the same process share
space from that of its parent process the address space of its parent process

4 When a process is created, a PCB is A thread typically requires fewer resources

allocated, which is a large data than process. When a thread is created, the OS
[Link] includes memory map, list of allocates to it a data structure that holds set of
open files, environment variables etc. registers, stack, and priority of the thread.

Advantages of threads
1) Threads provide low switching overhead over processes
2) Computational speedup by rapidly switching among multiple threads
3) Thread creation is more economical than process creation ( threads share resources )
4) Threads communicate efficiently via shared memory without executing system calls.
5) Threads utilize multiprocessor architecture properly by running multiple threads of a single process on
different CPUs at the same time
6) Multithreaded interactive processes have increased responsiveness
Implementation of Threads
 Kernel-level Threads
o Kernel is responsible for creating, scheduling and managing thread within the kernel space.
o Kernel maintains a thread table in addition to the process table that holds the program counter, stack
pointer, registers, state etc. of each thread in the system.

Page 5 of 19
Operating System – Module II Notes – Part I Processes, Threads, CPU Scheduling

o Advantages :
 Multiple kernel-level threads belonging to a process can be scheduled to run simultaneously
on different CPUs in a multiprocessor environment. Thus computation speedup can be
achieved
 If one thread is blocked by some system call, kernel can choose another thread to run from
the same process or from different process
o Disadvantages:
 The cost of creating and destroying threads is relatively greater
 Thread switching by kernel is an overhead to the system
 User-level Threads
o User-level threads are implemented by a thread library associated with the code of a process.
o Whenever a process wishes to create or terminate a thread, it can do so by calling an appropriate
function from the thread library without the need of kernel intervention.
o Each process maintains their own thread table. Kernel maintains only the process table.
o Examples for thread libraries : Pthreads, UI-threads, C-threads etc.
o Advantages :
 Thread creation and management is faster than kernel threads
 Thread switching overhead is smaller because no need to issue system calls
 Thread library can use best schedule policy for threads that suits the process’s nature ( for
instance, priority-based policy for real-time process, round-robin policy for web server etc. )
o Disadvantages:
 At most, one user level thread can be in operation, limiting the degree of parallelism
 If one thread is blocked, the whole process will get blocked. This is because the kernel does
not know the difference between a thread and a process.

Process Scheduling

 When two or more processes compete for the CPU at the same time then a choice has to be made as to which
process to allocate the CPU next. This procedure of determining the next process to be executed on the CPU
is called process scheduling.
 The module of the OS that makes this decision is called scheduler.

Scheduling Queues

 Job queue: As the processes enter the system for execution, they are kept in a queue called job queue ( or
input queue ) on a mass storage device such as hard disk.

Page 6 of 19
Operating System – Module II Notes – Part I Processes, Threads, CPU Scheduling

 Ready Queue: From the job queue, the processes which are ready for execution are shifted into the main
memory and kept there in a queue called ready queue. Ready queue contains processes that are waiting for
CPU.
 Device Queue: For each I/O device in the system, a separate queue is maintained which is called device
queue. The process that needs to perform I/O during its execution is kept into this queues and it waits there
until it is served by the device.
Both ready queue and device queue are maintained as linked lists that contains PCBs of the processes in the queue
as nodes. Each PCB includes a pointer to the PCB of the next process in the queue as shown in diagram.

The header node contains pointers to the PCBs of the first and the last process in the queue.

Queuing Diagram

Process scheduling can be represented with the help of queuing diagram as shown above
Once CPU is allocated to a process in the ready queue, the following transitions may occur :
 If the process needs to perform some I/O operation during its execution , it will be moved to the device
queue. When the process completes its I/O operation , it will be switched from device queue to ready queue.
 If an interrupt occurs, the current process has to wait until the interrupt is handled. After that the process is
put back to the ready queue.
 If the process creates a new process, it has to wait until the child process terminates. After that it is again put
back to the ready queue.
 If the time slice of the process has expired, the process is put back into the ready queue.
 If the process has successfully completed its task, it is terminated. All allocated resources will be released

Page 7 of 19
Operating System – Module II Notes – Part I Processes, Threads, CPU Scheduling

Types of Schedulers

Scheduler is the component of OS that selects processes from various queues in order to allocate the required
resources to them for execution.
Fig : Types of schedulers

The following types of schedulers may exist in a complex operating system:

 Long-term scheduler
o It is also known as job scheduler, which works with job queue.
o It selects the next process to be executed form job queue and loads it into the main memory for
execution.
o To achieve best performance, the long-term scheduler must select the processes in such a way that
some of the processes are CPU-bound while others are I/O-bound.
o The main objective of this scheduler is to control the degree of multiprogramming in order to keep
the processor utilization at the desired level.
o The long term scheduler is generally invoked only when a process exits from the system. The
frequency of invocation of long-term scheduler is much lower than other two types of schedulers
 Short-term scheduler
o It is also known as CPU scheduler or Process Scheduler
o It selects a process from ready queue and allocates CPU to it.
o This scheduler is frequently invoked as compared to long-term scheduler because a process
generally executes for a short period and then it may have to wait for I/O or something else.
o CPU scheduler must be fast in order to provide the least time gap between executions.
 Medium-term scheduler
o It is also known as swapper

Page 8 of 19
Operating System – Module II Notes – Part I Processes, Threads, CPU Scheduling

o It is used when a process is to be removed ( Swap-out)from ready queue or from CPU in case the
process is executing. This removed process is then kept at some space on the hard disk and later
brought ( swap-in) into the memory to restart execution from the point where it left off.
o Its objective is to reduce the degree of multiprogramming
o The task of temporarily switching a process in and out of main memory is known as swapping.
o It is usually invoked when there is some unoccupied space in the memory made by the termination
of a process or if the supply of ready processes reduces below a specified limit.

Context Switching

Diagram showing CPU switches from process to process is shown below :

 Transferring the control of CPU from one process to another needs saving of the context of the currently
running process and loading the context of another ready process
 The mechanism of saving and restoring the context is known as context switch
 The context is represented in the PCB of the process. The portion of PCB including the process state,
memory management information, CPU scheduling information together constitute the context ( state
information ) of a process.
 Context Switch may occur due to a number of reasons such as :
o The current process terminates and exits from the system
o The time slice of the current process expires
o The process has to wait for I/O or some other resource
o Some higher priority process enters the system
o The process relinquishes the CPU by invoking some system call
 Context Switching is performed in two steps :

Page 9 of 19
Operating System – Module II Notes – Part I Processes, Threads, CPU Scheduling

o Save Context : In this step, the kernel saves the context of the currently executing process in its
PCB so that it can restore this context while resuming its execution later.
o Restore Context : In this step, the kernel loads the saved context of a different process that is to be
executed next.
 Context –switch time is pure overhead because the system does no useful work during this time.
 The speed of context switch is highly dependent on machine features such as memory speed, number of
registers to be copied, existence of special instructions ( for instance, single instruction to load or store all
registers ) etc.

CPU and I/O burst cycles

 The process execution comprises alternate cycles of CPU and I/O burst as shown in figure:

 Process execution consists of a cycle of CPU execution and I/O wait.

 The time period elapsed in processing before performing next I/O operation is known as CPU burst and the
time period elapsed in performing I/O before the next CPU burst is known as I/O Burst.
 Generally, the process execution starts with a CPU burst , followed by an I/O burst, then again by a CPU
burst and so on until the termination of the process
 The length of the CPU burst and the I/O burst varies from process to process depending on whether the
process is CPU-bound or I/O-bound. If the process is CPU-Bound, it will have longer CPU bursts as
compared to I/O bursts , and vice versa.
Dispatcher
 It is a module or component of operating system that gives control of the CPU to the process selected by the
short-term scheduler (CPU scheduler )
 Dispatcher performs its function in 3 steps :

Page 10 of 19
Operating System – Module II Notes – Part I Processes, Threads, CPU Scheduling

o Context switching ( save the state information of current process & load the state information of next
process to be executed )
o The system switches from kernel mode to user mode as a user process is to be executed
o Start execution of the process from the interrupted position or from first instruction, if the process is
new.
 Dispatcher should be as fast as possible. The time taken by the dispatcher to stop one process and start
another running is known as the dispatch latency.

Preemptive versus Non-preemptive scheduling

 OS take scheduling decisions under following situations :

1. When a process switches from running to waiting state
2. When a process switches from running to ready state due to occurrence of an interrupt
3. When a process switches from waiting state to ready state
4. When a process terminates and exits the system
 Non-preemptive Scheduling
o Under non-preemptive scheduling, once the CPU has been allocated to a process, it cannot be taken back
until the process voluntarily releases it either by terminating it or by switching to the waiting state.
o Non-preemptive scheduling is also known as cooperative or voluntary scheduling
o Examples for non-preemptive scheduling algorithms are : First-Come First-Served ( FCFS ), Shortest
Job First ( SJF ), non-preemptive Priority-based Scheduling
 Pre-emptive Scheduling
o Under pre-emptive scheduling, the CPU can be forcibly taken back from the currently running process
before its completion and can be allocated to some other process
o The decision to schedule another process is made whenever an interrupt occurs causing the currently
running process to switch to ready state or a process having higher priority is ready to execute.
o Examples for preemptive scheduling algorithms are : Shortest Remaining Time Next ( SRTN ) , priority-
based scheduling and round robin (RR ) scheduling

Various scheduling criteria

 The scheduler must consider the following performance measures and optimization criteria in order to maximize
the performance of the system.
1. CPU Utilization : It is the percentage of time the CPU is busy. For higher utilization, the CPU must be kept
as busy as possible, that is, there must be some process running at all times. Conceptually, CPU utilization
can range from 0 to 100 percent. In real systems , it ranges from 40% for lightly loaded systems to 90% for
heavily used systems.

Page 11 of 19
Operating System – Module II Notes – Part I Processes, Threads, CPU Scheduling

2. Throughput : It is the total number of processes that a system can execute per unit of time. It depends on the
average length of the processes to be executed. For systems running long processes, throughput will be less
as compared to the systems running short processes
3. Turnaround time: It is the interval from the time of submission of a process to the time of completion. It
is the sum of all the time the process has spent waiting to get into memory, waiting in the ready queue,
executing on the CPU and doing I/O. More the turnaround time, less will be the throughput
4. Waiting time : It is defined as the time spent by a process while waiting in the ready queue. It does not take
into account the execution time and time consumed for I/O. So, it is the difference between turnaround time
and processing time.
5. Response time : It is the time from the submission of request until the first response is produced , that is,
the time the process takes to start responding. For interactive systems, it is the best measure to evaluate the
performance.
6. Fairness : It is the degree to which each process is getting an equal chance to execute. The scheduler must
ensure that each process should get a fair share of CPU
7. Balanced Utilization : It is the percentage of time all the system resources are busy. For balanced
utilization, it is desirable to load a mixture of CPU-bound and I/O-bound processes in memory.

Scheduling Algorithms

 There are many different CPU-scheduling algorithms which deals with the problem of deciding which of the
processes in the ready queue is to be allocated the CPU.
 The basic purpose of a CPU scheduling algorithm is that it should tend to maximize fairness, CPU
utilization, balanced utilization and throughput, and minimize turnaround, waiting and response time.

 Here we discuss the following algorithms :

First-Come First-Serve ( FCFS ) Priority-based Scheduling

Shortest Job First ( SJF ) Round-Robin Scheduling
Shortest Remaining Time Next ( SRTN ) Multi-level Queue Scheduling
Multi-level feedback Queue Scheduling

First-Come, First-Serve ( FCFS ) Scheduling

 FCFS is a non-preemptive scheduling algorithm
 The processes are executed in the order of their arrival in the ready queue.
 Ready queue is managed as a FIFO queue.
 When the first process enters the ready queue, it immediately gets the CPU and starts executing. Other
processes enter the system are added to the end of the queue by inserting their PCB in the queue.

Page 12 of 19
Operating System – Module II Notes – Part I Processes, Threads, CPU Scheduling

 When currently running process blocks or completes, the CPU is allocated to the process at the front of the
queue. When the blocked process come to the ready state, its PCB is linked to the end of ready queue.
 Example : Consider 4 processes P1, P2, P3 and P4 with their arrival times and required CPU burst ( in
milliseconds ) as shown in the following table :

Process P1 P2 P3 P4

Arrival time 0 2 3 5

CPU Burst 15 6 7 5

FCFS algorithm will schedule these processes as shown in the following Gantt chart

P1 P2 P3 P4

0 15 21 28 33

Turnaround time Waiting Time

= Exit time - entry time = Turnaround time – CPU Burst

For P1 = ( 15 - 0 ) = 15 ms For P1 = ( 15 - 15 ) = 0 ms
For P2 = ( 21 – 2 ) = 19 ms For P2 = ( 19 – 6 ) = 13 ms
For P3 = ( 28 – 3 ) = 25 ms For P3 = ( 25 – 7 ) = 18 ms
For P4 = ( 33 – 5 ) = 28 ms For P4 = ( 28 – 5 ) = 23 ms
Average turnaround time = Average waiting time =
( 15 + 19 + 25 + 28 ) /4 = 21.75 ms ( 0 + 13 + 18 + 23 ) /4 = 13.5 ms

 Performance of FCFS scheduling algorithm depends on the order of arrival of processes in the ready queue.
Suppose, the processes of above example enter the ready queue in the order P4, P2, P3 and P1, then the
schedule will be as shown in the following Gantt chart.

P4 P2 P3 P1

0 5 11 18 33
Average turnaround time = ( (5-0) + (11 -2) + (18 – 3 ) + ( 33 – 5 ) ) / 4 = 14.25 ms
Average waiting time = ( (5 – 5 ) + (9 – 6) + (15 – 7 ) + ( 28 – 15 ) ) / 4 = 6 ms
 If the processes having shorter CPU bursts executes before those having longer CPU bursts, the average
waiting and turnaround time may reduce significantly.
 Advantages : It is easy to understand and implement. It is well suited for batch systems
 Disadvantages : The average waiting time is not minimum, so never recommended where high performance
is needed. It reduces CPU and I/O utilization under some circumstances. It is not suitable for time sharing
systems.
Shortest Job First (SJF) Scheduling
 It is also known as Shortest Job Next scheduling

Page 13 of 19
Operating System – Module II Notes – Part I Processes, Threads, CPU Scheduling

 It is a non-preemptive scheduling algorithm that schedules the process according the length of CPU burst
they require.
 At any point of time, the process having the shortest CPU burst is scheduled first. A process has to wait until
all the processes shorter than it have been executed.
 Two processes with same CPU Burst are scheduled in the FCFS order.
Example : Consider 4 processes P1, P2, P3 and P4 with their arrival times and required CPU burst ( in milliseconds
) as shown in the following table :

Process P1 P2 P3 P4

Arrival Time 0 1 3 4

CPU Burst ( ms ) 7 5 2 3

According SJF scheduling, the processes will be scheduled as shown in the Gantt Chart below :

P1 P3 P4 P2

0 7 9 12 17

Turnaround time ( Exit Time – entry time ) Waiting Time

( Turnaround time – processing time )

For P1 = ( 7 – 0 ) = 7 ms For P1, ( 7 – 7 ) = 0 ms

For P2 , ( 17 – 1 ) = 16 ms For P2, ( 16 – 5 ) = 11 ms
For P3, ( 9 – 3 ) = 6 ms For P3, ( 6 – 2 ) = 4 ms
For P4, ( 12 – 4 ) = 8 ms For P4, ( 8 – 3 ) = 5 ms
Average turnaround time Average waiting time
= ( 7 + 16+ 6 + 8 ) / 4 = 9.25 ms = ( 0 + 11 + 4 + 5 ) / 4 = 5 ms

Advantages : It decreases the average waiting time.

Disadvantage : It is difficult to implement as it needs to know the length of CPU burst of processes in advance. It
does not favour processes with longer CPU burst. They have to wait as long as shorter processes continue to enter the
ready queue. This results in starvation of long processes.

Shortest Remaining Time Next ( SRTN ) Scheduling

 It is the preemptive version of SJF scheduling.
 It consider the remaining CPU burst of the processes rather than the whole length in order to schedule them.
 When a process is being executed, the CPU can be taken back from it and assigned to some newly arrived
process if the CPU burst of the new process is shorter than its remaining CPU burst.

Page 14 of 19
Operating System – Module II Notes – Part I Processes, Threads, CPU Scheduling

 Equal CPU burst processes are scheduled FCFS order

Example : Suppose , the arrival time and CPU burst of processes P1, P2 and P3 are as shown below:

Process Arrival time (ms) CPU Burst (ms)

P1 0.0 8

P2 0.4 4

P3 1.0 1

What is the average turnaround time ad average waiting time under SRTN scheduling?
According to SRTN scheduling algorithm, the processes can be scheduled as shown in the following Gantt chart.

P1 P2 P3 P2 P1

0 0.4 1.0 2.0 5.4 13

Turnaround time ( Exit Time – entry time ) Waiting Time

( Turnaround time – processing time )

Turnaround time of P1 = ( 13 – 0.0) = 13 Waiting time for P1 = 13 – 8 = 5 ms

Turnaround time of P2 = ( 5.4 - 0.4 ) = 5 ms Waiting time for P2 = 5 - 4 = 1 ms
Turnaround time of P3 = ( 2 – 1 ) = 1 ms Waiting time for P3 = 1 – 1 = 0 ms
Average turnaround time Average Waiting time
= (13 + 5 + 1) / 3 = 6.33 ms = ( 5 + 1 + 0 ) / 3 = 2 ms

Advantages: Improved turnaround time of long processes ( A long process near to its completion may be favoured
over the short processes entering the system )
Disadvantages: It requires advance estimation of CPU bursts of processes. Starvation of long processes may exist
still. Turnaround times of several short processes entering the system may be affected.

Priority-based scheduling
 In priority-based scheduling, each process is assigned a priority and the higher priority processes are
scheduled before the lower priority processes.
 In case two processes are having the same priority, they are executed in the FCFS order.
 Priority scheduling may be either preemptive or non-preemptive. If the newly arrived process has the higher
priority than the currently running process, the preemptive scheduling prompts the current process and
allocates CPU to the new process where as non-preemptive scheduling allows the current process to
complete and the new process has to wait.

Page 15 of 19
Operating System – Module II Notes – Part I Processes, Threads, CPU Scheduling

 Both SJF and SRTN are special cases of priority-based scheduling. Lower is the CPU burst, higher will be
the priority.
Example : Consider 4 processes P1, P2, P3, P4 with arrival time, CPU burst and priority are given below:

Process P1 P2 P3 P4

Arrival time 0 1 3 4

CPU burst (ms) 7 4 3 2

Priority 4 3 1 2

Assuming lower number means higher priority, the processes will be scheduled as shown below :

Gantt Chart for non-preemptive priority scheduling algorithm

P1 P3 P4 P2

0 7 10 12 16

Turnaround time ( exit time - entry time ) Waiting time ( turnaround time – CPU Burst )

Turnaround time for P1 , ( 7 – 0 ) = 7 Waiting Time for P1, ( 7 - 7 ) = 0

Turnaround time for P2 , ( 16 – 1 ) = 15 Waiting Time for P2, ( 15 – 4 ) = 11
Turnaround time for P3 , ( 10 – 3 ) = 7 Waiting Time for P3, ( 7 - 3 ) = 4
Turnaround time for P4 , ( 12 – 4 ) = 8 Waiting Time for P4, ( 8 - 2 ) = 6
Average turnaround time = 37/4 = 9.25 ms Average waiting time = 21 / 4 = 5.25 ms

Gantt chart for preemptive priority based scheduling algorithm

P1 P2 P3 P4 P2 P1

0 1 3 6 8 10 16

Turnaround time ( exit time - entry time ) Waiting time ( tturnaround time – CPU Burst )

Turnaround time for P1 , ( 16 – 0 ) = 16 Waiting time for P1 = ( 16 – 7 ) = 9

Turnaround time for P2 , ( 10 – 1 ) = 9 Waiting time for P2 = ( 9 – 4 ) = 5
Turnaround time for P3, ( 6 – 3 ) = 3 Waiting time for P1 = ( 3 – 3 ) = 0
Turnaround time for P4 , ( 8 – 4 ) = 4 Waiting time for P1 = ( 4 – 2 ) = 2
Average turnaround time = 32/4 = 8 ms Average waiting time = 16/4 = 4 ms

Advantages: Important processes are never made to wait because of the execution of less important processes
Disadvantages: It suffers from the problem of starvation of lower priority processes. One solution to this issue is
aging. Aging is a process of gradually increasing the priority of a lower priority process with increase in its
waiting time.

Page 16 of 19
Operating System – Module II Notes – Part I Processes, Threads, CPU Scheduling

Round Robin ( RR ) scheduling

 The round robin scheduling is one of the most widely used preemptive scheduling algorithms
 Algorithm considers all the processes as equally important.
 Each process in the ready queue gets a fixed amount of CPU time ( 10 to 100 ms ) known as time slice or
time quantum for its execution.
 If there are n processes in the ready queue and time quantum is q, then each process get 1/n of the CPU time
in chunks of at most q time units.
 Ready queue is treated as a circular queue.
 Processes arriving in the ready queue are put at the end of queue. The CPU is allocated to the first process
and executes until its time slice expires.
 If the CPU burst of the process is less than the time slice, the process itself release the CPU and is deleted
from the queue.
 If the process does not execute completely in a time slice, it is pre-empted after the time slice , put back at
the end of the queue and the CPU is allocated to the next process in the queue.
 Time quantum ( time slice ) should be large compared with the context-switching time
Example : Consider four processes P1, P2, P3 and P4 with their arrival time & CPU Burst.

Process P1 P2 P3 P4

Arrival time 0 1 3 4

CPU Burst (ms) 10 5 2 3

Assume that the time slice is 3 ms. Compute the average turnaround time and waiting time.
Gnatt chart

P1(3) P2(3) P3(2) P1(3) P4(3) P2(2) P1(3) P1(1)

0 3 6 8 11 14 16 19 20

Turnaround time ( Exit time – entry time ) Waiting time =( turnaround time – CPU Burst)

Turnaround time for P1 = 20 – 0 = 20 Waiting time for P1 = 20 – 10 = 10

Turnaround time for P2 = 16 – 1= 15 Waiting time for P2 = 15 – 5 =10
Turnaround time for P3 = 8 – 3 = 5 Waiting time for P3 = 5 – 2 = 3
Turnaround time for P4 = 14 – 4 = 10 Waiting time for P4 =10 - 3= 7
Average turnaround time Average waiting time
= ( 20+15+5+10)/4 = 50/4 = 12.5 ms = ( 10 + 10 + 3 + 7)/4 = 30/4 = 7.5 ms

Page 17 of 19
Operating System – Module II Notes – Part I Processes, Threads, CPU Scheduling

Multilevel queue scheduling

 The multilevel queue scheduling is designed for situations in which processes can be classified into different
groups on the basis of their response time or scheduling needs

 For example processes can be classified as system processes, interactive (foreground) processes, or batch
(background) processes etc. Each group is associated with a specific priority. System processes may have
highest priority where as batch processes may have the least priority.
 A multilevel queue scheduling algorithm partitions the ready queue into several separate queues
o When a new process enters, it is permanently assigned to one of the ready queues based on some
property of the process , such as memory size, process priority, or process type.
o Each ready queue has its own algorithm.
o Batch processes ( background queue) may use FCFS scheduling , interactive processes may use RR
scheduling
o In addition, the processes in higher priority queues are executed before those in lower priority queues.

Multilevel feedback queue scheduling

 In multilevel queue scheduling, processes are permanently assigned to a queue, they do not move from one
queue to another. So scheduling overhead is low, but it is inflexible.
 In multilevel feedback queues, processes are allowed to move between the queues.
 The idea is to separate processes according to their CPU bursts.
o If a process has too much CPU time, it will be moved to a lower priority queue
o This scheme leaves I/O bound and interactive processes in the higher priority queues
o A process that waits too long in a lower priority queue may be moved to a higher priority queue. This
form of aging prevents starvation.
 Figure shows a multilevel feedback queue scheduler with three queues. The scheduler executes all processes in
queue 0. Only when queue 0 is empty, it will execute processes from Queue 1. Similarly, Queue 2 will be
executed if Queue 0 & 1 are empty.

Page 18 of 19
Operating System – Module II Notes – Part I Processes, Threads, CPU Scheduling

 A process entering the ready queue is put in queue 0 and is given a time quantum of 8 milliseconds. If it does
not finish within this time, it is moved to the tail of queue 1. If queue 0 is empty, the process at the head of
queue 1 is given a quantum of 16 milliseconds. If it does not complete, it is pre-empted and is put into queue
2. Processes in queue 2 are run on an FCFS basis but are run only when queue 0 and 1 are empty.

Page 19 of 19