RMW

x86:

[lock](<https://www.felixcloutier.com/x86/lock>) add/sub/xor/...

xchg %r32, m32  //  exchange; "lock" implied

lock xadd %r32, m32  //  { tmp = m32; m32 += r32; r32 = tmp; }

lock cmpxchg %r32, m32  // CAS — compare and swap
// Compare %eax with m32.
// If equal, set ZF and load r32 into m32.
// Else, clear ZF and load m32 into %eax.

C11:

#include <stdatomic.h>

_Bool atomic_compare_exchange_strong(volatile A *object, C *expected, C desired);
_Bool atomic_compare_exchange_weak(volatile A *object, C *expected, C desired);
/*
Atomically, compares the value pointed to by object for equality
with that in expected, and if true, replaces the value pointed to by object with
desired, and if false, updates the value in expected with the value pointed to by
object.
Returns the result of the comparison.
*/

if (weak && !x86) {
	sometimes {
		return false;  // weak-версия иногда фейлится просто так
    // load-linked + store-conditional — напомните рассказать, если время будет
	}
}
atomically {
  bool equal = (*object == *expected);
  *expected = *object;
  if (equal) {
		*object = desired;
	}
	return equal;
}

C++: cppreference.

Критические секции (мьютексы)

Бывают вещи, которые нужно сделать атомарно, а готовой atomic/RMW операции для этого нет:

struct list {
	int val;
  struct list* next;
}

void push(struct list** head, int value) {
	struct list *node = calloc(1, sizeof(*node));
  node->val = value;
	spin_lock(lock);
  {
    node->next = *head;
    *head = node;
  }
  spin_unlock(lock);
}

/*
Thread 0         Thread 1
*head = node;
lock = 0;  ----> lock == 0
                 node->next = *head;
*/

Mutex — от MUTual EXclusion.

Перед тем, как построить мьютекс, построим спинлок.

Spinlock

int spinlock;
// 0 — unlocked
// 1 — locked

Будем пользоваться примитивом Compare-And-Swap:

cmpxchg(var, expected, desired) {
	atomically {
		old = var;
		if (var == expected) {
			var = desired;
		}
		return old;
	}
}

Спинлок:

typedef _Atomic int spinlock;

// Неэффективный, но работающий спинлок
void spin_lock(spinlock *s) {
	while (cmpxchg(*s, 0, 1) != 0) { asm volatile ("pause"); }
}

void spin_unlock(spinlock *s) {
	*s = 0;
}

Спинлок отлично работает, когда защищает пару инструкций, но бесконечно тратит ресурсы, если нужно подождать подольше. На этот случай нам нужен способ остановиться и подождать, а с этим нам может помочь только ядро.

Фьютексы

Примитив синхронизации в ядре Linux (википедия):