27 марта 2013 в 03:21

Частые ошибки при разработке lockfree-алгоритмов и их решения

На хабре уже было несколько статей про lock-free алгоритмы. Этот пост — это перевод статьи моего коллеги, которую мы планируем публиковать в нашем корпоративном блоге. По роду деятельности мы пишем огромное количество lock-free алгоритмов и структур данных, и этой статьей хочется показать, насколько это интересно и сложно одновременно.



Эта статья во многом похожа на эту статью, но в той статье рассматриваются не все проблемы, с которыми можно столкнуться, разрабатывая lock-free структуры данных, и уделяется очень мало внимания решению этих проблем. В этой статье хочется детально остановиться на некоторых решениях, которые мы используем в реальной реализации lock-free структур данных в нашем продукте, и больше внимания уделить оценке производительности.

По определению, lock-free алгоритм гарантирует, что время между двумя подряд идущими завершенными операциями ограничено сверху некоторой величиной, которая не зависит от того, как операционная система эти потоки распределит во времени. Такая гарантия звучит очень приятно, потому что потоки могут обращаться к одному и тому же участку памяти одновременно, и даже если операционная система решит временно усыпить один или несколько потоков посреди выполнения какой-то операции с этим участком памяти, остальные потоки продолжат работу. Как бы два или более потока не пересеклись друг с другом во времени, хотя бы один из них всегда завершится за конечное время (в отличие от wait-free, lock-free не гарантирует, что все они завершатся за конечное время).

Lock-free алгоритмы обычно противопоставляются традиционному подходу к написанию многопоточных приложений с использованием блокировок вокруг кода, обращающегося к общим участкам памяти. Когда поток хочет обратиться к памяти, он блокирует к ней доступ других потоков. Если какой-то другой поток заблокировал доступ раньше, то текущий поток ждет, пока блокировка не будет снята. Если операционная система решит временно усыпить поток, владеющий блокировкой, вся система останавливается без возможности изменить общий участок памяти.

Вместо использования блокировок, lock-free алгоритмы используют команду, известную как compare and swap (CAS). Ее логику можно описать следующим фрагментом кода, с той оговркой, что CAS выполняется атомарно:

1 bool CompareAndSwap(Value* addr, Value oldVal, Value newVal){
2     if(*addr == oldVal){
3         *addr = newVal;
4         return true;
5     }else{
6         return false;
7     }
8 }


Основными проблемами lock-free алгоритмов являются следующие три:

1. Часто lock-free реализация является менее практичной, чем реализация с блокировками.
2. Писать lock-free код не просто.
3. Писать правильный lock-free код невероятно сложно.

Чтобы доказать пункт три, расмотрим простой пример — реализацию стека на связных списках. Если попросить человека, не знакомого с lock-free написать стек, то его первая реализация будет примерно следующей:

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

Для операции удаления из стека, запомним текущую вершину стека, и, с помощью CAS, попытаемся поменять ее на значение ее указателя на следующий элемент. Если CAS прошел успешно, то элемент из стека убран, иначе вершина стека была изменена другим потоком, и мы пытаемся удалить ее опять.

На С++ это будет выглядить примерно следующим образом:

 1 template <class Entry>
 2 class LockFreeStack{
 3     struct Node{
 4         Entry* entry;
 5         Node* next;
 6     };
 7 
 8     Node* m_head;
 9 
10     void Push(Entry* e){
11         Node* n = new Node;
12         n->entry = e;
13         do{
14             n->next = m_head;
15         }while(!CompareAndSwap(&m_head, n->next, n));
16     }
17 
18     Entry* Pop(){
19         Node* old_head;
20         Entry* result;
21         do{
22             old_head = m_head;
23             if(old_head == NULL){
24                 return NULL;
25             }
26         }while(!CompareAndSwap(&m_head, old_head, old_head->next));
27 
28         result = old_head->entry;
29         delete old_head;
30         return result;
31     }
32 }


К сожалению, эта, кажущаяся на первый взгляд разумной, реализация lock-free стека содержит огромное количество ошибок.

SegFault

Даже самый простой тест такого стека быстро упадет с Segmentation Fault. Причина — в строке 22 мы читаем указатель на текущую вершину стека. В стоке 26 мы обращаемся к ее полю next. За время между тем, как мы прочитали указатель, и тем, как мы обратились к его полю next, одновременно выполняющийся Pop мог удалить этот элемент (строка 29), тем самым приведя к тому, что память, прочитанная в стоке 26, уже освобождена.
Для правильной работы алгоритма необходим какой-то безопасный алгоритм управления памятью.

Потеря элемента

