многопоточность — безблокировочные структуры данных C ++, невозможно?
Я действительно не понимаю, как вы можете сделать некоторые структуры данных без блокировки. Например, если у вас есть связанный список, то либо вы окружаете операции мьютексами, либо вы можете получить условие гонки, если другой поток выполняется, пока вы заняты повторным связыванием новых узлов вместе.
Концепция «без блокировки» (я понимаю, что это не означает «без блокировок», но означает, что потоки могут развиваться, не дожидаясь завершения других потоков), просто не имеет смысла.
Может кто-нибудь показать мне простой пример использования стека, очереди или связанного списка и т. Д., Который реализован как «свободный от блокировок», потому что я не могу понять, как можно предотвратить состояние гонки, не влияя на производительность других потоков? Наверняка эти две цели противоречат друг другу?
Решение
Структуры данных без блокировки используют атомарные операции и могут налагать дополнительные требования. Например, структура данных может быть безопасной только для одного читающего и одного записывающего потока или любой другой комбинации. В случае простого связанного списка будут использоваться атомарные чтения и записи в указатель узла, чтобы гарантировать, что несколько потоков могут безопасно читать и записывать в него одновременно.
Вы можете или не можете сойти с рук только с этим. Если вам нужны дополнительные гарантии относительно содержимого структуры данных и проверки, вы, вероятно, не сможете сделать это без какой-либо формы высокоуровневой блокировки. Кроме того, не каждая структура данных позволяет переписать ее так, чтобы она была свободной от блокировки, даже с учетом дополнительных требований к тому, как используется структура данных. В этом случае неизменные объекты могут быть решением, но они обычно сопровождаются снижением производительности из-за копирования, что не всегда желательно из-за блокировки объекта и последующего его изменения.
Другие решения
Доступны различные примитивы, которые позволяют создавать такие структуры данных без блокировки. Например, сравните-и-своп (CAS для краткости), который атомарно выполняет следующий код:
CAS(x, o, n)
if x == o:
x = n
return o
else:
return x
С помощью этой операции вы можете делать атомарные обновления. Рассмотрим, например, очень простой связанный список, который хранит элементы в отсортированном порядке, позволяет вставлять новые элементы и проверять, существует ли элемент. Операция find будет работать как прежде: она будет проходить по всем ссылкам, пока не найдет элемент или не найдет элемент большего размера, чем запрос. Вставка должна быть немного более осторожной. Это может работать следующим образом:
insert(lst, x)
xn = new-node(x)
n = lst.head
while True:
n = find-before(n, x)
xn.next = next = n.next
if CAS(n.next, next, x) == next:
break
find-before(n,x) просто находит элемент, который предшествует x в порядке. Это, конечно, просто набросок. Все становится сложнее, если вы хотите поддерживать удаление. Я рекомендую Херлихи и Шавита «Искусство многопроцессорного программирования». Следует также отметить, что зачастую выгодно переключать структуры данных, которые реализуют одну и ту же модель, чтобы сделать их свободными от блокировки. Например, если вы хотите реализовать эквивалент std::mapбыло бы больно делать это с красно-черным деревом, но список пропусков гораздо более управляемый.
Структура без блокировки использует атомарную инструкцию для получения права собственности на ресурсы. Атомная инструкция блокирует переменную, которая работает на уровне кэша ЦП, и уверяет вас, что другие ядра не могут мешать работе.
Допустим, у вас есть эти атомарные инструкции:
- читать (A) -> A
- сравнивать и поменять (A, B, C) -> oldA = A; if (A == B) {A = C}; вернуть oldA;
С помощью этой инструкции вы можете просто создать стек:
template<typename T, size_t SIZE>
struct LocklessStack
{
public:
LocklessStack() : top(0)
{
}
void push(const T& a)
{
int slot;
do
{
do
{
slot = read(top);
if (slot == SIZE)
{
throw StackOverflow();
}
}while(compare_and_swap(top, slot, slot+1) == slot);
// NOTE: If this thread stop here. Another thread pop and push
// a value, this thread will overwrite that value [ABA Problem].
// This solution is for illustrative porpoise only
data[slot] = a;
}while( compare_and_swap(top, slot, slot+1) == slot );
}
T pop()
{
int slot;
T temp;
do
{
slot = read(top);
if (slot == 0)
{
throw StackUnderflow();
}
temp = data[slot-1];
}while(compare_and_swap(top, slot, slot-1) == slot);
return temp;
}
private:
volatile int top;
T data[SIZE];
};
требуется volatile, чтобы компилятор не нарушал порядок операций во время оптимизации.
Два одновременных нажатия происходят:
Первый вход в цикл while и чтение слота, затем прибывает второй толчок, чтение сверху, успешное сравнение и свопинг (CAS) и увеличение приращения. Другой поток просыпается, CAS терпит неудачу и читает другое время сверху.
Происходят два одновременных щелчка:
Действительно похоже на предыдущий случай. Нужно также прочитать значение.
Один поп и пуш происходят одновременно:
pop прочитайте верх, прочитайте temp .. нажмите ввод и измените top и нажмите новое значение. Ошибка Pop CAS, pop () снова выполнит цикл и прочитает новое значение
или же
нажмите читать верхнюю часть и получите слот, нажмите ввод и измените верхнее значение. Нажать CAS не удалось, и приходится повторять цикл, нажимая на более низкий индекс.
Очевидно, что это не так в параллельной среде
stack.push(A);
B = stack.pop();
assert(A == B); // may fail
причина, в то время как толчок атомарен, и поп атомарен, их комбинация не атомарна.
Первая глава Gem 6 игрового программирования хорошая ссылка.
Обратите внимание, что код НЕ ПРОВЕРЕН и атомарный может быть действительно противный.
Ваше определение блокировки свободы неверно.
Свобода блокировки позволяет отдельным потокам голодать, но гарантирует пропускную способность всей системы. Алгоритм не блокируется, если он удовлетворяет тому, что когда программные потоки выполняются достаточно долго, по крайней мере один из потоков выполняет прогресс (для некоторого разумного определения прогресса)
https://en.wikipedia.org/wiki/Non-blocking_algorithm
это означает, что при доступе к структуре данных нескольких потоков будет предоставлен только 1; остальное не получится
важная вещь о свободе блокировки — вероятность столкновения памяти.
Структура данных, защищенная блокировками, как правило, будет быстрее, чем реализация с атомарными переменными, но она плохо масштабируется с небольшой вероятностью столкновения.
пример: несколько потоков постоянно push_back данных в вашем списке. это приведет ко многим столкновениям, и классический мьютекс в порядке. Однако, если у вас есть 1 поток, выдвигающий данные в конец списка, и 1 поток, выдвигающий данные вперед, ситуация будет иной. Если список не пустой, push_back () и pop_front () не будут сталкиваться (зависит от реализации), поскольку они не работают с одним и тем же объектом. Но все еще есть изменение пустого списка, так что вам все еще нужно защитить доступ. В этом сценарии блокировка свободы будет лучшим решением, поскольку вы можете вызывать обе функции одновременно, не дожидаясь.
короче говоря: без блокировки предназначен для больших структур данных, где несколько авторов в основном разделены и редко сталкиваются.
Я пытался реализовать контейнер списка без блокировки самостоятельно … https://codereview.stackexchange.com/questions/123201/lock-free-list-in-c
Предположим, простая операция, которая увеличивает переменную на единицу. Если вы реализуете это, используя «чтение переменной из памяти в процессор, добавление 1 в регистр процессора, запись переменной обратно», то вам придется использовать какой-то мьютекс вокруг всего этого, потому что вы хотите убедиться, что второй поток не будет читать переменную, пока после первый написал это обратно.
Если ваш процессор имеет атомарную инструкцию по сборке «места увеличения памяти», блокировка вам не нужна.
Или предположим, что вы хотите вставить элемент в связанный список, а это значит, что вам нужно сделать указатель начала на новый элемент, а затем указать новый элемент на элемент, который был предыдущим первым. С помощью атомарной операции «обмен двух ячеек памяти» вы можете записать текущий указатель начала в «следующий» указатель нового элемента, а затем поменять местами два указателя — теперь, в зависимости от того, какой поток запускается первым, элементы будут в разных порядок в списке, но структура данных списка остается неизменной.
По сути, это всегда «делать несколько вещей одновременно, за одну атомарную операцию, чтобы вы не могли разбить операцию на отдельные части, которые не могут быть прерваны».