Аsymmetric rw_mutex

76 views
Skip to first unread message

Dmitriy Vyukov

unread,
Jun 21, 2007, 6:24:27 AM6/21/07
to
Аsymmetric rw_mutex with no atomic_rmw/membars on reader side! No
joke!
Here is the sketch:

class arw_mutex_t
{
private:
mutex_t guard;
unsigned reader_count;
bool volatile writer_pending;

public:
arw_mutex_t()
: reader_count()
, writer_pending()
{}

void register_reader()
{
lock_t lock (guard);
++reader_count;
}

void unregister_reader()
{
notify_writer();
lock_t lock (guard);
--reader_count;
}

void reader_lock()
{
if (writer_pending)
{
notify_writer();
wait_for_writer_notification();
}
}

void reader_unlock()
{
}

void writer_lock()
{
guard.lock();
writer_pending = true;
wait_for_all_readers_notifications();
writer_pending = false;
}

void writer_unlock()
{
notify_all_readers();
guard.unlock();
}
};


-------------------------------------------------

Usage example:

arw_mutex_t guard;

void reader_thread()
{
guard.register_reader();
while (!stop)
{
guard.reader_lock();
read_some();
guard.reader_unlock();
}
guard.unregister_reader();
}

void writer_thread()
{
while (!stop)
{
guard.writer_lock();
write_some();
guard.writer_unlock();
sleep_some();
}
}

The only requirement - reader must periodically execute reader_lock()/
reader_unlock() while he is registered. Else it will prevent writer
from acquiring the mutex.


Dmitriy V'jukov

Dmitriy Vyukov

unread,
Jun 21, 2007, 6:37:39 AM6/21/07
to
On Jun 21, 2:24 pm, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
> Аsymmetric rw_mutex with no atomic_rmw/membars on reader side! No
> joke!


I don't make real implementation and full testing yet. But I am sure
the idea is working.


Notification mechanism can be implemented with semaphore, because we
know exactly how many readers will be waiting on it. Here no race
conditions because register_reader()/unregister_reader() protected
with the same mutex as writer_lock()/writer_unlock().
unregister_reader() must be implemented carefully to prevent deadlock
with writer_lock().


If reader for a long time don't want to acquire mutex, he can execute
something like this:

void reader_sync()
{
reader_lock();
reader_unlock();
}

Or reader just can unregister and then register again when he start
work with mutex.


Dmitriy V'jukov

Torsten Robitzki

unread,
Jun 21, 2007, 6:45:54 AM6/21/07
to
Dmitriy Vyukov wrote:

> Аsymmetric rw_mutex with no atomic_rmw/membars on reader side! No
> joke!
> Here is the sketch:

> void reader_unlock()
> {
> }

Wow, that's really very little overhead ;-)

Dmitriy Vyukov

unread,
Jun 21, 2007, 6:43:45 AM6/21/07
to
On Jun 21, 2:45 pm, Torsten Robitzki <MyFirstn...@Robitzki.de> wrote:

> Wow, that's really very little overhead ;-)

Yes. If there are no writers waiting, then variable writer_pending
will be cached in readers cores caches. So all reader lock/unlock
cycle is no more then reading one cached word and one compare!


Dmitriy V'jukov

Chris Thomasson

unread,
Jun 21, 2007, 7:09:31 AM6/21/07
to
I am looking at your code... One very quick concern:

[...]
___


void reader_lock()
{
if (writer_pending)
{
notify_writer();
wait_for_writer_notification();
}
}

___

Since there is a writer_pending flag, I think you may have to use "at least"
a #LoadLoad membar here instead of a data-dependency for the readers... It
might end up requiring a #LoadStore | #LoadLoad...

Chris Thomasson

unread,
Jun 21, 2007, 7:14:54 AM6/21/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1182421467.8...@z28g2000prd.googlegroups.com...

Аsymmetric rw_mutex with no atomic_rmw/membars on reader side! No
joke!
Here is the sketch:
[...]

Also, not quite sure how writers know when readers are finished, I have some
ideas, however your read_unlock gives no "real" clues... I mean, I would
think that the read_unlock wrt rw-mutex would involve at least a single
atomic store...

;^)

Dmitriy Vyukov

unread,
Jun 21, 2007, 7:14:06 AM6/21/07
to

As I understand, I don't need any membars here. Because here is
control-dependency on writer_pending. Processors must respect it.
Idea is the next: reader will see writer_pending == true sometime, no
matter when exactly and then he will execute notify_writer()/
wait_for_writer_notification() which definitely contain full membars.
But I will be very appreciate if you examine code in detail and say
whether here must be any membar or not.


Dmitriy V'jukov

Dmitriy Vyukov

unread,
Jun 21, 2007, 7:20:20 AM6/21/07
to
On Jun 21, 3:14 pm, "Chris Thomasson" <cris...@comcast.net> wrote:

> Also, not quite sure how writers know when readers are finished, I have some
> ideas, however your read_unlock gives no "real" clues... I mean, I would
> think that the read_unlock wrt rw-mutex would involve at least a single
> atomic store...

No. read_unlock() is really empty.
Writer will know that readers are finished when all readers will see
(writer_pending == true) and execute notify_writer() after that.

Dmitriy V'jukov

Chris Thomasson

unread,
Jun 21, 2007, 7:35:44 AM6/21/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1182424820.0...@o11g2000prd.googlegroups.com...

Okay; I see that now. IMHO, this doesn't look that different than something
like RCU. However, I think I see a possible race-condition that could allow
a read and write to happen concurrently. I am definitely not sure yet. I
need to work out the possible execution scenarios which I think could trip
the possible race-condition.

Chris Thomasson

unread,
Jun 21, 2007, 7:39:02 AM6/21/07
to
"Chris Thomasson" <cri...@comcast.net> wrote in message
news:fd2dnZZ97IwJ_Ofb...@comcast.com...

