A set of processes is deadlocked if each process in the set is waiting for an event that can be caused by another process in the set. The events that we are mainly concerned with are resource acquisition and release. The resources may be physical resources (CPU, I/O devices, memory) or logical resources (files, semaphores or monitors).
A resource might be Preemptable or non-preemptable.
Preemptable meaning that without harm, the resource can be borrowed form the process. Sometimes a resource can be made preemptable by the OS at some cost. Example: Memory can be preempted from a process by suspending the process and copying the contents of the memory to disk. Later the data is copied back to the memory
And the process is allowed to continue. Preemption effectively makes a serially reusable resource look sharable.
A non-preemptable resource is one that without causing undesirable efforts, cannot be taken away from the current user.
Deadlock involves non-preemptable resources.
So, deadlock can arise if 4 conditions hold simultaneously:
Deadlock is more precisely described in terms of a directed graph called Resource allocation graph. It consists of a set of all active processes and resource types in the system. Processes are described by circles and resources by squares connected by appropriate directed arrows depending on whether a resource is requested by a process or is holding on it.
If a graph contains a cycle then:
Ensure that at least one of the necessary conditions does not hold.
The simplest and most useful model requires that each process declares the maximum number of resources of each type that it may need. The deadlock avoidance algorithm dynamically examines the resource allocation state to ensure that there can never be a circular wait condition. Resource allocation state is defined by the number of available and allocated resources and the maximum demands of the processes.
The following parameters need to be examined before deciding which process to terminate:
The scariest thing that can happen to a java program is deadlock. It is a special type of error that you need to avoid that relates specifically to multitasking which occurs when two threads have a circular dependency on a pair of synchronized objects. This occurs when two threads are blocked, with each waiting for the other’s lock. Neither can run until the other gives up its lock so they’ll sit there forever. For example, suppose one thread enters the monitor on object X and another thread enters the monitor on object Y. If the thread in X tries to call any synchronized method on Y, it will block as expected. However, if the thread in Y, in turn, tries to call any synchronized method on X, the thread waits forever, because to access X, it would have to release its own lock on Y so that the first thread could complete.
Deadlock is a difficult error to debug for two reasons:-
This example creates two classes, Dead1 and Dead2, with methods m1( ) and m2( ), respectively, which pause briefly before trying to call a method in the other class. The main class, named Deadlock, creates an Dead1 and a Dead2 instance, and then starts a second thread to set up the deadlock condition. The m1() and m2( ) methods use sleep( ) as a way to force the deadlock condition to occur.
MainThread entered Dead1.m1
RacingThread entered Dead2.m2
MainThread trying to call Dead2.last()
RacingThread trying to call Dead1.last()
Because the program has deadlocked, you need to press CTRL-C to end the program. You can see a full thread and monitor cache dump by pressing CTRL-BREAK on a PC . You will see that RacingThread owns the monitor on b, while it is waiting for the monitor on a. At the same time, MainThread owns a and is waiting to get b. This program will never complete. If a multithreaded program locks up occasionally, deadlock is one of the first conditions that should be checked for.
Another Example that demonstrates deadlock:
When several transactions occur concurrently in the database the isolation property may no longer be preserved. To ensure that it is preserved the system must control the interaction among the concurrent transactions. Such mechanisms are called concurrency- control schemes. One of such scheme is based on the serializability property. One way to ensure serializability is to require that data items be accessed in a mutually exclusive manner. That is while one transaction is accessing a data item no other transaction can modify that data item. The most common method used to implement this is to allow a transaction to access a data item only if it is currently holding a lock on that item.
Lock is a variable associated with a data item that describes the status of the data item with respect to the possible operations that can be applied to it.
There are various modes in which a data item may be locked. But we restrict our attention to two modes:
Shared:- If a transaction T1 has obtained a lock a shared mode lock (denoted by S) on an item Q then T1 can read but cannot write Q.
Exclusive:- If a transaction T1 has obtained a lock a exclusive mode lock (denoted by X) on an item Q then T1 can both read write and Q.
It is required that every transaction request a lock in an appropriate mode on data item Q depending on the types of operation that will be performed on Q.
But unfortunately locking can lead to an undesirable situation. Consider two transactions T1 and T2. T1 is holding an exclusive lock on a data item B. T2 is holding a shared mode lock on a data item A. Now T2 requests a shared mode lock on B. It is waiting for T1 to unlock B. T1 requests an exclusive mode lock on A. So T1 is waiting for T2 to unlock A. So a situation has arrived where neither of these transactions can ever proceed with its normal execution. This situation is called deadlock. When deadlock occurs the system must rollback one of these two transactions. Once a transaction has been rolled back the items that were locked by that transaction are unlocked. These data items are then available to the other transaction which can then continue with its execution.
UPDATE ACCT_MSTR SET CURBAL=500 WHERE ACCT_NO=’SB1’;
UPDATE ACCT_MSTR SET CURBAL=2500 WHERE ACCT_NO=’CA2’
UPDATE ACCT_MSTR SET CURBAL=5000 WHERE ACCT_NO=’CA2’;
UPDATE ACCT_MSTR SET CURBAL=3500 WHERE ACCT_NO=’SB1’
When such a situation is detected by the Oracle Engine both update statements are rolled back automatically and the deadlock is resolved.
If you liked this article do nominate this article for Article of the month - May 2010
Locks and Sleeps are things you should never use. The software I develop is fully event based and has no locks. This is especially important for daemons or other server software that needs high availability.
|All times are GMT +5.5. The time now is 13:57.|