Успешный CAS не гарантирует, что за время его выполнения память не была изменена. Он гарантирует, что ее значение в момент, когда он ее перезаписал, было равно тому значению, которое ему передано как ожидаемое. Иными словами, если вы вызываете CAS(ptr, 5, 6) в момент, когда значение в ptr равно пяти, затем другой поток меняет значение в ptr на семь, и затем обратно на пять, CAS выполнится успешно, перезависав пять шестью. Это может привести к проблеме, известной как проблема ABA. Рассмотрим следующий пример:

Допустим, что в стеке сейчас два элемента, A -> C.

Поток 1 вызывает Pop, читает в строке 22 m_head (A), в строке 26 читает old_head->next (С), а затем операционная система усыпляет поток.
Поток 2 вызывает Pop, и успешно убирает элемент A.
Поток 2 вызывает Push, и успешно вставляет элемент B.
Поток 2 вызывает Push опять, и вставляет элемент, расположенный по тому же адресу, что и A (либо A был освобожден, и затем другой элемент был заведен по тому же адресу, либо пользователь решил вставить элемент, который он только что взял со стека, обратно)
Поток 1 просыпается, и вызывает CAS. CAS выполняется успешно, не смотря на то, что за это время m_head изменился три раза! Как следствие, элемент B потерян.

Не lock-free

Стандарт С++ не гарантирует, что new и delete являются lock-free. В чем смысл разрабатывать lock-free алгоритм, если он вызывает библиотечные функции, которые не lock-free? Для того, чтобы алгоритм был lock-free, работа с памятью тоже должна быть lock-free.

Одновременный доступ к памяти

Если текущее значение в некоторой ячейке памяти равно 100, и один из потоков в данный момент пишет в нее 200, а другой поток читает ее значение (допустим, что кроме этих двух потоков в системе других потоков нет). Какое значение прочитает второй поток? Кажется разумным, что он прочитает либо 100, либо 200. Однако, это не так. В С++ описанный сценарий приводит к неопределенному поведению, и второй поток теоретически может прочитать 42. До C++11 люди использовали volatile для переменных, к которым был возможен одновременный доступ, но на самом деле volatile для этой цели использован никогда быть не должен.
В нашей реализации Push и Pop оба читают и пишут m_head, тем самым, каждое чтение m_head приводит к неопределенному поведению, и может вернуть значение, которое никогда в m_head записано не было.

Порядок обращений к памяти

Хорошо известно, что как компилятор, так и процессор могут поменять порядок выполнения команд. Рассмотрим такой пример. Пусть x и y оба равны нулю, и затем два потока выполняют следующий код:

Поток 1: print x; x = 1; print y;
Поток 2: print y; y = 1; print x;

Допустим, что оба потока вывели два нуля. Из этого следует, что первый поток вывел y до того, как второй поток присвоил ему единицу, что произошло перед тем, как второй поток вывел x, что произошло перед тем, как первый поток присвоил ему единицу, что произошло перед тем, как первый поток вывел y. То есть первый поток вывел y прежде, чем он вывел y, что не имеет смысла. Однако, такой сценарий возможен, потому что как компилятор, так и процессор могли поменять порядок чтения и записи x и y врутри потоков.
В нашей реализации lock-free стека мы можем видеть значение в указателе на следующий элемент, которое было давно изменено, и, как следствие, можем обратиться к памяти, которая была освобождена.

Так как же написать lock-free стек?


Большинство описанных проблем имеют более одного решения. Здесь приводятся решения, которые мы используем в нашей работе как для стека, так и для других структур данных.

SegFault

Прежде, чем удалить участок памяти, надо убедиться, что никто эту память не читает. Первая мысль, которая приходит на ум, это использовать счетчик ссылок, но это решение не работает: между тем, как мы получили адрес, и тем, как мы увеличили счетчик ссылок, память могла быть освобождена. Мы используем решение, которое называется «Hazard Pointers». В случае для стека, каждый поток имеет спецальный видимый всем указатель (назовем его «локальный указатель»), где хранится адрес элемента, с которым данный поток работает в настоящий момент. Прежде, чем удалить любой элемент, удаляющий поток убеждается, что этот элемент не содержится ни в одном из локальных указателей. Если он содержится в локальных указателях, удалять элемент нельзя. Можно либо подождать и попробовать снова, либо занести элемент в очередь на удаление и доверить другим потокам удалить его позже.
Каждый поток, который хочет сделать какую-либо операцию на вершине стека сначала сохраняет вершину стека в свой локальный указатель, затем убеждается, что сохраненный в локальный указатель элемент все еще является вершиной стека (он мог быть убран и память могла быть освобождена пока мы сохраняли его в локальный указатель). После этого поток может быть уверен, что память, занятая элементом, освобождена не будет.
Большим недостатком может являться то, что для удаления элемента требуется просканировать массив, размер которого равен количеству потоков в системе. Один из вариантов оптимизации может быть следующий: вместо удаления элемента всегда класть его в очередь, и только когда очередь набирает достаточно большое количество элементов на удаление (сравнимое с количеством потоков), удалить их все сразу. В этом случае можно скопировать значения всех локальных указателей на тот момент в какую-то структуру данных с быстрым поиском (например, хеш-таблицу), и использовать эту структуру данных, чтобы проверять, можно ли удалить элемент.
Для структур данных сложнее, чем стек (связные списки, skiplists) может потребоваться более одного локального указателя на поток.

