Wat is multithreading en wat heb je er aan?

Toen in de jaren 2000 bleek dat de kloksnelheden van processors niet onbeperkt verhoogd konden worden, werd de keuze gemaakt om in te zetten op meer processorcores. Een systeem met meerdere cores was niet nieuw. Servers hadden al langere tijd multisocket-moederborden, met ondersteuning voor meerdere processors. Doordat nu meerdere cores werden geïntegreerd in een enkele zogenoemde ‘die’, werd multithreading een stuk toegankelijker.

Het daadwerkelijk goed benutten van die extra cores loopt wel achter op de technische verbeteringen. Sommige programma’s zijn goed geoptimaliseerd voor multithreading en kunnen 16 cores benutten, maar dit is lang niet altijd het geval. Dit heeft meerdere oorzaken, waar we nu naar gaan kijken.

Wat zijn threads?

Allereerst is het belangrijk om onderscheid te maken tussen processen en threads. Elk proces beschikt over zijn eigen geheugensegment en opereert in principe compleet onafhankelijk van andere processen. Het besturingssysteem voorkomt elke poging van een proces om bij het geheugen van een ander proces te komen. Daarentegen zijn threads niet volledig onafhankelijk. Ze kunnen bij het geheugen van andere threads komen, maar het is wel een andere ‘draad’ van executie, die tegelijkertijd met de andere threads wordt uitgevoerd. Een proces kan meerdere threads hebben, maar een thread kan zelf geen eigen processen hebben.

Er zijn twee soorten threads: software-threads en hardware-threads. Het aantal software-threads wordt bepaald door het totale aantal ‘draden’. Dit kan veranderen, afhankelijk van het opstarten en afsluiten van programma’s. Wanneer we in dit artikel het woord thread zonder kwalificatie gebruiken, bedoelen we software-threads.

Het aantal hardware-threads ligt juist vast, en is afhankelijk van het aantal cores en of er Simultaneous Multithreading (SMT) wordt ondersteund. Een 8core-processor met SMT heeft bijvoorbeeld 16 threads.

Ideaal is een situatie waarbij er evenveel software-threads zijn als hardware-threads. Wanneer er minder software-threads zijn, wordt de hardware niet efficiënt benut. Dat spreekt voor zich, maar ook een te groot aantal software-threads kan negatief uitpakken voor de prestaties.

Threads versus processen

Zowel processen als threads kunnen gebruikt worden voor ‘concurrency’, een term die iets breder is dan multithreading, omdat het alles omvat waarbij meerdere taken tegelijkertijd worden uitgevoerd. Het voordeel van het gebruik van processen is dat het crashen van een proces niet leidt tot het beëindigen van het programma: Google gebruikt voor zijn Chrome-browser bijvoorbeeld meerdere processen om de stabiliteit te verbeteren.

Het grote nadeel is dat het opstarten van een proces veel trager is dan het starten van een thread. Dit is vooral het geval op Windows, waarbij alle bronnen van tevoren toegekend moeten worden. Linux heeft een andere implementatie, waarbij een proces zichzelf kan klonen. Deze kloon of ‘fork’ heeft toegang tot alle bronnen van het eerste proces. Door copy-on-write krijgt het tweede proces pas zijn eigen kopie van delen van het geheugen, als het ernaar probeert te schrijven. Dit zorgt voor veel efficiëntere multiprocessing dan op Windows, waarbij het zoals gezegd voor het creëren van een proces noodzakelijk is dat alle bronnen van tevoren toegewezen worden.

© PXimport

Aangezien threads dezelfde bronnen delen, is het makkelijker voor threads om te communiceren dan voor processen (maar zoals in de paragraaf ‘Gezamenlijk geheugengebruik’ wordt uitgelegd, is dit ook erg gevaarlijk). Inter-process communication is een kunst op zich en dat gaat vaak via omwegen die veel zwaarder en trager zijn dan wat voor threads mogelijk is. Niettemin is er een plaats voor multiprocessing en dit is vaak ook een stuk eenvoudiger te programmeren dan multithreading.

