Rintrah84
26-06-2009, 19:51
Ciao,
tra pochissimi giorni dovrò sostenere un orale relativo ai database...in particolar modo la teoria tratterà argomenti come la teoria della gestione della concorrenza...tra l'altro devo portare anche una tesina e pensavo di farla su questo argomento (è il più complesso e per questo motivo avendo poco tempo è quello su cui ho studiato di più).
Per gli studenti di Tor Vergata...evitate di fare copia e incolla sulla vostra tesina altrimenti portiamo 2 tesine uguali e non sarebbe carino... :D
Quì di seguito posto le mie idee su quello che ho capito...potete dirmi se ci sono imperfezioni\errori\incomprensioni? Dovendoci fare una tesina preferirei evitare di scrivere michiate...poi magari può essere anche stimolante per qualcun altro :)
DEFINIZIONE DI TRANSAZIONE: E' l'unità di lavoro fondamentale svolta da un'applicazione e viene fatto riferimento specialmente alle operazioni che modificano il contenuto del DB. Ogni transazione è specificata racchiudendo la sequenza di operazioni che la compongono dentro una coppia di istruzioni che ne specificano l'inizio e la fine, queste istruzioni sono:
1) START: dice dove inizia la transazione
2) COMMIT: richiede una conclusione positiva della transazione e richiede che tutti gli aggiornamenti siano salvati sul DB (proprietà di persistenza appartenente alle proprietà ACID)
o ROLBACK: in alcuni casi si possono verificare delle condizione che portano all'annullamento degli aggiornamenti (tramite operazioni di undo nel file di log del controllore dell'affidabilità del DBMS).
Generalmente le transazioni sono concorrenti, ovvero più transazioni possono voler accedere in letura o scrittura agli stessi dati in maniera contemporanea.
Potenzialmente il numero di transazioni che arrivano ad un DBMS possono essere anche dell'ordine di migliaia di transazioni per secondo, ciò rende impossibile pensare ad una loro esecuzione seriale, da quì deriva l'esigenza di trattarle in modo concorrente.
Un'eventuale errata gestione della concorrenza potrebbe portare alle famose anomalie (che non le descrivo per non dilungarmi troppo...sono stranote e casomai le aggiungo sulla tesina per fare spessore): PERDITA DI AGGIORNAMENTO, LETTURA SPORCA, LETTURE INCONSISTENTI, AGGIORNAMENTI FANTASMA, INSERIMENTO FANTASMA.
A grandi linee si può affermare che il controllore della concorrenza è il componente di un DBMS che riceve le ricieste di accesso ai dati e decide se accettarle o rifiutarle
Da quì l'esigenza di trattare con un approccio scientifico la teoria del controllo di concorrenza poichè non si può lasciare al caso l'esecuzione delle varie azioni all'interno di transazioni concorrenti.
Per semplicità possiamo definire una transazione come una sequenza di azioni di LETTURA o di SCRITTURA. Sotto questa assunzione una transazione è un oggetto sintattico di cui si conoscono soltanto le azioni di ingresso ed uscita.
Un esempio di transazione può essere:
t1 = r1(x), r1(y), w1(x), w1(y)
mentre uno SCHEDULE è definito come la sequenza di operazioni presentate da transazioni concorrenti.
Un esempio di schedule può essere:
S1 = r1(x), r2(z), w1(x), w2(z),...
con r1(x) rappresenta la lettura dell'oggetto x da parte della transazione 1 mentre r2(z) rappresenta la letura dell'oggetto z da parte della transazione 2.
Lo scopo del controllore della concorrenza è quindi quello di accettare alcuni schedule e rifiutarne altri in modo da evitare le anomalie sopracitate. Il modulo che gestisce tale funzione viene per questo detto SCHEDULER.
Per lo studio della teoria del controllo di concorrenza si assume per facilità che le transazione che formano un qualsiasi schedule abbiano tutte un esito ovvero terminino tutte con una operazione di COMMIT escoludendo così il caso in cui al posto della commit vi sia un'istruzione di rolback.
Uno schedue di questo tipo si definisce come COMMIT PROIEZIONE e facendo questa assunzione il relativo scheduler non potrà mai rilevare e gestire i casi in cui si verifica l'operazione di LETTURA SPORCA (che prevede un'operazione di ABORT).
Definiamo SCHEDULE SERIALE un qualsiasi schedule in cui le azioni di ogni transazione compaiano in sequenza senza essere inframezzate da azioni di altre transazioni.
Ad esempio il seguente schedule è seriale:
Ho 3 transazioni: t0, t1, t2 e lo schedule seriale:
S= r0(x), r0(y), w0(x), r1(y) w1(y), r1(x), r2(x), w2(y), r2(y)
L'esecuzione di uno schedule a commit proiezione è CORRETTO se e solo se produce lo stesso risultato di uno schedule seriale ed in questo caso si dice che è SERIALIZZABILE.
Quindi lo studio della teoria del controllo di concorrenza si pone come obbiettivo principale quello di riuscire a capire se dato un qualsiasi schedule questo sia serializzabile quindi da accettare, oppure no quindi da rifiutare.
Per rispondere a questa domanda sono state trovate varie soluzioni, alcune valide solo dal punto di vista teorico ma non applicabili praticamente poichè troppo costose dal punto di vista algoritmico, quì di seguito ne saranno presentate 3:
1) DEFINIZIONE DI VIEW EQUIVALENZA: Viene definita un'operazione che lega COPPIE DI OPERAZIONE di lettura e scrittura nel seguente modo:
1) Un'operazione di lettura r_i(x) LEGGE DA UN'OPERAZIONE DI SCRITTURA w_j(x) se e solo se w_j(x) precede r_i(x) e non vi è alcuna operazione di scrittura w_k(x) nel mezzo.
2) Un'operazione di scrittura w_i(x) si dice SCRITTURA FINALE se è l'ultima operazione di scrittura che agisce sull'oggetto x nello schedule considerato.
Definita questa relazione si dice che 2 schedule sono VIEW EQUIVALENTI se entrambi possiedono la stessa relazione "LEGGE DA" e la stessa scrittura finale
Per esempio considerando questi 2 schedule possiamo affermare che sono view equivalenti:
S1: w0(x), r2(x), r1(x), w2(x), w2(z)
S2: w0(x), r1(x), r2(x), w2(x), w2(z)
perchè entrambi hanno la stessa scrittura finale w2(z) e poichè possiedono la stessa relazione "LEGGE DA" in quanto in S1 la transazione 2 legge da x dopo che la transazione 0 ha scritto x e la stessa cosa accade nello schedule S2.
Uno schedule si definisce VIEW SERIALIZABBILE se è VIEW EQUIVALENTE ad uno scedule seriale.
Ad esempio questo schedule è view serializzabile:
S1: w0(x), r1(x), w1(x), r2(x), w1(z)
in quanto è view equivalente a questo schedule seriale:
S2: w0(x), r1(x), w1(x), w1(z), r2(x) (è seriale)
come prima si nota che hanno la stessa scrittua finale w1(z) e la stessa relazione "LEGGE DA".
E' facilmente dimostrabile che schedule che generano le anomalie di cui ho parlato in precedenza non sono mai serializzaili.
Uno schedule potrebbe utilizzare questa tecnica per determinare se uno schedule è view equivalente ad un qualsiasi schedule seriale, tuttavia trattandosi di un problema NP-HARD (può esistere un numero esponenziale di schedule seriali determinato da tutte le permutazioni delle transazioni con cui confrontare lo schedule dato) tale tecnica non risulta applicabile per scopi pratici.
2) DEFINIZIONE DI CONFLICT EQUIVALENZA:
Tale tecnica si basa sulla definizione di CONFLITTO, cioè: Date due azioni a_i ed a_j, con i diverso da j, si dice che a_i è in conflitto con a_j se esse operano sullo stesso oggetto e se almeno una di esse è un'azione di scrittura. Quindi avremo i seguenti casi di conflitto:
1) CONFLITTI LETTURA-SCRITTURA: RW o WR
2) CONFLITTI SCRITTURA-SCRITTURA: WW
Uno schedule S_i è CONFLICT EQUIVALENTE ad un altro schedule S_j se i 2 schedule presentano le stesse operazioni ed ogni coppia di operazioni in conflitto è nelo stesso ordine nei due schedule.
Ad esempio i seguenti due schedule sono conflict equivalenti:
S1: w0(x), r1(x), w0(z), r1(z), r2(x), r3(z), w3(z), w1(x)
S2; w0(x), w0(z), r1(x), r2(x), r1(z), w1(x), r3(z), w3(z)
Perchè contengono le stesse operazioni e l'ordine dei conflitti è lo stesso. Ad esempio sia in S1 che in S2 il primo conflitto che si verifica è quello tra w0(x) ed r1(x).
Si nota che l'insieme degli schedule conflict serializzabili è contenuto propriamente nell'insieme degli schedule view serializzabile quindi la conflict serializzabilità è una condizione sufficiente (ma non necessaria) per la view equivalenza.
Esiste un algoritmo per determinare se uno schedule è CONFLICT SERIALIZZABILE (cioè se uno schedule è conflict equivalente ad uno schedule seriale) e tale algoritmo si basa sull'analisi del GRAFO DEI CONFLITTI.
Il GRAFO DEI CONFLITTI viene costruito facendo corrispondere uno specifico nodo ad ogni transazione che compare nello schedule di partenza. Si traccia un arco orientato dal nodo t_i al nodo t_j se esiste almeno un conflitto tra un'azione a_i della transazione t_i ed un'azione a_j appartenente alla transazione t_j.
Dopo aver così costruito il grafo dei conflitti, se tale grafo è ACICLICO allora lo schedule di partenza è CONFLICT EQUIVALENTE AD UNO SCHEDULE SERIALE poichè il grafo non presentando cicli al suo interno definirà un ORDINAMENTO TOPOLOGICO DEI NODI che porterà facilmente alla costruzione del corrispondente schedule seriale.
Anche se l'analisi della ciclicità di un grafo ha una complessità lineare rispetto alla dimensioni del grafo stesso l'uso di tale tecnica risulta ancora troppo onerosa in termini temporali e di risorse richieste. Inoltre tale tecnica risulta assolutamente inaccettabile in un contesto di database distribuito poichè il grafo dovrebbe essere ricostrutio a partire da archi che vengono riconosciuti sui diversi server del sistema distribuito. Per questi motivi anche questa tecnica rimane solamente una soluzione teorica che non ha alcuna applicazione pratica all'interno dei DBMS.
DEFINIZIONE DI LOCKING A 2 FASI: Si tratta della tecnica più nota utilizzata nei DBMS per risolvere il problema della gestione delle transazioni concorrenti e sfrutta un'intuizione molto semplice cioè di PROTEGGERE TUTTE LE OPERAZIONI DI LETTURA E SCRITTURA mediante le seguenti primitive:
1) r_lock: Protegge le operazioni di lettura
2) w_lock: Protegge le operazioni di scrittura
3) unlock: Toglie il lock da un'operazione di lettura o di scrittura.
Lo scheduler viene detto LOCK MANAGER in quanto il suo compito risulta essere quello di lockare ed unlockare le risorse in modo appropriato rispettando i seguenti semplici vincoli:
1) LOCK CONDIVISO: Ogni operazione di lettura deve essere preceduta dall'invocazione della primitiva r_lock sulla risorse a cui si vuole accedere in lettura e seguida da una unlock. Su un dato a cui si accede in lettura possono essere attivi contemporaneamente più r_lock e per questo si dice lock condiviso.
2) LOCK ESCLUSIVO: Ogni operazione di scrittura deve essere preceduta dall'invocazione della primitiva w_lock e deve essere seguita da una unlock. Su un dato a cui una transazione accede in scrittura non possono essere attivi altri w_lock, ciò significa che solo una transazione per volta può scrivere su di una certa risorse e per questo prende il nome di lock esclusivo.
Il gestore della concorrenza riceve le richieste di lock da parte delle varie transazioni e tramite una TABELLA DEI CONFLITTI determina se concedere o meno il lock della risorsa a tale transazione.
Le politiche in base a cui la tabella dei conflitti permette al gestore della concorrenza se concedere o meno il lock della risorsa richiesto sono le seguenti:
Se viene richiesto un r_lock per una determinata risorsa succede così: se la risorsa è completamente libera, viene concesso l'r_lock, se ci sono già attivi altri r_lock di altre transazioni su tale risorsa viene comunque concesso (più transazioni possono leggere contemporaneamente la stessa risorsa), se è attivo un w_lock su tale risorsa allora non viene concesso l'r_lock.
Se viene richiesto un w_lock e lo stato della risorsa è completamente libero, allora il w_lock viene concesso, se su tale risorsa è già attivo uno o più r_lock allora il w_lock non viene concesso (non si può andare a scrivere dove qualcun altro stà leggendo), se su tale risorsa è attivo un altro w_lock il w_lock non viene concesso (non si può andare a scrivere dove qualcun altro stà scrivendo).
Se viene richiesto un unlock e lo stato della risorsa risulta essere libero avviene un errore (no si può liberare qualcosa di gia libero), se viene richiesto su una risorsa su cui è presente un r_lock dipende (solo se non ci sono altre transazioni in lettura su quella risorsa) mentre se viene richiesto su una risorsa dove c'è un w_lock viene concesso e la risorsa viene liberata.
Si può notare che i 3 casi in cui viene negata un'operaione di lock ed unlock rappresentano i confliti che si possono presentare.
Per avere la garanzia che le transazioni seguano no schedule serializzabile è necessario porre una restrizione sull'ordinamento delle richieste di lock che prende il nome di locking a 2 fasi e cioè: UNA TRANSAZIONE, DOPO AVER RILASCIATO UN LOCK, NON PUO' ACQUISTARNE ALTRI.
La diretta conseguenza di tale restrizione è che si vengono a creare due fasi distinte:
1) FASE CRESCENTE: è la prima fase in cui la transazione acquisisce i lock per le risorse a cui dovrà accedere.
2) FASE CALANTE: è la seconda fase in cui i lock acquisiti nella prima fase vengono rilasciati.
*NB: un eventuale passaggio da r_lock a w_lock costituisce un incremnto del livello del lock sulla risorsa e fa parte della fase crescente.
Nel mezzo delle due fasi il DBMS esegue le varie operazioni sui dati.
Un sistema il cui lock manager rispetta la politica appena descritta è quindi un sistema transazionale caratterizzato dalla serializzabilità delle sue transazioni e quindi ogni schedule che rispetti i requisiti del lock a 2 fasi risulta essere anche uno schedule serializzabile rispetto alla conflict equivalenza
tra pochissimi giorni dovrò sostenere un orale relativo ai database...in particolar modo la teoria tratterà argomenti come la teoria della gestione della concorrenza...tra l'altro devo portare anche una tesina e pensavo di farla su questo argomento (è il più complesso e per questo motivo avendo poco tempo è quello su cui ho studiato di più).
Per gli studenti di Tor Vergata...evitate di fare copia e incolla sulla vostra tesina altrimenti portiamo 2 tesine uguali e non sarebbe carino... :D
Quì di seguito posto le mie idee su quello che ho capito...potete dirmi se ci sono imperfezioni\errori\incomprensioni? Dovendoci fare una tesina preferirei evitare di scrivere michiate...poi magari può essere anche stimolante per qualcun altro :)
DEFINIZIONE DI TRANSAZIONE: E' l'unità di lavoro fondamentale svolta da un'applicazione e viene fatto riferimento specialmente alle operazioni che modificano il contenuto del DB. Ogni transazione è specificata racchiudendo la sequenza di operazioni che la compongono dentro una coppia di istruzioni che ne specificano l'inizio e la fine, queste istruzioni sono:
1) START: dice dove inizia la transazione
2) COMMIT: richiede una conclusione positiva della transazione e richiede che tutti gli aggiornamenti siano salvati sul DB (proprietà di persistenza appartenente alle proprietà ACID)
o ROLBACK: in alcuni casi si possono verificare delle condizione che portano all'annullamento degli aggiornamenti (tramite operazioni di undo nel file di log del controllore dell'affidabilità del DBMS).
Generalmente le transazioni sono concorrenti, ovvero più transazioni possono voler accedere in letura o scrittura agli stessi dati in maniera contemporanea.
Potenzialmente il numero di transazioni che arrivano ad un DBMS possono essere anche dell'ordine di migliaia di transazioni per secondo, ciò rende impossibile pensare ad una loro esecuzione seriale, da quì deriva l'esigenza di trattarle in modo concorrente.
Un'eventuale errata gestione della concorrenza potrebbe portare alle famose anomalie (che non le descrivo per non dilungarmi troppo...sono stranote e casomai le aggiungo sulla tesina per fare spessore): PERDITA DI AGGIORNAMENTO, LETTURA SPORCA, LETTURE INCONSISTENTI, AGGIORNAMENTI FANTASMA, INSERIMENTO FANTASMA.
A grandi linee si può affermare che il controllore della concorrenza è il componente di un DBMS che riceve le ricieste di accesso ai dati e decide se accettarle o rifiutarle
Da quì l'esigenza di trattare con un approccio scientifico la teoria del controllo di concorrenza poichè non si può lasciare al caso l'esecuzione delle varie azioni all'interno di transazioni concorrenti.
Per semplicità possiamo definire una transazione come una sequenza di azioni di LETTURA o di SCRITTURA. Sotto questa assunzione una transazione è un oggetto sintattico di cui si conoscono soltanto le azioni di ingresso ed uscita.
Un esempio di transazione può essere:
t1 = r1(x), r1(y), w1(x), w1(y)
mentre uno SCHEDULE è definito come la sequenza di operazioni presentate da transazioni concorrenti.
Un esempio di schedule può essere:
S1 = r1(x), r2(z), w1(x), w2(z),...
con r1(x) rappresenta la lettura dell'oggetto x da parte della transazione 1 mentre r2(z) rappresenta la letura dell'oggetto z da parte della transazione 2.
Lo scopo del controllore della concorrenza è quindi quello di accettare alcuni schedule e rifiutarne altri in modo da evitare le anomalie sopracitate. Il modulo che gestisce tale funzione viene per questo detto SCHEDULER.
Per lo studio della teoria del controllo di concorrenza si assume per facilità che le transazione che formano un qualsiasi schedule abbiano tutte un esito ovvero terminino tutte con una operazione di COMMIT escoludendo così il caso in cui al posto della commit vi sia un'istruzione di rolback.
Uno schedue di questo tipo si definisce come COMMIT PROIEZIONE e facendo questa assunzione il relativo scheduler non potrà mai rilevare e gestire i casi in cui si verifica l'operazione di LETTURA SPORCA (che prevede un'operazione di ABORT).
Definiamo SCHEDULE SERIALE un qualsiasi schedule in cui le azioni di ogni transazione compaiano in sequenza senza essere inframezzate da azioni di altre transazioni.
Ad esempio il seguente schedule è seriale:
Ho 3 transazioni: t0, t1, t2 e lo schedule seriale:
S= r0(x), r0(y), w0(x), r1(y) w1(y), r1(x), r2(x), w2(y), r2(y)
L'esecuzione di uno schedule a commit proiezione è CORRETTO se e solo se produce lo stesso risultato di uno schedule seriale ed in questo caso si dice che è SERIALIZZABILE.
Quindi lo studio della teoria del controllo di concorrenza si pone come obbiettivo principale quello di riuscire a capire se dato un qualsiasi schedule questo sia serializzabile quindi da accettare, oppure no quindi da rifiutare.
Per rispondere a questa domanda sono state trovate varie soluzioni, alcune valide solo dal punto di vista teorico ma non applicabili praticamente poichè troppo costose dal punto di vista algoritmico, quì di seguito ne saranno presentate 3:
1) DEFINIZIONE DI VIEW EQUIVALENZA: Viene definita un'operazione che lega COPPIE DI OPERAZIONE di lettura e scrittura nel seguente modo:
1) Un'operazione di lettura r_i(x) LEGGE DA UN'OPERAZIONE DI SCRITTURA w_j(x) se e solo se w_j(x) precede r_i(x) e non vi è alcuna operazione di scrittura w_k(x) nel mezzo.
2) Un'operazione di scrittura w_i(x) si dice SCRITTURA FINALE se è l'ultima operazione di scrittura che agisce sull'oggetto x nello schedule considerato.
Definita questa relazione si dice che 2 schedule sono VIEW EQUIVALENTI se entrambi possiedono la stessa relazione "LEGGE DA" e la stessa scrittura finale
Per esempio considerando questi 2 schedule possiamo affermare che sono view equivalenti:
S1: w0(x), r2(x), r1(x), w2(x), w2(z)
S2: w0(x), r1(x), r2(x), w2(x), w2(z)
perchè entrambi hanno la stessa scrittura finale w2(z) e poichè possiedono la stessa relazione "LEGGE DA" in quanto in S1 la transazione 2 legge da x dopo che la transazione 0 ha scritto x e la stessa cosa accade nello schedule S2.
Uno schedule si definisce VIEW SERIALIZABBILE se è VIEW EQUIVALENTE ad uno scedule seriale.
Ad esempio questo schedule è view serializzabile:
S1: w0(x), r1(x), w1(x), r2(x), w1(z)
in quanto è view equivalente a questo schedule seriale:
S2: w0(x), r1(x), w1(x), w1(z), r2(x) (è seriale)
come prima si nota che hanno la stessa scrittua finale w1(z) e la stessa relazione "LEGGE DA".
E' facilmente dimostrabile che schedule che generano le anomalie di cui ho parlato in precedenza non sono mai serializzaili.
Uno schedule potrebbe utilizzare questa tecnica per determinare se uno schedule è view equivalente ad un qualsiasi schedule seriale, tuttavia trattandosi di un problema NP-HARD (può esistere un numero esponenziale di schedule seriali determinato da tutte le permutazioni delle transazioni con cui confrontare lo schedule dato) tale tecnica non risulta applicabile per scopi pratici.
2) DEFINIZIONE DI CONFLICT EQUIVALENZA:
Tale tecnica si basa sulla definizione di CONFLITTO, cioè: Date due azioni a_i ed a_j, con i diverso da j, si dice che a_i è in conflitto con a_j se esse operano sullo stesso oggetto e se almeno una di esse è un'azione di scrittura. Quindi avremo i seguenti casi di conflitto:
1) CONFLITTI LETTURA-SCRITTURA: RW o WR
2) CONFLITTI SCRITTURA-SCRITTURA: WW
Uno schedule S_i è CONFLICT EQUIVALENTE ad un altro schedule S_j se i 2 schedule presentano le stesse operazioni ed ogni coppia di operazioni in conflitto è nelo stesso ordine nei due schedule.
Ad esempio i seguenti due schedule sono conflict equivalenti:
S1: w0(x), r1(x), w0(z), r1(z), r2(x), r3(z), w3(z), w1(x)
S2; w0(x), w0(z), r1(x), r2(x), r1(z), w1(x), r3(z), w3(z)
Perchè contengono le stesse operazioni e l'ordine dei conflitti è lo stesso. Ad esempio sia in S1 che in S2 il primo conflitto che si verifica è quello tra w0(x) ed r1(x).
Si nota che l'insieme degli schedule conflict serializzabili è contenuto propriamente nell'insieme degli schedule view serializzabile quindi la conflict serializzabilità è una condizione sufficiente (ma non necessaria) per la view equivalenza.
Esiste un algoritmo per determinare se uno schedule è CONFLICT SERIALIZZABILE (cioè se uno schedule è conflict equivalente ad uno schedule seriale) e tale algoritmo si basa sull'analisi del GRAFO DEI CONFLITTI.
Il GRAFO DEI CONFLITTI viene costruito facendo corrispondere uno specifico nodo ad ogni transazione che compare nello schedule di partenza. Si traccia un arco orientato dal nodo t_i al nodo t_j se esiste almeno un conflitto tra un'azione a_i della transazione t_i ed un'azione a_j appartenente alla transazione t_j.
Dopo aver così costruito il grafo dei conflitti, se tale grafo è ACICLICO allora lo schedule di partenza è CONFLICT EQUIVALENTE AD UNO SCHEDULE SERIALE poichè il grafo non presentando cicli al suo interno definirà un ORDINAMENTO TOPOLOGICO DEI NODI che porterà facilmente alla costruzione del corrispondente schedule seriale.
Anche se l'analisi della ciclicità di un grafo ha una complessità lineare rispetto alla dimensioni del grafo stesso l'uso di tale tecnica risulta ancora troppo onerosa in termini temporali e di risorse richieste. Inoltre tale tecnica risulta assolutamente inaccettabile in un contesto di database distribuito poichè il grafo dovrebbe essere ricostrutio a partire da archi che vengono riconosciuti sui diversi server del sistema distribuito. Per questi motivi anche questa tecnica rimane solamente una soluzione teorica che non ha alcuna applicazione pratica all'interno dei DBMS.
DEFINIZIONE DI LOCKING A 2 FASI: Si tratta della tecnica più nota utilizzata nei DBMS per risolvere il problema della gestione delle transazioni concorrenti e sfrutta un'intuizione molto semplice cioè di PROTEGGERE TUTTE LE OPERAZIONI DI LETTURA E SCRITTURA mediante le seguenti primitive:
1) r_lock: Protegge le operazioni di lettura
2) w_lock: Protegge le operazioni di scrittura
3) unlock: Toglie il lock da un'operazione di lettura o di scrittura.
Lo scheduler viene detto LOCK MANAGER in quanto il suo compito risulta essere quello di lockare ed unlockare le risorse in modo appropriato rispettando i seguenti semplici vincoli:
1) LOCK CONDIVISO: Ogni operazione di lettura deve essere preceduta dall'invocazione della primitiva r_lock sulla risorse a cui si vuole accedere in lettura e seguida da una unlock. Su un dato a cui si accede in lettura possono essere attivi contemporaneamente più r_lock e per questo si dice lock condiviso.
2) LOCK ESCLUSIVO: Ogni operazione di scrittura deve essere preceduta dall'invocazione della primitiva w_lock e deve essere seguita da una unlock. Su un dato a cui una transazione accede in scrittura non possono essere attivi altri w_lock, ciò significa che solo una transazione per volta può scrivere su di una certa risorse e per questo prende il nome di lock esclusivo.
Il gestore della concorrenza riceve le richieste di lock da parte delle varie transazioni e tramite una TABELLA DEI CONFLITTI determina se concedere o meno il lock della risorsa a tale transazione.
Le politiche in base a cui la tabella dei conflitti permette al gestore della concorrenza se concedere o meno il lock della risorsa richiesto sono le seguenti:
Se viene richiesto un r_lock per una determinata risorsa succede così: se la risorsa è completamente libera, viene concesso l'r_lock, se ci sono già attivi altri r_lock di altre transazioni su tale risorsa viene comunque concesso (più transazioni possono leggere contemporaneamente la stessa risorsa), se è attivo un w_lock su tale risorsa allora non viene concesso l'r_lock.
Se viene richiesto un w_lock e lo stato della risorsa è completamente libero, allora il w_lock viene concesso, se su tale risorsa è già attivo uno o più r_lock allora il w_lock non viene concesso (non si può andare a scrivere dove qualcun altro stà leggendo), se su tale risorsa è attivo un altro w_lock il w_lock non viene concesso (non si può andare a scrivere dove qualcun altro stà scrivendo).
Se viene richiesto un unlock e lo stato della risorsa risulta essere libero avviene un errore (no si può liberare qualcosa di gia libero), se viene richiesto su una risorsa su cui è presente un r_lock dipende (solo se non ci sono altre transazioni in lettura su quella risorsa) mentre se viene richiesto su una risorsa dove c'è un w_lock viene concesso e la risorsa viene liberata.
Si può notare che i 3 casi in cui viene negata un'operaione di lock ed unlock rappresentano i confliti che si possono presentare.
Per avere la garanzia che le transazioni seguano no schedule serializzabile è necessario porre una restrizione sull'ordinamento delle richieste di lock che prende il nome di locking a 2 fasi e cioè: UNA TRANSAZIONE, DOPO AVER RILASCIATO UN LOCK, NON PUO' ACQUISTARNE ALTRI.
La diretta conseguenza di tale restrizione è che si vengono a creare due fasi distinte:
1) FASE CRESCENTE: è la prima fase in cui la transazione acquisisce i lock per le risorse a cui dovrà accedere.
2) FASE CALANTE: è la seconda fase in cui i lock acquisiti nella prima fase vengono rilasciati.
*NB: un eventuale passaggio da r_lock a w_lock costituisce un incremnto del livello del lock sulla risorsa e fa parte della fase crescente.
Nel mezzo delle due fasi il DBMS esegue le varie operazioni sui dati.
Un sistema il cui lock manager rispetta la politica appena descritta è quindi un sistema transazionale caratterizzato dalla serializzabilità delle sue transazioni e quindi ogni schedule che rispetti i requisiti del lock a 2 fasi risulta essere anche uno schedule serializzabile rispetto alla conflict equivalenza