Læsning 17: samtidighed

#### programmer i 6.005

#### mål + meddelelse passerer & delt hukommelse+ processer & tråde+ tid udskæring+ Race betingelser## samtidighed*samtidighed* betyder flere beregninger sker på samme tid. Samtidighed er overalt i moderne programmering, uanset om vi kan lide det eller ej:+ flere computere i et netværk+ flere applikationer, der kører på en computer+ flere processorer i en computer (i dag, ofte flere processorkerner på en enkelt chip) faktisk er samtidighed afgørende i moderne programmering:+ hjemmesider skal håndtere flere samtidige brugere.+ Mobile apps skal gøre noget af deres behandling på servere (“i skyen”).+ Grafiske brugergrænseflader kræver næsten altid baggrundsarbejde, der ikke afbryder brugeren. For eksempel samler Eclipse din Java-kode, mens du stadig redigerer den.At kunne programmere med samtidighed vil stadig være vigtigt i fremtiden. Processorens clockhastigheder stiger ikke længere. I stedet får vi flere kerner med hver ny generation af chips. Så i fremtiden, for at få en beregning til at køre hurtigere, bliver vi nødt til at opdele en beregning i samtidige stykker.## To modeller til samtidig Programmeringder er to almindelige modeller til samtidig programmering: *delt hukommelse* og *meddelelse passerer*.

**delt hukommelse.** I den delte hukommelsesmodel for samtidighed interagerer samtidige moduler ved at læse og skrive Delte Objekter i hukommelsen. Andre eksempler på den delte hukommelsesmodel: + A og B kan være to processorer (eller processorkerner) på den samme computer, der deler den samme fysiske hukommelse.+ A og B kan være to programmer, der kører på den samme computer, og deler et fælles filsystem med filer, de kan læse og skrive.+ A og B kan være to tråde i det samme Java-program (vi forklarer, hvad en tråd er nedenfor), der deler de samme Java-objekter.

**meddelelse passerer.** I meddelelsesovergangsmodellen interagerer samtidige moduler ved at sende meddelelser til hinanden via en kommunikationskanal. Moduler sender beskeder, og indgående meddelelser til hvert modul står i kø til håndtering. Eksempler inkluderer: + A og B kan være to computere i et netværk, der kommunikerer via netværksforbindelser.+ A og B kan være en internetserver og en internetserver-a åbner en forbindelse til B, beder om en hjemmeside, og B sender hjemmesidens data tilbage til A.+ A og B kan være en instant messaging klient og server.+ A og B kan være to programmer, der kører på den samme computer, hvis input og output er forbundet med et rør, som `ls | grep` skrevet i en kommandoprompt.## Processer, tråde, tidsskæringbesked-passing og shared-memory modeller handler om, hvordan samtidige moduler kommunikerer. De samtidige moduler selv kommer i to forskellige slags: processer og tråde.**Proces**. En proces er en forekomst af et kørende program, der er *isoleret* fra andre processer på den samme maskine. Især har den sin egen private del af maskinens hukommelse.Procesabstraktionen er en * virtuel computer*. Det får programmet til at føle, at det har hele maskinen til sig selv-som om der er oprettet en frisk computer med frisk hukommelse bare for at køre dette program.Ligesom computere, der er forbundet på tværs af et netværk, deler processer normalt ingen hukommelse mellem dem. En proces kan ikke få adgang til en anden proces hukommelse eller objekter på alle. Deling af hukommelse mellem processer er * mulig * på de fleste operativsystemer, men det kræver særlig indsats. I modsætning hertil er en ny proces automatisk klar til meddelelsesoverførsel, fordi den oprettes med standard input & outputstrømme, som er `systemet.ud `og ‘System.in’ streams du har brugt i Java.**Tråd**. En tråd er et sted for kontrol inde i et kørende program. Tænk på det som et sted i det program, der køres, plus stakken med metodeopkald, der førte til det sted, som det vil være nødvendigt at vende tilbage til.Ligesom en proces repræsenterer en virtuel computer, repræsenterer trådabstraktionen en * virtuel processor*. At lave en ny tråd simulerer at lave en frisk processor inde i den virtuelle computer repræsenteret af processen. Denne nye virtuelle processor kører det samme program og deler den samme hukommelse som andre tråde i processen.Tråde er automatisk klar til delt hukommelse, fordi tråde deler al hukommelse i processen. Det kræver særlig indsats for at få “tråd-lokal” hukommelse, der er privat til en enkelt tråd. Det er også nødvendigt at oprette Besked-passing eksplicit, ved at oprette og bruge kø datastrukturer. Vi vil tale om, hvordan man gør det i en fremtidig læsning.

