[dmd-concurrency] CSP: Communicating sequential processes

[Kevin Bealer]

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>