Потеря элемента

Чтобы ABA проблема никогда не происходила, достаточно гарантировать, что m_head никогда не примет одно и тоже значение дважды. Для этого можно хранить с указателем 64-ех битное число (назовем его версией), которое увеличивается на единицу с каждой операцией. Для того, чтобы менять указатель и версию одновременно, нам понадобится Double CAS, который доступен на всех современных процессорах.

Не lock-free

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

Одновременный доступ к памяти

Мы используем boost::atomic для переменных, к которым возможен доступ из нескольких потоков. Хотя в компиляторе, который мы используем (g++ 4.6) уже есть реализация std::atomic, она значительно менее эффективна, чем boost::atomic, потому что использует memory_barrier после каждой операции, даже если memory_barrier после нее не нужен.

Порядок обращений к памяти

В С++11 была введена новая модель памяти и правила обращения к памяти для atomic переменных. Для каждой операции чтения или записи можно указать, какие гарантии требуются. Для обращений к вершине lock-free стека мы вынуждены использовать CompareAndSwap с гарантией sequential consistency (это самая строгая гарантия, и, как следствие, самая медленная). Sequential consistency значит, что для всех операций чтения и записи, выполненных в некоторый промежуток времени всеми потоками, существует порядок такой, что каждый поток видел эти операции, как если бы они произошли в этом порядке.
Если вы понимаете модель памяти С++11, и попытаетесь проанилизировать, какие гарантии следует использовать для работы с локальными указателями (hazard pointers), вы можете предположить, что aqcuire/release достаточны.

Что такое acquire/release
Гарантия acquire/release может быть описана следующим сценарием: если Поток 1 поменял переменную A с гарантией release, а затем переменную B с гарантией release, а Поток 2 прочитал B с гаранией acquire, и увидел значение, записанное Потоком 1, то гарантируется, что если затем Поток 2 прочитает A с гарантией acquire, то он увидит изменение, сделанное Потоком 1.


Мы использовали acquire/release некоторое время, пока в один день сервер не упал на удачно поставленном assert. Детальный анализ ошибки показал, что при использовании acquire/release возможен следующий сценарий:

Поток 1 готовится выполнить Pop и читает вершину стека
Поток 1 пишет вершину стека в свой локальный указатель (используя release гарантию)
Поток 1 читает вершину стека снова, она не изменилась
Поток 2 убирает вершину стека, и решает ее удалить (или добавляет в очередь на удаление, и другой поток решает ее удалить — назовем поток, удаляющий элемент, Поток 3)
Поток 3 читает массив локальных указателей с гарантией acquire. Здесь возникает пробоема — не гарантируется, что мы видим изменение, сделанное Потоком 1.
Поток 3 удаляет память.
Поток 1 разыменовывает сохраненную вершину стека, которая была удалена, и падает с SegFault.

Если же использовать Sequential Consistency как для доступа к локальным указателям, так и для работы с вершиной стека, такой сценарий не возможен. Поскольку порядок операций для всех потоков одинаков, то либо Поток 2 убрал элемент с вершины стека прежде, чем Поток 1 проверил его после записи в локальный указатель (тогда Поток 1 поймет, что вершина стека изменилась, и начнет сначала), либо Поток 1 успешно сравнил свой локальный указатель с вершиной стека прежде, чем Поток 2 убрал элемент с вершины стека, что значит, что Поток 3 увидит удаляемую вершину стека в локальном указателе.

Производительность


Для этой статьи мы написали две реализации стека: одну lock-free, другую — с использованием std::mutex. Тестовая программа запускала несколько потоков, и вызывала Push и Pop с равной вероятностью в бесконечном цикле. Для замеров использовался Dell Precision T5500. Результаты показаны на графике ниже. Ось X — количество потоков, ось Y — количество операций в секунду.