Sommige taken zijn relatief eenvoudig multithreaded te maken, dit geldt bijvoorbeeld voor 3D-rendering en encoderen onder. Andere programma’s, zoals computer assisted design (CAD), zijn dan weer noodgedwongen singlethreaded. Dit is niet willekeurig, maar hangt af van hoe geschikt een bepaald programma is voor multithreading.

Rekenen

Het belangrijkste punt is dat er zo min mogelijk afhankelijkheidsrelaties moeten zijn. In wiskundige termen moet de taak associatief zijn, wat inhoudt dat het niet uitmaakt in welke volgorde hij wordt uitgevoerd. De plusoperatie is bijvoorbeeld associatief, waardoor de volgende simpele berekening prima in een andere volgorde kan worden uitgevoerd: x = 4 + 2 + 5 + 6.

We zouden deze som met of zonder afhankelijkheid kunnen uitvoeren. In het eerste geval berekenen we eerst 4 + 2, vervolgens 6 + 5 en uiteindelijk 11 + 6. Tijdens elke stap hebben we de uitkomst van de vorige berekening nodig. Stel dat we dit anders doen, dat we eerst 4 + 2 berekenen, dan 5 + 6 en tot slot de uitkomst hiervan bij elkaar optellen. Het aantal benodigde berekeningen verandert niet, dat blijft drie, maar de afhankelijkheid is verminderd.

Voor de mens wordt het er niet makkelijker op, maar een cpu zou de eerste twee berekeningen tegelijkertijd kunnen uitvoeren, waardoor er (uitgaande van een enkele klokcyclus voor de add-instructie) maar twee klokcycli nodig zijn en niet drie. Dit voorbeeld dient ter illustratie, want als deze getallen worden ingevoerd als ‘literals’ (vaste getallen), weet een beetje compiler wel het juiste antwoord direct in te voeren.

© PXimport

Heel spannend klinkt dit misschien niet, maar de vorige paragraaf verklaart waarom bijvoorbeeld het encoderen van video zo goed als perfect multithreaded is. Het beeld wordt opgedeeld in bijvoorbeeld zestien verschillende delen. Deze hebben ieder niets te maken met de andere delen, waardoor processorthreads er onafhankelijk aan kunnen werken. Uiteindelijk wordt het beeld samengevoegd, iets wat wel afhankelijk is van de eerdere berekeningen, maar triviaal is daarmee vergeleken.

Het verklaart ook waarom sommige andere taken heel slecht geschikt zijn voor multithreaded, zoals CAD en sommige Photoshop-filters. Deze hebben een zeer hoge mate van afhankelijkheid van andere delen van een foto, waardoor het niet mogelijk is om de taak op te splitsen in verschillende delen. Het gevolg is dat er minder threads aan kunnen werken.

In hoeverre multithreading de prestaties kan verbeteren, kan uitgerekend worden op basis van het deel van het werk dat parallel te maken is. Dit heet de wet van Amdahl en luidt als volgt: 1 / (1 – p), waarbij p staat voor het deel dat te parallelliseren is. Een programma waarbij de helft geschikt is voor multithreading, kan met een onbeperkt aantal cores maximaal twee keer zo snel worden. Dit is omdat het voor de helft van de tijd niet uitmaakt hoeveel cores er zijn.

Thread-safety en cache coherence

Drie termen die vaak worden gebruikt in combinatie met multithreading zijn thread-safe, thread-unsafe en thread-compatible. Dit gaat altijd over delen van een bepaald programma, oftewel functies. Allereerst heb je functies die thread-unsafe zijn. Deze kunnen überhaupt niet vanuit meerdere threads gebruikt worden. Dit is vrijwel altijd het resultaat van slecht programmeerwerk. Het standaardniveau is thread-compatible. Dit betekent dat de functie geen problemen oplevert, zolang er niets naar het geheugen wordt geschreven.

Zonder wijzigingen is er ook geen synchronisatie noodzakelijk. Het hoogste niveau is thread-safe. Dit betekent dat er data wordt gewijzigd, maar dit levert geen problemen op dankzij de synchronisatiemechanismes die we verderop bespreken.

© PXimport

