Introduction of Process Management

A process is a program in execution. For example, when we write a program in C or C++

and compile it, the compiler creates binary code. The original code and binary code are both
programs. When we actually run the binary code, it becomes a process. A process is an ‘active’
entity instead of a program, which is considered a ‘passive’ entity. A single program can create
many processes when run multiple times; for example, when we open a .exe or binary file multiple
times, multiple instances begin (multiple processes are created).
Process management includes various tools and techniques such as process mapping, process
analysis, process improvement, process automation, and process control. By applying these tools
and techniques, organizations can streamline their processes, eliminate waste, and improve
productivity. Overall, process management is a critical aspect of modern business operations and
can help organizations achieve their goals and stay competitive in today’s rapidly changing
marketplace.
What is Process Management?
If the operating system supports multiple users then services under this are very important. In this
regard, operating systems have to keep track of all the completed processes, Schedule them, and
dispatch them one after another. However, the user should feel that he has full control of the CPU.
Process management refers to the techniques and strategies used by organizations to design,
monitor, and control their business processes to achieve their goals efficiently and effectively. It
involves identifying the steps involved in completing a task, assessing the resources required for
each step, and determining the best way to execute the task.
Process management can help organizations improve their operational efficiency, reduce costs,
increase customer satisfaction, and maintain compliance with regulatory requirements. It involves
analyzing the performance of existing processes, identifying bottlenecks, and making changes to
optimize the process flow.
Some of the systems call in this category are as follows.
 Create a child’s process identical to the parent’s.
 Terminate a process
 Wait for a child process to terminate
 Change the priority of the process
 Block the process
 Ready the process
 Dispatch a process
 Suspend a process
 Resume a process
 Delay a process
 Fork a process
How Does a Process Look Like in Memory?
The process looks like

Explanation of Process
 Text Section: A Process, sometimes known as the Text Section, also includes the current
activity represented by the value of the Program Counter.
 Stack: The stack contains temporary data, such as function parameters, returns addresses,
and local variables.
 Data Section: Contains the global variable.
 Heap Section: Dynamically memory allocated to process during its run time.
Key Components of Process Management
Below are some key component of process management.
 Process mapping: Creating visual representations of processes to understand how tasks
flow, identify dependencies, and uncover improvement opportunities.
 Process analysis: Evaluating processes to identify bottlenecks, inefficiencies, and areas for
improvement.
 Process redesign: Making changes to existing processes or creating new ones to optimize
workflows and enhance performance.
 Process implementation: Introducing the redesigned processes into the organization and
ensuring proper execution.
 Process monitoring and control: Tracking process performance, measuring key metrics,
and implementing control mechanisms to maintain efficiency and effectiveness.
Importance of Process Management System
It is critical to comprehend the significance of process management for any manager overseeing a
firm. It does more than just make workflows smooth. Process Management makes sure that every
part of business operations moves as quickly as possible.
By implementing business processes management, we can avoid errors caused by inefficient human
labor and cut down on time lost on repetitive operations. It also keeps data loss and process step
errors at bay. Additionally, process management guarantees that resources are employed effectively,
increasing the cost-effectiveness of our company. Process management not only makes business
operations better, but it also makes sure that our procedures meet the needs of your clients. This
raises income and improves consumer happiness.
Characteristics of a Process
A process has the following attributes.
 Process Id: A unique identifier assigned by the operating system.
 Process State: Can be ready, running, etc.
 CPU registers: Like the Program Counter (CPU registers must be saved and restored when
a process is swapped in and out of the CPU)
 Accounts information: Amount of CPU used for process execution, time limits, execution
ID, etc
 I/O status information: For example, devices allocated to the process, open files, etc
 CPU scheduling information: For example, Priority (Different processes may have
different priorities, for example, a shorter process assigned high priority in the shortest job first
scheduling)
All of the above attributes of a process are also known as the context of the process. Every process
has its own process control block(PCB), i.e. each process will have a unique PCB. All of the above
attributes are part of the PCB.
States of Process:
A process is in one of the following states:
 New: Newly Created Process (or) being-created process.
 Ready: After the creation process moves to the Ready state, i.e. the process is ready for
execution.
 Run: Currently running process in CPU (only one process at a time can be under execution
in a single processor)
 Wait (or Block): When a process requests I/O access.
 Complete (or Terminated): The process completed its execution.
 Suspended Ready: When the ready queue becomes full, some processes are moved to a
suspended ready state
 Suspended Block: When the waiting queue becomes full.

Context Switching of Process:

The process of saving the context of one process and loading the context of another process is
known as Context Switching. In simple terms, it is like loading and unloading the process from the
running state to the ready state.
When Does Context Switching Happen?
1. When a high-priority process comes to a ready state (i.e. with higher priority than the running
process).
2. An Interrupt occurs.
3. User and kernel-mode switch (It is not necessary though)
4. Preemptive CPU scheduling is used.
Context Switch vs Mode Switch
A mode switch occurs when the CPU privilege level is changed, for example when a system call is
made or a fault occurs. The kernel works in more a privileged mode than a standard user task. If a
user process wants to access things that are only accessible to the kernel, a mode switch must occur.
The currently executing process need not be changed during a mode switch. A mode switch
typically occurs for a process context switch to occur. Only the kernel can cause a context switch.
CPU-Bound vs I/O-Bound Processes
A CPU-bound process requires more CPU time or spends more time in the running state. An I/O-
bound process requires more I/O time and less CPU time. An I/O-bound process spends more time
in the waiting state.
Process planning is an integral part of the process management operating system. It refers to the
mechanism used by the operating system to determine which process to run next. The goal of
process scheduling I
s to improve overall system performance by maximizing CPU utilization, minimizing execution
time, and improving system response time.
Process Scheduling Algorithms
The operating system can use different scheduling algorithms to schedule processes. Here are
some commonly used timing algorithms:
 First-come, first-served (FCFS): This is the simplest scheduling algorithm, where the
process is executed on a first-come, first-served basis. FCFS is non-preemptive, which means
that once a process starts executing, it continues until it is finished or waiting for I/O.
 Shortest Job First (SJF): SJF is a proactive scheduling algorithm that selects the process
with the shortest burst time. The burst time is the time a process takes to complete its execution.
SJF minimizes the average waiting time of processes.
 Round Robin (RR): Round Robin is a proactive scheduling algorithm that reserves a fixed
amount of time in a round for each process. If a process does not complete its execution within
the specified time, it is blocked and added to the end of the queue. RR ensures fair distribution
of CPU time to all processes and avoids starvation.
 Priority Scheduling: This scheduling algorithm assigns priority to each process and the
process with the highest priority is executed first. Priority can be set based on process type,
importance, or resource requirements.
Advantages of Process Management
 Improved Efficiency: Process management can help organizations identify bottlenecks and
inefficiencies in their processes, allowing them to make changes to streamline workflows and
increase productivity.
 Cost Savings: By identifying and eliminating waste and inefficiencies, process
management can help organizations reduce costs associated with their business operations.
 Improved Quality: Process management can help organizations improve the quality of
their products or services by standardizing processes and reducing errors.
 Increased Customer Satisfaction: By improving efficiency and quality, process
management can enhance the customer experience and increase satisfaction.
 Compliance with Regulations: Process management can help organizations comply with
regulatory requirements by ensuring that processes are properly documented, controlled, and
monitored.
Disadvantages of Process Management
 Time and Resource Intensive: Implementing and maintaining process management
initiatives can be time-consuming and require significant resources.
 Resistance to Change: Some employees may resist changes to established processes,
which can slow down or hinder the implementation of process management initiatives.
 Overemphasis on Process: Overemphasis on the process can lead to a lack of focus on
customer needs and other important aspects of business operations.
 Risk of Standardization: Standardizing processes too much can limit flexibility and
creativity, potentially stifling innovation.
 Difficulty in Measuring Results: Measuring the effectiveness of process management
