rw_mutex with costless read_lock/unlock
Dmitriy Vyukov
memory barriers.
Bad news: works only on Windows Vista/Longhorn :( Because of
FlushProcessWriteBuffers() function. If this function will be ported
to linux than solution will work on linux too. Really bad news: this
function requires kernel-space...
Anyway.
int const max_reader_count = 1024;
// unique thread index (0 .. (max_reader_count - 1))
__declspec(thread) int current_thread_index;
class rw_mutex_t
{
private:
CRITICAL_SECTION cs;
// private flag for every reader
bool volatile reader_inside [max_reader_count];
bool volatile writer_pending;
public:
rw_mutex_t()
{
InitializeCriticalSection(&cs);
writer_pending = false;
for (int i = 0; i != max_reader_count; ++i)
reader_inside[i] = false;
}
void reader_lock()
{
reader_inside[current_thread_index] = true;
// no explicit #StoreLoad
// but it will be implicitly executed
// by FlushProcessWriteBuffers()
// in writer_lock()
if (writer_pending)
{
// if writer is pending
// than signal that we see it
// and wait for writer to complete
reader_inside[current_thread_index] = false;
EnterCriticalSection(&cs);
reader_inside[current_thread_index] = true;
LeaveCriticalSection(&cs);
}
}
void reader_unlock()
{
reader_inside[current_thread_index] = false;
}
void writer_lock()
{
EnterCriticalSection(&cs);
// set that we are waiting
writer_pending = true;
store_load_membar();
// all magic is here:
// implicitly execute full memory barrier
// on all other processors (with help from IPI)
FlushProcessWriteBuffers();
// here we are sure that:
// (1) writer will see (reader_inside[i] == true)
// or (2) reader will see (writer_pending == true)
// so no race conditions
for (int i = 0; i != max_reader_count; ++i)
{
// wait for all readers to complete
while (reader_inside[i])
SwitchToThread();
}
}
void writer_unlock()
{
LeaveCriticalSection(&cs);
}
};
The algorithm is very similar to asymmetric rw_mutex:
http://groups.google.com/group/comp.programming.threads/tree/browse_frm/thread/b7d3b8c08f9ca3c6
But this algorithm eliminates false dependencies between threads which
can lead to deadlocks.
And writer_lock() here must be significantly faster because of IPI
magic.
FlushProcessWriteBuffers() also can be used to implement very fast
user-space friendly RCU like PDR. No need to poll other processors. No
need to wait for blocked threads. No need to auto-detect quiescent
periods with undocumented hacks. Every processor just execute
FlushProcessWriteBuffers() and can be sure that all other processors
execute memory barrier.
Dmitriy V'jukov
Chris Thomasson
news:467074c5-760e-4afa...@s8g2000prg.googlegroups.com...
> read_lock()/read_unlock() issue no atomic rmw instructions or heavy
> memory barriers.
> Bad news: works only on Windows Vista/Longhorn :( Because of
> FlushProcessWriteBuffers() function. If this function will be ported
> to linux than solution will work on linux too. Really bad news: this
> function requires kernel-space...
> Anyway.
Why can't you use rcu_synchronize() on Linux? BTW, do you know for sure that
FlushProcessWriteBuffers works the same way? I noticed the following
conversation:
http://forums.microsoft.com/MSDN/ShowPost.aspx?PostID=2514078&SiteID=1
Have you got any confirmation? AFAICT, it should be analog of
rcu_synchronize()...
Chris Thomasson
news:467074c5-760e-4afa...@s8g2000prg.googlegroups.com...
> FlushProcessWriteBuffers() also can be used to implement very fast
> user-space friendly RCU like PDR. No need to poll other processors. No
> need to wait for blocked threads. No need to auto-detect quiescent
> periods with undocumented hacks. Every processor just execute
> FlushProcessWriteBuffers() and can be sure that all other processors
> execute memory barrier.
Well, the thing with FlushProcessWriteBuffers() is that it will generate a
lot of traffic in the sense of sending the interrupts to all the CPUS in the
processes affinity mask. This is an "active" form of quiescent state
auto-detection. As of now, vZOOM uses "passive" detection technique on
Windows; It does not need to interrupt CPU activity.
AFAICT, that is the only advantage I can see to passive epoch detection,
rather than active. Also, for PDR, the epochs should be detected on a
frequent enough basis to keep the deferred object lists from backing up too
much. The frequency of epochs in an active system will be creating a lot of
IPI traffic, while the passive system will be creating none.
Humm.
Chris Thomasson
news:467074c5-760e-4afa...@s8g2000prg.googlegroups.com...
> memory barriers.
> Bad news: works only on Windows Vista/Longhorn :( Because of
> FlushProcessWriteBuffers() function. If this function will be ported
I could easily do this with signals on Unix.
Dmitriy Vyukov
> "Dmitriy Vyukov" <dvyu...@gmail.com> wrote in message
>
> news:467074c5-760e-4afa...@s8g2000prg.googlegroups.com...> read_lock()/read_unlock() issue no atomic rmw instructions or heavy
> > memory barriers.
> > Bad news: works only on Windows Vista/Longhorn :( Because of
> > FlushProcessWriteBuffers() function. If this function will be ported
> > to linux than solution will work on linux too. Really bad news: this
> > function requires kernel-space...
> > Anyway.
>
> [...]
>
> Why can't you use rcu_synchronize() on Linux?
Yes. rcu_synchronize() can be used here in principle.
Minor problem: it is slower... afaik... rcu_synchronize() waits for 2
quiescent points on all processors... FlushProcessWriteBuffers() uses
IPI to "synchronously" signal all processors.
Major problem: afaik rcu_synchronize() is kernel space function.
right?
> BTW, do you know for sure that
> FlushProcessWriteBuffers works the same way? I noticed the following
> conversation:
>
> http://forums.microsoft.com/MSDN/ShowPost.aspx?PostID=2514078&SiteID=1
>
> Have you got any confirmation? AFAICT, it should be analog of
> rcu_synchronize()...
No. Also see this conversation:
http://forums.microsoft.com/MSDN/ShowPost.aspx?PostID=2586815&SiteID=1
:)
To help me to force M$ guys to reveal some more information you can
create some hype there :)
I'm thinking - that this function can do other than rcu_synchronize()
do? And I don't see any useful alternatives...
Also I'm thinking - why M$ include this function into WinAPI?
Definitely not for public use. I think they include this function
because they need it somewhere else... for example in .NET... Maybe
for GC or something...
Dmitriy V'jukov
Dmitriy Vyukov
> "Dmitriy Vyukov" <dvyu...@gmail.com> wrote in message
Definitely this question needs more investigation.
We must consider "total net cost" of detection of 1 quiescent point.
Including all polling, reading of foreign memory and so on. Not only
IPI traffic.
Dmitriy V'jukov
Dmitriy Vyukov
> "Dmitriy Vyukov" <dvyu...@gmail.com> wrote in message
Hmmm...
Will it work with arbitrary thread? For example, with threads from
thread pool of some db library...
And can you be sure that when raise()/kill() returns target thread is
already executing signal handler? Or at least that target thread will
not execute any "user" code before signal handler. Otherwise it will
not work...
Dmitriy V'jukov
Chris Thomasson
> On Dec 26, 5:09 am, "Chris Thomasson" <cris...@comcast.net> wrote:
>> "Dmitriy Vyukov" <dvyu...@gmail.com> wrote in message
>>
>> news:467074c5-760e-4afa...@s8g2000prg.googlegroups.com...
>>
>> > read_lock()/read_unlock() issue no atomic rmw instructions or heavy
>> > memory barriers.
>> > Bad news: works only on Windows Vista/Longhorn :( Because of
>> > FlushProcessWriteBuffers() function. If this function will be ported
>> > to linux than solution will work on linux too. [...]
>>
>> I could easily do this with signals on Unix.
>
>
> Hmmm...
> Will it work with arbitrary thread?
I could do an analog of the FlushProcessWriteBuffers in Unix by using
something like the following:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/01b5800851223134
BTW, you are talking about code getting a callback from an arbitrary thread,
and using the rwmutex API within its context right?
Dmitriy Vyukov
> "Dmitriy Vyukov" <dvyu...@gmail.com> wrote in message
>
> news:bc3f3709-47d5-45f3...@e23g2000prf.googlegroups.com...
>
> > On Dec 26, 5:09 am, "Chris Thomasson" <cris...@comcast.net> wrote:
> >> "Dmitriy Vyukov" <dvyu...@gmail.com> wrote in message
>
> >>news:467074c5-760e-4afa...@s8g2000prg.googlegroups.com...
>
> >> > read_lock()/read_unlock() issue no atomic rmw instructions or heavy
> >> > memory barriers.
> >> > Bad news: works only on Windows Vista/Longhorn :( Because of
> >> > FlushProcessWriteBuffers() function. If this function will be ported
> >> > to linux than solution will work on linux too. [...]
>
> >> I could easily do this with signals on Unix.
>
> > Hmmm...
> > Will it work with arbitrary thread?
>
> [...]
>
> I could do an analog of the FlushProcessWriteBuffers in Unix by using
> something like the following:
>
Interesting.
But I still see some problems:
1. Signal is delivered on per thread basis, and IPI is delivered on
per processor basis. So there can be significantly more signals than
IPI. Not really serious problem.
2. As Joe Seigh pointed here:
http://groups.google.com/group/comp.programming.threads/tree/browse_frm/thread/9545d3e17806ccfe/ca24918934aa601d?rnum=1&_done=%2Fgroup%2Fcomp.programming.threads%2Fbrowse_frm%2Fthread%2F9545d3e17806ccfe%3F#doc_0c892c8aac6a13e4
thread can dispatch signal after arbitrary amount of time. Serious
problem.
3. Really serious problem. As thread dispatches signals only in some
special points - time slice end, syscalls etc. This can lead to
deadlocks as in my asymmetric_rw_mutex:
http://groups.google.com/group/comp.programming.threads/tree/browse_frm/thread/b7d3b8c08f9ca3c6
Example. Thread 1 tries lo lock rw_mutex_1 in write mode.
Simultaneously thread 2 tries lo lock rw_mutex_2 in write mode. Thread
1 sends signal to thread 2 and waits for response. Thread 2 sends
signal to thread 1 and waits for response. Assume threads do active
spin wait so they can't dispatch signals. Gameover. Deadlock.
This works in your vzoom polling logic because you have *dedicated*
thread. And nobody waits for it.
> BTW, you are talking about code getting a callback from an arbitrary thread,
> and using the rwmutex API within its context right?
Yes.
Dmitriy V'jukov
Chris Thomasson
> On 27 дек, 06:42, "Chris Thomasson" <cris...@comcast.net> wrote:
> > "Dmitriy Vyukov" <dvyu...@gmail.com> wrote in message
> >
> > news:bc3f3709-47d5-45f3...@e23g2000prf.googlegroups.com...
> >
> > > On Dec 26, 5:09 am, "Chris Thomasson" <cris...@comcast.net> wrote:
> > >> "Dmitriy Vyukov" <dvyu...@gmail.com> wrote in message
> >
> > >>news:467074c5-760e-4afa...@s8g2000prg.googlegroups.com...
> >
> > >> > read_lock()/read_unlock() issue no atomic rmw instructions or heavy
> > >> > memory barriers.
> > >> > Bad news: works only on Windows Vista/Longhorn :( Because of
> > >> > FlushProcessWriteBuffers() function. If this function will be
> > >> > ported
> > >> > to linux than solution will work on linux too. [...]
> >
> > >> I could easily do this with signals on Unix.
> >
> > > Hmmm...
> > > Will it work with arbitrary thread?
> >
> > [...]
> >
> > I could do an analog of the FlushProcessWriteBuffers in Unix by using
> > something like the following:
> Interesting.
> But I still see some problems:
> 1. Signal is delivered on per thread basis, and IPI is delivered on
> per processor basis. So there can be significantly more signals than
> IPI. Not really serious problem.
True, however, you don't nesseally need to send a signal to every thread in
the process. You need to send the signal to each registered thread in a
polling epoch-list. You can application with 10 threads, but only 3 of them
need to be registered because of the nature of the applications
architecture.
> 2. As Joe Seigh pointed here:
> thread can dispatch signal after arbitrary amount of time. Serious
> problem.
It can be. This would not be that much of a problem for applications that
use a lot of I/O, such as servers. Generally, the signals will be deliverd
on system-calls, and I/O systems eventually must make systems-calls on a
fairly regular basis. PDR works well with servers, because they tend to need
to execute some sort of searching algorihtm. And PDR works well with
searching.
> 3. Really serious problem. As thread dispatches signals only in some
> special points - time slice end, syscalls etc. This can lead to
> deadlocks as in my asymmetric_rw_mutex:
> http://groups.google.com/group/comp.programming.threads/tree/browse_frm/thread/b7d3b8c08f9ca3c6
Assume that the mutex implmentation uses POSIX semaphores...
> Example. Thread 1 tries lo lock rw_mutex_1 in write mode.
> Simultaneously thread 2 tries lo lock rw_mutex_2 in write mode.
Now, which one wins? Lets assume that Thread 1 fails to grab the lock and
ends up waiting...
[...]
> Thread 2 sends
> signal to thread 1 and waits for response.
Thread 1 executes signal-handler and the semaphore wait gets interrupted by
the signal.
> Assume threads do active
> spin wait so they can't dispatch signals. Gameover. Deadlock.
I think I could re-work your algorihtm to work within this context for sure.
Humm...
> This works in your vzoom polling logic because you have *dedicated*
> thread. And nobody waits for it.
Right. It makes things eaiser, IMHO that is... ;^)
> > BTW, you are talking about code getting a callback from an arbitrary
> > thread,
> > and using the rwmutex API within its context right?
> Yes.
Well, this can be a nasty problem indeed! There would need to be explicit
documentation that mentions that signals are going to be used by the PDR.
Chris Thomasson
> On Dec 26, 12:52 am, "Chris Thomasson" <cris...@comcast.net> wrote:
>> "Dmitriy Vyukov" <dvyu...@gmail.com> wrote in message
>>
>> news:467074c5-760e-4afa...@s8g2000prg.googlegroups.com...>
>> read_lock()/read_unlock() issue no atomic rmw instructions or heavy
>> > memory barriers.
>> > Bad news: works only on Windows Vista/Longhorn :( Because of
>> > FlushProcessWriteBuffers() function. If this function will be ported
>> > to linux than solution will work on linux too. Really bad news: this
>> > function requires kernel-space...
>> > Anyway.
>>
>> [...]
>>
>> Why can't you use rcu_synchronize() on Linux?
>
>
> Yes. rcu_synchronize() can be used here in principle.
> Minor problem: it is slower... afaik... rcu_synchronize() waits for 2
> quiescent points on all processors... FlushProcessWriteBuffers() uses
> IPI to "synchronously" signal all processors.
> Major problem: afaik rcu_synchronize() is kernel space function.
> right?
Yeah. I guess you could do a kernel hack or something...
>> BTW, do you know for sure that
>> FlushProcessWriteBuffers works the same way? I noticed the following
>> conversation:
>>
>> http://forums.microsoft.com/MSDN/ShowPost.aspx?PostID=2514078&SiteID=1
>>
>> Have you got any confirmation? AFAICT, it should be analog of
>> rcu_synchronize()...
>
>
> No. Also see this conversation:
> http://forums.microsoft.com/MSDN/ShowPost.aspx?PostID=2586815&SiteID=1
> :)
> To help me to force M$ guys to reveal some more information you can
> create some hype there :)
Humm, yeah. I think I will probablly do that. I hope that we can get better
responses than the Intel Threading Forum generates!
:^0
> I'm thinking - that this function can do other than rcu_synchronize()
> do? And I don't see any useful alternatives...
> Also I'm thinking - why M$ include this function into WinAPI?
> Definitely not for public use. I think they include this function
> because they need it somewhere else... for example in .NET... Maybe
> for GC or something...
I wonder if Microsoft is using something like RCU in Vista!?
http://groups.google.com/group/comp.lang.c++/msg/b3207a94970e5df9
Oh shit!
Dmitriy Vyukov
> > 3. Really serious problem. As thread dispatches signals only in some
> > special points - time slice end, syscalls etc. This can lead to
> > deadlocks as in my asymmetric_rw_mutex:
> >http://groups.google.com/group/comp.programming.threads/tree/browse_f...
>
> Assume that the mutex implmentation uses POSIX semaphores...
>
> > Example. Thread 1 tries lo lock rw_mutex_1 in write mode.
> > Simultaneously thread 2 tries lo lock rw_mutex_2 in write mode.
>
> Now, which one wins? Lets assume that Thread 1 fails to grab the lock and
> ends up waiting...
No. No. Different locks. Thread 1 and thread 2 are in process of
grabbing *different* locks.
Dmitriy V'jukov
Chris Thomasson
Why would a semaphore which gets interrupted by signal not work here?
Chris Thomasson
"Chris Thomasson" <cri...@comcast.net> wrote in message
news:9cedncIRnPj--OXa...@comcast.com...
Signal issue/response logic could be integrated into spinlock backoff logic,
for sure... Spinlock is analogous to a basic trylock and "do something else
on failure" scheme.
Dmitriy Vyukov
> "Dmitriy Vyukov" <dvyu...@gmail.com> wrote in message
>
> news:1077e91c-a652-4bd2...@s8g2000prg.googlegroups.com...
> On 31 ÄÅË, 03:47, "Chris Thomasson" <cris...@comcast.net> wrote:
>
> > > 3. Really serious problem. As thread dispatches signals only in some
> > > special points - time slice end, syscalls etc. This can lead to
> > > deadlocks as in my asymmetric_rw_mutex:
> > >http://groups.google.com/group/comp.programming.threads/tree/browse_f...
>
> > Assume that the mutex implmentation uses POSIX semaphores...
>
> > > Example. Thread 1 tries lo lock rw_mutex_1 in write mode.
> > > Simultaneously thread 2 tries lo lock rw_mutex_2 in write mode.
>
> > Now, which one wins? Lets assume that Thread 1 fails to grab the lock and
> > ends up waiting...
> > No. No. Different locks. Thread 1 and thread 2 are in process of
> > grabbing *different* locks.
>
> Why would a semaphore which gets interrupted by signal not work here?
Semaphore will work here.
Ok. Another example:
rw_mutex m;
void thread1()
{
while (true)
{
MSG m;
GetMessage(&m);
DispatchMessage(&m);
m.write_lock();
m.write_unlock();
}
}
void thread2()
{
while (true)
{
SendMessageToThread1AndWaitAnswer();
m.read_lock();
m.read_unlock();
}
}
So you must ensure that basically every possible mechanizm on which
one thread can wait for other thread *will* process signals. Otherwise
addition of such mutex can lead to deadlock.
Dmitriy V'jukov
Chris Thomasson
> On 31 дек, 06:51, "Chris Thomasson" <cris...@comcast.net> wrote:
> > "Dmitriy Vyukov" <dvyu...@gmail.com> wrote in message
> >
> > news:1077e91c-a652-4bd2...@s8g2000prg.googlegroups.com...
> > On 31 ÄÅË, 03:47, "Chris Thomasson" <cris...@comcast.net> wrote:
> >
> > > > 3. Really serious problem. As thread dispatches signals only in some
> > > > special points - time slice end, syscalls etc. This can lead to
> > > > deadlocks as in my asymmetric_rw_mutex:
> > > >http://groups.google.com/group/comp.programming.threads/tree/browse_f...
> >
> > > Assume that the mutex implmentation uses POSIX semaphores...
> >
> > > > Example. Thread 1 tries lo lock rw_mutex_1 in write mode.
> > > > Simultaneously thread 2 tries lo lock rw_mutex_2 in write mode.
> >
> > > Now, which one wins? Lets assume that Thread 1 fails to grab the lock
> > > and
> > > ends up waiting...
> > > No. No. Different locks. Thread 1 and thread 2 are in process of
> > > grabbing *different* locks.
> >
> > Why would a semaphore which gets interrupted by signal not work here?
> Semaphore will work here.
Indeed they will.
> Ok. Another example:
> So you must ensure that basically every possible mechanizm on which
> one thread can wait for other thread *will* process signals. Otherwise
> addition of such mutex can lead to deadlock.
Yes. You would need to _clearly_ document that caveat. However, on Unix,
your more than likely to be blocking on a system call that does indeed get
interrupted by signals (e.g., sem_wait, select, aio_suspend, read, write,
accept, ect...)
Dmitriy Vyukov
wrote:
> "Dmitriy Vyukov" <dvyu...@gmail.com> wrote in message
In certain conditions this mutex can work on all versions on Windows.
I think that signals can be emulated with APC. But this is definitely
not general solution, because you must ensure than waits which can
lead to deadlock must be alertable.
Basic outline:
When writer notice that he waits too long (potential deadlock) writer
can issue APC with QueueUserAPC() to reader thread. APC executed on
reader thread will resolve deadlock - for example execute membar and
set some flag.
Dmitriy V'jukov
Dmitriy Vyukov
> read_lock()/read_unlock() issue no atomic rmw instructions or heavy
> memory barriers.
> Bad news: works only on Windows Vista/Longhorn :( Because of
> FlushProcessWriteBuffers() function. If this function will be ported
> to linux than solution will work on linux too. Really bad news: this
> function requires kernel-space...
And what do c.p.t think about:
void writer_lock()
{
EnterCriticalSection(&cs);
writer_pending = true;
*Sleep(1)*;
for (int i = 0; i != max_reader_count; ++i)
{
while (reader_inside[i])
SwitchToThread();
}
}
Writer just need to wait *enough* time to all processors flush their
store buffers. I perfectly understand that this is... hazard approach,
but anyway.
It fully portable in the sense that you can wait on every OS and
architecture.
Dmitriy V'jukov
Chris Thomasson
> On Dec 25 2007, 6:33 pm, Dmitriy Vyukov <dvyu...@gmail.com> wrote:
>> read_lock()/read_unlock() issue no atomic rmw instructions or heavy
>> memory barriers.
>> Bad news: works only on Windows Vista/Longhorn :( Because of
>> FlushProcessWriteBuffers() function. If this function will be ported
>> to linux than solution will work on linux too. Really bad news: this
>> function requires kernel-space...
>
>
> And what do c.p.t think about:
>
> void writer_lock()
> {
> EnterCriticalSection(&cs);
> writer_pending = true;
You still need a store/load right after you store to writer_pending.
[...]
>
>
> Writer just need to wait *enough* time to all processors flush their
> store buffers. I perfectly understand that this is... hazard approach,
> but anyway.
> It fully portable in the sense that you can wait on every OS and
> architecture.
Its like implementing RCU pattern with timers. If the timer goes off, and
another thread is still reading from the data-structure, well, that's a
race-condition waiting to happen...
Dmitriy Vyukov
> > And what do c.p.t think about:
>
> > void writer_lock()
> > {
> > EnterCriticalSection(&cs);
> > writer_pending = true;
>
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>
> You still need a store/load right after you store to writer_pending.
I don't need a store/load right after store to writer_pending. Because
I assume that during "Sleep(1)" *all* processors execute store/load
(more precisely - processors don't have to execute exactly store/load
memory barrier, but any load executed after Sleep(1) must not jump
before any store executed before Sleep(1)). If this assumption is not
correct then the store/load will not help too much.
> > Writer just need to wait *enough* time to all processors flush their
> > store buffers. I perfectly understand that this is... hazard approach,
> > but anyway.
> > It fully portable in the sense that you can wait on every OS and
> > architecture.
>
> Its like implementing RCU pattern with timers.
What is "RCU with timers"? I mean that I can guess what is "RCU with
timers", but can you give any links.
> If the timer goes off, and
> another thread is still reading from the data-structure, well, that's a
> race-condition waiting to happen...
No. I have 'reader_inside' flags. If reader is still inside critical
section then writer will see (reader_inside[x] == true) and will wait.
Sleep(1) is only needed to ensure correct visibility of stores.
Sleep(1) is just 'more portable' replacement for
FlushProcessWriteBuffers().
Dmitriy V'jukov
Chris Thomasson
> On Jan 17, 7:09 pm, "Chris Thomasson" <cris...@comcast.net> wrote:
>
>> > And what do c.p.t think about:
>>
>> > void writer_lock()
>> > {
>> > EnterCriticalSection(&cs);
>> > writer_pending = true;
>>
>> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>>
>> You still need a store/load right after you store to writer_pending.
>
>
> I don't need a store/load right after store to writer_pending. Because
> I assume that during "Sleep(1)" *all* processors execute store/load
> (more precisely - processors don't have to execute exactly store/load
> memory barrier, but any load executed after Sleep(1) must not jump
> before any store executed before Sleep(1)). If this assumption is not
> correct then the store/load will not help too much.
>
>
>> > Writer just need to wait *enough* time to all processors flush their
>> > store buffers. I perfectly understand that this is... hazard approach,
>> > but anyway.
>> > It fully portable in the sense that you can wait on every OS and
>> > architecture.
>>
>> Its like implementing RCU pattern with timers.
>
>
> What is "RCU with timers"? I mean that I can guess what is "RCU with
> timers", but can you give any links.
http://groups.google.com/group/comp.programming.threads/msg/23bdbd6b4bba766c
RCU with convoluted timing "assumptions" to me more precise...
>> If the timer goes off, and
>> another thread is still reading from the data-structure, well, that's a
>> race-condition waiting to happen...
>
>
> No. I have 'reader_inside' flags.
I was referring to RCU with timers being the assumptions made by a given
algorithm. A timer going off is the time-period that represents a certain
"timing assumption":
http://groups.google.com/group/comp.programming.threads/msg/b851b6ffd816cf22
You cannot rely on timers generally, unless your working on an operating
system internals, and know exactly what's going on. However, you can use
timer events as flag(s) to query for quiescent states.
> If reader is still inside critical
> section then writer will see (reader_inside[x] == true) and will wait.
> Sleep(1) is only needed to ensure correct visibility of stores.
> Sleep(1) is just 'more portable' replacement for
> FlushProcessWriteBuffers().
I was referring to RCU with timing assumptions; not your asymmetric
algorithm. However, I think that Sleep(1) cannot be used as a guarantee that
every thread has executed proper memory barriers. Its a timing assumption,
which is subject to false-positives.
Dmitriy Vyukov
> However, I think that Sleep(1) cannot be used as a guarantee that
> every thread has executed proper memory barriers. Its a timing assumption,
> which is subject to false-positives.
Note that I don't need exactly store-load memory barrier. I just need
"the effect of store-load memory barrier". Do you think that it's
possible to load to jump above store which was executed 1ms before? I
don't think it's possible.
Dmitriy V'jukov