Linearizzabilità - Linearizability

In grigio una sottostoria lineare, i processi che iniziano in b non hanno una cronologia linearizzabile perché b0 o b1 possono essere completati in entrambi gli ordini prima che si verifichi b2.

Nella programmazione concorrente , un'operazione (o insieme di operazioni) è linearizzabile se è costituita da un elenco ordinato di eventi di invocazione e risposta ( callback ), che può essere esteso aggiungendo eventi di risposta tali che:

1. L'elenco esteso può essere riespresso come cronologia sequenziale (è serializzabile ).
2. Quella cronologia sequenziale è un sottoinsieme dell'elenco non esteso originale.

Informalmente, ciò significa che l'elenco di eventi non modificato è linearizzabile se e solo se le sue invocazioni erano serializzabili , ma alcune delle risposte della pianificazione seriale devono ancora essere restituite.

In un sistema simultaneo, i processi possono accedere contemporaneamente a un oggetto condiviso. Poiché più processi accedono a un singolo oggetto, può verificarsi una situazione in cui mentre un processo accede all'oggetto, un altro processo ne modifica il contenuto. Questo esempio dimostra la necessità di linearizzabilità. In un sistema linearizzabile, sebbene le operazioni si sovrappongano su un oggetto condiviso, ogni operazione sembra svolgersi istantaneamente. La linearizzazione è una forte condizione di correttezza, che vincola quali output sono possibili quando a un oggetto accedono più processi contemporaneamente. È una proprietà di sicurezza che garantisce che le operazioni non vengano completate in modo imprevisto o imprevedibile. Se un sistema è linearizzabile, consente a un programmatore di ragionare sul sistema.

Storia della linearizzabilità

La linearizzazione è stata introdotta per la prima volta come modello di coerenza da Herlihy e Wing nel 1987. Comprendeva definizioni più restrittive di atomico, come "un'operazione atomica è quella che non può essere (o non è) interrotta da operazioni simultanee", che di solito sono vaghe su quando si ritiene che un'operazione inizi e finisca.

Un oggetto atomico può essere compreso immediatamente e completamente dalla sua definizione sequenziale, come un insieme di operazioni eseguite in parallelo che sembrano sempre verificarsi una dopo l'altra; non possono emergere incongruenze. Nello specifico, la linearizzabilità garantisce che gli invarianti di un sistema siano osservati e preservati da tutte le operazioni: se tutte le operazioni conservano singolarmente un invariante, lo farà il sistema nel suo insieme.

Definizione di linearizzabilità

Un sistema simultaneo consiste in un insieme di processi che comunicano attraverso strutture dati o oggetti condivisi. La linearizzazione è importante in questi sistemi simultanei in cui è possibile accedere agli oggetti da più processi contemporaneamente e un programmatore deve essere in grado di ragionare sui risultati attesi. L'esecuzione di un sistema simultaneo risulta in una cronologia , una sequenza ordinata di operazioni completate.

Una cronologia è una sequenza di chiamate e risposte fatte di un oggetto da un insieme di thread o processi. Un'invocazione può essere considerata come l'inizio di un'operazione e la risposta come la fine segnalata di tale operazione. Ogni invocazione di una funzione avrà una risposta successiva. Questo può essere usato per modellare qualsiasi uso di un oggetto. Supponiamo, ad esempio, che due thread, A e B, tentino entrambi di afferrare un lucchetto, indietreggiando se è già stato preso. Questo sarebbe modellato come entrambi i thread che invocano l'operazione di blocco, quindi entrambi i thread ricevono una risposta, uno riuscito, uno no.

Una storia sequenziale è quella in cui tutte le invocazioni hanno risposte immediate; cioè l'invocazione e la risposta si considerano avvenute istantaneamente. Una storia sequenziale dovrebbe essere banale su cui ragionare, poiché non ha una reale concorrenza; l'esempio precedente non era sequenziale, e quindi è difficile ragionare. È qui che entra in gioco la linearità.

Una storia è linearizzabile se esiste un ordine lineare delle operazioni completate tale che: ${\displaystyle \sigma}$

1. Per ogni operazione completata in , l'operazione restituisce lo stesso risultato nell'esecuzione come l'operazione restituirebbe se ogni operazione fosse completata una per una in ordine .${\displaystyle \sigma}$${\displaystyle \sigma}$
2. Se un'operazione op _{1 viene} completata (ottene una risposta) prima che op ₂ inizi (richiama), allora op ₁ precede op ₂ in .${\displaystyle \sigma}$

