В современной разработке программного обеспечения параллелизм перестал быть экзотикой, превратившись в обязательное требование для производительных систем. Однако простое использование блокировок (locks) часто становится «бутылочным горлышком», ограничивающим масштабируемость. В тринадцатой лекции курса Stanford CS149 рассматриваются фундаментальные проблемы синхронизации, способы реализации эффективных примитивов на уровне железа и переход к парадигме программирования без блокировок (lock-free).
🛑 Три всадника проблем синхронизации: Deadlock, Livelock и Starvation 0:32
Прежде чем переходить к реализации механизмов защиты данных, необходимо разобраться в трех классических состояниях, когда программа перестает выполнять полезную работу. Профессор Стэнфорда (в данном курсе это традиционно Кейвон Фатахалиан) выделяет следующие термины:
1. Deadlock (Взаимная блокировка) Это ситуация, когда группа потоков ожидает ресурсы, удерживаемые друг другом, и никто не может сдвинуться с места. Для возникновения дедлока должны одновременно соблюдаться четыре условия:
- Взаимное исключение (Mutual Exclusion): ресурс может удерживаться только одним участником.
- Удержание и ожидание (Hold and Wait): участник удерживает один ресурс и ждет получения другого.
- Отсутствие вытеснения (No Preemption): ресурс нельзя принудительно отобрать у владельца.
- Циклическое ожидание (Circular Wait): существует замкнутая цепь потоков, где каждый ждет ресурс, удерживаемый следующим .
2. Livelock (Живая блокировка) Потоки постоянно меняют свое состояние и выполняют какие-то действия, но полезного прогресса нет. Классический пример из жизни — ситуация в дверном проеме, когда два человека пытаются уступить дорогу, одновременно делая шаг в одну и ту же сторону, затем в другую, и так до бесконечности . В логах системы это выглядит как активная работа, но транзакции не завершаются.
3. Starvation (Голодание) Система в целом работает и выполняет полезные задачи, но конкретный поток или тип задач никогда не получает доступа к ресурсу. Пример: машина, пытающаяся выехать со второстепенной дороги на оживленное шоссе (Highway 1). Если поток машин на шоссе бесконечен и правила требуют уступать, «желтая машина» будет ждать вечно, хотя движение на шоссе идет полным ходом .
🧠 Когерентность кэша и цена блокировки 9:47
Реализация блокировок неразрывно связана с тем, как работают кэши процессоров. Основная задача протоколов когерентности кэша (например, MSI — Modified, Shared, Invalid) — гарантировать, что все ядра видят актуальные данные .
Когда один процессор записывает значение в память (например, меняет флаг блокировки с 0 на 1), протокол обязан аннулировать (invalidate) все копии этой строки кэша в других ядрах . Это создает серьезную проблему для производительности:
- Если несколько потоков одновременно пытаются захватить блокировку, используя простую инструкцию
test-and-set, строка кэша с переменной блокировки начинает «прыгать» между ядрами . - Каждая попытка записи вызывает инвалидацию в других кэшах.
- Даже если поток уже удерживает блокировку и просто работает внутри критической секции, другие «вращающиеся» в цикле потоки могут забивать шину данных постоянными запросами на чтение и запись .
С увеличением количества ядер стоимость одной операции захвата/освобождения блокировки растет экспоненциально из-за перегрузки межпроцессорного соединения .
🛠 Реализация эффективных примитивов: от TAS до Ticket Locks 18:07
Для минимизации трафика когерентности инженеры используют различные программные стратегии.
Test-and-Set (TAS)
Самый простой вариант. Поток в цикле вызывает атомарную инструкцию, которая читает значение и устанавливает его в 1.
Test-and-Test-and-Set (TTAS)
Более умный подход. Поток сначала просто читает значение (в обычном цикле), и только если видит, что блокировка свободна (0), пытается выполнить атомарную запись test-and-set .
- Плюс: Пока блокировка занята, потоки читают данные из своего локального кэша в состоянии Shared (S), не генерируя трафик на шине . Трафик возникает только в момент освобождения блокировки, когда все сразу пытаются её захватить («feeding frenzy» — кормовое безумие) .
Ticket Lock (Билетная блокировка)
Аналогия с очередью в мясной лавке или отделе деликатесов: вы берете номерок, а продавец объявляет текущий номер обслуживания .
- Используются две переменные:
next_ticketиnow_serving. - Поток получает уникальный номер через атомарный инкремент и ждет, пока
now_servingстанет равен его номеру . - Плюс: Это гарантирует честность (FIFO) — потоки получают доступ в порядке очереди, что исключает голодание .
🔄 Атомарные операции и Compare-and-Swap (CAS) 36:28
Современные процессоры предоставляют богатый набор атомарных инструкций. Одной из самых важных является Compare-and-Swap (CAS) . Логика CAS: «Если значение по адресу равно X, замени его на Y, иначе ничего не делай».
На базе CAS можно реализовать любой сложный атомарный примитив, например, atomic_min :
- Считать текущее значение из памяти.
- Вычислить локально новое минимальное значение.
- Вызвать CAS. Если за время вычислений значение в памяти изменилось, CAS вернет ошибку.
- В случае неудачи — повторить цикл заново .
По мнению лектора, понимание CAS критически важно, так как это фундамент для создания всех lock-free структур данных .
⛓ Тонкая синхронизация в структурах данных 52:41
Простое «грубое» решение (одна блокировка на весь связный список) убивает параллелизм, превращая выполнение программы в последовательное . Альтернатива — тонкая синхронизация (fine-grained synchronization).
Метод Hand-over-hand Locking
Аналогия — прохождение рукохода на полосе препятствий Ninja Warrior: вы не отпускаете одну перекладину, пока не схватитесь за следующую .
- Чтобы безопасно перемещаться по списку, поток захватывает блокировку на текущем узле (current) и на предыдущем (previous) .
- Перед переходом к следующему узлу поток захватывает
next, и только потом отпускаетprevious. - Это гарантирует, что никто не сможет удалить или вставить элемент прямо перед вами или за вами, пока вы проходите этот участок .
Однако у такого подхода есть цена: вместо одного захвата блокировки на всю операцию вы совершаете десятки захватов при обходе списка, что может замедлить работу одного потока в несколько раз .
🚀 Введение в Lock-Free программирование 1:11:10
Lock-free алгоритмы позволяют потокам работать с данными без использования мьютексов, что исключает риск блокировки всей системы, если один поток будет прерван ОС .
Ключевая идея: Вместо того чтобы запрещать другим вход (блокировка), мы выполняем работу спекулятивно. В самый последний момент, перед записью результата, мы проверяем с помощью CAS, не изменился ли мир за это время. Если изменился — мы просто отбрасываем результат и пробуем снова .
Такой подход особенно эффективен в высоконагруженных системах (базы данных, веб-серверы), где контекстное переключение потока, удерживающего блокировку, может привести к простою сотен других потоков . Большинство современных конкурентных коллекций в Java и C++ реализованы именно на базе lock-free алгоритмов .
