Párhuzamosság megvalósítása Oberon rendszerben
Spiros Lalis és Beverly A. Sanders
Institut für Computersysteme
Swiss Federal Institute of Technology (ETH Zürich)
ETH Zentrum
CH-8092 Zürich
Switzerland
Kivonat. A Niklaus Wirth és Jürg Gutknecht által kifejlesztett Oberon rendszer különlegessége, hogy bár van benne "single process multitasking" vezérelt ablakkezelés, mégsem támogatja programok konkurens futattását. Ez a megközelítés egyszerű felépítést eredményez, és meglepően jól működik, de megvan a maga gyakorlati hátránya. Cikkünk ismertet egy tervezetet, a Konkurens Oberont, mely konkurens programozással egészíti ki az Oberon rendszert, miközben megtartja az eredeti egyszerűségét és szellemiségét.
Oberonnak hívják egyrészt a Niklaus Wirth által tervezett programozási nyelvet [RW92] és a Ceres munkaállomások [Ebe87] operációs rendszerét [WG92], melyet Wirth és Jürg Gutknecht alkotott.2 Mind a nyelv, amely támogatja az objektum orientált programozást, mind az operációs rendszer feltűnik a tervezés eleganciájával és a meglehetősen széleskörű felhasználhatósággal, kismértékű erőforráshasználat mellett.
A minden ablakhoz külön folyamatot és címtartományt rendelő rendszerekkel ellentétben az Oberonban "single process multitasking" van megvalósítva az Oberon ciklusnak nevezett folyamat segítségével. Minden ablakhoz illetve megjelenítő objektumhoz (viewer) tartozik egy dinamikusan létrehozott eljárás, amelyet (ablak)kezelőnek hívunk. A billentyűzet és egér állapotát az Oberon ciklus felváltva ellenőrzi, és amikor változást észlel, üzenetet küld a megfelelő megjelenítőnek. Az üzenetküldés a kezelő meghívásával történik, amely feldolgozza azt, majd visszaadja a vezérlést az Oberon ciklusnak.
A "programok" futtatásának szokásos módja az, hogy az ablakkezelő meghív egy parancsnak (command) nevezett speciális eljárást az üzenetkezelés közben. Például, ha az egér középső gombjával kattintunk rá egy parancs nevére egy megjelenítőben, akkor az megjelenítő objektum ablakkezelője meghívja a parancsot, mint eljárást. Amint a parancs végrehajtása befejeződött, az Oberon ciklus újra hozzálát a bemenet ellenőrzéséhez. Ennek a működésnek az a következménye, hogy minden parancs sekvenciálisan fut le a rendszerben, és a rendszer nem reagál bemeneti jelekre miközben egy parancsot hajt végre. Az egyszálú végrehajtás nagyban egyszerűsíti a rendszert, és gyorsítja a parancsok végrehajtását, mivel nincs veszteség, ami a szálak közti váltogatásból adódna (context switching). Továbbá nagyon jól működik interaktív alkalmazásoknál, hiszen a legtöbb esemény, mint például egy karakter kiírása gyakorlatilag azonnali és a leggyakrabban használt parancsok is rövid időt vesznek igénybe.
Vannak azonban esetek, amelyekben ez a fajta modell nem a legmegfelelőbb. Például, nem ésszerű nagy számításokat parancsként megvalósítani, mivel a végrehajtás felfüggeszti a rendszert amíg a parancs készen nem lesz, ami percekig vagy órákig is tarthat. Továbbá vannak olyan alkalmazások, amelyek külső eseményekre reagálnak (ld. hálózaton érkezik egy csomag), ahol az erőforrás időnkénti lekérdezése elfogadhatatlan megoldás.
Az ilyen alkalmazásokra adnak megoldást az Oberon rendszer taszkjai (task). A taszkok speciális eljárások, amelyeket az Oberon ciklus hív meg periódikusan. Más szóval a taszkok olyan parancsok, amelyek ismétlődően meghívódnak a háttérben, anélkül, hogy a felhasználó külön kérné azt.
Igaz ugyan, hogy néhány egyszerű alkalmazást így meg lehet valósítani, azonban ez sem megoldás a fent említett problémákra. A legnagyobb hibája az, hogy a taszk végrehajtása bármilyen nagy ideig késhet, más parancsok futása illetve a bemenet feldolgozása miatt. Lehetetlen emiatt garantálni, hogy egy taszk elkezdődik a megfelelő időben, ami elengedhetetlen olyan alkalmazásoknál, ahol időkorlátok vannak felállítva a részfeladatok közt; például kapcsolat orientált hálózati protokoloknál.
A másik probléma az, hogy a taszkok, mint a parancsok, addig futnak, amíg van mit végrehajtani, azaz felfüggesztik a rendszert a saját futásuk alatt. Annak érdekében, hogy megvalósítsuk a háttérben zajló feldolgozást, miközben a rendszer interaktív marad, a számításokat le kell bontani egymás után végrehajtandó taszk-hívásokra. Mivel a taszkok és az Oberon ciklus egy vermen osztozik, ezért ehhez minden esetben explicit módon el kell menteni a számítás állapotát, mielőtt visszaadjuk a vezérlést az Oberon ciklusnak [Rei91]. Az olyan programoknál amelyeket nem lehet leírni egyszerű autómatával, ez nagyon bonyolultá válhat; ilyenek például a rekurzív algoritmusok. A taszkok és az Oberon ciklus közti váltás explicit, ezért a taszkot úgy kell megírni, hogy ne legyen se "túl hosszú" se "túl rövid". Ha ez nem így van akkor vagy túl sokáig fogja a rendszert a taszk, vagy a váltásra megy el sok idő. Azon gondolkozni, hogy egy kódrészlet mennyi ideig fut majd, nem igazán tartozik bele abba, hogy a programozó hogyan akarja megoldani a feladatot. Az ilyen számítások idegesítőek, gépfüggőek vagy egyszerűen megoldhatatlanok, ha a futási idő függ a kódoláskor ismeretlen paraméterektől.
A mi taszkokkal szerzett tapasztalataink azt mutatták, hogy ezek a korlátok tényleg nagy gyakorlati fontosságúak, és ezért elhatároztuk, hogy kifejlesztjük az Oberon rendszer egy olyan változatát, amely mentes ezektől a problémáktól. További motivációt adott, hogy az Oberont, amelyet az összes kezdő számítástudományi kurzuson jelen van itt az ETH-n, felhasználjuk konkurens programozás gyakoroltatására. A célunk az volt, hogy egyszerű, átlátható eszközt adjunk a háttérben történő feldolgozás, események lekezelése és alacsony szintű szinkronizálás megvalósítására. Az utóbbi megengedné, hogy a párhuzamosság tanításában és kutatásában használt magasabb szintű technikákat könnyen implementáljuk. Fontos szempont volt az eredeti rendszer egyszerűségének és szellemiségének a lehető legjobb megőrzése.
Hogy elérjük a fenti célokat, megvalósítottuk az Oberon rendszer egy új változatát, amelyet Konkurens Oberonnak nevezünk. A Konkurens Oberon szálakat (könnyű folyamatokat) szolgáltat egy egyszerű priorításos ütemező mellett. A szálak eltárolják és elrejtik a számítás állapotát és lehetővé teszik, hogy a programozó átadja a vezérlést mást szálaknak, anélkül, hogy külön el kéne mentenie az állapotot. Az ütemező háromféle prioritást ismer. Az azonos prioritású szálak közt "round robin" ütemezés osztja el a processzort, ha nincs magasabb prioritású szál. Ez a megoldás gyors válaszidőket eredményez ott, ahol szükség van rá, és gyakorlatilag láthatatlanná teszi a háttérben futó szálakat a felhasználó felé. Az eredeti rendszerrel való kompatibilitás jegyében a taszkok továbbra is használhatóak.
A konkurencia bevezetése egy olyan rendszerbe, amelyet eredetileg szekvenciálisnak terveztek, érdekes mérnöki problémának bizonyult. Az Oberont áthatja a bonyolult globális adatszerkezetek használata, így egy figyelmetlen párhuzamosság implementáció katasztrofális hatással lenne. Nagy számú megosztott adatszerkezet van, amely nincs teljesen beágyazva, azaz nem csak eljárásokon keresztül módosítható, hanem a kliens eljárások közvetlenül változtathatják őket. Vegyük még ehhez hozzá, hogy sok Oberon alkalmazás úgy van megírva, hogy felteszi, hogy a műveletek sorban és atomian hajtódnak végre, azaz gyakran elvárják, hogy az absztrakt adattípus állapota ne változzon két művelet végrehajtása között. így a nyilvánvaló megoldás, azaz, hogy szinkronizáló műveleteket adunk egy absztrakt adattípushoz, nem elégséges.
Konkurens Obernonban van egy speciális "Oberon szál", amely megállapodás szerint felelős a billentyűzet és egér eseményeiért, a képernyőkezelésért és hogy kezelje a bemenethez és képernyőhöz tartozó magas szintű adatszerkezeteket. Az a döntés, hogy ezeket a dolgokat csak egyetlen szál végezze, kiküszöböli a legtöbb explicit szinkronizálást. új szálakat háttérben történő számítások elvégzésére lehet létrehozni és ezek csak felügyelt módon férhetnek hozzá a fenti közös erőforrásokhoz az Oberon szálon keresztül. Ez a megoldás megfelel az elvárásoknak, különösebb bonyolultság nélkül, és emellett gyakorlati szempontból is hasznos, mivel kompatibilis marad az eredeti Oberon rendszerrel. A már meglévő alkalmazások változtatás nélkül futnak a Konkurens Oberonban.
Lényeges következmény, hogy ebben a megközelítésben a párhuzamosság nem teljesen átlátszatlan. Azokat a programokat, amelyeket párhuzamosan akarunk futtatni, úgy kell megírni, hogy alkalmasak legyenek rá, főleg, mert szinkronizálniuk kell az Oberon szállal, ha megosztott erőforrásokat akarnak használni. Nem gondoljuk, hogy ez jelentős megkötés lenne, mivel egy tipikus háttérszámítás nem kommunikál sokat a felhasználóval és a szükséges szinkronizáció se túl bonyolult.3
Konkurens Oberonban a szálak egyetlen közös címtartományt foglalnak el. Minden modul csak egy példányban kerül betöltésre a memóriába. Ez azt jelenti, hogy a modul globális változói közösek a modul eljárásait futtató szálakban illetve az ezeket a változókat importáló modulokban. Kihatással van ez az olyan modulokra is amelyek eljárásait szálakból hívunk vagy amelyeknek az adatait konkurens módon használjuk.
A különböző szálak közti memória-védelem hiánya hibákhoz vezethetne, ha nem biztonságos nyelvet használnánk. Kisebb programozói hibák, főleg mutatókkal és tömbökkel kapcsolatban, könnyen a rendszer összeomlásához vezethetnének, mivel akaratlanul is módosíthatnák egy másik szál adatait. A mi esetünkben az Oberon nyelv szigorú típusellenőrzése lényegében garantálja, hogy az ilyen hibákat vagy már a fordító észleli vagy kivételt (trap) okoznak futás közben. Pontosabban a fordító és a futtató környezet garantálja, hogy egy mutató mindig a megfelelő típusú objektumra mutat, és amely benne van az éppen futó kód láthatósági körében; így küszöbölve ki az olyan, a rendszer összeomlásához vezető, hibákat, amelyek egy másik szál memóriájába írásból erednének. A mi rendszerünk továbbá észleli továbbá a verem túlcsordulást, és leállítja a hibás szálat.
A legnagyobb veszélyforrás a Konkurens Oberonban az, hogy egy szál nem szinkronizál megfelelően az Oberon szállal. A mi tapasztalataink azt mutatják, hogy ez nem komoly hiányosság, mivel a kritikus adatszerkezetek jól ismertek, és --mint azt a 3.6. fejezet leírja-- a szinkronizáció könnyen megoldható.
Ebben a fejezetben ismertetjük a Threads modult, amely bevezeti az új lehetőségeket a Konkurens Oberonba. A modul definiálja a szálak létrehozásához és törléséhez szükséges eljárásokat, valamint olyan műveleteket, amelyekkel tetszőleges szinkronizáló eszközök megvalósíthatóak (pl.: szemaforok, jelek (signals), monitorok, feltételek). Itt vannak az Oberon szállal történő szinkronizációhoz illetve kommunikációhoz szükséges eljárások, és néhány, a rendszerprogramok által használt, eljárás.
Szál leírónak (ThreadDesc) nevezzük azt a rekordot (objektumot), amely tartalmazza az ütemezőnek szükséges állapotleíró adatokat a szálról. Következik a definíció:
TYPE
Thread = POINTER TO ThreadDesc;
ThreadProc = PROCEDURE();
ThreadDesc = RECORD
state, priority: SHORTINT; (* csak olvasható *)
incNo: LONGINT; (* csak olvasható *)
END;
PROCEDURE Create (this: Thread; proc, trapproc: ThreadProc;
wsp: LONGINT);
PROCEDURE Destroy (this: Thread);
új szál létrehozásához a programozónak le kell foglalnia a memóriában NEW eljárással helyet a szál leírónak, majd meg kell hívnia a Create eljárást a következő paraméterekkel: proc, trapbody és wsp. A kívánt munkaterület (verem) méretét adhatjuk meg a wsp paraméterrel, míg a proc, trapproc eljárások rendre akkor hívódnak meg, amikor a szálat elindítjuk illetve kivétel lép föl. Az utóbbít föl lehet használni rendtevésre illetve a szál újraindítására. Ha a trapproc értéke NIL, akkor nem történik semmi. A Create lefoglalja a munkaterületet és beállítja a szál állapotát és prioritását (state, pritority) az alapértékekre, amelyek rendre a felfüggesztett (suspended) és alacsony (low). Ha egy újonnan lefoglalt szál leírót használtunk, akkor az incNo mező értéke 1 lesz; ha egy már használt leírót alkalmazunk, akkor a reinkarnáció számláló megnövekszik eggyel. Egy leíró nem használható fel újra, amíg a megfelelő szál le nem futott. A Destroy eljárás törli a szálat, és felszabadítja a lefoglalt erőforrásokat.
A Threads modul két csak olvasható változót exportál:
VAR cur, oberon: Thread;
Az oberon változó jelzi az Oberon szálat és a cur jelzi az éppen futó szálat. Az utóbbit az ütemező minden alaklommal frissíti, amikor a vezérlés átadásra kerül.
Szálat úgy lehet paraméterezni, hogy kihasználjuk az Oberon nyelv típusbővítési lehetőségét [RW92]. Létrehozhatunk új mezőket tartalmazó szál leíró típust, amelynek egyedeit használhatjuk a Create eljárás paraméterezésében. A szálak eljárásai használhatják ezeket az új mezőket az éppen futó szálban, a cur változóra alkalmazott típusőr mellett. Erre ad példát a 3.5. fejezet.
Az ütemező három eltérő prioritást ismer és csak akkor próbál ütemezni egy szálat, ha nem áll készen a futásra nála nagyobb prioritású szál. Elkerülendő, hogy egy szál éhenhaljon (azaz sose kerüljön sorra - a ford.) a szálaknak megfelelő prioritást kell adni, vagy megváltoztatni azt, amikor szükséges. Egy szál prioritását a szál leíró priority mezője adja meg és ezt a SetPriority függvény tudja megváltoztatni.
CONST
low = 0; norm = 1; high = 2;
PROCEDURE SetPriority (this: Thread; prio: SHORTINT);
A prioritás hangolására példa az Oberon szál, amely a bemeneti eseményeket normál prioritás mellett dolgozza fel, majd amikor nincs több esemény, akkor a prioritása alacsonyra vált, hogy engedje az alacsony prioritású szálakat is futni. Amikor viszont van billentyűzet vagy egér esemény, akkor a prioritása visszaállítódik normálisra. A magas (high) prioritást olyan szálaknak ajánlott fönntartani, amelyek az idő nagy részében fel vannak függesztve és valamilyen eseményre várnak, amit aztán gyorsan tudnak kezelni.
Az itt következő konstansok és eljárások vannak hatással egy szál futási állapotára, amelyet a szál leíró state mezője tartalmaz.
CONST ready = 0; asleep = 1; suspended = 2; destroyed = 3; trapped = 4; PROCEDURE Suspend; PROCEDURE Resume (this: Thread); PROCEDURE Pass; PROCEDURE Sleep (msecs: LONGINT);
Az a szál amelynek állapota futtatható (ready) az vagy éppen fut, vagy várja, hogy az ütemező kiadja neki a processzort. Az állapot felfüggesztett (suspended) értékre változik, ha kiadjuk a Suspend utasítást. Egy felfüggesztett szálat futtathatóvá lehet tenni, ha egy másik folyamat meghívja rá a Resume eljárást. A Create hívás után a szál állapota suspended, ezért meg kell rá hívni a Resume függvényt, hogy futtathatóvá tegyük. A Resume eljárás nem azt mondja, hogy ennek a szálnak kell rögtön futnia, hanem csak megváltoztatja az állapotot, hogy az ütemező kiválaszthassa. Sleep eljárással lehet egy szál állapotát alvóra (asleep) változtatni. Egy alvó szál akkor válik újra futtathatóvá, ha vagy Resume eljárás fölkelti, vagy lejár a megadott időkorlát. A destroyed illetve trapped állapot rendre azt jelzi, hogy egy szál törölve lett-e vagy kivétel miatt leállt. A Pass eljárás feladja a processzort, anélkül, hogy a szál futási állapotát megváltoztatná.
Annak érdekében, hogy magasabb szintű szinkronizációs alapműveletek is implementálhatóak legyenek, olyan alapműveleteket adunk, amelyekkel atomi részeket definiálhatunk a programban, azaz olyan utasítássorozatokat, amelyeket atomian kell végrehajtani.
PROCEDURE BeginAtomic; PROCEDURE EndAtomic;
BeginAtomic jelzi, hogy az aktuális szál futását nem szakíthatja meg az ütemező. EndAtomic törli ezt a jelzést. Azaz utasítássorozatok a BeginAtomic és EndAtomic között atomian fognak végrehajtódni.4 Helyesen egybeágyazott BeginAtomic-EndAtomic párok is megengedettek. Egy atomi kódrészleten belül a vezérlés átadható más szálnak a Suspend, Sleep és Pass eljárásokkal. Amikor a szál újra futásra kerül, akkor a kódrészlet további része atomi marad. Atomi kódrészleteket elsődlegesen magas szintű szinkronizáció megvalósítására vezettük be, nem általános szinkronizáló céllal. Az atomi végrehajtást önmagát, mint magas szintű elvet vezettük be. Ennek eredményeképp a Threads modul az végrehajtás-megszakítás (preemption) megvalósításától függetlenül implementálja a szinkronizáló műveleteket. Ez a megoldás más, mint az általában használt, amelynél a programozónak le kell tiltania a megszakításokat, ha atomi végrehajtást akar. Ekkor azonban minden megszakítás forrásra gondolnia kell, ami miatt sokáig tarthat a letiltás és ha újfajta megszakítás fölmerül, akkor az összes szinkronizáló utasítást újra kell írni. Az is előfordulhat, hogy a végrehajtás-megszakítás nem is megszakításokkal működik, hanem a fordító illeszt be a kód közé (a programozó által láthatatlanul) a processzort feladó utasításokat.
Ebben a fejezetben megadjuk az eddig tárgyalt eljárások formálisan definiált absztrakt implementációját. Legfontosabb ezek közül a futási állapotot változtató eljárások leírása, mert így pontosabban látszik szemantikájuk és lehetővé teszik a formális programhelyesség bizonyítást. Az absztrakt implementáció megadásához a [And91]-ben adott jelölésrendszert használjuk. Ez a jelölésrendszer egyfajta kiterjesztése Dijkstra jelölésrendszerének, és tartalmazza az await kifejezést szinkronizációhoz és a kacsacsőrök "<>" használatát az atomi parancsok, parancssorozatok jelölésére. Az [And91]-ben leírt bizonyítási lépések használhatóak formális helyességbizonyításhoz.
PROCEDURE Create (this: Thread; proc, trapproc: ThreadProc;
wsp: LONGINT);
<wsp méretű verem lefoglalva "and" this.state := suspended
"and" this.priority := low>
PROCEDURE Destroy (this: Thread);
<if
this.state < destroyed --> this.state := destroyed
else
this.state >= destroyed --> skip
fi>
PROCEDURE SetPriority (this: Thread; prio: SHORTINT);
<this.priority := prio>
PROCEDURE Suspend;
<th.state := suspended>;<await(th.state = ready)>
PROCEDURE Resume (this: Thread);
<if
this.state < destroyed --> this.state := ready
else
this.state >= destroyed --> skip
fi>
PROCEDURE Pass;
skip
PROCEDURE Sleep (msecs: LONGINT);
<t := Time; th.state := asleep>;
<await(Time >= t+msecs "or" th.state = ready) --> th.state := ready>
A fentiekben a t egy új lokális változója a szálnak, és th az (adott) neve az aktuális szálnak. A Time változó az aktuális rendszeridőre utal, amelyet csak az óra folyamat növel megfelelő időnként. Time-ot tartalmazó várakozási feltétel ezek után csak olyan lehet, amelyik nem változik át hamisra, ahogy az idő telik; például: Time >= n. Igazából nem bizonyítunk az idő értékével, hanem a Sleep-et úgy értjük, hogy igazzá válik véges idő után, ahol az adott időkorlát az ütemezőnek szóló segítség. Ekkor a paraméter értéke nem befolyásolja a helyességet, csak a hatékonyságot.
A BeginAtomic és EndAtomic eljárások megfelelnek a nyitó és záró kacsacsőröknek. Pass, Suspend illetve Sleep hívása BeginAtomic és EndAtomic között explicit módon föloldják az atomi végrehajtást, ami újrakezdődik a visszatéréskor és az EndAtomic utasításig tart. Más szóval BeginAtomic és EndAtomic közt megváltozik a Sleep és Suspend definíciója, úgy, hogy a kezdő "<" és az utolsó ">" kacsacsőr eltűnik. A Pass definíciója pedig "> skip <" lesz. Például: BeginAtomic S1; S2; Suspend; S3; S4; EndAtomic ekvivalens a következővel: < S1; S2; th.state := Suspended >;< await(th.state = ready); S3; S4>. Az utasítássorozat BeginAtomic S1; S2; Pass; S3; S4; EndAtomic pedig ekvivalens < S1; S2 >;< S3; S4> kifejezéssel.
A példa bemutatja a műveletek használatát, egy olyan szálon, amely egy változót növel minden T ezredmásodpercben (msec). A növekmény és a T értékét a szál változójaként adjuk át. Továbbá a szál normál prioritással fut majd, hogy bemenet kezelés közben is garantáltan lefusson.
TYPE
MyThread = POINTER TO MyThreadDesc;
(* MyThreadDesc a Threads.ThreadDesc kiterjesztése *)
MyThreadDesc = RECORD (Threads.ThreadDesc)
i, inc, T: LONGINT
END;
PROCEDURE Body;
BEGIN
(* Típusőr gondoskodik arról,
hogy az aktuális szál tényleg MyThread típusú legyen *)
WITH Threads.cur: MyThread DO
LOOP Threads.Sleep(Threads.cur.T);
INC(Threads.cur.i, Threads.cur.inc)
END;
END;
END Body;
PROCEDURE Start;
VAR t: MyThread;
BEGIN
(* Lefoglaljuk a leíró helyét, és kezdőértéket állítunk *)
NEW(t); t.inc := 100; t.i := 0; t.T := 50;
(* Munkaterület létrehozása és alapmezők beállítása *)
Threads.Create(t, Body, NIL, 128);
(* Prioritását megemeljük alacsonyról *)
Threads.SetPriority(t, Threads.norm);
(* állapot beállítása, hogy elkezdhessen futni *)
Threads.Resume(t);
END Start;
Annak érdekében, hogy egy szál együttműködjön az Oberon szállal -- például képernyőre íráskor -- olyan adatszerkezeteket kell módosítania, amelyeket az Oberon szál is használ. Ebben a fejezetben eljárások két csoportját ismertetjük, melyek lehetővé teszik, hogy egy szál szinkronizáljon az Oberon szállal, anélkül hogy az osztott adatszerkezetekben hiba lépne fel. Ezekkel az eljárásokkal megoldható, hogy ne kelljen a programban explicit módon szinkronizálni, ha az kizárólag az Oberon szálon belül fut. Az első módszer kölcsönös kizárást biztosít, a második pedig aszinkron üzenetküldést valósít meg az Oberon szál felé, ami aztán elvégzi a kért feladatot. Fájl műveleteknél nincs szükség explicit szinkronizációra, mert a rendszer automatikusan biztosítja a sorbarendezést.
Az Oberon szálhoz való szinkronizáció legegyszerűbb módja, ha a Threads modul által kezelt lakatot (lock) használjuk, melyet a következő eljárásokkal lehet megszerezni és elengedni:
PROCEDURE LockOberon; PROCEDURE UnlockOberon;
A lakatot kezdetben az Oberon szál tartja magánál, és parancsok (vagy taszkok) futatása közötti időben engedi el, aztán szerzi vissza. Ha egy szál kritikus adatokat akar módosítani, akkor a megfelelő utasítások előtt meg kell hívni a LockOberon eljárást, utánuk pedig az UnlockOberon-t, hogy elengedje a lakatot. LockOberon felfüggeszti az aktuális szálat, ha a lakat egy másik szálnál van. Nagy valószínűséggel előfordulhat kényszerű várakozás a lakatra, mivel azt az Oberon szál magánál tartja amikor parancsokat vagy taszkokat futat. Megengedet ezen utasítások egymásba ágyazása, így lehetséges olyan parancsokat futatni az Oberon szálban vagy más háttérfolyamatban, mely tartalmazza őket.
Például, ha úgy szeretnénk módosítani a 3.4. fejezetben adott szálat, hogy a változó növekedését a rendszer naplóba beírja, akkor így tehetjük meg:
PROCEDURE Body1;
VAR W: Texts.Writer;
BEGIN
WITH Threads.cur: MyThread DO
Texts.OpenWriter(W); (* kiíró létrehozása *)
LOOP
Threads.Sleep(Threads.cur.T);
INC(Threads.cur.i, Threads.cur.inc);
(* beírjuk a bufferbe az értéket *)
Texts.WriteString(W, "i = ");
Texts.WriteInt(W, Threads.cur.i, 0);
(* a rendszer naplóban megmutatjuk *)
Threads.LockOberon;
Texts.Append(Oberon.Log, W.buf);
Threads.UnlockOberon
END
END
END Body1;
A fenti példában a W egy lokális Texts.Writer típusú változó, mely egy buffert tartalmaz, amibe beírjuk amit meg kívánunk jeleníteni. A Text.Append(Oberon.Log,W.buf) parancs hozzáfűzi a buffer tartalmát a rendszer naplóhoz. A rendszer napló általában képernyőn látszik egy megjelenítőben.
Adatok képernyőre írására illetve az Oberon szállal közös adatszerkezetek módosítására egy másik megközelítés az aszinkron üzenetküldés használata. Ez a technika több erőfeszítést igényel az implementálás során, mint a LockOberon és UnlockOberon használata, de alkalmasabb olyan esetekben, ahol fontos, hogy a kimenetet várakozás nélkül tudjuk produkálni (pl.: hálózatfigyelésnél, vagy egy kivételkezelőben).
TYPE
OberonAction = POINTER TO OberonActionDesc;
OberonActionProc = PROCEDURE (this: OberonAction);
OberonActionDesc = RECORD
body: OberonActionProc
END;
PROCEDURE QueueOberonAction (this: OberonAction);
PROCEDURE DoOberonActions;
Az alapötlet az, hogy az olyan eljárásokat, melyek az Oberon szállal közös adatszerkezeteket használnak, berakjuk egy várakozási sorba, melyet maga az Oberon szál dolgoz föl. Az DoOberonActions eljárás nem azért van, hogy a programozó meghívja, ezt az Oberon szál megteszi magától. Amikor meghívódik, feldolgozza a sorban lévő összes OberonAction-t, úgy hogy meghívja a benne tárolt OberonActionDesc rekordok body eljárását, a megfelelő OberonAction mutatóval, mint paraméterrel. Hasonlóan a szálak paraméterezéséhez, itt is át lehet adni adatokat, ha kiterjesztjük az OberonActionDesc típust új mezőkkel.
Az előző példa módosításával megmutatjuk, hogy hogyan lehet ezeket az akciókat (action) felhasználni az zárolás elkerülésére.
TYPE
MyAction = POINTER TO MyActionDesc;
MyActionDesc = RECORD (Threads.OberonActionDesc)
i: LONGINT
END;
VAR W: Texts.Writer;
PROCEDURE ActionBody (this: Threads.OberonAction);
BEGIN
WITH this: MyAction DO
Texts.WriteString(W, "i = ");
Texts.WriteInt(W, this.i, 0);
Texts.WriteLn(W);
Texts.Append(Oberon.Log, W.buf)
END
END ActionBody;
PROCEDURE Body2;
VAR a: MyAction;
BEGIN
WITH Threads.cur: MyThread DO
LOOP
Threads.Sleep(Threads.cur.T);
INC(Threads.cur.i);
(* akció létrehozása *)
NEW(a); a.i := Threads.cur.i; a.body := ActionBody;
(* berakjuk a sorba *)
Threads.QueueOberonAction(a);
END
END
END Body2;
A Threads modul sok olyan eljárást exportál, melyet a más rendszermodulok használnak (pl.: Input, System), a végrehajtás-megszakítás és kivételkezelés megvalósítására. Bár nem általános használatra készültek, benne vannak a modul definíciójában, ezért röviden leírjuk őket a teljesség kedvéért.
PROCEDURE Tick (ticks: LONGINT); PROCEDURE Enumerate (proc: ThreadProc); PROCEDURE StackState (this: Thread; VAR fp, pc: LONGINT);
A Tick eljárást a belső időzítő megszakítás-kezelő használja, hogy növelje a rendszeridőt. Az Enumerate végrehajt valamilyen eljárást az összes szálra. StackState visszaadja egy szál utolsó elmentett állapotát, vagyis az aktivációs rekord frame pointerét és a legutóbbi utasítás címét. Az aktuális szálra kiadva, a visszaadott értékeknek nincs jelentése. Ezeket az eljárásokat a következő parancsok használják: System.ShowThreads, System.DumpThread, System.DestroyThread és System.DestroyAllThreads, melyek információt adnak a szálakról és felügyelő funkciókat a felhasználónak.
A Threads modul következő eljárásait szabad meghívni megszakítás-kezelőből: Resume, SetPriority, Pass és Destroy.5
A System modul kiterjesztésre került három új paranccsal, melyekkel a felhasználó figyelni és törölni tudja a szálakat, interaktív parancsok segítségével.
PROCEDURE ShowThreads; PROCEDURE DumpThread; PROCEDURE DestroyThread; PROCEDURE DestroyAllThreads;
A ShowThreads parancs megnyit egy megjelenítőt, mely tartalmazza az összes futó szálat. Minden szálhoz ott van egy egyedi azonosító, a kezdőeljárás neve és a futási állapot. A DumpThread parancs is megnyit egy megjelenítőt, melyben a kiválasztott szál veremállapota látható, míg a DestroyThread parancs törli a kiválasztott szálat. Minkét esetben a kiválasztás a szál azonosítója alapján történik. A DestroyAllThreads parancs kitörli az összes szálat kivéve az Oberon szálat. Az utóbbit ajánlott a rendszer leállítása előtt kiadni, hogy elkerülendő a fájl rendszerben esetleg keletkező hibákat.
Az új rendszer szerkezete az ábrán látható. Az eredeti rendszer azon moduljai, melyek nem látszanak az ábrán, nem kerültek módosításra a Konkurens Oberonban.
(Jelmagyarázat: A dobozokba írt nevek modulokat jelölnek. Továbbá, protection: védelem, trap handling: kivételkezelés, synchronization: szinkronizáció, scheduling: ütemezés, preemption: végrehajtás-megszakítás, coroutine primitives: korutin alapműveletek.)
Az ütemezési stratégia tervezésének szempontjai: azonos prioritású szálak közt megosztani a processzort, a háttérfolyamatok láthatatlansága a felhasználó felé és garantáltan gyors reagálás bizonyos eseményekre. A végrehajtás-megszakítás eszköze az ütemező meghívása egy megszakítás-kezelőből, felhasználva a Threads.Pass eljárást. Az időzítő megszakítás-kezelő az Input modulban rendszeresen meghívja ezt az eljárást, hogy a futatható szálakat round-robin módon ütemezze.
Az Oberon szál prioritása átáll normálisra és az ütemező meghívásra kerül, ha billentyűzet vagy egér esemény tűnik fel. Az egér eseményeit az időzítő megszakítás az egér állapotának lekérdezésével veszi észre. A billentyűzet eseményei automatikusan megszakítást váltanak ki, melyeket szintén az Input modul kezel. Ha az összes bemeneti esemény feldolgozásra került, akkor az Oberon szál prioritása visszaáll alacsonyra, esélyt adva így az alacsonyabb prioritású szálak futására. Ezzel a megoldással a háttérben futó szálak kihasználhatják azt az időt, amikor nem kell az interaktivitást biztosítani, de mégsem befolyásolják az interaktiv rendszer válaszidejét. Az Oberon szál szerkezete a következő:
(* A lakat (lock) már megvan *)
LOOP
WHILE **billentyűzet vagy egér esemény**
DO
**esemény kezelése**
**következő taszk futtatása**
Threads.DoOberonActions;
END;
Threads.SetPriority(Threads.oberon, low);
Threads.UnlockOberon;
Threads.Pass;
Threads.LockOberon;
END;
Az eredeti Oberon rendszerben, ha futási hiba lépett fel, akkor a kivételkezelő kinyitott egy megjelenítőt benne a megszakadt eljárás veremállapotával. Konkurens Oberonban a kivételkezelő a Threads modulban van megvalósítva és aszinkron kommunikáció használatával az Oberon szálon keresztül jelenít meg információkat a kivételről. Egy speciális OberonAcion van definiálva, mely megnyit egy megjelenítőt és kiírja a verem tartalmát. Ha futási hiba lép fel, akkor létrejön egy új akció, kitöltődnek a mezői a rendszermag (kernel) által adott információ alapján, majd a QueueOberonAction eljárás meghívásával beáll a sorba, és a processzort feladja egy futatható szálnak. A kivétel megjelenítése egy későbbi időpontban következik be, amikor az Oberon szál feldolgozza a sorban álló OberonAction-t.
A Kernel modul kiterjesztésre került oly módon, hogy egyszerű korutinokat [Wir83] támogasson, és ezáltal megteremtse a párhuzamosság megvalósításának alapjait a rendszerben. A Threads modul felhasználja ezeket a rutinokat, hogy implementálja a kívánt ütemezési algoritmust.
TYPE
Stack = POINTER TO StackDesc;
StackDesc = RECORD
status: SHORTINT;
inSVC: BOOLEAN;
END;
PROCEDURE NewStack (VAR stack: Stack; wsp: LONGINT);
PROCEDURE InitStack (stk: Stack; proc: PROCEDURE);
PROCEDURE Transfer (stk: Stack);
PROCEDURE Current (VAR cur: Stack);
PROCEDURE StackState (this: Stack; Var fp, pc: LONGINT);
A NewStack eljárás lefoglal egy wsp méretű vermet és visszaad egy ide mutató pointert. A szemétgyűjtő felszabadítja a verem által foglalt memóriát, amint megszűnik minden hivatkozás a veremre. Egy vermen való futatás előkészítéséhez meg kell hívni az InitStack-et a veremre és az eljárásra, mint paraméterekre. A végrehajtás akkor kezdődik meg, amikor a vezérlés először kerül az előkészítet veremre. A vezérlésátadást valósítja meg a Transfer eljárás, mely figyelembe veszi az aktuális végrehajtás állapotát. Ezeket az információkat a status és inSVC mezők tárolják. A status azt mondja meg, hogy a végrehajtás éppen normál, kivétel vagy megszakítás módban van-e. Az utóbbi esetben az inSVC mező mondja meg, hogy éppen rendszer-felügyelő (supervisor) eljárás lett-e megszakítva. Az aktuális végrehajtás vermét adja vissza a Current eljárás. Végül a StackState eljárással lehet lekérdezni az állapotát egy vermen történő futatásnak. Az aktuális veremre kiadva a visszakapott értéknek nincs értelme. Ebben a verzióban ezeknek az eljárásoknak a megvalósítása rendszer-felügyelő módban történt, ami megengedte, hogy úgy terjesszük ki a Kernel modult, hogy a szimbólum fájlt nem kellett megváltoztatni. Erre azért volt szükség, mert ellenkező esetben minden ezt a modult használó kliensprogramot újra kellett volna fordítani.6
A File modulban történő szinkronizáció megvalósításához két eljárás típusú változót definiálunk:
VAR lock, unlock: PROCEDURE;
Kezdetben ezeknek üres az értéke, és később a Threads modul tölti ki őket igazi szinkronizáló alapműveletekkel (értsd BeginAtomic és EndAtomic). Ezzel a közvetett módszerrel lehetett a Threads modult magasabb szintre helyezni az Oberon hierarchiában, vagyis a "belső magon" kívülre ("inner core").
További módosítás a Kernel modulban az, hogy a szemétgyűjtő minden vermen megjelöli a mutatókat. Az eredeti rendszerben csak egy verem volt -- amelyiken az Oberon ciklus működik --, és a szemétgyűjtő csak parancsok hívása közt került aktiválásra, amikor a verem garantáltan üres volt. Nyilvánvaló, hogy Konkurens Oberonban soha sem lehet garantálni, hogy minden verem egyszerre üres, ezért egy bonyolultabb algoritmus szükséges.
Konkurens Oberon régebbi verzióiban a verem memóriák külön memórialapokra kerültek és a processzor beépített védelmét használva figyeltük a veremtúlcsordulást. Ebben a verzióban a vermeket a heap memóriában foglaljuk le, mint bármi mást is, és ezért a szemétgyűjtő automatikusan figyeli őket. Az Oberon fordító egy módosított változatát használjuk, mely minden eljáráshíváshoz veremtúlcsordulást figyelő kódot is fordít. Ezzel lehetővé válik a Konkurens Oberon implementációja olyan hardverre is, melyben nincs beépített memóriavédelem (pl.: Ceres-3 munkaállomások), azon az áron, hogy az eljáráshívás kicsit költségesebb lett.
Az eredeti Oberon rendszer nem támogatta a Konkurens programozást. Szerintünk igaz ugyan, hogy nincs szükség párhuzamosságra egy interaktív, ablakozós rendszerben, de ettől függetlenül kívánatos, hogy támogassa a rendszer. Azzal hogy létrehoztuk a Konkurens Oberon rendszert megmutattuk, hogy jelentős méret- és bonyolultság-növekedés nélkül bevezethető. Mivel az eredeti programozási felület nem változott, vagy legfeljebb kiterjesztésre került, az Oberon ciklus szemantikája nem változott, így a Konkurens Oberon kompatibilis az eredeti rendszerrel és a programok változtatás nélkül futnak rajta. A Konkurens Oberont sikeresen használták fel eleddig: egy osztott programozást kutató témában [Lal94], számos doktori dolgozatban (köztük az egyik a TCP/IP hálózati kommunikációs protokoll implementációja [Ste92], mely jelentősen megnöveli a rendszer kapcsolatát a külvilággal), és osztott rendszerek valamint párhuzamos programozás gyakorlati tanításában.
Szeretnénk megköszönni Nilaus Wirth Professzornak, hogy megosztotta velünk az Oberon rendszer forrását, mellyel lehetővé tette ennek a programnak a létrejöttét, valamint azért, hogy módosította az Oberon fordítót a verem túlcsordulás figyelésére. Hanspeter Mössenböck, Martin Gitsels Professzorok és az Institut für Computersysteme további munkatársainak hasznos hozzászólásait a cikk korai változataihoz. Végül szeretnénk köszönetet mondani Philipp Heubergernek és Martin Gitselsnek, a Konkurens Oberon kipróbálásáért és értékes visszajelzéseikért a program fejlesztése alatt.
[And91] Gregory R. Andrews. Concurrent Programming: Principles and Practice. Benjamin/Cummings Publishing Company, 1991.
[Ebe87] Hans Eberle. Development and Analysis of a Workstation Computer. PhD thesis, Swiss Federal Institute of Technology (ETH Zürich), 1987. Number 8431.
[Lal94] Spiros Lalis. Distributed Object-Orinted Programming in a Network of Personal Workstations. PhD thesis, Swiss Federal Institute of Technology (ETH Zürich), 1994. In preparation.
[Rei91] Martin Reiser. The Oberon System: User Guide and Programmer's Manual. ACM Press, Addison-Wesley, 1991.
[RW92] Martin Reiser and Niklaus Wirth. Programming in Oberon: Steps Beyond Pascal and Modula. ACM Press, Addison-Wesley, 1992.
[Ste92] Michael Steiner. TCP/IP für Ceres. ETH Informatik Diplomarbeit (Senior Thesis), 1992.
[WG92] Niklaus Wirth and Jürg Gutnecht. Project Oberon : The Design of an Operating System and Compiler. ACM Press, Addison-Wesley, 1992.
[Wir83] Niklaus Wirth. Programming in Modula 2. Springer Verlag, 1983.
Fordította Krajcsovits György, 2001.IV.16.
Ez nem tükörfordítás. A fordító semmiféle felelőséget nem vállal a
benne foglaltak helyességéért. Mindeki saját felelőségére használja.
Translator: George Krajcsovits, 16th April 2001.
Should not be considered as word-for-word translation. The translator
does not accept any responsibility for the rightness therein.
Use at your on risk.