Nederlands
Menu

Spinlock versus mutex: wachten, CPU-gebruik en gebruik in de kernel vergeleken

Spinlocks en mutexen zijn allebei locks die slechts één thread tegelijk in een kritieke sectie toelaten, maar ze wachten op een andere manier tot de lock vrijkomt. Een spinlock wacht met busy waiting, waarbij de lockvariabele in een lus steeds opnieuw wordt gecontroleerd; hij blijft tijdens het wachten CPU-tijd gebruiken, maar kan de lock direct nemen zodra die vrij is. Een mutex laat de wachtende thread slapen en geeft de CPU vrij; zodra de lock wordt vrijgegeven, wekt het besturingssysteem de thread. Spinlocks worden gebruikt bij zeer korte houdtijden en in interrupthandlers die niet mogen slapen, mutexen bij lange houdtijden of als de thread tijdens het vasthouden mogelijk moet slapen.

KenmerkSpinlockMutex
Manier van wachtenControleert de variabele in een lus tot de lock vrij is (busy waiting)Slaapt als de lock bezet is en wordt gewekt zodra die wordt vrijgegeven
CPU tijdens het wachtenBlijft die gebruikenGeeft die vrij. Andere threads kunnen de CPU in die tijd gebruiken
Overhead van het wachtenGeen contextwissel; de lock wordt direct genomen zodra die vrij isBij inslapen en ontwaken kosten systeemaanroepen en contextwissels tijd
Geschikte houdtijdZeer kort (korter dan de tijd van een contextwissel)Lang. Wanneer de thread tijdens het vasthouden mogelijk slaapt, bijvoorbeeld bij het wachten op I/O
Slapen terwijl de lock wordt vastgehoudenNiet toegestaan. De wachtende kant zou dan CPU-tijd blijven verbruikenToegestaan
Bij één kernTijdens het wachten kan de thread die de lock heeft niet draaien, dus spinnen maakt de lock niet vrij. In de kernel wordt preëmptie uitgeschakeld tijdens het gebruikWerkt zonder problemen
Gebruik in de kernelOok bruikbaar waar niet mag worden geslapen, zoals in interrupthandlers (interruptcontext). Bij data die met een interrupt wordt gedeeld, worden eerst interrupts uitgeschakeld en daarna wordt de lock genomenKan slapen en is dus alleen in procescontext bruikbaar, niet in interrupthandlers
PrioriteitsinversieAls de thread die de lock heeft wordt onderbroken, blijft de wachtende kant spinnen. De kernel voorkomt dit door preëmptie tijdens het vasthouden uit te schakelenTe ondervangen met een mutex met prioriteitsovererving
Voorbeeld van implementatieDe variabele wordt aangepast met atomaire instructies (test-and-set of compare-and-swap). Test-and-test-and-set wacht normaal met gewone leesacties en vermindert zo het verkeer tussen kernenMet futex in Linux wordt bij geen concurrentie alleen met atomaire instructies in user space gelockt, en alleen bij concurrentie laat de kernel de thread slapen. Er zijn ook implementaties die eerst even spinnen en dan slapen

De getalswaarden zijn typische ordegroottes en variëren per procesgeneratie en product.

Wanneer welke variant?

Spinlock
Op multicoresystemen wanneer de lock zeer kort wordt vastgehouden (korter dan de overhead van een contextwissel). Kernelcode waarin slapen niet is toegestaan, zoals interrupthandlers.
Mutex
Wanneer de lock lang wordt vastgehouden of wanneer de thread tijdens het vasthouden mogelijk slaapt, bijvoorbeeld voor I/O of geheugentoewijzing. Gewone wederzijdse uitsluiting in applicaties in user space.
Combinatie
Veel muteximplementaties combineren de voordelen van beide: zonder concurrentie wordt de lock zonder te slapen alleen met atomaire instructies genomen, en lukt dat niet, dan wordt eerst even gespind voordat de thread gaat slapen.

Veelgestelde vragen

Waarom worden spinlocks gebruikt als ze CPU-tijd verspillen?

Omdat bij een zeer korte houdtijd even spinnen sneller is dan de contextwissels voor inslapen en ontwaken. Bovendien zijn spinlocks het enige wat werkt op plekken waar slapen niet mag, zoals interrupthandlers in de kernel.

Waarom kan een interrupthandler geen mutex gebruiken?

Een mutex laat de wachtende thread slapen als de lock niet beschikbaar is, maar een interrupthandler draait niet als een bepaalde thread en kan dus niet inslapen om later te worden gewekt. Bij data die met een interrupthandler wordt gedeeld, combineer je een spinlock met het uitschakelen van interrupts.

Wat is een futex?

Een mechanisme in Linux om onder meer mutexen snel te implementeren. Zonder concurrentie volstaat het om de lockvariabele in user space met atomaire instructies aan te passen; alleen als er concurrentie is en gewacht moet worden, laat een systeemaanroep de kernel de thread slapen. Omdat de meeste locks niet worden betwist, bespaart dit de overhead van systeemaanroepen.

Wat gebeurt er als je een spinlock gebruikt op een systeem met één kern?

