Lezen 17: Concurrency

#### Software in 6.005

#### Objectives+ Message passing & gedeeld geheugen + processen & threads+ Time slicing+ Race conditions## Concurrency* Concurrency * betekent dat meerdere berekeningen tegelijkertijd plaatsvinden. Concurrency is overal in de moderne programmering, of we het nu leuk vinden of niet: + meerdere computers in een netwerk+ meerdere applicaties die op een computer draaien+ meerdere processors in een computer (tegenwoordig vaak meerdere processorkernen op een enkele chip) in feite is concurrency essentieel in de moderne programmering:+ websites moeten meerdere gelijktijdige gebruikers verwerken.+ Mobiele apps moeten een deel van hun verwerking op servers (“in de cloud”).+ Grafische gebruikersinterfaces vereisen bijna altijd achtergrondwerk dat de gebruiker niet onderbreekt. Eclipse compileert bijvoorbeeld je Java-code terwijl je het nog aan het bewerken bent.In staat zijn om te programmeren met concurrency zal nog steeds belangrijk zijn in de toekomst. De kloksnelheid van de Processor neemt niet meer toe. In plaats daarvan krijgen we meer kernen met elke nieuwe generatie chips. Dus in de toekomst, om een berekening sneller te laten lopen, moeten we een berekening opsplitsen in gelijktijdige stukken.## Twee modellen voor gelijktijdig programmeren er zijn twee gemeenschappelijke modellen voor gelijktijdig programmeren: * gedeeld geheugen * en * bericht doorgeven*.

* * gedeeld geheugen.** In het gedeelde geheugen model van concurrency, gelijktijdige modules interactie door het lezen en schrijven van gedeelde objecten in het geheugen. Andere voorbeelden van het shared-memory model: + A en B kunnen twee processors (of processorkernen) in dezelfde computer zijn, die hetzelfde fysieke geheugen delen.+ A en B kunnen twee programma ‘ s zijn die op dezelfde computer draaien en een gemeenschappelijk bestandssysteem delen met bestanden die ze kunnen lezen en schrijven.+ A en B kunnen twee threads zijn in hetzelfde Java-programma( we zullen hieronder uitleggen wat een thread is), die dezelfde Java-objecten delen.

* * doorgeven van berichten.** In het message-passing model, gelijktijdige modules interactie door het verzenden van berichten naar elkaar via een communicatiekanaal. Modules verzenden berichten, en inkomende berichten naar elke module worden in de wachtrij geplaatst voor afhandeling. Voorbeelden zijn:+ A en B kunnen twee computers in een netwerk zijn, die communiceren via netwerkverbindingen.+ A en B kunnen een webbrowser en een webserver zijn – A opent een verbinding met B, vraagt om een webpagina, en B stuurt de webpagina-gegevens terug naar A.+ A en B kunnen een instant messaging-client en-server zijn.+ A en B kunnen twee programma `s zijn die draaien op dezelfde computer waarvan de invoer en uitvoer zijn verbonden door een pipe, zoals` ls | grep ‘ die in een opdrachtprompt is getypt.## Processen, Threads, Time-slicingThe message-passing en shared-memory modellen gaan over hoe gelijktijdige modules communiceren. De gelijktijdige modules zelf komen in twee verschillende soorten: processen en threads.**Proces**. Een proces is een instantie van een draaiend programma dat * geà soleerd* is van andere processen op dezelfde machine. In het bijzonder heeft het een eigen privé gedeelte van het geheugen van de machine.De process abstraction is een * virtuele computer*. Het programma voelt alsof het de hele machine voor zichzelf heeft — alsof er een nieuwe computer is gemaakt, met vers geheugen, alleen maar om dat programma uit te voeren.Net als computers die via een netwerk zijn verbonden, delen processen normaal gesproken geen geheugen tussen hen. Een proces heeft geen toegang tot het geheugen of de objecten van een ander proces. Het delen van geheugen tussen processen is *mogelijk* op de meeste besturingssystemen, maar het vereist speciale inspanning. Een nieuw proces is daarentegen automatisch klaar voor het doorgeven van berichten, omdat het wordt aangemaakt met standaard invoer & uitvoerstromen, die het ‘systeem’ zijn.uit ‘en `System.in’ streams die je hebt gebruikt in Java.**Draad**. Een thread is een locus van controle binnen een draaiend programma. Zie het als een plaats in het programma dat wordt uitgevoerd, plus de stapel van methode oproepen die hebben geleid tot die plaats waar het nodig zal zijn om terug te keren door.Net zoals een proces een virtuele computer vertegenwoordigt, vertegenwoordigt de thread abstraction een *virtuele processor*. Het maken van een nieuwe thread simuleert het maken van een verse processor in de virtuele computer vertegenwoordigd door het proces. Deze nieuwe virtuele processor draait hetzelfde programma en deelt hetzelfde geheugen als andere threads in proces.Threads zijn automatisch klaar voor gedeeld geheugen, omdat threads al het geheugen in het proces delen. Het heeft speciale inspanning nodig om “thread-local” geheugen te krijgen dat privé is voor een enkele thread. Het is ook noodzakelijk om message-passing expliciet in te stellen, door het creëren en gebruiken van wachtrij data structuren. We zullen praten over hoe dat te doen in een toekomstige lezing.

