Agenda:

• Dining Philosophers Problem
• The Readers Writers Problem
• Monitors
• Deadlocks

Dining Philosophers Problem

The Dining Philosophers Problem is a classic synchronization problem that represents a fundamental issue in concurrent programming and resource sharing. The scenario is designed to showcase challenges that arise when several processes must share resources without conflict.

The problem involves five philosophers who alternate between thinking and eating. The unique challenge is that:

• The philosophers are arranged in a circular fashion around a table.
• Each philosopher has a chopstick to their left and right, which they need to eat.
• A philosopher can only eat when they have access to both adjacent chopsticks.

Problem Setup and Philosophers’ Life Cycle

The setup includes:

• Philosophers: Five philosophers (P1, P2, P3, P4, and P5) who each occupy one seat at the table.
• Table and Chopsticks: The table has a bowl of noodles in the center, with one chopstick placed between each pair of adjacent philosophers, totaling five chopsticks.

The philosophers’ life cycle consists of two states:

1. Thinking:
   • While in the thinking state, a philosopher is mentally occupied and does not require any chopsticks.
   • The philosopher is not interacting with the resources or other philosophers.
2. Eating:
   • When a philosopher gets hungry, they transition to the eating state.
   • To eat, they need both chopsticks adjacent to them (left and right).
   • A philosopher can only pick up one chopstick at a time. If a chopstick is in use by a neighboring philosopher, they must wait until it is released.

After a philosopher eats, they put down both chopsticks and resume thinking.

Initial Solution Using Semaphores

Semaphores are commonly used to manage concurrent access to resources. In the Dining Philosophers Problem, each chopstick can be represented by a binary semaphore (either available or unavailable).

Semaphore Setup

semaphore chopstick[5]; // 5 chopsticks, all initialized to 1 (indicating they're free)

Philosopher Actions

Each philosopher executes two wait operations to acquire their left and right chopsticks and two signal operations to release them when done:

