deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does.  In computer science, Coffman deadlock refers to a specific condition when two or more processes are each waiting for the other to release a resource, or more than two processes are waiting for resources in a circular chain. Deadlocks are particularly troubling because there is no general solution to avoid (soft) deadlocks.

Consider a following bridge crossing example:

Each segment of road can be viewed as a resource

  • Car must own the segment under them
  • Must acquire segment that they are moving into

For bridge: must acquire both halves

  • Traffic only in one direction at a time
  • Problem occurs when two cars in opposite directions on bridge: each acquires one segment and needs next

If a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback)

  • Several cars may have to be backed up

Starvation is possible

  • East-going traffic really fast
  • no one goes west

Train Example (Wormhole-Routed Network)

Circular dependency (Deadlock!)

  • Each train wants to turn right
  • Blocked by other trains
  • Similar problem to multiprocessor networks

Fix? Imagine grid extends in all four directions

  • Force ordering of channels (tracks). 
  • Protocol: Always go east-west first, then north-south

Called “dimension ordering” (X then Y)

Dining Lawyers Problem

Five chopsticks/Five lawyers (really cheap restaurant)

  • Free-for all: Lawyer will grab any one they can
  • Need two chopsticks to eat

What if all grab at same time?

  • Deadlock!

How to fix deadlock?

  • Make one of them give up a chopstick (Hah!)
  • Eventually everyone will get chance to eat

How to prevent deadlock?

Never let lawyer take last chopstick if no hungry lawyer has two chopsticks afterwards

 

Starvation vs Deadlock

Starvation: thread waits indefinitely

  • Example, low-priority thread waiting for resources constantly in use by high-priority threads

Deadlock: circular waiting for resources

  • Thread A owns Res 1 and is waiting for Res 2
  • Thread B owns Res 2 and is waiting for Res 1

Deadlock -> Starvation but not vice versa

  • Starvation can end (but doesn’t have to)
  • Deadlock can’t end without external intervention

Four requirements for Deadlock

  1. Hold and wait: Thread holding at least one resource is waiting to acquire additional resources held by other threads
  2. Limited Resources: There is a limited number of resources of a particular type. Processes will block if requesting a limited that is unavailable
  3. No preemption: Resources are released only voluntarily by the thread holding the resource, after thread is finished with it
  4. Circular wait: There exists a set {T1, …, Tn} of waiting threads
  • T1 is waiting for a resource that is held by T2
  • T2 is waiting for a resource that is held by T3
  • Tn is waiting for a resource that is held by T1

Deadlock Prevention

Hold and Wait

sharable resources like read-only files are deadlock free

Limited Resources

Resources with unlimited instances are deadlock free.

No Preemption (Disadvantage: loss of data integrity)

Release all resources instead of blocking on a resource request. The preempted resources are added to the resource wait list. Restarted when all requested resources are allocated.

Circular Wait (Disadvantage: Low resource utilization)

Impose a total ordering of resource types. Processes must request resources in an increasing order of enumeration. Processes cannot request resources when already holding others.

Deadlocks occur with multiple resources. Means you can’t decompose the problem. 

What to do when detect deadlock?

  • Terminate thread, force it to give up resources
  • Preempt resources without killing off thread
  • Roll back actions of deadlocked threads
  • Many operating systems use other options

Techniques for Preventing Deadlock

  • Infinite resources: Include enough resources so that no one ever runs out of resources. Doesn’t have to be infinite, just large. Give illusion of infinite resources (e.g. virtual memory). For Examples: Bay bridge with 12,000 lanes Never wait!, Infinite disk space (not realistic yet?)
  • No Sharing of resources (totally independent threads)
  • Don’t allow waiting
  • Force all threads to request resources in a particular order preventing any cyclic use of resources

Deadlock Prevention Algorithms

  • One-shot Algorithm
  • Hierarchical Algorithm
  • Havender’s Algorithms
  • Baker’s Algorithm

 

 

Tagged with: JAVAJAVA GUIObject OrientedThreads
 

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

 

Looking for something?

Use the form below to search the site:


Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.