Параллельные алгоритмы имеют параметры шаблона, названные, ExecutionPolicy которые описывают способ, которым выполнение этих алгоритмов может быть распараллелено, и способ, которым они применяют функции доступа к элементам.
Если не указано иное, реализации могут делать произвольные копии элементов (с типом T) из последовательностей where is_trivially_copy_constructible_v<T> и is_trivially_destructible_v<T> are true. [ Note: Это означает, что объекты функций, предоставляемые пользователем, не должны полагаться на идентичность объекта аргументов для таких входных последовательностей. Пользователи, для которых важна идентичность аргументов этих функциональных объектов, должны рассмотреть возможность использования итератора-оболочки, который возвращает не скопированный объект реализации, такой как reference_wrapper<T> ([refwrap]), или какое-либо эквивалентное решение. ] — end note
Вызов функций доступа к элементам в параллельных алгоритмах, вызываемых с помощью объекта политики выполнения типа, execution::sequenced_policy все происходит в вызывающем потоке выполнения. [ Note: Вызовы не чередуются; см [intro.execution]. ] — end note
Вызов функций доступа к элементам в параллельных алгоритмах, вызываемых с помощью объекта политики выполнения типа execution::parallel_policy , разрешается выполнять либо в вызывающем потоке выполнения, либо в потоке выполнения, неявно созданном библиотекой для поддержки выполнения параллельного алгоритма. Если потоки выполнения, созданные с помощью thread provide concurrent forward progress guarantees, то поток выполнения, неявно созданный библиотекой, будет обеспечивать параллельные гарантии продвижения вперед; в противном случае предоставленная гарантия продвижения вперед определяется реализацией. Любые такие вызовы, выполняемые в одном и том же потоке выполнения, имеют неопределенную последовательность относительно друг друга. [ Note: Вызывающая сторона несет ответственность за то, чтобы вызов не привел к скачкам данных или взаимоблокировкам. ] [ — end note Example:
int a[] = {0,1};
std::vector<int> v;
std::for_each(std::execution::par, std::begin(a), std::end(a), [&](int i) {
v.push_back(i*2+1); // incorrect: data race
});Программа выше имеет гонку данных из-за несинхронизированного доступа к контейнеру v. ] [ — end example Example:
std::atomic<int> x{0};
int a[] = {1,2};
std::for_each(std::execution::par, std::begin(a), std::end(a), [&](int) {
x.fetch_add(1, std::memory_order_relaxed);
// spin wait for another iteration to change the value of x
while (x.load(std::memory_order_relaxed) == 1) { } // incorrect: assumes execution order
});Приведенный выше пример зависит от порядка выполнения итераций и не завершится, если обе итерации выполняются последовательно в одном и том же потоке выполнения. ] [ — end example Example:
int x = 0;
std::mutex m;
int a[] = {1,2};
std::for_each(std::execution::par, std::begin(a), std::end(a), [&](int) {
std::lock_guard<mutex> guard(m);
++x;
});В приведенном выше примере синхронизируется доступ к объекту, x гарантируя, что он увеличивается правильно. ] — end example
Вызовы функций доступа к элементам в параллельных алгоритмах, вызываемых политикой выполнения типа execution::parallel_unsequenced_policy , разрешается выполнять неупорядоченным образом в неуказанных потоках выполнения и неупорядоченно по отношению друг к другу в каждом потоке выполнения. Эти потоки выполнения являются либо вызывающим потоком выполнения, либо потоками выполнения, неявно созданными библиотекой; последний будет обеспечивать слабо параллельные гарантии продвижения вперед. [ Note: Это означает, что вызовы нескольких функциональных объектов могут чередоваться в одном потоке выполнения, что отменяет обычную гарантию того, [intro.execution] что выполнение функций не чередуется друг с другом. ] Поскольку позволяет чередовать выполнение функций доступа к элементам в одном потоке выполнения, блокирующая синхронизация, включая использование мьютексов, может привести к тупиковой ситуации. Таким образом, синхронизация с ограничивается следующим образом: стандартная библиотечная функция - это если она указана для синхронизации с вызовом другой функции, или если для синхронизации с ней указан вызов другой функции, и если это не функция выделения или освобождения памяти. Небезопасные для векторизации функции стандартной библиотеки не могут быть вызваны пользовательским кодом, вызываемым из алгоритмов. [ Реализации должны гарантировать, что внутренняя синхронизация внутри стандартных библиотечных функций не препятствует продвижению вперед, когда эти функции выполняются потоками исполнения со слабо параллельными гарантиями продвижения вперед. ] [ — end note execution::parallel_unsequenced_policy execution::parallel_unsequenced_policy vectorization-unsafe execution::parallel_unsequenced_policy Note: — end note Example:
int x = 0;
std::mutex m;
int a[] = {1,2};
std::for_each(std::execution::par_unseq, std::begin(a), std::end(a), [&](int) {
std::lock_guard<mutex> guard(m); // incorrect: lock_guard constructor calls m.lock()
++x;
});Вышеупомянутая программа может привести к двум последовательным вызовам m.lock() в одном и том же потоке выполнения (что может привести к взаимной блокировке), потому что приложения объекта функции не гарантированно работают в разных потоках выполнения. ] [ Семантика вызова или позволяет реализации вернуться к последовательному выполнению, если система не может распараллелить вызов алгоритма из-за нехватки ресурсов. ] — end example Note: execution::parallel_policy execution::parallel_unsequenced_policy — end note
Если при вызове параллельного алгоритма используются потоки выполнения, неявно созданные библиотекой, то вызывающий поток выполнения будет либо
временно блокировать с делегированием гарантии продвижения вперед ([intro.progress]) по завершении этих управляемых библиотекой потоков выполнения, или
в конечном итоге выполнить функцию доступа к элементу;
поток выполнения будет продолжать делать это до тех пор, пока алгоритм не будет завершен. [ Note: При блокировке с делегированием гарантии продвижения вперед в этом контексте поток выполнения, созданный библиотекой, считается завершенным, как только он завершил выполнение конкретной функции доступа к элементу, от которой логически зависит вызывающий поток выполнения. ] — end note