Однако и после обеспечения безопасности отдельных операций наши неприятности еще не закончилисьгонки все еще возможны, даже для самого простого интерфейса. Рассмотрим структуру данных для реализации стека, например, адаптер контейнера std::stack, показанный в листинге 3.3. Помимо конструкторов и функции swap(), имеется еще пять операций со стеком: push() заталкивает в стек новый элемент, pop() выталкивает элемент из стека, top() возвращает элемент, находящийся на вершине стека, empty() проверяет, пуст ли стек, и size() возвращает размер стека. Если изменить top(), так чтобы она возвращала копию, а не ссылку (в соответствии с рекомендацией из раздела 3.2.2), и защитить внутренние данные мьютексом, то и тогда интерфейс уязвим для гонки. Проблема не в реализации на основе мьютексов, она присуща самому интерфейсу, то есть гонка может возникать даже в реализации без блокировок.
Листинг 3.3. Интерфейс адаптера контейнера std::stack
template<typename T, typename Container = std::deque<T> >
class stack {
public:
explicit stack(const Container&);
explicit stack(Container&& = Container());
template <class Alloc> explicit stack(const Alloc&);
template <class Alloc> stack(const Container&, const Alloc&);
template <class Alloc> stack(Container&&, const Alloc&);
template <class Alloc> stack(stack&&, const Alloc&);
bool empty() const;
size_t size() const;
T& top();
T const& top() const;
void push(T const&);
void push(T&&);
void pop();
void swap(stack&&);
};
Проблема в том, что на результаты, возвращенные функциями empty() и size(), нельзя полагатьсяхотя в момент вызова они, возможно, и были правильны, но после возврата из функции любой другой поток может обратиться к стеку и затолкнуть в него новые элементы, либо вытолкнуть существующие, причем это может произойти до того, как у потока, вызвавшего empty() или size(), появится шанс воспользоваться полученной информацией.
Если экземпляр stack не является разделяемым, то нет ничего страшного в том, чтобы проверить, пуст ли стек с помощью empty(), а затем, если стек не пуст, вызвать top() для доступа к элементу на вершине стека:
stack<int> s;
if (!s.empty()) (1)
{
int const value = s.top(); (2)
s.pop(); (3)
do_something(value);
}
Такой подход в однопоточном коде не только безопасен, но и единственно возможен: вызов top() для пустого стека приводит к неопределенному поведению. Но если объект stack является разделяемым, то такая последовательность операций уже не безопасна, так как между вызовами empty() (1) и top() (2) другой поток мог вызвать pop() и удалить из стека последний элемент. Таким образом, мы имеем классическую гонку, и использование внутреннего мьютекса для защиты содержимого стека ее не предотвращает. Это следствие дизайна интерфейса.
И что же делать? Поскольку проблема коренится в дизайне интерфейса, то и решать ее надо путем изменения интерфейса. Но возникает вопросакак его изменить? В простейшем случае мы могли бы просто декларировать, что top() возбуждает исключение, если в момент вызова в стеке нет ни одного элемента. Формально это решает проблему, но затрудняет программирование, поскольку теперь мы должны быть готовы к перехвату исключения, даже если вызов empty() вернул false. По сути дела, вызов empty() вообще оказывается ненужным.
Внимательно присмотревшись к показанному выше фрагменту, мы обнаружим еще одну потенциальную гонку, на этот раз между вызовами 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() под защитой одного мьютекса. Том Каргилл указал, что такой объединенный вызов приводит к проблемам в случае, когда копирующий конструктор объектов в стеке может возбуждать исключения. С точки зрения безопасности относительно исключений, задачу достаточно полно решил Герб Саттер, однако возможность возникновения гонки вносит в нее новый аспект.
Для тех, кто незнаком с историей вопроса, рассмотрим класс stack<vector<int>>. Векторэто контейнер с динамически изменяемым размером, поэтому при копировании вектора библиотека должна выделить из кучи память. Если система сильно загружена или имеются жесткие ограничения на ресурсы, то операция выделения памяти может завершиться неудачно, и тогда копирующий конструктор вектора возбудит исключение std::bad_alloc. Вероятность такого развития событий особенно велика, если вектор содержит много элементов. Если бы функция pop() возвращала вытолкнутое из стека значение, а не только удаляла его из стека, то мы получили бы потенциальную проблему: вытолкнутое значение возвращается вызывающей программе только после модификации стека, но в процессе копирования возвращаемых данных может возникнуть исключение. Если такое случится, то только что вытолкнутые данные будут потеряныиз стека они удалены, но никуда не скопированы! Поэтому проектировщики интерфейса std::stack разбили операцию на две: получить элемент, находящийся на вершине (top()), а затем удалить его из стека (pop()). Теперь, данные, которые не удалось скопировать, остаются в стеке; если проблема связана с нехваткой памяти в куче, то, возможно, приложение сможет освободить немного памяти и попытаться выполнить операцию еще раз.
Увы, это как раз то разбиение, которого мы пытались избежать в попытке уйти от гонки! К счастью, альтернативы имеются, но они не бесплатны.