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 & ulostulovirtojen avulla, 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.

Kuvittele, että pankissa on käteisautomaatteja, jotka käyttävät jaettua muistimallia, joten kaikki käteisautomaatit voivat lukea ja kirjoittaa saman tilin objekteja memory.To havainnollistaa, mikä voi mennä pieleen, yksinkertaistetaan pankki alas yhden tilin, jossa dollarin 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;}private static void withdraw () {balance = balance – 1;}“asiakkaat käyttävät käteisautomaatteja tehdäkseen näin:“javadeposit (); / / put a dollar inwithdraw (); / / 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 entirect afterward-yksityinen staattinen void cashmachine() { for (int I = 0; i < TRANSACTIONS_PER_MACHINE; ++i) { deposit (); / / put a dollar in Draw (); / / take it back out }}“So at the end of the day, whether whether many cash machines were operating, 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 interleave keskenään (jotkut saattavat jopa samanaikaisesti jossain mielessä, mutta let`s just worry about interleaving for now):` ‘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) “‘ Tämä interleaving on hieno-päädymme tasapainoon 2, joten sekä A että B onnistuivat sijoittamaan dollarin. Mutta mitä jos välilevyt näyttävät tältä:`’A get balance (saldo=0)b get balance (saldo=0) a add 1 B add 1 A write back the result (saldo=1) B write back the result (saldo=1)“saldo on nyt 1-A: n dollari hävisi! 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älkiehtojen ja invarianttien tyytyväisyys) riippuu tapahtumien suhteellisesta ajoituksesta samanaikaisissa laskutoimituksissa A ja B. Kun näin tapahtuu, sanomme “A on kilpailussa B: n kanssa.”jotkut tapahtumien välilevyt voivat olla OK siinä mielessä, että ne ovat yhdenmukaisia sen kanssa, mitä yksittäinen, ei-ajankohtainen prosessi tuottaisi, mutta muut välilevyt tuottavat vääriä vastauksia-rikkoen postconditioita tai invariantteja.## Säätäminen koodi ei auta kaikki nämä versiot pankki-tilin koodi näytteille sama rotu kunnossa:””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// version 3private static void deposit() { ++balance;}yksityinen 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ä.tuotto(); } jos (vastaus == 0) heitä Uusi RuntimeException (“vastaus ei ollut valmis!”);} “‘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 kenttiä 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 koskaan nosta enempää kuin tilillä on, koska tilinylityksistä seuraa suuria pankkisakkoja:“get-balanceif saldo >= 1 then within withdraw 1 “‘ ongelma on jälleen talletusten väli, mutta tällä kertaa pankkitilille Lähetettyjen *viestien* väli, eikä A: n ja B: n toteuttamien *instructions*. Jos tili alkaa dollarilla siinä, niin mikä viestien lomitus hämää A: ta ja B: tä luulemaan, että molemmat voivat nostaa dollarin, jolloin tili ylittyy?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 osaksi 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: multiple computations running simultaneously + Shared-memory & message-passing paradigms+ Processes & threads + Process is like a virtual computer; säie on kuin virtuaaliprosessori + kisaolosuhteet + kun tuloksen oikeellisuus (jälkiolosuhteet ja invariantit) riippuu tapahtumien suhteellisesta ajoituksesta.nämä ideat kytkeytyvät hyvän ohjelmiston 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ä.