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

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

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

  • блокировка 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 :(

multithreading x86 concurrency synchronization assembly
person Martin    schedule 03.03.2010    source источник

Ответы (3)


arrow_upward
23
arrow_downward

  • На практике они обычно реализуются с помощью CAS и LL / SC. (... и некоторое вращение перед тем, как отказаться от временного отрезка потока - обычно путем вызова функции ядра, которая переключает контекст.)
  • Если вам нужна только спин-блокировка, википедия дает вам пример, который обменивает CAS на блокировку с префиксом xchg на x86. / x64. Таким образом, в строгом смысле CAS не требуется для создания спин-блокировки, но все же требуется некоторая атомарность. В этом случае он использует атомарную операцию, которая может записывать регистр в память и возвращать предыдущее содержимое этого слота памяти за единичный шаг. (Чтобы уточнить немного больше: префикс lock утверждает сигнал #LOCK, который гарантирует, что текущий ЦП имеет монопольный доступ к памяти. В современных ЦП это не обязательно выполняется таким образом, но эффект то же самое. Используя xchg, мы гарантируем, что нас не вытеснят где-то между чтением и записью, поскольку инструкции не будут прерваны на полпути. Итак, если бы у нас была мнимая блокировка mov reg0, mem / lock mov mem , reg1 (которую мы не делаем), это не совсем то же самое - ее можно было бы вытеснить только между двумя mov.)
  • В текущих архитектурах, как указано в комментариях, вы в основном используете атомарные примитивы ЦП и протоколы согласованности, предоставляемые подсистемой памяти.
  • По этой причине вы должны не только использовать эти примитивы, но и учитывать согласованность кеш-памяти и памяти, гарантированную архитектурой.
  • There may be implementation nuances as well. Considering e.g. a spinlock:
    • instead of a naive implementation, you should probably use e.g. a TTAS spin-lock with some exponential backoff,
    • на гиперпоточном процессоре вам, вероятно, следует выпустить pause инструкции, которые служат подсказками, что вы вращаете, чтобы ядро, на котором вы работаете, могло делать что-то полезное во время этого
    • вам действительно стоит отказаться от вращения и передать контроль другим потокам через некоторое время
    • и т.д...
  • это все еще пользовательский режим - если вы пишете ядро, у вас могут быть другие инструменты, которые вы также можете использовать (поскольку вы тот, кто планирует потоки и обрабатывает / включает / отключает прерывания).
person Andras Vass    schedule 03.03.2010
comment
Чтобы расширить это, CAS и аналогичные операции используются для реализации синхронизации, потому что процессоры специально спроектированы так, чтобы они были атомарными операциями - они делают все за один шаг, и никакая другая операция не может их прервать. - person Amber; 03.03.2010
comment
Примечание: как указал Джон Неллер, xchg подразумевает блокировку, начиная с 80386 - префикс записан в большинстве примеров для ясности (что я считаю хорошей практикой) , а не по необходимости. Это неверно для других - например, cmpxchg. Поэтому я думаю, что безопаснее всего всегда явно указывать префикс, когда вы намереваетесь получить монопольный доступ к памяти. - person Andras Vass; 03.03.2010

arrow_upward
11
arrow_downward

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

Также всегда существовал префикс lock, который можно было применить к любой отдельной инструкции, чтобы сделать эту инструкцию атомарной. До того, как появились многопроцессорные системы, все это действительно было для предотвращения доставки прерывания в середине заблокированной инструкции. (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

person John Knoeller    schedule 03.03.2010
comment
@andras: Да, я полагаю, это вводило в заблуждение, я изменю формулировку. И спасибо за список. - person John Knoeller; 03.03.2010

arrow_upward
2
arrow_downward

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

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

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

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

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

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

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

person jsshah    schedule 03.03.2010