Final Considerations
The single-threaded code below shows the value of the list.size() when Producing/ Consuming elements:
LockFreeQueue<int> q; // list.size() == 1
q.Produce(1); // list.size() == 2
int i;
q.Consume(i); // list.size() == still 2!;
// Consume() doesn't modify the list
q.Produce(i); // list.size() == 2 again;
The size of the queue is 1 if Produce() was never called and greater than 1 if any element was produced.
No matter how many times Consume() is called, the list's size will stay constant. It is Produce() that is increasing the size (by 1); and if there were consumed elements, it will also delete them from the queue. In a way, Produce() acts as a simple garbage collector. The whole thread safety comes from the fact that specific data is modified from single threads only. The synchronization between threads is done using iterators (or pointers, whichever has atomic read/write operation on your machine). Also consider this code:
usleep(1000); // sleep 1 microsecond
On the face of it, this line of code makes a thread sleep for 1 microsecond, and then continue. In reality, 1 microsecond is just a lower bound to the duration of the call.
The man page for usleep() says, "The usleep() function suspends execution of the calling process for (at least) usec microseconds. The sleep may be lengthened slightly by any system activity or by the time spent processing the call or by the granularity of system timers," or if you use the nanosleep() function. "Therefore, nanosleep() always pauses for at least the specified time; however, it can take up to 10 ms longer than specified until the process becomes runnable again."
So if the process is not scheduled under a real-time policy, there's no guarantee when your thread will be running again. I've done some tests and (to my surprise) there are situations when code such as:
cond.timed_wait(lock, x); // x = e.g. 1 millisecond
will actually wait for more than 1 second.
Acknowledgments
Many thanks to Andrei Alexandrescu who took the time to review this article. Also, thanks to Radu Duta for making useful corrections.
