Bloqueo de dos fases

Ir a: navegación, búsqueda de
Este artículo es sobre control de concurrencia. Por consenso se comprometen en una transacción distribuida, ver Protocolo de dos fases.

En bases de datos y procesamiento de transacciones, bloqueo de dos fases (2PL) es un control de concurrencia método que garantiza serializabilidad.[1][2] También es el nombre del conjunto resultante de transacciones de bases de datos horarios (historias). Utiliza el protocolo cerraduras, aplicado por una transacción a datos, que pueden bloquear (interpretados como señales para parar) otras transacciones de acceso a los mismos datos durante la vida de la transacción.

Por el 2PL protocolo cerraduras son aplicadas y eliminadas en dos fases:

  1. Fase de expansión: se adquieren bloqueos y bloqueos no son liberados.
  2. Fase de contracción: los bloqueos son liberados y no se adquieren bloqueos.

Dos tipos de cerraduras son utilizados por el protocolo básico: Compartido y Exclusivo cerraduras. Refinamientos del protocolo básico pueden utilizar más tipos de bloqueo. Uso de cerraduras que bloquean los procesos, 2PL puede ser sujeto a interbloqueos el resultado del bloqueo mutuo de dos o más transacciones.

Contenido

  • 1 Cerraduras de acceso a datos
  • 2 Bloqueo de dos fases y sus casos especiales
    • 2.1 Bloqueo de dos fases
    • 2.2 Estricto bloqueo de dos fases
    • 2.3 Fuerte estricto bloqueo de dos fases
    • 2.4 Resumen: las relaciones entre las clases
  • 3 Interbloqueos en 2PL
  • 4 Véase también
  • 5 Referencias

Cerraduras de acceso a datos

A cerradura es un objeto de sistema asociado a un recurso compartido como un elemento de datos de tipo elemental, una fila en una base de datos o una página de memoria. En una base de datos, un bloqueo en un objeto de base de datos (un bloqueo de acceso a datos) puede necesitar ser adquirida por una transacción antes de acceder al objeto. El uso correcto de las cerraduras impide operaciones indeseadas, incorrectas o inconsistentes en los recursos compartidos por otras transacciones concurrentes. Cuando un objeto de base de datos con un bloqueo existente adquirido por una transacción necesita acceder por otra transacción, la cerradura existente para el objeto y el tipo de acceso prevista son revisadas por el sistema. Si el tipo de cerradura existente no permite a este tipo de acceso concurrente intento específico, la transacción de acceso está bloqueada (según un esquema de acuerdo/predefinido). En la práctica un bloqueo sobre un objeto no bloquea directamente la operación de una transacción sobre el objeto, pero prefiero bloquea esa transacción de adquirir otra cerradura sobre el mismo objeto, debía ser sostenido/propiedad de la transacción antes de realizar esta operación. Por lo tanto, con un mecanismo de bloqueo, bloqueo de operación necesaria es controlado por un esquema bloqueo cerradura apropiada, que indica que bloques de tipo cerradura que Trabe el tipo.

Se utilizan dos tipos principales de bloqueos:

  • Bloqueo de escritura (bloqueo exclusivo) está asociado a un objeto de base de datos de una transacción (terminología: "la transacción bloquea el objeto," o "adquiere el bloqueo por ello") antes de escritura (insertar/modificar/borrar) este objeto.
  • Leer-cerradura (bloqueo compartido) está asociado a un objeto de base de datos de una transacción antes de lectura (recuperar el estado de) este objeto.

Las interacciones comunes entre estos tipos de bloqueo se definen mediante el bloqueo de comportamiento como sigue:

  • Una ya existente bloqueo de escritura en una base de datos objeto bloquea un previsto escribir sobre el mismo objeto (ya solicitados/emitido) por otra transacción mediante el bloqueo de un respectivo bloqueo de escritura de ser adquirida por la otra transacción. El segundo bloqueo de escritura será adquirido y la escritura requerida del objeto llevará a cabo (materializar) después de soltar el bloqueo de escritura existente.
  • A bloqueo de escritura bloquea a un previsto (ya solicitados/emitido) leer por otra transacción mediante el bloqueo de los respectivos leer-cerradura .
  • A leer-cerradura bloquea un previsto escribir por otra transacción mediante el bloqueo de los respectivos bloqueo de escritura .
  • A leer-cerradura No bloquee un previsto leer por otra transacción. El respectivo leer-cerradura para leer la intención es adquirida (compartido con la lectura anterior) inmediatamente después de que se solicita previsto leer, y luego se lee la intención ocurre.

