June 13, 2026
Организация одновременного выполнения множества задач — одна из фундаментальных и запутанных областей современного Computer Science. «Параллелизм», «конкурентность», «асинхронность», «многопоточность», «многозадачность» — все эти слова слышал каждый разработчик. Зачастую они используются как взаимозаменяемые, что сильно затрудняет понимание концептов. Как результат, «плавание» в знаниях этой области, к сожалению, не редкость.
С этой же проблемой столкнулся и я. Вся терминология и теоретический аппарат выглядел для меня как большой запутанный клубок, который неясно откуда начинать распутывать. Поэтому я решил провести исследование этой области. Эта статья — журнал этого исследования, структурированный из него вывод.
Перед началом исследования я поставил для себя два требования, которые посчитал необходимыми для наиболее полного понимания темы:
Исследование базируется на статьях в блогах, докладах, научных работах, интервью — всём, что доступно в интернете. Поиск и подбор материалов осуществлялся с помощью LLM (Gemini Deep Research).
Статья, следовательно, построена так: сначала разбираются ключевые для понимания термины, затем в хронологическом порядке исследуются различные подходы.
Для начала, стоит разобрать эти основные термины:
Стоит заметить, что теоретический аппарат довольно запутан с точки зрения толкования основных терминов и концепций. Пересечения нескольких областей вносят ещё бо́льшую двусмысленность в них. Эта статья про разработку. Наша задача состоит в том, чтобы выделить наиболее релевантные определения именно для этой области. Поэтому где-то будут рассматриваться и противоречащие утверждения.
Начнём с простого. Конкурентность — не параллелизм. И не наоборот. Замечательное сравнение приводит Роб Пайк:
Конкурентность — это работа с несколькими вещами одновременно (англ. dealing with many things at once), а параллелизм — выполнение нескольких вещей одновременно (англ. doing many things at once).
— Роб Пайк, «Concurrency Is Not Parallelism», 2012[1]
Конкурентность — способ организации программы, параллелизм — нюанс её исполнения. Конкурентно написанная программа может выполняться не параллельно, а параллельное выполнение не всегда означает наличие конкурентной программы. Конкурентная программа порождает и взаимодействует с некоторым количеством конкурентных событий.
Определение
—->:
- если события
aиbпринадлежат одному процессу, и событиеbпроисходит после событияa, тоa --> b;- если
a— отправка сообщения одним процессом, аb— его получение другим процессом, тоa --> b;- если
a --> bиb --> c, тоa --> c. Два событияaиbназываются конкурентными, еслиa -/-> bиb -/-> a. Другой взгляд на это определение:a --> bозначает, чтоaможет повлиять наb.— Лесли Лемпорт, «Time, Clocks, and the Ordering of Events in a Distributed System», 1978[2]
Проще говоря, два события считаются конкурентными, если они не могут повлиять друг на друга. Взгляните на этот пример. На этой иллюстрации события p1 --> q2, q1 --> p2, p5 --> q4 связаны. На практике это могут быть, например, блокировки при доступе к общим ресурсам или тот же самый обмен сообщениями через брокер.
Видно, что p3, p4 и q3 могут занимать какое угодно положение относительно друг друга. Разве что p3 будет происходить до p4. Эти события мы и назовём конкурентными. Может возникнуть соблазн назвать их параллельными, но это будет ошибкой, так как мы говорим об общем случае. Эти процессы действительно можно запустить параллельно, но взгляните на другой пример:
Здесь изначально конкурентная программа вынуждена выполняться на одном ядре процессора. Заметьте, что теперь параллелизм точно отсутствует, но конкурентность осталась — существуют несколько способов расположить события так, чтобы они удовлетворяли ограничениям (на анимации показаны не все из них). Таким образом, конкурентность возможна без параллелизма.
В то же время и параллелизм возможен без конкурентности. Но для этого нужно нырнуть глубоко внутрь — на самые нижние слои абстракции — процессорные инструкции. Типичный пример параллелизма без конкурентности: SIMD.
SIMD (single instruction — multiple data) или векторные инструкции позволяют производить одну и ту же операцию одновременно на нескольких данных. Например, если машинное слово — 64 бита, то обычная инструкция ADD сможет сложить максимум два 64-битных числа. Векторная инструкция сможет сложить 2, 4 и более, в зависимости от размера вектора (256 бит, 512 бит и т.д.). Тем не менее, порядок событий в такой программе вполне себе может быть единственным, и независимые события могут отсутствовать.
То есть, справедливо будет составить такую таблицу простых примеров каждой комбинации:
| Нет параллельности | Есть параллельность | |
|---|---|---|
| Нет конкурентности | Классическая последовательная программа | То же самое, но с, например, векторными оптимизациями |
| Есть конкурентность | Типичный ПК 90-х: на одном ядре работает много программ одновременно | Веб-сервер запускает несколько воркеров на многоядерном процессоре |
И соответствующие определения:
Параллелизм — способность выполнить несколько задач в одну единицу времени на физическом уровне.
Конкурентность — свойство программы, в которой существуют независимые друг от друга события (ни одно из них не обязано предшествовать другому), что допускает множество различных порядков их исполнения.
Ситуация с определением асинхронности сложилась более сложно. Пожалуй, из всех терминов, асинхронность — наиболее подвижный. Во-первых, определение асинхронности может меняться в зависимости от времени публикации. Во-вторых, определение асинхронности зависит от контекста: пытаемся ли мы описать в целом концепцию или рассматриваем какую-то технологию/язык в частности.
Термин «синхронный» относится к среде связи, где каждый участник получает (и если нужно обрабатывает и/или отвечает) сообщения немедленно (или настолько быстро, на сколько это возможно). Термин асинхронный относится к двум или более объектам или событиям, которые не существуют или не происходят одновременно, то есть они не являются синхронными.
— Глоссарий MDN[3]
Асинхронное программирование — концепция программирования, которая заключается в том, что результат выполнения функции доступен не сразу, а через некоторое время в виде некоторого асинхронного (нарушающего обычный порядок выполнения) вызова.
— «Википедия»[6]
Постараемся рассмотреть определения вблизи. Определение из MDN может показаться прямо противоположным действительности: «термин асинхронный относится к двум или более объектам или событиям, которые не существуют или не происходят одновременно». Это стоит понимать скорее как: «события, которые не существуют в одной временной цепочке», то есть, разорваны во времени.
В условиях наличия асинхронности, при, например, запросе по сети, мы не заняты ожиданием ответа. При этом мы не «бросаем» этот запрос — когда он вернётся с ответом, мы выполним какие-то действия. Всё происходящее в задаче запроса от момента её создания до момента её возврата с ответом структурно отделено от задачи, которая её породила. Именно это и имеется в виду под «не существуют одновременно».
Таким образом, можно сказать, что:
Асинхронность — это особенность структуры конкретной программы: начало и конец отделены, а вызывающая сторона не блокируется в ожидании завершения задачи.
Асинхронность — ни в коем случае не то же самое, что и конкурентность. Для этого продемонстрируем такой пример. Запустим два запроса в двух потоках — получим конкурентность без асинхронности:
Если мы напишем несколько запросов в асинхронном стиле, но искусственно введём ограничение: заставим каждый последующий запрос выполняться строго после конца предыдущего, то мы получим асинхронно написанную программу, но выполняющуюся не конкурентно, потому как у нас отсутствуют независимые события:
Таким образом, можем сказать, что определения параллелизма, конкурентности и асинхронности — ортогональны и образуют 8 разных возможных комбинаций.
| Не параллельно | Параллельно | |
|---|---|---|
| Не конкурентно, Не асинхронно |
Классическая последовательная программа: запрос → ожидание → ответ. | То же самое, но, например, есть SIMD-ускорение. В работе одновременно всё ещё только одна задача. |
| Не конкурентно, Асинхронно |
Программа асинхронна, но искусственно выстроена так, что каждый следующий запрос идёт только после очередного ответа (цепочка из await). | То же самое, но, например, есть SIMD-ускорение. |
| Конкурентно, Не асинхронно |
Создаём на каждый запрос по потоку, но на одном ядре. | Создаём на каждый запрос по потоку, но на нескольких ядрах, каждый поток выполняет синхронный блокирующий запрос. |
| Конкурентно, Асинхронно |
Есть только один поток, сразу после запроса не ждём ответа, а делаем следующий: классический event loop. Ответы будут доставлены позже. | Запускаем несколько параллельных event loop в нескольких потоках на нескольких ядрах. |
Можно заметить, что асинхронность может являться инструментом реализации конкурентности в отсутствие параллельности.
Мы можем встретить и такие определения асинхронности:
Асинхронность — способность задач привести к корректному результату при выполнении вне зависимости от порядка.
— Лорис Кро, Zig Software Foundation VP, «Asynchrony is not Concurrency», 2025[4]
Агент P может бездействовать неограниченно долго, но в любой момент времени может совершить и любое другое действие. Мы можем думать о таких агентах и их произведениях как об асинхронных.
— Робин Милнер, «Calculi for Synchrony and Asynchrony», 1983[5]
Очевидно, что они не соответствуют данному ранее определению. Лорис Кро в своей статье называет асинхронностью то, что мы в этой статье понимаем под конкурентностью со ссылкой на Лемпорта. Робин Милнер в своей работе определяет асинхронность через некоторое время ожидания задачи, однако, далее развивая его мысль, мы тоже будем дальше уходить от нашего определения асинхронности. Почему так?
Как уже было сказано ранее, асинхронность — наиболее подвижный термин и тут мы видим два наглядных примера. Работа Милнера имеет свои корни в теории систем и конкретно с написанием программ не имеет практически ничего общего. Статья Кро специфична для языка программирования Zig и именно в контексте этого языка Кро переопределяет термины, чтобы они лучше соответствовали действительности.
Как видно, определения в общем случае, определения из смежных областей и определения применительно к конкретным технологиям могут сильно отличаться. В этой статье мы изначально рассматриваем наиболее общие определения, поэтому будем придерживаться уже данных. Не стоит думать, что два рассмотренных выше им противоречат, они просто находятся в разных плоскостях.
Другой важной вещью, о которой стоит помнить, работая с конкурентностью, является недетерминированность. Если несколько конкурентных процессов (задач/исполнителей/подставить своё) взаимодействуют хотя бы с одним общим ресурсом, то без дополнительных условий мы не можем гарантировать какой-то конкретный результат их выполнения.
Классический пример: инкремент счётчика несколькими потоками (обычно они запускаются параллельно). Псевдокод:
c = 0
def loop():
100 times:
c = c + 1
th1 = thread(loop)
th2 = thread(loop)
start(th1)
start(th2)
join(th1)
join(th2)
print(c)
Результаты запуска такой программы будут различаться. Поток состоит из повторяющейся последовательности действий:
Так как они пока что независимы, мы не знаем в каком порядке могут выполниться события относительно друг друга (определение конкурентности), то есть возможен любой порядок. Можно смоделировать такую ситуацию ( и — локальные копии значения C в памяти каждого из потоков соответственно):
| Поток 1 | Поток 2 | C | ||
|---|---|---|---|---|
| Получить С | 0 | 0 | ||
| 0 | Получить С | 0 | 0 | |
| Прибавить 1 | 1 | 0 | 0 | |
| 1 | Прибавить 1 | 1 | 0 | |
| 1 | Сохранить C | 1 | 1 | |
| Сохранить C | 1 | 1 | 1 | |
| Конец | 1 | Конец | 1 | 1 |
Видно, что определенный порядок действий приводит к результату C = 1. Однако другой порядок может привести к другому результату. Например, если один из потоков успеет сохранить значение C до того, как другой его прочитает:
| Поток 1 | Поток 2 | C | ||
|---|---|---|---|---|
| Получить С | 0 | |||
| Прибавить 1 | 1 | |||
| Сохранить C | 1 | |||
| Конец | 1 | |||
| Получить С | 1 | 1 | ||
| Прибавить 1 | 2 | 1 | ||
| Сохранить C | 2 | 2 | ||
| Конец | 2 | 2 |
А постольку поскольку оба потока конкурентны и порядок их событий не определён, то не определён и результат системы — мы получили недетерминированность. Заметим, что ни параллелизм, ни асинхронность по отдельности не вносят недетерминированность; она свойственна только конкурентным программам, более конкретно — конкурентному доступу к разделяемым ресурсам (при определённых ситуациях, как будет пояснено дальше).
Эти проблемы активно исследовались с середины 1960-х. Несколько исследователей, в том числе Эдсгер Дейкстра, используют термин «критическая секция»[8][9]. Его определение довольно однозначно:
Критическая секция — некоторый набор последовательных действий в конкурентной единице (поток, процесс и т.д.), притом при выполнении нескольких конкурентных единиц максимум один из них имеет право выполнять действия из критической секции. Иными словами, критические секции — взаимоисключающие.
Понятие критической секции тесно связано с доступом к разделяемым ресурсам. В нашем примере с двумя потоками можно легко решить проблему обозначив критические секции так:
c = 0
def loop():
100 times:
critical section:
c = c + 1
th1 = thread(loop)
th2 = thread(loop)
start(th1)
start(th2)
join(th1)
join(th2)
print(c)
Тогда мы гарантируем, что не произойдёт такой ситуации, при которой потеряются данные, так как на момент начала критической секции в каждом потоке никаких действий с C другими потоками не производится, равно как и во время неё.
Однако стоит заметить, что есть случаи, когда конкурентные процессы с разделяемыми ресурсами без критических секций дают детерминированный результат.
<...>, мы можем думать о четырёх различных способах, как подпрограмма может взаимодействовать с памятью:
- Только читать
- Только записывать
- Сначала читать, затем записывать
- Сначала записывать, затем читать
Обозначим эти места памяти для подпрограммы как , , и соответственно. <...> В конце концов, мы должны убедиться в том, что частичное состояние, от которого зависит , одинаково для параллельных и последовательных моделей (прим: — подпрограмма, выполняющаяся после и ). <...> Упрощая, получаем 3 условия:
— Артур Бернстайн, «Analysis of Programs for Parallel Processing», 1966[10]
Проще говоря, детерминированный результат гарантирован, если процессы либо только читают общие ресурсы, либо их множества чтения и записи не пересекаются (ни один процесс не читает то, что пишет другой, и они не пишут в одни и те же места). В ином случае, требуется чёткое выделение критических секций, и как следствие, их синхронизация.
Перечитать, какой-то очень шаткий раздел, фу
Небольшое отступление, которое хочется сделать. То, что мы наблюдали в примере с двумя потоками — гонка. Однако, обычно разделяют: data race и race condition, но, несмотря на это, эти термины тоже часто путают. Постараемся им дать определение, основываясь на примерах:
Рассмотрим тот же пример с двумя потоками. Представим, что он выполняется на микроконтроллере с машинным словом в 8 бит, а C имеет тип uint32_t. Из-за физических ограничений процессор не сможет ни прочитать, ни сложить, ни сохранить два таких числа за одно действие — их придётся читать и складывать по частям размером в машинное слово. Тогда у нас возможна подобная ситуация:
Получилось, что первый поток сейчас имеет «порванное» число в памяти: первые 16 бит у него от предыдущего состояния, а вторые 16 бит — актуальные.
Другой пример — компиляторная оптимизация. Компилятор может решить, что не стоит тратить время на обновление переменной C каждый раз и сначала 100 раз сложить её с 1 и только затем записать результат в C.
В обоих случаях, мы, как программисты, не ожидаем такого поведения от нижележащих слоёв: процессора и компилятора — и, как следствие, логика работы программы полностью сломана. Это мы назовём Data race.
Теперь представим, что у нас есть специальная метка atomic для того, чтобы сказать компилятору о том, что мы хотим, чтобы операции с этой переменной не порождали data race (например, в случае с 8-битным процессором, не было «разорванного» чтения). Тогда наша программа выглядит так:
atomic c = 0
def loop():
100 times:
c = c + 1
th1 = thread(loop)
th2 = thread(loop)
start(th1)
start(th2)
join(th1)
join(th2)
print(c)
Data race в каком-то роде исключён, но, как можно заметить, результат всё ещё не определён, так как всё действие инкремента в целом не атомарно. В таком случае, мы говорим, что у нас Race condition.
Data race — явление, при котором к одному и тому же месту в памяти происходит два и более неконтролируемых конкурентных обращений, среди которых есть хотя бы одна операция записи.
Race condition — явление, при котором результат выполнения программы зависит от конкретной последовательности выполнения формально независимых (конкурентных) событий.
Теперь рассмотрим занятный пример. Допустим мы разрабатываем виртуальную машину как рантайм какого-то языка (представим, что это что-то похожее на Python). Рассмотрим операцию удаления элемента из массива. Для того, чтобы удалить элемент, нужно:
Представим, что все эти операции атомарны сами по себе, что для нас означает, что все биты памяти задаются одновременно. Тем не менее, вся операция удаления элемента без дополнительных ограничений не атомарна, а следовательно может сложиться такая ситуация для двух конкурентных потоков A и B (за обозначим разницу счётчика ссылок объекта элемента до последовательности действий и после):
ПримечаниеВ примере используется понятие счётчика ссылок. Это способ автоматического управления памятью. Объект имеет счётчик ссылок — количество различных мест, где он сейчас используется. Если счётчик ссылок доходит до 0, это значит, что объект более в программе не используется и может быть немедленно удалён для освобождения памяти.
Как видим, несмотря на то, что у элемента стало одним использованием меньше (ровно из одного места он был удалён), . В конечном итоге это приводит к преждевременному удалению объекта из памяти и, как следствие, к «use after free» и «double free», что обрекает ВМ на отказ. Вопрос вот какой — что мы наблюдали: data race или race condition?
Я предлагаю ответить на этот вопрос так: зависит от того, на каком уровне абстракции мы сейчас находимся. С точки зрения разработчика ВМ — это race condition. С точки зрения программист на языке, который на этой ВМ выполняется, — это data race.
Для того, чтобы избежать недетерминизма при конкурентном доступе к разделяемым ресурсам, нужно накладывать ограничения на порядок выполнения некоторых действий в процессах/потоках. Эти ограничения будут создавать зависимости между событиями, как мы уже видели на иллюстрациях в самом начале статьи, когда мы рассуждали на тему конкурентности. Такое создание зависимостей между ранее независимыми событиями называется синхронизацией.
Дейкстра в своих работах[8][9] говорит о том, что для синхронизации критических секций стоит использовать примитивы синхронизации. Далее мы рассмотрим как семафоры, которые предлагает использовать Дейкстра, так и другие способы синхронизации для дальнейшего понимания того, как работают различные подходы.
Это именно тот примитив синхронизации, который использует Дейкстра.
Семафор — по сути, неотрицательное целое число; более того, при решении только проблемы взаимного исключения, его значения будут ограничены до 0 и 1.
— Эдсгер Дейкстра, «Cooperating Sequential Processes» (EWD123), 1968[9]
Дейкстра называет такое подмножество семафоров «бинарными семафорами».
Для семафоров определяется 2 операции:
Такое количество упоминаний атомарности необходимо. Во-первых, чтобы избежать уже привычной нам проблемы с потерянным обновлением переменной (вспоминаем пример с двумя потоками и C). Во-вторых, чтобы избежать следующей ситуации:
| Семафор до | Поток 1 | Поток 2 | Поток 3 | Семафор после |
|---|---|---|---|---|
| 0 | в ожидании | в ожидании | 1 | |
| 1 | загрузил семафор | 1 | ||
| 1 | загрузил семафор | 1 | ||
| 1 | проверил — да | 1 | ||
| 1 | проверил — да | 1 | ||
| 1 | завершил | 0 | ||
| 0 | завершил | -1 |
Запомним операцию — обычно она «усыпляет» поток в ожидании возможности «забрать» семафор. Подробнее об этом поговорим далее в секции про потоки и процессы.
Для решения проблемы взаимного исключения критических секций семафоры используются так:
semaphore S = 1
c = 0
def loop():
100 times:
P(S)
c = c + 1
V(S)
th1 = thread(loop)
th2 = thread(loop)
start(th1)
start(th2)
join(th1)
join(th2)
print(c)
Кроме бинарных семафоров (ограниченных значениями 0 и 1), существуют и общие семафоры. Типичный пример использования такого семаформа — проблема производителя-потребителя.
Пусть у нас есть Производитель (процесс, который порождает какие-то данные для обработки) и Потребитель (процесс, который принимает и обрабатывает эти данные). Эти два процесса передают данные через очередь с ограниченным размером в N элементов. Что если производитель производит данные со скоростью 2 единицы/с, а потребитель потребляет их со скоростью 1 единица/с? Очевидно, что уже через N с очередь переполнится и данные начнут теряться. Но может быть и обратная ситуация — потребителю придётся ждать производителя, так как попытка достать что-то из пустой очереди ведёт к некорректному поведению.
Для решения этой проблемы будем использовать семафоры:
Алгоритм производителя:
P(E)
P(Q)
какой-то код добавления в очередь
V(Q)
V(F)
Алгоритм потребителя
P(F)
P(Q)
какой-то код получения из очереди
V(Q)
V(E)
??? вставить анимацию ???
Мьютексы (от англ. mutual exclusion — взаимное исключение) в каком-то смысле похожи на бинарные семафоры, можно сказать, что это продолжение их идеи. С мьютексами можно проделывать два действия:
Их главное отличие в том, что мьютекс «знает», какой поток/процесс его заблокировал и не даст разблокировать себя другому (например, вызвав ошибку).
Reentrant mutex (часто называется рекурсивным мьютексом) — особая разновидность обычного мьютекса. Его отличие заключается в том, что повторная операция блокировки из того же потока не приводит к бесконечному ожиданию (deadlock, о нём поговорим далее). Наглядный пример:
mutex M
def do_smth(i):
lock M
f(i)
unlock M
def f(i):
if i > 0:
do_smth(i - 1)
else:
...
do_smth(10)
Рекурсивные вызовы несколько раз захватывают M и уже ко второму захвату поток блокируется навсегда. Рекурсивный мьютекс позволяет избежать этих проблем. Вот как он определяется стандартом POSIX:
Позволяет любому потоку рекурсивно блокировать мьютекс. Мьютекс должен быть разблокирован такое же количество раз, как и заблокирован, чтобы стать доступным для других потоков.
<...> не требуется синхронизация памяти, если тип мьютекса — PTHREAD_MUTEX_RECURSIVE и вызывающий поток уже владеет этим мьютексом. <...> Каждый раз, когда поток блокирует мьютекс, количество блокировок увеличивается на один. Каждый раз, когда разблокирует, количество блокировок уменьшается на 1. Когда количество блокировок доходит до 0, мьютекс становится доступным для блокировки другими потоками.
<...> Поток, пытающийся заблокировать мьютекс без его разблокировки, должен успешно заблокировать мьютекс. Deadlock, случающийся при переблокировке PTHREAD_MUTEX_NORMAL, не может произойти с рекурсивным мьютексом.
— POSIX, стр. 98, 1599, 1622, 3473[11]
Возможно, вам встречалось где-то понятие фьютексов. Фьютекс — это специфичная для некоторых систем оптимизация мьютекса. Конкретная реализация в этой статье рассмотрена не будет, но в общих словах, фьютексы позволяют в некоторых случаях избегать системного вызова и дорогостоящего переключения в пространство ядра.
Спин-блокировка — один из самых простых вариантов взаимного исключения. Отличается от мьютекса тем, что процесс, пытающийся захватить лок, находится в состоянии busy-waiting, постоянно проверяя возможность захвата лока, тогда как мьютекс предполагает «усыпление» потока планировщиком.
Busy-waiting — постоянная повторяющаяся проверка определённого условия.
Интересно, что ещё публикации формализма семафоров, Дейкстра использовал то, что мы бы назвали спинлоком, в своём «Решении проблемы контроля в конкурентном программировании»[8]:
integer j;
LiO: b[i] := false;
Li1: if k != i then
Li2: begin
c[i] := true;
Li3: if b[k] then k := i;
go to Li1
end
else
Li4: begin
c[i] := false;
for j := 1 step 1 until N do
if j != i and not c[j] then go to Li1
end;
critical section;
c[i] := true;
b[i] := true;
remainder of the cycle in which stopping is allowed;
go to LiO
Что здесь происходит?У каждого процесса есть номер
i.b— массив «намерений»,c— «занятости». Когда i-тый процесс хочет войти в критическую секцию, он сначала заявляет намерение (b[i] := false). Если сейчас не его очередь (k != i), то он «уступает» (c[i] := true), затем в цикле (goto Li1) проверяет, не закончил ли текущий «владелец» операцию. Если да, то процесс ставит себя в приоритет (k := i). После этого процесс проваливается в другой цикл, где проверяет, не заявил ли ещё кто-то о том, что хочет войти в критическую секцию. Если да, то алгоритм повторяется, в противном случае можно начать выполнять критическую секцию. После выполнения отпускаем «намерение» и «занятость»:c[i] := true; b[i] := true.Дейкстра использует здесь свою вариацию алгоритма Деккера (??? да ???)[14].
Спин-блокировка (или, как её ещё называют, спинлок) эффективна в случае, когда затраты времени на переключение контекста (об этом поговорим далее, в секции про потоки и процессы) превышают время, в течение которого спинлок потенциально может быть заблокирован, так как (обычно) в ОС другие примитивы синхронизации вроде мьютекса говорят планировщику о том, что процесс можно временно снять с исполнения, тогда как спинлок такого поведения не имеет.
В ряде случаев обычные мьютексы (или бинарные семафоры) могут быть излишне ограничивающими. Как следствие, ухудшается производительность. Как мы помним из секции про недетерминированность, то в случае, если разделяемый ресурс только читается, то нужды в синхронизации нет. Очевидно, что каждая синхронизация бьёт по потенциальной производительности в целом, поэтому, когда возможно, хочется её избегать.
«Проблема писателей-читателей» была сформулирована и решена в 1971[12]. Выглядит она так: есть два класса процессов: писатели и читатели. Соответственно, писатели — те, кто проводят операции записи с разделяемыми ресурсами, а читатели — те, кто проводят операции чтения. Формулируется уже понятное нам требование: «читатели могут разделять секцию друг с другом, но у писателей должен быть эксклюзивный доступ».
У этой проблемы существует два решения: одно приоритизирует читателей, другое — писателей. Но в общем случае, принцип остаётся тот же:
Использование такой разновидности синхронизации позволяет значительно увеличить скорость чтения.
Монитор — это примитив синхронизации уровнем выше, чем семафоры и мьютексы. Если последние обычно предоставляются операционной системой, то монитор — соответственный механизм на уровне языка программирования (по крайней мере, в работах, связанных с мониторами, он представляется концепцией языка и оперирует сущностями конкретного языка программирования, например, переменными и процедурами). Концепцию мониторов вводит Хансен и формализует Хоар:
Чтобы упростить задачу, для каждого ресурса стоит создать отдельный планировщик. Каждый планировщик будет состоять из некоторого количества локальных подконтрольных ему данных вместе с некоторым количеством процедур и функций, которые будут вызываться программами, которые хотят забирать и возвращать ресурсы. Такая совокупность данных и процедур называется монитором.
— Ч. Энтони Р. Хоар, «Мониторы: концепция структурирования операционной системы», 1974[13]
Как уже было сказано, монитор — более высокоуровневая структура. Мониторы позволяют инкапсулировать и частично скрыть подробности синхронизации от пользователей (???). Можно дать такое определение:
Монитор — разделяемый объект с данными и процедурами (методами/функциями) доступа к этим данным, который защищает свои данные от небезопасного конкурентного доступа, автоматически синхронизируясь определенным образом при вызове своих процедур.
Немного далее будет приведён пример монитора, который внесёт ясность в определение.
Допустим, у нас существует монитор буфера сообщений. На очередном шаге программы потребитель пробует достать оттуда сообщение, но ничего не находит. Поток останавливается и говорит, что он ожидает условия "буфер не пуст". В этот момент можно переключиться на другие потоки. Как только производитель положит что-то в буфер, он просигнализирует о том, что условие "буфер не пуст" теперь выполняется. Все, кто ждал этого условия, теперь могут продолжать работу. Именно этим сигнализированием и занимается условная переменная. Заметим, что эксклюзивная блокировка (мьютекс) отпускается на время ожидания, чтобы другие потоки/процессы могли изменять состояние данных монитора.
Таким образом, мы вводим новый тип «переменной», известной как «условие»; и писатель монитора должен определить такие условные переменные для каждой причины, по которой программа может ожидать.
Такая переменная не принимает значения ни true, ни false; на самом деле, у неё вообще нет никакого значения, доступного программе. На практике, условная переменная будет представлена в виде (изначально пустой) очереди процессов, которые в данный момент ждут этого условия; но эта очередь невидима как для ожидающих, так и для сигнализирующих.
— Ч. Энтони Р. Хоар, «Мониторы: концепция структурирования операционной системы», 1974[[13]]
Для наглядности приведем пример одного из мониторов, которые описывает Хоар:
# (псевдокод)
monitor Buffer[T]:
buffer: list[T] = [], len(buffer) = N
lastpointer: int = 0, lastpointer < N
count: int = 0 , count <= N
nonempty: conditionvar
nonfull: conditionvar
def put(x: T):
if count == N:
nonfull.wait()
buffer[lastpointer] = x
lastpointer = (lastpointer + 1) mod N
count++
nonempty.signal()
def get() -> T:
if count == 0:
nonempty.wait()
x = buffer[(lastpointer - count) mod N]
nonfull.signal()
return x
Довольно простая концепция, растущая из распределенных вычислений, заострять на ней внимание не будем. Кратко ее можно описать так:
Барьер — примитив и точка синхронизации, достигнув которой, все связанные одним барьером потоки/процессы должны дождаться выполнения остальных связанных, но не успевших выполниться. Продолжать выполнение можно только после того, как все потоки/процессы достигли барьера.
Барьеры применяются в основном при параллельных вычислениях. Тем не менее, мы можем очень часто столкнуться с Thread.join, gather и другими API для ожидания одной или нескольких задач. Это тоже своего рода барьер (???).
Некоторые механизмы синхронизации слишком специфичны, чтобы описывать их здесь. Тем не менее, упомянуть их существование стоит:
Более подробно о них можно почитать в интернете.
Если при отсутствии синхронизации мы рискуем получить data race или race condition, то при её использовании появляются новые проблемы.
Дедлоки (взаимные блокировки) замечает ещё Дейкстра в своей работе 1968 года[9], называя их «deadly embrace». Формализовано это понятие будет позже, через 3 года:
Такая ситуация взаимной блокировки возможна, если выполняются все следующие условия:
Задачи требуют эксклюзивного владения ресурсом (взаимное исключение).
Задачи удерживают одни ресурсы, пока ожидают другие.
Ресурсы не могут быть насильно изъяты у задач, пока те не завершатся и не отдадут ресурсы сами.
Существует «круговая цепь» из задач, то есть одна задача удерживает ресурсы, которые ожидает следующая.
— Э. Коффман и др., «System Deadlocks», 1971[15]
??? вставить анимацию ???
Таким образом, дедлоки могут случиться в любой программе, в которой есть хотя бы два ресурса, владение которыми является взаимоисключающим (на практике, например, — два мьютекса).
Из данных условий следуют такие способы предотвращения дедлоков:
Задачи должны запрашивать все требуемые ресурсы сразу <...>
Если задача ожидает другие ресурсы, она должна отпустить уже занятые <...>
Требование линейного упорядочения ресурсов на всех задачах; т.е., если задача заблокировала ресурс , то далее она имеет право блокировать только такие ресурсы, которые следуют за по порядку <...>
— Э. Коффман и др., «System Deadlocks», 1971[15]
Коффман находит третий подход наиболее удачным и походящим под бОльшее количество случаев. Собственно, такой подход широко применяется и по сей день.
Можно легко продемонстрировать, что он действительно работает. Пусть есть задачи и ресурсы . Для всех задач (глобально) введём строгий порядок ресурсов. Обозначим его так: . Тогда обе задачи содержат такой код: ... -> lock p -> ... -> lock q -> .... Так как порядок глобальный и одинаковый, то блокировка на очередном ресурсе будет означать, что другая задача либо продолжает ожидать этот же ресурс, либо его уже освободила, а равно и освободила все предыдущие ресурсы.
??? вставить анимацию ???
Если дедлок уже произошёл, то по сути, остаётся только одно решение: «убить» одну из задач, чтобы разорвать цепь блокировок. Для того чтобы определить дедлок, можно применить обычный обход графа блокировок.
??? заполнить ???
Известная проблема обедающих философах в одной из формулировок звучит так:
За круглым столом сидят пять философов. Перед каждым из них бесконечная миска риса, между мисками — по одной палочке для еды. Каждый философ может либо есть, либо размышлять. Есть можно только если у философа есть по палочке в каждой руке. Взятие палочки и возврат на стол — раздельные действия, выполняющиеся одно за другим. Как сделать так, чтобы ни один из философов не голодал (т.е. все чередовали размышление и обед).
Первая проблема, которая тут может возникнуть — дедлок. В случае наивного алгоритма, который берёт сначала левую, потом правую палочку, очень быстро получится ситуация, при которой все пять философов держат левую палочку, но отпустить не могут, так как их правая палочка занята следующим философом. С этой проблемой мы уже умеем разбираться. Проще всего — занумеровать все палочки от 1 до 5 и блокировать их в одном порядке. Так мы избавимся от дедлока.
Тем не менее, возможна такая ситуация, что один из философов будет отставать от своих соседей, которые будут постоянно успевать брать палочки первыми. Такой философ будет голодать, так как не будет успевать брать палочки. С практической точки зрения, один поток может постоянно блокировать один и тот же ресурс, не давая другим потокам его заблокировать, создавая ресурсное голодание.
Другой, более практический пример ресурсного голодания можно привести с уже знакомым нам механизмом RWLock. В приведённой реализации возможна ситуация, при которой писатели никогда не смогут получить доступ к данным, из-за постоянного потока читателей.
Решать проблему голодания можно разными способами. Ограничимся лишь поверхностным перечислением основных:
Всё не нравится, переписать
Более сложной проблемой является livelock. Впервые этот термин в литературе предлагает, насколько мне известно, Эдвард Эшкрофт в своей работе по доказательству корректности параллельных программ. Так как верификация и доказательства (к сожалению) выходят за пределы статьи, рассматривать работу в деталях мы не будем. Ограничимся этим отрывком:
Мы видим, что T может быть полностью остановлен постоянно меняющимся набором ограничений. Эта ситуация не является дедлоком, и, на самом деле, отслеживается гораздо сложнее. Мы можем использовать термин «livelock», чтобы описать её. <…> Разумеется, условия, при которых может произойти livelock, довольно эзотеричны в этой программе, однако в других они могут таковыми и не являться. Скорее всего, возможно сконструировать параллельную программу, где, например, алгоритм round-robin, который решает, какую инструкцию исполнить дальше, порождает ровно такое поведение, которое приводит к livelock.
— Эдвард Эшкрофт, «Proving assertions about parallel programs», 1975[16]
Затем Лесли Лемпорт в своей работе «Proving the Correctness of Multiprocess Programs» формально описывает понятия safety и liveness. Последнее свойство говорит о том, что при корректном вводе программа рано или поздно завершится. Иными словами, не войдёт в цикл переключений между состояниями без какого-либо прогресса.
Избитый пример для объяснения лайвлока: два человека на узкой дороге — каждый отходит в сторону, но в итоге всё равно не могут пройти, потому что каждый раз оказываются друг напротив друга. Процессы (люди) не заблокированы, они продолжают выполнение и постоянно меняют состояние, но прогресса никакого нет.
Другой пример: модифицированный алгоритм у обедающих философов. Сделаем так, что если одна из палочек уже занята, философ положит свою палочку обратно и немного подождёт, прежде чем взять её снова. Однако так как все философы поступают одинаково, они будут постоянно брать и отпускать палочки, создавая лайвлок:
??? вставить анимацию ???
К этому моменту становится понятно, что центральной проблемой в организации конкурентных вычислений становится избежание ошибок, связанных с разделяемой памятью. Каждый язык и система реализуют их по-своему. Это называется «моделью памяти». Механизмы реализации конкурентности в языках программирования тесно с ней связаны.
Давайте очень кратко изложим ещё раз всё самое важное:
Параллелизм — способность выполнить несколько задач в одну единицу времени на физическом уровне.
Конкурентность — способность работать с независимыми событиями.
Асинхронность — способность не блокироваться во время ожидания.
Совместное использование конкурентными процессами разделяемых ресурсов ведёт к недетерминированности, кроме случая когда процессы либо только читают общие ресурсы, либо их множества чтения и записи не пересекаются (ни один процесс не читает то, что пишет другой, и они не пишут в одни и те же места). В иных случаях для достижения детерминированности требуется синхронизация и взаимное исключение критических секций.
Критическая секция — участок кода, который может выполняться только одним/потоком процессом, т.е. требующий взаимного исключения.
Синхронизировать можно:
Синхронизацию можно оптимизировать:
При синхронизации можно получить проблемы:
Без синхронизации можно получить проблемы:
Теперь мы можем начать исследование того, как развивались подходы.
Впервые заниматься несколькими вещами одновременно потребовалось системам в 1950-х. Конкретно, необходимо было освободить процессор от задач по вводу-выводу, например, печати ленты с результатом, для того чтобы он мог заниматься полезными вычислениями. ??? описать делегирование ввода-вывода доп. устройству, дать определение прерываниям, DMA, подвязать к определению Лемпорта ???.
По мере развития вычислительной техники и программного обеспечения, операционные системы стали поддерживать запуск нескольких процессов одновременно на одном компьютере.
Примерно с середины девяностых и к началу нулевых стало ясно, что существующие модели не способны удовлетворить растущие потребности приложений, в первую очередь — веб-приложений.
Центральной темой стала так называемая C10k problem (проблема 10 тысяч соединений), сформулированная в 1999 году. Её суть — невозможность обработать большое количество интернет-соединений из-за ограничений программного обеспечения, при наличии физической возможности у оборудования справиться с такой задачей.
Первым ответом на проблему C10k стал подход Event Loop + Callbacks