> -----Original Message-----
> From: Branko Čibej [mailto:[EMAIL PROTECTED]
> Subject: Re: Can a thread write-lock a rwlock that it already has read-
> locked?
> 
> I wonder though iif your lock promotion scheme really works. Yes, it's
> possible to implement it, but I've never seen an implementation that,
> even when correct, is fair to all participating threads. For example,
> what happens if two threads try to promote their lock at the same time
> (that is, two are waiting on the promotion at the same time)? If you
> grant both requests, the one that comes in second will "do something"
> with a result that's no longer valid. If you only grant the first
> request, the second thread will have to recalculate its result again,
> and you end up with the same algorithm I outlined above, plus the
> overhead of a complex lock promotion implementation.

I think we agree on the following points:

1) "read/write" locks are merely names for shared or exclusive locks,
respectively -- it doesn't actually allow or prevent reading or writing
(that's up to the application).

2) The existing design of the read/write lock cannot prevent a race
condition in the "long read operation / do something" example, unless the
write lock is held (non-optimally) throughout the "long read operation".


I mentioned lock promotion as one possible solution to the "write lock
required during long read operation" dilemma, though it's not my preferred
option.  Rather, my preferred option is to allow a thread to write lock so
long as it holds all of the read locks.  Metaphorically this is equivalent
to "nested read lock + write lock".

Specifically, I'm proposing the following algorithm:

# struct rwlock {
#       mutex outer, inner;
#       stack readerStack;
# }
# void readLock( rwlock* rw ) {
#       lock( outer, inner ); // Blocks here if another thread is writing
#       push( readerStack, currentThreadID( ) );
#       unlock( inner, outer );
# }
# void readUnlock( rwlock* rw ) {
#       lock( outer, inner );
#       pop( readerStack );
#       unlock( inner, outer );
# }
# void writeLock( rwlock* rw ) {
#       lock( outer, inner );
#       while( another thread is reading ) {
#               unlock( inner, outer );
#               yield thread; // loops here while other threads read
#               lock( outer, inner );
#       }
#       // do not unlock inner
#       unlock( outer );
# }
# void writeUnlock( rwlock* rw ) {
#       unlock( inner );
# }

I'm not saying this implementation is without flaws (I especially don't like
that inner loop but I'm not sure how to get rid of it), but it illustrates
the behavior I'd like to have.  With this sort of read/write lock, functions
can read or write lock without knowing or caring about the lock state of the
calling thread:

# int longOperation( ) { 
#       readLock( );
#       ... 
#       readUnlock( );
# }
# void doIt( int result ) {
#       writeLock( );
#       ...
#       writeUnlock( );
# }
# void testAndDo( ) {
#       readLock( );
#       int result;
#       if( result = longOperation( ) ) doIt( result );
#       readUnlock( );
# }
# void justDoIt( ) {
#       writeLock( );
#       doIt( longOperation( ) );
#       writeUnlock( );
# }

I think this locking behavior better encapsulates functionality as the
caller doesn't need to know the locking needs (or restrictions) of the
function, and the function doesn't need to know the locking state of the
caller.

I believe APR's mutex operations are sufficient for creating this
implementation.  It's a little tricky as I need to either lock or fail to
lock multiple mutexes together (ie, if I can't lock both I don't want to
lock either), but I think I can do this with the following:

# void lock2( lockA, lockB ) {
#       while( 1 ) {
#               lock( lockA );
#               if( trylock( lockB ) ) return;
#               else unlock( lockA );
#       }
# }

Anyway, that's my goal, and while I'd love any feedback on my approach
(especially to point out any gaping logic holes I've overlooked), I think
I'm all set.

-david 

Reply via email to