En tecnología de la información y la 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 de software como de hardware , constan de módulos o componentes. Cada componente está diseñado para funcionar correctamente, es decir, para obedecer o cumplir con ciertas reglas de consistencia. Cuando los componentes que operan simultáneamente interactúan mediante mensajes o compartiendo datos a los que se accede (en la memoria o el almacenamiento ), la consistencia de un determinado componente puede ser violada por otro componente. El área general del control de concurrencia proporciona reglas, métodos, metodologías de diseño y teorías para mantener la consistencia de los componentes que operan simultáneamente mientras interactúan y, por lo tanto, la consistencia y la corrección de todo el sistema. Introducir el control de concurrencia en un sistema significa aplicar restricciones de operación que generalmente resultan en alguna reducción del rendimiento. La consistencia y la corrección de la operación deben lograrse con la mejor 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 resultar en corrupción de datos debido a operaciones de lectura o escritura interrumpidas.
Comentarios:
El control de concurrencia en 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 en red y computación en la nube ) garantiza que las transacciones de bases de datos se realicen simultáneamente sin violar la integridad de los datos de las respectivas bases de datos . Por lo tanto, el control de concurrencia es un elemento esencial para la corrección en cualquier sistema donde dos transacciones de base de datos o más, ejecutadas con superposición en el tiempo, pueden acceder a los mismos datos, por ejemplo, virtualmente en cualquier sistema de base de datos de propósito general. En consecuencia, se ha acumulado una gran cantidad 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: teoría de serialización , que permite diseñar y analizar de manera efectiva 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, de mayor alcance y ha sido menos utilizada en la literatura sobre bases de datos que la teoría clásica mencionada anteriormente. Cada teoría tiene sus pros y sus contras, énfasis y perspectivas . Hasta cierto punto son complementarias y su fusión puede ser útil.
Para garantizar la corrección, un DBMS generalmente garantiza que solo se generen programaciones de transacciones serializables , a menos que la serializabilidad se relaje intencionalmente para aumentar el rendimiento, pero solo en casos en los que la corrección de la aplicación no se vea perjudicada. Para mantener la corrección en casos de transacciones fallidas (abortadas) (lo que siempre puede suceder por muchas razones), las programaciones también deben tener la propiedad de recuperabilidad (de aborto). Un DBMS 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 mediante 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, bases de datos federadas a principios de 1990 y computación en la nube en la actualidad), 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 tanto un comportamiento bien entendido del sistema de base de datos en un entorno defectuoso donde las fallas pueden ocurrir en cualquier momento, como la recuperación de una falla a un estado bien entendido de la base de datos. Una transacción de base de datos es una unidad de trabajo, que generalmente 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 compatible con bases de datos y también con 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 (determinadas por el programador de la transacción a través de comandos de transacción especiales). Cada transacción de base de datos obedece 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 hasta convertirse en transacciones comerciales que realmente implementan tipos de flujo de trabajo y no son atómicas. Sin embargo, estas transacciones mejoradas también 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 concurrencia de transacciones. Sin embargo, si se permiten transacciones simultáneas con operaciones intercaladas de manera no controlada, pueden producirse algunos resultados inesperados e indeseables, 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, estos sistemas no pueden proporcionar resultados correctos ni mantener sus bases de datos consistentes.
Las principales categorías de mecanismos de control de concurrencia son:
Las distintas categorías ofrecen distintos rendimientos, es decir, distintas tasas promedio de finalización de transacciones ( rendimiento ), según la combinación de tipos de transacciones, el nivel de paralelismo computacional y otros factores. Si se dispone de la posibilidad de elegir y conocer las ventajas y desventajas, se debe elegir la categoría y el método que ofrezcan el mayor rendimiento.
El bloqueo mutuo entre dos transacciones (donde cada una bloquea a la otra) o más da como resultado un interbloqueo , donde las transacciones involucradas se estancan y no pueden llegar a 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 interbloqueo), y su reinicio y re-ejecución inmediatos. La probabilidad de un interbloqueo es típicamente baja.
Los bloqueos, los puntos muertos y los abortos resultan en una reducción del rendimiento y, por lo tanto, en compensaciones entre las categorías.
Existen muchos métodos para el control de concurrencia. La mayoría de ellos se pueden implementar dentro de cualquiera de las categorías principales mencionadas anteriormente. 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 fuerte 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 se pueden generar mediante este mecanismo, es decir, estas programaciones SS2PL (o Rigorous) tienen la propiedad SS2PL (o Rigorousness).
Los mecanismos de control de concurrencia deben funcionar en primer lugar 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 quedan fuera del alcance de este documento) 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 cada vez más la necesidad de funcionar de manera efectiva mientras las transacciones se distribuyen entre procesos , computadoras y redes de computadoras . Otros temas que pueden afectar el control de concurrencia son la recuperación y la replicación .
Para la corrección, 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 serializabilidad de una programación significa equivalencia (en los valores de la base de datos resultantes) con alguna programación serial con las mismas transacciones (es decir, en la que las transacciones son secuenciales sin superposición en el tiempo y, por lo tanto, completamente aisladas entre sí: no es posible el acceso simultáneo por parte de dos transacciones cualesquiera 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 serialización relajadas y comprometidas para un mejor rendimiento (por ejemplo, el popular mecanismo de aislamiento Snapshot ) o para cumplir con los requisitos de disponibilidad en sistemas altamente distribuidos (consulte Consistencia eventual ), pero solo si la corrección de la aplicación no se ve violada por la relajación (por ejemplo, no se permite relajación para las transacciones de dinero , ya que por relajación el dinero puede desaparecer o aparecer de la nada).
Casi todos los mecanismos de control de concurrencia implementados logran serializabilidad al proporcionar serializabilidad de conflictos , un caso especial amplio de serializabilidad (es decir, cubre, habilita la mayoría de los programas serializables y no impone restricciones adicionales significativas que provoquen demoras) que se puede implementar de manera eficiente.
El control de concurrencia normalmente también asegura la propiedad de recuperabilidad de las programaciones para mantener la corrección en casos de transacciones abortadas (lo que siempre puede suceder por muchas razones). La recuperabilidad (de un aborto) significa que ninguna transacción confirmada en una programación ha leído datos escritos por una transacción abortada. Dichos datos desaparecen de la base de datos (al abortar) y son partes de un estado de base de datos incorrecto. La lectura de dichos datos viola la regla de consistencia de ACID. A diferencia de la serialización, la recuperabilidad no se puede comprometer ni relajar 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 de mecanismos para admitir la recuperabilidad. Un caso especial de recuperabilidad comúnmente utilizado es Strictness , que permite una recuperación eficiente de la base de datos tras un fallo (pero excluye las implementaciones optimistas).
Con el rápido desarrollo tecnológico de la informática, la diferencia entre la informática local y distribuida en redes o buses de baja latencia se está difuminando. Por lo tanto, es común la utilización bastante efectiva de técnicas locales en dichos entornos distribuidos, por ejemplo, en clústeres de computadoras y procesadores multinúcleo . Sin embargo, las técnicas locales tienen sus limitaciones y utilizan multiprocesos (o subprocesos) respaldados por multiprocesadores (o multinúcleos) para escalar. Esto a menudo convierte las transacciones en distribuidas, si es que ellas mismas necesitan abarcar multiprocesos. En estos casos, la mayoría de las técnicas de control de concurrencia local no escalan bien.
Todos los sistemas son propensos a fallas y es imprescindible gestionar la recuperación de fallas. Las propiedades de los cronogramas generados, que están dictadas 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 Capacidad de recuperación anterior) suele ser deseable para una recuperación eficiente.
Para lograr una alta disponibilidad, los objetos de la base de datos suelen replicarse . 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 (p. ej., 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 realmente se estén ejecutando en un momento dado debido a las limitaciones del hardware en el que se ejecuta el sistema operativo. Este tipo de multitarea es bastante simple 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 bloqueos utilizados en las bases de datos, pero corren el riesgo de causar problemas propios, como el bloqueo mutuo . Otras soluciones son los algoritmos sin bloqueo y los algoritmos de lectura-copia-actualización .