Тема 4. Организация параллельной обработки с использованием средств исключения и предупреждения состязаний

Учебные вопросы

• Параллелизм, разделяемая память и критерии Дейкстры
• Алгоритм Петерсона, Out-of-Order и барьеры памяти
• Аппаратные атомики (CAS, LOCK), проблема ABA
• Легковесные блокировки (SRWLock, futex, спинлоки)
• Задача «Производители–Потребители» и дедлоки (Deadlock)

Цели занятия

• Понять влияние внеочередного исполнения ЦПУ на память
• Изучить работу инструкции Compare-And-Swap (CAS)
• Освоить применение легковесных блокировок Ring 3
• Реализовать схему «Производитель–Потребитель»
• Изучить 4 условия Коффмана и иерархический порядок захвата

Параллелизм в архитектурах SMP

• Многоядерные процессоры исполняют потоки одновременно
• Потоки разделяют память: кучу (Heap), глобальные переменные, дескрипторы
• Обеспечивает масштабирование вычислительной мощности

Проблема состязаний (Race Condition)

• Недетерминированное поведение при одновременной модификации
• Искажение данных: считывание частично записанных структур
• Требует строгой изоляции критических участков программы

Понятие критической секции

• Критическая секция: участок программного кода, обращающийся к разделяемому ресурсу
• Должен выполняться как атомарная транзакция

Три условия Дейкстры (1965)

1. Взаимное исключение: внутри критической секции одновременно не более одного потока
2. Прогресс: свободная секция немедленно доступна любому ждущему потоку
3. Ограниченное ожидание: конечное время ожидания; отсутствие голодания (Starvation)

Программная синхронизация (1981)

bool flag[2] = {false, false};
int turn = 0;

// Поток 0 (для Потока 1 — симметрично)
void Enter_Peterson(void) {
    flag[0] = true; // Намерение войти
    turn = 1;       // Вежливость: уступить
    while (flag[1] && turn == 1) {
        // Активное ожидание (spin)
    }
}

void Leave_Peterson(void) {
    flag[0] = false; // Освобождение
}

Доказательство корректности

• turn равен либо 0, либо 1, и не может быть равен обоим одновременно
• Поток, записавший turn последним, сам себя блокирует в while
• Обеспечивает взаимное исключение и прогресс на модели последовательной консистентности

Аппаратное переупорядочивание

• Современные процессоры оптимизируют конвейер через Store Buffers
• Чтение обгоняет запись: Store-Load Reordering
• Внеочередное исполнение (Out-of-Order) приводит к тому, что оба потока входят в секцию Петерсона!

Барьеры памяти (Memory Fences)

• MFENCE (x86/x64): останавливает конвейер до сброса буферов записи в кэш L1
• Запрещают переупорядочивание инструкций компилятором и микропроцессором
• В C11/C++20: std::memory_order_seq_cst, acquire, release

Семантика операции CAS

bool CAS(int *addr, int exp, int val) {
    ATOMICALLY {
        if (*addr == exp) {
            *addr = val;
            return true;
        }
        return false;
    }
}

• Основа неблокирующих алгоритмов (Lock-Free)
• Позволяет безопасно обновить указатель без захвата мьютекса

Инструкция ЦПУ: LOCK CMPXCHG

• Выполняет чтение, сравнение и запись неделимо
• Блокирует кэш-линию в монопольном состоянии протокола MESI (Modified)
• В Windows: InterlockedCompareExchange
• В Linux / GCC: __atomic_compare_exchange_n

Сущность проблемы ABA

1. Поток 1 считывает вершину стека со значением A
2. Поток 1 вытеснен планировщиком
3. Поток 2 удаляет A, удаляет B, освобождает память
4. Поток 3 выделяет узел; аллокатор возвращает тот же адрес A!
5. Поток 1 просыпается: *top == A (успех CAS), но A->next указывает на разрушенный узел B
6. Результат: разрушение структуры данных!

Архитектурное решение

• Версионирование (Tagged Pointers): вместе с адресом хранится 64-битный счетчик изменений
• При каждом изменении счетчик версий инкрементируется: (A, 1) -> (B, 2) -> (A, 3)
• В x86-64: 128-битная инструкция LOCK CMPXCHG16B

Спинлоки (Spinlocks)

• Активное ожидание в цикле:

while (__atomic_test_and_set(&lock, 
       __ATOMIC_ACQUIRE)) {
    _mm_pause(); // Снижает нагрузку ЦПУ
}

• Сверхмалая задержка (~10–20 нс)
• Сжигает 100% ядра ЦПУ при долгом локе

Блокировки SRWLock (WinAPI)

• Занимает размер указателя (8 байт)
• Читатели (AcquireSRWLockShared) и писатели (AcquireSRWLockExclusive)
• Без состязания: захват за 1 атомарную инструкцию
• Без создания дескрипторов ядра

