Параллельное программирование

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

Мы начнем с некоторой мотивации, затем рассмотрим последовательное выполнение, программирование с потоками или процессами, а затем асинхронное программирование. Глава завершается разделом о параллелизме и конкурентности.

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

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

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

Последовательное выполнение

Режимом выполнения по умолчанию в большинстве языков программирования (включая Rust) является последовательное выполнение.

do_a_thing();
println!("hello!");
do_another_thing();

Каждое оператор завершается до начала следующего1. Между этими операторами ничего не происходит2. Это может показаться тривиальным, но это действительно полезное свойство для рассуждений о нашем коде. Однако это также означает, что мы тратим много времени впустую. В приведенном выше примере, пока мы ждем выполнения println!("hello!"), мы могли бы выполнить do_another_thing(). Возможно, мы могли бы даже выполнить все три оператора одновременно.

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

Процессы и потоки

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

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

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

ОС отвечает за планирование потоков, что означает, что она решает, когда потоки запускаются и как долго. Большинство современных компьютеров имеют несколько ядер, поэтому они могут запускать несколько потоков буквально одновременно. Однако обычно потоков намного больше, чем ядер, поэтому ОС будет запускать каждый поток в течение небольшого промежутка времени, затем приостанавливать его и запускать другой поток на некоторое время7. Когда несколько потоков запускаются на одном ядре таким образом, это называется чередованием (interleaving) или разделением времени (time-slicing). Поскольку ОС выбирает, когда приостановить выполнение потока, это называется вытесняющей многозадачностью (pre-emptive multitasking) (многозадачность здесь просто означает одновременное выполнение нескольких потоков); ОС вытесняет (pre-empts) выполнение потока (или, более многословно, ОС вытесняюще приостанавливает выполнение. Она вытесняющая, потому что ОС приостанавливает поток, чтобы освободить время для другого потока, до того, как первый поток иначе приостановился бы, чтобы гарантировать, что второй поток сможет выполниться до того, как станет проблемой, что он не может).

Давайте снова посмотрим на IO. Что происходит, когда поток блокируется в ожидании IO? В системе с потоками ОС приостановит поток (в любом случае он просто будет ждать) и разбудит его снова, когда IO завершится8. В зависимости от алгоритма планирования, может пройти некоторое время после завершения IO, пока ОС разбудит поток, ожидающий IO, поскольку ОС может подождать, пока другие потоки выполнят некоторую работу. Так что теперь все стало намного эффективнее: пока один поток ждет IO, другой поток (или, скорее всего, многие потоки из-за многозадачности) может прогрессировать. Но с точки зрения потока, выполняющего IO, все остается последовательным — он ждет завершения IO, прежде чем начать следующую операцию.

Поток также может добровольно приостановить себя, вызвав функцию sleep, обычно с таймаутом. В этом случае ОС приостанавливает поток по запросу самого потока. Подобно приостановке из-за вытеснения или IO, ОС позже (после таймаута) разбудит поток для продолжения выполнения.

Когда ОС приостанавливает один поток и запускает другой (по любой причине), это называется переключением контекста (context switching). Переключаемый контекст включает регистры, записи операционной системы и содержимое многих кэшей. Это нетривиальный объем работы. Вместе с передачей управления ОС и обратно к потоку и затратами на работу с устаревшими кэшами, переключение контекста является дорогой операцией.

Наконец, обратите внимание, что некоторое оборудование или ОС не поддерживают процессы или потоки, это более вероятно во встроенном мире (embedded).

Асинхронное программирование

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

Чтобы отличать их от потоков, мы будем называть последовательность выполнений в асинхронной конкурентности задачей (task) (их также называют зелеными потоками (green threads), но это иногда имеет смысл вытесняющего планирования и деталей реализации, таких как один стек на задачу). Способ выполнения, планирования и представления задачи в памяти очень отличается от потока, но для высокоуровневой интуиции может быть полезно думать о задачах как о потоках, но управляемых полностью внутри программы, а не ОС.

