Chapter Six

Main Topics

CIS343

 

Deadlock::

4 Necessary Conditions:

  w Mutual exclusion

          Only one process may use a resource at a time.

  w Hold and wait

          A process may hold allocated resources while awaiting assignment of others.

  w No preemption

          No resource may be forcefully removed from a process holding it.

  w Circular wait

          A closed chain of processes exists.

 

3 Ways to Handle Deadlock

  w Deadlock Prevention

          Prevent one of the 4 conditions from occurring

  w Deadlock Avoidance

          Never allow system to reach an unsafe state

  w Deadlock Detection & Recovery

          Allow deadlock to occur; detect its occurrence; remove processes until deadlock

          is eliminated

 

Deadlock Prevention

          Actions taken (AT) matched with condition prevented (CP)::

  w AT: A process holding a resource must surrender it when denied a further request.

          CP: No preemption/Hold & Wait

  w AT: A resource requested by one process may be taken from the process holding it.

          CP: No preemption

  w AT: Resource types have a linear ordering. Resource requests must be made in the

          specified order.

          CP: Circular Wait

  w AT: A process must make all its resource requests at one time.

          CP: Hold & Wait

Notice: No action corresponds to prevention of mutual exclusion, since, in general,

          this condition cannot be disallowed.

 

Deadlock Avoidance

          Actions taken (AT: ) matched with name of strategy (STR: )::

  w AT: Grant a request only if the result of the grant is a safe state.

          STR: Resource allocation denial (banker's algorithm)

  w AT: Start a process only if the maximum claims of all current processes plus those

          of the new process can be met.

          STR: Process initiation denial

 

Banker's Algorithm

  w All states are either safe or unsafe.

  w Safe state

          There is at least one sequence in which all processes can run to completion

          without leading to deadlock

  w Question/Answer

      v Q: Since in a safe state, there are some sequences of execution that could lead to

              deadlock, why is it called safe? I.e., what keeps deadlock from occurring?

      v A: If one of the sequences leading to an unsafe state were to occur, it would

               trigger resource denial by the OS

 

Q/A Information:

1. Rank these in order, from most conservative to least.

a. Deadlock detection & recovery

b. Deadlock prevention

c. Deadlock avoidance

B, C, A

(2-10) Classify each of these in one of the categories listed immediately below:

DP. Deadlock prevention

DA. Deadlock avoidance

DDR. Deadlock detection & recovery

IDS. Integrated deadlock strategy

2. Do not start a process if its demands might lead to deadlock.

DA

3. Deny the hold and wait condition

DP

4. Successively preempt until deadlock no longer exists.

DDR

5. Group resources into classes,with linear ordering in each class. Within any class use the algorithm most appropriate for that class.

IDS

6. Back up each deadlocked process to some previously defined checkpoint. Restart all processes.

DDR

7. A process holding a resource must surrender it when denied a further request.

DP

8. Do not grant a resource request if it could lead to deadlock.

DA

9. Abort all deadlocked processes.

DDR

10. Processes must make all resource requests in a predefined order, regardless of the order of actual need by that process.

DP

 

11. What is the most commonly adopted solution to deadlock recovery?

Abort all deadlocked processes