In altre parole:

• le sue invocazioni e risposte possono essere riordinate per produrre una storia sequenziale;
• che la storia sequenziale è corretta secondo la definizione sequenziale dell'oggetto;
• se una risposta ha preceduto un'invocazione nella storia originaria, deve comunque precederla nel riordino sequenziale.

(Si noti che i primi due punti elenco qui corrispondono alla serializzabilità : le operazioni sembrano avvenire in un certo ordine. È l'ultimo punto che è unico per la linearizzazione, ed è quindi il contributo principale di Herlihy e Wing.)

Diamo un'occhiata a due modi per riordinare l'esempio di blocco sopra.

Riordinando l'invocazione di B sotto la risposta di A si ottiene una cronologia sequenziale. È facile ragionare su questo, poiché tutte le operazioni ora avvengono in un ordine ovvio. Sfortunatamente, non corrisponde alla definizione sequenziale dell'oggetto (non corrisponde alla semantica del programma): A dovrebbe aver ottenuto con successo il blocco e B dovrebbe aver successivamente interrotto.

Questa è un'altra storia sequenziale corretta. È anche una linearizzazione! Si noti che la definizione di linearizzabilità preclude solo il riordino delle risposte che precedono le invocazioni; poiché la storia originale non ha avuto risposte prima delle invocazioni, possiamo riordinarla come vogliamo. Quindi la storia originale è effettivamente linearizzabile.

Un oggetto (al contrario di una storia) è linearizzabile se tutte le storie valide del suo utilizzo possono essere linearizzate. Nota che questa è un'affermazione molto più difficile da dimostrare.

Linearizzabilità contro serializzabilità

Considera la seguente cronologia, ancora una volta di due oggetti che interagiscono con un lucchetto:

Questa storia non è valida perché c'è un punto in cui sia A che B mantengono il blocco; inoltre, non può essere riordinato ad una cronologia sequenziale valida senza violare la regola di ordinamento. Pertanto, non è linearizzabile. Tuttavia, in serializzabilità, l'operazione di sblocco di B può essere spostata prima del blocco originale di A, che è una cronologia valida (supponendo che l'oggetto inizi la cronologia in uno stato bloccato):

Questo riordino è ragionevole a condizione che non ci siano mezzi alternativi di comunicazione tra A e B. La linearizzazione è migliore quando si considerano i singoli oggetti separatamente, poiché le restrizioni di riordino assicurano che più oggetti linearizzabili siano, considerati nel loro insieme, ancora linearizzabili.

Punti di linearizzazione

Questa definizione di linearizzabilità è equivalente alla seguente:

• Tutte le chiamate di funzione hanno un punto di linearizzazione in qualche istante tra la loro invocazione e la loro risposta.
• Tutte le funzioni sembrano verificarsi istantaneamente nel loro punto di linearizzazione, comportandosi come specificato dalla definizione sequenziale.

Questa alternativa è di solito molto più facile da dimostrare. È anche molto più facile ragionare come utente, in gran parte grazie alla sua intuitività. Questa proprietà di verificarsi istantaneamente, o indivisibilmente, porta all'uso del termine atomico in alternativa al più lungo "linearizzabile".

Negli esempi seguenti, il punto di linearizzazione del contatore costruito su compare-and-swap è il punto di linearizzazione del primo (e unico) aggiornamento di confronto e scambio riuscito. Si può ritenere che il contatore costruito utilizzando il blocco si linearizza in qualsiasi momento mentre i blocchi sono mantenuti, poiché eventuali operazioni potenzialmente in conflitto sono escluse dall'esecuzione durante quel periodo.

Istruzioni atomiche primitive

I processori dispongono di istruzioni che possono essere utilizzate per implementare algoritmi di blocco e senza blocco e senza attesa . La capacità di inibire temporaneamente gli interrupt , assicurando che il processo attualmente in esecuzione non possa essere commutato in contesto , è sufficiente anche su un uniprocessore . Queste istruzioni vengono utilizzate direttamente dai compilatori e dagli autori del sistema operativo, ma sono anche astratte ed esposte come bytecode e funzioni di libreria nei linguaggi di livello superiore:

• lettura-scrittura atomica;
• scambio atomico (l'istruzione RDLK in alcuni mainframe Burroughs e l' istruzione XCHG x86 );
• prova-e-set ;
• prendi e aggiungi ;
• confronta-e-scambia ;
• load-link/store-conditional .

La maggior parte dei processori include operazioni di archiviazione che non sono atomiche rispetto alla memoria. Questi includono archivi di più parole e operazioni su stringhe. Se si verifica un'interruzione ad alta priorità quando una parte dell'archivio è completa, l'operazione deve essere completata quando viene restituito il livello di interruzione. La routine che elabora l'interrupt non deve modificare la memoria che viene modificata. È importante tenerne conto quando si scrivono le routine di interrupt.

Quando sono presenti più istruzioni che devono essere completate senza interruzione, viene utilizzata un'istruzione della CPU che disabilita temporaneamente gli interrupt. Questo deve essere limitato a poche istruzioni e gli interrupt devono essere riabilitati per evitare tempi di risposta inaccettabili agli interrupt o addirittura la perdita degli interrupt. Questo meccanismo non è sufficiente in un ambiente multiprocessore poiché ogni CPU può interferire con il processo indipendentemente dal verificarsi o meno di interruzioni. Inoltre, in presenza di una pipeline di istruzioni , le operazioni ininterrotte presentano un rischio per la sicurezza, in quanto possono essere potenzialmente concatenate in un ciclo infinito per creare un attacco denial of service , come nel bug coma Cyrix .

Lo standard C e SUSv3 forniscono sig_atomic_tsemplici letture e scritture atomiche; non è garantito che l'incremento o il decremento sia atomico. Operazioni atomiche più complesse sono disponibili in C11 , che fornisce stdatomic.h. I compilatori utilizzano le funzionalità hardware o metodi più complessi per implementare le operazioni; un esempio è libatomic di GCC.

Il set di istruzioni ARM fornisce LDREXe STREXistruzioni che possono essere utilizzati per implementare l'accesso memoria atomico utilizzando monitor esclusive implementate nel processore per monitorare accessi di memoria per un indirizzo specifico. Tuttavia, se si verifica un cambio di contesto tra le chiamate a LDREXe STREX, la documentazione rileva che STREXavrà esito negativo, indicando che è necessario ritentare l'operazione.

Operazioni atomiche di alto livello

Il modo più semplice per ottenere la linearizzazione è eseguire gruppi di operazioni primitive in una sezione critica . Strettamente, operazioni indipendenti possono quindi essere accuratamente consentite per sovrapporre le loro sezioni critiche, a condizione che ciò non violi la linearità. Tale approccio deve bilanciare il costo di un gran numero di blocchi con i vantaggi di un maggiore parallelismo.

Un altro approccio, favorito dai ricercatori (ma non ancora ampiamente utilizzato nell'industria del software), è quello di progettare un oggetto linearizzabile utilizzando le primitive atomiche native fornite dall'hardware. Questo ha il potenziale per massimizzare il parallelismo disponibile e minimizzare i costi di sincronizzazione, ma richiede prove matematiche che dimostrino che gli oggetti si comportano correttamente.

Un ibrido promettente di questi due è fornire un'astrazione della memoria transazionale . Come per le sezioni critiche, l'utente contrassegna il codice sequenziale che deve essere eseguito in isolamento dagli altri thread. L'implementazione garantisce quindi che il codice venga eseguito in modo atomico. Questo stile di astrazione è comune quando si interagisce con i database; ad esempio, quando si utilizza Spring Framework , l'annotazione di un metodo con @Transactional garantirà che tutte le interazioni del database racchiuso si verifichino in una singola transazione del database . La memoria transazionale va oltre, garantendo che tutte le interazioni con la memoria avvengano in modo atomico. Come per le transazioni di database, sorgono problemi riguardanti la composizione delle transazioni, in particolare le transazioni di database e in memoria.

Un tema comune quando si progettano oggetti linearizzabili è quello di fornire un'interfaccia tutto o niente: o un'operazione riesce completamente o fallisce e non fa nulla. ( I database ACID fanno riferimento a questo principio come atomicità .) Se l'operazione fallisce (di solito a causa di operazioni simultanee), l'utente deve riprovare, di solito eseguendo un'operazione diversa. Per esempio:

• Compare-and-swap scrive un nuovo valore in una posizione solo se il contenuto di quest'ultima corrisponde a un vecchio valore fornito. Questo è comunemente usato in una sequenza read-modify-CAS: l'utente legge la posizione, calcola un nuovo valore da scrivere e lo scrive con un CAS (compare-and-swap); se il valore cambia contemporaneamente, il CAS fallisce e l'utente riprova.
• Load-link/store-conditional codifica questo modello in modo più diretto: l'utente legge la posizione con load-link, calcola un nuovo valore da scrivere e lo scrive con store-conditional; se il valore è cambiato contemporaneamente, l'SC (store-conditional) avrà esito negativo e l'utente riprova.
• In una transazione di database , se la transazione non può essere completata a causa di un'operazione simultanea (ad esempio in un deadlock ), la transazione verrà interrotta e l'utente dovrà riprovare.

Esempi di linearizzabilità

Contatori

Per dimostrare la potenza e la necessità della linearizzazione prenderemo in considerazione un semplice contatore che diversi processi possono incrementare.

Vorremmo implementare un oggetto contatore a cui possono accedere più processi. Molti sistemi comuni utilizzano contatori per tenere traccia del numero di volte in cui si è verificato un evento.

L'oggetto contatore è accessibile da più processi e dispone di due operazioni disponibili.

1. Incremento - aggiunge 1 al valore memorizzato nel contatore, restituisce il riconoscimento
2. Leggi - restituisce il valore corrente memorizzato nel contatore senza modificarlo.

Cercheremo di implementare questo oggetto contatore usando registri condivisi

Il nostro primo tentativo che vedremo non linearizzabile ha la seguente implementazione utilizzando un registro condiviso tra i processi.

Non atomico

L'implementazione ingenua e non atomica:

Incremento:

1. Leggere il valore nel registro R
2. Aggiungi uno al valore
3. Riscrive il nuovo valore nel registro R

Leggere:

Leggi registro R

Questa semplice implementazione non è linearizzabile, come dimostra l'esempio seguente.

Immagina che due processi siano in esecuzione accedendo al singolo oggetto contatore inizializzato per avere valore 0:

1. Il primo processo legge il valore nel registro come 0.
2. Il primo processo aggiunge uno al valore, il valore del contatore dovrebbe essere 1, ma prima che abbia finito di scrivere il nuovo valore nel registro potrebbe essere sospeso, mentre il secondo processo è in esecuzione:
3. Il secondo processo legge il valore nel registro, che è ancora uguale a 0;
4. Il secondo processo aggiunge uno al valore;
5. il secondo processo scrive il nuovo valore nel registro, il registro ora ha valore 1.

Il secondo processo ha terminato l'esecuzione e il primo processo continua a funzionare da dove era stato interrotto:

1. Il primo processo scrive 1 nel registro, ignaro che l'altro processo ha già aggiornato il valore nel registro a 1.

Nell'esempio sopra, due processi hanno invocato un comando di incremento, tuttavia il valore dell'oggetto è aumentato solo da 0 a 1, invece di 2 come avrebbe dovuto. Una delle operazioni di incremento è andata persa a causa della non linearizzazione del sistema.

L'esempio sopra mostra la necessità di riflettere attentamente attraverso le implementazioni delle strutture dati e come la linearità può avere un effetto sulla correttezza del sistema.

Atomico

Per implementare un oggetto contatore linearizzabile o atomico modificheremo la nostra precedente implementazione in modo che ogni processo P i utilizzi il proprio registro R i

Ogni processo incrementa e legge secondo il seguente algoritmo:

Incremento:

1. Leggi il valore nel registro R i .
2. Aggiungi uno al valore.
3. Riscrivi il nuovo valore in R i

Leggere:

1. Leggi i registri R 1, R 2, ... R n .
2. Restituisce la somma di tutti i registri.

Questa implementazione risolve il problema con la nostra implementazione originale. In questo sistema le operazioni di incremento sono linearizzate in fase di scrittura. Il punto di linearizzazione di un'operazione di incremento è quando quell'operazione scrive il nuovo valore nel suo registro R i. Le operazioni di lettura vengono linearizzate ad un punto del sistema quando il valore restituito dalla lettura è uguale alla somma di tutti i valori memorizzati in ciascun registro R i.

Questo è un esempio banale. In un sistema reale, le operazioni possono essere più complesse e gli errori introdotti estremamente sottili. Ad esempio, la lettura di un valore a 64 bit dalla memoria può essere effettivamente implementata come due letture sequenziali di due locazioni di memoria a 32 bit . Se un processo ha letto solo i primi 32 bit e prima di leggere i secondi 32 bit il valore in memoria viene modificato, non avrà né il valore originale né il nuovo valore ma un valore confuso.

Inoltre, l'ordine specifico in cui vengono eseguiti i processi può modificare i risultati, rendendo difficile rilevare, riprodurre ed eseguire il debug di tale errore .

Confronta e scambia-

La maggior parte dei sistemi fornisce un'istruzione di confronto e scambio atomica che legge da una posizione di memoria, confronta il valore con uno "previsto" fornito dall'utente e scrive un valore "nuovo" se i due corrispondono, restituendo se l'aggiornamento è riuscito . Possiamo usarlo per correggere l'algoritmo del contatore non atomico come segue:

1. Leggere il valore nella locazione di memoria;
2. aggiungi uno al valore;
3. utilizzare compare-and-swap per riscrivere il valore incrementato;
4. riprovare se il valore letto da compare-and-swap non corrisponde al valore letto originariamente.

Poiché il confronto e lo scambio si verificano (o sembrano verificarsi) istantaneamente, se un altro processo aggiorna la posizione mentre siamo in corso, è garantito che il confronto e lo scambio non riusciranno.

Recupera e incrementa

Molti sistemi forniscono un'istruzione di recupero e incremento atomico che legge da una posizione di memoria, scrive incondizionatamente un nuovo valore (il vecchio valore più uno) e restituisce il vecchio valore. Possiamo usarlo per correggere l'algoritmo del contatore non atomico come segue:

1. Usa fetch-and-increment per leggere il vecchio valore e riscrivere il valore incrementato.

L'uso di fetch-and-swap è sempre migliore (richiede meno riferimenti di memoria) per alcuni algoritmi, come quello mostrato qui, rispetto a compare-and-swap, anche se Herlihy ha dimostrato in precedenza che il confronto e lo scambio è migliore per alcuni altri algoritmi che non può essere implementato affatto utilizzando solo fetch-and-increment. Quindi i progetti di CPU con sia fetch-and-increment che compare-and-swap (o istruzioni equivalenti) possono essere una scelta migliore rispetto a quelli con solo l'uno o l'altro.

Blocco

Un altro approccio consiste nel trasformare l'algoritmo ingenuo in una sezione critica , impedendo ad altri thread di interromperlo, utilizzando un blocco . Ancora una volta correggendo l'algoritmo del contatore non atomico:

1. Acquisire un blocco, escludendo contemporaneamente altri thread dall'esecuzione della sezione critica (passaggi 2-4);
2. leggere il valore nella locazione di memoria;
3. aggiungi uno al valore;
4. riscrivere il valore incrementato nella locazione di memoria;
5. rilasciare il blocco.

Questa strategia funziona come previsto; il blocco impedisce ad altri thread di aggiornare il valore finché non viene rilasciato. Tuttavia, se confrontato con l'uso diretto delle operazioni atomiche, può soffrire di un sovraccarico significativo a causa della contesa di blocco. Per migliorare le prestazioni del programma, potrebbe quindi essere una buona idea sostituire semplici sezioni critiche con operazioni atomiche per la sincronizzazione non bloccante (come abbiamo appena fatto per il contatore con confronto e scambio e recupero e incremento), invece di viceversa, ma sfortunatamente non è garantito un miglioramento significativo e gli algoritmi privi di blocchi possono facilmente diventare troppo complicati per valerne la pena.

Guarda anche

• Transazione atomica
• Modello di consistenza
• ACIDO
• Aggiornamento lettura-copia (RCU)
• Leggi-modifica-scrivi
• Tempo di controllo a tempo di utilizzo

Riferimenti

Ulteriori letture

• Herlihy, Maurice P.; Ala, Jeannette M. (1987). Assiomi per oggetti concorrenti . Atti del XIV Simposio ACM SIGACT-SIGPLAN sui Principi dei Linguaggi di Programmazione, POPL '87 . pag. 13. doi : 10.1145/41625.41627 . ISBN 978-0-89791-215-0. S2CID  16017451 .
• Herlihy, Maurice P. (1990). Una metodologia per l'implementazione di strutture di dati altamente simultanee . Avvisi ACM SIGPLAN . 25 . pp. 197-206. CiteSeerX  10.1.1.186.6400 . doi : 10.1145/99164.99185 . ISBN 978-0-89791-350-8.
• Herlihy, Maurice P.; Ala, Jeannette M. (1990). "Linearizzabilità: una condizione di correttezza per oggetti concorrenti". Transazioni ACM su linguaggi e sistemi di programmazione . 12 (3): 463–492. CiteSeerX  10.1.1.142.5315 . doi : 10.1145/78969.78972 . S2CID  228785 .
• Afiro. "Modelli di consistenza forte" . aphyr.com . Afiro . Estratto il 13 aprile 2018 .