Конкурентность в программировании: одновременное выполнение задач без влияния на результат. Структура vs. параллелизм, повышение скорости работы программ.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Способность выполнять задачу не последовательно.
Ability to execute a task in a non serial manner
В информатике, конкурентность (concurrency) – это способность различных частей или единиц программы, алгоритма или задачи выполняться в произвольном или частичном порядке, не влияя на конечный результат. Это позволяет выполнять конкурирующие (concurrent) единицы параллельно, что может значительно повысить общую скорость выполнения в многопроцессорных и многоядерных системах. В более строгих терминах, конкурентность относится к возможности разложения программы, алгоритма или задачи на компоненты или единицы вычислений, не зависящие от порядка или частично упорядоченные. По словам Роба Пайка, конкурентность – это композиция независимо выполняющихся вычислений, и конкурентность – это не параллелизм: конкурентность – это умение справляться со многими вещами одновременно, а параллелизм – это делать многие вещи одновременно. Конкурентность касается структуры, а параллелизм – исполнения; конкурентность предоставляет способ структурировать решение для задачи, которая может (но не обязательно) быть распараллелена. Для описания общей конкурентной обработки разработаны различные математические модели, включая сети Петри, исчисления процессов, модель параллельной машины с произвольным доступом к памяти, акторную модель и язык координации Reo.
In computer science, concurrency is the ability of different parts or units of a program, algorithm, or problem to be executed out of order or in partial order, without affecting the outcome. This allows for parallel execution of the concurrent units, which can significantly improve overall speed of the execution in multi processor and multi core systems. In more technical terms, concurrency refers to the decomposability of a program, algorithm, or problem into order independent or partially ordered components or units of computation. According to Rob Pike, concurrency is the composition of independently executing computations, and concurrency is not parallelism: concurrency is about dealing with lots of things at once but parallelism is about doing lots of things at once. Concurrency is about structure, parallelism is about execution, concurrency provides a way to structure a solution to solve a problem that may (but not necessarily) be parallelizable. A number of mathematical models have been developed for general concurrent computation including Petri nets, process calculi, the parallel random access machine model, the actor model and the Reo Coordination Language.
Проблемы
Поскольку вычисления в конкурентной системе могут взаимодействовать друг с другом в процессе выполнения, количество возможных путей выполнения в системе может быть чрезвычайно велико, а конечный результат – недетерминированным. Конкурентное использование общих ресурсов может быть источником недетерминированности, приводящей к таким проблемам, как взаимные блокировки и нехватка ресурсов. Разработка конкурентных систем часто включает в себя поиск надежных методов координации их выполнения, обмена данными, выделения памяти и планирования выполнения для минимизации времени отклика и максимизации пропускной способности.
Because computations in a concurrent system can interact with each other while being executed, the number of possible execution paths in the system can be extremely large, and the resulting outcome can be indeterminate. Concurrent use of shared resources can be a source of indeterminacy leading to issues such as deadlocks, and resource starvation. Design of concurrent systems often entails finding reliable techniques for coordinating their execution, data exchange, memory allocation, and execution scheduling to minimize response time and maximise throughput.
Теория
Теория параллелизма активно развивалась как область исследований в теоретической информатике. Одной из первых работ стала основополагающая работа Карла Адама Петри по сетям Петри в начале 1960-х годов. С тех пор было разработано множество формализмов для моделирования и анализа параллелизма.
Concurrency theory has been an active field of research in theoretical computer science. One of the first proposals was Carl Adam Petri's seminal work on Petri nets in the early 1960s. In the years since, a wide variety of formalisms have been developed for modeling and reasoning about concurrency.
Логика
Различные типы временной логики могут быть использованы для анализа поведения параллельных систем. Некоторые из этих логик, такие как линейная временная логика и логика дерева вычислений, позволяют формулировать утверждения о последовательностях состояний, которые может пройти параллельная система. Другие, такие как логика дерева действий, логика Хеннесси-Милнера и временная логика действий Лампорта, строят свои утверждения на основе последовательностей действий (изменений состояния). Основное применение этих логик – написание спецификаций для параллельных систем.
Various types of temporal logic can be used to help reason about concurrent systems. Some of these logics, such as linear temporal logic and computation tree logic, allow assertions to be made about the sequences of states that a concurrent system can pass through. Others, such as action computational tree logic, Hennessy–Milner logic, and Lamport's temporal logic of actions, build their assertions from sequences of actions (changes in state). The principal application of these logics is in writing specifications for concurrent systems.
Практика
Конкурентное программирование охватывает языки программирования и алгоритмы, используемые для реализации конкурентных систем. Конкурентное программирование обычно считается более общим, чем параллельное программирование, поскольку оно может включать произвольные и динамические схемы связи и взаимодействия, в то время как параллельные системы обычно имеют предопределённую и хорошо структурированную схему связи. Основные цели конкурентного программирования включают корректность, производительность и надёжность. Конкурентные системы, такие как операционные системы и системы управления базами данных, как правило, разрабатываются для неопределённо долгой работы, включая автоматическое восстановление после сбоев, и не должны завершаться неожиданно (см. Управление конкурентным доступом). Некоторые конкурентные системы реализуют форму прозрачной конкуренции, в которой конкурентные вычислительные сущности могут конкурировать за общий ресурс и совместно использовать его, но сложности этой конкуренции и совместного использования скрыты от программиста. Поскольку они используют общие ресурсы, конкурентные системы в целом требуют включения некоторого арбитра в их реализацию (часто в базовом аппаратном обеспечении) для контроля доступа к этим ресурсам. Использование арбитров вводит возможность недетерминированности в конкурентные вычисления, что имеет серьёзные последствия для практики, включая корректность и производительность. Например, арбитраж вводит неограниченный недетерминизм, что вызывает проблемы при верификации моделей, поскольку приводит к взрывному росту пространства состояний и может даже привести к тому, что модели будут иметь бесконечное число состояний. Некоторые модели конкурентного программирования включают сопроцессы и детерминированную конкуренцию. В этих моделях потоки управления явно уступают свои кванты времени либо системе, либо другому процессу.
Concurrent programming encompasses programming languages and algorithms used to implement concurrent systems. Concurrent programming is usually considered to be more general than parallel programming because it can involve arbitrary and dynamic patterns of communication and interaction, whereas parallel systems generally have a predefined and well structured communications pattern. The base goals of concurrent programming include correctness, performance and robustness. Concurrent systems such as Operating systems and Database management systems are generally designed to operate indefinitely, including automatic recovery from failure, and not terminate unexpectedly (see Concurrency control). Some concurrent systems implement a form of transparent concurrency, in which concurrent computational entities may compete for and share a single resource, but the complexities of this competition and sharing are shielded from the programmer. Because they use shared resources, concurrent systems in general require the inclusion of some kind of arbiter somewhere in their implementation (often in the underlying hardware), to control access to those resources. The use of arbiters introduces the possibility of indeterminacy in concurrent computation which has major implications for practice including correctness and performance. For example, arbitration introduces unbounded nondeterminism which raises issues with model checking because it causes explosion in the state space and can even cause models to have an infinite number of states. Some concurrent programming models include coprocesses and deterministic concurrency. In these models, threads of control explicitly yield their timeslices, either to the system or to another process.