> "Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
> news:1182424820.0...@o11g2000prd.googlegroups.com...
>> On Jun 21, 3:14 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>>
>>> Also, not quite sure how writers know when readers are finished, I have
>>> some
>>> ideas, however your read_unlock gives no "real" clues... I mean, I would
>>> think that the read_unlock wrt rw-mutex would involve at least a single
>>> atomic store...
>>
>> No. read_unlock() is really empty.
>> Writer will know that readers are finished when all readers will see
>> (writer_pending == true) and execute notify_writer() after that.
>
> Okay; I see that now. IMHO, this doesn't look that different than
> something like RCU.

The quiescent states are requested by the writers...

Dmitriy Vyukov

unread,
Jun 21, 2007, 7:49:07 AM6/21/07
to
On Jun 21, 3:35 pm, "Chris Thomasson" <cris...@comcast.net> wrote:

> Okay; I see that now. IMHO, this doesn't look that different than something
> like RCU. However, I think I see a possible race-condition that could allow
> a read and write to happen concurrently. I am definitely not sure yet. I
> need to work out the possible execution scenarios which I think could trip
> the possible race-condition.

Yes, arw_mutex_t have something in common with RCU, but not very much,
no more than any other "membarless" technique.
First of all, this is mutex and not memory reclamation scheme :)
Second, readers don't make any epochs, writer notify them, so readers
are more passive.

Let me describe the idea.
Assume there is only one writer (because writer part protected with
mutex).
Assume readers don't register and unregister and there are N readers.
Writer set writer_pending = true. And then wait when all N readers
will see writer_pending == true and notify him.
Every reader will eventually see that writer_pending == true and then
notify writer and wait when writer finish writing and notify him.
When writer see that all N readers notify him, he execute critical
section. And then notify all readers that he is finished.
When reader see that writer notify him, he can continue with reading.

For the time present I don't see any races here, I see full order
between readers and writer.

Dmitriy V'jukov

Dmitriy Vyukov

unread,
Jun 21, 2007, 7:51:57 AM6/21/07
to
On Jun 21, 3:39 pm, "Chris Thomasson" <cris...@comcast.net> wrote:

> > Okay; I see that now. IMHO, this doesn't look that different than
> > something like RCU.
>
> The quiescent states are requested by the writers...

But this is still not memory reclamation scheme :)

Dmitriy V'jukov


Chris Thomasson

unread,
Jun 21, 2007, 8:00:01 AM6/21/07
to
[...]

> I am definitely not sure yet. I need to work out the possible execution
> scenarios which I think could trip the possible race-condition.

Okay. I don't think the race will occur now. Well, it seems like the idea
should work. It seems similar to vZOOM manual pdr epoch detection in which
reader threads needs to periodically/episodically do something in order to
keep things moving. Except in your setup a write to a collection cannot
concurrently execute along side reads. Given than, I think it should
outperform most conventional rw-locks...

Chris Thomasson

unread,
Jun 21, 2007, 8:03:23 AM6/21/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1182426717....@i38g2000prf.googlegroups.com...

Well, I think your still effectively deferring any possible pointers to
allocated memory that are used in the critical section of the rw-mutex from
being deleted until there are no readers... So, a rw-mutex could be
analogous to PDR in that sense... Humm...


Chris Thomasson

unread,
Jun 21, 2007, 8:11:10 AM6/21/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1182424446.1...@g37g2000prf.googlegroups.com...

> On Jun 21, 3:09 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>> I am looking at your code... One very quick concern:
>>
>> [...]
>> ___
>> void reader_lock()
>> {
>> if (writer_pending)
>> {
>> notify_writer();
>> wait_for_writer_notification();
>> }
>> }
>>
>> ___
>>
>> Since there is a writer_pending flag, I think you may have to use "at
>> least"
>> a #LoadLoad membar here instead of a data-dependency for the readers...
>> It
>> might end up requiring a #LoadStore | #LoadLoad...
>
> As I understand, I don't need any membars here. Because here is
> control-dependency on writer_pending. Processors must respect it.

Isn't that arch dependent behavior?


> But I will be very appreciate if you examine code in detail and say
> whether here must be any membar or not.

Humm... I think it depends on:

wait_for_all_readers_notifications();
writer_pending = false;


A load to writer_pending could get reordered.. I think its similar situation
wrt using a DCL algorithm with an extra level of indirection (e.g., a flag
that says the pointer has been stored to). The load to the flag needs to be
followed by a #LoadLoad. However, your depending on a control-dependency wrt
branching on the value of writer_pending... Need to think some more on
this.

Chris Thomasson

unread,
Jun 21, 2007, 9:15:44 AM6/21/07
to
"Chris Thomasson" <cri...@comcast.net> wrote in message
news:F86dnSIVRILY-ufb...@comcast.com...

Mabey all "conventional" rw-locks...

;^)

Dmitriy Vyukov

unread,
Jun 21, 2007, 9:15:53 AM6/21/07
to
On Jun 21, 4:11 pm, "Chris Thomasson" <cris...@comcast.net> wrote:

> Isn't that arch dependent behavior?

It must work on x86. I am not sure about others. But I think it must
work.


> Humm... I think it depends on:
>
> wait_for_all_readers_notifications();
> writer_pending = false;
>
> A load to writer_pending could get reordered.. I think its similar situation
> wrt using a DCL algorithm with an extra level of indirection (e.g., a flag
> that says the pointer has been stored to). The load to the flag needs to be
> followed by a #LoadLoad. However, your depending on a control-dependency wrt
> branching on the value of writer_pending... Need to think some more on
> this.

I rely on control-dependency...
If this is the problem and we need #LoadLoad here then maybe we can
make the same thing like in DCL w/o an extra level of indirection.
I.e. combine pointer to the user object and writer_pending flag...

Dmitriy V'jukov

Chris Thomasson

unread,
Jun 21, 2007, 9:22:06 AM6/21/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1182426547.3...@d30g2000prg.googlegroups.com...

> On Jun 21, 3:35 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> Okay; I see that now. IMHO, this doesn't look that different than
>> something
>> like RCU. However, I think I see a possible race-condition that could
>> allow
>> a read and write to happen concurrently. I am definitely not sure yet. I
>> need to work out the possible execution scenarios which I think could
>> trip
>> the possible race-condition.
>
> Yes, arw_mutex_t have something in common with RCU, but not very much,
> no more than any other "membarless" technique.
> First of all, this is mutex and not memory reclamation scheme :)
> Second, readers don't make any epochs, writer notify them, so readers
> are more passive.

