Plan de ejecución es completo



Descargar 41.06 Kb.
Fecha de conversión28.12.2018
Tamaño41.06 Kb.
Resumen de Términos Importantes

(Transacciones y Control de Concurrencia)

  • Un plan de ejecución es completo si:

  1. Las operaciones del plan son las contenidas en las Ti además de las operaciones de confirmar y/o abortar como última operación de cada Ti.

  2. Para toda operación dentro de una Ti, su orden de aparición en el plan debe ser el mismo que aparece en la Ti

  3. Para cualesquiera de las operaciones en conflicto, una de ellas debe aparecer antes que la otra en el plan.

  4. Un plan completo terminado no contendrá Ti activas.

  • Planes recuperables: Un plan P es recuperable si ninguna Ti de P se confirma antes de haberse confirmado todas las Tj que han escrito un elemento que Ti lee. Una Ti lee de Tj en P si Tj escribe primero algún elemento X y luego Ti lo lee.

Ejemplo: P1 es un plan completo y recuperable. P4: L1(X), E1(X), L2(X), L1(Y), E2(X), C2, A1 es un plan completo no recuperable.

  • Plan que evita la reversión en cascada: es un plan P donde toda Ti sólo lee elementos escritos por las Ti confirmadas.

Ejemplo: P5: L1(X), E1(X), L2(X), L1(Y), E2(X), E1(Y), A1 es un plan completo recuperable que no evita la reversión en cascada, en cambio P6: L1(X), E1(X), L1(Y), E1(Y), L2(X), E2(X), A1 es un plan completo recuperable que evita la reversión en cascada.

  • Plan estricto: cuando las Ti no pueden leer ni escribir un elemento X en tanto no se haya confirmado o abortado la última Ti que escribió X. Un plan estricto es también recuperable y evita la reversión en cascada.

Ejemplo: P7: E1(X, 5), E2(X, 8), A1 no es estricto, pero P8: E1(X, 5), A1, E2(X, 8) si es estricto.

  • Transacciones de dos fases: Es una T que no hace bloquear luego de hacer un desbloquear. Una T dos fases debe hacer todos los bloqueos a sus gránulas antes de comenzar a desbloquear.

Reglas de uso de bloquear/desbloquear: Deben ser seguidas por cualquier T en un sistema de bases de datos (SBD):

  1. Toda T debe bloquear con los modos de operación correctos sobre g antes de ejecutar alguna operación sobre ella.

  2. Toda T debe hacer desbloquear sobre g luego de la ejecución de la operación.

  3. Cualquier T no puede hacer bloquear luego de haber hecho desbloquear.

Problemas:


  1. Interbloqueo o abrazo mortal: Es la situación en la que las gránulas han sido bloqueadas en un orden tal que un grupo de T verifican las dos propiedades siguientes:

  1. Cada T del grupo está en espera de una g

  2. La ejecución supuesta de todas las otras T que no pertenecen al grupo, no permite desbloquear una de las T del grupo.

T1

T2

Bloquear(gi, actualización)

 

 

Bloquear(gj, actualización)

Bloquear(gj, actualización)

 

espera

Bloquear(gi, consulta protegida)

 

espera

Grafo de esperas: es un grafo G = ( T, ES ) donde T son las transacciones concurrentes que comparten las gránulas g1, g2, ..., gm y ES es la relación espera definida por: Tp espera a Tq si y sólo sí Tp espera el bloqueo de gi mientras que gi ha sido bloqueada por otra Tq.

T1 espera por T2 que a su vez espera por T3



Teorema: Existe interbloqueo si y sólo sí el grafo de esperas contiene un circuito.

Relación entre el grafo de precedencia y el de esperas: Si Ti espera por Tj implica que Tj bloqueó g y Ti desea bloquear g en modo incompatible, por lo cual Tj efectuará la operación antes de Ti. Por lo tanto Ti y Tj son incompatibles y no permutables lo que equivale a que Ti > Tj (Ti espera por Tj). Si el grafo de esperas tiene un circuito, el grafo de precedencia también lo tendrá.

El problema de interbloqueo es irresoluble, si se desea evitarlo, la solución es detectarlo o prevenirlo.



Método de detección de interbloqueo: Se deduce del algoritmo de detección de circuitos en el grafo de esperas.

Métodos de prevención de interbloqueo:

  1. Esperar-morir: Ti pide bloquear g que está bloqueada por Tj en modo incompatible.




esperarMorir(Ti, Tj)

1

2


Si ( i < j ) entonces

Ti espera

sino

Ti muere
re-iniciar Ti con la misma etiqueta



