Поток (вычисления)

Эта статья о концепции параллелизма. Информацию о многопоточности в аппаратном обеспечении см. в разделе Многопоточность (компьютерная архитектура) . О форме кода, полностью состоящего из вызовов подпрограмм , см. Поточный код . Чтобы узнать о других значениях, см. Тема (значения) .

Процесс с двумя потоками выполнения, работающий на одном процессоре

Программа , процесс и поток
Планирование , вытеснение , переключение контекста

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

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

Реализация потоков и процессов различается в разных операционных системах. В книге «Современные операционные системы» Таненбаум показывает , что возможны многие различные модели организации процессов.

История

Потоки впервые появились под названием «задачи» в книге «Мультипрограммирование с переменным числом задач» OS/360 (MVT) в 1967 году. Зальцер (1966) приписывает Виктору А. Высоцкому термин «поток».

Использование потоков в программных приложениях стало более распространенным в начале 2000-х годов, когда процессоры начали использовать несколько ядер. Приложения, желающие использовать преимущества нескольких ядер для повышения производительности, должны были использовать параллелизм для использования нескольких ядер.

Связанные понятия

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

Процессы

Основная статья: Процесс (вычисления)

На уровне ядра процесс содержит один или несколько потоков ядра , которые совместно используют ресурсы процесса, такие как память и дескрипторы файлов: процесс — это единица ресурсов, а поток — это единица планирования и выполнения. Планирование ядра обычно выполняется упреждающе или, реже, совместно. На уровне пользователя такой процесс, как система выполнения, сам может планировать несколько потоков выполнения. Если они не используют общие данные, как в Erlang, их обычно аналогично называют процессами. в то время как, если они совместно используют данные, их обычно называют (пользовательскими) потоками , особенно если они запланированы заранее. Совместно запланированные пользовательские потоки известны как волокна ; разные процессы могут планировать пользовательские потоки по-разному. Пользовательские потоки могут выполняться потоками ядра различными способами (один-к-одному, многие-к-одному, многие-ко-многим). Термин « облегченный процесс » по-разному относится к пользовательским потокам или к механизмам ядра для планирования пользовательских потоков в потоках ядра.

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

Потоки ядра

Поток ядра — это «облегченная» единица планирования ядра. В каждом процессе существует по крайней мере один поток ядра. Если в процессе существует несколько потоков ядра, они используют одну и ту же память и файловые ресурсы. процессов операционной системы Потоки ядра являются вытесняющими многозадачными, если планировщик является вытесняющим. Потоки ядра не владеют ресурсами, за исключением стека , копии регистров , включая программный счетчик , и локальной памяти потока (если таковая имеется), и поэтому их создание и уничтожение относительно дешевы. Переключение потоков также является относительно дешевым: оно требует переключения контекста (сохранение и восстановление регистров и указателя стека), но не меняет виртуальную память и, следовательно, дружественно к кэшу (оставляя TLB действительным). Ядро может назначить один или несколько программных потоков каждому ядру ЦП (оно может назначить себе несколько программных потоков в зависимости от поддержки многопоточности) и может заменять потоки, которые блокируются. Однако обмен потоками ядра занимает гораздо больше времени, чем пользовательские потоки.

Пользовательские темы

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

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

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

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

Волокна

Основная статья: Fiber (информатика)

Волокна представляют собой еще более легкую единицу планирования, которая планируется совместно : работающее волокно должно явно « уступить », чтобы позволить другому волокну работать, что делает их реализацию намного проще, чем ядро ​​или пользовательские потоки . Файбер можно запланировать для работы в любом потоке одного и того же процесса. Это позволяет приложениям повысить производительность за счет самостоятельного управления планированием вместо того, чтобы полагаться на планировщик ядра (который может быть не настроен для приложения). Некоторые исследовательские реализации модели параллельного программирования OpenMP реализуют свои задачи посредством волокон. Тесно связанными с волокнами являются сопрограммы , с той разницей, что сопрограммы являются конструкцией уровня языка, а волокна — конструкцией системного уровня.

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

Потоки отличаются от традиционных многозадачных операционной системы процессов по нескольким причинам:

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

