Deadlock avoidance (Banker's algorithm) in Operating Systems - Mini Project: Build & Apply

Deadlock Avoidance with Banker's Algorithm

📖 Scenario: You are managing resource allocation in a computer system to avoid deadlocks. You want to use the Banker's algorithm to check if the system is in a safe state before granting resource requests.

🎯 Goal: Build a step-by-step Banker's algorithm setup that models processes, resources, and checks for safe states to avoid deadlocks.

📋 What You'll Learn

Create data structures for processes, maximum resource needs, allocated resources, and available resources.

Define a variable to track the number of processes.

Implement the core logic to calculate the need matrix and check for a safe sequence.

Complete the setup by adding a final step to confirm the system's safe state.

💡 Why This Matters

🌍 Real World

Operating systems use the Banker's algorithm to avoid deadlocks by ensuring resource allocation keeps the system in a safe state.

💼 Career

Understanding deadlock avoidance is important for system administrators, OS developers, and anyone working with concurrent systems or resource management.

1

Set up initial resource allocation data

Create a dictionary called allocated with these exact entries: 0: [0, 1, 0], 1: [2, 0, 0], 2: [3, 0, 2], 3: [2, 1, 1], 4: [0, 0, 2]. Also create a dictionary called maximum with these exact entries: 0: [7, 5, 3], 1: [3, 2, 2], 2: [9, 0, 2], 3: [2, 2, 2], 4: [4, 3, 3]. Finally, create a list called available with the exact values [3, 3, 2].

Operating Systems

# Create allocated, maximum dictionaries and available list with exact values
# Your code here

Need a hint?

Use dictionaries for allocated and maximum with process IDs as keys and lists of resource counts as values. Use a list for available.

2

Define the number of processes

Create a variable called num_processes and set it to the integer 5.

Operating Systems

allocated = {
    0: [0, 1, 0],
    1: [2, 0, 0],
    2: [3, 0, 2],
    3: [2, 1, 1],
    4: [0, 0, 2]
}
maximum = {
    0: [7, 5, 3],
    1: [3, 2, 2],
    2: [9, 0, 2],
    3: [2, 2, 2],
    4: [4, 3, 3]
}
available = [3, 3, 2]
# Create a variable num_processes and set it to 5
# Your code here

Need a hint?

Count the number of processes from the dictionaries and assign it to num_processes.

3

Calculate the need matrix

Create a dictionary called need where each key is a process ID from 0 to 4, and the value is a list representing the difference between maximum and allocated resources for that process. Use a for loop with the variable i to iterate over the process IDs.

Operating Systems

allocated = {
    0: [0, 1, 0],
    1: [2, 0, 0],
    2: [3, 0, 2],
    3: [2, 1, 1],
    4: [0, 0, 2]
}
maximum = {
    0: [7, 5, 3],
    1: [3, 2, 2],
    2: [9, 0, 2],
    3: [2, 2, 2],
    4: [4, 3, 3]
}
available = [3, 3, 2]
num_processes = 5
# Calculate the need dictionary using a for loop with variable i
# Your code here

Need a hint?

Use a dictionary comprehension inside the loop to subtract allocated from maximum for each resource.

4

Check for a safe sequence

Create a list called finish with False repeated num_processes times. Create a list called work as a copy of available. Use a while loop to find a process i where finish[i] is False and all elements in need[i] are less than or equal to corresponding elements in work. If found, add allocated[i] to work, set finish[i] to True. Repeat until no such process is found. This completes the Banker's algorithm safe state check.

Operating Systems

allocated = {
    0: [0, 1, 0],
    1: [2, 0, 0],
    2: [3, 0, 2],
    3: [2, 1, 1],
    4: [0, 0, 2]
}
maximum = {
    0: [7, 5, 3],
    1: [3, 2, 2],
    2: [9, 0, 2],
    3: [2, 2, 2],
    4: [4, 3, 3]
}
available = [3, 3, 2]
num_processes = 5
need = {}
for i in range(num_processes):
    need[i] = [maximum[i][j] - allocated[i][j] for j in range(len(available))]
# Add code to create finish list, work list, and implement the safe sequence check loop
# Your code here

Need a hint?

Use a while loop with a flag variable found to repeat the search for a process that can finish safely.