Indicatore di pericolo - Hazard pointer

In un ambiente di elaborazione multithread , i puntatori di rischio sono un approccio alla risoluzione dei problemi posti dalla gestione dinamica della memoria dei nodi in una struttura di dati priva di blocchi . Questi problemi sorgono generalmente solo in ambienti che non dispongono di Garbage Collection automatico .

Qualsiasi struttura dati senza lock che utilizzi la primitiva compare-and-swap deve affrontare il problema ABA . Ad esempio, in uno stack senza blocco rappresentato come un elenco collegato in modo intrusivo, un thread potrebbe tentare di estrarre un elemento dalla parte anteriore dello stack (A → B → C). Ricorda il secondo valore "B" dall'alto, quindi esegue . Sfortunatamente, nel mezzo di questa operazione, un altro thread potrebbe aver fatto due pop e poi aver riportato A in cima, risultando nello stack (A → C). Il confronto e lo scambio riesce a scambiare `testa` con `B`, e il risultato è che lo stack ora contiene spazzatura (un puntatore all'elemento liberato "B"). compare_and_swap(target=&head, newvalue=B, expected=A)

Inoltre, qualsiasi algoritmo senza lock contenente codice della forma 

    Node* currentNode = this->head;  // assume the load from "this->head" is atomic
    Node* nextNode = currentNode->next;  // assume this load is also atomic

soffre di un altro grosso problema, in assenza di raccolta automatica dei rifiuti. Tra queste due righe, è possibile che un altro thread possa estrarre il nodo puntato da this->heade deallocarlo, il che significa che l'accesso alla memoria attraverso currentNodela seconda riga legge la memoria deallocata (che in realtà potrebbe essere già in uso da qualche altro thread per uno scopo completamente diverso).

Gli indicatori di rischio possono essere utilizzati per affrontare entrambi questi problemi. In un sistema di puntatori di pericolo, ogni thread mantiene un elenco di puntatori di pericolo che indica a quali nodi il thread sta attualmente accedendo. (In molti sistemi questa "lista" può essere probabilmente limitata a solo uno o due elementi.) I nodi nell'elenco dei puntatori di pericolo non devono essere modificati o deallocati da nessun altro thread.

Ogni thread di lettura possiede un puntatore condiviso a scrittore singolo/multilettore chiamato "puntatore di rischio". Quando un thread di lettura assegna l'indirizzo di una mappa al suo hazard pointer, sta fondamentalmente annunciando ad altri thread (scrittori): "Sto leggendo questa mappa. Puoi sostituirla se vuoi, ma non cambiarne il contenuto e certamente tieni le tue deletemani lontane da esso."

—  Andrei Alexandrescu e Maged Michael, Strutture di dati senza blocco con indicatori di rischio

Quando un thread desidera rimuovere un nodo, lo inserisce in un elenco di nodi "da liberare in seguito", ma in realtà non dealloca la memoria del nodo fino a quando l'elenco di pericoli di nessun altro thread contiene il puntatore. Questa garbage collection manuale può essere eseguita da un thread di garbage collection dedicato (se l'elenco "da liberare in seguito" è condiviso da tutti i thread); in alternativa, la pulizia dell'elenco "da liberare" può essere eseguita da ciascun thread di lavoro come parte di un'operazione come "pop" (nel qual caso ogni thread di lavoro può essere responsabile del proprio elenco "da liberare").

Nel 2002, Maged Michael di IBM ha presentato una domanda per un brevetto statunitense sulla tecnica del puntatore di pericolo, ma l'applicazione è stata abbandonata nel 2010.

Le alternative agli indicatori di pericolo includono il conteggio dei riferimenti .

Guarda anche

Riferimenti

  1. ^ a b c Anthony Williams. Concorrenza C++ in azione: multithreading pratico. Manning:Shelter Island, 2012. Si veda in particolare il capitolo 7.2, "Esempi di strutture dati prive di blocchi".
  2. ^ a b Andrei Alexandrescu e Maged Michael (2004). "Strutture di dati senza blocco con indicatori di pericolo" . del dottor Dobb . (articolo orientato al C++)
  3. ^ Domanda statunitense 20040107227  Maged M. Michael, "Metodo per l'implementazione efficiente di strutture dati dinamiche prive di blocco con recupero sicuro della memoria". Depositato il 3 dicembre 2002.

link esterno