How are you handling the possibility of registered thread's blocking? Like
if a registered reader thread needs to read something that it could possible
have to block on... And the blocking is possibly dependant on some other
registered threads, and non-registered threads, or even i/o... This is where
the automatic epoch detection comes in real handy. ;^)


Dmitriy Vyukov

unread,
Jun 21, 2007, 9:20:22 AM6/21/07
to
On Jun 21, 4:03 pm, "Chris Thomasson" <cris...@comcast.net> wrote:

> > But this is still not memory reclamation scheme :)
>
> Well, I think your still effectively deferring any possible pointers to
> allocated memory that are used in the critical section of the rw-mutex from
> being deleted until there are no readers... So, a rw-mutex could be
> analogous to PDR in that sense... Humm...

Yes, of course.
But this is not like PDR, this is more like usual mutex here. I.e. you
can safely reclaim memory on writer side with classical rw_mutex. And
arw_mutex is semantically like classical rw_mutex. So you certainly
can safely reclaim memory with arw_mutex too.


Dmitriy V'jukov

Dmitriy Vyukov

unread,
Jun 21, 2007, 9:22:40 AM6/21/07
to
On Jun 21, 5:15 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
> "Chris Thomasson" <cris...@comcast.net> wrote in message

>
> Given than, I think it should
> outperform most conventional rw-locks...
>
> Mabey all "conventional" rw-locks...

It should kill all other rw-locks! :)

Dmitriy V'jukov

Dmitriy Vyukov

unread,
Jun 21, 2007, 9:26:14 AM6/21/07
to
On Jun 21, 5:22 pm, "Chris Thomasson" <cris...@comcast.net> wrote:

> How are you handling the possibility of registered thread's blocking? Like
> if a registered reader thread needs to read something that it could possible
> have to block on... And the blocking is possibly dependant on some other
> registered threads, and non-registered threads, or even i/o... This is where
> the automatic epoch detection comes in real handy. ;^)

If reader is going to do some long-running/blocking operation then he
can unregister from arw_mutex and then register again.


Dmitriy V'jukov

Dmitriy Vyukov

unread,
Jun 21, 2007, 9:44:02 AM6/21/07
to
On Jun 21, 5:22 pm, Dmitriy Vyukov <dvyu...@gmail.com> wrote:

Why subject periodically changed to 'symmetric rw_mutex'? I don't do
this! It seems some bug in Google.Groups...

Dmitriy V'jukov

Chris Thomasson

unread,
Jun 21, 2007, 9:51:07 AM6/21/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1182432374.4...@d30g2000prg.googlegroups.com...

Well, I was talking about the possibility of readers blocking unexpectedly
on something. You seem to be suggesting that readers have to have prior
knowledge of exactly where and when they will be blocking. Am I way off base
here? I think I understand your idea about 99%... Good job.

Zeljko Vrba

unread,
Jun 21, 2007, 9:53:06 AM6/21/07
to

What if the OS scheduler suspends the reader for indeterminate amount of time?
And reader does *not* know in advance that it's going to be preempted.

Chris Thomasson

unread,
Jun 21, 2007, 10:05:14 AM6/21/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1182433442....@g37g2000prf.googlegroups.com...

> On Jun 21, 5:22 pm, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
>
> Why subject periodically changed to 'symmetric rw_mutex'? I don't do
> this! It seems some bug in Google.Groups...

Strange; on my newsreader, it appears as:

'?symmetric rw_mutex'

on google, it appears like it should appear: ? == A.

Chris Thomasson

unread,
Jun 21, 2007, 10:11:55 AM6/21/07
to
"Zeljko Vrba" <zvrba....@ieee-sb1.cc.fer.hr> wrote in message
news:slrnf7l0m1...@ieee-sb1.cc.fer.hr...

That's one possible scenario in which automatic epoch detection comes in
handy. Of course, this is why any automatic detection is usually 100%
non-portable... Well, I guess a signal-based algorithm I developed can make
it "more" portable wrt operating systems other than Windows. On windows, the
most portable automatic algorithm I can come up with involves using the
undocumented native Nt API, or using an SEH hack.

As for blocking, I was thinking of calls to an abstract i/o read function
that is implemented by a third-party which can decide to block the calling
thread until it has something to read...

Dmitriy Vyukov

unread,
Jun 21, 2007, 10:08:30 AM6/21/07
to
On Jun 21, 5:51 pm, "Chris Thomasson" <cris...@comcast.net> wrote:

> Well, I was talking about the possibility of readers blocking unexpectedly
> on something. You seem to be suggesting that readers have to have prior
> knowledge of exactly where and when they will be blocking. Am I way off base
> here? I think I understand your idea about 99%... Good job.

Yes, this is the weak place.
And this is why I name it 'Asymmetric'. Because it moves priority to
readers even more. And this permits readers to work w/o membars.
And if this happens (reader go to sleep unexpectedly) nothing really
horrible doesn't happen, writer just will wait for the reader.
And this can happen with classical rw_mutex too if reader will go to
sleep unexpectedly in critical section.


Dmitriy V'jukov

Chris Thomasson

unread,
Jun 21, 2007, 10:13:56 AM6/21/07
to
[...]

> As for blocking, I was thinking of calls to an abstract i/o read function
> that is implemented by a third-party which can decide to block the calling
> thread until it has something to read...

In other words, the call to the i/o function could just block without
informing your thread ahead of time.

Dmitriy Vyukov

unread,
Jun 21, 2007, 10:10:33 AM6/21/07
to
On Jun 21, 5:53 pm, Zeljko Vrba <zvrba.nos...@ieee-sb1.cc.fer.hr>
wrote:

> What if the OS scheduler suspends the reader for indeterminate amount of time?
> And reader does *not* know in advance that it's going to be preempted.

Please see the answer here:
http://groups.google.com/group/comp.programming.threads/msg/12c17873bc153761?hl=en&


Dmitriy V'jukov

Dmitriy Vyukov

unread,
Jun 21, 2007, 10:12:46 AM6/21/07
to

