Многозадачность: процессы, потоки, параллелизм и почему это сложно

В статье про операционную систему мы видели, как одно ядро создаёт иллюзию, что десятки программ работают одновременно: планировщик тысячи раз в секунду переключает процессор между процессами (Что делает операционная система). Пока задачи независимы, эта иллюзия дёшева и приятна. Настоящая боль начинается, когда задачам нужно работать над общими данными — тогда «переключается когда захочет» превращается из удобства в источник багов, которые не воспроизводятся, исчезают под отладчиком и всплывают раз в миллион запусков в проде.

Эта статья — про то, почему многозадачность одновременно необходима и трудна. Мы разведём два часто путаемых слова (конкурентность и параллелизм), разберём процессы и потоки как единицы многозадачности, увидим корень зла — общее изменяемое состояние — и пройдёмся по инструментам, которыми его приручают: замки, атомарные операции, модели без разделяемой памяти. Глубокие механизмы планировщика и примитивов живут в треке Операционные системы; здесь — большая картина и интуиция, зачем всё это и где оно ломается.

Зачем это вообще стало важно: стена частоты

Тридцать лет закон Мура исправно удваивал число транзисторов, и вместе с ними росла тактовая частота: 100 МГц, 1 ГГц, 3 ГГц. Программист мог ничего не делать — код сам ускорялся с каждым новым процессором. Примерно к 2005 году эта халява кончилась. Частоту уперли в физику: чем быстрее переключаются транзисторы, тем больше тепла, а отвести его с крохотного кристалла нечем. Частоты застряли около 3–5 ГГц и с тех пор почти не растут.

Транзисторы же продолжили дешеветь, и индустрия пошла вширь, а не ввысь: вместо одного быстрого ядра — много ядер на одном кристалле. Ваш телефон имеет 6–8 ядер, сервер — десятки. Но вот засада: одно-поточная программа на 16-ядерной машине использует ровно одно ядро, остальные 15 простаивают. Чтобы код стал быстрее, программист теперь обязан сам разбить работу на части, которые пойдут по ядрам параллельно. Бесплатный обед кончился — за производительность стало нужно платить многозадачным мышлением. Отсюда и важность темы: конкурентность перестала быть уделом авторов ОС и стала повседневным навыком.

Два разных слова: конкурентность и параллелизм

Их постоянно путают, а разница принципиальна.

• Конкурентность (concurrency) — про структуру: как устроена программа, которая имеет дело со многими задачами сразу. Задачи логически независимы и могут продвигаться, чередуясь. Это способ организовать работу.
• Параллелизм (parallelism) — про исполнение: две и более вещи физически считаются в один и тот же момент, на разных ядрах. Это способ ускорить работу.

Конкурентность возможна без параллелизма: одно ядро, чередуя задачи по кванту времени, конкурентно, но не параллельно — в каждый момент считает ровно одну. И наоборот, параллелизм требует конкурентной структуры, но добавляет к ней настоящую одновременность. Роб Пайк сформулировал канонически: «Конкурентность — это про то, как справляться с множеством дел; параллелизм — про то, чтобы делать множество дел сразу» (доклад «Concurrency Is Not Parallelism»).

Практический вывод: разбив программу на конкурентные задачи, вы получаете потенциал к параллельному ускорению — но только если под ним есть свободные ядра. На одном ядре конкурентность всё равно полезна: пока одна задача ждёт диск или сеть, другая считает, и ядро не простаивает. Именно так одно-поточный веб-сервер обслуживает тысячи соединений.

Процессы и потоки: две единицы многозадачности

Многозадачность бывает двух «весов». Разница — в том, что они разделяют.

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

Поток (thread) — нить исполнения внутри процесса. У потока свои регистры и свой стек (где он находится в коде и его локальные переменные), но кучу, глобальные данные и открытые файлы он делит со всеми остальными потоками того же процесса. Именно это общее пространство делает потоки одновременно мощными и опасными.

Сравнение по граням, которые решают на практике:

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

Почему это сложно: общее изменяемое состояние

Вот вся суть боли в одной строке. Возьмём безобиднейший код — увеличить счётчик:

counter = counter + 1

