Exclusió mútua
|
Per a altres significats, vegeu «Exclusió mútua (biologia)». |
Exclusió mútua (comunament abreujada com mutex per mutual exclusion ), és una expressió utilitzada en programació concurrent que fa referència al fet d'evitar l'accés simultani de dos fragments de codi a un recurs compartit (per exemple una cua, un comptador, etc.). Així, aquests fragments de codi (seccions crítiques) s'han d'excloure mútuament per no provocar inconsistències en les dades que estan actualitzant.
En general, és necessari disposar de mecanismes adequats per garantir accés exclusiu en sistemes multitasca on diversos fils d'execució poden intentar accedir a un recurs al mateix temps, o també en recursos que poden accedits en context d'interrupció de la CPU.
La major part d'aquests recursos són els senyals, comptadors, cues i altres dades que s'empren en la comunicació entre el codi que s'executa quan es dona servei a una interrupció i el codi que s'executa la resta del temps. Es tracta d'un problema de vital importància perquè, si no es prenen les precaucions degudes, una interrupció pot passar entre dues instruccions qualssevol del codi normal i això pot provocar greus errors.
La tècnica que s'utilitza normalment per aconseguir l'exclusió mútua és inhabilitar les interrupcions durant el conjunt d'instruccions més petit que impedirà la corrupció de l'estructura compartida (la secció crítica). Això impedeix que el codi de la interrupció s'executi al mig de la secció crítica.
En un sistema multiprocessador de memòria compartida, es fa servir l'operació indivisible test-and-set sobre una bandera, per esperar fins que l'altre processador la rebutgi. L'operació test-and-set realitza les dues operacions sense alliberar el bus de memòria a un altre processador. Així, quan el codi deixa la secció crítica, s'aclareix la bandera. Això es coneix com a spin lock o espera activa.
Alguns sistemes tenen instruccions multioperació indivisibles similars a les anteriorment descrites per manipular les llistes enllaçades que s'utilitzen per a les cues d'esdeveniments i altres estructures de dades que els sistemes operatius fan servir comunament.
La majoria dels mètodes d'exclusió mútua clàssics intenten reduir la latència i espera activa mitjançant les cues i canvis de context. Alguns investigadors afirmen que les proves indiquen que aquests algorismes especials perden més temps del que estalvien.
Malgrat tot el que s'ha dit, moltes tècniques d'exclusió mútua tenen efectes col·laterals. Per exemple, els semàfors permeten interbloquejos (deadlocks) en què un procés obté un semàfor, un altre procés obté el semàfor i tots dos es queden a l'espera que l'altre procés alliberi el semàfor. Altres efectes comuns inclouen la inanició, en el qual un procés essencial no s'executa durant el temps desitjat, i la inversió de prioritats , en el qual una tasca de prioritat elevada espera per altra tasca de menor prioritat, així com la latència alta en què la resposta a les interrupcions no és immediata.
La major part de la investigació actual en aquest camp, pretén eliminar els efectes anteriorment descrits. Si bé no hi ha un esquema perfecte conegut, hi ha un interessant esquema no clàssic d'enviament de missatges entre fragments de codi que, tot i que permet inversions de prioritat i produeix una major latència, impedeix els interbloquejos.
Algorismes
[modifica]Els algorismes d'exclusió mútua que s'usen en programació concurrent per a evitar l'ús simultani de recursos comuns, com a variables globals, per fragments de codi coneguts com a seccions crítiques.
Una forma habitual de garantir exclusió mútua en sistemes uni-processador és deshabilitar les interrupcions a l'entrada de la secció crítica i habilitar-les a la sortida. Aquesta solució, permet que mentre s'accedeix al recurs no hi hagi canvis de context deguts a una interrupció. En sistemes multi-processador de memòria compartida (per exemple SMP) s'utilitza una operació atòmica anomenada test-and-set, que permet comprovar l'estat d'una adreça de memòria i actualitzar el seu valor en un sol pas (sense alliberar el bus de memòria). Així, el processador que vulgui accedir al recurs compartit entrarà en espera activa fins que processador que en aquell moment utilitza el recurs l'alliberi i reiniciï el valor d'una variable (aquesta tècnica s'anomena spinlock).
La majoria de les solucions estan encaminades maximitzar l'eficiència en l'ús del processador, evitant en la mesura del possible efectes no desitjats tals com l'interbloqueig, la inanició de recursos o la inversió de prioritat.
Pel que fa a programari, existeixen múltiples solucions per garantir exclusió mútua. Per exemple:
- L'ús de semàfors
- L'ús de monitors
- El pas de missatges
Alguns exemples d'algorismes clàssics d'exclusió mútua són:
Vegeu també
[modifica]- Algorisme del banquer
- Cadenat d'exclusió mútua o locks
- Semàfor (inventat per Edsger Dijkstra)
- Monitor (concurrència) (inventat per C. A. R. Hoare) (sense interbloquejos)
.