Existen varias variaciones y mejoras de estos tipos de cerradura principal, con variaciones respectivas de bloqueo de comportamiento. Si un primer bloqueo bloquea otra cerradura, se denominan las dos cerraduras incompatible; de lo contrario son las cerraduras compatible. A menudo bloquear tipos de interacciones bloquea se presentan en la literatura técnica por un Tabla de compatibilidad de la cerradura. El siguiente es un ejemplo con los tipos de cerradura común, principales:

Tabla de compatibilidad de la cerradura
Tipo de bloqueo leer-cerradura bloqueo de escritura
leer-cerradura X
bloqueo de escritura X X
X indica incompatibilidad, es decir, un caso de un bloqueo del primer tipo (en la columna izquierda) en un objeto bloquea una cerradura del segundo tipo (en la fila superior) de ser adquirido en el mismo objeto (por otra transacción). Un objeto normalmente tiene una cola de espera operaciones solicitadas (por transacciones) con cerraduras respectivas. La primera cerradura bloqueada para la operación en la cola se adquiere tan pronto como se quita el bloqueo bloqueo existente del objeto, y entonces se ejecuta la operación respectiva. Si una cerradura para la operación en la cola no está bloqueada por cualquier cerradura existente (existencia de múltiples bloqueos compatibles en un mismo objeto es posible simultáneamente) se adquiere inmediatamente.
Comentario: En algunas publicaciones las entradas de la tabla están marcadas simplemente "compatible" o "incompatible", o "Sí" o "no".

Bloqueo de dos fases y sus casos especiales

Bloqueo de dos fases

Según el bloqueo de dos fases Protocolo de una transacción encarga de sus cerraduras en dos fases distintas, consecutivas durante la ejecución de la transacción:

  1. Fase de expansión (también conocido como fase de crecimiento): cerraduras se adquieren y no se lanzan cerraduras (sólo puede aumentar el número de bloqueos).
  2. Fase menguante:: los bloqueos son liberados y no se adquieren bloqueos.

La fase dos de regla de bloqueo puede resumirse como: nunca adquirir un bloqueo después de una cerradura ha sido liberada. El serializabilidad propiedad está garantizado por un calendario con las transacciones que obedezca esta regla.

Normalmente, sin conocimiento explícito en una transacción en la final de la fase-1, se determina con seguridad sólo cuando una transacción tiene proceso completado y cometer solicitada. En este caso todos los bloqueos pueden ser liberados al mismo tiempo (fase-2).

Estricto bloqueo de dos fases

Para cumplir con el protocolo de S2PL una transacción necesita cumplir con 2PL y suelte su escribir (exclusivo) cerraduras sólo después de que ha terminado, es decir, ser comprometido o abortado. Por otro lado leer (compartida) los bloqueos son liberados periódicamente durante la fase 2.

Fuerte estricto bloqueo de dos fases

o Rigurosidad, o Programación rigurosa, o Riguroso bloqueo de dos fases

Para cumplir con fuerte estricto bloqueo de dos fases (SS2PL) el protocolo de bloqueo ambos lanzamientos escribir (exclusivo) y leer (compartida) cerraduras aplicadas por una transacción sólo después de que ha terminado la transacción, es decir, solamente después de tanto completar ejecutando (siendo listo) y convertirse en cualquier comprometido o abortado. Este protocolo también cumple con la normativa S2PL. Una transacción obedeciendo SS2PL puede considerarse como teniendo fase-1 que dura la duración entera de la ejecución de la transacción y no hay fase-2 (o un degenerado fase-2). Así, en realidad queda solamente una fase, y "dos fases" en el nombre parecen todavía ser utilizados debido al desarrollo histórico del concepto de 2PL, y 2PL siendo una super-clase. También se llama la propiedad SS2PL de un programa de Rigurosidad. También es el nombre de la clase de los horarios que esta propiedad, y un calendario de SS2PL también se llama un "riguroso horario". El término "Rigurosidad" es libre del legado innecesario de "dos fases", así como ser independiente de cualquier mecanismo (bloqueo) (en principio que pueden utilizarse otros mecanismos de bloqueo). Mecanismo de bloqueo respectiva de la propiedad se refiere a veces como Riguroso 2PL.