Hoe kan ik veel gelijktijdige threads hebben met slechts één of twee processors in mijn computer? Wanneer er meer threads dan processors zijn, wordt concurrency gesimuleerd door * * time slicing**, wat betekent dat de processor tussen threads schakelt. De figuur aan de rechterkant laat zien hoe drie threads T1, T2 en T3 in de tijd kunnen worden gesneden op een machine die slechts twee werkelijke processors heeft. In de figuur gaat de tijd naar beneden, dus eerst draait de ene processor thread T1 en de andere thread T2, en dan schakelt de tweede processor over naar thread T3. Thread T2 gewoon pauzeert, tot de volgende keer slice op dezelfde processor of een andere processor.Op de meeste systemen, tijd snijden gebeurt onvoorspelbaar en niet-deterministisch, wat betekent dat een thread kan worden gepauzeerd of hervat op elk moment.

mitx:C613ec53e92840a4a506f3062c994673 processen & Threads # # gedeeld geheugen ExampleLet ‘ s kijk naar een voorbeeld van een gedeeld geheugensysteem. Het punt van dit voorbeeld is om aan te tonen dat gelijktijdig programmeren moeilijk is, omdat het subtiele bugs kan hebben.

stel je voor dat een bank geldautomaten heeft die een gedeeld geheugenmodel gebruiken, zodat alle geldautomaten dezelfde rekeningobjecten in het geheugen kunnen lezen en schrijven.Om te illustreren wat er mis kan gaan, laten we de bank vereenvoudigen tot een enkele rekening, met een dollarsaldo opgeslagen in de `balance` variabele, en twee operaties `storting` en `opnemen` die gewoon toevoegen of verwijderen van een dollar: “java// veronderstel dat alle geldautomaten delen een enkele bankrekening private static int balance = 0;private static void deposit() { balance = balance + 1;}private static void trekken() { balance = balance – 1;}“Klanten gebruiken de geldautomaten om transacties als volgt te doen:“javadeposit(); // put een dollar in withdraw(); // take it back out` ‘ in dit eenvoudige voorbeeld is elke transactie slechts een storting van één dollar gevolgd door een opname van één dollar, dus het moet het saldo op de rekening ongewijzigd laten. Gedurende de dag verwerkt elke geldautomaat in ons netwerk een reeks stortings – /opnametransacties.”‘java / / each ATM does a tross of transactions that / / modify balance, but leave it unchanged afterwardprivate static void cashMachine () {for (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) { deposit (); / / put a dollar in withdraw(); // take it back out}} “‘ dus aan het einde van de dag, ongeacht hoeveel geldautomaten draaiden, of hoeveel transacties we verwerkt, moeten we verwachten dat het saldo van de rekening nog steeds 0.Maar als we deze code uitvoeren, ontdekken we vaak dat het saldo aan het einde van de dag *niet* 0 is. Als meer dan één` cashMachine () ` – oproep tegelijkertijd wordt uitgevoerd — bijvoorbeeld op afzonderlijke processors in dezelfde computer — dan is` balance ‘ misschien niet nul aan het einde van de dag. Waarom niet?# Er is één ding dat kan gebeuren. Stel dat twee geldautomaten, A en B, beide werken aan een storting op hetzelfde moment. Hier is hoe de storting() Stap meestal opgesplitst in low – level processor instructies` “‘get balance (balance=0)add 1 write back the result (balance=1) “‘ Wanneer A en B gelijktijdig worden uitgevoerd, deze low-level instructies interleave met elkaar (sommige misschien zelfs gelijktijdig in zekere zin, maar laten we gewoon zorgen te maken over interleaving voor nu):”‘A get balance(balance = 0) a add 1 A write back the result (balance=1) B get balance (balance=1) B add 1 B write back the result (balance=2)“Deze interleaving is prima-we eindigen met balance 2, dus zowel A als B succesvol in een dollar. Maar wat als de interleaving er zo uitzag: “‘a krijg balans (saldo=0) B krijg balans (saldo = 0) a voeg 1 B voeg 1 A schrijf het resultaat terug (saldo=1) B schrijf het resultaat terug (saldo=1)“Het saldo is nu 1 — A’ S dollar was verloren! A en B lazen allebei het saldo op hetzelfde moment, berekenden afzonderlijke eindsaldi, en renden toen om het nieuwe saldo terug op te slaan — die geen rekening hielden met de storting van de ander.## Race Conditiondit is een voorbeeld van een**race condition**. Een wedstrijdconditie betekent dat de juistheid van het programma (de tevredenheid van postcondities en invarianten) afhankelijk is van de relatieve timing van gebeurtenissen in gelijktijdige berekeningen A en B. Wanneer dit gebeurt, zeggen we “A is in een race met B.”Sommige interleavings van gebeurtenissen kunnen OK zijn, in de zin dat ze consistent zijn met wat een enkel, niet-onderling proces zou produceren, maar andere interleavings produceren verkeerde antwoorden-het schenden van postvoorwaarden of invarianten.## Het aanpassen van de Code zal niet helpen al deze versies van de bank-rekening code vertonen dezelfde race voorwaarde: “‘java / / version 1private static void deposit () { balance = balance + 1;}private static void trekken () {balance = balance-1;} “”” java / / version 2private static void deposit () { balance + = 1;} private static void trekken () {balance – = 1;}`””java// version 3private static void deposit() { ++balance;}private static void trekken() { –balance;}” `je kunt niet vertellen alleen uit te kijken naar Java-code hoe de processor gaat om het uit te voeren. Je kunt niet zeggen wat de ondeelbare operaties — de atomaire operaties — zullen zijn. Het is niet atomisch alleen omdat het één lijn Java is. Het raakt het evenwicht niet slechts één keer aan, alleen maar omdat de Balance identifier slechts één keer in de regel voorkomt. De Java compiler, en in feite de processor zelf, maakt geen verplichtingen over wat low-level operaties het zal genereren van uw code. In feite, een typische moderne Java compiler produceert precies dezelfde code voor alle drie van deze versies!De belangrijkste les is dat je niet kunt zien door te kijken naar een uitdrukking of het veilig zal zijn voor de omstandigheden van het ras.

