Souběžné výpočty - Concurrent computing

Více teoretické diskuse najdete v tématu Souběžnost (počítačová věda) .
Programovací paradigmata

Souběžné počítání je forma výpočtu, ve které je prováděno několik výpočtů souběžně - během překrývajících se časových období - namísto sekvenčně - s tím, že jedno bude dokončeno před začátkem dalšího.

Toto je vlastnost systému - ať už programu , počítače nebo sítě - kde pro každý proces existuje samostatný bod spuštění nebo „vlákno kontroly“. Souběžný systém je případ, kdy výpočet může postupovat bez čekání pro všechny ostatní výpočty dokončit.

Souběžné výpočty jsou formou modulárního programování . Ve svém paradigmatu je celkový výpočet zapracovány do subcomputations, které mohou být provedeny současně. Mezi průkopníky v oblasti souběžných počítačů patří Edsger Dijkstra , Per Brinch Hansen a CAR Hoare .

Úvod

Viz také: Paralelní výpočet

Pojem souběžného výpočtu je často zaměňován se souvisejícím, ale odlišným pojmem paralelního počítání , ačkoli oba lze popsat jako „více procesů provádějících během stejného časového období “. V paralelních výpočtů, provedení dochází na stejné fyzické okamžik: například na samostatných procesorech jednoho více procesory stroj, s cílem urychlení výpočtů-paralelní výpočty je možné na ( jedno-core ) jedním procesorem, jako jediný k výpočtu může dojít v kterémkoli okamžiku (během jakéhokoli jediného hodinového cyklu). Souběžné výpočty se naopak skládají z překrývajících se životů procesů , ale provedení nemusí probíhat ve stejný okamžik. Cílem je modelovat procesy ve vnějším světě, které se dějí souběžně, například více klientů přistupujících k serveru současně. Strukturování softwarových systémů složených z více souběžných, komunikujících částí může být užitečné pro řešení složitosti, bez ohledu na to, zda lze části provádět souběžně.

Souběžné procesy lze například provádět na jednom jádře prokládáním kroků provádění každého procesu prostřednictvím řezů sdílení času : v jednom okamžiku běží pouze jeden proces, a pokud se během časového úseku nedokončí, je pozastaven , další proces začíná nebo pokračuje a později se obnoví původní proces. Tímto způsobem je více procesů částečně prováděno v jednom okamžiku, ale v daném okamžiku se provádí pouze jeden proces.

Souběžné výpočty lze provádět souběžně, například přiřazením každého procesu samostatnému procesoru nebo jádru procesoru nebo distribucí výpočtu v síti. Obecně však jazyky, nástroje a techniky pro paralelní programování nemusí být vhodné pro souběžné programování a naopak.

Přesné načasování provádění úkolů v souběžném systému závisí na plánování a úkoly nemusí být vždy prováděny souběžně. Například pro dva úkoly, T1 a T2:

  • T1 lze spustit a dokončit před T2 nebo naopak (sériové a sekvenční)
  • T1 a T2 lze provádět střídavě (sériově a souběžně)
  • T1 a T2 mohou být prováděny současně ve stejném okamžiku (paralelně a souběžně)

Slovo „sekvenční“ se používá jako antonymum pro „souběžné“ i „paralelní“; pokud jsou výslovně rozlišeny, jsou souběžné/sekvenční a paralelní/sériové použity jako protichůdné páry. Plán, ve kterém se úkoly provádějí po jednom (sériově, bez paralelismu), bez prokládání (postupně, bez souběžnosti: žádný úkol nezačne, dokud neskončí předchozí úkol), se nazývá sériový plán . Sada úloh, které lze naplánovat sériově, je serializovatelná , což zjednodušuje řízení souběžnosti .

Koordinace přístupu ke sdíleným zdrojům

Hlavní výzvou při navrhování souběžných programů je řízení souběžnosti : zajištění správného sekvenování interakcí nebo komunikace mezi různými výpočetními provedeními a koordinace přístupu ke zdrojům sdíleným mezi popravami. Mezi potenciální problémy patří závodní podmínky , zablokování a hladovění zdrojů . Zvažte například následující algoritmus pro výběr z běžného účtu reprezentovaného sdíleným prostředkem balance: 

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

Předpokládejme balance = 500, že a dvě souběžná vlákna uskutečňují hovory withdraw(300)a withdraw(350). Pokud se řádek 3 v obou operacích provede před řádkem 5, obě operace zjistí, že se balance >= withdrawalvyhodnotí true, a provádění bude pokračovat k odečtení částky výběru. Jelikož však oba procesy provádějí své výběry, celková částka vybraná nakonec bude vyšší než původní zůstatek. Tyto druhy problémů se sdílenými prostředky těží z použití řízení souběžnosti nebo neblokujících algoritmů .

