Exclusio mutua
(comunament abreujada com
mutex
per
mutual exclusion
), es una expressio utilitzada en
programacio concurrent
que fa referencia al fet d'evitar l'acces simultani de dos fragments de codi a un recurs compartit (per exemple una cua, un comptador, etc.). Aixi, aquests fragments de codi (
seccions critiques
) s'han d'
excloure mutuament
per no provocar inconsistencies en les dades que estan actualitzant.
En general, es necessari disposar de mecanismes adequats per garantir acces exclusiu en sistemes
multitasca
on diversos
fils d'execucio
poden intentar accedir a un recurs al mateix temps, o tambe en recursos que poden accedits en context d'interrupcio de la
CPU
.
La major part d'aquests recursos son els senyals, comptadors, cues i altres dades que s'empren en la comunicacio entre el codi que s'executa quan es dona servei a una
interrupcio
i el codi que s'executa la resta del temps. Es tracta d'un problema de vital importancia perque, si no es prenen les precaucions degudes, una interrupcio pot passar entre dues instruccions qualssevol del codi normal i aixo pot provocar greus errors.
La tecnica que s'utilitza normalment per aconseguir l'exclusio mutua es inhabilitar les
interrupcions
durant el conjunt d'instruccions mes petit que impedira la corrupcio de l'estructura compartida (la seccio critica). Aixo impedeix que el codi de la interrupcio s'executi al mig de la seccio critica.
En un sistema
multiprocessador
de memoria compartida, es fa servir l'operacio indivisible
test-and-set
sobre una bandera, per esperar fins que l'altre processador la rebutgi. L'operacio test-and-set realitza les dues operacions sense alliberar el bus de memoria a un altre processador. Aixi, quan el codi deixa la seccio critica, s'aclareix la bandera. Aixo es coneix com a
spin lock
o
espera activa
.
Alguns sistemes tenen instruccions multioperacio indivisibles similars a les anteriorment descrites per manipular les
llistes enllacades
que s'utilitzen per a les cues d'esdeveniments i altres
estructures de dades
que els
sistemes operatius
fan servir comunament.
La majoria dels metodes d'exclusio mutua classics intenten reduir la latencia i espera activa mitjancant les cues i
canvis de context
. Alguns investigadors afirmen que les proves indiquen que aquests algorismes especials perden mes temps del que estalvien.
Malgrat tot el que s'ha dit, moltes tecniques d'exclusio mutua tenen efectes col·laterals. Per exemple, els
semafors
permeten interbloquejos (
deadlocks
) en que un proces obte un semafor, un altre proces obte el semafor i tots dos es queden a l'espera que l'altre proces alliberi el semafor. Altres efectes comuns inclouen la
inanicio
, en el qual un proces essencial no s'executa durant el temps desitjat, i la
inversio de prioritats
, en el qual una tasca de prioritat elevada espera per altra tasca de menor prioritat, aixi com la
latencia alta
en que la resposta a les interrupcions no es immediata.
La major part de la investigacio actual en aquest camp, preten eliminar els efectes anteriorment descrits. Si be no hi ha un esquema perfecte conegut, hi ha un interessant esquema no classic d'enviament de missatges entre fragments de codi que, tot i que permet inversions de prioritat i produeix una major latencia, impedeix els interbloquejos.
Els
algorismes
d'exclusio mutua que s'usen en
programacio concurrent
per a evitar l'us simultani de recursos comuns, com a variables globals, per fragments de codi coneguts com a seccions critiques.
Una forma habitual de garantir exclusio mutua en sistemes
uni-processador
es deshabilitar les interrupcions a l'entrada de la seccio critica i habilitar-les a la sortida. Aquesta solucio, permet que mentre s'accedeix al recurs no hi hagi
canvis de context
deguts a una interrupcio. En sistemes multi-processador de memoria compartida (per exemple
SMP
) s'utilitza una operacio atomica anomenada
test-and-set
, que permet comprovar l'estat d'una adreca de memoria i actualitzar el seu valor en un sol pas (sense alliberar el bus de memoria). Aixi, el processador que vulgui accedir al recurs compartit entrara en
espera activa
fins que processador que en aquell moment utilitza el recurs l'alliberi i reinicii el valor d'una variable (aquesta tecnica s'anomena
spinlock
).
La majoria de les solucions estan encaminades maximitzar l'eficiencia en l'us del processador, evitant en la mesura del possible efectes no desitjats tals com
l'interbloqueig
, la
inanicio
de recursos o la
inversio de prioritat
.
Pel que fa a programari, existeixen multiples solucions per garantir exclusio mutua. Per exemple:
Alguns exemples d'algorismes classics d'exclusio mutua son:
.