Выглядит не очень впечатляюще.
Одна из проблем заключается в том, что по своей природе стек имеет очень узкое место — его вершину. Все потоки сражаются за то, чтобы изменить ее первыми, и производительность будет настолько высока, насколько быстро есть теоретическая возможность менять вершину. Операции Push и Pop настолько просты, что даже при использовании одного потока упираются в лимит количества изменений вершины стека в единицу времени. Добавление новых потоков только замедляет общую производительность, потому что теперь надо синхронизировать изменения вершины стека между потоками.
Другая проблема заключается в том, что когда несколько потоков одновременно пытаются поменять вершину стека, только один из них это успешно сделает, и все остальные потоки пойдут на новую итерацию. Это проблема. Как известно, у каждой проблемы есть быстрое, красивое но неправильное решение. Таким решением для этой проблемы будет добавить usleep(250) после неудачного CAS. Это простой, но не оптимальный способ заставить потоки меньше пересекаться при изменении вершины стека. Результат может показаться удивительным — добавление usleep(250) улучшает производительность в 10 раз! На практике мы используем немного более сложные подходы для уменьшения количества неудачных CAS, но как видно, даже такой простой подход, как usleep, дает отличные результаты.



Интересно также посмотреть на то, сколько ресурсов потребляют различные реализации:
Вот так выглядит HTOP для запуска с lock-free стеком без usleep в 16 потоках:



Как видно, процессор занят на 100%. Это связано с тем, что все потоки в цикле пытаются изменить вершину стека, снова и снова выполняя новую итерацию, целиком потребляя доступное им процессорное время.

Вот так выглядит HTOP для запуска с lock-free стеком с usleep в 16 потоках:



Процессор почти простаивает. Потоки, не сумевшие сразу поменять вершину, спят, не занимая процессор. Это удивительное наблюдение — добавление usleep не только увеличило полезную производительность в 10 раз, но и заметно понизило потребление процессорного времени.

Вот так выглядит HTOP для запуска со стеком с блокировками в 16 потоках:



Здесь хорошо видно, что процессор целиком занят системными вызовами. Иными словами, почти все процессорное время затрачено на работу с блокировками.

Заключение


Lock-free гарантирует, что система всегда будет выполнять полезную работу, даже если часть потоков была приостановлена операционной системой. Но lock-free не гарантирует, что это будет достигнуто эффективно. Кроме того, lock-free алгоритмы часто содержат ошибки, которые не всегда легко заметить или воспроизвести. Простая реализация стека в начале этой статьи содержала пять различных ошибок, и по производительности уступала реализации с блокировками. Если вы хотите использовать lock-free алгоритмы, убедитесь, что они того стоят, как с точки зрения производительности, так и с точки зрения сложности реализации. Старайтесь не изобретать свои собственные lock-free алгоритмы, а находить готовые реализации или научные работы.

Код


Исходный код
С блокировками:

 1 #include <mutex>
 2 #include <stack>
 3 
 4 template<class T>
 5 class LockedStack{
 6 public:
 7     void Push(T* entry){
 8         std::lock_guard<std::mutex> lock(m_mutex);
 9         m_stack.push(entry);
10     }
11 
12     // For compatability with the LockFreeStack interface,
13     // add an unused int parameter.
14     //
15     T* Pop(int){
16         std::lock_guard<std::mutex> lock(m_mutex);
17         if(m_stack.empty()){
18             return nullptr;
19         }
20         T* ret = m_stack.top();
21         m_stack.pop();
22         return ret;
23     }
24 
25 private:
26     std::stack<T*> m_stack;
27     std::mutex m_mutex;
28 };


