Algoritmo non bloccante - Non-blocking algorithm

Da non confondere con I/O non bloccanti .

In informatica , un algoritmo è chiamato non-blocking se il fallimento o la sospensione di un thread non può causare il fallimento o la sospensione di un altro thread; per alcune operazioni, questi algoritmi forniscono un'utile alternativa alle tradizionali implementazioni di blocco . Un algoritmo non bloccante è privo di blocchi se è garantito un avanzamento a livello di sistema e privo di attesa se è garantito anche un avanzamento per thread. "Non-blocking" è stato utilizzato come sinonimo di "lock-free" in letteratura fino all'introduzione della libertà di ostruzione nel 2003.

La parola "non bloccante" era tradizionalmente usata per descrivere le reti di telecomunicazioni che potevano instradare una connessione attraverso una serie di relè "senza dover riorganizzare le chiamate esistenti" (vedi rete Clos ). Inoltre, se la centrale telefonica "non è difettosa, può sempre effettuare la connessione" (vedi switch di span minimo non bloccante ).

Motivazione

Articolo principale: Svantaggi delle serrature

L'approccio tradizionale alla programmazione multi-thread consiste nell'utilizzare i blocchi per sincronizzare l'accesso alle risorse condivise . Primitive di sincronizzazione come mutex , semafori e sezioni critiche sono tutti meccanismi mediante i quali un programmatore può garantire che determinate sezioni di codice non vengano eseguite contemporaneamente, se ciò danneggerebbe le strutture di memoria condivisa. Se un thread tenta di acquisire un blocco già mantenuto da un altro thread, il thread si bloccherà finché il blocco non sarà libero.

Il blocco di un thread può essere indesiderabile per molte ragioni. Una ragione ovvia è che mentre il thread è bloccato, non può eseguire nulla: se il thread bloccato avesse eseguito un'attività ad alta priorità o in tempo reale , sarebbe altamente indesiderabile interromperne l'avanzamento.

Altri problemi sono meno evidenti. Ad esempio, determinate interazioni tra i blocchi possono portare a condizioni di errore come deadlock , livelock e inversione di priorità . L'utilizzo dei blocchi comporta anche un compromesso tra il blocco a grana grossa, che può ridurre significativamente le opportunità di parallelismo , e il blocco a grana fine, che richiede una progettazione più attenta, aumenta il sovraccarico di blocco ed è più soggetto a bug.

A differenza degli algoritmi di blocco, gli algoritmi non di blocco non soffrono di questi aspetti negativi e inoltre sono sicuri per l'uso nei gestori di interrupt : anche se il thread interrotto non può essere ripreso, il progresso è ancora possibile senza di esso. Al contrario, le strutture dati globali protette dalla mutua esclusione non possono essere raggiunte in sicurezza in un gestore di interrupt, poiché il thread interrotto potrebbe essere quello che detiene il lock, ma questo può essere corretto facilmente mascherando la richiesta di interrupt durante la sezione critica.

È possibile utilizzare una struttura di dati senza blocchi per migliorare le prestazioni. Una struttura dati senza blocco aumenta la quantità di tempo trascorso nell'esecuzione parallela piuttosto che nell'esecuzione seriale, migliorando le prestazioni su un processore multi-core , perché l'accesso alla struttura dati condivisa non ha bisogno di essere serializzato per rimanere coerente.

Implementazione

Con poche eccezioni, gli algoritmi non bloccanti utilizzano primitive atomiche di lettura-modifica-scrittura che l'hardware deve fornire, la più notevole delle quali è compare e scambia (CAS) . Le sezioni critiche sono quasi sempre implementate utilizzando interfacce standard su queste primitive (in generale, le sezioni critiche si bloccheranno, anche se implementate con queste primitive). Negli anni '90 tutti gli algoritmi non bloccanti dovevano essere scritti "nativamente" con le primitive sottostanti per ottenere prestazioni accettabili. Tuttavia, il campo emergente della memoria transazionale software promette astrazioni standard per scrivere codice efficiente non bloccante.

Sono state fatte molte ricerche anche per fornire strutture dati di base come stack , code , set e tabelle hash . Questi consentono ai programmi di scambiare facilmente dati tra i thread in modo asincrono.

Inoltre, alcune strutture di dati non bloccanti sono abbastanza deboli da essere implementate senza particolari primitive atomiche. Queste eccezioni includono:

  • un buffer circolare FIFO a lettura singola ea scrittura singola , con una dimensione che divide equamente l'overflow di uno dei tipi di interi senza segno disponibili, può essere implementato incondizionatamente in modo sicuro utilizzando solo una barriera di memoria
  • Leggi-copia-aggiornamento con un solo scrittore e un numero qualsiasi di lettori. (I lettori sono senza attesa; lo scrittore di solito è senza blocco, fino a quando non ha bisogno di recuperare la memoria).
  • Leggi-copia-aggiornamento con più scrittori e qualsiasi numero di lettori. (I lettori sono senza attesa; più scrittori generalmente serializzano con un lucchetto e non sono privi di ostacoli).

Diverse librerie utilizzano internamente tecniche lock-free, ma è difficile scrivere codice senza lock corretto.

Libertà di attesa

La libertà di attesa è la più forte garanzia non bloccante del progresso, che combina un throughput garantito a livello di sistema con la libertà da fame . Un algoritmo è senza attesa se ogni operazione ha un limite al numero di passaggi che l'algoritmo eseguirà prima del completamento dell'operazione. Questa proprietà è fondamentale per i sistemi in tempo reale ed è sempre utile se il costo delle prestazioni non è troppo elevato.