initiatives can be difficult, making it challenging to determine their impact on organizational
performance.
Process Table and Process Control Block (PCB)
While creating a process, the operating system performs several operations. To identify the
processes, it assigns a process identification number (PID) to each process. As the operating system
supports multi-programming, it needs to keep track of all the processes. For this task, the process
control block (PCB) is used to track the process’s execution status. Each block of memory contains
information about the process state, program counter, stack pointer, status of opened
files, scheduling algorithms, etc.
All this information is required and must be saved when the process is switched from one state to
another. When the process makes a transition from one state to another, the operating system must
update information in the process’s PCB. A process control block (PCB) contains information about
the process, i.e. registers, quantum, priority, etc. The process table is an array of PCBs, that means
logically contains a PCB for all of the current processes in the system.
1. Pointer: It is a stack pointer that is required to be saved when the process is switched from
one state to another to retain the current position of the process.
2. Process state: It stores the respective state of the process.
3. Process number: Every process is assigned a unique id known as process ID or PID which
stores the process identifier.
4. Program counter: It stores the counter,: which contains the address of the next instruction
that is to be executed for the process.
5. Register: Registers in the PCB, it is a data structure. When a processes is running and it’s
time slice expires, the current value of process specific registers would be stored in the PCB
and the process would be swapped out. When the process is scheduled to be run, the register
values is read from the PCB and written to the CPU registers. This is the main purpose of the
registers in the PCB.
6. Memory limits: This field contains the information about memory management system
used by the operating system. This may include page tables, segment tables, etc.
7. Open files list : This information includes the list of files opened for a process.
Additional Points to Consider for Process Control Block (PCB)
 Interrupt handling: The PCB also contains information about the interrupts that a process
may have generated and how they were handled by the operating system.
 Context switching: The process of switching from one process to another is called context
switching. The PCB plays a crucial role in context switching by saving the state of the current
process and restoring the state of the next process.
 Real-time systems: Real-time operating systems may require additional information in the
PCB, such as deadlines and priorities, to ensure that time-critical processes are executed in a
timely manner.
 Virtual memory management: The PCB may contain information about a process’s virtual
memory management, such as page tables and page fault handling.
 Inter-process communication: The PCB can be used to facilitate inter-process
communication by storing information about shared resources and communication channels
between processes.
 Fault tolerance: Some operating systems may use multiple copies of the PCB to provide
fault tolerance in case of hardware failures or software errors.
Advantages-
1. Efficient process management: The process table and PCB provide an efficient way to
manage processes in an operating system. The process table contains all the information about
each process, while the PCB contains the current state of the process, such as the program counter
and CPU registers.
2. Resource management: The process table and PCB allow the operating system to manage
system resources, such as memory and CPU time, efficiently. By keeping track of each process’s
resource usage, the operating system can ensure that all processes have access to the resources
they need.
3. Process synchronization: The process table and PCB can be used to synchronize processes
in an operating system. The PCB contains information about each process’s synchronization state,
such as its waiting status and the resources it is waiting for.
4. Process scheduling: The process table and PCB can be used to schedule processes for
execution. By keeping track of each process’s state and resource usage, the operating system can
determine which processes should be executed next.
Disadvantages-
1. Overhead: The process table and PCB can introduce overhead and reduce system
performance. The operating system must maintain the process table and PCB for each process,
which can consume system resources.
2. Complexity: The process table and PCB can increase system complexity and make it more
challenging to develop and maintain operating systems. The need to manage and synchronize
multiple processes can make it more difficult to design and implement system features and
ensure system stability.
 3. Scalability: The process table and PCB may not scale well for large-scale systems with
many processes. As the number of processes increases, the process table and PCB can become
larger and more difficult to manage efficiently.
4. Security: The process table and PCB can introduce security risks if they are not
implemented correctly. Malicious programs can potentially access or modify the process table
and PCB to gain unauthorized access to system resources or cause system instability.
Operation on a Process
The execution of a process is a complex activity. It involves various operations. Following are the
operations that are performed while execution of a process:

Creation
This is the initial step of the process execution activity. Process creation means the construction of a
new process for execution. This might be performed by the system, the user, or the old process
itself. There are several events that lead to the process creation. Some of the such events are the
following:
1. When we start the computer, the system creates several background processes.
2. A user may request to create a new process.
3. A process can create a new process itself while executing.
4. The batch system takes initiation of a batch job.
Scheduling/Dispatching
The event or activity in which the state of the process is changed from ready to run. It means the
operating system puts the process from the ready state into the running state. Dispatching is done by
the operating system when the resources are free or the process has higher priority than the ongoing
process. There are various other cases in which the process in the running state is preempted and the
process in the ready state is dispatched by the operating system.
Blocking
When a process invokes an input-output system call that blocks the process, and operating system is
put in block mode. Block mode is basically a mode where the process waits for input-output. Hence
on the demand of the process itself, the operating system blocks the process and dispatches another
process to the processor. Hence, in process-blocking operations, the operating system puts the
process in a ‘waiting’ state.
Preemption
When a timeout occurs that means the process hadn’t been terminated in the allotted time interval
and the next process is ready to execute, then the operating system preempts the process. This
operation is only valid where CPU scheduling supports preemption. Basically, this happens in
priority scheduling where on the incoming of high priority process the ongoing process is
preempted. Hence, in process preemption operation, the operating system puts the process in a
‘ready’ state.
Process Termination
Process termination is the activity of ending the process. In other words, process termination is the
relaxation of computer resources taken by the process for the execution. Like creation, in
termination also there may be several events that may lead to the process of termination. Some of
them are:
1. The process completes its execution fully and it indicates to the OS that it has finished.
2. The operating system itself terminates the process due to service errors.
3. There may be a problem in hardware that terminates the process.
4. One process can be terminated by another process.
What is Process Scheduling?
Process scheduling is the activity of the process manager that handles the removal of the running
process from the CPU and the selection of another process based on a particular strategy.
Process scheduling is an essential part of a Multiprogramming operating system. Such operating
systems allow more than one process to be loaded into the executable memory at a time and the
loaded process shares the CPU using time multiplexing.
 Process scheduler

Categories of Scheduling
Scheduling falls into one of two categories:
 Non-preemptive: In this case, a process’s resource cannot be taken before the process has
finished running. When a running process finishes and transitions to a waiting state, resources
are switched.
 Preemptive: In this case, the OS assigns resources to a process for a predetermined period.
The process switches from running state to ready state or from waiting for state to ready state
during resource allocation. This switching happens because the CPU may give other processes
priority and substitute the currently active process for the higher priority process.
Types of Process Schedulers
There are three types of process schedulers:
1. Long Term or Job Scheduler:
It brings the new process to the ‘Ready State’. It controls the Degree of Multi-programming, i.e.,
the number of processes present in a ready state at any point in time. It is important that the long-
term scheduler make a careful selection of both I/O and CPU-bound processes. I/O-bound tasks are
which use much of their time in input and output operations while CPU-bound processes are which
spend their time on the CPU. The job scheduler increases efficiency by maintaining a balance
between the two. They operate at a high level and are typically used in batch-processing systems.
2. Short-Term or CPU Scheduler:
It is responsible for selecting one process from the ready state for scheduling it on the running state.
Note: Short-term scheduler only selects the process to schedule it doesn’t load the process on
running. Here is when all the scheduling algorithms are used. The CPU scheduler is responsible for
ensuring no starvation due to high burst time processes.

Short Term Scheduler

The dispatcher is responsible for loading the process selected by the Short-term scheduler on the
CPU (Ready to Running State) Context switching is done by the dispatcher only. A dispatcher does
the following:
 Switching context.
 Switching to user mode.
 Jumping to the proper location in the newly loaded program.
3. Medium-Term Scheduler:
It is responsible for suspending and resuming the process. It mainly does swapping (moving
processes from main memory to disk and vice versa). Swapping may be necessary to improve the
process mix or because a change in memory requirements has overcommitted available memory,
requiring memory to be freed up. It is helpful in maintaining a perfect balance between the I/O
bound and the CPU bound. It reduces the degree of multiprogramming.

Medium Term Scheduler

Some Other Schedulers

 I/O schedulers: I/O schedulers are in charge of managing the execution of I/O operations
such as reading and writing to discs or networks. They can use various algorithms to determine
the order in which I/O operations are executed, such as FCFS (First-Come, First-Served) or RR
(Round Robin).
 Real-time schedulers: In real-time systems, real-time schedulers ensure that critical tasks
