Объекты типа std::thread::id можно без ограничений копировать и сравнивать, в противном случае они вряд ли могли бы играть роль идентификаторов. Если два объекта типа std::thread::id равны, то либо они представляют один и тот же поток, либо оба содержат значение «не поток». Если же два таких объекта не равны, то либо они представляют разные потоки, либо один представляет поток, а другой содержит значение «не поток».
Библиотека Thread Library не ограничивается сравнением идентификаторов потоков на равенство, для объектов типа std::thread::id определен полный спектр операторов сравнения, то есть на множестве идентификаторов потоков задан полный порядок. Это позволяет использовать их в качестве ключей ассоциативных контейнеров, сортировать и сравнивать любым интересующим программиста способом. Поскольку операторы сравнения определяют полную упорядоченность различных значений типа std::thread::id, то их поведение интуитивно очевидно: если a<b и b<c то а<с и так далее. В стандартной библиотеке имеется также класс std::hash<std::thread::id>, поэтому значения типа std::thread::id можно использовать и в качестве ключей новых неупорядоченных ассоциативных контейнеров.
Объекты std::thread::id часто применяются для того, чтобы проверить, должен ли поток выполнить некоторую операцию. Например, если потоки используются для разбиения задач, как в листинге 2.8, то начальный поток, который запускал все остальные, может вести себя несколько иначе, чем прочие. В таком случае этот поток мог бы сохранить значение std::this_thread::get_id() перед тем, как запускать другие потоки, а затем в основной части алгоритма (общей для всех потоков) сравнить собственный идентификатор с сохраненным значением.
std::thread::id master_thread;
void some_core_part_of_algorithm() {
if (std::this_thread::get_id() == master_thread) {
do_master_thread_work();
}
do_common_work();
}
Или можно было бы сохранить std::thread::id текущего потока в некоторой структуре данных в ходе выполнения какой-то операции. В дальнейшем при операциях с той же структурой данных можно было сравнить сохраненный идентификатор с идентификатором потока, выполняющего операцию, и решить, какие операции разрешены или необходимы.
Идентификаторы потоков можно было бы также использовать как ключи ассоциативных контейнеров, если с потоком нужно ассоциировать какие-то данные, а другие механизмы, например поточно-локальная память, не подходят. Например, управляющий поток мог бы сохранить в таком контейнере информацию о каждом управляемом им потоке. Другое применение подобного контейнера передавать информацию между потоками.
Идея заключается в том, что в большинстве случаев std::thread::id вполне может служить обобщенным идентификатором потока и лишь, если с идентификатором необходимо связать какую-то семантику (например, использовать его как индекс массива), может потребоваться другое решение. Можно даже выводить объект std::thread::id в выходной поток, например std::cout:
std::cout << std::this_thread::get_id();
Точный формат вывода зависит от реализации; стандарт лишь гарантирует, что результаты вывода одинаковых идентификаторов потоков будут одинаковы, а разных различаться. Поэтому для отладки и протоколирования это может быть полезно, но так как никакой семантики у значений идентификаторов нет, то сделать на их основе какие-то другие выводы невозможно.
2.6. Резюме
В этой главе мы рассмотрели основные средства управления потоками, имеющиеся в стандартной библиотеке С++: запуск потоков, ожидание завершения потока и отказ от ожидания вследствие того, что поток работает в фоновом режиме. Мы также научились передавать аргументы функции потока при запуске и передавать ответственность за управление потоком из одной части программы в другую. Кроме того, мы видели, как можно использовать группы потоков для разбиения задачи на части. Наконец, мы обсудили механизм идентификации потоков, позволяющий ассоциировать с потоком данные или поведение в тех случаях, когда использовать другие средства неудобно. Даже совершенно независимые потоки позволяют сделать много полезного, как видно из листинга 2.8, но часто требуется, чтобы работающие потоки обращались к каким-то общим данным. В главе 3 рассматриваются проблемы, возникающие при разделении данных между потоками, а в главе 4более общие вопросы синхронизации операций с использованием и без использования разделяемых данных.
Глава 3.Разделение данных между потоками
В этой главе:
Проблемы разделения данных между потоками.
Защита данных с помощью мьютексов.
Альтернативные средства защиты разделяемых данных.
Одно из основных достоинств применения потоков для реализации параллелизма возможность легко и беспрепятственно разделять между ними данные, поэтому, уже зная, как создавать потоки и управлять ими, мы обратимся к вопросам, связанным с разделением данных.
Представьте, что вы живете в одной квартире с приятелем. В квартире только одна кухня и только одна ванная. Если ваши отношения не особенно близки, то вряд ли вы будете пользоваться ванной одновременно, поэтому, когда сосед слишком долго занимает ванную, у вас возникает законное недовольство. Готовить два блюда одновременно, конечно, можно, но если у вас духовка совмещена с грилем, то ничего хорошего не выйдет, когда один пытается жарить сосиски, а другойпечь пирожные. Ну и все мы знаем, какую досаду испытываешь, когда, сделав половину работы, обнаруживаешь, что кто-то забрал нужный инструмент или изменил то, что вы уже сделали.
То же самое и с потоками. Если потоки разделяют какие-то данные, то необходимы правила, регулирующие, какой поток в какой момент к каким данным может обращаться и как сообщить об изменениях другим потокам, использующим те же данные. Легкость, с которой можно разделять данные между потоками в одном процессе, может обернуться не только благословением, но проклятием. Некорректное использование разделяемых данных одна из основных причин ошибок, связанных с параллелизмом, и последствия могут оказаться куда серьезнее, чем пропахшие сосисками пирожные.
Эта глава посвящена вопросу о том, как безопасно разделять данные между потоками в программе на С++, чтобы избежать возможных проблем и достичь оптимального результата.
3.1. Проблемы разделения данных между потоками
Все проблемы разделения данных между потоками связаны с последствиями модификации данных. Если разделяемые данные только читаются, то никаких сложностей не возникает, поскольку любой поток может читать данные независимо от того, читают их в то же самое время другие потоки или нет. Но стоит одному или нескольким потокам начать модифицировать разделяемые данные, как могут возникнуть неприятности. В таком случае ответственность за правильную работу ложится на программиста.
При рассуждениях о поведении программы часто помогает понятие инварианта утверждения о структуре данных, которое всегда должно быть истинным, например, «значение этой переменной равно числу элементов в списке». В процессе обновления инварианты часто нарушаются, особенно если структура данных сложна или обновление затрагивает несколько значений.
Рассмотрим двусвязный список, в котором каждый узел содержит указатели на следующий и предыдущий узел. Один из инвариантов формулируется так: если «указатель на следующий» в узле А указывает на узел В, то «указатель на предыдущий» в узле В указывает на узел А. Чтобы удалить узел из списка, необходимо обновить узлы по обе стороны от него, так чтобы они указывали друг на друга. После обновления одного узла инвариант оказывается нарушен и остается таковым, пока не будет обновлен узел по другую сторону. После того как обновление завершено, инвариант снова выполняется.
Шаги удаления узла из списка показаны на рис. 3.1:
1. Найти подлежащий удалению узел (N).
2. Изменить «указатель на следующий» в узле, предшествующем N, так чтобы он указывал на узел, следующий за N.
3. Изменить «указатель на предыдущий» в узле, следующем за N, так чтобы он указывал на узел, предшествующий N.
4. Удалить узел N.
Рис. 3.1. Удаление узла из двусвязного списка
Как видите, между шагами b и с указатели в одном направлении не согласуются с указателями в другом направлении, и инвариант нарушается.
Простейшая проблема, которая может возникнуть при модификации данных, разделяемых несколькими потоками,нарушение инварианта. Если не предпринимать никаких мер, то в случае, когда один поток читает двусвязный список, а другой в это же время удаляет из списка узел, вполне может случиться, что читающий поток увидит список, из которого узел удален лишь частично (потому что изменен только один указатель, как на шаге b на рис. 3.1), так что инвариант нарушен. Последствия могут быть разнымиесли поток читает список слева направо, то он просто пропустит удаляемый узел. Но если другой поток пытается удалить самый правый узел, показанный на рисунке, то он может навсегда повредить структуру данных, и в конце концов это приведет к аварийному завершению программы. Как бы то ни было, этот пример иллюстрирует одну из наиболее распространенных причин ошибок в параллельном коде: состояние гонки (race condition).
3.1.1. Гонки
Предположим, вы покупаете билеты в кино. Если кинотеатр большой, то в нем может быть несколько касс, так что в каждый момент времени билеты могут покупать несколько человек. Если кто-то покупает билет на тот же фильм, что и вы, но в другой кассе, то какие места вам достанутся, зависит от того, кто был первым. Если осталось всего несколько мест, то разница может оказаться решающей: за последние билеты возникает гонка в самом буквальном смысле. Это и есть пример состояния гонки: какие места вам достанутся (да и достанутся ли вообще), зависит от относительного порядка двух покупок.
В параллельном программировании под состоянием гонки понимается любая ситуация, исход которой зависит от относительного порядка выполнения операций в двух или более потокахпотоки конкурируют за право выполнить операции первыми. Как правило, ничего плохого в этом нет, потому что все исходы приемлемы, даже если их взаимный порядок может меняться. Например, если два потока добавляют элементы в очередь для обработки, то вообще говоря неважно, какой элемент будет добавлен первым, лишь бы не нарушались инварианты системы. Проблема возникает, когда гонка приводит к нарушению инвариантов, как в приведенном выше примере удаления из двусвязного списка. В контексте параллельного программирования состоянием гонки обычно называют именно такую проблематичную гонкубезобидные гонки не так интересны и к ошибкам не приводят. В стандарте С++ определен также термин гонка за данными (data race), означающий ситуацию, когда гонка возникает из-за одновременной модификации одного объекта (детали см. в разделе 5.1.2); гонки за данными приводят к внушающему ужас неопределенному поведению.
Проблематичные состояния гонки обычно возникают, когда для завершения операции необходимо модифицировать два или более элементов данных, например два связующих указателя в примере выше. Поскольку элементов несколько, то их модификация производится разными командами, и может случиться, что другой поток обратится к структуре данных в момент, когда завершилась только одна команда. Зачастую состояние гонки очень трудно обнаружить и воспроизвести, поскольку она происходит в очень коротком интервале времени,если модификации производятся последовательными командами процессора, то вероятность возникновения проблемы при конкретном прогоне очень мала, даже если к структуре данных одновременно обращается другой поток. По мере увеличения нагрузки на систему и количества выполнений операции вероятность проблематичной последовательности выполнения возрастает. И, разумеется, почти всегда такие ошибки проявляются в самый неподходящий момент. Поскольку состояние гонки так чувствительно ко времени, оно может вообще не возникнуть при запуске приложения под отладчиком, так как отладчик влияет на хронометраж программ, пусть и незначительно.
При написании многопоточных программ гонки могут изрядно отравить жизньсвоей сложностью параллельные программы в немалой степени обязаны стараниям избежать проблематичных гонок.
3.1.2. Устранение проблематичных состояний гонки
Существует несколько способов борьбы с проблематичными гонками. Простейший из них - снабдить структуру данных неким защитным механизмом, который гарантирует, что только поток, выполняющий модификацию, может видеть промежуточные состояния, в которых инварианты нарушены; с точки зрения всех остальных потоков, обращающихся к той же структуре данных, модификация либо еще не началась, либо уже завершилась. В стандартной библиотеке С++ есть несколько таких механизмов, и в этой главе мы их опишем.
Другой вариантизменить дизайн структуры данных и ее инварианты, так чтобы модификация представляла собой последовательность неделимых изменений, каждое из которых сохраняет инварианты. Этот подход обычно называют программированием без блокировок (lock-free programming) и реализовать его правильно очень трудно; если вы работаете на этом уровне, то приходится учитывать нюансы модели памяти и разбираться, какие потоки потенциально могут увидеть те или иные наборы значений. Модель памяти обсуждается в главе 5, а программирование без блокировокв главе 7.
Еще один способ справиться с гонкамирассматривать изменения структуры данных как транзакцию, то есть так, как обрабатываются обновления базы данных внутри транзакции. Требуемая последовательность изменений и чтений данных сохраняется в журнале транзакций, а затем атомарно фиксируется. Если фиксация невозможна, потому что структуру данных в это время модифицирует другой поток, то транзакция перезапускается. Это решение называется программной транзакционной памятью (Software Transactional MemorySTM), в настоящее время в этой области ведутся активные исследования. Мы не будем рассматривать STM в этой книге, потому что в С++ для нее нет поддержки. Однако к самой идее о том, чтобы выполнить какую-то последовательность действий и за один шаг зафиксировать результаты, я еще вернусь.
Самый простой механизм защиты разделяемых данных из описанных в стандарте С++это мьютекс, с него мы и начнем рассмотрение.
3.2. Защита разделяемых данных с помощью мьютексов
Итак, у нас есть разделяемая структура данных, например связанный список из предыдущего раздела, и мы хотим защитить его от гонки и нарушения инвариантов, к которым она приводит. Как было бы здорово, если бы мы могли пометить участки кода, в которых производятся обращения к этой структуре данных, взаимно исключающими, так что если один поток начинает выполнять такой участок, то все остальные потоки должны ждать, пока первый не завершит обработку данных. Тогда ни один поток, кроме выполняющего модификацию, не смог бы увидеть нарушенный инвариант.
Что ж, это вовсе не сказкаименно такое поведение вы получаете при использовании примитива синхронизации, который называется мьютекс (слово mutex происходит от mutual exclusionвзаимное исключение). Перед тем как обратиться к структуре данных, программа захватывает (lock) мьютекс, а по завершении операций с ней освобождает (unlock) его. Библиотека Thread Library гарантирует, что если один поток захватил некоторый мьютекс, то все остальные потоки, пытающиеся захватить тот же мьютекс, будут вынуждены ждать, пока удачливый конкурент не освободит его. В результате все потоки видят согласованное представление разделяемых данных, без нарушенных инвариантов.
Мьютексынаиболее общий механизм защиты данных в С++, но панацеей они не являются; важно структурировать код так, чтобы защитить нужные данные (см. раздел 3.2.2), и избегать состояний гонки, внутренне присущих интерфейсам (см раздел 3.2.3). С мьютексами связаны и собственные проблемы, а именно: взаимоблокировки (deadlock) (см. раздел 3.2.4), а также защита слишком большого или слишком малого количества данных (см. раздел 3.2.8). Но начнем с простого.