We got two posters accepted at PPoPP 2016, yupiii!!!
One was for "Poor Man's URCU" which we talked about on a post long ago.
http://dl.acm.org/citation.cfm?id=3019021
It's a very simple way to implement a Userspace RCU using reader-writer locks, in a lock-free way. Yes, you can use the trylock() API in reader-writer locks to build lock-free constructs, with URCU being an example.
The other one was the Turn Queue, the world's fastest (so far) wait-free linearizable MPMC queue with wait-free memory reclamation, which we talked about on a post a couple months ago.
http://dl.acm.org/citation.cfm?id=3019022
The full paper is called "A Wait-Free Queue with Wait-Free Memory Reclamation" and you can get a draft here if you want to.
Hello. I'm facing a challenge with a queue-like structure you might have tips on for me. The situation is as follows:
ReplyDeleteThread 1 offers items into a bounded "queue". Thread 2 traverses the queue from time to time, occasionally removing items at non-deterministic places (no need for FIFO actually). Thread 3 may come in and remove all items from the queue and signal Thread 1 to stop trying to offer any more items.
The extended problem is when the "queue" is unbounded and may need to grow.
My current solution is in the form of a copy-on-write array with a special terminal indicator array instance. If removals were not part of the requirement, this could be just the ordinary and cheap single-producer single-consumer bounded queue.