bélyegkép|207x207px| 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 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, 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.Frederick Knabe. A Distributed Protocol for Channel-Based Communication with Choice PARLE 1992. ) A zárt rendszerrel jelölt matematikai denotáció egyre jobb közelítéseket konstruál az úgynevezett kezdeti viselkedésből viselkedést közelítő függvény használatával denotáció (jelentése) megalkotásához a következőképpen:
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.
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
Jegyzetek
További irodalom
Distefano, S., & Bruneo, D. (2015). Quantitative assessments of distributed systems: Methodologies and techniques (1st ed.). Somerset: John Wiley & Sons Inc.ISBN 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 Wolter, K. (2012;2014;). Resilience assessment and evaluation of computing systems (1. Aufl.;1; ed.). London;Berlin;: Springer. ISBN 9783642290329
További információk 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
Kategória:Informatika