Week 9: Deadlocks

Question 1

What are shared resources?

Answer 1

Resources shared by processes, classified as:
- Physical (e.g., processor, memory, I/O
- Logical (e.g., data structures, message queues).

Question 2

What are reusable and consumable resources?

Answer 2

• Reusable: Not destroyed by use (e.g., memory, processor).
• Consumable: Used up after one use (e.g., signals, messages).

Question 3

What are the three main synchronisation problems?

Answer 3

• Race conditions: two or more processes competing for a shared resource the result varies according to the order of process execution
• Deadlocks: a situation where two or more processes are each waiting for resources held by others
• Starvation: a process never gets access to a required resource

Question 4

What is a deadlock?

Answer 4

A situation where two or more processes wait indefinitely for resources held by each other, creating a cycle of dependencies.

Question 5

What are the four conditions for a deadlock to occur?

Answer 5

• Mutual exclusion: Resources cannot be shared.
• Hold and wait: Processes hold resources while waiting for others.
• No pre-emption: Allocated resources cannot be forcibly taken.
• Circular wait: A closed chain of processes exists where each holds at least one resource needed by the next.

Question 6

What is deadlock modelling using directed graphs?

Answer 6

• Processes are represented as circles.
• Resources are represented as squares.
• Arrows indicate allocation or waiting for a resource.

Question 7

Scheduling choices can avoid or cause deadlock. A resource graph can be created & checked at each step. When is a deadlock guaranteed to happen?

Answer 7

When it contains a cycle, then there is a deadlock

Question 8

What are the four strategies to deal with a deadlock?

Answer 8

• Deadlock Avoidance: Careful scheduling to ensure safe states.
• Deadlock Prevention: Alter system conditions to prevent deadlock.
• Deadlock Detection and Recovery: Identify and resolve deadlocks.
• Ostrich Algorithm: Ignore the problem if its occurrence is infrequent.

Question 9

Why must the OS keep track of the current state to avoid deadlocks?

Answer 9

To determine whether it is safe or unsafe

Question 10

What is a safe state vs. an unsafe state?

Answer 10

• Safe state: No deadlock and all resource requests can eventually be met.
• Unsafe state: Deadlock may occur depending on process behaviour.

Question 11

What is the banker’s algorithm?

Answer 11

A deadlock avoidance algorithm that evaluates resource allocation states to ensure safe system operation.

Question 12

How does the banker’s algorithm work?

Answer 12

We have three 2D tables:
- Allocation table
- Max table
- Available table.

The Allocation table holds the amount of each resource each process is currently using.
The Max table holds the amount of each resource each process requires to finish.
The Available table holds the amount of each resource that is currently available for allocation.

For row=1 (the first row) we create a table Need that each row includes Max[row] - Allocation[row]

Then, for each row in the Need table, we check if Need[row] <= Available[row]. If no row satisfies this then the system is in an unsafe state. If a row satisfies this, then, Available += Allocation[row], and For each resource in Need[row] the amount becomes 0.

This is repeated until all the rows of Need have their resources of 0 amounts.