Souběžnost (počítačová věda) - Concurrency (computer science)

Pro praktičtější diskusi viz Souběžné výpočty.
Další významy viz Konkurence.
The „Jídelní filozofové“ klasický problém zahrnující souběžnost a sdílené prostředky

v počítačová věda, konkurence je schopnost různých částí nebo jednotek programu, algoritmu nebo problému provádět mimo pořadí nebo v částečném pořadí, aniž by to ovlivnilo konečný výsledek. To umožňuje paralelní provádění souběžných jednotek, což může výrazně zlepšit celkovou rychlost provádění ve víceprocesorových a vícejádrových systémech. Z technického hlediska souběžnost označuje vlastnost rozložitelnosti programu, algoritmu nebo problému na součásti nebo jednotky nezávislé na pořadí nebo částečně uspořádané.[1]

Pro obecný souběžný výpočet byla vyvinuta řada matematických modelů Petriho sítě, zpracovat kalkul, paralelní stroj s náhodným přístupem model, herec model a Reo koordinační jazyk.

Dějiny

Tak jako Leslie Lamport (2015) uvádí: „Zatímco souběžný program poprava byla zvažována po celá léta, počítačová věda o souběžnosti začala Edsger Dijkstra Seminární práce z roku 1965, která představila vzájemné vyloučení problém. ... Následující desetiletí zaznamenaly obrovský nárůst zájmu o souběžnost - zejména o distribuované systémy. Při pohledu zpět na počátky pole vyniká zásadní role, kterou hraje Edsger Dijkstra “.[2]

Problémy

Vzhledem k tomu, že výpočty v souběžném systému mohou při provádění vzájemně ovlivňovat, může být počet možných cest provádění v systému extrémně velký a výsledný výsledek může být neurčitý. Současné použití sdíleného zdroje může být zdrojem neurčitosti vedoucí k problémům jako např zablokování, a hladovění zdrojů.[3]

Návrh souběžných systémů často vyžaduje nalezení spolehlivých technik pro koordinaci jejich provádění, výměnu dat, alokace paměti a plánování provádění minimalizovat Doba odezvy a maximalizovat propustnost.[4]

Teorie

Teorie souběžnosti byla aktivní oblastí výzkumu v teoretická informatika. Jeden z prvních návrhů byl Carl Adam Petri klíčová práce na Petriho sítě na počátku šedesátých let. V následujících letech byla vyvinuta široká škála formalismů pro modelování a uvažování o souběžnosti.

Modely

Byla vyvinuta řada formalismů pro modelování a porozumění souběžným systémům, včetně:[5]

Některé z těchto modelů souběžnosti jsou primárně určeny na podporu uvažování a specifikace, zatímco jiné lze použít během celého vývojového cyklu, včetně návrhu, implementace, kontroly, testování a simulace souběžných systémů. Některé z nich jsou založeny na předávání zpráv, zatímco jiné mají různé mechanismy pro souběžnost.

Šíření různých modelů souběžnosti motivovalo některé výzkumníky k vývoji způsobů sjednocení těchto různých teoretických modelů. Například Lee a Sangiovanni-Vincentelli prokázali, že lze použít takzvaný model „značkovaného signálu“ k poskytnutí společného rámce pro definování denotační sémantika různých modelů souběžnosti,[7] zatímco Nielsen, Sassone a Winskel to prokázali teorie kategorií lze použít k poskytnutí podobného jednotného porozumění různým modelům.[8]

Věta o reprezentaci souběžnosti v modelu herec poskytuje poměrně obecný způsob, jak reprezentovat souběžné systémy, které jsou uzavřeny v tom smyslu, že neobdrží komunikaci zvenčí. (Jiné souběžné systémy, např. zpracovat kalkul lze modelovat v modelu herce pomocí a dvoufázový protokol potvrzení.[9]) Matematická denotace označená uzavřeným systémem S je konstruována stále lepší aproximace z původního volaného chování ⊥S pomocí funkce aproximace chování postupS sestavit označení (význam) pro S jak následuje:[10]

OznačitS ≡ ⊔i∈ω postupSi(⊥S)

Takto, S lze matematicky charakterizovat z hlediska všech jeho možných chování.

Logika

Různé typy časová logika[11] lze použít jako pomůcku pro souběžné systémy. Některé z těchto logik, jako např lineární časová logika a logika výpočetního stromu, umožnit tvrzení o sledech stavů, kterými může souběžný systém projít. Ostatní, jako např akční výpočetní logika stromu, Logika Hennessy – Milner, a Lamportova časová logika akcí, stavět svá tvrzení ze sekvencí akce (změny stavu). Hlavní aplikací těchto logik je psaní specifikací pro souběžné systémy.[3]

Praxe

