[dmd-concurrency] CSP: Communicating sequential processes

[Kevin Bealer]

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

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/14c1edfe/attachment.htm>