are completed within a specified time frame. They can prioritize and schedule tasks using
various algorithms such as EDF (Earliest Deadline First) or RM (Rate Monotonic).
Comparison Among Scheduler

Long Term Scheduler Short term schedular Medium Term Scheduler

 Long Term Scheduler Short term schedular Medium Term Scheduler

It is a process-swapping
It is a job scheduler It is a CPU scheduler
scheduler.

Speed lies in between both

Generally, Speed is lesser than Speed is the fastest among all
short and long-term
short term scheduler of them.
schedulers.

It gives less control over how

It controls the degree of It reduces the degree of
much multiprogramming is
multiprogramming multiprogramming.
done.

It is barely present or
It is a minimal time-sharing It is a component of systems
nonexistent in the time-
system. for time sharing.
sharing system.

It can re-enter the process into It can re-introduce the process

It selects those processes
memory, allowing for the into memory and execution
which are ready to execute
continuation of execution. can be continued.

Two-State Process Model Short-Term

The terms “running” and “non-running” states are used to describe the two-state process model.
1. Running: A newly created process joins the system in a running state when it is created.
2. Not running: Processes that are not currently running are kept in a queue and await
execution. A pointer to a specific process is contained in each entry in the queue. Linked lists
are used to implement the queue system. This is how the dispatcher is used. When a process is
stopped, it is moved to the back of the waiting queue. The process is discarded depending on
whether it succeeded or failed. The dispatcher then chooses a process to run from the queue in
either scenario.
Context Switching:
In order for a process execution to be continued from the same point at a later time, context
switching is a mechanism to store and restore the state or context of a CPU in the Process Control
block. A context switcher makes it possible for multiple processes to share a single CPU using this
method. A multitasking operating system must include context switching among its features.
The state of the currently running process is saved into the process control block when the
scheduler switches the CPU from executing one process to another. The state used to set the
computer, registers, etc. for the process that will run next is then loaded from its own PCB. After
that, the second can start processing.

Context Switching

In order for a process execution to be continued from the same point at a later time, context
switching is a mechanism to store and restore the state or context of a CPU in the Process Control
block. A context switcher makes it possible for multiple processes to share a single CPU using this
method. A multitasking operating system must include context switching among its features.
 Program Counter
 Scheduling information
 The base and limit register value
 Currently used register
 Changed State
 I/O State information
 Accounting information

CPU scheduling is the process of deciding which process will own the CPU to use while
another process is suspended. The main function of the CPU scheduling is to ensure that whenever
the CPU remains idle, the OS has at least selected one of the processes available in the ready-to-use
line.
In Multiprogramming, if the long-term scheduler selects multiple I / O binding processes then most
of the time, the CPU remains an idle. The function of an effective program is to improve resource
utilization.
If most operating systems change their status from performance to waiting then there may always
be a chance of failure in the system. So in order to minimize this excess, the OS needs to schedule
tasks in order to make full use of the CPU and avoid the possibility of deadlock.
Objectives of Process Scheduling Algorithm:
 Utilization of CPU at maximum level. Keep CPU as busy as possible.
 Allocation of CPU should be fair.
 Throughput should be Maximum. i.e. Number of processes that complete their execution
per time unit should be maximized.
 Minimum turnaround time, i.e. time taken by a process to finish execution should be the
least.
 There should be a minimum waiting time and the process should not starve in the ready
queue.
 Minimum response time. It means that the time when a process produces the first response
should be as less as possible.
What are the different terminologies/ criteria to take care of in any CPU Scheduling algorithm?
 Arrival Time: Time at which the process arrives in the ready queue.
 Completion Time: Time at which process completes its execution.
 Burst Time: Time required by a process for CPU execution.
 Turn Around Time: Time Difference between completion time and arrival time.
Turn Around Time = Completion Time – Arrival Time
 Waiting Time(W.T): Time Difference between turn around time and burst time.
Waiting Time = Turn Around Time – Burst Time
Things to take care while designing a CPU Scheduling algorithm?
Different CPU Scheduling algorithms have different structures and the choice of a particular
algorithm depends on a variety of factors. Many conditions have been raised to compare CPU
scheduling algorithms.
The criteria include the following:
 CPU utilization: The main purpose of any CPU algorithm is to keep the CPU as busy as
possible. Theoretically, CPU usage can range from 0 to 100 but in a real-time system, it varies
from 40 to 90 percent depending on the system load.
 Throughput: The average CPU performance is the number of processes performed and
completed during each unit. This is called throughput. The output may vary depending on the
length or duration of the processes.
 Turn round Time: For a particular process, the important conditions are how long it takes
to perform that process. The time elapsed from the time of process delivery to the time of
completion is known as the conversion time. Conversion time is the amount of time spent
waiting for memory access, waiting in line, using CPU, and waiting for I / O.
 Waiting Time: The Scheduling algorithm does not affect the time required to complete the
process once it has started performing. It only affects the waiting time of the process i.e. the
time spent in the waiting process in the ready queue.
 Response Time: In a collaborative system, turn around time is not the best option. The
process may produce something early and continue to computing the new results while the
previous results are released to the user. Therefore another method is the time taken in the
submission of the application process until the first response is issued. This measure is called
response time.
What are the different types of CPU Scheduling Algorithms?
There are mainly two types of scheduling methods:
 Preemptive Scheduling: Preemptive scheduling is used when a process switches from
running state to ready state or from the waiting state to the ready state.
 Non-Preemptive Scheduling: Non-Preemptive scheduling is used when a process
terminates , or when a process switches from running state to waiting state.

Different types of CPU Scheduling Algorithms

Let us now learn about these CPU scheduling algorithms in operating systems one by one:
1. First Come First Serve:
FCFS considered to be the simplest of all operating system scheduling algorithms. First come first
serve scheduling algorithm states that the process that requests the CPU first is allocated the CPU
first and is implemented by using FIFO queue.
Characteristics of FCFS:
 FCFS supports non-preemptive and preemptive CPU scheduling algorithms.
 Tasks are always executed on a First-come, First-serve concept.
 FCFS is easy to implement and use.
 This algorithm is not much efficient in performance, and the wait time is quite high.
Example
S. No Process ID Process Name Arrival Time Burst Time
___ ______ _______ _______ _______
1 P1 A 0 9
2 P2 B 1 3
3 P3 C 1 2
4 P4 D 1 4
5 P5 E 2 3
6 P6 F 3 2
Non Pre Emptive Approach

Now, let us solve this problem with the help of the Scheduling Algorithm named First Come First
Serve in a Non Preemptive Approach.

Gantt chart for the above Example 1 is:

Turn Around Time = Completion Time - Arrival Time

Waiting Time = Turn Around Time - Burst Time

Solution to the Above Question Example 1

S. Process Arrival Burst Completion Turn Around Waiting

No ID Time Time Time Time Time

1 P1 A 0 9 9 9 0

2 P2 B 1 3 12 11 8

3 P3 C 1 2 14 13 11
4 P4 D 1 4 18 17 13

5 P5 E 2 3 21 19 16

6 P6 F 3 2 23 20 18

The Average Completion Time is:

Average CT = ( 9 + 12 + 14 + 18 + 21 + 23 ) / 6

Average CT = 97 / 6

Average CT = 16.16667

The Average Waiting Time is:

Average WT = ( 0 + 8 + 11 + 13 + 16 + 18 ) /6

Average WT = 66 / 6

Average WT = 11

The Average Turn Around Time is:

Average TAT = ( 9 + 11 + 13 + 17 + 19 +20 ) / 6

Average TAT = 89 / 6

Average TAT = 14.83334

This is how the FCFS is solved in Non Pre Emptive Approach.

Advantages of FCFS:
 Easy to implement
 First come, first serve method
Disadvantages of FCFS:
 FCFS suffers from Convoy effect.
 The average waiting time is much higher than the other algorithms.
 FCFS is very simple and easy to implement and hence not much efficient.

2. Shortest Job First(SJF):

Shortest job first (SJF) is a scheduling process that selects the waiting process with the smallest
execution time to execute next. This scheduling method may or may not be preemptive.
Significantly reduces the average waiting time for other processes waiting to be executed. The full
form of SJF is Shortest Job First.

Example

