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

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

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.