Lectură 17: concurență

#### Software în 6.005

#### obiective + mesaj care trece & memorie partajată+ procese & fire+ timp feliere+ condițiile de rasă## Concurrency*Concurrency* înseamnă mai multe calcule se întâmplă în același timp. Concurența este peste tot în programarea modernă, indiferent dacă ne place sau nu:+ mai multe computere într-o rețea+ mai multe aplicații care rulează pe un computer+ mai multe procesoare într-un computer (astăzi, adesea mai multe nuclee de procesor pe un singur cip) de fapt, concurența este esențială în programarea modernă:+ site-urile Web trebuie să gestioneze mai mulți utilizatori simultani.+ Aplicațiile Mobile trebuie să facă o parte din procesarea lor pe servere (“în cloud”).+ Interfețele grafice de utilizator necesită aproape întotdeauna lucrări de fundal care nu întrerup utilizatorul. De exemplu, Eclipse compilează codul Java în timp ce îl editați în continuare.Posibilitatea de a programa cu concurență va fi în continuare importantă în viitor. Viteza ceasului procesorului nu mai crește. În schimb, obținem mai multe nuclee cu fiecare nouă generație de cipuri. Deci, în viitor, în scopul de a obține un calcul pentru a rula mai repede, va trebui să împartă un calcul în bucăți concurente.## Două modele pentru programarea Concurentăexistă două modele comune pentru programarea concurentă: *memorie partajată* și *transmiterea mesajelor*.

**memorie partajată.** În modelul de memorie partajată de concurență, modulele concurente interacționează prin citirea și scrierea obiectelor partajate în memorie. Alte exemple ale modelului de memorie partajată: + A și B ar putea fi două procesoare (sau nuclee de procesor) în același computer, partajând aceeași memorie fizică.+ A și B ar putea fi două programe care rulează pe același computer, partajarea unui sistem de fișiere comun cu fișiere pe care le pot citi și scrie.+ A și B ar putea fi două fire în același program Java (vom explica ce este un fir de mai jos), împărtășind aceleași obiecte Java.

**transmiterea mesajului.** În modelul de transmitere a mesajelor, modulele concurente interacționează prin trimiterea de mesaje între ele printr-un canal de comunicare. Modulele trimit mesaje, iar mesajele primite către fiecare modul sunt puse în coadă pentru manipulare. Exemplele includ:+ A și B pot fi două computere dintr-o rețea, comunicând prin conexiuni de rețea.+ A și B ar putea fi un browser web și un server web-a deschide o conexiune la B, solicită o pagină web și B trimite datele paginii web Înapoi la A.+ a și B ar putea fi un client și un server de mesagerie instantanee.+ A și B ar putea fi două programe care rulează pe același computer a cărui intrare și ieșire au fost conectate printr-o conductă, cum ar fi `LS | grep` tastat într-un prompt de comandă.## Procese, Fire, timp-slicingThe mesaj-trecere și modele de memorie partajată sunt despre modul în care modulele concurente comunica. Modulele concurente în sine vin în două tipuri diferite: procese și fire.** Proces**. Un proces este o instanță a unui program care rulează care este *izolat* de alte procese de pe aceeași mașină. În special, are propria secțiune privată a memoriei mașinii.Procesul de abstractizare este un * calculator virtual*. Face ca programul să se simtă ca și cum ar avea întreaga mașină pentru sine-ca și cum un computer proaspăt a fost creat, cu memorie proaspătă, doar pentru a rula acel program.La fel ca computerele conectate printr-o rețea, procesele nu au în mod normal memorie între ele. Un proces nu poate accesa memoria sau obiectele altui proces. Partajarea memoriei între procese este *posibilă* pe majoritatea sistemului de operare, dar are nevoie de efort special. În schimb, un nou proces este pregătit automat pentru transmiterea mesajelor, deoarece este creat cu fluxuri de ieșire standard de intrare &, care sunt `sistem.afară ‘ și `System.in fluxuri pe care le-ați folosit în Java.** Fir**. Un fir este un locus de control în interiorul unui program care rulează. Gândiți-vă la el ca la un loc în programul care se execută, plus stiva de apeluri de metode care au dus la acel loc în care va fi necesar să se întoarcă.Așa cum un proces reprezintă un computer virtual, abstractizarea firului reprezintă un *procesor virtual*. Realizarea unui fir nou simulează realizarea unui procesor proaspăt în interiorul computerului virtual reprezentat de proces. Acest nou procesor virtual rulează același program și împărtășește aceeași memorie ca și alte fire în proces.Firele sunt pregătite automat pentru memoria partajată, deoarece firele Partajează toată memoria din proces. Este nevoie de un efort special pentru a obține memorie “fir-local”, care este privat la un singur fir. De asemenea, este necesar să configurați transmiterea mesajelor în mod explicit, prin crearea și utilizarea structurilor de date din coadă. Vom vorbi despre cum să facem asta într-o lectură viitoare.