Для человека это атомарное «прибавь один». Для процессора — три отдельных шага (как процессор исполняет команды):

1. прочитать counter из памяти в регистр;
2. прибавить 1 в регистре;
3. записать результат обратно в память.

Пока поток один — неважно. Но пусть два потока делают counter + 1 одновременно, а планировщик, как мы знаем, может вытеснить поток в любой момент — хоть между шагом 1 и шагом 3. Тогда возможна такая расстановка:

Оба потока прочитали 41, оба записали 42 — одно из двух увеличений бесследно пропало. Это гонка данных (data race): результат зависит от того, в каком порядке планировщик чередует шаги, а порядок недетерминирован. Запустите миллион раз — почти всегда верно, но иногда нет. И это счётчик; в реальном коде «потерянное обновление» — это пропавший платёж, задвоенный заказ, поехавшая структура данных.

Три свойства делают такие баги особенно коварными:

• Недетерминизм. Тот же вход, тот же код — разный результат от запуска к запуску, потому что решает планировщик, а не вы.
• Гейзенбаги. Отладчик, лог, замедление меняют тайминги — и баг исчезает. Отсюда название: наблюдение меняет наблюдаемое.
• Редкость. Окно гонки — наносекунды между шагами. Может не выстрелить месяцами, а потом «вдруг» — под нагрузкой в чёрную пятницу, когда потоков и переключений больше.

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

Синхронизация: как навести порядок

Инструменты, которыми потоки договариваются не наступать друг другу на ноги.

Взаимное исключение — мьютекс (mutex, замок). Замок можно захватить (lock) и отпустить (unlock). Если замок занят, второй поток на lock блокируется и ждёт, пока первый не отпустит. Оборачиваем критическую секцию — и гонка исчезает, потому что внутрь пускают по одному:

import threading

counter = 0
lock = threading.Lock()

def increment():
    global counter
    with lock:            # захватить замок; ждать, если занят
        counter = counter + 1   # критическая секция — здесь всегда один поток
        # замок отпускается автоматически на выходе из with

Атомарные операции. Для простых случаев вроде счётчика тяжёлый замок избыточен. Процессоры дают атомарные инструкции — read-modify-write, которую железо выполняет как одно неделимое действие (compare-and-swap, fetch-and-add). Наши три шага сливаются в один, который нельзя разорвать вытеснением. Это фундамент lock-free структур данных — быстрых, но дьявольски сложных в проектировании.

Семафор — счётчик разрешений: пускает в секцию до N потоков сразу (мьютекс — частный случай при N = 1). Годится для «не более 10 одновременных запросов к БД».

Условная переменная — позволяет потоку уснуть до наступления события («буфер не пуст») и быть разбуженным другим потоком. Основа паттерна «производитель — потребитель».

У всякой синхронизации есть цена, и она называется сериализация. Заперев участок под мьютекс, вы заставили потоки проходить его по очереди — то есть выключили на нём параллелизм. Чем шире критическая секция и чем больше потоков за неё дерутся (contention, состязание за замок), тем ближе программа к последовательной, несмотря на все ядра.

Это не абстрактная угроза, а математический потолок — закон Амдала. Если доля $p$ работы распараллеливается, а доля $(1-p)$ строго последовательна, то ускорение на $N$ ядрах ограничено:

$$S(N) = \frac{1}{(1-p) + \dfrac{p}{N}}$$

Пусть 95% кода параллельно ($p = 0.95$). При $N \to \infty$ ускорение упирается в $1 / (1 - 0.95) = 20$ раз — и всё. Оставшиеся 5% последовательного кода (часто это как раз критические секции под замком) не дадут разогнаться сильнее, сколько ядер ни добавь. Мораль: уменьшайте долю последовательного — сужайте критические секции, а не наращивайте железо.

Новые беды от решений: взаимоблокировки

Замки лечат гонки, но порождают собственный класс бед. Самая известная — взаимоблокировка (deadlock): два потока навечно ждут друг друга. Поток A захватил замок 1 и хочет замок 2; поток B захватил замок 2 и хочет замок 1. Оба ждут, ни один не отпустит. Программа зависла навсегда, процессор при этом свободен.

