Blocco a due fasi

Blocco a due fasiModifica

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:

1. Fase di espansione (detta anche fase di crescita): i blocchi vengono acquisiti e nessun blocco viene rilasciato (il numero di blocchi può solo aumentare).
2. Fase di contrazione (detta anche fase di contrazione): i blocchi vengono rilasciati e nessun blocco viene acquisito.

Le regole di blocco in due fasi possono essere riassunte come: mai acquisire un blocco dopo che un blocco è stato rilasciato. La proprietà di serializzabilità è garantita per un programma con transazioni che obbediscono a questa regola.

In genere, senza una conoscenza esplicita in una transazione sulla fine della fase 1, si determina con sicurezza solo quando una transazione ha completato l’elaborazione e richiesto il commit. In questo caso, tutti i lock possono essere rilasciati in una volta sola (fase 2).

Conservatore del locking a due fasiModifica

La differenza tra 2PL e C2PL è che le transazioni C2PL ottengono tutti i lock di cui hanno bisogno prima che le transazioni inizino. Questo per assicurare che una transazione che già detiene alcune chiusure non si blocchi in attesa di altre chiusure. Il 2PL conservativo previene i deadlock.

Strict two-phase lockingEdit

Per essere conforme al protocollo S2PL, una transazione deve essere conforme al 2PL, e rilasciare i suoi lock di scrittura (esclusivi) solo dopo che si è conclusa, cioè è stata commessa o abortita. D’altra parte, i blocchi di lettura (condivisi) sono rilasciati regolarmente durante la fase 2. Questo protocollo non è appropriato negli alberi B perché causa un collo di bottiglia (mentre gli alberi B iniziano sempre la ricerca dalla radice madre).

Strong strict two-phase lockingEdit

o Rigorousness, o Rigorous scheduling, o Rigorous two-phase locking

Per rispettare il strong strict two-phase locking (SS2PL) il protocollo di locking rilascia entrambi i lock di scrittura (esclusivi) e lettura (condivisi) applicati da una transazione solo dopo che la transazione è finita, cioè, solo dopo aver completato l’esecuzione (essere pronti) e dopo essere stati impegnati o interrotti. Questo protocollo è anche conforme alle regole S2PL. Una transazione che obbedisce a SS2PL può essere vista come se avesse una fase 1 che dura l’intera durata dell’esecuzione della transazione, e nessuna fase 2 (o una fase 2 degenerata). Così, solo una fase è effettivamente lasciata, e “due fasi” nel nome sembra essere ancora utilizzato a causa dello sviluppo storico del concetto da 2PL, e 2PL è una superclasse. La proprietà SS2PL di un programma è anche chiamata Rigorosità. È anche il nome della classe di programmi che hanno questa proprietà, e un programma SS2PL è anche chiamato “programma rigoroso”. Il termine “Rigorosità” è libero dall’inutile retaggio di “bifase”, oltre ad essere indipendente da qualsiasi meccanismo (di blocco) (in linea di principio altri meccanismi di blocco possono essere utilizzati). Il rispettivo meccanismo di blocco della proprietà è talvolta indicato come Rigoroso 2PL.

SS2PL è un caso speciale di S2PL, cioè, la classe di programmi SS2PL è una vera e propria sottoclasse di S2PL (ogni programma SS2PL è anche un programma S2PL, ma esistono programmi S2PL che non sono SS2PL).

SS2PL è stato il protocollo di controllo della concorrenza scelto per la maggior parte dei sistemi di database e utilizzato fin dai loro primi giorni negli anni 70. Ha dimostrato di essere un meccanismo efficace in molte situazioni, e fornisce oltre alla serializzabilità anche la severità (un caso speciale di recuperabilità senza cascata), che è strumentale per un efficiente recupero del database, e anche l’ordine di impegno (CO) per partecipare ad ambienti distribuiti in cui vengono impiegate soluzioni di serializzabilità distribuita e serializzabilità globale basate su CO. Essendo un sottoinsieme di CO, esiste un’implementazione efficiente di SS2PL distribuito senza un gestore di blocco distribuito (DLM), mentre i deadlock distribuiti (vedi sotto) sono risolti automaticamente. Il fatto che SS2PL impiegato in sistemi di database multipli assicuri la serializzabilità globale era noto da anni prima della scoperta di CO, ma solo con CO è arrivata la comprensione del ruolo di un protocollo di impegno atomico nel mantenere la serializzabilità globale, così come l’osservazione della risoluzione automatica dei deadlock distribuiti (vedi un esempio dettagliato di SS2PL distribuito). Di fatto, SS2PL che eredita le proprietà di Recoverability 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à (tuttavia la serializzabilità è anche implicita in CO), non è noto per fornire a SS2PL altre qualità significative. La 2PL nella sua forma generale, così come quando è combinata con la severità, cioè la Strictness 2PL (S2PL), non è nota per essere utilizzata in 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 menzionato sopra, le utili proprietà di Strictness e Commitment ordering.

