Hispanopedia Wiki
Articulo de referencia

Control de concurrencia

Comprobado En tecnología de la información e informática , especialmente en los campos de la programación informática , los sistemas operativos , los multiprocesadores y las bas...

Hispanopedia WikiContenido en espanolLectura gratuita
Comprobado
Página protegida con cambios pendientes

En tecnología de la información e informática , especialmente en los campos de la programación informática , los sistemas operativos , los multiprocesadores y las bases de datos , el control de concurrencia garantiza que se generen resultados correctos para las operaciones concurrentes , al tiempo que se obtienen esos resultados lo más rápido posible.

Los sistemas informáticos, tanto de software como de hardware , constan de módulos o componentes. Cada componente está diseñado para funcionar correctamente, es decir, para cumplir ciertas reglas de consistencia. Cuando los componentes que operan concurrentemente interactúan mediante mensajería o compartiendo datos (en memoria o almacenamiento ), la consistencia de un componente puede verse comprometida por otro. El control de concurrencia proporciona reglas, métodos, metodologías de diseño y teorías para mantener la consistencia de los componentes que operan concurrentemente mientras interactúan, y por lo tanto, la consistencia y corrección de todo el sistema. Introducir el control de concurrencia en un sistema implica aplicar restricciones operativas que, por lo general, resultan en una reducción del rendimiento. La consistencia y corrección operativa deben lograrse con la mayor eficiencia posible, sin reducir el rendimiento por debajo de niveles razonables. El control de concurrencia puede requerir una complejidad y sobrecarga significativamente mayores en un algoritmo concurrente en comparación con el algoritmo secuencial más simple .

Por ejemplo, un fallo en el control de concurrencia puede provocar la corrupción de datos debido a operaciones de lectura o escritura incompletas .

Control de concurrencia en bases de datos

Comentarios:

  1. Esta sección es aplicable a todos los sistemas transaccionales, es decir, a todos los sistemas que utilizan transacciones de bases de datos ( transacciones atómicas ; por ejemplo, objetos transaccionales en la gestión de sistemas y en redes de teléfonos inteligentes que normalmente implementan sistemas de bases de datos privados y dedicados), no solo a los sistemas de gestión de bases de datos (DBMS) de propósito general .
  2. Los sistemas de gestión de bases de datos (DBMS) también deben abordar problemas de control de concurrencia que no son exclusivos de las transacciones de bases de datos, sino que son comunes a los sistemas operativos en general. Estos problemas (véase, por ejemplo, el apartado «Control de concurrencia en sistemas operativos » más adelante) quedan fuera del alcance de esta sección.

El control de concurrencia en los sistemas de gestión de bases de datos (DBMS; p. ej., Bernstein et al. 1987 , Weikum y Vossen 2001 ), otros objetos transaccionales y aplicaciones distribuidas relacionadas (p. ej., computación en malla y computación en la nube ) garantiza que las transacciones de la base de datos se realicen simultáneamente sin violar la integridad de los datos de las bases de datos respectivas . Por lo tanto, el control de concurrencia es un elemento esencial para la corrección en cualquier sistema donde dos o más transacciones de base de datos, ejecutadas con solapamiento temporal, puedan acceder a los mismos datos, p. ej., prácticamente en cualquier sistema de base de datos de propósito general. En consecuencia, se ha acumulado un vasto cuerpo de investigación relacionada desde que surgieron los sistemas de bases de datos a principios de la década de 1970. Una teoría de control de concurrencia bien establecida para sistemas de bases de datos se describe en las referencias mencionadas anteriormente: la teoría de la serializabilidad , que permite diseñar y analizar eficazmente métodos y mecanismos de control de concurrencia. Una teoría alternativa para el control de concurrencia de transacciones atómicas sobre tipos de datos abstractos se presenta en ( Lynch et al. 1993 ), y no se utiliza a continuación. Esta teoría es más refinada, compleja y de mayor alcance, y se ha utilizado menos en la literatura sobre bases de datos que la teoría clásica mencionada anteriormente. Cada teoría tiene sus ventajas y desventajas, sus énfasis y sus perspectivas . Hasta cierto punto, son complementarias y su combinación podría resultar útil.