Iets wat multithreading heel ingewikkeld maakt, is het probleem van ‘cache coherency’, een van de fundamentele uitdagingen in de computerwetenschap. Dit gaat over de vraag hoe je ervoor zorgt dat het geheugen consistent is wanneer er meerdere programma’s zijn die hetzelfde geheugen lezen en ernaar schrijven. Het grote probleem is dat deze lees- en schrijfoperaties via de cache gebeuren, omdat deze vele malen sneller is dan het werkgeheugen. Aangezien iedere core zijn eigen cache heeft, kan het gebeuren dat de waarde hier verschilt met die in het geheugen, doordat een andere thread het geheugen heeft veranderd, of doordat de huidige thread de cache heeft aangepast en deze nog niet is bijgewerkt in het geheugen.

Gezamenlijk geheugengebruik

Op zich is het geen enkel probleem als er meerdere threads gebruik willen maken van hetzelfde geheugen, zolang er maar geen enkele thread is die naar het geheugen schrijft. Als er meerdere threads naar het geheugen schrijven, is dat zeker een probleem. Dit maakt multithreading onmiddellijk een stuk moeilijker … en gevaarlijker! Om een heel simpel voorbeeld te geven: stel dat er een programma is met een functie die enkel een teller verhoogt. Het volgende is een voorbeeld in C++:

We willen dit programma graag multithreaded maken. Simpeler dan dit kan niet, dus je zou verwachten dat dit geen problemen zou kunnen geven. Helaas niet. Er gaat veel meer gepaard met het verhogen van een teller dan je zou verwachten. Dit heet een RMW- operatie: read-modify-write. Het systeem moet eerst uitlezen wat de teller is (bijvoorbeeld door het te kopiëren naar een processorregister), vervolgens dit aantal verhogen met 1 en dit daarna terugschrijven naar de geheugenlocatie. Vooral deze laatste stap gaat gepaard met een aanzienlijke vertraging. Wat als de teller op 2 staat en de functie wordt twee keer tegelijkertijd aangeroepen? In beide gevallen zal de functie 2 lezen en zal de verhoging daarom uitkomen op 3, terwijl het eigenlijk 4 zou moeten zijn.

Het kan nog erger. Het uitlezen ging het vorige voorbeeld immers nog netjes, ondanks het gelijktijdig beschrijven van exact hetzelfde geheugen. We krijgen óf de waarde van voor de laatste verandering óf die van daarna, maar niet iets anders. Dit is lang niet op alle processorarchitecturen zo (maar wel op x86). In een ander geval kan de tweede functie een willekeurig getal uitlezen, bijvoorbeeld 284 of -90. Dit getal wordt dan netjes vermeerderd met 1, maar het komt helaas op iets anders uit dan de 4 die we willen hebben. Het resultaat is ongedefinieerd gedrag, wat inhoudt dat er geen enkele garantie is voor wat de uitkomst is.

Een race-conditie is wanneer de uitkomst van een programma afhangt van de volgorde waarin of de tijd waarop bepaalde code toevallig wordt uitgevoerd. Een programma hoort deterministisch en daarmee voorspelbaar te zijn, dus een goed programma hoort vrij te zijn van race-condities. Wat we willen, is dat de tweede oproep van de functie netjes wacht totdat de vorige klaar is, en dat hij daarom ook de nieuwe waarde leest. Hiervoor is synchronisatie noodzakelijk, iets wat we hierna bespreken.

© PXimport

Mutex en Atomics

Een veelgebruikt synchronisatiemechanisme is een ‘mutual exclusion object’ (mutex). Een mutex is vergelijkbaar met een ‘stoplicht’, dat voorkomt dat meerdere threads tegelijkertijd bij een bepaald deel van het geheugen kunnen komen. Een thread die toegang wil, zal eerst een vrije mutex op ‘slot’ zetten. Elke volgende thread die bij de mutex komt, zal geblokkeerd worden totdat de mutex weer vrijgegeven wordt door de eerste thread.

