OS Mutexes

Hallo,

Ik ben momenteel met een softwarecursus bezig, maar hoe vaak iemand het ook uitlegt, ik snap niks van Mutexes. Maar dan ook echt niks. Ik weet dus ook niet of de manier waarop ik de vraag stel goed of slecht is. Ik hoop dat de experts hier het mij kunnen uitleggen :)

Kan iemand mij uitleggen wat nou precies een OS mutex is (zowel Pend als Post).
Het liefst in zo eenvoudig mogelijke taal, of aan de hand van een voorbeeldje. Ik leer graag, maar dit gaat momenteel mijn pet te boven.

Wij gebruiken het OS van Labrosse,
https://file.elecfans.com/web1/M00/7F/DD/pIYBAFwnEZGAcwiCAEGrbQfCqmc94…
pagina 447 o.a.

Mutexes zijn een van de tools om te voorkomen dat in een computer met meerdere processoren dingen tegelijk gebeuren die niet tegelijk mogen.

simpelere beschrijvingen kun je vinden in de wereld van spoorwegen, waar soorgelijke systemen gebruikt werden om te voorkomen dat twee treinen tegelijk op een spoor reden.

En dat is denk ik ook de enige link met hardware die ik kan maken, het heeft helemaal niets met elektronica te maken: In elektronica gebeurd alles per definitie tegelijkertijd!

Arco

Special Member

Mutex wordt bijvoorbeeld ook gebruikt om te voorkomen dat een programma meerdere keren op dezelfde PC kan worden opgestart...

Arco - "Simplicity is a prerequisite for reliability" - hard-, firm-, en software ontwikkeling: www.arcovox.com
maartenbakker

Golden Member

Het hebben van 1 of meer processoren is niet relevant, het geldt ook voor interrupts.

Als je een stuk code uitvoert dat niet twee keer gelijktijdig doorlopen mag worden (bijvoorbeeld aansturing van hardware), zet je een vlag. Als je eruit bent verwijder je de vlag. Als de vlag staat en je probeert het uit te voeren dan moet je of wachten of gelijk terugkeren.

Hoe het specifiek in jouw OS geïmplementeerd is, weet ik niet.

www.elba-elektro.nl | "The mind is a funny thing. Sometimes it needs a good whack on the side of the head to jar things loose."
Totale beginner

Golden Member

Je kan een mutex (het non-reentrant type) het best vergelijken met bv een bal (mutex) die je kan vastnemen en terugleggen op een bepaalde plaats. Je spreekt dan af dat degene die de bal vast heeft en enkel diegene die de bal vastheeft bepaalde handelingen mag uitvoeren. Met dit mechanisme kan je de toegang tot een bepaalde resource (bv. een variabele) beperken tot slechts 1 persoon (thread) tegelijkertijd.

Mutexen zijn vooral bedoeld voor multi-tasking operating systemen. Zodra je multi-tasking gebruikt krijg je last van allerlei verrassende problemen waar je tegen moet beschermen.

Een simpele voorbeeld:

code:


a = a + 1; 

Als je nu meerdere tasks hebt die allemaal bovenstaande code gebruiken dan zal dat in de meeste gevallen wel goed gaan, maar soms gaat het fout.

Stel dat proces 1 de variabele a uitleest, en dat je dan precies op dat moment een task-switch krijgt (getriggered door een timer interrupt) en proces 2 voert dezelfde code uit. Dan wordt a opgehoogd door proces 2. Even later komt proces 1 weer aan de beurt, Die had de oude waarde van a al gelezen, en gaat dan verder met de increment. Het uiteindelijke effect is dan dat beide processen een increment hebben uitgevoerd, maar de increment van proces 2 is teniet gedaan door de latere update door proces 1.

Dus dan heb je een programma dat zo heel af en toe een increment mist.

Om dat te voorkomen kun je een mutex gebruiken. Die zorgt ervoor dat process 2 niet aan dit stukje code kan beginnen voordat process 1 heeft afgemeld.

