Exclusió mútua: diferència entre les revisions
Contingut suprimit Contingut afegit
m Bot: substitució ’ → ', “ i ” → ", l•l → l·l, 9kg → 9 kg, km2 → km² |
Cap resum de modificació |
||
Línia 2:
En general, és necessari disposar de mecanismes adequats per garantir accés exclusiu en sistemes [[multitasca]] on diversos [[fil d'execució| 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 dóna 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 [[interrupció|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-setembre]] sobre una bandera, per esperar fins que l'altre processador la rebuig. L'operació test-and-setembre 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 [[spinlock|spin lock]] o [[espera activa]].
Alguns sistemes tenen instruccions multioperación indivisibles similars a les anteriorment descrites per manipular les [[llista enllaçada|llistes enllaçades]] que s'utilitzen per les cues d'esdeveniments i altres [[estructura de dades|estructures de dades]] que els [[sistema operatiu|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 [[canvi de context|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àfor (programació)|semàfors]] permeten interbloquejos ([[deadlock]] s) 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==
Alguns exemples d'algorismes clàssics de exclusió mútua són:
* El [[algorisme de Dekker]].
* El [[algorisme de Peterson]].
Una forma habitual de garantir exclusió mútua en sistemes [[uni-processador]] es 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 [[canvi de context|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 re-inicii el valor d'una variable (aquesta tècnica s'anomena [[spinlock]]).
| |||