Reading 17: Concurrency

#### ohjelmisto 6.005

#### tavoitteet + viestin läpäisy & jaettu muisti+ prosessit & kierteet+ ajan viipalointi+ kisaolosuhteet## Yhtäaikaisuus*Yhtäaikaisuus* tarkoittaa, että useita laskutoimituksia tapahtuu samanaikaisesti. Samanaikaisuus on kaikkialla nykyaikaisessa ohjelmoinnissa, pidimmepä siitä tai emme:+ useita tietokoneita verkossa+ useita sovelluksia yhdellä tietokoneella+ useita suorittimia tietokoneessa (nykyään usein useita prosessoriytimiä yhdellä sirulla) itse asiassa, samanaikaisuus on välttämätöntä nykyaikaisessa ohjelmoinnissa:+ www-sivustojen on käsiteltävä useita samanaikaisia käyttäjiä.+ Mobiilisovellusten on tehtävä osa prosessoinnistaan palvelimilla (“pilvessä”).+ Graafiset käyttöliittymät vaativat lähes aina taustatyötä, joka ei keskeytä käyttäjää. Eclipse esimerkiksi kokoaa Java-koodisi, kun vielä muokkaat sitä.Mahdollisuus ohjelmoida samanaikaisesti on edelleen tärkeää tulevaisuudessa. Prosessorin kellotaajuudet eivät enää kasva. Sen sijaan saamme lisää ytimiä jokaisen uuden sukupolven sirujen mukana. Joten tulevaisuudessa, jotta laskutoimitus toimisi nopeammin, meidän täytyy jakaa laskenta samanaikaisiin osiin.## Kaksi mallia samanaikaiselle ohjelmoinnille on kaksi yhteistä mallia samanaikaiselle ohjelmoinnille: * jaettu muisti * ja * viestien välittäminen*.

* * Jaettu muisti.** Yhteisvaluutan jaetun muistin mallissa samanaikaiset moduulit ovat vuorovaikutuksessa lukemalla ja kirjoittamalla jaettuja objekteja muistiin. Muita esimerkkejä jaetun muistin mallista : + A ja B voivat olla kaksi prosessoria (tai prosessoriydintä) samassa tietokoneessa, jotka jakavat saman fyysisen muistin.+ A ja B voivat olla samalla tietokoneella toimivia ohjelmia, jotka jakavat yhteisen tiedostojärjestelmän luettavien ja kirjoitettavien tiedostojen kanssa.+ A ja B voivat olla kaksi säiettä samassa Java-ohjelmassa (selitämme, mitä säiettä alla on), jakaen samat Java-objektit.

