Interbloqueo

	Instancia de situación; debilidade de seguridade; tipo de erro; causa de fallo; patrón de concurrencia; CWE weakness (en)
	Subclase de erro; risco procesal; bug
	Parte de Q18019258
	Aspecto de sistema operativo
	Estudado por programación paralela

Interbloqueo
	Instancia de situación; debilidade de seguridade; tipo de erro; causa de fallo; patrón de concurrencia; CWE weakness (en)
	Subclase de erro; risco procesal; bug
	Parte de Q18019258
	Aspecto de sistema operativo
	Estudado por programación paralela
Freebase
Códigos e identificadores
Freebase
Freebase	/m/0qcdj
OpenAlex	C159023740
	Wikidata

Un interbloqueo (tamén coñecido como bloqueo mutuo ou deadlock), en programación concorrente, é calquera situación onde un conxunto de entidades non pode continuar porque cada membro do conxunto espera a outro membro del para continuar^[1].

No contexto dos sistemas operativos, os interbloqueos ocorren cando un proceso ou fío ocorre entra nun estado de espera porque un recurso do sistema está sendo usado por outro proceso, que espera un recurso que está usando o primeiro (considerando un conxunto de dous procesos).

Condicións

Un interbloqueo sobre un recurso só pode xorder se todas as seguintes condicións se cumpren simultaneamente sobre un sistema. Doutro xeito, se unha delas non se cumpre, o sistema estará libre de interbloqueos.

As tres primeiras condicións caracterizan un modelo de sistema, mentres que a última é o interbloqueo propiamente dito.

Condición de exclusión mutua. O acceso aos recursos é exclusivo: nun momento dado, cada recurso está asignado a un único proceso ou está libre.
Condición de contención e espera. Os procesos aos que lle foron outorgados recursos poden solicitar novos recursos e bloquearse esperando por eles.
Condición de non apropiativa. Os recursos xa asignados a procesos non poden ser quitados á forza, senón que deben ser liberados de xeito explícito polo proceso que os posúe.
Condición de espera circular. Hai un conxunto de procesos, P = {P₁, P₂, …, P_n} de xeito que P₁ espera por un recurso que P₂ posúe, P₂ espera por un recurso que P₃ posúe e así sucesivamente ata que P_n está esperando un recurso que P₁ posúe.

Estas catro condicións coñécense como condicións de Coffman debido á súa primeira descrición nun artigo publicado por Edward G. Coffman, Jr. en 1971^[2].

Representación de interbloqueos usando grafos

Os interbloqueos poden ser representados usando grafos dirixidos, onde o proceso é representado por un cadrado e o recurso, por un círculo. Cando un proceso solicita un recurso, unha frecha é dirixida dende o proceso ao recurso. En cambio, cando un recurso é asignado a un proceso, unha frecha é dirixida dende o recurso ao proceso.

Na figura do exemplo, poden verse dous procesos diferentes (A e B) que posúen cadanseu recurso asignado (R₁ e R₂, respectivamente). Neste exemplo clásico de bloqueo mutuo, vese con facilidade a condición de espera circular na que cada proceso implicado solicita un recurso que está asignado a outro proceso.

Este tipo de grafos son útiles para detectar interbloqueos cando hai un único recurso de cada tipo, tal e como se reflicte no algoritmo de grafos de asignación de recursos.

Xestión de interbloqueos

A meirande parte dos sistemas operativos non son capaces de prever os interbloqueos.^[3] En liñas xerais, existen catro xeitos de xestionar os interbloqueos nun sistema operativo.

Ignorar os interbloqueos

A estratexia máis simple para o tratamento dos interbloqueos, coñecida como algoritmo da avestruz, é ignoralo^[4]. Os defensores desta alternativa sinalan que a frecuencia deste tipo de eventos é baixa de máis como para sobrecargar a CPU con códigos extra. Foi un enfoque usado inicialmente por MINIX e UNIX^[5].

Detectar interbloqueos e recuperar o sistema

Baixo a detección de interbloqueos, os interbloqueos poden ocorrer. Para aplicar esta estratexia, empréganse estruturas de datos para almacenar a relación entre os procesos e os recursos do sistema. A idea é usar estas estruturas para detectar interbloqueos e, no caso de que existan, recuperar o sistema.

Se existe un recurso de cada tipo, pode manterse un grafo como o que se describiu anteriormente e buscar ciclos nel para detectar interbloqueos.

Se existen varios recursos de cada tipo, existe un algoritmo específico deseñado para esta situación. Daquela, vexamos como funciona este algoritmo.

