Dr. Soumadip Biswas
Computer Science & Engineering | Student | Researcher | Educator

Assignment 05: Deadlock Management

I. Objective & Theoretical Framework

In a multiprogramming environment, several processes may compete for a finite number of resources. If a process requests resources that are currently unavailable, it enters a waiting state. A deadlock occurs when a waiting process can never again change state because the resources it has requested are held by other waiting processes.

This laboratory focuses on Deadlock Avoidance using the Banker’s Algorithm. This approach requires the operating system to be given advanced information concerning which resources a process will request and use during its lifetime. The system uses this knowledge to evaluate whether granting a request will leave the system in a “Safe State.”

The Banker’s Algorithm is specifically applicable to a system with multiple instances of each resource type.

II.A. Motivation: Experiencing Deadlock in Action

Before implementing an avoidance algorithm, it is crucial to observe how easily deadlocks manifest in concurrent programming. You will compile and run the attached dining_philosophers_deadlock.c resource file.

This program simulates five philosophers sitting at a table, where each must pick up a left fork and a right fork to eat. Because every thread is programmed to pick up the left fork first, pause slightly, and then request the right fork, a circular wait is guaranteed.

Instructions to test the deadlock:

  1. Download the attached dining_philosophers_deadlock.c file.
  2. Compile it using the POSIX threads library: gcc dining_philosophers_deadlock.c -o deadlock_sim -pthread
  3. Execute the binary: ./deadlock_sim
  4. Observe the terminal output. The program will freeze indefinitely once every philosopher is holding their left fork and waiting for the right. You must manually terminate the process using Ctrl+C.

This catastrophic system freeze is exactly what the Banker’s Algorithm is designed to prevent.

💻 Attached codes

II.B. Prerequisite Knowledge & Resources

III. Starter Code & Partial Implementations

To manage the matrices cleanly, it is highly recommended to use an array of structures. The following starter code provides the data structure and the initial logic to compute the need matrix.

#include <stdio.h>

// Structure to hold resource data for a single process
struct process_node {
    int all[10];  // Allocation
    int max[10];  // Maximum demand
    int need[10]; // Remaining need
    int flag;     // Visited/Finished status
};

int main() {
    struct process_node p[10];
    int avail[10], seq[10];
    int n, r, i, j;

    printf("Enter number of processes: ");
    scanf("%d", &n);
    printf("Enter number of resource types: ");
    scanf("%d", &r);

    // [Omitted: Code to scan Allocation and Max matrices from the user]

    // Calculate the Need Matrix
    for(i = 0; i < n; i++) {
        for(j = 0; j < r; j++) {
            p[i].need[j] = p[i].max[j] - p[i].all[j];
            // Safety catch for invalid inputs
            if(p[i].need[j] < 0) {
                p[i].need[j] = 0;
            }
        }
        p[i].flag = 0; // Initialize as unvisited
    }

    // [Insert Safety Algorithm Logic Here]

    return 0;
}

IV. Step-by-Step Task List

  1. Matrix Initialization: Complete the starter code by writing the for loops to accept user input for the Allocation and Maximum matrices, as well as the initial Available resources array.

  2. The Safety Algorithm: Implement the core Banker’s logic. Iterate through all unvisited processes (flag == 0). For each process, check if its need for every resource type is $\le$ the avail resources.

  3. Simulate Execution: If a process can be executed, mark it as visited (flag = 1), add it to your Safe Sequence array (seq), and release its allocated resources back into the avail pool ($Available = Available + Allocation$).

  4. State Output: Loop this process until all processes are visited (System is in a Safe State) or until you complete a full loop without being able to execute any process (System is in an Unsafe State). Print the Safe Sequence if one exists.

V. Common Pitfalls & Debugging Strategies

VI. Real-World Case Study

The principles of deadlock avoidance are foundational to distributed systems. In a cluster computing environment or a distributed database, multiple nodes often request locks on shared data tables concurrently. If these locks are not mathematically vetted for safety before being granted, a circular wait occurs, freezing the database. While modern operating systems rarely use the Banker’s algorithm for general processes due to the overhead of knowing “Max Demand” in advance, specialized distributed transaction managers and embedded avionics systems still rely heavily on graph-based avoidance algorithms derived directly from these concepts.

VII. Advanced Variant Tasks

The Concept: Instead of just printing “Safe” or “Unsafe” to the terminal, require your Banker’s Algorithm (or your simulated deadlock code) to dynamically generate a Resource Allocation Graph (RAG).

The Task:

  • Add a function to your C code that writes the current state of processes and resources to a .dot text file using Graphviz syntax.
  • For example, your C code prints P1 -> R1; (Request edge) and R2 -> P1; (Assignment edge) to the file based on the Need and Allocation matrices.
  • The Observation: You run your C program, pipe the .dot file into the open-source Graphviz tool (dot -Tpng rag.dot -o rag.png), and instantly generate a visual map of the system state. If a deadlock occurs, you will literally be able to see the circular wait rendered as a cycle on your screen.

VIII. Resources & Further Reading

SDB Watermark