Hvordan kan jeg have mange samtidige tråde med kun en eller to processorer i min computer? Når der er flere tråde end processorer, simuleres samtidighed ved **tidsskæring**, hvilket betyder, at processoren skifter mellem tråde. Figuren til højre viser, hvordan tre tråde T1, T2 og T3 kan være tidsskåret på en maskine, der kun har to faktiske processorer. I figuren fortsætter tiden nedad, så i første omgang kører en processor tråd T1 og den anden kører tråd T2, og derefter skifter den anden processor til at køre tråd T3. Tråd T2 simpelthen pauser, indtil dens næste gang skive på den samme processor eller en anden processor.På de fleste systemer sker tidsskæring uforudsigeligt og ikke-bestemt, hvilket betyder, at en tråd kan sættes på pause eller genoptages når som helst.

Mikkel:C613ec53e92840a4a506f3062c994673 processer & tråde## delt hukommelse Eksempellad os se på et eksempel på et delt hukommelsessystem. Pointen med dette eksempel er at vise, at samtidig programmering er svært, fordi det kan have subtile fejl.

Forestil dig, at en bank har pengeautomater, der bruger en delt hukommelsesmodel, så alle pengeautomater kan læse og skrive de samme kontoobjekter i hukommelsen.For at illustrere, hvad der kan gå galt, lad os forenkle banken ned til en enkelt konto med en dollarsaldo gemt i `balance` – variablen og to operationer `depositum` og `hæve`, der blot tilføjer eller fjerner en dollar: “java// Antag, at alle pengeautomater deler en enkelt bankkontoprivat statisk int-balance = 0;privat statisk ugyldig indbetaling() { balance = balance + 1;}privat statisk ugyldig tilbagetrækning() { balance = balance-1;}“kunder bruger pengeautomaterne til at udføre transaktioner som denne:“javadeposit(); // sæt en dollar itrække(); // tag det ud igen “‘ i dette enkle eksempel er hver transaktion kun et indskud på en dollar efterfulgt af en tilbagetrækning på en dollar, så det skal lade saldoen på kontoen være uændret. I løbet af dagen behandler hver pengeautomat i vores netværk en række indbetalings – /udbetalingstransaktioner.”‘java / / hver ATM udfører en masse transaktioner, der / / ændrer saldoen, men lader den være uændret bagefter private static void cashMachine () {for (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) { deposit (); / / sæt en dollar i træk (); // take it back out}} “‘ så i slutningen af dagen, uanset hvor mange pengeautomater der kørte, eller hvor mange transaktioner vi behandlede, skulle vi forvente, at kontosaldoen stadig er 0.Men hvis vi kører denne kode, opdager vi ofte, at balancen i slutningen af dagen er *ikke* 0. Hvis mere end et` cashMachine () ` – opkald kører på samme tid-siger på separate processorer i samme computer-så er` balance ‘ muligvis ikke nul i slutningen af dagen. Hvorfor ikke?## Interleavingher er en ting, der kan ske. Antag, at to pengeautomater, A og B, begge arbejder på et depositum på samme tid. Sådan opdeles indbetalingstrinnet() typisk i processorinstruktioner på lavt niveau` “‘ få balance (balance=0) tilføj 1 skriv resultatet tilbage (balance=1)“Når A og B kører samtidigt, går disse instruktioner på lavt niveau sammen med hinanden (nogle kan endda være samtidige i en vis forstand, men lad os bare bekymre os om interleaving for nu):”‘A get balance (balance=0) a add 1 A skriv tilbage resultatet (balance=1) b få balance (balance=1) B tilføj 1 B skriv resultatet tilbage (balance=2)“Denne interleaving er fint-vi ender med balance 2, så både A og B med succes sat i en dollar. Men hvad nu hvis interleaving så sådan ud“`a Få balance (balance=0) b få balance (balance=0)a tilføj 1 B tilføj 1 A skriv resultatet tilbage (balance=1) B skriv resultatet tilbage (balance=1) “‘saldoen er nu 1-A’ S dollar var tabt! A og B læste begge saldoen på samme tid, beregnede separate endelige saldi og kørte derefter for at gemme den nye saldo-som ikke tog hensyn til den andres indbetaling.## Race Conditiondette er et eksempel på en**race condition**. En racebetingelse betyder, at programmets rigtighed (tilfredshed med postbetingelser og invarianter) afhænger af den relative timing af begivenheder i samtidige beregninger A og B. Når dette sker, siger Vi “A er i et løb med B.”Nogle interleavings af begivenheder kan være OK, i den forstand, at de er i overensstemmelse med, hvad en enkelt, ikke-nuværende proces ville producere, men andre interleavings producerer forkerte svar-overtræder postconditions eller invariants.## Tilpasning af koden hjælper ikke alle disse versioner af bankkontokoden udviser den samme race-tilstand:` ‘java / / version 1private static void deposit () { balance = balance + 1;} privat statisk void tilbagetrækning () { balance = balance-1;} “”” java / / version 2private static void deposit () { balance + = 1;} privat statisk void tilbagetrækning () {balance – = 1;} “””java / / version 3private static void deposit () {++balance;}privat statisk void tilbagetrækning () {–balance;}“Du kan ikke fortælle bare fra at se på Java-kode, hvordan processoren skal udføre den. Du kan ikke fortælle, hvad de udelelige operationer-atomoperationerne-vil være. Det er ikke atomisk, bare fordi det er en linje af Java. Det berører ikke balance kun en gang, bare fordi balanceidentifikatoren kun forekommer en gang i linjen. Java-kompilatoren, og faktisk selve processoren, forpligter sig ikke til, hvilke operationer på lavt niveau det vil generere fra din kode. Faktisk producerer en typisk moderne Java-kompilator nøjagtig den samme kode til alle tre af disse versioner!Den vigtigste lektion er, at du ikke kan fortælle ved at se på et udtryk, om det vil være sikkert fra raceforhold.