In the following example, there are five jobs named as P1, P2, P3, P4 and P5. Their arrival time and
burst time are given in the table below.

PID Arrival Time Burst Time Completion Time Turn Around Time Waiting Time

1 1 7 8 7 0

2 3 3 13 10 7

3 6 2 10 4 2

4 7 10 31 24 14

5 9 8 21 12 4

Since, No Process arrives at time 0 hence; there will be an empty slot in the Gantt chart from time 0
to 1 (the time at which the first process arrives).
According to the algorithm, the OS schedules the process which is having the lowest burst time
among the available processes in the ready queue.

Till now, we have only one process in the ready queue hence the scheduler will schedule this to the
processor no matter what is its burst time.

This will be executed till 8 units of time. Till then we have three more processes arrived in the ready
queue hence the scheduler will choose the process with the lowest burst time.

Among the processes given in the table, P3 will be executed next since it is having the lowest burst
time among all the available processes.

So that's how the procedure will go on in shortest job first (SJF) scheduling algorithm.

Avg Waiting Time = 27/5

Characteristics of SJF:
 Shortest Job first has the advantage of having a minimum average waiting time among
all operating system scheduling algorithms.
 It is associated with each task as a unit of time to complete.
 It may cause starvation if shorter processes keep coming. This problem can be solved using
the concept of ageing.
Advantages of Shortest Job first:
 As SJF reduces the average waiting time thus, it is better than the first come first serve
scheduling algorithm.
 SJF is generally used for long term scheduling
Disadvantages of SJF:
 One of the demerit SJF has is starvation.
 Many times it becomes complicated to predict the length of the upcoming CPU request
To learn about how to implement this CPU scheduling algorithm, please refer to our detailed article
on Shortest Job First.
3. Priority Scheduling:
Preemptive Priority CPU Scheduling Algorithm is a pre-emptive method of CPU scheduling
algorithm that works based on the priority of a process. In this algorithm, the editor sets the
functions to be as important, meaning that the most important process must be done first. In the
case of any conflict, that is, where there is more than one process with equal value, then the most
important CPU planning algorithm works on the basis of the FCFS (First Come First Serve)
algorithm.
Characteristics of Priority Scheduling:
 Schedules tasks based on priority.
 When the higher priority work arrives and a task with less priority is executing, the higher
priority proess will takes the place of the less priority proess and
 The later is suspended until the execution is complete.
 Lower is the number assigned, higher is the priority level of a process.

Example

There are 7 processes P1, P2, P3, P4, P5, P6 and P7 given. Their respective priorities, Arrival Times
and Burst times are given in the table below.

Process Id Priority Arrival Time Burst Time

1 2 0 1

2 6 1 7

3 3 2 3

4 5 3 6

5 4 4 5
6 10 5 15

7 9 15 8

GANTT chart Preparation

At time 0, P1 arrives with the burst time of 1 units and priority 2. Since no other process is available
hence this will be scheduled till next job arrives or its completion (whichever is lesser).

At time 1, P2 arrives. P1 has completed its execution and no other process is available at this time
hence the Operating system has to schedule it regardless of the priority assigned to it.

The Next process P3 arrives at time unit 2, the priority of P3 is higher to P2. Hence the execution of
P2 will be stopped and P3 will be scheduled on the CPU.

During the execution of P3, three more processes P4, P5 and P6 becomes available. Since, all these
three have the priority lower to the process in execution so PS can't preempt the process. P3 will
complete its execution and then P5 will be scheduled with the priority highest among the available
processes.
 Meanwhile the execution of P5, all the processes got available in the ready queue. At this point, the
algorithm will start behaving as Non Preemptive Priority Scheduling. Hence now, once all the
processes get available in the ready queue, the OS just took the process with the highest priority and
execute that process till completion. In this case, P4 will be scheduled and will be executed till the
completion.

Since P4 is completed, the other process with the highest priority available in the ready queue is P2.
Hence P2 will be scheduled next.

P2 is given the CPU till the completion. Since its remaining burst time is 6 units hence P7 will be
scheduled after this.

The only remaining process is P6 with the least priority, the Operating System has no choice unless of
executing it. This will be executed at the last.

The Completion Time of each process is determined with the help of GANTT chart. The turnaround
time and the waiting time can be calculated by the following formula.

1. Turnaround Time = Completion Time - Arrival Time

2. Waiting Time = Turn Around Time - Burst Time

Process Priority Arrival Burst Completion Turn around Waiting

Id Time Time Time Time Time

1 2 0 1 1 1 0

2 6 1 7 22 21 14

3 3 2 3 5 3 0

4 5 3 6 16 13 7

5 4 4 5 10 6 1

6 10 5 15 45 40 25

7 9 6 8 30 24 16

Avg Waiting Time = (0+14+0+7+1+25+16)/7 = 63/7 = 9 units

Advantages of Priority Scheduling:

 The average waiting time is less than FCFS
 Less complex
Disadvantages of Priority Scheduling:
 One of the most common demerits of the Preemptive priority CPU scheduling algorithm is
the Starvation Problem. This is the problem in which a process has to wait for a longer amount
of time to get scheduled into the CPU. This condition is called the starvation problem.
To learn about how to implement this CPU scheduling algorithm, please refer to our detailed article
on Priority Preemptive Scheduling algorithm.
4. Round robin:
Round Robin is a CPU scheduling algorithm where each process is cyclically assigned a fixed time
slot. It is the preemptive version of the First come First Serve CPU Scheduling algorithm.

 Round Robin CPU Algorithm generally focuses on Time Sharing technique.

 The period of time for which a process or job is allowed to run in a pre-emptive method is
called time quantum.
 Each process or job present in the ready queue is assigned the CPU for that time quantum, if
the execution of the process is completed during that time then the process will end else the
process will go back to the waiting table and wait for its next turn to complete the execution.
Characteristics of Round robin:
 It’s simple, easy to use, and starvation-free as all processes get the balanced CPU allocation.
 One of the most widely used methods in CPU scheduling as a core.
 It is considered preemptive as the processes are given to the CPU for a very limited time.

Example 2: Consider the following table of arrival time and burst time for three processes P1, P2
and P3 and given Time Quantum = 2

Process Burst Time Arrival Time

P1 10 ms 0 ms

P2 5 ms 0 ms

P3 8 ms 0 ms

Similarly, Gantt chart for this example:

Gantt chart for example 2

Now, lets calculate average waiting time and turn around time:

Processes AT BT CT TAT WT

P1 0 10 23 23-0 = 23 23-10 = 13

P2 0 5 15 15-0 = 15 15-5 = 10

P3 0 8 21 21-0 = 21 21-8 = 13

Total Turn Around Time = 59 ms

So, Average Turn Around Time = 59/3 = 19.667 ms
 And, Total Waiting Time = 36 ms
So, Average Waiting Time = 36/3 = 12.00 ms

Advantages of Round Robin CPU Scheduling Algorithm

 There is fairness since every process gets an equal share of the CPU.
 The newly created process is added to the end of the ready queue.
 A round-robin scheduler generally employs time-sharing, giving each job a time slot or
quantum.
 While performing a round-robin scheduling, a particular time quantum is allotted to
different jobs.
 Each process get a chance to reschedule after a particular quantum time in this scheduling.
Disadvantages of Round Robin CPU Scheduling Algorithm:
 There is Larger waiting time and Response time.
 There is Low throughput.
 There is Context Switches.
 Gnatt chart seems to come too big.
 Time consuming scheduling for small quantum.

Inter Process Communication (IPC):

A process can be of two types:

 Independent process.
 Co-operating process.
An independent process is not affected by the execution of other processes while a co-operating
process can be affected by other executing processes. Though one can think that those processes,
which are running independently, will execute very efficiently, in reality, there are many situations
when co-operative nature can be utilized for increasing computational speed, convenience, and
modularity. Inter-process communication (IPC) is a mechanism that allows processes to
communicate with each other and synchronize their actions. The communication between these
processes can be seen as a method of co-operation between them. Processes can communicate with
each other through both:

