PadhaikoAll subjects

Classical problems of synchronization: Readers-writers problem…

Operating System (ENCT 254)

Open in the Padhaiko app

3.4 Classical problems of synchronization: Readers-writers problem, producer-consumer problem, dining philosopher problem

Operating system designers validate synchronization primitives against three canonical coordination problems: the Producer-Consumer (Bounded-Buffer) Problem, the Readers-Writers Problem, and the Dining Philosophers Problem.


1. The Producer-Consumer (Bounded-Buffer) Problem

Definition

Producer-Consumer (Bounded-Buffer) Problem

Two processes share a common, fixed-size buffer capable of holding items:

Synchronization Constraints:

  1. Buffer Overflow Prevention: If the buffer is completely full (), the producer must go to sleep until the consumer removes at least one item.
  2. Buffer Underflow Prevention: If the buffer is completely empty (), the consumer must go to sleep until the producer inserts at least one item.
  3. Mutual Exclusion: The producer and consumer must never manipulate the shared buffer pointers or counter simultaneously.

Fatal Race Condition with Unprotected sleep() and wakeup()

Consider a naive implementation using an unprotected shared integer count (initially 0):

Producer-Consumer with a Fatal Lost-Wakeup Race ConditionC
#define N 100
int count = 0;

void producer(void) {                   void consumer(void) {
    int item;                               int item;
    while (TRUE) {                          while (TRUE) {
        item = produce_item();                  if (count == 0)
        if (count == N)                             sleep();
            sleep();                            item = remove_item();
        insert_item(item);                      count = count - 1;
        count = count + 1;                      if (count == N - 1)
        if (count == 1)                             wakeup(producer);
            wakeup(consumer);                   consume_item(item);
    }                                       }
}                                       }

Deadlock-Free Solution Using Three Semaphores

To eliminate both the lost-wakeup problem and simultaneous buffer access, three semaphores are used (OS Ch3):

Producer-Consumer Solution Using SemaphoresC
#define N 100
typedef int semaphore;

semaphore S = 1;    /* Binary semaphore (mutex) controlling access to CR */
semaphore E = N;    /* Counting semaphore: number of empty buffer slots */
semaphore F = 0;    /* Counting semaphore: number of full buffer slots */

void producer(void) {
    int item;
    while (TRUE) {
        item = produce_item();
        wait(E);                /* Decrement empty count (sleep if E == 0) */
        wait(S);                /* Enter critical region */
        insert_item(item);      /* Put new item in buffer */
        signal(S);              /* Leave critical region */
        signal(F);              /* Increment count of full slots */
    }
}

void consumer(void) {
    int item;
    while (TRUE) {
        wait(F);                /* Decrement full count (sleep if F == 0) */
        wait(S);                /* Enter critical region */
        item = remove_item();   /* Take item from buffer */
        signal(S);              /* Leave critical region */
        signal(E);              /* Increment count of empty slots */
        consume_item(item);
    }
}

2. The Readers-Writers Problem

Definition

Readers-Writers Problem (Courtois et al., 1971)

The Readers-Writers problem models concurrent access to a shared database or file by two classes of processes:

Semaphore Solution (First Readers-Writers / Reader-Preference)

The solution uses two binary semaphores and one shared integer counter (OS Ch3):

Readers-Writers Problem Solution Using SemaphoresC
typedef int semaphore;

semaphore s = 1;            /* Controls mutually exclusive access to rc */
semaphore write = 1;        /* Controls exclusive access to the database */
int rc = 0;                 /* Number of processes currently reading */

void reader(void) {
    while (TRUE) {
        wait(s);                /* Get exclusive access to rc */
        rc = rc + 1;            /* One more active reader */
        if (rc == 1)
            wait(write);        /* First reader locks out writers */
        signal(s);              /* Release exclusive access to rc */

        read_data_base();       /* Concurrent reading allowed here! */

        wait(s);                /* Get exclusive access to rc */
        rc = rc - 1;            /* One fewer active reader */
        if (rc == 0)
            signal(write);      /* Last reader unlocks writers */
        signal(s);              /* Release exclusive access to rc */

        use_data_read();        /* Non-critical region */
    }
}

void writer(void) {
    while (TRUE) {
        think_up_data();        /* Non-critical region */
        wait(write);            /* Request exclusive access to database */
        write_data_base();      /* Update the database */
        signal(write);          /* Release exclusive access */
    }
}

3. The Dining Philosophers Problem

Definition

Dining Philosophers Problem (Dijkstra, 1965)

