Process Management

Curriculum
• Basic Concepts of Process: Process State
Transition Model, Operations, Process Control
Block, Context Switching; Introduction to
Threads, Types of Threads, Thread Models,
• Basic Concepts of Scheduling, Types of
Schedulers, Type of scheduling algorithms:
Preemptive and non preemptive (FCFS, SJF,
Priority and Round Robin)
Basic concepts of process
• A process can be thought of as a program in execution.
• A process will need certain resources—such as CPU time,
memory, files, and I/O devices —to accomplish its task.
• These resources are allocated to the process either when it is
created or while it is executing.
• Systems consist of a collection of processes: operating-
system processes execute system code, and user processes
execute user code.
• All these processes may execute concurrently.
Basic concepts of process
• The operating system is responsible for several important aspects of
process and thread management: the creation and deletion of both
user and system processes; the scheduling of processes; and the
provision of mechanisms for synchronization, communication, and
deadlock handling for processes.
Program Process
The program contains a set of instructions The process is an instance of an executing
designed to complete a specific task. program.
A program is a passive entity as it resides in The process is an active entity as it is
the secondary memory. created during execution and loaded into
the main memory.
Program exists at a single place and The process exists for a limited period as it
continues to exist until it is deleted. gets terminated after the completion of the
task.
A program is a static entity. The process is a dynamic entity.
The program does not have any resource The process has a high resource
requirement, it only requires memory requirement, it needs resources like CPU,
space for storing the instructions. memory address, and I/O during its
lifetime.
Program Process
The program does not have any control Process has its control block called
block. Process Control Block.
The program has two logical In addition to program data, a process
components: code and data. also requires additional information
required for the management and
execution.
The program does not change itself. Many processes may execute a single
program. Their program code may be
the same but program data may be
different. these are never the same.
Program contains instructions The process is a sequence of instruction
execution.
Process State Diagram(5 states)
Process States
• As a process executes, it changes state. The state of a process is
defined in part by the current activity of that process. A process may
be in one of the following states:
• New. The process is being created.
• Running. Instructions are being executed.
• Waiting. The process is waiting for some event to occur (such as an
I/O completion or reception of a signal).
• Ready. The process is waiting to be assigned to a processor.
• Terminated. The process has finished execution.
Process State Diagram(6 states)
Process States
• New – The process is being created.
• Ready – The process is loaded into memory and waiting for CPU time.
• Running – The process is currently being executed by the CPU.
• Waiting (Blocked) – The process is waiting for an event or I/O to
complete.
• Suspended Ready – The process is ready to run but has been
swapped out of main memory.
• Suspended Waiting (Suspended Blocked) – The process is waiting for
an event and is also swapped out of memory.
Process State Diagram(7 states)
 Process State Diagram(7 states)
• New − Contains the processes that are newly coming for execution.
• Ready − Contains the processes that are present in main memory and available for
execution.
• Running − Contains the process that is running or executing.
• Blocked − Contains the processes that are present in main memory and awaiting
an event to occur.
• Blocked Suspend − It contains the process present in secondary memory and
awaits an event to occur.
• Ready Suspend − Contains the processes that are present in secondary memory
but is available for execution as soon as it is loaded into main memory.
• Exit − Contains the processes that complete its execution.
 Process Id: Process Id is a unique Id that identifies
Process Control Block each process of the system uniquely.
A process Id is assigned to each process during its
creation.
Program Counter: Program counter specifies the
address of the instruction to be executed next.
Before execution, program counter is initialized with
the address of the first instruction of the program.
After executing an instruction, value of program
counter is automatically incremented to point to the
next instruction.
This process repeats till the end of the program.
 Process Control Block
• Process State: Each process goes through different states during its lifetime.
• Process state specifies the current state of the process.
• Priority: Priority specifies how urgent is to execute the process.
• Process with the highest priority is allocated the CPU first among all the
processes.
• List of Open files: This information includes the list of files opened for a process.
• PCB pointer: This field contains the address of the next PCB, which is in ready
state. This helps the operating system to hierarchically maintain an easy control
flow between parent processes and child processes.
 Process Control Block