Para garantizar la corrección, un SGBD generalmente garantiza que solo se generen secuencias de transacciones serializables , a menos que la serializabilidad se relaje intencionalmente para aumentar el rendimiento, pero solo en casos donde la corrección de la aplicación no se vea perjudicada. Para mantener la corrección en casos de transacciones fallidas (abortadas) (que siempre pueden ocurrir por muchas razones), las secuencias también deben tener la propiedad de recuperabilidad (desde el aborto). Un SGBD también garantiza que no se pierda ningún efecto de las transacciones confirmadas , y que ningún efecto de las transacciones abortadas ( revertidas ) permanezca en la base de datos relacionada. La caracterización general de las transacciones generalmente se resume en las reglas ACID que se muestran a continuación. A medida que las bases de datos se han vuelto distribuidas , o han necesitado cooperar en entornos distribuidos (por ejemplo, bases de datos federadas a principios de la década de 1990, y computación en la nube actualmente), la distribución efectiva de los mecanismos de control de concurrencia ha recibido especial atención.

Transacción de base de datos y las reglas ACID

El concepto de transacción de base de datos (o transacción atómica ) ha evolucionado para permitir un comportamiento predecible del sistema de base de datos en un entorno con fallos, donde pueden producirse caídas en cualquier momento, y la recuperación tras una caída a un estado de base de datos predecible. Una transacción de base de datos es una unidad de trabajo que, por lo general, encapsula varias operaciones sobre una base de datos (por ejemplo, leer un objeto de base de datos , escribir, adquirir un bloqueo, etc.), una abstracción compatible con la base de datos y otros sistemas. Cada transacción tiene límites bien definidos en cuanto a las ejecuciones de programa/código que incluye (determinados por el programador de la transacción mediante comandos especiales). Cada transacción de base de datos obedece las siguientes reglas (con soporte del sistema de base de datos; es decir, un sistema de base de datos está diseñado para garantizarlas para las transacciones que ejecuta):

  • Atomicidad : Cuando una transacción se completa ( se confirma o se cancela, respectivamente) , los efectos de todas o ninguna de sus operaciones permanecen (semántica de "todo o nada"). En otras palabras, para el mundo exterior, una transacción confirmada parece (por sus efectos en la base de datos) indivisible (atómica), y una transacción cancelada no afecta en absoluto a la base de datos. O se realizan todas las operaciones o no se realiza ninguna.
  • Consistencia : Cada transacción debe dejar la base de datos en un estado consistente (correcto), es decir, debe mantener las reglas de integridad predeterminadas de la base de datos (restricciones aplicadas a los objetos de la base de datos y entre ellos). Una transacción debe transformar una base de datos de un estado consistente a otro (sin embargo, es responsabilidad del programador de la transacción asegurarse de que la transacción en sí sea correcta, es decir, que realice correctamente lo que pretende realizar (desde el punto de vista de la aplicación) mientras que el sistema de gestión de bases de datos (DBMS) aplica las reglas de integridad predefinidas). Por lo tanto, dado que una base de datos normalmente solo puede modificarse mediante transacciones, todos los estados de la base de datos son consistentes.
  • Aislamiento : Las transacciones no pueden interferir entre sí (como resultado final de su ejecución). Además, por lo general (dependiendo del método de control de concurrencia), los efectos de una transacción incompleta ni siquiera son visibles para otra transacción. Proporcionar aislamiento es el objetivo principal del control de concurrencia.
  • Durabilidad : los efectos de las transacciones exitosas (confirmadas) deben persistir a través de fallos (normalmente registrando los efectos de la transacción y su evento de confirmación en una memoria no volátil ).

El concepto de transacción atómica se ha extendido a lo largo de los años hasta convertirse en transacciones comerciales que, en realidad, implementan flujos de trabajo y no son atómicas. Sin embargo, estas transacciones mejoradas también suelen utilizar transacciones atómicas como componentes.

¿Por qué es necesario el control de concurrencia?

Si las transacciones se ejecutan en serie , es decir, secuencialmente sin superposición en el tiempo, no existe concurrencia de transacciones. Sin embargo, si se permiten transacciones concurrentes con operaciones intercaladas de manera no controlada, pueden ocurrir algunos resultados inesperados e indeseables, tales como:

  1. El problema de la actualización perdida : Una segunda transacción escribe un segundo valor de un elemento de datos (dato) sobre un primer valor escrito por una primera transacción concurrente, y el primer valor se pierde para otras transacciones que se ejecutan simultáneamente y que, por su precedencia, necesitan leerlo. Las transacciones que han leído el valor incorrecto obtienen resultados erróneos.
  2. El problema de la lectura sucia : Las transacciones leen un valor escrito por una transacción que posteriormente se canceló. Este valor desaparece de la base de datos al cancelarse la transacción y no debería haber sido leído por ninguna otra ("lectura sucia"). Las transacciones de lectura finalizan con resultados incorrectos.
  3. El problema del resumen incorrecto: Mientras una transacción genera un resumen de los valores de todas las instancias de un elemento de datos repetido, una segunda transacción actualiza algunas instancias de ese mismo elemento. El resumen resultante no refleja un resultado correcto para ningún orden de precedencia (generalmente necesario para la corrección) entre las dos transacciones (si una se ejecuta antes que la otra), sino un resultado aleatorio, que depende del momento de las actualizaciones y de si ciertos resultados de actualización se han incluido o no en el resumen.

