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

Алгоритмы и структуры данных, в которых для синхронизации доступа используются мьютексы, условные переменные и будущие результаты, называются блокирующими . Приложение вызывает библиотечные функции, которые приостанавливают выполнение потока до тех пор, пока другой поток не завершит некоторое действие. Такие библиотечные функции называются блокирующими , потому что поток не может продвинуться дальше некоторой точки, пока не будет снят блокировка. Обычно ОС полностью приостанавливает заблокированный поток (и отдает его временные кванты другому потоку) до тех пор, пока он не будет разблокирован в результате выполнения некоторого действия в другом потоке, будь то освобождение мьютекса, сигнал условной переменной или перевод будущего результата в состояние готов .

Структуры данных и алгоритмы, в которые блокирующие библиотечные функции не используются, называются неблокирующими . Но не все такие структуры данных свободны от блокировок , поэтому давайте сначала рассмотрим различные типы неблокирующих структур.

В главе 5 мы реализовали простой мьютекс-спинлок с помощью std::atomic_flag. Этот код воспроизведён в листинге ниже.

Листинг 7.1.Реализация мьютекса-спинлока с помощью std::atomic_flag

class spinlock_mutex {

std::atomic_flag flag;

public:

spinlock_mutex():

flag(ATOMIC_FLAG_INIT) {}

void lock() {

while (flag.test_and_set(std::memory_order_acquire));

}

void unlock() {

flag.clear(std::memory_order_release);

}

};

Здесь не вызываются никакие блокирующие функции; lock()просто «крутится» в цикле, пока test_and_set()не вернет false. Отсюда и название спинлок (spin lock) — слово spin означает «крутиться». Как бы то ни было, блокирующих вызовов нет, и, значит, любая программа, в которой для защиты разделяемых данных используется такой мьютекс, будет неблокирующей . Однако она не свободна от блокировок . Это по-прежнему мьютекс, который в каждый момент времени может захватить только один поток. Теперь сформулируем определение свободы от блокировок и посмотрим, какие структуры данных под него подпадают.

Чтобы структура данных считалась свободной от блокировок, она должна быть открыта для одновременного доступа со стороны сразу нескольких потоков. Не требуется, чтобы потоки могли выполнять одну и ту же операцию; свободная от блокировок очередь может позволять одного потоку помещать, а другому — извлекать данные, но запрещать одновременное добавление данных со стороны двух потоков. Более того, если один из потоков, обращающихся к структуре данных, будет приостановлен планировщиком в середине операции, то остальные должны иметь возможность завершить операцию, не дожидаясь возобновления приостановленного потока.

Алгоритмы, в которых применяются операции сравнения с обменом, часто содержат циклы. Зачем вообще используются такие операции? Затем, что другой поток может в промежутке модифицировать данные, и тогда программа должна будет повторить часть операции, прежде чем попытается еще раз выполнить сравнение с обменом. Такой код может оставаться свободным от блокировок при условии, что сравнение с обменом в конце концов завершится успешно, если другие потоки будут приостановлены. Если это не так, то мы по существу получаем спинлок, то есть алгоритм неблокирующий, но не свободный от блокировок.

Свободные от блокировок алгоритмы с такими циклами могут приводить к застреванию (starvation) потоков, когда один поток, выполняющий операции с «неудачным» хронометражем, продвигается вперёд, а другой вынужден постоянно повторять одну и ту же операцию. Структуры данных, в которых такой проблемы не возникает, называются свободными от блокировок и ожидания.

Свободная от блокировок структура данных называется свободной от ожидания, если обладает дополнительным свойством: каждый обращающийся к ней поток может завершить свою работу за ограниченное количество шагов вне зависимости от поведения остальных потоков. Алгоритмы, в которых количество шагов может быть неограничено из-за конфликтов с другими потоками, не свободны от ожидания.

Корректно реализовать свободные от ожидания структуры данных чрезвычайно трудно. Чтобы гарантировать, что каждый поток сможет завершить свою работу за ограниченное количество шагов, необходимо убедиться, что каждая операция может быть выполнена за один проход и что шаги, выполняемые одним потоком, не приводят к ошибке в операциях, выполняемых другими потоками. В результате алгоритмы выполнения различных операций могут значительно усложниться. Учитывая, насколько трудно правильно реализовать структуру данных, свободную от блокировок и ожидания, нужно иметь весьма веские причины для того, чтобы взяться за это дело; требуется тщательно соотносить затраты с ожидаемым выигрышем. Поэтому обсудим, какие факторы влияют на это соотношение.