If, like me, you have no idea what's going on here: LR/SC stands for load-reserved/store-conditional, also called load-linked/store-conditional. In a traditio

If, like me, you have no idea what's going on here: LR/SC stands for load-reserved/store-conditional, also called load-linked/store-conditional. In a traditional atomic implementation using Compare-and-Swap, the order of execution is as follows: 1. Read value X into register A. 2. Do computation using register A, creating a new value in register B. 3. Do a compare-and-swap on value X: If X == A, then set X to B. The operation was successful. If X != B, another thread changed X while we were using it, so the operation failed. Rollback and retry. This suffers from the ABA problem: it does not detect the case where another thread changes X to a new value C, but then changed it back to A before the compare-and-swap happens. An example: def push(stack, val): 1. new = malloc() 2. new->data = val 3. orig = atomic_load(&stack->head) 4. new->next = orig 5. compare_and_swap(&stack->head, new, orig) // todo retry on CAS failure def pop(stack): 1. orig = atomic_load(&stack->head) 2. new = orig->next 3. compare_and_swap(&stack->head, new, orig) // again, retry skipped for brevity 4. val = orig->data 5. free(orig) 6. return val This allows for the following order of execution: Our stack contains 3 items at 0x01, 0x02, 0x03. Thread 1 calls pop 1. orig = atomic_load(&stack->head) // orig = 0x01 2. new = orig->next // new = 0x02 Context switch. Thread 2 calls pop twice. 1. orig = atomic_load(&stack->head) // orig = 0x01 2. new = orig->next // new = 0x02 3. compare_and_swap(&stack->head, new, orig) // stack->head = 0x02 5. free(orig) // 0x01 is freed 1. orig = atomic_load(&stack->head) // orig = 0x02 2. new = orig->next // new = 0x03 3. compare_and_swap(&stack->head, new, orig) // stack->head = 0x03 5. free(orig) // 0x02 is freed Context switch. Thread 3 calls push. 1. new = malloc() // new = 0x01. Valid, it was just freed. 3. orig = atomic_load(&stack->head) // orig = 0x03 4. new->next = orig // new->next = 0x03 5. compare_and_swap(&stack->head, new, orig) // stack->head = 0x01 Context switch. Thread 1 continues pop 3. compare_and_swap(&stack->head, new, orig) // stack->head = 0x02 5. free(orig) // 0x01 is freed Boom. stack->head now points to 0x02, which has already been freed! LR/SC avoids this by having "lr" reserve a memory location. On calling "sc", if any write to it occured since "lr", the write will fail - even if the content when "sc" is called is identical to the content when "lr" was called. Please feel free to correct me if I got anything wrong - this is what I found when trying to understand it myself!