Cum pot avea mai multe fire concurente cu doar unul sau două procesoare în computerul meu? Când există mai multe fire decât procesoarele, concurența este simulată prin **felierea timpului**, ceea ce înseamnă că procesorul comută între fire. Figura din dreapta arată cum trei fire T1, T2 și T3 ar putea fi tăiate în timp pe o mașină care are doar două procesoare reale. În figură, timpul continuă în jos, astfel încât la început un procesor rulează thread T1, iar celălalt rulează thread T2, iar apoi al doilea procesor comută pentru a rula thread T3. Thread T2 pur și simplu pauze, până la următoarea felie de timp pe același procesor sau un alt procesor.În majoritatea sistemelor, felierea timpului se întâmplă imprevizibil și nedeterminist, ceea ce înseamnă că un fir poate fi întrerupt sau reluat în orice moment.

mitx: c613ec53e92840a4a506f3062c994673 procesează & Fire## exemplu de memorie Partajatăsă ne uităm la un exemplu de sistem de memorie partajată. Scopul acestui exemplu este de a arăta că programarea concurentă este dificilă, deoarece poate avea bug-uri subtile.

Imaginați-vă că o bancă are bancomate care utilizează un model de memorie partajată, astfel încât toate bancomatele pot citi și scrie aceleași obiecte de cont în memory.To ilustrați ce poate merge prost, să simplificăm Banca până la un singur cont, cu un sold Dolar stocat în variabila “sold” și două operațiuni “depozit” și “retragere” care pur și simplu Adaugă sau elimină un dolar: “” java / / să presupunem că toate bancomatele împărtășesc un singur cont bancarprivat static int balance = 0 ; private static void deposit() { balance = balance + 1;} private static void retrage () {balance = balance – 1;}“clienții folosesc bancomatele pentru a face tranzacții de genul acesta:“javadeposit (); / / pune un dolar inwithdraw (); / / scoate-l înapoi“în acest exemplu simplu, fiecare tranzacție este doar un depozit de un dolar urmat de o retragere de un dolar, deci ar trebui să lase soldul în cont neschimbat. Pe tot parcursul zilei, fiecare bancomat din rețeaua noastră procesează o secvență de tranzacții de depunere/retragere.”‘java / / fiecare ATM face o grămadă de tranzacții care// modifica soldul, dar lăsați-l neschimbat afterwardprivate static void cashMachine() { pentru (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) { depozit(); // pune un dolar în retragere(); // ia-l înapoi }}“deci, la sfârșitul zilei, indiferent de cât de multe mașini de numerar au fost difuzate, sau cât de multe tranzacții am procesat, ar trebui să ne așteptăm ca soldul contului să fie încă 0.Dar dacă rulăm acest cod, descoperim frecvent că soldul la sfârșitul zilei este *Nu * 0. Dacă mai mult de un apel `cashMachine()` se execută în același timp-să zicem, pe procesoare separate în același computer-atunci `sold` nu poate fi zero la sfârșitul zilei. De ce nu?## InterleavingHere e un lucru care se poate întâmpla. Să presupunem că două bancomate, A și B, lucrează la un depozit în același timp. Iată cum deposit() pas de obicei descompune în instrucțiuni de procesor de nivel scăzut:“get balance (balance=0)add 1 write back the result (balance=1)“Când a și B rulează concomitent, aceste instrucțiuni de nivel scăzut se întrepătrund între ele (unele ar putea fi chiar simultane într-un anumit sens, dar hai să ne facem griji pentru intercalare deocamdată):“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) “‘ Această intercalare este în regulă — ajungem cu balance 2, deci, atât a, cât și B au pus cu succes un dolar. Dar dacă intercalarea arăta astfel:”‘A obține sold (sold=0) b obține sold (sold=0)a adăuga 1 B adăuga 1 a scrie înapoi rezultatul (Sold=1) B scrie înapoi rezultatul (Sold=1)“soldul este acum 1-a dolar a fost pierdut! A și B au citit soldul în același timp, au calculat soldurile finale separate și apoi au concurat pentru a stoca noul sold-care nu a reușit să ia în considerare depozitul celuilalt.## Race ConditionThis este un exemplu de * * race condition**. O condiție de rasă înseamnă că corectitudinea programului (satisfacția postcondițiilor și invarianților) depinde de momentul relativ al evenimentelor din calculele concurente a și B. Când se întâmplă acest lucru, spunem “A este într-o cursă cu B.”Unele interconexiuni ale evenimentelor pot fi OK, în sensul că sunt în concordanță cu ceea ce ar produce un singur proces neconcurent, dar alte interconexiuni produc răspunsuri greșite-încălcând postcondițiile sau invarianții.## Tweaking codul nu va HelpAll aceste versiuni ale codului de cont bancar prezintă aceeași condiție cursa:”‘java / / versiunea 1private static void deposit () {balance = balance + 1;}private static void retrageți () {balance = balance – 1;}“`java// versiunea 2private static void deposit () {balance += 1;}private static void retrageți () {balance -= 1;}“`java// versiunea 3private static void deposit () {++balance;}private static void retrageți () {–balance;}“nu puteți spune doar uitându-vă la codul Java cum îl va executa procesorul. Nu poți spune care vor fi operațiile indivizibile — operațiile atomice–. Nu este atomic doar pentru că este o linie de Java. Nu atinge echilibrul o singură dată doar pentru că identificatorul de echilibru apare o singură dată în linie. Compilatorul Java și, de fapt, procesorul în sine, nu își asumă angajamente cu privire la operațiunile de nivel scăzut pe care le va genera din codul dvs. De fapt, un compilator tipic Java modern produce exact același cod pentru toate cele trei versiuni!Lecția cheie este că nu poți spune uitându-te la o expresie dacă va fi ferită de condițiile de rasă.

