Párhuzamosság (számítástudomány)

 Ezt a szócikket némileg át kellene dolgozni a wiki jelölőnyelv szabályainak figyelembevételével, hogy megfeleljen a Wikipédia alapvető stilisztikai és formai követelményeinek.
A „Dining Philosophers” egy klasszikus probléma, amely a párhuzamosságot és a megosztott erőforrásokat foglalja magába.

Az informatikában a párhuzamosság egy program, algoritmus vagy probléma különböző részeinek vagy egységeinek azon képessége, hogy soron kívül vagy részlegesen hajthatók végre anélkül, hogy a végeredményt befolyásolnák. Az egyidejű egységek a párhuzamos egységek párhuzamos végrehajtását, ami jelentősen javíthatja a végrehajtás általános sebességét többprocesszoros és többmagos rendszerekben. Technikai értelemben a párhuzamosság egy program, algoritmus vagy probléma felbonthatóságát jelenti sorrendtől független vagy részben rendezett komponensekre vagy számítási egységekre.[1]

Rob Pike szerint az egyidejűség önállóan végrehajtott számítások összetétele,[2] a párhuzamosság pedig nem párhuzamosság: az egyidejűség azt jelenti, hogy sok mindent egyszerre kell kezelni, de a párhuzamosság azt jelenti, hogy sok mindent egyszerre kell végrehajtani. Az egyidejűség a struktúráról, a párhuzamosság a végrehajtásról szól, a párhuzamosság pedig módot ad a megoldás felépítésére egy olyan probléma megoldására, amely lehet (de nem feltétlenül) párhuzamosítható.[3]

Számos matematikai modellt fejlesztettek ki általános párhuzamos számításokhoz, beleértve a Petri-hálókat, a folyamatszámításokat, a párhuzamos véletlen hozzáférésű gépmodellt, a szereplőmodellt és a Reo koordinációs nyelvet.

Történelem

Leslie Lamport (2015) megjegyzése szerint: „Míg a párhuzamos programvégrehajtást már évek óta fontolgatták, a párhuzamosság számítástechnikája Edsger Dijkstra 1965-ös alapvető tanulmányával kezdődött, amely bemutatta a kölcsönös kizárás problémáját. . . . Az elkövetkező évtizedekben az egyidejűség – különösen az elosztott rendszerek – iránti érdeklődés óriási növekedést mutatott. Ha visszatekintünk a terület eredetére, az Edsger Dijkstra alapvető szerepe kiemelkedik." [4]

Problémák

Mivel egy párhuzamos rendszerben végzett számítások kölcsönhatásba léphetnek egymással a végrehajtás során, a lehetséges végrehajtási utak száma a rendszerben rendkívül nagy lehet, és az eredmény meghatározhatatlan lehet. A megosztott erőforrások egyidejű használata bizonytalanság forrása lehet, ami olyan problémákhoz vezethet, mint például a holtpontok és az erőforrás-éhezés . [5]

A párhuzamos rendszerek tervezése gyakran azt jelenti, hogy megbízható technikákat kell találni a végrehajtásuk, az adatcseréjük, a memóriafoglalásuk és a végrehajtási ütemezésük koordinálására a válaszidő minimalizálása és az átviteli sebesség maximalizálása érdekében. [6]

Elmélet

A párhuzamosságelmélet az elméleti számítástechnika aktív kutatási területe volt. Az egyik első javaslat Carl Adam Petrinek a Petri-hálókkal kapcsolatos alapműve volt az 1960-as évek elején. Az elkövetkező évek során formalizmusok széles választékát fejlesztették ki, melyek az

egyidejűség modellezésére és alátámasztására szolgáltak.

Modellek

Számos formalizmust fejlesztettek ki a párhuzamos rendszerek modellezésére és megértésére, többek között: [7]

  • A párhuzamos véletlen hozzáférésű gép [8]
  • A színész modell
  • Számítási áthidaló modellek, mint például a tömeges szinkron párhuzamos (BSP) modell
  • Petri hálók
  • Folyamat kalkulusok
    • Kommunikációs rendszerek számítása (CCS)
    • Kommunikációs szekvenciális folyamatok (CSP) modell
    • π-számítás
  • Tuple szóközök, pl. Linda
  • Egyszerű párhuzamos objektumorientált programozás (SCOOP)
  • Reo koordinációs nyelv
  • Nyom monoidok

