Reading 7. HTM. Multiple atomic read-write operations

Stone et al., IEEE Concurrency 1993: Multiple atomic read-write operations ("Oklahoma Update")

Let's extend compare&swap command set to support multiple memory locations.

• read-and-reserve - reads a memory location into a specified general-purpose register, places a reservation on the location’s address in the reservation register, and clears the reservation register’s data field.
• store-contingent - locally updates the reservation register’s data field without obtaining write permissions.
• write-if-reserved - specifies a set of reservation registers and updates the memory locations reserved by those registers. It is used to initiate the commit process. It attempts to obtain exclusive ownership for each of the addresses in the reservation registers. If the reservations remain valid during this process, the instruction updates memory with the modified data from the reservation registers. The instruction returns an indication whether the update succeeded or not.

Example

Having such commands we can write i.e. synchronized queue:

void Enqueue(newpointer) {
 Memory[newpointer].next = NULL;
 status = 0;

 while (!status) {
   last_pointer = Read_and_Reserve(Memory[tail].next, reservation1);
   if (last_pointer == NULL) {
     // this is an empty queue
     first_pointer = Read_and_Reserve(Memory[head].next, reservation2);
     Store_Contingent(newpointer, reservation1);
     Store_Contingent(newpointer, reservation2);
     status = Write_If_Reserved(reservation1, reservation2);
   } else {
     // non-empty queue
     temp_pointer = Read_and_Reserve(Memory[last_pointer].next, reservation2);
     Store_Contingent(newpointer, reservation1);
     Store_Contingent(newpointer, reservation2);
     status = Write_If_Reserved(reservation1, reservation2);
   }
 } // repeat until successful

 return;
}

Implementation

Compared to compare&swap decomposition, hardware implementation for Oklahoma Update is much more complex.
Instead of one xa-address register this implementation requires number of reservation registers per CPU to store memory locations and various flags. Those are places
read-and-reserve and store-contingent writes to. And write-if-reserved can be called commit operation since it commits all local writes to shared memory.

Basically, commit operation consists of two phases:

• Requesting write permissions. CPU ensures having exclusive write lock to every location from reservation registers. To avoid deadlocking to commit operations from other processors, CPU acquires locks in address-ascending manner.
  
  If it can't obtain every one lock entire conflict resolution takes place. CPU may try to restart the process after some time or abort the operation.
• Commiting data values. As soon as processor has locks it starts uninterruptable operation to write data.
  

Interactions between the new instructions and regular store operations introduce forward-progress concerns. Regular stores do not participate in the new instructions’ conflict resolution mechanism. If a regular store from one processor conflicted with an address specified in a reservation register of another processor, this processor would abort its update. See more on this in the original paper.

Classification

Strong or weak isolation	Strong
Transaction granularity	Cache line
Direct or deferred update	Deferred (in reservation registers)
Concurrency control	Optimistic. Commit initiates acquiring ownership
Conflict detection	Late write-write conflict (if not a regular store) Late write-read conflict (if not a regular store)
Inconsistent reads	None
Conflict resolution	Address-based rwo-phase commit
Nested transaction	N/A

Sources

• J.R. Larus, R.Rajwar Transactional Memory, 4.3.4
• J. M. Stone, H. S. Stone, P. Heidelberger and J. Turek, “Multiple reservations and the Oklahoma update,” IEEE Concurrency, Vol. 1(4), pp. 58–71 Nov. 1993.