Bloccaggio bifase - Two-phase locking
Nei database e nell'elaborazione delle transazioni , il blocco a due fasi ( 2PL ) è un metodo di controllo della concorrenza che garantisce la serializzabilità . È anche il nome dell'insieme risultante di pianificazioni delle transazioni del database (cronologia). Il protocollo utilizza blocchi , applicati da una transazione ai dati, che possono bloccare (interpretati come segnali di arresto) altre transazioni dall'accesso agli stessi dati durante la vita della transazione.
Con il protocollo 2PL, i blocchi vengono applicati e rimossi in due fasi:
- Fase di espansione: i lock vengono acquisiti e non vengono rilasciati lock.
- Fase di restringimento: le serrature vengono rilasciate e non vengono acquisite serrature.
Il protocollo di base utilizza due tipi di blocchi: i blocchi condivisi ed esclusivi . I perfezionamenti del protocollo di base possono utilizzare più tipi di blocco. Utilizzando blocchi che bloccano i processi, 2PL può essere soggetto a deadlock che derivano dal blocco reciproco di due o più transazioni.
Blocchi per l'accesso ai dati
Un blocco è un oggetto di sistema associato a una risorsa condivisa come un elemento di dati di tipo elementare, una riga in un database o una pagina di memoria. In un database, potrebbe essere necessario acquisire un blocco su un oggetto del database (un blocco di accesso ai dati) da una transazione prima di accedere all'oggetto. L'uso corretto dei blocchi impedisce operazioni indesiderate, errate o incoerenti su risorse condivise da parte di altre transazioni simultanee. Quando un oggetto di database con un blocco esistente acquisito da una transazione deve essere accessibile da un'altra transazione, il sistema controlla il blocco esistente per l'oggetto e il tipo di accesso previsto. Se il tipo di blocco esistente non consente questo specifico tipo di accesso simultaneo tentato, la transazione che tenta l'accesso viene bloccata (in base a un accordo/schema predefinito). In pratica, un blocco su un oggetto non blocca direttamente l'operazione di una transazione sull'oggetto, ma impedisce a tale transazione di acquisire un altro blocco sullo stesso oggetto, necessario per essere tenuto/possesso dalla transazione prima di eseguire questa operazione. Pertanto, con un meccanismo di blocco, il necessario blocco delle operazioni è controllato da un opportuno schema di blocco dei blocchi, che indica quale tipo di blocco blocca quale tipo di blocco.
Vengono utilizzati due tipi principali di serrature:
- Write-lock ( blocco esclusivo ) è associato a un oggetto di database da una transazione (Terminologia: "la transazione blocca l'oggetto" o "acquisisce il blocco per esso") prima di scrivere (inserire/modificare/eliminare) questo oggetto.
- Read-lock ( blocco condiviso ) è associato a un oggetto di database da una transazione prima di leggere (recuperare lo stato di) questo oggetto.
Le interazioni comuni tra questi tipi di blocco sono definite dal comportamento di blocco come segue:
- Un blocco di scrittura esistente su un oggetto di database blocca una scrittura prevista sullo stesso oggetto (già richiesta/emessa) da un'altra transazione, impedendo che un rispettivo blocco di scrittura venga acquisito dall'altra transazione. Il secondo write-lock verrà acquisito e la scrittura richiesta dell'oggetto avrà luogo (materializzarsi) dopo il rilascio del write-lock esistente.
- Un blocco di scrittura blocca una lettura prevista (già richiesta/emessa) da un'altra transazione bloccando il rispettivo blocco di lettura .
- Un blocco di lettura blocca una scrittura prevista da un'altra transazione bloccando il rispettivo blocco di scrittura .
- Un blocco di lettura non blocca una lettura prevista da un'altra transazione. Il rispettivo blocco di lettura per la lettura prevista viene acquisito (condiviso con la lettura precedente) immediatamente dopo la richiesta della lettura prevista, quindi ha luogo la lettura prevista.
Esistono diverse varianti e perfezionamenti di questi principali tipi di blocco, con rispettive variazioni del comportamento di blocco. Se un primo blocco blocca un altro blocco, i due blocchi sono detti incompatibili ; altrimenti le serrature sono compatibili . Spesso, i tipi di blocco che bloccano le interazioni sono presentati nella letteratura tecnica da una tabella di compatibilità dei blocchi . Di seguito è riportato un esempio con i principali tipi di blocco comuni:
Tabella di compatibilità delle serrature Tipo di blocco blocco di lettura blocco scrittura blocco di lettura ? X blocco scrittura X X
- ✔ indica compatibilità
- X indica un'incompatibilità, cioè un caso in cui un lock del primo tipo (nella colonna di sinistra) su un oggetto impedisce che un lock del secondo tipo (nella riga in alto) venga acquisito sullo stesso oggetto (da un'altra transazione). Un oggetto in genere ha una coda di operazioni richieste (dalle transazioni) in attesa con i rispettivi blocchi. Il primo blocco bloccato per l'operazione nella coda viene acquisito non appena il blocco di blocco esistente viene rimosso dall'oggetto, quindi viene eseguita la rispettiva operazione. Se un blocco per l'operazione in coda non è bloccato da alcun blocco esistente (è possibile l'esistenza di più blocchi compatibili su uno stesso oggetto contemporaneamente), viene acquisito immediatamente.
- Commento: In alcune pubblicazioni, le voci della tabella sono semplicemente contrassegnate come "compatibili" o "incompatibili" o rispettivamente "sì" o "no".
Bloccaggio bifase e suoi casi particolari
Bloccaggio bifase
Secondo il protocollo di blocco a due fasi , una transazione gestisce i suoi blocchi in due fasi distinte e consecutive durante l'esecuzione della transazione:
- Fase di espansione (aka fase di crescita): i blocchi vengono acquisiti e non vengono rilasciati blocchi (il numero di blocchi può solo aumentare).
- Fase di restringimento (nota anche come fase di contrazione): i blocchi vengono rilasciati e non vengono acquisiti blocchi.
Le due regole di blocco di fase possono essere riassunte come: non acquisire mai un blocco dopo che un blocco è stato rilasciato. La proprietà di serializzabilità è garantita per una pianificazione con transazioni che obbediscono a questa regola.
In genere, senza una conoscenza esplicita in una transazione alla fine della fase 1, viene determinata in modo sicuro solo quando una transazione ha completato l'elaborazione e ha richiesto il commit. In questo caso è possibile sbloccare contemporaneamente tutte le serrature (fase 2).
Blocco conservativo a due fasi
La differenza tra 2PL e C2PL è che le transazioni di C2PL ottengono tutti i blocchi di cui hanno bisogno prima dell'inizio delle transazioni. Questo per garantire che una transazione che contiene già alcuni blocchi non si blocchi in attesa di altri blocchi. Il 2PL conservativo previene i deadlock .
Rigoroso bloccaggio a due fasi
Per rispettare il protocollo S2PL, una transazione deve rispettare 2PL, e rilasciare la sua scrittura (esclusiva) blocca solo dopo che si è concluso, vale a dire, essendo sia commesso o interrotta . D'altra parte, i blocchi di lettura (condivisi) vengono rilasciati regolarmente durante la fase 2. Questo protocollo non è appropriato nei B-tree perché causa un collo di bottiglia (mentre i B-tree iniziano sempre a cercare dalla radice padre).
Forte e rigoroso bloccaggio a due fasi
o Rigorezza , o Rigorosa programmazione , o Rigorosa chiusura a due fasi
Per conformarsi al forte rigoroso blocco a due fasi (SS2PL) il protocollo di blocco rilascia sia i blocchi di scrittura (esclusivi) che quelli di lettura (condivisi) applicati da una transazione solo dopo che la transazione è terminata, ovvero solo dopo che entrambi hanno completato l'esecuzione (essere pronti ) e diventando commesso o abortito . Questo protocollo è inoltre conforme alle regole S2PL. Una transazione che obbedisce a SS2PL può essere vista come avente la fase 1 che dura l'intera durata dell'esecuzione della transazione e nessuna fase 2 (o una fase 2 degenerata). Quindi, in realtà è rimasta solo una fase e "due fasi" nel nome sembra essere ancora utilizzata a causa dello sviluppo storico del concetto da 2PL, e 2PL è una super-classe. La proprietà SS2PL di una pianificazione è anche chiamata Rigorezza . È anche il nome della classe di schedulazioni che ha questa proprietà e una schedulazione SS2PL è anche chiamata "schedula rigorosa". Il termine "Rigorezza" è libero dall'eredità non necessaria di "due fasi", oltre ad essere indipendente da qualsiasi meccanismo (di blocco) (in linea di principio è possibile utilizzare altri meccanismi di blocco). Il rispettivo meccanismo di blocco della proprietà è talvolta indicato come Rigorous 2PL .
SS2PL è un caso speciale di S2PL, cioè la classe di schedulazioni SS2PL è una sottoclasse propria di S2PL (ogni schedula SS2PL è anche una schedulazione S2PL, ma esistono schedulazioni S2PL che non sono SS2PL).
SS2PL è stato il protocollo di controllo della concorrenza prescelto per la maggior parte dei sistemi di database e utilizzato sin dai primi giorni negli anni '70. Si è dimostrato un meccanismo efficace in molte situazioni, e fornisce oltre alla Serializability anche Strictness (un caso speciale di Cascadeless Recoverability), che è strumentale per un efficiente ripristino del database , e anche Commitment Ordering (CO) per la partecipazione in ambienti distribuiti in cui un CO vengono impiegate soluzioni di serializzabilità distribuita basata e serializzabilità globale . Essendo un sottoinsieme di CO, esiste un'implementazione efficiente di SS2PL distribuito senza un gestore di lock distribuito (DLM), mentre i deadlock distribuiti (vedi sotto) vengono risolti automaticamente. Il fatto che SS2PL impiegato in sistemi multi database garantisca la serializzabilità globale è noto da anni prima della scoperta di CO, ma solo con CO è arrivata la comprensione del ruolo di un protocollo di impegno atomico nel mantenimento della serializzabilità globale, nonché l'osservazione di risoluzione deadlock distribuita (vedere un esempio dettagliato di Distributed SS2PL ). Infatti, SS2PL eredita le proprietà di Recuperabilità e CO è più significativo che essere un sottoinsieme di 2PL, che di per sé nella sua forma generale, oltre a comprendere un semplice meccanismo di serializzabilità (comunque la serializzabilità è implicita anche da CO), in non noto per fornire a SS2PL qualsiasi altra qualità significativa. 2PL nella sua forma generale, così come quando combinato con Strictness, cioè Strict 2PL (S2PL), non è noto per essere utilizzato nella pratica. Il popolare SS2PL non richiede la marcatura "fine della fase 1" come fanno 2PL e S2PL, e quindi è più semplice da implementare. Inoltre, a differenza del 2PL generale, SS2PL fornisce, come accennato in precedenza, le utili proprietà di ordinamento di Rigore e Impegno .
Esistono molte varianti di SS2PL che utilizzano vari tipi di blocco con varie semantiche in diverse situazioni, inclusi casi di modifica del tipo di blocco durante una transazione. Notevoli sono le varianti che utilizzano il blocco della granularità multipla .
Commenti:
- SS2PL vs. S2PL: entrambi forniscono serializzabilità e rigore. Poiché S2PL è una superclasse di SS2PL, in linea di principio può fornire più concorrenza. Tuttavia, in genere non si nota praticamente alcun vantaggio di concorrenza (esiste esattamente lo stesso blocco per entrambi, con un rilascio del blocco praticamente non molto precedente per S2PL) e il sovraccarico di gestire un meccanismo di fine fase-1 in S2PL, separato dalla fine della transazione , non è giustificato. Inoltre, mentre SS2PL fornisce l' ordine Commitment , S2PL no. Questo spiega la preferenza di SS2PL su S2PL.
- Soprattutto prima del 1990, ma anche dopo, in molti articoli e libri, ad esempio (Bernstein et al. 1987, p. 59), il termine "Strict 2PL" (S2PL) è stato spesso definito dal protocollo di chiusura "Release all locks only dopo la fine della transazione", che è il protocollo di SS2PL. Quindi, "Strict 2PL" non potrebbe essere il nome dell'intersezione di Strictness e 2PL, che è più grande della classe generata dal protocollo SS2PL. Questo ha creato confusione. Con un'esplicita definizione di S2PL come l'intersezione di Rigore e 2PL, un nuovo nome per SS2PL, e un'esplicita distinzione tra le classi S2PL e SS2PL, gli articoli (Breitbart et al. 1991) e (Raz 1992) hanno inteso azzerare il confusione: il primo usando il nome "rigorezza", e il secondo "SS2PL".
- Esiste una proprietà più generale di SS2PL (una superclasse di pianificazione), ordinamento di impegno rigoroso (CO rigoroso o SCO), che fornisce anche serializzabilità, rigore e CO e ha un sovraccarico di blocco simile. A differenza di SS2PL, SCO non si blocca in caso di conflitto di lettura-scrittura (un blocco di lettura non blocca l'acquisizione di un blocco di scrittura; sia SCO che SS2PL hanno lo stesso comportamento per i conflitti di scrittura-lettura e scrittura-scrittura) al costo di un possibile ritardo commit e su tale tipo di conflitto SCO ha un tempo medio di completamento della transazione più breve e prestazioni migliori rispetto a SS2PL. Mentre SS2PL obbedisce alla tabella di compatibilità dei blocchi sopra, SCO ha la seguente tabella:
Compatibilità serratura per SCO Tipo di blocco blocco di lettura blocco scrittura blocco di lettura X blocco scrittura X X
- Si noti che sebbene SCO rilasci tutti i blocchi alla fine della transazione e sia conforme alle regole di blocco 2PL, SCO non è un sottoinsieme di 2PL a causa della sua diversa tabella di compatibilità dei blocchi. SCO consente conflitti materializzati di lettura-scrittura tra due transazioni nelle loro fasi 1, cosa che 2PL non consente nella fase 1 (vedi sui conflitti materializzati in Serializability ). D'altra parte 2PL consente altri tipi di conflitto materializzato nella fase 2 che SCO non consente affatto. Insieme questo implica che le classi di programma 2PL e SCO sono incomparabili (cioè, nessuna classe contiene l'altra classe).
Riepilogo - Relazioni tra le classi
Tra due classi di abachi (definite dalle rispettive proprietà degli abachi) che hanno schedulazioni comuni, una contiene l'altra ( contiene rigorosamente se non sono uguali), oppure sono incomparabili . Le relazioni di contenimento tra le classi 2PL e le altre principali classi di pianificazione sono riassunte nel diagramma seguente. 2PL e le sue sottoclassi sono intrinsecamente bloccanti , il che significa che non esistono implementazioni ottimistiche per loro (e ogni volta che viene menzionato "Optimistic 2PL" si riferisce a un meccanismo diverso con una classe che include anche pianificazioni non nella classe 2PL).
Deadlock in 2PL
I blocchi bloccano le operazioni di accesso ai dati. Il blocco reciproco tra le transazioni determina un deadlock , in cui l'esecuzione di queste transazioni viene bloccata e non è possibile raggiungere il completamento. Pertanto, i deadlock devono essere risolti per completare le esecuzioni di queste transazioni e rilasciare le risorse di elaborazione correlate. Un deadlock è un riflesso di un potenziale ciclo nel grafico di precedenza , che si verificherebbe senza il blocco. Un deadlock viene risolto interrompendo una transazione coinvolta con tale ciclo potenziale e interrompendo il ciclo. Viene spesso rilevato utilizzando un grafico wait-for (un grafico di conflitti bloccati dalla materializzazione dei lock; conflitti non materializzati nel database a causa di operazioni bloccate non si riflettono nel grafico di precedenza e non influiscono sulla serializzabilità ), che indica quale transazione è "in attesa di" il rilascio del blocco con quale transazione e un ciclo indica un deadlock. L'interruzione di una transazione per ciclo è sufficiente per interrompere il ciclo. Se una transazione è stata interrotta a causa della risoluzione di un deadlock, spetta all'applicazione decidere cosa fare dopo. Di solito, un'applicazione riavvia la transazione dall'inizio, ma può ritardare questa azione per dare ad altre transazioni tempo sufficiente per terminare per evitare di causare un altro deadlock.
In un ambiente distribuito , per l' atomicità viene utilizzato un protocollo di impegno atomico , in genere il protocollo di commit a due fasi (2PC) . Quando i dati recuperabili (dati sotto il controllo delle transazioni) sono partizionati tra i partecipanti 2PC (ovvero, ogni oggetto dati è controllato da un singolo partecipante 2PC), i deadlock distribuiti (globali), i deadlock che coinvolgono due o più partecipanti in 2PC, vengono risolti automaticamente come segue:
Quando SS2PL viene effettivamente utilizzato in un ambiente distribuito, i deadlock globali dovuti al blocco generano deadlock di voto in 2PC e vengono risolti automaticamente da 2PC (vedere Ordine di impegno (CO), in Caratterizzazione esatta dei deadlock di voto per cicli globali ; Nessun riferimento tranne che gli articoli CO sono noti per notare questo). Per il caso generale di 2PL, i deadlock globali vengono similmente risolti automaticamente dal protocollo del punto di sincronizzazione dell'estremità della fase 1 in una transazione distribuita (il punto di sincronizzazione viene raggiunto "votando" (notificando l'estremità della fase 1 locale) ed essendo propagato al partecipanti a una transazione distribuita allo stesso modo di un punto di decisione in impegno atomico; in analogia al punto di decisione in CO, un'operazione conflittuale in 2PL non può avvenire prima del punto di sincronizzazione finale della fase 1, con lo stesso deadlock di voto risultante nel caso di un deadlock globale di accesso ai dati; il deadlock di voto (che è anche un deadlock globale basato sul blocco) viene risolto automaticamente dal protocollo che interrompe alcune transazioni coinvolte, con un voto mancante, in genere utilizzando un timeout ).
Commento :
- Quando i dati sono partizionati tra i partecipanti al protocollo di impegno atomico (ad es. 2PC), la risoluzione automatica dei deadlock globali è stata trascurata nella letteratura di ricerca sui database, sebbene i deadlock in tali sistemi siano stati un'area di ricerca piuttosto intensa:
- Per CO e il suo caso speciale SS2PL, la risoluzione automatica tramite il protocollo di impegno atomico è stata notata solo negli articoli CO. Tuttavia, è stato notato nella pratica che in molti casi i deadlock globali vengono rilevati molto raramente dai meccanismi di risoluzione dedicati, meno di quanto ci si potesse aspettare ("Perché vediamo così pochi deadlock globali?"). Il motivo sono probabilmente i deadlock che vengono risolti automaticamente e quindi non gestiti e non conteggiati dai meccanismi;
- Per 2PL in generale, la risoluzione automatica tramite il protocollo del punto di sincronizzazione (obbligatorio) di