## Reordonareaeste chiar mai rău decât asta, de fapt. Condiția cursei pe soldul contului bancar poate fi explicată în termeni de intercalări diferite ale operațiunilor secvențiale pe diferite procesoare. Dar, de fapt, atunci când utilizați mai multe variabile și mai multe procesoare, nici măcar nu puteți conta pe modificările acelor variabile care apar în aceeași ordine.Iată un exemplu` “‘ javaprivate Boolean ready = false; private int answer = 0; / / computeAnswer rulează într-un singur threadprivate void computeAnswer() { answer = 42; ready = true;}// useAnswer rulează într-un alt threadprivate void useAnswer() { while (!gata) { fir.randament(); } dacă (răspuns == 0) arunca nou RuntimeException (“răspunsul nu a fost gata!”);} “‘Avem două metode care sunt rulate în fire diferite. ‘computeAnswer’ face un calcul lung, în cele din urmă venind cu răspunsul 42, pe care îl pune în variabila de răspuns. Apoi setează variabila ‘ready `la true, pentru a semnala metodei care rulează în celălalt fir,` useAnswer’, că răspunsul este gata pentru utilizare. Privind Codul, ‘răspuns` este setat înainte de gata este setat, astfel încât odată ‘useAnswer’ vede ‘gata’ ca adevărat, atunci se pare rezonabil că se poate presupune că `răspuns` va fi 42, dreapta? Nu așa.Problema este că compilatoarele și procesoarele moderne fac multe lucruri pentru a face Codul rapid. Unul dintre aceste lucruri este de a face copii temporare ale variabilelor, cum ar fi răspuns și gata în stocare mai rapidă (registre sau cache-uri pe un procesor), și de a lucra cu ei temporar înainte de a le stoca în cele din urmă înapoi la locația lor oficială în memorie. Storeback-ul poate apărea într-o ordine diferită de variabilele care au fost manipulate în codul dvs. Iată ce s-ar putea întâmpla sub copertine (dar exprimat în sintaxa Java pentru a clarifica). Procesorul creează efectiv două variabile temporare, “tmpr” și “tmpa”, pentru a manipula câmpurile gata și a răspunde: “‘ javaprivate void computeAnswer() { boolean tmpr = ready; int tmpa = answer; tmpa = 42; tmpr = true; ready = tmpr; // <– ce se întâmplă dacă useAnswer() interleaves aici? // ready este setat, dar răspunsul nu este. answer = tmpa;} “‘ mitx: 2bf4beb7ffd5437bbbb9c782bb99b54e condiții de cursă # # exemplu de trecere a mesajului