1. Shared Memory
2. Message passing
Figure 1 below shows a basic structure of communication between processes via the shared memory
method and via the message passing method.
An operating system can implement both methods of communication. First, we will discuss
the shared memory methods of communication and then message passing. Communication between
processes using shared memory requires processes to share some variable, and it completely
depends on how the programmer will implement it. One way of communication using shared
memory can be imagined like this: Suppose process1 and process2 are executing simultaneously,
and they share some resources or use some information from another process. Process1 generates
information about certain computations or resources being used and keeps it as a record in shared
memory. When process2 needs to use the shared information, it will check in the record stored in
shared memory and take note of the information generated by process1 and act accordingly.
Processes can use shared memory for extracting information as a record from another process as
well as for delivering any specific information to other processes.
Let’s discuss an example of communication between processes using the shared memory method.

i) Shared Memory Method:

Ex: Producer-Consumer problem

There are two processes: Producer and Consumer.

The producer produces some items and the Consumer consumes that item. The two
processes share a common space or memory location known as a buffer where the item produced by
the Producer is stored and from which the Consumer consumes the item if needed. There are two
versions of this problem: the first one is known as the unbounded buffer problem in which the
Producer can keep on producing items and there is no limit on the size of the buffer, the second one
is known as the bounded buffer problem in which the Producer can produce up to a certain number
of items before it starts waiting for Consumer to consume it. We will discuss the bounded buffer
problem. First, the Producer and the Consumer will share some common memory, then the producer
will start producing items. If the total produced item is equal to the size of the buffer, the producer
will wait to get it consumed by the Consumer. Similarly, the consumer will first check for the
availability of the item. If no item is available, the Consumer will wait for the Producer to produce
it. If there are items available, Consumer will consume them.

ii) Messaging Passing Method

Now, We will start our discussion of the communication between processes via message passing. In
this method, processes communicate with each other without using any kind of shared memory. If
two processes p1 and p2 want to communicate with each other, they proceed as follows:

 Establish a communication link (if a link already exists, no need to establish it again.)
 Start exchanging messages using basic primitives.
We need at least two primitives:
– send(message, destination) or send(message)
– receive(message, host) or receive(message)

The message size can be of fixed size or of variable size. If it is of fixed size, it is easy for
an OS designer but complicated for a programmer and if it is of variable size then it is easy for a
programmer but complicated for the OS designer. A standard message can have two parts: header
and body.
The header part is used for storing message type, destination id, source id, message length, and
control information. The control information contains information like what to do if runs out of
buffer space, sequence number, priority. Generally, message is sent using FIFO style.

Message Passing through Communication Link.

Direct and Indirect Communication link
Now, We will start our discussion about the methods of implementing communication links. While
implementing the link, there are some questions that need to be kept in mind like :

1. How are links established?

2. Can a link be associated with more than two processes?
3. How many links can there be between every pair of communicating processes?
4. What is the capacity of a link? Is the size of a message that the link can accommodate fixed
or variable?
5. Is a link unidirectional or bi-directional?
A link has some capacity that determines the number of messages that can reside in it
temporarily for which every link has a queue associated with it which can be of zero capacity,
bounded capacity, or unbounded capacity. In zero capacity, the sender waits until the receiver
informs the sender that it has received the message. In non-zero capacity cases, a process does not
know whether a message has been received or not after the send operation. For this, the sender must
communicate with the receiver explicitly. Implementation of the link depends on the situation, it
can be either a direct communication link or an in-directed communication link.
Direct Communication links are implemented when the processes use a specific process identifier
for the communication, but it is hard to identify the sender ahead of time.
For example the print server.
In-direct Communication is done via a shared mailbox (port), which consists of a queue of
messages. The sender keeps the message in mailbox and the receiver picks them up.

Message Passing through Exchanging the Messages.

Synchronous and Asynchronous Message Passing:

A process that is blocked is one that is waiting for some event, such as a resource becoming
available or the completion of an I/O operation. IPC is possible between the processes on same
computer as well as on the processes running on different computer i.e. in networked/distributed
system. In both cases, the process may or may not be blocked while sending a message or
attempting to receive a message so message passing may be blocking or non-blocking. Blocking is
considered synchronous and blocking send means the sender will be blocked until the message is
received by receiver. Similarly, blocking receive has the receiver block until a message is available.
Non-blocking is considered asynchronous and Non-blocking send has the sender sends the
message and continue. Similarly, Non-blocking receive has the receiver receive a valid message or
null. After a careful analysis, we can come to a conclusion that for a sender it is more natural to be
non-blocking after message passing as there may be a need to send the message to different
processes. However, the sender expects acknowledgment from the receiver in case the send fails.
Similarly, it is more natural for a receiver to be blocking after issuing the receive as the information
from the received message may be used for further execution. At the same time, if the message send
keep on failing, the receiver will have to wait indefinitely. That is why we also consider the other
possibility of message passing. There are basically three preferred combinations:

 Blocking send and blocking receive

 Non-blocking send and Non-blocking receive
 Non-blocking send and Blocking receive (Mostly used)
In Direct message passing, The process which wants to communicate must explicitly name the
recipient or sender of the communication.
e.g. send(p1, message) means send the message to p1.
Similarly, receive(p2, message) means to receive the message from p2.
In this method of communication, the communication link gets established automatically, which
can be either unidirectional or bidirectional, but one link can be used between one pair of the sender
and receiver and one pair of sender and receiver should not possess more than one pair of links.
Symmetry and asymmetry between sending and receiving can also be implemented i.e. either both
processes will name each other for sending and receiving the messages or only the sender will name
the receiver for sending the message and there is no need for the receiver for naming the sender for
receiving the message. The problem with this method of communication is that if the name of one
process changes, this method will not work.
In Indirect message passing, processes use mailboxes (also referred to as ports) for sending and
receiving messages. Each mailbox has a unique id and processes can communicate only if they
share a mailbox. Link established only if processes share a common mailbox and a single link can
be associated with many processes. Each pair of processes can share several communication links
and these links may be unidirectional or bi-directional. Suppose two processes want to
communicate through Indirect message passing, the required operations are: create a mailbox, use
this mailbox for sending and receiving messages, then destroy the mailbox. The standard primitives
used are: send(A, message) which means send the message to mailbox A. The primitive for the
receiving the message also works in the same way e.g. received (A, message). There is a problem
with this mailbox implementation. Suppose there are more than two processes sharing the same
mailbox and suppose the process p1 sends a message to the mailbox, which process will be the
receiver? This can be solved by either enforcing that only two processes can share a single mailbox
or enforcing that only one process is allowed to execute the receive at a given time or select any
process randomly and notify the sender about the receiver. A mailbox can be made private to a
single sender/receiver pair and can also be shared between multiple sender/receiver pairs. Port is an
implementation of such mailbox that can have multiple senders and a single receiver. It is used in
client/server applications (in this case the server is the receiver). The port is owned by the receiving
process and created by OS on the request of the receiver process and can be destroyed either on
request of the same receiver processor when the receiver terminates itself. Enforcing that only one
process is allowed to execute the receive can be done using the concept of mutual exclusion. Mutex
mailbox is created which is shared by n process. The sender is non-blocking and sends the message.
The first process which executes the receive will enter in the critical section and all other processes
will be blocking and will wait.

Examples of IPC systems

1. Posix : uses shared memory method.

2. Mach : uses message passing
3. Windows XP : uses message passing using local procedural calls
Communication in client/server Architecture:
There are various mechanism:

 Pipe
 Socket
 Remote Procedural calls (RPCs)
The above three methods will be discussed in later articles as all of them are quite conceptual and
deserve their own separate articles.

Advantages of IPC:

1. Enables processes to communicate with each other and share resources, leading to increased
efficiency and flexibility.
2. Facilitates coordination between multiple processes, leading to better overall system
performance.
3. Allows for the creation of distributed systems that can span multiple computers or networks.
4. Can be used to implement various synchronization and communication protocols, such as
semaphores, pipes, and sockets.

Disadvantages of IPC:

1. Increases system complexity, making it harder to design, implement, and debug.

2. Can introduce security vulnerabilities, as processes may be able to access or modify data
belonging to other processes.
3. Requires careful management of system resources, such as memory and CPU time, to
ensure that IPC operations do not degrade overall system performance.
Can lead to data inconsistencies if multiple processes try to access or modify the same data at
the same time.
4. Overall, the advantages of IPC outweigh the disadvantages, as it is a necessary mechanism
for modern operating systems and enables processes to work together and share resources in a
flexible and efficient manner. However, care must be taken to design and implement IPC
systems carefully, in order to avoid potential security vulnerabilities and performance issues.

