Поток выполнения

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 16:54, 24 августа 2017.

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

Отличие от процессов

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

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

История

Потоки впервые появились в 1967 году в OS/360 Multiprogramming с переменным числом задач, в контексте которой они назывались «задачами». Термин «поток» был приписан Виктору Высоцкому. Планировщики процессов многих современных операционных систем напрямую поддерживают как поточную, так и многопроцессорную потоковую обработку, а ядро операционной системы позволяет программистам манипулировать потоками, предоставляя необходимые функциональные возможности через интерфейс системных вызовов. Некоторые реализации потоков называются потоками ядра, в то время как легкие процессы (англ. Light-weight processes, LWP) - это особый тип потока ядра, который имеет одно и то же состояние и информацию. Кроме того, программы могут иметь потоки пользовательского пространства при потоковой передаче с помощью таймеров, сигналов или других методов, чтобы прервать собственное выполнение.

Многопоточность

Системы с одним процессором обычно реализуют многопоточность путем временной нарезки: центральный процессор (ЦП) переключается между различными программными потоками. Такое переключение контекста обычно происходит настолько часто и быстро, что пользователи воспринимают потоки и задачи как параллельные. На многопроцессорной или многоядерной системе несколько потоков могут выполняться параллельно, причем каждый процессор или ядро выполняет отдельный поток одновременно; На процессоре или ядре с аппаратными потоками отдельные программные потоки могут также выполняться одновременно отдельными аппаратными потоками[Источник 1]

Преимущества
  • Реактивность: многопоточность может позволить приложению оставаться отзывчивым к вводу. В однопоточной программе, если основной поток выполнения блокирует длительную задачу, все приложение может зависнуть. Перемещая такие длительные задачи в рабочий поток, который выполняется одновременно с основным исполнительным потоком, приложение может оставаться отзывчивым к вводу пользователя при выполнении задач в фоновом режиме. С другой стороны, в большинстве случаев многопоточность не является единственным способом поддержания реакции программы, при этом для получения аналогичных результатов доступны неблокирующие сигналы ввода / вывода и / или Unix.
  • Более быстрое выполнение: это преимущество многопоточной программы позволяет ей работать быстрее в компьютерных системах, имеющих несколько центральных процессоров (CPU) или один или несколько многоядерных процессоров, или через кластер машин при условии достаточной независимости (отсутствия необходимости ждать друг друга).
  • Более низкое потребление ресурсов: при использовании потоков приложение может обслуживать несколько клиентов одновременно, используя меньшее количество ресурсов, чем это требовалось бы при использовании нескольких копий процессов. Например, HTTP-сервер Apache использует пулы потоков: пул потоков слушателя для прослушивания входящих запросов и пул потоков сервера для обработки этих запросов.
  • Эффективное использование системы: в качестве примера файловая система, использующая несколько потоков, может достичь более высокой пропускной способности и меньшей задержки, поскольку данные на более быстром носителе (например, в кэш-памяти) могут быть получены одним потоком, в то время как другой поток извлекает данные с более медленной среды (например, как внешнее хранилище), причем ни один поток не ожидает завершения другого.
  • Упрощенный обмен и обмен данными: в отличие от процессов, для которых требуется передача сообщений или механизм общей памяти для выполнения межпроцессного взаимодействия (англ. inter-process communication, IPC), потоки могут взаимодействовать через данные, код и файлы, которые они уже используют.
  • Распараллеливание: приложения, использующие многоядерные или многопроцессорные системы, могут использовать многопоточность для разделения данных и задач на параллельные подзадачи, и позволить базовой архитектуре управлять тем, как выполняются потоки, либо одновременно на одном ядре, либо параллельно на нескольких ядрах. Графические вычислительные среды, такие как CUDA и OpenCL, используют модель многопоточности, где от нескольких десятков до сотен потоков параллельно работают с данными, используя большое количество ядер.
Недостатки
  • Синхронизация: поскольку потоки используют одно и то же адресное пространство, программист должен быть осторожным, чтобы избежать конкуренции и других неинтуитивных действий. Для правильного управления данными потоки часто должны состыковываться во времени, чтобы обрабатывать данные в правильном порядке. Потоки могут также требовать взаимоисключающих операций (часто реализуемых с помощью семафоров), чтобы предотвратить одновременное изменение или чтение общих данных в процессе их модификации. Небрежное использование таких примитивов может привести к ошибках.
  • Поток разрушает процесс: незаконная операция, выполняемая потоком, приводит к сбою всего процесса; Поэтому один неверный поток может нарушить обработку всех других потоков в приложении.

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

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

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

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

Процессы, потоки выполнения ядра, пользовательские потоки и файберы

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

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

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

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

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

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

Проблемы потоков и файберов

Параллелизм и структуры данных

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

Ввод-вывод и планирование

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

Модели

1:1 (на уровне ядра)

Потоки в данной модели соответствуют диспетчируемым сущностям ядра, что является простейшим способом реализации потоковости. В Windows API этот подход использовался с самого начала. В Linux обычная библиотека C реализует этот подход (через библиотеку потоков POSIX, а в более старших версиях через LinuxThreads). Аналогичный подход используется NetBSD, ОС Solaris, FreeBSD.

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