В асинхронной системе все еще есть планировщик (scheduler), который решает, какую задачу запустить следующей (он является частью программы, а не частью ОС). Однако планировщик не может вытеснить задачу. Вместо этого задача должна добровольно отказаться от управления и позволить запланировать другую задачу. Поскольку задачи должны сотрудничать (cooperate) (отказываясь от управления), это называется кооперативной многозадачностью (cooperative multitasking).

Использование кооперативной, а не вытесняющей многозадачности имеет много последствий:

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

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

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

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

  • С потоками: поток, выполняющий IO, запрашивает IO у ОС, поток приостанавливается ОС, другие потоки выполняют работу, и когда IO завершен, ОС пробуждает поток, чтобы он мог продолжить выполнение с результатом IO.
  • С async: задача, выполняющая IO, запрашивает IO у среды выполнения, среда выполнения запрашивает IO у ОС, но ОС возвращает управление среде выполнения. Среда выполнения приостанавливает задачу IO и планирует другие задачи для выполнения работы. Когда IO завершен, среда выполнения пробуждает задачу IO, чтобы она могла продолжить выполнение с результатом IO.

Преимущество использования асинхронного IO заключается в том, что накладные расходы намного ниже, поэтому система может поддерживать на порядки больше задач, чем потоков. Это делает асинхронную конкурентность особенно хорошо подходящей для задач с большим количеством пользователей, которые проводят много времени в ожидании IO (если они не проводят много времени в ожидании и вместо этого выполняют много работы, ограниченной CPU, то преимущество низких накладных расходов не так велико, потому что узким местом будут ресурсы CPU и памяти).

Потоки и async не исключают друг друга: многие программы используют и то, и другое. Некоторые программы имеют части, которые лучше реализованы с использованием потоков, и части, которые лучше реализованы с использованием async. Например, сервер базы данных может использовать асинхронные техники для управления сетевым общением с клиентами, но использовать потоки ОС для вычислений с данными. Альтернативно, программа может быть написана только с использованием асинхронной конкурентности, но среда выполнения будет выполнять задачи в нескольких потоках. Это необходимо для того, чтобы программа могла использовать несколько ядер CPU. Мы рассмотрим пересечение потоков и асинхронных задач в нескольких местах позже в книге.

Конкурентность и параллелизм

До сих пор мы говорили о конкурентности (concurrency) (делать или казаться делающим много вещей одновременно), и мы намекали на параллелизм (parallelism) (наличие нескольких ядер CPU, что способствует буквальному выполнению многих вещей одновременно). Эти термины иногда используются взаимозаменяемо, но они являются разными концепциями. В этом разделе мы попытаемся точно определить эти термины и разницу между ними. Я буду использовать простой псевдокод для иллюстрации.

Представьте себе одну задачу, разбитую на кучу подзадач:

task1 {
  subTask1-1()
  subTask1-2()
  ...
  subTask1-100()
}

Давайте представим, что мы процессор, который выполняет такой псевдокод. Очевидный способ сделать это — сначала выполнить subTask1-1, затем выполнить subTask1-2 и так далее, пока мы не выполним все подзадачи. Это последовательное выполнение.

Теперь рассмотрим несколько задач. Как мы могли бы их выполнить? Мы могли бы начать одну задачу, выполнить все подзадачи, пока вся задача не будет завершена, затем начать следующую. Две задачи выполняются последовательно (и подзадачи внутри каждой задачи также выполняются последовательно). Глядя только на подзадачи, вы бы выполнили их так:

subTask1-1()
subTask1-2()
...
subTask1-100()
subTask2-1()
subTask2-2()
...
subTask2-100()

В качестве альтернативы, вы могли бы выполнить subTask1-1, затем отложить task1 (запомнив, как далеко вы продвинулись), взять следующую задачу и выполнить первую подзадачу из нее, затем вернуться к task1, чтобы выполнить следующую подзадачу. Две задачи были бы чередующимися (interleaved), мы называем это конкурентным выполнением двух задач. Это могло бы выглядеть так:

subTask1-1()
subTask2-1()
subTask1-2()
subTask2-2()
...
subTask1-100()
subTask2-100()

Если только одна задача не может наблюдать результаты или побочные эффекты другой задачи, то с точки зрения задачи подзадачи все еще выполняются последовательно.

