Синхронизация потоков

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

История

Проблемы синхронизации стали актуальны с развитием многозадачных операционных систем в 1960-х годах. Одним из первых формальных подходов к описанию задач синхронизации стала задача об обедающих философах, сформулированная Эдсгером Дейкстрой в 1965 году. Дейкстра также ввёл понятие семафора — одного из первых примитивов синхронизации, реализованного в операционной системе THE.

В 1970-х годах, с распространением многопроцессорных систем, возникла потребность в более эффективных механизмах. В 1974 году появились мониторы — высокоуровневые конструкции, предложенные Чарльзом Хоаром и Пером Бринчем Хансеном. В 1980-х годах, с развитием Unix-подобных систем, широкое распространение получили мьютексы (mutex) и условные переменные, реализованные в стандарте POSIX Threads (Pthreads).

Современные языки программирования, такие как Java, C# и Go, включают встроенные средства синхронизации, основанные на мониторах (synchronized в Java) или каналах (channels в Go), что упрощает разработку многопоточных приложений.

Основные проблемы, решаемые синхронизацией

Состояние гонки (Race condition)

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

Взаимная блокировка (Deadlock)

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

Голодание (Starvation)

Голодание — ситуация, при которой один или несколько потоков не получают доступа к ресурсу в течение длительного времени, в то время как другие потоки активно его используют. Это может происходить из-за неправильной политики планирования или приоритетов.

Инверсия приоритетов (Priority inversion)

Инверсия приоритетов — ситуация, при которой высокоприоритетный поток не может получить доступ к ресурсу, удерживаемому низкоприоритетным потоком, который, в свою очередь, вытесняется среднеприоритетными потоками. Эта проблема была одной из причин сбоя марсохода Mars Pathfinder в 1997 году.

Примитивы синхронизации

Атомарные операции

Атомарные операции — это операции, которые выполняются как единое неделимое действие. В современных процессорах поддерживаются атомарные инструкции, такие как test-and-set, compare-and-swap (CAS), load-linked/store-conditional (LL/SC). На их основе строятся более сложные механизмы синхронизации.

Мьютекс (Mutex)

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

Семафор

Семафор — целочисленная переменная, поддерживающая две атомарные операции: P (proberen — попробовать, уменьшить) и V (verhogen — увеличить). Семафор с начальным значением 1 работает как мьютекс. Семафоры могут быть счётными (значение больше 1) и двоичными (0 или 1). В отличие от мьютекса, семафор не привязан к конкретному потоку и может быть освобождён другим потоком, что делает его более гибким, но и более подверженным ошибкам.

Условная переменная (Condition variable)

Условная переменная — примитив, позволяющий потоку ожидать наступления определённого условия. Она всегда используется вместе с мьютексом. Поток захватывает мьютекс, проверяет условие, и если оно не выполнено, вызывает wait, который атомарно освобождает мьютекс и блокирует поток. Когда другой поток изменяет состояние и вызывает signal (разбудить один ожидающий поток) или broadcast (разбудить все ожидающие потоки), ожидающий поток просыпается, вновь захватывает мьютекс и проверяет условие.

Монитор (Monitor)

Монитор — высокоуровневая конструкция, объединяющая данные, процедуры и механизмы синхронизации. В мониторе только один поток может выполнять любой из его методов в данный момент времени. Внутри монитора используются условные переменные для организации ожидания. Мониторы реализованы в языках Java (ключевое слово synchronized), C# (lock) и Pascal (Concurrent Pascal).

Барьер (Barrier)

Барьер — примитив синхронизации, используемый в параллельных вычислениях. Он заставляет потоки ожидать, пока все участники не достигнут определённой точки выполнения. После этого все потоки продолжают работу одновременно. Барьеры широко применяются в MPI-программах и в OpenMP-директивах.

Спинлок (Spinlock)

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

Read-Write Lock (RW-lock)

Read-Write Lock — примитив, позволяющий множеству потоков одновременно читать данные, но только одному потоку — записывать. Это повышает производительность в сценариях, где операции чтения преобладают над записью. В реализации RW-lock обычно используется два мьютекса и счётчик активных читателей.

Алгоритмы и подходы

Алгоритм Петерсона

Алгоритм Петерсона — классический программный алгоритм взаимного исключения для двух потоков, не требующий аппаратной поддержки атомарных операций, кроме атомарности чтения и записи. Он использует два флага и переменную turn. Несмотря на свою простоту, алгоритм доказывает, что взаимное исключение возможно без специальных инструкций процессора.

