Tools4ever Tech Blog

Multi-threading vanaf C++ 11

Ralph Langendam - Sr. Software Engineer | 22 november 2016

Tot aan versie 11 was er binnen C++ en de STL geen platform onafhankelijke mogelijkheid om multi-threading applicaties te ontwikkelen. Ondanks de voortschrijdende ontwikkelingen op dit gebied blijven er nog enkele ruwe randjes bestaan. De meest voor de hand liggende taken kunnen inmiddels prima met de bestaande bouwstenen worden gerealiseerd.

In deze blogpost illustreren we, aan de hand van een aantal voorbeelden, hoe diverse concurrency scenario’s kunnen worden geïmplementeerd door gebruik te maken van de verschillende threading faciliteiten.

Green threads

Multi-threading c++ 11 green and redVrijwel alle software en hardware platformen ondersteunen parallelle uitvoering van instructies. Zelfs wanneer de hardware geen ondersteuning biedt of geen resources beschikbaar heeft, kan parallelle uitvoering door software worden geëmuleerd. Deze zogenaamde ‘green’ threads worden scheduled door een runtime of virtual machine.

Het meest bekende voorbeeld hiervan zijn de event-driven webapplicaties die van de browser hoogstens 1 software thread tot hun beschikking krijgen. Asynchroniciteit is dan ook allerminst een garantie voor parallelisme.

De meest voorkomende implementatie van green threads is in termen van coroutines. Coroutines zijn (sub)routines die kunnen worden onderbroken en hervat met behoud van de stack. Zij realiseren daarmee softwarematig non-preemptive multitasking. Standaard C++ biedt hier nog geen ondersteuning voor, maar bibliotheken als Boost.Coroutine zijn hierop een welkome aanvulling.

Red threads

Het zijn de native threads of ‘red’ threads waar C++ threading zich voornamelijk op richt. We beginnen met de thread handle std::thread.

 

Het joinen van een std::thread is verplicht, omdat de destructor van std::thread een exceptie gooit, zolang deze nog joinable is. Omdat we geen return waardes uit de functie van de thread terug krijgen is het teruglezen van result nogal omslachtig.

Futures en promises

Het is beter om de scope beperkt te houden door gebruik te maken van std::promise en std::future.

 

Merk op dat we de waarde uit future kunnen lezen nog voordat de executie van thread afgelopen is. We kunnen exact het oude gedrag nabootsen door de promise pas te vervullen wanneer de thread klaar is. Nadat de thread klaar is moeten we deze alsnog joinen.

 

Asynchroniciteit

Voor dergelijke scenario’s is de wrapper functionaliteit van std::async syntactisch echter veel minder beladen. Bovendien kan Factorial nu geschreven worden zonder expliciete promises.

 

std::async retourneert een std::future<T> met T het return type van de meegegeven functie. Een ander subtiel verschil is de afwezigheid van een thread handle. De reden hiervoor is simpel: er komt mogelijk helemaal geen extra thread aan de executie te pas. Met std::async delegeren we de keuze om Factorial al dan niet op een nieuwe thread uit te voeren aan het systeem.

Launch policies

Multi-threading c++ 11 launch policiesAls eerste argument van std::async kan een enum class std::launch instantie meegegeven worden om het gewenste gedrag af te dwingen. Deze zogenaamde launch policy default naar std::launch::async | std::launch::deferred op std::async. Wanneer expliciet een van beiden wordt meegegeven zal er respectievelijk een nieuwe ‘red’ of ‘green’ thread worden gebruikt voor de executie. Let op: ten tijde van schrijven wijkt de Microsoft C++ 2015 compiler hierin af van de C++ 11 standaard. Hierdoor is het niet gegarandeerd dat std::launch::async een nieuwe thread instantieert.

In het geval van std::launch::deferred zal de uitvoering lazy, maar wel synchroon plaatsvinden. Om precies te zijn: zodra de get methode op de bijbehorende future wordt aangeroepen. Wanneer get niet wordt aangesproken, zal de deferred functie dus ook niet worden uitgevoerd.

