2

What is the best strategy to lock on varying (dynamic) number of objects/keys?

Consider the scenario, where a thread can only proceed with a task (transaction), when locks are gained on a number of objects (array of objects is dynamic and cannot be predicted). In this example, an ID can represent an Object, which needs to be modified as part of "transaction".

Example:

Thread: Objects to Lock (as part of transaction)

T1:       A   B   C   D

T2:           B       D

T3:       A           D

EDIT: Improving the example

Clearly, doing sequential dynamic locking, can cause a deadlock for all threads, as T1 can gain lock of A, while T2 gains lock on B, and T3 grabbed lock on D. T1 waits for T2 to release B, and T2 waits for T3 to release D, and T3 waits for T1 to release A.

What are possible options to implement such multi-object locking?

The question is in part theoretical, and in part practical as it must be solved in C# / .NET

Possible Solution:

In order to keep both the parallelism and also maintain correct locking, I thought of the following scheme:

Two Queues:

  1. Sequential Queue (served by 1 thread only, hence sequential)
  2. Parallel Queue (served by a pool of threads)

When a request arrives for N objects, examine each object Id and if increment lock count for each ID (this can be a Dictionary<int, int> - <Id, Lock Count>).

IF all IDs are "locked" (note that no actual locking takes place), i.e. requested for the first time, put the request in Parallel queue ELSE put the request in sequential queue

This hybrid approach allows to process "contesting" requests sequentially, and non-contesting - in parallel.

Improve this question
6
  • Why does T2 wait for T1 to release A? T2 isn't locking on A Commented Dec 16, 2013 at 19:24
  • @dcastro Because T1 grabbed A and then B, meanwhile T2 wants B, so it waits for T1 to finish with C and D before it will release B. Commented Dec 16, 2013 at 19:28
  • Yes, agree that the example can be improved - the point is that the scenario in question involves two thread holding some keys, which the other thread wants as well. Commented Dec 16, 2013 at 19:31
  • 1
    Consider T1: A B -- T2: B A, in which each has grabbed their first lock and not their second. This will deadlock. You need to ensure that that can't happen with your code, which isn't always easy. Commented Dec 16, 2013 at 19:34
  • 1
    @DavidHaney your sequence is valid, but in the example given B was grabbed by T2. Commented Dec 16, 2013 at 19:39

3 Answers 3

Reset to default
3

The way to prevent deadlock when locking multiple objects is to have a canonical order for acquiring locks. In your example, let's create the scheme that locks must be acquired in alphabetical order. Say T1 acquires A and T2 acquires B. T3 should not try to acquire D until it acquires A. B can then acquire D and complete. T1 can then acquire B, and subsequently T3 can acquire A.

However, this scheme cannot be violated anywhere in the code base. If you have acquired locks A, B, and D, you cannot go back and acquire C.

Proof by contradiction:

Assume it is possible to deadlock with this scheme. This means that all threads are waiting for locks. If all locks must be acquired in sequence, that means all locks can be mapped to integers 1 ... N. One acquired lock L must be the highest acquired lock in the sequence. However, that thread cannot be blocked, since no thread can have a lock higher than L. Therefore it is not possible for all threads to be blocked.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I guess that is the only solution, if locking was utilized (and not redesign). So accepting this and zmbq's answer as they are similar.
Apparently you can't accept two answers here, so had to pick this one as it has the "proof of theorem".
3

I agree with @Reed, if it's possible to redesign the code to avoid all those locks - do it.

One very easy way to redesign this, since you have so many locks, is to lose concurrency altogether. Run everything sequentially. You might just find out it works just as fast, because all the locking is preventing concurrency anyway.

If you can't do that for some reason, one way to make sure deadlocks do not appear is to always obtain locks in the same order. In your example, if a task needs both locks A and D, always lock A before D. Do that in all other tasks as well.

A deadlock is impossible this way. A deadlock occurs when task 1 has lock A and wants lock B, and task 2 has lock B and wants lock A. If you always lock A before you lock B, there's no way task 2 will have lock B and then want lock A.

Improve this answer

2 Comments

I have thought of a hybrid sequential/parallel approach (see Edit) - how does it fair vs sequential only?
There's no way to predict that without trying it out first. I'd try the sequential approach first, it might be fast enough, and is by far the easiest to implement.
2

In general, you should do everything you can to avoid trying to lock on multiple objects in this fashion. It gets very difficult to avoid deadlocks when you start optionally locking on multiple resources.

Instead, it's almost always a better approach to rethink the design, and come up with other strategies. Using immutable types, for example, can avoid the need for locking altogether in many scenarios. Concurrent collections can also be hugely beneficial to avoid locks, as you can separate out the processing of the data from the production (producer/consumer via BlockingCollection<T>, etc).

Improve this answer

7 Comments

This is the truth. You should not lock both super granularly and sequentially. Pick one or the other. Sequential broad locks always gained in the same order, or granular locks that are not sequentially acquired.
Would be interesting to get ideas on how, with a change of design, to also keep "transaction" functionality - operation is requested by multiple clients (parallel requests) on multiple objects, and can only be performed once all objects are locked (transaction). Making the request processing sequential negates the parallelism.
@user2983917 If you can pipeline the operations, that may help. Look into TPL Dataflow for more details.
@user2983917 The root question begins with why do you need transaction functionality?
If operation fails on one of the objects, all objects are restored to pre-request state, hence the transaction functionality.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.