Deadlocks

Overview

• Deadlocks and conditions for deadlocks
• Algorithms to detect[探知] deadlocks
  Approaches to recover from deadlocks

  Deadlocks

  How Occur deadlocks?[看看就好]

• Some resources are mutually exclusive and can only be used by one process at a time
• On occasions[偶然], multiple processes will require access to multiple mutually exclusive resources (e.g. process A and B need resources X and Y)
• Process A and B request the resources in opposite orders and end up in deadlock
  • Deadlocks can occur on the same machine or between multiple machines (e.g. resources are requested over the network) and any number of resources
  • Deadlocks are not just related to operating systems but also occur, e.g., in databases

resource

• A resource (e.g. a device, a data record, file, semaphore) can be acquired, used, and released
  • A resource can be preemptable, i.e., it can be forcefully taken away from the process without permanent adverse effect
  • A resource can be non-preemptable, i.e., it cannot be taken away from a process without permanent adverse effect
• If a non-preemptable resource is requested but not available, the process is made to wait
• Deadlocks only occur for non-preemtable resources because preemtable resources can be temporarily taken away to recover from the deadlock

Definition

“A set of processes is deadlocked if each process in the set is waiting for an event that only the other process in the set can cause”
– Tanenbaum

• Each deadlocked process is waiting for a resource held by an other deadlocked process (which cannot run and hence cannot release the resources)
• This can happen between any number of processes and for any number of resources

Conditions

Four conditions must hold for deadlocks to occur (Coffman et al. (1971)):

• Mutual exclusion: a resource can be assigned to at most one process at a time
• Hold and wait condition: a resource can be held whilst[同时] requesting new resources
• No preemption: resources cannot be forcefully taken away from a process
• Circular wait: there is a circular chain of two or more processes, waiting for a resource held by the other processes

No deadlocks can occur if one of the conditions is not satisfied

赏

谢谢投喂 (～o￣3￣)～

支付宝