6

Deadlock situation: A is waiting for B; B is waiting for A

• All processes/threads are waiting for an event (blocked state)

• The events will never be initiated.

• None of the processes/threads will ever be ready again

Preemptable

can be withdrawn from process, preventing deadlocks

Nonpreemptible

can’t be withdrawn from process, as this leads to termination

1. Mutual Exclusion Each resource can be held by only one process at a time.

2. Hold and Wait Processes holding resources can request additional resources.

3. No Preemption Resources cannot be forcibly taken from a process; they must be released voluntarily.

4. Circular Wait A cycle of processes, each waiting for a resource held by the next process in the chain.

1 through 3 are necessary prerequisites for the fourth condition to occur at all

1. Ostrich Algorithm

   Ignore the problem, assuming deadlocks are rare and acceptable in the system.

2. Detection and Recovery

   Allow deadlocks to occur, then detect and resolve them (e.g., killing a process or resource preemption).

3. Deadlock Avoidance

   Dynamically avoid entering a deadlock state by ensuring the system never satisfies all four conditions (e.g., Banker's Algorithm).

4. Deadlock Prevention

   Eliminate at least one of the four necessary conditions for deadlock through system design.

1. How likely is a deadlock compared to other failures (e.g., hardware errors)?

2. Can the system tolerate deadlocks by simply resetting or restarting without serious consequences?

Ignore the problem.

1. Initialization

   • A = current available resources

   • Finish[i] = false if process i has outstanding requests (i.e., C[i] ≠ 0); otherwise, true.

2. Find a Process

   • Look for a process i such that: Finish[i] == false and R[i] ≤ A (the process’s remaining request can be satisfied with currently available resources).

3. Simulate Resource Release

   • If such a process is found:

     • A = A + C[i]

     • Finish[i] = true

     • Repeat Step 2.

4. Deadlock Detection

   • If no such process can be found in Step 2 and there are processes with Finish[i] == false, these processes are in deadlock.

1. E = Existing (total) resources.

2. A = Available resources.

3. C = Current allocations per process.

4. R = Requested by process

1. Recovery through preemption

• Difficult, since non-preemptable resources are considered.

2. Rollback of a process

• Establishment of checkpoints

• If deadlock is detected, rollback a process to such a checkpoint

• Also difficult to implement

3. Termination of a process/thread

• Easiest to implement.

• Select the process whose termination will cause the "least damage".

• A state is considered safe if there is an execution order of processes in which every process is completed (without deadlock), even if all processes immediately request their respective maximum number of resources.

• Otherwise, a state is considered unsafe.

Banker's algorithm:

• The operating system checks each resource request to see if there would still be a safe state when it was granted. If not, the resource request is not granted (process/thread is blocked).

This requires prior knowledge of the maximum requirement of each process/thread!

Basically Matrix Algorithm but R = Q, with Q = max – C

Q are basically the needed maximum ressouces.

In general

MAX REQUESTED RESSOURCES (MAX) - CURRENTLY UTILZED RESSOURCES (C) = NEEDED RESSOURCES (Q)

EXISTING RESSOURCES (E) - C = AVAILABLE RESSOURCES (A)

if for any process (Pi)

Qi < A

holds

execute Pi and

Ci + A = A

and go to next process

Condition 1 (mutual exclusion):

• This condition cannot be made ineffective, since the mechanisms of mutual exclusion must exist to avoid synchronisation problems.

• However, mutual exclusion can be limited to what is absolutely necessary. ( he likelihood of a deadlock decreases)

• For example, separation between transmission of the print job and the printing process itself via printer spooler.

Condition 2 (hold and wait):

• A process has to make all its resource requests at one time. • The problem here:

1. Not all resources are needed all the time.

2. Granting such a large resource request takes longer, as some of the required resources may still be in use elsewhere

Condition 3 (no preemption):

2 variants

1. If a process is denied a resource request, it must release all resources used by itself. (All processes developers must know and observe this rule.)

2. The operating system can force a process to release a resource. This requires the ability to save and restore the current working state of the resource for the releasing process. (This is partly difficult to implement).

Condition 4 (circular wait):

• A linear order of the resource types is defined. • Processes may only request resources following this order.

• The problem here (similar to hold & wait):

1. Resources must already be requested that are not yet needed.

2. Granting such an early request can (unnecessarily) block the process if the resource is already being used.