Wederzijdse uitsluiting
(Engels:
mutual exclusion
of
mutex
) is een term uit de
informatica
waarmee de eis bedoeld wordt dat wanneer een
proces
zich in een
kritieke sectie
bevindt en er gebruikgemaakt wordt van gedeelde bronnen, er geen andere processen zijn die zich ook in een kritieke sectie bevinden waarbij dezelfde gedeelde bronnen worden gebruikt.
Voorbeelden van gedeelde bronnen zijn
vlaggen
,
tellers
of
queues
die gebruikt worden om te communiceren tussen verschillende
processen
of
threads
. Het regelen van de toegang tot gedeelde bronnen is een probleem in de computerwetenschappen. Dit komt doordat
threads
op eenieder willekeurig moment kunnen starten of stoppen.
Er zijn zowel hardware- als softwareoplossingen voor het bereiken van wederzijdse uitsluiting. De verschillende mogelijkheden worden hieronder toegelicht.
Op een systeem met slechts een
processor
kan wederzijdse uitsluiting worden bereikt door het tijdelijk uitschakelen van het
interruptmechanisme
. Interrupts worden gebruikt bij de
scheduling
van
threads
en zijn verantwoordelijk voor het onderbreken van lopende processen. Als er geen interrupts kunnen plaatsvinden tijdens het uitvoeren van de
kritieke sectie
, dan kunnen we de wederzijdse uitsluiting garanderen.
Het nadeel van deze aanpak is dat het
schedulingmechanisme
tijdelijk wordt verstoord. Dit kan de efficientie van de lopende programma's nadelig beinvloeden. Deze methode is niet geschikt voor multiprocessors, omdat de verschillende processors onafhankelijk werken en er geen interruptcommunicatie tussen de processors plaatsvindt. We kunnen niet verhinderen dat de verschillende processors afzonderlijke processen uitvoeren die tevens gebruikmaken van dezelfde gedeelde bronnen.
Op een multiprocessorsysteem delen verschillende processors toegang tot eenzelfde geheugen. Hier kan wederzijdse uitsluiting worden bereikt door gebruik te maken van atomaire instructies, die in een klokcyclus uitgevoerd worden. Een atomaire instructie kan niet onderbroken worden, waardoor de wederzijdse uitsluiting gegarandeerd is.
De meest gebruikte atomaire instructies voor wederzijdse uitsluiting:
Test-and-set
wordt gebruikt om een vlag in te stellen, bij aanvang van de kritieke sectie, waarmee het gebruik van een gedeelde bron kan worden aangetoond. Met dezelfde instructie kan een lus worden gemaakt om de waarde van de vlag te testen. Dit noemt men "
busy waiting
". Als de kritieke sectie voorbij is, wordt de vlag vrijgegeven.
Compare-and-swap
wordt gebruikt om in een bewerking een waarde in een datastructuur te wijzigen.
Het voordeel van het gebruik van machine-instructies is dat deze methode werkt voor zowel uni- als multiprocessors. Deze benadering kan worden gebruikt voor de ondersteuning van meerdere kritieke secties door het gebruik van meerdere vlaggen.
Het nadeel van deze aanpak is dat een "busy-wait" mogelijk is waarbij er processortijd verloren gaat tijdens het wachten op een gedeelde bron. Omdat deze methode het
schedulingalgoritme
verstoort, is het mogelijk dat er
uithongering
of
deadlocks
ontstaan.
Er zijn ook softwareoplossingen voor het bekomen van wederzijdse uitsluiting.
Volgende algoritmen maken gebruik van "
busy waiting
" en gaan ervan uit dat geheugenoperaties
sequentieel
worden doorlopen.
Door gebruik te maken van complexere systemen, kunnen we ook wederzijdse uitsluiting bekomen:
Veel vormen van wederzijdse uitsluiting hebben neveneffecten, zoals de mogelijkheid op deadlocks of een grote responstijd.