Ukazatel nebezpečí - Hazard pointer

V vícevláknové výpočetní životní prostředí, ukazatele nebezpečí jsou jedním z přístupů k řešení problémů, které představuje dynamická správa paměti uzlů v a bez zámku datová struktura. Tyto problémy obvykle vznikají pouze v prostředích, která nemají automatický sběr odpadu.[1]

Jakákoli bezzámková datová struktura, která používá porovnat a vyměnit primitivní se musí vypořádat s Problém ABA. Například v bezzámkovém zásobníku představovaném jako seznam narušený spojením se může jedno vlákno pokoušet o vyskakování položky z přední strany stohu (A → B → C). Pamatuje si druhou hodnotu „B“ a poté provádí porovnat a vyměnit(cílová=&hlava, nová hodnota=B, očekávaný=A). Uprostřed této operace bohužel mohl jiný podproces provést dva vystřelování a poté tlačit A zpět nahoru, což vedlo k zásobníku (A → C). Porovnání a výměna uspěje v záměně `head` za` B` a výsledkem je, že zásobník nyní obsahuje odpadky (ukazatel na uvolněný prvek „B“).

Kromě toho jakýkoli bezblokový algoritmus obsahující kód formuláře

    Uzel* currentNode = tento->hlava;  // předpokládejme, že zátěž z „this-> head“ je atomová    Uzel* nextNode = currentNode->další;  // předpokládejme, že toto zatížení je také atomové

trpí dalším velkým problémem, protože chybí automatický sběr odpadu. Mezi těmito dvěma řádky je možné, že další vlákno může vyskočit na uzel, na který ukazuje to-> hlava a uvolnit jej, což znamená, že přístup do paměti prostřednictvím currentNode na druhém řádku čte uvolněnou paměť (která může být ve skutečnosti již používána jiným vláknem pro úplně jiný účel).

K řešení obou těchto problémů lze použít ukazatele nebezpečí. V systému ukazatelů nebezpečí každý vlákno udržuje seznam ukazatelů nebezpečí, které označují, ke kterým uzlům vlákno aktuálně přistupuje. (V mnoha systémech může být tento „seznam“ pravděpodobně omezen pouze na jeden[1][2] nebo dva prvky.) Uzly v seznamu ukazatelů nebezpečí nesmí být upraveny ani uvolněny jiným vláknem.

Každé vlákno čtečky vlastní sdílený ukazatel s jedním zapisovatelem / více čtečkami, který se nazývá „ukazatel nebezpečí“. Když vlákno čtečky přiřadí adresu mapy jejímu ukazateli nebezpečí, v podstatě oznamuje ostatním vláknům (autorům): „Čtu tuto mapu. Pokud chcete, můžete ji nahradit, ale neměňte její obsah a určitě nechte si vymazatruce pryč. “

— Andrei Alexandrescu a Maged Michael, datové struktury bez zámku s ukazateli nebezpečí[2]

Pokud si vlákno přeje odebrat uzel, umístí jej na seznam uzlů „k uvolnění později“, ale ve skutečnosti nezruší uvolnění paměti uzlu, dokud žádný seznam nebezpečí jiného vlákna neobsahuje ukazatel. Tento ruční sběr odpadu lze provést vyhrazeným podprocesem pro sběr odpadu (pokud je seznam „k uvolnění později“ sdílen všemi vlákny); alternativně může vyčištění seznamu „být uvolněn“ provedeno každým pracovním vláknem jako součást operace, jako je „pop“ (v takovém případě může být každé pracovní vlákno odpovědné za svůj vlastní seznam „k uvolnění“).

V roce 2002 Maged Michael z IBM podal přihlášku k americkému patentu na techniku ​​ukazatele nebezpečí,[3] ale od aplikace bylo v roce 2010 upuštěno.

Mezi alternativy ukazatelů nebezpečí patří počítání referencí.[1]

Viz také

Reference

  1. ^ A b C Anthony Williams. C ++ souběžnost v akci: Praktické multithreading. Manning: Shelter Island, 2012. Viz zejména Kapitola 7.2, „Příklady bezzámkových datových struktur“.
  2. ^ A b Andrei Alexandrescu a Maged Michael (2004). „Bezzámkové datové struktury s ukazateli nebezpečí“. Dr. Dobb. (Článek orientovaný na C ++)
  3. ^ Americká žádost 20040107227  Maged M. Michael, „Metoda pro efektivní implementaci dynamických bezzámkových datových struktur s bezpečnou rekultivací paměti.“ Podáno dne 3. prosince 2002.

externí odkazy