Asymmetric Dekker Synchronization
Chris Thomasson
http://blogs.sun.com/dave/resource/Asymmetric-Dekker-Synchronization.txt
http://www.trl.ibm.com/people/kawatiya/Kawachiya05phd.pdf
(chapter 6)
Looks like a tweaked Petersons algorithm.
Chris Thomasson
news:ua-dnQfDe-ngdzDb...@comcast.com...
From just an extremely brief look at some of the documentation it seems like
they are identifying "dominate" threads and give them a privileged access
that requires no interlocked rmw instructions. The define "dominate" thread
as one that frequently takes the lock. Need to read this more carefully...
Humm...
Dmitriy Vyukov
> From just an extremely brief look at some of the documentation it seems like
> they are identifying "dominate" threads and give them a privileged access
> that requires no interlocked rmw instructions. The define "dominate" thread
> as one that frequently takes the lock. Need to read this more carefully...
> Humm...
It seems that idea is very similar to my symmetric rw_mutex:
http://groups.google.com/group/comp.programming.threads/msg/7aac340450bd8c08?hl=en&
They propose more methods for "serizlization" (including kernel mode
variants - I don't want to go to kernel). But they miss reader-writer
possibility :)
And they have the same problems. They bring in additional
possibilities for deadlocks. For example, if Thread 1 waits Thread 2,
and Thread 2 execute SERIALIZE operation waiting for Thread 1 for
serialize - you've got a deadlock...
Dmitriy V'jukov
Dmitriy Vyukov
> It seems that idea is very similar to my symmetric rw_mutex
But direction of thinking is clear - you can split synchronization
algorithm for two versions: first is "fast" and second is "slow"...
First can even don't include membars. And possibly this relate not
only to mutexes algorithms, maybe other synchronization algorithms can
be split this way...
Dmitriy V'jukov
Joe Seigh
The first one is using waiting until other threads execute a membar
at least once to elimnate the need for those threads to execute a
store/load membar in a critical code path. RCU+SMR does something
similar.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
Chris Thomasson
news:1185807687.8...@i13g2000prf.googlegroups.com...
Perhaps. I think I could fairly easily can setup pc_sample in a way that
could give a "dominate" thread some access to a proxy collector without an
xadd for pc_inc or cas for pc_dec...
Not sure how much heavily fast-pathing a single thread is going to buy you
in the context of a mutex. For my memory allocator I do this for a
per-thread heap. A mutex is naturally going to be accessed by more than one
thread. N-1 threads per-mutex will still be contending so your still going
to have spin-lock scaleable problems for all of the foreign threads. I could
see how to extend this, but I would rather use vZOOM or pc_sample or
something...
Chris Thomasson
news:Kgvri.8749$ug4.6607@trndny07...
In some examples a foreign thread has to suspend the owner thread in order
to direct them it to synchronize. I would rather use a lock-free reader
pattern anyway... You can only optimize a mutex so much before it gets
ridiculous.
Chris Thomasson
> "Joe Seigh" <jsei...@xemaps.com> wrote in message
> news:Kgvri.8749$ug4.6607@trndny07...
>> Chris Thomasson wrote:
>>> "Chris Thomasson" <cri...@comcast.net> wrote in message
>>> news:ua-dnQfDe-ngdzDb...@comcast.com...
> In some examples a foreign thread has to suspend the owner thread in order
> to direct them it to synchronize. I would rather use a lock-free reader
> pattern anyway... You can only optimize a mutex so much before it gets
> ridiculous.
I would not mind using these mutexs on the writer-side of a reader
pattern...
Chris Thomasson
> On Jul 30, 5:54 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> From just an extremely brief look at some of the documentation it seems
>> like
>> they are identifying "dominate" threads and give them a privileged access
>> that requires no interlocked rmw instructions. The define "dominate"
>> thread
>> as one that frequently takes the lock. Need to read this more
>> carefully...
>> Humm...
>
> It seems that idea is very similar to my symmetric rw_mutex:
> http://groups.google.com/group/comp.programming.threads/msg/7aac340450bd8c08?hl=en&
>
> They propose more methods for "serizlization" (including kernel mode
> variants - I don't want to go to kernel). But they miss reader-writer
> possibility :)
Yes, they sure did miss your r/w variant; too bad for them!
;^)