Futures en promises delen een shared state met een mogelijke thread handle. Zodra een future uit scope raakt en daarmee de laatste referentie naar de shared state verdwijnt, wordt niet alleen de shared state, maar ook de eventuele thread opgeruimd. Voor een joinable thread impliceert dit een join. Dit verklaart waarom de volgende code alleen de tekst “called async” op het scherm print.

 

Packaged tasks

Multi-threading c++ 11 Packaged tasksstd::async doet onder water twee dingen:

  1. Verpak de gedelegeerde functieaanroep als een Callable std::packaged_task.
  2. Bepaal op basis van de launch policy of deze packaged_task al dan niet op een aparte thread moet worden uitgevoerd.
    • Als de packaged_task niet op een aparte thread moet worden uitgevoerd, dan retourneert async de future van de packaged_task.
    • Als de packaged_task op een aparte thread moet worden uitgevoerd, dan regelt async dat de thread aangemaakt wordt en dat de shared state van geretourneerde future gekoppeld is aan het joinen van de thread.

std::packaged_task en std::thread zijn meer low-level constructies die alleen in specifieke gevallen van toegevoegde waarde zijn. Het gebruik van std::async is in zijn algemeenheid dan ook te verkiezen boven std::thread.

 

Excepties

Excepties moeten binnen iedere thread zelf worden afgehandeld op straffe van een aanroep van std::terminate vanuit de overtredende thread. Om excepties door te geven over thread barrières kunnen we std::exception_ptr gebruiken.

 

Mutual exclusion

Om synchronisatie tussen threads te bewerkstelligen gebruiken we binnen C++ voornamelijk STL classes die synchroniciteitsconcepten implementeren. Zo kennen we concepten als BasicLockable, Lockable, Mutex, TimedLockable, TimedMutex, SharedLockable, SharedMutex en SharedTimedMutex. De Mutex concepten hiervan hebben referentie-implementaties binnen STL. Zo kennen we

  • std::mutex (Mutex): deze biedt lock (blocking wait), unlock en try_lock (retourneert direct of het locken is geslaagd) methoden.
  • std::recursive_mutex (Mutex): een mutex die meerdere malen vanuit dezelfde thread locked kan worden.
  • std::timed_mutex (TimedMutex): een mutex die try_lock_for (met een std::duration) en try_lock_until (met een std::time_point) methoden aanbiedt.
  • std::shared_mutex (SharedMutex): een mutex die ook lock_shared, unlock_shared en try_lock_shared methoden biedt, waarmee synchronisatie tussen meerdere lezers en een enkele schrijver geregeld kan worden.
  • std::shared_timed_mutex (SharedTimedMutex): een SharedMutex die ook een TimedMutex is.

Het expliciet locken en unlocken van mutexen is meestal niet nodig. De STL biedt namelijk een aantal RAII-containers wiens scope identiek is aan de critical section van een mutex:

  • std::unique_lock beheert de exclusieve critical section van een Mutex, TimedMutex, SharedMutex of SharedTimedMutex.
  • std::shared_lock beheert de gedeelde critical section van een SharedMutex of SharedTimedMutex.
  • std::lock_guard biedt tot C++17 slechts een deel van de functionaliteit van std::unique_lock en is daarmee praktisch overbodig. Vanaf C++17 biedt std::lock_guard ook RAII-functionaliteit voor het gelijktijdig locken van meerdere mutexen, zonder deadlocks. Deze functionaliteit is zonder RAII reeds in C++11 beschikbaar als std::lock.

We kijken nu naar een synchronisatie voorbeeld met std::shared_mutex.

 

Door de macroscopisch gekozen tijden kunnen we met enige zekerheid inzicht krijgen in het platform specifieke gedrag van de applicatie. Ofschoon outputs naar de console niet beschermd zijn verwachten we dat er geen read regels tussen de ‘write lock 1’ en ‘write unlock 1’ regels heen zullen komen.

Daarnaast kunnen we zien of het platform actief starvation van writers door readers voorkomt. Uitvoeren onder Windows 10 met MsBuild 2015 geeft:

read lock 1
read unlock 1
write lock 1
write unlock 1
read lock 2
read lock 3
read unlock 2
read unlock 3

Terwijl Linux 3.2.0 met gcc 6.2.0 geeft:

read lock 1
read lock 2
read unlock 1
read unlock 2
write lock 1
write unlock 1
read lock 3
read unlock 3

Op beide platformen zien we dat read locks gelijktijdig gedeeld kunnen worden tussen thread, maar we zien ook dat beide platformen actief starvation van de writer tegengaan door readers tegen te houden als er ook een writer wacht. Op een platform zonder deze voorziening zal de output er als volgt uitzien:

read lock 1
read lock 2
read unlock 1
read lock 3
read unlock 2
read unlock 3
write lock 1
write unlock 1

Condition variables

In multi-threading applicaties komt het vaak voor dat data tussen threads overgeheveld moet worden. Bijvoorbeeld voor het verzamelen van data in een gemeenschappelijke aggregatiethread of juist voor het uitdelen van taken aan meerdere threads. Voor dergelijke scenario’s biedt std::condition_variable uitkomst. Een condition variable valideert een conditie en het lockt een mutex in een atomaire stap.

Hier volgt een voorbeeld van een enkele source thread, gekoppeld aan meerdere worker threads. Op hun beurt sturen de workers hun resultaten weer naar een enkele sink thread.

 

Deze applicatie print de getallen 1 t/m 100 in potentieel willekeurige volgorde. De waarde 0 wordt zowel bij source en sink als een extra state gebruikt. We gebruiken twee std::condition_variables per std::mutex om signalen heen en weer tussen source en worker, maar ook tussen worker en sink te sturen.

Atomair gedrag

Multi-threading c++ 11 atomair gedragDe wait methode van een std::condition_variable is een atomaire operatie. Het controleren van het predicaat gaat immers gepaard met het locken van de mutex binnen de std::unique_lock. Het is dus niet mogelijk voor een andere thread om de conditie te invalideren voordat de mutex locked wordt.

Meer algemeen kunnen we stellen dat de critical section van een niet-shared mutex atomair is, bezien vanuit het perspectief van alle andere threads. Atomair gedrag is echter niet beperkt tot de relatief zware thread synchronisatie en context switching van een mutex.

Vanaf C++ 11 heeft STL een bibliotheek voor de ondersteuning van atomaire operaties. Voor alle heeltallige types en pointer types bestaat er een specialisatie van std::atomic. D.w.z. voor ieder type T, waarvoor std::is_integral<T>::value || std::is_pointer<T>::value waar is, bestaat een specialisatie van std::atomic<T>.

Een std::atomic<T> representeert de waarde van een T die complexe atomaire operaties toestaat. Zo zijn er load en store methoden die als thread-safe getter en setter kunnen fungeren. Daarnaast zijn er onder ander methodes zoals fetch_add om atomair een waarde op te hogen en compare_exchange_weak en _strong om atomair een waarde de lezen, vergelijken en conditioneel te schrijven.

Tegenwoordig ondersteunen veel platformen dergelijke operaties zonder gebruik te maken van mutexen. In het geval dat het platform niet beschikt over de benodigde instructies wordt er teruggevallen op klassieke synchronisatiemethoden, gebaseerd op bijvoorbeeld std::mutex.

Indien het platform voor een bepaald type T atomaire operaties ondersteund, dan zal std::atomic<T>::is_lock_free() alleen true retourneren als de bewuste applicatie instantie hier ook gebruik van maakt. Dit is niet voor alle types een garantie en kan per applicatie instantie verschillen. Sinds C++ 17 is er de compile-time constant expressie bool std::atomic<T>::is_always_lock_free. Als deze waarde false is, bestaat er alsnog een mogelijkheid voor std::atomic<T>::lock_free() om true terug te geven tijdens runtime.

We roepen hierbij in herinnering dat een algoritme non-blocking is als het falen of wachten in een thread geen falen of wachten van een andere thread tot gevolg kan hebben. Een algoritme is lock-free als deze non-blocking is en bovendien systeem breed gegarandeerd voortgang vertoont. Tot slot is een algoritme wait-free als de lock-free voorwaarde kan worden versterkt tot een gegarandeerde voortgang per thread.

