Lesing 17: Samtidighet

#### Programvare i 6.005

#### Mål + Melding passerer & delt minne + Prosesser & tråder + tid slicing + Race conditions# # Samtidighet * Samtidighet * betyr flere beregninger skjer samtidig. Samtidighet er overalt i moderne programmering, enten vi liker det eller ikke: + flere datamaskiner i et nettverk + Flere applikasjoner som kjører på en datamaskin+ Flere prosessorer i en datamaskin (i dag, ofte flere prosessorkjerner på en enkelt chip) faktisk er samtidighet viktig i moderne programmering:+ Nettsteder må håndtere flere samtidige brukere.+ Mobile apps trenger å gjøre noe av sin behandling på servere (“i skyen”).+ Grafiske brukergrensesnitt krever nesten alltid bakgrunnsarbeid som ikke forstyrrer brukeren. Eclipse kompilerer For eksempel Java-koden din mens du fortsatt redigerer Den.Å kunne programmere med samtidighet vil fortsatt være viktig i fremtiden. Prosessorens klokkehastigheter øker ikke lenger. I stedet får vi flere kjerner med hver ny generasjon sjetonger. Så i fremtiden, for å få en beregning til å løpe raskere, må vi dele opp en beregning i samtidige stykker.## To Modeller For Samtidig Programmingdet er to vanlige modeller for samtidig programmering: * delt minne * og * melding passerer*.

**Delt minne.** I delt minne modell av samtidighet, samtidige moduler samhandle ved å lese og skrive delte objekter i minnet. Andre eksempler på modellen for delt minne: + A og B kan være to prosessorer (eller prosessorkjerner) i samme datamaskin, som deler samme fysiske minne.+ A Og B kan være to programmer som kjører på samme datamaskin, og deler et felles filsystem med filer de kan lese og skrive.+ A og B kan være to tråder i Samme Java-program (vi forklarer hva en tråd er under), og deler De samme Java-objektene.

**Melding passerer.** I meldingsmodellen samhandler samtidige moduler ved å sende meldinger til hverandre via en kommunikasjonskanal. Moduler sende av meldinger, og innkommende meldinger til hver modul er kø for håndtering. Eksempler er: + A og B kan være to datamaskiner i et nettverk som kommuniserer via nettverkstilkoblinger.+ A og B kan være en nettleser og en webserver-a åpner en tilkobling Til B, ber Om en nettside, og B sender nettsidedataene tilbake til A.+ A og B kan være en direktemeldingsklient og-server.+ A og B kan være to programmer som kjører på samme datamaskin hvis inngang og utgang er koblet til med et rør, som `ls | grep` skrevet inn i en ledetekst.## Prosesser, Tråder, tidsskivingmeldings-og delte minnemodeller handler om hvordan samtidige moduler kommuniserer. De samtidige modulene selv kommer i to forskjellige typer: prosesser og tråder.**Prosess**. En prosess er en forekomst av et kjørende program som er * isolert * fra andre prosesser på samme maskin. Spesielt har den sin egen private del av maskinens minne.Prosessen abstraksjon er en * virtuell datamaskin*. Det gjør at programmet føler at det har hele maskinen til seg selv-som en ny datamaskin er opprettet, med nytt minne, bare for å kjøre det programmet.Akkurat som datamaskiner som er koblet over et nettverk, deler prosesser normalt ikke noe minne mellom dem. En prosess kan ikke få tilgang til en annen prosess minne eller objekter i det hele tatt. Deling av minne mellom prosesser er * mulig * på de fleste operativsystemer, men det trenger spesiell innsats. Derimot er en ny prosess automatisk klar for meldingsoverføring, fordi den er opprettet med standardinngang & utgangsstrømmer, som Er Systemet.ut `og ‘System.in’ strømmer du har brukt I Java.**Tråd**. En tråd er et kontrollpunkt inne i et løpende program. Tenk på det som et sted i programmet som kjøres, pluss stabelen med metodekall som førte til det stedet som det vil være nødvendig å returnere gjennom.Akkurat som en prosess representerer en virtuell datamaskin, representerer trådabstraksjonen en * virtuell prosessor*. Å lage en ny tråd simulerer å lage en ny prosessor inne i den virtuelle datamaskinen representert av prosessen. Denne nye virtuelle prosessoren kjører det samme programmet og deler samme minne som andre tråder i prosessen.Tråder er automatisk klare for delt minne, fordi tråder deler alt minnet i prosessen. Den trenger spesiell innsats for å få” tråd-lokal ” minne som er privat til en enkelt tråd. Det er også nødvendig å sette opp melding-passerer eksplisitt, ved å opprette og bruke kø datastrukturer. Vi snakker om hvordan du gjør det i en fremtidig lesning.

