Bloqueo (informática)

En informática , un bloqueo o mutex (de mutual exclusion ) es una primitiva de sincronización que impide que varios subprocesos de ejecución modifiquen o accedan a un estado a la vez. Los bloqueos aplican políticas de control de concurrencia de exclusión mutua y, con una variedad de métodos posibles, existen múltiples implementaciones únicas para diferentes aplicaciones.

En general, los bloqueos son bloqueos consultivos , en los que cada subproceso coopera adquiriendo el bloqueo antes de acceder a los datos correspondientes. Algunos sistemas también implementan bloqueos obligatorios , en los que intentar acceder sin autorización a un recurso bloqueado forzará una excepción en la entidad que intente realizar el acceso.

El tipo de bloqueo más simple es un semáforo binario . Proporciona acceso exclusivo a los datos bloqueados. Otros esquemas también proporcionan acceso compartido para leer datos. Otros modos de acceso ampliamente implementados son el exclusivo, el de intención de exclusión y el de intención de actualización.

Otra forma de clasificar los bloqueos es por lo que sucede cuando la estrategia de bloqueo impide el progreso de un hilo. La mayoría de los diseños de bloqueo bloquean la ejecución del hilo que solicita el bloqueo hasta que se le permite acceder al recurso bloqueado. Con un spinlock , el hilo simplemente espera ("gira") hasta que el bloqueo esté disponible. Esto es eficiente si los hilos están bloqueados por un corto tiempo, porque evita la sobrecarga de la reprogramación de procesos del sistema operativo. Es ineficiente si el bloqueo se mantiene durante mucho tiempo o si el progreso del hilo que mantiene el bloqueo depende de la preempción del hilo bloqueado.

Los bloqueos suelen requerir soporte de hardware para una implementación eficiente. Este soporte suele adoptar la forma de una o más instrucciones atómicas , como " test-and-set ", " fetch-and-add " o " compare-and-swap ". Estas instrucciones permiten que un único proceso pruebe si el bloqueo está libre y, si lo está, lo adquiera en una única operación atómica.

Las arquitecturas monoprocesador tienen la opción de utilizar secuencias ininterrumpibles de instrucciones (utilizando instrucciones especiales o prefijos de instrucciones para desactivar las interrupciones temporalmente), pero esta técnica no funciona en máquinas multiprocesador con memoria compartida. El soporte adecuado para bloqueos en un entorno multiprocesador puede requerir un soporte de hardware o software bastante complejo, con importantes problemas de sincronización .

La razón por la que se requiere una operación atómica es la concurrencia, donde más de una tarea ejecuta la misma lógica. Por ejemplo, considere el siguiente código C :

