On Jan 20, 2010, at 4:28 AM, Michel Fortin wrote:
> 
> I'd like to note that even upgrading the lock to a write lock might be a problem: as I said in my other message, making this an automatic upgrade might force the release the reader lock until the writer lock is acquired, which would be unexpected from test()'s point of view.

ReadWriteMutex is implemented internally using a mutex and condition variable, so the basic process would be:

Upgrade:

* set thread-local heldReadLock flag
* decrement numReaders
* enter write queue

When exiting a write lock, if heldReadLock is set then it's cleared and the thread enters the read queue.  Both operations would be atomic.  But even the write lock isn't recursive so I'm hesitant to encourage people to get terribly fancy with using the lock.

On Wed, 20 Jan 2010 07:14:44 -0500, Michel Fortin <michel.fortin at michelf.com> wrote:

> Le 2010-01-20 ? 2:53, Robert Jacques a ?crit :
>
>> Sort of; I was thinking about implicit use and not explicit use; i.e. const functions would take a reader lock and non-const function would take a writer lock. Generally, I've heard reports that CREW locks give big performance boosts in certain domains (game programming, for instance), but I don't know exactly the real performance trade-off compare to normal locks under low contention. Still, it would be nice to be able to replace an object's mutex with a rwmutex and have it work right.
>
> I think read/write lock usage should only be used explicitly.
>
> That's because you can never upgrade "safely" from a read lock to a write lock, or to be precise there is always a risk that you must release your read lock before upgrading. Two threads could acquire a read lock and then both might want to upgrade to a write lock, which can't be satisfied without one of them dropping its read lock first.
>
> If the read lock drops because you call another function that wants a write lock, this could be trouble. Upgrades work well when there is only one thread requesting upgrades. Otherwise the upgrade must be seen as a drop-read-lock then acquire-write-lock non-atomic operation.
>

Ah, the composability problem. Thanks for explaining.

On Wed, 20 Jan 2010 10:48:57 -0500, Robert Jacques <sandford at jhu.edu> wrote:

> On Wed, 20 Jan 2010 07:14:44 -0500, Michel Fortin <michel.fortin at michelf.com> wrote:
>
>> Le 2010-01-20 ? 2:53, Robert Jacques a ?crit :
>>
>>> Sort of; I was thinking about implicit use and not explicit use; i.e. const functions would take a reader lock and non-const function would take a writer lock. Generally, I've heard reports that CREW locks give big performance boosts in certain domains (game programming, for instance), but I don't know exactly the real performance trade-off compare to normal locks under low contention. Still, it would be nice to be able to replace an object's mutex with a rwmutex and have it work right.
>>
>> I think read/write lock usage should only be used explicitly.
>>
>> That's because you can never upgrade "safely" from a read lock to a write lock, or to be precise there is always a risk that you must release your read lock before upgrading. Two threads could acquire a read lock and then both might want to upgrade to a write lock, which can't be satisfied without one of them dropping its read lock first.
>>
>> If the read lock drops because you call another function that wants a write lock, this could be trouble. Upgrades work well when there is only one thread requesting upgrades. Otherwise the upgrade must be seen as a drop-read-lock then acquire-write-lock non-atomic operation.
>>
>
> Ah, the composability problem. Thanks for explaining.

But, since the reader lock would only be called from const functions, there would never be a situation where you'd want to upgrade a reader lock to a writer lock. The only issue would be writer locks trying to take a reader or a second writer lock. Or am I missing something?

On Jan 20, 2010, at 7:39 AM, Sean Kelly wrote:

> On Jan 20, 2010, at 4:28 AM, Michel Fortin wrote:
>> 
>> I'd like to note that even upgrading the lock to a write lock might be a problem: as I said in my other message, making this an automatic upgrade might force the release the reader lock until the writer lock is acquired, which would be unexpected from test()'s point of view.
> 
> ReadWriteMutex is implemented internally using a mutex and condition variable, so the basic process would be:
> 
> Upgrade:
> 
> * set thread-local heldReadLock flag

Um... thread-local per instance of the ReadWriteMutex, which means an associative array or the like.  So this bit actually adds a fair bit of complexity to the design.

By the way, Sean, is it ok if I don't describe anything beyond "synchronized" in TDPL with regard to lock-based coding?

Andrei

