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

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

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

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

3 ответа

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

В архитектуре 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

Источник

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

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

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

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

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

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

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

Источник
Другие вопросы по тегам