Aanvulling:

code:


   Pend(MyMutex);
   a = a + 1
   Post(MyMutex);

In bovenstaande geval kan er nog steeds een task-switch komen op een kritiek moment:
- Proces 1 begint. De mutex is vrij dus proces 1 kan verder.
- De Pend() ( uitgevoerd door proces 1) zorgt ervoor dat de mutex op slot gaat voor alle andere processen.
- Proces 1 leest a
- Task switch. Proces 2 gaat lopen.
- Maar proces 2 wordt geblocked in de Pend() en kan daar niet meer verder.
- Nieuwe task switch. Process 1 gaat verder en voltooit de increment.
- Proces 1 Post() de mutex. Die komt dan weer vrij.
- Bij de volgende task-switch kan proces 2 dan weer verder.
Resultaat: Beide increments succesvol.

[Bericht gewijzigd door deKees op woensdag 29 september 2021 16:13:02 (24%)

Op 29 september 2021 13:19:20 schreef maartenbakker:
Het hebben van 1 of meer processoren is niet relevant, het geldt ook voor interrupts.

Bij interrupts kun je het probleem van simultane toegang tot hardware (of in het algemeen, een resource) oplossen door een vlag te zetten. Geen Mutex voor nodig.

De essentie van een Mutex is juist dat je in feite drie handelingen tegelijk doet:
- Controleren dat de vlag eerst niet gezet is
- De vlag zetten
- Controleren dat de vlag daarna wel gezet is.

In een interrupt kun je die drie handelingen na elkaar doen: Niemand onderbreekt de interrupt[1]

In een multi-processor geval is dat niet zo: Twee processoren kunnen de bovenste drie stappen synchroon uitvoeren, en dan allebei denken dat ze de vlag gezet hebben.

Multi-processor-hardware heeft daarom altijd instructies die de bovenste drie handelingen atomair (ondeelbaar, in een keer) uitvoeren.

De OS Mutex is de interface die software kan gebruiken om van die instructie gebruik te maken op een gestandaardiseerde en hardware onafhankelijke manier.

@deKees:
In een multitasking OS kan de applicatiesoftware (in principe) niet zien of het systeem 1 of meer processoren heeft, het OS verbergt dat. Dus heeft de applicatiesoftware mutexen nodig.
Maar op een single-cpu systeem kan het OS die gewoon zonder moeite met een simpele vlag implementeren. Op een multi-cpu systeem niet, daar is hardware support nodig (en dit is tenslotte een hardware forum, geen software ;-) )

[1] in het geval van prioriteiten onder interrupts: De hoogste prio interrupt pakt de vlag voordat de lagere er iets mee gedaan heeft. En na voltooiing geeft de hogere de vlag natuurlijk vrij.

[Bericht gewijzigd door blurp op woensdag 29 september 2021 16:09:58 (14%)

@blurp:

Ik gebruik hier de ESP32, een dual-core processor, met Free-RTOS.
Dan heb ik zelf toch wel controle over welke processor ik gebruik. Niks hiding. Bij het starten van een nieuwe task kan ik aangeven welke core voor die task gebruikt wordt.

Free-RTOS kan ook op een simpele AVR processor.
De implementatie van die Mutex funkties zal in beide gevallen wel anders zijn. Maar daar is een bibliotheek voor.

PS,
Mutexen gebruiken in interrupts is tricky. Wat moet je doen als de mutext niet vrij is? Wachten tot die vrij komt? Dan kun je lang wachten... :) 8)7