SS2PL es un caso especial de S2PL, es decir, la clase SS2PL de horarios es una subclase de S2PL adecuada (cada horario SS2PL es también un calendario de S2PL, pero S2PL horarios existen que no son SS2PL).

SS2PL ha sido el protocolo de control de concurrencia de elección para la mayoría sistemas de base de datos y utilizados desde sus inicios en la década de 1970. Se ha demostrado para ser un mecanismo eficaz en muchas situaciones y proporciona además Serializabilidad también Rigor (un caso especial de recuperación cascadeless), que es instrumental para la eficiente base de datos recuperacióny también Compromiso ordenando (CO) por participar en entornos distribuidos donde basado en un CO serializabilidad distribuido y serializabilidad global se emplean soluciones. Ser un subconjunto de CO, una implementación eficiente de SS2PL distribuida existe sin un Administrador de bloqueos distribuido (DLM), mientras que los deadlocks distribuidos (véase abajo) se resuelven automáticamente. El hecho de que SS2PL empleadas en los sistemas de base de datos multi asegura serializabilidad global ha sido conocido durante años antes de que el descubrimiento de CO, pero sólo con CO vino la comprensión del papel de un compromiso atómico Protocolo en mantener serializabilidad global, así como la observación de resolución automática de deadlocks distribuidos (véase un ejemplo detallado de SS2PL distribuidos). Como cuestión de hecho, es más importante que ser un subconjunto de 2PL, SS2PL hereda las propiedades de recuperación y CO que por sí mismo en su forma general, además de que comprende un mecanismo simple serializabilidad (sin embargo serializabilidad también está implicada por CO), en no conocida por proporcionar SS2PL con cualquier otras cualidades significativas. 2PL en su forma general, así como cuando se combina con rigor, es decir, estricta 2PL (S2PL), no son conocidos por ser utilizados en la práctica. El SS2PL popular no requiere marcar "fin de la fase-1" como 2PL y do S2PL y así es más fácil de implementar. También, a diferencia de los generales 2PL, SS2PL ofrece, como se mencionó anteriormente, los útiles Rigor y Compromiso ordenando propiedades.

Muchas variantes de SS2PL hay que utilizar varios tipos de cerradura con varios semántica en diferentes situaciones, incluso en caso de bloqueo de tipo de cambio durante una transacción. Notables son las variantes que utilizan Bloqueo de granularidad múltiple.

Comentario:

  1. SS2PL vs S2PL: Ambos proporcionan serializabilidad y rigor. Puesto que S2PL es una clase estupenda de SS2PL puede, en principio, proporcionan más concurrencia. Sin embargo, la ventaja de no concurrencia típicamente es prácticamente notada (exactamente el mismo bloqueo existe para ambos, con desbloqueo prácticamente no mucho antes de S2PL), y la sobrecarga de lidiar con un mecanismo de fin-de-fase-1 en S2PL, separado del final de transacción no está justificada. También, mientras que SS2PL ofrece Compromiso ordenando, No S2PL. Esto explica la preferencia de SS2PL por S2PL.
  2. Especialmente antes de 1990, pero también después, en muchos artículos y libros, por ejemplo, (Bernstein et al. 1987, p. 59),[1] el término "2PL estricto" (S2PL) ha sido con frecuencia definida por el protocolo de bloqueo "Liberación todas las cerraduras solamente después del final de la transacción," que es el protocolo de SS2PL. Así, "2PL estricta" podría no estar ahí el nombre de la intersección de rigor y 2PL, que es más grande que la clase generada por el protocolo de SS2PL. Esto ha causado confusión. Con una definición explícita de S2PL como la intersección de rigor y 2PL, un nuevo nombre para SS2PL y una distinción explícita entre las clases S2PL y SS2PL, a los artículos (Breitbart et al., 1991)[3] y (Raz 1992)[4] han destinado a despejar la confusión: el primero usando el nombre de "Rigurosidad" y el segundo "SS2PL".
  3. Existe una propiedad más general que SS2PL (una programa súper clase), Compromiso estricto orden (Strict CO o SCO), que también proporciona tanto serializabilidad, rigor y CO, y tiene encima de la cabeza de bloqueo similar. A diferencia de SS2PL, SCO no bloquea a un conflicto de lectura y escritura (un bloqueo de lectura no bloquea adquirir un bloqueo de escritura; tanto SCO y SS2PL tienen el mismo comportamiento para escritura-lectura y escritura-escritura conflictos) a costa de una posible confirmación retardada y en tal conflicto tipo SCO tiene menor tiempo de finalización promedio transacción y mejor rendimiento que SS2PL.[5] Mientras que SS2PL obedece la tabla de compatibilidad de la cerradura anteriormente, SCO tiene la siguiente tabla:
