I'm wondering if there's a package or model that will help me solve this scenario.
Let's say I have 3 threads and a bunch of objects A,B,C,D,E,F
- T1 needs locks A,B
- T2 needs locks B,C,D
- T3 needs locks E,F
In this scenario, it'd be ok if T1 & T3 ran simultaneously. Also, T2 & T3 can run simultaneously. But T1 & T2 should never run simultaneously.
Also, note that
- Threads can obtain an arbitrary number of locks, not just 2. (I saw an elegant solution to this problem with a fixed number of locks but not sure I can apply it here.)
- Obviously, I'd like each thread to acquire all the needed locks at the same time to prevent deadlock.
If someone can point me to a package that supports this use case, or some snippet of code that resolves this, please let me know.
Thanks so much.
Step 1
Provide a natural ordering for your resources. For example, if your resources were letters, A would come before B, B would come before C, and so on.
Step 2
Only allow your threads to grab resources in order.
Now your threads cannot possibly reach deadlock in any situation.
Example
- Thread 1 needs locks on resources
A, B, D, and E
- Thread 2 needs locks on resources
B and E
Our threads must fight for locks on resources B and D. Because we have enforced a natural order, the thread that obtains the lock on B first is guaranteed to get the lock on D and proceed smoothly. The losing thread will be waiting for B to be released.
To avoid deadlock in these scenarios you must need to induce an ordering on the locks and acquire them according to the induced ordering consistently though out your application.
I understand this answer has been mentioned and may be sufficient in particularly your case but natural ordering is possible only when objects are comparable :(
Best way to induce ordering on objects is to use the System.identityHashCode(A/B/C...lock object) which returns value of hashcode. But again don't feel 100% safe as you might be victim of hash collision and even the chance is rare but you might get Deadlock. In those scenarios you need additional safety in your code. Your make your threads to compete for some separate 'tie breaking' lock. Hope this information helps in getting a bit more clear picture on your problem.
