PDF de programación - Detección de Candados Mortales en Base de Datos utilizando Redes de Petri

CENTRO de INVESTIGACIÓN
y de ESTUDIOS AVANZADOS

del IPN



DEPARTAMENTO DE INGENIERIA ELECTRICA

SECCION DE COMPUTACION



Detección de Candados Mortales en Base de Datos

utilizando Redes de Petri



Tesis que Presenta el:

Ing. José de Jesús Trujillo Ferrara

para obtener el grado de Maestro en Ciencias
en la especialidad de Ingeniería Eléctrica

Opción Computación

Director de la tesis

Dra. Xiaoou Li Zhang



México, D.F.



Mayo de 2004

Índice general

. Agradecimientos

. Resumen

. Abstract

1

3

5

1. Introducción

7
1.1. Planteamiento del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2. Estado del Arte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3. Motivación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4. Descripción del trabajo

2. Introducción a Base de Datos y Candados Mortales

21
2.1. Manejadores de base de datos.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2. Modelo entidad-relación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3. Estructura general de un sistema de base de datos.
. . . . . . . . . . . . . . . . . . . 24
2.4. Lenguaje SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5. Transacciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.6. Control de concurrencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.6.1. Teoría de la seriabilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.6.2. Algoritmo basado con el mecanismo de espera . . . . . . . . . . . . . . . . . . 31
2.6.3. Protocolo de dos fases (2PL) para candados.
. . . . . . . . . . . . . . . . . . 32
2.6.4. Algoritmo basado con el mecanismo de timestamp. . . . . . . . . . . . . . . . 32

ii

ÍNDICE GENERAL

2.6.5. Algoritmo basado con el mecanismo de rollback.

. . . . . . . . . . . . . . . . 33
2.7. Candados mortales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
. . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.7.1. Modelos de candados mortales.
2.7.2. Prevención de candados mortales . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.7.3. Detección y recuperación de candados mortales . . . . . . . . . . . . . . . . . 36
2.8. Manejo de candados en DBMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.8.1. MySQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.8.2. PostgreSQL.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.8.3. Oracle.
2.8.4. Borland InterbaseTM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.9. Comentarios finales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3. Fundamentos de PN

45
3.1. Definiciones Preliminares
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2. Propiedades de PN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.2.1. Vida.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.2.2. Alcanzabilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.3. Análisis de PN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.3.1. Árbol de alcanzabilidad. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.3.2. Matriz de incidencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.4. Extensiones de las PN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.5. Comentarios finales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

4. Análisis de candados mortales con PN

65
4.1. Sintaxis para modelar transacciones
. . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.2. Modelación de transacciones con PN . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
Implementación del editor de redes de Petri. . . . . . . . . . . . . . . . . . . . . . . . 70
4.3.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.3.1. Variables.
4.3.2. Algoritmos.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.4. Detección de candados mortales con Matriz de incidencia . . . . . . . . . . . . . . . 77
4.4.1. Análisis de la estructura de una PN con matriz de incidencia . . . . . . . . . 77

ÍNDICE GENERAL

iii

4.5. Ejemplos Prácticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.6. Comentarios finales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

5. Plataforma de desarrollo

89
5.1. Planteamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.2. Arquitectura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.3. Diseño . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.4. Las clases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.4.1. La clase Editor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.4.2. La clase RedPetri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.4.3. La clase Figura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

5.5. Uso de TRANSimul

6. Conclusiones

105
6.1. Resultados obtenidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6.2. Trabajo futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

. Bibliografía

109

iv

ÍNDICE GENERAL

Agradecimientos

Al CONACYT por apoyarme con la beca de maestría y al CINVESTAV en general.

2

ÍNDICE GENERAL

Resumen

Imaginemos que tenemos un grupo de transacciones tal que cada transacción está esperando
que otra transacción del mismo grupo libere un recurso compartido. A esta situación se le denomina
candado mortal; este problema se puede tratar de diferentes formas: la detección, el análisis y la
recuperación [6].

Para la detección se trabajará con redes de Petri para modelar y describir gráficamente el
comportamiento de un grupo de "n"transacciones que estén compitiendo por un recurso compartido
en la base de datos. El grafico generado se analizará para determinar si algunas transacciones se
encuentran esperando a que se libere un recurso o, a que una transacción finalice.

Si se detecta un candado mortal, se tendrá que brindar los recursos que necesita a una transac-
ción para que termine su ejecución, dejando bloqueadas las demás transacciones; al terminar la
primera transacción se debe poner en ejecución a las restantes.

En la fase de recuperación se tiene que estar en constante revisión el comportamiento general
de las transacciones y los recursos de la base de datos; con la finalidad de generar otro grafico y
realizar el análisis de detección, en este caso se tendrá que bloquear la ejecución de una y liberar
los recursos que esté utilizando.

Para esta tesis se trabajo con un conjunto de transacciones que se deseen poner en ejecución
concurrentemente. Con la finalidad de evitar candados mortales. Si se detecta que este conjunto de
transacciones tienen conflictos se optará por reiniciar una transacción.

4

ÍNDICE GENERAL

Abstract

In this thesis, we focus on database transaction deadlock detection. Transaction dependencies
are modeled with Petri nets, then deadlocks of transactions are detected based on the Petri net
model. The main results are:

1. Analyze dependency relation between database transactions.
2. Model transaction dependencies with Petri nets. A set of transactions can be converted into

a Petri net model. A conversion algorithm is developed.

3. Use the incidence matrix techniques of Petri net model to detect deadlock. A deadlock

detection algorithm is developed.

4. Implementation of TRANSimul (TRANSaction Simulation).

4.1 TRANSimul interface design and implementation
4.2 implementation of the conversion algorithm
4.3 implementation of the deadlock detection algorithm
4.4 Experiments on TRANSimul with different examples

6

ÍNDICE GENERAL

Capítulo 1

Introducción

Una colección de varias operaciones (consultas, actualizaciones, etc.) en una base de datos
son llamadas transacciones. La base de datos debe asegurar que los datos sean íntegros y que las
transacciones se ejecuten satisfactoriamente. Para esto las transacciones deben tener las siguientes
propiedades: [2]

Atomicidad: Se deben ejecutar todas las operaciones de la transacción o ninguna.

Consistencia: La ejecución de una instrucción es aislada y preserva la consistencia en la base
de datos.

Aislamiento: Varias transacciones se pueden ejecutar concurrentemente; el sistema debe
garantizar que todas se ejecuten satisfactoriamente.

Durabilidad: Después que una transacción termine satisfactoriamente, los cambios hechos
por ésta deben persistir en la base de datos.

La transacción en una base de datos está compuesta por dos operaciones:

leer(x), se transfiere el dato x de la base de datos a un almacenamiento local (buffer) para la
operación leer.

escribir(x ), se transfiere el dato x del buffer local para escribirlos en la base de datos.

8

Introducción

Usualmente los sistemas de base de datos permiten múltiples transacciones, es decir, que se
pueden ejecutar concurrentemente. Esto nos brinda mayor eficiencia pero, si no se controla ade-
cuadamente, puede causar problemas en la consistencia de los datos. Cuando un grupo de transac-
ciones se van a ejecutar, es necesario generar un