Banker’s Algorithm

 

Banker’s Algorithm 


The resource-allocation graph algorithm works only when each resource type has one instance.

When there are multiple instances of each resource type, we use the Banker’s Algorithm for deadlock avoidance.

It is called the Banker’s Algorithm because:

Just like a banker gives loans only if he is sure he can satisfy all customers eventually, the OS allocates resources only if it guarantees no deadlock will occur.

Basic Idea

When a thread (process) enters the system:

  • It must declare its maximum resource requirement.

  • The system will grant a request only if the system remains in a safe state after allocation.

If granting a request makes the system unsafe → the thread must wait.

Important Data Structures

Suppose:

  • n = number of threads

  • m = number of resource types

We maintain:

Available (Vector of size m)

Available[j] = number of free instances of resource type Rj

Example:
If Available = (3,3,2)

That means:

  • 3 instances of A are free

  • 3 instances of B are free

  • 2 instances of C are free

 Max (n × m Matrix)

Max[i][j] = maximum demand of thread Ti for resource Rj

This is declared before execution starts.

 Allocation (n × m Matrix)

Allocation[i][j] = number of resources of type Rj currently allocated to Ti

Need (n × m Matrix)

Need[i][j] = Max[i][j] − Allocation[i][j]

It represents how many more resources a thread may still request.

Safe State Concept

A system is in a safe state if:

There exists a sequence of threads such that each thread can finish with currently available resources plus resources released by previous threads.

If such a sequence exists → Safe state
If not → Unsafe state (may lead to deadlock)

Safety Algorithm (To Check Safe State)

We can now present the algorithm for finding out whether or not a system is in a safe state. This algorithm can be described as follows:

  1. Let Work and Finish be vectors of length m and n, respectively. Initialize Work = Available and Finish[i] = false for i = 0, 1, ..., n − 1.

  2. Find an index i such that both
    a. Finish[i] == false
    b. Needi ≤ Work
    If no such i exists, go to step 4.

  3. Work = Work + Allocationi
    Finish[i] = true
    Go to step 2.

  4. If Finish[i] == true for all i, then the system is in a safe state.

Explanation

Step 1: Initialization

Let:

  • Work = vector of length m

  • Finish = vector of length n

Initialize:

Work = Available
Finish[i] = false   for i = 0, 1, 2, ..., n − 1

Step 2: Find a Suitable Thread

Find an index i such that:

  1. Finish[i] == false

  2. Need[i] ≤ Work

If no such i exists, go to Step 4.

Step 3: Pretend Thread i Finishes

If such an i is found:

Work = Work + Allocation[i]
Finish[i] = true

Then go back to Step 2.

Step 4: Check Final Condition

If:

Finish[i] == true  for all i

Then:

✅ The system is in a safe state

Otherwise:

❌ The system is in an unsafe state

Time Complexity

The safety algorithm may require:

O(m×n2)O(m \times n^2)

Where:

  • m = number of resource types

  • n = number of threads

Resource-Request Algorithm

1.If Requestᵢ ≤ Needᵢ, go to step 2. Otherwise, raise an error condition, since the thread has exceeded its maximum claim.
2.If Requestᵢ ≤ Available, go to step 3. Otherwise, Tᵢ must wait, since the resources are not available.

3.Have the system pretend to have allocated the requested resources to thread Tᵢ by modifying the state as follows:

    Available = Available − Requestᵢ
    Allocationᵢ = Allocationᵢ + Requestᵢ
    Needᵢ = Needᵢ − Requestᵢ

If the resulting resource-allocation state is safe, the transaction is completed, and thread Tᵢ is allocated its resources. However, if the new state is unsafe, then Tᵢ must wait for Requestᵢ, and the old resource-allocation state is restored.

Explanation

When a thread Ti requests resources:

Let:

Requesti = vector of requested resources

Step 1: Check Maximum Claim

If:

Requesti ≤ Needi

If not → error (exceeded maximum claim)

Step 2: Check Availability

If:

Requesti ≤ Available

If not → thread must wait.

Step 3: Pretend Allocation

Temporarily update:

Available = Available − Requesti
Allocationi = Allocationi + Requesti
Needi = Needi − Requesti

Then run Safety Algorithm.

  • If safe → grant request.

  • If unsafe → rollback changes and make thread wait.

Example 

Consider a system with five threads T0 through T4 and three resource types A, B, and C. Resource type A has ten instances, resource type B has five instances, and resource type C has seven instances. Suppose that the following snapshot represents the current state of the system:

System:

  • 5 Threads: T0–T4

  • 3 Resource types: A (10), B (5), C (7)

Available = (3,3,2)



Need matrix:

ThreadAB    C
T0    7    4    3
T1    12    2
T2    60    0
T3    01    1
T4        43    1

Safe sequence:

<T1, T3, T4, T2, T0>

So system is safe.

If T1 requests:

Request1 = (1,0,2)

Check:

  • (1,0,2) ≤ (3,3,2) ✅

  • Pretend allocation

  • Run safety algorithm

  • New safe sequence exists

So request is granted and we arrive at the following new state

We must determine whether this new system state is safe. To do so, we execute our safety algorithm and find that the sequence <T1, T3, T4, T0, T2> satisfies the safety requirement. Hence, we can immediately grant the request of thread T1.

You should be able to see, however, that when the system is in this state, a request for (3,3,0) by T4 cannot be granted, since the resources are not available. Furthermore, a request for (0,2,0) by T0 cannot be granted, even though the resources are available, since the resulting state is unsafe.

Why It Works

The algorithm ensures:

  • The system never enters a deadlock state.

  • Every allocation guarantees at least one safe sequence.

Time Complexity

Safety algorithm may require:

O(m × n²)

Where:

  • m = number of resource types

  • n = number of threads

Key Points for Exams

✔ Used for multiple instances of resources
✔ Avoids deadlock (does NOT detect it)
✔ Requires advance knowledge of maximum need
✔ Uses:

  • Available

  • Max

  • Allocation

  • Need
    ✔ Uses safety algorithm before granting request

Comments

Post a Comment

Popular posts from this blog

Operating Systems OS PCCST403 Semester 4 BTech KTU CS 2024 Scheme

 About Me Scheme and Syllabus Module-1 Introduction and CPU Scheduling Introduction to OS - 3 important pieces- virtualization, concurrency, persistence Operating System Services Operating System and Kernel Linux Versus Classic Unix Kernels Difference between Linux and Unix Kernels Process and Process Creation- overview Process States in Operating System Data Structures in Operating Systems Key Aspects of a Program and Process in an Operating System-Summary Sharing the Processor Among Processes System Boot Sequence Threads and Concurrency Case Study: Linux Kernel Process management Case Study: Linux Implementation of Threads CPU Scheduling Multi-level feedback Queue ( MLFQ) Scheduler How MLFQ Approximates Shortest Job First (SJF) I/O in MLFQ Problems With the Basic MLFQ Scheduler Solving the Issues with MLFQ Scheduler Case Study: Linux Completely Fair Scheduler (CFS) Module-2 Concurrency and Synchronization Tools Concurrency and Synchronization- Basic principles Critical secti...
Read more

Introduction to Operating System -Virtualization, Concurrency, and Persistence

  How Operating Systems Really Work: Virtualization, Concurrency, and Persistence Have you ever wondered how your laptop can play music, run a web browser, download files, and open a Word document—all at the same time—without melting down? It might look simple, but beneath the surface, your operating system (OS) is doing incredibly sophisticated work. In this , we’ll break down the three most important ideas that make modern operating systems possible: Virtualization Concurrency Persistence These concepts are the foundation of how computers manage programs(applications), memory, and data.  1. Virtualization: Making One Computer Look Like Many Virtualization is all about creating useful illusions . You might have Spotify playing, Instagram open, and a browser loading—all on one phone. It feels like all apps run simultaneously, but the phone is rapidly switching between them so smoothly you don’t notice. Virtualization = making one CPU appear like many. Ev...
Read more

Differences Between Linux and Classic UNIX Kernels

  Differences Between Linux and Classic UNIX Kernels Although Linux and classic UNIX kernels share a common heritage and a similar system-call interface, Linux introduces several important design improvements that distinguish it from traditional UNIX systems. 1. Dynamic Kernel Modules Linux supports dynamic loading and unloading of kernel modules at runtime. Even though Linux is a monolithic kernel , new functionality (such as device drivers) can be added without rebooting. Classic UNIX kernels are mostly static , requiring recompilation and reboot for changes. 2. Symmetric Multiprocessing (SMP) Support Linux has strong SMP support , allowing efficient use of multiple CPUs. Traditional UNIX implementations had limited or no SMP support. Many modern UNIX variants added SMP later, but Linux was designed with scalability in mind. 3. Kernel Preemption The Linux kernel is fully preemptive , meaning a running kernel task can be interrupted to improve r...
Read more