Process Synchronization in OS (Operating System)

Process Synchronization is the coordination of execution of multiple processes in a multi-process

system to ensure that they access shared resources in a controlled and predictable manner. It aims to
resolve the problem of race conditions and other synchronization issues in a concurrent system.

The main objective of process synchronization is to ensure that multiple processes access shared
resources without interfering with each other and to prevent the possibility of inconsistent data due
to concurrent access. To achieve this, various synchronization techniques such as semaphores,
monitors, and critical sections are used.

In a multi-process system, synchronization is necessary to ensure data consistency and integrity,

and to avoid the risk of deadlocks and other synchronization problems. Process synchronization is
an important aspect of modern operating systems, and it plays a crucial role in ensuring the correct
and efficient functioning of multi-process systems.

On the basis of synchronization, processes are categorized as one of the following two types:

 Independent Process: The execution of one process does not affect the execution of other
processes.
 Cooperative Process: A process that can affect or be affected by other processes executing
in the system.
Process synchronization problem arises in the case of Cooperative processes also because resources
are shared in Cooperative processes.

Race Condition
When more than one process is executing the same code or accessing the same memory or any
shared variable in that condition there is a possibility that the output or the value of the shared
variable is wrong so for that all the processes doing the race to say that my output is correct this
condition known as a race condition. Several processes access and process the manipulations over
the same data concurrently, and then the outcome depends on the particular order in which the
access takes place. A race condition is a situation that may occur inside a critical section. This
happens when the result of multiple thread execution in the critical section differs according to the
order in which the threads execute. Race conditions in critical sections can be avoided if the critical
section is treated as an atomic instruction. Also, proper thread synchronization using locks or
atomic variables can prevent race conditions.

Example:

Let’s understand one example to understand the race condition better:

Let’s say there are two processes P1 and P2 which share a common variable (shared=10), both
processes are present in – queue and waiting for their turn to be executed. Suppose, Process P1 first
come under execution, and the CPU store a common variable between them (shared=10) in the local
variable (X=10) and increment it by 1(X=11), after then when the CPU read line sleep(1),it
switches from current process P1 to process P2 present in ready-queue. The process P1 goes in a
waiting state for 1 second.

Now CPU execute the Process P2 line by line and store common variable (Shared=10) in its local
variable (Y=10) and decrement Y by 1(Y=9), after then when CPU read sleep(1), the current
process P2 goes in waiting for state and CPU remains idle for some time as there is no process in
ready-queue, after completion of 1 second of process P1 when it comes in ready-queue, CPU takes
the process P1 under execution and execute the remaining line of code (store the local variable
(X=11) in common variable (shared=11) ), CPU remain idle for sometime waiting for any process
in ready-queue,after completion of 1 second of Process P2, when process P2 comes in ready-queue,
CPU start executing the further remaining line of Process P2(store the local variable (Y=9) in
common variable (shared=9) ).

Initially Shared = 10

Process 1 Process 2

int X = shared int Y = shared

X++ Y–

sleep(1) sleep(1)

shared = X shared = Y

Note: We are assuming the final value of a common variable(shared) after execution of Process P1
and Process P2 is 10 (as Process P1 increment variable (shared=10) by 1 and Process P2 decrement
variable (shared=11) by 1 and finally it becomes shared=10). But we are getting undesired value
due to a lack of proper synchronization.

Actual meaning of race-condition

 If the order of execution of the process(first P1 -> then P2) then we will get the value of
common variable (shared) =9.
 If the order of execution of the process(first P2 -> then P1) then we will get the final value
of common variable (shared) =11.
 Here the (value1 = 9) and (value2=10) are racing, If we execute these two processes in our
computer system then sometime we will get 9 and sometime we will get 10 as the final value of
a common variable(shared). This phenomenon is called race condition.
Critical Section Problem
A critical section is a code segment that can be accessed by only one process at a time. The critical
section contains shared variables that need to be synchronized to maintain the consistency of data
variables. So the critical section problem means designing a way for cooperative processes to
access shared resources without creating data inconsistencies.

In the entry section, the process requests for entry in the Critical Section.

Any solution to the critical section problem must satisfy three requirements:

 Mutual Exclusion: If a process is executing in its critical section, then no other process is
allowed to execute in the critical section.
 Progress: If no process is executing in the critical section and other processes are waiting
outside the critical section, then only those processes that are not executing in their remainder
 section can participate in deciding which will enter the critical section next, and the selection
can not be postponed indefinitely.
 Bounded Waiting: A bound must exist on the number of times that other processes are
allowed to enter their critical sections after a process has made a request to enter its critical
section and before that request is granted.
Peterson’s Solution:
Peterson’s Solution is a classical software-based solution to the critical section problem. In
Peterson’s solution, we have two shared variables:

 boolean flag[i]: Initialized to FALSE, initially no one is interested in entering the critical
section
 int turn: The process whose turn is to enter the critical section.

Peterson’s Solution preserves all three conditions:

 Mutual Exclusion is assured as only one process can access the critical section at any time.
 Progress is also assured, as a process outside the critical section does not block other
processes from entering the critical section.
 Bounded Waiting is preserved as every process gets a fair chance.
Disadvantages of Peterson’s Solution
 It involves busy waiting. (In the Peterson’s solution, the code statement- “while(flag[j] &&
turn == j);” is responsible for this. Busy waiting is not favored because it wastes CPU cycles that
could be used to perform other tasks.)
 It is limited to 2 processes.
 Peterson’s solution cannot be used in modern CPU architectures.

Semaphores:
A semaphore is a signaling mechanism and a thread that is waiting on a semaphore can be signaled
by another thread. This is different than a mutex as the mutex can be signaled only by the thread
that is called the wait function.

A semaphore uses two atomic operations, wait and signal for process synchronization.
A Semaphore is an integer variable, which can be accessed only through two operations wait() and
signal().

There are two types of semaphores: Binary Semaphores and Counting Semaphores.

 Binary Semaphores: They can only be either 0 or 1. They are also known as mutex locks,
as the locks can provide mutual exclusion. All the processes can share the same mutex
semaphore that is initialized to 1. Then, a process has to wait until the lock becomes 0. Then, the
process can make the mutex semaphore 1 and start its critical section. When it completes its
critical section, it can reset the value of the mutex semaphore to 0 and some other process can
enter its critical section.
 Counting Semaphores: They can have any value and are not restricted to a certain domain.
They can be used to control access to a resource that has a limitation on the number of
simultaneous accesses. The semaphore can be initialized to the number of instances of the
resource. Whenever a process wants to use that resource, it checks if the number of remaining
instances is more than zero, i.e., the process has an instance available. Then, the process can
enter its critical section thereby decreasing the value of the counting semaphore by 1. After the
process is over with the use of the instance of the resource, it can leave the critical section
thereby adding 1 to the number of available instances of the resource.
Advantages of Process Synchronization
 Ensures data consistency and integrity
 Avoids race conditions
 Prevents inconsistent data due to concurrent access
 Supports efficient and effective use of shared resources
Disadvantages of Process Synchronization
 Adds overhead to the system
 This can lead to performance degradation
 Increases the complexity of the system
 Can cause deadlocks if not implemented properly.
Problem on Counting Semaphore:
1. Wait → Decrement → Down → P

2. Signal → Increment → Up → V

A Counting Semaphore was initialized to 12. then 10P (wait) and 4V (Signal) operations were
computed on this semaphore. What is the result?

1. S = 12 (initial)

2. 10 p (wait) :

3. SS = S -10 = 12 - 10 = 2

4. then 4 V :

5. SS = S + 4 =2 + 4 = 6

Hence, the final value of counting semaphore is 6.

Deadlock in Operating System:

A deadlock is a situation where a set of processes is blocked because each process is holding
a resource and waiting for another resource acquired by some other process. In this article, we will
discuss deadlock, its necessary conditions, etc. in detail.

What is Deadlock?