Tot slot is er met iedere atomaire operatie een zogenaamde memory order geassocieerd, maar hier zullen we later nog op terug komen. Voor nu is het alleen belangrijk om te weten dat er een default memory order voor alle atomaire operaties wordt gekozen die altijd klassiek voorspelbaar gedrag oplevert, maar mogelijk niet in alle situaties optimaal presteert.

Hier volgt een ietwat gegeneraliseerde versie van het voorgaande voorbeeld. In plaats van workers beschouwen we nu meerdere producers en consumers die zowel via een std::condition_variable als via atomaire variabelen communiceren.

 

Evaluatievolgorde

Wat denkt u dat de output is van de volgende code?

 

Multithreading is weliswaar ingewikkeld, maar single threading is ook zeker niet altijd eenvoudig. De bovenstaande code toont op mijn computer iedere run 20 maal de vergelijking 1+2+3=6 op het scherm. Echter, de C++ standaard legt dit niet vast. Het kan namelijk best zo zijn dat iemand anders 3+2+1=6 of een willekeurige andere permutatie van 1, 2 en 3 op het scherm ziet. Sterker nog, binnen dezelfde run kunnen alle 6 verschillende permutaties van deze valide vergelijking op het scherm verschijnen.

De associativiteitsregels van de plus operator dwingen weliswaar af dat de Print statements geparsed worden als (Print(1) + Print(2)) + Print(3), maar dit zegt niets over de evaluatievolgorde van de Print statements zelf. Deze volgorde is namelijk ongedefinieerd.

Multi-threading c++ 11 sequencing
Sequencing

Sinds C++11 zijn er extra sequencing regels van toepassing die ons in specifieke situaties meer kennis en controle kunnen geven over de observeerbare evaluatievolgorde. Met de introductie van move semantics hebben de value categorieën eveneens een update gekregen. We roepen in herinnering dat iedere C++ expressie een type en value categorie heeft. We kennen 5 value categorieën:

  • De evaluatie van een glvalue bepaalt de identiteit van object, bit-field of functie.
  • De evaluatie van een prvalue bepaalt ofwel de waarde van een operand of operator, danwel initialiseert een object of bit-field.
  • Een xvalue is een object of bit-field wiens resources hergebruikt kunnen worden.
  • Een lvalue is een glvalue die geen xvalue is.
  • Een rvalue is een prvalue of een xvalue.

Hiermee onderscheiden we twee soorten van expressie evaluatie binnen C++:

  • Waarde bepalingen: berekening van een resultante waarde van een expressie. Hiervoor mogen glvalues en prvalues geëvalueerd worden.
  • Side-effects:
    • Lezen van of schrijven naar het object van een volatile glvalue
    • Schrijven naar een object
    • Aanroepen van een I/O functie
    • Aanroepen van een functie met side-effects

De evaluaties van alle expressies binnen een C++ thread vormen een strikte partiële ordening onder de 'sequenced-before' relatie. Dit verdient mogelijk wat uitleg:

Strikte partiële ordeningen

Zij gegeven een verzameling V en een binaire relatie R op V. Dat wil zeggen R is een deelverzameling van alle paren van elementen van V. Notatie: R ⊆ V × V. Voor twee elementen v en w van V (Notatie: v, w ∈ V) noteren we vRw als het geordende paar (v,w) in R ligt. Het paar (V,R) definieert een strikte partiële ordening als aan de volgende drie voorwaarden is voldaan:

  1. R is irreflexief, oftewel voor alle v ∈ V geldt niet dat vRv.
  2. R is transitief, oftewel wanneer voor u, v, w ∈ V geldt dat uRv en vRw dan geldt ook uRw.
  3. R is asymmetrisch, oftewel als voor v, w ∈ V geldt dat vRw, dan geldt niet wRv.