Five philosophers () sit around a circular table, alternating between thinking and eating spaghetti. Between each adjacent pair of plates lies a single fork ( forks in total). To eat, a philosopher must acquire both her left fork and her right fork .

Why the Naive Solution Deadlocks

Suppose each fork is represented by a semaphore and every philosopher executes:

take_fork(i);               /* Pick up left fork */
take_fork((i + 1) % N);     /* Pick up right fork */
eat();
put_fork(i);
put_fork((i + 1) % N);

If all philosophers become hungry at the same instant and each picks up her left fork i simultaneously, all forks are now held and every philosopher blocks forever waiting for her right fork (i + 1) % 5—a classic circular-wait deadlock. (If modified so philosophers put down their left fork and retry after a fixed delay, all may repeatedly pick up and put down their forks in lockstep without anyone eating—a condition called livelock or starvation.)

Tanenbaum's Deadlock-Free Semaphore Solution

To guarantee both deadlock freedom and maximum parallelism (allowing two non-adjacent philosophers to eat simultaneously), we track each philosopher's state in an array state[N] (THINKING = 0, HUNGRY = 1, EATING = 2), protect state transitions with a binary semaphore s = 1, and assign one blocking semaphore p[i] (initialized to 0) per philosopher (OS Ch3):

Deadlock-Free Dining Philosophers Solution Using SemaphoresC
#define N        5                  /* Number of philosophers */
#define LEFT     ((i + N - 1) % N)  /* Index of i's left neighbor */
#define RIGHT    ((i + 1) % N)      /* Index of i's right neighbor */
#define THINKING 0                  /* Philosopher is thinking */
#define HUNGRY   1                  /* Trying to acquire forks */
#define EATING   2                  /* Philosopher is eating */

typedef int semaphore;
int state[N];                       /* Tracks everyone's current state */
semaphore s = 1;                    /* Mutual exclusion for state[] updates */
semaphore p[N];                     /* One semaphore per philosopher (init 0) */

void philosopher(int i) {           /* i: philosopher number 0 to N-1 */
    while (TRUE) {
        think();
        take_forks(i);              /* Acquire both forks or block */
        eat();
        put_forks(i);               /* Put both forks back and wake neighbors */
    }
}

void take_forks(int i) {
    wait(s);                        /* Enter critical region */
    state[i] = HUNGRY;              /* Record that philosopher i is hungry */
    test(i);                        /* Try to acquire both forks */
    signal(s);                      /* Exit critical region */
    wait(p[i]);                     /* Block if forks were not acquired */
}

void put_forks(int i) {
    wait(s);                        /* Enter critical region */
    state[i] = THINKING;            /* Philosopher has finished eating */
    test(LEFT);                     /* Check if left neighbor can now eat */
    test(RIGHT);                    /* Check if right neighbor can now eat */
    signal(s);                      /* Exit critical region */
}

void test(int i) {
    if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
        state[i] = EATING;
        signal(p[i]);               /* Allow philosopher i to proceed */
    }
}

3.5 Deadlock: Prevention, ignorance, avoidance, detection and recovery

Definition

Deadlock

A set of processes is in a deadlock state when every process in the set is blocked waiting for an event (the release of a resource) that can only be caused by another blocked process in the same set. Because none of the deadlocked processes can run, none of them can release any resources or be awakened.

Processes utilize resources (CPU cycles, memory space, I/O devices, files) in a strict three-phase sequence: Request Use Release.

Four Necessary Conditions for Deadlock (Coffman Conditions)

A deadlock can occur in a system if and only if all four of the following conditions hold simultaneously (OS Ch3):

Four Necessary (Coffman) Conditions for Deadlock
ConditionFormal RequirementConcrete Example
1. Mutual ExclusionAt least one resource must be held in a non-sharable (exclusive) mode; only one process can use the resource at a time.A physical printer or a write-locked database record allocated exclusively to .
2. Hold and WaitA process must currently be holding at least one resource while simultaneously requesting and waiting for additional resources held by other processes. holds Resource_1 (scanner) and requests Resource_2 (printer) held by .
3. No PreemptionResources already allocated to a process cannot be forcibly taken away; they can only be released voluntarily by the holding process after it finishes its task.Halfway through printing a document, the printer cannot be preempted without corrupting the output.
4. Circular WaitA closed directed chain of processes exists such that waits for a resource held by , waits for , , and waits for a resource held by . holds and waits for , while holds and waits for .