This can be handled be explicitly unregister reader before call to
suspicious function.


Dmitriy V'jukov

Chris Thomasson

unread,
Jun 21, 2007, 10:20:48 AM6/21/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1182434910....@a26g2000pre.googlegroups.com...

> On Jun 21, 5:51 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> Well, I was talking about the possibility of readers blocking
>> unexpectedly
>> on something.
[...]

> Yes, this is the weak place.
[...]

> And this can happen with classical rw_mutex too if reader will go to
> sleep unexpectedly in critical section.

Well, this is one of the reasons why you never "should" be calling any
function(s) that have the possibility of blocking the calling thread within
any critical-section... The blocking could be unexpected and the total time
of blocking could possibly be long, medium, short, or whatever... Humm, I
think you need to clarify the usage pattern and caveats...

Chris Thomasson

unread,
Jun 21, 2007, 10:21:29 AM6/21/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1182435166.9...@d30g2000prg.googlegroups.com...

Yup. That would work for sure.

Chris Thomasson

unread,
Jun 21, 2007, 10:26:01 AM6/21/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1182431753.5...@d30g2000prg.googlegroups.com...

> On Jun 21, 4:11 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> Isn't that arch dependent behavior?
>
> It must work on x86. I am not sure about others. But I think it must
> work.

You could just use an explicit load-style barrier call if in doubt.

>> Humm... I think it depends on:
>>
>> wait_for_all_readers_notifications();
>> writer_pending = false;
>>
>> A load to writer_pending could get reordered.. I think its similar
>> situation
>> wrt using a DCL algorithm with an extra level of indirection (e.g., a
>> flag
>> that says the pointer has been stored to).

[...]

> I rely on control-dependency...
> If this is the problem and we need #LoadLoad here then maybe we can
> make the same thing like in DCL w/o an extra level of indirection.
> I.e. combine pointer to the user object and writer_pending flag...

I think that may be a possible solution.

Dmitriy Vyukov

unread,
Jun 21, 2007, 10:43:30 AM6/21/07
to
On Jun 21, 6:20 pm, "Chris Thomasson" <cris...@comcast.net> wrote:

> Well, this is one of the reasons why you never "should" be calling any
> function(s) that have the possibility of blocking the calling thread within
> any critical-section... The blocking could be unexpected and the total time
> of blocking could possibly be long, medium, short, or whatever... Humm, I
> think you need to clarify the usage pattern and caveats...


Yes, of course... when I will know them by myself :)

So, suspicious functions we can handle by explicit unregistering.

And I think thread preempting be OS should not be a very big problem
in common case, provided that all threads have about the same
priority. I.e. there is no real-time critical thread that eat all
time. Further provided that all other threads (writer and all other
readers) must go to sleep (because writer set writer_pending flag). So
OS must wake up the reader thread and he eventually execute
notify_writer().
But definitely this is the hazard and significant point in asymmetric
rw_mutex.


Dmitriy V'jukov

Chris Thomasson

unread,
Jun 21, 2007, 7:35:43 PM6/21/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1182432022.9...@i13g2000prf.googlegroups.com...

> On Jun 21, 4:03 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> > But this is still not memory reclamation scheme :)
>>
>> Well, I think your still effectively deferring any possible pointers to
>> allocated memory that are used in the critical section of the rw-mutex
>> from
>> being deleted until there are no readers... So, a rw-mutex could be
>> analogous to PDR in that sense... Humm...
>
> Yes, of course.
> But this is not like PDR, this is more like usual mutex here. I.e.

I think that 'PDR' is a "broad enough" term to cover many different
synchronization techniques... Basically, when you find yourself deferring
"any" reclamations until there rendered safely quiescent, your "effectively"
making use of an algorithm that is "compatible" with the "overall"
definition of 'PDR'. IMHO, I think that virtually any sort of
mutual-exclusion method can be "thought of" as just another one of the basic
mechanisms covered by 'PDR' as a whole. Well, at least the 'DR' portion of
the acronym is relevant to mutexs and many other related mechanisms,
including some of the more "exotic" lock-free schemes.

IMHO, Deferred Reclamation of "any" allocations used in "critical-sections"
will be honored by the various mutual-exclusion schemes, therefore rendering
them compatible with the "root meaning" of 'PDR'. IMO, mutual-exclusion
techniques simply adds to the various examples of algorithms in which PDR
can apply/covers. Yes, the term is broad indeed!

;^)


Any thoughts?

Dmitriy Vyukov

unread,
Jun 24, 2007, 12:53:40 PM6/24/07
to
On 21 июн, 18:26, "Chris Thomasson" <cris...@comcast.net> wrote:

> > I rely on control-dependency...
> > If this is the problem and we need #LoadLoad here then maybe we can
> > make the same thing like in DCL w/o an extra level of indirection.
> > I.e. combine pointer to the user object and writer_pending flag...
>
> I think that may be a possible solution.

Anyway I think that #LoadLoad membar is not needed here, because every
processor must respect control-dependency. Otherwise the processor
will be not sequentially self-consistent.

Dmitriy V'jukov

Dmitriy Vyukov

unread,
Jun 24, 2007, 1:05:46 PM6/24/07
to
On 22 , 03:35, "Chris Thomasson" <cris...@comcast.net> wrote:
> "Dmitriy Vyukov" <dvyu...@gmail.com> wrote in message

Yes.
You miss 'P', or 'PCOW'.
With mutex you usually do (or at least you can do) 'inplace update'
and not 'partial copy-on-write'.
So it is not the example of PDR. It is example of IDR (Inplace update,
deferred reclamation)... and reclamation is not deferreed here. So it
is IIR (Inplace update, immediate reclamation) :)

Dmitriy V'jukov

Dmitriy Vyukov

unread,
Jun 24, 2007, 1:09:55 PM6/24/07
to
On 21 , 18:05, "Chris Thomasson" <cris...@comcast.net> wrote:

> Strange; on my newsreader, it appears as:
>
> '?symmetric rw_mutex'
>
> on google, it appears like it should appear: ? == A.

Maybe I type Russian 'A'... and your newsreader make some very-old-
unicode-unaware programmer :)

