std::cout << "do_something() заняла "
<< std::chrono::duration<
double, std::chrono::seconds>(stop-start).count()
<< " секунд" << std::endl;
Однако параметр clock объекта std::chrono::time_point<> не только определяет эпоху. Если передать момент времени функции с ожиданием, принимающей абсолютный таймаут, то указанный в нем параметр clock используется для измерения времени. Это существенно в случае, когда часы подводятся, потому что механизм ожидания замечает, что наказания часов изменились, и не дает функции вернуть управление, пока функция-член часов now() не вернет значение, большее, чем задано в таймауте. Если часы подведены вперёд, то это может уменьшить общее время ожидания (измеренное но стабильным часам), а если назадто увеличить.
Как и следовало ожидать, моменты времени применяются в вариантах функций с ожиданием, имена которых заканчиваются словом _until. Как правило, таймаут задается в виде смещения от значения some-clock::now(), вычисленного в определенной точке программы, хотя моменты времени, ассоциированные с системными часами, можно получить из time_t с помощью статической функции-члена std::chrono::system_clock::to_time_point(), если при планировании операций требуется использовать время в понятном пользователю масштабе. Например, если на ожидание события, связанного с условной переменной, отведено не более 500 мс, то можно написать такой код.
Листинг 4.11. Ожидание условной переменной с таймаутом
#include <condition_variable>
#include <mutex>
#include <chrono>
std::condition_variable cv;
bool done;
std::mutex m;
bool wait_loop() {
auto const timeout = std::chrono::steady_clock::now() +
std::chrono::milliseconds(500);
std::unique_lock<std::mutex> lk(m);
while(!done) {
if (cv.wait_until(lk, timeout) == std::cv_status::timeout)
break;
}
return done;
}
Это рекомендуемый способ ожидания условной переменной с ограничением по времени в случае, когда предикат не указывается. При этом ограничивается общее время выполнения цикла. В разделе 4.1.1 мы видели, что при использовании условных переменных без предиката цикл необходим для защиты от ложных пробуждений. Но если вызывать в цикле wait_for(), то может получиться, что функция прождёт почти все отведенное время, а затем произойдёт ложное пробуждение, после чего на следующей итерации отсчет времени начнется заново. И так может происходить сколько угодно раз, в результате чего общее время ожидания окажется неограниченным.
Вооружившись знаниями о том, как задавать таймауты, рассмотрим функции, в которых таймауты используются.
4.3.4. Функции, принимающие таймаут
Простейший случай использования таймаутазадание паузы в потоке, чтобы он не отнимал у других потоков время, когда ему нечего делать. Соответствующий пример был приведён в разделе 4.1, где мы в цикле опрашивали флаг «done». Для этого использовались функции std::this_thread::sleep_for() и std::this_thread::sleep_until(). Обе работают как будильник: поток засыпает либо на указанный интервал (в случае sleep_for()), либо до указанного момента времени (в случае sleep_until()). Функцию sleep_for() имеет смысл применять в ситуации, описанной в разделе 4.1, когда что-то необходимо делать периодически и важна лишь продолжительность периода. С другой стороны, функция sleep_until() позволяет запланировать пробуждение потока в конкретный момент времени, например: запустить в полночь резервное копирование, начать в 6 утра распечатку платёжной ведомости или приостановить поток до момента следующего обновления кадра при воспроизведении видео.
Разумеется, таймаут принимают не только функции типа sleep. Выше мы видели, что таймаут можно задавать при ожидании условных переменных и будущих результатов. А также при попытке захватить мьютекс, если сам мьютекс такую возможность поддерживает. Обычные классы std::mutex и std::recursive_mutex не поддерживают таймаут при захвате, зато его поддерживают классы std::timed_mutex и std::recursive_timed_mutex. В том и в другом имеются функции-члены try_lock_for() и try_lock_until(), которые пытаются получить блокировку в течение указанного интервала или до наступления указанного момента времени. В табл. 4.1 перечислены функции из стандартной библиотеки С++, которые принимают таймауты, их параметры и возвращаемые значения. Параметр duration должен быть объектом типа std::duration<>, а параметр time_pointобъектом типа std::time_point<>.
Таблица 4.1. Функции, принимающие таймаут
| Класс / пространство имен | Функции | Возвращаемые значения |
|---|---|---|
std::this_thread пространство имен | sleep_for(duration) sleep_until(time_point) | Неприменимо |
std::condition_variable или std::condition_variable_any | wait_for(lock, duration) wait_until(lock, time_point) | std::cv_status::timeout или std::cv_status::no_timeout |
wait_for(lock, duration, predicate) wait_until(lock, time_point, predicate) | bool значение, возвращенное предикатом predicate при пробуждении | |
std::timed_mutex или std::recursive_timed_mutex | try_lock_for(duration) try_lock_until(time_point) | bool true, если мьютекс захвачен, иначе false |
std::unique_lock<TimedLockable> | unique_lock(lockable, duration) unique_lock(lockable, time_point) | Неприменимо функция owns_lock() для вновь сконструированного объекта возвращает true, если мьютекс захвачен, иначе false |
try_lock_for(duration) try_lock_until(time_point) | bool true, если мьютекс захвачен, иначе false | |
std::future<ValueType> или std::shared_future<ValueType> | wait_for(duration) wait_until(time_point) | std::future_status::timeout, если истек таймаут, std::future_status::ready, если будущий результат готов, std::future_status::deferred, если в будущем результате хранится отложенная функция, которая еще не начала исполняться |
Теперь, когда мы рассмотрели условные переменные, будущие результаты, обещания и упакованные задачи, настало время представить более широкую картину их применения для синхронизации операций, выполняемых в разных потоках.
4.4. Применение синхронизации операций для упрощения кода
Использование описанных выше средств синхронизации в качестве строительных блоков позволяет сосредоточиться на самих нуждающихся в синхронизации операциях, а не на механизмах реализации. В частности, код можно упростить, применяя более функциональный (в смысле функционального программирования) подход к программированию параллелизма. Вместо того чтобы напрямую разделять данные между потоками, мы можем снабдить каждый поток необходимыми ему данными, а результаты вычисления предоставить другим потокам, которые в них заинтересованы, с помощью будущих результатов.
4.4.1. Функциональное программирование с применением будущих результатов
Термином функциональное программирование (ФП) называют такой стиль программирования, при котором результат функции зависит только от ее параметров, но не от внешнего состояния. Это напрямую соотносится с понятием функции в математике и означает, что если два раза вызвать функцию с одними и теми же параметрами, то получатся одинаковые результаты. Таким свойством обладают многие математические функции в стандартной библиотеке С++, например sin, cos и sqrt, а также простые операции над примитивными типами, например 3+3, 6*9 или 1.3/4.7. Чистая функция не модифицирует никакое внешнее состояние, она воздействует только на возвращаемое значение.
При таком подходе становится проще рассуждать о функциях, особенно в присутствии параллелизма, поскольку многие связанные с разделяемой памятью проблемы, обсуждавшиеся в главе 3, просто не возникают. Если разделяемые данные не модифицируются, то не может быть никакой гонки и, стало быть, не нужно защищать данные с помощью мьютексов. Это упрощение настолько существенно, что в программировании параллельных систем все более популярны становятся такие языки, как Haskell, где все функции чистые по умолчанию. В таком окружении нечистые функции, которые все же модифицируют разделяемые данные, отчетливо выделяются, поэтому становится проще рассуждать о том, как они укладываются в общую структуру приложения.
Но достоинства функционального программирования проявляются не только в языках, где эта парадигма применяется по умолчанию. С++мультипарадигменный язык, и на нем, безусловно, можно писать программы в стиле ФП. С появлением в С++11 лямбда-функций (см. приложение А, раздел А.6), включением шаблона std::bind из Boost и TR1 и добавлением автоматического выведения типа переменных (см. приложение А, раздел А.7) это стало даже проще, чем в С++98. Будущие результатыэто последний элемент из тех, что позволяют реализовать на С++ параллелизм в стиле ФП; благодаря передаче будущих результатов результат одного вычисления можно сделать зависящим от результата другого без явного доступа к разделяемым данным.
Быстрая сортировка в духе ФП
Чтобы продемонстрировать использование будущих результатов при написании параллельных программ в духе ФП, рассмотрим простую реализацию алгоритма быстрой сортировки Quicksort. Основная идея алгоритма проста: имея список значений, выбрать некий опорный элемент и разбить список на две частив одну войдут элементы, меньшие опорного, в другую большие или равные опорному. Отсортированный список получается путем сортировки обоих частей и объединения трех списков: отсортированного множества элементов, меньших опорного элемента, самого опорного элемента и отсортированного множества элементов, больших или равных опорному элементу. На рис. 4.2 показано, как этот алгоритм сортирует список из 10 целых чисел. В листинге ниже приведена последовательная реализация алгоритма в духе ФП; в ней список принимается и возвращается по значению, а не сортируется по месту в std::sort().
Рис. 4.2. Рекурсивная сортировка в духе ФП
Листинг 4.12. Последовательная реализация Quicksort в духе ФП
template<typename T>
std::list<T> sequential_quick_sort(std::list<T> input) {
if (input.empty()) {
return input;
}
std::list<T> result;
result.splice(result.begin(), input, input.begin());(1)
T const& pivot = *result.begin(); (2)
auto divide_point = std::partition(input.begin(), input.end(),
[&](T const& t) { return t < pivot; });(3)
std::list<T> lower_part;
lower_part.splice(
lower_part.end(), input, input.begin(), divide_point); (4)
auto new_lower(
sequential_quick_sort(std::move(lower_part))); (5)
auto new_higher(
sequential_quick_sort(std::move(input))); (6)
result.splice(result.end(), new_higher); (7)
result.splice(result.begin(), new_lower); (8)
return result;
}
Хотя интерфейс выдержан в духе ФП, прямое применение ФП привело бы к неоправданно большому числу операций копирования, поэтому внутри мы используем «обычный» императивный стиль. В качестве опорного мы выбираем первый элемент и отрезаем его от списка с помощью функции splice() (1). Потенциально это может привести к неоптимальной сортировке (в терминах количества операций сравнения и обмена), но любой другой подход при работе с std::list может существенно увеличить время за счет обхода списка. Мы знаем, что этот элемент должен войти в результат, поэтому можем сразу поместить его в список, где результат будет храниться. Далее мы хотим использовать этот элемент для сравнения, поэтому берем ссылку на него, чтобы избежать копирования (2). Теперь можно с помощью алгоритма std::partition разбить последовательность на две части: меньшие опорного элемента и не меньшие опорного элемента (3). Критерий разбиения проще всего задать с помощью лямбда-функции; мы запоминаем ссылку в замыкании, чтобы не копировать значение pivot (подробнее о лямбда-функциях см. в разделе А.5 приложения А).
Алгоритм std::partition() переупорядочивает список на месте и возвращает итератор, указывающий на первый элемент, который не меньше опорного значения. Полный тип итератора довольно длинный, поэтому мы используем спецификатор типа auto, чтобы компилятор вывел его самостоятельно (см. приложение А, раздел А.7).
Раз уж мы выбрали интерфейс в духе ФП, то для рекурсивной сортировки обеих «половин» нужно создать два списка. Для этого мы снова используем функцию splice(), чтобы переместить значения из списка input до divide_point включительно в новый список lower_part (4). После этого input будет со держать только оставшиеся значения. Далее оба списка можно отсортировать путем рекурсивных вызовов (5), (6). Применяя std::move() для передачи списков, мы избегаем копированиярезультат в любом случае неявно перемещается. Наконец, мы еще раз вызываем splice(), чтобы собрать result в правильном порядке. Значения из списка new_higher попадают в конец списка (7), после опорного элемента, а значения из списка new_lowerв начало списка, до опорного элемента (8).
Параллельная реализация Quicksort в духе ФП
Раз уж мы все равно применили функциональный стиль программирования, можно без труда распараллелить этот код с помощью будущих результатов, как показано в листинге ниже. Набор операций тот же, что и раньше, только некоторые из них выполняются параллельно.
Листинг 4.13. Параллельная реализация Quicksort с применением будущих результатов
template<typename T>
std::list<T> parallel_quick_sort(std::list<T> input) {
if (input.empty()) {
return input;
}
std::list<T> result;
result.splice(result.begin(), input, input.begin());