CRITICAL_SECTION в Windows

• Совмещает фазу спина и сон ядра:

1. Фаза спина (Spin Phase): крутится в Ring 3 до $N$ циклов (SetCriticalSectionSpinCount)
2. Фаза ядра (Sleep Phase): при неудаче усыпляет поток в очереди ядра

• Оптимальный баланс между задержкой и энергопотреблением

Механизм futex в Linux

• Fast Userspace Mutex: целое число int
• Захват в Ring 3 через atomic_cmpxchg (0 системных вызовов)
• Системный вызов sys_futex(FUTEX_WAIT) инициируется только при реальном конфликте

Назначение и функции

• Ожидание выполнения логического предиката над разделяемыми данными
• В Windows: CONDITION_VARIABLE, SleepConditionVariableSRW, WakeConditionVariable
• В Linux / POSIX: pthread_cond_t, pthread_cond_wait, pthread_cond_signal

Канонический шаблон ожидания

AcquireSRWLockExclusive(&lock);

// Цикл while обязателен!
while (!predicate_is_true()) {
    // Атомарно освобождает lock и спит
    SleepConditionVariableSRW(&cv, 
        &lock, INFINITE, 0);
}

// Обработка данных...
ReleaseSRWLockExclusive(&lock);

• Защита от ложных пробуждений (Spurious Wakeups): проверка условия строго в while

Код производителя (Produce)

// 1. Ждем свободного слота
WaitForSingleObject(b->sem_empty, INFINITE);

// 2. Критическая секция буфера
EnterCriticalSection(&b->cs);
b->data[b->tail] = item;
b->tail = (b->tail + 1) % BUF_SIZE;
LeaveCriticalSection(&b->cs);

// 3. Сигнализируем заполнение
ReleaseSemaphore(b->sem_full, 1, NULL);

Код потребителя (Consume)

// 1. Ждем заполненного слота
WaitForSingleObject(b->sem_full, INFINITE);

// 2. Критическая секция буфера
EnterCriticalSection(&b->cs);
int item = b->data[b->head];
b->head = (b->head + 1) % BUF_SIZE;
LeaveCriticalSection(&b->cs);

// 3. Сигнализируем освобождение
ReleaseSemaphore(b->sem_empty, 1, NULL);

Понятие Deadlock

• Аварийная остановка системы, при которой потоки бесконечно ожидают ресурсы друг друга
• Потоки не потребляют такты ЦПУ, но приложение полностью зависает

4 необходимых условия Коффмана (1971)

1. Взаимное исключение: ресурсы неделимы и монопольны
2. Удержание и ожидание: поток удерживает ресурс и запрашивает новый
3. Невытесняемость: ресурс нельзя отобрать принудительно
4. Круговое ожидание: замкнутая цепочка ожидания $\{T_1 \to T_2 \to ... \to T_1\}$

Иерархическое упорядочение (Lock Ordering)

• Все ресурсы нумеруются: $R_1, R_2, ..., R_n$
• Потоки обязаны захватывать ресурсы строго по возрастанию номеров
• Разрушает 4-е условие Коффмана (круговой цикл математически невозможен)

Дополнительные методы

• Неблокирующий захват (try_lock): при неудаче освобождает ранее захваченные ресурсы и делает откат
• Алгоритм банкира Дейкстры: планировщик выделяет ресурс, только если состояние системы безопасно
• Сторожевой таймер (Watchdog): обнаружение циклов и принудительный откат одного из потоков

Постановка проблемы

• 5 философов сидят за круглым столом, между ними 5 вилок
• Для еды каждому требуются две вилки (левая и правая)
• Дедлок: если все одновременно возьмут левую вилку, ни один не получит правую — гибель от голода

Инженерные решения

1. Асимметричный порядок (Lock Ordering):
   • Четные философы берут сначала левую вилку, затем правую
   • Нечетные философы берут сначала правую, затем левую
   • Разрывает замкнутый цикл ожидания
2. Ограничение доступа (Семафор):
   • За стол допускаются не более 4 философов одновременно

Аппаратура и атомики

• Несогласованный доступ к разделяемой памяти ведет к Race Condition
• Out-of-Order конвейер процессора требует барьеров памяти (MFENCE)
• LOCK CMPXCHG (CAS) выполняет атомарный обмен на уровне кэшей MESI
• Проблема ABA решается версионированием указателей (Tagged Pointers)

Примитивы и дедлоки

• SRWLock и спинлоки минимизируют накладные расходы в Ring 3
• CRITICAL_SECTION и futex используют гибридную схему (spin + sleep)
• «Производители–потребители» требуют семафоров и условия порядка
• Дедлок предотвращается иерархическим упорядочением захвата (Lock Ordering)