fsi
regrese

-i, j: Etiquetas de las transacciones.

Toda T sólo puede esperar T más jóvenes que ella.


Una T que muere tarde o temprano llegará a ser la más vieja y no morirá.
La T más joven se aborta y se re-inicia luego.




  1. Herir-esperar: Ti pide bloquear g que está bloqueada por Tj en modo incompatible.




herirEsperar(Ti, Tj)

1

2


Si ( i < j ) entonces

Tj muere
re-iniciar Tj con su misma etiqueta

sino

Ti espera



fsi
regrese

-i, j: Etiquetas de las transacciones.

La T más joven puede esperar que la más vieja termine, pero la T más vieja desalojará a la más joven haciendo que ésta aborte.






  1. Espera cautelosa: Ti pide bloquear g que está bloqueada por Tj en modo incompatible.




esperaCautelosa(Ti, Tj)

1
2

Si ( Tj no está esperando ) entonces

Ti espera

sino

Ti muere (se aborta Ti )



fsi
regrese

-i, j: Etiquetas de las transacciones.

Reduce el número de T re-iniciadas y está libre de interbloqueos.






  1. Uso de tiempos predefinidos: Si una T espera por un lapso de tiempo mayor a una cota prefijada, se considera que está en abrazo mortal y se aborta, sin verificar si hay realmente tal interbloqueo.

  1. Espera indefinida: Cuando una T se encuentra detenida (en espera) mientras las otras continúan su ejecución. Varias Ts coinciden efectuando operaciones compatibles contra una Tk que desea hacer una operación incompatible.

Solución: Tener un esquema de espera justo que utiliza una cola de peticiones de bloqueo de sus gránulas según el orden de llegada de las Ts.

  1. Inanición: Si los algoritmos que resuelven el interbloqueo seleccionan una y otra vez la misma víctima T. Los algoritmos de esperar-morir y herir-esperar evitan la inanición.

  2. Fantasmas: Cuando se inserta en la BD y la T no puede ser tratada en el orden lógico.



T1

T2

Listar la tabla Pasajero del vuelo 100

Inserta en Pasajero (Fantasma, 100, 14C)

Listar la tabla Vuelo

Incrementa el Vuelo.nroDePasajeros




Pasajero

nombre

nroDeVuelo

puesto

 

Manuel Sierra

100

10C

José Méndez

100

12B

Rodrigo Riera

100

12C

Fantasma

100

14C




Vuelo

nroDeVuelo

nroDePasajeros

 

100

4

P = L1( Pasajero ), E2 ( Pasajero ), E2 ( Vuelo ), L1( Vuelo )

T1 ve 3 pasajeros en la lista y luego ve que el número de pasajeros es 4.

Two-Phase Locking


This approach [ Gray CACM ] locks data and assumes that a transaction is divided into a growing phase, in which locks are only acquired, and a shrinking phase, in which locks are only released. A transaction that tries to lock data that has been locked is forced to wait and may deadlock. The use of locks is illustrated in Figure 2.


Strict two-phase locking

From Wikipedia, the free encyclopedia


Jump to: navigation, search

In computer science, strict two-phase locking (Strict 2PL) is a locking method used in concurrent systems.

The two rules of Strict 2PL are:


  1. If a transaction T wants to read/write an object, it must request a shared/exclusive lock on the object.

  2. All exclusive locks held by transaction T are released when T commits (and not before).

Here is an example of Strict 2PL in action with interleaved actions.

or in text form:

T1: S(A), R(A); T2: S(A), R(A), X(B), R(B), W(B), Commit; T1: X(C), R(C), W(C), Commit

where


  • S(O) is a shared lock action on an object O

  • X(O) is an exclusive lock action on an object O

  • R(O) is a read action on an object O

  • W(O) is a write action on an object O

Strict 2PL prevents transactions reading uncommitted data, overwriting uncommitted data, and unrepeatable reads. Thus, it prevents cascading rollbacks, since eXclusive locks (for write privileges) must be held until a transaction commits.


[edit] Strict 2PL does not guarantee a deadlock-free schedule


Avoiding deadlocks can be important in real time systems, and may additionally be difficult to enforce in distributed data bases, or fault tolerant systems with multiple redundancy.

A deadlocked schedule allowed under Strict 2PL:



Text: T1: X(A) T2:X(B) T1:X(B) T2: X(A)

T1 is waiting for T2's lock on B to be released, while T2 is waiting for T1's lock on A to be released. These transactions cannot proceed and both are deadlocked.

