Read on Twitter
Let& #39;s talk about the nightmare of concurrency: Deadlock 
https://abs.twimg.com/emoji/v2/... draggable="false" alt="☠️" title="Totenkopf" aria-label="Emoji: Totenkopf">
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& #39;t answer this!
https://abs.twimg.com/emoji/v2/... draggable="false" alt="🧵" title="Thread" aria-label="Emoji: Thread">Threadhttps://abs.twimg.com/emoji/v2/... draggable="false" alt="🧵" title="Thread" aria-label="Emoji: 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& #39;t answer this!
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& #39;s use an analogy.
https://abs.twimg.com/emoji/v2/... draggable="false" alt="👇" title="Rückhand Zeigefinger nach unten" aria-label="Emoji: Rückhand Zeigefinger nach unten">
Sounds confusing right? Let& #39;s use an analogy.
" title="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& #39;s use an analogy.https://abs.twimg.com/emoji/v2/... draggable="false" alt="👇" title="Rückhand Zeigefinger nach unten" aria-label="Emoji: Rückhand Zeigefinger nach unten">" class="img-responsive" style="max-width:100%;"/>
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.
https://abs.twimg.com/emoji/v2/... draggable="false" alt="👇" title="Rückhand Zeigefinger nach unten" aria-label="Emoji: Rückhand Zeigefinger nach unten">
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.
" title="AnalogyYou 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 itDeadlock and no sandwich.https://abs.twimg.com/emoji/v2/... draggable="false" alt="👇" title="Rückhand Zeigefinger nach unten" aria-label="Emoji: Rückhand Zeigefinger nach unten">" class="img-responsive" style="max-width:100%;"/>
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!
https://abs.twimg.com/emoji/v2/... draggable="false" alt="👇" title="Rückhand Zeigefinger nach unten" aria-label="Emoji: Rückhand Zeigefinger nach unten">
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
https://abs.twimg.com/emoji/v2/... draggable="false" alt="👇" title="Rückhand Zeigefinger nach unten" aria-label="Emoji: Rückhand Zeigefinger nach unten">
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
" title="Necessary ConditionsA 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 heldhttps://abs.twimg.com/emoji/v2/... draggable="false" alt="👇" title="Rückhand Zeigefinger nach unten" aria-label="Emoji: Rückhand Zeigefinger nach unten">" class="img-responsive" style="max-width:100%;"/>
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
https://abs.twimg.com/emoji/v2/... draggable="false" alt="👇" title="Rückhand Zeigefinger nach unten" aria-label="Emoji: Rückhand Zeigefinger nach unten">
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 crossedhttps://abs.twimg.com/emoji/v2/... draggable="false" alt="🤞" title="Crossed fingers" aria-label="Emoji: Crossed fingers">
2) Detection: An algorithm tracks resources allocation and process states and rolls back and restarts one or more processors to recover from a deadlock
https://abs.twimg.com/emoji/v2/... draggable="false" alt="👇" title="Rückhand Zeigefinger nach unten" aria-label="Emoji: Rückhand Zeigefinger nach unten">
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
https://abs.twimg.com/emoji/v2/... draggable="false" alt="👇" title="Rückhand Zeigefinger nach unten" aria-label="Emoji: Rückhand Zeigefinger nach unten">
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.
https://abs.twimg.com/emoji/v2/... draggable="false" alt="👇" title="Rückhand Zeigefinger nach unten" aria-label="Emoji: Rückhand Zeigefinger nach unten">
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)
https://abs.twimg.com/emoji/v2/... draggable="false" alt="👇" title="Rückhand Zeigefinger nach unten" aria-label="Emoji: Rückhand Zeigefinger nach unten">
- 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 interviewhttps://abs.twimg.com/emoji/v2/... draggable="false" alt="😉" title="Zwinkerndes Gesicht" aria-label="Emoji: Zwinkerndes Gesicht">
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!
I hope you enjoyed it and learned a couple of things about Deadlocks.Thanks for reading!" title="2 bonus use cases are:- Pass an exam in Computer Science- Pass an interview https://abs.twimg.com/emoji/v2/... draggable="false" alt="😉" title="Zwinkerndes Gesicht" aria-label="Emoji: Zwinkerndes Gesicht">I hope you enjoyed it and learned a couple of things about Deadlocks.Thanks for reading!" class="img-responsive" style="max-width:100%;"/>