Výhody

Mezi výhody souběžného výpočtu patří:

  • Vyšší propustnost programu - paralelní provádění souběžného programu umožňuje zvýšit počet úkolů dokončených v daném čase úměrně počtu procesorů podle Gustafsonova zákona
  • Vysoká odezva na vstup/výstup-programy náročné na vstup/výstup většinou čekají na dokončení vstupních nebo výstupních operací. Souběžné programování umožňuje, aby čas, který byste strávili čekáním, byl použit k jinému úkolu.
  • Vhodnější struktura programu-některé problémy a problémové domény jsou vhodné pro reprezentaci jako souběžné úkoly nebo procesy.

Modely

Petriho sítě , zavedené v roce 1962, byly raným pokusem kodifikovat pravidla souběžného provádění. Teorie toku dat na nich později stavěla a architektury toku dat byly vytvořeny za účelem fyzické implementace myšlenek teorie toku dat. Počínaje koncem sedmdesátých let byly vyvinuty procesní kameny jako Calculus of Communicating Systems (CCS) a Communicating Sequential Processes (CSP), které umožňují algebraické úvahy o systémech složených z interagujících komponent. Π-kalkul přidal schopnost k uvažování o dynamických topologií.

Vstupní/výstupní automaty byly zavedeny v roce 1987.

Pro popis chování souběžných systémů byla také vyvinuta logika, jako je Lamportův TLA+ , a matematické modely, jako jsou stopy a diagramy událostí herců .

Softwarová transakční paměť si z teorie databáze vypůjčuje koncept atomových transakcí a aplikuje je na přístupy do paměti.

Konzistenční modely

Hlavní článek: Model konzistence

Souběžné programovací jazyky a víceprocesorové programy musí mít model konzistence (známý také jako paměťový model). Model konzistence definuje pravidla, jak dochází k operacím s pamětí počítače a jak se vytvářejí výsledky.

Jeden z prvních modelů konzistence byla Leslie Lamport je sekvenční konzistence modelu. Sekvenční konzistence je vlastnost programu, že jeho provádění přináší stejné výsledky jako sekvenční program. Konkrétně je program sekvenčně konzistentní, pokud „výsledky jakéhokoli spuštění jsou stejné, jako kdyby operace všech procesorů byly provedeny v nějakém sekvenčním pořadí, a operace každého jednotlivého procesoru se objevily v tomto pořadí v pořadí určeném jeho programem ".

Viz také: Uvolněná sekvenční

Implementace

K implementaci souběžných programů lze použít řadu různých metod, jako je implementace každé výpočetní exekuce jako proces operačního systému nebo implementace výpočetních procesů jako sady vláken v rámci jednoho procesu operačního systému.

Interakce a komunikace

V některých souběžných výpočetních systémech je komunikace mezi souběžnými komponentami před programátorem skryta (např. Pomocí futures ), zatímco v jiných s ní musí být zacházeno explicitně. Explicitní komunikaci lze rozdělit do dvou tříd:

Komunikace se sdílenou pamětí
Souběžné komponenty komunikují změnou obsahu umístění sdílené paměti (příkladem jsou Java a C# ). Tento styl souběžného programování obvykle potřebuje ke koordinaci mezi vlákny použít nějakou formu uzamykání (např. Mutexy , semafory nebo monitory ). Program, který správně implementuje některý z nich, je údajně bezpečný pro vlákna .
Komunikace předávající zprávu
Souběžné komponenty komunikují výměnou zpráv (příkladem jsou MPI , Go , Scala , Erlang a occam ). Výměna zpráv může být prováděna asynchronně, nebo může být použit synchronní styl „setkání“, ve kterém odesílatel blokuje, dokud není zpráva přijata. Asynchronní předávání zpráv může být spolehlivé nebo nespolehlivé (někdy se označuje jako „odesílejte a modlete se“). Souběžnost předávání zpráv má tendenci být mnohem snazší uvažovat než souběžnost sdílené paměti a je obvykle považována za robustnější formu souběžného programování. K dispozici je široká škála matematických teorií pro pochopení a analýzu systémů pro předávání zpráv, včetně hereckého modelu a různých procesních kalkulů . Předávání zpráv lze efektivně implementovat prostřednictvím symetrického vícenásobného zpracování s koherencí mezipaměti sdílené paměti nebo bez ní .

Sdílená paměť a souběžnost předávání zpráv mají různé výkonnostní charakteristiky. Typicky (i když ne vždy) je režie paměti na proces a přepínání úkolů v systému předávání zpráv nižší, ale režie předávání zpráv je větší než u volání procedury. Tyto rozdíly jsou často zahlceny jinými výkonnostními faktory.

Dějiny

Souběžné výpočty se vyvinuly z dřívějších prací o železnicích a telegrafii z 19. a počátku 20. století a některé termíny pocházejí z tohoto období, například semafory. Ty vyvstaly, aby se zabývaly otázkou, jak zvládnout více vlaků na stejném železničním systému (vyhnout se kolizím a maximalizovat účinnost) a jak zvládnout více přenosů přes danou sadu drátů (zlepšit účinnost), například prostřednictvím multiplexování s časovým dělením (70. léta 19. století) ).

