Здравствуйте, 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;
    }