Bloqueo mutuo

Bloqueo mutuo

En sistemas operativos, el bloqueo mutuo (también conocido como interbloqueo, traba mortal, deadlock, abrazo mortal) es el bloqueo permanente de un conjunto de procesos o hilos de ejecución en un sistema concurrente que compiten por recursos del sistema o bien se comunican entre ellos. A diferencia de otros problemas de concurrencia de procesos, no existe una solución general para los interbloqueos.

Todos los interbloqueos surgen de necesidades que no pueden ser satisfechas, por parte de dos o más procesos. En la vida real, un ejemplo puede ser el de dos niños que intentan jugar al arco y flecha, uno toma el arco, el otro la flecha. Ninguno puede jugar hasta que alguno libere lo que tomó.

En el siguiente ejemplo, dos procesos compiten por dos recursos que necesitan para funcionar, que sólo pueden ser utilizados por un proceso a la vez. El primer proceso obtiene el permiso de utilizar uno de los recursos (adquiere el lock sobre ese recurso). El segundo proceso toma el lock del otro recurso, y luego intenta utilizar el recurso ya utilizado por el primer proceso, por lo tanto queda en espera. Cuando el primer proceso a su vez intenta utilizar el otro recurso, se produce un interbloqueo, donde los dos procesos esperan la liberación del recurso que utiliza el otro proceso.

Contenido

Representación de Bloqueos Mutuos usando grafos

Ejemplo de representación de Bloqueo Mutuo en grafos de alocación de recursos con dos procesos A y B, y dos recursos R1 y R2.

El Bloqueo mutuo también puede ser representado usando grafos dirigidos, donde el proceso es representado por un cuadrado y el recurso, por un círculo. Cuando un proceso solicita un recurso, una flecha es dirigida del círculo al cuadrado. Cuando un recurso es asignado a un proceso, una flecha es dirigida del cuadrado al círculo.

En la figura del ejemplo, se pueden ver dos procesos diferentes (A y B), cada uno con un recurso diferente asignado (R1 y R2). En este ejemplo clásico de bloqueo mutuo, es fácilmente visible la condición de espera circular en la que los procesos se encuentran, donde cada uno solicita un recurso que está asignado a otro proceso.

Condiciones necesarias

También conocidas como condiciones de Coffman por su primera descripción en 1971 en un artículo escrito por E. G. Coffman.

Estas condiciones deben cumplirse simultáneamente y no son totalmente independientes entre ellas.

Sean los procesos P0, P1, ..., Pn y los recursos R0, R1, ..., Rm:

  • Condición de exclusión mutua: existencia de al menos de un recurso compartido por los procesos, al cual sólo puede acceder uno simultáneamente.
  • Condición de retención y espera: al menos un proceso Pi ha adquirido un recurso Ri, y lo retiene mientras espera al menos un recurso Rj que ya ha sido asignado a otro proceso.
  • Condición de no expropiación: los recursos no pueden ser expropiados por los procesos, es decir, los recursos sólo podrán ser liberados voluntariamente por sus propietarios.
  • Condición de espera circular: dado el conjunto de procesos P0...Pm(subconjunto del total de procesos original),P0 está esperando un recurso adquirido por P1, que está esperando un recurso adquirido por P2,... ,que está esperando un recurso adquirido por Pm, que está esperando un recurso adquirido por P0. Esta condición implica la condición de retención y espera.

Evitando bloqueos mutuos

Los bloqueos mutuos pueden ser evitados si se sabe cierta información sobre los procesos antes de la asignación de recursos. Para cada petición de recursos, el sistema controla si satisfaciendo el pedido entra en un estado inseguro, donde puede producirse un bloqueo mutuo. De esta forma, el sistema satisface los pedidos de recursos solamente si se asegura que quedará en un estado seguro. Para que el sistema sea capaz de decidir si el siguiente estado será seguro o inseguro, debe saber por adelantado y en cualquier momento el número y tipo de todos los recursos en existencia, disponibles y requeridos. Existen varios algoritmos para evitar bloqueos mutuos:

  • Algoritmo del banquero, introducido por Dijkstra.
  • Algoritmo de grafo de asignación de recursos.
  • Algoritmo de Seguridad.
  • Algoritmo de solicitud de recursos.

Prevención