La mayoría de los sistemas transaccionales de alto rendimiento necesitan ejecutar transacciones simultáneamente para cumplir con sus requisitos de rendimiento. Por lo tanto, sin control de concurrencia, dichos sistemas no pueden proporcionar resultados correctos ni mantener sus bases de datos de forma consistente.

Mecanismos de control de concurrencia

Categorías

Las principales categorías de mecanismos de control de concurrencia son:

  • Optimista : Permite que las transacciones continúen sin bloquear ninguna de sus operaciones (lectura, escritura) («…y sé optimista respecto al cumplimiento de las reglas…»), y solo verifica las infracciones de las reglas de integridad deseadas (p. ej., serializabilidad y recuperabilidad ) al confirmar cada transacción. Si se detectan infracciones al confirmar una transacción, esta se aborta y se reinicia. Este enfoque es muy eficiente cuando se abortan pocas transacciones.
  • Enfoque pesimista : Bloquear una operación de una transacción si puede provocar una violación de las reglas (por ejemplo, serializabilidad y recuperabilidad) hasta que desaparezca la posibilidad de dicha violación. El bloqueo de operaciones suele estar relacionado con una reducción del rendimiento.
  • Semioptimista : responde de forma pesimista u optimista dependiendo del tipo de infracción y de la rapidez con que pueda detectarse.

Las distintas categorías ofrecen un rendimiento diferente, es decir, distintas tasas promedio de finalización de transacciones ( rendimiento ), dependiendo de la combinación de tipos de transacciones, el nivel de paralelismo computacional y otros factores. Si se dispone de información sobre las ventajas y desventajas de cada opción, se debe elegir la categoría y el método que ofrezcan el máximo rendimiento.

El bloqueo mutuo entre dos o más transacciones (donde cada una bloquea a la otra) da lugar a un interbloqueo , en el que las transacciones implicadas se estancan y no pueden completarse. La mayoría de los mecanismos no optimistas (con bloqueo) son propensos a los interbloqueos, que se resuelven mediante la interrupción intencionada de una transacción estancada (lo que libera a las demás transacciones bloqueadas) y su reinicio y ejecución inmediatos. La probabilidad de un interbloqueo suele ser baja.

Los bloqueos, los interbloqueos y las interrupciones provocan una reducción del rendimiento y, por lo tanto, existen compensaciones entre las diferentes categorías.

Métodos

Existen muchos métodos para el control de concurrencia. La mayoría de ellos pueden implementarse dentro de cualquiera de las categorías principales mencionadas anteriormente. Los métodos principales, [ 1 ] que tienen muchas variantes cada uno y que en algunos casos pueden superponerse o combinarse, son:

  1. Bloqueo (por ejemplo, bloqueo de dos fases - 2PL): Control del acceso a los datos mediante bloqueos asignados a los mismos. El acceso de una transacción a un elemento de datos (objeto de base de datos) bloqueado por otra transacción puede quedar bloqueado (según el tipo de bloqueo y el tipo de operación de acceso) hasta que se libere el bloqueo.
  2. Verificación del grafo de serialización (también llamada verificación de serializabilidad, o de conflictos, o de precedencia): comprobar si hay ciclos en el grafo de planificación y romperlos mediante interrupciones.
  3. Ordenación por marca de tiempo (TO): Asignación de marcas de tiempo a las transacciones y control o verificación del acceso a los datos mediante el orden de las marcas de tiempo.

Otros tipos importantes de control de concurrencia que se utilizan junto con los métodos anteriores incluyen:

  • Control de concurrencia multiversión (MVCC): aumenta la concurrencia y el rendimiento al generar una nueva versión de un objeto de base de datos cada vez que se escribe en él, y permite que las transacciones realicen operaciones de lectura de varias versiones recientes relevantes (de cada objeto) según el método de planificación.
  • Control de concurrencia de índices : sincronización de las operaciones de acceso a los índices , en lugar de a los datos de usuario. Los métodos especializados proporcionan mejoras sustanciales en el rendimiento.
  • Modelo de espacio de trabajo privado ( actualización diferida ): cada transacción mantiene un espacio de trabajo privado para los datos a los que accede, y los datos modificados solo se hacen visibles fuera de la transacción al confirmarla (por ejemplo, Weikum y Vossen, 2001 ). Este modelo ofrece un comportamiento de control de concurrencia diferente, con ventajas en muchos casos.

