En tecnología de la información e informática , especialmente en los campos de programación informática , sistemas operativos , multiprocesadores y bases de datos , el control de concurrencia garantiza que se generen resultados correctos para operaciones concurrentes , al tiempo que se obtienen esos resultados lo más rápido posible.
Los sistemas informáticos, tanto software como hardware , constan de módulos o componentes. Cada componente está diseñado para funcionar correctamente, es decir, para obedecer o cumplir ciertas reglas de coherencia. Cuando los componentes que funcionan simultáneamente interactúan mediante mensajes o comparten los datos a los que se accede (en la memoria o el almacenamiento ), otro componente puede violar la coherencia de un determinado componente. El área general de control de concurrencia proporciona reglas, métodos, metodologías de diseño y teorías para mantener la coherencia de los componentes que operan simultáneamente mientras interactúan y, por tanto, la coherencia y corrección de todo el sistema. Introducir el control de concurrencia en un sistema significa aplicar restricciones operativas que normalmente resultan en cierta reducción del rendimiento. La coherencia y corrección de la operación 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 una sobrecarga adicionales significativas en un algoritmo concurrente en comparación con el algoritmo secuencial más simple .
Por ejemplo, una falla en el control de concurrencia puede provocar daños en los datos debido a operaciones de lectura o escritura rotas.
Comentarios:
El control de concurrencia en los sistemas de gestión de bases de datos (DBMS; por ejemplo, Bernstein et al. 1987, Weikum y Vossen 2001), otros objetos transaccionales y aplicaciones distribuidas relacionadas (por ejemplo, computación Grid y computación en la nube ) garantiza que las transacciones de bases de datos se realicen simultáneamente sin violar el integridad de los datos de las respectivas bases de datos . Por tanto, el control de concurrencia es un elemento esencial para la corrección en cualquier sistema en el que dos transacciones de bases de datos o más, ejecutadas con superposición temporal, puedan acceder a los mismos datos, por ejemplo, prácticamente en cualquier sistema de bases de datos de propósito general. En consecuencia, se ha acumulado una gran cantidad de investigaciones relacionadas desde que surgieron los sistemas de bases de datos a principios de los años setenta. En las referencias mencionadas anteriormente se describe una teoría de control de concurrencia bien establecida para sistemas de bases de datos: teoría de la serializabilidad , que permite diseñar y analizar de manera efectiva métodos y mecanismos de control de concurrencia. En (Lynch et al. 1993) se presenta una teoría alternativa para el control de concurrencia de transacciones atómicas sobre tipos de datos abstractos , que no se utiliza a continuación. Esta teoría es más refinada, compleja, con un alcance más amplio y se ha utilizado menos en la literatura sobre bases de datos que la teoría clásica anterior. Cada teoría tiene sus pros y sus contras, énfasis y conocimiento . Hasta cierto punto son complementarios y su fusión puede resultar útil.
Para garantizar la corrección, un DBMS generalmente garantiza que solo se generen programas de transacciones serializables , a menos que la serialización se relaje intencionalmente para aumentar el rendimiento, pero solo en los casos en que 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), los cronogramas también deben tener la propiedad de recuperabilidad (de cancelación). Un DBMS también garantiza que no se pierda ningún efecto de las transacciones confirmadas y que no quede ningún efecto de las transacciones abortadas ( revertidas ) en la base de datos relacionada. La caracterización general de las transacciones generalmente se resume en las reglas ACID a continuación. A medida que las bases de datos se han vuelto distribuidas , o han necesitado cooperar en entornos distribuidos (por ejemplo, las bases de datos federadas a principios de 1990 y la computación en la nube actualmente), la distribución efectiva de los mecanismos de control de concurrencia ha recibido especial atención.
El concepto de transacción de base de datos (o transacción atómica ) ha evolucionado para permitir un comportamiento bien entendido del sistema de base de datos en un entorno defectuoso donde las fallas pueden ocurrir en cualquier momento, y la recuperación de una falla a un estado de base de datos bien entendido. Una transacción de base de datos es una unidad de trabajo, que normalmente encapsula una serie de operaciones sobre una base de datos (por ejemplo, leer un objeto de base de datos, escribir, adquirir un bloqueo, etc.), una abstracción admitida en la base de datos y también en otros sistemas. Cada transacción tiene límites bien definidos en términos de qué ejecuciones de programa/código se incluyen en esa transacción (determinados por el programador de la transacción mediante comandos de transacción especiales). Cada transacción de base de datos obedece a las siguientes reglas (por soporte en el sistema de base de datos; es decir, un sistema de base de datos está diseñado para garantizarlas para las transacciones que ejecuta):
El concepto de transacción atómica se ha extendido a lo largo de los años a lo que se ha convertido en transacciones comerciales que en realidad implementan tipos de flujo de trabajo y no son atómicas. Sin embargo, estas transacciones mejoradas suelen utilizar transacciones atómicas como componentes.
Si las transacciones se ejecutan en serie , es decir, secuencialmente sin superposición en el tiempo, no existe simultaneidad en las transacciones. Sin embargo, si se permiten transacciones concurrentes con operaciones de entrelazado de manera no controlada, pueden ocurrir algunos resultados inesperados e indeseables, tales como:
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 manera consistente.
Las principales categorías de mecanismos de control de concurrencia son:
Las diferentes categorías proporcionan un rendimiento diferente, es decir, diferentes 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 selección y conocimiento sobre las compensaciones, entonces se deben elegir la categoría y el método para proporcionar el mayor rendimiento.
El bloqueo mutuo entre dos transacciones (donde cada una bloquea a la otra) o más da como resultado un punto muerto , donde las transacciones involucradas se estancan y no pueden completarse. La mayoría de los mecanismos no optimistas (con bloqueo) son propensos a interbloqueos que se resuelven mediante un aborto intencional de una transacción estancada (que libera las otras transacciones en ese punto muerto), y su reinicio y reejecución inmediatos. La probabilidad de un punto muerto suele ser baja.
Los bloqueos, los puntos muertos y los abortos dan como resultado una reducción del rendimiento y, por tanto, las compensaciones entre las categorías.
Existen muchos métodos para el control de la concurrencia. La mayoría de ellos se pueden implementar dentro de cualquiera de las categorías principales anteriores. Los métodos principales, [1] que tienen muchas variantes y en algunos casos pueden superponerse o combinarse, son:
Otros tipos importantes de control de concurrencia que se utilizan junto con los métodos anteriores incluyen:
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) tanto del bloqueo de dos fases (2PL) ) y Orden de compromiso (CO). 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 sólo después de que la transacción haya finalizado". SS2PL (o Rigurosidad) es también el nombre del conjunto de todos los cronogramas que pueden generarse mediante este mecanismo, es decir, estos cronogramas SS2PL (o Riguroso) tienen la propiedad SS2PL (o Rigurosidad).
En primer lugar, los mecanismos de control de concurrencia deben funcionar correctamente, es decir, mantener las reglas de integridad de cada transacción (en relación con la concurrencia; las reglas de integridad específicas de la aplicación están fuera del alcance aquí) 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 desempeño posible. Además, existe cada vez más la necesidad de operar eficazmente mientras las transacciones se distribuyen entre procesos , computadoras y redes informáticas . Otros temas que pueden afectar el control de concurrencia son la recuperación y la replicación .
Para que sea correcto, un objetivo principal común de la mayoría de los mecanismos de control de concurrencia es generar programaciones con la propiedad Serializabilidad . Sin serializabilidad pueden ocurrir fenómenos indeseables, por ejemplo, el dinero puede desaparecer de las cuentas o generarse de la nada. La serialización de un cronograma significa equivalencia (en los valores de la base de datos resultantes) con algún cronograma en serie con las mismas transacciones (es decir, en el que las transacciones son secuenciales sin superposición en el tiempo y, por lo tanto, están completamente aisladas entre sí: no hay acceso simultáneo por parte de dos transacciones cualesquiera). a los mismos datos es posible). La serialización se considera el nivel más alto de aislamiento entre las transacciones de bases de datos y el principal criterio de corrección para las transacciones concurrentes. En algunos casos, se permiten formas de serialización relajadas y comprometidas para un mejor rendimiento (por ejemplo, el popular mecanismo de aislamiento de instantáneas ) o para cumplir con los requisitos de disponibilidad en sistemas altamente distribuidos (consulte Consistencia final ), pero solo si la relajación no viola la corrección de la aplicación ( ej., no se permite ninguna relajación para las transacciones monetarias , ya que mediante la relajación el dinero puede desaparecer o aparecer de la nada).
Casi todos los mecanismos de control de concurrencia implementados logran la serialización al proporcionar serializabilidad de conflicto , un caso especial amplio de serialización (es decir, cubre, permite la mayoría de los cronogramas serializables y no impone restricciones adicionales significativas que causen retrasos) que se puede implementar de manera eficiente.
Comentario: Mientras que en el área general de los sistemas el término "recuperabilidad" puede referirse a la capacidad de un sistema para recuperarse de una falla o de un estado incorrecto/prohibido, dentro del control de concurrencia de los sistemas de bases de datos este término ha recibido un significado específico.
El control de concurrencia generalmente también garantiza la propiedad de Recuperabilidad de los cronogramas para mantener la corrección en casos de transacciones abortadas (lo que siempre puede suceder por muchas razones). Recuperabilidad (desde aborto) significa que ninguna transacción confirmada en un cronograma ha leído datos escritos por una transacción abortada. Estos datos desaparecen de la base de datos (al cancelarse) y forman parte de un estado incorrecto de la base de datos. La lectura de dichos datos viola la regla de coherencia de ACID. A diferencia de la serialización, la recuperabilidad no puede verse comprometida ni relajada en ningún caso, ya que cualquier relajación da como resultado una rápida violación de la integridad de la base de datos al abortar. Los principales métodos enumerados anteriormente proporcionan mecanismos de serialización. Ninguno de ellos en su forma general proporciona automáticamente recuperabilidad, y se necesitan consideraciones especiales y mejoras en los mecanismos para respaldar la recuperabilidad. Un caso especial de recuperabilidad comúnmente utilizado es Strictness , que permite una recuperación eficiente de la base de datos frente a fallas (pero excluye implementaciones optimistas; por ejemplo, Strict CO (SCO) no puede tener una implementación optimista, pero tiene implementaciones semioptimistas).
Comentario: Tenga en cuenta que la propiedad Recuperabilidad es necesaria incluso si no se produce ningún error en la base de datos y no es necesaria ninguna recuperación de la base de datos tras un error. Más bien es necesario para manejar correctamente y automáticamente las cancelaciones de transacciones, que pueden no estar relacionadas con la falla de la base de datos y la recuperación de la misma.
Con el rápido desarrollo tecnológico de la informática, la diferencia entre la informática local y la distribuida a través de redes o buses de baja latencia se está volviendo borrosa. Por lo tanto, la utilización bastante efectiva de técnicas locales en tales entornos distribuidos es común, por ejemplo, en grupos de computadoras y procesadores multinúcleo . Sin embargo, las técnicas locales tienen sus limitaciones y utilizan multiprocesos (o subprocesos) respaldados por multiprocesadores (o múltiples núcleos) para escalar. Esto a menudo convierte las transacciones en distribuidas, si ellas mismas necesitan abarcar múltiples procesos. En estos casos, la mayoría de las técnicas de control de concurrencia local no escalan bien.
A medida que los sistemas de bases de datos se distribuyeron o comenzaron a cooperar en entornos distribuidos (por ejemplo, las bases de datos federadas a principios de la década de 1990 y hoy en día la computación Grid , la computación en la nube y las redes con teléfonos inteligentes ), algunas transacciones se han distribuido. Una transacción distribuida significa que la transacción abarca procesos y puede abarcar computadoras y sitios geográficos. Esto genera la necesidad de mecanismos eficaces de control de la concurrencia distribuida . Lograr la propiedad de serialización de la programación de un sistema distribuido (consulte Serializabilidad distribuida y serialización global ( serializabilidad modular )) plantea de manera efectiva desafíos especiales que normalmente no enfrentan la mayoría de los mecanismos de serialización regulares, originalmente diseñados para operar localmente. Esto se debe especialmente a la necesidad de una costosa distribución de información de control de concurrencia en medio de la comunicación y la latencia de la computadora . La única técnica general efectiva conocida para la distribución es la orden de compromiso, que se dio a conocer públicamente en 1991 (después de ser patentada ). El orden de compromiso (Commit ordering, CO; Raz 1992) significa que el orden cronológico de los eventos de compromiso de las transacciones se mantiene compatible con su respectivo orden de precedencia . CO no requiere la distribución de información de control de concurrencia y proporciona una solución general efectiva ( confiable , de alto rendimiento y escalable ) para la serialización distribuida y global, también en un entorno heterogéneo con sistemas de bases de datos (u otros objetos transaccionales) con diferentes ( cualquiera) mecanismos de control de concurrencia. [1] CO es indiferente a qué mecanismo se utiliza, ya que no interfiere con la programación de ninguna operación de transacción (que la mayoría de los mecanismos controlan) y solo determina el orden de los eventos de confirmación. Por lo tanto, CO permite la distribución eficiente de todos los demás mecanismos, y también la distribución de una combinación de diferentes (cualquier) mecanismo local, para lograr una serialización distribuida y global. La existencia de una solución de este tipo se consideró "improbable" hasta 1991, y muchos expertos también más tarde, debido a una mala comprensión de la solución de CO (ver Citas en Serialización global ). Un beneficio secundario importante de CO es la resolución automática de puntos muertos distribuidos . A diferencia del CO, prácticamente todas las demás técnicas (cuando no se combinan con el CO) son propensas a estancamientos distribuidos.(también llamados puntos muertos globales) que necesitan un manejo especial. CO es también el nombre de la propiedad de programación resultante: una programación tiene la propiedad CO si el orden cronológico de los eventos de confirmación de sus transacciones es compatible con el orden de precedencia (parcial) de las transacciones respectivas .
SS2PL mencionado anteriormente es una variante (caso especial) de CO y, por lo tanto, también es eficaz para lograr una serialización distribuida y global. También proporciona resolución automática de interbloqueos distribuidos (un hecho que se pasa por alto en la literatura de investigación incluso después de la publicación de CO), así como rigor y, por lo tanto, capacidad de recuperación. La posesión de estas propiedades deseadas junto con implementaciones conocidas basadas en bloqueos eficientes explica la popularidad de SS2PL. SS2PL se ha utilizado para lograr de manera eficiente la serialización distribuida y global desde 1980, y se ha convertido en el estándar de facto para ello. Sin embargo, SS2PL es bloqueador y restrictivo (pesimista), y con la proliferación de distribución y utilización de sistemas diferentes de los sistemas de bases de datos tradicionales (por ejemplo, como en la computación en la nube ), pueden ser necesarios tipos de CO menos restrictivos (por ejemplo, CO optimista ) para mejor interpretación.
Comentarios:
A diferencia de la serialización, la recuperabilidad distribuida y el rigor distribuido se pueden lograr de manera eficiente y sencilla, de manera similar a la forma en que se logra el CO distribuido: en cada sistema de base de datos deben aplicarse localmente y emplear una estrategia de ordenación de votos para el protocolo de confirmación de dos fases. (2PC; Raz 1992, página 307).
Como se mencionó anteriormente, SS2PL distribuido , incluido el rigor distribuido (recuperabilidad) y el orden de compromiso distribuido (serialización), emplea automáticamente la estrategia de ordenación de votos necesaria y se logra (globalmente) cuando se emplea localmente en cada sistema de base de datos (local) (como se ha hecho). ha sido conocido y utilizado durante muchos años; de hecho, la localidad se define por los límites de un participante de 2PC (Raz 1992).
Todos los sistemas son propensos a fallar y es imprescindible gestionar la recuperación tras una falla. Las propiedades de los cronogramas generados, que están dictados por el mecanismo de control de concurrencia, pueden afectar la efectividad y eficiencia de la recuperación. Por ejemplo, la propiedad de rigor (mencionada en la sección Recuperabilidad anterior) suele ser deseable para una recuperación eficiente.
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 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] ).
Los sistemas operativos multitarea , especialmente los sistemas operativos en tiempo real , necesitan mantener la ilusión de que todas las tareas que se ejecutan sobre ellos se ejecutan al mismo tiempo, aunque solo una o unas pocas tareas se estén ejecutando en un momento dado debido a la limitaciones del hardware en el que se ejecuta el sistema operativo. Esta multitarea es bastante sencilla cuando todas las tareas son independientes entre sí. Sin embargo, cuando varias tareas intentan utilizar el mismo recurso, o cuando las tareas intentan compartir información, puede generar confusión e inconsistencia. La tarea de la computación concurrente es resolver ese problema. Algunas soluciones implican "bloqueos" similares a los utilizados en las bases de datos, pero corren el riesgo de causar sus propios problemas, como un punto muerto . Otras soluciones son los algoritmos sin bloqueo y la lectura, copia y actualización .