Без блокировок (в коде отсутствует логика, отвечающая за очистку памяти)

 1 class LockFreeStack{
 2 public:
 3     // Элементы стека должны наследоваться от Node
 4     //
 5     struct Node{
 6         boost::atomic<Node*> next;
 7     };
 8
 9
10     // К сожалению, нет платформо-независимого способа написать этот класс.
11     // Приведенный код работает для gcc на архитектуре x86_64.
12     //
13     class TaggedPointer{
14     public:
15         TaggedPointer(): m_node(nullptr), m_counter(0) {}
16 
17         Node* GetNode(){
18             return m_node.load(boost::memory_order_acquire);
19         }
20 
21         uint64_t GetCounter(){
22             return m_counter.load(boost::memory_order_acquire);
23         }
24 
25         bool CompareAndSwap(Node* oldNode, uint64_t oldCounter, Node* newNode, uint64_t newCounter){
26             bool cas_result;
27             __asm__ __volatile__
28             (
29                 "lock;"
30                 "cmpxchg16b %0;"
31                 "setz       %3;"
32 
33                 : "+m" (*this), "+a" (oldNode), "+d" (oldCounter), "=q" (cas_result)
34                 : "b" (newNode), "c" (newCounter)
35                 : "cc", "memory"
36             );
37             return cas_result;
38         }
39     private:
40         boost::atomic<Node*> m_node;
41         boost::atomic<uint64_t> m_counter;
42     }
43     // Выравнивание по 16 байтам необходимо для правильной работы double cas
44     //
45     __attribute__((aligned(16)));
46     
47 
48     bool TryPushStack(Node* entry){
49         Node* oldHead;
50         uint64_t oldCounter;
51 
52         oldHead = m_head.GetNode();
53         oldCounter = m_head.GetCounter();
54         entry->next.store(oldHead, boost::memory_order_relaxed);
55         return m_head.CompareAndSwap(oldHead, oldCounter, entry, oldCounter + 1);
56     }
57 
58     bool TryPopStack(Node*& oldHead, int threadId){
59         oldHead = m_head.GetNode();
60         uint64_t oldCounter = m_head.GetCounter();
61         if(oldHead == nullptr){
62             return true;
63         }
64         m_hazard[threadId*8].store(oldHead, boost::memory_order_seq_cst);
65         if(m_head.GetNode() != oldHead){
66             return false;
67         }
68         return m_head.CompareAndSwap(oldHead, oldCounter, oldHead->next.load(boost::memory_order_acquire), oldCounter + 1);
69     }
70 
71     void Push(Node* entry){
72         while(true){
73             if(TryPushStack(entry)){
74                 return;
75             }
76             usleep(250);
77         }
78     }
79 
80     Node* Pop(int threadId){
81         Node* res;
82         while(true){
83             if(TryPopStack(res, threadId)){
84                 return res;
85             }
86             usleep(250);
87         }
88     }
89 
90 private:
91     TaggedPointer m_head;
92     // Умножение на восемь позволяет каждому локальному указателю быть в
93     //   своей собственной кеш-линии, что заметно ускоряет работу с ними.
94     //
95     boost::atomic<Node*> m_hazard[MAX_THREADS*8];
96 };



Код бенчмарка также доступен на github (если вы хотите запустить тест локально):

https://github.com/memsql/lockfree-bench

Update:


По предложению lostmsu добавил в бенчмарк стек со spinlock вместо std::mutex. Для чистоты эксперемента использовал spinlock, который, как и lockfree реализация, спит 250 миллисекунд, если не удается захватить блокировку с первой попытки. Не неожиданно, такая реализация оказалась производительнее и lock-free реализации, и реализации с std::mutex. Потребление процессора визуально такое же, как и у lock-free реализации с usleep(250).



Репозиторий на гитхабе тоже обновлен с новой реализацией.
+146
43071
475

Комментарии (50)

+1
lostmsu, #
А можно увидеть код бенчмарка?
+8
lostmsu, #
Объясню, почему спрашиваю: мне кажется, что если бы вы использовали spin lock вместо обычного мьютекса, производительность была бы на порядки выше.
+2
SkidanovAlex, #
В конце статьи есть ссылка на бенчмарк, можно запустить локально.
Идея со спинлоком хорошая — вечером напишу, и добавлю в статью результаты.
Если добавите сами, присылайте pull-request.
+4
datacompboy, #
и как итог со спинлоком?
+3
SkidanovAlex, #
Добавил в конец статьи. Все как предсказывал lostmsu.
+3
datacompboy, #
Спасибо. Просто чудесно доказательно, что lock-free для мутабельных языков — только лишний геморрой. :)
0
fossdev, #
Попробуйте реализацию с __try/__except вместо hazard pointers. Именно такая реализация используется в windows как на уровне ядра, так и в юзермоде. Там даже сделана специальная оптимизация, есть особая проверка в KiTrap0E, но и без такой оптимизации должно быть быстро.
0
Akson87, #
Когда начал читать статью, думал, что никогда не писал lock-free стек. А потом оказалось, что именно этим и занимался, только на GPU, ибо вариантов других там особо не было (ну кроме совсем медленных).
+2
mark_ablov, #
> Hazard Pointers
А как гарантируется что между точками «проверяем все локальные указатели» и «удаляем элемент» один из потоков не начнет работу с этим элементом?
+3
SkidanovAlex, #
Удаляющий поток:

1. Убрать A с вершины стека.
2. Прочитать все hazard-указатели, убедиться, что там нет A.
3. Удалить А.

Читающий поток:

a) Прочитать вершину стека
b) Сохранить прочитанную вершину в hazard указатель
c) Прочитать вершину стека опять. Если она изменилась, то перейти к a)