Néhány ilyen párhuzamossági modell elsősorban az érvelés és a specifikáció támogatására szolgál, míg mások a teljes fejlesztési ciklus alatt használhatók, beleértve a párhuzamos rendszerek tervezését, megvalósítását, bizonyítását, tesztelését és szimulációját. Ezek némelyike az üzenettovábbításon alapul, míg mások más-más párhuzamossági mechanizmussal rendelkeznek.

A párhuzamosság különböző modelljeinek elterjedése arra késztetett néhány kutatót, hogy módszereket dolgozzanak ki e különböző elméleti modellek egységesítésére. Lee és Sangiovanni-Vincentelli például bebizonyították, hogy egy úgynevezett "tagged-signal" modell használható arra, hogy közös keretet biztosítson a különböző párhuzamossági modellek denotációs szemantikájának meghatározásához, [9] míg Nielsen, Sassone, és Winskel bebizonyította, hogy a kategóriaelmélet felhasználható a különböző modellek hasonló egységes megértésére.

A cselekvőmodell egyidejű reprezentációs tétele meglehetősen általános módot ad a párhuzamos rendszerek ábrázolására, amelyek zártak abban az értelemben, hogy nem kapnak kommunikációt kívülről. (Más párhuzamossági rendszerek, pl. folyamatszámítások modellezhetők az aktormodellben egy kétfázisú véglegesítési protokoll segítségével. [10] ) A zárt rendszerrel jelölt matematikai denotációS egyre jobb közelítéseket konstruál az úgynevezett kezdeti viselkedésből⊥S viselkedést közelítő függvény használatávalprogressionS denotáció (jelentése) megalkotásáhozS a következőképpen: [11]

DenoteS ≡ ⊔i∈ω progressionSi(⊥S)

ly módon S matematikailag jellemezhető minden lehetséges viselkedése szempontjából.

Logikák

Az időbeli logika különböző típusai [12] használhatók a párhuzamos rendszerekkel kapcsolatos érvelés segítésére. Ezen logikák némelyike, mint például a lineáris időbeli logika és a számítási fa logikája, lehetővé teszi olyan állítások megfogalmazását az állapotsorozatokról, amelyeken egy párhuzamos rendszer áthaladhat. Mások, mint például a cselekvési számítási fa logikája, a Hennessy–Milner-logika és a Lamport-féle időbeli cselekvési logika, cselekvési sorozatokból (állapotváltozásokból) építik fel állításaikat. E logikák fő alkalmazása a párhuzamos rendszerekre vonatkozó specifikációk írása. [5]Cleaveland, Rance; Scott Smolka (December 1996). "Strategic Directions in Concurrency Research". ACM Computing Surveys. 28 (4): 607. doi:10.1145/242223.242252.</ref>

Gyakorlat

A párhuzamos programozás magában foglalja a párhuzamos rendszerek megvalósítására használt programozási nyelveket és algoritmusokat. A párhuzamos programozást általában általánosabbnak tekintik, mint a párhuzamos programozást, mivel tetszőleges és dinamikus kommunikációs és interakciós mintákat foglalhat magában, míg a párhuzamos rendszerek általában előre meghatározott és jól strukturált kommunikációs mintával rendelkeznek. A párhuzamos programozás alapvető céljai közé tartozik a helyesség, a teljesítmény és a robusztusság . A párhuzamos rendszereket, például az operációs rendszereket és az adatbázis-kezelő rendszereket általában úgy tervezték, hogy korlátlan ideig működjenek, beleértve a meghibásodások utáni automatikus helyreállítást is, és ne szakadjanak meg váratlanul (lásd: Konkurencia-vezérlés ). Egyes párhuzamos rendszerek az átlátszó párhuzamosság egy formáját valósítják meg, amelyben a párhuzamos számítási entitások versenyezhetnek egyetlen erőforrásért és megoszthatják azt, de ennek a versengésnek és a megosztásnak a bonyolultsága védve van a programozó elől.

Mivel megosztott erőforrásokat használnak, ezért az egyidejű rendszerek megkövetelik, hogy a