Mutexen hebben alleen wel de nodige problemen. Zo zijn ze relatief sloom en gevaarlijker is het probleem van potentiële deadlocks. Dat is wanneer verschillende delen van een programma meerdere van dezelfde mutexen nodig hebben, dan kan het gebeuren dat een benodigde mutex nooit vrijgegeven wordt en dat het programma blijft hangen. Deze kans is nog aanzienlijker wanneer met andere mutexen beschermde delen van het programma afhankelijk zijn van elkaar. Als deze dan tegelijkertijd gedraaid worden, dan wacht de ene thread op een vrije mutex totdat hij zijn eigen mutex vrijgeeft, terwijl de eerste mutex niet vrijkomt totdat de eerste thread klaar is met zijn werk. Er moet dus op een goed doordachte manier geprogrammeerd worden. Een simpel voorbeeld in C++:

In sommige gevallen kan het lonen om in plaats van een gewone mutex een ‘reader writer’-mutex te gebruiken. Deze kan of aan één thread schrijftoestemming geven of aan een onbeperkt aantal threads leesbevoegdheid. Aangezien alleen veranderend geheugen race-condities oplevert, kan dit de prestaties verbeteren als er maar weinig naar het beschermde geheugen wordt geschreven.

Concurrency-problemen kunnen in sommige gevallen ook opgelost worden door het gebruiken van variabelen die geen tussenstaat laten zien. Deze heten ‘atomics’ in C en C++, en ‘volatile’ variabelen (vluchtige variabelen) in Java en C#. Als we een atomische variabele gebruiken voor ons eerdere scenario, dan begint de tweede operatie pas wanneer de eerste klaar is. Dan heb je niet het probleem dat een van de vermeerderingen potentieel verloren gaan.

Volgorde

Simpele atomics lossen niet alle problemen op. Atomische variabelen kunnen ook garanderen dat bepaalde code in een voorgeschreven volgorde wordt uitgevoerd. Elke atomische operatie heeft een bepaalde ‘memory barrier’, ook wel ‘memory order’ genoemd. Deze barrière bestaat uit een ‘acquire’-laadoperatie die wordt gekoppeld aan ‘release’-opslagoperatie. Tussen deze twee operaties wordt er een zogenoemde ‘çritical section’ gecreëerd. Instructies binnen dit deel is sterk beperkt in herordening: ze mogen niet buiten de sectie worden gebracht door de compiler of de processor. Dit garandeert dat alle instructies binnen (en voor) dit deel zijn uitgevoerd wanneer er een ‘acquire’ wordt uitgevoerd. Ook wordt er gegarandeerd dat de laatste waarde van de atomische variabele is geschreven naar het geheugen en de caches, zodra de acquire is uitgevoerd.

Als er toegang wordt gevraagd voordat het systeem hier klaar mee is, wordt toegang tot de betrokken delen van het geheugen geblokkeerd. Dit om te voorkomen dat er iets gebeurt met de tussenstaat van de variabele. Hier zijn speciale machine-instructies voor, die het werk efficiënter kunnen verrichten dan een mutex. Het volgende voorbeeld laat zien hoe dat werkt.

In de praktijk komt dit erop neer dat een ‘release’ informatie publiceert die een ‘acquire’ kan opvragen (bij een RMW-operatie is er een gecombineerde acquire en release). Waar zou dit nuttig voor kunnen zijn? Veel systemen moeten van een valide staat naar een andere valide staat gebracht worden, zonder dat er het een en ander kan gebeuren in de tussenstaat. Om maar een voorbeeld te geven: bij het uitvoeren van een banktransactie is het een goed idee om zowel de vermindering als de vermeerdering op de respectieve rekeningen als een alles-of-niets-transactie uit te voeren.

Het voordeel van atomics ten opzichte van een mutex, is dat ze sneller zijn en dat deadlocks niet tot de mogelijkheden behoren. Het nadeel is dat ze nog altijd substantieel langzamer zijn dan gewone variabelen, vooral wanneer het gaat om schrijfacties. Veranderingen moet immers verspreid worden naar niet alleen de verschillende caches, maar ook naar het werkgeheugen. In de tussentijd mag er geen enkele andere thread gebruikmaken van de oude waarde. Een verder nadeel is dat niet alles met atomische variabelen geïmplementeerd kan worden. Programma’s die hier wel gebruik van maken, heten ‘lockfree’, omdat ze geen gebruikmaken van een mutex-slot.