Operating systems handle deadlocks using four strategies:

  1. Deadlock Ignorance (Ostrich Algorithm)
  2. Deadlock Prevention
  3. Deadlock Avoidance
  4. Deadlock Detection and Recovery

1. Deadlock Ignorance (The Ostrich Algorithm)

Definition

The Ostrich Algorithm

The Ostrich Algorithm is the strategy of ignoring potential deadlocks altogether—"sticking one's head in the sand and pretending there is no problem."


2. Deadlock Prevention

Deadlock prevention structurally constrains how processes request resources so that at least one of the four Coffman conditions can never hold (OS Ch3):

Deadlock Prevention by Attacking Each Coffman Condition
Condition AttackedPrevention StrategyPracticality & Drawbacks
1. Mutual ExclusionConvert exclusive access into virtual shared access using spooling (e.g., printer daemon spools files to disk so no user process locks the physical printer).Not always possible: many resources (e.g., write-locked files, process table slots) are intrinsically non-sharable.
2. Hold and WaitProtocol A: Require a process to request and be allocated all its required resources before it begins execution. Protocol B: Require a process to release all currently held resources before requesting a new set of resources.Low resource utilization (resources sit idle for long periods) and potential starvation for processes needing many popular resources.
3. No PreemptionIf a process holding resources requests another resource that cannot be immediately allocated, implicitly preempt (release) all resources currently held by that process and add them to the list of resources for which it is waiting.Applicable only to resources whose state can be easily saved and restored (e.g., CPU registers, memory pages), not to I/O devices like printers or tape drives.
4. Circular WaitAssign a global numerical index to every resource type () and require every process to request resources in strictly increasing (or decreasing) numerical order. To request , a process must first release all with .Most practical prevention technique! If every process acquires locks in ascending order (), a cycle in the wait graph is mathematically impossible.

3. Deadlock Avoidance

Rather than imposing rigid structural rules upfront, deadlock avoidance dynamically examines every resource request at runtime using advance knowledge of each process's maximum resource claim, granting a request only if the resulting system state is safe (OS Ch3).

Safe State vs. Unsafe State

Definition

Safe State, Safe Sequence, and Unsafe State

Single-Resource Avoidance Trace (OS Ch3)

Suppose a system has instances of a single resource type shared among three processes :

Is this state safe?

  1. needs (cannot be satisfied yet), and needs , but needs . Allocate instances to (). When finishes, it releases all instances: (or ).
  2. Now needs . Allocate instances to (). When finishes, it releases all instances: .
  3. Finally, needs . Allocate instances to (). When finishes, it releases all instances: .

Because all processes finish in the order , the state is safe.

Banker's Algorithm (Dijkstra) for Multiple Resource Types

For a system with processes and resource types, the Banker's Algorithm maintains four data structures (OS Ch3):

Theorem

Banker's Safety and Resource-Request Algorithms

Part A — Safety Algorithm (Testing whether a state is safe):

  1. Let Work and Finish be vectors of length and respectively. Initialize:
  1. Find an index such that both conditions hold:

If no such exists, proceed to the final check.

  1. Simulate completion of process :

Append to the safe sequence and repeat from the search step.

  1. Final Check: If for all , the system is in a safe state. Otherwise, the state is unsafe.

Part B — Resource-Request Algorithm (When process requests vector ):

  1. Verify . If not, raise an error (process exceeded its maximum declared claim).
  2. Verify . If not, must wait (resources are not currently available).
  3. Pretend to allocate the requested resources to by modifying the state tentatively:
  1. Run the Safety Algorithm on the tentative state. If the resulting state is safe, grant the resources permanently; if unsafe, restore the original state and make wait.

4. Deadlock Detection and Recovery

If a system does not employ deadlock prevention or avoidance, it must provide a deadlock detection algorithm and a recovery mechanism (OS Ch3).

Detection for a Single Instance of Each Resource Type

  1. Resource Allocation Graph (RAG): A directed bipartite graph with two node types—Process nodes (circles ) and Resource nodes (rectangles with one dot per instance)—and two edge types:
    • Request Edge (): Directed from process to resource , meaning is currently requesting an instance of .
    • Assignment / Allocation Edge (): Directed from resource to process , meaning an instance of is currently allocated to .
  2. Wait-For Graph (WFG): Obtained from a single-instance RAG by collapsing resource nodes: an edge exists in the Wait-For Graph if and only if and in the RAG ( is waiting for to release ).
