Энтони Уильямс - Параллельное программирование на С++ в действии. Практика разработки многопоточных программ

template 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 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()под защитой одного мьютекса. Том Каргилл [4] Tom Cargill «Exception Handling: A False Sense of Security» в журнале C++ Report 6, № 9 (ноябрь-декабрь 1994). Доступна также по адресу http://www.informit.com/content/images/020163371х/supplements/Exception_Handling_Article.html. указал, что такой объединенный вызов приводит к проблемам в случае, когда копирующий конструктор объектов в стеке может возбуждать исключения. С точки зрения безопасности относительно исключений, задачу достаточно полно решил Герб Саттер [5] Herb Sutter, Exceptional C++: 47 Engineering Puzzles, Programming Problems, and Solutions (Addison Wesley Professional, 1999). , однако возможность возникновения гонки вносит в нее новый аспект.