Deadlocks

Deadlock: Deadlock can occur when threads wait on each other in such a way that none can proceed. Example:

Thread 1 calls some synchronized function on object1 which calls some synchronized function on object 2. This means it has already locked object1 and is also trying to lock object2.

If at the same time, Thread 2 calls a synchronized method on object 2 which calls a synchronized method on object 1, then deadlock will occur because both object1 and object2 were locked by independent threads and now they want to lock each other which will never happen.

Deadlocks in DB transactions: When a DB record is updated during a transaction, that record is locked for updates from other transactions, until the first transaction completes. Each update request within the same transaction may therefore lock some records in the database.

If multiple transactions are running at the same time that need to update the same records, there is a risk of them ending up in a deadlock.

For example:

Transaction 1, request 1, locks record 1 for update
Transaction 2, request 1, locks record 2 for update
Transaction 1, request 2, tries to lock record 2 for update.
Transaction 2, request 2, tries to lock record 1 for update.

Deadlock Prevention

This can be done in 3 ways (although none of them is foolproof or easy):

1) Lock Ordering - If multiple threads need locks on multiple objects, they should always lock the objects in the same order so that no 2 threads try to lock each other’s locked objects. But it is sometimes not possible to determine the lock ordering before-hand or sometimes it is required to lock the objects differently for different threads and cannot be changed.

2) Lock Timeout - Another approach is to have a timeout such that if a thread does not acquire the lock after a predetermined time interval, it will backup, release all locks, wait for some random time and then try again. This gives other threads a chance to acquire all the locks earlier held by the timing-out thread. However, if there are too many threads in the system contesting for a shared resource’s lock, there may be too many timeouts and backouts which can reduce the performance of the system.

3. Deadlock Prevention - One can create a graph of objects locks and requests for locks and time-out the threads request for locks only if the graph indicates a deadlock. This is an improvisation over #2 but not foolproof and can still reduce system performance if there are too many threads.

Different kinds of Dead-locks

1) Deadlock

Deadlock occurs when two threads cyclically wait on each other’s resources.

2) Livelock

Livelock is similar to deadlock except that in livelock, threads are not in a waiting state. They keep on running, trying to obtain lock on each other’s resources but not succeeding. So the threads are not in a real wait state, but they are not able to make progress.

An example of this is 2 people meeting in a corridor and each one trying to give way to other by moving aside but since both move to same side, they block again and repeat the process of moving and blocking.

From a programming viewpoint, you can consider 2 threads waiting on each other. When they have waited a specified interval of time, they release their own lock, sleep for 30 seconds and repeat the process. Since each thread sleeps for same amount of time, they wake up at the same time and try to acquire lock on each other’s locked resources at the same time again.

Thus, the threads are locked even though their internal state keeps changing.

3) Spinlock

Spinlock happens when a thread simply waits in a loop ("spins") repeatedly checking until the lock becomes available. Its also called busy waiting.

4) Sequential Lock

A sequential-lock consists of a sequence number in addition to a lock.

• The lock is to support synchronization between two writers and

• The counter is for indicating consistency in readers.

In addition to updating the shared data, the writer increments the sequence number, both after acquiring the lock and before releasing the lock. Readers read the sequence number before and after reading the shared data. If the sequence number is odd on either occasion, a writer had taken the lock while the data was being read and it may have changed. If the sequence numbers are different, a writer has changed the data while it was being read.

In either case readers simply retry (using a loop) until they read the same even sequence number before and after.

The reader never blocks, but it may have to retry if a write is in progress; this speeds up the readers in the case where the data was not modified, since they do not have to acquire the lock as they would with a traditional read-write lock. Also, writers do not wait for readers, whereas with traditional read-write locks they do, leading to potential resource starvation in a situation where there are a number of readers (because the writer must wait for there to be no readers). Because of these two factors, seqlocks are more efficient than traditional read-write locks.