Можно ли их использовать? читаю книжку 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 я не знаю на кого грешить. На книжку, на себя или на компилятор и сырую реализацию стандартной библиотеки