Párhuzamosság (számítástechnika)

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. július 24-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A számítástechnikában a párhuzamosság a rendszerek azon tulajdonsága, amelyekben egyszerre több számítást hajtanak végre, és ennek során esetleg kölcsönhatásba lépnek egymással. A számítások futhatnak több magon ugyanazon a chipen , megelőző időmegosztási szálakkal ugyanazon a processzoron, vagy futhatnak fizikailag különálló processzorokon . Számos matematikai modellt fejlesztettek ki párhuzamos számítások elvégzésére, beleértve a Petri-hálókat , a folyamatszámítást , a párhuzamos véletlen hozzáférésű számítási modelleket és a szereplőmodelleket .

Megjegyzés  - Az orosz nyelvű irodalomban a "párhuzamosság" és a "versenyképesség" kifejezéseket gyakran összekeverik. . Mindkét a kifejezések a folyamatok egyidejűségét jelentik, de az első fizikai szintű (több folyamat párhuzamos végrehajtása, amely csak a végrehajtás sebességének növelését célozza megfelelő hardveres támogatás használatával), a második pedig az egyik a logikai szint (a folyamatokat függetlenként azonosító rendszertervezési paradigma , amely többek között lehetővé teszi azok párhuzamos fizikai végrehajtását, de elsősorban a többszálú programok írásának egyszerűsítését és stabilitásának növelését célozza).

Problémák

Mivel a párhuzamos rendszerekben végzett számítások kölcsönhatásba lépnek egymással, a lehetséges végrehajtási utak száma rendkívül nagy lehet, és a kapott eredmény nem-determinisztikussá (meghatározatlanná) válhat. A megosztott erőforrások egyidejű használata a nem-determinizmus egyik forrása lehet, ami olyan problémákhoz vezethet, mint például a holtpont vagy az erőforrás-éhezés. [egy]

A párhuzamos rendszerek felépítéséhez megbízható módszereket kell találni a futó folyamatok koordinálására, a kommunikációra, a memória lefoglalására és az ütemezésre a válaszidő minimalizálása és az átviteli sebesség növelése érdekében.

Elmélet

A párhuzamos számítástechnika elmélete az elméleti számítástechnika aktív kutatási területe . Az egyik első ilyen irányú javaslat Carl Adam Petri alapműve volt a Petri- hálókkal kapcsolatban az 1960-as évek elején. A következő években a formalizmusok széles skáláját fejlesztették ki párhuzamos rendszerek modellezésére és leírására.

Modellek

A párhuzamos rendszerek működésének modellezésére és megértésére már számos formális módszert fejlesztettek ki, többek között: [2]

Ezen párhuzamossági modellek némelyike ​​elsősorban következtetések és specifikációk leírására szolgál, míg mások a fejlesztési ciklus során használhatók, beleértve a tervezést, a megvalósítást, az eredmények igazolását, a tesztelést és a párhuzamos rendszerek szimulációját.

A különböző párhuzamossági modellek elterjedése arra késztetett néhány kutatót, hogy módszereket dolgozzanak ki ezen elméleti modellek kombinálására. Például Lee és Sangiovanni-Vincentelli kimutatta, hogy az úgynevezett "címkézett jelek" modellje közös keretet biztosíthat különböző párhuzamossági modellek denotációs szemantikájának leírására [4] , Nielsen, Sassoon és Winskle pedig kimutatta. hogy a kategóriaelmélet felhasználható a különböző modellek közös megértésére. [5]

Az aktormodell egyidejű reprezentációs tétele meglehetősen általános módot ad a párhuzamos rendszerek leírására, amelyek zártak abban az értelemben, hogy nem kapnak üzenetet kívülről. A párhuzamosság leírásának más módszerei, mint például a folyamatszámítás , leírhatók a kétfázisú véglegesítési protokollt használó aktormodellben. [6] Az S zárt rendszer leírására használt matematikai jelölés jobb közelítést ad, ha egy kezdeti viselkedésből épül fel, amelyet ⊥ S -vel jelölünk , S közelítő viselkedési függvényprogresszív felhasználásával . [7] Ekkor az S jelölése a következőképpen épül fel:

Jelölje S ≡ ⊔ i∈ω progresszió S i (⊥ S )

Így S matematikailag kifejezhető az összes lehetséges viselkedésével.

Logika

A párhuzamos rendszerek logikai érvelésének biztosítására különféle időbeli logikák használhatók [8] . Némelyikük, mint például a lineáris időbeli logika vagy a számítási fa logika, lehetővé teszi állítások készítését az állapotok sorozatáról, amelyen egy párhuzamos rendszer át tud menni. Mások, mint például a számítási fa cselekvési logikája, a Hennessy-Milner logika vagy a Lamport-féle időbeli cselekvési logika, műveletek sorozatából (állapotváltozásokból) építik fel állításaikat . E logikák fő felhasználása a párhuzamos rendszerek specifikációinak írása. [egy]

Gyakorlat

Ebben a részben a párhuzamosság két, az angol irodalomban elterjedt fogalmát fogjuk használni, mivel ezek egymással való összehasonlításáról lesz szó. A Concurrency kifejezést "egyidejűségnek", a párhuzamosság kifejezést pedig "párhuzamosságnak" fordítják.

A szimultán programozás magában foglalja a programozási nyelveket és az egyidejű rendszerek megvalósítására használt algoritmusokat. A szimultán programozást általában általánosabbnak tekintik, mint a párhuzamos programozást, mivel tetszőleges dinamikus kommunikációs és interakciós mintákat foglalhat magában, míg a párhuzamos rendszerek leggyakrabban előre meghatározott és jól strukturált kommunikációs mintákat valósítanak meg. A párhuzamos programozás fő céljai a helyesség , hatékonyság , stabilitás . A párhuzamos rendszereket, például az operációs rendszereket és az adatbázis-kezelő rendszereket elsősorban bizonytalan körülmények közötti működésre tervezték, ideértve a hiba utáni automatikus helyreállítást is, ezért nem szabad váratlanul leállniuk. Egyes párhuzamos rendszerek transzparens szimultanitás formájában működnek, amelyben párhuzamos számítási entitások versenyezhetnek ugyanannak az erőforrásnak a használatáért, de ennek a versengésnek a lényege rejtve marad a programozó előtt.

Mivel a párhuzamos rendszerek megosztják az erőforrásokat, jellemzően valamilyen döntőbíróra van szükségük, amely be van építve a megvalósításukba (gyakran a mögöttes hardverbe) az erőforrásokhoz való hozzáférés szabályozásához. A döntőbírók alkalmazása megteremti a bizonytalanság lehetőségét az egyidejű számításoknál, ami a gyakorlat szempontjából nagy jelentőséggel bír, így a helyesség és a hatékonyság biztosítása szempontjából is. Például az arbitrázs nem zárja ki a korlátlan indeterminizmust, amely a modellellenőrzési problémához kapcsolódik , amely az állapottér robbanékonyságának oka, és akár egy végtelen számú állapotú modell kialakulásához is vezethet.

Egyes párhuzamos programozási modellek magukban foglalják a társfolyamatok létrehozását és a determinisztikus szimultanitást . Ezekben a modellekben a folyamatvezérlő szálak kifejezetten megadják időszeleteiket vagy a rendszernek, vagy egy másik folyamatnak.

Lásd még

Jegyzetek

  1. ↑ 1 2 Cleaveland, Rance; Scott Smolka. Stratégiai irányok a párhuzamossági kutatásban  //  ACM Computing Surveys : folyóirat. - 1996. - December ( 28. évf. , 4. sz.). - 607. o . - doi : 10.1145/242223.242252 .
  2. ↑ Filman, Robert; Daniel Friedman. Koordinált számítástechnika – Eszközök és technikák az elosztott  szoftverekhez . - McGraw-Hill Education , 1984. - ISBN 0-07-022439-0 . Archivált másolat (nem elérhető link) . Letöltve: 2011. október 5. Az eredetiből archiválva : 2007. május 16.. 
  3. ↑ Keller, George; Christoph Kessler, Jesper Träff. Gyakorlati PRAM programozás  (neopr.) . – John Wiley és fiai , 2001.
  4. ↑ Lee, Edward; Alberto Sangiovanni-Vincentelli. A számítási modellek összehasonlításának keretrendszere  // IEEE-tranzakciók  CAD -on : folyóirat. - 1998. - December ( 17. évf. , 12. sz.). - P. 1217-1229 . - doi : 10.1109/43.736561 .
  5. ↑ Mogens Nielsen; Vladimiro Sassone és Glynn Winskel (1993). "Az egyidejűségi modellek közötti kapcsolatok" . REX Iskola/Szimpózium . Archiválva az eredetiből, ekkor: 2009-02-26 . Letöltve: 2011-10-05 . Elavult használt paraméter |deadlink=( súgó )
  6. ↑ Frederick Knabe. Elosztott protokoll a csatorna alapú kommunikációhoz a Choice PARLE-vel 1992.
  7. ↑ William Clinger. A színészszemantika alapjai  (neopr.) . - MIT, 1981. - június ( köt. Matematika Doktori Értekezés ).
  8. ↑ Roscoe, Colin. A folyamatok modális és időbeli tulajdonságai  . - Springer, 2001. - ISBN 0-387-98717-7 .

Linkek

  Ugrás a Wikidata elemre  Szótárak és enciklopédiák