[Bericht gewijzigd door deKees op woensdag 29 september 2021 16:24:21 (16%)

Je begrijpt er helemaal niks van?
Maar je kunt het wel goed spellen?

Mutex is een afkorting van "mutually exclusive", en de betekenis daarvan is "als ik het heb dan heb jij het niet, en als jij het hebt, dan heb ik het niet".

Stel je eens voor dat jij en je vriendin eten eten aan het koken zijn, en je stopt allebij ingredienten in een soep pan. Op een gegeven moment vraag je je af of er wel of niet genoeg groente in zit. Heeft niemand er zout bij gedaan, of hebben jullie er allebij zout bij gedaan, en als je allebij tegelijkertijd groente in de pan wilt doen dan valt de helf naast de pan.

Dat wordt dus een rommeltje.
De volgende keer spreek je met elkaar af dat je allen spul in de soep pan mag stoppen, als je ook de pollepel vast hebt.
Nu kun je eindeloos ruzzieen over wie dat de pollepel heeft, maar dat maakt voor de soep pan niet uit. (Misschien brand de soep aan als het te lang duurt?) Als een van jullie heeft gewonnen kan die verder gaan met ingredienten in de soep stoppen, en dat gaat dan orderlijk omdat maar een persoon daarmee bezig is.

En met computers werkt het ook ongeveer zo.

Op 29 september 2021 16:21:29 schreef deKees:

Mutexen gebruiken in interrupts is tricky. Wat moet je doen als de mutext niet vrij is? Wachten tot die vrij komt? Dan kun je lang wachten... :) 8)7

Dat is sowieso een probleem: Als proces 1 Mutex A heeft en wacht op Mutex B, en proces 2 heeft Mutex B en wacht op A.. De klassieke beschrijving is het dining philosophers probleem, en het is niet uniek voor mutexen.

Eigenlijk is mijn punt dat je moet begrijpen wat het onderliggende probleem is, wat het onderliggende mechanisme is om te begrijpen wat een Mutex doet.

Als je alleen maar naar de Mutex als los ding kijkt ga je gegarandeerd fouten maken met het gebruik ervan.

Lucky Luke

Golden Member

Op 30 september 2021 07:09:40 schreef blurp:
dining philosophers probleem

Filosofen aan een ronde tafel met tussen elke 2 filosofen 1 vork, ze mogen alleen eten als ze zowel in hun linker als rechterhand een vork hebben. Als ze klaar zijn met eten leggen ze hun vorken weer neer. (Met 1 filosoof en 2 vorken is dat simpel en gaat het altijd goed. Met meer filosofen zitten ze op elkaar te wachten en moet je er iets op verzinnen dat elk kan eten)