do {   wait(chopstick[i]); // Acquires the left chopstick   wait(chopstick[(i+1) % 5]); // Acquires the right chopstick   // Eat   signal(chopstick[i]); // Releases the left chopstick   signal(chopstick[(i+1) % 5]); // Releases the right chopstick   // Think } while (true);

The Deadlock Problem

The semaphore-based solution can lead to deadlock, a situation where all philosophers get stuck indefinitely. Deadlock arises here because:

1. All philosophers might become hungry simultaneously.
2. Each philosopher could pick up their left chopstick first.
3. With each philosopher holding their left chopstick, no one can pick up their right chopstick, since it’s already held by their neighbour.

This scenario leads to a circular waiting condition, a primary cause of deadlock, as all philosophers end up waiting for resources (right chopsticks) that will never become available.

Deadlock Prevention in this problem

Several strategies can prevent deadlock in this problem by relaxing one or more of the deadlock conditions.

Limiting the Number of Philosophers

One straightforward solution is to allow only four philosophers to sit at the table simultaneously:

• With only four philosophers, at least one chopstick will always remain free.
• This guarantees that at least one philosopher will always be able to acquire both chopsticks, breaking the cycle of circular waiting and preventing deadlock.

Atomic Pickup of Both Chopsticks

Another approach is to ensure that a philosopher can pick up both chopsticks only if both are available simultaneously. This can be done by using a critical section for acquiring the chopsticks:

• When a philosopher wants to eat, they enter a critical section to check if both chopsticks are free.
• If both are available, the philosopher picks them up atomically. If not, the philosopher waits until both become free.

This approach prevents deadlock by ensuring that philosophers cannot hold onto one chopstick indefinitely while waiting for another.

Odd-Even Rule (Asymmetric Solution)

The odd-even rule is an asymmetric solution that breaks the circular waiting condition by altering the sequence in which philosophers pick up chopsticks:

• Odd-numbered philosophers (P1, P3, P5) pick up their left chopstick first and then their right chopstick.
• Even-numbered philosophers (P2, P4) pick up their right chopstick first and then their left chopstick.

By staggering the sequence, at least one philosopher will be able to acquire both chopsticks and start eating, thus avoiding a deadlock.

Starvation Issue and Fairness

While the above solutions help prevent deadlock, they may lead to starvation, where a philosopher could potentially be waiting indefinitely due to other philosophers continuously grabbing chopsticks before them.

To avoid starvation, we can:

• Implement a fair scheduling policy that ensures philosophers take turns eating.
• For instance, we could keep a count of how long each philosopher has been waiting to eat and prioritize them accordingly.

Ensuring that all philosophers eventually get both chopsticks in a fair and cyclic manner prevents starvation and promotes fairness.

Final Deadlock-Free Solution Outline

Combining the strategies discussed, a potential deadlock-free and starvation-free solution could look like this:

1. Apply the Odd-Even Rule:
   • Odd philosophers pick up their left chopstick first, then their right.
   • Even philosophers pick up their right chopstick first, then their left.
2. Atomic Pickup Check:
   • Philosophers can enter a critical section to ensure both chopsticks are free before picking them up.
3. Fair Scheduling:
   • A scheduling algorithm that tracks waiting time for each philosopher and allows turn-based access to the chopsticks to avoid starvation.

Example of Enhanced Solution Structure

do {   // Check if both chopsticks are available in a critical section   enter_critical_section();   if (both_chopsticks_available) {       if (philosopher_id % 2 == 0) { // Even philosopher           wait(chopstick[(i+1) % 5]); // Right chopstick first           wait(chopstick[i]);         // Left chopstick       } else { // Odd philosopher           wait(chopstick[i]);         // Left chopstick first           wait(chopstick[(i+1) % 5]); // Right chopstick       }       exit_critical_section();       // Eat       signal(chopstick[i]); // Release left chopstick       signal(chopstick[(i+1) % 5]); // Release right chopstick   } else {       exit_critical_section();       // Think or wait   } } while (true);

The Readers-Writers Problem

The Readers-Writers Problem is a classic example of a synchronization problem where we need to manage concurrent access to a shared data object. The goal is to allow multiple readers to access the shared data concurrently but to ensure that writers have exclusive access. This means that while readers can access the data simultaneously without issues, a writer must have sole access to prevent data inconsistencies.

Problem Setup

There are two types of processes:

• Readers: Processes that only read data and don’t modify it.
• Writers: Processes that both read and modify data.

Requirements

1. Multiple readers can read the data simultaneously without any adverse effects.
2. Writers require exclusive access to the data, meaning that when a writer is working on the data, no other reader or writer should access it.
3. The goal is to synchronize access to the shared data such that:
   • Readers can read concurrently.
   • Writers have priority when they need to write (depending on the specific solution).

This ensures data consistency and avoids race conditions where one process could read inconsistent or incomplete data being modified by another process.

Variants of the Readers-Writers Problem

There are two main variations of the Readers-Writers problem:

1. First Readers-Writers Problem: Prioritizes readers over writers. No reader should wait for another reader simply because a writer is waiting.
   • Consequence: Writers may starve if there are always readers trying to access the shared resource.
2. Second Readers-Writers Problem: Prioritizes writers over readers. Once a writer is waiting, no new readers are allowed access until the writer has finished.
   • Consequence: Readers may starve if there’s a constant flow of writers.

In both cases, starvation can be a problem. For instance, in the first variant, if readers keep coming in, writers might never get access to the shared resource, and vice versa in the second variant.

Solution to the First Readers-Writers Problem

We use semaphores to control access to the shared data. This solution aims to allow readers priority while still ensuring safe and mutually exclusive access for writers.

Data Structures

1. Semaphores:
   • mutex: A binary semaphore used for mutual exclusion while updating the readcount variable.
   • wrt: Another binary semaphore that provides mutual exclusion for writers, and ensures that no readers or other writers can access the data while a writer is working.
2. Shared Variable:
   • readcount: An integer that keeps track of the number of readers currently accessing the data. This helps manage the transition between readers and writers.

Initialization

• Both mutex and wrt are initialized to 1 (indicating they are available).
• readcount is initialized to 0 (since no readers are initially accessing the data).

Solution Code Explanation

Writer Process Code

The writer process code is straightforward:

do {   wait(wrt); // Requests exclusive access to the shared resource   // Critical section: writing is performed here   signal(wrt); // Releases access to the shared resource } while(1);

• wait(wrt): The writer waits to acquire wrt, ensuring no other writers or readers are accessing the shared data.
• Critical Section: The writer performs its writing operation once it has exclusive access.
• signal(wrt): After writing, the writer releases wrt, allowing other waiting processes (either readers or writers) to access the shared resource.

Reader Process Code

The reader process code is a bit more complex, as it includes logic to manage multiple readers entering and leaving the critical section:

do {   wait(mutex); // Request access to modify readcount   readcount++;   if (readcount == 1)       wait(wrt); // First reader locks the writer out   signal(mutex); // Release access to readcount   // Critical section: reading is performed here   wait(mutex); // Request access to modify readcount   readcount--;   if (readcount == 0)       signal(wrt); // Last reader releases the writer   signal(mutex); // Release access to readcount } while(1);

1. wait(mutex): Each reader must acquire mutex to modify the readcount variable.
   • This ensures that no two readers modify readcount simultaneously, preventing race conditions.
2. readcount++: The reader increments readcount to indicate another reader is accessing the data.
3. if (readcount == 1): If the current reader is the first reader, it must acquire wrt. This prevents writers from accessing the shared data while readers are in their critical section.
4. signal(mutex): The reader releases mutex after modifying readcount, allowing other readers to enter.
5. Reading Critical Section: The reader performs its read operation. Multiple readers can perform their read operations simultaneously because they don’t need exclusive access.
6. wait(mutex): After reading, each reader acquires mutex to safely modify readcount.
7. readcount--: The reader decrements readcount to indicate it is done.
8. if (readcount == 0): If the current reader is the last reader to finish reading, it releases wrt, allowing writers access.
9. signal(mutex): Finally, the reader releases mutex, allowing other readers or writers to proceed.

Possible Scenarios and Edge Cases

Reader Starvation

In the first variant, writer starvation can occur because if new readers keep arriving before the wrt semaphore is released, writers may be indefinitely blocked. The semaphore wrt could potentially remain held by readers as long as new readers continue arriving.

Mutual Exclusion Management with Semaphores

The mutual exclusion provided by mutex ensures that readcount is modified safely. Without mutex, concurrent updates to readcount could cause incorrect counts, leading to incorrect releases of wrt (e.g., a reader might think it is the last one when it isn’t).

Semaphore Usage

• mutex: Controls access to readcount, ensuring only one reader at a time modifies readcount.
• wrt: Controls access to the shared data for writers and blocks all readers while a writer is working.

Monitors

Monitors are a high-level synchronization construct in operating systems and concurrent programming, designed to control access to shared resources and avoid race conditions. They combine data encapsulation (similar to classes in object-oriented programming) with built-in synchronization, allowing only one process to be active in the monitor at any time. This helps in managing complex synchronization problems, particularly in cases where semaphores and mutexes might become complex to handle.

Components of Monitors

1. Monitor Structure: A monitor typically consists of:
   • Local variables: Only accessible within the monitor, ensuring encapsulation.
   • Procedures or Functions: Methods within the monitor that define operations to access and modify the monitor's internal state. These methods control how shared data is accessed by multiple processes.
2. Mutual Exclusion: Monitors inherently ensure that only one process can execute inside the monitor at any time. Thus, programmers do not need to explicitly write code for mutual exclusion when using monitors.
3. Condition Variables: For finer-grained control over process execution within the monitor, monitors support condition variables. Condition variables allow processes to wait or be signaled based on specific conditions in the monitor.

Condition Variables in Monitors

Condition variables in monitors allow more flexible control over process synchronization than semaphores alone.

Condition Variables Declaration: Condition variables are declared inside the monitor.

condition x, y;

• • Condition variables x and y are special types of variables that allow processes to wait for specific conditions within the monitor.
• Operations on Condition Variables:
  • Wait: If a process calls x.wait(), it is suspended (put on hold) until another process calls x.signal(). Only the process that invoked x.signal() can activate a waiting process.
  • Signal: When a process calls x.signal(), it wakes up one of the processes that is suspended on x. If no process is waiting, the signal() operation has no effect.

How Condition Variables Works

Unlike semaphores, where signal() always affects the semaphore’s state, in monitors:

1. If there is no suspended process waiting on the condition variable x, signal() does not affect the state of x.
2. If there is a suspended process waiting on x, it will be immediately resumed when signal() is called.

Below is an example to demonstrate how condition variables work in a monitor.

monitor ExampleMonitor {     int shared_data; // Some shared data variable     condition x; // Condition variable         void updateData() {         if (/* some condition is not met */) {             x.wait(); // Wait until another process signals x         }         // Perform operations on shared_data         x.signal(); // Signal other waiting processes     }     void checkData() {         if (/* some condition is met */) {             x.signal(); // Signal to wake a waiting process         }     } };

In this example:

• The updateData() function uses x.wait() to suspend execution if a certain condition isn’t met.
• The checkData() function uses x.signal() to wake up processes waiting on x, if a condition is satisfied.

Interaction Between Processes Using Condition Variables

When a process calls x.signal(), there are two choices for which process continues:

1. Hoare's Solution (Option 1): The signaling process (let’s say P) is suspended, and the waiting process (Q) is immediately resumed. Once Q finishes, P can resume execution.
   • Advantage: Guarantees that the condition that Q was waiting for is still valid when Q starts executing.
   • Disadvantage: This method can be harder to implement in some languages or systems.
2. Alternative (Option 2): The signaling process (P) continues executing, and the waiting process (Q) resumes only after P leaves the monitor.
   • Advantage: Easier to implement in most systems and avoids extra context switches.
   • Disadvantage: By the time Q resumes, the condition it was waiting for may no longer hold.

Many systems use a compromise approach, as in Concurrent C, where the waiting process (Q) is resumed immediately, but there are restrictions on repeated signaling.

Deadlocks

A deadlock is a situation in computer science where a set of processes is in a blocked state, each waiting for a resource that can only be released by another process in that set. This forms a cyclic dependency where each process is holding at least one resource while waiting for another. The critical consequence is that none of the processes can proceed, as they are all dependent on resources held by other processes in the deadlocked set. None of them can complete, release resources, or be awakened, which brings the entire system to a halt.

A deadlock occurs when a set of processes each hold resources while waiting for resources held by others in the same set, creating a cycle of dependency that prevents any process from progressing.

Competition for Finite Resources in a Multi-Programming Environment

In a multi-programming environment, there are multiple processes running concurrently, all vying for a limited set of resources. These resources could be physical (e.g., memory space, CPU cycles, input/output devices) or logical (e.g., files, locks, sockets, semaphores). Since these resources are limited, each process must wait until the resources it needs become available. However, this competition for finite resources leads to situations where processes may never complete their tasks because they are waiting indefinitely for resources held by other processes, resulting in deadlock.

Consider two processes, P1 and P2. Process P1 is holding a memory lock and needs access to a file lock that process P2 is holding. Process P2, on the other hand, needs the memory lock held by process P1 to proceed. Since neither process can release its current lock until it obtains the other, both are indefinitely stuck in a state of deadlock.

When Waiting Processes Never Get Resources

When a process requests a resource, if the resource is currently in use by another process, the requesting process enters a waiting state. Normally, this waiting process would eventually acquire the resource once it becomes available. However, in some cases, the waiting process never receives the resource because the resource is being indefinitely held by another process in a similar waiting state, thus resulting in a deadlock.

Deadlock as a Bug in Synchronization

Deadlock is a defect in the synchronization of processes or threads, arising due to poor handling of resources. In systems where multiple threads or processes are designed to share resources, proper synchronization ensures that resources are allocated, used, and released efficiently without creating circular dependencies. However, deadlocks represent a failure in this synchronization mechanism, as the processes end up in a state where they can no longer progress.

Effects of Deadlock on System Performance

When deadlock occurs, the affected processes are unable to complete their execution, resulting in a significant waste of system resources. Furthermore, the deadlock prevents other jobs from starting because the resources are tied up by the deadlocked processes. This situation can severely impact the system's overall performance, as it reduces the number of processes that can execute concurrently and may render the system unresponsive.

Examples of Resources Involved in Deadlock

Various types of resources can become involved in a deadlock situation, including:

• Memory space: Required for storing process data and code.
• CPU cycles: Essential for executing process instructions.
• Files: Needed by processes for reading and writing data.
• Locks: Used to control access to shared data or critical sections.
• Sockets: Employed in network communication between processes.
• Input/output (I/O) devices: Required for data transfer and processing tasks.

Each resource type can be uniquely allocated, or it may be shareable to a certain extent among processes. When a resource is allocated in an exclusive (non-sharable) mode, deadlocks are more likely if not managed correctly.

Multiple Instances of Resources

Some resources have multiple instances available. For example, a CPU can have multiple cores, each acting as an independent CPU instance. Processes can utilize these multiple instances, which can potentially reduce the chance of deadlock since they increase the likelihood that a waiting process can access an available instance. However, if all instances of a resource type are allocated, the possibility of deadlock remains.

How a Process Utilizes a Resource

The general process for utilizing a resource follows a standardized sequence to avoid conflicts with other processes. The sequence includes:

Request

A process first requests access to a resource it needs. If the resource is free, the process can lock it, marking it as in use. However, if the resource is already locked by another process, the requesting process enters a waiting state until the resource becomes available. This state of waiting can lead to deadlock if it results in a circular wait, where each process is waiting for a resource held by another.

Use

Once the resource is acquired, the process can perform its required operations on the resource. During this stage, the process has exclusive control of the resource (for non-sharable resources) and can carry out its tasks without interruption from other processes requesting the same resource.

Release

After using the resource, the process releases it, making it available for other processes that may be waiting. By promptly releasing resources once they are no longer needed, processes help prevent prolonged waiting states for other processes and reduce the likelihood of deadlock.

Example Scenario Illustrating Deadlock

Imagine a scenario where:

• Process A has been allocated a printer.
• Process B has been allocated a hard drive.
• Process A now requests access to the hard drive, but it is held by process B.
• Process B, in turn, needs access to the printer held by process A.

Since neither process can proceed without the other's resource, they both remain indefinitely blocked, resulting in a deadlock. This is a classic example of how improper resource allocation and synchronization can lead to a system deadlock.

Deadlock Necessary Conditions

In the context of deadlock in a multi-programming environment, four necessary conditions must hold simultaneously for deadlock to occur. These conditions are: 

1. Mutual Exclusion

The mutual exclusion condition requires that some resources can only be held by one process at a time. If a process has acquired a resource, no other process can access that resource until the first process releases it.

• Example: Imagine a printer shared by multiple processes. Only one process can use the printer at any given time. If another process needs the printer while it is already in use, the second process must wait until the printer is released.
• Relevance to Deadlock: Mutual exclusion is necessary to create deadlock because, without exclusive access, multiple processes could share resources without waiting. The need for exclusive access makes waiting inevitable when resources are limited.

For resources that are inherently non-shareable, such as files, memory locks, or certain hardware devices, mutual exclusion is unavoidable. This condition makes deadlock possible since a process waiting for a resource will have to pause until it becomes available.

2. Hold and Wait

The hold and wait condition specifies that a process must be holding at least one resource while simultaneously waiting to acquire additional resources that are held by other processes.

• Example: Suppose Process A holds a file lock and requests access to a database connection currently held by Process B. Meanwhile, Process B holds the database connection but needs the file lock held by Process A. Both processes are holding one resource and waiting for the other.
• This condition allows processes to acquire resources progressively while holding others. It contributes to deadlock because a process that holds resources while waiting can potentially block other processes from accessing those resources indefinitely.

If a process could not hold resources while waiting for additional ones, it would be forced to release any held resources before making new requests, reducing the risk of deadlock. However, allowing processes to hold resources while waiting introduces dependencies among processes, making deadlock possible.

3. No Preemption

The no-preemption condition requires that resources cannot be forcibly taken from a process. A resource can only be released voluntarily by the process that holds it, typically after the process completes its task.

• Imagine Process A holds a lock on memory and is performing a complex computation. Process B needs access to that memory but cannot force Process A to release it, even if it is waiting. Process A will release the memory only after finishing its computation.
• This condition contributes to deadlock because if a process cannot relinquish a resource until it is done, other processes that need that resource must wait indefinitely. If the waiting processes also hold other resources, a cycle of dependencies can arise.

Without preemption, resources become locked with their holding processes until released voluntarily. This locking effect makes deadlock possible. In some systems, resource preemption (forcefully taking resources from a process) is used to avoid deadlock, but it can complicate resource management and potentially lead to data inconsistencies.

4.Circular Wait

Circular wait is a condition where a set of processes are waiting on each other in a circular chain. Each process in the set holds at least one resource that the next process in the chain requires, leading to an unbreakable cycle.

• Example: Consider a set of processes {P0, P1, P2, ... , Pn} where:
  • Process P0 holds a resource that Process P1 needs,
  • Process P1 holds a resource that Process P2 needs,
  • Process P2 holds a resource that Process P3 needs, and so on,
  • Finally, Process Pn holds a resource that Process P0 needs.
• This cycle means that no process can proceed, as each is waiting for a resource held by the next process.
• Relevance to Deadlock: Circular wait is essential for deadlock because it creates a closed loop of processes, each waiting for the next, making progress impossible. The lack of any exit from this waiting cycle means that all processes are stuck indefinitely.

The circular wait condition is often targeted in deadlock prevention techniques. By ensuring that processes request resources in a specific order or by avoiding circular dependencies, systems can reduce the risk of deadlock

Resource-Allocation Graph 

A Resource-Allocation Graph (RAG) is a directed graph used to represent the allocation of resources to processes and to detect deadlocks in a system. It visually illustrates how resources are assigned to processes and which processes are waiting for resources. Understanding this graph helps in analyzing system states and identifying potential deadlocks. Here's a detailed explanation of its components and functionality, along with a specific example based on the provided information.

Components of the Resource-Allocation Graph

1. Vertices (V):
   • The set of vertices VV is divided into two types:
     • Process Nodes (P): Represents all the active processes in the system. Each process Pi​ is represented as a circle.
     • Resource Nodes (R): Represents all the resource types in the system. Each resource type Rj​ is represented as a square. If a resource type has multiple instances, these instances are depicted as dots inside the square.
2. Edges (E):
   • Request Edge (Pi → Rj): A directed edge from a process node PiPi​ to a resource node Rj​ indicates that process Pi​ is requesting an instance of resource type Rj​ and is currently waiting for it.
   • Assignment Edge (Rj → Pi): A directed edge from a resource node Rj​ to a process node Pi signifies that an instance of resource type Rj​ has been allocated to process Pi​.

Visual Representation

• Process Nodes: Represented as circles (e.g., P1,P2,P3​).
• Resource Nodes: Represented as squares (e.g., R1,R2,R3,R4​).
• Request Edges: Arrows pointing from processes to resources.
• Assignment Edges: Arrows pointing from resources to processes.

Example Breakdown:

Given Sets

• Processes: P={P1​,P2​,P3​}
• Resources:R={R1​,R2​,R3​,R4​}

Edges: E={P1→R1,P2→R3,R1→P2,R2→P2,R2→P1,R3→P3}

Resource Instances

• One instance of resource type R1
• Two instances of resource type R2
• One instance of resource type R3
• Three instances of resource type R4

Deadlock Detection

• No Cycles: If the RAG contains no cycles, it guarantees that no process is deadlocked. Each process can potentially complete its execution and release resources.
• Cycles Present: If there are cycles in the graph:
  • Single Instance Resources: If each resource type has only one instance, the presence of a cycle is both necessary and sufficient for a deadlock. This means that if there’s a cycle, all processes in that cycle are deadlocked because each one is waiting for a resource held by another in the cycle.
  • Multiple Instance Resources: If resource types have multiple instances, a cycle is a necessary condition for deadlock but not sufficient. This means that while a cycle indicates a potential deadlock, it doesn't confirm it since resources can be released or allocated in such a way that processes can continue executing.

Example Scenario

Resource Allocation Graph with a deadlock

Initial Resource Allocation

Given your initial state:

• Processes:
  • P1​: Holding R2​, waiting for R1​.
  • P2​: Holding R1​ and R2​, waiting for R3​.
  • P3​: Holding R3​, waiting for R2.

Adding a Request Edge

Now suppose P3 requests an instance of R2​:

• The new edge P3→R2​ is added.

Resulting Cycles

With the new edge, the following cycles form:

1. Cycle1: P1​→R1​→P2​→R3​→P3​→R2​→P1​
2. Cycle 2: P2→R3→P3→R2→P2

Analysis of Deadlock

In this configuration:

• Each process is waiting for a resource held by another process in the cycle, indicating that:
  • P1​ is waiting for R1​ (held by P2​).
  • P2​ is waiting for R3​ (held by P3​).
  • P3​ is waiting for R2​ (held by P1​).

Thus, all processes P1,P2 and P3​ are deadlocked.

Example Without Deadlock

Resource Allocation Graph with a Cycle but No Deadlock

Now, consider a scenario where a cycle exists but there is no deadlock. If we introduce another process P4P4​ that holds an instance of R2R2​ and can release it, we have the following:

• Current Resource State:P4​ can release its instance of R2​, which allows P3​ to acquire it, breaking the cycle:
  • P4​ releases R2​ → P3​ gets R2​ → Now P3​ can complete its execution and release its resources.

In this scenario, even with the cycle present, deadlock does not occur because resources can be freed, allowing processes to complete.

Methods of Handling Deadlock

Deadlock Prevention

Deadlock prevention aims to ensure that at least one of the necessary conditions for a deadlock cannot hold in a system. The classic conditions for deadlocks are Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait. By addressing each of these conditions, we can effectively prevent deadlocks from occurring.

1. Elimination of the Mutual Exclusion Condition

• The mutual exclusion condition states that at least one resource must be held in a non-sharable mode; that is, only one process can use the resource at any given time. If another process requests that resource, it must be delayed until the resource is released.
• Challenges:
  • Some resources, like printers or hard drives, are inherently non-shareable and require mutual exclusion.
  • Shareable resources, like read-only files, do not involve mutual exclusion since multiple processes can access them simultaneously. However, they do not contribute to deadlocks.
• Implementation:
  • For non-shareable resources, mutual exclusion cannot be completely eliminated. However, the system can minimize the use of such resources or design resources that can be shared where possible.

2. Elimination of the Hold and Wait Condition

• The hold and wait condition occurs when a process holds at least one resource while waiting to acquire additional resources. This situation can lead to a deadlock if multiple processes hold resources while waiting for each other.
• Prevention Strategies:
  • All-or-None Strategy: Require a process to request all the resources it will need at once before execution begins. If not all resources are available, the process must wait until all resources are free.
  • No Hold and Wait: Disallow processes from holding resources while waiting for others. If a process requests a resource and cannot be granted that resource, it must release all currently held resources and request them again later.
• Implications:
  • This strategy can lead to resource underutilization since processes may have to release resources they currently hold, causing inefficiencies.

3. Elimination of the No Preemption Condition

• The no-preemption condition states that resources cannot be forcibly taken from a process holding them. If a process is holding some resources and requests another that cannot be allocated, it must wait until it can be granted all its resources.
• Prevention Strategy:
  • Preemption: Allow the system to preempt resources from processes. If a process requests a resource that is not immediately available, the system should forcefully take away some resources from that process and allocate them to others.
• Implementation:
  • When a process that holds resources makes an additional request and cannot be granted that resource, it must release its held resources. The process can then re-request those resources along with the additional needed resource.
• Challenges:
  • This approach can lead to complex state management and may also result in processes being rolled back to a safe state if they lose resources.

4. Elimination of the Circular Wait Condition

• The circular wait condition occurs when there is a closed loop of processes, each waiting for a resource held by the next process in the loop. This condition is essential for a deadlock to occur.
• Prevention Strategy:
  • Total Ordering of Resources: Impose a strict order in which resources must be requested. Each process must request resources in a predefined order, either in ascending or descending numerical order.
• Example:
  • Consider the following global numbering of resources:
    1. Card Reader
    2. Printer
    3. Optical Driver
    4. Hard Disk Drive (HDD)
    5. Card Punch
  • Under this rule, if a process wants to request resources, it must do so in a strict sequence. For instance, a process may request the Printer (2) first and then the HDD (4), but it cannot request the Optical Driver (3) first and then the Printer (2).
• Implications:
  • While this strategy effectively prevents circular wait conditions, finding a globally acceptable ordering that satisfies all processes can be challenging and may lead to inefficiencies.

Deadlock Avoidance

Deadlock avoidance is a crucial technique in operating systems to prevent deadlocks from occurring. This approach anticipates potential deadlock situations by dynamically analyzing resource allocation states before granting resource requests. If granting a resource request would lead to a situation where deadlock could occur, the system postpones the request. The most well-known algorithm for deadlock avoidance is the Banker’s algorithm.

Key Concepts

1. Deadlock Conditions: Deadlocks can occur when the following four conditions are present simultaneously:
   • Mutual Exclusion: Resources cannot be shared.
   • Hold and Wait: Processes holding resources can request additional resources.
   • No Preemption: Resources cannot be forcibly taken from a process.
   • Circular Wait: A cycle exists where each process holds a resource and waits for another resource held by another process.
2. Safe and Unsafe States:
   • Safe State: The system is in a safe state if there exists a sequence of processes such that each process can finish executing without causing deadlock. This means all resources can eventually be allocated to all processes.
   • Unsafe State: An unsafe state does not guarantee that all processes can complete their execution. While the system may not be deadlocked, it is possible that a request from one or more processes could lead to a deadlock.

Relation between Safe, Unsafe and Deadlocked States

Resource-Allocation Graph

Deadlock avoidance can also be implemented using a Resource-Allocation Graph (RAG), where:

• Processes are represented as nodes.
• Resources are represented as nodes.
• An assignment edge (solid arrow) indicates that a resource is allocated to a process.
• A request edge (dashed arrow) indicates that a process is requesting a resource.
• A claim edge (also dashed) indicates that a process may request a resource in the future.

When a process requests a resource:

• The system checks if adding a request edge would create a cycle in the graph.
• If no cycle is created, the resource allocation is allowed. If a cycle is formed, the request is denied to prevent deadlock.

Banker’s Algorithm

The Banker's Algorithm, developed by Edsger Dijkstra, is a popular deadlock avoidance algorithm that ensures safe resource allocation by simulating resource requests.

Requirements for the Banker's Algorithm

The algorithm requires three primary pieces of information:

1. Max Matrix: Represents the maximum demand of each process for each resource.
2. Allocation Matrix: Indicates the currently allocated resources to each process.
3. Available Vector: Shows the number of available instances of each resource type.

To implement the Banker's Algorithm, the following data structures are used:

• Available: A vector indicating the number of available instances of each resource type.
• Max: An n x m matrix where n is the number of processes and m is the number of resource types, defining the maximum demand of each process.
• Allocation: An n x m matrix indicating the number of resources currently allocated to each process.
• Need: An n x m matrix where Need[i][j] = Max[i][j] - Allocation[i][j], indicating how many more resources of type j process i needs to complete its execution.

Safety Algorithm

The safety algorithm checks if the system is in a safe state:

1. Initialize: Set Work = Available and Finish[i] = false for all i.
2. Find Process: Look for a process i such that:
   • Finish[i] = false
   • Need[i] ≤ Work
3. Resource Allocation: If such a process is found, simulate resource allocation:
   • Work = Work + Allocation[i]
   • Finish[i] = true
4. Repeat: Go back to step 2.
5. Safe State Check: If Finish[i] = true for all processes, the system is in a safe state.

This algorithm may require O(m × n²) operations to determine if a state is safe.

Resource-Request Algorithm

When a process requests resources, the following checks are performed:

1. If the request exceeds the process's maximum claim (Request[i] > Need[i]), an error is raised.
2. If the request exceeds available resources (Request[i] > Available), the process must wait.
3. If the request is valid, the system temporarily allocates the requested resources and checks for safety:
   • Update Available, Allocation, and Need accordingly.
   • Run the safety algorithm to see if the new state is safe. If it is safe, grant the request; if not, roll back to the previous state and the process must wait.

Example

Let's consider a system with five processes (P0 through P4) and three resource types (A, B, C) with the following parameters:

• Available Resources:
  • A = 10
  • B = 5
  • C = 7
• Current Allocations:

Process	A	B	C
P0	0	1	0
P1	2	0	0
P2	3	0	2
P3	2	1	1
P4	0	0	2

Max 

Process	A	B	C
P0	7	5	3
P1	3	2	2
P2	9	0	2
P3	2	2	2
P4	4	3	3

Need Calculation:

Process	A	B	C
P0	7	4	3
P1	1	2	2
P2	6	0	0
P3	0	1	1
P4	4	3	1

Safety Check Example

Assuming we have the sequence <P1, P3, P4, P2, P0> that meets the safety criteria. Now if P1 requests one additional instance of resource type A and two instances of resource type C, making Request1 = (1, 0, 2).

1. Check Availability: Is Request1 ≤ Available?(1, 0, 2) ≤ (3, 3, 2) → Yes.

Pretend Allocation:Updated Allocation

A B C

P0 0 1 0 P1 3 0 2 P2 3 0 2 P3 2 1 1 P4 0 0 2

Updated Need A B C P0 7 4 3 P1 0 2 0 P2 6 0 0 P3 0 1 1 P4 4 3 1

Updated Available A B C P0 7 4 3

Run the safety algorithm to ensure the new state is safe. Assuming the sequence <P1, P3, P4, P0, P2> satisfies the safety requirement, we can grant P1's request.

Denied Requests

• If P4 requests `(3, 3, 0)`, the request cannot be granted since resources are not available.
• If P0 requests `(0, 2, 0)`, even though resources are available, granting it would lead to an unsafe state, hence denied.

Deadlock Detection

Deadlock detection is a crucial aspect of system resource management, especially when a system does not employ deadlock prevention or avoidance algorithms. When deadlocks occur, the system must have mechanisms to detect and recover from these situations. The detection process typically involves checking the state of resource allocation among processes and identifying cycles in the wait-for graph or applying specific algorithms to assess resource requests.

Categories of Deadlock Detection Algorithms

Deadlock detection algorithms can be classified based on the number of instances of each resource type:

1. Single Instance of Each Resource Type:
   • Wait-for Graph: In this scenario, each resource type has only one instance, making it easier to represent the system's state using a wait-for graph. The wait-for graph is derived from the resource-allocation graph by eliminating resource nodes and retaining only process nodes.
     1. Construction:
        • If process Pi is waiting for process Pj to release a resource, a directed edge is created from Pi to Pj in the wait-for graph.
        • This relationship exists if there are two edges in the resource-allocation graph: Pi→RqPi→Rq(Pi holds resource Rq) and Rq→PjRq→Pj (Pj is waiting for resource Rq).
     2. Cycle Detection: A deadlock exists in the system if there is a cycle in the wait-for graph. To detect cycles:
        • The system maintains the wait-for graph and periodically checks for cycles using algorithms that can run in O(n2)O(n2) time, where nn is the number of vertices in the graph. If a cycle is detected, the processes involved in the cycle are deadlocked.

2. Several Instances of a Resource Type:
   • For systems where resources can have multiple instances, a more complex detection algorithm is required that maintains several dynamic data structures:
     1. Available: A vector indicating the number of available resources of each type.
     2. Allocation: An n×mn×m matrix where each entry indicates the number of resources of each type currently allocated to each process.
     3. Request: An n×mn×m matrix that shows the current requests of each process for additional resources.
   • Detection Algorithm:
     1. Initialization:
        • Create two vectors: Work (initialized to Available) and Finish (initialized to false for all processes).
     2. Finding a Process:
        • Search for an index ii such that:
          • Finish[i]=falseFinish[i]=false (process Pi​ is not finished)
          • Request[i]<WorkRequest[i]<Work (the process's request can be satisfied with the currently available resources)
        • If no such index exists, go to step 4.
     3. Resource Allocation Simulation:
        • If a suitable process Pi​ is found:
          • Update Work by adding AllocationiAllocationi​ to it.
          • Set Finish[i]=true (indicating that Pi​ can finish).
          • Repeat step 2.
     4. Deadlock Detection:
        • If there exists any ii such that Finish[i]=false after the algorithm has finished, it indicates that the system is in a deadlock state. The processes that are not finished are considered deadlocked.

Complexity of Detection Algorithms

• The deadlock detection algorithms described require O(m×n2) operations to determine if the system is in a deadlocked state:
  • mm represents the number of resource types.
  • nn represents the number of processes in the system.

Recovery from Deadlock

Once a deadlock has been detected, the system must implement a recovery strategy to break the deadlock and restore normal operation. There are primarily two approaches to resolving deadlocks: Process Termination and Resource Preemption.

Process Termination

This method involves terminating one or more processes involved in the deadlock. There are two strategies for process termination:

Abort All Deadlocked Processes

• This approach involves terminating all processes that are currently deadlocked. By doing so, the deadlock cycle is broken immediately.
• Advantages:
  • Simplicity: The method is straightforward and ensures that all resources are released.
  • Cost-Effectiveness: Since all processes are terminated, there's no need to evaluate individual processes for termination, making it faster.
• Disadvantages:
  • Loss of Computation: This method results in the loss of all the work done by the terminated processes. Any progress they made is lost, which can be costly, especially if the processes have completed significant work.

Abort One Process at a Time

• Instead of terminating all processes, this method involves aborting one process at a time. After each termination, the system invokes a deadlock-detection algorithm to check if the deadlock persists.
• Advantages:
  • Minimized Loss: By aborting one process at a time, the system attempts to preserve the work completed by the other processes.
• Disadvantages:
  • Time-Consuming: This method can take longer to resolve the deadlock, as it requires repeated checks to see if the deadlock condition has been resolved.
  • Complexity: Determining which process to terminate can add complexity to the recovery process.

Resource Preemption

In this approach, the system forcibly takes resources away from one or more processes and reallocates them to other processes to break the deadlock cycle. This method requires careful management and consideration of several factors:

A. Selecting a Victim

• The system must decide which process to preempt. This decision is typically based on several criteria, including:
  • Cost of Preemption: This considers the overhead involved in rolling back a process and the potential impact on overall system performance.
  • Process Priority: Higher-priority processes might be preserved over lower-priority ones.
  • Resource Utilization: The current state of resource utilization and the amount of work already completed by the processes can influence which process to preempt.
• The goal is to minimize the overall impact on the system while effectively breaking the deadlock.

B. Rollback

• When resources are preempted from a process, that process may need to be rolled back to a previous safe state. This involves:
  • Checkpointing: The system should maintain checkpoints at regular intervals. If a process is rolled back, it can resume from the last checkpoint rather than starting over.
  • Resource State Management: The system must ensure that the resources are in a consistent state after rollback.
• Implementing an effective rollback mechanism requires additional overhead and management, as the system must keep track of the state of each process and its allocated resources.

C. Starvation

• When resources are preempted from a process, there is a risk of starvation, where a process might be continually denied the resources it needs to proceed. To mitigate starvation:
  • Fairness Policies: The system should implement policies that prevent indefinite preemption of resources from the same process.
  • Aging: This technique gradually increases the priority of processes that have been waiting for resources for a long time, ensuring they eventually get the resources they need.
• The aim is to ensure that every process gets a fair opportunity to execute, preventing situations where certain processes are perpetually starved of resources.