Het valt eenvoudig in te zien dat 3 uit 1 en 2 volgt. Immers, als zowel vRw als wRv, dan zou op basis van transitiviteit gelden dat vRv, maar dit is in tegenspraak met irreflexiviteit. Omgekeerd valt ook eenvoudig in te zien hoe 1 volgt uit 3. Immers, stel dat er een v ∈ V is waarvoor vRv, dan zou voor w gelijk aan v, op basis van asymmetrie gelden dat vRv niet waar is.

Sequenced before

Multi-threading c++ 11 sequenced beforeDe volgorde waarin evaluaties binnen een thread worden uitgevoerd definieert de zogenaamde sequencing. Gegeven twee evaluaties e en f binnen een thread, dan voldoet de sequenced-before relatie S aan de volgende eigenschappen:

  • Als eSf dan is e klaar voordat f begint.
  • Als niet eSf en niet fSe dan zijn er twee mogelijkheden:
    • e en f zijn niet sequenced. Oftewel, ze mogen in iedere volgorde en zelfs tegelijkertijd binnen dezelfde thread worden uitgevoerd. Bijvoorbeeld door interleaving van CPU-instructies.
    • e en f zijn onbepaald sequenced. Oftewel, ze mogen in iedere volgorde, maar niet gelijktijdig binnen een thread worden uitgevoerd.

De evaluaties E en relatie S vormen een strikte partiële ordening (E,S). Het voert voor nu te ver om voor alle combinaties van evaluaties S te specificeren. Er zijn echter een aantal opvallende wijzigingen in S aangebracht door C++17:

  • Iedere komma-gescheiden lijst van expressies in een initializer is onbepaald sequenced.
  • Voor ieder tweetal expressies x en y en iedere (compound-)assignment operator O is de evaluatie van y sequenced voor de evaluatie van x in de expressie xOy.
  • Voor iedere functie aanroep geldt dat de evaluatie van alle expressies, wiens resultaat van evaluatie een argument is van de functie, onderling onbepaald sequenced zijn.

Execution policies

Tot slot wil ik de aandacht vestigen op de volgende pre-C++11 regel: gegeven de evaluaties e en f van twee functie calls, waarvoor geldt dat niet eSf noch fSe dan zijn de evaluaties onbepaald sequenced. C++17 voegt hier aan een uitzondering toe: alle functies, aangeroepen door een STL-algoritme onder de std::par_unseq executie policy, zijn niet sequenced. Dit zullen we nu nader expliciteren.

C++17 introduceert op veel functies in <algorithm> een zogenaamde execution policy. Dit is een extra parameter die als eerste argument aan het algoritme mee kan worden gegeven om te bepalen hoe de parallelle calls sequenced worden. We onderscheiden 3 execution policies:

  • Het type std::execution::sequenced_policy heeft een globale instantie std::execution::seq en bepaald dat alle geassocieerde functie call expressies onbepaald sequenced worden geëvalueerd vanuit de aanroepende thread.
  • Het type std::execution::parallel_policy heeft een globale instantie std::execution::par en bepaald dat alle geassocieerde functie call expressies parallel mogen worden geëvalueerd op aparte threads, maar dat alle functie calls binnen dezelfde thread onderling onbepaald sequenced zijn.
  • Het type std::execution::parallel_unsequenced_policy heeft een globale instanctie std::execution::par_unseq die, net als std::execution::par, toestaat dat alle functie call expressies parallel en op verschillende threads worden geëvalueerd, maar dat alle functie call expressies binnen dezelfde thread niet sequenced zijn.

 

Memory ordening