Sean Kelly wrote:
> On Jan 20, 2010, at 7:39 AM, Sean Kelly wrote:
> 
>> On Jan 20, 2010, at 4:28 AM, Michel Fortin wrote:
>>> I'd like to note that even upgrading the lock to a write lock might be a problem: as I said in my other message, making this an automatic upgrade might force the release the reader lock until the writer lock is acquired, which would be unexpected from test()'s point of view.
>> ReadWriteMutex is implemented internally using a mutex and condition variable, so the basic process would be:
>>
>> Upgrade:
>>
>> * set thread-local heldReadLock flag
> 
> Um... thread-local per instance of the ReadWriteMutex, which means an associative array or the like.  So this bit actually adds a fair bit of complexity to the design.
> _______________________________________________
> dmd-concurrency mailing list
> dmd-concurrency at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-concurrency

Yeah.  There's no reason to get into the library stuff beyond perhaps saying that the traditional things are available for those who want them.

On Jan 20, 2010, at 8:37 AM, Andrei Alexandrescu wrote:

> By the way, Sean, is it ok if I don't describe anything beyond "synchronized" in TDPL with regard to lock-based coding?
> 
> Andrei
> 
> Sean Kelly wrote:
>> On Jan 20, 2010, at 7:39 AM, Sean Kelly wrote:
>>> On Jan 20, 2010, at 4:28 AM, Michel Fortin wrote:
>>>> I'd like to note that even upgrading the lock to a write lock might be a problem: as I said in my other message, making this an automatic upgrade might force the release the reader lock until the writer lock is acquired, which would be unexpected from test()'s point of view.
>>> ReadWriteMutex is implemented internally using a mutex and condition variable, so the basic process would be:
>>> 
>>> Upgrade:
>>> 
>>> * set thread-local heldReadLock flag
>> Um... thread-local per instance of the ReadWriteMutex, which means an associative array or the like.  So this bit actually adds a fair bit of complexity to the design.
>> _______________________________________________
>> dmd-concurrency mailing list
>> dmd-concurrency at puremagic.com
>> http://lists.puremagic.com/mailman/listinfo/dmd-concurrency
> _______________________________________________
> dmd-concurrency mailing list
> dmd-concurrency at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-concurrency

Le 2010-01-20 ? 10:57, Robert Jacques a ?crit :

>>> I think read/write lock usage should only be used explicitly.
>>> 
>>> That's because you can never upgrade "safely" from a read lock to a write lock, or to be precise there is always a risk that you must release your read lock before upgrading. Two threads could acquire a read lock and then both might want to upgrade to a write lock, which can't be satisfied without one of them dropping its read lock first.
>>> 
>>> If the read lock drops because you call another function that wants a write lock, this could be trouble. Upgrades work well when there is only one thread requesting upgrades. Otherwise the upgrade must be seen as a drop-read-lock then acquire-write-lock non-atomic operation.
>>> 
>> 
>> Ah, the composability problem. Thanks for explaining.
> 
> But, since the reader lock would only be called from const functions, there would never be a situation where you'd want to upgrade a reader lock to a writer lock. The only issue would be writer locks trying to take a reader or a second writer lock. Or am I missing something?

A const function only makes the "this" reference const. Accessing the same objects through other references (such as a global or an argument) could cause non-const functions to be called on that same object, which could require a write lock even when calling a const function.

Pure functions are safe of course, but that's too restricting to be really useful.

-- 
Michel Fortin
michel.fortin at michelf.com
http://michelf.com/

On Wed, Jan 20, 2010 at 9:23 AM, Kevin Bealer <kevinbealer at gmail.com> wrote:

> There is a type of locking pattern that solves this issue.  It involves locks that can be in "read", "write" or "shared" mode.  The concept is that you get a shared lock when you might want to upgrade to a write lock.
>
> Shared mode can coexist with other threads that are in "read" mode, but is not compatible with other threads that are in write or shared mode.  You can upgrade a shared mode lock to a write lock without deadlocking -- it waits for other threads to finish reading.
>
> The normal usage pattern is that you get a shared mode when you might want to modify something.  Let's say that a user wants to write a line to a logfile.  You get a shared mode lock on the directory, then check if the file exists.  If it already exists, you downgrade the shared lock to a read lock, then get a write mode lock on the file.  If the file does not exist, you instead upgrade the shared lock to a write lock, then create the file (which is why you needed write permissions), then get a write lock on the new file and downgrade or release the directory lock.
>
> This model of locking cannot deadlock on itself because there is only one "shared" process at a time -- when getting a shared lock, you need to wait for all existing writers to exit, and for any existing shared lock holders to exit or downgrade.  It works best for cases where a processes often thinks it *might* need to do a write operation but usually doesn't, in which case it reduces lock contention for reader threads.  The most common situation is where you don't know if you need to do the write until you've done some reads to asses the current situation.
>
> I know we used locks like this when I was at IBM.  I wish I could find out who invented this so I know whether it is patented.  (IBM loves patents -- I suspect it isn't patented but I haven't found a good writeup of it online yet.)
>
> Kevin
>
>

