- PVSM.RU - https://www.pvsm.ru -
Эта статья — введение в программирование без блокировок (неблокирующая синхронизация). Я пишу ее, потому что она будет ключем к пониманию моей следующей статьи [1] [от пер.: перевод в процессе]. Она же является основой моего выступления на Qt Developer Days 2011 [2].
Программирование без блокировок [3] — это подход к разработке алгоритмов и структур данных, которые не нуждаются в блокировке или мьютексах.
Когда разным потокам в вашей программе необходимо получить доступ к одним и тем же данным, необходимо убедиться, что эти данные всегда во время использования находятся в целостном актуальном (когерентном) состоянии. Один из путей достижения этой цели — делать блокировки. Поток овладевает мьютексом, для записи данных. Этот поток может работать со структурами данных и держать их в неопределенном состоянии, но это не приведет к проблеме, т.к. другие потоки в это время не смогут получить доступ к данным, потому что они будут заблокированы, ожидая освобождения мьютекса. Пока поток ожидает, операционная система переключится на другие потоки или процессы, а может просто даст процессору отдохнуть.
Мьютексы — отличный инструмент. Но когда есть блокировки, возникают проблемы. Когда хочется, что бы ваш алгоритм работал быстро, возникает мысль использовать доступные ядра по максимуму, не давая им простаивать. Поток может овладеть мьютексом, а затем ЦП отложит его выполнение (из-за кеш промаха или исчерпания кванта времени). В таком случае, все остальные потоки, которым необходим тот же мьютекс будут заблокированы. Если таких блокировок будет много, ОС придется делать многочисленные переключения контекста, которые обходятся очень дорого из-за очистки кешей.
Если вы программируете систему реального времени, возникают другие проблемы (перестановка приоритетов [4], lock convoy [5] (в любой момент времени все нити за исключением одной заблокированы)). К тому же мьютексы нельзя использовать в обработчиках сигналов.
Рассмотрим абсолютно другой пример: Предположим, вы хотите разделить вашу программу на несколько процессов, что бы при ошибке падал только один процесс, а не все приложение. (Так делаю современные браузеры: рендеринг страницы выполняется в отдельном процессе.) Но, если процесс упадет в момент, когда ему принадлежит разделяемая блокировка, будут большие проблемы, т.к. в большинстве случаев это приведет к взаимной блокировке (deadlock) основного приложения.
У современных процессоров есть так называемые атомарные операции [6]. Существуют библиотеки, у которых есть API, который позволяет использовать эти атомарные операции. В Qt есть два класса: QAtomicInt и QAtomicPointer. В других библиотеках или языках скорее всего есть другие примитивы, но смысл тот же.
Я не буду вдаваться в подробности интерфейсов, потому что об этом можно почитать в документации QAtomicInt [7] и QAtomicPointer [8].
Но подчеркну: оба класса имеют схожий API. Это обертки над int и указателем, которые позволяют выполнять атомарные операции над ними. Есть 3 основных оперции: fetchAndAdd, fetchAndStore и testAndSet. Каждая из которых доступна в 4-х вариантах, для разного порядка выполнения.
Здесь мы будем использовать операцию testAndSet. В другой литературе ее так же называют “Сравнить и Поменять” (Compare and Swap [9]).
Это не атомарная реализация:
bool QAtomicInt::testAndSet(int expectedValue, int newValue) {
if (m_value != expectedValue)
return false;
m_value = newValue;
return true;
}
Что тут происходит: оборачиваемое значение изменяется на новое только в том случае, если оно равно ожидаемому значению, в противном случае ничего не происходит и возвращается false.
Операция атомарная, в том смысле, что два потока работая со значением в одно и то же время выполняются последовательно.
Конечно, настоящая реализация далека от вышеописанной. Она реализована с помощью ассемблерных вставок. Атомарные классы Qt — одно из немногих мест внутри Qt, реализованное на ассемблере для каждой платформы.
Современные процессоры обладают так называемым внеочередным исполнением [10]. Это значит, что каждый такт процессор может прочитать несколько инструкций (скажем 6) из памяти, декодировать их и сохранить в специальном пуле инструкций. Процессор может вычислить зависимости между инструкциями и передавать их вычислительному блоку в том порядке, в котором получится выжать наибольшее быстродействие. Таким образом, инструкции, а самое главное операции чтения и записи, могут выполняться не в том порядке, который мы задали в настоящей программе. Процессор делает это только в том случае, если не изменяет конечного результат работы потока.
Тем не менее, нам бы хотелось сохранить последовательность выполнения, когда мы работаем с атомарными операциями. На самом деле, если запись в память будет производиться в другом порядке в момент, когда другой поток попытается ее прочитать, структура данных может находиться в неопределенном состоянии.
Приведем пример:
QAtomicPointer<int> p;
int x;
//...
x = 4;
p.fetchAndStoreRelease(&x);
Очень важно, что бы p было установлено в &x, когда x уже станет 4. В противном случае, поток будет видеть значение p, которое будет указывать на что нибудь другое.
Этого можно достичь, явно указав запрет на изменение порядка выполнения в программе. Для запрета изменения порядка выполнения существуют специальные инструкции процессора. У нас есть 4 запрета:
Тип запрета передается в функцию операции потому что на некоторых архитектура одна инструкция используется одновременно для атомарной операции и запрета изменения порядка выполнения.
Запрет изменения порядка выполнения защитит нас только от действий в центральном процессоре. Он никак не повлияет на перестановки, которые может выполнить компилятор. Что бы защититься от изменения порядка выполнения компилятором, можно воспользоваться ключевым словом '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;
}
};
Я воспользуюсь схемами, что бы показать, как работает этот код:
В основе лежит связанный список [11]: каждый узел имеет указатель на следующий, а так же у нас есть указатель на первый узел, который будем называть вершиной стека (head).
В этом примере два потока хотят добавить узел в стек. Оба потока находятся в точке n->next = head и вскоре вызовут атомарную операцию, которая изменит вершину стека head с (B) на n (C или D)
На этой картинке видно, что Поток 2 был первым. И D теперь в стеке.
testAndSet Потока 1 завершится неудачей. Вершина стека head уже не B. Новая вершина стека — D.
Поток 1 получит уведомление, что testAndSet завершилось неудачей и попробует повторить попытку, но уже с новой вершиной стека head, которой является теперь D.
Теперь можете сами попробовать этот маленький пример: lockfreestack.cpp [12]
(Загрузите файл в новую директорию и выполните 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), в то время, как с мьютексами много времени тратится на блокировки.
Все хорошо, но в нашей реализации присутствует большая дыра. Стек отлично работает в нашем тесте, потому что мы сначала вставляем узлы, а потом извлекаем их. Нет потоков, которые одновременно бы вставляли и извлекали узлы. В реальном приложении, мы захотим, что мы стек работал даже в том случае, когда потоки одновременно вставляют и извлекают узлы.
Так в чем же проблема? Вновь, я воспользуюсь изображениями:
В примере, Поток 1 хочет извлечь узел. Он берет адрес узла А и собирается выполнить testAndSet что автоматически изменит вершину стека head с А на B. Но перед выполнением атомарной операции ОС переключается на другой поток, который только что запустился.
Пока Поток 1 спит, Поток 2 успешно изымает узел, таким образом А больше не находится в стеке.
Если бы Поток 1 сейчас проснулся, то атомарная операция в Потоке 1 завершилась бы неудачей, потому что вершина стека head уже не равна А. Но Поток 1 не проснулся, а Поток 2 продолжил выполняться…
Поток 2 вставляет в стек узел (С). И снова, если бы поток 1 проснулся, то не было бы никаких проблем. Но он до сих пор спит…
И Поток 2 вставляет узел А назад в стек.
А вот теперь просыпается Поток 1 и выполняет testAndSet, который успешно завершается, потому что вершина стека head вновь А. Это и есть проблема, потому что мы потеряли С!
Все было бы намного хуже, если бы Поток 2 пытался извлечь узел B.
У любой проблемы есть решения. Детальное решение выходит за рамки этой статьи. Я всего лишь дам наводку, что бы вы смогли легко найти детали в интернете:
Как видно, разработка алгоритмов без блокировок требует более серьезного обдумывания, чем с блокировками. Потому, пользуйтесь мьютексами дальше, если в коде много блокировок либо же ищите приключения.
Мне часто задают вопрос, не лучше ли просто блокировать, позволяя другим потокам работать, вместо того, что бы вводить что-то, что может показаться спинлоком (циклической блокировкой). Но на самом деле это не спинлок. Атомарные операции завершаются успехом намного чаще, чем неудачей. Они завершаются неудачей только в том случае, если был прогресс (в смысле, другой поток прогрессировал).
Автор: surik
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/4801
Ссылки в тексте:
[1] следующей статьи: http://woboq.com/blog/internals-of-qmutex-in-qt5.html
[2] Qt Developer Days 2011: http://woboq.com/blog/qt-devdays-2011.html
[3] Программирование без блокировок: http://en.wikipedia.org/wiki/Non-blocking_algorithm
[4] перестановка приоритетов: http://en.wikipedia.org/wiki/Priority_inversion
[5] lock convoy: http://en.wikipedia.org/wiki/Lock_convoy
[6] атомарные операции: http://en.wikipedia.org/wiki/Atomic_operation
[7] QAtomicInt: http://doc.qt.nokia.com/latest/qatomicint.html
[8] QAtomicPointer: http://doc.qt.nokia.com/latest/qatomicpointer.html
[9] Compare and Swap: http://en.wikipedia.org/wiki/Compare-and-swap
[10] внеочередным исполнением: http://en.wikipedia.org/wiki/Out-of-order_execution
[11] связанный список: http://en.wikipedia.org/wiki/Linked_list
[12] lockfreestack.cpp: http://woboq.com/blog/introduction-to-lockfree-programming/lockfreestack.cpp
[13] Hazard pointer: http://en.wikipedia.org/wiki/Hazard_pointer
Нажмите здесь для печати.