Los bloqueos mutuos pueden prevenirse asegurando que no suceda alguna de las condiciones necesarias vistas anteriormente.

  • Eliminando la exclusión mutua: ningún proceso puede tener acceso exclusivo a un recurso. Esto es imposible para procesos que no pueden ser encolados (puestos en un spool), e incluso con colas también pueden ocurrir interbloqueos.
  • La condición de posesión y espera puede ser eliminada haciendo que los procesos pidan todos los recursos que van a necesitar antes de empezar. Este conocimiento por adelantado muchas veces es imposible nuevamente. Otra forma es requerir a los procesos liberar todos sus recursos antes de pedir todos los recursos que necesitan. Esto también es poco práctico en general.
  • La condición de no expropiación puede ser también imposible de eliminar dado que un proceso debe poder tener un recurso por un cierto tiempo o el procesamiento puede quedar inconsistente.
  • La condición de espera circular es la más fácil de atacar. Se le permite a un proceso poseer sólo un recurso en un determinado momento, o una jerarquía puede ser impuesta de modo tal que los ciclos de espera no sean posibles.

Livelock

Un livelock es similar a un deadlock, excepto que el estado de los dos procesos envueltos en el livelock constantemente cambia con respecto al otro. Livelock es una forma de inanición y la definición general sólo dice que un proceso específico no está procesando.

En un ejemplo del mundo real, un livelock ocurre por ejemplo cuando dos personas, al encontrarse en un pasillo angosto avanzando en sentidos opuestos, y cada una trata de ser amable moviéndose a un lado para dejar a la otra persona pasar, pero terminan moviéndose de lado a lado sin tener ningún progreso, pues ambos se mueven hacia el mismo lado, al mismo tiempo.

Livelock es un riesgo con algunos algoritmos que detectan y recuperan los interbloqueos, pues si más de uno toma cartas en el asunto, la detección del interbloqueo puede ser disparada continuamente; pudiendo ser arreglado asegurándose que sólo un proceso (escogido al azar o por prioridad) tome acción.


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Bases de datos distribuidas — Saltar a navegación, búsqueda Una base de datos distribuida (BDD) es un conjunto de múltiples bases de datos lógicamente relacionadas las cuales se encuentran distribuidas entre diferentes sitios interconectados por una red de comunicaciones, los …   Wikipedia Español

  • Gestor transaccional — En computación, un gestor transaccional es un componente que procesa información descomponiéndola de forma unitaria en operaciones indivisibles, llamadas transacciones. Cada transacción debe finalizar de forma correcta o incorrecta como una… …   Wikipedia Español

  • Problema de la cena de los filósofos — Ilustración del problema de los filósofos cenando. El problema de los filósofos cenando es un problema clásico de las ciencias de la computación propuesto por Edsger Dijkstra en 1965 para representar el problema de la sincronización de procesos… …   Wikipedia Español

  • Elección del Consejo de Seguridad de las Naciones Unidas de 2006 — Saltar a navegación, búsqueda La Elección del Consejo de Seguridad de las Naciones Unidas de 2006 empezó el 16 de octubre de 2006 durante la 61ª sesión de la Asamblea General de las Naciones Unidas, que tuvo lugar en la Sede de la ONU en Nueva… …   Wikipedia Español

  • Condición de carrera — es una expresión usada en electrónica y en programación. Procede del inglés race condition (si bien sería mejor hablar de estado de carrera, igual que se habla de estado de espera). Múltiples procesos están en condición de carrera si el resultado …   Wikipedia Español

  • Coupling Facility — Saltar a navegación, búsqueda En las computadoras centrales de IBM, una Coupling Facility o CF es un componente de hardware que permite a más de un procesador acceder a los mismos datos. Los Sysplex Paralelos necesitan como mínimo una Couplin… …   Wikipedia Español

  • Sentido de circulación —      Conducen por la derecha.     Conducen por la izquierda …   Wikipedia Español

  • Contención de recursos — En informática, se llama contención de recursos (del inglés resource contention) a un conflicto en el acceso a un recurso compartido como RAM, unidad de disco, caché de CPU, un bus interno o un dispositivo de red. Una de las funciones básicas de… …   Wikipedia Español

  • Ataque a la flotilla de Gaza — Lugar Aguas internacionales del mar Mediterráneo Coordenadas …   Wikipedia Español

  • Wikipedia:Tablón de anuncios de los bibliotecarios/Portal/Archivo/3RR/Actual — Alertas sobre guerras de ediciones Esta sección del tablón de anuncios de los bibliotecarios sirve para alertar sobre guerras de ediciones en curso. Antes de alertar sobre una guerra de ediciones, debes tener en cuenta qué es una guerra de… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”