## Genbestillingdet er faktisk endnu værre end det. Løbsbetingelsen på bankkontosaldoen kan forklares med hensyn til forskellige interleavings af sekventielle operationer på forskellige processorer. Men faktisk, når du bruger flere variabler og flere processorer, kan du ikke engang regne med ændringer i de variabler, der vises i samme rækkefølge.Her er et eksempel:“javaprivate boolean ready = false;privat int svar = 0;// computesvar kører i en threadprivate void computesvar() { svar = 42; ready = true;}// usesvar kører i en anden threadprivate void usesvar() { mens (!klar) { tråd.udbytte ();} hvis (Svar == 0) kast ny Runtimeundtagelse (“svaret var ikke klar!”);} “‘Vi har to metoder, der køres i forskellige tråde. ‘computersvar’ gør en lang beregning, endelig kommer op med svaret 42, som det sætter i svarvariablen. Derefter indstiller den `klar` – variablen til sand for at signalere til metoden, der kører i den anden tråd, `brugssvar`, at svaret er klar til brug. Når man ser på koden, er` svar ‘indstillet, før klar er indstillet, så når` useansvar `ser` klar `som sandt, synes det rimeligt, at det kan antage, at` svaret’ vil være 42, ikke? Ikke så.Problemet er, at moderne kompilatorer og processorer gør mange ting for at gøre koden hurtig. En af disse ting er at lave midlertidige kopier af variabler som svar og klar i hurtigere opbevaring (registre eller cacher på en processor) og arbejde med dem midlertidigt, før de til sidst gemmer dem tilbage til deres officielle placering i hukommelsen. Storebacken kan forekomme i en anden rækkefølge end variablerne blev manipuleret i din kode. Her er hvad der kan ske under omslagene (men udtrykt i Java-syntaks for at gøre det klart). Processoren skaber effektivt to midlertidige variabler, `tmpr` og `tmpa’, for at manipulere felterne klar og svar:”‘javaprivate void computesvar () { boolean tmpr = ready; int tmpa = svar; tmpa = 42; tmpr = true; ready = tmpr; / / < – hvad sker der, hvis usesvar() interleaves her? // klar er indstillet, men svaret er ikke. svar = tmpa;}“Mitch:2bf4beb7ffd5437bbbb9c782bb99b54e Race betingelser## Message Passing eksempel

