Вариант 1: передавать ссылку
Первый вариант решенияпередавать функции pop() ссылку на переменную, в которую она должна будет поместить вытолкнутое из стека значение:
std::vector<int> result;
some_stack.pop(result);
Во многих случаях это приемлемо, но есть и очевидный недостаток: вызывающая программа должна до обращения к функции сконструировать объект того типа, которым конкретизирован стек, чтобы передать его в качестве аргумента. Для некоторых типов это не годится, так как конструирование дорого обходится с точки зрения времени или потребления ресурсов. Для других типов это вообще может оказаться невозможно, так как конструкторы требуют параметров, которые в данной точке программы могут быть недоступны. Наконец, требуется, чтобы хранящийся в стеке тип допускал присваивание. Это существенное ограничение, многие пользовательские типы не поддерживают присваивание, хотя могут поддерживать конструирование перемещением и даже копированием (и потому допускают возврат по значению).
Вариант 2: потребовать наличия копирующего конструктора, не возбуждающего исключений, или перемещающего конструктора
Проблема с безопасностью относительно исключений в варианте функции pop(), возвращающей значение, проявляется только тогда, когда исключение может возникать в процессе возврата значения. Во многих типах имеются копирующие конструкторы, которые не возбуждают исключений, а после поддержки в стандарте С++ ссылок на r-значения (см. приложение А, раздел А.1), появилось еще много типов, в которых перемещающий конструктор не возбуждает исключений, даже если копирующий конструктор может их возбуждать. Один из вариантов решения заключается в том, чтобы наложить на потокобезопасный стек ограничение: в нем можно хранить только типы, поддерживающие возврат по значению без возбуждения исключений.
Это решение, пусть и безопасное, не идеально. Хотя на этапе компиляции можно узнать, существует ли копирующий или перемещающий конструктор, который не возбуждает исключений,с помощью концепций std::is_nothrow_copy_constructible, std::is_nothrow_move_constructible и характеристик типов, но это слишком ограничительное требование. Пользовательских типов, в которых копирующий конструктор может возбуждать исключение и перемещающего конструктора нет, гораздо больше, чем типов, в которых копирующий и (или) перемещающий конструктор гарантированно не возбуждают исключений (хотя ситуация может измениться, когда разработчики привыкнут к появившейся в С++11 поддержке ссылок на r-значения). Было бы крайне нежелательно запрещать хранение таких объектов в потокобезопасном стеке.
Вариант 3: возвращать указатель на вытолкнутый элемент
Третий вариантвозвращать не копию вытолкнутого элемента по значению, а указатель на него. Его достоинство в том, указатели можно копировать, не опасаясь исключений, поэтому указанную Каргиллом проблему мы обходим. А недостаток в том, что возврат указателя заставляет искать средства для управления выделенной объекту памятью, так что для таких простых типов, как целые числа, накладные расходы на управление памятью могут превысить затраты на возврат типа по значению. В любом интерфейсе, где применяется этот вариант, в качестве типа указателя было бы разумно избрать std::shared_ptr; мало того что это предотвращает утечки памяти, поскольку объект уничтожается вместе с уничтожением последнего указателя на него, так еще и библиотека полностью контролирует схему распределения памяти и не требует использования new и delete. Это существенно с точки зрения оптимизациитребование, чтобы память для всякого хранящегося в стеке объекта выделялась с помощью new, повлекло бы заметные накладные расходы по сравнению с исходной версией, небезопасной относительно потоков.
Вариант 4: реализовать одновременно вариант 1 и один из вариантов 2 или 3
Никогда не следует пренебрегать гибкостью, особенно в обобщенном коде. Если остановиться на варианте 2 или 3, то будет сравнительно нетрудно реализовать и вариант 1, а это оставит пользователю возможность выбрать наиболее подходящее решение ценой очень небольших накладных расходов.
Пример определения потокобезопасного стека
В листинге 3.4 приведено определение класса стека со свободным от гонок интерфейсом. В нем реализованы приведенные выше варианты 1 и 3: имеется два перегруженных варианта функции-члена pop()один принимает ссылку на переменную, в которой следует сохранить значение, а второй возвращает std::shared_ptr<>. Интерфейс предельно прост, он содержит только функции: push() и pop().
Листинг 3.4. Определение класса потокобезопасного стека
#include <exception>
struct empty_stack: std::exception {
const char* what() const throw();
};
template<typename T>
class threadsafe_stack {
public:
threadsafe_stack();
threadsafe_stack(const threadsafe_stack&);
threadsafe_stack& operator=(const threadsafe_stack&)
= delete;(1)
void push(T new_value);
std::shared_ptr<T> pop();
void pop(T& value);
bool empty() const;
};
Упростив интерфейс, мы добились максимальной безопасностидаже операции со стеком в целом ограничены: стек нельзя присваивать, так как оператор присваивания удален (1) (см. приложение А, раздел А.2) и функция swap() отсутствует. Однако стек можно копировать в предположении, что можно копировать его элементы. Обе функции pop() возбуждают исключение empty_stack, если стек пуст, поэтому программа будет работать, даже если стек был модифицирован после вызова empty(). В описании варианта 3 выше отмечалось, что использование std::shared_ptr позволяет стеку взять на себя распределение памяти и избежать лишних обращений к new и delete. Теперь из пяти операций со стеком осталось только три: push(), pop() и empty(). И даже empty() лишняя. Чем проще интерфейс, тем удобнее контролировать доступ к даннымможно захватывать мьютекс на все время выполнения операции. В листинге 3.5 приведена простая реализация в виде обертки вокруг класс std::stack<>.
Листинг 3.5. Определение класса потокобезопасного стека
#include <exception>
#include <memory>
#include <mutex>
#include <stack>
struct empty_stack: std::exception {
const char* what() const throw();
};
template<typename T>
class threadsafe_stack {
private:
std::stack<T> data;
mutable std::mutex m;
public:
threadsafe_stack(){}
threadsafe_stack(const threadsafe_stack& other) {
std::lock_guard<std::mutex> lock(other.m);
data = other.data; (1) Копирование производится в теле
} конструктора
threadsafe_stack& operator=(const threadsafe_stack&) = delete;
void push(T new_value) {
std::lock_guard<std::mutex> lock(m);
data.push(new_value);
}
std::shared_ptr<T> pop()Перед тем как выталкивать значение,
{ проверяем, не пуст ли стек
std::lock_guard<std::mutex> lock(m);
if (data.empty()) throw empty_stack();
std::shared_ptr<T> const res(std::make_shared<T>(data.top()));
data.pop(); Перед тем как модифицировать стек
return res; в функции pop(), выделяем память
} для возвращаемого значения
void pop(T& value) {
std::lock_guard<std::mutex> lock(m);
if (data.empty()) throw empty_stack();
value = data.top();
data.pop();
}
bool empty() const {
std::lock_guard<std::mutex> lock(m);
return data.empty();
}
};
Эта реализация стека даже допускает копированиекопирующий конструктор захватывает мьютекс в объекте-источнике, а только потом копирует внутренний стек. Копирование производится в теле конструктора (1), а не в списке инициализации членов, чтобы мьютекс гарантированно удерживался в течение всей операции.
Обсуждение функций top() и pop() показывает, что проблематичные гонки в интерфейсе возникают из-за слишком малой гранулярности блокировкизащита не распространяется на выполняемую операцию в целом. Но при использовании мьютексов проблемы могут возникать также из-за слишком большой гранулярности, крайним проявление этого является применение одного глобального мьютекса для защиты всех разделяемых данных. В системе, где разделяемых данных много, такой подход может свести на нет все преимущества параллелизма, постольку потоки вынуждены работать но очереди, даже если обращаются к разным элементам данных. В первых версиях ядра Linux для многопроцессорных систем использовалась единственная глобальная блокировка ядра. Это решение работало, но получалось, что производительность одной системы с двумя процессорами гораздо ниже, чем двух однопроцессорных систем, а уж сравнивать производительность четырёхпроцессорной системы с четырьмя однопроцессорными вообще не имело смыслаконкуренция за ядро оказывалась настолько высока, что потоки, исполняемые дополнительными процессорами, не могли выполнять полезную работу. В последующих версиях Linux гранулярность блокировок ядра уменьшилась, и в результате производительность четырёхпроцессорной системы приблизилась к идеалучетырехкратной производительности однопроцессорной системы, так как конкуренция за ядро значительно снизилась.
При использовании мелкогранулярных схем блокирования иногда для защиты всех данных, участвующих в операции, приходится захватывать более одного мьютекса. Как отмечалось выше, бывают случаи, когда лучше повысить гранулярность защищаемых данных, чтобы для их защиты хватило одного мьютекса. Но это не всегда желательно, например, если мьютексы защищают отдельные экземпляры класса. В таком случае блокировка «на уровень выше» означает одно из двух: передать ответственность за блокировку пользователю или завести один мьютекс, который будет защищать все экземпляры класса. Ни одно из этих решений не вызывает восторга.
Но когда для защиты одной операции приходится использовать два или более мьютексов, всплывает очередная проблема: взаимоблокировка. По природе своей она почти противоположна гонке: если в случае гонки два потока состязаются, кто придет первым, то теперь каждый поток ждет другого, и в результате ни тот, ни другой не могут продвинуться ни на шаг.
3.2.4. Взаимоблокировка: проблема и решение
Представьте игрушку, состоящую из двух частей, причем для игры необходимы обе части,например, игрушечный барабан и палочки. Теперь вообразите двух ребятишек, которые любят побарабанить. Если одному дать барабан с палочками, то он будет радостно барабанить, пока не надоест. Если другой тоже хочет поиграть, то ему придётся подождать, как бы это ни было печально. А теперь представьте, что барабан и палочки закопаны где-то в ящике для игрушек (порознь), и оба малыша захотели поиграть с ними одновременно. Один отыскал барабан, а другой палочки. И оба оказались в тупикеесли кто-то один не решится уступить и позволить поиграть другому, то каждый будет держаться за то, что имеет, требуя, чтобы другой отдал недостающее. В результате побарабанить не сможет никто.
А теперь от детей и игрушек перейдём к потокам, ссорящимся по поводу захвата мьютексов,оба потока для выполнения некоторой операции должны захватить два мьютекса, но сложилось так, что каждый поток захватил только один мьютекс и ждет другого. Ни один поток не может продолжить, так как каждый ждет, пока другой освободит нужный ему мьютекс. Такая ситуация называется взаимоблокировкой; это самая трудная из проблем, возникающих, когда для выполнения операции требуется захватить более одного мьютекса.
Общая рекомендация, как избежать взаимоблокировок, заключается в том, чтобы всегда захватывать мьютексы в одном и том же порядке,если мьютекс А всегда захватывается раньше мьютекса В, то взаимоблокировка не возникнет. Иногда это просто, потому что мьютексы служат разным целям, а иногда совсем не просто, например, если каждый мьютекс защищает отдельный объект одного и того же класса. Рассмотрим, к примеру, операцию сравнения двух объектов одного класса. Чтобы сравнению не мешала одновременная модификация, необходимо захватить мьютексы для обоих объектов. Однако, если выбрать какой-то определенный порядок (например, сначала захватывается мьютекс для объекта, переданного в первом параметре, а потомдля объекта, переданного во втором параметре), то легко можно получить результат, обратный желаемому: стоит двум потокам вызвать функцию сравнения, передав ей одни и те же объекты в разном порядке, как мы получим взаимоблокировку!
К счастью, в стандартной библиотеке есть на этот случай лекарство в виде функции std::lock, которая умеет захватывать сразу два и более мьютексов без риска получить взаимоблокировку. В листинге 3.6 показано, как воспользоваться ей для реализации простой операции обмена.
Листинг 3.6. Применение std::lock и std::lock_guard для реализации операции обмена
class some_big_object;
void swap(some_big_object& lhs, some_big_object& rhs);
class X {
private:
some_big_object some_detail;
std::mutex m;
public:
X(some_big_object const& sd) : some_detail(sd) {}
friend void swap(X& lhs, X& rhs) {
if (&lhs == &rhs)
return;
std::lock(lhs.m, rhs.m); (1)
std::lock_guard<std::mutex> lock_a(lhs.m, std::adopt_lock);(2)
std::lock_guard<std::mutex> lock_b(rhs.m, std::adopt_lock);(3)
swap(lhs.some_detail,rhs.some_detail);
}
};
Сначала проверяется, что в аргументах переданы разные экземпляры, постольку попытка захватить std::mutex, когда он уже захвачен, приводит к неопределенному поведению. (Класс мьютекса, допускающего несколько захватов в одном потоке, называется std::recursive_mutex. Подробности см. в разделе 3.3.3.) Затем мы вызываем std::lock() (1), чтобы захватить оба мьютекса, и конструируем два экземпляра std::lock_guard (2), (3)по одному для каждого мьютекса. Помимо самого мьютекса, конструктору передается параметр std::adopt_lock, сообщающий объектам std::lock_guard, что мьютексы уже захвачены, и им нужно лишь принять владение существующей блокировкой, а не пытаться еще раз захватить мьютекс в конструкторе.
Это гарантирует корректное освобождение мьютексов при выходе из функции даже в случае, когда защищаемая операция возбуждает исключение, а также возврат результата сравнения в случае нормального завершения. Стоит также отметить, что попытка захвата любого мьютекса lhs.m или rhs.m внутри std::lock может привести к исключению; в этом случае исключение распространяется на уровень функции, вызвавшей std::lock. Если std::lock успешно захватила первый мьютекс, но при попытке захватить второй возникло исключение, то первый мьютекс автоматически освобождается; std::lock обеспечивает семантику «все или ничего» в части захвата переданных мьютексов.