Dmitriy V'jukov

Dmitriy Vyukov

unread,
Jun 24, 2007, 2:49:46 PM6/24/07
to
On 21 июн, 14:24, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
> Аsymmetric rw_mutex with no atomic_rmw/membars on reader side! No
> joke!

So, here is some potential problem with reader thread unexpected
blocking. You can read more detailed here:
http://groups.google.ru/group/comp.programming.threads/tree/browse_frm/thread/b7d3b8c08f9ca3c6/8e9140133b01a35b?rnum=21&_done=%2Fgroup%2Fcomp.programming.threads%2Fbrowse_frm%2Fthread%2Fb7d3b8c08f9ca3c6%2Fcc13020190741308%3F#doc_8e9140133b01a35b

And here is another problem.
This mutex create additional dependency between writer thread and
reader thread and between reader thread and writer thread. Initially
dependencies are not cyclic. But you can make them cyclic relatively
easy. This would lead to deadlock.

For example, if reader execute SendMessage() (from Win32 API) to
writer, this can lead to deadlock. Because reader will be waiting for
writer to process the message and writer will be waiting for reader to
execute arw_mutex::read_lock().

Or if writer acquire another resource (mutex) and reader try to
acquire the same resource, this can lead to deadlock too. Because
reader will be waiting for writer to release the resource and writer
will be waiting for reader to execute arw_mutex::read_lock().

Or if reader1 execute SendMessage() (or try to acquire some resource)
to reader2, this can lead to deadlock too. Because reader1 will be
waiting for reader2 to process the message. Reader2 will be waiting
for writer to release arw_lock. And writer will be waiting for reader1
to execute arw_mutex::read_lock().

So from this point of view, this mutex can be called 'inverted
rw_mutex' or 'rw_mutex with inverted reader side'. Because the mutex
effectively acquired by reader all the time and released by reader
only sometimes (when writer require this). So critical section on
reader side extend from part of code surrounded with read_lock()/
read_unlock() to *all* reader thread code (between register_reader()/
unregister_reader() ).

Dmitriy V'jukov

Dmitriy Vyukov

unread,
Jun 24, 2007, 2:59:39 PM6/24/07
to
On 21 июн, 14:24, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
> Аsymmetric rw_mutex with no atomic_rmw/membars on reader side! No
> joke!

Here can be implemented writer batching.
I.e. if writer1 acquire arw_mutex for writing. And before writer1
release arw_mutex writer2 is arrived. writer1 can transfer mutex
ownership directly to writer2 instead of transferring ownership to
readers. This can help reduce overheads due to writer_lock()
operation.

This can be implemented by means of writer_count variable. Variable
must be maintained by writers by atomic operations.

Dmitriy V'jukov

Dmitriy Vyukov

unread,
Jun 24, 2007, 3:07:19 PM6/24/07
to
On 21 июн, 14:24, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
> Аsymmetric rw_mutex with no atomic_rmw/membars on reader side! No
> joke!

Operations register_reader()/unregister_reader() can be implemented
with only one atomic operation. This made register_reader()/
unregister_reader() operations light enough to execute them more
often.

To implement this we must use following structure.

struct count
{
unsigned short reader_count;
unsigned short writer_count;
};

By writer_count I mean number of writers that want to acquire mutex
for writing right now. This variable must be maintained by atomic
operations in register_reader()/unregister_reader() and write_lock()/
write_unlock().


Dmitriy V'jukov

Dmitriy Vyukov

unread,
Jun 24, 2007, 3:19:17 PM6/24/07
to
On 21 июн, 14:24, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
> Аsymmetric rw_mutex with no atomic_rmw/membars on reader side! No
> joke!

And here is one more very interesting feature.
Suppose writer_lock() operation looks like this:

void writer_lock()
{
writer_pending = true;
wait_for_all_readers_notifications();
writer_pending = false;
}

We can divide this operation on 2 parts. Like this:

void writer_lock_phase1()
{
writer_pending = true;
}

void writer_lock_phase2()
{
wait_for_all_readers_notifications();
writer_pending = false;
}

So writer can execute:
mutex1.writer_lock_phase1();
mutex2.writer_lock_phase1();
mutex3.writer_lock_phase1();

And then:
mutex1.writer_lock_phase2();
mutex2.writer_lock_phase2();
mutex3.writer_lock_phase2();

With some probability notifications for mutex2 and mutex3 arrive when
writer execute writer_lock_phase2() for them. So there will be no
blocking.

Or writer just can do some useful work between phase1 and phase2.

But here are some open questions with implementation of this stuff...

Dmitriy V'jukov

Dmitriy Vyukov

unread,
Jun 24, 2007, 3:46:41 PM6/24/07
to
On 21 июн, 14:24, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
> Аsymmetric rw_mutex with no atomic_rmw/membars on reader side! No
> joke!

And now I am thinking of the next issue.
Consider we have plurality of objects (each object contain mutex). And
objects created and destroyed continually. So readers just don't have
opportunity to register and unregister in every object.

Maybe we can bring out reader_count variable from arw_mutex to
separate entity. And arw_mutex will contain pointer to the entity...

Or maybe we can steal some techniques from RCU (while arw_mutex is
similar to RCU :) ). Maybe we can eliminate reader_count at all and
instead create some quiescent states for readers. And after quiescent
period writer can modify object safely...

And one more thought.
If we bring out reader_count variable from arw_mutex to separate
entity, maybe we can create two-level mutex, that can be locked for
individual object (low level) or can be locked for "all" objects (high
level). I mean that several mutexes point to one entity that contain
reader_count. With such mutex hash-table with lock per node can be
implemented very effectively. And this still with no membars on reader
side.

But for now this is just thoughts...

Dmitriy V'jukov

Chris Thomasson

unread,
Jun 25, 2007, 5:49:52 AM6/25/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1182704995.7...@w5g2000hsg.googlegroups.com...

;^)

Chris Thomasson

unread,
Jun 25, 2007, 5:50:24 AM6/25/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1182704020....@k79g2000hse.googlegroups.com...

Ask this over on comp.arch

Chris Thomasson