Souběžné programování zahrnuje programovací jazyky a algoritmy používané k implementaci souběžných systémů. Souběžné programování je obvykle považováno za obecnější než paralelní programování protože to může zahrnovat libovolné a dynamické vzorce komunikace a interakce, zatímco paralelní systémy mají obecně předdefinovaný a dobře strukturovaný komunikační vzor. Mezi základní cíle souběžného programování patří správnost, výkon a robustnost. Souběžné systémy jako např Operační systémy a Systémy pro správu databází jsou obecně navrženy tak, aby fungovaly na dobu neurčitou, včetně automatického zotavení po selhání, a nikoli neočekávaně ukončeny (viz Řízení souběžnosti ). Některé souběžné systémy implementují formu transparentní souběžnosti, ve které mohou souběžné výpočetní entity soutěžit a sdílet jeden zdroj, ale složitost této soutěže a sdílení jsou chráněny před programátorem.

Protože používají sdílené prostředky, souběžné systémy obecně vyžadují zahrnutí nějakého druhu rozhodce někde v jejich implementaci (často v základním hardwaru), kontrolovat přístup k těmto zdrojům. Použití rozhodců zavádí možnost neurčitost při souběžném výpočtu což má hlavní důsledky pro praxi, včetně správnosti a výkonu. Například představuje arbitráž neomezený nedeterminismus což vyvolává problémy s kontrola modelu protože způsobuje explozi ve stavovém prostoru a může dokonce způsobit, že modely budou mít nekonečné množství stavů.

Některé modely souběžného programování zahrnují koprocesy a deterministická souběžnost. V těchto modelech podprocesy řízení výslovně výtěžek jejich časové plány, buď do systému, nebo do jiného procesu.

Viz také

Reference

  1. ^ Lamport, Leslie (červenec 1978). „Čas, hodiny a řazení událostí v distribuovaném systému“ (PDF). Komunikace ACM. 21 (7): 558–565. doi:10.1145/359545.359563. Citováno 4. února 2016.
  2. ^ Lamport, Leslie. „Turing Lecture: The Computer Science of Concurrency: The Early Years (Communications of the ACM, Vol. 58 No. 6, June 2015)“. ACM. Citováno 22. března 2017.
  3. ^ A b Cleaveland, Rance; Scott Smolka (prosinec 1996). „Strategické směry ve výzkumu souběžnosti“. ACM Computing Surveys. 28 (4): 607. doi:10.1145/242223.242252.
  4. ^ Campbell, Colin; Johnson, Ralph; Miller, Ade; Toub, Stephen (srpen 2010). Paralelní programování s Microsoft .NET. Microsoft Press. ISBN  978-0-7356-5159-3.
  5. ^ Filman, Robert; Daniel Friedman (1984). Koordinované výpočty - nástroje a techniky pro distribuovaný software. McGraw-Hill. ISBN  978-0-07-022439-1.
  6. ^ Keller, Jörg; Christoph Keßler; Jesper Träff (2001). Praktické programování PRAM. John Wiley and Sons.
  7. ^ Lee, Edward; Alberto Sangiovanni-Vincentelli (prosinec 1998). „Rámec pro porovnání modelů výpočtu“ (PDF). Transakce IEEE na CAD. 17 (12): 1217–1229. doi:10.1109/43.736561.
  8. ^ Mogens Nielsen; Vladimiro Sassone; Glynn Winskel (1993). „Vztahy mezi modely souběžnosti“. REX School / Symposium.
  9. ^ Frederick Knabe. Distribuovaný protokol pro komunikaci založenou na kanálech s volbou PARLE 1992.
  10. ^ William Clinger (Červen 1981). "Základy herecké sémantiky". Disertační práce z matematiky. MIT. hdl:1721.1/6935. Citovat deník vyžaduje | deník = (Pomoc)
  11. ^ Roscoe, Colin (2001). Modální a dočasné vlastnosti procesů. Springer. ISBN  978-0-387-98717-0.

Další čtení

  • Lynch, Nancy A. (1996). Distribuované algoritmy. Morgan Kaufmann. ISBN  978-1-55860-348-6.
  • Tanenbaum, Andrew S .; Van Steen, Maarten (2002). Distribuované systémy: Principy a paradigmata. Prentice Hall. ISBN  978-0-13-088893-8.
  • Kurki-Suonio, Reino (2005). Praktická teorie reaktivních systémů. Springer. ISBN  978-3-540-23342-8.
  • Garg, Vijay K. (2002). Prvky distribuovaného výpočtu. Wiley-IEEE Press. ISBN  978-0-471-03600-5.
  • Magee, Jeff; Kramer, Jeff (2006). Souběžnost: Stavové modely a programování v jazyce Java. Wiley. ISBN  978-0-470-09355-9.
  • Distefano, S., & Bruneo, D. (2015). Kvantitativní hodnocení distribuovaných systémů: Metodiky a techniky (1. vyd.). Somerset: John Wiley & Sons Inc.ISBN  9781119131144
  • Bhattacharyya, S. S. (2013; 2014;). Příručka systémů pro zpracování signálu (Druhý; 2; 2. 2013; ed.). New York, NY: Springer 10. 1007 / 978-1-4614-6859-2 ISBN  9781461468592
  • Wolter, K. (2012; 2014;). Posouzení odolnosti a hodnocení výpočetních systémů (1. Aufl.; 1; ed.). Londýn; Berlín ;: Springer. ISBN  9783642290329

externí odkazy