Operating Systems
COMP 3430 Guderian
Copyright By PowCoder代写 加微信 powcoder
Avoiding deadlock
Conditions
4 conditions for deadlock
Mutual exclusion Hold-and-wait No preemption Circular wait
Prevent ONE, and no deadlock can occur
Prevent mutex lock
Ask yourself some questions
Prevent mutex lock
Ask yourself some questions Can I lock smaller elements?
Prevent mutex lock
Ask yourself some questions
Can I lock smaller elements? Does THIS need to be locked?
Prevent mutex lock
Ask yourself some questions
Can I lock smaller elements? Does THIS need to be locked? Does this NEED to be locked?
Prevent mutex lock
Ask yourself some questions
Can I lock smaller elements? Does THIS need to be locked? Does this NEED to be locked? Is there a lock-free solution?
Prevent hold-and-wait
Get all locks at once, atomically
Prevent hold-and-wait
Get all locks at once, atomically
If we can¡¯t get them all, give them all up. Sleep, hoping they will become available
Prevent hold-and-wait
Get all locks at once, atomically
If we can¡¯t get them all, give them all up. Sleep, hoping they will become available
Terrible, but easy
Prevent hold-and-wait
Get all locks at once, atomically
If we can¡¯t get them all, give them all up. Sleep, hoping they will become available
Terrible, but easy
We saw this with spin locks
Prevent hold-and-wait
Get all locks at once, atomically
If we can¡¯t get them all, give them all up. Sleep, hoping they will become available
Terrible, but easy
We saw this with spin locks
Or, list up-front what we need, don¡¯t wake until all locks are available
Prevent hold-and-wait
Get all locks at once, atomically
If we can¡¯t get them all, give them all up. Sleep, hoping they will become available
Terrible, but easy
We saw this with spin locks
Or, list up-front what we need, don¡¯t wake until all locks are available
Unrealistic!
Prevent ¡°no preemption¡±
Allow preemption! Take locks away from deadlocked processes
Prevent ¡°no preemption¡±
Allow preemption! Take locks away from deadlocked processes
Prevent ¡°no preemption¡±
Allow preemption! Take locks away from deadlocked processes
How do we preempt a process that is holding a lock?
Prevent ¡°no preemption¡±
Allow preemption! Take locks away from deadlocked processes
How do we preempt a process that is holding a lock?
It¡¯s unsafe!
Prevent ¡°no preemption¡±
Allow preemption! Take locks away from deadlocked processes
How do we preempt a process that is holding a lock?
It¡¯s unsafe!
pthread_mutex_trylock – don¡¯t have to be preempted!
Prevent circular wait
This is where we can be clever! This is preventing livelock.
Prevent circular wait
This is where we can be clever! This is preventing livelock.
Can we… Always lock in a certain order?
Prevent circular wait
This is where we can be clever! This is preventing livelock.
Always lock in a certain order?
ALWAYS lock L1, then L2, would never have L2 locked without L1
Prevent circular wait
This is where we can be clever! This is preventing livelock.
Always lock in a certain order?
ALWAYS lock L1, then L2, would never have L2 locked without L1
Called Partial ordering
Prevent circular wait
This is where we can be clever! This is preventing livelock.
Always lock in a certain order?
ALWAYS lock L1, then L2, would never have L2 locked without L1
Called Partial ordering
Draw the resource dependency graph
Other deadlock avoidance
Scheduling:
Other deadlock avoidance
Scheduling:
Never schedule P1 and P2 at the same time (multi- CPU)
Other deadlock avoidance
Scheduling:
Never schedule P1 and P2 at the same time (multi- CPU)
Clean up locks before context switch
Other deadlock avoidance
Scheduling:
Never schedule P1 and P2 at the same time (multi- CPU)
Clean up locks before context switch
Wait, we can¡¯t control that
Other deadlock avoidance
Detect and Recover – This is real-world
Other deadlock avoidance
Detect and Recover – This is real-world Use an outside process to monitor for deadlocks
Other deadlock avoidance
Detect and Recover – This is real-world
Use an outside process to monitor for deadlocks If all processes are blocked, kill one
Other deadlock avoidance
Detect and Recover – This is real-world
Use an outside process to monitor for deadlocks If all processes are blocked, kill one
Or, send a signal (SIGUSR1?) which tells one process to drop locks?
Concurrency, conclusion
Locks are difficult to make
Deadlock is hard to avoid
Resources are hard to manage
The OS manages locks, to aide with concurrency
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com