* * viestin läpäisy.** Message-passing-mallissa samanaikaiset moduulit ovat vuorovaikutuksessa lähettämällä viestejä toisilleen viestintäkanavan kautta. Moduulit lähettävät viestejä, ja saapuvat viestit kuhunkin moduuliin jonotetaan käsittelyä varten. Esimerkkejä ovat: + A ja B saattavat olla verkossa kaksi tietokonetta, jotka kommunikoivat verkkoyhteyksillä.+ A ja B voivat olla verkkoselain ja WWW-palvelin-A avaa yhteyden B: hen, pyytää verkkosivua ja B lähettää verkkosivun tiedot takaisin A: lle.+ A ja B saattaa olla pikaviestiohjelma ja-palvelin.+ A ja B voivat olla samassa tietokoneessa toimivia ohjelmia, joiden tulo ja lähtö on yhdistetty putkella, kuten komentokehotteeseen kirjoitettu `LS | grep`.## – Prosessit, viestiketjut, aikaleikkaus ja jaetun muistin mallit kertovat siitä, miten samanaikaiset moduulit kommunikoivat. Samanaikaisia moduuleja on kahta erilaista: prosesseja ja säikeitä.**Prosessi**. Prosessi on esimerkki käynnissä olevasta ohjelmasta, joka on * eristetty * muista saman koneen prosesseista. Erityisesti sillä on oma yksityinen osionsa koneen muistista.Prosessin abstraktio on * virtual computer*. Se saa ohjelman tuntemaan, että sillä on koko kone itsellään — kuin uusi tietokone olisi luotu, tuoreella muistilla, vain ohjelman ajamista varten.Aivan kuten tietokoneet, jotka on kytketty verkkoon, prosessit eivät yleensä Jaa muistia keskenään. Prosessi ei voi käyttää toisen prosessin muistia tai esineitä lainkaan. Muistin jakaminen prosessien välillä on* mahdollista * useimmissa käyttöjärjestelmissä, mutta se vaatii erityistä vaivaa. Sen sijaan Uusi prosessi on automaattisesti valmis sanoman välittämiseen, koska se luodaan vakiosyöte & lähtövirroilla, jotka ovat ` – järjestelmä.ulos `ja ‘System.in” virtoja, joita käytit Jaavalla.**Kierre**. Säie on ohjauspaikka käynnissä olevan ohjelman sisällä. Ajattele sitä paikka ohjelmassa, joka on käynnissä, plus pino menetelmä puhelut, jotka johtivat siihen paikkaan, johon se on tarpeen palata läpi.Aivan kuten prosessi edustaa virtuaalista tietokonetta, thread-abstraktio edustaa *virtuaalista suoritinta*. Uuden langan tekeminen simuloi tuoreen prosessorin tekemistä prosessin edustaman virtuaalikoneen sisällä. Tämä uusi virtuaaliprosessori ajaa samaa ohjelmaa ja jakaa samaa muistia kuin muut kierteet prosessissa.Kierteet ovat automaattisesti valmiita jaettuun muistiin, koska kierteet jakavat kaiken muistin prosessissa. Se tarvitsee erityistä vaivaa saada “Lanka-paikallinen” muisti, joka on yksityinen yhteen säiettä. On myös tarpeen määrittää sanomanvälitys eksplisiittisesti luomalla ja käyttämällä jonotietorakenteita. Puhutaan siitä, miten se tehdään tulevassa käsittelyssä.

miten minulla voi olla monia samanaikaisia säikeitä, joissa on vain yksi tai kaksi prosessoria tietokoneessani? Kun kierteitä on enemmän kuin prosessoreita, samanaikaisuutta simuloidaan **aikaleikkauksella**, jolloin prosessori vaihtaa kierteiden välillä. Kuvassa oikealla näkyy, kuinka kolme kierteet T1, T2 ja T3 voidaan aikaleikata koneella, jossa on vain kaksi varsinaista prosessoria. Kuviossa aika etenee alaspäin, joten aluksi toinen suoritin ajaa säiettä T1 ja toinen säiettä T2, ja sitten toinen suoritin siirtyy ajamaan säiettä T3. Säie T2 yksinkertaisesti pysähtyy, kunnes se seuraavan kerran viipaloi samalla prosessorilla tai toisella prosessorilla.Useimmissa järjestelmissä, aika viipalointi tapahtuu arvaamattomasti ja ei-deterministisesti, mikä tarkoittaa, että lanka voidaan keskeyttää tai jatkaa milloin tahansa.

mitx:c613ec53e92840a4a506f3062c994673 prosessit & Threads## Shared Memory ExampleLet ‘ s katso esimerkki jaetusta muistijärjestelmästä. Tämän esimerkin tarkoituksena on osoittaa, että samanaikainen ohjelmointi on vaikeaa, koska siinä voi olla hienovaraisia vikoja.