El tipo de mecanismo más común en los sistemas de bases de datos desde sus inicios en la década de 1970 ha sido el bloqueo estricto de dos fases (SS2PL; también llamado programación rigurosa o 2PL riguroso ), que es un caso especial (variante) del bloqueo de dos fases (2PL). Es pesimista. A pesar de su nombre largo (por razones históricas), la idea del mecanismo SS2PL es simple: "Liberar todos los bloqueos aplicados por una transacción solo después de que la transacción haya finalizado". SS2PL (o Rigorousness) es también el nombre del conjunto de todas las programaciones que puede generar este mecanismo, es decir, estas programaciones SS2PL (o Rigorous) tienen la propiedad SS2PL (o Rigorousness).

Objetivos principales de los mecanismos de control de concurrencia

Los mecanismos de control de concurrencia deben, en primer lugar, funcionar correctamente, es decir, mantener las reglas de integridad de cada transacción (relacionadas con la concurrencia; las reglas de integridad específicas de la aplicación quedan fuera del alcance de este análisis) mientras las transacciones se ejecutan simultáneamente, y, por lo tanto, la integridad de todo el sistema transaccional. La corrección debe lograrse con el mejor rendimiento posible. Además, existe una necesidad creciente de operar eficazmente cuando las transacciones se distribuyen entre procesos , ordenadores y redes informáticas . Otros aspectos que pueden afectar al control de concurrencia son la recuperación y la replicación .

Exactitud

Serializabilidad

Para garantizar la corrección, un objetivo principal común de la mayoría de los mecanismos de control de concurrencia es generar secuencias de transacciones con la propiedad de serializabilidad . Sin serializabilidad, pueden ocurrir fenómenos indeseables; por ejemplo, el dinero puede desaparecer de las cuentas o generarse de la nada. La serializabilidad de una secuencia de transacciones implica la equivalencia (en los valores de la base de datos resultante) con una secuencia serial con las mismas transacciones (es decir, en la que las transacciones son secuenciales sin solapamiento temporal y, por lo tanto, completamente aisladas entre sí: no es posible el acceso concurrente de dos transacciones a los mismos datos). La serializabilidad se considera el nivel más alto de aislamiento entre las transacciones de la base de datos y el principal criterio de corrección para las transacciones concurrentes. En algunos casos, se permiten formas de serializabilidad menos estrictas para un mejor rendimiento (por ejemplo, el popular mecanismo de aislamiento Snapshot ) o para cumplir con los requisitos de disponibilidad en sistemas altamente distribuidos (véase Consistencia eventual ), pero solo si la corrección de la aplicación no se ve comprometida por la flexibilización (por ejemplo, no se permite ninguna flexibilización para las transacciones monetarias , ya que, debido a la flexibilización, el dinero puede desaparecer o aparecer de la nada).

Casi todos los mecanismos de control de concurrencia implementados logran la serializabilidad al proporcionar serializabilidad de conflictos , un caso especial amplio de serializabilidad (es decir, cubre y habilita la mayoría de las planificaciones serializables y no impone restricciones adicionales significativas que causen retrasos) que se puede implementar de manera eficiente.

Recuperabilidad
Consulte Recuperabilidad en Serializabilidad.

