Print this chapterPrint this chapter

CS401 Study Guide

Unit 5: Deadlock

5a. Explain what deadlock is in relation to operating systems

  • Define deadlock.
  • Describe the conditions for deadlock.

Deadlock is a specific type of computer scheduling starvation where the execution of a job process is delayed for an inordinate amount of time. Deadlock occurs when the process is never allowed to execute. The job is in a circular starvation pattern which never allows it to execute.

Five conditions for deadlock include:

  1. Mutual Exclusion – only one thread at a time can use a resource.
  2. Hold and Wait – a thread holding at least one resource is waiting to acquire additional resources held by other threads.
  3. No Preemption – threads only release resources voluntarily.
  4. Circular Wait – there is a set of threads with a cyclic waiting pattern.
  5. Requesting Resources in the Wrong Order.

Review this material in Deadlock.

 

5b. Discuss deadlock prevention, avoidance, and the differences between each

  • Describe some techniques for preventing deadlock.
  • Define the Banker's Algorithm.

Brilliant and elegant thinking, and using computer-based logic may be required to avoid or overcome deadlock.

Some techniques for avoiding gridlock include:

  1. Providing excess resources.
  2. Never sharing resources.
  3. Eliminating wait time.
  4. Pre-requesting resources.
  5. Forcing resources to be requested in order.

One technique for avoiding deadlock is Banker's Algorithm. This technique involves incorporating a dynamic allocation of resources. Think about how a banker needs to calculate whether the bank should lend money to a customer based on how much money the individual has deposited at the bank.

In the same way, all resources that might be required, while not immediately seized, must be made known in advance by the thread. This process ensures each thread releases its resources after execution. Banker's Algorithm dictates that the maximum amount of all resource needs for all of the current threads is greater than the total resources.

Note that we are using a fluid or expanding the definition of "program". The more formal understanding is that a program is the written software, dormant on a shutdown computer that is ready to run. Although we often say "run the program", computer purists would dismiss this.

A process means the program is running. You might consider a thread to be a "program" since it executes one particular function the program does or is supposed to do. Each process must request resources from the OS, such as CPU time to run. The OS commands everything and will grant threads resources based on how the OS is written. Different results will ensue depending on how that OS is written and handles the allocation of resources to requesting threads. You can think about a thread as a single keystroke, when it shows up on the keyboard and when it is recorded in memory. Each of those could be its own thread.

Review this material in Deadlock.

 

5c. Describe deadlock detection and recovery

  • Describe three ways to discover deadlock.
  • Name some ways to recover from deadlock.

Deadlock describes a specific case of starvation where a thread will NEVER be executed. It is logically impossible, not just operationally unlikely, although it may seem so.

Deadlock cannot be allowed and must be anticipated if possible. If ignored, a reboot is required. If a reboot is unacceptable, the computer programmer must find a better and more elegant design that definitively avoids deadlock, otherwise, the consequences of a failure of the software will ensue, and are assured to occur at an unspecified time. Most likely, any time is the worst time for it to occur.

Three ways to discover deadlock include:

  1. Infinite testing – this option is often impractical.
  2. Analysis – examine for no cycles in "lock" acquisition.
  3. Random timing testing.

Some ways to recover from deadlock include:

  1. Add more resources.
  2. Interrupt thread participating in deadlock.
  3. Prioritize non-competing threads.
  4. Preventing deadlock by definition, i.e. proper ordering of threads, aka dimension ordering

Review these materials in:

 

Unit 5 Vocabulary

  • Banker's Algorithm
  • Circular wait
  • Deadlock
  • Hold and wait
  • Mutual exclusion
  • No preemption
  • Starvation