Algorisme sense bloqueig
En informàtica, un algorisme s'anomena no bloqueig si la fallada o la suspensió d'algun fil no pot provocar la fallada o la suspensió d'un altre fil; [1] per a algunes operacions, aquests algorismes proporcionen una alternativa útil a les implementacions de bloqueig tradicionals. Un algorisme sense bloqueig està lliure de bloqueig si hi ha un progrés garantit a tot el sistema i sense espera si també hi ha un progrés garantit per cada fil. "No bloquejar" es va utilitzar com a sinònim de "lliure de bloqueig" a la literatura fins a la introducció de la llibertat d'obstrucció el 2003.
La paraula "no bloqueig" s'utilitzava tradicionalment per descriure xarxes de telecomunicacions que podien encaminar una connexió a través d'un conjunt de relés "sense haver de reorganitzar les trucades existents" (vegeu xarxa Clos). A més, si la central telefònica "no és defectuosa, sempre pot fer la connexió" (vegeu el commutador d'abast mínim sense bloqueig).
Motivació[modifica]
L'enfocament tradicional de la programació multifil és utilitzar bloquejos per sincronitzar l'accés als recursos compartits. Les primitives de sincronització com ara mutexs, semàfors i seccions crítiques són mecanismes pels quals un programador pot assegurar-se que determinades seccions de codi no s'executen simultàniament, si fer-ho corrompria les estructures de memòria compartida. Si un fil intenta adquirir un bloqueig que ja està subjecte a un altre fil, el fil es bloquejarà fins que el bloqueig estigui lliure.
Bloquejar un fil pot ser indesitjable per moltes raons. Una raó òbvia és que mentre el fil està bloquejat, no pot aconseguir res: si el fil bloquejat hagués estat realitzant una tasca d'alta prioritat o en temps real, seria molt indesitjable aturar-ne el progrés.
Altres problemes són menys evidents. Per exemple, determinades interaccions entre bloquejos poden provocar condicions d'error com ara bloqueig, bloqueig en directe i inversió de prioritat. L'ús de panys també implica una compensació entre el bloqueig de gra gruixut, que pot reduir significativament les oportunitats de paral·lelisme, i el bloqueig de gra fi, que requereix un disseny més acurat, augmenta la sobrecàrrega de bloqueig i és més propens a errors.A diferència dels algorismes de bloqueig, els algorismes sense bloqueig no pateixen aquests inconvenients i, a més, són segurs per utilitzar-los en controladors d'interrupcions: tot i que el fil preemptat no es pot reprendre, el progrés encara és possible sense ell. En canvi, no es pot accedir amb seguretat a les estructures de dades globals protegides per exclusió mútua en un controlador d'interrupcions, ja que el fil preemptat pot ser el que manté el bloqueig, però això es pot rectificar fàcilment emmascarant la sol·licitud d'interrupció durant la secció crítica.[2]
Implementació[modifica]
Amb poques excepcions, els algorismes que no bloquegen utilitzen primitives de lectura-modificació-escriptura atòmiques que ha de proporcionar el maquinari, la més notable de les quals és comparar i intercanviar (CAS). Les seccions crítiques gairebé sempre s'implementen utilitzant interfícies estàndard sobre aquestes primitives (en el cas general, les seccions crítiques es bloquejaran, fins i tot quan s'implementen amb aquestes primitives). A la dècada de 1990, tots els algorismes sense bloqueig s'havien d'escriure "nativament" amb els primitius subjacents per aconseguir un rendiment acceptable. No obstant això, el camp emergent de la memòria transaccional del programari promet abstraccions estàndard per escriure codi eficient no bloquejant.[3][4]
També s'ha investigat molt per proporcionar estructures de dades bàsiques com ara piles, cues, conjunts i taules hash. Això permet als programes intercanviar fàcilment dades entre fils de manera asíncrona.
A més, algunes estructures de dades que no bloquegen són prou febles per implementar-se sense primitives atòmiques especials. Aquestes excepcions inclouen:
- una memòria intermèdia FIFO d'anell d'escriptor únic d'un sol lector, amb una mida que divideix uniformement el desbordament d'un dels tipus d'enters sense signe disponibles, es pot implementar de manera incondicional amb seguretat utilitzant només una barrera de memòria.
- Lectura-copia-actualització amb un sol escriptor i qualsevol nombre de lectors. (Els lectors estan lliures d'espera; l'escriptor sol estar lliure de bloqueig, fins que necessita recuperar la memòria).
- Lectura-copia-actualització amb diversos escriptors i qualsevol nombre de lectors. (Els lectors estan lliures d'espera; en general, diversos escriptors es serialitzen amb un bloqueig i no estan lliures d'obstruccions).
Referències[modifica]
- ↑ Göetz, Brian. Java concurrency in practice (en anglès). Upper Saddle River, NJ: Addison-Wesley, 2006, p. 41. ISBN 9780321349606.
- ↑ Butler W. Lampson; David D. Redell Communications of the ACM, 23, 2, February 1980, pàg. 105–117. DOI: 10.1145/358818.358824.
- ↑ Harris, Tim; Fraser, Keir ACM SIGPLAN Notices, 38, 11, 26-11-2003, pàg. 388. DOI: 10.1145/949343.949340.
- ↑ Harris, Tim. «Composable memory transactions». A: Proceedings of the 2005 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '05 : Chicago, Illinois (en anglès). New York, NY: ACM Press, June 15–17, 2005, p. 48–60. DOI 10.1145/1065944.1065952. ISBN 978-1-59593-080-4.