if ( lock == 0 ) { // bloqueo libre, configúrelo lock = myPID ; }        

El ejemplo anterior no garantiza que la tarea tenga el bloqueo, ya que más de una tarea puede estar probando el bloqueo al mismo tiempo. Como ambas tareas detectarán que el bloqueo está libre, ambas intentarán establecer el bloqueo, sin saber que la otra tarea también lo está estableciendo. El algoritmo de Dekker o el de Peterson son posibles sustitutos si no están disponibles las operaciones de bloqueo atómico.

El uso descuidado de los bloqueos puede dar lugar a un bloqueo mutuo o un bloqueo activo . Se pueden utilizar varias estrategias para evitar o recuperarse de los bloqueos mutuos o los bloqueos activos, tanto en tiempo de diseño como en tiempo de ejecución . (La estrategia más común es estandarizar las secuencias de adquisición de bloqueos de modo que las combinaciones de bloqueos interdependientes siempre se adquieran en un orden de "cascada" específicamente definido).

Algunos lenguajes admiten bloqueos sintácticamente. A continuación, se muestra un ejemplo en C# :

clase pública Cuenta // Este es un monitor de una cuenta { decimal privado _balance = 0 ; objeto privado _balanceLock = nuevo objeto ();               public void Deposit ( decimal amount ) { // Solo un hilo a la vez puede ejecutar esta declaración. lock ( _balanceLock ) { _balance += amount ; } }              public void Withdraw ( decimal amount ) { // Solo un hilo a la vez puede ejecutar esta declaración. lock ( _balanceLock ) { _balance -= amount ; } } }             

El código lock(this)puede generar problemas si se puede acceder a la instancia de forma pública. ^[1]

De manera similar a Java , C# también puede sincronizar métodos completos, utilizando el atributo MethodImplOptions.Synchronized. ^{[2] [3]}

[MethodImpl(MethodImplOptions.Synchronized)] public void SomeMethod () { // hacer cosas }   

Antes de familiarizarse con la granularidad de los bloqueos, es necesario comprender tres conceptos sobre ellos:

• sobrecarga de bloqueos : los recursos adicionales para usar bloqueos, como el espacio de memoria asignado para los bloqueos, el tiempo de CPU para inicializar y destruir bloqueos, y el tiempo para adquirir o liberar bloqueos. Cuantos más bloqueos use un programa, mayor será la sobrecarga asociada con el uso;
• Contención de bloqueo : esto ocurre siempre que un proceso o subproceso intenta adquirir un bloqueo mantenido por otro proceso o subproceso. Cuanto más detallados sean los bloqueos disponibles, menos probable será que un proceso o subproceso solicite un bloqueo mantenido por el otro. (Por ejemplo, bloquear una fila en lugar de toda la tabla, o bloquear una celda en lugar de toda la fila);
• punto muerto : situación en la que al menos dos tareas están esperando un bloqueo que la otra tiene. A menos que se haga algo, las dos tareas esperarán eternamente.

Existe un equilibrio entre reducir la sobrecarga de bloqueo y reducir la contención de bloqueo al elegir la cantidad de bloqueos en la sincronización.

Una propiedad importante de un bloqueo es su granularidad . La granularidad es una medida de la cantidad de datos que el bloqueo está protegiendo. En general, la elección de una granularidad gruesa (una pequeña cantidad de bloqueos, cada uno protegiendo un gran segmento de datos) da como resultado una menor sobrecarga de bloqueo cuando un solo proceso accede a los datos protegidos, pero un peor rendimiento cuando varios procesos se ejecutan simultáneamente. Esto se debe a una mayor contención de bloqueo . Cuanto más grueso sea el bloqueo, mayor será la probabilidad de que el bloqueo impida que un proceso no relacionado continúe. Por el contrario, el uso de una granularidad fina (una mayor cantidad de bloqueos, cada uno protegiendo una cantidad bastante pequeña de datos) aumenta la sobrecarga de los propios bloqueos, pero reduce la contención de bloqueo. El bloqueo granular, donde cada proceso debe mantener múltiples bloqueos de un conjunto común de bloqueos, puede crear dependencias de bloqueo sutiles. Esta sutileza puede aumentar la posibilidad de que un programador introduzca sin saberlo un punto muerto . ^{[ cita requerida ]}

En un sistema de gestión de bases de datos , por ejemplo, un bloqueo podría proteger, en orden de granularidad decreciente, parte de un campo, un campo, un registro, una página de datos o una tabla entera. La granularidad gruesa, como el uso de bloqueos de tabla, tiende a brindar el mejor rendimiento para un solo usuario, mientras que la granularidad fina, como los bloqueos de registros, tiende a brindar el mejor rendimiento para múltiples usuarios.

Los bloqueos de bases de datos se pueden utilizar como un medio para garantizar la sincronicidad de las transacciones, es decir, cuando se realiza un procesamiento de transacciones concurrente (intercalado de transacciones), el uso de bloqueos de dos fases garantiza que la ejecución concurrente de la transacción resulte equivalente a algún orden serial de la transacción. Sin embargo, los bloqueos se convierten en un desafortunado efecto secundario del bloqueo en las bases de datos. Los bloqueos se previenen al predeterminar el orden de bloqueo entre transacciones o se detectan utilizando gráficos de espera . Una alternativa al bloqueo para la sincronización de la base de datos mientras se evitan los bloqueos implica el uso de marcas de tiempo globales totalmente ordenadas.

Existen mecanismos que se emplean para administrar las acciones de varios usuarios simultáneos en una base de datos; el objetivo es evitar la pérdida de actualizaciones y las lecturas sucias. Los dos tipos de bloqueo son el bloqueo pesimista y el bloqueo optimista :

• Bloqueo pesimista : un usuario que lee un registro con la intención de actualizarlo coloca un bloqueo exclusivo en el registro para evitar que otros usuarios lo manipulen. Esto significa que nadie más puede manipular ese registro hasta que el usuario libere el bloqueo. La desventaja es que los usuarios pueden quedar bloqueados durante mucho tiempo, lo que ralentiza la respuesta general del sistema y causa frustración.

Dónde utilizar el bloqueo pesimista: se utiliza principalmente en entornos donde la contención de datos (el grado de solicitudes de los usuarios al sistema de base de datos en un momento dado) es alta; donde el costo de proteger los datos mediante bloqueos es menor que el costo de revertir las transacciones, si ocurren conflictos de concurrencia. La concurrencia pesimista se implementa mejor cuando los tiempos de bloqueo serán cortos, como en el procesamiento programático de registros. La concurrencia pesimista requiere una conexión persistente a la base de datos y no es una opción escalable cuando los usuarios interactúan con los datos, porque los registros pueden estar bloqueados durante períodos de tiempo relativamente largos. No es adecuado para su uso en el desarrollo de aplicaciones web.

• Bloqueo optimista : permite que varios usuarios concurrentes accedan a la base de datos mientras el sistema conserva una copia de la lectura inicial realizada por cada usuario. Cuando un usuario desea actualizar un registro, la aplicación determina si otro usuario ha cambiado el registro desde la última lectura. La aplicación hace esto comparando la lectura inicial guardada en la memoria con el registro de la base de datos para verificar los cambios realizados en el registro. Cualquier discrepancia entre la lectura inicial y el registro de la base de datos viola las reglas de concurrencia y, por lo tanto, hace que el sistema ignore cualquier solicitud de actualización. Se genera un mensaje de error y se le pide al usuario que inicie nuevamente el proceso de actualización. Mejora el rendimiento de la base de datos al reducir la cantidad de bloqueo necesario, lo que reduce la carga en el servidor de la base de datos. Funciona de manera eficiente con tablas que requieren actualizaciones limitadas ya que no se bloquea a ningún usuario. Sin embargo, algunas actualizaciones pueden fallar. La desventaja son los constantes fallos de actualización debido a los altos volúmenes de solicitudes de actualización de varios usuarios concurrentes, lo que puede resultar frustrante para los usuarios.

Dónde utilizar el bloqueo optimista: esto es apropiado en entornos donde hay poca contención de datos o donde se requiere acceso de solo lectura a los datos. La concurrencia optimista se utiliza ampliamente en .NET para abordar las necesidades de aplicaciones móviles y desconectadas, ^[4] donde el bloqueo de filas de datos durante períodos prolongados de tiempo sería inviable. Además, mantener los bloqueos de registros requiere una conexión persistente al servidor de base de datos, lo que no es posible en aplicaciones desconectadas.

Existen varias variaciones y refinamientos de estos tipos de bloqueo principales, con sus respectivas variaciones de comportamiento de bloqueo. Si un primer bloqueo bloquea otro bloqueo, los dos bloqueos se denominan incompatibles ; de lo contrario, los bloqueos son compatibles . A menudo, los tipos de bloqueo que bloquean las interacciones se presentan en la literatura técnica mediante una tabla de compatibilidad de bloqueos . El siguiente es un ejemplo con los tipos de bloqueo principales más comunes:

• ✔ indica compatibilidad
• X indica incompatibilidad, es decir, un caso en el que un bloqueo del primer tipo (en la columna de la izquierda) en un objeto impide que se adquiera un bloqueo del segundo tipo (en la fila superior) en el mismo objeto (por otra transacción). Un objeto normalmente tiene una cola de operaciones solicitadas (por transacciones) en espera con los respectivos bloqueos. El primer bloqueo bloqueado para la operación en la cola se adquiere tan pronto como se elimina el bloqueo de bloqueo existente del objeto, y luego se ejecuta su respectiva operación. Si un bloqueo para la operación en la cola no está bloqueado por ningún bloqueo existente (es posible la existencia de múltiples bloqueos compatibles en un mismo objeto simultáneamente), se adquiere inmediatamente.

Comentario: En algunas publicaciones, las entradas de la tabla están simplemente marcadas como "compatibles" o "incompatibles", o respectivamente "sí" o "no". ^[5]

La protección de recursos basada en bloqueos y la sincronización de subprocesos/procesos tienen muchas desventajas:

• Contención: algunos subprocesos o procesos tienen que esperar hasta que se libere un bloqueo (o un conjunto completo de bloqueos). Si uno de los subprocesos que mantiene un bloqueo muere, se detiene, se bloquea o entra en un bucle infinito, otros subprocesos que esperan el bloqueo pueden esperar indefinidamente hasta que se apague y encienda la computadora .
• Gastos generales: el uso de bloqueos agrega gastos generales por cada acceso a un recurso, incluso cuando las posibilidades de colisión son muy escasas. (Sin embargo, cualquier posibilidad de que se produzcan tales colisiones constituye una condición de carrera ).
• Depuración: los errores asociados con los bloqueos dependen del tiempo y pueden ser muy sutiles y extremadamente difíciles de replicar, como los bloqueos .
• Inestabilidad: el equilibrio óptimo entre la sobrecarga de bloqueo y la contención de bloqueo puede ser exclusivo del dominio del problema (aplicación) y sensible al diseño, la implementación e incluso a cambios arquitectónicos de bajo nivel del sistema. Estos equilibrios pueden cambiar durante el ciclo de vida de una aplicación y pueden implicar cambios tremendos para actualizar (reequilibrar).
• Componibilidad: los bloqueos solo se pueden componer (por ejemplo, administrar múltiples bloqueos simultáneos para eliminar atómicamente el elemento X de la tabla A e insertar X en la tabla B) con un soporte de software relativamente elaborado (sobrecarga) y una adherencia perfecta por parte de la programación de aplicaciones a convenciones rigurosas.
• Inversión de prioridad : un subproceso o proceso de baja prioridad que mantiene un bloqueo común puede impedir que los subprocesos o procesos de alta prioridad sigan adelante. La herencia de prioridad se puede utilizar para reducir la duración de la inversión de prioridad. El protocolo de límite de prioridad se puede utilizar en sistemas monoprocesador para minimizar la duración de la inversión de prioridad en el peor de los casos, así como para evitar el bloqueo .
• Convoying : todos los demás subprocesos deben esperar si un subproceso que mantiene un bloqueo se desprograma debido a una interrupción de un intervalo de tiempo o un error de página.

Algunas estrategias de control de concurrencia evitan algunos o todos estos problemas. Por ejemplo, un embudo o tokens serializadores pueden evitar el mayor problema: los bloqueos. Las alternativas al bloqueo incluyen métodos de sincronización no bloqueantes , como técnicas de programación sin bloqueos y memoria transaccional . Sin embargo, estos métodos alternativos a menudo requieren que los mecanismos de bloqueo reales se implementen en un nivel más fundamental del software operativo. Por lo tanto, es posible que solo liberen al nivel de aplicación de los detalles de implementación de bloqueos, y los problemas enumerados anteriormente aún deben resolverse por debajo de la aplicación.

En la mayoría de los casos, el bloqueo adecuado depende de que la CPU proporcione un método de sincronización atómica del flujo de instrucciones (por ejemplo, la adición o eliminación de un elemento en una tubería requiere que todas las operaciones contemporáneas que necesiten agregar o eliminar otros elementos en la tubería se suspendan durante la manipulación del contenido de memoria necesario para agregar o eliminar el elemento específico). Por lo tanto, una aplicación a menudo puede ser más robusta cuando reconoce las cargas que impone sobre un sistema operativo y es capaz de reconocer con elegancia el informe de demandas imposibles. ^{[ cita requerida ]}

Uno de los mayores problemas de la programación basada en bloqueos es que "los bloqueos no se componen ": es difícil combinar módulos pequeños y correctos basados ​​en bloqueos en programas más grandes igualmente correctos sin modificar los módulos o al menos conocer sus componentes internos. Simon Peyton Jones (un defensor de la memoria transaccional de software ) da el siguiente ejemplo de una aplicación bancaria: ^[6] diseña una clase Account que permite a varios clientes concurrentes depositar o retirar dinero a una cuenta, y proporciona un algoritmo para transferir dinero de una cuenta a otra.

La solución basada en bloqueo para la primera parte del problema es:

Clase Cuenta: miembro saldo: miembro entero mutex: bloqueo método deposito(n: entero) bloqueo mutex() equilibrio ← equilibrio + n mutex.desbloquear() método retirar(n: entero) depósito(−n)

La segunda parte del problema es mucho más complicada. Una rutina de transferencia que sea correcta para programas secuenciales sería

función transferir(desde: Cuenta, a: Cuenta, importe: Entero) desde.retirar(cantidad) a.depositar(cantidad)

En un programa concurrente, este algoritmo es incorrecto porque cuando un hilo está a mitad de la transferencia , otro puede observar un estado en el que se ha retirado una cantidad de la primera cuenta, pero aún no se ha depositado en la otra cuenta: el dinero ha desaparecido del sistema. Este problema solo se puede solucionar por completo colocando bloqueos en ambas cuentas antes de cambiar cualquiera de ellas, pero luego los bloqueos se deben colocar de acuerdo con un orden arbitrario y global para evitar un bloqueo:

función transferir(desde: Cuenta, hasta: Cuenta, monto: Entero) si desde < hasta // orden arbitrario en los bloqueos desde.lock() para bloquear() demás para bloquear() desde.lock() desde.retirar(cantidad) a.depositar(cantidad) desde.unlock() para desbloquear()

Esta solución se vuelve más complicada cuando hay más bloqueos involucrados y la función de transferencia necesita conocer todos los bloqueos, por lo que no se pueden ocultar .

Los lenguajes de programación varían en su soporte para la sincronización:

• Ada proporciona objetos protegidos que tienen subprogramas o entradas protegidos visibles ^[7] así como encuentros. ^[8]
• El estándar ISO/IEC C proporciona una interfaz de programación de aplicaciones (API) de exclusión mutua (bloqueos) estándar desde C11 . El estándar ISO/IEC C++ actual admite funciones de subprocesamiento desde C++11 . El estándar OpenMP es compatible con algunos compiladores y permite especificar secciones críticas mediante pragmas. La API pthread de POSIX proporciona compatibilidad con bloqueos. ^[9] Visual C++ proporciona el atributo de los métodos que se sincronizarán, pero esto es específico de los objetos COM en la arquitectura de Windows y el compilador de Visual C++ . ^[10] C y C++ pueden acceder fácilmente a cualquier función de bloqueo del sistema operativo nativo. synchronize
• C# proporciona la lockpalabra clave en un hilo para garantizar su acceso exclusivo a un recurso.
• Visual Basic (.NET) proporciona una SyncLockpalabra clave como la palabra clave de C# lock.
• Java proporciona la palabra clave synchronizedpara bloquear bloques de código, métodos u objetos ^[11] y bibliotecas con estructuras de datos seguras para la concurrencia.
• Objective-C proporciona la palabra clave @synchronized^[12] para colocar bloqueos en bloques de código y también proporciona las clases NSLock, ^[13] NSRecursiveLock, ^[14] y NSConditionLock ^[15] junto con el protocolo NSLocking ^[16] para el bloqueo también.
• PHP proporciona un bloqueo basado en archivos ^[17] así como una Mutexclase en la pthreadsextensión. ^[18]
• Python proporciona un mecanismo mutex de bajo nivel con una Lock clase del threadingmódulo. ^[19]
• El estándar ISO/IEC Fortran (ISO/IEC 1539-1:2010) proporciona el lock_typetipo derivado en el módulo intrínseco iso_fortran_envy las declaraciones lock/ unlockdesde Fortran 2008. [ ^20]
• Ruby proporciona un objeto mutex de bajo nivel y ninguna palabra clave. ^[21]
• Rust proporciona la estructura Mutex<T>^[22] . ^[23]
• El lenguaje ensamblador x86 proporciona el LOCKprefijo en ciertas operaciones para garantizar su atomicidad.
• Haskell implementa el bloqueo a través de una estructura de datos mutable llamada MVar, que puede estar vacía o contener un valor, normalmente una referencia a un recurso. Un hilo que quiere utilizar el recurso "toma" el valor de la MVar, dejándola vacía, y lo vuelve a poner cuando termina. Intentar tomar un recurso de una , vacía, MVarhace que el hilo se bloquee hasta que el recurso esté disponible. ^[24] Como alternativa al bloqueo, también existe una implementación de memoria transaccional de software . ^[25]
• Go proporciona un objeto Mutex de bajo nivel en el paquete de sincronización de la biblioteca estándar. ^[26] Se puede utilizar para bloquear bloques de código, métodos u objetos .

• Sección crítica
• Bloqueo doblemente comprobado
• Bloqueo de archivos
• Algoritmos sin bloqueos ni esperas
• Monitor (sincronización)
• Exclusión mutua
• Patrón de bloqueo de lectura/escritura

• Tutorial sobre bloqueos y secciones críticas