[Q] convert read lock on pthread_rwlock to write lock...
Chung Ha-nyung
Hi.
I wanna convert read lock to write lock atomically.
U know, pthread_rwlock_unlock & pthread_rwlock_wrlock is not a critical
region and other trials to get read/write lock on the same rwlock can
interrupt between two calls, unlock & wrlock.
I thought about using wrapper functions w/ mutexes but it seemed to be
a bit slow. ;(
--
Chung Ha-nyung <alita@[kldp.org|neowiz.com]>
SayClub <http://www.sayclub.com>
NeoWiz <http://www.neowiz.com>
Kaz Kylheku
>
> Hi.
>
> I wanna convert read lock to write lock atomically.
This makes *much* less sense than you might think.
I've been down that road; namely, I hastily implemented an ``upgrade''
operation in a library supporting read/write locks. This operation was
supposed to do what you are asking for: atomically switch a read lock
to a write lock.
But then I reasoned about it properly, and backed out the addition of
this operation, because it can't possibly work.
The problem is that there can be many readers, and many of them
might want to upgrade to a write lock at the same time.
Well, it cannot possibly happen atomically for all of them. At most,
it can happen for one of them.
Someone has to be first in getting the upgrade to the write lock. The rest
cannot get an atomic upgrade, because this first one has interrupted them
by obtaining the upgrade.
At best, what you can implement is a try_upgrade operation, which will
upgrade you to a write lock *if it can*, or else will return a failure
indication to tell you that some other reader got the upgrade.
This might still provide a wortwhile optimization in some cases,
but it increases the complexity of the program, which needs to have
a fallback strategy for when the upgrade cannot be obtained.
David Schwartz
> The problem is that there can be many readers, and many of them
> might want to upgrade to a write lock at the same time.
>
> Well, it cannot possibly happen atomically for all of them. At most,
> it can happen for one of them.
>
> Someone has to be first in getting the upgrade to the write lock. The rest
> cannot get an atomic upgrade, because this first one has interrupted them
> by obtaining the upgrade.
>
> At best, what you can implement is a try_upgrade operation, which will
> upgrade you to a write lock *if it can*, or else will return a failure
> indication to tell you that some other reader got the upgrade.
Another thing you can do is issue an 'upgradable' read lock. Only one
thread can hold an 'upgradable' read lock at a time, but any number of
threads can hold a read lock while one thread holds an upgradable lock.
When a thread attempts to upgrade its read lock, you simply block until
all read locks are released.
This is a highly specialized optimization and it is rare to find a case
where the effort is worth it. In general, you're best bet is to either
grab a write lock if there's any chance you might need one or restart
the operation (releasing your read lock and acquiring a write lock) if
you discover you need a write lock in mid-stream (while doing an
operation that had a very low chance of requiring a read lock).
DS
DS
Kaz Kylheku
>Kaz Kylheku wrote:
>> At best, what you can implement is a try_upgrade operation, which will
>> upgrade you to a write lock *if it can*, or else will return a failure
>> indication to tell you that some other reader got the upgrade.
>
> Another thing you can do is issue an 'upgradable' read lock. Only one
>thread can hold an 'upgradable' read lock at a time, but any number of
>threads can hold a read lock while one thread holds an upgradable lock.
>When a thread attempts to upgrade its read lock, you simply block until
>all read locks are released.
Thought of that one; it doesn't seem all that useful.
> This is a highly specialized optimization and it is rare to find a case
>where the effort is worth it. In general, you're best bet is to either
Something like: a rarely executed operation that involves a long,
time-consuming search of the read-locked data structure followed by
an update depending on the results of the search in such a way
that giving up the lock would require re-doing the computation.
The fact that the initial computation is long makes a write lock
poor, since it locks out other readers. So doing it in parallel with
other readers would be nice, but then because only one thread can be
doing that, which is why the other criterion is that this be a rarely
executed operation.
David Schwartz
> Thought of that one; it doesn't seem all that useful.
My point in brining it up was not so much to suggest that anyone use it
but to remind people that once you know your exact locking needs, it may
be worth investingating 'unusual' algorithms optimized for that
particular set of requirements.
However, unless you can demonstrate that the locking is a problem,
you're probably better off sticking to generic locking techniques for
two reasons. First, custom locks are more likely to cause problems if
you don't thorougly debug them. Second, custom locks may wind up being
suboptimal if the locking patterns change.
But if you do need locks that are optimized for a particular access
pattern, chances are there's a way to get them.
DS
Joe Seigh
Chung Ha-nyung wrote:
>
> Hi.
>
> I wanna convert read lock to write lock atomically.
> U know, pthread_rwlock_unlock & pthread_rwlock_wrlock is not a critical
> region and other trials to get read/write lock on the same rwlock can
> interrupt between two calls, unlock & wrlock.
You just need another mutex to coordinate only threads trying to update.
Read only access would still be
pthread_rwlock_rdlock
... // read date
pthread_rwlock_unlock
Read and then update would be
pthread_mutex_lock
pthread_rwlock_rdlock
... // read data
pthread_rwlock_unlock
pthread_rwlock_wrlock
... // update data
pthread_rwlock_unlock
pthread_mutex_unlock
No pthread_rwlock_wrlocks anywhere without the mutex
wrapper!
> I thought about using wrapper functions w/ mutexes but it seemed to be
> a bit slow. ;(
Shouldn't be. Low contention mutexes should be fairly efficient.
Joe Seigh
Joe Seigh
As an interesting side note, I always though that a bakery style
spin lock would be quite adaptable to use as an upgrade lock.
Basically the rules for bakery style read/write locks are
writers wait for all prior accesses to complete
readers wait for all prior write accesses to complete
read then write would be
wait for all prior write accesses to complete
perform read access
wait for all prior read accesses to complete
perform write access
In pseudo C w/ perl style assignments so I can show
the atomic bits which would probably be implemented
with compare and swap or something.
// global
int cs = 0; // current
int cx = 0;
int ns = 0; // next
int nx = 0;
// thread local
int ws = 0; // wait
int wx = 0;
// read
(ws, wx) = (ns++, nx); // atomic
while (wx != cx) {} // wait for prior write accesses to complete
... // read access
cs++; // complete read access
// write
(ws, wx) = (ns, nx++); // atomic
while (wx != cx && ws != cs) {} // wait for prior accesses to complete
... // write access
cx++; // complete write access
// note that
// while (wx != cx && ws != cs)
// is equivalent to
// while (wx != cx) {}
// while (ws != cs) {}
// read then upgrade to write
(ws, wx) = (ns, nx++); // atomic
while (wx != cx) {} // wait for prior write accesses to complete
... // read access
while (ws != cs) {} // wait for prior read accesses to complete
... // write access
cx++; // complete write access
Joe Seigh
Bil Lewis
probably want to keep in mind that it will almost
never be useful. Simple RWLocks are already so
specialized and expensive that they are rarely
useful.
RWLocks are ~4x more expensive than mutexes.
Most shared data is accessed for a very short
time, typically less than the cost of a mutex
lock/unlock. Very few locks have any contention.
So...
How much contention, average access time, and
difference between RWLocks & mutexes give the
advantage to the RWLock?
How often are those conditions met?
Now do those same numbers for the convertible.
-Bil
(But don't get me wrong. It's still a cool thing
to do.)
Joe Seigh
True, it all depends on the factors involved. Bear
in mind though some of it is a self fulfilling prophecy.
If you start out writing an operating system with
only mutexes, mutex contention is so expensive that
when it happens the system is changed to avoid it.
So when you analyse the system to determine whether
rwlocks will buy you anything, you find there is
little to no lock contention to justify using
rwlocks.
Brings to mind that joke. There's this river with
no bridge over it. Somebody decides that it would
be useful to have a bridge over it, so they send
out some people to gather requirements for a
bridge. These people eventually report back
and report that analysis of traffic over the
river shows that there's no need for a bridge.
Joe Seigh