Foundations of Shared Memory

At the hardware level, threads communicate by reading and writing shared memory.

How to implement linearizable read and write register for multiple readers and writers?

Can any data structure implemented from the most powerful registers we define also be implemented from the weakest?

The weakest form of persistent synchronization if (arguably) the ability to set a single persistent bit in shared memory, and the weakest form of synchronization is (unarguably) none at all: if the act of setting a bit does not overlap the act of reading that bit, then the value read is the same as the value written Otherwise, a read overlapping a write would return any value.

A single-writer, multi-reader register implementation is safe if –

  • A read() call that does not overlap a write() call returns the value written by the most recent write() call.
  • Otherwise, if a read() call overlaps a write() call, then the read() call may return any value within the register’s allowed range of values (for example, $0$ to $M - 1$ for an $M$-valued register)

The term safe is a historical accident. Because they provide such weak guarantees, “safe” registers are actually quite unsafe.

image-20211121200633192

我至今还是不知道为什么 Boolean 不是 Regular 而只能是 safe。这真的能返回出奇怪的值吗？

我想跳过这个了