There is no general solution to the problem of deadlocks in computing systems, so they must be anticipated and dealt with accordingly. Nonetheless, several solutions such as the Banker's algorithm or the imposition of a partial ordering on lock acquisition exist for avoiding deadlocks under certain conditions.


Even more strict than strict two-phase locking is rigorous two-phase locking, in which transactions can be serialized by the order in which they commit. Under rigorous 2PL, all locks (shared and exclusive) must be held until a transaction commits. Most database systems use strict 2PL.


Non-strict two-phase locking

From Wikipedia, the free encyclopedia


Jump to: navigation, search

In computer science, non-strict two-phase locking, also 2PL, is a locking method used in concurrent systems.

The rules for 2PL are similar to those of Strict 2PL:


  1. If a transaction T wants to read/write an object, it must request a shared/exclusive lock on the object.

  2. A transaction cannot request additional locks on any object once it releases any lock, and it can release locks at any time (not only at commit time as in Strict 2PL).

So, every transaction has a growing phase (it acquires locks) and a shrinking phase (it releases locks). 2PL allows only conflict serializable schedules, but does not guarantee freedom of deadlock.

Una visión de SQL Anywhere

Serializable schedules


To process transactions concurrently, the database server must execute some component statements of one transaction, then some from other transactions, before continuing to process further operations from the first. The order in which the component operations of the various transactions are interleaved is called the schedule.

Applying transactions concurrently in this manner can result in many possible outcomes, including the three particular inconsistencies described in the previous section. Sometimes, the final state of the database also could have been achieved had the transactions been executed sequentially, meaning that one transaction was always completed in its entirety before the next was started. A schedule is called serializable whenever executing the transactions sequentially, in some order, could have left the database in the same state as the actual schedule.

For more information about how Adaptive Server Anywhere handles serialization, see Two-phase locking.

Serializability is the commonly accepted criterion for correctness. A serializable schedule is accepted as correct because the database is not influenced by the concurrent execution of the transactions.

The isolation level affects a transaction's serializability. At isolation level 3, all schedules are serializable. The default setting is 0.


Serializable means that concurrency has added no effect 

Even when transactions are executed sequentially, the final state of the database can depend upon the order in which these transactions are executed. For example, if one transaction sets a particular cell to the value 5 and another sets it to the number 6, then the final value of the cell is determined by which transaction executes last.

Knowing a schedule is serializable does not settle which order transactions would best be executed, but rather states that concurrency has added no effect. Outcomes which may be achieved by executing the set of transactions sequentially in some order are all assumed correct.


Unserializable schedules introduce inconsistencies 

The inconsistencies introduced in Typical types of inconsistency are typical of the types of problems that appear when the schedule is not serializable. In each case, the inconsistency appeared because the statements were interleaved in such a way as to produce a result that would not be possible if all transactions were executed sequentially. For example, a dirty read can only occur if one transaction can select rows while another transaction is in the middle of inserting or updating data in the same row.

Two-phase locking


Often, the general information about locking provided in the earlier sections will suffice to meet your needs. There are times, however, when you may benefit from more knowledge of what goes on inside the database server when you perform basic types of operations. This knowledge will provide you with a better basis from which to understand and predict potential problems that users of your database may encounter.

Two-phase locking is important in the context of ensuring that schedules are serializable. The two-phase locking protocol specifies a procedure each transaction follows.

This protocol is important because, if observed by all transactions, it will guarantee a serializable, and thus correct, schedule. It may also help you understand why some methods of locking permit some types of inconsistencies.

The two-phase locking protocol 

  1. Before operating on any row, a transaction must acquire a lock on that row.

  2. After releasing a lock, a transaction must never acquire any more locks.

In practice, a transaction normally holds locks until it terminates with either a COMMIT or ROLLBACK statement. Releasing locks before the end of the transaction disallows the operation of rolling back the changes whenever doing so would necessitate operating on rows to return them to an earlier state.

The two-phase locking protocol allows the statement of the following important theorem:


The two-phase locking theorem 

If all transactions obey the two-phase locking protocol, then all possible interleaved schedules are serializable.

In other words, if all transactions follow the two-phase locking protocol, then none of the inconsistencies mentioned above are possible.

This protocol defines the operations necessary to ensure complete consistency of your data, but you may decide that some types of inconsistencies are permissible during some operations on your database. Eliminating all inconsistency often means reducing the efficiency of your database.



Write locks are placed on modified, inserted, and deleted rows regardless of isolation level. They are always held until commit and rollback.





La base de datos está protegida por derechos de autor ©bazica.org 2016
enviar mensaje

    Página principal