Cycle Rule in Resource Allocation Graphs
Graph ConditionSingle Instance per Resource TypeMultiple Instances per Resource Type
No cycle in RAGNo deadlockNo deadlock
Cycle exists in RAG / WFGDeadlock definitely exists (necessary and sufficient)Deadlock may exist (necessary, but not sufficient)

Detection for Multiple Instances of Each Resource Type

When resources have multiple instances, a cycle in the RAG is no longer sufficient to prove deadlock. Instead, we run a variant of Banker's algorithm that uses each process's actual current Request[n][m] matrix in place of Need[n][m]:

  1. Initialize . For each process , if , set ; otherwise set .
  2. Repeatedly find an unfinished process with , set and .
  3. When no more processes satisfy , any process with is deadlocked.

Recovery from Deadlock

Once deadlock is detected, the OS breaks the deadlock using one of three recovery strategies (OS Ch3):

  1. Recovery through Preemption: Temporarily take a resource away from its current owner and give it to another process so the second process can finish and release all its resources. Depends heavily on whether the resource's state can be cleanly saved and restored.
  2. Recovery through Rollback (Checkpointing): Periodically checkpoint each process's state (memory image and resource list) to disk. When a deadlock is detected, roll a deadlocked process back to an earlier checkpoint taken before it acquired the contested resource, and reassign the freed resource to another deadlocked process.
  3. Recovery through Killing Processes: The simplest and crudest approach—abort one or more processes in the cycle (or kill a process outside the cycle that holds a resource a deadlocked process needs). Prefer killing processes that can be rerun from the beginning with no ill effects (e.g., a compilation pass rather than a database update).

Worked Out Examples

Example 3.1

3.1

Consider a system with processes () and resource types () with the following snapshot (OS Ch3, Example 1):

ProcessAllocation ()Max ()Available ()

Answer the following using the Banker's Algorithm:

  1. Compute the Need matrix.
  2. Is the system in a safe state? If so, show a step-by-step safe execution sequence.
  3. If a request from process arrives for , can it be granted immediately?

Part 1 — Computing the Need Matrix (): Subtracting Allocation from Max row by row:

Process

Part 2 — Running the Safety Algorithm: Initialize and :

  • Check : executes and releases :
  • Check : (since and ), so must wait.
  • Check : executes and releases :
  • Check : executes and releases :
  • Check : executes and releases :
  • Re-check : executes and releases :

Since all five processes complete, the system is in a safe state with safe sequence .

Part 3 — Evaluating Request from :

  1. Check : holds true.
  2. Check : holds true.
  3. Tentative Allocation:
  4. Safety Check on Tentative State: Starting from :
    • () runs .
    • () runs .
    • () runs .
    • () runs .
    • () runs . A safe sequence (or ) still exists, so the request can be granted immediately.
Answer:
  1. Need Matrix: , , , , .
  2. Safe State: Yes, the system is in a safe state with safe sequence .
  3. Request by : Yes, it can be granted immediately because , , and the resulting state with remains safe.
Example 3.2

3.2

Consider a system with concurrent processes () and resource types (). The total number of instances of each resource type in the system is respectively (OS Ch3, Example 2):

ProcessAllocation ()Maximum Claim ()

Compute the Available vector and Need matrix, determine whether the state is safe, and show the safe execution sequence.

Computing the Available Vector: First sum the allocated instances across all processes:

Subtracting from the total system resources :

Computing the Need Matrix ():

  • :
  • :
  • :
  • :
  • :

Tracing the Safety Algorithm: Starting with :

  1. needs and needs .
  2. executes: releases :
  1. executes: releases :
  1. executes: releases :
  1. executes: releases :
  1. executes: releases :
Answer:
  • Available Vector: .
  • Need Matrix: , , , , .
  • Safe State: Yes, the system is in a safe state with safe execution sequence .
Example 3.3

3.3

Consider a system with processes through and resource types ( instances), ( instances), and ( instances). At time , the system has the following Allocation and Request matrices (OS Ch3, Example 3):

ProcessAllocation ()Request ()Available ()
  1. Is the system currently in a deadlocked state at ?
  2. Suppose process makes an additional request of . What will be the effect of this request on the system?

Part 1 — Running the Deadlock Detection Algorithm at : Initialize and :

  1. runs: finishes and releases :
  1. runs: finishes and releases :
  1. runs: finishes and releases :
  1. runs: finishes and releases :
  1. runs: finishes and releases :

Since for all via the sequence , the system is not in a deadlocked state at .