Если a) произошло до 1, но b) произошло после или в течение 2, то при повторной проверке (с)) вершина будет уже изменена, то есть проверка провалится, и мы перейдем опять к a), не начав работу с элементом.
0
kenoma, #
А что отложено по осям на графиках результатов замеров Dell Precision T5500?
0
shamg, #
X: Количество потоков, Y: операций в секунду
+3
klirichek, #
Хм… по поводу hazard pointer-ов.
А чем плох вариант, если поток при намерении изменить элемент, запишет его адрес не себе в «видимый снаружи указатель», а поставит метку (свой thread id, например) в спец. поле в самом элементе? А при освобождении — соответственно, стирает её.
А конкурирующий поток сперва проверяет метку, и если элемент свободен — ставит свою. А если занят (т.е. всё равно ждать) — либо ждёт, либо по вашим вариантам — кладёт в очередь и т.д.
Да, на эту метку уйдёт сколько-то памяти (она ведь в каждом элементе).
Но за счёт этого устранится необходимость ходить по hazard pointer-ам всех потоков.
0
quarck, #
Это видимо будет уже не lock-free, т.к. подобная метка — это по сути уже самодельный мьютекс (точнее спинлок, т.к. не зависит от ядра), причем рекурсивный ;)
0
klirichek, #
так-то да. Но ровно так же сыграет и наличие адреса этого элемента в некоем hazard-pointer потока.
Логика работы абсолютно та же, за исключением того, что не нужно перерывать массив hazard-pointer-ов в поисках «нет ли там вдруг этого элемента?».
+1
quarck, #
Продолжая рассуждения дальше, имхо не будет особой разницы, если сделать не lock-free код, но код использующий спин-локи, и максимально минимизирующий время пребывания в локе потоком, используя схемы доступа аналогичные первому «глючному» коду. Мне кажется используя спинлоки, можно достичь той-же производительности, и иметь при этом куда меньше проблем, т.к. со спин локом не составит труда например сделать:

spin_lock(m_lock);
old_head = m_head;
if(m_head != NULL)
    m_head = m_head->next;
spin_unlock(m_lock);


время, в течении которого тут будет удерживаться лок — это буквально время исполнения нескольких ассемблерных инструкций, сравнимо с оверхедом от lock-free кода.

P.S. Возможно просто стек — не очень удачный пример структуры данных, на которой получается большой выйгрыш от lock-free
0
klirichek, #
Разницы почти не будет только если вместо прямой блокировки использовать «try» функцию
(вроде TryEnterCriticalSection под windows или аналога в других системах).

А если как у вас — то это в чистом виде lock-код, со всеми вытекающими, описанными в начале статьи. Его проблема — в том, что нет никакого гарантированного «времени исполнения нескольких ассемблерных инструкций». Никто не обещает, что во время блокировки не произойдёт переключения контекстов, и ваш поток не уйдёт в спячку, может даже надолго. И другие потоки тогда тоже будут вынуждены стоять на входе в блокировку.
0
quarck, #
Да, тут вы правы. У меня большая часть опыта работы со spin_lock-ами из ядра растет, а там проблем, что кто-то тебя вытеснит — не было.
0
JuriyOgijenko, #
Это самодельный Lock. А что будет если поток у вас упадет после того как установил свой thread id? Кто будет освобождать ресурс?
+2
klirichek, #
Я думаю, тот же код, что удалит hazard-pointer на уровне потока в случае его смерти.
0
SkidanovAlex, #
Тогда не понятно что делать, если более одного потока хотят работать с элементом. Первый поток поставил свой thread id в спец поле, и начал работать с элементом. Второй поток теперь свой thread id поставить не может, но и надеяться, что первый поток продержит элемент достаточно долго, тоже нельзя.
0
klirichek, #
А это просто такой вариант hazard-pointer-а, без необходимости поиска.
Соответственно, решение в самой статье, раздел segfault
0
klirichek, #
Вот! Вся фишка, что у второго потока теперь есть ВЫБОР!
В случае лока он может только уснуть в функции блокировки. А здесь он может принять решение. Например, так же лечь спать. (но тогда в чём смысл делать lock-free?). Или сделать что-нибудь полезное.
0
rustler2000, #
Кстати — а кэш не профайлили? Думаю что ему живется существенно легче с usleep
0
Gorthauer87, #
Думаю, что перед тем как искать хорошие реализации, можно в тестовом проекте и походить по граблям.
+1
OpenMinded, #
Походить по граблям самому конечно очень интересно и полезно, но сложность lock-free алгоритмов нельзя недооценивать, если сам Jon Skeet в большинстве случаев предпочитает locking.
0
artemaliev, #
В параллельном программировании грабли (race condition) случаются раз в год и только у заказчика :). ABA проблем в этом деле чемпион. Так что никаких велосипедов и много верификации алгоритмов.
+5
artemaliev, #
Хм, описывая ваше решение коротко: контеншин на одной ячейке памяти (кеш линии) — это плохо, давайте займем чем-нибудь потоки на время 250usec (для статьи это sleep, но у нас есть еще и секретный способ :). Кроме того, что в жизни потоки и так заняты чем-то еще кроме pop и push, использует для этого очень секретный способ: Room synchronization. В простейшем виде: можно копить push() каждого локального среда в маленький list и раз 250usec добавлять его целиком, с pop() чуть сложнее :). Если у вас стэк основанный на массиве, то у вас две комнаты в одной собираются потоки которые хотят сделать push и получают номерки со смещением куда они будут вписывать данные, в другой комнате pop() потоки со смещением откуда читать. И переключатель, пока одни парни параллельно пишут, каждый в свою ячейку, вторые копятся, потом парни меняются. Как быстро раздавать номерки это еще один очень секретный алгоритм.
+2
antoshkka, #
А чем вас не устроил boost_1_53_0/boost/lockfree/stack.hpp (оттестированное решение работающее на множестве платформ)?
0
Unhandled_Exception, #
Расскажите, пожалуйста, про автоматическую проверку таких алгоритмов. Ведь наверняка есть какие-то наработки.
0
metar, #
Возможно, уместно запостить немного state of the art: комбинация техник separation logic и rely-guarantee, носящая имя RGsep, была специально заточена, чтобы сделать формальные доказательства memory safety и linearisability неблокирующих алгоритмов подъемными. В частности, если интересна теория, то по ссылке вроде как есть примеры с неблокирующим стеком, разными реализациями списков. Насколько хороша утилита, делающая это автоматически, пока не интересовался.
+3
olekl, #
«В случае для стека, каждый поток имеет спецальный видимый всем указатель (назовем его «локальный указатель»), где хранится адрес элемента, с которым данный поток работает в настоящий момент.»

