<div class="gmail_quote">On Wed, Jan 27, 2010 at 12:36 PM, Michel Fortin <span dir="ltr"><<a href="mailto:michel.fortin@michelf.com">michel.fortin@michelf.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">Le 2010-01-27 à 11:40, Kevin Bealer a écrit :<br>
<div class="im"><br>> Tier A, the shared operations, could include byte and int64 operations, but also anything else you'd like to do with a shared object, such as modifying an associative array's contents or swapping the contents of two adjacent fields of the same object.<br>
<br></div>Hum, nice idea, but we need to be careful with that. Locking into the lock pool for performing a simple data operation is fine. But since you never know in what order each thread will take its locks in the lock pool, no thread should be allowed to take a lock while it holds a lock in the lock pool, even a separate object lock.</blockquote>
<div> </div>
<div>What I was thinking of is two non-overlapping lock pools, and the order would always be that you either take a (shared) lock in the first, then (an exclusive in) the second, or you only take the (exclusive) lock in the first. So all lock ops should be ordered and safe from deadlock as long as the thread doesn't go belly up while holding the lock. If you needed to take two locks in either pool, you'd need to take them together in each pool in order, and you could take both of the disk-page level locks in numerical order to avoid an ordering issue there -- I'm thinking of these locks as only being accessible to this shared-qualifier implementation layer, not taken from a general pool of locks the user can dip into. The disk-page locks are not in the same pool as the 8-byte-range locks.</div>
<div> </div>
<div>E.g. update a shared long on a platform that doesn't have 8 byte atomics, assuming a secondary protection size of 16:</div>
<div> </div>
<div>address = 12345;</div>
<div> </div>
<div>
<div>get_shared_lock(table1[address / disk_page_size]);</div>
<div>
<div>get_exclusive_lock(table2[address / 16]);</div>
<div>
<div> </div>
<div>// modify the long in some way</div>
<div>*12345 = *12345 + 10;</div>
<div> </div>
<div>clear_exclusive_lock(table2[address / 16]);</div>
<div>
<div>clear_shared_lock(table1[address / disk_page_size]);</div>
<div> </div></div></div></div></div>
<div>I was thinking of the disk page locks as a way to support operations that cover any operation affecting an entire shared struct no matter how big it is (up to the disk page size). If we assume that all ops will be field-wise then you could just use one lock that is at the granularity you want to lock at.</div>
<div> </div>
<div>This should be deadlock free as long as the set of locks needed for any op are known before getting any of them, which I think is doable if the operations each apply to one location. This scheme wouldn't work if you wanted to combine arbitrary sets of operations under a single atomicness constraint -- it only works for simply defined operations, like reading a 16 byte value or storing a single byte into a word.</div>
<div> </div>
<div>One nice thing about spinlocks is that they don't actually "block", so you can avoid deadlocks based on lock order anyway -- if you can't get the last lock you need after N operations, you could back out the ones you have and wait for a few milliseconds. But I was trying to avoid that kind of complexity.</div>
<div> </div>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">
<div class="im">> Maybe this should be limited to things that might conceivably be possible using atomic CPU operations, such as atomically modifying two adjacent fields together (I'm thinking of array assignment but it's probably better for layer 1 to be conceived in terms of what phyical operation is being done), but maybe not something like sorting<br>
> an array.<br><br></div>As I explained, it needs to be limited to some specific operation to avoid deadlocks.<br><br>If you see atomic operations *as an optimization*, then for that optimization to be possible you need to restrict the lock pool to only what is possible using atomics. That's because you can't mix atomic and lock pool operations on the same variable. If only one of the allowed operations can't be done with atomics, you need to use the lock pool for all others too.<br>
</blockquote>
<div>Right. I was thinking that each operation, defined in terms like "increment an int32" is either a lock-pool op or an atomic op for a given platform. If your platform allows single-byte-write without shearing then writing shared 'byte' fields should be done using that mechanism. If it doesn't support 8-byte atomic operations, then those fields have to be handled with the lock pool mechanism in all cases.</div>
<div> </div>
<div>This implies that every piece of the data is part of exactly one protection domain -- e.g. if you have an 8 byte region of memory, you need to either treat it as a long or as two integers, you can't mix. It also implies that if you want byte-level access and don't have it natively, that objects falling in the same word need to share their locking strategy -- so maybe every struct would need a map of which fields are locked and which are atomic.</div>
<div> </div>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">Note that I said "as an optimization". If using the lock pool is done explicitly, the programer can ensure correct usage:<br>
<br> shared int x;<br> shared long y;<br><br> ++atomic(x); // x always accessed as atomic<br> ++locked(y); // y always accessed as locked<br><br>Although in this case it might be safer if this was part of the type information, perhaps through a template:<br>
<br> shared Atomic!int x;<br> shared Locked!long y;<br><br> ++x; // x always accessed as atomic<br> ++y; // y always accessed as locked<br><br>Static if could be used to choose between Atomic!T and Locked!T when specific atomic capabilities are missing:<br>
<br> // check for atomic increment<br> static if (is(Atomic!long()++))<br> Atomic!long y;<br> else<br> Locked!long y;<br><font color="#888888"><br><br>--<br>Michel Fortin<br><a href="mailto:michel.fortin@michelf.com">michel.fortin@michelf.com</a><br>
<a href="http://michelf.com/" target="_blank">http://michelf.com/</a><br></font>
<div>
<div></div>
<div class="h5"><br><br><br>_______________________________________________<br>dmd-concurrency mailing list<br><a href="mailto:dmd-concurrency@puremagic.com">dmd-concurrency@puremagic.com</a><br><a href="http://lists.puremagic.com/mailman/listinfo/dmd-concurrency" target="_blank">http://lists.puremagic.com/mailman/listinfo/dmd-concurrency</a><br>
</div></div></blockquote></div><br>