È stato dimostrato negli anni '80 che tutti gli algoritmi possono essere implementati senza attesa e sono state dimostrate molte trasformazioni dal codice seriale, chiamate costruzioni universali . Tuttavia, le prestazioni risultanti non corrispondono in generale nemmeno ai design di blocco ingenui. Diversi documenti da allora hanno migliorato le prestazioni delle costruzioni universali, ma ancora, le loro prestazioni sono molto al di sotto dei progetti di blocco.

Diversi articoli hanno studiato la difficoltà di creare algoritmi senza attesa. Ad esempio, è stato dimostrato che le primitive condizionali atomiche ampiamente disponibili , CAS e LL/SC , non possono fornire implementazioni prive di fame di molte strutture dati comuni senza che i costi di memoria crescano linearmente nel numero di thread.

Ma in pratica questi limiti inferiori non rappresentano una vera barriera poiché spendere una linea di cache o un granulo di prenotazione esclusivo (fino a 2 KB su ARM) di memoria per thread nella memoria condivisa non è considerato troppo costoso per i sistemi pratici (tipicamente la quantità di store logicamente richiesto è una parola, ma le operazioni CAS fisicamente sulla stessa linea di cache si scontrano e le operazioni LL/SC nello stesso granulo di prenotazione esclusiva si scontrano, quindi la quantità di store fisicamente richiesta è maggiore).

Gli algoritmi senza attesa erano rari fino al 2011, sia nella ricerca che nella pratica. Tuttavia, nel 2011 Kogan e Petrank hanno presentato una costruzione di coda senza attesa sulla primitiva CAS , generalmente disponibile su hardware comune. La loro costruzione ha ampliato la coda senza blocco di Michael e Scott, che è una coda efficiente spesso utilizzata nella pratica. Un documento di follow-up di Kogan e Petrank ha fornito un metodo per rendere veloci gli algoritmi senza attesa e ha utilizzato questo metodo per rendere la coda senza attesa praticamente veloce quanto la sua controparte senza blocco. Un successivo articolo di Timnat e Petrank ha fornito un meccanismo automatico per generare strutture di dati senza attesa da quelle senza blocco. Pertanto, sono ora disponibili implementazioni senza attesa per molte strutture di dati.

Libertà di blocco

La libertà di blocco consente ai singoli thread di morire di fame, ma garantisce un throughput a livello di sistema. Un algoritmo è lock-free se, quando i thread del programma vengono eseguiti per un tempo sufficientemente lungo, almeno uno dei thread fa progressi (per una definizione sensata di avanzamento). Tutti gli algoritmi senza attesa sono privi di blocco.

In particolare, se un thread viene sospeso, un algoritmo senza blocco garantisce che i thread rimanenti possano ancora progredire. Quindi, se due thread possono contendersi lo stesso mutex lock o spinlock, l'algoritmo non è esente da lock. (Se sospendiamo un thread che mantiene il blocco, il secondo thread si bloccherà.)

Un algoritmo è esente da blocco se l'operazione infinitamente spesso da parte di alcuni processori riesce in un numero finito di passaggi. Ad esempio, se N processori stanno tentando di eseguire un'operazione, alcuni degli N processi riusciranno a completare l'operazione in un numero finito di passaggi e altri potrebbero non riuscire e riprovare in caso di errore. La differenza tra wait-free e lock-free è che l'operazione senza attesa di ciascun processo è garantita per avere successo in un numero finito di passaggi, indipendentemente dagli altri processori.

In generale, un algoritmo lock-free può essere eseguito in quattro fasi: completamento della propria operazione, assistenza a un'operazione di ostacolo, interruzione di un'operazione di ostacolo e attesa. Il completamento della propria operazione è complicato dalla possibilità di assistenza e aborto simultanei, ma è invariabilmente il percorso più rapido per il completamento.

La decisione su quando assistere, interrompere o attendere quando si incontra un ostacolo è responsabilità di un responsabile del contenzioso . Questo può essere molto semplice (assistere le operazioni con priorità più alta, interrompere quelle con priorità più bassa) o può essere più ottimizzato per ottenere un throughput migliore o ridurre la latenza delle operazioni con priorità.

L'assistenza simultanea corretta è in genere la parte più complessa di un algoritmo senza lock e spesso molto costosa da eseguire: non solo il thread di assistenza rallenta, ma grazie alla meccanica della memoria condivisa, anche il thread che viene assistito sarà rallentato , se è ancora in esecuzione.

Libertà di ostruzione

La libertà da ostacoli è la più debole garanzia naturale di progresso non bloccante. Un algoritmo è privo di ostacoli se, in qualsiasi momento, un singolo thread eseguito in isolamento (cioè con tutti i thread di ostacolo sospesi) per un numero limitato di passaggi completerà la sua operazione. Tutti gli algoritmi senza blocco sono privi di ostacoli.

La libertà da ostacoli richiede solo che qualsiasi operazione parzialmente completata possa essere interrotta e le modifiche apportate annullate. L'eliminazione dell'assistenza simultanea può spesso comportare algoritmi molto più semplici e più facili da convalidare. Prevenire il sistema dal live-locking continuo è compito di un gestore di contese.

Alcuni algoritmi privi di ostacoli utilizzano una coppia di "marcatori di coerenza" nella struttura dei dati. I processi che leggono la struttura dei dati leggono prima un marker di coerenza, quindi leggono i dati rilevanti in un buffer interno, quindi leggono l'altro marker e quindi confrontano i marker. I dati sono coerenti se i due marker sono identici. I marker possono essere non identici quando la lettura viene interrotta da un altro processo che aggiorna la struttura dei dati. In tal caso, il processo scarta i dati nel buffer interno e riprova.

Guarda anche

Riferimenti

link esterno