Re: single producer, single consumer
On Oct 6, 1:52 pm, Joshua Maurice <joshuamaur...@gmail.com> wrote:
On Oct 6, 7:00 am, goodfella <goodfella...@gmail.com> wrote:> Here is s=
ome code I came up with for a lock free single producer
single consumer algorithm. I have done some tests using GCC with -O3
optimizations and all seems well. I would like some constructive
criticism of the code as I am not yet an expert on concurrency.
I'm assuming that reading and writing the value of a pointer is
atomic. Although, I have read on some architectures that is a bad
assumption, so to insure correctness across all platforms, I may have
to wait for C++ atomic types. Any suggestions and criticisms are
welcomed thanks. The code is below.
[Snip code]
As already mentioned, multi-processor systems will probably not run
your code as you intended because of cache coherency. I'd strongly
suggest looking it up and getting some good references on threading.
The short version is that BOTH the reader and the writer threads must
execute some kind of synchronization primitive to have any guarantee
WHATSOEVER on the order that writes become visible to another thread
(where a synchronization primitive might be a full blown lock, acquire
and release memory barriers, read and write memory barriers, etc.).
Ex:
#include <string>
#include <fstream>
using namespace std;
//insert threading library
template <typename callable_t>
void startThread(callable_t callable);
int x = 0;
int y = 0;
struct foo
{ foo(string const& f) : filename(f) {}
string filename;
void operator() ()
{ ofstream fout(filename.c_str());
fout << x << " " << y << endl;
}
};
int main()
{ startThread(foo("a"));
startThread(foo("b"));
startThread(foo("c"));
startThread(foo("d"));
x = 1;
y = 2;
}
This program, on a \single\ execution, can produce 4 files with the
contents (though highly unlikely for this contrived example):
0 0
0 2
1 0
1 2
This is the cache coherency problem. Let me emphasize again: two
different threads may see the same writes occur in different orders.
On modern machines, there is no single view of main memory. Everyone
has their own local copy because of their own independent caches. One
thread may execute the instructions "load register to x" then "load
register to y", but another thread may see it happen in the opposite
order.
Synchronization instructions make the view consistent when used
properly. Atomic is insufficient. The pointer might have been updated
but what it points to has not been updated. See C++ And The Perils Of
Double Checked Lockinghttp://www.aristeia.com/Papers/DDJ_Jul_Aug_2004_rev=
ised.pdf
for an excellent description of modern threading, and common
pitfalls.
This is of course ignoring the other two big "culprits" of making non-
conformant code do what the user does not expect: compiler
optimizations and single core pipeline reorderings / optimizations.
Also, even on a single core single processor machine, you might still
hit related issues due to compiler optimizations and hardware pipeline
optimizations, especially with signal handlers.
The machine I'm testing this on has a dual core processor, and I have
yet to hit a problem like that. I would expect the process to hang
because the producer would constantly be getting a false value
returned from the push function and the consumer would constantly be
getting a null pointer from the pop function due to the fact that the
pointer value would be stored in their respective cache's and a write
to the pointer in one cache would not propagate to the pointer value
in the other cache. Are there any guarantees in regard to cache
coherency on certain platforms?