Как блокировки реализованы на нескольких ядрах

Question

Для однопроцессорного алгоритма блокировки довольно просто.

Lock(threadID) {
  Disable Interrupts
  If lock is already owned by same thread{
    Restore Interrupts
    return
  }
  if lock is free {
    make lock busy
    set current thread as the owner of the lock
  }
  else {
     add threadID to the lock queue.
  }
  Restore Interrupts
  return
}

Но как мы реализуем этот код в многопроцессорных / многоядерных системах. Что делать, если 2 ядра / прокси пытаются установить одинаковую блокировку для разных процессов.

Answer 1

Мьютексы обычно реализуются с атомарными операциями для одного значения памяти.Например, блокировка может быть одним словом, которое свободно при 0 и заблокировано при 1.Чтобы получить блокировку, процессор заблокирует шину памяти (чтобы другие процессоры не могли читать или записывать в память), считывать самое текущее значение слова, устанавливать его на 1, если оно равно 0, и разблокироватьшина памяти.Для разблокировки слово может быть установлено на 0.

. Это простой пример, в котором не говорится о том, что происходит, когда утверждается блокировка.Разные ОС справляются с этим, используя разные механизмы.Linux использует то, что называется futexes .Я не уверен, что делают Windows или Mac.

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

Answer 2

Я говорю, что самый простой способ думать о блокировке - это инструкция атомного обмена. Следующее приобретает блокировку X.

LOCK:
  set RegisterA = 1
  Atomic_Exchange(X, RegisterA)  //runs such that no other thread can work with X
  if RegisterA == 1:
    Means X was 1 when I esecuted the exchange thus someone else has the lock
    Since I do not have the lock, goto LOCK
  else:
    If A is zero, it means I was the first one to set X to 1, which means I own the lock

UNLOCK:
    X = 0

Атомный обмен существует в большинстве компьютеров. Intel x86 имеет инструкцию EXCHG для этого. Только для справки, у Intel x86 также есть инструкция сравнения и обмена, которая позаботится о приобретении, а также о сравнении для вас. По сути, вместо того, чтобы сначала выполнять обмен, а затем выполнять тестирование в программном обеспечении, он использует аппаратное обеспечение и выполняет обмен только в том случае, если X == 0 для начала. Это экономит дополнительную запись в переменную X, что уменьшает количество кеш-пропусков для X, что приводит к повышению производительности.