Takashi's Notes

Foundations of shared memory

5 min read

Foundations of shared memory

Prev: Concurrent Objects Next: The relative power of primitive synchronization operations

Exercises

Exercise 4.1. Consider the safe Boolean MRSW construction shown in Fig. 4.6. True or false: if we replace the safe Boolean SRSW register array with an array of safe -valued SRSW registers, then the construction yields a safe -valued MRSW register. Justify your answer.

Exercise 4.2. Consider the safe Boolean MRSW construction shown in Fig. 4.6. True or false: if we replace the safe Boolean SRSW register array with an array of regular Boolean SRSW registers, then the construction yields a regular Boolean MRSW register. Justify your answer.

Exercise 4.3. Consider the safe Boolean MRSW construction shown in Fig. 4.6. True or false: if we replace the safe Boolean SRSW register array with an array of regular -valued SRSW registers, then the construction yields a regular -valued MRSW register. Justify your answer.

Exercise 4.4. Consider the regular Boolean MRSW construction shown in Fig. 4.7. True or false: if we replace the safe Boolean MRSW register with a safe -valued MRSW register, then the construction yields a regular -valued MRSW register. Justify your answer.

Exercise 4.5. Consider the atomic MRSW construction shown in Fig. 4.12. True or false: if we replace the atomic SRSW registers with regular SRSW registers, then the construction still yields an atomic MRSW register. Justify your answer.

Exercise 4.6. Give an example of a quiescently consistent register execution that is not regular.

Exercise 4.7. You are given the following algorithm for constructing an atomic -valued SRSW register using atomic Boolean SRSW registers. Does this proposal work? Either prove the correctness or present a counterexample.

public class AtomicSRSWRegister implements Register<int> {
  private static int RANGE = M;
  boolean[] r_bit = new boolean[RANGE];
 
  public AtomicSRSWRegister(int capacity) {
    for (int i = 1; i <= RANGE; i++)
      r_bit[i] = false;
    r_bit[0] = true;
  }
 
  public void write(int x) {
    r_bit[x] = true;
    for (int i = x - 1; i >= 0; i--)
      r_bit[i] = false;
  }
 
  public int read() {
    for (int i = 0; i <= RANGE; i++)
      if (r_bit[i]) {
        return i;
      }
    return -1;
  }
}

Exercise 4.8. Imagine running a 64-bit system on a 32-bit system, where each 64-bit memory location, or register, is implemented using two atomic 32-bit memory locations. A write operation is implemented by simply writing the first 32 bits in the first register and then the second 32 bits in the second register. A read, similarly, reads the first half from the first register, then reads the second half from the second register, and returns the concatenation. What is the strongest property that this 64-bit register satisfies?

  • safe register,
  • regular register,
  • atomic register,
  • it does not satisfy any of these properties.

Exercise 4.9. Does Peterson’s two-thread mutual exclusion algorithm work if the shared atomic flag registers are replaced by regular registers?

Exercise 4.10. Consider the following implementation of a register in a distributed message-passing system. There are processors arranged in a ring, where can send messages only to . Messages are delivered in FIFO order along each link. Each processor keeps a copy of the shared register.

  • To read the register, the processor reads the copy in its local memory.
  • A processor starts a write() call of value to register x, by sending the message “P_i: write to x” to .
  • If receives a message “P_j: write to x”, for , then it writes to its local copy of x, and forwards the message to .
  • If receives a message “P_i: write to x”, then it writes to its local copy of x, and discards the message. The write() call is now complete.

Give a short justification or counterexample.

If write() calls never overlap:

  • is this register implementation regular?
  • is it atomic?

If multiple processors call write():

  • is this register implementation safe?

Exercise 4.11. The following code shows an implementation of a multivalued write-once MRSW register from an array of multivalued safe MRSW registers. Remember, there is one writer, who can overwrite the register’s initial value with a new value, but it can only write once. You do not know the register’s initial value.

Is this implementation regular? Atomic?

class WriteOnceRegister implements Register {
  private SafeMRSWRegister[] s = new SafeMRSWRegister[3];
 
  public void write(int x) {
    s[0].write(x);
    s[1].write(x);
    s[2].write(x);
  }
 
  public int read() {
    v2 = s[2].read();
    v1 = s[1].read();
    v0 = s[0].read();
    if (v0 == v1) return v0;
    else if (v1 == v2) return v1;
    else return v0;
  }
}

Exercise 4.12. A single-writer register is 1-regular if the following conditions hold:

  • If a read() operation does not overlap with any write() operations, then it returns the value written by the last write() operation.
  • If a read() operation overlaps with exactly one write() operation, then it returns a value written either by the last write() operation or the concurrent write() operation.
  • Otherwise, a read() operation may return an arbitrary value.

Construct an SRSW -valued 1-regular register using SRSW Boolean regular registers. Explain why your construction works.

Exercise 4.13. Prove that the safe Boolean MRSW register construction from safe Boolean SRSW registers illustrated in Fig. 4.6 is a correct implementation of a regular MRSW register if the component registers are regular SRSW registers.

Exercise 4.14. Define a wraparound register that has the property that there is a value such that writing the value sets the value of the register to .

If we replace the Bakery algorithm’s shared variables with either regular, safe, or atomic wraparound registers, then does it still satisfy mutual exclusion and FIFO ordering?

You should provide six answers. Justify each claim.

Prev: Concurrent Objects Next: The relative power of primitive synchronization operations

Graph View

Backlinks