Akademická studie souběžných algoritmů byla zahájena v 60. letech 20. století a Dijkstra (1965) se zasloužil o to, že byl prvním dokumentem v této oblasti, který identifikoval a řešil vzájemné vyloučení .

Prevalence

Souběžnost je v oblasti výpočetní techniky všudypřítomná, od hardwaru nízké úrovně na jednom čipu až po celosvětové sítě. Následují příklady.

Na úrovni programovacího jazyka:

Na úrovni operačního systému:

Na úrovni sítě jsou síťové systémy obecně svou povahou souběžné, protože se skládají ze samostatných zařízení.

Jazyky podporující souběžné programování

Souběžné programovací jazyky jsou programovací jazyky, které pro souběžnost používají jazykové konstrukce . Tyto konstrukce mohou zahrnovat více vláken , podporu distribuovaných počítačů , předávání zpráv , sdílené prostředky (včetně sdílené paměti ) nebo futures a sliby . Tyto jazyky jsou někdy popisovány jako jazyky orientované na souběžnost nebo souběžně orientované programovací jazyky (COPL).

Dnes jsou nejčastěji používanými programovacími jazyky, které mají specifické konstrukce pro souběžnost, Java a C# . Oba tyto jazyky zásadně používají model souběžné paměti se sdílenou pamětí, přičemž uzamykání zajišťují monitory (ačkoli modely předávání zpráv mohou a byly implementovány nad základní model sdílené paměti). Z jazyků, které používají souběžný model pro předávání zpráv, je v současnosti v průmyslu pravděpodobně nejrozšířenější Erlang .

