Interbloqueig

Quatre processos (línies blaves) competeixen per un recurs (cercle gris), seguint una política de dreta-abans que-esquerra. Un bloqueig mutu apareix quan tots els processos bloquegen el recurs simultàniament (línies negres). El bloqueig es pot resoldre trencant la simetria.

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 el següent exemple, dos processos competeixen per dos recursos que necessiten per funcionar, que només poden ser utilitzats per un procés alhora. El primer procés obté el permís d'utilitzar un dels recursos (adquireix el lock sobre aquest recurs). El segon procés pren el lock de l'altre recurs, i després intenta utilitzar el recurs ja utilitzat pel primer procés, per tant queda en espera. Quan el primer procés al seu torn intenta utilitzar l'altre recurs, es produeix un interbloqueig, on els dos processos esperen l'alliberament de el recurs que utilitza l'altre procés.

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 ₀ 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

Exemple de representació de Bloqueig Mutu en grafs d'al·locació de recursos amb dos processos A i B , i dos recursos R1 i R2 .

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)

Bibliografia

• Zhou, M.C.; Fanti, M.P.. Deadlock Resolution in Computer-Integrated Systems. CRC Press, 2018. ISBN 978-1-4822-7653-4. 
• 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"