Hvordan kan jeg ha mange samtidige tråder med bare en eller to prosessorer i datamaskinen min? Når det er flere tråder enn prosessorer, simuleres samtidighet med * * tidsskive**, noe som betyr at prosessoren bytter mellom tråder. Figuren til høyre viser hvordan tre tråder T1, T2 og T3 kan være tidsskåret på en maskin som bare har to faktiske prosessorer. I figuren går tiden nedover, så først kjører en prosessor tråd T1 og den andre kjører tråd T2, og deretter bytter den andre prosessoren til å kjøre tråd T3. Tråd T2 bare pauser, til sin neste gang skive på samme prosessor eller en annen prosessor.På de fleste systemer skjer tidsskåret uforutsigbart og ikke-deterministisk, noe som betyr at en tråd kan bli stoppet eller gjenopptatt når som helst.

mitx:c613ec53e92840a4a506f3062c994673 Prosesser & Tråder # # Delt Minne Eksempella oss se på et eksempel på et delt minnesystem. Poenget med dette eksemplet er å vise at samtidig programmering er vanskelig, fordi det kan ha subtile feil.

Tenk deg at en bank har minibanker som bruker en delt minnemodell, slik at alle minibankene kan lese og skrive de samme kontoobjektene i minnet.For å illustrere hva som kan gå galt, la oss forenkle banken ned til en enkelt konto, med en dollarbalanse lagret i `balanse` variabelen, og to operasjoner `innskudd` og `uttak` som bare legger til eller fjerner en dollar: “java// anta at alle minibankene deler en enkelt bankkontoprivate static int balance = 0;private static void deposit() { balance = balance + 1;}private static void withdraw() { balance = balance – 1;}“Kunder bruker minibankene til å gjøre transaksjoner som dette:“javadeposit(); // put en dollar inwithdraw(); /”i dette enkle eksempelet er hver transaksjon bare et innskudd på en dollar etterfulgt av et uttak på en dollar, så det bør la saldoen på kontoen være uendret. Gjennom dagen behandler hver minibank i vårt nettverk en sekvens av innskudd / uttak transaksjoner.”‘java / / hver ATM gjør en haug med transaksjoner som / / endre balanse, men la det uendret afterwardprivate statisk ugyldig cashMachine () {for (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) { innskudd (); / / sette en dollar i uttak(); /”‘så på slutten av dagen, uansett hvor mange minibanker som kjørte, eller hvor mange transaksjoner vi behandlet, bør vi forvente at kontosaldoen fortsatt vil være 0.Men hvis vi kjører denne koden, oppdager vi ofte at balansen på slutten av dagen er *ikke * 0. Hvis mer enn en cashMachine () – samtale kjører samtidig-si på separate prosessorer i samme datamaskin-så kan saldoen ikke være null på slutten av dagen. Hvorfor ikke?## InterleavingHere er en ting som kan skje . Anta at to minibanker, A og B, begge jobber på et innskudd samtidig. Her er hvordan innskudd() trinn vanligvis bryter ned i lavt nivå prosessor instruksjoner: “‘ få balanse (balanse=0) legg til 1 skriv tilbake resultatet (balanse=1)“når A og B kjører samtidig, disse lavt nivå instruksjoner interleave med hverandre (noen kan også være samtidig i noen forstand, men la oss bare bekymre interleaving for nå):`’ A få balanse (balanse=0)a legg til 1 a skriv tilbake resultatet (balanse=1) b få balanse (balanse=1) b legg til 1 B skriv tilbake resultatet (balanse=2)“Denne interleaving er bra-vi ender med balanse 2, så Både A og B lykkes med å sette inn en dollar. Men hva om interleaving så slik ut` “‘a få balanse (balanse=0) b få balanse (balanse=0) a legg til 1 B legg til 1 a skriv tilbake resultatet (balanse=1) b skriv tilbake resultatet (balanse=1)“balansen er nå 1-A’ s dollar var tapt! A og B både lese balansen samtidig, beregnet separate endelige saldoer, og deretter kjørte for å lagre tilbake den nye balansen-som ikke klarte å ta den andre innskudd i betraktning.## Race Conditiondette er et eksempel på en * * race condition**. En løpsbetingelse betyr at programmets korrekthet (tilfredsstillelsen av postconditions og invariants) avhenger av den relative timingen av hendelser i samtidige beregninger A og B. Når dette skjer, sier Vi ” A er i et løp Med B.”Noen interleavings av hendelser kan VÆRE OK, i den forstand at de er i samsvar med hva en enkelt, nonconcurrent prosess ville produsere, men andre interleavings produserer feil svar-brudd på postconditions eller invariants.## Tweaking Koden Vil Ikke Hjelpealle disse versjonene av bankkontokoden har samme løpstilstand` “‘java// versjon 1private static void deposit () { balance = balance + 1;} private static void uttak () { balance = balance-1;} “” java / / versjon 2private static void deposit () { balance + = 1;} private static void uttak () { balance – = 1;}`””java// versjon 3private static void deposit() { ++balance;}private static void withdraw() { –balance;}” `du kan ikke fortelle bare fra Å se På Java-koden hvordan prosessoren skal utføre den. Du kan ikke fortelle hva de udelelige operasjonene-atomoperasjonene – vil være. Det er ikke atomisk bare fordi Det er En Linje Av Java. Det berører ikke balanse bare en gang bare fordi balanseidentifikatoren bare oppstår en gang i linjen. Java-kompilatoren, og faktisk selve prosessoren, gir ingen forpliktelser om hvilke operasjoner på lavt nivå det vil generere fra koden din. Faktisk produserer en typisk Moderne Java-kompilator nøyaktig samme kode for alle tre av disse versjonene!Nøkkelleksjonen er at du ikke kan fortelle ved å se på et uttrykk om det vil være trygt fra raseforhold.