kuvitelkaa, että pankissa on käteisautomaatteja, jotka käyttävät jaettua muistimallia, joten kaikki käteisautomaatit voivat lukea ja kirjoittaa samat tilin objektit muistiin.Havainnollistaa, mikä voi mennä vikaan, yksinkertaistetaan pankki alas yhden tilin, jossa Dollari saldo tallennetaan `saldo` muuttuja, ja kaksi operaatiota `talletus` ja `nostaa`, jotka yksinkertaisesti lisätä tai poistaa dollari: “java// oletetaan, että kaikki käteisautomaatit jakavat yhden pankkitilinyksityinen staattinen int saldo = 0;yksityinen staattinen void talletus() { saldo = saldo + 1;}yksityinen staattinen void peruuttaa() { balance = saldo – 1;}` “asiakkaat käyttävät käteisautomaatteja tehdä liiketoimia näin:” `javadeposit(); // put dollari vedossa(); // take it back out “‘ tässä yksinkertaisessa esimerkissä jokainen tapahtuma on vain yhden dollarin talletus, jota seuraa yhden dollarin nosto, joten sen pitäisi jättää tilin saldo ennalleen. Koko päivän, jokainen Pankkiautomaatti verkostossamme käsittelee sekvenssi talletus / nosto tapahtumia.””java/ / each ATM does a bunch of transactions that / / modifying balance, but leave it entrant afterward-yksityinen staattinen void cashmachine () {for (int I = 0; i < TRANSACTIONS_PER_MACHINE; ++i) { deposit (); / / put a dollar in Draw(); // take it back out }} “‘ s so at the end of the day, whether whether montako käteisautomaattia oli käytössä, or how many transactions we processed, we should expect the account to still be 0.Mutta jos käytämme tätä koodia, huomaamme usein, että saldo päivän lopussa on *ei * 0. Jos useampi kuin yksi “cashMachine ()” – puhelu on käynnissä samaan aikaan-vaikkapa saman tietokoneen erillisillä prosessoreilla-niin “saldo” ei välttämättä ole nolla päivän päätteeksi. Miksi ei?## InterleavingHere ‘ s one thing that can happen. Oletetaan, että kaksi käteisautomaattia, A ja B, ovat molemmat tekemässä talletusta samaan aikaan. Näin talletusvaihe () tyypillisesti hajoaa matalan tason prosessoriohjeiksi: “‘get balance (balance=0)add 1 write back the result (balance=1) “‘ Kun A ja B ovat käynnissä samanaikaisesti, nämä matalan tason ohjeet välileveävät keskenään (jotkut saattavat olla jopa samanaikaisia jossain mielessä, mutta huolehditaan vain välileveydestä toistaiseksi):`’A get balance (saldo=0)a add 1 A write back the result (saldo=1) B get balance (saldo=1) B add 1 B write back the result (Saldo=2)“Tämä välileima on hieno-päädymme balanssiin 2, joten sekä A että B laitetaan onnistuneesti dollariin. Mutta mitä jos interleaving näytti tältä:“a get balance (balance=0) b get balance (balance=0)a add 1 B add 1 A write back the result (balance=1) B write back the result (balance=1) “‘ tasapaino on nyt 1-A: n dollari oli menetetty! A ja B molemmat lukivat saldon samaan aikaan, laskivat erilliset lopulliset saldot, ja sitten kiirehtivät tallentamaan uuden saldon takaisin-joka ei ottanut toisen talletusta huomioon.## Race ConditionThis is a example of a * * race condition**. Rotuehto tarkoittaa, että ohjelman oikeellisuus (jälkiolosuhteiden ja invarianttien tyytyväisyys) riippuu tapahtumien suhteellisesta ajoituksesta samanaikaisissa laskutoimituksissa A ja B. Kun tämä tapahtuu, sanomme “A on kilpailussa B: n kanssa.”Jotkut interleavings tapahtumien voi olla OK, siinä mielessä, että ne ovat yhdenmukaisia mitä yksittäinen, nonconcurrent prosessi tuottaisi, mutta muut interleavings tuottaa vääriä vastauksia-rikkoo postconditions tai invariants.## Koodin säätäminen ei auta kaikkia näitä tilikoodin versioita, joissa on sama rotutilanne: “‘java/ / version 1private static void deposit () { balance = balance + 1;}private static void withdraw() { balance = balance – 1;} “” java/ / version 2private static void deposit () {balance + = 1;} private static void withdraw () { balance – = 1;} “””java / / versio 3private static void deposit() { ++balance;}private static void withdraw() { –balance;}`” et voi vain katsomalla Java-koodia, miten prosessori aikoo suorittaa sen. Ei voi tietää, mitä jakamattomat operaatiot — atomioperaatiot — tulevat olemaan. Se ei ole atomic vain koska se on yksi rivi Java. Se ei kosketa tasapainoa vain kerran vain siksi, että tasapainon tunniste esiintyy vain kerran rivillä. Java-kääntäjä, ja itse asiassa prosessori itse, ei tee sitoumuksia siitä, mitä matalan tason toimintoja se luo koodistasi. Itse asiassa tyypillinen moderni Java-kääntäjä tuottaa täsmälleen saman koodin kaikille kolmelle näistä versioista!Keskeinen opetus on se, että ilmaisua katsomalla ei voi tietää, onko se turvassa kisaolosuhteilta.

