What is a deadlock

Question

When writing multi-threaded applications  one of the most common problems experienced are deadlocks     My questions to the community are    What is a deadlock   How do you detect them   Do you handle them    And finally  how do you prevent them from occurring

User · Accepted Answer

A lock occurs when multiple processes try to access the same resource at the same time   One process loses out and must wait for the other to finish   A deadlock occurs when the waiting process is still holding on to another resource that the first needs before it can finish   So  an example   Resource A and resource B are used by process X and process Y   X starts to use A  X and Y try to start using B Y  wins  and gets B first now Y needs to use A A is locked by X  which is waiting for Y   The best way to avoid deadlocks is to avoid having processes cross over in this way  Reduce the need to lock anything as much as you can   In databases avoid making lots of changes to different tables in a single transaction  avoid triggers and switch to optimistic dirty nolock reads as much as possible

User · Answer

Deadlocks does not just occur with locks  although that s the most frequent cause  In C    you can create deadlock with two threads and no locks by just having each thread call join   on the std  thread object for the other

User · Answer

A deadlock is a state of a system in which no single process thread is capable of executing an action  As mentioned by others  a deadlock is typically the result of a situation where each process thread wishes to acquire a lock to a resource that is already locked by another  or even the same  process thread   There are various methods to find them and avoid them  One is thinking very hard and or trying lots of things  However  dealing with parallelism is notoriously difficult and most  if not all  people will not be able to completely avoid problems   Some more formal methods can be useful if you are serious about dealing with these kinds of issues  The most practical method that I m aware of is to use the process theoretic approach  Here you model your system in some process language  e g  CCS  CSP  ACP  mCRL2  LOTOS  and use the available tools to  model- check for deadlocks  and perhaps some other properties as well   Examples of toolset to use are FDR  mCRL2  CADP and Uppaal  Some brave souls might even prove their systems deadlock free by using purely symbolic methods  theorem proving  look for Owicki-Gries    However  these formal methods typically do require some effort  e g  learning the basics of process theory   But I guess that s simply a consequence of the fact that these problems are hard

User · Answer

Deadlocks will only occur when you have two or more locks that can be aquired at the same time and they are grabbed in different order   Ways to avoid having deadlocks are    avoid having locks  if possible    avoid having more than one lock always take the locks in the same order

User · Answer

Lock-based concurrency control Using locking for controlling access to shared resources is prone to deadlocks  and the transaction scheduler alone cannot prevent their occurrences  For instance  relational database systems use various locks to guarantee transaction ACID properties  No matter what relational database system you are using  locks will always be acquired when modifying  e g   UPDATE or DELETE  a certain table record  Without locking a row that was modified by a currently running transaction  Atomicity would be compromised   What is a deadlock A deadlock happens when two concurrent transactions cannot make progress because each one waits for the other to release a lock  as illustrated in the following diagram   Because both transactions are in the lock acquisition phase  neither one releases a lock prior to acquiring the next one  Recovering from a deadlock situation If you re using a Concurrency Control algorithm that relies on locks  then there is always the risk of running into a deadlock situation  Deadlocks can occur in any concurrency environment  not just in a database system  For instance  a multithreading program can deadlock if two or more threads are waiting on locks that were previously acquired so that no thread can make any progress  If this happens in a Java application  the JVM cannot just force a Thread to stop its execution and release its locks  Even if the Thread class exposes a stop method  that method has been deprecated since Java 1 1 because it can cause objects to be left in an inconsistent state after a thread is stopped  Instead  Java defines an interrupt method  which acts as a hint as a thread that gets interrupted can simply ignore the interruption and continue its execution  For this reason  a Java application cannot recover from a deadlock situation  and it is the responsibility of the application developer to order the lock acquisition requests in such a way that deadlocks can never occur  However  a database system cannot enforce a given lock acquisition order since it s impossible to foresee what other locks a certain transaction will want to acquire further  Preserving the lock order becomes the responsibility of the data access layer  and the database can only assist in recovering from a deadlock situation  The database engine runs a separate process that scans the current conflict graph for lock-wait cycles  which are caused by deadlocks   When a cycle is detected  the database engine picks one transaction and aborts it  causing its locks to be released  so that the other transaction can make progress  Unlike the JVM  a database transaction is designed as an atomic unit of work  Hence  a rollback leaves the database in a consistent state

User · Answer

A classic and very simple program for understanding Deadlock situation  -  public class Lazy        private static boolean initialized   false       static           Thread t   new Thread new Runnable                 public void run                     initialized   true                                     t start             try               t join              catch  InterruptedException e                e printStackTrace                         public static void main String   args            System out println initialized             When the main thread invokes Lazy main  it checks whether the class Lazy has been initialized and begins to initialize the class  The main thread now sets initialized to false   creates and starts a background thread whose run method sets initialized to true   and waits for the background thread to complete   This time  the class is currently being initialized by another thread  Under these circumstances  the current thread  which is the background thread  waits on the Class object until initialization is complete  Unfortunately  the thread that is doing the initialization  the main thread  is waiting for the background thread to complete  Because the two threads are now waiting for each other  the program is DEADLOCKED

User · Answer

Deadlock is a common problem in multiprocessing multiprogramming problems in OS  Say there are two processes P1  P2 and two globally shareable resource R1  R2 and in critical section both resources need to be accessed   Initially  the OS assigns R1 to process P1 and R2 to process P2  As both processes are running concurrently they may start executing their code but the PROBLEM arises when a process hits the critical section  So process R1 will wait for process P2 to release R2 and vice versa    So they will wait for forever  DEADLOCK CONDITION             A small ANALOGY          Your Mother OS     You P1     Your brother P2     Apple R1     Knife R2     critical section cutting apple with knife            Your mother gives you the apple and the knife to your brother in the beginning    Both are happy and playing Executing their codes     Anyone of you wants to cut the apple critical section  at some point    You don t want to give the apple to your brother    Your brother doesn t want to give the knife to you    So both of you are going to wait for a long very long time

