# Синхронизация в параллельных системах: от дедлоков до Lock-Free структур

Источник: https://www.youtube.com/watch?v=GA1ObImqaMo
Канал: Stanford Online
Опубликовано: 24.09.2024

---

В современной разработке программного обеспечения параллелизм перестал быть экзотикой, превратившись в обязательное требование для производительных систем. Однако простое использование блокировок (locks) часто становится «бутылочным горлышком», ограничивающим масштабируемость. В тринадцатой лекции курса Stanford CS149 рассматриваются фундаментальные проблемы синхронизации, способы реализации эффективных примитивов на уровне железа и переход к парадигме программирования без блокировок (lock-free).

## 🛑 Три всадника проблем синхронизации: Deadlock, Livelock и Starvation
[[JUMP:0:32]]

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

**1. Deadlock (Взаимная блокировка)** [1:13]
Это ситуация, когда группа потоков ожидает ресурсы, удерживаемые друг другом, и никто не может сдвинуться с места. Для возникновения дедлока должны одновременно соблюдаться четыре условия:

*   **Взаимное исключение (Mutual Exclusion):** ресурс может удерживаться только одним участником.
*   **Удержание и ожидание (Hold and Wait):** участник удерживает один ресурс и ждет получения другого.
*   **Отсутствие вытеснения (No Preemption):** ресурс нельзя принудительно отобрать у владельца.
*   **Циклическое ожидание (Circular Wait):** существует замкнутая цепь потоков, где каждый ждет ресурс, удерживаемый следующим [6:18].

**2. Livelock (Живая блокировка)** [7:03]
Потоки постоянно меняют свое состояние и выполняют какие-то действия, но полезного прогресса нет. Классический пример из жизни — ситуация в дверном проеме, когда два человека пытаются уступить дорогу, одновременно делая шаг в одну и ту же сторону, затем в другую, и так до бесконечности [8:11]. В логах системы это выглядит как активная работа, но транзакции не завершаются.

**3. Starvation (Голодание)** [8:25]
Система в целом работает и выполняет полезные задачи, но конкретный поток или тип задач никогда не получает доступа к ресурсу. Пример: машина, пытающаяся выехать со второстепенной дороги на оживленное шоссе (Highway 1). Если поток машин на шоссе бесконечен и правила требуют уступать, «желтая машина» будет ждать вечно, хотя движение на шоссе идет полным ходом [9:22].

## 🧠 Когерентность кэша и цена блокировки
[[JUMP:9:47]]

Реализация блокировок неразрывно связана с тем, как работают кэши процессоров. Основная задача протоколов когерентности кэша (например, MSI — Modified, Shared, Invalid) — гарантировать, что все ядра видят актуальные данные [10:28].

Когда один процессор записывает значение в память (например, меняет флаг блокировки с 0 на 1), протокол обязан аннулировать (invalidate) все копии этой строки кэша в других ядрах [14:11]. Это создает серьезную проблему для производительности:

*   Если несколько потоков одновременно пытаются захватить блокировку, используя простую инструкцию `test-and-set`, строка кэша с переменной блокировки начинает «прыгать» между ядрами [23:50].
*   Каждая попытка записи вызывает инвалидацию в других кэшах.
*   Даже если поток уже удерживает блокировку и просто работает внутри критической секции, другие «вращающиеся» в цикле потоки могут забивать шину данных постоянными запросами на чтение и запись [27:32].

С увеличением количества ядер стоимость одной операции захвата/освобождения блокировки растет экспоненциально из-за перегрузки межпроцессорного соединения [27:06].

## 🛠 Реализация эффективных примитивов: от TAS до Ticket Locks
[[JUMP:18:07]]

Для минимизации трафика когерентности инженеры используют различные программные стратегии.

### Test-and-Set (TAS)
Самый простой вариант. Поток в цикле вызывает атомарную инструкцию, которая читает значение и устанавливает его в 1.

