Efficient pure-buffer algorithms for real-time systems

We present wait-free algorithms for implementing multi-writer read/write pure-buffers in multiprocessor real-time systems. Such buffers are commonly used when existing data is overwritten as newly-produced data becomes available. Pure-buffer algorithms share several buffers between client processes and use handshaking mechanisms to ensure the safety of concurrent read and write operations. We present algorithms optimized for both quantum- and priority-scheduled systems. When used to implement a B-word buffer shared across a constant number of processors, the time complexity for reading and writing in each of our algorithms is O(B), and the space complexity is Theta (B).