Sorry, i don't seem to understand this completely.
B) How to implement a lock-free fifo? Or rather: is there some ready to use implementation of it?
i just use RingBuffer<Event*> (assuming you know C++ syntax). pseudo code:
delivery:
Event* event; event = new Event (arg1, arg2, ...); pending_events.write (&event, 1);
receipt:
Event* event;
if (pending_events.read (&event, 1) == 1) { process_event (event); }
What is the underlying data structure (for pending_events)?
How can be guarantied that the write and read operations are atomic?
What is the second argument of write/read ("1")?
"&event" is a pointer to a pointer? Why not store a pointer to an Event object?
Or to put it different: What is happening in the read/write methods?
My adhoc (and maybe naive) approach would look something like this (assuming ++some_ptr is atomic):
Event** read_ptr; Event** write_ptr;
bool read(Event ** e){
(... on "xrun" return false ...) (*)
*e = *read_ptr;
++read_ptr;
(... wrap arround at end of array ...)
return true;
}void write(Event ** e){
(... on "xrun" return false ...) (*)
*write_ptr = *e;
++write_ptr;
(... wrap arround at end of array ...)
}The critical line seems to be the one marked with (*).
How would this be done? Can it be implemented as an "atomic" operation?
To tell the truth, i'm getting pretty much confused when trying to determine what would be an overrrun and would be an underrun in the above implementation. I guess a general xrun occurs if either of the two pointers overtakes the other one. If in the the write method the write_ptr overtakes the read_ptr, that would be an overrun, if in the read method the read_ptr overtakes the write_ptr, this would be an underrun. Is this correct?
And of course this only works with a single reader and a single writer thread. so if communication has to happen between event sources on several different threads and a single "event delegation" thread, then there has to be one fifo for each of the threads that create events. Right?
What happens if this runs on a multi processor system? even if the operations are atomic, they could happen at the same time than, couldn't they?
Propably this are very basic issues, and propably i am not the first one to ask this questions. Please have patience with me :-)
Regards, Lukas
