Souběh (informatika)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 24. července 2022; kontroly vyžadují 2 úpravy .

V informatice je paralelismus vlastnost systémů, ve kterých se provádí několik výpočtů současně, a přitom spolu možná interagují. Výpočty mohou běžet na více jádrech na stejném čipu s preemptivními vlákny sdílení času na stejném procesoru nebo mohou běžet na fyzicky samostatných procesorech . Pro provádění paralelních výpočtů byla vyvinuta řada matematických modelů, včetně Petriho sítí , procesního počtu , paralelních výpočtových modelů s náhodným přístupem a modelů aktérů .

Poznámka  – V ruskojazyčné literatuře se často zaměňují pojmy „paralelnost“ a „konkurenceschopnost“. . Oba termíny znamenají simultánnost procesů, ale první je na fyzické úrovni (paralelní provádění několika procesů, zaměřené pouze na zvýšení rychlosti provádění pomocí vhodné hardwarové podpory), a druhý jeden je na logické úrovni ( paradigma návrhu systému , který identifikuje procesy jako nezávislé, což mimo jiné umožňuje jejich fyzické paralelní provádění, ale je primárně zaměřeno na zjednodušení psaní vícevláknových programů a zvýšení jejich stability).

Problémy

Vzhledem k tomu, že výpočty v paralelních systémech na sebe vzájemně působí, může být počet možných cest provádění extrémně velký a výsledný výsledek se může stát nedeterministickým (neurčitým). Současné používání sdílených zdrojů může být jedním ze zdrojů nedeterminismu, což vede k problémům, jako je uváznutí nebo nedostatek zdrojů. [jeden]

Budování paralelních systémů vyžaduje nalezení spolehlivých metod pro koordinaci běžících procesů, komunikaci, alokaci paměti a plánování, aby se minimalizovala doba odezvy a zvýšila se propustnost.

Teorie

Teorie paralelního počítání je aktivní oblastí výzkumu v teoretické informatice . Jedním z prvních návrhů v tomto směru byla stěžejní práce Carla Adama Petriho o Petriho sítích na počátku 60. let 20. století. V následujících letech byla vyvinuta široká škála formalismů pro modelování a popis paralelních systémů.

Modely

Pro modelování a pochopení fungování paralelních systémů již bylo vyvinuto velké množství formálních metod, včetně: [2]

Některé z těchto modelů souběžnosti jsou primárně určeny pro odvození a popisy specifikací, zatímco jiné lze použít v průběhu celého vývojového cyklu, včetně návrhu, implementace, ověřování výsledků, testování a simulace paralelních systémů.

Šíření různých modelů souběžnosti přimělo některé výzkumníky k vyvinutí způsobů, jak tyto teoretické modely kombinovat. Například Lee a Sangiovanni-Vincentelli ukázali, že takzvaný model „označených signálů“ lze použít k poskytnutí společného rámce pro popis denotační sémantiky různých modelů souběžnosti, [4] a Nielsen, Sassoon a Winskle ukázali tato teorie kategorií může být použita k poskytnutí společného porozumění různým modelům. [5]

Věta o reprezentaci souběžnosti z modelu aktéra poskytuje poměrně obecný způsob, jak popsat souběžné systémy, které jsou uzavřené v tom smyslu, že nepřijímají žádné zprávy zvenčí. Další metody popisu souběžnosti, jako je procesní kalkul , lze popsat pomocí modelu aktéra pomocí dvoufázového potvrzovacího protokolu. [6] Matematická notace používaná k popisu uzavřeného systému S poskytuje lepší aproximaci, je-li vytvořena z počátečního chování, označovaného ⊥ S , pomocí progrese aproximační funkce chování S . [7] Potom se zápis pro S zkonstruuje takto:

Označme S ≡ ⊔ i∈ω progresi S i (⊥ S )

S může být tedy matematicky vyjádřen v termínech všech jeho možných chování.

Logika

K poskytnutí logické úvahy o paralelních systémech lze použít různé druhy temporálních logik [8] . Některé z nich, jako je lineární temporální logika nebo logika výpočetního stromu, umožňují učinit prohlášení o posloupnosti stavů, kterými může paralelní systém projít. Jiní, jako je výpočtová stromová akční logika, Hennessy-Milnerova logika nebo Lamportova dočasná akční logika, sestavují svá prohlášení ze sledu akcí (změn stavu). Hlavním využitím těchto logik je psaní specifikací pro paralelní systémy. [jeden]

