Jak zbudować kolejkę bez blokady?

Spędziłem dziś patrząc na kolejki bez blokady. Mam wielu producentów, wielu konsumentów. Zaimplementowałem, do testowania, system wykorzystujący blokowany SList pod Win32 i podwoił wydajność mojego mocno wątkowego kodu opartego na zadaniach. Niestety, jednak, chciałbym wspierać wiele platform. Samo blokowanie na wielu platformach nie stanowi problemu i mogę bezpiecznie założyć, że mogę zablokować się bez problemów. Jednak rzeczywista realizacja mnie gubi.

Dużym problemem wydaje się być to, że musisz zagwarantować, że list push/pop użyje tylko jednego połączenia z blokadą. W przeciwnym razie zostawiasz miejsce na kolejny wątek, aby wkręcić się i wszystko spieprzyć. Nie jestem pewien, jak działa implementacja Microsoftu pod maską i chciałbym wiedzieć więcej.

Czy ktoś może wskazać mi przydatne informacje(Platforma i język są dość nieistotne)?

Dodany do tego chciałbym wiedzieć, czy to możliwe, aby wdrożyć wektor bez blokady. To miałoby dla mnie ogromne znaczenie. :) Zdrowie!

Edit: po przeczytaniu artykułu Herba DDJ widzę zmniejszoną kolejkę blokad, która jest dość podobna do tej, którą już miałem. Zauważam jednak, że na końcu są dokumenty, które mogą wykonać prawdziwą kolejkę bez blokady za pomocą operacji double compare-and-swap (DCAS). Czy ktoś zaimplementował kolejkę używając cmpxchg8b(lub cmpxchg16b)?

W tym momencie tylko się zastanawiam (nie czytając gazet) ale możesz użyć tego systemu, aby jednocześnie zaktualizować wskaźnik głowy i ogona, a tym samym uniknąć problemów z innym wątkiem przeskakującym między 2 operacjami atomowymi. Jednak nadal trzeba uzyskać następny wskaźnik głowy, aby przetestować, że przeciwko wskaźnik ogon, aby zobaczyć, czy yo właśnie zmodyfikował ogon. Jak uniknąć zmiany tych informacji przez inny wątek, gdy ten sam się do tego przygotowuje? W jaki sposób jest to realizowane bez blokady? A może lepiej poczytać nieczytelność, która jest dokumentem badawczym? ;)

Author: Goz, 2009-11-12
Source

5 answers

Prawdopodobnie możesz zaimplementować kolejkę o ograniczonym rozmiarze z najmniejszym poziomem trudności... Myślałem o tym ostatnio i wymyśliłem ten projekt, ale prawdopodobnie można znaleźć wiele innych ciekawych pomysłów: (uwaga: może mieć pewne problemy!)

  • kolejka jest tablicą wskaźników do elementów
  • musisz zarządzać dwoma wskaźnikami (head, tail), które działają nad kolejką w taki sam sposób, jak okrągły bufor
  • Jeśli head == tail, nie ma elementów
  • Jeśli chcesz enqueue(ptr), Interlocked-Swap tail with NULL (prev_tail jest wartością swapowaną)
    • Jeśli prev_tail == NULL, spróbuj ponownie
    • if prev_tail + 1 (with wraparound) = = head, twoja kolejka jest pełna
    • w przeciwnym razie umieść ptr w *prev_tail i przypisz prev_tail+1 do tail (uważaj na zawijanie bufora)
  • for dequeue() make a copy tmp_head=head and check tmp_head == tail
    • jeśli to prawda, zwróć, ponieważ kolejka jest pusta
    • if it ' s false
      • Zapisz *tmp_head jako ptr
      • do a CAS: porównaj head z tmp_head zamień head z head+1
      • if CAS failed -- start the whole function over
      • if it successful -- return ptr

Możesz czekać zarówno na operacje head, jak i tail CAS, ale jeśli kolejka nie zostanie zakwestionowana, powinieneś odnieść sukces za pierwszym razem, bez zbędnych blokad.

Kolejki o nieograniczonej wielkości są" trochę " trudniejsze ;) ale powinieneś być w stanie stworzyć wystarczająco dużą kolejkę dla większości potrzeb.

 11
Author: viraptor,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-11-13 01:17:56

Myślę, że jest jakaś ciekawa dyskusja na ten temat tutaj, szczególnie ten wątek.

 3
Author: MikeB,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-11-12 22:19:55

Warto przyjrzeć się implementacji Herba Suttersa w kolejce niskiego zamka.

Http://www.drdobbs.com/hpc-high-performance-computing/211601363

Używa atomiki c++0x, ale byłaby (powinna być) łatwa do zaimplementowania z konkretnymi architekturami atomic ops (__sync _ * używając GNU, atomic_* na Solarisie itp.).

 3
Author: ScaryAardvark,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-03-11 13:14:44

Ci faceci mają, może znajdziesz tam jakąś inspirację. Inne ciekawe pliki to yqueue.hpp i atomic_ptr.hpp

 2
Author: nos,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-11-12 22:13:09

Rozwiązanie Viraptor jest blokowane, nie ma wielu producentów / wielu konsumentów bez blokady kolejki algotihms im świadomy .

 1
Author: ben,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-01-19 07:12:45