Аsymmetric rw_mutex
Dmitriy Vyukov
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
> А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
> А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
> 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
[...]
___
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
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
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
> 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
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
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
> 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
> > 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
> 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
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
> 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
Mabey all "conventional" rw-locks...
;^)
Dmitriy Vyukov
> 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
> 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
> > 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
> "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
> 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
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
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
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
> 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
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
> 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
> 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
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
This can be handled be explicitly unregister reader before call to
suspicious function.
Dmitriy V'jukov
Chris Thomasson
> 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
Yup. That would work for sure.
Chris Thomasson
> 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
> 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
> 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
> > 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
> "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
> 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
> А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
> А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
> А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
> А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
> А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
;^)
Chris Thomasson
Ask this over on comp.arch
Chris Thomasson
[...][...]
>> 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
> 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
> 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
> 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
>> 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
> 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
> 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
> 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
> 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
> Аsymmetric rw_mutex with no atomic_rmw/membars on reader side! No
> joke!
[...]
Neat.
Chris Thomasson
> 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
>
> >> 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
Did you find a potential problem?
Dmitriy Vyukov
> > 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
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
> 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
>
> > 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
> 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
> 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
> 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
> 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
> 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
> 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:
Well, I am wondering about the spin-wait method shown in the sketch.
Chris Thomasson
What type of writer frequency do you have in mind? Something on the order of
writes-per-second or, per-minute? I wonder about
forward-progress/scalability issues wrt the "consensus" that has to occur
whenever a write needs to occur. It's not going to behave like an algorithm
that allows any writer to execute in parallel any reader.
But, well, that's kind of like comparing apples to oranges because your
working on an algorithm that depends on a form of mutual-exclusion, not 100%
lock-free. From my experience, traditional rw-mutexs will start to break
down once you hit them with some load, and I don't think the performance
degradation is due to the membars on the reader-side alone... They are a
major part for sure, however, the blocking has an effect as well.
Scalability and performance should hold through the worst of times and the
best of times, therefore, IMHO, you should test your algorithm against other
rw-mutexs in various worst case scenarios. For instance, see how well it can
handle unexpected periods of sustained writer activity...
Chris Thomasson
> 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.
Your not going to need explicit lfence on x86. Well, at least on the current
models!
;^)
> 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).
[...]
Yeah, I have some ideas, however, I am bogged down trying to meet several
important deadlines so I don't really have any free time! ;^(...
Also, I have to worry about my 50+ year old Cabin burning down. Well, at
least the Firefighters kicked the shi% out of the Angora Fire and got it 55%
contained. It's almost like South Tahoe dodged a damn bullet; what a relief!
:^0
Chris Thomasson
> 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:
Doh! I was thinking about something else.
Chris Thomasson
> 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...
;^)
Chris Thomasson
> "Dmitriy Vyukov" <dvy...@gmail.com> wrote in message
> news:1182932987.8...@g4g2000hsf.googlegroups.com...
>> 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...
For some reason, I don't think there is going to be much interest because it
seems that most programmers simply do not have the necessary skills and/or
patience to use such primitives directly and effectively. The STM-hype is
appealing to them because it sort-of eliminates the need to think hard about
solving various concurrency issues:
http://groups.google.com/group/comp.arch/msg/00232a377a4c87a5
Our algorithms might start to "take off" when the number of cores is up in
the thousands. However, by then they will most-likely have PDR epoch logic
on a chip. I even created a draft for a new chip design on paper in my spare
time, and posted an extremely rough info of my idea here:
http://groups.google.com/group/comp.programming.threads/msg/6236a9029d80527a
I mentioned this to Andy Glew from Intel:
http://groups.google.com/group/comp.arch/msg/2a0f4163f8e13f1e
And have not received any sort of response. DAMN! I think that epoch
detection on the hardware could be extremely promising and would definitely
scale to the mega-core chips of the future. I have yet to see any patents
that deal with sticking PDR on the hardware.
Here is some more info on the idea:
http://groups.google.com/group/comp.arch/msg/1d61f26c4ed4142e
http://groups.google.com/group/comp.arch/msg/6486e768886bc02e
http://groups.google.com/group/comp.arch/msg/ab4d7fe1d3dbe2e1
So far, David Hopwood is the only person to comment on my hardware
technique.
;^(...
>> Or they are waiting when I write lengthy white paper and
>> make out-of-the-box library... Hmm...
[...]
I think everybody looking for an out-of-the-box library that is going to
solve everything without any hard work:
http://groups.google.com/group/comp.programming.threads/msg/fee430a522e1a5f1
:^(...
Chris Thomasson
> Our algorithms might start to "take off" when the number of cores is up in
> the thousands. However, by then they will most-likely have PDR epoch logic
> on a chip. I even created a draft for a new chip design on paper in my
> spare time, and posted an extremely rough info of my idea here:
>
> http://groups.google.com/group/comp.programming.threads/msg/6236a9029d80527a
>
>
> I mentioned this to Andy Glew from Intel:
>
> http://groups.google.com/group/comp.arch/msg/2a0f4163f8e13f1e
>
> And have not received any sort of response. DAMN! I think that epoch
> detection on the hardware could be extremely promising and would
> definitely scale to the mega-core chips of the future. I have yet to see
> any patents that deal with sticking PDR on the hardware.
I think I will post a new message over in comp.arch in a little while to see
if I can get a discussion going. This is probably going to be an exercise in
futility!
Chris Thomasson
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.
[...]
I think a condition variable would be better than a semaphore. I think it
would make it easier to unregister threads...
Joe Seigh
PDR was coined because attempting to use the term GC in a generic sense
was futile. It's sort of tied in with a specific usage pattern which
might have been called RCU (Read, Copy, Update) except McKenney used
it to refer to a specific PDR algorithm which makes it useless to use
as a pattern name. No good name for the pattern yet. PDR includes
RCU, hazard pointers, lock-free reference counting, VZOOM, conventional
GC since they can all be used in that pattern even though some of them,
like GC and refcounting, don't require explicit scheduling of deallocation.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
Dmitriy Vyukov
> I think a condition variable would be better than a semaphore. I think it
> would make it easier to unregister threads...
Yes, maybe. I was thinking in terms in Win32 API, not POSIX :)
And in terms of Win32 API auto reset event would be better, because
only one reader can notify writer. Something like:
void read_lock()
{
if (writer_pending && 0 == atomic_dec(reader_count2))
{
SetEvent(notify_writer);
WaitForSingleObject(notify_readers);
}
}
Dmitriy V'jukov
Dmitriy Vyukov
> PDR was coined because attempting to use the term GC in a generic sense
> was futile. It's sort of tied in with a specific usage pattern which
> might have been called RCU (Read, Copy, Update) except McKenney used
> it to refer to a specific PDR algorithm which makes it useless to use
> as a pattern name. No good name for the pattern yet. PDR includes
> RCU, hazard pointers, lock-free reference counting, VZOOM, conventional
> GC since they can all be used in that pattern even though some of them,
> like GC and refcounting, don't require explicit scheduling of deallocation.
But here I have some kind of 'actual' mutex. I.e. writer can reclaim
memory immediately. And writer can do inplace update of data
structure. Is it still PDR? Chris Thomasson asserts that this is PDR
too...
Dmitriy V'jukov
Dmitriy Vyukov
> > I think a condition variable would be better than a semaphore. I think it
> > would make it easier to unregister threads...
>
> Yes, maybe. I was thinking in terms in Win32 API, not POSIX :)
>
> And in terms of Win32 API auto reset event would be better, because
> only one reader can notify writer. Something like:
I am not sure what is the best replacement for 'auto reset event' in
POSIX...
Dmitriy V'jukov
Dmitriy Vyukov
> And have not received any sort of response. DAMN! I think that epoch
> detection on the hardware could be extremely promising and would definitely
> scale to the mega-core chips of the future. I have yet to see any patents
> that deal with sticking PDR on the hardware.
The same question arise like in David Hopwood answer.
Callback frequency can be too high. So we can limit Callback frequency
to no more than 1 in a second. But then somebody can say 'Callback
frequency is too low, I have too many unreclaimed memory!'... This is
the problem...
The hardware can just put information about quiescent states into same
table...
And the second question. What is core groups?
Are you mean 1 group per process? Or what? Why not just stick to
cores?
Dmitriy V'jukov
Dmitriy Vyukov
> What type of writer frequency do you have in mind? Something on the order of
> writes-per-second or, per-minute? I wonder about
> forward-progress/scalability issues wrt the "consensus" that has to occur
> whenever a write needs to occur. It's not going to behave like an algorithm
> that allows any writer to execute in parallel any reader.
The first scheme (that in first post in this topic) really need low
write frequency, because all reader threads must (1) notify writer and
(2) wait in block for writer. I think of, maybe, one write per per-
minute. But definitely this question need more investigation. I am
even don't execute implementation on single-core machine!
And the second scheme (few posts upper) must allow higher write
frequency, because if writers and readers don't correlate (i.e. work
on different cells of hashed table) then readers don't have to block
and wait for writers. Only readers which going to work on cell that is
currently wrote have to block. Other readers just have to periodically
notify writer that they don't work on cells, on which writer want to
work. This is the main advantage. And this question need even more
investigation.
> But, well, that's kind of like comparing apples to oranges because your
> working on an algorithm that depends on a form of mutual-exclusion, not 100%
> lock-free. From my experience, traditional rw-mutexs will start to break
> down once you hit them with some load, and I don't think the performance
> degradation is due to the membars on the reader-side alone... They are a
> major part for sure, however, the blocking has an effect as well.
> Scalability and performance should hold through the worst of times and the
> best of times, therefore, IMHO, you should test your algorithm against other
> rw-mutexs in various worst case scenarios. For instance, see how well it can
> handle unexpected periods of sustained writer activity...
Here is a little problem.
First of all, I don't have access to any multicore/multiprocessor
machines. So it is a bit difficult to me to test something of this
stuff...
Second, I don't have enough time for this. My current employer
completely not interested in this stuff. So all this is going in my
own time...
Dmitriy V'jukov
Joe Seigh
PDR manages memory for lock-free algorithms that do a space time trade-off
using extra memory (space) to improve performance (time).
Joe Seigh
> Second, I don't have enough time for this. My current employer
> completely not interested in this stuff. So all this is going in my
> own time...
>
No employer is interested in this stuff except in a trivial sense.
They have really low expectations for threading skills so you don't
need to know much in that area. Plus popular programming languages
like Java and C# have GC which covers up a multitude of programming
sins.
Eventually, things will reach a crisis point where threading skills
really do become important. Unfortunately, there will be some
horrific messes to clean up. Not even STM will be able to save them
there.
Dmitriy Vyukov
> PDR manages memory for lock-free algorithms that do a space time trade-off
> using extra memory (space) to improve performance (time).
One more definition. This complicate thing even more :)
So algorithms with immediate memory reclamation is not PDR. And my
arw_mutex is not PDR.
Dmitriy V'jukov
Dmitriy Vyukov
> Аsymmetric rw_mutex with no atomic_rmw/membars on reader side! No
> joke!
I think it is better to rename some functions here:
register_reader -> reader_lock
unregister_reader -> reader_unlock
reader_lock -> reader_try_yield
reader_unlock -> eliminate this function
So reader holds reader lock all the time and only sometimes (in
function reader_try_yield) release reader lock and get writer
possibility to update data structure. I think this change makes things
more clear. And explains better why there are additional possibilities
for deadlocks.
Dmitriy V'jukov
Chris Thomasson
> On Jun 28, 8:52 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> And have not received any sort of response. DAMN! I think that epoch
>> detection on the hardware could be extremely promising and would
>> definitely
>> scale to the mega-core chips of the future. I have yet to see any patents
>> that deal with sticking PDR on the hardware.
>
> The same question arise like in David Hopwood answer.
> Callback frequency can be too high. So we can limit Callback frequency
> to no more than 1 in a second. But then somebody can say 'Callback
> frequency is too low, I have too many unreclaimed memory!'... This is
> the problem...
> The hardware can just put information about quiescent states into same
> table...
Well, this could be tied into the system heartbeat "so-to-speak"...
>
> And the second question. What is core groups?
> Are you mean 1 group per process? Or what? Why not just stick to
> cores?
Think distributed...
A hardware group of cores could be bound to a specific range of memory...
You need to do this if PDR has any chance in hell to scale up to mega-core
processors...
A hardware logic can carve out the groups of cores along with their
respective "semi-shared" private memory spaces... The OS can query the
hardware to gain information and begin to setup the PDR polling daemons
bound to their respective core groups...
Groups amortizes memory access and PDR polling activities across the
board...
Chris Thomasson
> Аsymmetric rw_mutex with no atomic_rmw/membars on reader side! No
> joke!
> Here is the sketch:
> class arw_mutex_t
> {
> public:
[...]
> void writer_unlock()
> {
the following function executes a release barrier before it
notifies any reader correct?
// membar #LoadStore | #StoreStore;
> notify_all_readers();
> guard.unlock();
> }
> };
[...]
Dmitriy Vyukov
> > "Dmitriy Vyukov" <dvyu...@gmail.com> wrote in message
Right. This was only the high-level sketch of algorithm.
I think that notification mechanism will execute all needed barriers.
Otherwise barrier must be executed explicitly.
Dmitriy V'jukov