acum să ne uităm la abordarea de transmitere a mesajelor la exemplul nostru de cont bancar.Acum nu numai că sunt modulele bancomatului, dar și conturile sunt module. Modulele interacționează prin trimiterea de mesaje reciproc. Cererile primite sunt plasate într-o coadă pentru a fi tratate unul câte unul. Expeditorul nu încetează să funcționeze în timp ce așteaptă un răspuns la solicitarea sa. Se ocupă de mai multe cereri de la propria coadă. Răspunsul la cererea sa în cele din urmă vine înapoi ca un alt mesaj.Din păcate, transmiterea mesajelor nu elimină posibilitatea condițiilor de cursă. Să presupunem că fiecare cont acceptă operațiunile ‘get-balance’ și ‘retragere’, cu mesajele corespunzătoare. Doi utilizatori, la bancomatul A și B, încearcă amândoi să retragă un dolar din același cont. Ei verifică mai întâi soldul pentru a se asigura că nu retrag niciodată mai mult decât deține contul, deoarece descoperirile de cont declanșează penalități bancare mari:“get-balanceif balance >= 1 apoi retrage 1“problema este din nou intercalarea, dar de data aceasta intercalarea mesajelor ** trimise în contul bancar, mai degrabă decât instrucțiunile ** executate de A și B. Dacă contul începe cu un dolar în el, atunci ce intercalare a mesajelor îi va păcăli pe A și B să creadă că pot retrage amândoi un dolar, depășind astfel contul?O lecție aici este că trebuie să alegeți cu atenție operațiunile unui model de transmitere a mesajelor. ‘retrage-dacă-suficiente-fonduri `ar fi o operațiune mai bună decât doar`retrage’.## Concurența este greu de testat și Depanatdacă nu v-am convins că concurența este dificilă, iată ce este mai rău. Este foarte greu să descoperi condițiile de cursă folosind testarea. Și chiar și odată ce un test a găsit o eroare, poate fi foarte greu să o localizezi la partea din program care o provoacă.Bug-urile de concurență prezintă o reproductibilitate foarte slabă. Este greu să le faci să se întâmple la fel de două ori. Intercalarea instrucțiunilor sau a mesajelor depinde de momentul relativ al evenimentelor care sunt puternic influențate de mediu. Întârzierile pot fi cauzate de alte programe care rulează, alte trafic de rețea, decizii de planificare a sistemului de operare, variații ale vitezei ceasului procesorului etc. De fiecare dată când rulați un program care conține o condiție de cursă, este posibil să aveți un comportament diferit. Aceste tipuri de bug-uri sunt **heisenbugs**, care sunt nedeterministe și greu de reprodus, spre deosebire de un “bohrbug”, care apare în mod repetat ori de câte ori te uiți la el. Aproape toate bug-urile din programarea secvențială sunt bohrbug-uri.Un heisenbug poate chiar să dispară atunci când încercați să-l priviți cu `println` sau `debugger`! Motivul este că imprimarea și depanarea sunt mult mai lente decât alte operații, adesea cu 100-1000x mai lente, încât schimbă dramatic calendarul operațiunilor și intercalarea. Deci, introducerea unui simplu declarație de imprimare în cashMachine():”‘javaprivate static void cashMachine() { pentru (int i = 0; i < TRANSACTIONS_PER_MACHINE; ++i) { depozit(); // pune un dolar în retragere(); // ia-l înapoi Sistem.afară.println (echilibru); / / face bug-ul să dispară! }}“`…și dintr-o dată soldul este întotdeauna 0, după cum se dorește, iar bug-ul pare să dispară. Dar este doar mascat, nu cu adevărat fixat. O schimbare a calendarului în altă parte a programului poate face brusc bug-ul să revină.Concurenta este greu pentru a obține dreptul. O parte din scopul acestei lecturi este să te sperii puțin. În următoarele câteva lecturi, vom vedea modalități principiale de a proiecta programe concurente, astfel încât acestea să fie mai sigure de aceste tipuri de bug-uri.mitx: 704b9c4db3c6487c9f1549956af8bfc8 testarea concurenței # # rezumat + concurență: calcule multiple care rulează simultan + memorie partajată & paradigme de trecere a mesajelor + procese & fire + procesul este ca un computer virtual; thread este ca un procesor virtual + condiții de cursă + când corectitudinea rezultatului (postcondițiile și invarianții) depinde de momentul relativ al evenimenteloraceste idei se conectează la cele trei proprietăți cheie ale software-ului bun, mai ales în moduri proaste. Concurența este necesară, dar provoacă probleme serioase pentru corectitudine. Vom lucra la rezolvarea acestor probleme în următoarele câteva lecturi.+ * * Sigur de bug-uri.** Bug-uri de concurență sunt unele dintre cele mai grele bug-uri pentru a găsi și repara, și necesită un design atent pentru a evita.+ * * Ușor de înțeles.** Prezicerea modului în care codul concurent s-ar putea intercala cu alt cod concurent este foarte greu pentru programatori. Cel mai bine este să proiectați în așa fel încât programatorii să nu fie nevoiți să se gândească la asta. + * * Gata pentru schimbare.** Nu este deosebit de relevant aici.