Игрушечный пример параллельного стека через атомарные переменные и шаблон CAS

Я написал игрушечный пример параллельного стека, в котором всего три функции push(), peek(), и length(). Я использовал атомарные переменные для синхронизации. Что-то не так в плане синхронизации? Не могли бы вы просмотреть этот код?

#include <iostream>
#include <thread>
#include <atomic>
#include <vector>

template <typename T>
struct Node {
    Node<T>* next{};
    T val{};
    Node(const T& v) : val(v) {};
};

template <typename T>
class Stack {
    std::atomic<Node<T>*> top{};
    std::atomic<size_t> size{};
    public:
    void push(const T& data) {
        Node<T>* node = new Node<T>(data);
        size_t length = size.load(std::memory_order_relaxed);
        node->next = top.load(std::memory_order_relaxed);
        while(!std::atomic_compare_exchange_weak_explicit(&top, &node->next, node, std::memory_order_release, std::memory_order_relaxed));
        while(!std::atomic_compare_exchange_weak_explicit(&size, &length, size + 1, std::memory_order_release, std::memory_order_relaxed));
    }
    Node<T>* peek() {
        return top.load();
    }
    size_t length() const {
        return size;
    }
};

template <typename T>
class Runner {
    int cnt{};
    Stack<T>* ss{};
    public:
        Runner(const int n, Stack<T>* s) : cnt(n), ss(s) {}
        void operator()() {
            for(int i = 0; i < cnt; ++i) {
                size_t size = ss->length();
                if(size >= cnt) {
                    return;
                }
                ss->push(i);
            }
        }
        Stack<T>* get_stack() const {
            return ss;
        }
};

int main() {
    std::vector<std::thread> threads{};
    Stack<int>* s = new Stack<int>();
    int n = 10;
    Runner<int> r(n, s);
    for(int i = 0; i < 3; ++i) {
        threads.push_back(std::move(std::thread(r)));
    }
    for(int i = 0; i < 3; ++i) {
        threads[i].join();
    }
    Stack<int>* top = r.get_stack();
    Node<int>* head = top->peek();
    while(head) {
        std::cout << head->val << ", ";
        head = head->next;
    }
    size_t size = top->length();
    return 0;
}

2 ответа
2

Именование

Моя немедленная реакция такова, что без pop (или что-то подобное) на самом деле это не стек. Особенно учитывая приведенный ниже пункт о раскрытии деталей реализации, с точки зрения клиента это действительно связанный список, который поддерживает только пару операций: добавление узлов в начало, получение длины и (зная реализацию) обход списка.

Раскрытие внутренних деталей

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

Избегание условий гонки

Я бы также поставил под сомнение (по крайней мере, в некоторой степени) включение length в интерфейсе. В многопоточной среде почти все возможные варианты использования length практически гарантированно введут условия гонки — к тому времени, когда вы действительно попытаетесь использовать длина, которую вы прочитали, могла измениться, поэтому вы используете устаревшую информацию.

Может иметь смысл (по крайней мере, вроде) использовать length для таких вещей, как ведение журнала, просто чтобы дать пользователю хотя бы некоторое представление о том, постоянно ли растет стек (например) (но в этом случае это в значительной степени само собой разумеющееся, поскольку вы пропустили pop из его интерфейса).

Примечание

Не сразу видно, думаете ли вы о Runner как часть Stack сам или дополнительный класс, который вы включили, чтобы продемонстрировать / протестировать фактическое Stack. По крайней мере, сейчас я относился к нему как к вспомогательному, поэтому он показывает, как Stack используется, но я не пробовал рассматривать его отдельно.

    Чтобы добавить к ответу Джерри Коффина:

    Шаг struct Node в class Stack

    А Node это просто деталь реализации Stack, поэтому переместите объявление первого во второе. В качестве бонуса вам не придется повторять <T>. Вот как это выглядит:

    template <typename T>
    class Stack {
    public:
        struct Node {
            Node* next{};
            T val{};
            Node(const T& v): val(v) {};
        };
    
    private:
        std::atomic<Node*> top{};
        ...
    };
    

    Хотя я согласен с Джерри Коффином, что у вас должен быть надлежащий pop() вместо peek(), использование последнего теперь будет выглядеть так:

    Stack<int>::Node* head = top->peek();
    

    Хотя вам следует просто использовать auto Вот:

    auto head = top->peek();
    

    Не забудьте очистить память

    Понимаю new в вашем коде, но нет delete. Это означает, что у вас утечка памяти. Обычно я бы рекомендовал вам использовать std::unique_ptr<> для управления памятью, но поскольку вы используете атомарные указатели, это не работает. Поэтому убедитесь, что вы добавили деструкторы в Node и Stack чтобы ресурсы были очищены правильно.

    И в main(), нет причин использовать new создать новый Stack, просто объявите его в … стеке:

    Stack<int> s;
    Runner<int> r(n, &s);
    

    Использовать emplace_back()

    В следующей строке move() не нужно:

    threads.push_back(std::move(std::thread(r)));
    

    Это потому что std::thread(r) является временным, и поэтому перегрузка push_back() будет выбрана ссылка на r-значение. Однако еще лучше использовать emplace_back(), тогда вы можете просто написать:

    threads.emplace_back(r);
    

    • Большое спасибо за обзор и за ваше время.

      — user37014

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *