Läsning 17: samtidighet

#### programvara i 6.005

#### mål + meddelande som passerar & delat minne+ processer & trådar+ Tidsskivning+ rasförhållanden## samtidighet*samtidighet* betyder att flera beräkningar händer samtidigt. Samtidighet finns överallt i modern programmering, oavsett om vi gillar det eller inte:+ flera datorer i ett nätverk+ flera applikationer som körs på en dator+ flera processorer i en dator (idag, ofta flera processorkärnor på ett enda chip) faktum är att samtidighet är viktigt i modern programmering:+ webbplatser måste hantera flera samtidiga användare.+ Mobilappar måste göra en del av sin bearbetning på servrar (“i molnet”).+ Grafiska användargränssnitt kräver nästan alltid bakgrundsarbete som inte avbryter användaren. Eclipse sammanställer till exempel din Java-kod medan du fortfarande redigerar den.Att kunna programmera med samtidighet kommer fortfarande att vara viktigt i framtiden. Processorns klockhastigheter ökar inte längre. Istället får vi fler kärnor med varje ny generation chips. Så i framtiden, för att få en beräkning att springa snabbare, måste vi dela upp en beräkning i samtidiga bitar.## Två modeller för samtidig Programmeringdet finns två vanliga modeller för samtidig programmering: *delat minne* och *meddelandepassering*.

**delat minne.** I den delade minnesmodellen för samtidighet samverkar samtidiga moduler genom att läsa och skriva Delade objekt i minnet. Andra exempel på den delade minnesmodellen: + A och B kan vara två processorer (eller processorkärnor) i samma dator, som delar samma fysiska minne.+ A och B kan vara två program som körs på samma dator, dela ett gemensamt filsystem med filer de kan läsa och skriva.+ A och B kan vara två trådar i samma Java-program (vi förklarar vad en tråd är nedan) och delar samma Java-objekt.

**meddelande passerar.** I meddelandepassningsmodellen samverkar samtidiga moduler genom att skicka meddelanden till varandra via en kommunikationskanal. Moduler skickar meddelanden och inkommande meddelanden till varje modul står i kö för hantering. Exempel är: + A och B kan vara två datorer i ett nätverk som kommunicerar via nätverksanslutningar.+ A och B kan vara en webbläsare och en webbserver-a öppnar en anslutning till B, ber om en webbsida och B skickar webbsidans data tillbaka till A.+ A och B kan vara en snabbmeddelandeklient och server.+ A och B kan vara två program som körs på samma dator vars ingång och utgång har anslutits med ett rör, som `ls | grep` skrivit in i en kommandotolk.## Processer, trådar, Tidsskivningmeddelandepasserande och delade minnesmodeller handlar om hur samtidiga moduler kommunicerar. De samtidiga modulerna finns i två olika typer: processer och trådar.**Process**. En process är en instans av ett program som körs som är *isolerat* från andra processer på samma maskin. I synnerhet har den sin egen privata del av maskinens minne.Processabstraktionen är en * virtuell dator*. Det får programmet att känna att det har hela maskinen för sig själv-som en ny dator har skapats, med nytt minne, bara för att köra det programmet.Precis som datorer som är anslutna över ett nätverk delar processer normalt inget minne mellan dem. En process kan inte komma åt en annan process minne eller objekt alls. Att dela minne mellan processer är * möjligt * på de flesta operativsystem, men det behöver särskild ansträngning. Däremot är en ny process automatiskt redo för meddelandeöverföring, eftersom den skapas med standardinmatning & utgångsströmmar, som är `systemet.ut ‘och `System.in’ strömmar du har använt i Java.**Tråd**. En tråd är en kontrollplats i ett löpande program. Tänk på det som en plats i programmet som körs, plus stapeln med metodsamtal som ledde till den plats som det kommer att bli nödvändigt att återvända till.Precis som en process representerar en virtuell dator, representerar trådabstraktionen en *virtuell processor*. Att skapa en ny tråd simulerar att skapa en ny processor inuti den virtuella datorn som representeras av processen. Denna nya virtuella processor kör samma program och delar samma minne som andra trådar i processen.Trådar är automatiskt redo för delat minne, eftersom trådar delar allt minne i processen. Det behöver särskild ansträngning för att få “tråd-lokalt” minne som är privat för en enda tråd. Det är också nödvändigt att ställa in meddelandeöverföring uttryckligen genom att skapa och använda ködatastrukturer. Vi pratar om hur man gör det i en framtida läsning.

Hur kan jag ha många samtidiga trådar med endast en eller två processorer i min dator? När det finns fler trådar än processorer simuleras samtidighet genom **tidsskivning**, vilket innebär att processorn växlar mellan trådar. Figuren till höger visar hur tre trådar T1, T2 och T3 kan vara tidsskivade på en maskin som bara har två faktiska processorer. I figuren fortsätter tiden nedåt, så först kör en processor tråd T1 och den andra kör tråd T2, och sedan växlar den andra processorn för att köra tråd T3. Tråd T2 pausar helt enkelt tills nästa gång skiva på samma processor eller en annan processor.På de flesta system sker tidsskivning oförutsägbart och nondeterministiskt, vilket innebär att en tråd kan pausas eller återupptas när som helst.

mitx:c613ec53e92840a4a506f3062c994673 processer & trådar## delat minne Exempellåt oss titta på ett exempel på ett delat minnessystem. Poängen med detta exempel är att visa att samtidig programmering är svår, eftersom den kan ha subtila buggar.

Föreställ dig att en bank har bankomater som använder en delad minnesmodell, så att alla bankomater kan läsa och skriva samma kontoobjekt i minnet.För att illustrera vad som kan gå fel, låt oss förenkla banken till ett enda konto, med ett dollarsaldo lagrat i variabeln `balans`och två operationer`insättning ” och “uttag” som helt enkelt lägger till eller tar bort en dollar: “`java// anta att alla bankomater delar ett enda bankkontoprivate static int balance = 0;private static void deposit() { balance = balance + 1;}private static void retrait() { balance = balance – 1;} “` kunder använder bankomaterna för att göra transaktioner så här: “`javadeposit(); // sätt en dollar inwithdraw(); // take it back out “‘ I det här enkla exemplet är varje transaktion bara en insättning på en dollar följt av ett uttag på en dollar, så det borde lämna saldot på kontot oförändrat. Under hela dagen behandlar varje bankomat i vårt nätverk en sekvens av insättnings – / uttagstransaktioner.”‘java / / varje ATM gör en massa transaktioner som / / ändra balans, men lämna den oförändrad afterwardprivate statisk void cashMachine() { för (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) { insättning (); / / sätta en dollar i uttag(); // take it back out}} “‘ så i slutet av dagen, oavsett hur många bankomater som kördes, eller hur många transaktioner vi behandlade, borde vi förvänta oss att kontosaldot fortfarande är 0.Men om vi kör den här koden upptäcker vi ofta att balansen i slutet av dagen är *inte* 0. Om mer än ett` cashMachine () ` – samtal körs samtidigt-säg på separata processorer i samma dator-kanske` balans ‘ inte är noll i slutet av dagen. Varför inte?## InterleavingHere är en sak som kan hända. Antag att två bankomater, A och B, båda arbetar på en insättning samtidigt. Så här bryter insättningssteget() vanligtvis ner i processorinstruktioner på låg nivå: “‘få balans (balans = 0) Lägg till 1 Skriv tillbaka resultatet (balans=1) “‘ När A och B körs samtidigt, dessa lågnivåinstruktioner interleave med varandra (vissa kan till och med vara samtidiga i någon mening, men låt oss bara oroa oss för att interleaving för nu):”‘A Få balans (balans = 0) a Lägg till 1 A skriv tillbaka resultatet (balans=1) b få balans (balans=1) b Lägg till 1 B skriv tillbaka resultatet (balans=2)“Denna interfoliering är bra-vi slutar med balans 2, så både A och B framgångsrikt sätta i en dollar. Men vad händer om interfolieringen såg ut så här:“a Få balans (balans=0) B få balans (balans=0)a Lägg till 1 b Lägg till 1 A skriv tillbaka resultatet (balans=1) b skriv tillbaka resultatet (balans=1) “‘ balansen är nu 1-A: S dollar förlorades! A och B läste båda saldot samtidigt, beräknade separata slutliga saldon och tävlade sedan för att lagra tillbaka det nya saldot-vilket misslyckades med att ta hänsyn till den andras insättning.## Race Conditiondetta är ett exempel på ett **race condition**. Ett tävlingsvillkor innebär att programmets korrekthet (tillfredsställelsen av postvillkor och invarianter) beror på den relativa tidpunkten för händelser i samtidiga beräkningar A och B. När detta händer säger Vi “A är i ett lopp med B.”Vissa interleavings av händelser kan vara OK, i den meningen att de överensstämmer med vad en enda, icke-pågående process skulle producera, men andra interleavings ger felaktiga svar-bryter mot postvillkor eller invarianter.## Tweaking koden hjälper intealla dessa versioner av bankkontokoden uppvisar samma race villkor: “‘ java / / version 1private statisk void insättning () { balans = balans + 1;} privat statisk void uttag() { balans = balans-1;}“java// version 2private statisk void insättning () { balans + = 1;} privat statisk void uttag () { balans – = 1;}`””java// version 3private static void deposit() { ++balance;}private static void retrait() { –balance;}” `du kan inte berätta bara från att titta på Java-kod hur processorn kommer att utföra det. Du kan inte berätta vad de odelbara operationerna-atomoperationerna – kommer att vara. Det är inte atomärt bara för att det är en rad Java. Det berör inte balans bara en gång bara för att balansidentifieraren bara förekommer en gång i raden. Java-kompilatorn, och i själva verket processorn själv, gör inga åtaganden om vilka lågnivåoperationer den kommer att generera från din kod. Faktum är att en typisk modern Java-kompilator producerar exakt samma kod för alla tre av dessa versioner!Den viktigaste lektionen är att du inte kan berätta genom att titta på ett uttryck om det kommer att vara säkert från rasförhållanden.

## Omordningdet är ännu värre än det, faktiskt. Tävlingsvillkoren på bankkontosaldot kan förklaras i termer av olika interleavings av sekventiella operationer på olika processorer. Men när du använder flera variabler och flera processorer kan du inte ens räkna med ändringar av de variabler som visas i samma ordning.Här är ett exempel:“javaprivate boolean ready = false; private int answer = 0;// computeAnswer körs i en threadprivate void computeAnswer() { answer = 42; ready = true;} / / useAnswer körs i en annan threadprivate void useAnswer() { while (!klar) { tråd.avkastning ();} om (Svar == 0) kasta ny RuntimeException (“svaret var inte klart!”);} “‘Vi har två metoder som körs i olika trådar. ‘computeAnswer’ gör en lång beräkning och kommer äntligen med svaret 42, som det sätter i svarvariabeln. Sedan sätter den` ready ‘ – variabeln till true, för att signalera till metoden som körs i den andra tråden, `useAnswer`, att svaret är klart för det att använda. Om man tittar på koden,` svar ‘ är inställd innan redo är inställd, så när `useAnswer` ser `redo` som sant, då verkar det rimligt att det kan anta att `svaret` kommer att vara 42, höger? Inte så.Problemet är att moderna kompilatorer och processorer gör många saker för att göra koden snabb. En av dessa saker är att göra tillfälliga kopior av variabler som svar och redo i snabbare Lagring (register eller cachar på en processor) och arbeta med dem tillfälligt innan de så småningom lagras tillbaka till deras officiella plats i minnet. Storebacken kan förekomma i en annan ordning än variablerna manipulerades i din kod. Här är vad som kan hända under omslagen (men uttryckt i Java-syntax för att göra det klart). Processorn skapar effektivt två tillfälliga variabler ` ‘tmpr’ och ‘ tmpa`, för att manipulera fälten redo och svara:”‘javaprivate void computeAnswer () { boolean tmpr = ready; int tmpa = answer; tmpa = 42; tmpr = true; ready = tmpr; / / < – vad händer om useAnswer() interleaves här? // ready är inställd, men svaret är inte. answer = tmpa;} “‘ mitx: 2bf4beb7ffd5437bbbb9c782bb99b54e Race Conditions## meddelande passerar exempel

Låt oss nu titta på meddelandet passerar strategi för vårt bankkonto exempel.Nu är inte bara bankomatmodulerna, men kontona är också moduler. Moduler interagerar genom att skicka meddelanden till varandra. Inkommande förfrågningar placeras i en kö som ska hanteras en i taget. Avsändaren slutar inte arbeta medan han väntar på ett svar på sin begäran. Den hanterar fler förfrågningar från sin egen kö. Svaret på sin begäran kommer så småningom tillbaka som ett annat meddelande.Tyvärr eliminerar inte meddelandepassningen möjligheten till rasförhållanden. Antag att varje konto stöder ‘get-balance’ och` dra tillbaka ‘ operationer, med motsvarande meddelanden. Två användare, på Bankomat A och B, försöker båda ta ut en dollar från samma konto. De kontrollerar saldot först för att se till att de aldrig tar ut mer än kontot innehar, eftersom kassakrediter utlöser stora bankstraff:“get-balanceif balance >= 1 Dra sedan tillbaka 1` ” problemet är igen interfoliering, men den här gången interfoliering av *meddelanden* skickas till bankkontot, snarare än *instruktioner* exekveras av A och B. Om kontot börjar med en dollar i det, då vad interfoliering av meddelanden kommer att lura A och B att tro att de kan både ta ut en dollar och därmed överdraga kontot?En lektion här är att du måste noggrant välja verksamheten för en meddelandepassande modell. ‘dra tillbaka-om-tillräckliga-medel’ skulle vara en bättre operation än bara`dra tillbaka’.## Samtidighet är svårt att testa och Felsökaom vi inte har övertygat dig om att samtidighet är knepig, här är det värsta av det. Det är väldigt svårt att upptäcka tävlingsförhållanden med hjälp av testning. Och även när ett test har hittat ett fel kan det vara mycket svårt att lokalisera det till den del av programmet som orsakar det.Samtidighet buggar uppvisar mycket dålig Reproducerbarhet. Det är svårt att få dem att hända på samma sätt två gånger. Interfoliering av instruktioner eller meddelanden beror på den relativa tidpunkten för händelser som påverkas starkt av miljön. Förseningar kan orsakas av andra program som körs, annan nätverkstrafik, beslut om schemaläggning av operativsystem, variationer i processorns klockhastighet etc. Varje gång du kör ett program som innehåller ett tävlingsförhållande kan du få olika beteenden. Dessa typer av buggar är **heisenbugs**, som är nondeterministiska och svåra att reproducera, i motsats till en “bohrbug”, som dyker upp upprepade gånger när du tittar på det. Nästan alla buggar i sekventiell programmering är bohrbugs.En heisenbug kan till och med försvinna när du försöker titta på den med `println` eller `debugger`! Anledningen är att utskrift och felsökning är så mycket långsammare än andra operationer, ofta 100-1000x långsammare, att de dramatiskt förändrar tidpunkten för operationer och interfoliering. Så sätter en enkel utskrift uttalande i cashMachine (): “‘ javaprivate statisk void cashMachine () {för (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) {insättning (); / / sätta en dollar i uttag (); / / ta tillbaka ut systemet.ut.println (balans); / / gör felet försvinner! }}“`…och plötsligt är balansen alltid 0, som önskat, och felet verkar försvinna. Men det är bara maskerat, inte riktigt fixat. En förändring i timing någon annanstans i programmet kan plötsligt få buggen att komma tillbaka.Samtidighet är svårt att få rätt. En del av poängen med denna läsning är att skrämma dig lite. Under de kommande flera avläsningarna ser vi principiella sätt att utforma samtidiga program så att de är säkrare från dessa typer av buggar.mitx: 704b9c4db3c6487c9f1549956af8bfc8 testa samtidighet## sammanfattning + samtidighet: flera beräkningar som körs samtidigt + delat minne & meddelandepassande paradigmer+ processer & trådar + processen är som en virtuell dator; tråden är som en virtuell processor+ rasförhållanden + när resultatets korrekthet (postvillkor och invarianter) beror på den relativa tidpunkten för händelserdessa tankar ansluter till våra tre nyckelegenskaper för bra programvara, mestadels på dåliga sätt. Samtidighet är nödvändig men det orsakar allvarliga problem för korrekthet. Vi kommer att arbeta med att åtgärda dessa problem i de närmaste avläsningarna.+ * * Säker från buggar.** Samtidighet buggar är några av de svåraste buggar att hitta och åtgärda, och kräver noggrann design för att undvika.+ * * Lätt att förstå.** Att förutsäga hur samtidig kod kan interleave med andra samtidiga kod är mycket svårt för programmerare att göra. Det är bäst att utforma på ett sådant sätt att programmerare inte behöver tänka på det. + * * Redo för förändring.** Inte särskilt relevant här.