deadlock caused by a cyle of locks ? unprobable event causing it or just a false intuition

Question

Thanks a lot for your help.

I want to understand what really causes what I suppose to be a deadlock:

I have standards objects, let's call it 'Words' that contains 3 letters and a key; (it doesn t really matter for my problem)

I have a container (list) of Couples, where a Couple simply is: 2 Words and 1 couple-Key.

I have a function that is suppose to do some calculation on the list of Couples, it might modify the letters and the key during the calculation , but when the calculation is finish we can stock the result and reset it to the initial values.

Considering a code that uses a parallel for loop to get the results of all my couples. This uses a lock on the first word and then a lock on the second word before calling the getResult() function, why could a deadlock happen ?

My first idea was that if we have :

Couple 1 : A B

Couple 2 : B C

Couple 3 : C D

Couple 4 : D A

Couple 5 : A E.

If a thread takes the Couple 5, the thread taking the couple 4 will lock D and wait, etc... to Couple 2.

My intuition is that, someway deadlock might occur if a cycle pattern appears in my list of Couples. On the other hand, I am unable to build an example that explains a deadlock appearance without considering one of these event:

• simultaneously 2 different thread have the Couples A B and B A, and each thread lock the other word at the same moment (quite unprobable to me).

• a thread takes the priority to a former one (example:well I can't find any, finally I thinks it s equivalent to simultaneously 2 different thread have the Couples A B and B A, and each thread lock the other word at the same moment. It's just that, considering a big cycle, the probability that it happends is as high as the proportion of time required for a calculation over the number of threads.

Am i right with my analysis ?

If the cause of the eventual deadlock is not due to the "simultaneously " event, I'd be glad to know what causes it, or happy if more precision to deadlock probability appearances depending on number of threads or length of cycles etc... are discussed .

Actually, I kind of have 10^5 Couples 10^4 Words.

Thanks,

Guillaume

Answer 1

If a thread takes the Couple 5, the thread taking the couple 4 will lock D and wait, etc... to Couple 2.

Couple 1 tries to start and is waiting on A, couple 4 tries to start but is also waiting on A.

After couple 5 finishes one of the waiting couples will be able to lock A. If it is couple 1 then it will need to lock B before it can continue, however that is held by couple 2 and that is waiting on couple 2 which is waiting on couple 3 etc. until couple 4 which is now waiting on couple 1. There is no way to make progress $\implies$ deadlock.

It's important to keep in mind that between locking one word and locking the next a process can be interrupted or another can simple be faster and lock the second word.

You can avoid the lock by always locking the words in alphabetical order, that way couple 4 will lock A before it will try to lock D and couple 3 is then able to make forward progress and a deadlock is impossible.