Interbloqueig

Un interbloqueig, també conegut com a deadlock, abraçada mortal o bloqueig mutu és una situació on dues o més accions s'esperen mútuament, incapaces de seguir fins que les altres no acabin, i, per tant, cap d'elles no acaba mai. Apareix sovint en les paradoxes, com el sopar de filòsofs.

Tots els interbloquejos sorgeixen de necessitats que no poden ser satisfetes, per part de dos o més processos. A la vida real, un exemple pot ser el de dos nens que intenten jugar amb un arc i una fletxa, un pren l'arc, l'altre la fletxa. Cap dels dos pot jugar fins que un d'ells no alliberi el que ha agafat a l'altre.

Informàtica 

En sistemes operatius, és el bloqueig permanent de dos o més processos o fils d'execució en un sistema concurrent que competeixen per recursos de sistema o bé es comuniquen entre ells. A diferència d'altres problemes de concurrència de processos, no hi ha una solució general per als interbloquejos.

En el context de bases de dades, es refereix a la possibilitat d'una espera infinita quan un SGBD fa el control de concurrència mitjançant un sistema de reserves. Les abraçades mortals són un problema habitual de concurrència, on diversos processos comparteixen un tipus específic de recurs mutualment exclusiu anomenat mutex. Són especialment problemàtiques perquè no hi ha una solució general per a resoldre abraçades mortals.

Condicions necessàries 
També conegudes com a condicions de Coffman per la seva primera descripció en 1971 en un article escrit per EG Coffman.

Aquestes condicions s'han de complir simultàniament i no són totalment independents entre elles.

Siguin els processos P 0, P 1,. . ., P n i els recursos R 0, R 1,. . ., R m :

 Condició d'exclusió mútua: existència d’almenys un recurs compartit pels processos, al qual només pot accedir un simultàniament.
 Condició de retenció i espera: almenys un procés P i ha adquirit un recurs R i, i el reté mentre espera a l'almenys un recurs R j que ja ha estat assignat a un altre procés.
 Condició de no expropiació: els recursos no poden ser expropiats pels processos, és a dir, els recursos només podran ser alliberats voluntàriament pels seus propietaris (el sistema operatiu no pot llevar-li un recurs al procés).
 Condició d'espera circular: donat el conjunt de processos P 0. . . P m (subconjunt del total de processos original), P 0 està esperant un recurs adquirit per P 1, que està esperant un recurs adquirit per P 2, ..., que està esperant un recurs adquirit per P m, que està esperant un recurs adquirit per P 0. Aquesta condició implica la condició de retenció i espera.

Evitar interbloquejos 
Els interbloquejos poden evitar-se si tenim certa informació a priori sobre el bloqueig dels recursos. Per cada petició de bloqueig el sistema pot comprovar si el fet d'assignar el recurs al procés que el demana durà el sistema a un estat insegur, entenent com a estat insegur aquell on l'interbloqueig és possible. Si tenim, doncs, la capacitat de fer aquesta comprovació, el sistema només assignarà un recurs quan aquesta assignació mantingui el sistema en un estat segur. Tanmateix, en molts sistemes no és possible saber d'antuvi si un estat és segur o insegur, i per tant no tenim un algorisme genèric per a evitar abraçades mortals.

Prevenció d'abraçades mortals 
Podem prevenir l'aparició d'abraçades mortals assegurant que una de les quatre condicions d'abans no succeeix. D'aquestes condicions la que habitualment és més senzilla d'evitar és l'espera circular: podem imposar un ordre en l'adquisició de recursos, de tal manera que no puguin produir-se esperes circulars.

Detecció d'abraçades mortals 
A vegades no és possible de prevenir ni evitar les abraçades mortals. En aquests casos s'empra un algorisme de detecció d'abraçades mortals, que cerca esperes circulars i mata un o més dels processos involucrats per a desfer l'interbloqueig.

Representació de bloquejos mutus usant grafs 
El Bloqueig mutu també pot ser representat usant grafs dirigits, on el procés és representat per un cercle i el recurs, per un quadrat. Quan un procés sol·licita un recurs, una fletxa és dirigida des del procés al recurs. En canvi, quan un recurs està assignat a un procés, una fletxa és dirigida del recurs al procés.

A la figura de l'exemple, es poden veure dos processos diferents (A i B), cadascun amb un recurs diferent assignat (R1 i R2). En aquest exemple clàssic de bloqueig mutu, és fàcilment visible la condició d'espera circular en què els processos es troben, on cadascun sol·licita un recurs que està assignat a un altre procés.

Livelock  o atzucac viu 
Un atzucac viu o  livelock  és similar a un  deadlock , excepte que els estats dels dos processos implicats en el livelock  canvien constantment l'un respecte a l'altre. El  livelock  és una forma d'inanició (informàtica) encara que la definició general de l'error només especificarà que un procés determinat no s'està processant.

El terme va ser encunyat per Edward A. Ashcroft en un document de 1975  en relació amb un examen dels sistemes de reserva de companyies aèries. Livelock és un cas especial de fam de recursos; la definició general només estableix que un procés específic no progressa.

En un exemple del món real, un  livelock  passa per exemple quan dues persones, es troben en un passadís estret avançant en sentits oposats, i cadascuna tracta de ser amable movent-se a un costat per deixar passar l'altra persona, però acaben movent-se de costat a costat totes dues sense aconseguir res, ja que ambdues es mouen cap al mateix costat al mateix temps.

Livelock és un risc amb alguns algoritmes que detecten i es recuperen del deadlock. Si s’actua més d’un procés, es pot activar repetidament l'algorisme de detecció de deadlock. Això es pot evitar assegurant-se que només un procés (escollit a l'atzar o per prioritat) actuï.

Vegeu també 
 Algorisme del banquer (ideat per Edsger Dijkstra)
 Cadenats d'exclusió mútua o locks
 Semàfor (ideat per Edsger Dijkstra)
 Monitor (concurrència) (inventat per C. A. R. Hoare) (sense interbloquejos)

Referències

Bibliografia 
 
 Kaveh, Nima; Emmerich, Wolfgang Falta indicar la publicació [London].
 Bensalem, Saddek. Confirmation of deadlock potentials detected by runtime analysis. ACM, 2006, p. 41–50. DOI 10.1145/1147403.1147412. ISBN 978-1595934147.
 Coffman, Edward G., Jr.; Elphick, Michael J.; Shoshani, Arie ACM Computing Surveys, 3, 2, 1971, pàg. 67–78. DOI: 10.1145/356586.356588.
 Mogul, Jeffrey C.; Ramakrishnan, K. K. ACM Transactions on Computer Systems, 15, 3, 1997, pàg. 217–252. DOI: 10.1145/263326.263335. ISSN: 0734-2071.
 Havender, James W. IBM Systems Journal, 7, 2, 1968, pàg. 74. DOI: 10.1147/sj.72.0074.
 Holliday, JoAnne L.; El Abbadi, Amr Encyclopedia of Distributed Computing [Consulta: 29 December 2004].
 Knapp, Edgar ACM Computing Surveys, 19, 4, 1987, pàg. 303–328. DOI: 10.1145/45075.46163. ISSN: 0360-0300.
 Ling, Yibei; Chen, Shigang; Chiang, Jason IEEE Transactions on Computers, 55, 9, 2006, pàg. 1178–1187. DOI: 10.1109/tc.2006.151.

Enllaços externs 
 "Advanced Synchronization in Java Threads" by Scott Oaks and Henry Wong
 Deadlock Detection Agents
 DeadLock at the Portland Pattern Repository
 Etymology of "Deadlock"

Programació
Bases de dades