Detección de interbloqueos con varios recursos de cada tipo

O algoritmo de detección de interbloqueos con varios recursos de cada tipo pódese empregar en situacións nas que se posúan varios recursos de cada tipo e os procesos soliciten unicamente o tipo de recurso que desexan usar, sen especificar cal deles.

Deste xeito, un proceso pode solicitar unha unidade de CD para lectura. Se o sistema posúe dúas, o proceso usa a que estea dispoñible, sen especificar cal en concreto.

Este algoritmo precisa das seguintes estruturas de datos, sendo m a cantidade de tipos de recursos e n a cantidade de procesos activos:

o vector E = (e_i)_m, denominado vector de recursos existentes. O elemento e_i é o número de recursos do tipo i.
o vector A = (a_i)_m, denominado vector de recursos dispoñibles. O elemento a_i é o número de recursos dispoñibles (sen estar en uso por ningún proceso) do tipo i.
a matriz C = (c_ij)_nxm, denominada matriz de asignacións actuais. O elemento c_ij é o número de recursos do tipo j que ten o proceso i.
a matriz R = (r_ij)_nxm, denominada matriz de peticións. O elemento R_ij é o número de recursos do tipo j que desexa pedir o proceso i.

Nótese que estas estruturas de datos cumpren a relación $\sum _{i=1}^{n}c_{ij}+a_{j}=e_{j}$ . Noutras palabras, os recursos dun tipo que posúe o sistema son a suma dos dispoñibles máis os que están sendo usados polos procesos nun determinado momento.

Para detectar un interbloqueo, séguense os seguintes pasos:

Inicialmente, desmárcanse todos os procesos.
Búscase un proceso P_i desmarcado para o cal todos os elementos da fila i da matriz R son menores que os do vector A. Noutras palabras, búscase un proceso que poida finalizar cos recursos dispoñibles. Se non existe ningún proceso desmarcado nestas condicións, o sistema atópase nun estado de interbloqueo e o algoritmo acaba.
Este proceso márcase e especúlase co que ocorrería se finaliza, liberando os recursos que posúe actualmente, é dicir, súmase ao vector A a fila i-ésima da matriz C.
Volver ao paso 2, ata que finalicen todos os procesos.

Grosso modo, a lóxica do algoritmo é a seguinte: se se consegue marcar todos os procesos, quere dicir que se atopou un xeito de que todos os procesos finalicen e, polo tanto, o sistema non está nun estado de interbloqueo.

Cómpre destacar que o algoritmo só realiza unha comprobación sobre as estruturas de datos: en ningún momento outorga os recursos do paso 3 a ningún proceso.

Esta estratexia para detectar interbloqueos dá pé a unha pregunta: cando executar o algoritmo. Unha primeira alternativa é realizalo de xeito periódico, pero isto pode sobrecargar a CPU. Outras opcións son realizalo cando hai varios procesos bloqueados ou tras a concesión dun recurso.

Recuperación do sistema

Tras detectar un interbloqueo, débese recuperar o sistema. Preséntanse tres opcións:

Polo medio da apropiación. Consiste en retirar os recursos a un proceso e outorgarllos a outro para resolver o interbloqueo.
A través do retroceso. Baséase no almacenamento periódico do estado do sistema. Cando existe un interbloqueo, un proceso que posúe un recurso necesario para resolvelo revértese a un punto no tempo antes de que o adquirise. Todo o traballo realizado a partir dese punto debe ser descartado.
A través da eliminación de procesos. Consiste na eliminación dun proceso que poida resolver o interbloqueo sen efectos daniños.

Evitar os interbloqueos

A estratexia de evitar os interbloqueos consiste en analizar de xeito detallado a solicitude de cada recurso, para saber se a súa concesión derivará nun interbloqueo ou non. Se deriva nel, négase a concesión do recurso.

O algoritmo máis coñecido no tocante á prevención de interbloqueos é o algoritmo do banqueiro^[6]. Na realidade, o algoritmo do banqueiro é o algoritmo de detección de interbloqueos para varios recursos de cada tipo. A única diferenza é que, cando se solicita un recurso, o algoritmo do banqueiro executa o procedemento coas estruturas de datos coma se se tivese concedido o recurso, mentres que, na estratexia de detección, se executa co estado real do sistema.

Atacar unha das catro condicións

A última estratexia para tratar os interbloqueos é evitar unha das catro condicións de Coffman e colaboradores.