Deadlock is a situation in computing where two or more processes are unable to proceed because each
is waiting for the other to release resources. Key concepts include mutual exclusion, resource holding,
circular wait, and no preemption.

Consider an example when two trains are coming toward each other on the same track and there is
only one track, none of the trains can move once they are in front of each other. This is a practical
example of deadlock.

How Does Deadlock occur in the Operating System?

Before going into detail about how deadlock occurs in the Operating System, let’s first discuss how
the Operating System uses the resources present. A process in an operating system uses resources in
the following way.

 Requests a resource
 Use the resource
 Releases the resource
A situation occurs in operating systems when there are two or more processes that hold some
resources and wait for resources held by other(s). For example, in the below diagram, Process 1 is
holding Resource 1 and waiting for resource 2 which is acquired by process 2, and process 2 is
waiting for resource 1.

Examples of Deadlock

There are several examples of deadlock. Someof them are mentioned below.

1. The system has 2 tape drives. P0 and P1 each hold one tape drive and each needs another one.

2. Semaphores A and B, initialized to 1, P0, and P1 are in deadlock as follows:

 P0 executes wait(A) and preempts.

 P1 executes wait(B).
 Now P0 and P1 enter in deadlock.

P0 P1

Wait(A); wait(B)

wait(B); wait(A)

3. Assume the space is available for allocation of 200K bytes, and the following sequence of events
occurs.
 P0 P1

Request 80KB; Request 70KB;

Request 60KB; Request 80KB;

Deadlock occurs if both processes progress to their second request.

Necessary Conditions for Deadlock in OS

Deadlock can arise if the following four conditions hold simultaneously (Necessary Conditions)

 Mutual Exclusion: Two or more resources are non-shareable (Only one process can use at a
time).
 Hold and Wait: A process is holding at least one resource and waiting for resources.
 No Preemption: A resource cannot be taken from a process unless the process releases the
resource.
 Circular Wait: A set of processes waiting for each other in circular form.

What is Deadlock Detection?

Deadlock detection is a process in computing where the system checks if there are any sets of
processes that are stuck waiting for each other indefinitely, preventing them from moving forward. In
simple words, deadlock detection is the process of finding out whether any process are stuck in loop
or not. There are several algorithms like

 Resource Aloocation Graph

 Banker’s Algorithm

These algorithms helps in detection of deadlock in Operating System.

What are the Methods For Handling Deadlock?

There are three ways to handle deadlock

 Deadlock Prevention or Avoidance

 Deadlock Recovery
 Deadlock Ignorance

Deadlock Prevention or Avoidance

Deadlock Prevention and Avoidance is the one of the methods for handling deadlock. First, we will
discuss Deadlock Prevention, then Deadlock Avoidance.
What is Deadlock Prevention?

The idea is to not let the system into a deadlock state. This system will make sure that above
mentioned four conditions will not arise. These techniques are very costly so we use this in cases
where our priority is making a system deadlock-free.
One can zoom into each category individually, Prevention is done by negating one of the above-
mentioned necessary conditions for deadlock. Prevention can be done in four different ways:

 Eliminate mutual exclusion

 Solve Hold and Wait
 Allow Preemption
 Circular Wait Solution

What is Deadlock Avoidance?

Avoidance is kind of futuristic. By using the strategy of “Avoidance”, we have to make an assumption.
We need to ensure that all information about resources that the process will need is known to us
before the execution of the process. We use Banker’s algorithm (Which is in turn a gift from Dijkstra)
to avoid deadlock.

In prevention and avoidance, we get the correctness of data but performance decreases.

What is Deadlock Recovery?

If Deadlock prevention or avoidance is not applied to the software then we can handle this by
deadlock detection and recovery. which consist of two phases:

1. In the first phase, we examine the state of the process and check whether there is a deadlock
or not in the system.
2. If found deadlock in the first phase then we apply the algorithm for recovery of the deadlock.

In Deadlock detection and recovery, we get the correctness of data but performance decreases.

Methods of Deadlock Recovery

There are several Deadlock Recovery Techniques:

 Manual Intervention
 Automatic Recovery
 Process Termination
 Resource Preemption
1. Manual Intervention

When a deadlock is detected, one option is to inform the operator and let them handle the situation
manually. While this approach allows for human judgment and decision-making, it can be time-
consuming and may not be feasible in large-scale systems.

2. Automatic Recovery

An alternative approach is to enable the system to recover from deadlock automatically. This method
involves breaking the deadlock cycle by either aborting processes or preempting resources. Let’s
delve into these strategies in more detail.

3. Process Termination

 Abort all Deadlocked Processes

o This approach breaks the deadlock cycle, but it comes at a significant cost. The
processes that were aborted may have executed for a considerable amount of time, resulting
in the loss of partial computations. These computations may need to be recomputed later.
 Abort one process at a time
o Instead of aborting all deadlocked processes simultaneously, this strategy involves
selectively aborting one process at a time until the deadlock cycle is eliminated. However,
this incurs overhead as a deadlock-detection algorithm must be invoked after each process
termination to determine if any processes are still deadlocked.
o Factors for choosing the termination order:
o The process’s priority
o Completion time and the progress made so far
o Resources consumed by the process
o Resources required to complete the process
o Number of processes to be terminated
o Process type (interactive or batch)

4. Resource Preemption

 Selecting a Victim
o Resource preemption involves choosing which resources and processes should be
preempted to break the deadlock. The selection order aims to minimize the overall cost of
 recovery. Factors considered for victim selection may include the number of resources held
by a deadlocked process and the amount of time the process has consumed.
 Rollback
o If a resource is preempted from a process, the process cannot continue its normal
execution as it lacks the required resource. Rolling back the process to a safe state and
restarting it is a common approach. Determining a safe state can be challenging, leading to
the use of total rollback, where the process is aborted and restarted from scratch.
 Starvation Prevention
o To prevent resource starvation, it is essential to ensure that the same process is not
always chosen as a victim. If victim selection is solely based on cost factors, one process
might repeatedly lose its resources and never complete its designated task. To address this,
it is advisable to limit the number of times a process can be chosen as a victim, including
the number of rollbacks in the cost factor.

What is Deadlock Ignorance?

If a deadlock is very rare, then let it happen and reboot the system. This is the approach that both
Windows and UNIX take. we use the ostrich algorithm for deadlock ignorance.

In Deadlock, ignorance performance is better than the above two methods but the correctness of data
is not there.

Safe State

A safe state can be defined as a state in which there is no deadlock. It is achievable if:

 If a process needs an unavailable resource, it may wait until the same has been released by a
process to which it has already been allocated. if such a sequence does not exist, it is an unsafe
state.
 All the requested resources are allocated to the process.

Aspect Deadlock Starvation

A condition where two or more A condition where a process is

Definition processes are blocked forever, each perpetually denied necessary resources,
waiting for a resource held by another. despite resources being available.
 Aspect Deadlock Starvation

Resources are available but are

Resource Resources are held by processes
continuously allocated to other
Availability involved in the deadlock.
processes.

Circular dependency between processes, Continuous preference or priority given

Cause where each process is waiting for a to other processes, causing a process to
resource from another. wait indefinitely.

Requires intervention, such as aborting Can be mitigated by adjusting

Resolution processes or preempting resources to scheduling policies to ensure fair
break the cycle. resource allocation.

Resource Allocation Graph

The resource allocation graph is the pictorial representation of the state of a system. As its name
suggests, the resource allocation graph is the complete information about all the processes which are
holding some resources or waiting for some resources.

It also contains the information about all the instances of all the resources whether they are available
or being used by the processes.

In Resource allocation graph, the process is represented by a Circle while the Resource is represented
by a rectangle. Let's see the types of vertices and edges in detail.
Vertices are mainly of two types, Resource and process. Each of them will be represented by a
different shape. Circle represents process while rectangle represents resource.

A resource can have more than one instance. Each instance will be represented by a dot inside the
rectangle.

Edges in RAG are also of two types, one represents assignment and other represents the wait of a
process for a resource. The above image shows each of them.

A resource is shown as assigned to a process if the tail of the arrow is attached to an instance to the
resource and the head is attached to a process.

A process is shown as waiting for a resource if the tail of an arrow is attached to the process while the
head is pointing towards the resource.