Нет причин ограничиваться двумя задачами, мы можем чередовать любое количество и делать это в любом порядке.

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

Теперь представьте, что обрабатываете задачи не только вы, у вас есть друзья-процессоры, чтобы помочь. Вы можете работать над задачами одновременно и выполнять работу быстрее! Это параллельное выполнение (которое также является конкурентным). Вы могли бы выполнять подзадачи так:

Процессор 1           Процессор 2
==============        ==============
subTask1-1()          subTask2-1()
subTask1-2()          subTask2-2()
...                   ...
subTask1-100()        subTask2-100()

Если процессоров больше двух, мы можем обрабатывать еще больше задач параллельно. Мы также могли бы делать некоторое чередование задач на каждом процессоре или разделение задач между процессорами.

В реальном коде все немного сложнее. Некоторые подзадачи (например, IO) не требуют активного участия процессора, им нужно только запуститься, и некоторое время спустя собрать результаты. А некоторые подзадачи могут требовать результаты (или побочные эффекты) подзадачи из другой задачи для продолжения работы (синхронизация). Оба этих сценария ограничивают эффективные способы конкурентного выполнения задач, и именно поэтому, вместе с обеспечением некоторой концепции справедливости, планирование важно.

Достаточно глупых примеров, давайте попробуем определить вещи правильно

Конкурентность (Concurrency) — это про порядок вычислений, а параллелизм (Parallelism) — про режим выполнения.

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

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

Перефразируя, два вычисления могут происходить одно за другим (ни конкурентно, ни параллельно), их выполнение может быть чередовано на одном ядре CPU (конкурентно, но не параллельно), или они могут выполняться одновременно на двух ядрах (конкурентно и параллельно)11.

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

Как системы с потоками, так и асинхронные системы могут предлагать и конкурентность, и параллелизм. В обоих случаях конкурентность контролируется кодом (порождение потоков или задач), а параллелизм контролируется планировщиком, который является частью ОС для потоков (настраивается через API ОС) и частью библиотеки среды выполнения для async (настраивается выбором среды выполнения, тем, как реализована среда выполнения, и опциями, которые среда выполнения предоставляет клиентскому коду). Однако есть практическое различие из-за соглашений и общих значений по умолчанию. В системах с потоками каждый конкурентный поток выполняется параллельно с использованием как можно большего параллелизма. В асинхронных системах нет строгого значения по умолчанию: система может запускать все задачи в одном потоке, может назначать несколько задач одному потоку и привязывать этот поток к ядру (так что группы задач выполняются параллельно, но внутри группы каждая задача выполняется конкурентно, но никогда параллельно с другими задачами внутри группы), или задачи могут запускаться параллельно с ограничениями или без. Для первой части этого руководства мы будем использовать среду выполнения Tokio, которая в основном поддерживает последнюю модель. Т.е. поведение относительно параллелизма похоже на конкурентность с потоками. Более того, мы увидим функции в асинхронном Rust, которые явно поддерживают конкурентность, но не параллелизм, независимо от среды выполнения.