(Zoek 'm maar ergens op. Dan is het vast beter uitgelegd dan dat ik doe. Het is een leuke en het legt uit wat "deadlock" en "starvation" is.)

In plaats van filosofen en vorken kan het ook een stuk software zijn dat wacht op 2 resources. Bijvoorbeeld schrijftoegang tot een stuk geheugen (of een file) en toegang tot een communicatiebus.

Maar met 3 filosofen en 3 vorken bijvoorbeeld, kun je methoden uitdenken hoe te voorkomen dat iedereen op elkaar zit te wachten.

Probeersel 1:
Elk pakt eerst zijn linkervork, en dan de rechter. Als er een vork niet is, wachten ze. Als ze beide vorken hebben eten ze. Als ze uitgegeten zijn leggen ze de vork neer.
Resultaat: Elk pakt een linkervork en zit te verhongeren.

Probeersel 2:
Elk pakt een linkervork, dan de rechter. Als een vork er niet is, leggen ze de vork die ze al hebben weer terug. Als ze beide vorken hebben eten ze. Als ze uitgegeten zijn leggen ze de vork neer.
Resultaat:
Een helehoop gegooi met vorken, maar er wordt met wat mazzel nog wat gegeten tussendoor.

Probeersel 3:
Elk pakt een linkervork, dan de rechter. Als een vork er niet is, wachten ze een random tijd tussen 0 en 1 seconde en als ze dan de andere vork niet hebben kunnen pakken leggen ze de vork die ze al hebben weer terug. Als ze beide vorken hebben eten ze. Als ze uitgegeten zijn leggen ze de vork neer.
Resultaat:
Een helehoop gegooi met vorken, maar er wordt nog wat gegeten tussendoor.

Er was een betere methode, maar die weet ik niet meer uit mijn hoofd.
Je kunt ook de filosofen nummeren en iets maken dat lagere nummers / hogere prioriteit vorken kan afpakken van hogere nummers / lagere prioriteit. Dan wel zorgen dat elk van je filosofen een uniek nummer heeft.

Of je maakt 1 mutex, een lepel, en wie de lepel heeft mag vorken pakken.

(Het kan ook met N/2 lepels en N vorken, maar dan moet elke filosoof toegang hebben tot elke vork, en dus niet alleen tot die die links en rechts naast 'm liggen).

1-voor-1 atomic vorken pakken (2 vorken tegelijk pakken zonder dat een ander ermee vandoor kan gaan) gaat ook goed. Moeten er wel nog 2 vorken zijn en niet nog maar eentje, maar je zit tenminste niet te wachten met elk 1 vork.

Valsspelen door ze gewoon 2x zo veel vorken te geven als er filosofen zijn, mag voor het gedachte-experiment niet (Maar kan in het echt wel werken, als je inderdaad kunt garanderen dat er altijd genoeg resources zijn / de resources gewoon vast toewijst en niet deelt - een communicatiebus waar maar 1 proces aan mag zitten of gewoon vast toegewezen geheugen.)

Valsspelen door ze 1 vork extra te geven, zodat er gagarandeerd eentje kan eten die dan zijn vorken neerlegt waarna de rest aan de beurt is mocht geloof ik wel. Maar werkt in het echt niet, als je die extra resource gewoon niet hebt. Dan heb je dus alsnog de betere methode nodig. (Bijvoorbeeld de mutex/lepel)

Er is online wel betere uitleg te vinden dan dat ik hier neerzet. Je moet er eigenlijk al een plaatje bij hebben van de ronde tafel met 3 filosofen en 3 vorken tussen hen in. (Of het bestek op een hoop in het midden: 3 vorken en 1 lepel. Of 4 vorken en 2 lepels, etc. bij meer filosofen. Wie de lepel/mutex heeft mag 2 vorken uit de hoop graaien).

't is jammer dan bd.eduweb.hhs.nl offline is, via http://www.hc11.demon.nl is het ook niet meer te bereiken. Wel zijn daar de nieuwere sheets voor de Rotterdamse studenten te vinden, maar daar kan ik het minder makkelijk terugvinden. (Desondanks is het het bekijken ongetwijfeld waard. Harry Broeders is een hele goede docent.)

EDIT: zie je wel, het ging bij mij al mis zonder plaatje te tekenen met 3 filosofen en 4 vorken. Dat is dus de "valsspelen met een extra vork" optie.

Eluke.nl | handgetypt | De mens onderscheid zich van (andere) dieren door o.a. complexe gereedschappen en bouwwerken te maken. Mens zijn is nerd zijn. Blijf Maken. (Of wordt, bijvoorbeeld, cultuurhistoricus)
High met Henk

Special Member

is dit dan vrijwel hetzelfde als een semaphore of een critical section.

E = MC^2, dus de magnetische compatibiliteit doet kwadratisch mee???

is dit dan vrijwel hetzelfde als een semaphore of een critical section.

Niet helemaal. Maar het zit wel allemaal in dezelfde hoek. De Mutex wordt gebruikt om een critical section te bewaken.

En een semafoor kun je gebruiken als Mutex. Maar die kun je ook gebruiken om een task te laten wachten op een event.

Ik ben van mening dat je vaak zonder kan.

Bijvoorbeeld bij een user-proces die dingen uit een buffer haalt die er door een interrupt in gezet zijn.

Maak je dan een "aantal-karakters-in-de-buffer" variabele dan krijg je het probleem wat Dekees beschreven heeft. Klein beetje minder erg: normaliter kan een taak een interrupt niet onderbreken maar andersom zeker wel.

Als je het goed doet, hou je bij waar nieuwe karakters in de buffer er bij gezet moeten woren en waar ze er weer uitgehaald kunnen worden.

De interrupt moet na het er in zetten zijn "hier nieuwe karakters' ophogen, maar de user-taak hoeft dat ding alleen te lezen. Zolang dat lezen altijd goed gaat (OF de oude waarde OF de nieuwe), hoeft dat niet tegen mekaar beschermd te worden. Idem maar dan andersom voor de andere variabele.

Dit kan dus in z'n geheel zonder mutex of andere synchronisatieprimitieven.

Het wordt lastiger als er twee "consumers" zijn. In dit geval dus twee processen die uit die buffer kunnen lezen. m.i. krijg je dan altijd gezeik, maar goed, wat je in ieder geval niet wil is dat beide processen tegelijk dezellfde data uit de buffer kunnen lezen. voordat ze de boel updaten dat die data uit de buffer is... Dan heb je dus iets nodig.

Re: filosofen en 2 vorken: Geinig: Met de lepel: Doorgeven naar rechts zodra je kan eten. Zie je twee vorken en heb je de lepel, ga je eten, zoniet (heb je maar 1 of 0 vorken) geef je de lepel door naar rechts. Dit voorkomt niet alleen deadlock, maar ook livelock. Dat is als er wel dingen gebeuren, maar geen voortgang geboekt wordt. Stel alle filosofen zijn precies even snel. Pak vork links, pak vork rechts, zonee, leg linker vork neer en begin nu rechts. Als ze dat allemaal precies synchroon doen, krijgt niemand te eten maar het houdt ze wel bezig. :-)

four NANDS do make a NOR . Kijk ook eens in onze shop: http://www.bitwizard.nl/shop/

De essentie van een Mutex is wel iets meer dan een vlaggetje.

Als een proces de Pend() uitvoert op een Mutex die niet 'vrij' is, dan wordt de status van dat proces gewijzigd van 'Running' naar 'Pending', gevolgd door een task-switch waarbij het aanroepende proces geen cycles meer krijgt. En dat geldt voor alle processen die de Pend() uitvoeren, dus dan kunnen er meerdere processen in de wachtrij staan. Elke Mutex heeft een eigen wachtrij als het goed is.

Zodra proces 1 een Post() uitvoert dan kiest het OS één van die wachtende processen, en die krijgt dan de status 'Ready' zodat die weer meedoet bij een volgende task-switch. Als er geen proces staat te wachten, dan wordt de Mutex vrijgegeven totdat er weer een Pend() wordt uitgevoerd.

Als een proces een Pend() uitvoert op een Mutex die wel 'vrij' is, dan gaat de Mutex op slot. Het aanroepende proces blijft dan 'running' en loopt dus gewoon door.

@rew: Wat jij beschrijft is een fifo. In feite is daar geen sprake van een gedeelde resource, want hoewel zowel de producent als de consument gebruik maken van de fifo, gebruiken ze verschillende delen.

In een multi-CPU omgeving kan er uitstekend tegelijk geschreven en gelezen worden uit de fifo.

@deKees: Wat jij beschrijft is een (verstandige) actie van een multitasking OS rond Mutexen. Het is echter geen essentieel onderdeel van een Mutex.

Voor het begrip waar een mutex echt over gaat is het compleet irrelevant.

Klopt wel wat rew zegt. Je kunt Mutexen vaak vermijden. Maar ook dan moet je wel weten wat je doet.

Zolang dat lezen altijd goed gaat (OF de oude waarde OF de nieuwe)

Dit is namelijk wel een instinker. Als je een 8-bit processor hebt en je gebruikt een multi-byte variabele dan loop je het risico dat je een byte leest voordat de update door de interrupt (of proces 2) komt, en het tweede byte na de update.

Dus bij een increment van 0x01FF naar 0x0200 heb je kans dat je 0x0100 of 0x02FF leest als je pech hebt. En als je het vaak genoeg doet dan heb je vroeg of laat een keer pech.

Op een ARM zal je hier niet zo gauw last van hebben. (Of misschien toch als de variabele op een oneven adres ligt?)

Op 30 september 2021 15:41:47 schreef deKees:
Klopt wel wat rew zegt. Je kunt Mutexen vaak vermijden. Maar ook dan moet je wel weten wat je doet.

[...]

Dit is namelijk wel een instinker. Als je een 8-bit processor hebt en je gebruikt een multi-byte variabele dan loop je het risico dat je een byte leest voordat de update door de interrupt (of proces 2) komt, en het tweede byte na de update.

Dus bij een increment van 0x01FF naar 0x0200 heb je kans dat je 0x0100 of 0x02FF leest als je pech hebt. En als je het vaak genoeg doet dan heb je vroeg of laat een keer pech.

Op een ARM zal je hier niet zo gauw last van hebben. (Of misschien toch als de variabele op een oneven adres ligt?)

Goeie deKees, een FIFO werkt alleen als je read en write atomair zijn.

Aan de andere kant, ik ken geen 8-bitters die multi-CPU of privillege levels doen, dus op een 8-bitter kun je altijd de interrupts disablen voor je een variabele leest of schrijft.

Ik beken eerlijk dat ik alle antwoorden niet helemaal heb gelezen, maar dit is mijn Jip en Janneke uitleg:

Een Mutex is bedoeld om te voorkomen dat een bepaalde resource maar door 1 thread tegelijk gebruikt kan worden. Een semaphore is bedoeld om synchronisatie tussen 2 threads te doen.

Semaphore is een estafette stokje. Persoon 1 heeft het stokje vast en is dus aan het rennen. De andere personen staan te wachten tot een van hen het stokje krijgt. Pas als iemand het stokje heeft mag hij gaan rennen.

Een Semphore gebruik je om te synchroniseren tussen taken. Bijvoorbeeld taak 1 heeft data ontvangen over SPI en die heeft dat naar een buffer geschreven. Nu zegt taak 1 (dmv de semaphore) aan taak 2 dat taak 2 de gebufferde data mag gaan verwerken.

Mutex is een bezet bord voor een vergader ruimte. Als de ruimte in gebruik is door iemand dan zet hij het bordje op bezet. De andere personen moeten dan wachten tot de vergaderruimte weer vrij is.

Een mutex gebruik je om een resource te beveiligen. Bijvoorbeeld er mag maar 1 taak te gelijke tijd de SPI bus gebruiken. Als meerdere taken tegelijk zouden praten over SPI dan hoort de ontvanger een hele hoop zaken door elkaar.

Nee ze zijn niet hetzelfde
In eerste opzicht lijken deze 2 functionaliteiten enorm veel op elkaar. Echter zitten er een paar subtiele verschillen in. Bij FreeRTOS is dat bijvoorbeeld het concept "priority inheritance". Dit maakt het verhaal direct een stuk ingewikkelder. Ik zou je aanraden om een goede uitleg hierover te lezen.

Dan bestaat er ook nog een zogenaamde counting semaphore. Dan heb je bijvoorbeeld 3 stokjes, dus er mogen 3 personen tegelijk rennen. Ook over dit soort zaken zou ik je aanraden gewoon een goed stuk te lezen.

Mutexes are binary semaphores that include a priority inheritance mechanism. Whereas binary semaphores are the better choice for implementing synchronisation (between tasks or between tasks and an interrupt), mutexes are the better choice for implementing simple mutual exclusion (hence 'MUT'ual 'EX'clusion).

https://www.freertos.org/Real-time-embedded-RTOS-mutexes.html

PE2BAS