Wait-free counters

Suppose that there are two threads that share a wait-free counter. They would each like to perform fetch, increment and decrement operations, with the following requirements.

1. A fetch operation returns a value that the counter had at some point during the processing of the fetch operation. That is, it gets a snapshot of the counter. (Remember that one thread can be changing the counter while the other does a fetch.)

2. The steps of the operations can be interleaved in any way without damaging the value of the counter. For example, if the counter has value 5 and one thread is doing a decrement while the other does an increment, then after both threads have performed their operations the counter still has value 5. There is no interference.

3. Neither thread is allowed to wait for the other thread to do anything. This is why the counter is called wait-free. Any thread can stop for arbitrarily long at any time, including in the middle of a fetch, increment or decrement operation. The other thread must still be able to perform operations on the counter.

Problems

1. Describe how to implement a wait-free counter that can be shared by two threads. Assume that the memory only supports fetch and store instructions. To increment a memory cell, you must fetch the value into a register, increment the register, and then store the value back into the memory cell. There is no atomic increment or decrement instruction.

   Hint. Use two variables to represent the counter. Make sure that one of the variables is only modified by the first thread, and the other variable is only modified by the second thread.

2. Explain why a straightforward generalization of your solution to problem 1 does not work for a counter that is to be shared by three threads.

3. Suppose that your memory supports an atomic memory-to-memory swap instruction. That is, there is a single instruction that is given two memory addresses, and swaps the contents of those two addresses (with the memory bus locked the entire time, so that no other changes to the memory can happen simultaneously).

   Show a simple solution to the critical section problem using a swap instruction. The solution must work for n threads, for arbitrary n, and must satisfy all of the requirements of the critical section problem, including bounded waiting. The solution should use busy-waiting (spinlock) to wait for access to the critical section. Make your solution as simple as you can. See the solution in the textbook using test-and-set.

   Hint: have a shared variable that tells whether any thread is in the critical section, and another variable for each thread telling whether that thread is waiting to get into the critical section.

4. Silberschatz and Galvin, exercise 6.10.

5. Silberschatz and Galvin, exercise 6.17.