Vault

ECS150-L16

3 min read

📗 -> 02/13/26: ECS150-L16

[Lecture Slide Link]

🎤 Vocab

❗ Unit and Larger Context

Deadlock

✒️ -> Scratch Notes

Real-life deadlock: Traffic jam

Code example

void thread1(void) { 
	lock(lock1); 
	lock(lock2); 
	... /* computation */ ... 
	unlock(lock2); 
	unlock(lock1); 
}
void thread2(void) { 
	lock(lock2); 
	lock(lock1); 
	... /* computation */ ... 
	unlock(lock2); 
	unlock(lock1); 
}

Somewhat similar to a race condition

  • Depending on interleaving, code might deadlock

Could be solved by respecting consistent structure:

  • Core design pattern in concurrent programming

Deadlocks PROBABLY won’t happen, but if code is interleaved juuust right you could run into issues

Vocab

Starvation - One or more tasks of a group are indefinitely blocked

  • Not able to make progress
  • These tasks (or philosophers in that one example) are starving
    The group as a whole is still making progress

Deadlock - A GROUP of tasks is deadlocked if EACH task in the group is waiting for an even that only another task in the group can trigger

  • Usually, the even is the release of a currently held resource
  • None of the tasks can: run, release resources, or be awakened
    A deadlock is the ultimate starvation

Formalism

A cycle in the resource allocation graph expresses a deadlock
Connections in resource allocation graph:

  • Process -> Resource
    • Requesting a resource, want a mutex dropped
  • Resource -> Process
    • Holding a resource, keeping a mutex dropped
Four conditions for deadlock
  1. Mutual exclusion/bounded resources
    • Limited amount of resources, otherwise they could just… do their task
  2. Hold and wait
    • Each task is holding a resource while waiting for another resource
  3. No preemption
    • ‘Cannot steal a resource, it must be given’
    • Resources cannot be preempted, only released voluntarily
  4. Circular wait
    • One task waiting for another in a circular fashion

Deadlock Strategy

  1. Ostrich algorithm - Just ignore the problem completely, reset when it happens
  2. Detection and recovery - Let the deadlock occur, fix it afterwards
  3. Dynamic avoidance - Careful resource allocation during execution. Avoid getting deadlocked
  4. Prevention - Negating one of the four necessary conditions so that by design, a deadlock can never happen
Ostrich

Idea - Just run the code and deal with problems:

  • If OS kernel locks - Reboot
  • If application hangs - Kill it
  • etc.

Mitigation:

  • Make restarts less painful:
    • Autosave or restore features
    • If an application hangs:
      • Checkpoint application / change environment (reboot) / restart from checkpoint
Detection and Recovery

Idea: Search for deadlocks and deal with them

1. Detection
Detect resource ownerships and requests

  • Search for cycles in the graph, if found there is a deadlock

2. Recovery

  • Terminate one task (choose easiest task to rerun?)
  • Rollback one task (regular checkpoints to restart from?)

3? Resource preemption - Take resource from another task

  • IMPOSSIBLE in most cases
Dynamic Avoidance

Idea: When a resource is requested, decide intelligently whether to grant request

Define states:

  • Safe - for any possible sequence of resource requests, there exists at least one safe sequence of processing the requests that eventually succeeds in granting all pending and future requests
  • Unsafe - exists at least one sequence … that leads to deadlock no matter what order is tried
  • Deadlock

Banker’s Algo

  1. State maximum resource needs in advance
  2. Allocate resources dynamically, when resource is requested
    • Wait if request is : impossible or would lead to unsafe state
  1. Request can be granted only if there exists a sequential ordering of threads that is deadlock free

??

How does “maximum need” work for banking algorithm? what if estimates bad?

Same thing goes for scheduling

🔗 -> Links

Resources

  • Put useful links here

Connections

  • Link all related words

Graph View

Backlinks