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. 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

VIII. Resources & Further Reading