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.
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.
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.
|