'how can deadlock occur if locks guarantee atomicity

Situation 1:

//snippet1
a=1
if(a!=0){
print(a);
}
//snippet2
a=0;

lets say thread T1 is executing snippet1, checks the if condition (which is true),enters the scope of if, then T1 is interrupted, and T2 executes snippet2, now T1 resumes and executes print(a). this is wrong as even though a is now 0, T1 goes ahead and prints despite the if condition being false. The solution to the above problem that I read is acquire a lock on snippet1, then until the snippet1 is over, T1 won't be interrupted.

Good enough!

But I have a doubt regarding the following: Situation 2:

//snippet3
acquire_lock1;
{
acquire_lock2;
}

//snippet4
acquire_lock2;
{
acquire_lock1;
}

Lets say thread T3 is executing snippet3 and T4 executing snippet4. Say T3 acquired lock1, was interrupted, T4 acquired lock2 and went on to acquire lock1, but it is now held by T3. So now this is a classic example of deadlock.

I am having problem in understanding that, if acquiring a lock guarantees atomicity of execution, and that once lock is acquired on the critical section, we cannot interrupt that thread, then how come after acquiring lock1 was T3 interrupted and T4 went on with the execution. According to me, once lock1 is acquired by T3, it should begin execution without getting interrupted ,acquire Lock2, release lock2,release lock1, and complete this entire process without interruption. But this way a deadlock shall never occur.

Can anyone explain me whats wrong with this thought process, and when exactly can a deadlock occur?

Thanks in advance!

javamultithreadingconcurrencypython-multithreadingandroidnode.jsbluetooth-lowenergybluetooth-peripheral


Solution 1:[1]

As @Kayaman said already in there comment: "Acquiring a lock doesn't mean that the thread can't be interrupted".

The lock just protects ("guards") a code section from being executed by two threads at the same time (or that another thread may enter that section before another thread has left it). Technically, an acquired lock only guarantees that no other thread can acquire the same lock at the same time. This means that such another thread waits in the acquire statement until the lock is released (or a timeout expires, or hell freezes over … – for the following discussion, these details are not required).

So when Thread1 acquires Lock1 at the beginning of Section1, and then dies without returning the lock, no other thread may enter Section1. Or when Thread1 will be interrupted while holding the lock, it has to get back control to be able to release the lock before any other thread may enter Section1.

Your second scenario is now prone to a deadlock:

  1. Thread1 acquires Lock1 when entering Section1_1, guarded by this lock
  2. Thread2 acquires Lock2, guarding Section2_1,
  3. Thread1 advances to the begin of Section1_2 that is guarded by Lock2
  4. The attempt by Thread1 to acquire Lock2 fails, because this is already hold by Thread2
  5. Thread1 now waits that Lock2 is released
  6. Meanwhile Thread2 advanced to the begin of Section2_2 that is guarded by Lock1
  7. As Lock1 is already hold by Thread1, the attempt by Thread2 to acquire that lock fails
  8. Now Thread2 wait for Lock1 to be released
  9. As both threads are now mutually waiting for the other one to release the thread, your program is trapped in a deadlock

An easy way to prevent that is to ensure that locks are always taken in the same sequence (also known as the 'ABC' rule): when threads need the locks Lock_One, Lock_Two, Lock_Three, they have to acquire them always in the sequence of their names (first Lock_One, then Lock_Three, finally Lock_Two). Although this seems not logical (because of the chosen names …) it guarantees that you do not get a dead lock. A thread can acquire Lock_Three only if it has already acquired Lock_One, or it does not need Lock_One at all; same for Lock_Two …

If for some reason it is required to acquire Lock_Two before Lock_Three … rename the locks so that the ABC rule will work again – and adjust your code afterwards!

Solution 2:[2]

If the peripheral has for example a HID GATT service exposed, then you can pair and connect to it through the system settings. This means BLE keyboards and mice can be used without any app.

If your peripheral only has custom services or only services the OS knows nothing about, then you will need some app to connect to it.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1
Solution 2 Emil

Related Questions