Wederzijdse uitsluiting
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.
Oplossingen bewerken
Er zijn zowel hardware- als softwareoplossingen voor het bereiken van wederzijdse uitsluiting. De verschillende mogelijkheden worden hieronder toegelicht.
Hardwareoplossingen bewerken
Interruptblokkering bewerken
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 efficiëntie van de lopende programma's nadelig beïnvloeden. 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.
Machine-instructies bewerken
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 één 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 één 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.
Softwareoplossingen bewerken
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.
Geavanceerde oplossingen bewerken
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.
Bronvermelding bewerken
- William Stallings: Operating Systems, Pearson Education, ISBN 90-430-0985-7