lad os nu se på message-passing tilgang til vores bankkonto eksempel.Nu er ikke kun pengeautomatmodulerne, men regnskabet er også moduler. Moduler interagerer ved at sende beskeder til hinanden. Indgående anmodninger placeres i en kø, der skal håndteres en ad gangen. Afsenderen stopper ikke med at arbejde, mens han venter på et svar på sin anmodning. Det håndterer flere anmodninger fra sin egen kø. Svaret på anmodningen kommer til sidst tilbage som en anden besked.Desværre eliminerer meddelelsesoverføring ikke muligheden for raceforhold. Antag, at hver konto understøtter` get-balance `og` tilbagetræk ‘ operationer med tilsvarende meddelelser. To brugere, på Pengeautomat A og B, forsøger begge at trække en dollar fra samme konto. De kontrollerer saldoen først for at sikre, at de aldrig trækker mere ud, end kontoen har, fordi overtræk udløser store bankbøder:“get-balanceif balance >= 1 derefter trække 1 “‘ problemet er igen interleaving, men denne gang interleaving af *meddelelser* sendt til bankkontoen, snarere end *instruktioner* udført af A og B. hvis kontoen starter med en dollar i den, så hvilken interleaving af meddelelser vil narre A og B til at tro, at de begge kan trække en dollar og derved overtrække kontoen?En lektion her er, at du nøje skal vælge operationerne i en meddelelsesovergangsmodel. ‘trække-hvis-tilstrækkelige-midler’ ville være en bedre operation end blot `trække`.## Samtidighed er svært at teste og DebugIf vi ikke har overbevist dig om, at samtidighed er vanskelig, her er det værste af det. Det er meget svært at opdage løbsbetingelser ved hjælp af test. Og selv når en test har fundet en fejl, kan det være meget svært at lokalisere det til den del af programmet, der forårsager det.Concurrency bugs udviser meget dårlig Reproducerbarhed. Det er svært at få dem til at ske på samme måde to gange. Interleaving af instruktioner eller meddelelser afhænger af den relative timing af begivenheder, der er stærkt påvirket af miljøet. Forsinkelser kan skyldes andre kørende programmer, anden netværkstrafik, beslutninger om planlægning af operativsystemer, variationer i processorens clockhastighed osv. Hver gang du kører et program, der indeholder en race tilstand, kan du få forskellige adfærd. Disse slags bugs er * * heisenbugs**, som er ikke-deterministiske og svære at reproducere, i modsætning til en “bohrbug”, som dukker op gentagne gange, når du ser på det. Næsten alle fejl i sekventiel programmering er bohrbugs.En heisenbug kan endda forsvinde, når du prøver at se på den med `println` eller `debugger`! Årsagen er, at udskrivning og fejlfinding er så meget langsommere end andre operationer, ofte 100-1000 gange langsommere, at de dramatisk ændrer tidspunktet for operationer og interleaving. Så indsætter en simpel udskriftsopgørelse i cashMachine (): “‘ javaprivate static void cashMachine () {for (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) {deposit (); / / sæt en dollar i træk (); / / tag det tilbage ud System.uden.println (balance); // gør fejlen forsvinde! }}“`…og pludselig er balancen altid 0, som ønsket, og fejlen ser ud til at forsvinde. Men det er kun maskeret, ikke rigtig fast. En ændring i timingen et andet sted i programmet kan pludselig få fejlen til at komme tilbage.Samtidighed er svært at få ret. En del af pointen med denne læsning er at skræmme dig lidt. I løbet af de næste flere aflæsninger ser vi principielle måder at designe samtidige programmer på, så de er sikrere fra disse slags fejl.Mitch:704b9c4db3c6487c9f1549956af8bfc8 test samtidighed # # sammendrag + samtidighed: flere beregninger kører samtidigt+ delt-hukommelse & message-passing paradigmer+ processer & tråde + proces er som en virtuel computer; tråd er som en virtuel processor+ Race betingelser + når rigtigheden af resultatet (postconditions og invariants) afhænger af den relative timing af begivenhederdisse ideer forbinder til vores tre nøgleegenskaber ved godt program hovedsagelig på dårlige måder. Samtidighed er nødvendig, men det medfører alvorlige problemer for korrekthed. Vi vil arbejde på at løse disse problemer i de næste par aflæsninger.+ * * Sikker fra bugs.** Concurrency bugs er nogle af de sværeste bugs at finde og rette, og kræver omhyggeligt design for at undgå.+ * * Let at forstå.** Forudsige, hvordan samtidige kode kan interleave med andre samtidige kode er meget svært for programmører at gøre. Det er bedst at designe på en sådan måde, at programmører ikke behøver at tænke over det. + * * Klar til forandring.** Ikke særlig relevant her.