Thread Deadlocks

Here's an interesting technique on deadlock avoidance. We had a pretty complex multi-threaded application running C/C++ code. As with any multi-threaded application deadlocks were a major problem. The solution, serialize access to resources. This ensures that all threads enter the critical region in a serial order avoiding deadlocks.

How does it work ?
Lets say we have three threads t1, t2 and t3 that need to access resources r1, r2, r3. We create three locks/ semaphores s1, s2, s3. We enforce the rule that the locks must be aquired in the following order r1, r2, r3 ie. no thread can aquire r3 before r2 & releasing the locks must be in the reverse order.

Assuming t2 requires resources r1 r2 and r3. It first aquires the lock for r1, r2 and r3. But before t1 aquires r3 , t2 comes along, it needs resources r3 and r2. Even though the lock for r3 is available it cant aquire r3 because of the order restriction we impose. T2 waits for till t1 releases the r2 and starts processing. If we did not impose this order restriction, t2 would have aquired r3 and would be waiting for t1 to release r2. While t1 would be waiting for t2 to release r3, resulting in a deadlock.

Another interesting deadlock detection technique a little simpler to program but a little less efficient. Everytime a thread is unable to aquire a lock, it releases all its locks and calls a scheduled yeild or kills itself. Although this method works in most cases it is not really guaranteed to work at all times.