4

I have an array, that represents an inventory, with nearly 50 elements (items: some costum objects) and I need a readerwritelock for it (okay, i think a simple lock would be enough too). It should support both reference changing and value changing.

As reading and writing to different position of the array is threadsafe (Proof) I want to ensure that multiple read/write operations on the same array position is also threadsafe.

I surely could create 50 readerwriterlocks, but I don't want that ;) Is there a way to archive this? (I know ConcurrentList/Dictionary/etc. but I want an array...)

Thanks

Community
  • 1
  • 1
hellow
  • 12,430
  • 7
  • 56
  • 79

2 Answers2

5

If you are replacing the references in the array, then this is already safe, since reference swaps are inherently atomic. So you can use:

var val = arr[index];
// now work with val

and

var newVal = ...
arr[index] = newVal;

perfectly safely, at least in terms of avoiding torn references. So one pragmatic option is to make the object immutable, and just employ the above. If you need to change the value, take a local copy, make a new version based from that, and then swap them. If lost updates are a problem, then Interlocked.CompareExchange and a re-apply loop can be used very successfully (i.e. you keep reapplying your change until you "win"). This avoids the need for any locking.

If, however, you are mutating the individual objects, then the game changes. You could make the object internally thread-safe, but this is usually not pretty. You could have a single lock for all the objects. But if you want granular locking then you will need multiple locks.

My advice: make the object immutable and just use the atomic reference-swap trick.

Marc Gravell
  • 1,026,079
  • 266
  • 2,566
  • 2,900
  • For mutating the individual objects, they could also lock on the object itself. As long as nothing else is likely to lock on it (best guarantee - nothing else can even see it), then this is safe. I've had success with using lock-free techniques for the main collection (that lots of threads hit simultaneously) and locks on mutable objects contained (where contention is low per object, I also gained some more by putting the details of operations that failed to obtain the lock immediately into a queue for later processing, so threads could get on with those operations with no current contention). – Jon Hanna Aug 14 '12 at 11:02
  • Worth noting though, that while the two examples you give are safe the pair in tandem are not (I know that, you know that, but someone reading this...) – Jon Hanna Aug 14 '12 at 11:03
  • @Jon indeed, although then it gets trickier as you need to know what locks that object. I actually wish `Monitor` was an *instance* class, and you had to lock an explicit `Monitor` instance - it would have made locking far less problematic. For granular locking, I think I prefer your striped option, to be honest. – Marc Gravell Aug 14 '12 at 11:04
  • I've thought that about monitor a few times myself, though it would force one into the likes of striping in cases where we don't need it today. We can safely lock on "the object of interest" when that object is private to our code and "the object of interest" is easily defined, which comes up a lot but is far from covering every case. – Jon Hanna Aug 14 '12 at 11:07
  • Heh, and it occurs now, that that "success" I mention is part of the most complicated real-life production-code multithreading I've ever done, so maybe it's not the best example now that I think about it. – Jon Hanna Aug 14 '12 at 11:14
3

First off, you may not need any locks. Reading and writing with an array of a type where the CPU would handle each read and write atomically, is in and of itself thread-safe (but you might want to put in a memory barrier to avoid stale reads).

That said, just like x = 34 for an integer is threadsafe but x++ is not, if you've writes that depend upon the current value (and which are hence a read and a write), then that is not threadsafe.

If you do need locks, but don't want as many as 50, you could stripe. First set up your striped locks (I'll use simple locks rather than ReaderWriterSlim for smaller example code, the same principle applies):

var lockArray = new object[8];
for(var i =0; i != lockArray.Length; ++i)
  lockArray[i] = new object();

Then when you go to use it:

lock(lockArray[idx % 8])
{
  //operate on item idx of your array here
}

It's a balance between the simplicity and size of one lock for everything, vs the memory use of one lock for each element.

The big difficulty comes in if an operation on one element depends on that of another, if you need to resize the array, or any other case where you need to have more than one lock. A lot of deadlock situations can be avoided by always acquiring the locks in the same order (so no other thread needing more than one lock will try to get one you already have while holding one you need), but you need to be very careful in these cases.

You also want to make sure that if you are dealing with say, index 3 and index 11, you avoid locking on object 3 twice (I can't think of a way this particular recursive locking would go wrong, but why not just avoid it rather than have to prove it's one of the cases where recursive locking is safe?)

Jon Hanna
  • 110,372
  • 10
  • 146
  • 251
  • I like the idea of only using 8 locks but in my case won't fit I think. But also good idea. I think i can use this somewhere else ;) Thanks. – hellow Aug 14 '12 at 11:10
  • You can add more to your question about why it won't fit. Ideally the first part of my answer "you may not need any locks" fits, though you have to be **really** sure it fits! Otherwise, there's a variety of options, but they do need more detail before suggesting. – Jon Hanna Aug 14 '12 at 11:16