Esistono molte varianti di SS2PL che utilizzano vari tipi di lock con varie semantiche in diverse situazioni, inclusi i casi di cambiamento del tipo di lock durante una transazione. Notevoli sono le varianti che usano il locking a granularità multipla.

1. SS2PL vs. S2PL: Entrambi forniscono Serializzabilità e Strictness. Poiché S2PL è una superclasse di SS2PL può, in linea di principio, fornire più concorrenza. Tuttavia, in pratica non si nota alcun vantaggio in termini di concorrenza (esiste esattamente lo stesso locking per entrambi, con un rilascio del lock praticamente non molto anticipato per S2PL), e l’overhead di gestire un meccanismo di fine-fase-1 in S2PL, separato dalla fine della transazione, non è giustificato. Inoltre, mentre SS2PL fornisce l’ordine di Commitment, S2PL non lo fa. Questo spiega la preferenza di SS2PL rispetto a S2PL.
2. 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 locking “Release all locks only after transaction end”, che è il protocollo di SS2PL. Così, “Strict 2PL” non potrebbe essere lì il nome dell’intersezione di Strictness e 2PL, che è più grande della classe generata dal protocollo SS2PL. Questo ha causato confusione. Con una definizione esplicita di S2PL come intersezione di Strictness e 2PL, un nuovo nome per SS2PL, e una distinzione esplicita tra le classi S2PL e SS2PL, gli articoli (Breitbart et al. 1991) e (Raz 1992) hanno inteso chiarire la confusione: il primo usando il nome “rigorosità,” e il secondo “SS2PL.”
3. Esiste una proprietà più generale di SS2PL (una superclasse di programmazione), Strict commitment ordering (Strict CO, o SCO), che pure fornisce sia serializzabilità, rigorosità e CO, e ha un overhead di locking simile. A differenza di SS2PL, SCO non si blocca in caso di conflitto lettura-scrittura (un blocco in lettura non blocca l’acquisizione di un blocco in scrittura; sia SCO che SS2PL hanno lo stesso comportamento per i conflitti scrittura-lettura e scrittura-scrittura) al costo di un possibile commit ritardato, e su tale tipo di conflitto SCO ha un tempo medio di completamento della transazione più breve e prestazioni migliori di SS2PL. Mentre SS2PL obbedisce alla tabella di compatibilità dei lock di cui sopra, SCO ha la seguente tabella:

Si noti che sebbene SCO rilasci tutti i lock alla fine della transazione e rispetti le regole del locking 2PL, SCO non è un sottoinsieme di 2PL a causa della sua diversa tabella di compatibilità dei lock. SCO permette conflitti di lettura-scrittura materializzati tra due transazioni nelle loro fasi 1, cosa che 2PL non permette nella fase 1 (vedere i conflitti materializzati in Serializability). D’altra parte 2PL permette altri tipi di conflitti materializzati nella fase 2 che SCO non permette affatto. Insieme questo implica che le classi di programmazione 2PL e SCO sono incomparabili (cioè, nessuna classe contiene l’altra classe).

Riassunto – Relazioni tra le classiModifica

Contenimento delle classi di programma: Una freccia dalla classe A alla classe B indica che la classe A contiene strettamente B; la mancanza di un percorso diretto tra le classi significa che le classi sono incomparabili. Una proprietà è intrinsecamente bloccante, se può essere applicata solo bloccando le operazioni di accesso ai dati della transazione fino a quando non si verificano certi eventi in altre transazioni. (Raz 1992)

Tra due qualsiasi classi di programma (definite dalle rispettive proprietà dei programmi) che hanno programmi comuni, o una contiene l’altra (contiene strettamente se non sono uguali), o sono incomparabili. Le relazioni di contenimento tra le classi 2PL e le altre principali classi di calendario sono riassunte nel seguente diagramma. 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 orari non nella classe 2PL).