Test-and-set

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

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

Инструкция test-and-set работает с одним операндом — адресом ячейки памяти (обычно размером в слово). Её выполнение состоит из двух шагов, которые гарантированно выполняются атомарно (без прерывания):

1. Чтение текущего значения из указанной ячейки памяти.
2. Запись в эту же ячейку нового значения (как правило, 1 или true).

Результатом операции является старое значение, прочитанное на первом шаге. Если старое значение равно 0 (свободно), поток считается захватившим ресурс; если 1 (занято), поток понимает, что ресурс уже используется другим потоком, и может либо повторить попытку (спин-блокировка), либо перейти в режим ожидания.

Псевдокод

Атомарная операция test-and-set может быть описана следующим псевдокодом:

`` function test_and_set(lock) { old = lock; // Чтение текущего значения lock = 1; // Запись единицы return old; // Возврат старого значения } ``

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

История

Концепция атомарных операций для синхронизации возникла в 1960-х годах с развитием многозадачных операционных систем. Первые реализации test-and-set появились в мейнфреймах IBM System/360 (1964 год), где использовалась инструкция CS (Compare and Swap) и её модификации. В 1970-х годах алгоритм test-and-set был формализован в контексте теории параллельных вычислений, в частности, в работах Эдсгера Дейкстры по взаимному исключению.

В 1980-х годах, с распространением многопроцессорных систем (например, Symmetry SGI, Sequent Balance), test-and-set стала стандартной инструкцией в наборах команд процессоров Intel x86 (инструкция LOCK XCHG), ARM (инструкции LDREX/STREX), SPARC и других архитектур. В современных процессорах test-and-set часто реализуется через более гибкие примитивы, такие как compare-and-swap (CAS), но остаётся базовым элементом для построения низкоуровневых блокировок.

Реализация в процессорах

Архитектура x86

В процессорах Intel и AMD инструкция test-and-set реализуется через префикс LOCK в сочетании с инструкцией XCHG (обмен значениями). Например:

``assembly lock xchg eax, [lock_var] ; Атомарно обменивает eax (обычно 1) с содержимым lock_var ``

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

Архитектура ARM

В процессорах ARM (включая Cortex-A, Apple Silicon) test-and-set реализуется через пару инструкций LDREX (Load-Exclusive) и STREX (Store-Exclusive). LDREX читает значение и помечает ячейку памяти как «отслеживаемую», а STREX пытается записать новое значение, проверяя, не изменилась ли ячейка другим ядром. Если запись прошла успешно, операция считается атомарной. Пример:

``assembly try: ldrex r0, [r1] ; Атомарное чтение cmp r0, #0 ; Проверка, свободен ли ресурс strexeq r2, #1, [r1] ; Попытка записи единицы cmpeq r2, #0 ; Проверка успешности записи bne try ; Если не удалось — повторить ``

Архитектура RISC-V

В RISC-V (открытый стандарт) test-and-set реализуется через инструкции атомарного доступа (A-расширение), например AMOSWAP.W (Atomic Memory Swap Word):

``assembly amoswap.w r0, r1, (r2) ; Атомарно обменивает r1 с содержимым по адресу r2, результат в r0 ``

Применение

Реализация мьютексов

Test-and-set используется для построения простейших спин-блокировок (spinlock). Поток циклически вызывает TAS, пока не получит значение 0 (свободно). Пример на C:

```c volatile int lock = 0;

void acquire() { while (test_and_set(&lock) == 1) { // ожидание (spinning) } }

void release() { lock = 0; // не обязательно атомарно, так как только один поток пишет } ```

Семафоры и барьеры

На основе TAS строятся более сложные примитивы синхронизации: семафоры (счётчики ресурсов), барьеры памяти (memory barriers), условные переменные. В операционных системах (Linux, Windows) test-and-set используется в ядре для быстрой синхронизации коротких критических секций.

Очереди без блокировок (lock-free)

Test-and-set применяется в алгоритмах без блокировок, таких как lock-free стек (Treiber stack) или lock-free очередь (Michael-Scott). В этих алгоритмах TAS используется для атомарного обновления указателей.

Недостатки и ограничения

Проблема «активного ожидания» (busy-waiting)

Основной недостаток test-and-set в спин-блокировках — трата процессорного времени на циклы ожидания, особенно при высокой конкуренции. Это может привести к снижению производительности и перегреву процессора. Для смягчения применяются методы:

• Пауза (pause instruction на x86) — снижает энергопотребление.
• Экспоненциальная задержка (exponential backoff) — поток ждёт всё дольше между попытками.
• Передача управления (yield) — поток добровольно отдаёт процессорное время.

Проблема «инверсии приоритетов»

В системах с приоритетами потоков низкоприоритетный поток, захвативший блокировку через TAS, может быть вытеснен высокоприоритетным, который будет ждать освобождения ресурса. Это решается через протоколы наследования приоритетов (priority inheritance) в операционных системах реального времени.

Ограничение на масштабируемость

При большом числе ядер (16 и более) спин-блокировки на основе TAS могут вызывать перегрузку шины памяти из-за постоянных попыток записи. Для таких случаев применяются более эффективные алгоритмы: MCS-блокировка (Mellor-Crummey and Scott) или ticket-блокировка, которые используют очереди ожидания на уровне ядра.

Альтернативы

• Compare-and-swap (CAS): более гибкая атомарная операция, позволяющая сравнивать и менять значение только при совпадении ожидаемого. Используется в lock-free структурах данных.
• Load-link/store-conditional (LL/SC): пара инструкций, как в ARM (LDREX/STREX), позволяющая реализовать CAS и TAS без блокировки шины.
• Fetch-and-add (FAA): атомарное прибавление константы к ячейке памяти, используется в счётчиках и барьерах.
• Test-and-test-and-set (TTAS): модификация TAS, где поток сначала читает значение без записи (обычным load), и только если оно равно 0, пытается выполнить TAS. Это снижает нагрузку на шину.

Примеры в языках программирования

• C++11: std::atomic_flag — реализует test-and-set через метод test_and_set().
• Java: AtomicBoolean — метод compareAndSet() (основан на CAS), но для TAS используется getAndSet(true).
• C#: Interlocked.Exchange(ref lock, 1) — атомарный обмен, аналогичный TAS.
• Linux kernel: atomic_xchg() — функция для атомарного обмена, эквивалентная TAS.

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

• Инструкция test-and-set в процессорах x86 (через LOCK XCHG) является одной из самых старых атомарных операций, сохранившихся с 1980-х годов.
• В суперкомпьютерах Cray (1980-е) test-and-set реализовывался на уровне аппаратных регистров, что позволяло синхронизировать до 64 процессоров.
• В некоторых архитектурах (например, в ранних версиях ARM) test-and-set отсутствовал аппаратно, и его эмулировали через прерывания и отключение кэша.

Источники

• Maurice Herlihy, Nir Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 2012.
• Intel 64 and IA-32 Architectures Software Developer’s Manual, Volume 2A: Instruction Set Reference, A-L.
• ARM Architecture Reference Manual, ARMv8-A.
• Andrew S. Tanenbaum, Herbert Bos. Modern Operating Systems. Pearson, 2015.
• Документация Linux kernel: Documentation/locking/spinlocks.txt.