Part 2 — Effect when makes an additional request of : Now becomes . Re-running the detection algorithm from :

  • runs: finishes and releases , so and .
  • Checking remaining processes against :
    • :
    • : (needs instance of , but are available!)
    • :
    • :

No remaining process can satisfy its request! Thus , and the system enters a deadlock consisting of processes .

Answer:
  1. At : The system is not deadlocked because the execution sequence satisfies all current requests.
  2. If requests : Only can complete (bringing to ), which is insufficient for any of . Consequently, the system enters a deadlock involving processes and .

Exercises

Practice Exercises — Classical Synchronization Problems & Deadlocks

Question 1

Explain the Producer-Consumer (Bounded-Buffer) problem. Why does a solution using sleep() and wakeup() without semaphores suffer from a fatal race condition, and how do three semaphores solve it?

Problem Description: In the Producer-Consumer problem, a producer process generates items and places them into a shared fixed-size buffer of slots, while a consumer process removes items from the buffer. The producer must block when the buffer is full (), the consumer must block when the buffer is empty (), and both must not access the buffer simultaneously.

Why Unprotected sleep() / wakeup() Fails: If the buffer is empty (count == 0), the consumer reads count == 0 and prepares to call sleep(), but a clock interrupt preempts the consumer before sleep() executes. The producer then inserts an item, increments count to 1, and calls wakeup(consumer). Because the consumer is not yet asleep, the wakeup signal is lost; the consumer subsequently resumes and calls sleep(), eventually causing both processes to sleep forever.

How Three Semaphores Solve It: Using S = 1 (binary mutex for critical section), E = N (counting empty slots), and F = 0 (counting full slots):

  • Producer executes wait(E); wait(S); insert_item(item); signal(S); signal(F);
  • Consumer executes wait(F); wait(S); item = remove_item(); signal(S); signal(E);

Because wait() and signal() are atomic and store wakeup counts in the integer values of E and F, no wakeup can ever be lost.

Answer:

The Producer-Consumer problem coordinates access to an -slot bounded buffer. Unprotected sleep()/wakeup() fails when a consumer is preempted after testing count == 0 but before calling sleep(), causing the producer's wakeup() signal to be lost. Using three atomic semaphores (S = 1 for mutual exclusion, E = N for empty slots, F = 0 for full slots) stores wakeups in semaphore counters and guarantees mutual exclusion.

Question 2

State the Dining Philosophers problem and explain why the naive approach where every philosopher picks up her left fork and then her right fork can cause deadlock. How does Tanenbaum's semaphore solution prevent deadlock?

Problem Statement and Naive Deadlock: Five philosophers sit around a circular table with forks (one between each adjacent pair). A philosopher needs both her left fork and right fork to eat. If all philosophers become hungry simultaneously and each picks up her left fork take_fork(i), all forks are held and every philosopher blocks forever waiting for her right fork—satisfying all four Coffman conditions (mutual exclusion on forks, hold-and-wait, no preemption, and circular wait).

How Tanenbaum's Semaphore Solution Prevents Deadlock: Tanenbaum's solution maintains state[5] (THINKING, HUNGRY, EATING), a mutex s = 1, and per-philosopher semaphores p[5] initialized to 0. Inside take_forks(i), protected by wait(s), philosopher sets state[i] = HUNGRY and calls test(i):

if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
    state[i] = EATING;
    signal(p[i]);
}

A philosopher acquires both forks atomically only when neither neighbor is eating; otherwise she blocks on wait(p[i]) without holding a single fork, breaking the Hold and Wait condition.

Answer:

In the Dining Philosophers problem, if all philosophers pick up their left fork simultaneously, a circular-wait deadlock occurs as each waits for her right fork. Tanenbaum's solution prevents deadlock by testing both neighbors' states (state[LEFT] != EATING && state[RIGHT] != EATING) under a mutex s = 1 and transitioning to EATING (acquiring both forks together) only when both forks are available.

Question 3

List the four necessary conditions for a deadlock to occur, and explain how Deadlock Prevention eliminates each condition. Which prevention technique is most widely used in practice and why?

Four Necessary Conditions and Their Prevention:

  1. Mutual Exclusion: Resources are held exclusively. Prevention: Spool resources (e.g., printer spooler) so processes do not lock physical devices directly—though many resources cannot be made sharable.
  2. Hold and Wait: A process holds resources while waiting for more. Prevention: Require processes either to request all needed resources before starting execution, or to release all currently held resources before requesting new ones.
  3. No Preemption: Held resources cannot be forcibly taken away. Prevention: If a process holding resources requests another resource that is unavailable, implicitly preempt all its held resources.
  4. Circular Wait: A closed chain of processes each waiting for a resource held by the next. Prevention: Impose a global numerical ordering on all resources and require processes to request resources in strictly increasing order.