## se on vielä pahempaa. Kilpailutilanne pankkitilin saldossa selittyy erilaisilla peräkkäisten operaatioiden interleavingeilla eri prosessoreilla. Mutta itse asiassa, kun käytät useita muuttujia ja useita prosessoreita, et voi edes luottaa muutoksiin, jotka näkyvät samassa järjestyksessä.Tässä on esimerkki: “‘ javaprivate boolean ready = false;private int answer = 0;// computeAnswer toimii yhdessä threadprivate void computeAnswer() { answer = 42; ready = true;}// useAnswer toimii eri threadprivate void useAnswer() { while (!valmis) {säiettä.yield ();} if (answer == 0) throw new RuntimeException(“answer wasn’ t ready!”);} “‘Meillä on kaksi menetelmää, joita ajetaan eri säikeissä. “computeAnswer” tekee pitkän laskutoimituksen ja lopulta keksii vastauksen 42, jonka se laittaa vastausmuuttujaan. Sitten se asettaa “ready” – muuttujan true-arvoksi viestittääkseen toisessa säkeessä ajettavalle menetelmälle, “useAnswer”, että vastaus on valmis käytettäväksi. Kun koodia tarkastellaan ` “vastaus” asetetaan ennen kuin valmis on asetettu, joten kun “useAnswer” näkee “valmis” olevan totta, niin vaikuttaa järkevältä, että se voi olettaa, että “vastaus” on 42, eikö? Ei pidä paikkaansa.Ongelmana on, että nykyaikaiset kääntäjät ja prosessorit tekevät paljon asioita, jotta koodi olisi nopea. Yksi näistä asioista on tehdä väliaikaisia kopioita muuttujista, kuten vastaus ja valmis nopeampaan tallennukseen (rekisterit tai välimuistit prosessorilla), ja työskennellä niiden kanssa väliaikaisesti ennen kuin lopulta tallentaa ne takaisin viralliseen sijaintiinsa muistiin. Storeback voi tapahtua eri järjestyksessä kuin muuttujia manipuloitiin koodissasi. Tässä mitä voisi olla meneillään kannen alla (mutta ilmaistuna Java syntaksi tehdä selväksi). Suoritin luo tehokkaasti kaksi väliaikaista muuttujaa, “tmpr” ja “tmpa”, manipuloidakseen kentät valmiiksi ja vastatakseen:`”javaprivate void computeAnswer() { boolean tmpr = ready; int tmpa = answer; tmpa = 42; tmpr = true; ready = tmpr; // <– what happens if useAnswer() interleaves here? // ready is set, but answer isn`t. answer = tmpa;}` ‘mitx:2bf4beb7ffd5437bbbb9c782bb99b54e Race Conditions## Message Passing Example

