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

Question

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

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

• замок А удерживается нитью 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 :(

Answer 1

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

Answer 2

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

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

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

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

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

Answer 3

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

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

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

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

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

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

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