Может, я чего-то не понял — но чем это от блокировки отличается? Если поток, который собирался поменять элемент и поместил его адрес в «локальный указатель», отправится системой спать, то никакой другой поток этот элемент поменять не сможет, ведь так?
0
SkidanovAlex, #
Никто другой не сможет очистить занятую им память. Класть его на стек и убирать его со стека по прежнему можно.
0
ivanrt, #
Все прочитанное вызвало у меня ощущение разумности за исключением 42, что подвергает сомнению всё остальное.
Замена выровненного машинного слова в памяти не вызывает случайного значения при чтении. Невыровненые или не размером в регистр машины — легко, выровненные — нет. В противном случае managed runtimes, ака Java и другие должны падать постоянно, так как там объекты хранят указатели на другие объекты и ссылки меняются и читаются в разных трэдах. Я сам участвовал в написании JVM и без этого просто ничего не выйдет.
+2
SkidanovAlex, #
Когда в С++ что-то определено как Undefined Behavior, это не всегда значит, что на практике оно действительно поведет себя не так, как ожидается. Это всего лишь значит, что не гарантируется, что оно поведет себя так, как ожидается. Я очень сомневаюсь, что на современном железе действительно может быть возвращено что-то кроме 100 и 200, но поведение не определенное, и лучше сделать надежно.

Но иногда неопределенное поведение действительно ведет себя непредсказуемо. Например, угадайте, что выведет вот такой код, скомпилированный g++ с -O2?
for (int i = 0; i >= 0; ++ i)
{
    if (i % 1000000000 == 0) printf("%d\n", i);
}

0
Lockal, #
Почему gcc не предупреждает об этом? Вроде не так сложно выявить int % unsigned long. Или для этого есть скрытый флаг, не входящий в -Wall -Wextra?
0
SkidanovAlex, #
Проблема не во взятии по модулю, проблема в переполнении i — это заметить сложнее. Переполнение знакового типа — это неопределенное поведение. В данном случае g++ заменяет цикл на while (true), потому что i может только увеличиваться, а значит i >= 0 всегда верно. Так как переполнение знакового типа неопределено, здесь компилятор имеет право сделать такое предположение.
НЛО прилетело и опубликовало эту надпись здесь
0
SkidanovAlex, #
5.4
If during the evaluation of an expression, the result is not mathematically defined or not in the range of representable values for its type, the behavior is undefined.


Так что знаковое переполнение — это неопределенное поведение.
Беззнаковое переполнение определено:

3.9.1.4.
Unsigned integers, declared unsigned, shall obey the laws of arithmetic modulo 2^n where n is the number of bits in the value representation of that particular size of integer.