Example
Let'sconsider 3 processes P1, P2 and P3, and two types of resources R1 and R2. The resources are
having 1 instance each.

According to the graph, R1 is being used by P1, P2 is holding R2 and waiting for R1, P3 is waiting
for R1 as well as R2.

The graph is deadlock free since no cycle is being formed in the graph.

Deadlock Detection using RAG

If a cycle is being formed in a Resource allocation graph where all the resources have the single
instance then the system is deadlocked.

In Case of Resource allocation graph with multi-instanced resource types, Cycle is a necessary
condition of deadlock but not the sufficient condition.

The following example contains three processes P1, P2, P3 and three resources R2, R2, R3. All the
resources are having single instances each.
If we analyze the graph then we can find out that there is a cycle formed in the graph since the system
is satisfying all the four conditions of deadlock.

Banker's Algorithm: How Does It Work?

Let us consider a bank has "n" number of accounts and "M" is the total cash in the bank. If a customer
has applied for a loan, then the bank first subtracts the loan amount from the total cash available and
then verifies that the cash difference must be greater than the total cash "M" to approve the loan. This
process helps the bank to manage and operate all the banking functions without any restriction.

In the same way, the banker’s algorithm works in a computer system’s operating system. In a
computer system, when a new process enters the system. Then, the process must declare the
maximum number of instances of each resource type that it may require to execute. This number must
not be more than the total number of resources in the system. Now, when a new process requests
resources, the system must calculate whether the allocation of the requested resources will leave the
computer system in a safe state. If so then the process will get allocated the requested resources,
otherwise it must wait until some other process releases the requested resources.

By following this practice, the banker’s algorithm avoids deadlock and allocate resources safely. For
this reason, it is also termed as deadlock detection algorithm or deadlock avoidance algorithm in
the operating system.

Data Structures Used in Banker’s Algorithm

In a computer system, if the number of processes is equal to "n" and the number of resource types is
"m". The following four data structures are required to implement the banker’s algorithm −

Available − It is a vector of length "m" that indicates the number of available resources of
each type in the system. If Available [j] = k, then "k" be the instances of resource type
Rj available in the system.

Max − It is a [n × m] matrix that defines the maximum resource demand of each process.
When Max [I, j] = k, then a process Pi may request maximum k instances of resource type, Rj.
 Allocation − – It is also a [n × m] matrix that defines the number of resources of each type
which are currently allocated to each process. Therefore, if Allocation [i, j] = k, then a process
Pi is currently allocated "k" instances of resource type, Rj.

Need − It is an [n × m] matrix that represents the remaining resource need of each process.
When Need [i, j] = k, then a process Pi may need "k" more instances of resource type Rj to
accomplish the assigned task.

Finish − It is a matrix of length "m". It includes a Boolean value, i.e. TRUE or FALSE to
indicate whether a process has been allocated to the needed resources, or all resources have
been released after finishing the assigned work.

Also, it is to be noted that,

Need [i, j] = Max [i, j] – Allocation [i, j]

The baker’s algorithm is a combination of two algorithms namely, Safety Algorithm and Resource
Request Algorithm. These two algorithms together control the processes and avoid dead lock in a
system.

Safety Algorithm

The safety algorithm is one that determines whether or not the system is in a safe state. It follows the
following safe sequence in the banker’s algorithm −

Step 1
Consider two vectors named Work and Finish of lengths "m" and "n" respectively.

Initialize: Work = Available

Finish [i] = false; for i = 0, 1, 2, 3, 4, 5 … n.

Step 2

Find "i" such that both Finish [i] = false and Needi ≤ Work

If such "i" does not exist, then go to the step 4.

Step 3
Work = Work + Allocation

Finish [i] = true

Go to step 2.
Step 4
If Finish [i] = true for all "i", it means that the system is in a safe state otherwise it is in unsafe
state.

This algorithm takes (m × n2) operations to decide whether the state is safe or not.

Now, let us discuss the Resource Request Algorithm.

Resource Request Algorithm:

This algorithm determines how a system behaves when a process request for each type of resource in
the system.

Let us consider a request vector Requesti for a process Pi. When Requesti [j] = k, then the process
Pi requires k instances of resource type Rj.

When a process Pi requests for resources, the following sequence is followed −

Step 1

If Requesti ≤ Needi, then go to the step 2. Otherwise give an error as the process has exceeded its
maximum claim for the resource.

Step 2

If Requesti ≤ Available, then go to the step 3. Otherwise, the process Pi must wait until the resource is
available.

Step 3

If the requested resource is allocated to the process, Pi by modifying the state as follows −
Available = Available – Requesti;
Allocationi = Allocationi + Requesti;
Needi = Needi – Requesti;

When the state of the resulting resource allocation is safe, then the requested resources are allocated to
the process, Pi. If the new state is unsafe, then the process Pi must wait for Requesti and the old
resource allocation state is restored.

Example: Consider a system that contains five processes P1, P2, P3, P4, P5 and the three resource
types A, B and C. Following are the resources types: A has 10, B has 5 and the resource type C has 7
instances.

Process Allocation Max Available

A B C A B C A B C

P1 0 1 0 7 5 3 3 3 2

P2 2 0 0 3 2 2

P3 3 0 2 9 0 2

P4 2 1 1 2 2 2

P5 0 0 2 4 3 3

Answer the following questions using the banker's algorithm:

1. What is the reference of the need matrix?

2. Determine if the system is safe or not.
3. What will happen if the resource request (1, 0, 0) for process P1 can the system accept this
request immediately?

Ans. 2: Context of the need matrix is as follows:

Need [i] = Max [i] - Allocation [i]

Need for P1: (7, 5, 3) - (0, 1, 0) = 7, 4, 3
Need for P2: (3, 2, 2) - (2, 0, 0) = 1, 2, 2
Need for P3: (9, 0, 2) - (3, 0, 2) = 6, 0, 0
Need for P4: (2, 2, 2) - (2, 1, 1) = 0, 1, 1
Need for P5: (4, 3, 3) - (0, 0, 2) = 4, 3, 1

Process Need
A B C

P1 7 4 3

P2 1 2 2

P3 6 0 0

P4 0 1 1

P5 4 3 1

Hence, we created the context of need matrix.

Ans. 2: Apply the Banker's Algorithm:

Available Resources of A, B and C are 3, 3, and 2.

Now we check if each type of resource request is available for each process.

Step 1: For Process P1:

Need <= Available

7, 4, 3 <= 3, 3, 2 condition is false.

So, we examine another process, P2.

Step 2: For Process P2:

Need <= Available

1, 2, 2 <= 3, 3, 2 condition true

New available = available + Allocation

(3, 3, 2) + (2, 0, 0) => 5, 3, 2

Similarly, we examine another process P3.

Step 3: For Process P3:

P3 Need <= Available

6, 0, 0 < = 5, 3, 2 condition is false.

Similarly, we examine another process, P4.

Step 4: For Process P4:

P4 Need <= Available

0, 1, 1 <= 5, 3, 2 condition is true

New Available resource = Available + Allocation

5, 3, 2 + 2, 1, 1 => 7, 4, 3

Similarly, we examine another process P5.

Step 5: For Process P5:

P5 Need <= Available

4, 3, 1 <= 7, 4, 3 condition is true

New available resource = Available + Allocation

7, 4, 3 + 0, 0, 2 => 7, 4, 5

Now, we again examine each type of resource request for processes P1 and P3.

Step 6: For Process P1:

P1 Need <= Available

7, 4, 3 <= 7, 4, 5 condition is true

New Available Resource = Available + Allocation

7, 4, 5 + 0, 1, 0 => 7, 5, 5

So, we examine another process P2.

Step 7: For Process P3:

P3 Need <= Available

6, 0, 0 <= 7, 5, 5 condition is true

New Available Resource = Available + Allocation

7, 5, 5 + 3, 0, 2 => 10, 5, 7

Hence, we execute the banker's algorithm to find the safe state and the safe sequence like P2, P4,
P5, P1 and P3.

Ans. 3: For granting the Request (1, 0, 2), first we have to check that Request <= Available, that is (1,
0, 2) <= (3, 3, 2), since the condition is true. So the process P1 gets the request immediately.