Multi-threading c++ 11 memory ordeningIn de context van atomaire operaties hebben we gesproken over memory ordening. Met onze kennis over sequencing en execution policies kunnen we dit concept nu makkelijker begrijpen. We onderscheiden 6 waarden binnen de enum std::memory_order. Deze kunnen worden meegegeven aan atomaire operaties om de vrijheid in sequencing te beinvloeden.

  • memory_order_relaxed: Kan aan alle atomaire operaties worden meegegeven. Alleen atomair gedrag is gewaarborgd. Er zijn geen beperkingen op synchronisatie of ordening.
  • memory_order_consume: Kan alleen aan load operaties worden meegegeven. Alle leesacties die afhankelijk zijn van de hier gelezen waarde mogen niet voor deze load sequenced worden. Dit zorgt ervoor dat alle schrijfacties van data-afhankelijke variabelen vanuit andere threads op deze geheugenlocatie, die zijn uitgevoerd met minstens memory_order_release, vanaf deze load zichtbaar zijn in de huidige thread.
  • memory_order_acquire: Kan alleen aan load operaties worden meegegeven. Geen enkele lees- of schrijf-actie in de huidige thread mag voor deze operatie sequenced worden. Dit zorgt ervoor dat alle schrijf acties vanuit andere threads, gevolgd door een store op deze geheugenlocatie met minstens memory_order_release, zichtbaar zijn in de huidige thread.
  • memory_order_release: Kan alleen aan store operaties worden meegegeven. Geen enkele lees- of schrijf-actie in de huidige thread mag na deze operatie sequenced worden. Dit zorgt ervoor dat alle schrijfacties, waarop deze store operatie een afhankelijkheid heeft, zichtbaar worden in andere threads die een load operatie met minstens memory_order_consume uitvoeren. Als de load operatie met minstens memory_order_acquire is uitgevoerd dan zijn alle schrijfacties zichtbaar.
  • memory_order_acq_rel: Kan alleen aan read-modify-write operaties worden meegegeven. Dit is zowel een memory_order_acquire als een memory_order_release. Kortom, alle lees- en schrijf-acties voor respectievelijk na deze operatie kunnen niet na respectievelijk voor deze operatie sequenced worden. Dit zorgt ervoor dat alle schrijfoperaties voorafgaand aan een store, met minstens memory_order_release in een andere thread, zichtbaar zijn in de huidige thread. Bovendien is de huidige operatie zichtbaar in alle threads die minstens een memory_order_acquire load operatie op dezelfde geheugenlocatie hebben uitgevoerd.
  • memory_order_seq_cst: Kan aan alle atomaire operatie worden meegegeven en is tevens een memory_order_acquire en memory_order_release. Bovendien bestaat er een unieke globale volgorde waarin alle threads deze modificaties waarnemen. Deze memory ordening is de default waarde voor alle atomaire operaties. Het effect is dat deze operaties alleen anders sequenced mogen worden als dit niet tot klassiek inconsistent gedrag leidt. Vandaag de naam: sequentieel consistent.

We zullen enkele van deze memory ordeningen nader toelichten aan de hand van voorbeelden.

Relaxte ordening

Om het principe van relaxte memory ordening te illustreren beschouwen we de volgende code:

 

Bovenstaande code mag vanuit beide threads de waarde true op het scherm printen. Immers, door de relaxte ordening van de store en load in thread 2 mag de store voor de load plaatsvinden. Indien de store uit thread 2 plaatsvindt voor de load in thread 1, bezien vanuit thread 1, dan print thread 1 true. Als de load in thread 2 nu plaatsvindt na de store in thread 1, bezien vanuit thread 2, dan wordt ook in thread 2 true op het scherm geprint.

Wanneer we de store operatie in thread 2 echter afhankelijk maken van de gelezen waarde kan dit niet meer voorkomen.

 

Beide threads printen nu gegarandeerd false als waarde. Deze relaxte memory ordening wordt binnen STL voornamelijk gebruikt voor reference counters in RAII-containers, toestandswaarden en vlaggetjes. In deze scenario’s is immers alleen atomair gedrag van belang.

Release Acquire Consume ordening

Deze vorm van memory ordening wordt veel gebruikt voor producer consumer patronen.

 

De bovenstaande code zal voor beide waarden nooit false op het scherm printen. Echter, wanneer we de memory order van de load verzwakken tot memory_order_consume, dan zou independent nog steeds als false geobserveerd kunnen worden vanuit de consumer.

 

Slotwoord

Ondanks de substantiële omvang van deze blogpost is dit nog slechts het topje van de ijsberg waar het op multi-threading in C++ aankomt. Hopelijk heeft dit artikel je interesse gewekt om meer over de behandelde onderwerpen te weten te komen.