В С++11 появились знаковые типы int16_t, int32_t, int8_t, int64_t, для которых переполнение определено.
НЛО прилетело и опубликовало эту надпись здесь
0
Lockal, #
Я бы отнёс это к -Wstrict-overflow=1. В крайнем случае, предупреждению точно есть место среди пяти уровней -Wstrict-overflow. Вечером поищу багрепорты/рассылки на эту тему, т. к. надо бы добавить предупреждение.
–3
mwizard, #
Думаю, что-то типа этого:
./a.cpp:1: error: expected unqualified-id before ‘for’
./a.cpp:1: error: expected constructor, destructor, or type conversion before ‘>=’ token
./a.cpp:1: error: expected unqualified-id before ‘++’ token</code>
+1
fossdev, #
hazard pointers это очень громоздкое и негибкое решение. Число потоков заранее неизвестно, их могут быть тысячи, они могут появляться и исчезать. Контейнер завязанный на конкретные потоки очень негибок.
Вы не думали что если из-за освобождения памяти возникает исключение, проще всего будет его ловить? Просто поставить __try/__except?
0
datacompboy, #
тысячи физических потоков OS? что-то надо в консерватории править.
0
gritzko, #
«Версии указателей» — это из серии «побеги модели Лампорта прорастают через трещины в асфальте».
0
olegdunkan, #
Если представить что стек содержит в себе запросы, а потоки забирают от туда элементы для обработки, то тогда какая разница, что там новый элемент-запрос, находящийся по адресу А, он же является таким же запросом, таким образом проблема АВА, зависит от того, что реализует стек. В вашем примере: «Поток 1 просыпается, и вызывает CAS. CAS выполняется успешно, не смотря на то, что за это время m_head изменился три раза! Как следствие, элемент B потерян.» Элемент В продолжает находиться в цепочке, а новый элемент запрос по адресу А в вершине стека (А->В->C), он его забирает и обрабатывает. Другое дело, если важно получить именно тот, первый элемент из стека, который раньше располагался по адресу А.
0
olegdunkan, #
т.е в вашем примере:
1.Допустим, что в стеке сейчас два элемента, A -> C.
2. Поток 1 вызывает Pop, читает в строке 22 m_head (A), в строке 26 читает old_head->next (С), а затем операционная система усыпляет поток.
3. Поток 2 вызывает Pop, и успешно убирает элемент A.
4. Поток 2 вызывает Push, и успешно вставляет элемент B.
5. Поток 2 вызывает Push опять, и вставляет элемент, расположенный по тому же адресу, что и A (либо A был освобожден, и затем другой элемент был заведен по тому же адресу, либо пользователь решил вставить элемент, который он только что взял со стека, обратно)
Поток 1 просыпается, и вызывает CAS. CAS выполняется успешно, не смотря на то, что за это время m_head изменился три раза! Как следствие, элемент B потерян

Стек
1. А->C
2. А->C
3. C
4. B->C
5. A (new)->B->C
6. B->C
каким образом мы теряем B?
0
olegdunkan, #
Понял, вопрос снимаю, я вызов CAS рассмотрел как атомарную операцию, с учетом получения в момент пробуждения потока аргументов, тут надо было уточнить, что уснул поток сразу перед инструкцией вызова, но перед занесением аргументов в стек вызова.
0
asArtem, #
для тех, кто будет читать эту статьию и пишет на C#
Статья будет не актуальна, в случае, если CAS реализован правильно, т.е. атомарно. Interlocked это позовляет делать. Также пишут, что есть атомарные CAS реализации в других ОС, но не в Windows…
От куда взято: boyet com/Articles/LockfreeStack.html

private static bool CAS( ref Node location, Node newValue, Node comparand )
{
// 1. если comparand и location равны, то другой поток не трогал значение location.
// 2. location будет присвоен newValue.
// 3. Метод вернёт старое значение location не зависимо от присвоения.
// 4. copmarand сранится со старым значением location (node.Next == старый head.Next ?)
// 5. если location(старый, возвращенный) не был изменён другим потоком то и CAS вернёт true, т.к. он совпадёт с comparand
return comparand == Interlocked.CompareExchange( ref location,
newValue,
comparand);
}

Там даже автор отвечает на безосновательное обвинение в якобы АВА проблема. Но т.к. CAS атомарен, то ABA проблемы не будет.
0
SkidanovAlex, #
> Также пишут, что есть атомарные CAS реализации в других ОС, но не в Windows…
А авторы WinAPI и не знают…
http://msdn.microsoft.com/en-us/library/windows/desktop/ms683560(v=vs.85).aspx
«Performs an atomic compare-and-exchange operation on the specified values.»

CAS везде атомарен. Код по вашей ссылке действительно не страдает от ABA проблемы, но не потому, что его CAS как-то более атомарен чем CAS в С++, а потому что в C# автоматический сборщик мусора (о чем он и говорит), Соответственно если мы увидели элемент на стеке, пока мы на него держим ссылку, память по этой ссылке не освободится, новый элемент по этому адресу не заведется, и проблема ABA не случится.

Только зарегистрированные пользователи могут оставлять комментарии.
Войдите, пожалуйста.