Реализация всплывающего окна без блокировки в C ++

Question

В C ++ Concurrency in Action, 2e, автор описывает реализацию связанного списка без блокировки потоков. Прямо сейчас он описывает метод pop () и то, как безопасно удалить узлы в своего рода методе «сборщика мусора», чтобы убедиться, что никакие другие потоки не вызывают pop в том же экземпляре. Вот часть этого кода для pop:

#include <atomic>
#include <memory>

template<typename T>
class lock_free_stack
{
private:
    std::atomic<unsigned> threads_in_pop;
    void try_reclaim(node* old_head);
public:
    std::shared_ptr<T> pop()
    {
        ++threads_in_pop;
        node* old_head=head.load();
        while(old_head &&
              !head.compare_exchange_weak(old_head,old_head->next));
        std::shared_ptr<T> res;
        if(old_head)
        {
            res.swap(old_head->data);
        }
        try_reclaim(old_head);
        return res;
    }
};

Важно то, что счетчик атомарно увеличивается каждый раз при вызове pop (). Затем функция try_reclaim уменьшит значение счетчика. Вот реализация try_reclaim:

void try_reclaim(node* old_head)
{
    if(threads_in_pop==1) //#1
    {
        node* nodes_to_delete=to_be_deleted.exchange(nullptr);
        if(!--threads_in_pop) //#2
        {
            delete_nodes(nodes_to_delete);
        }
        else if(nodes_to_delete)
        {
            chain_pending_nodes(nodes_to_delete);//#3
        }
        delete old_head; //#4 THIS IS THE PART I AM CONFUSED ABOUT
    }
    else
    {
        chain_pending_node(old_head);
        --threads_in_pop;
    }
}

Реализации других функций, вызываемых здесь, не имеют значения (они просто добавляют узлы в цепочку узлов, подлежащих удалению), поэтому я их пропустил. Часть кода, которая меня запутала, - это №4 (отмечена). Здесь автор вызывает delete для переданного old_head. Однако почему он не проверяет, является ли значение thread_in_pop по-прежнему равным нулю в этот момент, прежде чем удалять old_head? Он дважды проверяет строки №2 и №1, чтобы убедиться, что другой поток в настоящее время не находится в pop (), так почему он не проверяет еще раз, прежде чем продолжить удаление old_head? Не мог ли другой поток вызвать pop () сразу после # 3, увеличив таким образом счетчик, и к тому времени, когда первый поток достигнет # 4, thread_in_pop больше не будет равным нулю?

Другими словами, не могло ли быть возможным, чтобы thread_in_pop было, например, 2, к тому времени, когда код достигнет # 4? Как он мог в таком случае безопасно удалить old_head? Может кто-нибудь объяснить, пожалуйста?

Answer 1

Поток, который вызывает try_reclaim, только что удалил old_head из стека.

Класс гарантирует, что любое другое использование old_head должно быть внутри pop вызовов из других потоков, поэтому, если поток обнаруживает, что других параллельных вызовов нет, то он знает, что является эксклюзивным держателем указателя old_head. Затем, пока он не публикует sh этот указатель, чтобы он мог быть взят из другого потока, он может удалить его всякий раз, когда доберется до него.

Таким образом, реализация безопасна. Заданный вами вопрос: «Почему он не проверяет [еще раз]?» Означает, что вы думаете об этом неправильно. Повторная проверка ничего не докажет, потому что если бы другой поток мог попасть в pop и использовать old_head, то это могло бы всегда случиться после вы проверяете!

Answer 2

У вас есть следующая (упрощенная) последовательность, и все операции atomi c последовательно согласованы:
++threads_in_pop -> head.cmpxchg -> threads_in_pop.load() -> delete old_head

Итак, мы сначала удаляем текущую головку, а затем проверяем количество threads_in_pop. Предположим, у нас есть два потока, T1 и T2, которые работают в стеке. Если T1 выполняет threads_in_pop.load() (# 1) в try_reclaim и видит 1, это означает, что T2 еще не выполнил приращение (++threads_in_pop), т.е. T1 - единственный поток, который может иметь ссылку на old_head в таком случае. Однако T1 уже удалил old_head из списка, поэтому любой поток, который входит в pop, уже увидит обновленную голову, поэтому никакой другой поток, возможно, больше не сможет получить ссылку на old_thread. Поэтому безопасно удалить old_head.

Проверка №2 необходима, чтобы не освобождать узлы, которые только что были добавлены в список to_be_released после того, как этот поток выполнил свое всплывающее сообщение. , но другие потоки все еще могут содержать ссылку. Рассмотрим следующую ситуацию:

• T1 выполняет всплывающее сообщение и собирается выполнить nodes_to_delete=to_be_deleted.exchange(nullptr);
• T2 запускает всплывающее окно и читает head
• T3 запускает всплывающее окно и читает head, видя то же значение, что и T2
• T2 завершает свое всплывающее окно и добавляет old_head в список
• ПРИМЕЧАНИЕ: T3 все еще имеет ссылку на узел, который теперь является частью список to_be_deleted
• T1 теперь выполняет nodes_to_delete=to_be_deleted.exchange(nullptr);

T1 теперь имеет список nodes_to_delete, который содержит ссылку на узел, к которому T3 все еще может получить доступ. Вот почему необходима проверка №2, чтобы не дать T1 освободить этот узел.