• CPU registers. The registers vary in number and type, depending on the
computer architecture.
• They include accumulators, index registers, stack pointers, and general-
purpose registers, plus any condition-code information.
• Along with the program counter, this state information must be saved when an
interrupt occurs, to allow the process to be continued correctly afterward
(

• CPU-scheduling information: This information includes a process priority,

pointers to scheduling queues, and any other scheduling parameters.
• Memory-management information: This information may include such
items as the value of the base and limit registers and the page tables, or
the segment tables, depending on the memory system used by the
operating system.
Process Control Block
• Accounting information: This information includes the amount of
CPU and real time used, time limits, account numbers, job or process
numbers, and so on.
• I/O status information: This information includes the list of I/O
devices allocated to the process, a list of open files, and so on.

• PCB serves as the repository for any information that may vary from
process to process
Process Control Block
Advantages of Process Control Block (PCB)
• Efficient Process Management: The Process Control Block allows the
operating system to manage multiple processes that ensures
maximum resource utilization.
• Quick Context Switching: In order to keep the system responsive, the
PCB allows rapid context switching by storing the state of a process.
• Resource Tracking and Allocation: The PCB tracks all the resources
allocated to a process to make sure that the resources are used
effectively and the errors are minimized.
• Simplified Process Control: The PCB provides a centralized structure
for storing process information, simplifying the control and
management of processes within the operating system.
Process Control Block
Disadvantages of Process Control Block (PCB)
• Increased Overhead: When there are a large number of processes,
maintaining them can create major overheads which consumes
memory and processing power.
• Synchronization Issues: For ensuring that the PCBs are updated
correctly and consistently with multi-threads, complicated
synchronization mechanisms are required.
• Difficulty in Modifications: Once a PCB structure is created making
changes or updates can be complex and may require significant
redesign efforts.
 Process Table
PC: Program Counter, SP: Stack Pointer, PSW, Process-id
Program Status Word, CC: Condition Code, User-id
GRPs: General Purpose Registers
Process State
Scheduling info
PCB1 Accounting info
PCB2 Pinter to other data
PCB3 structures
… Open files, Open
Sockets, Memory
PCBn regions
PC, SP, PSW, CC, GRPs
CPU Switch From Process to Process

Also known as Context Switch

CPU Switch From Process to Process
• Process P1 is initially running on the CPU for the execution of
its task. At the very same time, P2, another process, is in its
ready state. If an interruption or error has occurred or if the
process needs I/O, the P1 process would switch the state
from running to waiting.
• Before the change of the state of the P1 process, context
switching helps in saving the context of the P1 process as
registers along with the program counter (to PCB1). Then it
loads the P2 process state from its ready state (of PCB2) to
its running state.
• Steps are taken to switch the P1 to P2:
• The context switching must save the P1’s state as the program counter and
register to PCB that is in its running state.
• Now it updates the PCB1 to the process P1 and then moves the process to its
appropriate queue, like the ready queue, waiting queue and I/O queue.
• Then, another process enters the running state. A new process can also be
selected instead of from the ready state that needs to be executed or when a
process has a higher priority of executing its task.
• The PCB for the P2 selected process must be updated. It involves switching a
given process state from its running state or from any other state, such as exit,
blocked, or suspended.
• In case the CPU already performs the execution of the P2 process, then the P2
process’s status must be set, so as to resume the execution of it at the very
same time at the same point at which there’s a system interrupt.
CPU Switch From Process to Process
• Similarly, the P2 process is switched off from the system’s CPU to let
the process P1 resume its execution.
• The process P1 is reloaded to the running state from PCB1 to resume
its assigned task at the very same point.
• Else, the data is lost, so when the process is again executed, it starts
the execution at its initial level.
Interrupts
• An interrupt in an OS is a signal from hardware or software that tells
the CPU to pause its current task and handle an urgent event, like a
key press or system call, by transferring control to an Interrupt
Service Routine (ISR), essential for multitasking, I/O, and
responsiveness.
• These signals can be from devices (hardware interrupts), programs
(software interrupts/traps), and are managed by saving the CPU's
state, executing the ISR, and then resuming the original program.
Interrupts
Interrupt
Processing
Context Switching
• When the CPU is changed from one process to another, the context of
the first process is saved and that of the second process is loaded into
appropriate registers and other data structures.
• This is known as context switching or process switching.
• Process switching happens from one process to another in relation to
a CPU allotment and is managed by the OS.
• But, mode switching (user mode to kernel mode or vice versa) is
essentially a processor mode activity - that happens within the
context of a running process.
• Context switch is a kernel activity.
What causes the context switch and when?
• Running of an user process is disturbed only under three events:
interrupts, system call and trap.
1. Interrupts: An interrupt is an asynchronous activity.
• That can come from
i. The timer when time slice allocated for the running process is over
and another process scheduled to run next needs to get the CPU.
ii. I/O devices when some tasks assigned by some process to an I/O
device is complete and the processor is notified. The process is to be
scheduled for the CPU (either immediately or later) as decided by the
OS. If the notification comes from a device and the interrupt was not
blocked, there will be a process switch (currently running process will
be halted and a kernel process will start) to handle the interrupt.
What causes the context switch and when?
• 2. System calls: It happens when the running process itself requires
to execute a privileged instruction.
• Most system calls are for accessing hardware, like memory units or
I/O devices.
• However, note that interrupts are caused by I/O devices to the
processor, but system calls go from a running process to devices
through the OS kernel.
• Context of the running process is saved, and a suitable kernel process
is executed to meet the requirement.
What causes the context switch and when?

• 3. Trap / Exception: When a running process encounters some errors,

attempts illegal operation or to access restricted resources, traps are
flagged and handled in kernel mode by kernel processes.
How do context switches happen?
• A context switch involves several steps as given below:
➢Hardware context of the processor (PC, SP, PSW and other
registers) are saved.
➢The PCB of the running process is updated with the
hardware context. Process state is changed from running to
other appropriate states (waiting, ready or terminated) along
with other relevant fields including accounting information.
➢The PCB is put to the appropriate queue (ready queue,
blocked on some event queue, I/O queue etc).
How do context switches happen?
➢Another PCB is selected based on the priority and position
of the process in the scheduler queue.
➢The selected PCB is updated with process state (from earlier
state to running state).
➢Memory management data-structures are updated (e.g.,
base register, limit register of the processor)
➢All the hardware context of the processor is restored from
the selected PCB.
• A context switch thus takes some amount of time to
complete these tasks.
Process Thread

When a program is under execution, then it is A segment of a process is known as thread.

known as a process.

It consumes maximum time to stop. It consumes minimum time to stop.

It needs more time for work and conception. It needs less time for work and conception.

Context switching takes maximum time here. Here, context switching takes minimum time.

It is not that effective in terms of It is effective in terms of communication.

communication.

It takes more resources. It takes less resources.

It is a heavy weight process. It is a light weight process.

If one process is obstructed then it will not If one thread is obstructed then it will affect the
affect the operation of another process. execution of another process.
Aspect Interrupt Handling Context Switching
Hardware/software
Trigger Scheduler decision
signal
Purpose Handle an event Switch execution
Cost Low High
Duration Very short Longer
Process change Usually no Yes
Example Keyboard interrupt Switching from P1 to P2
Introduction to Threads
• A thread is a single flow of execution and considered a
basic unit of CPU utilization.
• A process can have one or more threads.
• Each thread can run independently.
• If there are multiple CPUs or multicores within a CPU,
threads of a single process can execute in parallel
simultaneously.
• Each thread has a thread ID, and holds a program
counter (PC), a register set, and a stack on its own.
• However, code section, data section, and other
operating-system resources, such as open files and
signals are shared by all threads within a process
Thread States
• Once a thread is created, it can go to the following principal states as
follows:
• Ready: the thread is prepared to go for execution, but not yet
scheduled a CPU core
• Running: after a CPU core is allocated, the thread executes
instructions from code
• Blocked: If the thread waits for some event to complete.
 Thread States
• There are four basic thread operations associated with a change in thread state:
• Spawn: Typically, when a new process is spawned, a thread for that process is
also spawned. Subsequently, a thread within a process may spawn another
thread within the same process, providing an instruction pointer and arguments
for the new thread. The new thread is provided with its own register context and
stack space and placed on the ready queue.
• Block: When a thread needs to wait for an event, it will block (saving its user
registers, program counter, and stack pointers).The processor may now turn to
the execution of another ready thread in the same or a different process.
• Unblock: When the event for which a thread is blocked occurs, the thread is
moved to the Ready queue.
• Finish: When a thread completes, its register context and stacks are deallocated.
Types of Threads
• There are two categories of threads:
• User level threads (ULTs) and kernel level threads (KLTs).
• KLTs are also called Lightweight processes (LWPs).
User Level Threads(ULT)
• User Level Thread is implemented in the user level library; they are
not created using the system calls.
• Thread switching does not need to call OS and to cause interrupt to
Kernel.
• Kernel doesn't know about the user level thread and manages them
as if they were single-threaded processes.
User Level Threads(ULT)
Advantages:
• Can be implemented on an OS that doesn't support multithreading .
• Simple representation since thread has only program counter ,
register set, stack space.
• Simple to create since no intervention of kernel.
• Thread switching is fast since no OS calls need to be made.
Disadvantages:
• No or less co-ordination among the threads and Kernel.
• If one thread causes a page fault, the entire process blocks.
Kernel Level Thread
• Kernel knows and manages the threads.
• Instead of thread table in each process, the kernel itself has thread
table (a master one) that keeps track of all the threads in the system.
• In addition, kernel also maintains the traditional process table to keep
track of the processes.
• OS kernel provides system call to create and manage threads.
Kernel Level Thread
Advantages
• Since kernel has full knowledge about the threads in the system,
scheduler may decide to give more time to processes having large
number of threads.
• Good for applications that frequently block.
Disadvantages
• Slow and inefficient.
• It requires thread control block so it is an overhead.
Thread Models
• There are four basic thread models :
1. User Level Single Thread Model
2. User Level Multi Thread Model
3. Kernel Level Single Thread Model
4. Kernel Level Multi Thread Model
User Level Single Thread Model
• Each process contains a
single thread.
• Single process is itself a
single thread.
• process table contains an
entry for every process by
maintaining its PCB.
User Level Multi Thread Model
• Each process contains multiple
threads.
• All threads of the process are
scheduled by a thread library at user
level.
• Thread switching can be done faster
than process switching.
• Thread switching is independent of
operating system which can be done
within a process.
User Level Multi Thread Model
• Blocking one thread makes blocking of entire process.
• Thread table maintains Thread Control Block of each thread of a
process.
• Thread scheduling happens within a process and not known to
Kernel.
Kernel Level Single Thread Model

• Each process contains

a single thread.
• Thread used here is
kernel level thread.
• Process table works as
thread table.
Kernel Level Multi Thread Model
• Thread scheduling is done at kernel
level.
• Fine grain scheduling is done on a
thread basis.
• If a thread blocks, another thread
can be scheduled without blocking
the whole process.
• Thread scheduling at Kernel process
is slower compared to user level
thread scheduling.
• Thread switching involves switch.
Basic Concept of Scheduling
• Scheduling is the process of deciding when and in what order tasks,
jobs, or processes should be executed so that resources (like CPU,
machines, people, or time) are used efficiently.
• Objectives of Scheduling
➢Maximize efficiency (reduce idle time)
➢Minimize waiting time
➢Ensure fairness among tasks/users
➢Meet deadlines
➢Improve performance (throughput, response time)
 Terms frequently used in Scheduling
•Task / Job
➢A unit of work that needs to be done
➢Example: a process in an operating system, a class in a timetable, or a job in a
factory
•Resource
➢The entity that performs the task
➢Example: CPU, machine, employee, classroom
•Time Allocation
➢Deciding how much time each task gets
➢Prevents conflicts and idle time
•Order of Execution
➢Determines which task runs first, next, and last
Types of Schedulers
• Long Term Scheduler
• Short Term Scheduler
• Medium Term Scheduler
 Long Term Scheduler(Job Scheduler)
• The Long-Term Scheduler is responsible for loading processes from disk
into main memory so they can begin execution. When a new process is
admitted, it moves into the Ready state.
• Transfers processes from the Job Queue to the Ready Queue.
• Controls the degree of Multi-programming — the number of processes
present in memory or ready state at any time.
• Carefully selects a balanced mix of I/O-bound and CPU-bound processes to
ensure efficient system performance.
• Helps avoid a situation where either the CPU or I/O devices remain idle.
• In many modern time-sharing systems (such as Windows), a long-term
scheduler may not exist; new processes are directly admitted to memory
for short-term scheduling.
• It is the slowest among all schedulers, as it operates less frequently.
 Short Term Scheduler (CPU Scheduler)
• The Short-Term Scheduler (STS) is responsible for selecting a
process from the ready queue and assigning the CPU to it.
• Frequently selects the next process to execute from the ready state.
• Ensures no process suffers from starvation.
• Uses various CPU scheduling algorithms to decide process order.
• Maximizes CPU utilization by keeping the processor as busy as
possible.
• Calls the dispatcher, which performs the actual context switch.
• It is the fastest scheduler, since it operates very frequently (often
every few milliseconds).
 Medium Term Scheduler (Swapper)
• This scheduler is invoked when there is a need to swap out some blocked
processes.
• It can happen in the case when all processes are blocked for some I/O devices
and there is no ready process to execute and there is no space for any other
process.
• In this case, some blocked processes need to be swapped out from the main
memory to the hard disk.
• There is another queue called blocked–suspended queue for this purpose in
the disk.
• The task of swapping the processes from the blocked queue to the blocked–
suspended queue is performed by another type of scheduler known as
medium-term scheduler.
 Medium Term Scheduler (Swapper)
• When there is a signal of completion of an I/O device for which the
process is blocked and presently in the blocked–suspended queue,
the process changes its state to ready–suspended and moves to the
ready–suspended queue.
• This task of moving a process from the blocked–suspended to the
ready–suspended queue is also performed by this medium-term
scheduler.
S.N. Long-Term Scheduler Short-Term Scheduler Medium-Term Scheduler
It is a process swapping
1 It is a job scheduler It is a CPU scheduler
scheduler.
Speed is lesser than short Speed is fastest among Speed is in between both short
2
term scheduler other two and long term scheduler.

It provides lesser control

It controls the degree of It reduces the degree of
3 over degree of
multiprogramming multiprogramming.
multiprogramming

It is almost absent or
It is also minimal in time It is a part of Time sharing
4 minimal in time sharing
sharing system systems.
system

It selects processes from It selects those processes It can re-introduce the process
5 pool and loads them into which are ready to into memory and execution can
memory for execution execute be continued.
CPU Scheduling
• CPU scheduling is needed under the following circumstances.
1. A newly created process joins the ready queue, and the process
needs to be immediately executed.
2. The time slice allocated to a process is over and another process
needs to get the CPU.
3. A process needs an I/O before it can proceed any further.
4. A process waits for its children to complete first before it proceeds
further.
5. A process waits for some interrupt (other than timer) and the
interrupt occurs.
6. A process completes its execution.
CPU Scheduler
• Whenever the CPU becomes idle, the operating system must select
one of the processes in the ready queue to be executed. The selection
process is carried out by the short-term scheduler, or CPU scheduler.
• The scheduler selects a process from the processes in memory that
are ready to execute and allocates the CPU to that process.
• Scheduling Algorithms define the different ways of scheduling
processes to ensure maximum and efficient utilization of the CPU.
• Scheduling algorithms in operating systems can be preemptive or
non-preemptive.
Preemptive Scheduling
• The OS can interrupt (preempt) a currently running process and
allocate the CPU to another process (usually one with higher priority
or shorter remaining time).
• CPU can be taken away at any time
• Better responsiveness
• More context switching overhead
• Suitable for multitasking and real-time systems
• A low-priority process is running, and a high-priority process arrives
→ OS preempts the running process immediately.
 Preemptive Scheduling
Advantages
• Faster response time
• Prevents CPU monopolization
• Better for interactive systems
Disadvantages
• Higher overhead due to frequent context switches
• More complex to implement
• Risk of starvation (low-priority processes may wait long)
Common Preemptive Algorithms
• Round Robin (RR), Shortest Remaining Time First (SRTF), Preemptive Priority
Scheduling, Multilevel Feedback Queue
Non-Preemptive Scheduling
• Once a process gets the CPU, it keeps it until it terminates or enters a
waiting state (I/O, sleep, etc.).
• CPU is not forcibly taken away
• Simple and low overhead
• Poor responsiveness
• A long process starts running → even if a short process arrives, it
must wait until the current process finishes.
Non-Preemptive Scheduling
Advantages
• Simple to implement
• No context switching overhead
• Predictable behavior
Disadvantages
• Poor response time
• Convoy effect (short jobs wait behind long jobs)
• Not suitable for real-time systems
Common Non-Preemptive Algorithms
• First Come First Serve (FCFS), Shortest Job First (SJF – non-
preemptive), Non-Preemptive Priority Scheduling
Feature Preemptive Scheduling Non-Preemptive Scheduling
Process The OS can interrupt a process The process runs until it finishes or
Control before completion. enters I/O.
CPU More efficient, as short and high- Less efficient, as long tasks can block
Utilizationpriority tasks get CPU sooner. others.
Context Frequent switching leads to higher No switching during execution,
Switching overhead. reducing overhead.
Ensures fair execution for all Some processes may suffer long
Fairness
processes. waiting times.
Complexity More complex to implement. Simpler and easier to manage.
Possible if low-priority processes No starvation, but long processes
Starvation
keep getting preempted. can slow the system.
Multitasking, real-time OS, time- Batch processing, simple OS, low-
Best For
sharing. overhead systems.
 Terminologies Used in CPU Scheduling (CPU Scheduling Criterion)
• Throughput - The number of processes that complete their execution per unit
time.
• Arrival time - The time at which a process enters the Ready queue.
• Completion time - The time at which a process completes its execution.
• Burst time - The time takes to execute a process in the CPU.
• Turnaround time - The time difference between completion time and arrival
time. It is the time interval between the submission and completion of a
process. Turn Around Time = Completion Time – Arrival Time
• Waiting time - The time difference between turnaround time and burst time. It
is the amount of time a process spends in the ready queue waiting for its turn
with the CPU.
• CPU Utilization: Measures the percentage of time the CPU is busy processing a
task
CPU Scheduling Criterion
First Come First Serve (FCFS)
• The process that requests the CPU first is allocated the CPU first.
• Every process is scheduled based on its arrival time (time of joining
the ready queue of the CPU) and continues to run until it is complete
or voluntarily leaves CPU for some I/O operation.
• When the CPU is free, the process that has the earliest arrival time is
scheduled next.
• FCFS can be implemented using a FIFO ready queue.
• When a process enters the ready queue, its PCB is linked onto the tail
of the queue.
• When the CPU is free, it is allocated to the process at the head of the
queue.
 First Come First Serve (FCFS)
Processes with Different Arrival Times

Process Arrival Burst

Time (Service) Waiting Time:
Time P1 = 0
P1 0 4 P2 = 4
P3 = 10
P2 3 6 P4 = 13
P3 5 3
P4 8 2
First Come First Serve (FCFS)
• In FCFS Scheduling, if multiple processes arrive at the same time,
FCFS by itself can’t distinguish between them—so a tie-breaking rule
is used.
• Common tie-breakers include:
• Order of insertion into the ready queue (e.g., the order the OS
creates or enqueues them)
• Process ID (PID) — lower PID first
• Input order (how they appear in a job list or input file)
• Priority, if FCFS is combined with priority as a secondary rule
• FCFS itself does not define a tie-breaking policy
 First Come First Serve (FCFS)
Processes with same Arrival Times Assume the order is P1 → P2 → P3
Process Arrival Burst (PID order)
Time (Service) Waiting Time:
Time P1 = 0
P1 0 4 P2 = 4
P3 = 7
P2 0 3
P3 0 2

0 4 7 9
First Come First Serve (FCFS)

Process Start Time Wait Time Completion Turnaround

Time Time
P1 0 0 4 4
P2 4 4 7 7
P3 7 7 9 9

Average Wait Time = 0 + 4 + 7 = 11/3 = 3.67

Average Turnaround Time = 4 + 7 + 9 = 20/3 = 6.67
First Come First Serve (FCFS)
Advantages of FCFS
• The simplest and basic form of CPU Scheduling algorithm
• Every process gets a chance to execute in the order of its arrival. This
ensures that no process is arbitrarily prioritized over another.
• Easy to implement, it doesn't require complex data structures.
• Since processes are executed in the order they arrive, there’s no risk
of starvation.
• It is well suited for batch systems where the longer time periods for
each process are often acceptable.
First Come First Serve (FCFS)
Disadvantages of FCFS
• As it is a Non-preemptive CPU Scheduling Algorithm, FCFS can result in long
waiting times, especially if a long process arrives before a shorter one. This
is known as the convoy effect, where shorter processes are forced to wait
behind longer processes, leading to inefficient execution.
• The average waiting time in the FCFS is much higher than in the others
• Since FCFS processes tasks in the order they arrive, short jobs may have to
wait a long time if they arrive after longer tasks, which leads to poor
performance in systems with a mix of long and short tasks.
• Processes that are at the end of the queue, have to wait longer to finish.
• It is not suitable for time-sharing operating systems where each process
should get the same amount of CPU time.
Shortest Job First (SJF)
• This algorithm looks at the CPU burst times of all the waiting
processes in the ready queue and allocates the CPU to the one with
the shortest CPU burst time.
• The shortest job will complete its execution quickly and reduce the
wait time for the next candidate.
• All the processes will have the least possible wait time and hence
least turnaround time as well.
Shortest Job First (SJF)
Advantages
• Increased throughput and shorter turnaround time.
• It minimizes waiting time for processes that are ready for execution.
• Effective in batch processing where job lengths are known in advance.
• Provides predictable and deterministic performance.
Disadvantages
• It may lead to starvation, as longer processes have to wait for their
turn until the shorter processes have been executed.
• Accurate prediction of job lengths is often challenging.
• Requires continuous monitoring of job lengths, adding complexity.
• A long job may need to wait indefinitely if shorter jobs keep arriving.
 Shortest Job First (SJF)
Sequence of Execution
Process Arrival Burst
P1→P3→P4→P2→P5
Time (Service)
Time
P1 0 4
P1 P3 P4 P2 P5
P2 1 3
0 4 5 7 10 16
P3 2 1
P4 3 2
P5 4 6
 Shortest Job First (SJF)
Waiting Time WT=Start Time−Arrival Time
Process Start Arrival WT
Time Time Total WT = 16
Average WT = 16 / 5 = 3.2
P1 0 0 0
P3 4 2 2
P4 5 3 2
P2 7 1 6
P5 10 4 6
 Shortest Job First (SJF)
Turnaround Time TAT= Completion Time−Arrival Time
Process Completion Arrival TAT
Time Time Total TAT = 32
Average TAT = 32 / 5 = 6.4
P1 4 0 4
P3 5 2 3
P4 7 3 4
P2 10 1 9
P5 16 4 12
Priority Scheduling
• A Priority (an integer) is associated with each process.
• The CPU is allocated to the process with the highest priority.
• Generally smallest integer is considered as the highest priority.
• Equal priority processes are scheduled in First Come First Serve order.
• It can be preemptive or Non-preemptive.

• In Non-Preemptive Priority Scheduling, the CPU is not taken away

from the running process. Even if a higher-priority process arrives, the
currently running process will complete first.
 Priority Scheduling
Sequence of Execution
Time 0 → only P1 has
Process Arrival Execution Priority arrived → run P1
Time Time Time 6 → available: P2,
P1 0 6 3 P3, P4
→ highest priority (lowest
P2 1 4 1(HP)
number) is P2
P3 2 5 4(LP) Next highest priority →
P4 3 2 2 P4
Last → P3
P1 P2 P4 P3 Order: P1 → P2 → P4 →
P3
0 6 10 12 17
 Priority Scheduling
Waiting Time WT=Start Time−Arrival Time
Process Start Arrival WT
Time Time Total WT = 22
Average WT = 22 / 4 = 5.5
P1 0 0 0
P2 1 6 5
P4 3 10 7
P3 2 12 10
 Priority Scheduling
Turnaround Time TAT= Completion Time−Arrival Time
Process Start Completion TAT
Time Time Total TAT = 39
Average TAT = 39 / 4 = 9.75
P1 0 6 6
P2 1 10 9
P4 3 12 9
P3 2 17 15
 Priority Scheduling
Advantages
• Processes with high priority need not wait for long. Hence, it
is suitable for applications with fluctuating time and resource
requirements.
• Priorities can be adjusted based on the specific requirements of the
system or application.
• High-priority tasks are executed promptly, leading to efficient
resource utilization.
• Processes are assigned priority levels, allowing for the execution of
higher-priority tasks first.
 Priority Scheduling

Disadvantages
• Since higher priority processes take over the majority of the CPU
time, it leads to starvation of lower priority processes.
• Priority inversion can occur, where a low-priority task holds a
resource needed by a higher-priority task.
• The need for dynamic adjustments to priorities adds complexity to
the scheduling algorithm.
• Assigning accurate and meaningful priorities to diverse processes can
be challenging.
Round Robin Scheduling
• The system rotates through all the processes, allocating each of them
a fixed time slice or "quantum", regardless of their priority.
• The primary goal of this scheduling method is to ensure that all
processes are given an equal opportunity to execute, promoting
fairness among tasks.
 Round Robin Scheduling
Process Burst Completion Arrival Time Turn Around Waiting Time
Term Time Time = CT-AT WT = TAT - BT

P1 5 15 0 15 15 - 5 = 10
P2 2 4 0 4 4-2=2
P3 6 17 0 17 17 - 6= 11
P4 4 14 0 14 14 - 4 = 10

Average TAT = 50 / 4 = 12.5 Average WT = 33 / 4 = 8.25

P1 P2 P3 P4 P1 P3 P4 P1 P3
0 2 4 6 8 10 12 14 15 17
 Round Robin Scheduling
• Advantages
• All processes have the same priority and are given an equal share of
CPU time.
• There is no starvation and no process is left unattended.
• Short processes generally experience lower waiting times compared
to some other scheduling algorithms.
• It is a straightforward and easy-to-implement scheduling algorithm.
 Round Robin Scheduling
• Disadvantages
• It has a long average waiting time.
• Setting a short time quantum can reduce CPU utilization and reduce
performance.
• The algorithm may result in lower throughput compared to other
scheduling algorithms, especially when processes have varying burst
times.
• Short processes can get stuck waiting behind a long process, leading to
a convoy effect where short processes are delayed.
 Preemptive Scheduling
• Preemptive scheduling is a CPU scheduling approach where
the operating system can interrupt (preempt) a currently
running process and switch the CPU to another process before
the first one finishes.
• A process starts running on the CPU
• If a higher-priority process arrives or a time slice expires, the
OS pauses the current process
• The CPU is reassigned to another process
• The paused process is saved and can resume later
 Preemptive Scheduling
Advantages of Preemptive Scheduling:
• Improved Response Time:
Preemptive scheduling ensures that time-sensitive tasks (with high
priority) get immediate access to CPU resources, improving overall
system responsiveness.
• Fairer Process Handling:
All processes in the ready queue are given a chance to run, ensuring
fairness. Low-priority tasks will not be starved unless high priority tasks
continuously arrive.
• Effective for Time sharing Systems:
In systems where multiple users interact with the CPU, preemptive
scheduling ensures that no single process monopolizes CPU time,
keeping all users’ tasks running smoothly.
 Preemptive Scheduling
Disadvantages of Preemptive Scheduling:
• Context Switching Overhead:
Frequent interruptions lead to increased context switching, which
involves saving and restoring process states, consuming CPU time.
• Complexity in Management:
Managing priority levels and determining the right moment for
preemption adds complexity to the system scheduler.
• Starvation:
Low priority processes may suffer from starvation if high priority tasks
are constantly entering the queue.
Preemptive Scheduling Non-preemptive Scheduling
A processor can be preempted to Once the processor starts its execution,
execute the different processes in the it must finish it before executing the
middle of any current process execution. other. It can’t be paused in the middle.
CPU utilization is more efficient
CPU utilization is less efficient compared
compared to Non-Preemptive
to preemptive Scheduling.
Scheduling.
Waiting and response time of Waiting and response time of the non-
preemptive Scheduling is less. preemptive Scheduling method is higher.
When any process enters the state of
Preemptive Scheduling is prioritized. The
running, the state of that process is
highest priority process is a process that
never deleted from the scheduler until it
is currently utilized.
finishes its job.
Preemptive Scheduling Non-preemptive Scheduling
Preemptive Scheduling is flexible. Non-preemptive Scheduling is rigid.
Examples: First Come First Serve,
Examples: – Shortest Remaining Time
Shortest Job First, Priority Scheduling,
First, Round Robin, etc.
etc.
Preemptive Scheduling algorithm can be
In non-preemptive scheduling process
pre-empted that is the process can be
cannot be Scheduled
Scheduled
In this process, CPU is allocated to the
In this process, the CPU is allocated to
process until it terminates or switches to
the processes for a specific time period.
the waiting state.
 SJF Preemptive
• A pre-emptive SJF algorithm will preempt the currently executing
process.
• Preemptive SJF scheduling is sometimes called shortest-remaining-
time-first scheduling.

Process Arrival Burst Time

Time
P1 0 5
P2 1 3
P3 2 3
P4 3 1
 SJF Preemptive

P1 will execute first till 1ms when P2 arrives

P2 needs 3ms of CPU. P1 needs 4ms of CPU> Hence P2 will execute till 2ms
when P3 arrives.
P3 needs 3ms, P2 needs 2ms of CPU and P1 needs 4ms of CPU. Hence at time
= 4ms P2 completes and P4 arrives with CPU requirement of 1ms(smallest).
P4 will execute next.
P3 will start after P4 and (CPU time 3ms) and then P1(CPU time 4ms)
 SJF Preemptive
Process Arrival Time Burst Time Wait Time TA Time
P1 0 5 8-1 = 7 12-0 = 12
P2 1 3 1-1 = 0 4-1 = 3
P3 2 3 5-2 = 3 8-2 = 6
P4 3 1 4-4 = 0 5-4 = 1

Average Wait Time = 10/4 = 2.5

Average TA Time = 22 / 4 = 5.5
SJF Preemptive
Process Arrival Burst
Time Time
P1 0 18
P2 1 4
P3 2 7
P4 3 2
SJF Preemptive
• Time 0 : Only P1 available → runs P1 remaining = 17
• Time 1: P2 arrives (BT 4 < 17) → preempts P1 P2 remaining = 3
• Time 2: P3 arrives (7)Shortest remaining: P2 (3) → continues
P2 remaining = 2
• Time 3: P4 arrives (2) Shortest remaining: P2 (2) or P4 (2)
Tie → earlier arrival P2 continues P2 remaining = 1
• Time 4: P2 (1) still shortest → finishes at time 5
• Time 5: Remaining: P1 = 17 P3 = 7 P4 = 2
P4 runs
• Time 7: P4 finishes Time 7–14 Remaining: P1 = 17 P3 = 7
P3 runs and finishes
• Time 14–31: Only P1 left → finishes
SJF Preemptive
Process Arrival Burst
Time Time
P1 0 18
P2 1 4
P3 2 7
P4 3 2

P1 P2 P4 P3 P1
 SJF Preemptive
Process Arrival Burst Completion Turn Waiting
Time Time Time Around Time
Time
P1 0 18 31 31 13
P2 1 4 5 4 0
P3 2 7 14 12 5
P4 3 2 7 4 2

Average WT = (13 + 0 + 5 + 2) / 4 = 5

Average TAT = (31 + 4 + 12 + 4) / 4 = 12.75

 Priority Preemptive
• In preemptive priority scheduling algorithm, every time a process
with higher priority arrives in the waiting queue, the CPU cycle is
shifted to the process with the highest priority. This is preemptive
because a process that’s already being executed can be stopped to
execute a process with higher priority.
Process Arrival Time Burst Time Priority (Higher
P1 0 4 2 number
P2 1 3 3 represents
P3 2 1 4 higher
priority)
P4 2 5 5
P5 4 2 5
Priority Preemptive
• Time 0 : Only P1(2) available → runs P1 remaining = 3
• Time 1: P2 (3)arrives (Priority 3 >2) → preempts P1 P2 remaining = 2
• Time 2: P3 arrives (4) Preempts P2 remaining = 2 P3 continues
• Time 3: P4 arrives (5) (Priority 5 > 4) Preempts P3 completes P4
Time 4: P5 (5) arrives
Tie (P4 and P5 have same priority) → earlier arrival P4 continues
• Time 8: P5 starts execution completes execution at 10
• Time 10: P2 with higher priority starts and completes execution at 12
Time 12: Only P1 left → finishes
 P1 P2 P3 P4 P5 P2 P1

Process Arrival Burst Priority Exit Time Turn Waiting

Time Time Around Time
time
P1 0 4 2 15 15 - 0 = 15 15 – 4 = 11
P2 1 3 3 12 12 - 1 = 11 11 – 3 = 8
P3 2 1 4 3 3-2=1 1–1=0
P4 2 5 5 8 8-3=5 5–5=0
P5 4 2 5 10 10 - 4 = 6 6–2=4

Turn Around time = Exit time – Arrival time Average Turn Around time = (15 + 11 + 1 + 5 + 6) / 5 = 38 / 5 = 7.6 un
Average waiting time = (11 + 8 + 0 + 0 + 4) / 5 = 23 / 5 = 4.6 unit
Waiting time = Turn Around time – Burst time
 Priority Preemptive
Process Arrival Time Burst Time Priority
P1 0 9 5
P2 1 4 3
P3 2 5 1
(Lower
P4 3 7 2
number
P5 4 3 4 represents
higher
priority)
Priority Preemptive
• 0–1: Only P1(5) → runs
• 1–2: P2(3) arrives (higher priority than P1) → preempts
• 2–7: P3(1) arrives (highest priority overall) → preempts all
• 7–14: Next highest is P4(2)
• 14–18: Resume P2
• 18–21: P5(5) runs
• 21–26: Finally P1 completes

P1 P2 P3 P4 P2 P5 P1
 Priority Preemptive

Process Arrival Burst Priority Exit Time Turn Waiting

Time Time Around Time
time
P1 0 9 5 26 26 15
P2 1 4 3 18 17 13
P3 2 5 1 7 5 0
P4 3 7 2 14 11 4
P5 4 3 4 21 17 14

Turn Around time = Exit time – Arrival time Average Turn Around time = 76 / 5 = 15.2
Waiting time = Turn Around time – Burst time Average waiting time = 56 / 5 = 11.2
Round Robin Preemptive
• Round Robin scheduling is inherently preemptive because the CPU is
forcibly taken away after the expiration of the time quantum.