W wspólnym std::forward_list jest bezpieczny dla wielu wątków, aby połączyć insert_after jednocześnie, jeśli gwarantują, że nigdy nie nazywają go taką samą pozycją iterator? Wygląda na to, że może to być bezpieczne, że wkładka jest gwarantowana, aby nie unieważnić innych ieratorów, a pojemnik nie ma metody size(), ale może coś brakuje?

Edytować:

Napisałem mały program testowy tortur, który wydaje się uruchamiać w clangu bez blokowania:

#include <forward_list>
#include <iostream>
#include <thread>
#include <vector>

using List = std::forward_list< int >;
using It = List::const_iterator;

void insertAndBranch (List& list, It it, int depth)
{
    if (depth-- > 0) {
        It newIt = list.insert_after (it, depth);
        std::thread thread0 ([&]{ insertAndBranch (list, it, depth); });
        std::thread thread1 ([&]{ insertAndBranch (list, newIt, depth); });
        thread0.join();
        thread1.join();
    }
}

int main()
{
    List list;
    insertAndBranch (list, list.before_begin(), 8);

    std::vector< It > its;
    for (It it = list.begin(); it != list.end(); ++it) {
        its.push_back (it);
    }
    std::vector< std::thread > threads;
    for (It it : its) {
        threads.emplace_back ([&]{ list.insert_after (it, -1); });
    }
    for (std::thread& thread : threads) {
        thread.join();
    }

    for (int i : list) {
        std::cout << i << ' ';
    }
    std::cout << '\n';
}

Wiem, że nic nie udowodni, ale sprawia, że mam nadzieję, że jest to bezpieczne. Nie jestem pewien, czy mogę go użyć bez pewnego potwierdzenia ze standardu.

2
atb 17 luty 2017, 16:23

2 odpowiedzi

Najlepsza odpowiedź

W wspólnym std::list jest bezpieczny dla wielu wątków do wstawienia jednocześnie, jeśli gwarantują, że nigdy nie nazywają go tym samym Ustaw ierator?

Nie. Nie byłoby bezpieczne ... (bez względu na wszystko).

Wkładanie do std::list będzie wymagał dostępu do previous node i next node do pozycji iteratora i size listy.

Nawet jeśli pozycje są daleko od siebie, prosty fakt, że {{x0} } jest wymagany do stały czas (C ++ 11). Oznacza to, że każde wstawianie zaktualizuje std::list::size().


Edytować:

W wspólnym {x0}} jest bezpieczny dla wielu wątków Zadzwoń do insert_After jednocześnie, jeśli gwarantują, że nigdy go nie nazywają z taką samą pozycją Iterator?

To nie jest bezpieczne. i nie zalecany. No Container STL został zaprojektowany z bezpieczeństwem gwintu.


W każdym razie pozwala przyjmować kilka podstawowych gwarancji, zakładaj, że bardzo prosta wersja {x1}}: insert_after modyfikuje węzeł wskazany przez iteratora, aby węzeł pojawi się teraz do nowo włożonego węzła, podczas gdy nowo włożone węzeł wskazuje na następny węzeł. Tak więc będzie "bezpieczny", jeśli Iteratorzy są co najmniej dwa węzły od siebie, a twój alokator jest bezpieczny.

Ilustracja:

Initial Forward_list
A -> B -> C -> D -> E

Insert K after C
A -> B -> C x D -> E
           \ /
            K

Jak widać, C jest czytana i modyfikowana. D można odczytać, podczas gdy włożono K.


Co do tego, dlaczego powiedziałem "przynajmniej dwa węzły", pozwala nabrać przypadek jednego węzła: Zakładając dwa wątki chcą wstawić K po C i M po M po M }} Odpowiednio:

Initial Forward_list
A -> B -> C -> D -> E

Insert K after C
A -> B -> C x D x E
           \ / \ /
            K   M

Z cppreference:

Gdy ocena wyrażenia pisze do lokalizacji pamięci i kolejna ocena odczytuje lub modyfikuje tę samą lokalizację pamięci, mówi się, że wyrażenia są konfliktowe.

1
WhiZTiM 17 luty 2017, 14:36

Nawet Czytaj Operacje są bezpieczne, gdy inny wątek pisze do listy (patrz Oto do dalszych wyjaśnień); Więc: wiele pisze nie jest bezpieczne:

Podczas odczytu z listy bez blokady nie zostanie uszkodzony listy, jeśli lista zostanie zmodyfikowana, gdy inny wątek odczytuje z niego, albo wątek może stać się uszkodzony (tj. Awaria lub wytwarza nieprawidłowe wyniki).

Potrzebujesz trochę zamka. Okres.

2
Community 23 maj 2017, 12:24