Egyidejűség (informatika) - Concurrency (computer science)
A számítástechnika , konkurencia az, hogy a különböző részek vagy egységek egy programot , algoritmus , vagy problémát kell végrehajtani out-of-order, vagy ugyanabban az időben egyszerre parciális rendezés , anélkül, hogy a végeredmény. Ez lehetővé teszi a párhuzamos egységek párhuzamos végrehajtását, ami jelentősen javíthatja a végrehajtás teljes sebességét a többprocesszoros és a többmagos rendszerekben. Technikai szempontból a párhuzamosság egy program, algoritmus vagy probléma bomlhatóságát jelenti sorrendfüggetlen vagy részlegesen elrendezett komponensekké vagy számítási egységekké.
Szerint Rob Pike , konkurencia az összetétele függetlenül végrehajtó számítások és konkurencia nem párhuzamosság: konkurencia kb foglalkozik rengeteg dolgot egyszerre, de párhuzamosság csinál sok dolgot egyszerre. A párhuzamosság a struktúráról szól, a párhuzamosság a végrehajtásról, a párhuzamosság módot kínál egy megoldás felépítésére egy probléma megoldására, amely (de nem feltétlenül) párhuzamosítható.
Számos matematikai modellt fejlesztettek ki az általános párhuzamos számításokhoz, ideértve a Petri-hálókat , a folyamatkalkulumokat , a párhuzamos véletlen hozzáférésű gépi modellt, a színész modellt és a Reo-koordinációs nyelvet .
Történelem
Ahogy Leslie Lamport (2015) megjegyzi: "Bár az egyidejű programfuttatást évek óta fontolóra vették, az egyidejűség informatikája Edsger Dijkstra 1965-ös alapdokumentumával kezdődött, amely bevezette a kölcsönös kirekesztési problémát. ... Az ezt követő évtizedekben hatalmas az egyidejűség iránti érdeklődés növekedése - különösen az elosztott rendszerekben . A terület eredetére visszatekintve az a kiemelkedő, hogy Edsger Dijkstra alapvető szerepet játszik ".
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 kimenetele meghatározhatatlan . A megosztott erőforrások egyidejű használata meghatározhatatlanság forrása lehet, ami olyan kérdésekhez vezethet, mint a holtpontok és az erőforrások éhezése .
Az egyidejű rendszerek tervezése során gyakran megbízható technikákat kell találni a végrehajtás, az adatcsere, a memóriaallokáció és a végrehajtás ütemezésének összehangolására a válaszidő minimalizálása és az áteresztőképesség maximalizálása érdekében .
Elmélet
A párhuzamosság-elmélet az elméleti informatika aktív kutatási területe volt . Az egyik első javaslat Carl Carl Petri Petri-hálókkal kapcsolatos alapvető munkája volt az 1960-as évek elején. Az azóta eltelt években sokféle formalizmust fejlesztettek ki az egyidejűség modellezésére és érvelésére.
Modellek
Számos formalizmust fejlesztettek ki az egyidejű 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ógépes áthidaló modellek, például a tömeges szinkron párhuzamos (BSP) modell
- Petri hálók
-
Folyamatkő
- A kommunikációs rendszerek kalkulusa (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
Ezen párhuzamossági modellek némelyike elsősorban az érvelés és a specifikáció támogatására szolgál, míg mások felhasználhatók a teljes fejlesztési ciklus alatt, ideértve a párhuzamos rendszerek tervezését, megvalósítását, igazolását, tesztelését és szimulációját. Ezek egy része az üzenet továbbításán alapul , míg mások eltérő mechanizmusokkal rendelkeznek az egyidejűségre vonatkozóan.
A különféle párhuzamossági modellek elterjedése arra ösztönzött néhány kutatót, hogy dolgozzon ki módszereket a különböző elméleti modellek egységesítésére. Például Lee és Sangiovanni-Vincentelli bebizonyította, hogy egy úgynevezett "tagged-signal" modell felhasználható közös keretrendszer létrehozására az egyidejűség különböző modelljeinek denotációs szemantikájának meghatározására , míg Nielsen, Sassone és Winskel kimutatták, hogy a kategóriaelmélet felhasználható a különböző modellek hasonló egységes megértésének biztosítására.
A színész modellben a párhuzamossági reprezentációs tétel meglehetősen általános módot kínál a bezárt párhuzamos rendszerek ábrázolására abban az értelemben, hogy kívülről nem kapnak kommunikációt. (Más párhuzamossági rendszerek, pl. Folyamatszámítások , az aktor modellben modellezhetők kétfázisú elkötelező protokoll segítségével .) Az S zárt rendszerrel jelölt matematikai denotáció egyre jobb közelítéseket alkot az ⊥ S nevű kezdeti viselkedésből, közelítő viselkedést alkalmazva. funkció progresszió S építésére denotációt (értelmét) az S az alábbiak szerint:
- Jelöljük az S ≡ ⊔ i∈ω progressziót S i (⊥ S )
Ily módon az S matematikailag jellemezhető az összes lehetséges viselkedése szempontjából.
Logika
Különböző típusú időbeli logika használható az egyidejű rendszerek indoklásának elő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 logika , lehetővé teszi állítások megfogalmazását azokról az állapotokról, amelyeken keresztül egy párhuzamos rendszer áthaladhat. Mások, mint például a cselekvés számítási fa logikája , a Hennessy – Milner logika és a Lamport cselekvések időbeli logikája, állításukat cselekvéssorozatokból (állapotváltozások) építik . Ezeknek a logikáknak az elsődleges alkalmazása az egyidejű rendszerek specifikációinak írása.
Gyakorlat
Az egyidejű programozás magában foglalja a programozási nyelveket és az egyidejű rendszerek megvalósításához használt algoritmusokat. Az egyidejű programozást általában általánosabbnak tekintik, mint a párhuzamos programozást, mert tetszőleges és dinamikus kommunikációs és interakciós mintákat vonhat maga után, míg a párhuzamos rendszerek általában előre definiált és jól strukturált kommunikációs mintával rendelkeznek. Az egyidejű programozás alapvető céljai a helyesség , a teljesítmény és a robusztusság . Az egyidejű rendszereket, például az operációs rendszereket és az adatbázis-kezelő rendszereket úgy tervezték, hogy a végtelenségig működjenek, beleértve a meghibásodás utáni automatikus helyreállítást is, és nem váratlanul szűnnek meg (lásd: Egyidejűség-vezérlés ) Egyes párhuzamos rendszerek az átlátszó egyidejűség egy olyan formáját valósítják meg, amelyben az egyidejű számítási entitások versenyezhetnek és egyetlen erőforráson osztozhatnak, de a verseny és a megosztás bonyolultságát védik a programozók.
Mivel megosztott erőforrásokat használnak, az egyidejű rendszerek általában megkövetelnek valamilyen döntőbíró bevonását valahol a megvalósításukba (gyakran az alapul szolgáló hardverbe), hogy ellenőrizzék az erőforrásokhoz való hozzáférést. A választottbírók használata megengedi a határozatlanság lehetőségét az egyidejű számításban, amelynek jelentős következményei vannak a gyakorlatra, beleértve a helyességet és a teljesítményt. Például a választottbírósági eljárás korlátlan nemdeterminizmust vezet be, amely problémákat vet fel a modellellenőrzéssel, mert robbanást okoz az állapottérben, és akár végtelen számú állapotot is okozhat a modellekben.
Egyes párhuzamos programozási modellek coprocesses és determinisztikus konkurencia . Ezekben a modellekben a vezérlő szálak kifejezetten adják az időszeletüket, akár a rendszernek, akár egy másik folyamatnak.
Lásd még
- Chu tér
- Kliens – kiszolgáló hálózati csomópontok
- Clojure
- Fürt csomópontok
- Egyidejűség-ellenőrzés
- Egyidejű számítás
- Egyidejű objektum-orientált programozás
- Párhuzamossági minta
- Elosztott folyamatok felépítése és elemzése (CADP)
- D (programozási nyelv)
- Elosztott rendszercsomópontok
- Elixir (programozási nyelv)
- Erlang (programozási nyelv)
- Go (programozási nyelv)
- Gordon Pask
- Nemzetközi konferencia a párhuzamosság elméletéről (CONCUR)
- OpenMP
- Párhuzamos számítás
- Particionált globális címtér
- Folyamatok
- Ptolemaiosz-projekt
- Rust (programozási nyelv)
- Köteg (matematika)
- Szálak
- X10 (programozási nyelv)
Hivatkozások
További irodalom
- Lynch, Nancy A. (1996). Elosztott algoritmusok . Morgan Kaufmann. ISBN 978-1-55860-348-6 .
- Tanenbaum, Andrew S .; Van Steen, Maarten (2002). Elosztott rendszerek: alapelvek és paradigmák . Prentice Hall. ISBN 978-0-13-088893-8 .
- Kurki-Suonio, Reino (2005). A reaktív rendszerek gyakorlati elmélete . Springer. ISBN 978-3-540-23342-8 .
- Garg, Vijay K. (2002). Az elosztott számítástechnika elemei . Wiley-IEEE Press. ISBN 978-0-471-03600-5 .
- Magee, Jeff; Kramer, Jeff (2006). Egyidejűség: Állapotmodellek és Java programozás . Wiley. ISBN 978-0-470-09355-9 .
- Distefano, S., és Bruneo, D. (2015). Az elosztott rendszerek kvantitatív értékelése: Módszertanok és technikák (1. kiadás). Somerset: John Wiley & Sons Inc. ISBN 9781119131144
- Bhattacharyya, SS (2013; 2014;). A jelfeldolgozó rendszerek kézikönyve (Második; 2; 2013. 2.; szerk.). New York, NY: Springer. 10.1007 / 978-1-4614-6859-2 ISBN 9781461468592
- Wolter, K. (2012; 2014;). A rugalmasság felmérése és a számítási rendszerek értékelése (1. Aufl.; 1; szerk.). London; Berlin ;: Springer. ISBN 9783642290329