Cvičení

V této části použijeme dva pojmy paralelismu, které jsou běžné v anglické literatuře, protože budeme hovořit o jejich vzájemném porovnávání. Termín souběžnost se bude překládat jako "souběžnost" a pojem paralelismus bude přeložen jako "paralelnost".

Simultánní programování zahrnuje programovací jazyky a algoritmy používané k implementaci simultánních systémů. Simultánní programování je obecně považováno za obecnější než paralelní programování, protože může zahrnovat libovolné dynamické komunikační a interakční vzorce, zatímco paralelní systémy nejčastěji implementují předem definované a dobře strukturované komunikační vzorce. Hlavními cíli souběžného programování jsou správnost , efektivita , stabilita . Souběžné systémy, jako jsou operační systémy a systémy pro správu databází, jsou navrženy především pro provoz v nejistých podmínkách, včetně automatického obnovení po selhání, neměly by neočekávaně přestat fungovat. Některé souběžné systémy fungují formou transparentní simultánnosti, ve které mohou souběžné výpočetní entity soutěžit o využití stejného zdroje, ale podstata této soutěže je programátorovi skryta.

Vzhledem k tomu, že souběžné systémy sdílejí zdroje, obvykle vyžadují nějaký druh arbitra zabudovaného do jejich implementace (často základní hardware), který řídí přístup k těmto zdrojům. Použití arbitrů vytváří možnost nejistoty při simultánních výpočtech, což má velký význam pro praxi, včetně zajištění správnosti a účinnosti. Například arbitráž nevylučuje neomezený indeterminismus, který je spojen s problémem kontroly modelu , který je příčinou výbušné povahy stavového prostoru a může dokonce vést k vytvoření modelu s nekonečným počtem stavů.

Některé modely souběžného programování zahrnují vytváření koprocesů a deterministickou simultánnost . V těchto modelech vlákna řízení procesů explicitně dávají své časové úseky buď systému, nebo jinému procesu.

Viz také

Poznámky

  1. ↑ 1 2 Cleaveland, Rance; Scott Smolka. Strategické směry ve výzkumu souběžnosti  //  ACM Computing Surveys : deník. - 1996. - prosinec ( roč. 28 , č. 4 ). — S. 607 . - doi : 10.1145/242223.242252 .
  2. ↑ Filman, Robert; Daniel Friedman. Coordinated Computing – Nástroje a techniky pro distribuovaný  software . - McGraw-Hill Education , 1984. - ISBN 0-07-022439-0 . Archivovaná kopie (nedostupný odkaz) . Získáno 5. října 2011. Archivováno z originálu 16. května 2007. 
  3. ↑ Keller, Jiří; Hrají: Christoph Kessler, Jesper Träff. Praktické programování PRAM  (neopr.) . — John Wiley and Sons , 2001.
  4. ↑ Lee, Edward; Alberto Sangiovanni-Vincentelli. Rámec pro porovnávání výpočetních modelů  // Transakce IEEE na  CAD : deník. - 1998. - prosinec ( roč. 17 , č. 12 ). - S. 1217-1229 . - doi : 10.1109/43.736561 .
  5. ↑ Mogens Nielsen; Vladimiro Sassone a Glynn Winskel (1993). "Vztahy mezi modely souběžnosti" . Škola/Symposium REX . Archivováno z originálu 2009-02-26 . Získáno 2011-10-05 . Použitý zastaralý parametr |deadlink=( nápověda )
  6. ↑ Frederick Knabe. Distribuovaný protokol pro kanálovou komunikaci s volbou PARLE 1992.
  7. ↑ William Clinger. Základy herecké sémantiky  (neopr.) . - MPO, 1981. - červen ( sv. Doktorská disertační práce z matematiky ).
  8. ↑ Roscoe, Colin. Modální a časové vlastnosti  procesů . - Springer, 2001. - ISBN 0-387-98717-7 .

Odkazy

  Přejděte na položku Wikidata  Slovníky a encyklopedie