Read on Twitter
Let's talk about the nightmare of concurrency: Deadlock 
In this thread, we will go through what is a Deadlock, required conditions, ways to handle it, and use cases.
A colleague rejected a candidate 3 days ago, in part, because he couldn't answer this!
Thread
In this thread, we will go through what is a Deadlock, required conditions, ways to handle it, and use cases.
A colleague rejected a candidate 3 days ago, in part, because he couldn't answer this!
Thread
A deadlock occurs when each consumer of a group is waiting for another consumer to release a locked resource to be able to finish its task with all the resources it needs.
Sounds confusing right? Let's use an analogy.
Sounds confusing right? Let's use an analogy.
Analogy
You and your friend want to make a sandwich. Both need a slice of bread, you prefer to go for the knife, your friend goes for the loaf of bread.
Now each one has 1 of the 2 things & neither is giving up waiting for the other to release it
Deadlock and no sandwich.
You and your friend want to make a sandwich. Both need a slice of bread, you prefer to go for the knife, your friend goes for the loaf of bread.
Now each one has 1 of the 2 things & neither is giving up waiting for the other to release it
Deadlock and no sandwich.
Operating Systems
A deadlock occurs when a process or a thread enters a waiting state because the requested resource to the OS is held by another process waiting for another resource that is being held.
This field is studied in most CS courses, and it is very fun!
A deadlock occurs when a process or a thread enters a waiting state because the requested resource to the OS is held by another process waiting for another resource that is being held.
This field is studied in most CS courses, and it is very fun!
Necessary Conditions
A deadlock can happen if and only if all of these conditions hold simultaneously:
1_ Mutual Exclusion: At least 1 resource must be held, non-shareable.
2_ Hold and wait: A process is holding a resource & requesting more being held
A deadlock can happen if and only if all of these conditions hold simultaneously:
1_ Mutual Exclusion: At least 1 resource must be held, non-shareable.
2_ Hold and wait: A process is holding a resource & requesting more being held
3_ No preemption: A resource can be released only voluntarily
4_ Circular wait: Each process must be waiting for a resource being held by another process, which is waiting for the 1st to release it
These conditions are sufficient, only indicate the possibility of a deadlock
4_ Circular wait: Each process must be waiting for a resource being held by another process, which is waiting for the 1st to release it
These conditions are sufficient, only indicate the possibility of a deadlock
Deadlock Handling
1) Ignore deadlock: Basically, you assume that a deadlock will never happen, fingers crossed
2) Detection: An algorithm tracks resources allocation and process states and rolls back and restarts one or more processors to recover from a deadlock
1) Ignore deadlock: Basically, you assume that a deadlock will never happen, fingers crossed
2) Detection: An algorithm tracks resources allocation and process states and rolls back and restarts one or more processors to recover from a deadlock
3) Prevention: Works by preventing 1 of the 4 conditions we studied above. You can remove mutual exclusion, that means no process has exclusive access to a resource (not feasible in many cases)
Remove hold and wait, process has to request all resources at start, inefficient
Remove hold and wait, process has to request all resources at start, inefficient
Remove no preemption is difficult or impossible since you would remove resources when a process is using it.
Remove circular wait, can be done via disabling interrupts during critical sections, and using a hierarchy to determine partial ordering of resources.
Remove circular wait, can be done via disabling interrupts during critical sections, and using a hierarchy to determine partial ordering of resources.
Use cases:
- Working with threads and shared resources.
- Databases, when transactions lock a table and need a second lock to complete itself that is already locked.
- Distributed systems (components are located on different networked computers, which communicate via messages)
- Working with threads and shared resources.
- Databases, when transactions lock a table and need a second lock to complete itself that is already locked.
- Distributed systems (components are located on different networked computers, which communicate via messages)
2 bonus use cases are:
- Pass an exam in Computer Science
- Pass an interview
I hope you enjoyed it and learned a couple of things about Deadlocks.
Thanks for reading!
- Pass an exam in Computer Science
- Pass an interview
I hope you enjoyed it and learned a couple of things about Deadlocks.
Thanks for reading!