User · Answer

To define deadlock  first I would define process   Process   As we know process is nothing but a program in execution   Resource   To execute a program process needs some resources  Resource categories may include memory  printers  CPUs  open files  tape drives  CD-ROMS  etc   Deadlock   Deadlock is a situation or condition when two or more processes are holding some resources and trying to acquire some more resources  and they can not release the resources until they finish there execution   Deadlock condition or situation    In the above diagram there are two process P1 and p2 and there are two resources R1 and R2   Resource R1 is allocated to process P1 and resource R2 is allocated to process p2  To complete execution of process P1 needs resource R2  so P1 request for R2  but R2 is already allocated to P2   In the same way  Process P2 to complete its execution needs R1  but R1 is already allocated to P1   both the processes can not release their resource until and unless they complete their execution  So both are waiting for another resources and they will wait forever  So this is a DEADLOCK Condition   In order for deadlock to occur  four conditions must be true    Mutual exclusion - Each resource is either currently allocated to exactly one process or it is available   Two processes cannot simultaneously control the same resource or be in their critical section   Hold and Wait - processes currently holding resources can request new resources  No preemption - Once a process holds a resource  it cannot be taken away by another process or the kernel  Circular wait - Each process is waiting to obtain a resource which is held by another process    and all these condition are satisfied in above diagram

User · Answer

Mutex in essence is a lock  providing protected access to shared resources  Under Linux  the thread mutex data type is pthread mutex t  Before use  initialize it   To access to shared resources  you have to lock on the mutex  If the mutex already on the lock  the call will block the thread until the mutex is unlocked  Upon completion of the visit to shared resources  you have to unlock them   Overall  there are a few unwritten basic principles    Obtain the lock before using the shared resources  Holding the lock as short time as possible  Release the lock if the thread returns an error

User · Answer

You can take a look at this wonderful articles  under section Deadlock  It is in C  but the idea is still the same for other platform  I quote here for easy reading     A deadlock happens when two threads each wait for a resource held by   the other  so neither can proceed  The easiest way to illustrate this   is with two locks    object locker1   new object    object locker2   new object     new Thread       gt                        lock  locker1                                              Thread Sleep  1000                         lock  locker2           Deadlock                                            Start    lock  locker2      Thread Sleep  1000     lock  locker1                               Deadlock

User · Answer

A deadlock occurs when there is a circular chain of threads or processes which each hold a locked resource and are trying to lock a resource held by the next element in the chain  For example  two threads that hold respectively lock A and lock B  and are both trying to acquire the other lock

User · Answer

Let me explain a real world  not actually real  example for a deadlock situation from the crime movies  Imagine a criminal holds an hostage and against that  a cop also holds an hostage who is a friend of the criminal  In this case  criminal is not going to let the hostage go if cop won t let his friend to let go  Also the cop is not going to let the friend of criminal let go  unless the criminal releases the hostage  This is an endless untrustworthy situation  because both sides are insisting the first step from each other   Criminal   Cop Scene    So simply  when two threads needs two different resources and each of them has the lock of the resource that the other need  it is a deadlock   Another High Level Explanation of Deadlock   Broken Hearts  You are dating with a girl and one day after an argument  both sides are heart-broken to each other and waiting for an I-am-sorry-and-I-missed-you call  In this situation  both sides want to communicate each other if and only if one of them receives an I-am-sorry call from the other  Because that neither of each is going to start communication and waiting in a passive state  both will wait for the other to start communication which ends up in a deadlock situation

User · Answer

Deadlock occurs when two threads aquire locks which prevent either of them from progressing  The best way to avoid them is with careful development  Many embedded systems protect against them by using a watchdog timer  a timer which resets the system whenever if it hangs for a certain period of time

User · Answer

A deadlock happens when a thread is waiting for something that never occurs   Typically  it happens when a thread is waiting on a mutex or semaphore that was never released by the previous owner   It also frequently happens when you have a situation involving two threads and two locks like this   Thread 1               Thread 2  Lock1- gt Lock            Lock2- gt Lock    WaitForLock2           WaitForLock1       lt -- Oops    You generally detect them because things that you expect to happen never do  or the application hangs entirely

User · Answer

Above some explanations are nice  Hope this may also useful  https   ora-data blogspot in 2017 04 deadlock-in-oracle html  In a database  when a session  e g  ora  wants a resource held by another session  e g  data   but that session  data  also wants a resource which is held by the first session  ora   There can be more than 2 sessions involved also but idea will be the same  Actually  Deadlocks prevent some transactions from continuing to work  For example  Suppose  ORA-DATA holds lock A and requests lock B And SKU holds lock B and requests lock A   Thanks

User · Answer

Deadlock is a situation occurs when there is less number of available resources as it is requested by the different process  It means that when the number of available resources become less than it is requested by the user then at that time the process goes in waiting condition  Some times waiting increases more and there is not any chance to check out the problem of lackness of resources then this situation is known as deadlock                      Actually  deadlock is a major problem for us and it occurs only in multitasking operating system  deadlock can not occur in single tasking operating system because all the resources are present only for that task which is currently running

User · Answer

Deadlock occurs when a thread is waiting for other thread to finish and vice versa      How to avoid                   - Avoid Nested Locks  - Avoid Unnecessary Locks  - Use thread join    How do you detect it  run this command in cmd     jcmd  PID Thread print   reference   geeksforgeeks

[multithreading] What is a deadlock?

Examples related to multithreading

Examples related to concurrency

Examples related to locking

Examples related to deadlock