Как реализована синхронизация потоков на уровне языка ассемблера?

Пока я знаком с параллельными концепциями программирования, такими как мьютексы и семафоры, я никогда не понимал, как они реализованы на уровне ассемблера.

Я предполагаю, что есть набор флагов памяти, в которых говорится:

блокировка A удерживается в потоке 1
блокировка B удерживается потоком 3
блокировка C не поддерживается нитью
и т.д.

Но как синхронизируется доступ к этим флагам между потоками? Что-то вроде этого наивного примера только создало бы состояние гонки:

  mov edx, [myThreadId]
wait:
  cmp [lock], 0
  jne wait
  mov [lock], edx
  ; I wanted an exclusive lock but the above 
  ; three instructions are not an atomic operation :(

Ответ 1

На практике они обычно реализуются с помощью CAS и LL/SC. (... и некоторое вращение, прежде чем отказаться от временного среза потока - обычно, вызывая функцию ядра, которая переключает контекст.)
Если вам нужен только spinlock, wikipedia дает вам пример, который обрабатывает CAS для префикса блокировки xchg на x86/x64. Таким образом, в строгом смысле, CAS не требуется для создания спин-блокировки, но по-прежнему требуется какая-то атомарность. В этом случае он использует атомную операцию, которая может записывать регистр в память и возвращать предыдущее содержимое этого слота памяти за один шаг. (Чтобы уточнить немного: префикс блокировки утверждает сигнал #LOCK, который гарантирует, что текущий процессор имеет эксклюзивный доступ к памяти. На сегодняшних CPU это не обязательно выполняется таким образом, но эффект тот же. Используя xchg мы убеждаемся, что мы не получим где-то между чтением и записью, так как инструкции не будут прерываться на полпути. Поэтому, если бы у нас была мнимая блокировка mov reg0, mem/lock mov mem, пара reg1 (что мы надеваем, t), это не совсем то же самое - его можно было бы выгрузить только между двумя мобами.)
В современных архитектурах, как указано в комментариях, вы в основном используете атомарные примитивы процессора и протоколы согласованности, предоставляемые подсистемой памяти.
По этой причине вам необходимо не только использовать эти примитивы, но и учитывать согласованность кеш/памяти, гарантированную архитектурой.
Там могут быть и нюансы реализации. Принимая во внимание, например, спин-блокировка:
- вместо наивной реализации, вы, вероятно, должны использовать, например, a Запорная блокировка TTAS с некоторым экспоненциальным отклонением,
- на процессоре с поддержкой Hyper-Threaded, вы должны, вероятно, выпустить инструкции pause, которые служат подсказками, которые вы вращаете, чтобы ядро, в котором вы работаете, может сделать что-то полезное во время этого
- вы должны действительно отказаться от прядения и контроля производительности для других потоков через некоторое время
- и т.д...
это по-прежнему пользовательский режим - если вы пишете ядро, у вас могут быть и другие инструменты, которые вы можете использовать (так как именно вы планируете создавать потоки и обрабатываете/разрешаете/запрещаете прерывания).

Ответ 2

Архитектура x86 уже давно имеет инструкцию под названием xchg, которая будет обмениваться содержимым регистра с ячейкой памяти. xchg всегда был атомарным.

Также всегда существовал префикс lock, который можно применить к ~~any~~ для одной инструкции, чтобы сделать эту инструкцию атомой. Прежде чем появились многопроцессорные системы, все это на самом деле заключалось в том, чтобы предотвратить прерывание доставки в середине заблокированной инструкции. (xchg неявно заблокирован).

В этой статье приведен пример кода с использованием xchg для реализации спин-блокировки http://en.wikipedia.org/wiki/Spinlock

Когда стали разрабатываться многопроцессорные и более поздние многоядерные системы, необходимы более сложные системы, чтобы гарантировать, что блокировка и xchg будут синхронизировать все подсистемы памяти, включая кеш l1 на всех процессорах. Примерно в это же время новые исследования блокировки и блокировки алгоритмов показали, что атомный CompareAndSet был более гибким примитивом, поэтому более современные процессоры имеют это как инструкцию.

Приложение: В комментариях andras предоставлен "пыльный старый" список инструкций, которые позволяют префикс lock. http://pdos.csail.mit.edu/6.828/2007/readings/i386/LOCK.htm

Ответ 3

Мне нравится думать о синхронизации потоков как снизу вверх, где процессор и операционная система предоставляют конструкцию, примитивную для более сложных

На уровне процессора у вас есть CAS и LL/SC, которые позволяют выполнять тест и хранить в одной атомной операции... у вас также есть другие конструкции процессора, которые позволяют вам отключать и разрешать прерывание (однако они считаются опасно... при определенных обстоятельствах у вас нет другого выбора, кроме как использовать их)

Операционная система

обеспечивает возможность переключения контекста между задачами, которые могут возникать каждый раз, когда поток использует свой временной срез... или это может произойти из-за других причин (я приду к этому)

тогда существуют конструкции более высокого уровня, такие как мьютексы, которые используют эти примитивные механизмы, предоставляемые процессором (думаю, вращающийся мьютекс)... который будет постоянно ждать, пока условие станет истинным, и проверит это условие атомарно

тогда эти вращающиеся мьютекс могут использовать функциональность, предоставляемую ОС (контекстный переключатель и системные вызовы, такие как выход, который отдает управление другому потоку) и дает нам мьютексы

эти конструкции далее используются конструкциями более высокого уровня, такими как условные переменные (которые могут отслеживать, сколько потоков ожидает мьютекс и какой поток разрешить первым, когда мьютекс становится доступным)

Эти конструкции, которые могут быть использованы далее для предоставления более сложных конструкций синхронизации... пример: семафоры и т.д.