Данная модель предполагает, что все потоки выполнения уровня пользователя отображаются на единую планируемую сущность уровня ядра, и ядро ничего не знает о составе прикладных потоков выполнения. При таком подходе переключение контекста может быть сделано очень быстро, и, кроме того, он может быть реализован даже на простых ядрах, которые не поддерживают многопоточность. Однако при таком подходе нельзя извлечь никакой выгоды из аппаратного ускорения на многопоточных процессорах или многопроцессорных компьютерах, потому что только один поток выполнения может быть запланирован на любой момент времени. Эта модель используется в GNU Portable Threads, Netscape Portable Runtime, FSU Pthreads.

M:N (смешанная потоковость)

В модели M:N некоторое число M прикладных потоков выполнения отображаются на некоторое число N сущностей ядра или «виртуальных процессоров». Модель является компромиссной между моделью уровня ядра («1:1») и моделью уровня пользователя («N:1»). Реализована, например в Microsoft Windows 7 или The Glasgow Haskell Compiler (GHC).

Реализация файберов

Файберы могут быть реализованы без поддержки операционной системы, хотя некоторые операционные системы и библиотеки предоставляют явную поддержку для них, например Библиотека Win32 содержит API для файберов, Ruby как реализация «зелёных потоков», Netscape Portable Runtime и т.д.

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

IBM PL / I (F) включила поддержку многопоточности (так называемой многозадачности) в конце 1960-х годов, и это было продолжено в Оптимизационном компиляторе и более поздних версиях. Компилятор IBM Enterprise PL / I представил новую модель API-потоков. Ни одна из версий не была частью стандарта PL / I.

Многие языки программирования поддерживают потоки в некоторой степени. Многие реализации C и C ++ поддерживают потоковую обработку и предоставляют доступ к собственным API-интерфейсам потоков в операционной системе. Некоторые более высокоуровневые (и, как правило, кросс-платформенные) языки программирования, такие как языки Java[Источник 2], предоставляют разработчикам потоки, абстрагируя специфические для платформы различия в реализациях потоков во время выполнения. Некоторые другие языки программирования и языковые расширения также пытаются полностью отделить концепцию параллелизма и потокования от разработчика (Cilk, OpenMP, Message Passing Interface (MPI)). Некоторые языки предназначены для последовательного параллелизма (особенно с использованием графических процессоров), не требуя параллелизма или потоков (Ateji PX, CUDA).

Некоторые интерпретируемые языки программирования имеют реализации (например, Ruby MRI для Ruby, CPython для Python), которые поддерживают потоковую обработку и параллелизм, но не параллельное выполнение потоков из-за глобальной блокировки интерпретатора (GIL). GIL - блокировка взаимного исключения, удерживаемая интерпретатором, которая может помешать интерпретатору одновременно интерпретировать код приложения на двух или более потоках одновременно, что фактически ограничивает параллелизм в нескольких основных системах.

Другие реализации интерпретируемых языков программирования, такие как Tcl, использующие расширение Thread, избегают предела GIL, используя "модель апартаментов", где данные и код должны быть явно «разделяемы» между потоками. В Tcl каждый поток имеет один или несколько интерпретаторов.

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

Практическая многопоточность

Стандартизованным интерфейсом для реализации потоков является POSIX Threads (Pthreads), который представляет собой набор вызовов библиотеки C-функций[Источник 3]. Поставщики ОС могут свободно внедрять интерфейс по желанию, но разработчик приложения должен иметь возможность использовать один и тот же интерфейс на нескольких платформах. Большинство платформ Unix, включая Linux, поддерживают Pthreads. Microsoft Windows имеет свой собственный набор функций потока в интерфейсе process.h для многопоточности. Java предоставляет еще один стандартизованный интерфейс для операционной системы хоста, используя библиотеку java.util.concurrent для Java.[Источник 4]


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

Еще одна парадигма использования потоков - это пулы потоков, где заданное число потоков создается при запуске, а затем ожидает назначения задачи. Когда приходит новая задача, пул просыпается, выполянет задачу и возвращается к ожиданию после ее завершения. Это позволяет избежать относительно дорогих функций создания и уничтожения потоков для каждой выполняемой задачи и выводит управление потоками из руки разработчика приложения и оставляет его в библиотеке или операционной системе, которая лучше подходит для оптимизации управления потоками. Используется в таких структурах как Grand Central Dispatch и Threading Building Blocks.

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

Источники

  1. What is Multithreading? // thekiransblog: сайт. URL: http://thekiransblog.blogspot.ru/2010/02/multithreading.html/ (дата обращения: 08.05.2017)
  2. A Tool for Testing Multi-threaded Java Applications // research.ibm: сайт. URL: https://www.research.ibm.com/haifa/projects/verification/contest (дата обращения: 08.05.2017)
  3. POSIX threads explained // IBM: сайт. URL: https://www.ibm.com/developerworks/library/l-posix1/index.html (дата обращения: 08.05.2017)
  4. What makes parallel programming hard? // futurechips: сайт. URL: http://www.futurechips.org/tips-for-power-coders/parallel-programming.html (дата обращения: 08.05.2017)