## het is zelfs nog erger dan dat. De racevoorwaarde op het bankrekeningsaldo kan worden verklaard in termen van verschillende interleavings van sequentiële operaties op verschillende processors. Maar in feite, wanneer je meerdere variabelen en meerdere processors gebruikt, kun je niet eens rekenen op veranderingen in die variabelen die in dezelfde volgorde verschijnen.Hier is een voorbeeld: “‘ javaprivate boolean ready = false; private int answer = 0;// computeAnswer draait in een threadprivate void computeAnswer() { answer = 42; ready = true;} / / useAnswer draait in een andere threadprivate void useAnswer() { while (!klaar) { draad.yield ();} if (answer = = 0) gooi nieuwe RuntimeException (“antwoord was niet klaar!`);} “`We hebben twee methoden die worden uitgevoerd in verschillende threads. ‘computeAnswer’ maakt een lange berekening en komt uiteindelijk met het antwoord 42, dat het in de antwoordvariabele zet. Dan stelt het de `ready` variabele op true, om aan de methode die in de andere thread, `useAnswer`, dat het antwoord klaar is voor het te gebruiken signaal. Kijkend naar de code,` antwoord ‘is ingesteld voordat klaar is ingesteld, dus zodra ‘useAnswer’ ziet ‘klaar’ als waar, dan lijkt het redelijk dat het kan aannemen dat het` antwoord ‘ 42 zal zijn, toch? Niet zo.Het probleem is dat moderne compilers en processors veel dingen doen om de code snel te maken. Een van die dingen is het maken van tijdelijke kopieën van variabelen zoals antwoord en klaar in snellere opslag (registers of caches op een processor), en het werken met hen tijdelijk voordat ze uiteindelijk op te slaan terug naar hun officiële locatie in het geheugen. De storeback kan plaatsvinden in een andere volgorde dan de variabelen werden gemanipuleerd in uw code. Hier is wat er zou kunnen gebeuren onder de covers (maar uitgedrukt in Java syntaxis om het duidelijk te maken). De processor creëert effectief twee tijdelijke variabelen, ‘tmpr’ en ‘tmpa’, om de velden klaar te manipuleren en te beantwoorden:”‘javaprivate void computeAnswer () { boolean tmpr = ready; int tmpa = answer; tmpa = 42; tmpr = true; ready = tmpr; / / <– what happens if useAnswer() interleaves here? // ready is ingesteld, but answer isn ‘t. answer = tmpa;} “‘ mitx: 2bf4beb7ffd5437bbbb9c782bb99b54e Race Conditions # # Message Passing Example

