Инструкция Test-and-Set¶

Test-and-Set (TAS) — это атомарная машинная инструкция, используемая в многопроцессорных и многопоточных системах для реализации примитивов синхронизации, в первую очередь — мьютексов (взаимных исключений) и спин-блокировок (spinlocks). Она выполняет две операции — чтение значения из ячейки памяти и запись в неё нового значения — как единое, неделимое действие, что предотвращает состояние гонки (race condition) при одновременном доступе нескольких потоков или процессов к общему ресурсу.

¶История

Инструкция Test-and-Set была разработана в 1960-х годах для ранних многопроцессорных систем, таких как IBM System/360. В этих системах возникла необходимость в аппаратной поддержке синхронизации, поскольку программные методы (например, алгоритм Деккера) требовали сложных и неэффективных циклов ожидания. Первые реализации TAS были реализованы на уровне центрального процессора (ЦП) и использовали специальные сигналы шины памяти для блокировки доступа других процессоров на время выполнения операции.

В 1970-х годах TAS стала стандартной инструкцией в архитектурах x86 (как инструкция XCHG с префиксом LOCK), ARM (инструкция LDREX/STREX, эмулирующая TAS), SPARC и других. С развитием многоядерных процессоров и операционных систем, поддерживающих многопоточность (например, Linux и Windows), TAS остаётся одним из базовых строительных блоков для реализации высокопроизводительных блокировок.

¶Принцип работы

Инструкция Test-and-Set выполняет следующую последовательность операций атомарно:

1. Чтение текущего значения из ячейки памяти (обычно это 1 байт, слово или двойное слово).
2. Запись нового значения (чаще всего — 1, или «истина») в ту же ячейку.
3. Возврат старого значения (прочитанного на шаге 1) в регистр процессора или в аккумулятор.

На псевдокоде это можно описать так:

`` function TestAndSet(var lock: boolean): boolean old = lock lock = true return old ``

Ключевое свойство — атомарность: никакой другой процессор или поток не может прервать выполнение этой последовательности между чтением и записью. В современных процессорах атомарность обеспечивается либо аппаратной блокировкой шины памяти (например, с помощью сигнала LOCK# в x86), либо через протоколы когерентности кэша (MESI, MOESI), которые гарантируют, что во время выполнения инструкции ни один другой кэш не содержит модифицированной копии этой ячейки.

¶Применение

¶Реализация мьютексов (спин-блокировок)

Наиболее распространённое применение TAS — создание спин-блокировок (spinlock). Спин-блокировка — это простейший мьютекс, в котором поток, пытающийся захватить блокировку, непрерывно циклически проверяет её состояние («крутится» в цикле ожидания) до тех пор, пока блокировка не станет доступной.

Псевдокод захвата спин-блокировки с помощью TAS:

``` lock = 0 // 0 — свободно, 1 — занято

while TestAndSet(lock) == 1 // ждать (spin) // (возможна вставка инструкции PAUSE для снижения энергопотребления) ```

Поток вызывает TestAndSet(lock). Если lock был равен 0 (свободен), инструкция возвращает 0 и устанавливает lock в 1 — поток успешно захватывает блокировку. Если lock уже был равен 1 (занят), инструкция возвращает 1 и оставляет lock в 1 — поток продолжает цикл ожидания.

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

¶Другие примитивы синхронизации

На основе TAS могут быть построены более сложные примитивы, такие как:

• Семафоры (с помощью TAS реализуется атомарное уменьшение счётчика).
• Барьеры памяти (в комбинации с другими инструкциями).
• Атомарные счётчики (например, для подсчёта ссылок в объектах).
• Реализация очередей без блокировок (lock-free queues) — хотя для этого чаще используются более мощные инструкции, такие как Compare-and-Swap (CAS).

¶Классификация

¶По способу реализации

1. Аппаратная TAS — реализована непосредственно в наборе инструкций процессора. Обеспечивает максимальную производительность, но требует поддержки на уровне кэша и шины.
2. Программная эмуляция TAS — используется в системах без аппаратной поддержки (например, в некоторых старых архитектурах или в эмуляторах). Реализуется через отключение прерываний на время выполнения операции (на однопроцессорных системах) или через использование специальных протоколов (например, в распределённых системах — через алгоритм Деккера).

¶По типу блокировки

• Test-and-Set с ожиданием (spinlock) — поток активно ждёт, потребляя процессорное время. Эффективен при коротких периодах удержания блокировки.
• Test-and-Set с блокировкой потока (sleeping lock) — если блокировка не захвачена, поток переводится в состояние ожидания (вытесняется из процессора). Реализуется на уровне операционной системы (например, через системные вызовы futex в Linux или WaitForSingleObject в Windows). TAS используется только для быстрой проверки и захвата блокировки без переключения контекста.

¶Преимущества и недостатки

¶Преимущества

• Простота — минимальная логика, легко реализуется как аппаратно, так и программно.
• Низкая задержка — для захвата свободной блокировки требуется всего одна атомарная инструкция.
• Независимость от планировщика — не требует поддержки со стороны операционной системы (в случае спин-блокировок).
• Работа в контексте прерываний — может использоваться в обработчиках прерываний, где запрещено переключение контекста.

¶Недостатки

• Активное ожидание (busy-waiting) — в спин-блокировках поток тратит процессорное время впустую, что снижает общую производительность системы, особенно при большом числе потоков.
• Проблема инверсии приоритетов — если низкоприоритетный поток удерживает блокировку, а высокоприоритетный поток пытается её захватить, высокоприоритетный поток может бесконечно долго ждать (если планировщик не вытеснит низкоприоритетный поток).
• Неэффективность на многоядерных системах — при большом числе ядер активное ожидание приводит к интенсивному трафику на шине памяти и кэш-промахам, что замедляет работу всех потоков.
• Отсутствие гарантии прогресса (starvation) — при высокой конкуренции некоторые потоки могут никогда не захватить блокировку (особенно в наивной реализации без очереди).

¶Сравнение с другими атомарными инструкциями

¶Интересные факты

• В архитектуре x86 инструкция XCHG (обмен значениями между регистром и памятью) с префиксом LOCK фактически является реализацией Test-and-Set, если второй операнд — регистр, содержащий 1.
• В ранних версиях операционной системы Linux (до версии 2.6) спин-блокировки были реализованы исключительно на TAS. Начиная с версии 2.6, для повышения производительности на многоядерных системах была внедрена очередь ожидания (ticket spinlock), которая использует TAS только для захвата «билета».
• В некоторых архитектурах (например, в ARMv7) инструкция TAS отсутствует, и её роль выполняет пара инструкций Load-Linked (LDREX) и Store-Conditional (STREX), которые эмулируют поведение TAS через цикл повторения.
• Инструкция TAS может быть использована для реализации простейшего семафора, но для этого требуется дополнительная логика управления счётчиком.

¶Критика

Основная критика в адрес Test-and-Set связана с её неэффективностью в условиях высокой конкуренции. Активное ожидание (spin) приводит к неоправданному расходу энергии и снижению пропускной способности системы. В современных высоконагруженных системах (например, в базах данных или веб-серверах) предпочтение отдаётся более сложным, но масштабируемым механизмам синхронизации, таким как блокировки на основе очередей (MCS lock, CLH lock) или lock-free структуры данных, использующие Compare-and-Swap.

Кроме того, в системах реального времени (RTOS) использование спин-блокировок на TAS может привести к нарушению временных гарантий, так как поток, ожидающий блокировку, не может быть вытеснен планировщиком.