Compatibilidad con cerradura para SCO
Tipo de bloqueo leer-cerradura bloqueo de escritura
leer-cerradura
bloqueo de escritura X X
Tenga en cuenta que aunque SCO libera todos los bloqueos al final de la transacción y cumple con las reglas de bloqueo de 2PL, SCO no es un subconjunto de 2PL debido a su tabla de compatibilidad de bloqueo diferente. SCO permite materializados lectura-escritura conflictos entre dos transacciones en sus etapas 1, no permite que 2PL en fase-1 (véase sobre conflictos materializados en Serializabilidad). Por otro lado 2PL permite otros tipos de conflicto materializada en la fase-2 que SCO no permite en absoluto. Juntos, esto implica que el horario clases 2PL y SCO son incomparables (es decir, no hay clase contiene la otra clase).

Resumen: las relaciones entre las clases

Horario clases contención: Una flecha de clase A clase B indica que clase contiene estrictamente B; la falta de un camino dirigido entre clases significa que las clases son incomparables. Es una propiedad inherentemente bloqueo, si se puede cumplir sólo mediante el bloqueo de las operaciones de acceso a datos de la transacción hasta que ocurran ciertos acontecimientos en otras transacciones. (Raz 1992)

Entre dos clases (definir propiedades respectivas de sus horarios) que tienen horarios comunes, ninguno de planificaciones contiene el otro)contiene estrictamente Si no son iguales), o son incomparable. Las relaciones de contención entre las clases 2PL y otras clases de horario principales se resumen en el siguiente diagrama. 2PL y sus subclases son inherentemente bloqueo, lo que significa que no existen optimistas implementaciones para ellos (y cada vez que se menciona "2PL optimista" se refiere a un mecanismo diferente con una clase que incluye también los horarios no en la clase 2PL).

Interbloqueos en 2PL

Cerraduras de bloquean las operaciones de acceso a datos. Bloqueo mutuo entre transacciones resulta en un interbloqueo, donde la ejecución de estas transacciones está paralizada, y no puede llegar a ninguna conclusión. Así los interbloqueos necesitan ser resueltos completar las ejecuciones de estas transacciones y liberar recursos informáticos relacionados. Un bloqueo es un reflejo de un ciclo de potencial en la gráfico de precedencia, que se produciría sin el bloqueo. Un interbloqueo resuelve anular una transacción con tal ciclo potencial y romper el ciclo. A menudo se detecta mediante un Espera-gráfico (un gráfico de conflictos bloqueado por bloqueos de ser materializado; los conflictos no se ha materializado en la base de datos debido a las operaciones de bloqueadas no se reflejan en el gráfico de precedencia y no afectan serializabilidad), que indica que la transacción es "waiting for" desbloqueo por transacción que, y un ciclo significa un interbloqueo. Anular una transacción por ciclo es suficiente para romper el ciclo. Anulado debido a una resolución de estancamiento de las transacciones se ejecutan inmediatamente.

En un entorno distribuido un compromiso atómico Protocolo, típicamente la Ejecución en dos fases Protocolo (2PC), es utilizado para atomicidad. Cuando datos recuperables (datos bajo el control de la transacción) se reparten entre los participantes 2PC (es decir, cada objeto de datos es controlado por un participante individual 2PC), y luego distribuidos interbloqueos (globales), interbloqueos con dos o más participantes en 2PC, se resuelven automáticamente de la siguiente manera:

Cuando SS2PL se utiliza eficazmente en un entorno distribuido, entonces interbloqueos globales debido al bloqueo de generar interbloqueos votando en 2PC y son resueltos automáticamente por 2PC (véase Compromiso ordenando (CO), en Caracterización exacta de interbloqueos votando por ciclo global; Ninguna referencia excepto los artículos CO destaca de este aviso). Para el caso general de 2PL, interbloqueos globales del mismo modo se resuelven automáticamente por el punto de sincronización Protocolo de fase-1 final en una transacción distribuida (punto de sincronización se logra mediante el "voto" (notificación local phase-1 final) y se propaga a los participantes en una transacción distribuida punto de la misma manera que una decisión en compromiso atómico; en analogía al punto de decisión en CO, una operación conflictiva en 2PL no puede ocurrir antes del punto de sincronización de fase-1 final, con la misma resultante votación-callejón sin salida en el caso de un bloqueo de acceso a datos globales; la votación-callejón sin salida (que es también un bloqueo bloqueo global basado) automáticamente se resuelve mediante el protocolo de interrupción alguna transacción involucrados, con un voto perdido, normalmente utilizando un tiempo de espera).

Comentario:

Cuando los datos se reparten entre el compromiso atómico Protocolo (por ejemplo, 2PC) participantes, automáticos estancamiento global resolución ha sido pasados por alto en la literatura de investigación de base de datos, aunque los interbloqueos en dichos sistemas ha sido un área de investigación muy intensivo:
  • Para el CO y su especial del caso SS2PL, la resolución automática por el Protocolo de compromiso atómico se ha notado en los artículos CO. Sin embargo, se ha notado en la práctica que en muchos casos los interbloqueos globales muy pocas veces son detectados por los mecanismos de resolución dedicada, menos de lo que podría esperarse ("¿por qué vemos tan pocas interbloqueos globales?"). La razón es probablemente los impasses que automáticamente resuelto y por lo tanto no manejado son contabilizadas por los mecanismos;
  • Para 2PL en general, la resolución automática por el (obligatorio) Protocolo de sincronización de fin-de-fase-uno punto No se ha mencionado (que tiene el mismo mecanismo de votación como protocolo de compromiso atómico y mismo voto falta manejo previa votación estancamiento, dando por resultado la resolución estancamiento global) hasta hoy (2009). Prácticamente sólo el caso especial que se utiliza SS2PL, donde no hay sincronización de fin-de-fase-uno es necesario además commit de atómico.
En un entorno distribuido donde datos recuperables no se reparten entre los participantes de protocolo de compromiso atómico, no existe tal resolución automática, y deadlocks distribuidos deben ser resueltos mediante técnicas dedicadas.

Véase también

  • Serializabilidad
  • Cerradura (informática)

Referencias

  1. ^ a b Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman (1987): Control de concurrencia y recuperación en sistemas de base de datos, Addison Wesley Publishing Company, ISBN 0-201-10715-5
  2. ^ Gerhard Weikum, Gottfried Vossen (2001): Sistemas de información transaccional, Elsevier, ISBN 1-55860-508-8
  3. ^ Yuri Breitbart, Dimitrios Georgakopulos, Marek Rusinkiewicz, Abraham Silberschatz (1991): "Sobre la transacción rigurosa programación", IEEE Transactions on Software Engineering (TSE), septiembre de 1991, volumen 17, número 9, págs. 954-960, ISSN: 0098-5589
  4. ^ Yoav Raz (1992): "El principio de compromiso ordenando, o garantizar serializabilidad en un entorno heterogéneo de múltiples administradores de recursos autónomos mediante compromiso atómica" (PDF), Actas de la XVIII Conferencia Internacional sobre Bases de datos muy grandes (VLDB), págs. 292-312, Vancouver, Canadá, agosto de 1992, ISBN 1-55860-151-1 (también 841 DEC-TR, Digital Equipment CorporationDe noviembre de 1990)
  5. ^ Yoav Raz (1991): "pedidos de compromiso estricto bloqueo basado, o cómo mejorar la concurrencia en los administradores de recursos de bloqueo basado, 844 DEC-TR, diciembre de 1991.

Otras Páginas

Obtenido de"https://en.copro.org/w/index.php?title=Two-phase_locking&oldid=627316994"