Резюме

  • Существует много моделей выполнения. Мы описали последовательное выполнение, потоки и процессы, и асинхронное программирование.
    • Потоки — это абстракция, предоставляемая (и планируемая) ОС. Они обычно включают вытесняющую многозадачность, по умолчанию параллельны и имеют довольно высокие накладные расходы на управление и переключение контекста.
    • Асинхронное программирование управляется пользовательской средой выполнения (user-space runtime). Многозадачность кооперативная. Оно имеет более низкие накладные расходы, чем потоки, но ощущается немного иначе, чем программирование с потоками, поскольку использует другие примитивы программирования (async и await, и фьючерсы (futures), а не потоки как объекты первого класса).
  • Конкурентность и параллелизм — это разные, но тесно связанные концепции.
    • Конкурентность — это про порядок вычислений (операции конкурентны, если порядок их выполнения нельзя наблюдать).
    • Параллелизм — это про вычисления на нескольких процессорах (операции параллельны, если они буквально происходят в одно и то же время).
  • И потоки ОС, и асинхронное программирование обеспечивают конкурентность и параллелизм; асинхронное программирование также может предлагать конструкции для гибкой или детализированной конкурентности, которые не являются частью API потоков большинства операционных систем.

  1. На самом деле это не совсем так: современные компиляторы и процессоры реорганизуют ваш код и выполняют его в любом порядке, который им нравится. Последовательные операторы, вероятно, будут перекрываться многими различными способами. Однако это никогда не должно быть наблюдаемо для самой программы или ее пользователей. ↩

  2. Это тоже не совсем так: даже когда одна программа является чисто последовательной, другие программы могут работать одновременно; подробнее об этом в следующем разделе. ↩

  3. IO — это аббревиатура от input/output (ввод/вывод). Это означает любое общение программы с миром вне программы. Это может быть чтение или запись на диск или в сеть, вывод на терминал, получение пользовательского ввода с клавиатуры или мыши или общение с ОС или другой программой, работающей в системе. IO интересен в контексте конкурентности, потому что его выполнение занимает на несколько порядков больше времени, чем почти любая задача, которую программа может выполнять внутри. Это обычно означает много ожидания, и это время ожидания — возможность сделать другую работу. ↩

  4. То, когда именно IO завершен, на самом деле довольно сложно. С точки зрения программы, один вызов IO завершен, когда управление возвращается от ОС. Обычно это указывает на то, что данные были отправлены в какое-то оборудование или другую программу, но это не обязательно означает, что данные были фактически записаны на диск или показаны пользователю и т.д. Для этого может потребоваться дополнительная работа в оборудовании или периодическая очистка кэшей, или чтобы другая программа прочитала данные. В основном нам не нужно об этом беспокоиться, но полезно знать. ↩

  5. с точки зрения пользователя, одна программа может включать несколько процессов, но с точки зрения ОС каждый процесс — это отдельная программа. ↩

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

  7. То, как именно ОС выбирает, какой поток запускать и как долго (и на каком ядре), является ключевой частью планирования. Существует множество вариантов, как высокоуровневых стратегий, так и опций для настройки этих стратегий. Принятие правильных решений здесь имеет crucialное значение для хорошей производительности, но это сложно, и мы не будем здесь углубляться. ↩

  8. Есть другой вариант: поток может активно ждать (busy wait), просто вращаясь в цикле, пока IO не завершится. Это не очень эффективно, поскольку другие потоки не смогут запуститься, и это необычно для большинства современных систем. Вы можете столкнуться с этим в реализациях блокировок или в очень простых встраиваемых системах. ↩

  9. Мы начнем наше объяснение, предполагая, что программа имеет только один поток, но расширим его позже. Вероятно, в системе работают другие процессы, но они реально не влияют на то, как работает асинхронная конкурентность. ↩

  10. Есть некоторые языки программирования (или даже библиотеки), которые имеют конкурентность, управляемую внутри программы (без ОС), но с вытесняющим планировщиком, а не полагаясь на сотрудничество между потоками. Go — известный пример. Эти системы не требуют обозначений async и await, но имеют другие недостатки, включая усложнение взаимодействия с другими языками или ОС и наличие тяжеловесной среды выполнения. Очень ранние версии Rust имели такую систему, но к версии 1.0 от нее не осталось и следа. ↩

  11. Может ли вычисление быть параллельным, но не конкурентным? Вроде да, но не факт. Представьте две задачи (a и b), которые состоят из одной подзадачи каждая (1 и 2, принадлежащие a и b, соответственно). Используя синхронизацию, мы не можем начать подзадачу 2, пока подзадача 1 не завершена, и задача a должна ждать завершения подзадачи 2, пока она не завершится. Теперь a и b работают на разных процессорах. Если мы смотрим на задачи как на черные ящики, мы можем сказать, что они работают параллельно, но в некотором смысле они не конкурентны, потому что их порядок полностью определен. Однако, если мы посмотрим на подзадачи, мы можем увидеть, что они ни параллельны, ни конкурентны. ↩

  12. Которую, я думаю, предложил Aaron Turon, и она отразилась в некотором дизайне стандартной библиотеки Rust, например, в функции available_parallelism. ↩