## Reorderingdet er enda verre enn det, faktisk. Løpsbetingelsen på bankkontosaldoen kan forklares i form av forskjellige interleavings av sekvensielle operasjoner på forskjellige prosessorer. Men faktisk, når du bruker flere variabler og flere prosessorer, kan du ikke engang regne med endringer i de variablene som vises i samme rekkefølge.Her er et eksempel:“javaprivate boolean ready = false;private int answer = 0;// computeAnswer kjører i en threadprivate void computeAnswer () {answer = 42; ready = true;}// useAnswer kjører i en annen threadprivate void useAnswer () {while (!klar) { Tråd.yield ();} hvis (svar == 0) kast ny RuntimeException (“svaret var ikke klart!`);} “`Vi har to metoder som kjøres i forskjellige tråder. ‘computeAnswer’ gjør en lang beregning, endelig kommer opp med svaret 42, som det setter i svarvariabelen. Deretter setter den `klar` variabelen til sann, for å signalisere til metoden som kjører i den andre tråden, `useAnswer’, at svaret er klart for bruk. Ser på koden,` svar ‘er satt før klar er satt, så når ‘useAnswer’ ser ‘klar’ som sant, så virker det rimelig at det kan anta at ‘svaret’ vil være 42, ikke sant? Ikke så.Problemet er at moderne kompilatorer og prosessorer gjør mange ting for å gjøre koden rask. En av disse tingene er å lage midlertidige kopier av variabler som svar og klar i raskere lagring (registre eller cacher på en prosessor), og jobbe med dem midlertidig før de til slutt lagrer dem tilbake til deres offisielle plassering i minnet. Storeback kan oppstå i en annen rekkefølge enn variablene ble manipulert i koden. Her er hva som kan skje under dekslene (men uttrykt I Java syntaks for å gjøre det klart). Prosessoren skaper effektivt to midlertidige variabler ` ‘tmpr’ og ‘tmpa’, for å manipulere feltene klare og svare:”‘javaprivate void computeAnswer () { boolsk tmpr = klar; int tmpa = svar; tmpa = 42; tmpr = sant; klar = tmpr; / / < – hva skjer hvis useAnswer () interleaves her? // klar er satt, men svaret er ikke. svar = tmpa;} “‘ mitx: 2bf4beb7ffd5437bbbb9c782bb99b54e Race Conditions # # Message Passing Example

