Как синхронизация потока реализована на уровне ассемблера?
В то время как я знаком с параллельными концепциями программирования, такими как взаимные исключения и семафоры, я никогда не понимал, как они реализованы на уровне ассемблера.
Я предполагаю там быть рядом высказывания "флагов" памяти:
- блокировка 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 :(
3 ответа
- На практике они обычно реализуются с CAS и LL / SC . (... и некоторое вращение перед тем, как отказаться от временного отрезка потока - обычно путем вызова функции ядра, которая переключает контекст.)
- Если вам нужна только спин-блокировка , википедия дает вам пример, в котором CAS заменяется блокировкой. с префиксом
xchgна x86 / x64. Таким образом, в строгом смысле CAS не требуется для создания спин-блокировки, но все же требуется некоторая атомарность. В этом случае он использует атомарную операцию, которая может записывать регистр в память и возвращать предыдущее содержимое этого слота памяти за один шаг . (Чтобы уточнить немного больше: префикс lock устанавливает сигнал #LOCK, который гарантирует, что текущий ЦП имеет монопольный доступ к памяти. В современных ЦП это не обязательно выполняется таким образом, но эффект то же самое.Используяxchg, мы гарантируем, что мы не будем вытеснены где-то между чтением и записью, поскольку инструкции не будут прерваны на полпути. Итак, если бы у нас была мнимая блокировка mov reg0, mem / lock mov mem, reg1 пара (которую мы не делаем), это не совсем то же самое - ее можно было бы вытеснить только между двумя mov.) - В текущих архитектурах, как указано в комментариях, вы в основном используете атомарные примитивы ЦП и протоколы согласованности, предоставляемые подсистемой памяти.
- По этой причине вы не только должны использовать эти примитивы, но и учитывать согласованность кэша / памяти, гарантированную архитектурой.
- Также могут быть нюансы реализации. Учитывая, например, спин-блокировка:
- вместо наивной реализации вам, вероятно, следует использовать, например, спин-блокировка TTAS с некоторой экспоненциальной задержкой ,
- на гиперпоточном процессоре, вам, вероятно, следует выполнить инструкции
pause, которые служат подсказками, что вы вращаете - чтобы ядро, на котором вы работаете, может сделать что-то полезное во время этого - , вам действительно следует отказаться от вращения и через некоторое время передать управление другим потокам
- и т. д.
- это все еще пользовательский режим - если вы при написании ядра у вас могут быть другие инструменты, которые вы также можете использовать (поскольку вы тот, кто планирует потоки и обрабатывает / включает / отключает прерывания).
Архитектура x86 уже давно имеет инструкцию под названием xchg, которая обменивается содержимым регистра с ячейкой памяти. xchg всегда была атомарной.
Также всегда существовал префикс lock, который можно было применить к любой отдельной инструкции, чтобы сделать ее атомарной. До появления многопроцессорных систем все, что это действительно делало - предотвращало прерывание в середине заблокированной инструкции. (xchg был неявно заблокирован).
В этой статье есть пример кода, использующего xchg для реализации спинлока http://en.wikipedia.org/wiki/Spinlock
Когда начали создаваться многопроцессорные, а затем и многоядерные системы, потребовались более сложные системы для обеспечения синхронизации всех подсистем памяти, включая кэш l1 на всех процессорах, с помощью lock и xchg. Примерно в это же время новые исследования алгоритмов блокировки и безблокировочных алгоритмов показали, что атомарный CompareAndSet является более гибким примитивом, поэтому в современных процессорах он используется в качестве инструкции.
Дополнение: В комментариях andras предоставил "пыльный старый" список инструкций, допускающих префикс lock. http://pdos.csail.mit.edu/6.828/2007/readings/i386/LOCK.htm
Мне нравится рассматривать синхронизацию потоков снизу вверх, когда процессор и операционная система обеспечивают конструкцию, от примитивной до более сложной.
На уровне процессора у вас есть CAS и LL / SC, которые позволяют выполнять тест и сохранять в одной атомарной операции ... у вас также есть другие конструкции процессора, которые позволяют вам отключать и разрешать прерывания (однако они считаются опасными ... при определенных обстоятельствах у вас нет другого выхода, кроме как их использовать)
операционная система предоставляет возможность переключения контекста между задачами, которые могут происходить каждый раз, когда поток использует свой временной интервал ... или это может происходить по другим причинам (я перейду к этому)
, тогда есть конструкции более высокого уровня, такие как мьютексы, которые используют эти примитивные механизмы, предоставляемые процессором (подумайте о вращающемся мьютексе) ... который будет постоянно ждать, пока условие станет истинным, и проверяет это условие атомарно
, тогда этот вращающийся мьютекс может использовать предоставленную функциональность ОС (переключение контекста и системные вызовы, такие как yield, который передает управление другому потоку) и дает нам мьютексы
, эти конструкции в дальнейшем используются конструкциями более высокого уровня, такими как условные переменные (которые могут отслеживать, сколько потоков ожидают мьютекс и какой поток разрешить первым, когда мьютекс станет доступным)
Эти конструкции могут быть использованы в дальнейшем для обеспечения более сложных конструкций синхронизации ...пример: семафоры и т. д.