Понятие параллелизма и потоки выполнения

Введение

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

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

История

В 1967 году потоки впервые появились под названием "задачи" в операционной системе OS/360 Multiprogramming with a Variable Number of Tasks (MVT). Солтцер (1966) отмечает, что термин "поток" был предложен Виктором А. Высоцким. Использование потоков в программных приложениях стало более распространенным в начале 2000-х годов, когда процессоры начали использовать многоядерную архитектуру. Приложения, стремящиеся использовать преимущества многоядерных процессоров для повышения производительности, нуждались в реализации параллельного выполнения.

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

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

Процессы

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

At the kernel level, a process contains one or more kernel threads, which share the process's resources, such as memory and file handles – a process is a unit of resources, while a thread is a unit of scheduling and execution. Kernel scheduling is typically uniformly done preemptively or, less commonly, cooperatively. At the user level a process such as a runtime system can itself schedule multiple threads of execution. If these do not share data, as in Erlang, they are usually analogously called processes, while if they share data they are usually called (user) threads, particularly if preemptively scheduled. Cooperatively scheduled user threads are known as fibers; different processes may schedule user threads differently. User threads may be executed by kernel threads in various ways (one to one, many to one, many to many). The term "light weight process" variously refers to user threads or to kernel mechanisms for scheduling user threads onto kernel threads. A process is a "heavyweight" unit of kernel scheduling, as creating, destroying, and switching processes is relatively expensive. Processes own resources allocated by the operating system. Resources include memory (for both code and data), file handles, sockets, device handles, windows, and a process control block. Processes are isolated by process isolation, and do not share address spaces or file resources except through explicit methods such as inheriting file handles or shared memory segments, or mapping the same file in a shared way – see interprocess communication. Creating or destroying a process is relatively expensive, as resources must be acquired or released. Processes are typically preemptively multitasked, and process switching is relatively expensive, beyond basic cost of context switching, due to issues such as cache flushing (in particular, process switching changes virtual memory addressing, causing invalidation and thus flushing of an untagged translation lookaside buffer (TLB), notably on x86).

Ядра

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

Темы пользователей

Потоки иногда реализуются в библиотеках пользовательского пространства, поэтому их называют пользовательскими потоками. Ядро не знает об их существовании, поэтому они управляются и планируются в пользовательском пространстве. Некоторые реализации основывают свои пользовательские потоки на нескольких потоках ядра, чтобы воспользоваться преимуществами многопроцессорных машин (модель M:N). Пользовательские потоки, реализованные виртуальными машинами, также называются "зелёными" потоками. Поскольку реализации пользовательских потоков обычно полностью находятся в пользовательском пространстве, переключение контекста между пользовательскими потоками в рамках одного процесса чрезвычайно эффективно, так как не требует никакого взаимодействия с ядром: переключение контекста может быть выполнено локальным сохранением регистров процессора, используемых текущим выполняемым пользовательским потоком или волокном, и последующей загрузкой регистров, необходимых для выполнения другого пользовательского потока или волокна. Поскольку планирование происходит в пользовательском пространстве, политика планирования может быть легче адаптирована к требованиям рабочей нагрузки программы. Однако использование блокирующих системных вызовов в пользовательских потоках (в отличие от потоков ядра) может быть проблематичным. Если пользовательский поток или волокно выполняет блокирующий системный вызов, другие пользовательские потоки и волокна в процессе не могут выполняться до тех пор, пока этот системный вызов не вернётся. Типичным примером этой проблемы является ввод-вывод: большинство программ написаны для синхронного выполнения операций ввода-вывода. Когда операция ввода-вывода инициируется, выполняется системный вызов, который не возвращается до завершения операции ввода-вывода. В течение этого времени весь процесс "блокируется" ядром и не может выполняться, что приводит к тому, что другие пользовательские потоки и волокна в том же процессе оказываются лишёнными возможности выполнения. Распространённым решением этой проблемы (используемым, в частности, многими реализациями "зелёных" потоков) является предоставление API ввода-вывода, который реализует интерфейс, блокирующий вызывающий поток, а не весь процесс, используя внутренне неблокирующий ввод-вывод и планируя другой пользовательский поток или волокно во время выполнения операции ввода-вывода. Аналогичные решения могут быть предоставлены и для других блокирующих системных вызовов. В качестве альтернативы, программа может быть написана таким образом, чтобы избегать использования синхронного ввода-вывода или других блокирующих системных вызовов (в частности, используя неблокирующий ввод-вывод, включая лямбда-продолжения и/или асинхронные/await примитивы).

Threads are sometimes implemented in userspace libraries, thus called user threads. The kernel is unaware of them, so they are managed and scheduled in userspace. Some implementations base their user threads on top of several kernel threads, to benefit from multi processor machines (M:N model). User threads as implemented by virtual machines are also called green threads. As user thread implementations are typically entirely in userspace, context switching between user threads within the same process is extremely efficient because it does not require any interaction with the kernel at all: a context switch can be performed by locally saving the CPU registers used by the currently executing user thread or fiber and then loading the registers required by the user thread or fiber to be executed. Since scheduling occurs in userspace, the scheduling policy can be more easily tailored to the requirements of the program's workload. However, the use of blocking system calls in user threads (as opposed to kernel threads) can be problematic. If a user thread or a fiber performs a system call that blocks, the other user threads and fibers in the process are unable to run until the system call returns. A typical example of this problem is when performing I/O: most programs are written to perform I/O synchronously. When an I/O operation is initiated, a system call is made, and does not return until the I/O operation has been completed. In the intervening period, the entire process is "blocked" by the kernel and cannot run, which starves other user threads and fibers in the same process from executing. A common solution to this problem (used, in particular, by many green threads implementations) is providing an I/O API that implements an interface that blocks the calling thread, rather than the entire process, by using non blocking I/O internally, and scheduling another user thread or fiber while the I/O operation is in progress. Similar solutions can be provided for other blocking system calls. Alternatively, the program can be written to avoid the use of synchronous I/O or other blocking system calls (in particular, using non blocking I/O, including lambda continuations and/or async/await primitives).