megvalósításnál (gyakran az alapul szolgáló szoftverbe) beépítsenek valamilyen erőforrás hozzáférés szabályzót.. A döntőbírók használata bevezeti a határozatlanság lehetőségét a párhuzamos számítások során, ami jelentős hatással van a gyakorlatra, beleértve a helyességet és a teljesítményt. Például az arbitráció bevezeti a korlátlan nondeterminizmust, ami problémákat vet fel a modellellenőrzés során, mert robbanást okoz az állapottérben, és akár végtelen számú állapotot is okozhat a modelleknek.

Egyes párhuzamos programozási modellek koprocesszusokat és determinisztikus párhuzamosságot tartalmaznak. Ezekben a modellekben a vezérlési szálak kifejezetten átadják az időszeleteket, akár a rendszernek, akár egy másik folyamatnak.

Lásd még

Jegyzetek

  1. ↑ Lamport (1978. július 1.). „Time, Clocks, and the Ordering of Events in a Distributed System”. Communications of the ACM 21 (7), 558–565. o. DOI:10.1145/359545.359563. (Hozzáférés: 2016. február 4.)  
  2. ↑ Go Concurrency Patterns. talks.golang.org. (Hozzáférés: 2021. április 8.)
  3. ↑ Concurrency is not Parallelism. talks.golang.org. (Hozzáférés: 2021. április 8.)
  4. ↑ Lamport, Leslie: Turing Lecture: The Computer Science of Concurrency: The Early Years (Communications of the ACM, Vol. 58 No. 6, June 2015). ACM. (Hozzáférés: 2017. március 22.)
  5. ↑ a b Cleaveland (1996. december 1.). „Strategic Directions in Concurrency Research”. ACM Computing Surveys 28 (4), 607. o. DOI:10.1145/242223.242252.  
  6. ↑ Campbell, Colin. Parallel Programming with Microsoft .NET. Microsoft Press (2010. augusztus 1.). ISBN 978-0-7356-5159-3 
  7. ↑ Filman, Robert. Coordinated Computing - Tools and Techniques for Distributed Software. McGraw-Hill (1984). ISBN 978-0-07-022439-1 
  8. ↑ Keller, Jörg. Practical PRAM Programming. John Wiley and Sons (2001) 
  9. ↑ Lee (1998. december 1.). „A Framework for Comparing Models of Computation”. IEEE Transactions on CAD 17 (12), 1217–1229. o. DOI:10.1109/43.736561.  
  10. ↑ Frederick Knabe. A Distributed Protocol for Channel-Based Communication with Choice PARLE 1992.
  11. ↑ William Clinger (1981. június 1.). „Foundations of Actor Semantics”, Kiadó: MIT.  
  12. ↑ Roscoe, Colin. Modal and Temporal Properties of Processes. Springer (2001). ISBN 978-0-387-98717-0 

További irodalom

  • Lynch, Nancy A.. Distributed Algorithms. Morgan Kaufmann (1996). ISBN 978-1-55860-348-6 
  • Tanenbaum, Andrew S.. Distributed Systems: Principles and Paradigms. Prentice Hall (2002). ISBN 978-0-13-088893-8 
  • Kurki-Suonio, Reino. A Practical Theory of Reactive Systems. Springer (2005). ISBN 978-3-540-23342-8 
  • Garg, Vijay K.. Elements of Distributed Computing. Wiley-IEEE Press (2002). ISBN 978-0-471-03600-5 
  • Magee, Jeff. Concurrency: State Models and Java Programming. Wiley (2006). ISBN 978-0-470-09355-9 
  • Distefano, S., & Bruneo, D. (2015). Quantitative assessments of distributed systems: Methodologies and techniques (1st ed.). Somerset: John Wiley & Sons Inc.ISBN 9781119131144ISBN 9781119131144
  • Bhattacharyya, S. S. (2013;2014;). Handbook of signal processing systems (Second;2;2nd 2013; ed.). New York, NY: Springer.10.1007/978-1-4614-6859-2 ISBN 9781461468592
  • Wolter, K. (2012;2014;). Resilience assessment and evaluation of computing systems (1. Aufl.;1; ed.). London;Berlin;: Springer. ISBN 9783642290329ISBN 9783642290329

Külső linkek

  • Folyamatalgebrai napló – Prof. Luca Aceto blogja a Konkurenciaelméletről
  • Párhuzamos rendszerek a WWW virtuális könyvtárában
  • Egyidejűségi minták bemutatása a scaleconf -on