Calcul simultan - Concurrent computing

Pentru o discuție mai teoretică, consultați Concurența (informatică) .
Paradigme de programare

Calculul simultan este o formă de calcul în care mai multe calcule sunt executate concomitent - pe perioade de timp suprapuse - în loc de secvențial - cu unul finalizând înainte de începerea următorului.

Aceasta este o proprietate a unui sistem - fie că este un program , un computer sau o rețea - unde există un punct de execuție separat sau un „fir de control” pentru fiecare proces. Un sistem concurent este acela în care un calcul poate avansa fără a aștepta finalizarea tuturor celorlalte calcule.

Calculul simultan este o formă de programare modulară . În paradigma sa, un calcul general este inclus în subcomputări care pot fi executate concomitent. Pionieri în domeniul calculelor concurente includ Edsger Dijkstra , Per Brinch Hansen și CAR Hoare .

Introducere

Vezi și: Calcul paralel

Conceptul de calcul simultan este frecvent confundat cu conceptul conex, dar distinct de calcul paralel , deși ambele pot fi descrise ca „procese multiple care se execută în aceeași perioadă de timp ”. În calcul paralel, execuția are loc în același moment fizic: de exemplu, pe procesoare separate ale unei mașini cu mai multe procesoare , cu scopul de a accelera calculele - calculul paralel este imposibil pe un singur procesor (cu un singur nucleu ), deoarece doar unul calculul poate avea loc în orice moment (în timpul oricărui ciclu de ceas). În schimb, calculul simultan constă în suprapunerea duratei de viață a proceselor , dar executarea nu trebuie să se întâmple în același moment. Scopul de aici este modelarea proceselor din lumea exterioară care au loc simultan, cum ar fi mai mulți clienți care accesează un server în același timp. Structurarea sistemelor software compuse din mai multe părți simultane și comunicante poate fi utilă pentru abordarea complexității, indiferent dacă piesele pot fi executate în paralel.

De exemplu, procesele concurente pot fi executate pe un nucleu prin intercalarea pașilor de execuție a fiecărui proces prin felii de partajare a timpului : numai un proces rulează la un moment dat și, dacă nu se finalizează în timpul tranșei sale de timp, este întrerupt , un alt proces începe sau se reia, iar ulterior procesul inițial este reluat. În acest fel, mai multe procese sunt parcurse prin executare într-un singur moment, dar doar un singur proces este executat în acel moment.

Calculele simultane pot fi executate în paralel, de exemplu, prin atribuirea fiecărui proces unui procesor separat sau nucleu de procesor sau distribuirea unui calcul pe o rețea. Cu toate acestea, în general, limbajele, instrumentele și tehnicile pentru programarea paralelă ar putea să nu fie potrivite pentru programarea simultană și invers.

Momentul exact al executării sarcinilor dintr-un sistem simultan depinde de programare , iar sarcinile nu trebuie întotdeauna executate simultan. De exemplu, având două sarcini, T1 și T2:

  • T1 poate fi executat și finalizat înainte de T2 sau invers (serial și secvențial)
  • T1 și T2 pot fi executate alternativ (serial și simultan)
  • T1 și T2 pot fi executate simultan în același moment de timp (paralel și concurent)

Cuvântul „secvențial” este folosit ca antonim atât pentru „simultan”, cât și „paralel”; când acestea sunt distincte în mod explicit, simultan / secvențial și paralel / serial sunt utilizate ca perechi opuse. Un program în care sarcinile se execută unul câte unul (în serie, fără paralelism), fără intercalare (secvențial, fără concurență: nici o activitate nu începe până când sarcina anterioară se termină) se numește programare în serie . Un set de sarcini care pot fi programate în serie este serializabil , ceea ce simplifică controlul concurenței .

Coordonarea accesului la resursele partajate

Principala provocare în proiectarea programelor concurente este controlul concurenței : asigurarea secvențierii corecte a interacțiunilor sau comunicațiilor dintre diferite execuții de calcul și coordonarea accesului la resursele care sunt partajate între execuții. Problemele potențiale includ condițiile cursei , blocajele și foametea resurselor . De exemplu, luați în considerare următorul algoritm pentru a face retrageri dintr-un cont de verificare reprezentat de resursa partajată balance: 

bool withdraw(int withdrawal)
{
    if (balance >= withdrawal)
    {
        balance -= withdrawal;
        return true;
    } 
    return false;
}

Să presupunem că balance = 500și două fire simultane fac apelurile withdraw(300)și withdraw(350). Dacă linia 3 din ambele operațiuni se execută înainte de linia 5, ambele operațiuni vor descoperi că se balance >= withdrawalevaluează trueși executarea va continua cu scăderea valorii retragerii. Cu toate acestea, întrucât ambele procese își efectuează retragerile, suma totală retrasă va ajunge să fie mai mare decât soldul inițial. Acest tip de probleme cu resursele partajate beneficiază de utilizarea controlului concurenței sau a algoritmilor care nu blochează .

