Egyidejű számítástechnika - Concurrent computing

További elméleti vitához lásd: Egyidejűség (számítástechnika) .
Programozási paradigmák

Egyidejű computing egyik formája a számítástechnikai amelyben több számítások végrehajtása egyidejűleg szelenii átfedő időszakok, ahelyett sequentially- egy befejezése előtt a következő megkezdődik.

Ez egy rendszer tulajdonsága - legyen az program , számítógép vagy hálózat -, ahol minden folyamathoz külön végrehajtási pont vagy "vezérlési szál" tartozik. A párhuzamos rendszer olyan, ahol a számítás előrehaladhat anélkül, hogy megvárná az összes többi számítás befejezését.

A párhuzamos számítástechnika a moduláris programozás egyik formája . A paradigmájában az átfogó számítást részszámításokba veszik , amelyek egyidejűleg végrehajthatók. A párhuzamos számítástechnika úttörői közé tartozik Edsger Dijkstra , Per Brinch Hansen és a CAR Hoare .

Bevezetés

Lásd még: Párhuzamos számítástechnika

A párhuzamos számítástechnika fogalmát gyakran összetévesztik a párhuzamos számítástechnika kapcsolódó, de különálló fogalmával , bár mindkettőt úgy írhatjuk le, mint "több folyamatot , amelyek ugyanabban az időszakban futnak ". A párhuzamos számítástechnikában a végrehajtás ugyanazon a fizikai pillanatban történik: például egy többprocesszoros gép külön processzorain , a számítások felgyorsítása érdekében-a párhuzamos számítás lehetetlen egy ( egymagos ) egyetlen processzoron, mivel csak egy a számítás bármikor megtörténhet (egyetlen órajel ciklus alatt). Ezzel szemben a párhuzamos számítástechnika a folyamatok élettartamának átfedéséből áll , de a végrehajtásnak nem kell ugyanabban a pillanatban történnie. A cél itt a külvilág egyidejűleg zajló folyamatainak modellezése, például több ügyfél egyidejű elérése egy szerverhez. A több párhuzamos, kommunikáló részből álló szoftverrendszerek strukturálása hasznos lehet a komplexitás kezelésében, függetlenül attól, hogy az alkatrészek párhuzamosan végrehajthatók -e.

Például az egyidejű folyamatok végrehajthatók egy magon úgy, hogy az egyes folyamatok végrehajtási lépéseit időmegosztó szeleteken keresztül összeillesztik: egyszerre csak egy folyamat fut, és ha nem fejeződik be az időszelet alatt, akkor szüneteltetik , egy másik folyamat kezdődik vagy folytatódik, majd később az eredeti folyamat folytatódik. Ily módon több folyamat is félidőben hajtódik végre a végrehajtásban egyetlen pillanatban, de csak egy folyamat kerül végrehajtásra abban a pillanatban.

Egyidejű számítások lehet párhuzamosan futtatni, például, hozzárendelésével minden egyes folyamat, hogy egy külön processzor vagy processzor mag, vagy forgalmazó a számítás a hálózaton keresztül. Általában azonban előfordulhat, hogy a párhuzamos programozás nyelvei, eszközei és technikái nem alkalmasak az egyidejű programozásra, és fordítva.

A párhuzamos rendszerben a feladatok végrehajtásának pontos időzítése az ütemezéstől függ , és a feladatokat nem kell mindig párhuzamosan végrehajtani. Például két feladat, a T1 és a T2 alapján:

  • A T1 végrehajtható és befejezhető a T2 előtt, vagy fordítva (soros és soros)
  • A T1 és T2 végrehajtható felváltva (soros és párhuzamos)
  • A T1 és T2 egyidejűleg végrehajtható ugyanabban az időpontban (párhuzamosan és párhuzamosan)

A "szekvenciális" szót az "egyidejű" és a "párhuzamos" antonimájaként használják; ha ezeket kifejezetten megkülönböztetik, akkor a párhuzamos/szekvenciális és a párhuzamos/soros ellentétes párokat használják. Azt az ütemezést, amelyben a feladatok egyenként hajtanak végre (sorozatosan, párhuzamosság nélkül), interleavelés nélkül (szekvenciálisan, nincs párhuzamosság: egyetlen feladat sem kezdődik el az előző feladat befejezéséig), soros ütemezésnek nevezzük . A sorozatosan ütemezhető feladatok sorozhatóak , ami leegyszerűsíti az egyidejűség ellenőrzését .

A megosztott erőforrásokhoz való hozzáférés koordinálása

A párhuzamos programok tervezésének fő kihívása a párhuzamosság -ellenőrzés : a különböző számítási végrehajtások közötti interakciók vagy kommunikációk helyes sorrendjének biztosítása, valamint a végrehajtások között megosztott erőforrásokhoz való hozzáférés koordinálása. A lehetséges problémák közé tartoznak a versenykörülmények , a patthelyzetek és az erőforrások éhezése . Például vegye figyelembe a következő algoritmust a megosztott erőforrás által képviselt folyószámláról történő kivonáshoz balance: 

bool withdraw(int withdrawal)
{
    if (balance >= withdrawal)
    {
        balance -= withdrawal;
        return true;
    } 
    return false;
}

Tegyük fel balance = 500, hogy két párhuzamos szál hívja withdraw(300)és withdraw(350). Ha mindkét művelet 3. sora végrehajtódik az 5. sor előtt, akkor mindkét művelet azt találja, hogy balance >= withdrawalaz érték lesz true, és a végrehajtás folytatja a kivonási összeg levonását. Mivel azonban mindkét folyamat végrehajtja a kivonásait, a teljes kivont összeg végül meghaladja az eredeti egyenleget. A megosztott erőforrásokkal kapcsolatos ilyen jellegű problémák előnyösek az egyidejűség-szabályozás vagy a nem blokkoló algoritmusok használatából .

Előnyök

Az egyidejű számítástechnika előnyei a következők:

  • Fokozott programáteresztő képesség - párhuzamos egyidejű program végrehajtása lehetővé teszi, hogy az adott idő alatt elvégzett feladatok száma arányosan növekedjen a processzorok számával Gustafson törvénye szerint
  • Magas érzékenység a bemenetre/kimenetre-a bemeneti/kimeneti intenzív programok többnyire megvárják a bemeneti vagy kimeneti műveletek befejezését. A párhuzamos programozás lehetővé teszi azt az időt, amelyet egy másik feladatra való felhasználásra várva kell tölteni.
  • Megfelelőbb programstruktúra-egyes problémák és problémakörök jól illeszkednek a párhuzamos feladatok vagy folyamatok megjelenítéséhez.

Modellek

Az 1962 -ben bevezetett Petri -hálók korai kísérletek voltak az egyidejű végrehajtás szabályainak kodifikálására. Az adatfolyam -elmélet később ezekre épült, és az adatfolyam -architektúrákat azért hozták létre, hogy fizikailag megvalósítsák az adatfolyam -elméletet. Az 1970 -es évek végétől kezdve olyan folyamatszámításokat fejlesztettek ki , mint a Kommunikációs Rendszerek Kalkulusa (CCS) és a Kommunikációs Szekvenciális Folyamatok (CSP), hogy lehetővé tegyék az algebrai érvelést az egymással kölcsönhatásban lévő komponensekből álló rendszerekről. A π-számítás hozzáadta a dinamikus topológiákkal kapcsolatos érvelés képességét.

A bemeneti/kimeneti automatákat 1987 -ben vezették be.

Olyan logikákat fejlesztettek ki, mint a Lamport TLA+ , valamint matematikai modelleket, például nyomvonalakat és Actor eseménydiagramokat , hogy leírják az egyidejű rendszerek viselkedését.

A szoftver tranzakciós memória az adatbázis -elméletből kölcsönzi az atomi tranzakciók fogalmát, és alkalmazza azokat a memória -hozzáférésekre.

Konzisztencia modellek

Fő cikk: Konzisztencia modell

A párhuzamos programozási nyelveknek és a többprocesszoros programoknak konzisztencia -modellel kell rendelkezniük (más néven memóriamodell). A konzisztencia modell meghatározza a számítógép memóriájában végzett műveletek végrehajtásának és az eredmények előállításának szabályait .

Az egyik első konzisztencia modell volt Molnár Emma „s szekvenciális konzisztencia modell. A szekvenciális konzisztencia egy program tulajdonsága, hogy végrehajtása ugyanazokat az eredményeket hozza, mint a szekvenciális program. Pontosabban, egy program akkor következetes, ha "bármely végrehajtás eredménye ugyanaz, mintha az összes processzor műveleteit valamilyen sorrendben hajtották volna végre, és minden egyes processzor műveletei ebben a sorrendben jelennek meg a program által meghatározott sorrendben ".

Lásd még: Nyugodt sorozat

Végrehajtás

Számos különböző módszer használható az egyidejű programok megvalósítására, például az egyes számítási végrehajtások végrehajtása operációs rendszer folyamatként , vagy a számítási folyamatok végrehajtása szálak halmazaként egyetlen operációs rendszer folyamatán belül.

Interakció és kommunikáció

Egyes párhuzamos számítástechnikai rendszerekben a párhuzamos komponensek közötti kommunikáció rejtve van a programozó előtt (pl. Határidős ügyletek használatával ), míg másokban ezt kifejezetten kell kezelni. Az explicit kommunikáció két osztályra osztható:

Kommunikáció megosztott memóriával
A párhuzamos komponensek a megosztott memóriahelyek tartalmának megváltoztatásával kommunikálnak (például Java és C# ). Ennek a párhuzamos programozási stílusnak általában szüksége van valamilyen zárolási módra (pl. Mutexek , szemaforok vagy monitorok ) a szálak közötti koordinációhoz. Egy olyan programot, amely ezek bármelyikét megfelelően végrehajtja, szálbiztosnak mondják .
Az üzenet továbbítása kommunikáció
A párhuzamos komponensek üzenetváltással kommunikálnak (például MPI , Go , Scala , Erlang és occam ). Az üzenetváltás történhet aszinkron módon, vagy használhat szinkron "találkozó" stílust, amelyben a feladó blokkolja az üzenet fogadását. Az aszinkron üzenetátadás megbízható vagy megbízhatatlan lehet (néha „küldés és imádkozás” néven is emlegetik). Az üzenetközvetítő párhuzamosságot sokkal könnyebb megfontolni, mint a megosztott memória párhuzamosságot, és általában a párhuzamos programozás robusztusabb formájának tekintik. Az üzenetátadó rendszerek megértéséhez és elemzéséhez számos matematikai elmélet áll rendelkezésre, beleértve a szereplő modellt és a különböző folyamatszámításokat . Az üzenetátadás hatékonyan megvalósítható szimmetrikus többfeldolgozással , megosztott memória gyorsítótár -koherenciával vagy anélkül .

A megosztott memória és az üzenettovábbítás párhuzamossága eltérő teljesítményjellemzőkkel rendelkezik. Jellemzően (bár nem mindig) a folyamatonkénti memória és a feladatváltás általános költsége alacsonyabb az üzenetátadó rendszerben, de az üzenetátadás költsége nagyobb, mint egy eljáráshívás esetén. Ezeket a különbségeket gyakran felülmúlják más teljesítménytényezők.

Történelem

A párhuzamos számítástechnika a vasútról és a távíróról szóló korábbi munkákból fejlődött ki , a 19. századból és a 20. század elejéről, és néhány kifejezés erre az időszakra datálódik, például a szemaforok. Ezek felmerültek annak a kérdésnek a megválaszolásához, hogy hogyan kell kezelni több vonatot ugyanazon a vasúti rendszeren (elkerülve az ütközéseket és maximalizálva a hatékonyságot), és hogyan kell kezelni a többszörös átvitelt egy adott vezetékkészleten keresztül (javítva a hatékonyságot), például időosztásos multiplexeléssel (1870-es évek) ).

A párhuzamos algoritmusok tudományos tanulmányozása az 1960 -as években kezdődött, Dijkstra (1965) szerint az első tanulmány ezen a területen, azonosítva és megoldva a kölcsönös kirekesztést .

Elterjedtség

A párhuzamosság elterjedt a számítástechnikában, az alacsony szintű hardverekről egyetlen chipen keresztül a világméretű hálózatokig. Példák következnek.

A programozási nyelv szintjén:

Operációs rendszer szinten:

Hálózati szinten a hálózati rendszerek jellegüknél fogva általában párhuzamosak, mivel különálló eszközökből állnak.

Az egyidejű programozást támogató nyelvek

A párhuzamos programozási nyelvek olyan programozási nyelvek, amelyek nyelvi konstrukciókat használnak az egyidejűséghez . Ezek a konstrukciók magukban foglalhatják a többszálasodást , az elosztott számítástechnika támogatását , az üzenetek továbbítását , a megosztott erőforrásokat (beleértve a megosztott memóriát ) vagy a jövőket és ígéreteket . Az ilyen nyelveket néha párhuzam-orientált nyelvnek vagy párhuzam-orientált programozási nyelvnek (COPL) írják le.

Manapság a leggyakrabban használt programozási nyelvek, amelyek specifikus konstrukciókkal rendelkeznek a párhuzamosságra, a Java és a C# . Mindkét nyelv alapvetően megosztott memóriájú párhuzamossági modellt használ, a zárolást a monitorok biztosítják (bár az üzenettovábbító modelleket az alapul szolgáló megosztott memória modell tetején is meg lehet valósítani). Az üzenettovábbító párhuzamossági modellt használó nyelvek közül az Erlang jelenleg talán a legszélesebb körben használt az iparban.

Sok párhuzamos programozási nyelvet inkább kutatási nyelvként (pl. Pict ) fejlesztettek ki, nem pedig termelési célú nyelvként. Az olyan nyelvek, mint az Erlang , a Limbo és az occam azonban az elmúlt 20 évben különböző időpontokban voltak ipari használatban. A párhuzamos programozási lehetőségeket használó vagy biztosító nyelvek nem teljes listája:

Sok más nyelv támogatja a párhuzamosságot könyvtárak formájában, a fenti listával nagyjából összehasonlítható szinten.

Lásd még

Megjegyzések

Hivatkozások

Források

  • Patterson, David A .; Hennessy, John L. (2013). Számítógép -szervezés és -tervezés: A hardver/szoftver interfész . A Morgan Kaufmann sorozat a számítógépes építészetben és tervezésben (5 szerk.). Morgan Kaufmann. ISBN 978-0-12407886-4.

További irodalom

Külső linkek