Ordered Locking Pattern and ReaderWriterLock in C#

开发者_如何转开发

Does the ordered locking pattern prevent deadlocks when used with a ReaderWriterLock (or ReaderWriterLockSlim)?

Clearly the pattern prevents deadlocks with a mutex. Does it still prevent deadlocks if I am locking several resources with ((N resources with read locks) and (1 or 2 resources with write locks)).

For example: (Bold numbers represent resources with write locks)

1 2 3 4 5

2 3 4

1 4 5

---

tl;dr Resource ordering prevents deadlock for reader-writer locks too.

Long answer:

Draw a wait-for graph like this:

First draw a vertex for all the resources from left to right in the prescribed order.

Then, for each process, waiting for a resource, draw a vertex, immediately preceding the vertex of the waited for resource. If a process is not waiting on any resources, draw a vertex on the far right, after all the resource vertices.

Then draw an edge from each process to the resource on which that process is waiting and draw an edge from each resource to the process, which is currently holding that resource.

Consider each edge on the graph. There are two cases:

• the edge is Pi -> Ri, i.e. from a process to a resource. Since each process is waiting on only one resource and we have drawn the process' vertex immediately to the left of the resource it is waiting for, then the edge is from left to right.

• the edge is Ri -> Pj, i.e. from a resource to a process. If Pj is not waiting to any resource, then its vertex is on the right of all the resources, therefore the edge is from left to right. If Pj is waiting to Rk, then i < k, because processes acquire resources in order. If i < k, then Ri is on the left of Rk, and Pj is immediately on the left of Rk (since we have drawn the grapgh that way), hence Ri is on the left of Pj, therefore the edge is again left to right.

Since all the edges of the graph drawn this way are from left to right, then we have constructed a topological sorting of the graph, hence the graph has no cycles, hence a deadlock cannot occur.

Note that what matters is the fact that a process waits, not why it waits. Thus, it does no matter whether it waits for a mutex, read-write lock, semaphore or whatever - this strategy for deadlock prevention works for all.

---

I think you're doing the Ordered locking pattern wrong, you have to grab all the locks in order. To grab the write lock for "4", you need to first grab the write lock for "3". For "5", you need to grab the write locks for "3" and "4" and "5".

With normal locks, the ordered locking pattern is expensive, but with SRW locks they're super expensive since you have to throw out all the readers first. Remember that SRW locks only are an advantage if at least 80%+ of your accesses don't need the Write lock - it's very expensive otherwise, and you can do far better with a simple lock.

Even better though, is to try to decouple your code so that you don't need the ordered locking (i.e. so I don't need access to the data from '3' and '4' at the same time). This isn't always possible, but your code will be simpler the more you can do this.

---

I attempted an implementation of ordered lock in C# that checks if locks have been acquired in a fixed order. See http://www.codeproject.com/Tips/563154/OrderedLock-in-Csharp