My Profile
Gifts
Active Members
TodayLast 7 Days
more...
|
What is Deadlock?
Posted Date:
25 Jul 2008
Total Responses:
10
|
Posted By: venkat Member Level: Gold Points: 1
|
Hi,
What is Deadlock?How to prevent the Deadlock?Any one give me the good notes plz...
Regards,
venkat.
|
Responses
|
| Author: chandramohan 25 Jul 2008 | Member Level: Gold | Rating:  Points: 1 | When multi-transaction mode is in effect across multiple DBEnvironments with multiple applications accessing the same DBEnvironments at the same time, it is possible that a deadlock that cannot be detected by ALLBASE/SQL could occur. This is known as an undetectable deadlock. In addition, when multi-transaction mode is used with multiple connections to the same DBEnvironment, an infinite wait can occur. To avoid these situations, be sure your timeout values are set to a value other than NONE. (Note that NONE is the default when no timeout value is specified at DBEnvironment creation time.)
Undetectable Deadlock Prevention
Suppose your application is simultaneously connected to two DBEnvironments in multi-transaction mode. At the same time, another user's application is connected to the same DBEnvironments. At some point as these applications execute, each one has an active transaction waiting for access to data locked by another transaction in the other application. It is a classic deadlock, and since the data being waited for spans more than one DBEnvironment, ALLBASE/SQL cannot detect this deadlock. The two databases will wait "forever" unless you have set a TIMEOUT value other than NONE for one or both of the application connections.
Infinite Wait Prevention
An application running in multi-transaction mode with multiple active transactions accessing data in the same DBEnvironment can encounter undetectable wait conditions. For instance, the first of two such transactions could be holding locks that cannot be released until the transaction is commited. And the second transaction could require the same locks in order to complete. The second transaction is waiting for the first to commit work, and the first transaction is waiting for the second to return control so that it can commit. Since both transactions are part of the same process, ALLBASE/SQL cannot detect this situation. Unless timeouts are set for at least one of these transactions, they could wait infinitely.
It may not be possible to predict an undetectable wait. Even when the transactions involved are accessing different tables, the physical proximity of system catalog data could mean that locks held by transaction one are required by transaction two. This is particularly true in relation to DDL statements (including the UPDATE STATISTICS statement, even though it is allowed in DML only mode) and dynamic space expansion.
To prevent an infinite wait, be sure to set appropriate timeout values and test for the occurrence of a timeout.
---------------
A deadlock is a situation wherein two or more competing actions are waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like 'the chicken or the egg'.” says Wikipedia and yes :) they are right. In SQL world deadlock refers to a specific condition when two or more queries are waiting for each other to release a datatable or a row. Actually we can’t prevent a deadlock in many situations but we can handle them by SQL 2005 TRY/CATCH blocks.
RETRY:
BEGIN TRY
BEGIN TRANSACTION
-- DO SOME BAD ACTION CAUSING DEADLOCK
COMMIT TRANSACTION
END TRY
BEGIN CATCH
SET @Err = @@ERROR
IF @Err = 1205
ROLLBACK TRANSACTION
INSERT INTO ErrorLog (ErrID, ErrMsg)
VALUES (@Err, 'Deadlock recovery attempt.')
WAITFOR DELAY '00:00:10'
GOTO RETRY
IF @Err = 2627
SET @ErrMsg = 'PK Violation.'
IF @ErrMsg IS NULL
SET @ErrMsg = 'Other Error.'
INSERT INTO ErrorLog (ErrID, ErrMsg)
VALUES (@Err, @ErrMsg)
END CATCH
TRY/CATCH block will catch errors and IF blocks will check what kind of error is happened. If that is a deadlock error we cancel our current transaction and use WAITFOR function to wait for 10 seconds to retry our query. This is actually an endless loop till there is no deadlock error. Notice that we are logging each error to an error table to check what’s happening.
In conclusion, deadlocks are easy to handle and be logged in SQL 2005 with TRY/CATCH blocks. In the other hand I would suggest you to check logs and analyze what’s causing deadlock and prevent getting deadlocks if possible without TRY/CATCH blocks :) for better performance.
------------------
SQL Deadlocks
When SQL deadlocks occur, your server’s performance slows down and suffers. Deadlocks can use up your SQL server’s resources and CPU power is wasted. Such server problems can also cause confusion to your users. SQL server deadlocks ultimately cost your business money as it drags server performance down.
SQL Solutions’ SQL Deadlock Detector is a SQL server performance tuning tool developed to help you solve your server deadlock problems. By allowing you to do the things you need to do to eliminate server deadlocks, SQL Deadlock Detector is the fastest, easiest way to a smooth-running SQL server.
With SQL Deadlock Detector, you can;
Monitor and detect long-running locks and deadlocks 24/7
Identify blocking SQL code, locked objects and deadlock victims with pinpoint accuracy
Zero impact SQL server tool
Accelerate system response time by reducing long lock waits
---------------------
You may need to write code that acquires more than one lock. This opens up the possibility of deadlock. Consider the following piece of code:
Lock *l1, *l2;
void p() {
l1->Acquire();
l2->Acquire();
code that manipulates data that l1 and l2 protect
l2->Release();
l1->Release();
}
void q() {
l2->Acquire();
l1->Acquire();
code that manipulates data that l1 and l2 protect
l1->Release();
l2->Release();
}
If p and q execute concurrently, consider what may happen. First, p acquires l1 and q acquires l2. Then, p waits to acquire l2 and q waits to acquire l1. How long will they wait? Forever.
This case is called deadlock. What are conditions for deadlock?
Mutual Exclusion: Only one thread can hold lock at a time.
Hold and Wait: At least one thread holds a lock and is waiting for another process to release a lock.
No preemption: Only the process holding the lock can release it.
Circular Wait: There is a set t1, ..., tn such that t1 is waiting for a lock held by t2, ..., tn is waiting for a lock held by t1.
How can p and q avoid deadlock? Order the locks, and always acquire the locks in that order. Eliminates the circular wait condition.
Occasionally you may need to write code that needs to acquire locks in different orders. Here is what to do in this situation.
First, most locking abstractions offer an operation that tries to acquire the lock but returns if it cannot. We will call this operation TryAcquire. Use this operation to try to acquire the lock that you need to acquire out of order.
If the operation succeeds, fine. Once you've got the lock, there is no problem.
If the operation fails, your code will need to release all locks that come after the lock you are trying to acquire. Make sure the associated data structures are in a state where you can release the locks without crashing the system.
Release all of the locks that come after the lock you are trying to acquire, then reacquire all of the locks in the right order. When the code resumes, bear in mind that the data structures might have changed between the time when you released and reacquired the lock.
Here is an example.
int d1, d2;
// The standard acquisition order for these two locks
// is l1, l2.
Lock *l1, // protects d1
*l2; // protects d2
// Decrements d2, and if the result is 0, increments d1
void increment() {
l2->Acquire();
int t = d2;
t--;
if (t == 0) {
if (l1->TryAcquire()) {
d1++;
} else {
// Any modifications to d2 go here - in this case none
l2->Release();
l1->Acquire();
l2->Acquire();
t = d2;
t--;
// some other thread may have changed d2 - must recheck it
if (t == 0) {
d1++;
}
}
l1->Release();
}
d2 = t;
l2->Release();
}
This example is somewhat contrived, but you will recognize the situation when it occurs.
There is a generalization of the deadlock problem to situations in which processes need multiple resources, and the hardware may have multiple kinds of each resource - two printers, etc. Seems kind of like a batch model - processes request resources, then system schedules process to run when resources are available.
In this model, processes issue requests to OS for resources, and OS decides who gets which resource when. A lot of theory built up to handle this situation.
Process first requests a resource, the OS issues it and the process uses the resource, then the process releases the resource back to the OS.
Reason about resource allocation using resource allocation graph. Each resource is represented with a box, each process with a circle, and the individual instances of the resources with dots in the boxes. Arrows go from processes to resource boxes if the process is waiting for the resource. Arrows go from dots in resource box to processes if the process holds that instance of the resource. See Fig. 7.1.
If graph contains no cycles, is no deadlock. If has a cycle, may or may not have deadlock. See Fig. 7.2, 7.3.
System can either
Restrict the way in which processes will request resources to prevent deadlock.
Require processes to give advance information about which resources they will require, then use algorithms that schedule the processes in a way that avoids deadlock.
Detect and eliminate deadlock when it occurs.
First consider prevention. Look at the deadlock conditions listed above.
Mutual Exclusion - To eliminate mutual exclusion, allow everybody to use the resource immediately if they want to. Unrealistic in general - do you want your printer output interleaved with someone elses?
Hold and Wait. To prevent hold and wait, ensure that when a process requests resources, does not hold any other resources. Either asks for all resources before executes, or dynamically asks for resources in chunks as needed, then releases all resources before asking for more. Two problems - processes may hold but not use resources for a long time because they will eventually hold them. Also, may have starvation. If a process asks for lots of resources, may never run because other processes always hold some subset of the resources.
Circular Wait. To prevent circular wait, order resources and require processes to request resources in that order.
Deadlock avoidance. Simplest algorithm - each process tells max number of resources it will ever need. As process runs, it requests resources but never exceeds max number of resources. System schedules processes and allocates resoures in a way that ensures that no deadlock results.
Example: system has 12 tape drives. System currently running P0 needs max 10 has 5, P1 needs max 4 has 2, P2 needs max 9 has 2.
Can system prevent deadlock even if all processes request the max? Well, right now system has 3 free tape drives. If P1 runs first and completes, it will have 5 free tape drives. P0 can run to completion with those 5 free tape drives even if it requests max. Then P2 can complete. So, this schedule will execute without deadlock.
If P2 requests two more tape drives, can system give it the drives? No, because cannot be sure it can run all jobs to completion with only 1 free drive. So, system must not give P2 2 more tape drives until P1 finishes. If P2 asks for 2 tape drives, system suspends P2 until P1 finishes.
Concept: Safe Sequence. Is an ordering of processes such that all processes can execute to completion in that order even if all request maximum resources. Concept: Safe State - a state in which there exists a safe sequence. Deadlock avoidance algorithms always ensure that system stays in a safe state.
How can you figure out if a system is in a safe state? Given the current and maximum allocation, find a safe sequence. System must maintain some information about the resources and how they are used. See OSC 7.5.3.
Avail[j] = number of resource j available
Max[i,j] = max number of resource j that process i will use
Alloc[i,j] = number of resource j that process i currently has
Need[i,j] = Max[i,j] - Alloc[i,j]
Notation: A<=B if for all processes i, A[i]<=B[i].
Safety Algorithm: will try to find a safe sequence. Simulate evolution of system over time under worst case assumptions of resource demands.
1: Work = Avail;
Finish[i] = False for all i;
2: Find i such that Finish[i] = False and Need[i] <= Work
If no such i exists, goto 4
3: Work = Work + Alloc[i]; Finish[i] = True; goto 2
4: If Finish[i] = True for all i, system is in a safe state
Now, can use safety algorithm to determine if we can satisfy a given resource demand. When a process demands additional resources, see if can give them to process and remain in a safe state. If not, suspend process until system can allocate resources and remain in a safe state. Need an additional data structure:
Request[i,j] = number of j resources that process i requests
Here is algorithm. Assume process i has just requested additional resources.
1: If Request[i] <= Need[i] goto 2. Otherwise, process has
violated its maximum resource claim.
2: If Request[i] <= Avail goto 3. Otherwise, i must wait
because resources are not available.
3: Pretend to allocate resources as follows:
Avail = Avail - Request[i]
Alloc[i] = Alloc[i] + Request[i]
Need[i] = Need[i] - Request[i]
If this is a safe state, give the process the resources. Otherwise,
suspend the process and restore the old state.
When to check if a suspended process should be given the resources and resumed? Obvious choice - when some other process relinquishes its resources. Obvious problem - process starves because other processes with lower resource requirements are always taking freed resources.
See Example in Section 7.5.3.3.
Third alternative: deadlock detection and elimination. Just let deadlock happen. Detect when it does, and eliminate the deadlock by preempting resources.
Here is deadlock detection algorithm. Is very similar to safe state detection algorithm.
1: Work = Avail;
Finish[i] = False for all i;
2: Find i such that Finish[i] = False and Request[i] <= Work
If no such i exists, goto 4
3: Work = Work + Alloc[i]; Finish[i] = True; goto 2
4: If Finish[i] = False for some i, system is deadlocked.
Moreover, Finish[i] = False implies that process i is deadlocked.
When to run deadlock detection algorithm? Obvious time: whenever a process requests more resources and suspends. If deadlock detection takes too much time, maybe run it less frequently.
OK, now you've found a deadlock. What do you do? Must free up some resources so that some processes can run. So, preempt resources - take them away from processes. Several different preemption cases:
Can preempt some resources without killing job - for example, main memory. Can just swap out to disk and resume job later.
If job provides rollback points, can roll job back to point before acquired resources. At a later time, restart job from rollback point. Default rollback point - start of job.
For some resources must just kill job. All resources are then free. Can either kill processes one by one until your system is no longer deadlocked. Or, just go ahead and kill all deadlocked processes.
In a real system, typically use different deadlock strategies for different situations based on resource characteristics.
This whole topic has a sort of 60's and 70's batch mainframe feel to it. How come these topics never seem to arise in modern Unix systems
-----------
condition that occurs when two processes are each waiting for the other to complete before proceeding. The result is that both processes hang. Deadlocks occur most commonly in multitasking and client/server environments. Ideally, the programs that are deadlocked, or the operating system, should resolve the deadlock, but this doesn't always happen.
A deadlock is also called a deadly embrace.
----------
Deadlock prevention methods guarantee that deadlocks cannot occur in the first place. Thus the transactions manager checks a transaction when it is first initiated and does not permit it to precede it may cause a deadlock. To perform this check, it is require that all of the data items that will be accessed, by a transaction be predeclared. The transactions manager then permits a transactions be predeclared. The transaction manager then permits a transaction to proceed if all the data items that it will access are available. Otherwise, the transaction is not permitted to proceed. The transaction manager reserves all the data items that are predeclared by a transaction that it allows proceeding.
Unfortunately such systems are not very suitable for database environments. The fundamental problem is that it is usually difficult to know precisely which data items will be accessed by a transaction. Access to certain data item may depend upon condition that may not be resolved until run time. To be safe system needs to be chose maximum sets of times. Even if they end up not being accessed this would certainly reduced concurrency. Furthermore there is additional overhead in evaluating whether a transaction can proceed safely. On the other hand such systems do not require run-time support.
-------------
Definition: deadlock: n. 1. [techspeak] A situation wherein two or more processes are unable to proceed because each is waiting for one of the others to do something. A common example is a program communicating to a server, which may find itself waiting for output from the server before sending anything more to it, while the server is similarly waiting for more input from the controlling program before outputting anything. (It is reported that this particular flavor of deadlock is sometimes called a `starvation deadlock', though the term `starvation' is more properly used for situations where a program can never run simply because it never gets high enough priority. Another common flavor is `constipation', in which each process is trying to send stuff to the other but all buffers are full because nobody is reading anything.) See deadly embrace. 2. Also used of deadlock-like interactions between humans, as when two people meet in a narrow corridor, and each tries to be polite by moving aside to let the other pass, but they end up swaying from side to side without making any progress because they always move the same way at the same time.
| | Author: UltimateRengan 25 Jul 2008 | Member Level: Diamond | Rating: Points: 1 | A deadlock is a situation in which two computer programs sharing the same resource are effectively preventing each other from accessing the resource, resulting in both programs ceasing to function.
The earliest computer operating systems ran only one program at a time. All of the resources of the system were available to this one program. Later, operating systems ran multiple programs at once, interleaving them. Programs were required to specify in advance what resources they needed so that they could avoid conflicts with other programs running at the same time. Eventually some operating systems offered dynamic allocation of resources. Programs could request further allocations of resources after they had begun running. This led to the problem of the deadlock. Here is the simplest example:
Program 1 requests resource A and receives it.
Program 2 requests resource B and receives it.
Program 1 requests resource B and is queued up, pending the release of B.
Program 2 requests resource A and is queued up, pending the release of A.
http://searchcio-midmarket.techtarget.com/sDefinition/0,,sid183_gci211913,00.html
| | Author: Lakshmankumar M 25 Jul 2008 | Member Level: Gold | Rating: Points: 6 | An error with the computer that occurs when two programs are trying to wait for a signal from the other program at the same time
Deadlocking occurs when two user processes have locks on separate objects and each process is trying to acquire a lock on the object that the other process has. When this happens, SQL Server identifies the problem and ends the deadlock by automatically choosing one process and aborting the other process, allowing the other process to continue. The aborted transaction is rolled back and an error message is sent to the user of the aborted process. Generally, the transaction that requires the least amount of overhead to rollback is the transaction that is aborted.
Program 1 requests resource A and receives it.
Program 2 requests resource B and receives it.
Program 1 requests resource B and is queued up, pending the release of B.
Program 2 requests resource A and is queued up, pending the release of A.
| | Author: Ashok 25 Jul 2008 | Member Level: Gold | Rating: Points: 1 | A deadlock is a situation wherein two or more competing actions are waiting for the other to finish, and thus neither ever does.
deadlock refers to a specific condition when two or more processes are each waiting for another to release a resource, or more than two processes are waiting for resources in a circular chain (see Necessary conditions). Deadlock is a common problem in multiprocessing where many processes share a specific type of mutually exclusive resource known as a software, or soft, lock. Computers intended for the time-sharing and/or real-time markets are often equipped with a hardware lock (or hard lock) which guarantees exclusive access to processes, forcing serialization. Deadlocks are particularly troubling because there is no general solution to avoid (soft) deadlocks.
| | Author: Ashok 25 Jul 2008 | Member Level: Gold | Rating: Points: 1 | Necessary conditions
There are four necessary conditions for a deadlock to occur,
1. Mutual exclusion condition: a resource that cannot be used by more than one process at a time
2. Hold and wait condition: processes already holding resources may request new resources
3. No preemption condition: only a process holding a resource may release it
4. Circular wait condition: two or more processes form a circular chain where each process waits for a resource that the next process in the chain holds
Avoidance
Deadlock can be avoided if certain information about processes is available in advance of resource allocation. For every resource request, the system sees if granting the request will mean that the system will enter an unsafe state, meaning a state that could result in deadlock. The system then only grants requests that will lead to safe states. In order for the system to be able to figure out whether the next state will be safe or unsafe, it must know in advance at any time the number and type of all resources in existence, available, and requested. One known algorithm that is used for deadlock avoidance is the Banker's algorithm, which requires resource usage limit to be known in advance. However, for many systems it is impossible to know in advance what every process will request. This means that deadlock avoidance is often impossible.
Two other algorithms are Wait/Die and Wound/Wait, each of which uses a symmetry-breaking technique. In both these algorithms there exists an older process (O) and a younger process (Y). Process age can be determined by a time stamp at process creation time. Smaller time stamps are older processes, while larger timestamps represent younger processes.
| | Author: Ashok 25 Jul 2008 | Member Level: Gold | Rating: Points: 1 | Prevention
Deadlocks can be prevented by ensuring that at least one of the following four conditions occur:
* Removing the mutual exclusion condition means that no process may have exclusive access to a resource. This proves impossible for resources that cannot be spooled, and even with spooled resources deadlock could still occur. Algorithms that avoid mutual exclusion are called non-blocking synchronization algorithms.
* The "hold and wait" conditions may be removed by requiring processes to request all the resources they will need before starting up (or before embarking upon a particular set of operations); this advance knowledge is frequently difficult to satisfy and, in any case, is an inefficient use of resources. Another way is to require processes to release all their resources before requesting all the resources they will need. This too is often impractical. (Such algorithms, such as serializing tokens, are known as the all-or-none algorithms.)
* A "no preemption" (lockout) condition may also be difficult or impossible to avoid as a process has to be able to have a resource for a certain amount of time, or the processing outcome may be inconsistent or thrashing may occur. However, inability to enforce preemption may interfere with a priority algorithm. (Note: Preemption of a "locked out" resource generally implies a rollback, and is to be avoided, since it is very costly in overhead.) Algorithms that allow preemption include lock-free and wait-free algorithms and optimistic concurrency control.
* The circular wait condition: Algorithms that avoid circular waits include "disable interrupts during critical sections" , and "use a hierarchy to determine a partial ordering of resources" (where no obvious hierarchy exists, even the memory address of resources has been used to determine ordering) and Dijkstra's solution.
Detection
Often neither deadlock avoidance nor deadlock prevention may be used. Instead deadlock detection and process restart are used by employing an algorithm that tracks resource allocation and process states, and rolls back and restarts one or more of the processes in order to remove the deadlock. Detecting a deadlock that has already occurred is easily possible since the resources that each process has locked and/or currently requested are known to the resource scheduler or OS.
Detecting the possibility of a deadlock before it occurs is much more difficult and is, in fact, generally undecidable, because the halting problem can be rephrased as a deadlock scenario. However, in specific environments, using specific means of locking resources, deadlock detection may be decidable. In the general case, it is not possible to distinguish between algorithms that are merely waiting for a very unlikely set of circumstances to occur and algorithms that will never finish because of deadlock.
| | Author: Ashok 25 Jul 2008 | Member Level: Gold | Rating: Points: 1 | In general, resources allocated to a process are not preemptable; this means that once a resource has been allocated to a process, there is no simple mechanism by which the system can take the resource back from the process unless the process voluntarily gives it up or the system administrator kills the process. This can lead to a situation called deadlock. A set of processes or threads is deadlocked when each process or thread is waiting for a resource to be freed which is controlled by another process. Here is an example of a situation where deadlock can occur.
Mutex M1, M2;
/* Thread 1 */
while (1) {
NonCriticalSection()
Mutex_lock(&M1);
Mutex_lock(&M2);
CriticalSection();
Mutex_unlock(&M2);
Mutex_unlock(&M1);
}
/* Thread 2 */
while (1) {
NonCriticalSection()
Mutex_lock(&M2);
Mutex_lock(&M1);
CriticalSection();
Mutex_unlock(&M1);
Mutex_unlock(&M2);
}
Suppose thread 1 is running and locks M1, but before it can lock M2, it is interrupted. Thread 2 starts running; it locks M2, when it tries to obtain and lock M1, it is blocked because M1 is already locked (by thread 1). Eventually thread 1 starts running again, and it tries to obtain and lock M2, but it is blocked because M2 is already locked by thread 2. Both threads are blocked; each is waiting for an event which will never occur.
| | Author: Biju 26 Jul 2008 | Member Level: Gold | Rating: Points: 6 | Currently the Mono team is working on various long-term solutions to the problem, but in the meantime a quick solution is to increase the number of active threads in the ThreadPool, effectively defeating part of the reason for the ThreadPool's own existance, you can do this by using the MONO_THREADS_PER_CPU environment variable, the default being 50 (25 on windows):
export MONO_THREADS_PER_CPU=2000If you are using Mono from Apache (http://www.apache.org/) to run ASP.NET, you can use the MonoSetEnv configuration option in Apache:
MonoSetEnv MONO_THREADS_PER_CPU=2000
For ASP.NET applications it's also a good idea to tweak the default values found in machine.config, inside <system.web> section:
<httpRuntime executionTimeout="90"
maxRequestLength="4096"
useFullyQualifiedRedirectUrl="false"
minFreeThreads="8"
minLocalRequestFreeThreads="4"
appRequestQueueLimit="100" />Consider changing minFreeThreads which is the amount of threads from the threadpool that ASP.NET will not use.
| | Author: Ratheesh 31 Jul 2008 | Member Level: Gold | Rating: Points: 1 | A situation wherein two or more processes are unable to proceed because each is waiting for one of the others to do something. A common example is a program communicating to a server, which may find itself waiting for output from the server before sending anything more to it, while the server is similarly waiting for more input from the controlling program before outputting anything. (It is reported that this particular flavor of deadlock is sometimes called a `starvation deadlock', though the term `starvation' is more properly used for situations where a program can never run simply because it never gets high enough priority. Another common flavor is `constipation', in which each process is trying to send stuff to the other but all buffers are full because nobody is reading anything.) See deadly embrace. 2. Also used of deadlock-like interactions between humans, as when two people meet in a narrow corridor, and each tries to be polite by moving aside to let the other pass, but they end up swaying from side to side without making any progress because they always move the same way at the same time.
| | Author: Sridhar R 27 Aug 2008 | Member Level: Diamond | Rating: Points: 5 | Deadlock..
When two computers shares the same resources, which will prevent each other from acessing the resource, at that situation both the programs ceasing to function.
Verify these links for more ideas..
http://searchcio-midmarket.techtarget.com/sDefinition/0,,sid183_gci211913,00.html
http://en.wikipedia.org/wiki/Deadlock
http://www.cs.rpi.edu/academics/courses/fall04/os/c10/index.html
|
| Post Reply |
|
|
|
You must Sign In to post a response.
|
|
|
|