|  | ||||||||
|  | ||||||||
| | ||||||||
| | ||||||||
 |
kategória |  |
||||||||
|
|
||||||||||
 |
 |
|
|
|
|
|
||
|
|
Programok párhuzamos futtatásának elve, feltételei.
A párhuzamos programfutás olyan programrészek (látszólag) egyidejű, "átlapolt" végrehajtását jelenti, amelyek közös feladatot oldanak meg, ezért egymástól nem függetlenek. Vele szemben a multiprogramozás teljesen független programrészek átlapolt végrehajtását jelenti; amit elsősorban oprdsz-ek használnak, az erőforrások jobb kihasználása végett (CPU és B/K igényes feladatok váltogatott végrehajtásakor).
A párhuzamos végrehajtás fogalmának pontosabb jelentése: nem sorrendi, műveleti sorrendiséget nem kívánó. Az adatfeldolgozás eredménye nem változna, ha a párhuzamos utasítás-csoportokat a processzor(ok) eltérő sorrendben hajtaná(k) végre. Természetesen nem minden feladat párhuzamosítható.
Ha tehát párhuzamosított programrészeket újra futtatunk, megváltozhat a műveletek végrehajtási sorrendje; az sem biztos, hogy a programozó által elkövetett hibák megismétlődnek. Emiatt a párhuzamos programozás során bonyolult hibakeresésre kell felkészülni; ráadásul a párhuzamos programozást támogató programnyelvek erősen gépfüggőek.
Szálak: az egyetlen processzoron végrehajtandó - vagyis a nem párhuzamosítható - utasításcsoportokat elemi utasításfonalnak, szálnak nevezik (thread). Egy-egy ilyen szál pl. előállíthat más és más perifériára kimenő adatokat, vagy feldolgozhat más és más forrásból származó adatokat. Természetes tehát, hogy a szálak végrehajtásának sorrendje nem befolyásolja a végeredményt. A szálon belül azonban az utasítások végrehajtási sorrendje meg van szabva.
Programok szinkronizációja, és ezek típusai.
Szimultán adatfeldolgozás (együttes, adatpárhuzamos feldolgozás): közös programot futtat több processzor, egymással összehangoltan (szinkronban), de eltérő adatokkal.
Az ilyen, általában SIMD elvű számítógépben minden processzor külön helyi (privát) tárrészben tartja saját adatait és közös tárrészben az utasításokat.
Egy szimultán adatfeldolgozás célja a sebesség növelése, az egyprocesszoros feldolgozáshoz képest.
Konkurrens adatfeldolgozás (vetélkedő, multiprocesszoros, funkcionálisan párhuzamos feldolgozás): eltérő feladatú részprogramokat futtat több processzor (aszinkron módon, de párhuzamosan). Bár a feldolgozott adatok eltérők, a processzorok közös erőforrásért versengenek (pl. puffer-területért).
Az ilyen, MIMD elvű számítógépekben mind az adatok, mind az utasítások elkülönített tárhelyekben vannak.
A konkurrens adatfeldolgozás célja a részprogramok közti együttműködés megvalósítása. Ez különösen hasznos a gyártási folyamatokat irányító számítógépekben, vagy a termelést és a fogyasztást elemző-szimuláló közgazdasági számításokban.
Folyamatok szinkronizációja alatt a folyamatok szinkron soros, vagy szinkron párhuzamos ütemezését értjük.
A szinkronizáció célja egy vagy több folyamat utasításcsoportjainak, programrészeinek időzített végrehajtása. Olyan folyamatokról van szó, amelyek közös objektumon osztoznak (pl. szignálkezelő eljáráson), ugyanattól az erőforrástól várnak megszakításkérést, vagy szignált. Emiatt kölcsönösen hatniuk kell egymásra, jelzéseket kell küldeniük és fogadniuk: kommunikálniuk kell.
Folyamatközi kommunikáció (IPC = InterProcess Communication): az IPC-nek két fő módja van. A partnerfolyamatok mindkettőben a saját PID-jukkal azonosítják magukat.
szorosan csatolt rendszerben közös tárrészt használnak: változókat, szemafort, osztott adatszegmenst.
lazán csatolt rendszerben IPC-re az oprdsz által továbbított üzeneteket kell használni. Az üzenetek csak közvetve, egy "postafiókon" keresztül jutnak el a címzett folyamathoz.
A SZINKRONIZÁCIÓ TÍPUSAI
A szinkronizációnak 3 fő típusa van. Az első kettő szinkron soros, a harmadik szinkron párhuzamos ütemezéssel valósítható meg.
Kölcsönös kizárás: a kölcsönös kizáráson alapuló szinkronizációra van szükség a leggyakrabban: pl. akkor, amikor egy soros elérésű perifériát (pl. nyomtatót) több folyamat is használni kíván.
Lényege a nevében van: amikor az egyik folyamat fut, akkor a másik nem futhat és fordítva.
A kölcsönös kizárás fogalmának leggyakoribb értelmezése az, hogy bizonyos programrészeket (folyamatokat) csak egymás után szabad beütemezni, egyidőben csakis egyiküket. Végrehajtásuk sorrendje azonban nincs megszabva, többféle lehet.
Precedencia: ez a sorrendi típusú szinkronizáció pl. akkor fordul elő, amikor másolni kell egy állományt: előtte kell befejeztetni minden író-olvasó folyamatot.
Precedencia során tehát bizonyos programrészeket (folyamatokat) - hasonlóan a kölcsönös kizáráshoz- csakis egymás után szabad beütemezni, sőt, még a végrehajtásuk sorrendjét is meg kell szabni.
Randevú: az egyidejű típusú szinkronizáció fordul elő pl. akkor, amikor egy folyamat olvasni szeretne egy közös tárrészből (adatszegmensből, pufferből), de az üres, mert egy másik folyamat még nem termelt bele adatot.
Megfordítva, a termelő folyamat készen állna arra, hogy írjon a közös tárrészbe, de az éppen teli van, mert a fogyasztó folyamat még nem igényelt ki belőle egy korábban beleírt adatot.
A randevú közvetlen kommunikációt jelent a résztvevő folyamatok között. Szinkron párhuzamos ütemezéssel valósítható meg.
Lényege, hogy a kommunikáló folyamatok bizonyos programrészei bevárják egymást: arra várnak, hogy a folytatáshoz adatot kapjanak a másik programrésztől. Az adatszolgáltatás előtt és után azonban a folyamatok felváltva, tetszőleges sorrendben, párhuzamosan is futhatnak.
A kritikus szakasz.
A közös erőforrásra hivatkozó utasításcsoportok, kódszegmensek neve kritikus szakasz (kritikus szekció).
Konkurrens folyamatoknak -erőforrásigényeik egyeztetése céljából- értesíteniük kell egymást arról, hogy valamelyikük belépett-e már egy kritikus szakaszba, vagy éppen belépni készül oda. Emiatt a szinkronizáció úgy tekinthető, mint a folyamatközi kommunikáció (IPC) speciális esete. Ha ugyanis az utasítás-csoportok között nem lehetne biztosítani a kritikus szakasz programkódjával szemben támasztott követelményeket:
Kölcsönös kizárás: a kritikus programrészek egyidejű végrehajtása nemcsak a kölcsönös kizáráson alapuló szinkronizáció során tilos, de a precedencia és a randevú típusú szinkronizálás esetén sem engedhető meg.
Véges időn belüli beléptetés: ezzel a követelménnyel a következőket lehet elérni:
a. "előrehaladást" a legelső igénylő folyamat számára, ha a kritikus szakasz üres (még nem lépett be egyetlen folyamat sem).
b. az "éhezés" elkerülését (mind az író, mind az olvasó folyamatok számára), ha nem üres a kritikus szakasz.
c. a "holtpont" elkerülését, amit pl. az idézhet elő, hogy egy nagy prioritású folyamat futása kedvéért az ütemező feltartóztat egy kisebb prioritású folyamatot; ha viszont ez utóbbi korábban már belépett a kritikus szakaszba, akkor a nagyobb prioritású folyamat hasztalan várná, hogy ő is beléphessen oda.
Korlátozott számú ismételt beléptetés: ez a követelmény a további igénylők érdekét szolgálja, hiszen köztük lehetnek kisebb prioritásúak is, mint az első belépő prioritása. Emiatt ennek a követelménynek a teljesítése programozástechnikailag igen nehéz.
Hibamentesség: tranzakciók -pl. távoli helyfoglalások- rendszerösszeomlás utáni helyreállításához a kritikus szakaszba lépés előtt menteni kell az osztott változók értékeit.
Szemaforok és alkalmazásuk lehetőségei.
Információ-feldolgozás: számítógépes erőforrásoknak nevezünk minden olyan SW-elemet és programozható HW-eszközt, amely adatfeldolgozásban vesz részt, információ-átalakításhoz szükséges.
Az oprdsz is adatfeldolgozást végez; számára ugyanis egy folyamat indítása, futtatása, megállítása jelenti az adatfeldolgozást.
A Neumann-elvű számítógépek oprdsz-e minden folyamatot adatnak tekint: megkülönbözteti az alkalmazói- és rendszerfolyamatok kód-, adat- és veremterületét, létrehozza és mozgatja őket a memóriában, sőt, megjeleníti őket a CPU számára, amikor átadja nekik a vezérlést.
Ütemezés: a vezérlés átadása előtt a rendszerSW az, amelynek garantálnia kell az igényelt erőforrások használatát az adatfeldolgozó folyamat számára.
Minden folyamatnak valamilyen vezérlési elv által megszabott ütemben , sorrendben kell futnia.
Az oprdsz-nek is van beépített vezérlési elve: a folyamatok erőforrásigénye. Minthogy az erőforrások végesek, a folyamatoknak versengeniük kell egymással, és egy rendszerSW-re van szükségük, hogy az eldöntse, melyiküknek biztosítson erőforrást és meddig. Az oprdsz ütemezője a többi folyamatot addig sorba állítja és várakoztatja.
Osztott és osztatlan erőforrások: egy osztott erőforrás gyakorlatilag párhuzamosan érhető el: különféle részeit több folyamat használhatja, szinte egyszerre vagy felváltva. Ilyen pl. a CPU (többprocesszoros rendszerben), a memória, egy több felhasználó által osztott olvasásra megnyitott állomány, a mágneslemezek, vagy egy ablakrendszerű képernyő.
Ezzel szemben egyszerre mindig csak egy folyamat számára érhető el, ezért osztatlan erőforrás pl. a CPU (egyprocesszoros rendszerben) és általában soros elérésű perifériák: a nyomtató, a mágnesszalag, a terminál, vagy az aktív alkalmazásablak egy ablakrendszerű képernyőn (ez utóbbit csak az előtérfolyamat használhatja). Osztatlan erőforrás egy sín topológiájú helyi hálózat koax kábele is.
SZEMAFOROK ALKALMAZÁSÁNAK MÓDJAI
Oszthatatlan műveletek: szorosan csatolt folyamatok -pl. kódmegosztásos szülő-, gyermek- vagy testvérfolyamatok- un. oszthatatlan művelettel módosíthatnak egy közös adatot, melynek változótípusa a programnyelvbe épített szemafor. Ha ez a változó hozzá van rendelve egy kritikus szakaszhoz, akkor a neve privát szemafor.
A kritikus szakaszt a szemafor vasúti vágánynak tekinti, amelyre különféle irányokból közeledhetnek vonatok (folyamatok), de egyszerre csak egyiküket szabad beengedni a kritikus szakaszba. Minden folyamatnak a szemafor módosításával kell jeleznie
belépési szándékát (még a kritikus szakasz végrehajtása előtt): a szemaforokat kezelő egyik rendszerrutinban, az un. monitorban pl. ezt segíti a wait (PID-várólista) nevű oszthatatlan művelet (rendszerhívás)
kilépését a kritikus szakaszból; ezt segíti pl. a signal(várólista) nevű oszthatatlan művelet (rendszerhívás).
Oszthatatlan művelet az olyan utasítás-sorozat vagy gépi kódú utasítás, melynek eredményét nem befolyásolja, ha végrehajtása közben az ütemezőnek még munkaváltást is végre kell hajtania. Pl. az Intel 80486 összes LOCK prefixű utasítása oszthatatlan, hiszen lefoglalja a rendszersínt. Egyetlen gépi kódú utasítás használata azonban nem elég ahhoz, hogy korlátozható legyen az ismételt beléptetések száma.
A szemafor definíciója: a szemafor az oprdsz globális változója, a kritikus szakasz kezelésének eszköze, a folyamatok szinkronizálásának régi, struktúrálatlan, de legáltalánosabb módszere. 3-féle típusa van:
logikai (másnéven bináris): ilyen pl. az Intel 80486 bináris szemafortáblát vizsgáló utasítása a BTS (Bit Test and Set) vagy a BSR (Bit Scan Reserve)
integer (másnéven számláló): ilyen típusú szemafor számlálja egy olvasó folyamat számára az adatpuffer telítettségét, vagy egy író folyamat számára a puffer üres helyeit
összetett (record vagy queue típusú, másnéven várólistás)
Szemafort létrehozni a UNIX-ban pl. a semget() rendszerhívással lehet.
Oszthatatlan szemaforműveletek: a szemafornak, mint változónak midig van kezdőértéke, és csak két oszthatatlan művelet végezhető vele. A szabályos kezdőértékadást a szülőfolyamatnak kell végrehajtania, pl. a következőképpen:
While (Szem <>kezdő) Do
If (Szem<>kezdő) Then V(Szem) Else P(Szem);
A kritikus szakaszba történő belépés előtt meghívandó az un. P() eljárás. Ennek a primitívként lefutó rendszerhívásnak a lényege a következő:
Procedure P(var S:integer); angolul wait
Begin
While (S>=0) Do aktív üresjárat
Dec(S);
End;
A P() eljárás aktív üresjáratát (busy-waiting, livelock) ki kell küszöbölni, hogy ne sajátíthassa ki a CPU-t. Ennek érdekében a hívó folyamatnak összetett szemafort kell igényelnie és a P()-nek kérnie kell a saját -és a hívó- feltartóztatását. Ennek érdekében egy recordban közölnie kell a hívó folyamat PID-ját is, a szemafor azonosítója mellett. A PID ezzel felkerül az összetett szemafor várólistájára.
A kritikus szakasz elhagyását jelző V() eljárás lényege a következő:
Procedure V(var S:integer) angolul signal()
Begin
Inc(S);
End;
A V() eljárás szabad jelzésűre állítja a szemafort, a kritikus szakaszhoz érkező többi folyamat számára. Várólistás szemafor esetén a V()-nek még ki kell választania a várólistára került folyamatok (PID-jai) közül azt, amelyiket majd az ütemezőnek futásra kész állapotba kell hoznia.
A konkurrens programvégrehajtás kezdetét a C nyelvekben a fork kulcsszó (szétágazás rendszerhívás) jelzi, a konkurrens programvégrehajtás végét padig a join (csatlakozás), ill. a wait (veszteglés).
A fork()
rendszerhívás visszatérési értéke a szülőben létrehozott gyermekfolyamat
PID-ja, a gyermekben viszont
Konkurrens Pascal-ban a Dijkstrától eredő parbegin és parend kulcsszavak között kell felsorolni a párhuzamosítandó utasításokat (külön szálnak számít minden begin-end közé írt utasításcsoport).
Erőforrások védelme, módszerei.
Az állományműveletek korlátozása nagyban függ az oprdsz-től.
Osztatlan perifériák lefoglalása: egy osztatlan periféria használatba vételét jelezni kell a többi igénylő folyamatnak is. Erre szolgál többek között egy perifériához rendelhető rendszerváltozó, az un. szemafor. Ennek kezdőértékét az adott periféria lefoglalása/felszabadítása esetén az oprdsz eggyel növeli/csökkenti. Ha az eredmény 0, akkor az osztatlan periféria szabad, egyébként a szemafor számlálhatja foglalási igényeket, amiket a különféle folyamatok jelentettek be. Sürgősségük szerint ezeket az ütemező sorba is állíthatja. Ilyenkor jó, ha az oprdsz automatikusan tudja változtatni a folyamatok prioritását, nehogy a szemafornál való várakoztatásuk a végtelenségig tartson, kiéheztetéssé fajuljon.
:
2841
