RE: Can a thread write-lock a rwlock that it already has read-locked?
-Original Message- From: Branko ibej [mailto:[EMAIL PROTECTED] Subject: Re: Can a thread write-lock a rwlock that it already has read- locked? David Barrett wrote: 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. I think your algorithm is a deadlock waiting to happen. Yikes, that's a good example you give. I will definitely keep an eye on that. Also, I realize I was a bit glowing and flippant in extolling the virtues of my proposal. But its measure shouldn't be can it deadlock, because all locking schemes can. Rather, it should be is it easier to code non-deadlocking code with this? That's a judgment call, and even I haven't made up my mind yet. But I totally agree, inventing new locking schemes is a dangerous game, and I definitely hear your advice on sticking closer to the tried and true approaches. Thanks for the discussion. -david
Re: Can a thread write-lock a rwlock that it already has read-locked?
David Barrett wrote:
-Original Message-
From: Branko ibej [mailto:[EMAIL PROTECTED]
Subject: Re: Can a thread write-lock a rwlock that it already has read-
locked?
David Barrett wrote:
I'm experimenting with the reader/writer locks and have a question:
Can a thread write-lock a thread on which it already holds the read
lock?
No. A write lock is always exclusive.
Well yes, I agree. It's just that a write-lock seems to be a superset of
the read lock. In my mind, to have the write lock means I also must hold a
read lock, too (because I can both read and write). Thus from this
perspective, write-locking when I already have the read lock is akin to a
write lock + nested read-lock. Nested read locks are allowed (at least I
think they are -- nested mutex locks are, at least), so I think this should
be too.
I think you're confused by the read and write in the names of the
lock types. The read is a shared lock, which means that several
threads/processes/whatever can hold it at the same time, while the
write is an exclusive lock. Neither kind actually controls whether you
can read from or write to the protected resource, but since the whole
idea of locking is to prevent concurrent modifications to a resource,
the terms read lock and write lock are used synonymously with
shared and exclusive
Anyway, this is all moot. I understand that APR disallows my desired
behavior (with a reasonable justification), and as a workaround I'm using
mutexes to create a read/write lock that works as I want.
But while I'm on the moot point, I might add I think my desired behavior is
*much* easier to work with. Consider:
# get read lock
#result = long operation;
#if( result ) {
#get write lock
# do something
#release write lock
#}
# release read lock
Lock promotions are very hard to do correctly, and are usually not needed.
Without the ability to write lock while I hold the read lock, I'd need to
write-lock during the long operation, even though it's not algorithmically
required. This blocks other threads for an unnecessarily long period.
But you can change your algorithm like this:
done = false
while not done:
get shared lock
result = long operation
if result:
*release shared lock
*get exclusive lock
if result is valid:
do something
done = true
end if
release exclusive lock
end if
end while
There is of course a race condition between releasing the shared lock
and acquiring the exclusive lock, which is why you must check that the
result is still valid after acquiring the exclusive lock
(If I had an atomic upgrade to write lock command I could do that too.
But without that, I can't safely give up the read lock and then grab the
write lock, because a thread might come in and invalidate the results of my
long operation.)
Excatly. That's why you have to check the validity of the result. If the
price of having to recalculate the result is too high, or it happens too
often, then its better to do everything under the exclusive lock.
But regardless, I get what APR does, I have a workaround, and all is right
in the world.
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.
-- Brane
RE: Can a thread write-lock a rwlock that it already has read-locked?
-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
Re: Can a thread write-lock a rwlock that it already has read-locked?
David Barrett wrote: 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. I think your algorithm is a deadlock waiting to happen. Consider the following situation: thraad A acquires read lock thread B acquires read lock thread C acquires read lock thread A requests write lock (blocks) thread B requests write lock (blocks) thread C releases read lock At this point, threads A and B are both waiting for other readers to release their locks, and there are no writers yet. So they're waiting for each other. Even if you allow a single thread to own a write and any number of read locks simultaneously, you can't avoid this kind of deadlock unless each thread releases all its read locks before acquiring a write lock. The best you can do is to fail a write-lock request if another thread is waiting for the write lock, but to avoid the deadlock the thread whose write-lock failed would still have to release all its read locks before retrying the request. Again, you end up with the algorithm I showed in my previous post, except that the code gets even more complex. All in all, I'd advise not trying to invent a better way of locking, but to use proven methods. Locking is notoriously tricky. -- Brane
RE: Can a thread write-lock a rwlock that it already has read-locked?
-Original Message-
From: Branko ibej [mailto:[EMAIL PROTECTED]
Subject: Re: Can a thread write-lock a rwlock that it already has read-
locked?
David Barrett wrote:
I'm experimenting with the reader/writer locks and have a question:
Can a thread write-lock a thread on which it already holds the read
lock?
No. A write lock is always exclusive.
Well yes, I agree. It's just that a write-lock seems to be a superset of
the read lock. In my mind, to have the write lock means I also must hold a
read lock, too (because I can both read and write). Thus from this
perspective, write-locking when I already have the read lock is akin to a
write lock + nested read-lock. Nested read locks are allowed (at least I
think they are -- nested mutex locks are, at least), so I think this should
be too.
Anyway, this is all moot. I understand that APR disallows my desired
behavior (with a reasonable justification), and as a workaround I'm using
mutexes to create a read/write lock that works as I want.
But while I'm on the moot point, I might add I think my desired behavior is
*much* easier to work with. Consider:
# get read lock
#result = long operation;
#if( result ) {
#get write lock
# do something
#release write lock
#}
# release read lock
Without the ability to write lock while I hold the read lock, I'd need to
write-lock during the long operation, even though it's not algorithmically
required. This blocks other threads for an unnecessarily long period.
(If I had an atomic upgrade to write lock command I could do that too.
But without that, I can't safely give up the read lock and then grab the
write lock, because a thread might come in and invalidate the results of my
long operation.)
But regardless, I get what APR does, I have a workaround, and all is right
in the world.
-david
Re: Can a thread write-lock a rwlock that it already has read-locked?
David Barrett wrote: I'm experimenting with the reader/writer locks and have a question: Can a thread write-lock a thread on which it already holds the read lock? No. A write lock is always exclusive. -- Brane
Can a thread write-lock a rwlock that it already has read-locked?
I'm experimenting with the reader/writer locks and have a question: Can a thread write-lock a thread on which it already holds the read lock? My tests seem to indicate that this is not allowed, but I want to confirm this is by design and not something I'm just doing wrong. Specifically, I'm using the following code: # apr_pool_t* pool; # apr_pool_create( pool, 0 ); # apr_thread_rwlock_t* lock; # apr_thread_rwlock_create( lock, pool ); # apr_thread_rwlock_rdlock( lock ); # apr_thread_rwlock_wrlock( lock ); // Hangs on this line # apr_thread_rwlock_unlock( lock ); Is this working as designed? I'm running this test on Win32. My followup question is, is there any way to override this behavior? It would seem to me that a thread could safely hold both a read and write lock, so long as no other thread held either. Furthermore, it'd be nice to give up the write lock without giving up the read lock. The pattern I'd like to use is something like: # get read lock #do some tests to decide if I need to write anything # get the write lock # make some changes # give up the write lock #do some more stuff just with the read lock # give up the read lock Is there something fundamentally wrong with this pattern that I'm not seeing? Is there some compelling reason why the rwlock must disallow a thread from holding both a read and write lock? -david
Re: Can a thread write-lock a rwlock that it already has read-locked?
On Thu, Oct 14, 2004 at 06:17:39PM -0600, David Barrett wrote: I'm experimenting with the reader/writer locks and have a question: Can a thread write-lock a thread on which it already holds the read lock? Hey, I answered that one already :) apr_thread_rwlock.h in 1.0 says: * Note: The following operations have undefined results: unlocking a * read-write lock which is not locked in the calling thread; write * locking a read-write lock which is already locked by the calling * thread; ... My followup question is, is there any way to override this behavior? It would seem to me that a thread could safely hold both a read and write lock, so long as no other thread held either. Furthermore, it'd be nice to give up the write lock without giving up the read lock. The pattern I'd like to use is something like: No, there's no way round it, APR just matches what the underlying rwlock semantics are. It's just the case that you have to take the write lock up front if you're going to be making changes, I suppose. joe