Дедлок возникает ровно при четырёх условиях Коффмана одновременно: взаимное исключение, удержание с ожиданием, невытесняемость замка и круговое ожидание (цикл в графе «кто кого ждёт»). Убери любое — и дедлок невозможен. На практике проще всего убить круговое ожидание: захватывать замки всегда в одном глобальном порядке. Если оба потока берут сначала замок 1, потом замок 2, цикл не замкнётся.

Родня дедлока:

• Livelock — потоки не заблокированы, а бесконечно уступают друг другу дорогу (как двое в узком коридоре шагают в одну сторону) — работа идёт, прогресса нет.
• Голодание (starvation) — поток формально может продвигаться, но его вечно оттесняют более приоритетные, и он не получает ресурс.

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

Абстракция протекает: модель памяти и видимость

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

Причина — в оптимизациях, которые мы разбирали в других слоях. Во-первых, у каждого ядра свой кэш (иерархия памяти). Ядро 0 записало x = 1 в свой L1-кэш, а до RAM и до кэша ядра 1 это ещё не дошло — и ядро 1 продолжает видеть старое значение.

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

# Поток 1 (писатель)          # Поток 2 (читатель)
data = 42                     while not ready:
ready = True                      pass
                              print(data)   # может напечатать 0, а не 42!

Кажется, что раз ready стало True, то data уже точно 42. Но процессор вправе переставить две записи местами или задержать data в кэше — и читатель увидит ready = True при ещё старом data. Интуиция «строки исполняются сверху вниз и сразу видны всем» — иллюзия однопоточного мира.

Лечится это барьерами памяти (memory barriers) и атомарными переменными с гарантиями порядка — но вручную их почти никто не расставляет. За вас это делают те же мьютексы и атомики: захват и освобождение замка содержат барьеры, которые гарантируют, что всё записанное до unlock станет видно потоку после его lock. Поэтому практический совет прост: трогаете общие данные — делайте это под синхронизацией, и модель памяти о вас позаботится. Языки описывают эти гарантии в своих memory model — например, модель памяти Java (JSR-133) и модель Go; понимать её тонкости нужно, лишь когда вы пишете lock-free код.

Модели конкурентности: разные способы приручить сложность

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

Потоки и замки — разделяемая память. Классика C++, Java, C#. Максимальный контроль и производительность, но вся тяжесть гонок, дедлоков и модели памяти — на вас. Мощно и остро.

Цикл событий — один поток, кооперативно. JavaScript и async/await во многих языках работают так: один поток крутит event loop, задачи добровольно уступают управление на операциях ожидания (await), а не вытесняются насильно. Раз поток один — гонок за память нет по построению: между двумя точками await код неделим. Плата: если задача не уступает (тяжёлый цикл без await), она блокирует весь цикл, и всё встаёт. Идеально для I/O-нагрузки (тысячи ожидающих сеть соединений), плохо для счётной нагрузки.

Обмен сообщениями — без общей памяти. Радикальное решение: у общей памяти нет — значит, и гонок за неё нет. Задачи изолированы и общаются, посылая друг другу сообщения.

• Акторы (Erlang, Elixir): каждый актор — крохотный изолированный процесс со своим состоянием и почтовым ящиком; он обрабатывает сообщения по одному, так что внутри него гонок нет. Миллионы акторов на машине — фундамент отказоустойчивых систем телефонии и мессенджеров.
• CSP (communicating sequential processes) — путь Go: дешёвые горутины общаются через типизированные каналы. Лозунг Go: «Не общайтесь через разделяемую память — разделяйте память, общаясь». Данные передаются по каналу от владельца к владельцу, а не лежат общей лужей под замком.

Параллелизм по данным. Когда одна и та же операция применяется к массиву независимых элементов, гонок нет вовсе — считай их параллельно. Так работают SIMD-инструкции процессора, GPU (тысячи ядер над пикселями и тензорами) и map-reduce на кластерах. Именно этот вид параллелизма кормит машинное обучение (Data Engineering).

Сравнить подходы помогает простая матрица: насколько легко писать против того, сколько контроля и производительности выжимаешь.