Волокна

Волокна — это еще более легковесная единица планирования, которая планируется кооперативно: работающее волокно должно явно "уступить" управление, чтобы позволить запуститься другому волокну, что значительно упрощает их реализацию по сравнению с потоками ядра или пользовательскими потоками. Волокно может быть запланировано для выполнения в любом потоке в пределах одного процесса. Это позволяет приложениям повысить производительность, самостоятельно управляя планированием, вместо того чтобы полагаться на планировщик ядра (который может быть не оптимизирован для конкретного приложения). Параллельные среды программирования, такие как OpenMP, иногда реализуют свои задачи с помощью волокон. Корутины тесно связаны с волокнами, при этом корутины являются конструкцией на уровне языка программирования, а волокна — конструкцией на системном уровне.

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

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

Системы с одним или несколькими процессорами

До начала 2000-х годов большинство настольных компьютеров имели процессор с одним ядром, без поддержки аппаратных потоков, хотя потоки всё ещё использовались, поскольку переключение между ними обычно было быстрее, чем полное переключение контекста процесса. В 2002 году Intel добавила поддержку одновременной многопоточности в процессор Pentium 4 под названием Hyper-Threading, а в 2005 году представила двухъядерный процессор Pentium D. В то же время AMD представила двухъядерный процессор Athlon 64 X2. В системах с одним процессором многопоточность обычно реализуется посредством разделения времени: центральный процессор (ЦП) переключается между различными программными потоками. Это переключение контекста обычно происходит достаточно часто, чтобы пользователи воспринимали потоки или задачи как выполняющиеся параллельно (для популярных серверных и настольных операционных систем максимальный квант времени потока, когда другие потоки ожидают, часто ограничен 100–200 мс). На многопроцессорной или многоядерной системе несколько потоков могут выполняться параллельно, при этом каждый процессор или ядро выполняет отдельный поток одновременно. На процессоре или ядре с аппаратными потоками отдельные программные потоки также могут выполняться одновременно разными аппаратными потоками.

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

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

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

Модель M: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 синхронизации включают условные переменные, критические секции, семафоры и мониторы.

Полы нитей

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

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

Многие языки программирования поддерживают многопоточность в той или иной степени. IBM PL/I(F) включал поддержку многопоточной обработки (называемой многозадачностью) еще в конце 1960-х годов, и это было продолжено в оптимизирующем компиляторе и последующих версиях. Компилятор IBM Enterprise PL/I представил новую модель API "thread". Ни одна из этих версий не входила в стандарт 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, имеют другую модель потоков, которая поддерживает чрезвычайно большое количество потоков (для моделирования аппаратного обеспечения).

Many programming languages support threading in some capacity. IBM PL/I(F) included support for multithreading (called multitasking) as early as in the late 1960s, and this was continued in the Optimizing Compiler and later versions. The IBM Enterprise PL/I compiler introduced a new model "thread" API. Neither version was part of the PL/I standard. Many implementations of C and C++ support threading, and provide access to the native threading APIs of the operating system. A standardized interface for thread implementation is POSIX Threads (Pthreads), which is a set of C function library calls. OS vendors are free to implement the interface as desired, but the application developer should be able to use the same interface across multiple platforms. Most Unix platforms, including Linux, support Pthreads. Microsoft Windows has its own set of thread functions in the process. h interface for multithreading, like beginthread. Some higher level (and usually cross platform) programming languages, such as Java, Python, and NET Framework languages, expose threading to developers while abstracting the platform specific differences in threading implementations in the runtime. Several other programming languages and language extensions also try to abstract the concept of concurrency and threading from the developer fully (Cilk, OpenMP, Message Passing Interface (MPI)). Some languages are designed for sequential parallelism instead (especially using GPUs), without requiring concurrency or threads (Ateji PX, CUDA). A few interpreted programming languages have implementations (e. g., Ruby MRI for Ruby, CPython for Python) which support threading and concurrency but not parallel execution of threads, due to a global interpreter lock (GIL). The GIL is a mutual exclusion lock held by the interpreter that can prevent the interpreter from simultaneously interpreting the application's code on two or more threads at once. This effectively limits the parallelism on multiple core systems. It also limits performance for processor bound threads (which require the processor), but doesn't effect I/O bound or network bound ones as much. Other implementations of interpreted programming languages, such as Tcl using the Thread extension, avoid the GIL limit by using an Apartment model where data and code must be explicitly "shared" between threads. In Tcl each thread has one or more interpreters. In programming models such as CUDA designed for data parallel computation, an array of threads run the same code in parallel using only its ID to find its data in memory. In essence, the application must be designed so that each thread performs the same operation on different segments of memory so that they can operate in parallel and use the GPU architecture. Hardware description languages such as Verilog have a different threading model that supports extremely large numbers of threads (for modeling hardware).