Можно ли их использовать? читаю книжку Antony Williams по многопоточности в c++0x. Написал lock free стек на STD атомиках. Но все падает. Сверил каждую строчку с тем как написано у него ну и мозгом понимаю что все нормально должно быть
Есть подозрение что атомик операции не вставляют барьеры памяти типа это вообще не реализовано и использовать их нет смысла. Кто-нибудь уже пробовал с ними работать?
Вот та реализация lock-free стека которая падает у меня.
Кстати если закомментировать строчки выделеные жирным, то падать перестаёт.
Ну и разумеется для воспроизведения падения, необходимо что бы pop вызывали несколько потоков.
template<typename T>
class lf_stack_pop_dummy_guard
{
public:
lf_stack_pop_dummy_guard() :
head_(0), threads_in_pop_(0), to_be_deleted_(0)
{}
lf_stack_pop_dummy_guard(const lf_stack_pop_dummy_guard&) = delete;
lf_stack_pop_dummy_guard& operator=(const lf_stack_pop_dummy_guard&) = delete;
~lf_stack_pop_dummy_guard()
{
node* head = head_.load(std::memory_order_relaxed);
while(head)
{
node* old_head = head;
head = head->next_;
delete old_head;
}
}
void push(const T& val)
{
node* const new_node = new node(val);
new_node->next_ = head_.load();
while(!head_.compare_exchange_weak(new_node->next_, new_node));
}
std::shared_ptr<T> pop()
{
++threads_in_pop_;
node* old_head = head_.load();
while(old_head && !head_.compare_exchange_strong(old_head, old_head->next_));
std::shared_ptr<T> res;
if (old_head)
res.swap(old_head->data_);
node* nodes_to_delete = to_be_deleted_.load();
if (!--threads_in_pop_)
{
if (to_be_deleted_.compare_exchange_strong(nodes_to_delete, 0))
delete_nodes(nodes_to_delete);
delete old_head;
}
else if (old_head)
{
old_head->next_ = nodes_to_delete;
while(!to_be_deleted_.compare_exchange_weak(old_head->next_, old_head));
}
return res;
}
private:
struct node
{
node(const T& data) : data_(new T(data)), next_(0) {}
node() = delete;
node(const node&) = delete;
node& operator=(const node&) = delete;
std::shared_ptr<T> data_;
node* next_;
};
static void delete_nodes(node* head)
{
while(head)
{
node* next = head->next_;
delete head;
head = next;
}
}
std::atomic<node*> head_;
std::atomic<unsigned> threads_in_pop_;
std::atomic<node*> to_be_deleted_;
};
Здравствуйте, TarasKo, Вы писали:
есть вопрос и несколько предложений.
1. какая архитектура ? x86 ?
для проверки самого алгоритма можно:
2. переписать код с использоанием TBB атомиков (
http://threadingbuildingblocks.org/files/documentation/a00117.html)
3. попробовать Relacy Race Detector (
http://www.1024cores.net/home/relacy-race-detector), там ксати вроде как и реализация С++0х атомиков есть тоже, можно ее попробовать
4. ИМХО в кодe метода pop есть шанс (хоть и маловероятный) бесконечного роста списка к удалению (to_be_deleted_). Сценарий такой:
1. первый поток, уменьшая счетчик потоков, входит в ветку if и засыпает
2. второй поток входит в pop (увеличивая счетчик потоков) и засыпает
3. третий поток входит в pop (увеличивая счетчик потоков), заходит в вветку else и меняет to_be_deleted_
4. первый поток просыпается, проваливается на compare_exchange (выделено жирным), и выходит
теоритически, такая последовательность может, повторяться бесконечное число раз, приводя к бесконечному накапливанию памяти.
std::shared_ptr<T> pop()
{
++threads_in_pop_;
node* old_head = head_.load();
while(old_head && !head_.compare_exchange_strong(old_head, old_head->next_));
std::shared_ptr<T> res;
if (old_head)
res.swap(old_head->data_);
node* nodes_to_delete = to_be_deleted_.load();
if (!--threads_in_pop_)
{
if (to_be_deleted_.compare_exchange_strong(nodes_to_delete, 0))
delete_nodes(nodes_to_delete);
delete old_head;
}
else if (old_head)
{
old_head->next_ = nodes_to_delete;
while(!to_be_deleted_.compare_exchange_weak(old_head->next_, old_head));
}
return res;
}
Спасибо за ссылки.
Да, архитектура x86. Я запускал на двухядерной машине.
Про TBB атомики почитаю.
Про Relacy Race Detector много раз слышал, и следующее что собирался сделать, воспользоваться им
Да, эта memory reclamation схема не очень хороша при очень частом вызове pop, в книжке тоже об этом сказано. Потом идут примеры с использованием hazard pointer-ов и счётчика ссылок. Однако программа падает довольно быстро. Дольше 5 секунд и не может продержаться, при одном потоке который пушит и двух попающих потоках. К сожалению не могу привести backtrace, сейчас на работе, приду домой скину.
Ещё я тут подумал что вот в этом месте
if (!--threads_in_pop_)
{
if (to_be_deleted_.compare_exchange_strong(nodes_to_delete, 0))
delete_nodes(nodes_to_delete);
теоретически возможна ABA проблема. Между
if (!--threads_in_pop_)
и
if (to_be_deleted_.compare_exchange_strong(nodes_to_delete, 0))
некие другие потоки могут удалить текущий nodes_to_delete, потом в пуше он выделится заново, потом будет помещён вновь в to_be_deleted_. При этом кто-то может продолжать его использовать. Изначальный поток который уснул между этими двумя командами проснётся и благополучно удалит эту ноду хотя threads_in_pop_ != 0 и эта нода используется в другом потоке.
Для реализации такого сценария, нужно как минимум три потока вызывающих pop. А у меня падает с двумя потоками. Поскольку всё это скомпилено с -std=с++0x да ещё с 4.6.0 я не знаю на кого грешить. На книжку, на себя или на компилятор и сырую реализацию стандартной библиотеки