Lecture Notes in Computer Science, 2008, Volume 5401/2008, 560-563, DOI: 10.1007/978-3-540-92221-6_40

Efficient Large Almost Wait-Free Single-Writer Multireader Atomic Registers

Andrew Lutomirski and Victor Luchangco

View Related Documents

Abstract

We present a nonblocking algorithm for implementing single-writer multireader atomic registers of arbitrary size given registers only large enough to hold a single word. The algorithm has several properties that make it practical: It is simple and has low memory overhead, readers do not write, write operations are wait-free, and read operations are almost wait-free. Specifically, to implement a register with w words, the algorithm uses N(w + O(1)) words, where N is a parameter of the algorithm. Write operations take amortized O(w) and worst-case O(Nw) steps, and a read operation completes in O(w(log(k + 2) + Nk·2− N )) steps, where k is the number of write operations it overlaps.

Fulltext Preview

Image of the first page of the fulltext document