Внимательно присмотревшись к показанному выше фрагменту, мы обнаружим еще одну потенциальную гонку, на этот раз между вызовами top() (2) и pop() (3). Представьте, что этот фрагмент исполняют два потока, ссылающиеся на один и тот же объект s типа stack. Ситуация вполне обычная: при использовании потока для повышения производительности часто бывает так, что несколько потоков исполняют один и тот же код для разных данных, и разделяемый объект stack идеально подходит для разбиения работы между потоками. Предположим, что первоначально в стеке находится два элемента, поэтому можно с уверенностью сказать, что между empty() и top() не будет гонки ни в одном потоке. Теперь рассмотрим возможные варианты выполнения программы.
Если стек защищен внутренним мьютексом, то в каждый момент времени лишь один поток может исполнять любую функцию-член стека, поэтому обращения к функциям-членам строго чередуются, тогда как вызовы do_something() могут исполняться параллельно. Вот одна из возможных последовательностей выполнения:
Поток А
- -
Поток В
if (!s.empty())
if (!s.empty())
int const value = s.top();
int const value = s.top();
s.pop();
do_something(value); s.pop();
do_something(value);
Как видите, если работают только эти два потока, то между двумя обращениями к top() никто не может модифицировать стек, так что оба потока увидят одно и то же значение. Однако беда в том, что между обращениями к pop() нет обращений к top(). Следовательно, одно из двух хранившихся в стеке значений никто даже не прочитает, оно будет просто отброшено, тогда как другое будет обработано дважды. Это еще одно состояние гонки, и куда более коварное, чем неопределенное поведение в случае гонки между empty() и top(), — на первый взгляд, ничего страшного не произошло, а последствия ошибки проявятся, скорее всего, далеко от места возникновения, хотя, конечно, всё зависит от того, что именно делает функция do_something().
Для решения проблемы необходимо более радикальное изменение интерфейса — выполнение обеих операций top() и pop() под защитой одного мьютекса. Том Каргилл[4] указал, что такой объединенный вызов приводит к проблемам в случае, когда копирующий конструктор объектов в стеке может возбуждать исключения. С точки зрения безопасности относительно исключений, задачу достаточно полно решил Герб Саттер[5], однако возможность возникновения гонки вносит в нее новый аспект.
Для тех, кто незнаком с историей вопроса, рассмотрим класс stack<vector<int>>. Вектор — это контейнер с динамически изменяемым размером, поэтому при копировании вектора библиотека должна выделить из кучи память. Если система сильно загружена или имеются жесткие ограничения на ресурсы, то операция выделения памяти может завершиться неудачно, и тогда копирующий конструктор вектора возбудит исключение std::bad_alloc. Вероятность такого развития событий особенно велика, если вектор содержит много элементов. Если бы функция pop() возвращала вытолкнутое из стека значение, а не только удаляла его из стека, то мы получили бы потенциальную проблему: вытолкнутое значение возвращается вызывающей программе только после модификации стека, но в процессе копирования возвращаемых данных может возникнуть исключение. Если такое случится, то только что вытолкнутые данные будут потеряны — из стека они удалены, но никуда не скопированы! Поэтому проектировщики интерфейса std::stack разбили операцию на две: получить элемент, находящийся на вершине (top()), а затем удалить его из стека (pop()). Теперь, данные, которые не удалось скопировать, остаются в стеке; если проблема связана с нехваткой памяти в куче, то, возможно, приложение сможет освободить немного памяти и попытаться выполнить операцию еще раз.
4
Tom Cargill «Exception Handling: A False Sense of Security» в журнале
5
Herb Sutter, Exceptional C++: 47 Engineering Puzzles, Programming Problems, and Solutions (Addison Wesley Professional, 1999).