laten we nu eens kijken naar de message-passing approach naar onze bankrekening voorbeeld.Nu zijn niet alleen de geldautomaat modules, maar de rekeningen zijn modules, ook. Modules communiceren door berichten naar elkaar te sturen. Inkomende verzoeken worden in een wachtrij geplaatst om één voor één te worden behandeld. De afzender stopt niet met werken terwijl hij wacht op een antwoord op zijn verzoek. Het behandelt meer verzoeken uit zijn eigen wachtrij. Het antwoord op zijn verzoek komt uiteindelijk terug als een ander bericht.Helaas, het doorgeven van berichten elimineert de mogelijkheid van race-omstandigheden niet. Stel dat elke account ondersteunt` get-balance `en` trekken ‘ operaties, met bijbehorende berichten. Twee gebruikers, bij geldautomaat A en B, proberen beiden een dollar van dezelfde rekening op te nemen. Ze controleren het saldo eerst te zorgen dat ze nooit meer terugnemen dan het account heeft, omdat rekening-courantkredieten trigger grote bank sancties:“get-balanceif balans >= 1 dan trekt 1“Het probleem is weer interleaving, maar deze keer interleaving van de *berichten* verzonden naar de bankrekening, in plaats van de *instructies* uitgevoerd door A en B. Als de rekening begint met één dollar in het wat interleaving van berichten dwaas A en B laten denken dat ze kunnen zowel trekken van de dollar, waardoor overdrawing de rekening?Een les hier is dat je moet zorgvuldig kiezen voor de werking van een bericht-doorgeven model. “geld opnemen-als-voldoende-geld opnemen” zou een betere operatie zijn dan alleen “geld opnemen”.## Concurrency is moeilijk te testen en DebugIf we hebben u niet overtuigd dat concurrency is lastig, hier is het ergste van het. Het is erg moeilijk om race-omstandigheden te ontdekken met behulp van testen. En zelfs als een test een bug heeft gevonden, kan het heel moeilijk zijn om het te lokaliseren naar het deel van het programma dat het veroorzaakt.Concurrency bugs vertonen een zeer slechte reproduceerbaarheid. Het is moeilijk om ze twee keer op dezelfde manier te laten gebeuren. Interleaving van instructies of berichten hangt af van de relatieve timing van gebeurtenissen die sterk worden beïnvloed door de omgeving. Vertragingen kunnen worden veroorzaakt door andere lopende programma ‘ s, ander netwerkverkeer, planning van het besturingssysteem beslissingen, variaties in processor kloksnelheid, enz. Elke keer dat u een programma met een race conditie uitvoert, kunt u ander gedrag krijgen. Dit soort bugs zijn * * heisenbugs**, die niet-deterministisch zijn en moeilijk te reproduceren, in tegenstelling tot een “bohrbug”, die herhaaldelijk verschijnt wanneer je ernaar kijkt. Bijna alle bugs in sequentiële programmering zijn bohrbugs.Een heisenbug kan zelfs verdwijnen als je hem probeert te bekijken met `println` of `debugger`! De reden is dat afdrukken en debuggen zijn zo veel langzamer dan andere operaties, vaak 100-1000x langzamer, dat ze drastisch veranderen de timing van de operaties, en de interleaving. Dus het invoegen van een eenvoudige print Static void cashMachine():“javaprivate static void cashMachine() { for (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) { deposit(); // put a dollar in withdraw(); // take it back out System.uit.println (balance); / / laat de bug verdwijnen! }}“`…en plotseling is de balans altijd 0, zoals gewenst, en de bug lijkt te verdwijnen. Maar het is alleen gemaskeerd, niet echt gemaakt. Een verandering in timing ergens anders in het programma kan plotseling de bug terug te komen.Concurrency is moeilijk goed te krijgen. Een deel van de bedoeling van deze lezing is om je een beetje bang te maken. In de volgende lezingen zullen we principiële manieren zien om gelijktijdige programma ‘ s te ontwerpen, zodat ze veiliger zijn voor dit soort bugs.mitx: 704b9c4db3c6487c9f1549956af8bfc8 Testing Concurrency# # Summary+ Concurrency: meerdere berekeningen die gelijktijdig draaien+ gedeeld geheugen & bericht-doorgeven paradigma’ s + processen & threads+ proces is als een virtuele computer; thread is als een virtuele processor + Race voorwaarden + wanneer de juistheid van het resultaat (postconditions en invarianten) afhankelijk is van de relatieve timing van gebeurtenissen deze ideeën verbinden zich met onze drie belangrijke eigenschappen van goede software meestal op slechte manieren. Concurrency is noodzakelijk, maar het Veroorzaakt ernstige problemen voor correctheid. We zullen werken aan het oplossen van die problemen in de komende paar lezingen.+ * * Veilig tegen bugs.** Concurrency bugs zijn enkele van de moeilijkste bugs te vinden en op te lossen, en vereisen zorgvuldig ontwerp te vermijden.+ * * Gemakkelijk te begrijpen.** Voorspellen hoe concurrent code kan interleave met andere concurrent code is erg moeilijk voor programmeurs om te doen. Het is het beste om zo te ontwerpen dat programmeurs daar niet aan hoeven te denken. + * * Klaar voor verandering.** Hier niet bijzonder relevant.