• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Stos bez blokad

VPS Starter Arubacloud
0 głosów
104 wizyt
pytanie zadane 10 września 2022 w C i C++ przez RufinB Obywatel (1,830 p.)

Czytając książkę o przetwarzaniu współbieżnym natrafiłem na fragment który mówi o konieczności pozbycia się wskaźnika next z usuwanego węzła aby uniknąć potencjalnego niebezpieczeństwa głęboko zagnieżdżonego uszkodzenia węzłów po usunięciu ostatniego egzemplarza std::shared_ptr który odwołuje się do danego węzła. Czy mógłby ktoś wytłumaczyć w jakiej okoliczności występuje ten błąd poniżej umieszczam kod tej klasy stosu problematyczna linijka znajduje się w funkcji pop

template<typename T>
class lock_free_stack
{
private:
    struct node
    {
        std::shared_ptr<T> data;
        std::shared_ptr<node> next;
        node(T const& data_):
            data(std::make_shared<T>(data_))
        {}
    };
    std::shared_ptr<node> head;
public:
    void push(T const& data)
    {
        std::shared_ptr<node> const new_node=std::make_shared<node>(data);
        new_node->next=std::atomic_load(&head);
        while(!std::atomic_compare_exchange_weak(&head,
                  &new_node->next,new_node));
    }
    std::shared_ptr<T> pop()
    {
        std::shared_ptr<node> old_head=std::atomic_load(&head);
        while(old_head && !std::atomic_compare_exchange_weak(&head,
                  &old_head,std::atomic_load(&old_head->next)));
        if(old_head)  {
            std::atomic_store(&old_head->next,std::shared_ptr<node>());
            return old_head->data;
        }
        return std::shared_ptr<T>();
    }
    ~lock_free_stack(){
        while(pop());
    }
};

 

 

 

1 odpowiedź

0 głosów
odpowiedź 11 września 2022 przez mokrowski Mędrzec (155,460 p.)
wybrane 11 września 2022 przez RufinB
 
Najlepsza
Czy ten pop() jest efektywny? Nawet w destruktorze masz pętlę która wołając pop() przechodzi po liście kilkukrotnie (okolice while czyli linia 25). Oczywiście jeśli to wymaganie, nie mam uwag (ale jak trzymasz head, można poświęcić jeden wskaźnik także na tail to będziesz miał lepszą efektywność pop().. nie będziesz robił malarza Shlemiel'a: https://www.joelonsoftware.com/2001/12/11/back-to-basics/ ).

Pytasz o łańcuch destrukcji wynikający z lawiny wywołań usunięcia wskaźnika inteligentnego, który wywołuje usunięcie następnego .. itd. Łatwo wtedy zauważyć że każde z wywołań odłoży na stos powrót do elementu szczytowego. Stąd może wystąpić przepełnienie stosu (stack overflow). Tu masz to przystępnie opisane: https://www.codeproject.com/Questions/321104/Shared-Pointers-Deallocation

Tu w formie wizualnej jeszcze więcej: https://www.youtube.com/watch?v=JfmTagWcqoE

BTW. Używasz atomic trochę bez świadomości wydajności. One ogólnie nie mają sensu wydajnościowo (a głównie po to są) bez memory order https://en.cppreference.com/w/cpp/atomic/memory_order. Polecam: https://www.youtube.com/watch?v=ZQFzMfHIxng
komentarz 11 września 2022 przez j23 Mędrzec (194,920 p.)
Chyba nawet w innym wątku sugerowałem mu, że te usuwanie w destruktorze następnego elementu listy (bo tam o listę chodziło) jest ryzykowne.

Podobne pytania

0 głosów
1 odpowiedź 172 wizyt
pytanie zadane 27 września 2022 w C i C++ przez RufinB Obywatel (1,830 p.)
0 głosów
2 odpowiedzi 342 wizyt
pytanie zadane 22 listopada 2017 w C i C++ przez foruminfa Początkujący (310 p.)
0 głosów
0 odpowiedzi 297 wizyt
pytanie zadane 6 kwietnia 2022 w C i C++ przez trampek Nowicjusz (120 p.)

92,451 zapytań

141,261 odpowiedzi

319,073 komentarzy

61,853 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...