такие системы, как Windows NT и OS/2, Говорят, что имеют дешевые потоки и дорогие процессы; в других операционных системах разница не столь велика, за исключением стоимости переключателя адресного пространства , который на некоторых архитектурах (особенно x86 ) приводит к сбросу буфера резервной трансляции (TLB).

Преимущества и недостатки потоков по сравнению с процессами включают в себя:

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

Планирование

кооперативное

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

многопроцессорные

До начала 2000-х годов большинство настольных компьютеров имели только один одноядерный процессор без поддержки аппаратных потоков , хотя потоки все еще использовались на таких компьютерах, поскольку переключение между потоками обычно происходило быстрее, чем полное переключение контекста процесса . В 2002 году Intel поддержку одновременной многопоточности добавила в процессор Pentium 4 под названием Hyper-Threading ; в 2005 году они представили двухъядерный процессор Pentium D , а AMD представила двухъядерный процессор Athlon 64 X2 .

Системы с одним процессором обычно реализуют многопоточность посредством квантования времени : центральный процессор (ЦП) переключается между различными программными потоками . Такое переключение контекста обычно происходит достаточно часто, чтобы пользователи воспринимали потоки или задачи как выполняемые параллельно (для популярных серверных/настольных операционных систем максимальный интервал времени потока, когда другие потоки ожидают, часто ограничивается 100–200 мс). В многопроцессорной или многоядерной системе несколько потоков могут выполняться параллельно , при этом каждый процессор или ядро ​​одновременно выполняет отдельный поток; на процессоре или ядре с аппаратными потоками отдельные программные потоки также могут выполняться одновременно отдельными аппаратными потоками.

Модели резьбы

1:1 (потоки на уровне ядра)

Потоки, создаваемые пользователем в соответствии 1:1 с планируемыми объектами в ядре. являются простейшей возможной реализацией потоков. OS/2 и Win32 использовали этот подход с самого начала, в то время как в Linux этот подход реализован библиотекой GNU C (через NPTL или более ранние версии LinuxThreads ). Этот подход также используется в Solaris , NetBSD , FreeBSD , macOS и iOS .

M :1 (потоки на уровне пользователя)

Модель M :1 подразумевает, что все потоки уровня приложения сопоставляются с одним запланированным объектом уровня ядра; ядро не знает потоков приложения. При таком подходе переключение контекста можно осуществить очень быстро и, кроме того, его можно реализовать даже на простых ядрах, не поддерживающих многопоточность. Однако одним из основных недостатков является то, что он не может получить выгоду от аппаратного ускорения на многопоточных процессорах или многопроцессорных компьютерах: одновременно не запланировано более одного потока. Например: если одному из потоков необходимо выполнить запрос ввода-вывода, весь процесс блокируется и преимущество многопоточности невозможно использовать. GNU Portable Threads использует потоки пользовательского уровня, как и State Threads .

M : N (гибридная резьба)

M : N отображает некоторое количество M потоков приложений на некоторое количество N объектов ядра, или «виртуальные процессоры». Это компромисс между потоками уровня ядра («1:1») и уровня пользователя (« N :1»). В общем, системы потоков « M : N » сложнее реализовать, чем потоки ядра или пользовательские потоки, поскольку требуются изменения как в коде ядра, так и в коде пользовательского пространства. . В реализации M:N библиотека потоков отвечает за планирование пользовательских потоков в доступных планируемых объектах; это делает переключение контекста потоков очень быстрым, поскольку позволяет избежать системных вызовов. Однако это увеличивает сложность и вероятность инверсии приоритетов , а также неоптимального планирования без обширной (и дорогостоящей) координации между планировщиком пользовательской области и планировщиком ядра.

гибридной

• Активации планировщика , используемые более старыми версиями реализации собственной библиотеки потоков NetBSD POSIX ( модель M : N в отличие от модели реализации ядра или пользовательского пространства 1:1)
• Облегченные процессы, используемые в старых версиях Solaris. операционной системы
• Марсель из проекта PM2 .
• ОС для Tera- Cray MTA-2
• Компилятор Glasgow Haskell (GHC) для языка Haskell использует облегченные потоки, запланированные для потоков операционной системы.

История моделей потоков в системах Unix

В SunOS 4.x реализованы облегченные процессы или LWP. NetBSD 2.x+ и DragonFly BSD реализуют LWP как потоки ядра (модель 1:1). В версиях от SunOS 5.2 до SunOS 5.8, а также от NetBSD 2 до NetBSD 4 реализована двухуровневая модель, мультиплексирующая один или несколько потоков пользовательского уровня в каждом потоке ядра (модель M:N). SunOS 5.9 и более поздние версии, а также NetBSD 5 устранили поддержку пользовательских потоков и вернулись к модели 1:1. Во FreeBSD 5 реализована модель M:N. FreeBSD 6 поддерживала как 1:1, так и M:N, пользователи могли выбирать, какой из них следует использовать с конкретной программой, используя /etc/libmap.conf. Начиная с FreeBSD 7, соотношение 1:1 стало значением по умолчанию. FreeBSD 8 больше не поддерживает модель M:N.

Однопоточные и многопоточные программы

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

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

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

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

Основная статья: Безопасность резьбы

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

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

Другие API синхронизации включают переменные условий , критические секции , семафоры и мониторы .

Пулы потоков

Основная статья: Шаблон пула потоков

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

Многопоточные программы против однопоточных:

Многопоточные приложения имеют следующие преимущества перед однопоточными:

• Отзывчивость : многопоточность позволяет приложению реагировать на вводимые данные. В однопоточной программе, если основной поток выполнения блокирует длительную задачу, может показаться, что все приложение зависло. Перемещая такие длительные задачи в рабочий поток , который выполняется одновременно с основным потоком выполнения, приложение может продолжать реагировать на ввод пользователя, выполняя задачи в фоновом режиме. С другой стороны, в большинстве случаев многопоточность — не единственный способ обеспечить отзывчивость программы, поскольку неблокирующие сигналы ввода-вывода и/или Unix . для получения аналогичных результатов доступны
• Распараллеливание : приложения, которым требуется использовать многоядерные или многопроцессорные системы, могут использовать многопоточность для разделения данных и задач на параллельные подзадачи и позволить базовой архитектуре управлять выполнением потоков либо одновременно на одном ядре, либо параллельно на нескольких ядрах. Вычислительные среды графических процессоров, такие как CUDA и OpenCL, используют модель многопоточности, в которой от десятков до сотен потоков параллельно обрабатывают данные на большом количестве ядер . Это, в свою очередь, позволяет лучше использовать систему и (при условии, что затраты на синхронизацию не съедают выгоды) может обеспечить более быстрое выполнение программы.

Многопоточные приложения имеют следующие недостатки:

• Сложность синхронизации и связанные с ней ошибки: при использовании общих ресурсов, типичных для многопоточных программ, программист должен быть осторожен, чтобы избежать состояний гонки и другого неинтуитивного поведения. Чтобы правильно манипулировать данными, потокам часто необходимо своевременно встречаться , чтобы обработать данные в правильном порядке. Потоки также могут требовать взаимоисключающих операций (часто реализуемых с использованием мьютексов ), чтобы предотвратить чтение или перезапись общих данных в одном потоке при изменении другим. Неосторожное использование таких примитивов может привести к взаимоблокировкам , активным блокировкам или гонкам за ресурсы. Как писал Эдвард А. Ли : «Хотя потоки кажутся небольшим шагом по сравнению с последовательными вычислениями, на самом деле они представляют собой огромный шаг. Они отказываются от наиболее важных и привлекательных свойств последовательных вычислений: понятности, предсказуемости и детерминизма. Потоки , как модель вычислений, крайне недетерминированы, и работа программиста состоит в том, чтобы сократить этот недетерминизм».
• Быть непроверяемым . В общем, многопоточные программы недетерминированы и, как следствие, нетестируемы. Другими словами, в многопоточной программе легко могут быть ошибки, которые никогда не проявляются в тестовой системе, а проявляются только в рабочей среде. Эту проблему можно облегчить, ограничив взаимодействие между потоками определенными четко определенными шаблонами (например, передачей сообщений).
• Стоимость синхронизации . Поскольку переключение контекста потока на современных процессорах может стоить до 1 миллиона циклов процессора, это затрудняет написание эффективных многопоточных программ. В частности, особое внимание необходимо уделять тому, чтобы синхронизация между потоками не выполнялась слишком часто.

Поддержка языков программирования