unread,
Jun 25, 2007, 5:52:57 AM6/25/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1182704746.5...@m36g2000hse.googlegroups.com...
[...]

>> > On Jun 21, 4:03 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
[...]

>> Any thoughts?
>
> Yes.
> You miss 'P', or 'PCOW'.
> With mutex you usually do (or at least you can do) 'inplace update'
> and not 'partial copy-on-write'.
[...]

Partial copy-on-write means that your not copying a substantial potion of
the collection you whish to modify. This is applicable under lock-free means
or lock-based means. PDR cover's ALL OF ITS BASES!.

Dmitriy Vyukov

unread,
Jun 25, 2007, 6:35:37 AM6/25/07
to
On Jun 25, 1:52 pm, "Chris Thomasson" <cris...@comcast.net> wrote:

> Partial copy-on-write means that your not copying a substantial potion of
> the collection you whish to modify. This is applicable under lock-free means
> or lock-based means. PDR cover's ALL OF ITS BASES!.

But COW also means that you *copy* some part of data structure. With
mutex this is false.

Anyway if mutex is also PDR, then term PDR is practically useless,
because it is toooooo broad...

And why you are trying to bring together [my] mutex and PDR? Is there
some clandestine purport? ;)


Dmitriy V'jukov

Chris Thomasson

unread,
Jun 25, 2007, 7:22:55 AM6/25/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1182767737.0...@e9g2000prf.googlegroups.com...

> On Jun 25, 1:52 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> Partial copy-on-write means that your not copying a substantial potion of
>> the collection you whish to modify. This is applicable under lock-free
>> means
>> or lock-based means. PDR cover's ALL OF ITS BASES!.
>
> But COW also means that you *copy* some part of data structure. With
> mutex this is false.

The rules wrt COW can be governed under PDR.

> Anyway if mutex is also PDR, then term PDR is practically useless,
> because it is toooooo broad...

That was the point: To come with a broad enough term to cover ref-counting,
proxy gc, mutexs, ect...

> And why you are trying to bring together [my] mutex and PDR? Is there
> some clandestine purport? ;)

There is nothing new under the sun. Sorry for the salty attitude. All joking
aside, I think your algorithm is worth while.

Chris Thomasson

unread,
Jun 25, 2007, 7:31:32 AM6/25/07
to

"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1182714401.7...@o61g2000hsh.googlegroups.com...

> On 21 июн, 14:24, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
>> Аsymmetric rw_mutex with no atomic_rmw/membars on reader side! No
>> joke!
>
> And now I am thinking of the next issue.
> Consider we have plurality of objects (each object contain mutex). And
> objects created and destroyed continually. So readers just don't have
> opportunity to register and unregister in every object.

Okay.

> Maybe we can bring out reader_count variable from arw_mutex to
> separate entity. And arw_mutex will contain pointer to the entity...

Humm.

> Or maybe we can steal some techniques from RCU (while arw_mutex is
> similar to RCU :) ). Maybe we can eliminate reader_count at all and
> instead create some quiescent states for readers. And after quiescent
> period writer can modify object safely...

That's the idea. RCU and reader count are non-related in a sense. RCU
decouple writers from readers in a way that allows them to both operate
concurrently. The user-state that can govern quiescent-states can exist in
any mutex, reference-counting or lock-free algorithm for that matter. Indeed
PDR is broad enough to keep itself relevant to state-of-the-art like your
algorithms posted here, or even down to the traditional level such as
mutex/rw-mutex.

Agreed?


> And one more thought.
> If we bring out reader_count variable from arw_mutex to separate
> entity, maybe we can create two-level mutex, that can be locked for
> individual object (low level) or can be locked for "all" objects (high
> level).

That's a from of PDR: IMVHO, PDR does NOT tie itself down to lock only
techniques.

> I mean that several mutexes point to one entity that contain
> reader_count. With such mutex hash-table with lock per node can be
> implemented very effectively. And this still with no membars on reader
> side.
>
> But for now this is just thoughts...

Keep up the good work!

Chris Thomasson

unread,
Jun 25, 2007, 7:36:14 AM6/25/07
to
[...]

>> And one more thought.
>> If we bring out reader_count variable from arw_mutex to separate
>> entity, maybe we can create two-level mutex, that can be locked for
>> individual object (low level) or can be locked for "all" objects (high
>> level).
[...]

Sure. That will work fine. You just have to define usage patterns wrt the
reader count along with any restricting and/or caveats that come along with
it.

Chris Thomasson

unread,
Jun 25, 2007, 7:41:13 AM6/25/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1182767737.0...@e9g2000prf.googlegroups.com...

> On Jun 25, 1:52 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> Partial copy-on-write means that your not copying a substantial potion of
>> the collection you whish to modify. This is applicable under lock-free
>> means
>> or lock-based means. PDR cover's ALL OF ITS BASES!.
>
> But COW also means that you *copy* some part of data structure. With
> mutex this is false.

COW implies that you copy-entire data-structure.


PCOW implies that you copy-partial struct. For instance, you can create a
new node and copy the ptr value to the next node into it. This could impl a
LIFO list and the PCOW operation itself only copied sizeof(void*) bytes of
info. COW and PCOW are nothing new under "our" sun. You have to concert
yourself with how you going to allow the partially copied entity to free
itself without pulling he rug out from under any potential accessor...

Chris Thomasson

unread,
Jun 25, 2007, 7:42:24 AM6/25/07
to
[...]

> That was the point: To come with a broad enough term to cover
> ref-counting, proxy gc, mutexs, ect...
[...

That was the point: To come __UP__ with a broad enough term to cover

Chris Thomasson

unread,
Jun 25, 2007, 7:54:25 AM6/25/07
to
[...]

> IMHO, I think that virtually any sort of mutual-exclusion method can be
> "thought of" as just another one of the basic mechanisms covered by 'PDR'
> as a whole.
[...]

This could be useful wrt creating a sort-of similarity between lock and
lock-free based algorithms. A marriage between the two is good and I am glad
that you took the time to create awr_mutex, simply because it __does__ fit
the bill.

I am not trying to slam your work. I just think that it's important to point
out of the caveats, which should end up making some potential users feel
"more" at ease.

Chris Thomasson

unread,
Jun 25, 2007, 8:07:40 AM6/25/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1182432160.6...@z28g2000prd.googlegroups.com...
> On Jun 21, 5:15 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>> "Chris Thomasson" <cris...@comcast.net> wrote in message
>>
>> Given than, I think it should
>> outperform most conventional rw-locks...
>>
>> Mabey all "conventional" rw-locks...
>
> It should kill all other rw-locks! :)

Yes. I agree.

Chris Thomasson

unread,
Jun 25, 2007, 8:08:04 AM6/25/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1182421467.8...@z28g2000prd.googlegroups.com...

> Аsymmetric rw_mutex with no atomic_rmw/membars on reader side! No
> joke!
> Here is the sketch:

[...]

Neat.

Chris Thomasson

unread,
Jun 25, 2007, 8:23:42 AM6/25/07
to
[...]

> There is nothing new under the sun.

[...]


Nothing new under the sun indeed!

Shi%t

Well, there is a fuc#ked up, strong _NASTY_ fire burning in South-West Lake
Tahoe that is getting OH SO DAMN CLOSE to a Cabin of mine, and one of my
Cousins residences. If the meadow behind their house goes up, well, it
should resemble a shi^ load of roman candles exploding all over the god
dammed place! If I loose my South Tahoe Cabin I am going to freak
out!!!!!!!!

Unfortunately, there a hundreds of homes that are just ruined!

FUC%%K!! DAMN SH"I%TTT FIRE SUCKS!

:^(...

Dmitriy Vyukov

unread,
Jun 25, 2007, 9:49:29 AM6/25/07
to
On Jun 25, 4:07 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
> >> Given than, I think it should
> >> outperform most conventional rw-locks...
>
> >> Mabey all "conventional" rw-locks...
>
> > It should kill all other rw-locks! :)
>
> Yes. I agree.

And then it will deadlock
:)

Chris Thomasson

unread,
Jun 25, 2007, 2:43:58 PM6/25/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1182779369.5...@i38g2000prf.googlegroups.com...

Did you find a potential problem?

Dmitriy Vyukov

unread,
Jun 26, 2007, 4:31:39 AM6/26/07
to
On Jun 25, 10:43 pm, "Chris Thomasson" <cris...@comcast.net> wrote:

> > And then it will deadlock
> > :)
>
> Did you find a potential problem?

The problem is not in the mutex itself. I describe it here:
http://groups.google.com/group/comp.programming.threads/tree/browse_frm/thread/b7d3b8c08f9ca3c6/d13a791af4427673?rnum=51&hl=en&_done=%2Fgroup%2Fcomp.programming.threads%2Fbrowse_frm%2Fthread%2Fb7d3b8c08f9ca3c6%2F61e39c3e1a85c540%3Fhl%3Den%26#doc_d13a791af4427673


Dmitriy V'jukov

Chris Thomasson

unread,
Jun 26, 2007, 10:39:03 PM6/26/07
to
"Chris Thomasson" <cri...@comcast.net> wrote in message
news:LqudnUq4DdFaL-Lb...@comcast.com...

> [...]
>
>> There is nothing new under the sun.
>
> [...]
>
>
> Nothing new under the sun indeed!
>
> Shi%t
>
> Well, there is a fuc#ked up, strong _NASTY_ fire burning in South-West
> Lake Tahoe that is getting OH SO DAMN CLOSE to a Cabin of mine, and one of
> my Cousins residences.

[...]

Ahhh crap...

The fire is getting worse, and there expecting 35-40+ mph winds tomorrow. If
that happens, it's going to crown the fire __yet again__, and destroy 1000's
of homes!

Please say a prayer for the community of South Lake Tahoe!

:^0

Dmitriy Vyukov

unread,
Jun 27, 2007, 4:29:47 AM6/27/07
to
On 25 , 15:36, "Chris Thomasson" <cris...@comcast.net> wrote:

> Sure. That will work fine. You just have to define usage patterns wrt the
> reader count along with any restricting and/or caveats that come along with
> it.

Ok. I will do this.
But it seems that there is no interest to such things at all in the
world... I post this to several forums, and only 3 (three) people out
there answer something, and you are the only who answer not senseless
things... Or they are waiting when I write lengthy white paper and
make out-of-the-box library... Hmm... It's the option. If they don't
want to think and want library, I can make library for them and then
collect comments and remarks in the form of bug reports about bugs and
deadlocks in their production code :)))

Dmitriy V'jukov

Dmitriy Vyukov

unread,
Jun 28, 2007, 11:04:13 AM6/28/07
to
On Jun 25, 3:31 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
> > Or maybe we can steal some techniques from RCU (while arw_mutex is
> > similar to RCU :) ). Maybe we can eliminate reader_count at all and
> > instead create some quiescent states for readers. And after quiescent
> > period writer can modify object safely...
>
> That's the idea. RCU and reader count are non-related in a sense. RCU
> decouple writers from readers in a way that allows them to both operate
> concurrently.

Now I am thinking of the next thing.
Assume hashed mutex table:

rw_mutex_t mutexes[100];

And reader-writer pattern like this:

void reader(some_t* obj)
{
mutexes[hash(obj)].reader_lock();
// ...
mutexes[hash(obj)].reader_unlock();
}

void writer(some_t* obj)
{
mutexes[hash(obj)].writer_lock();
// ...
mutexes[hash(obj)].writer_unlock();
}

Can I modify my arw_mutex to use in such scheme?
I am thinking of something like this:

arw_mutex_t mutexes[100];

void arw_mutex_t::unreader_lock()
{
if (writer_pending_on_some_of_the_mutexes_from_hashed_mutex_table())
{
notify_that_writer_that_i_am_not_working_with_shared_data();
}
}

void arw_mutex_t::reader_lock()
{
if (writer_pending_or_working_on_this_mutex())
{
wait_for_that_writer();
}
}

In this scheme readers not execute membars most of the time. And
readers don't have to necessarily block when there is writer pending.
In original scheme every reader have to necessarily block when there
is writer pending, and here I try to "unbind" readers and writers, so
readers would block only sometimes.