Алгоритм Деккера

Алгоритм Деккера — первый известный алгоритм взаимного исключения для двух потоков, разработанный голландским математиком Т. Деккером. Он также использует флаги и переменную turn, но имеет более сложную логику, чем алгоритм Петерсона.

Алгоритм хлебной булочки (Bakery algorithm)

Алгоритм хлебной булочки, предложенный Лесли Лампортом в 1974 году, обобщает алгоритм Петерсона на произвольное количество потоков. Каждый поток получает номер (как в пекарне), и поток с наименьшим номером получает доступ к критической секции. Алгоритм гарантирует взаимное исключение, отсутствие голодания и справедливость.

Lock-free и wait-free алгоритмы

Lock-free алгоритмы гарантируют, что хотя бы один поток в системе прогрессирует (не блокируется) за конечное число шагов. Wait-free алгоритмы гарантируют, что каждый поток прогрессирует за конечное число шагов, независимо от других потоков. Эти алгоритмы используют атомарные операции CAS или LL/SC и применяются в высокопроизводительных системах, где блокировки недопустимы (например, в ядре операционной системы Linux).

Применение

Операционные системы

В ядрах операционных систем синхронизация используется для управления доступом к глобальным структурам данных (списки процессов, файловые системы, сетевые стеки). В Linux используются спинлоки, мьютексы, семафоры, rw-lock и RCU (Read-Copy-Update) — специализированный механизм, оптимизированный для сценариев с частым чтением и редкой записью.

Базы данных

В системах управления базами данных (СУБД) синхронизация реализуется через блокировки (locks) на уровне строк, страниц или таблиц, а также через многоверсионность (MVCC), которая позволяет читателям не блокироваться писателями. В PostgreSQL, например, используется комбинация блокировок и MVCC для обеспечения изоляции транзакций.

Веб-серверы

Веб-серверы, такие как Nginx и Apache, используют синхронизацию для управления пулом потоков или процессов, обработки запросов и доступа к общим кэшам. В Nginx, работающем в асинхронном режиме, синхронизация минимальна, что обеспечивает высокую производительность.

Параллельные вычисления

В научных расчётах и обработке больших данных синхронизация необходима для координации работы тысяч потоков на графических процессорах (GPU) или кластерах. В CUDA и OpenCL используются барьеры и атомарные операции, специфичные для архитектуры GPU.

Критика и альтернативы

Традиционные подходы к синхронизации, основанные на блокировках, подвергаются критике за сложность отладки и высокую вероятность ошибок (deadlock, livelock, race condition). Альтернативными подходами являются:

• Акторная модель (Erlang, Akka), где потоки взаимодействуют через асинхронные сообщения, не разделяя состояние.
• Каналы (Go, CSP), где синхронизация осуществляется через передачу данных по каналам, а не через разделяемую память.
• Функциональное программирование (Haskell, Clojure), где неизменяемые данные (immutable data) исключают состояние гонки по определению.
• Транзакционная память (STM), позволяющая выполнять операции над разделяемыми данными как атомарные транзакции, поддерживаемая в некоторых языках (Clojure, Haskell).

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

• В 1997 году на марсоходе Mars Pathfinder возникла проблема инверсии приоритетов, которая была исправлена удалённо после обнаружения на Земле. Это привело к широкому внедрению протокола наследования приоритетов в реальном времени.
• Алгоритм хлебной булочки Лесли Лампорта используется в некоторых системах для доказательства корректности распределённых алгоритмов.
• В ядре Linux используется более 50 различных механизмов синхронизации, включая специализированные (seqlock, RCU, percpu-rwsem).
• Самая известная ошибка, связанная с синхронизацией, — это баг в программном обеспечении Therac-25 (1985-1987), который привёл к смерти нескольких пациентов из-за состояния гонки в управлении радиационной терапией.

Источники

• Э. Таненбаум, Х. Бос. «Современные операционные системы». 4-е издание, 2015.
• М. Бен-Ари. «Принципы параллельного программирования». 2009.
• Г. Эндрюс. «Основы многопоточного, параллельного и распределенного программирования». 2003.
• Д. Боуэн. «Синхронизация в многопроцессорных системах». 2018.
• Стандарт IEEE 1003.1-2017 (POSIX.1-2017).