Most Practical Technique: Attacking Circular Wait via resource ordering is the most widely used prevention technique in practice because it does not require advance knowledge of maximum resource needs, does not waste resources through upfront allocation, and works for non-preemptable locks and devices.

Answer:

The four conditions are Mutual Exclusion (prevented where possible by spooling), Hold and Wait (prevented by all-at-once allocation or release-before-request), No Preemption (prevented by preempting held resources on a blocked request), and Circular Wait (prevented by global numerical ordering of resource requests). Numerical resource ordering is the most practical because it avoids low resource utilization and works on any resource type.

Question 4

Consider a system with processes () and resource types ( instances), ( instances), and ( instances) with the following state:

ProcessAllocation ()Max ()
  1. Find the Available vector and the Need matrix.
  2. Show that the system is in a safe state and give a safe sequence.
  3. If process requests , can the request be granted immediately?

Part 1 — Computing Available and Need: Total allocated instances .

Computing :

  • :
  • :
  • :
  • :
  • :

Part 2 — Safety Algorithm Execution: Starting with :

  1. runs: .
  2. runs: .
  3. runs: .
  4. runs: .
  5. runs: .

Thus the state is safe with safe sequence .

Part 3 — Testing 's Request :

  1. holds.
  2. holds.
  3. Tentative state:
  4. Safety check from :
    • () runs .
    • Thereafter all complete as before. Since is a valid safe sequence, the request can be granted immediately.
Answer:
  1. Available: . Need Matrix: , , , , .
  2. Safe State: Yes, with safe sequence .
  3. Request by : Yes, it can be granted immediately (tentative , safe sequence ).
Question 5

Solve the following two resource-sizing problems for deadlock avoidance:

  1. A system has processes and each process requires a maximum of instances of resource type . What is the minimum number of instances of needed to guarantee that deadlock can never occur?
  2. Three processes share a single resource type with maximum claims , , and respectively. Find the minimum total instances of so that deadlock is impossible.

Part 1 — Equal Maximum Claims (): In the worst-case deadlocked state, each of the processes holds instances (total instances) and waits for more instance. Adding just additional instance ensures at least one process can acquire its -rd instance, finish, and release its resources:

Part 2 — Unequal Maximum Claims (): In the worst case before any process can finish, holds , holds , and holds . Adding more unit guarantees completion of at least one process:

Answer:
  1. Minimum instances of for processes each needing at most units: instances.
  2. Minimum instances of for processes with maximum claims : instances.
Question 6

Explain how a Resource Allocation Graph (RAG) and a Wait-For Graph (WFG) are used to detect deadlocks. Why does a cycle in a RAG guarantee deadlock when each resource type has a single instance, but not when resource types have multiple instances?

Resource Allocation Graph (RAG) and Wait-For Graph (WFG):

  • A RAG is a directed graph with process vertices (circles) and resource vertices (rectangles). A request edge indicates is waiting for ; an allocation edge indicates an instance of is held by .
  • For single-instance resources, collapsing the resource nodes yields a Wait-For Graph (WFG) containing only process nodes, where a directed edge means is waiting for a resource currently held by .

Why a Cycle Is Sufficient for Single-Instance Resources Only:

  • Single instance per resource type: If a cycle exists, has only one instance (held by ) and has only one instance (held by ). Neither process can ever acquire the resource it needs unless the other releases it first—so a cycle is both necessary and sufficient for deadlock.
  • Multiple instances per resource type: Suppose has instances, one held by (part of a cycle ) and the second held by an independent process that is not waiting for anything. When finishes, it releases its instance of , which satisfies and breaks the cycle! Hence, with multiple instances, a cycle is a necessary condition for deadlock, not a sufficient condition.
Answer:

A Resource Allocation Graph (RAG) tracks request edges () and allocation edges (); collapsing single-instance resource nodes produces a Wait-For Graph (). When each resource has only one instance, a cycle is both necessary and sufficient for deadlock because no external process can release an instance of any resource in the cycle. When resources have multiple instances, another process outside the cycle may hold an instance and release it upon completion, breaking the cycle; thus a cycle is only necessary, not sufficient.

Past exam questions for Operating System

← Principles of concurrency, race condition, critical region · Mutual…I/O management →