1. Introduction

Banker’s Algorithm is the most widely studied and important deadlock avoidance algorithm in operating systems. It was proposed by Edsger W. Dijkstra and is designed to ensure that the system never enters a deadlock state.

Unlike deadlock prevention, which permanently restricts resource allocation patterns, Banker’s Algorithm dynamically evaluates every resource request before granting it.

The algorithm works on a simple principle:

A resource request is granted only if doing so keeps the system in a safe state.

If granting a request would move the system into an unsafe state, the request is postponed until sufficient resources become available.

The name "Banker’s Algorithm" comes from the analogy of a banker who loans money only when it can guarantee that all customers can eventually be satisfied without causing insolvency.

2. Motivation

Consider a system where multiple processes compete for limited resources.

If resources are allocated carelessly:

Processes Obtain Resources
          ↓
Resources Become Exhausted
          ↓
Processes Wait For Each Other
          ↓
Deadlock

To prevent this situation, the operating system must predict whether a resource allocation decision could eventually lead to deadlock.

Banker’s Algorithm performs exactly this prediction.

3. Core Idea

Before allocating resources, the operating system asks:

"If I grant this request,
will the system remain safe?"

Possible outcomes:

Safe State
     ↓
Grant Request

or

Unsafe State
     ↓
Deny / Delay Request

Thus, the algorithm continuously keeps the system within the set of safe states.

4. Fundamental Concepts

Understanding Banker’s Algorithm requires understanding three important concepts:

• Safe State

• Safe Sequence

• Unsafe State

4.1 Safe State

A system is said to be in a safe state if there exists at least one order in which all processes can complete successfully.

Formally:

A state is safe if the operating system can find a sequence of process execution that guarantees completion of every process.

Safe states guarantee:

No Deadlock

4.2 Safe Sequence

A safe sequence is an ordering of processes such that each process can obtain all resources it needs, execute, release its resources, and allow the next process to proceed.

Example:

P2 → P1 → P3

Interpretation:

• P2 finishes first

• Releases resources

• P1 finishes next

• Releases resources

• P3 finishes last

All processes complete successfully.

Therefore:

Safe Sequence Exists
        ↓
Safe State

4.3 Unsafe State

A system is in an unsafe state when no guaranteed safe sequence exists.

Important:

Unsafe State ≠ Deadlock

An unsafe state simply means:

Deadlock May Occur

The system has entered a dangerous region where future allocations may lead to deadlock.

Visualization:

Safe State
     ↓
Unsafe State
     ↓
Possible Deadlock

5. Banker's Algorithm Analogy

Imagine a bank.

The bank has:

Limited Money

Customers request loans.

Before granting a loan, the bank checks:

Can Every Customer
Still Be Satisfied Later?

If yes:

Loan Approved

If no:

Loan Denied

The operating system behaves similarly with resources.

6. Assumptions of Banker’s Algorithm

The algorithm assumes:

Fixed Number of Processes

The number of processes is known.

Fixed Resource Types

Resource types are predefined.

Maximum Requirement Known

Every process declares:

Maximum Resource Need

before execution.

Resources Are Finite

Total resources are limited.

These assumptions are necessary for safe-state analysis.

7. Data Structures Used

Banker’s Algorithm maintains four important data structures.

7.1 Available Matrix

Represents currently available resources.

Example:

Available = [3, 2, 1]

Meaning:

3 instances of Resource A
2 instances of Resource B
1 instance of Resource C

are available.

7.2 Max Matrix

Represents maximum demand of each process.

Example:

Interpretation:

P1 may need at most:

7A, 5B, 3C

during execution.

7.3 Allocation Matrix

Represents resources currently allocated.

Example:

Meaning:

P1 currently holds:

1 instance of B

P2 currently holds:

2 instances of A

7.4 Need Matrix

Need represents remaining resource requirements.

Formula:

Example:

Max = 7
Allocation = 3

Then:

Need = 4

This indicates:

Process Still Requires 4 More Resources

to complete.

8. Safety Algorithm

The Safety Algorithm determines whether the current system state is safe.

This is the heart of Banker’s Algorithm.

8.1 Objective

Determine:

Does A Safe Sequence Exist?

If yes:

System Is Safe

Otherwise:

System Is Unsafe

8.2 Variables Used

Work

Temporary copy of Available.

Work = Available

Finish[i]

Tracks completion status.

Initially:

Finish[i] = False

for all processes.

8.3 Steps of Safety Algorithm

Step 1

Initialize:

Work = Available

Finish[i] = False

Step 2

Find process i satisfying:

Finish[i] = False

and

Need[i] ≤ Work

Meaning:

The process can obtain all remaining resources.

Step 3

Pretend process finishes.

Release resources:

Work = Work + Allocation[i]

Mark:

Finish[i] = True

Step 4

Repeat Step 2.

Step 5

If all processes become:

Finish = True

then:

Safe State

Otherwise:

Unsafe State

9. Example of Safety Check

Suppose:

Available = [3]

Processes:

P1 Need = 2

P2 Need = 1

Current Work:

Work = 3

Check:

P2 Need = 1 ≤ 3

P2 finishes.

Resources returned:

Work increases

Now:

P1 Need = 2 ≤ Work

P1 finishes.

Safe sequence:

P2 → P1

Therefore:

System Is Safe

10. Resource Request Algorithm

The Safety Algorithm only checks safety.

The Resource Request Algorithm decides whether a request should be granted.

10.1 Step 1 – Validate Request

Check:

Request ≤ Need

If not:

Error

because the process is requesting more than its declared maximum.

10.2 Step 2 – Check Availability

Verify:

Request ≤ Available

If not:

Process Waits

until resources become available.

10.3 Step 3 – Pretend Allocation

Temporarily allocate resources.

Update:

Available = Available - Request

Allocation = Allocation + Request

Need = Need - Request

10.4 Step 4 – Run Safety Algorithm

Check safety.

If:

Safe

then:

Grant Request

If:

Unsafe

then:

Rollback Allocation

and deny request.

11. Why Banker’s Algorithm Works

The algorithm never allows the system to enter an unsafe state.

Therefore:

Unsafe State Never Reached

which implies:

Deadlock Never Occurs

This guarantee is the primary strength of Banker’s Algorithm.

12. Advantages

Deadlock Avoidance

Guarantees deadlock-free execution.

Better Resource Utilization

More flexible than prevention methods.

Dynamic Decision Making

Evaluates each request individually.

Supports Multiple Resource Types

Can handle complex allocation scenarios.

13. Disadvantages

Maximum Demand Must Be Known

Processes must declare future needs.

Many real-world systems cannot do this accurately.

High Computational Overhead

Safety checks must be performed frequently.

Difficult for Dynamic Systems

Processes and resource requirements often change.

Scalability Issues

Large systems require significant computation.

14. Comparison with Other Deadlock Methods

15. Banker’s Algorithm vs Deadlock Prevention

16. Real-World Example

Consider a bank with:

₹10 Lakhs Total Capital

Customers:

Customer A may need ₹4 Lakhs
Customer B may need ₹3 Lakhs
Customer C may need ₹5 Lakhs

Before approving a new loan:

Bank Simulates Future Outcomes

If every customer can eventually receive their money:

Approve Loan

Otherwise:

Reject Loan

This is precisely how Banker’s Algorithm allocates resources.