Avantaje

Avantajele calculului simultan includ:

  • Creșterea randamentului programului - executarea paralelă a unui program simultan permite creșterea proporțională a numărului de sarcini finalizate într-un anumit timp cu numărul de procesoare conform legii Gustafson
  • Reactivitate ridicată pentru intrare / ieșire - programele intensive de intrare / ieșire așteaptă în cea mai mare parte finalizarea operațiunilor de intrare sau ieșire. Programarea simultană permite ca timpul care ar fi petrecut să aștepte să fie folosit pentru o altă sarcină.
  • O structură mai adecvată a programului - unele probleme și domenii de probleme sunt bine potrivite pentru reprezentare ca sarcini sau procese concurente.

Modele

Introducute în 1962, rețelele Petri au fost o încercare timpurie de codificare a regulilor de execuție concurentă. Teoria fluxului de date s-a construit ulterior pe acestea, iar arhitecturile fluxului de date au fost create pentru a implementa fizic ideile teoriei fluxului de date. Începând cu sfârșitul anilor 1970, calculele proceselor , cum ar fi Calculul sistemelor de comunicare (CCS) și Procesele secvențiale de comunicare (CSP), au fost dezvoltate pentru a permite raționamentul algebric despre sistemele compuse din componente care interacționează. Π-calculul adăugat capacitatea de raționament cu privire la topologii dinamice.

Automatele de intrare / ieșire au fost introduse în 1987.

Logici precum TLA + al lui Lamport și modele matematice precum urmele și diagramele de evenimente Actor au fost, de asemenea, dezvoltate pentru a descrie comportamentul sistemelor concurente.

Memoria tranzacțională software împrumută din teoria bazelor de date conceptul de tranzacții atomice și le aplică acceselor de memorie.

Modele de consistență

Articol principal: Model de coerență

Limbajele de programare simultane și programele multiprocesor trebuie să aibă un model de consistență (cunoscut și ca model de memorie). Modelul de consistență definește reguli pentru modul în care apar operațiile pe memoria computerului și modul în care rezultatele sunt produse.

Unul dintre primele modele de consistență a fost modelul de consistență secvențial al lui Leslie Lamport . Coerența secvențială este proprietatea unui program, că execuția acestuia produce aceleași rezultate ca un program secvențial. În mod specific, un program este consecvent secvențial dacă „rezultatele oricărei execuții sunt aceleași ca și cum operațiunile tuturor procesoarelor ar fi executate într-o anumită ordine secvențială, iar operațiunile fiecărui procesor individual apar în această secvență în ordinea specificată de programul său ".

Vezi și: Secvențial relaxat

Implementare

O serie de metode diferite pot fi folosite pentru a implementa programe concurente, cum ar fi implementarea fiecărei execuții de calcul ca proces de sistem de operare sau implementarea proceselor de calcul ca un set de fire într-un singur proces de sistem de operare.

Interacțiune și comunicare

În unele sisteme de calcul concurente, comunicarea dintre componentele concurente este ascunsă de programator (de exemplu, prin utilizarea futures ), în timp ce în altele trebuie tratată în mod explicit. Comunicarea explicită poate fi împărțită în două clase:

Comunicare de memorie partajată
Componentele simultane comunică prin modificarea conținutului locațiilor de memorie partajată (exemplificat prin Java și C # ). Acest stil de programare simultană necesită de obicei utilizarea unei forme de blocare (de exemplu, muturi , semafore sau monitoare ) pentru a se coordona între fire. Se spune că un program care implementează corect oricare dintre acestea este sigur pentru fire .
Comunicare de transmitere a mesajului
Componentele simultane comunică prin schimbul de mesaje (exemplificat prin MPI , Go , Scala , Erlang și occam ). Schimbul de mesaje poate fi realizat asincron sau poate utiliza un stil sincron „de întâlnire” în care expeditorul se blochează până la primirea mesajului. Transmiterea mesajelor asincrone poate fi fiabilă sau nesigură (uneori denumită „trimiteți și rugați-vă”). Concurența de transmitere a mesajelor tinde să fie mult mai ușor de argumentat decât concurența cu memorie partajată și este de obicei considerată o formă mai robustă de programare concurentă. Sunt disponibile o mare varietate de teorii matematice pentru a înțelege și analiza sistemele de transmitere a mesajelor, inclusiv modelul actorului și diverse calcule de proces . Transmiterea mesajelor poate fi implementată eficient prin multiprocesare simetrică , cu sau fără coerență cache cache de memorie partajată .

Memoria partajată și concurența de transmitere a mesajelor au caracteristici de performanță diferite. În mod obișnuit (deși nu întotdeauna), overhead-ul de memorie pe proces și overhead-ul de comutare a sarcinilor sunt mai mici într-un sistem de transmitere a mesajelor, dar overhead-ul pentru transmiterea mesajului este mai mare decât pentru un apel de procedură. Aceste diferențe sunt adesea copleșite de alți factori de performanță.

Istorie

Calculul simultan s-a dezvoltat din lucrările anterioare privind căile ferate și telegrafie , din secolul al XIX-lea și începutul secolului al XX-lea, iar unii termeni datează din această perioadă, cum ar fi semaforele. Acestea au apărut pentru a aborda problema cum să manevreze mai multe trenuri pe același sistem feroviar (evitând coliziunile și maximizând eficiența) și cum să gestionăm mai multe transmisii pe un anumit set de fire (îmbunătățind eficiența), cum ar fi prin multiplexarea prin diviziune în timp (anii 1870 ).

Studiul academic al algoritmilor concurenți a început în anii 1960, Dijkstra (1965) fiind creditat ca fiind prima lucrare în acest domeniu, identificând și rezolvând excluderea reciprocă .

Prevalenta

Concurența este omniprezentă în calcul, apărând de la hardware de nivel scăzut pe un singur cip la rețele mondiale. Urmează exemple.

La nivelul limbajului de programare:

La nivelul sistemului de operare:

La nivel de rețea, sistemele în rețea sunt în general concurente prin natura lor, deoarece constau din dispozitive separate.

Limbi care susțin programarea simultană

Limbajele de programare simultane sunt limbaje de programare care utilizează structuri de limbaj pentru concurență . Aceste construcții pot implica multi-threading , suport pentru calcul distribuit , transmiterea mesajelor , resurse partajate (inclusiv memorie partajată ) sau futures și promisiuni . Astfel de limbaje sunt uneori descrise ca limbaje orientate către concurență sau limbaje de programare orientate spre concurență (COPL).

Astăzi, cele mai utilizate limbaje de programare care au construcții specifice pentru concurență sunt Java și C # . Ambele limbaje folosesc în mod fundamental un model de concurență cu memorie partajată, cu blocare oferită de monitoare (deși modelele de transmitere a mesajelor pot și au fost implementate pe lângă modelul de memorie partajată de bază). Dintre limbile care utilizează un model de concurență care transmite mesaje, Erlang este probabil cel mai utilizat în industrie în prezent.

Multe limbaje de programare simultane au fost dezvoltate mai degrabă ca limbaje de cercetare (de ex. Pict ) decât ca limbaje pentru utilizare în producție. Cu toate acestea, limbi precum Erlang , Limbo și occam au cunoscut o utilizare industrială în diferite momente în ultimii 20 de ani. O listă neexhaustivă a limbajelor care utilizează sau oferă facilități de programare simultane:

  • Ada - scop general, cu suport nativ pentru transmiterea mesajelor și monitorizarea concurenței bazate pe
  • Alef - simultan, cu fire și mesaje transmise, pentru programarea sistemului în versiunile timpurii ale Planului 9 de la Bell Labs
  • Alice - extinderea la Standard ML , adaugă suport pentru concurență prin contracte futures
  • Ateji PX — extindere la Java cu primitive paralele inspirate din calculul π
  • Axum - domeniu specific, concurent, bazat pe modelul actorului și .NET Common Language Runtime folosind o sintaxă asemănătoare cu C
  • BMDFM — Mașină binară modulară de date
  • C ++ —std :: thread
  • Cω (C omega) - pentru cercetare, extinde C #, folosește comunicarea asincronă
  • C # - acceptă calcule concurente utilizând blocare, randament, de asemenea din versiunea 5.0 asincronizată și așteaptă introducerea cuvintelor cheie
  • Clojure - dialect modern și funcțional al Lisp pe platforma Java
  • Curatare simultană - programare funcțională, similară cu Haskell
  • Colecții simultane (CnC) —Realizează paralelismul implicit, independent de modelul de memorie, definind în mod explicit fluxul de date și control
  • Haskell simultan - limbaj funcțional leneș, pur, care operează procese simultane pe memoria partajată
  • ML simultan — extensie simultană a ML standard
  • Concurent Pascal - de Per Brinch Hansen
  • Curry
  • D - limbaj de programare a sistemului multi-paradigmă cu suport explicit pentru programare simultană ( model actor )
  • E - folosește promisiunile de a exclude blocajele
  • ECMAScript - folosește promisiuni pentru operațiuni asincrone
  • Eiffel - prin mecanismul său SCOOP bazat pe conceptele de Design by Contract
  • Elixir - limbaj conștient de meta-programare dinamic și funcțional care rulează pe Erlang VM.
  • Erlang — folosește transmiterea mesajelor asincrone fără nimic partajat
  • FAUST — funcțional în timp real, pentru procesarea semnalului, compilatorul asigură paralelizare automată prin OpenMP sau un planificator specific de furt de lucru
  • Fortran - coarrays și do concurrent fac parte din standardul Fortran 2008
  • Du-te - pentru programarea sistemului, cu un model de programare simultan bazat pe CSP
  • Haskell - limbaj de programare funcțional simultan și paralel
  • Hume - funcțional, concurent, pentru medii spațiale și temporare delimitate în care procesele automate sunt descrise de tipare de canale sincrone și de transmitere a mesajelor
  • Io — concurență bazată pe actori
  • Janus - prezintă interogatori și casieri diferiți la variabile logice, canale de sac; este pur declarativ
  • Java - clasă de fire sau interfață Runnable
  • Julia - „primitive de programare concurente: Sarcini, async-wait, canale”.
  • JavaScript - prin intermediul lucrătorilor web , într-un mediu de browser, promisiuni și apeluri de apel .
  • JoCaml — bazat pe canalul simultan și distribuit, extensia OCaml , implementează unirea-calculul proceselor
  • Alăturați-vă Java - simultan, pe baza limbajului Java
  • Joule - bazat pe flux de date, comunică prin transmiterea mesajului
  • Joyce - simultan, de predare, construit pe Concurrent Pascal cu caracteristici din CSP de Per Brinch Hansen
  • LabVIEW —grafic, flux de date, funcțiile sunt noduri într-un grafic, datele sunt fire între noduri; include un limbaj orientat obiect
  • Limbo - înrudit cu Alef , pentru programarea sistemului în Inferno (sistem de operare)
  • MultiLisp - Varianta schemei extinsă pentru a susține paralelismul
  • Modula-2 - pentru programarea sistemului, de N. Wirth ca succesor al lui Pascal cu suport nativ pentru coroutine
  • Modula-3 - membru modern al familiei Algol cu ​​suport extins pentru fire, mutexe, variabile de stare
  • Newsqueak — pentru cercetare, cu canale ca valori de primă clasă; predecesorul lui Alef
  • occam — influențat puternic de comunicarea proceselor secvențiale (CSP)
  • Orc - concurent, nedeterminist, bazat pe algebra Kleene
  • Oz-Mozart —multiparadigm, acceptă concurența de stat partajat și de transmitere a mesajelor, și viitorul
  • ParaSail — orientat spre obiect, paralel, fără indicatori, condiții de rasă
  • Pict — esențial o implementare executabilă a calculului π Milner
  • Raku include în mod implicit clase pentru fire, promisiuni și canale
  • Python - utilizează paralelism bazat pe fire și paralelism bazat pe procese
  • Reia — utilizează mesajul asincron care trece între obiectele nimic partajat
  • Roșu / Sistem - pentru programarea sistemului, bazat pe Rebol
  • Rugină - pentru programarea sistemului, folosind transmiterea mesajelor cu semantică de mișcare, memorie imutabilă partajată și memorie mutabilă partajată.
  • Scala — scop general, conceput pentru a exprima modele comune de programare într-un mod concis, elegant și sigur de tip
  • SecvențăL - obiectiv general funcțional, principalele obiective de proiectare sunt ușurința de programare, lizibilitatea codului și lizibilitatea automată pentru performanța pe hardware-ul multicore și fără probabilitate de condiții de cursă
  • SR —pentru cercetare
  • SuperPascal - simultan, pentru predare, construit pe Concurrent Pascal și Joyce de Per Brinch Hansen
  • Unicon - pentru cercetare
  • TNSDL — pentru dezvoltarea schimburilor de telecomunicații, utilizează transmiterea mesajelor asincronă
  • VHSIC Hardware Description Language ( VHDL ) —IEEE STD-1076
  • XC - subset de limbaj C extins cu monedă dezvoltat de XMOS , bazat pe comunicarea proceselor secvențiale , construcții încorporate pentru I / O programabile

Multe alte limbi oferă suport pentru concurență sub formă de biblioteci, la niveluri aproximativ comparabile cu lista de mai sus.

Vezi si

Note

Referințe

Surse

  • Patterson, David A .; Hennessy, John L. (2013). Organizarea și proiectarea computerelor: interfața hardware / software . Seria Morgan Kaufmann în arhitectură și proiectare calculatoare (5 ed.). Morgan Kaufmann. ISBN 978-0-12407886-4.

Lecturi suplimentare

linkuri externe