Введение
Выполнение нескольких вычислений в перекрывающиеся периоды времени.
Конкурентные вычисления – это форма вычислений, в которой несколько вычислений выполняются одновременно – в перекрывающиеся периоды времени – вместо последовательного выполнения, когда одно завершается перед началом следующего. Это свойство системы – будь то программа, компьютер или сеть – где для каждого процесса существует отдельная точка выполнения или "поток управления". Конкурентная система – это система, в которой вычисление может продвигаться вперед, не дожидаясь завершения всех остальных вычислений. Конкурентные вычисления являются формой модульного программирования. В рамках этой парадигмы общее вычисление разбивается на подвычисления, которые могут выполняться одновременно. Пионерами в области конкурентных вычислений являются Эдсгер Дейкстра, Пер Бринч Хансен и К. А. Р. Хоар.
Введение
Понятие конкурентных вычислений часто путают со связанным, но отличным понятием параллельных вычислений, хотя оба могут быть описаны как "множественные процессы, выполняющиеся в течение одного и того же периода времени". В параллельных вычислениях выполнение происходит в один и тот же физический момент: например, на отдельных процессорах многопроцессорной машины с целью ускорения вычислений — параллельные вычисления невозможны на (одном ядре) одноядерном процессоре, поскольку только одно вычисление может произойти в любой момент (в течение любого единичного такта). Напротив, конкурентные вычисления состоят из перекрывающихся жизненных циклов процессов, но выполнение не обязательно должно происходить в один и тот же момент. Целью здесь является моделирование процессов во внешнем мире, которые происходят одновременно, например, множественных клиентов, обращающихся к серверу одновременно. Структурирование программных систем, состоящих из нескольких конкурентных, взаимодействующих частей, может быть полезным для решения проблемы сложности, независимо от того, могут ли эти части выполняться параллельно. Например, конкурентные процессы могут выполняться на одном ядре путем чередования шагов выполнения каждого процесса с использованием временных интервалов: только один процесс выполняется за раз, и если он не завершается в течение своего временного интервала, он приостанавливается, другой процесс начинается или возобновляется, а затем позже исходный процесс возобновляется. Таким образом, несколько процессов находятся в процессе выполнения в один момент, но в этот момент выполняется только один процесс. Конкурентные вычисления могут выполняться параллельно, например, путем назначения каждого процесса отдельному процессору или ядру процессора или распределения вычислений по сети. Точный график выполнения задач в конкурентной системе зависит от планировщика, и задачи не всегда должны выполняться одновременно. Например, если заданы две задачи T1 и T2:
T1 может быть выполнена и завершена до T2 или наоборот (последовательно и последовательно)
T1 и T2 могут выполняться поочередно (последовательно и конкурентно)
T1 и T2 могут выполняться одновременно в один и тот же момент времени (параллельно и конкурентно)
T1 and T2 may be executed alternately (serial and concurrent)
T1 and T2 may be executed simultaneously at the same instant of time (parallel and concurrent)
Слово "последовательный" используется как антоним для обоих слов "конкурентный" и "параллельный"; когда они явно различаются, используются пары "конкурентный/последовательный" и "параллельный/последовательный" как противоположные. График, в котором задачи выполняются одна за другой (последовательно, без параллелизма), без чередования (последовательно, без конкурентности: ни одна задача не начинается, пока не закончится предыдущая задача), называется последовательным графиком. Набор задач, которые могут быть запланированы последовательно, является сериализуемым, что упрощает управление конкуренцией.
Координация доступа к общим ресурсам
Основная проблема при разработке параллельных программ — управление конкурентным доступом: обеспечение корректной последовательности взаимодействий или обмена данными между различными вычислительными потоками и координация доступа к ресурсам, совместно используемым этими потоками.
Реализация
Для реализации параллельных программ можно использовать ряд различных методов, например, реализацию каждого вычислительного потока как процесса операционной системы или реализацию вычислительных потоков в виде набора потоков внутри одного процесса операционной системы.
Взаимодействие и общение
В некоторых системах параллельных вычислений взаимодействие между параллельными компонентами скрыто от программиста (например, с помощью фьючерсов), в то время как в других оно должно обрабатываться явно. Явное взаимодействие можно разделить на два класса:
Shared memory communication Concurrent components communicate by altering the contents of shared memory locations (exemplified by Java and C#). This style of concurrent programming usually needs the use of some form of locking (e. g., mutexes, semaphores, or monitors) to coordinate between threads. A program that properly implements any of these is said to be thread safe. Message passing communication Concurrent components communicate by exchanging messages (exemplified by MPI, Go, Scala, Erlang and occam). The exchange of messages may be carried out asynchronously, or may use a synchronous "rendezvous" style in which the sender blocks until the message is received. Asynchronous message passing may be reliable or unreliable (sometimes referred to as "send and pray"). Message passing concurrency tends to be far easier to reason about than shared memory concurrency, and is typically considered a more robust form of concurrent programming. A wide variety of mathematical theories to understand and analyze message passing systems are available, including the actor model, and various process calculi. Message passing can be efficiently implemented via symmetric multiprocessing, with or without shared memory cache coherence. Shared memory and message passing concurrency have different performance characteristics. Typically (although not always), the per process memory overhead and task switching overhead is lower in a message passing system, but the overhead of message passing is greater than for a procedure call. These differences are often overwhelmed by other performance factors.
Взаимодействие через общую память. Параллельные компоненты взаимодействуют, изменяя содержимое общих областей памяти (примеры: Java и C#). Этот стиль параллельного программирования обычно требует использования некоторой формы блокировки (например, мьютексов, семафоров или мониторов) для координации между потоками. Программа, корректно реализующая любую из этих мер, считается потокобезопасной.
Shared memory communication Concurrent components communicate by altering the contents of shared memory locations (exemplified by Java and C#). This style of concurrent programming usually needs the use of some form of locking (e. g., mutexes, semaphores, or monitors) to coordinate between threads. A program that properly implements any of these is said to be thread safe. Message passing communication Concurrent components communicate by exchanging messages (exemplified by MPI, Go, Scala, Erlang and occam). The exchange of messages may be carried out asynchronously, or may use a synchronous "rendezvous" style in which the sender blocks until the message is received. Asynchronous message passing may be reliable or unreliable (sometimes referred to as "send and pray"). Message passing concurrency tends to be far easier to reason about than shared memory concurrency, and is typically considered a more robust form of concurrent programming. A wide variety of mathematical theories to understand and analyze message passing systems are available, including the actor model, and various process calculi. Message passing can be efficiently implemented via symmetric multiprocessing, with or without shared memory cache coherence. Shared memory and message passing concurrency have different performance characteristics. Typically (although not always), the per process memory overhead and task switching overhead is lower in a message passing system, but the overhead of message passing is greater than for a procedure call. These differences are often overwhelmed by other performance factors.
Взаимодействие посредством обмена сообщениями. Параллельные компоненты взаимодействуют путем обмена сообщениями (примеры: MPI, Go, Scala, Erlang и occam). Обмен сообщениями может осуществляться асинхронно или может использоваться синхронный стиль "встречи", в котором отправитель блокируется до получения сообщения. Асинхронный обмен сообщениями может быть надежным или ненадежным (иногда называемым "отправь и молись"). Параллелизм, основанный на обмене сообщениями, как правило, гораздо проще для понимания, чем параллелизм, основанный на общей памяти, и обычно считается более надежной формой параллельного программирования. Существует широкий спектр математических теорий для понимания и анализа систем обмена сообщениями, включая акторную модель и различные исчисления процессов. Обмен сообщениями может быть эффективно реализован с помощью симметричной многопроцессорности, с когерентностью кэша общей памяти или без нее. Параллелизм, основанный на общей памяти, и параллелизм, основанный на обмене сообщениями, имеют различные характеристики производительности. Как правило (хотя и не всегда), накладные расходы на память процесса и переключение задач ниже в системе обмена сообщениями, но накладные расходы на обмен сообщениями выше, чем при вызове процедуры. Эти различия часто нивелируются другими факторами производительности.
Shared memory communication Concurrent components communicate by altering the contents of shared memory locations (exemplified by Java and C#). This style of concurrent programming usually needs the use of some form of locking (e. g., mutexes, semaphores, or monitors) to coordinate between threads. A program that properly implements any of these is said to be thread safe. Message passing communication Concurrent components communicate by exchanging messages (exemplified by MPI, Go, Scala, Erlang and occam). The exchange of messages may be carried out asynchronously, or may use a synchronous "rendezvous" style in which the sender blocks until the message is received. Asynchronous message passing may be reliable or unreliable (sometimes referred to as "send and pray"). Message passing concurrency tends to be far easier to reason about than shared memory concurrency, and is typically considered a more robust form of concurrent programming. A wide variety of mathematical theories to understand and analyze message passing systems are available, including the actor model, and various process calculi. Message passing can be efficiently implemented via symmetric multiprocessing, with or without shared memory cache coherence. Shared memory and message passing concurrency have different performance characteristics. Typically (although not always), the per process memory overhead and task switching overhead is lower in a message passing system, but the overhead of message passing is greater than for a procedure call. These differences are often overwhelmed by other performance factors.
История
Одновременные вычисления развились из более ранних работ по железным дорогам и телеграфии, начиная с XIX и начала XX века, и некоторые термины восходят к этому периоду, например, семафоры. Они возникли в связи с необходимостью решения вопроса о том, как управлять движением нескольких поездов по одной железнодорожной сети (предотвращая столкновения и повышая эффективность) и как обрабатывать несколько передач по заданному набору проводов (улучшая эффективность), например, с помощью мультиплексирования с разделением по времени (1870-е годы). Академическое изучение параллельных алгоритмов началось в 1960-х годах, и считается, что первая работа в этой области была посвящена выявлению и решению проблемы взаимного исключения.