La Oss nå se på meldings-passing-tilnærmingen til vårt bankkontoeksempel.Nå er ikke bare minibankmodulene, men kontoene er også moduler. Moduler samhandler ved å sende meldinger til hverandre. Innkommende forespørsler er plassert i en kø som skal håndteres en om gangen. Avsenderen slutter ikke å fungere mens du venter på svar på forespørselen. Den håndterer flere forespørsler fra sin egen kø. Svaret på forespørselen kommer til slutt tilbake som en annen melding.Dessverre eliminerer meldingspassering ikke muligheten for raseforhold. Anta at hver konto støtter ‘get-balanse’ og` uttak ‘ operasjoner, med tilsvarende meldinger. To brukere, på minibank A Og B, prøver begge å trekke en dollar fra samme konto. De sjekker saldoen først for å sikre at de aldri tar ut mer enn kontoen holder, fordi overtrekk utløser store bankstraff:“get-balancehvis balanse >= 1 deretter trekker 1 “‘ problemet er igjen interleaving, men denne gangen interleaving av *meldinger* sendt til bankkontoen, i stedet for *instruksjonene* utført Av A og B. Hvis kontoen starter med en dollar i Den, så hva interleaving av meldinger vil lure A og B til å tro at de begge kan trekke en dollar, og dermed overtrekke kontoen?En leksjon her er at du må nøye velge driften av en meldingsmodell. ‘uttak-hvis-tilstrekkelig-midler’ ville være en bedre operasjon enn bare `uttak`.## Samtidighet Er Vanskelig Å Teste Og Feilsøke Hvis vi ikke har overbevist deg om at samtidighet er vanskelig, her er det verste av det. Det er veldig vanskelig å oppdage rase forhold ved hjelp av testing. Og selv når en test har funnet en feil, kan det være svært vanskelig å lokalisere den til den delen av programmet som forårsaker det.Samtidighet bugs viser svært dårlig reproduserbarhet. Det er vanskelig å få dem til å skje på samme måte to ganger. Interleaving av instruksjoner eller meldinger avhenger av den relative timingen av hendelser som er sterkt påvirket av miljøet. Forsinkelser kan skyldes andre kjørende programmer, annen nettverkstrafikk,operativsystemplanleggingsbeslutninger, variasjoner i prosessorens klokkehastighet, etc. Hver gang du kjører et program som inneholder en løpstilstand, kan du få forskjellig oppførsel. Disse typer feil er **heisenbugs**, som er ikke-deterministiske og vanskelig å reprodusere, i motsetning til en “bohrbug”, som dukker opp flere ganger når du ser på det. Nesten alle feil i sekvensiell programmering er bohrbugs.En heisenbug kan til og med forsvinne når du prøver å se på den med` println `eller`debugger’! Årsaken er at utskrift og feilsøking er så mye tregere enn andre operasjoner, ofte 100-1000x tregere, at de dramatisk endrer tidspunktet for operasjoner og interleaving. Så setter du inn en enkel utskriftsoppgave i cashMachine (): “‘ javaprivate static void cashMachine () {for (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) { deposit (); / / sett en dollar i uttak (); / / ta Det Ut Igjen System.ut.println (balanse); / / gjør feilen forsvinne! }}“`…og plutselig er balansen alltid 0, som ønsket, og feilen ser ut til å forsvinne. Men det er bare maskert, ikke virkelig løst. En endring i timing et annet sted i programmet kan plutselig gjøre feilen komme tilbake.Konkurranse er vanskelig å få rett. En del av poenget med denne lesningen er å skremme deg litt. I løpet av de neste flere avlesningene ser vi prinsipielle måter å designe samtidige programmer på, slik at de er sikrere fra slike feil.mitx:704b9c4db3c6487c9f1549956af8bfc8 Testing Samtidighet # # Sammendrag + Samtidighet: flere beregninger som kjører samtidig + Delt minne & meldingspasserende paradigmer + Prosesser & tråder + Prosess er som en virtuell datamaskin; tråd er som en virtuell prosessor + Raseforhold + når korrekt resultat (postconditions og invariants) avhenger av den relative timingen av hendelserdisse ideene kobles til våre tre nøkkelegenskaper for god programvare, for det meste på dårlige måter. Samtidighet er nødvendig, men det forårsaker alvorlige problemer for korrekthet. Vi vil jobbe med å fikse disse problemene i de neste lesingene.+ * * Trygg fra bugs.** Samtidighet bugs er noen av de vanskeligste bugs å finne og fikse, og krever nøye design for å unngå . + * * Lett å forstå.** Forutsi hvordan samtidig kode kan interleave med annen samtidig kode er svært vanskelig for programmerere å gjøre. Det er best å designe på en slik måte at programmerere ikke trenger å tenke på det. + * * Klar for endring.** Ikke spesielt relevant her.