Dmitriy V'jukov

Dmitriy Vyukov

unread,
Jun 28, 2007, 11:04:40 AM6/28/07
to
On Jun 25, 3:31 pm, "Chris Thomasson" <cris...@comcast.net> wrote:

> That's the idea. RCU and reader count are non-related in a sense. RCU
> decouple writers from readers in a way that allows them to both operate
> concurrently. The user-state that can govern quiescent-states can exist in
> any mutex, reference-counting or lock-free algorithm for that matter. Indeed
> PDR is broad enough to keep itself relevant to state-of-the-art like your
> algorithms posted here, or even down to the traditional level such as
> mutex/rw-mutex.
>
> Agreed?

I am not sure. I become tangled with tern 'PDR'...

Dmitriy V'jukov

Dmitriy Vyukov

unread,
Jun 28, 2007, 11:35:25 AM6/28/07
to
On Jun 28, 7:04 pm, Dmitriy Vyukov <dvyu...@gmail.com> wrote:

> Now I am thinking of the next thing.

Here is the sketch of such mutex:

class arw_mutex_t;
struct arw_reader_t;

struct arw_core_t
{
// counter of readers
// every reader get unique index
int counter_of_readers;

// counter of write operations
// this counter is incremented with every write operation
int counter_of_writes;

static const int max_reader_count = 10;

// in this array every reader copy value of
// counter_of_writes that he observe last
// or -1 if reader is going to sleep
int reader_status[max_reader_count];

arw_core_t()
: counter_of_readers()
, counter_of_writes()
{
memset(reader_status, 0, sizeof(reader_status));
}
};

// global object for simplicity
arw_core_t core;

struct arw_reader_t
{
// unique index of reader
// used as index in core.reader_status[]
int index;

// value of core.counter_of_writes
// that this reader observe last
int counter;

arw_reader_t()
: index(atomic_inc(core.counter_of_readers))
, counter()
{
}
};

class arw_mutex_t
{
private:
mutex_t guard;
bool volatile writer_pending;

public:
arw_mutex_t()
: writer_pending()
{}

void reader_lock(arw_reader_t& reader)
{
if (writer_pending)
{
// inform that reader is going to sleep
core.reader_status[reader.index] = -1;
do
{
thread_yield();
}
while (writer_pending);
// lfence
}
}

void reader_unlock(arw_reader_t& reader)
{
int local = core.counter_of_writes;
if (local != core.reader_status[reader.index])
{
core.reader_status[reader.index] = local;
//lfence to necessarily observe writer_pending flag
}
}

void writer_lock()
{
guard.lock();

// inform readers of this mutex that writer is pending
writer_pending = true;

// increment global counter
int counter = atomic_inc(core.counter_of_writes);

while (true)
{
thread_yield();

// check whether all readers
// (1) observe new value of
// global counter core.counter_of_writes
// or (2) is blocked in reader_lock() of this or
// some other mutex
// this will guarantee that they necessarily will see
// writer_pending flag too, if they execute
// reader_lock() of this mutex
bool all_readers_ready = true;
for (int i = 0; i != core.counter_of_readers; ++i)
{
if (core.reader_status[i] < counter && -1 !=
core.reader_status[i])
{
all_readers_ready = false;
break;
}
}
if (all_readers_ready)
break;
}
}

void writer_unlock()
{
writer_pending = false;

guard.unlock();
}
};

---------------------------------------------

And here is usage example:

arw_mutex_t guards[100];

bool stop = false;

void reader_thread()
{
arw_reader_t reader;
while (!stop)
{
int object = rand() % 100;
guards[object].reader_lock(reader);
//read_some();
guards[object].reader_unlock(reader);
}
}

void writer_thread()
{
while (!stop)
{
int object = rand() % 100;
guards[object].writer_lock();
//write_some();
guards[object].writer_unlock();
//sleep_some();
}
}

Any thoughts? :)

Dmitriy V'jukov

Dmitriy Vyukov

unread,
Jun 28, 2007, 11:46:01 AM6/28/07
to
On Jun 28, 7:35 pm, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
> On Jun 28, 7:04 pm, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
>
> > Now I am thinking of the next thing.
>
> Here is the sketch of such mutex:

I see here only one problem (for now :) ).

If writer has time to release the mutex (i.e. set writer_pending =
false) before reader try to lock this mutex, then reader would not
block. This is good on the one hand. But reader have to execute lfence
in this case in arw_mutex::reader_lock(), to see changes that was made
by writer.
I don't think out how this can be made yet.

And here is the good news.
I think that this lfence is not needed on x86. Because if reader
observe that writer_pending==false, than he must observe and all
previous stores made by writer too.

Dmitriy V'jukov

Dmitriy Vyukov

unread,
Jun 28, 2007, 11:51:13 AM6/28/07
to
On Jun 28, 7:46 pm, Dmitriy Vyukov <dvyu...@gmail.com> wrote:

> And here is the good news.
> I think that this lfence is not needed on x86. Because if reader
> observe that writer_pending==false, than he must observe and all
> previous stores made by writer too.

So I think that very-very fast hash table can be build on top of this
scheme (on x86 for now, and with not so often writes).

Dmitriy V'jukov

Chris Thomasson

unread,
Jun 28, 2007, 12:00:53 PM6/28/07
to
"Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
news:1183043053....@i38g2000prf.googlegroups.com...

> On Jun 25, 3:31 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>>
>> > Or maybe we can steal some techniques from RCU (while arw_mutex is
>> > similar to RCU :) ). Maybe we can eliminate reader_count at all and
>> > instead create some quiescent states for readers. And after quiescent
>> > period writer can modify object safely...
>>
>> That's the idea. RCU and reader count are non-related in a sense. RCU
>> decouple writers from readers in a way that allows them to both operate
>> concurrently.
>
> Now I am thinking of the next thing.
> Assume hashed mutex table:
[...]

> Can I modify my arw_mutex to use in such scheme?
> I am thinking of something like this:

[...]

I think so. However, it may complicate things a bit wrt organize
everything... Need to think some more on this.

Chris Thomasson

unread,
Jun 28, 2007, 12:05:29 PM6/28/07