El control de concurrencia normalmente también garantiza la propiedad de recuperabilidad de los planes para mantener la corrección en casos de transacciones abortadas (que siempre pueden ocurrir por muchas razones). La recuperabilidad (de un aborto) significa que ninguna transacción confirmada en un plan ha leído datos escritos por una transacción abortada. Dichos datos desaparecen de la base de datos (tras el aborto) y son parte de un estado incorrecto de la base de datos. Leer dichos datos viola la regla de consistencia de ACID. A diferencia de la serializabilidad, la recuperabilidad no puede verse comprometida, relajada en ningún caso, ya que cualquier relajación resulta en una rápida violación de la integridad de la base de datos tras los abortos. Los principales métodos enumerados anteriormente proporcionan mecanismos de serializabilidad. Ninguno de ellos en su forma general proporciona automáticamente recuperabilidad, y se necesitan consideraciones especiales y mejoras de mecanismos para admitir la recuperabilidad. Un caso especial de recuperabilidad comúnmente utilizado es la estrictez , que permite una recuperación eficiente de la base de datos ante fallos (pero excluye las implementaciones optimistas.

Distribución

Con el rápido desarrollo tecnológico de la computación, la diferencia entre la computación local y la distribuida en redes o buses de baja latencia se difumina. Por ello, es común el uso eficaz de técnicas locales en entornos distribuidos, por ejemplo, en clústeres de computadoras y procesadores multinúcleo . Sin embargo, estas técnicas tienen sus limitaciones y requieren multiprocesos (o hilos) soportados por multiprocesadores (o multinúcleos) para escalar. Esto suele convertir las transacciones en distribuidas si necesitan abarcar varios procesos. En estos casos, la mayoría de las técnicas locales de control de concurrencia no escalan bien.

Recuperación

Todos los sistemas son propensos a fallar, y la recuperación ante fallos es fundamental. Las propiedades de las planificaciones generadas, determinadas por el mecanismo de control de concurrencia, pueden afectar la efectividad y eficiencia de la recuperación. Por ejemplo, la propiedad de Estrictez (mencionada en la sección Recuperabilidad ) suele ser deseable para una recuperación eficiente.

Replicación

Para lograr alta disponibilidad, los objetos de la base de datos a menudo se replican . Las actualizaciones de las réplicas de un mismo objeto de la base de datos deben mantenerse sincronizadas. Esto puede afectar la forma en que se realiza el control de concurrencia (por ejemplo, Gray et al. 1996 [ 2 ] ).

Control de concurrencia en sistemas operativos

Los sistemas operativos multitarea , especialmente los de tiempo real , necesitan mantener la ilusión de que todas las tareas que se ejecutan sobre ellos lo hacen simultáneamente, aunque en realidad solo una o unas pocas se ejecutan en un momento dado debido a las limitaciones del hardware. Esta multitarea es bastante sencilla cuando todas las tareas son independientes entre sí. Sin embargo, cuando varias tareas intentan usar el mismo recurso o compartir información, puede generar confusión e inconsistencia. La computación concurrente se encarga de resolver este problema. Algunas soluciones implican "bloqueos" similares a los utilizados en las bases de datos, pero conllevan el riesgo de generar problemas propios, como el interbloqueo . Otras soluciones son los algoritmos sin bloqueo y la actualización mediante lectura y copia .

Véase también

Referencias

  • Andrew S. Tanenbaum, Albert S. Woodhull (2006): Diseño e implementación de sistemas operativos, 3.ª edición , Prentice Hall , ISBN 0-13-142938-8
  • Silberschatz, Avi; Galvin, Peter; Gagne, Greg (2008). Conceptos de sistemas operativos, 8.ª edición . John Wiley & Sons . ISBN 978-0-470-12872-5.
  • Philip A. Bernstein , Vassos Hadzilacos, Nathan Goodman (1987): Control de concurrencia y recuperación en sistemas de bases de datos (descarga gratuita en PDF), Addison Wesley Publishing Company, 1987, ISBN 0-201-10715-5
  • Gerhard Weikum , Gottfried Vossen (2001): Sistemas de información transaccional , Elsevier, ISBN 1-55860-508-8
  • Nancy Lynch , Michael Merritt, William Weihl, Alan Fekete (1993): Transacciones atómicas en sistemas concurrentes y distribuidos , Morgan Kaufmann (Elsevier), agosto de 1993, ISBN 978-1-55860-104-8, ISBN 1-55860-104-X
  • Yoav Raz (1992): "El principio de ordenación de compromisos, o la garantía de serializabilidad en un entorno heterogéneo de múltiples gestores de recursos autónomos mediante compromiso atómico." ( PDF ), Actas de la Decimoctava Conferencia Internacional sobre Bases de Datos Muy Grandes (VLDB), págs. 292-312, Vancouver, Canadá, agosto de 1992. (También DEC-TR 841, Digital Equipment Corporation , noviembre de 1990)

Citas

  1. ↑ Philip A. Bernstein , Eric Newcomer (2009): Principios del procesamiento de transacciones , 2.ª edición . Archivado el 7 de agosto de 2010 en Wayback Machine , Morgan Kaufmann (Elsevier), junio de 2009, ISBN 978-1-55860-623-4(página 145)
  2. ↑ Gray, J.; Helland, P.; O'Neil, P .; Shasha, D. (1996). Actas de la Conferencia Internacional ACM SIGMOD de 1996 sobre Gestión de Datos . Los peligros de la replicación y una solución (PDF) . págs. 173–182 . doi : 10.1145/233269.233330 . 
Obtenido de " https://en.wikipedia.org/w/index.php?title=Concurrency_control&oldid=1330549102 "