Practical Multiwriter Lock-Free Queues for "Hard Real-Time" Systems without CAS

Details Practical Multiwriter Lock-Free Queues for "Hard Real-Time" Systems without CAS Practical Multiwriter Lock-Free Queues for "Hard Real-Time" Systems without CAS

2007-09-28

arxiv.org/abs/0709.4558v1

Computer Science

Operating Systems

9 Pages, Preprint

Scientific paper

FIFO queues with a single reader and writer can be insufficient for "hard real-time" systems where interrupt handlers require wait-free guarantees when writing to message queues. We present an algorithm which elegantly and practically solves this problem on small processors that are often found in embedded systems. The algorithm does not require special CPU instructions (such as atomic CAS), and therefore is more robust than many existing methods that suffer the ABA problem associated with swing pointers. The algorithm gives "first-in, almost first-out" guarantees under pathological interrupt conditions, which manifests as arbitrary "shoving" among nearly-simultaneous arrivals at the end of the queue.

Affiliated with

Also associated with

No associations

Rating

Practical Multiwriter Lock-Free Queues for "Hard Real-Time" Systems without CAS does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Practical Multiwriter Lock-Free Queues for "Hard Real-Time" Systems without CAS, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Practical Multiwriter Lock-Free Queues for "Hard Real-Time" Systems without CAS will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-714885