*   **Минус:** Огромное количество записей на шине данных [21:50].

### Test-and-Test-and-Set (TTAS)
Более умный подход. Поток сначала просто читает значение (в обычном цикле), и только если видит, что блокировка свободна (0), пытается выполнить атомарную запись `test-and-set` [30:17].

*   **Плюс:** Пока блокировка занята, потоки читают данные из своего локального кэша в состоянии Shared (S), не генерируя трафик на шине [31:23]. Трафик возникает только в момент освобождения блокировки, когда все сразу пытаются её захватить («feeding frenzy» — кормовое безумие) [32:35].

### Ticket Lock (Билетная блокировка)
Аналогия с очередью в мясной лавке или отделе деликатесов: вы берете номерок, а продавец объявляет текущий номер обслуживания [33:29].

*   Используются две переменные: `next_ticket` и `now_serving`.
*   Поток получает уникальный номер через атомарный инкремент и ждет, пока `now_serving` станет равен его номеру [34:39].
*   **Плюс:** Это гарантирует честность (FIFO) — потоки получают доступ в порядке очереди, что исключает голодание [35:45].

## 🔄 Атомарные операции и Compare-and-Swap (CAS)
[[JUMP:36:28]]

Современные процессоры предоставляют богатый набор атомарных инструкций. Одной из самых важных является `Compare-and-Swap` (CAS) [37:10]. Логика CAS: «Если значение по адресу равно X, замени его на Y, иначе ничего не делай».

На базе CAS можно реализовать любой сложный атомарный примитив, например, `atomic_min` [38:47]:

1. Считать текущее значение из памяти.
2. Вычислить локально новое минимальное значение.
3. Вызвать CAS. Если за время вычислений значение в памяти изменилось, CAS вернет ошибку.
4. В случае неудачи — повторить цикл заново [41:37].

По мнению лектора, понимание CAS критически важно, так как это фундамент для создания всех lock-free структур данных [47:41].

## ⛓ Тонкая синхронизация в структурах данных
[[JUMP:52:41]]

Простое «грубое» решение (одна блокировка на весь связный список) убивает параллелизм, превращая выполнение программы в последовательное [1:00:05]. Альтернатива — тонкая синхронизация (fine-grained synchronization).

### Метод Hand-over-hand Locking
Аналогия — прохождение рукохода на полосе препятствий Ninja Warrior: вы не отпускаете одну перекладину, пока не схватитесь за следующую [1:04:29].

*   Чтобы безопасно перемещаться по списку, поток захватывает блокировку на текущем узле (current) и на предыдущем (previous) [1:05:22].
*   Перед переходом к следующему узлу поток захватывает `next`, и только потом отпускает `previous`.
*   Это гарантирует, что никто не сможет удалить или вставить элемент прямо перед вами или за вами, пока вы проходите этот участок [1:07:30].

Однако у такого подхода есть цена: вместо одного захвата блокировки на всю операцию вы совершаете десятки захватов при обходе списка, что может замедлить работу одного потока в несколько раз [1:10:13].

## 🚀 Введение в Lock-Free программирование
[[JUMP:1:11:10]]

Lock-free алгоритмы позволяют потокам работать с данными без использования мьютексов, что исключает риск блокировки всей системы, если один поток будет прерван ОС [1:13:16].

**Ключевая идея:**
Вместо того чтобы запрещать другим вход (блокировка), мы выполняем работу спекулятивно. В самый последний момент, перед записью результата, мы проверяем с помощью CAS, не изменился ли мир за это время. Если изменился — мы просто отбрасываем результат и пробуем снова [1:11:51].

Такой подход особенно эффективен в высоконагруженных системах (базы данных, веб-серверы), где контекстное переключение потока, удерживающего блокировку, может привести к простою сотен других потоков [1:15:08]. Большинство современных конкурентных коллекций в Java и C++ реализованы именно на базе lock-free алгоритмов [1:12:19].

---