now let’ s look at the message-passing approach to our bank account example.Nyt ei ole vain käteisautomaattimoduuleja, vaan myös tilit ovat moduuleja. Moduulit ovat vuorovaikutuksessa lähettämällä viestejä toisilleen. Saapuvat pyynnöt asetetaan jonoon, joka käsitellään yksi kerrallaan. Lähettäjä ei lopeta työskentelyä odottaessaan vastausta pyyntöönsä. Se käsittelee enemmän Oman jononsa pyyntöjä. Vastaus pyyntöön tulee lopulta toisena viestinä.Valitettavasti viestin välittäminen ei poista kisaolosuhteiden mahdollisuutta. Oletetaan, että jokainen tili tukee “get-balance” – ja “withdraw” – toimintoja vastaavine viesteineen. Kaksi käyttäjää, käteisautomaatti A ja B, yrittävät molemmat nostaa dollarin samalta tililtä. He tarkistavat ensin saldon varmistaakseen, etteivät he koskaan nosta enempää kuin tilillä on, koska tilinylitykset aiheuttavat suuria pankkisakkoja:“get-balanceif saldo >= 1 then withdraw 1 “‘ ongelma on jälleen se, että pankkitilille lähetetyt *viestit* jätetään väliin, eikä A: n ja B: n toteuttamia *ohjeita*. jos tili alkaa dollarilla, niin mikä viestien välitys hämää A: ta ja B: tä luulemaan, että molemmat voivat nostaa dollarin ja siten ylittää tilin?Yksi opetus tässä on, että sinun täytyy huolellisesti valita toimintaa viestin välittävän mallin. “nostakaa-jos-riittävästi-varoja” olisi parempi operaatio kuin vain “nostakaa”.## Concurrency is Hard to Test and Debugiff we haven ‘t conversed you that concurrency is tricky, here’ s the worst of it. Kisaolosuhteita on vaikea selvittää testaamalla. Ja jopa kun testi on löytänyt bugin, voi olla hyvin vaikea paikallistaa sitä siihen ohjelman osaan, joka sen aiheuttaa.Samanaikaisten vikojen toistettavuus on huono. Niitä on vaikea saada tapahtumaan samalla tavalla kahdesti. Ohjeiden tai viestien lomittaminen riippuu ympäristön voimakkaasti vaikuttavien tapahtumien suhteellisesta ajoituksesta. Viivästyksiä voivat aiheuttaa muut käynnissä olevat ohjelmat, muu verkkoliikenne, käyttöjärjestelmän aikataulupäätökset, prosessorin kellotaajuuden vaihtelut jne. Joka kerta, kun ajaa kisaehdon sisältävää ohjelmaa, voi tulla erilainen käytös. Tällaisia ötököitä ovat** heisenbugit**, jotka ovat nondeterministisiä ja vaikeasti lisääntyviä, erotuksena “bohrbugista”, joka ilmestyy toistuvasti aina kun sitä katsoo. Lähes kaikki ohjelmoinnin virheet ovat bohrbugeja.Heisenbug voi jopa kadota, kun yrität katsoa sitä `println` tai `debugger`! Syynä on se, että tulostus ja virheenkorjaus ovat niin paljon hitaampia kuin muut toiminnot, usein 100-1000x hitaampia, että ne muuttavat dramaattisesti toimintojen ajoitusta ja välilevyä. Joten lisäämällä yksinkertainen print statement in the cashMachine ():“javaprivate static void cashmachine () {for (int I = 0; i < TRANSACTIONS_PER_MACHINE; ++i) {deposit (); / / put a dollar in Draw (); / / take it back out System.ulos.println (tasapaino); / / saa vian katoamaan! }}“`…ja yhtäkkiä tasapaino on aina 0, kuten halutaan, ja vika näyttää katoavan. Mutta se on vain naamioitu, ei todella korjattu. Ajoituksen muutos jossain muualla ohjelmassa saattaa yhtäkkiä saada vian palaamaan.Yhteisvaluutta on vaikea saada kohdalleen. Osa tämän lukeman pointtia on pelotella sinua hieman. Seuraavien lukemien aikana näemme periaatteellisia tapoja suunnitella samanaikaisia ohjelmia niin, että ne ovat turvallisempia tällaisilta bugeilta.mitx: 704b9c4db3c6487c9f1549956af8bfc8 Testing Concurrency# # Summary+ Concurrency: useita samanaikaisia laskelmia + Jaettu muisti & viestin läpäisevät paradigmat+ prosessit & kierteet + prosessi on kuin virtuaalitietokone; säie on kuin virtuaaliprosessori+ kisaolosuhteet + kun tuloksen oikeellisuus (jälkiolosuhteet ja invariantit) riippuu tapahtumien suhteellisesta ajoituksesta.nämä ideat kytkeytyvät hyvien ohjelmistojen kolmeen keskeiseen ominaisuuteemme enimmäkseen huonoilla tavoilla. Samanaikainen käyttö on välttämätöntä, mutta se aiheuttaa vakavia ongelmia oikeellisuudelle. Korjaamme ongelmat seuraavissa lukemissa.+ **Turvassa bugeilta.** Samanaikaisuus vikoja ovat joitakin vaikeimpia vikoja löytää ja korjata, ja vaativat huolellista suunnittelua välttää.+ **Helppo ymmärtää.** Ennustaminen, miten samanaikainen koodi voi interleave muiden samanaikaisten koodi on hyvin vaikea ohjelmoijien tehdä. On parasta suunnitella niin, että ohjelmoijien ei tarvitse ajatella sitä. + **Valmis muutokseen.** Ei erityisen merkityksellinen tässä.