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

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.

Rob Pike szerint az egyidejűség önállóan végrehajtott számítások összetétele, 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ó.

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."

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 .

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.

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:

• A párhuzamos véletlen hozzáférésű gép
• 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 objektum-orientá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, 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. ) 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ávalprogression_S denotáció (jelentése) megalkotásáhozS a következőképpen:

Denote_S ≡ ⊔_i∈ω progression_Sⁱ(⊥_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 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. 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

• Ügyfél-szerver hálózati csomópontok
• Klaszter csomópontok
• D (programozási nyelv)
• Elosztott rendszer
• Go (programozási nyelv)
• Párhuzamos számítástechnika
• Folyamatok
• Rust (programozási nyelv)
• Szálak

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