Evitar a exclusión mutua. Ningún proceso pode ter acceso exclusivo a ningún recurso. Pode evitarse mediante o uso de spools. Non obstante, non todos os dispositivos admiten spools e, aínda así, os interbloqueos poden ocorrer, xa que só se está trasladando o problema de lugar.
Evitar a condición de contención e espera é factible se os procesos solicitan todo o que precisan ao comezo. Porén, resulta difícil que un proceso coñeza todos os recursos que vai necesitar de antemán. Outro xeito de atacar esta condición é que, cada vez que un proceso solicite un recurso, libere os que ten e pida os que tiña máis os novos que quere. Isto tampouco é moi práctico.
Evitar a condición de non apropiativa é complicado: non sempre é posible retirar un recurso sen consecuencias, aínda que en certos casos, pode ser factible mediante a virtualización do recurso.
Evitar a espera circular pode abordarse mediante o ordenamento dos recursos, de xeito que os recursos se solicitan en orde crecente de enumeración^[3].

Livelock ou bloqueo activo

Un livelock ou bloqueo activo é unha situación na que dous ou máis procesos cambian de estado en resposta ás accións dos demais, pero ningún logra avanzar e completar a súa tarefa.^[7] É semellante a un interbloqueo pero, neste caso, os procesos non están bloqueados, senón que seguen activos nun ciclo de actividade inútil.

Exemplo de livelock

O recadro inferior recolle o código de dous procesos, A e B. Se o recurso non pode ser adquirido, a chamada á función solicitar_recurso non supón o bloqueo do proceso, senón que o proceso volve a intentalo de novo.

//Código do proceso A
   solicitar_recurso(R1);
   solicitar_recurso(R2);
    
//Código do proceso B
    solicitar_recurso(R2);
    solicitar_recurso(R1);

Supoñamos que ambos recursos están dispoñibles e que o proceso A dispón da CPU e solicita o recurso R1. Logo, o proceso A perde a CPU, que é concedida ao proceso B, que solicita o recurso R2. Agora, os procesos atópanse nun estado de livelock: cando se lles concede a CPU, pasan todo o seu quantum tentando solicitar o recurso, mais non están bloqueados.

Notas

↑ Coulouris, Dillimore, Kindberg e Blair (2012), p. 716
↑ Coffman, Elphick e Shoshani (1971)
1 2 Silberschatz, Galvin e Gagne (2006), pp. 236-237.
↑ Stuart (2009), p. 446.
↑ Shibu (2009)
↑ "Deadlock Avoidance Algorithms in Operating System (OS)". electronicsmind.com (en inglés). 26 de xaneiro de 2022. Consultado o 5 de agosto de 2025.
↑ Tanenbaum (2009), p. 460

Véxase tamén

Bibliografía

Coffman, E. G.; Elphick, M.; Shoshani, A. (1 de xuño de 1971). Association for Computing Machinery, ed. "System Deadlocks". ACM Computing Surveys (CSUR) (en inglés) (Nova York) 3 (2): 67. ISSN 0360-0300. doi:10.1145/356586.356588.
Coulouris, George; Dollimore, Jean; Kindberg, Tim; Blair, Gordon (2012). Distributed Systems Concepts and Design. (en inglés) (5ª ed.). Boston: Pearson. ISBN 978-0-13-214301-1.
Shibu, K. (2009). Intro to Embedded Systems (en inglés). Nova Delhi: Tata McGraw-Hill Education. ISBN 9781283186766.
Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2006). Operating System Principles (en inglés) (7ª ed.). Nova Delhi: Wiley-India. ISBN 978-81-265-0962-1.
Stuart, Brian L. (2009). Principles of Operating Systems: Design & Applications (en inglés). Boston: Course Technology. ISBN 9780538749534. LCCN 2008297816. OL 11791733M.
Tanenbaum, Andrew S. (2009). Sistemas operativos modernos (en castelán). México: Pearson. ISBN 978-607-442-046-3.

[1] Coulouris, Dillimore, Kindberg e Blair (2012), p. 716

[2] Coffman, Elphick e Shoshani (1971)

[:0-3] 1 2 Silberschatz, Galvin e Gagne (2006), pp. 236-237.

[4] Stuart (2009), p. 446.

[5] Shibu (2009)

[6] "Deadlock Avoidance Algorithms in Operating System (OS)". electronicsmind.com (en inglés). 26 de xaneiro de 2022. Consultado o 5 de agosto de 2025.

[7] Tanenbaum (2009), p. 460

[1]

[2]

[3]

[4]

[5]

[6]

[7]