Deadlock avoidance (Banker's algorithm) in Operating Systems - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the Safe State in Banker's Algorithm

In the Banker's algorithm, what does it mean for the system to be in a safe state?

A The system can allocate resources to all processes in some order without causing a deadlock.

B The system has allocated all resources to processes, so no resources are free.

C The system has no processes currently requesting resources.

D The system is currently in a deadlock but can recover automatically.

💡 Hint

Think about what the algorithm tries to ensure before granting resource requests.

A safe state means the system can allocate resources to each process in some order and avoid deadlock. It does not mean no requests or all resources are allocated.

📋 Factual

intermediate

Key Data Structures in Banker's Algorithm

Which of the following is not a key data structure used in the Banker's algorithm?

A Request queue listing processes waiting for resources in order.

B Allocation matrix showing resources currently allocated to each process.

C Maximum matrix showing maximum demand of each process.

D Available vector showing currently free resources.

💡 Hint

Recall the matrices and vectors used to track resource allocation and needs.

The Banker's algorithm uses Available, Allocation, Maximum, and Need matrices/vectors. It does not use a request queue to order waiting processes.

🔍 Analysis

advanced

Analyzing Resource Allocation Safety

Given the following state:

Available = [3, 2, 2]
Allocation = [[0, 1, 0], [2, 0, 0], [3, 0, 2], [2, 1, 1], [0, 0, 2]]
Maximum = [[7, 5, 3], [3, 2, 2], [9, 0, 2], [2, 2, 2], [4, 3, 3]]

If process P1 requests [1, 0, 2], will granting this request keep the system in a safe state?

A Yes, because the request is less than or equal to the available resources.

B No, because the request exceeds the process's maximum demand.

C No, because the available resources are insufficient to grant the request.

D Yes, because after allocation, the system can find a safe sequence.

💡 Hint

Check if the request is within maximum demand and available resources, then verify if a safe sequence exists after allocation.

The request by P1 is within its maximum demand and available resources. After hypothetically granting it, the system can find a safe sequence, so it remains safe.

❓ Comparison

advanced

Comparing Deadlock Avoidance and Deadlock Prevention

Which statement best distinguishes deadlock avoidance (like Banker's algorithm) from deadlock prevention?

A Deadlock avoidance blocks all resource requests, while prevention allows all requests without checks.

B Deadlock avoidance requires no knowledge of maximum resource needs, while prevention requires full knowledge.

C Deadlock avoidance dynamically checks resource allocation safety, while prevention imposes strict resource usage rules upfront.

D Deadlock avoidance always leads to deadlock, while prevention never allows deadlock.

💡 Hint

Think about how each approach handles resource requests and system state.

Deadlock avoidance algorithms like Banker's check if granting a request keeps the system safe before allocation. Prevention methods restrict resource usage to avoid unsafe states.

❓ Reasoning

expert

Reasoning About Banker's Algorithm Limitations

Which of the following is a fundamental limitation of the Banker's algorithm in practical operating systems?

A It works only when there is a single type of resource.

B It requires processes to declare their maximum resource needs in advance, which is often impractical.

C It allows unsafe states that may lead to deadlock.

D It cannot detect deadlocks once they occur in the system.

💡 Hint

Consider what information the algorithm needs to function correctly.

The Banker's algorithm needs each process to declare its maximum resource needs beforehand, which is difficult in real systems where needs may be unknown or change.

Practice

1. What is the main purpose of the Banker's algorithm in operating systems?

easy

A. To increase CPU speed by optimizing instructions

B. To manage file storage on disk drives

C. To avoid deadlocks by checking if resource allocation is safe

D. To encrypt data for security purposes

Solution

1. Step 1: Understand the Banker's algorithm role

   The Banker's algorithm is designed to prevent deadlocks by simulating resource allocation and ensuring the system remains in a safe state.

2. Step 2: Compare options with the algorithm's purpose

   Only To avoid deadlocks by checking if resource allocation is safe correctly describes this purpose. Other options relate to unrelated system functions.

3. Final Answer:

   To avoid deadlocks by checking if resource allocation is safe -> Option C

4. Quick Check:

   Deadlock avoidance = Checking safe resource allocation [OK]

Hint: Banker's algorithm checks safety before granting resources [OK]

Common Mistakes:

• Confusing deadlock avoidance with performance optimization
• Thinking it manages storage or security
• Assuming it works after deadlock occurs

2. Which of the following is a required input for the Banker's algorithm to work correctly?

easy

A. The total CPU time each process will use

B. The maximum resource needs of each process

C. The size of the hard disk

D. The network bandwidth available

Solution

1. Step 1: Identify inputs needed by Banker's algorithm

   The algorithm requires the maximum resource needs of each process to predict safe allocation.

2. Step 2: Eliminate unrelated options

   CPU time, disk size, and network bandwidth are not inputs for this algorithm.

3. Final Answer:

   The maximum resource needs of each process -> Option B

4. Quick Check:

   Max resource needs = Required input [OK]

Hint: Know max needs to predict safe resource allocation [OK]

Common Mistakes:

• Confusing CPU time with resource needs
• Including unrelated system metrics
• Ignoring maximum resource requirements

3. Given the following data for three processes (P1, P2, P3) and one resource type with 10 units total:
Allocation: P1=3, P2=2, P3=2
Maximum: P1=7, P2=4, P3=3
Available: 1 unit
Which process can safely get its requested resources without causing deadlock?

medium

A. P1, because it needs 4 more units which are available

B. P2, because it needs 2 more units which are available

C. None, because available units are insufficient

D. P3, because it needs 1 more unit which is available

Solution

1. Step 1: Calculate each process's remaining need

   Need = Maximum - Allocation
   P1: 7-3=4 units
   P2: 4-2=2 units
   P3: 3-2=1 unit

2. Step 2: Compare needs with available units

   Available units = 1
   P1 needs 4 (not available)
   P2 needs 2 (not available)
   P3 needs 1 (available)
   Only P3 can be satisfied immediately, finishing first and releasing resources safely.

3. Final Answer:

   P3, because it needs 1 more unit which is available -> Option D

4. Quick Check:

   Need ≤ Available means safe allocation [OK]

Hint: Check need = max - allocation; compare with available [OK]

Common Mistakes:

• Miscalculating which process's need ≤ available
• Choosing process with higher need incorrectly
• Confusing allocation with need

4. A system using the Banker's algorithm has the following state:
Allocation: P1=1, P2=2
Maximum: P1=3, P2=3
Available: 1 unit
If process P1 requests 2 more units, what is the correct action?

medium

A. Deny the request to avoid unsafe state

B. Grant the request immediately

C. Ignore the request and continue

D. Increase available units to grant request

Solution

1. Step 1: Calculate P1's need and check availability

   P1's need = Maximum - Allocation = 3 - 1 = 2 units
   Available units = 1
   P1 requests 2 units, but only 1 is available.

2. Step 2: Determine if granting request is safe

   Granting 2 units is impossible now; it would cause an unsafe state or deadlock.
   Therefore, the request must be denied.

3. Final Answer:

   Deny the request to avoid unsafe state -> Option A

4. Quick Check:

   Request > Available means deny [OK]

Hint: Deny requests exceeding available resources [OK]

Common Mistakes:

• Granting requests without checking availability
• Ignoring unsafe states
• Assuming system can create resources

5. Consider a system with 3 processes (P1, P2, P3) and 2 resource types (R1 and R2).
Maximum needs:
P1: (7, 5), P2: (3, 2), P3: (9, 0)
Current allocation:
P1: (3, 2), P2: (2, 1), P3: (3, 0)
Available resources: (3, 2)
If P2 requests (1, 1), should the Banker's algorithm grant it? Why or why not?

hard

A. Yes, because granting keeps system in a safe state

B. No, because P2's request exceeds its maximum need

C. No, because granting leads to an unsafe state

D. Yes, because available resources are sufficient

Solution

1. Step 1: Check if request exceeds maximum need

   P2's maximum need = (3, 2)
   Current allocation = (2, 1)
   Request = (1, 1)
   New allocation would be (3, 2), which equals maximum need, so request is valid.

2. Step 2: Check if available resources can satisfy request and system remains safe

   Available = (3, 2)
   Request = (1, 1) ≤ Available, so resources are sufficient.
   After granting, Available becomes (2, 1).
   Check if system can finish all processes:
   - P1 needs (7-3, 5-2) = (4, 3)
   - P2 needs (3-3, 2-2) = (0, 0)
   - P3 needs (9-3, 0-0) = (6, 0)
   P2 can finish immediately, releasing (3, 2) back.
   Then Available becomes (5, 3), enough for P1 and P3 to finish.
   System is safe.

3. Final Answer:

   Yes, because granting keeps system in a safe state -> Option A

4. Quick Check:

   Request ≤ Max and safe state = Grant [OK]

Hint: Grant if request ≤ max and system stays safe after allocation [OK]

Common Mistakes:

• Denying valid requests due to misunderstanding max need
• Ignoring safety check after allocation
• Assuming available resources alone decide grant