Never mind that last bit, I just noticed that read/write/shared locks as I describe here are available in boost.  The patent I remember had something to do with specifics of how it was implemented.

Kevin

>  On Wed, Jan 20, 2010 at 7:28 AM, Michel Fortin <michel.fortin at michelf.com
> > wrote:
>
>> Le 2010-01-20 ? 2:07, Sean Kelly a ?crit :
>>
>> > Is what you want in core.sync.rwmutex?  You can use it as:
>> >
>> > synchronized( mut.reader ) {}
>> > synchronized( mut.writer ) {}
>> >
>> > It doesn't currently allow upgrading read locks to write locks, though I
>> think this wouldn't be difficult to add.  More importantly I suppose is that acquiring a concurrent read lock may be more expensive than you'd expect, so you really only want to use a ReadWriteMutex if the read operations take a reasonable amount of time to complete.
>>
>> What happens if you call test() here?
>>
>>        void test() {
>>                synchronized (mut.reader) {
>>                        // read A
>>                        testWrite();
>>                        // read B
>>                }
>>        }
>>
>>        void testWrite() {
>>                syncrhonized (mut.writer) {
>>                        // write C
>>                }
>>        }
>>
>> I guess that if you haven't implemented upgrades this will deadlock.
>>
>> I'd like to note that even upgrading the lock to a write lock might be a problem: as I said in my other message, making this an automatic upgrade might force the release the reader lock until the writer lock is acquired, which would be unexpected from test()'s point of view.
>>
>> This could work well as a transaction, where a failure to upgrade the lock would throw an exception, "read A" would be rollbacked, and the synchronized part would be attempted again. But without proper logic to deal with the unfortunate case of a failed upgrade you have either a race or a deadlock here.
>>
>> --
>> Michel Fortin
>> michel.fortin at michelf.com
>> http://michelf.com/
>>
>>
>>
>> _______________________________________________
>>  dmd-concurrency mailing list
>> dmd-concurrency at puremagic.com
>> http://lists.puremagic.com/mailman/listinfo/dmd-concurrency
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/dmd-concurrency/attachments/20100120/6180735b/attachment-0001.htm>

On Wed, 20 Jan 2010 12:05:27 -0500, Michel Fortin <michel.fortin at michelf.com> wrote:
> Le 2010-01-20 ? 10:57, Robert Jacques a ?crit :
>
>>>> I think read/write lock usage should only be used explicitly.
>>>>
>>>> That's because you can never upgrade "safely" from a read lock to a write lock, or to be precise there is always a risk that you must release your read lock before upgrading. Two threads could acquire a read lock and then both might want to upgrade to a write lock, which can't be satisfied without one of them dropping its read lock first.
>>>>
>>>> If the read lock drops because you call another function that wants a write lock, this could be trouble. Upgrades work well when there is only one thread requesting upgrades. Otherwise the upgrade must be seen as a drop-read-lock then acquire-write-lock non-atomic operation.
>>>>
>>>
>>> Ah, the composability problem. Thanks for explaining.
>>
>> But, since the reader lock would only be called from const functions, there would never be a situation where you'd want to upgrade a reader lock to a writer lock. The only issue would be writer locks trying to take a reader or a second writer lock. Or am I missing something?
>
> A const function only makes the "this" reference const. Accessing the same objects through other references (such as a global or an argument) could cause non-const functions to be called on that same object, which could require a write lock even when calling a const function.
>
> Pure functions are safe of course, but that's too restricting to be really useful.

Good point. Although, I'm tempted to say that any const function that results in mutation is a program logic error and therefore a deadlock may actually be desired behavior. Anyways, I thought of something else which throws a spanner into the work. Lock-regions, i.e. ownership regions, could protect multiple objects and the entire region would never be entirely const. So definitely no-go as a default. Still might a good option to have if we can find a good recursive CREW lock.