Важная оговорка про Python: из-за GIL (global interpreter lock) в стандартном CPython в любой момент байт-код исполняет лишь один поток, поэтому потоки Python не ускоряют счётную работу — для настоящего параллелизма там берут процессы (multiprocessing) или считают в C-расширениях. Это классический пример того, как «потоки» на бумаге и параллелизм на деле — разные вещи.

Как это применяют на практике

• Веб-серверы. Три школы ровно из моделей выше. «Поток на запрос» (традиционный Java, синхронный код, но тяжёлые потоки), «событийный цикл» (Node.js, nginx — один поток тянет тысячи соединений на I/O) и «лёгкие процессы/горутины» (Go, Elixir — дёшево масштабируются). Выбор диктует профиль нагрузки: I/O или счёт (как работает веб).
• Базы данных. Тысячи клиентов пишут в одни данные — это гонки в чистом виде, только на уровне записей. БД решают их транзакциями и блокировками/MVCC, пряча всю синхронизацию за свойством изоляции ACID (как данные переживают выключение).
• Параллельные алгоритмы. Сортировка слиянием, умножение матриц, обход графа распадаются на независимые куски — идеальные кандидаты на ядра. Насколько хорошо распараллеливается конкретный алгоритм — тема трека Алгоритмы.
• Отказоустойчивость. Изоляция акторов/процессов позволяет строить системы, где падение части не роняет целое (философия «let it crash» в Erlang/Elixir).

Типичные заблуждения

• «Больше потоков — всегда быстрее». До числа ядер — да; дальше начинается борьба за процессор, рост переключений контекста и состязание за замки. За пределом закона Амдала добавленные потоки только замедляют.
• counter + 1 атомарно». Нет — это три шага (чтение, сложение, запись), и между ними вас вытеснят. Отсюда все гонки.
• «Мой код без синхронизации работает — значит, он корректен». Гонка может не выстрелить миллион раз, а на миллион первый — под нагрузкой — уронить прод. «Работает сейчас» и «корректно» — разные вещи.
• «Потоки = параллелизм». Не обязательно: на одном ядре они лишь чередуются, а под GIL в Python вычисления и вовсе не параллельны.
• «Замок сделал код безопасным». Он убрал гонку, но мог добавить дедлок и сериализацию. Синхронизация — не «включить безопасность», а обмен одних проблем на другие.
• «Записал в общую память — другой поток сразу увидел». Нет: кэши и перестановки команд делают видимость негарантированной без барьеров, которые прячутся в синхронизации.

Мини-итог

Конкурентность — способ структурировать программу из многих логически независимых задач; параллелизм — их физически одновременное исполнение на многих ядрах, ставшее обязательным с тех пор, как частоты упёрлись в стену и процессоры пошли вширь. Единицы многозадачности — процессы (изолированы, безопасны, дороги в общении) и потоки (делят память, дёшевы, но опасны). Корень всей трудности — общее изменяемое состояние: безобидное counter + 1 распадается на три шага, чередование которых даёт гонки данных — недетерминированные, редкие, исчезающие под отладчиком баги. Их гасят синхронизацией (мьютексы, семафоры, атомики), но платят сериализацией (закон Амдала) и новыми бедами — дедлоками, livelock, голоданием. Вдобавок «одна общая память» — сама протекающая абстракция: кэши ядер и перестановки команд ломают наивную видимость записей. Радикальные лекарства убирают общую память вовсе — обмен сообщениями (акторы, CSP) и один поток с циклом событий (async/await), — обменивая часть производительности на безопасность по построению. Многозадачность сложна не из-за плохих инструментов, а по существу: недетерминизм совместного доступа — свойство самого мира, и вся инженерия здесь про то, как его ограничить.

Что дальше

Мы не раз упирались в вопросы вида «а можно ли вообще?»: можно ли гарантированно обнаружить дедлок в произвольной программе, всегда ли завершится вот этот цикл ожидания. Это уже вопросы не про скорость, а про пределы вычислимого — что машина может решить в принципе, а что не может никогда, сколько ядер ни дай. Следующая статья — про теорию вычислений: автоматы, машину Тьюринга и задачи, которые не решить алгоритмом вовсе.

Теория вычислений для всех: автоматы, машина Тьюринга и что нельзя вычислить