Mnoho souběžných programovacích jazyků bylo vyvinuto spíše jako výzkumné jazyky (např. Pict ) než jako jazyky pro produkční použití. Jazyky jako Erlang , Limbo a occam však za posledních 20 let zaznamenaly průmyslové využití v různých dobách. Neúplný seznam jazyků, které používají nebo poskytují souběžná programovací zařízení:

  • Ada - obecný účel s nativní podporou předávání zpráv a souběžnosti založené na monitoru
  • Alef — souběžný, s vlákny a předáváním zpráv, pro programování systému v raných verzích Plan 9 od Bell Labs
  • Alice - rozšíření o standardní ML , přidává podporu pro souběžnost prostřednictvím futures
  • Ateji PX-rozšíření do Javy s paralelními primitivy inspirovanými π-kalkulem
  • Axum — specifické pro doménu, souběžné, založené na modelu herce a .NET Common Language Runtime využívající syntaxi podobnou C
  • BMDFM - binární modulární modul DataFlow
  • C ++ —std :: vlákno
  • Cω (C omega) - pro výzkum rozšiřuje C#, používá asynchronní komunikaci
  • C# - podporuje souběžné výpočty pomocí zámku, výtěžku, také od verze 5.0 asynchronní a čekají na zavedení klíčových slov
  • Clojure - moderní, funkční dialekt Lispu na platformě Java
  • Souběžné čištění - funkční programování, podobné Haskellu
  • Souběžné sbírky (CnC) - dosahuje implicitní paralelismu nezávislého na paměťovém modelu tím, že výslovně definuje tok dat a řízení
  • Souběžný Haskell - líný, čistě funkční jazyk, který provozuje souběžné procesy ve sdílené paměti
  • Souběžné ML - souběžné rozšíření standardního ML
  • Souběžný Pascal - Per Brinch Hansen
  • Kari
  • D - víceparadigmový systémový programovací jazyk s explicitní podporou souběžného programování ( herecký model )
  • E — používá sliby k vyloučení zablokování
  • ECMAScript - používá sliby pro asynchronní operace
  • Eiffel - prostřednictvím svého mechanismu SCOOP založeného na konceptech Design by Contract
  • Elixír- dynamický a funkční metaprogramovací jazyk běžící na virtuálním počítači Erlang.
  • Erlang - používá asynchronní předávání zpráv bez sdílení
  • FAUST -funkce v reálném čase, pro zpracování signálu kompilátor zajišťuje automatickou paralelizaci prostřednictvím OpenMP nebo konkrétního plánovače krádeží práce
  • Fortran - coarrays a do concurrent jsou součástí standardu Fortran 2008
  • Jdi - pro programování systému se souběžným programovacím modelem založeným na CSP
  • Haskell - souběžný a paralelní funkční programovací jazyk
  • Hume - funkční, souběžný, pro ohraničená časoprostorová prostředí, kde jsou procesy automatů popsány vzory synchronních kanálů a předáváním zpráv
  • Io -souběžnost založená na hercích
  • Janus -features odlišné askers a skrutátorů do logických proměnných, taška kanálů; je čistě deklarativní
  • Java - třída vláken nebo spustitelné rozhraní
  • Julia- "souběžná programovací primitiva: úkoly, asynchronní čekání, kanály."
  • JavaScript - prostřednictvím webových pracovníků , v prostředí prohlížeče, sliby a zpětná volání .
  • JoCaml- souběžný a distribuovaný kanál, rozšíření OCaml , implementuje spojovací kalkul procesů
  • Přidejte se k Java -concurrent, založený na Java jazyku
  • Joule — založené na toku dat, komunikuje předáváním zpráv
  • Joyce — souběžná, výuka, postavená na Concurrent Pascal s funkcemi od CSP od Per Brinch Hansena
  • LabVIEW —grafické, tok dat, funkce jsou uzly v grafu, data jsou dráty mezi uzly; zahrnuje objektově orientovaný jazyk
  • Limbo -relative na Alef , pro programování systému v Pekle (operační systém)
  • MultiLisp - varianta schématu rozšířena o podporu paralelismu
  • Modula-2- pro programování systému N. Wirth jako nástupce Pascalu s nativní podporou korutin
  • Modula-3- moderní člen rodiny Algol s rozsáhlou podporou vláken, mutexů, proměnných podmínek
  • Newsqueak- pro výzkum s kanály jako prvotřídními hodnotami; předchůdce Alefa
  • occam - silně ovlivněn komunikačními sekvenčními procesy (CSP)
  • Orc - těžce souběžný, nedeterministický, založený na Kleeneově algebře
  • Oz-Mozart- multiparadigm, podporuje souběžnost sdíleného stavu a předávání zpráv a futures
  • ParaSail -objektově orientovaný, paralelní, bez ukazatelů, závodních podmínek
  • Pict-v podstatě spustitelná implementace Milnerova π-počtu
  • Raku standardně obsahuje třídy pro vlákna, sliby a kanály
  • Python -používá paralelismus založený na vláknech a paralelismus na základě procesů
  • Reia- používá asynchronní zprávy procházející mezi objekty typu shared-nothing
  • Červená/Systém - pro programování systému na základě Rebol
  • Rez- pro systémové programování využívající předávání zpráv se sémantikou pohybu, sdílenou neměnnou paměť a sdílenou proměnnou paměť.
  • Scala- obecný účel, navržený tak, aby stručným, elegantním a bezpečným způsobem vyjádřil běžné programovací vzorce
  • Sekvence L- obecný účel, hlavní cíle návrhu jsou snadné programování, čitelnost kódu a automatická paralelizace pro výkon na vícejádrovém hardwaru a prokazatelně bez závodních podmínek
  • SR - pro výzkum
  • SuperPascal - souběžný, pro výuku, postavený na souběžných Pascalech a Joyce od Per Brinche Hansena
  • Unicon - pro výzkum
  • TNSDL - pro vývoj telekomunikačních ústředen používá asynchronní předávání zpráv
  • VHSIC Hardware Description Language ( VHDL ) —IEEE STD-1076
  • XC -podmnožina jazyka C rozšířená o souběžnost vyvinutá XMOS , založená na komunikaci sekvenčních procesů , vestavěné konstrukce pro programovatelné I/O

Mnoho dalších jazyků poskytuje podporu pro souběžnost ve formě knihoven na úrovních zhruba srovnatelných s výše uvedeným seznamem.

Viz také

Poznámky

Reference

Prameny

  • Patterson, David A .; Hennessy, John L. (2013). Organizace a design počítače: Hardwarové/softwarové rozhraní . Série Morgan Kaufmann v počítačové architektuře a designu (5 ed.). Morgan Kaufmann. ISBN 978-0-12407886-4.

Další čtení

externí odkazy