concurrencia

Departamento de Lenguajes y Sistemas Informáticos
Avda Reina Mercedes s/n. 41012 Sevilla
Tlf/Fax 954 557 139 E-mail lsi@lsi.us.es www.lsi.us.es

Diseño de Bases de Datos
Concurrencia

Sevilla, octubre 2004
V 2004.02.1

E.T.S. Ingeniería
Informática

Diseño de Bases de Datos

Concurrencia

Sevilla, octubre 2004, V 2004.02.1

1

INTRODUCCIÓN AL PROBLEMA.........................................................................................................................................3

1.1
1.2
2

EJECUCIONES LIBRES DE CONFLICTOS...........................................................................................................................4

2.1
2.2
2.3
3

CONSISTENCIA DE LA BD...................................................................................................... 3
PROBLEMAS DE CONCURRENCIA ........................................................................................... 3
DEFINICIONES ...................................................................................................................... 4
PLANES SERIALIZABLES......................................................................................................... 4
RELACIÓN DE PRECEDENCIA ENTRE TRANSACCIONES. ........................................................ 5

PROTOCOLO DE BLOQUEO EN DOS-FASES (TWO-PHASE LOCKING PROTOCOL)..................................................6

3.1
ESTRUCTURAS DE DATOS ....................................................................................................... 6
3.2DEFINICIONES ...................................................................................................................... 6
3.3
ALGORITMO DE BLOQUEO EN DOS-FASES .............................................................................. 7
3.3.1 Corrección de algoritmo......................................................................................................................... 93.4
EL ABRAZO MORTAL (DEADLOCK) ....................................................................................... 10
3.4.1 Concepto de abrazo mortal ................................................................................................................. 10
3.4.2 Tratamiento de situaciones de abrazo mortal................................................................................... 10
4

ALGORITMOS DE ORDENACIÓN POR TIMESTAMP...................................................................................................... 13

4.1
4.2
4.3
4.4
5

DEFINICIONES .................................................................................................................... 13
ALGORITMOS DE ORDENACIÓN POR TIMESTAMP TOTAL..................................................... 13
ALGORITMOS DE ORDENACIÓN POR TIMESTAMP PARCIAL................................................... 14
ALGORITMOS DE ORDENACIÓN POR TIMESTAMP MULTIVERSIÓN. ...................................... 15

ALGORITMOS OPTIMISTAS................................................................................................................................................. 17Pág. 2 de 18

Diseño de Bases de Datos

Concurrencia

Sevilla, octubre 2004, V 2004.02.1

1 Introducción al problema
1.1

Consistencia de la BD

Un esquema de BD incluye la descripción de los datos y las restricciones de integridad. Las restricciones de
integridad (RI) son consistentes en sí mismas si no incluyen contradicciones desde el punto de vista
semántico. Un estado de la BDes consistente si las RI son consistentes en sí mismas y dicho estado no
viola las RI (“satisface las RI”: E=RI(E))

1.2 Problemas de concurrencia
El propósito del control de concurrencia es mantener la consistencia de la BD cuando ésta es actualizada
por múltiples usuarios. Existen casos en los que las transacciones ejecutadas aisladamente originan nuevos
estados consistentes, sin...