Resource-Allocation-Graph Algorithm

 

Resource-Allocation-Graph Algorithm (Deadlock Avoidance)

This algorithm is used when:

✔ Each resource type has only one instance

It is a modification of the regular resource-allocation graph used for deadlock detection, but here it is used for avoidance.

Basic Idea

The goal is:

Never allow the system to enter an unsafe state.

The algorithm checks whether granting a resource request would create a cycle in the graph.

  • If granting the request creates a cycle → Unsafe → Deny request

  • If no cycle is formed → Safe → Grant request

Since each resource has only one instance:

A cycle in the graph implies unsafe state (and potential deadlock).

Types of Edges in This Algorithm

In addition to the usual edges, we introduce a new edge type.

(1) Request Edge (Ti → Rj)

Thread Ti is requesting resource Rj.

(2) Assignment Edge (Rj → Ti)

Resource Rj is allocated to thread Ti.

(3) Claim Edge (Ti → Rj) ← New Concept

  • Represented as a dashed line

  • Indicates thread Ti may request resource Rj in the future

  • Declared before execution begins

 Why Claim Edges?

Claim edges allow the system to:

✔ Know in advance which resources a thread may request
✔ Predict possible future circular waits
✔ Prevent unsafe allocations

This is the key difference between detection and avoidance.

 Important Rule

All claim edges must be declared a priori (before thread starts execution).

This means:

The system must know the maximum possible resource needs of each thread beforehand.

How the Algorithm Works

Suppose thread Ti requests resource Rj.

Step 1

Convert the claim edge (Ti → Rj) into a request edge.

Step 2

Pretend to allocate the resource:
Convert request edge to assignment edge (Rj → Ti).

Step 3

Check if a cycle is formed in the graph.

  • If no cycle → Allocation is safe → Grant request

  • If cycle forms → Unsafe → Deny request and make Ti wait

Cycle detection takes O(n²) time (n = number of threads).

Why Cycle Means Unsafe?

Since each resource has only one instance:

Cycle ⇒ Circular wait ⇒ Deadlock possible

Thus:

  • No cycle → Safe

  • Cycle → Unsafe

 Example 




Consider a graph 8.9 with:

Threads: T1, T2
Resources: R1, R2

Suppose:

  • T1 holds R1

  • T2 requests R2

  • T1 may request R2

  • T2 may request R2

Now assume:

T2 requests R2 (which is free).

Even though R2 is free:

If we allocate R2 to T2, a cycle forms: fig 8.10

T1 → R2 → T2 → R1 → T1

This cycle indicates:

If T1 later requests R2 and T2 requests R1, deadlock will occur.

Therefore:

❌ We do NOT grant R2 to T2
Even though it is currently available.

This prevents unsafe state.

Important Observations

✔ Only works when each resource has one instance
✔ Uses cycle detection
✔ Requires advance knowledge of resource usage
✔ May deny allocation even if resource is free
✔ Lower resource utilization possible

Summary 

The Resource-Allocation-Graph Avoidance Algorithm:

  • Adds claim edges to show possible future requests.

  • When a thread requests a resource:

    • Pretend to allocate it.

    • Check for cycle.

  • If cycle forms → deny request.

  • If no cycle → grant request.

The system always remains in a safe state.

📌 Core Concept to Remember 

In a single-instance system, granting a request is safe if and only if doing so does not create a cycle in the resource-allocation graph.

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