Ook als je in user space spint om te wachten, kan de thread die de lock heeft niet op die kern draaien, zodat de lock pas vrijkomt als je eigen tijdsquantum op is. Daarom regelt de kernel op systemen met één kern wederzijdse uitsluiting niet met spinlocks, maar door preëmptie of interrupts uit te schakelen.

Test uw begrip

Welke uitleg over een spinlock is juist?

  1. AEen lock waarbij de thread slaapt en door het besturingssysteem wordt gewekt tot de lock vrij is
  2. BEen lock waarbij wordt gewacht door in een lus voortdurend de lockvariabele te controleren tot de lock vrij is
  3. CEen mechanisme waarbij een schijf wordt rondgedraaid om gegevens te beschermen
Antwoord en toelichting tonen

Antwoord: B. Een lock waarbij wordt gewacht door in een lus voortdurend de lockvariabele te controleren tot de lock vrij is

Een spinlock probeert met een atomaire instructie de lock te nemen en probeert het, als dat niet lukt, direct opnieuw. Omdat de moeite van het besturingssysteem aanroepen om te slapen en te ontwaken ontbreekt, werkt het snel wanneer de lock zeer kort wordt vastgehouden. Het wordt veel gebruikt in de kernel van het besturingssysteem en voor uitsluiting met interrupthandlers. Het nadeel is dat tijdens het wachten ook CPU-tijd wordt gebruikt.

In welke situatie is een spinlock het minst geschikt?

  1. AWanneer de lock lang wordt vastgehouden en wachtende threads nodeloos CPU-tijd blijven gebruiken
  2. BWanneer de lock zeer kort, enkele tientallen nanoseconden, wordt vastgehouden
  3. CBij bewerkingen in de kernel van het besturingssysteem die niet mogen slapen
Antwoord en toelichting tonen

Antwoord: A. Wanneer de lock lang wordt vastgehouden en wachtende threads nodeloos CPU-tijd blijven gebruiken

Een thread die bij een spinlock wacht, gebruikt CPU-tijd tot de lock vrij is. Bij een lange vasthoudtijd is al die CPU-tijd verspild en worden ook andere threads gehinderd. Met name als er maar één core is, komt de lock niet vrij zolang de lockhoudende thread niet draait, dus duurt het wachten tot de tijdsindeling is afgelopen. Voor lange wachttijden wordt een slapende mutex gebruikt, en er is ook een methode die een korte tijd draait en dan gaat slapen.

Waarom wordt bij een spinlock niet meteen met een atomaire instructie de lockvariabele proberen te wijzigen, maar wordt normaal met gewoon lezen gewacht tot de lock vrij lijkt en dan pas een atomaire instructie gebruikt (test-and-test-and-set)?

  1. AOmdat gewoon lezen nauwkeuriger is dan een atomaire instructie
  2. BOmdat een atomaire instructie maar één keer per programma kan worden gebruikt
  3. COmdat bij alleen lezen in de eigen cache kan worden gewacht, zodat het verkeer van cacheregels tussen cores sterk afneemt
Antwoord en toelichting tonen

Antwoord: C. Omdat bij alleen lezen in de eigen cache kan worden gewacht, zodat het verkeer van cacheregels tussen cores sterk afneemt

Een atomaire instructie omvat een schrijfactie, dus als een wachtende thread die herhaaldelijk uitvoert, strijden de cores telkens om de regel in de M-toestand en worden kopieën in andere cores steeds ongeldig gemaakt. Met gewoon lezen blijft elke core alleen zijn S-kopie in de eigen cache lezen, en ontstaat geen verkeer. Alleen wanneer de lock vrijkomt en de waarde verandert, wordt met een atomaire instructie geprobeerd hem te nemen.

  1. Welke vergelijking van een mutex (slapende lock) en een spinlock is juist?
  2. Welke uitspraak over prioriteitsinversie bij een RTOS is juist?
  3. Welke gedachte ligt achter "prioriteitsovererving" (priority inheritance), dat wordt gebruikt om prioriteitsinversie te voorkomen?

Oefenvragen over Multicore en synchronisatie

Belangrijke termen uitgelegd

Spinlock
Lock waarbij wordt gewacht door in een lus de lockvariabele te blijven controleren tot de lock vrij is. Snel als de wachttijd kort is, maar de CPU blijft ook tijdens het wachten in gebruik.
Mutex
Lock die slechts door één thread tegelijk kan worden vastgehouden. Gangbare implementatie: een thread die de lock niet kan krijgen gaat slapen en geeft de CPU af, en het besturingssysteem wekt hem wanneer de lock vrijkomt.
Contextwissel (context switch)
Het omschakelen van het proces of de thread dat de CPU uitvoert. De toestand zoals registers en programmateller wordt opgeslagen en hersteld; bij een proceswissel wordt ook de adresruimte omgeschakeld.
Atomaire instructie
Instructie die lezen en schrijven van het geheugen uitvoert als één bewerking die niet door andere cores kan worden onderbroken. Voorbeelden: CAS, fetch-and-add en LR/SC.
Prioriteitsinversie (priority inversion)
Verschijnsel waarbij een taak met hoge prioriteit wacht op een middel dat een taak met lage prioriteit vasthoudt, terwijl een taak met middelhoge prioriteit de lage taak onderbreekt en blijft doorlopen, zodat de hoge taak lang moet wachten.

Verwante vergelijkingen