Многие языки программирования в той или иной степени поддерживают многопоточность.

• IBM PL/I (F) включил поддержку многопоточности (называемой многозадачностью ) еще в конце 1960-х годов, и это было продолжено в Оптимизирующем компиляторе и более поздних версиях. Компилятор IBM Enterprise PL/I представил новую модель «поточного» API. Ни одна из версий не была частью стандарта PL/I.
• Многие реализации C и C++ поддерживают многопоточность и предоставляют доступ к собственным API-интерфейсам операционной системы. Стандартизированным интерфейсом для реализации потоков является POSIX Threads (Pthreads), который представляет собой набор вызовов библиотеки C-функций. Поставщики ОС могут свободно реализовывать интерфейс по своему усмотрению, но разработчик приложений должен иметь возможность использовать один и тот же интерфейс на нескольких платформах. Большинство платформ Unix , включая Linux, поддерживают Pthreads. Microsoft Windows имеет собственный набор функций потоков в интерфейсеprocess.h для многопоточности, например, Beginthread .
• Некоторые более высокого уровня (обычно кросс-платформенные языки программирования ), такие как Java , Python и .NET Framework , предоставляют разработчикам многопоточность, абстрагируя при этом специфические для платформы различия в реализации потоков во время выполнения. Несколько других языков программирования и языковых расширений также пытаются полностью абстрагировать концепцию параллелизма и многопоточности от разработчика ( Cilk , OpenMP , Message Passing Interface (MPI)). Некоторые языки вместо этого предназначены для последовательного параллелизма (особенно с использованием графических процессоров), не требуя параллелизма или потоков ( Ateji PX , CUDA ).
• Некоторые интерпретируемые языки программирования имеют реализации (например, Ruby MRI для Ruby, CPython для Python), которые поддерживают многопоточность и параллелизм, но не параллельное выполнение потоков из-за глобальной блокировки интерпретатора (GIL). GIL — это блокировка взаимного исключения, удерживаемая интерпретатором, которая может помешать интерпретатору одновременно интерпретировать код приложения в двух или более потоках одновременно. Это эффективно ограничивает параллелизм в многоядерных системах. Это также ограничивает производительность потоков, привязанных к процессору (которые требуют процессора), но не оказывает такого большого влияния на потоки, связанные с вводом-выводом или сетью. Другие реализации интерпретируемых языков программирования, такие как Tcl с использованием расширения Thread, позволяют избежать ограничения GIL за счет использования модели Apartment, где данные и код должны быть явно «разделены» между потоками. В Tcl каждый поток имеет один или несколько интерпретаторов.
• В моделях программирования, таких как CUDA , предназначенных для параллельных вычислений данных , массив потоков параллельно запускает один и тот же код, используя только его идентификатор для поиска данных в памяти. По сути, приложение должно быть спроектировано так, чтобы каждый поток выполнял одну и ту же операцию с разными сегментами памяти, чтобы они могли работать параллельно и использовать архитектуру графического процессора.
• Языки описания оборудования , такие как Verilog, имеют другую модель потоков, которая поддерживает чрезвычайно большое количество потоков (для моделирования оборудования).

См. также

• Клонировать (системный вызов Linux)
• Коммуникация последовательных процессов
• Многозадачность компьютера
• Многоядерный (вычисления)
• Многопоточность (компьютерное оборудование)
• Неблокирующий алгоритм
• Инверсия приоритета
• Протопотоки
• Одновременная многопоточность
• Шаблон пула потоков
• Безопасность резьбы
• Блок информации о потоке Win32

Дальнейшее чтение

• Дэвид Р. Бутенхоф: Программирование с использованием потоков POSIX , Аддисон-Уэсли, ISBN   0-201-63392-2
• Брэдфорд Николс, Дик Баттлар, Жаклин Пру Фарелл: Программирование Pthreads , O'Reilly & Associates, ISBN   1-56592-115-1
• Пол Хайд: Программирование потоков Java , Сэмс, ISBN   0-672-31585-8
• Джим Беверидж, Роберт Винер: Многопоточные приложения в Win32 , Аддисон-Уэсли, ISBN   0-201-44234-5
• Уреш Вахалия: Внутреннее устройство Unix: новые рубежи , Прентис Холл, ISBN   0-13-101908-2