Эта статья — введение в программирование без блокировок (неблокирующая синхронизация). Я пишу ее, потому что она будет ключем к пониманию моей следующей статьи [от пер.: перевод в процессе]. Она же является основой моего выступления на Qt Developer Days 2011.
Программирование без блокировок — это подход к разработке алгоритмов и структур данных, которые не нуждаются в блокировке или мьютексах.
Когда разным потокам в вашей программе необходимо получить доступ к одним и тем же данным, необходимо убедиться, что эти данные всегда во время использования находятся в целостном актуальном (когерентном) состоянии. Один из путей достижения этой цели — делать блокировки. Поток овладевает мьютексом, для записи данных. Этот поток может работать со структурами данных и держать их в неопределенном состоянии, но это не приведет к проблеме, т.к. другие потоки в это время не смогут получить доступ к данным, потому что они будут заблокированы, ожидая освобождения мьютекса. Пока поток ожидает, операционная система переключится на другие потоки или процессы, а может просто даст процессору отдохнуть.
Что не так с мьютексами?
Мьютексы — отличный инструмент. Но когда есть блокировки, возникают проблемы. Когда хочется, что бы ваш алгоритм работал быстро, возникает мысль использовать доступные ядра по максимуму, не давая им простаивать. Поток может овладеть мьютексом, а затем ЦП отложит его выполнение (из-за кеш промаха или исчерпания кванта времени). В таком случае, все остальные потоки, которым необходим тот же мьютекс будут заблокированы. Если таких блокировок будет много, ОС придется делать многочисленные переключения контекста, которые обходятся очень дорого из-за очистки кешей.
Если вы программируете систему реального времени, возникают другие проблемы (перестановка приоритетов, lock convoy (в любой момент времени все нити за исключением одной заблокированы)). К тому же мьютексы нельзя использовать в обработчиках сигналов.
Рассмотрим абсолютно другой пример: Предположим, вы хотите разделить вашу программу на несколько процессов, что бы при ошибке падал только один процесс, а не все приложение. (Так делаю современные браузеры: рендеринг страницы выполняется в отдельном процессе.) Но, если процесс упадет в момент, когда ему принадлежит разделяемая блокировка, будут большие проблемы, т.к. в большинстве случаев это приведет к взаимной блокировке (deadlock) основного приложения.
Как же сделать это без блокировок?
У современных процессоров есть так называемые атомарные операции. Существуют библиотеки, у которых есть API, который позволяет использовать эти атомарные операции. В Qt есть два класса: QAtomicInt и QAtomicPointer. В других библиотеках или языках скорее всего есть другие примитивы, но смысл тот же.
QAtomic API
Я не буду вдаваться в подробности интерфейсов, потому что об этом можно почитать в документации QAtomicInt и QAtomicPointer.
Но подчеркну: оба класса имеют схожий API. Это обертки над int и указателем, которые позволяют выполнять атомарные операции над ними. Есть 3 основных оперции: fetchAndAdd, fetchAndStore и testAndSet. Каждая из которых доступна в 4-х вариантах, для разного порядка выполнения.
Здесь мы будем использовать операцию testAndSet. В другой литературе ее так же называют “Сравнить и Поменять” (Compare and Swap).
Это не атомарная реализация:
bool QAtomicInt::testAndSet(int expectedValue, int newValue) {
if (m_value != expectedValue)
return false;
m_value = newValue;
return true;
}
Что тут происходит: оборачиваемое значение изменяется на новое только в том случае, если оно равно ожидаемому значению, в противном случае ничего не происходит и возвращается false.
Операция атомарная, в том смысле, что два потока работая со значением в одно и то же время выполняются последовательно.
Конечно, настоящая реализация далека от вышеописанной. Она реализована с помощью ассемблерных вставок. Атомарные классы Qt — одно из немногих мест внутри Qt, реализованное на ассемблере для каждой платформы.
Порядок выполнения
Современные процессоры обладают так называемым внеочередным исполнением. Это значит, что каждый такт процессор может прочитать несколько инструкций (скажем 6) из памяти, декодировать их и сохранить в специальном пуле инструкций. Процессор может вычислить зависимости между инструкциями и передавать их вычислительному блоку в том порядке, в котором получится выжать наибольшее быстродействие. Таким образом, инструкции, а самое главное операции чтения и записи, могут выполняться не в том порядке, который мы задали в настоящей программе. Процессор делает это только в том случае, если не изменяет конечного результат работы потока.
Тем не менее, нам бы хотелось сохранить последовательность выполнения, когда мы работаем с атомарными операциями. На самом деле, если запись в память будет производиться в другом порядке в момент, когда другой поток попытается ее прочитать, структура данных может находиться в неопределенном состоянии.
Приведем пример:
QAtomicPointer<int> p;
int x;
//...
x = 4;
p.fetchAndStoreRelease(&x);
Очень важно, что бы p было установлено в &x, когда x уже станет 4. В противном случае, поток будет видеть значение p, которое будет указывать на что нибудь другое.
Этого можно достичь, явно указав запрет на изменение порядка выполнения в программе. Для запрета изменения порядка выполнения существуют специальные инструкции процессора. У нас есть 4 запрета:
- Acquire
Никакие чтения или записи, идущие после, не могут быть выполнены перед атомарной операцией. - Release
Противоположно Acquire: Никакие чтения или записи, идущие перед, не могут быть выполнены после атомарной операции. - Ordered
Это комбинация первых двух. Ничто не может быть перемещено ни до, ни после атомарной операции. Это самый безопасный и самый используемый вариант, особенно если вы не знаете, что выбрать. - Relaxed
Никаких ограничений на изменение порядка выполнения.
Тип запрета передается в функцию операции потому что на некоторых архитектура одна инструкция используется одновременно для атомарной операции и запрета изменения порядка выполнения.
Запрет изменения порядка выполнения защитит нас только от действий в центральном процессоре. Он никак не повлияет на перестановки, которые может выполнить компилятор. Что бы защититься от изменения порядка выполнения компилятором, можно воспользоваться ключевым словом 'volatile'.
Стек без блокировок
Напишем стек, который будет работать без блокировок:
class Stack {
QAtomicPointer<Node> head;
public:
Stack() : head(0) {}
void push(Node *n) {
do {
n->next = head;
} while(!head.testAndSetOrdered(n->next, n));
}
Node *pop() {
Node *n;
do {
n = head;
if (!n)
return 0;
} while(!head.testAndSetOrdered(n, n->next));
return n;
}
};
Я воспользуюсь схемами, что бы показать, как работает этот код:
В основе лежит связанный список: каждый узел имеет указатель на следующий, а так же у нас есть указатель на первый узел, который будем называть вершиной стека (head).
Push
В этом примере два потока хотят добавить узел в стек. Оба потока находятся в точке n->next = head и вскоре вызовут атомарную операцию, которая изменит вершину стека head с (B) на n (C или D)
На этой картинке видно, что Поток 2 был первым. И D теперь в стеке.
testAndSet Потока 1 завершится неудачей. Вершина стека head уже не B. Новая вершина стека — D.
Поток 1 получит уведомление, что testAndSet завершилось неудачей и попробует повторить попытку, но уже с новой вершиной стека head, которой является теперь D.
Тест
Теперь можете сами попробовать этот маленький пример: lockfreestack.cpp
(Загрузите файл в новую директорию и выполните qmake -project && qmake && make)
Эта программа сначала добавит 2 миллиона узлов в список используя 4 потока и измерит потраченное время. Когда все потоки справятся с заданием, программа извлечет все эти узлы используя 4 потока и снова измерит, сколько заняла эта операция.
Программа также содержит версию стека, которая использует QMutex (в #if 0 блоке)
Результаты: (на моей 4-х ядерной машине)
| Вставка (мс) | Извлечение (мс) | Всего (real / user / sys) (мс) | |
|---|---|---|---|
| С QMutex | 3570 | 7287 | 7287 / 4180 / 11649 |
| Без блокировок | 185 | 237 | 420 / 547 / 297 |
Неплохо: стек без блокировок более чем в 100 раз быстрее. Как видно, конкуренция у потоков намного меньше в случае без блокировок (число real меньше user), в то время, как с мьютексами много времени тратится на блокировки.
Проблема ABA
Все хорошо, но в нашей реализации присутствует большая дыра. Стек отлично работает в нашем тесте, потому что мы сначала вставляем узлы, а потом извлекаем их. Нет потоков, которые одновременно бы вставляли и извлекали узлы. В реальном приложении, мы захотим, что мы стек работал даже в том случае, когда потоки одновременно вставляют и извлекают узлы.
Так в чем же проблема? Вновь, я воспользуюсь изображениями:
В примере, Поток 1 хочет извлечь узел. Он берет адрес узла А и собирается выполнить testAndSet что автоматически изменит вершину стека head с А на B. Но перед выполнением атомарной операции ОС переключается на другой поток, который только что запустился.
Пока Поток 1 спит, Поток 2 успешно изымает узел, таким образом А больше не находится в стеке.
Если бы Поток 1 сейчас проснулся, то атомарная операция в Потоке 1 завершилась бы неудачей, потому что вершина стека head уже не равна А. Но Поток 1 не проснулся, а Поток 2 продолжил выполняться…
Поток 2 вставляет в стек узел (С). И снова, если бы поток 1 проснулся, то не было бы никаких проблем. Но он до сих пор спит…
И Поток 2 вставляет узел А назад в стек.
А вот теперь просыпается Поток 1 и выполняет testAndSet, который успешно завершается, потому что вершина стека head вновь А. Это и есть проблема, потому что мы потеряли С!
Все было бы намного хуже, если бы Поток 2 пытался извлечь узел B.
Решение проблемы ABA
У любой проблемы есть решения. Детальное решение выходит за рамки этой статьи. Я всего лишь дам наводку, что бы вы смогли легко найти детали в интернете:
- Добавить серийный номер в указатель, который будет увеличиваться каждый раз при извлечение узла. Его можно хранить в младших битах указателя (соответственно не забывая про выравнивание адреса). Но битов может быть недостаточно. Вместо использования указателей, можно использовать индексы, как в массиве, оставляя достаточно битов для серийного номера.
- Hazard pointer: Каждый поток сохраняет указатель, который читает, в список, доступный всем потокам. Этот список потом проверяется при повторном использование узла.
- Двойное или множественное сравнение и обмен. (можно реализовать с помощью одинарного сравнения и обмена)
Выводы
Как видно, разработка алгоритмов без блокировок требует более серьезного обдумывания, чем с блокировками. Потому, пользуйтесь мьютексами дальше, если в коде много блокировок либо же ищите приключения.
Мне часто задают вопрос, не лучше ли просто блокировать, позволяя другим потокам работать, вместо того, что бы вводить что-то, что может показаться спинлоком (циклической блокировкой). Но на самом деле это не спинлок. Атомарные операции завершаются успехом намного чаще, чем неудачей. Они завершаются неудачей только в том случае, если был прогресс (в смысле, другой поток прогрессировал).
Автор: surik
