Párhuzamos programok szintézise

Előszó

Ez a módszertani anyag a párhuzamos program szintézisének
egy lehetséges "mechanikus" módszerét mutatja be. Az első
részben magát a módszer ismertetjük, röviden kitérve a
legfontosabb szükséges párhuzamossággal kapcsolatos
alapfogalmakra is. A második rész néhány konkrét feladatot
dolgoz föl, amelyből pontosan kiderülnek a módszer
"finomságai", legapróbb részletei. Igyekeztünk az egyes
feladatokat didaktikusan úgy építeni föl, hogy a
"bonyodalmak" lépésről-lépésre növekedjenek, s így mindig
éppencsak egy "újdonságra" kelljen figyelni. A következő
részt az egyik feladat egy lehetséges implementációjának
szenteltük, hogy lássuk –az elmélet után– milyen
gyakorlati problémákkal találkozhatunk egy konkrét
programozási nyelven történő megvalósítás közben..

Az anyag elméleti része G.R. Endrews 'A Method for
Solving Syncronization Problems' cikke alapján készült.
Az egyes párhuzamossággal kapcsolatos alapfogalmaknál
utalunk olyan irodalmakra, amelyekben utánanézhet az
Olvasó a pontos definícióknak és más kapcsolódó
fogalmaknak. A feladatok Varga László professzor úr
gyûjteményéből valók. A precíz kidolgozás is az Ő
iránymutatása szerint történt. Köszönet illeti még Kozma
László docens urat is, hogy kritikai észrevételeivel
nagyban hozzájárult, hogy mentes legyen
következetlenségektől és bosszantó elírásoktól. Erre annál
is inkább nagy szükség volt, mert az eredeti cikktől
bizonyos jelölésekben, értelmezési kérdésekben eltér a
jelen anyag.

Mindezek ellenére maradhattak benne elírások, amelyekért
elnézést kér az anyag

összeszerkesztője.





Párhuzamos programok szintézise


1. Bevezetés


Egy párhuzamos program az több szekvenciális program, azaz folyamat és
megosztott, közösen használt objektumok együttese. Az objektumokon
keresztül történik a folyamatok kommunikációja.

Program PárhuzamosProgramNév:

Változó ... közösen használt objektumok, kezdőértékükkel ...
{invariáns állítás}[1]

Folyamat FolyamatNév1(... folyamat paraméterek...):
Ciklus amíg ... aktívság feltétele ...
... tevékenységek ...
Ciklus vége
Folyamat vége.

Folyamat FolyamatNév2(... folyamat paraméterek...):
Ciklus amíg ... aktívság feltétele ...
... tevékenységek ...
Ciklus vége
Folyamat vége.

... további folyamatok, ill. azok által felhasznált (közös) eljárások és
függvények ...

... incializálási tevékenységek ...

Program vége.

A későbbiekben számunkra nem lesz fontos a teljes párhuzamos program
leírása. Csak azt vizsgáljuk, hogy mi történik a folyamatok elindulását
követően, hogyan kommunikálhatnak, ill. hogyan kommunikáljanak úgy, hogy a
párhuzamosság hibás mûködést ne vigyen bele az egyébként, külön-külön
helyesen mûködő folyamatok együttmûködésébe. Vagyis a szinkronizáció
megvalósítása érdekel bennünket. (Ez indokolja, hogy "szintaktikusan" nem
lesznek teljesek a későbbi programjaink.)

A szinkronizáció két típusát használjuk föl sûrûn az alábbiakban: (1) a
kölcsönös kizárást[2] és (2) a feltételes szinkronizációt[3]. Az (1)
lényege, hogy egy ún. kritikus szakaszban futó programok tevékenységei nem
átfedőek. A (2)-é pedig, hogy egy feltétel várakoztatja a folyamatot a
szinkronizáció érdekében.

2. A levezetési eljárás


Minden ilyen célú "mechanikus" átírással szembeni elvárás a biztonságosság,
emellett praktikusan az "életképesség", azaz a józan ész egyszerûsítő
észrevételeit is magában foglalja.

Az eljárás első megközelítése:


Legyen a programszöveg a bizonyítást lehetővé tevő állításokkal
megtûzdelve. Ha S egy atomi tevékenység, akkor egy rávonatkozó állítás az
alábbi alakú lesz:

{P} S {Q}

Értelmezése: ha az S végrehajtása előtt a P predikátum igaz volt, és az S
végrehajtása befejeződött, akkor a Q is tejesül. A P-t előfeltételnek (Ef),
a Q-t utófeltételnek (Uf) nevezik. Ekkor –tehát– az S mint predikátum-
transzformátor mûködik.

A párhuzamos program levezetése során két követelménynek kell
teljesülnie:

A folyamatok önállóan –mint szekvenciális programok– helyesek
legyenek.

A folyamatok kapcsolata legyen interferencia-mentes, ami a következőt
jelenti. Minden egyes Fi folyamat, amely a {Pi} Fi {Qi}
predikátumtranszformációt végzi el, és bármely másik folyamatbeli S
atomi tevékenység esetén a Pi igaz marad az S végrehajtása során.
Másképpen fogalmazva S nem interferál a {Pi} Fi {Qi} tétellel, ha

1. {PiEf(S)} S {Pi} és

2. bármely Fi' részfolyamatára Fi-nek, amely az {Ef(Fi')} halmazról
képez le, akkor teljesül a {Ef(Fi')Ef(S)} S {Ef(Fi')} [4]

Tehát a párhuzamosság specialitása a bizonyítással szemben megkövetelné,
hogy minden atomi tevékenység interferálását, bármely feltétellel,
ellenőrizzük, de ez polinomiális költségû lenne. Mármost, jellemezzük a
ROSSZ predikátummal az elkerülendő állapotokat, és a programban
biztosítani tudjuk a (ROSSZ állandóságát (invarianciáját) a megosztott
változókra vonatkozólag, akkor az interferencia-mentesség bizonyítását
lineáris költségûvé tettük. Így tehát az elkövetkezőkben éppen ezt fogjuk
tenni.

Az eljárás lépései


L1. Problémadefiníció – a folyamatok és szinkronizációjuk "azonosítása",
megtervezése, vagyis a szükséges változók bevezetése az invariáns
állítások leírásához ...

L2. Megoldásvázlat – a folyamatok "megtûzdelése" az osztott változók
inicializálását elvégző értékadásokkal, hogy az invariancia –legalábbis–
kezdetben biztosítva legyen ...

L3. Az invariancia (további) biztosítása – minden, az invarianciát érintő
atomi értékadó utasítást "védünk" várakoztató feltételekkel, ha kell,
hogy az utófeltétel teljesíthesse az invarianciát ...

L4. Az atomi tevékenységek implementálása – az atomi értékadások kódolása
szekvenciális utasításokká ...

További előzetes megjegyzések:


M1. Lf(S,Q) jelölés – S leggyengébb előfeltétele Q-ra vonatkozólag az a
feltétel, amelyből kiindulva S után Q igaz.

Pl. a) ha S: x:=e {Q(x)}, akkor Lf( S , Q(x)) ( Q(e)

b) ha S: S1;S2 {Q}, akkor Lf( S1;S2 , Q) ( Lf( S1 , Lf( S2 ,
Q))

M2. < S > jelölés – S oszthatatlanul hajtható végre.

jelölés egy "őrzött" tevékenységre utal, ami
azt jelenti, hogy a B igazzá válásáig[5] legyen várakozás, majd S
oszthatatlanul hajtódik végre. A várakozás egy sorban[6] történik.

M3. Tegyük föl, hogy K, L predikátumok függetlenek más folyamatoktól, és
igaz a {K} {L} .

Állítás. Tegyük föl (továbbá), hogy I invariánsa S-nek, akkor a -nek is invariánsa lesz. S így teljesülni fog az
alábbi is: K(I((B ( Lf(S,L(I) .

Így ez "receptül" is szolgálhat a B megvalósítására: B legyen olyan,
hogy
S termináljon, és
a végállapot az L(I-t kielégítse, továbbá
a leggyengébb legyen az indokolatlan megvárakoztatás elkerülése
érdekében.

3. Programozás szemaforokkal


Három fontos programozási technikát fogunk az alábbiakban bemutatni:

1. a változók cseréje,
2. a bináris szemaforok hasítása és
3. a stafétabot továbbadása.

Mindenek előtt gondoljuk meg, mik is azok a szemaforok és hogyan
használhatók párhuzamos folyamatok szinkronizálására!

A. Szemafor[7]


A szemafor egy absztrakt adattípus, amelyhez két jellegzetes mûvelet
tartozik: a P és a V[8]. Méghozzá azzal az elvárással, hogy az adott
szemaforra vonatkozó befejezett P-k végrehajtási száma soha nem haladhatja
meg a befejezett V-k számát. Így invariánsnak veendő a V és P végrehajtási
szám különbségének nem negativitása. A szemafor szokásos definícióját és
megvalósítását formálizáljuk az alábbiakban:

Értékhalmaz: s0

Asszociált mûveletek[9]: P,V: 00 , P(s): s:=s-1, V(s): s:=s+1

Típusinvariáns: SZEM(s) s(0.

Gondoljuk meg, hogy a típusinvariáns fenntartása érdekében, milyen
feltétellel kell ellátnunk a P-t és a V-t:

1) Lf( P(s), SZEM(s) ) (Lf( s:=s-1, s(0 ) ( s>0. Így:

P(s):

(Vegyük észre, hogy eszerint a szemafor egy sorkezelő mechanizmust is
feltételez. Erre később még visszatérünk.)

2) Lf( V(s), SZEM(s) ) (Lf( s:=s+1, s(0 ) ( s+1(0 ( s(-1.

Az nyilvánvaló, hogy SZEM(s) ( s(-1, ezért V-nél nincs szükség
várakoztató feltételre:

V(s):

B. Bináris szemafor


A bináris szemafor is szemafor, de esetében a végrehajtott V-k száma
legfeljebb eggyel haladhatja meg a P-k számát. Azért bináris, mert
reprezentálásához elegendő a 0, 1 érték. Formálisabban:

Értékhalmaz: b{0,1}

Asszociált mûveletek: P,V: {0,1}{0,1}, P(b): b:=b-1, V(b): b:=b+1

Típusinvariáns: BSZEM(b) b({0,1}

A fentihez hasonló gondolatmenettel belátható, hogy

P(b):

V(b):

Ha garantálható legalább az, hogy a P-k és a V-k "párosával" hajtódnak
végre, P-V sorrendben (ami egy-egy folyamat körültekintő meggondolásával
elérhető), akkor a V őrfeltétele elhagyható[10]:

V(b):

3.1. Kritikus szakasz – változók cseréje


L1. Megadjuk a probléma definícióját.

Legyenek F(1..N) folyamatok, amelyek egy kritikus szakaszban közösen
használnak egy erőforrást, a kritikus szakaszokon kívül csak lokális
változókat használnak. (S mindezt szakadatlanul teszik.) A bent(1..N) a
folyamatokhoz rendelt változó, amely 1, ha a megfelelő folyamat a kritikus
szakaszban van, egyébként 0. Nyilvánvaló elvárás, hogy

KSz: bent(1)+...+bent(N)1

Itt formálisan nem jeleztük, hogy bent(i){0,1}.

L2. A megoldásvázlat és inicializálások.

Változó bent: Tömb(1..N: Egész) (1..N: 0) {a KSz triviálisan igaz}

Folyamat F(i: 1..N):
Ciklus
... a nem kritikus szakasz ...
{bent(i)=0} {bent(i)=1}
... a kritikus szakasz ...
{bent(i)=1} {bent(i)=0}
... a nem kritikus szakasz ...
Ciklus vége
Folyamat vége.

Lényeg tehát, hogy az i. folyamat az i. bent-elemet használja a
kommunikációra, de a bent vektort egyszerre csak egy folyamat használhatja.

L3. Mivel KSz kezdetben kielégül, úgy kell "gardírozni" az atomi
tevékenységeket, hogy a KSz később is fennálljon, azaz invariáns lehessen.
Ehhez vizsgáljuk:

{bent(i)=0} {bent(i)=1}.

M3 alapján [11]

"Lf( bent(i):=1, bent(i)=1 bent(1) + ... + bent(i) + ... + "("
"bent(N)1 ) "1"
" ")"


"
" 1=1 bent(1) +... + 1 +... + bent(N)1 "("
" "2"
" ")"


"
" bent(1) +... + bent(i-1) + 0 + bent(i+1) + ... + bent(N)=0 " "


"(1) ekvivalencia M1a) miatt igaz, (2) igaz, mivel j: bent(j){0,1},
továbbá a bent(i):=1 értékadás előtt bent(i)=0 kellett teljesüljön. Tehát
az őrző feltétellel kiegészített atomi tevékenység:



Hasonlóan vizsgáljuk:

{bent(i)=1} {bent(i)=0}.

M3 alapján

"Lf( bent(i):=0, bent(i)=0 bent(1) + ... + bent(i) + ... + "("
"bent(N)1 ) "1"
" ")"


"
" 0=0 bent(1) +... + 0 +... + bent(N)1 KSz "("
" "2"
" ")"


"(1) ekvivalencia M1a) miatt igaz, (2) implikáció triviálisan igaz.
Tehát az őrfeltétel nélkül is megfelelő az atomi tevékenység:



Mindezek után a megoldás precízebb változata:

Változó bent: Tömb(1..N: Egész) (1..N: 0) {a KSz triviálisan igaz}

Folyamat F(i: 1..N):
Ciklus
... a nem kritikus szakasz ...
{bent(i)=0 ( KSz} {bent(i)=1 ( KSz}
... a kritikus szakasz ...
{bent(i)=1 ( KSz} {bent(i)=0 ( KSz}
... a nem kritikus szakasz ...
Ciklus vége
Folyamat vége.

L4. Kódolás szemaforokkal.

Egy új változót vezetünk be, ami majd helyettesítheti a bent(1..N)-t.

Definíció: mutex := 1 - j=1..N bent(j).

Állítás: mutex bináris szemafor.

Ugyanis: KSz mutex {0,1}

P,V –korábbi értelmezésével összhangban– definiálhatjuk így:

P(mutex) :=
(1)

V(mutex) := < mutex:=1; bent(i):=0 > (2)

s ekkor a jelen helyzetben is mint bináris szemaforoperátorok
funkcionálnak, hiszen:

0=mutex 0 = 1 - j=1..N bent(j) j=1..N bent(j)=1
j=1..N bent(j)0.

Azaz a 'mutex=0' feltétel elvivalens a korábbi programban szereplő
'(j=1..N bent(j)0' őrfeltétellel.



Mivel a bent(i..N)-nek megszünt a szerepe (ami abból látszik, hogy bár
módosul, de értékére sehol sincs szükség), ezért bûntetlenül elhagyható (a
P(mutex) és V(mutex)-ből is). A végleges megoldás tehát így fest:

Változó mutex: BinSzamfor (1)[12] {a KSz triviálisan igaz}

Folyamat F(i: 1..N):
Ciklus
... a nem kritikus szakasz ...
P(mutex)
... a kritikus szakasz ...
V(mutex)
... a nem kritikus szakasz ...
Ciklus vége
Folyamat vége.

Az itt bemutatott módszer változók cseréjével operált. Alkalmazásának
feltételei:

V1. Szemantikusan különböző őrök változók diszjunkt halmazára
vonatkozhatnak; a változók csak atomi utasításokban szerepelhetnek.

V2. Minden őrző "kifejezés>0" alakúvá tehető.

V3. Minden őrzött atomi utasítás csökkenti a kifejezés értékét a
transzformált őrzőben.

V4. Minden nem őrzött atomi utasítás növeli a kifejezés értékét a
transzformált őrzőben.

3.2. Termelő-fogyasztó probléma – bináris szemaforok hasítása


L1. Megadjuk a probléma definícióját.

A termelők üzenetet küldenek, hogy a fogyasztók azokat megkapják. A
(termelő és fogyasztó) folyamatok egyetlen, megosztott pufferen keresztül
kommunikálnak. A puffer minden időpillanatban legfeljebb egy üzenetet
tartalmazhat. Mindehhez két mûvelet áll rendelkezésre: Elküld (Deposit),
Értemegy (Fetch)[13]. A mûveletek alkalmazásának vannak feltételei:

1. először az Elküld mûvelet hajtódjék végre;

2. felváltva következzenek az Elküld és Értemegy mûveletek annak
érdekében, hogy elkerülhető legyen két probléma: mielőtt a címzett
értemenne az üzenetnek, más üzenet foglalja el helyét, ill. csak egyszer
lehessen a kurrens üzenetért menni.

Jelöljük a termelő Elküld mûveletének elkezdései számát Kelőtt-tel,
befejezései számát Kután-nal, ill. a fogyasztó Értemegy mûveletének
elkezdései számát Melőtt-tel, a befejezései számát Mután-nal.



Mivel a puffer legfeljebb egy üzenetet fogadhat be, és csak létező üzenet
vehető ki belőle, ezért állandóan teljesülnie kell, hogy

TF: Kelőtt(Mután+1 ( Melőtt(Kután

L2. A megoldásvázlat és inicializálások.

Változó puf: T
Kelőtt,Kután, Melőtt,Mután: Egész (0) {TF igaz}

Folyamat Termelő(i: 1..M):
Változó
üzenet: T
Ciklus
(Ti1) üzenetgyártás(üzenet)
(Ti2) Elküld(üzenet)
Ciklus vége
Folyamat vége.

Folyamat Fogyasztó(i: 1..N):
Változó
üzenet: T

Ciklus
(Fi1) Értemegy(üzenet)
(Fi2) üzenetetfeldolgoz(üzenet)
Ciklus vége
Folyamat vége.

Eljárás Elküld(üzenet: T):
< Kelőtt:=Kelőtt+1 >; puf:=uzenet; < Kután:=Kután+1 >
Eljárás vége.

Eljárás Értemegy(üzenet: T):
< Melőtt:=Melőtt+1 >; uzenet:=puf; < Mután:=Mután+1 >
Eljárás vége.

(Állítások közbeiktatásától most el lehet tekinteni, mivel nyilvánvaló az
interferenciamentesség.)

A későbbiekben manuálisat nyomonkövetjük a programot, ezért jelöltük meg
az egyes utasításokat rövid szimbólumokkal: (Ti1)..(Fi2).

L3. Gondoskodni kell arról, hogy a TF állítás igaz maradhasson a mûködés
közben is. Ehhez vizsgálnunk kell az atomi tevékenységeket mind az Elküld
eljárásban, mind az Értemegy-ben. Azaz:

< Kelőtt:=Kelőtt+1 >, < Kután:=Kután+1 > , ill.
< Melőtt:=Melőtt+1 >, < Mután:=Mután+1 >.

Az elsőhöz tartozó meggondolásaink a következők. M3 alapján

"Lf( Kelőtt:=Kelőtt+1, KelőttMután+1 MelőttKután ) "("
" "1"
" ")"


"
" Kelőtt+1Mután+1 MelőttKután "("
" "2"
" ")"


"
" KelőttMután " "


"(1) ekvivalencia M1a) miatt igaz. A (2)-beli második tényezőnek nincs
szerepe, hisz a transzformáció az igazságtartalmát nem változtatja meg,
továbbá az invariancia miatt előtte is igaz volt. Így az őrző feltétellel
kiegészített atomi tevékenység:

Mután majd Kelőtt:=Kelőtt+1>

Hasonlóan az előzőhöz

"Lf( Kután:=Kután+1, KelőttMután+1 MelőttKután ) "("
" "1"
" ")"


"
" KelőttMután+1 MelőttKután+1 "("
" "2"
" ")"


"
" Igaz " "


"(1) ekvivalencia M1a) miatt igaz, (2) TF igazságából következik. Így
azután nincs szükség a második atomi tevékenység mellé őrfeltételt
rendelni:

< Kután:=Kután+1 >

A másik kettő atomi utasítás esetén is mechanikusan járható ez az út.
Vagyis az M3 alapján

"Lf( Melőtt:=Melőtt+1, {KelőttMután+1 MelőttKután} ) "("
" "1"
" ")"


"
" KelőttMután+1 Melőtt+1Kután "("
" "2"
" ")"


"
" Melőtt (2)

P(tele) := (3)

V(tele) := < tele:=1 > (4)

s ekkor a jelen helyzetben is mint bináris szemaforok funkcionálnak,
hiszen P(üres) (1)-beli
definíciója megfelelő, mivel triviális átalakításokkal megkapható a
fenti őrző feltétel:

0=üres 0= Mután - Kelőtt + 1 Kelőtt > Mután (ez éppen
az 'Elküld' őrzője.).

továbbá P(tele) (3)-beli definíciója is hasonlóan megfelelő:

0=tele 0= Kután - Melőtt Melőtt = Kután

(mivel a > eleve lehetetlen, így) Melőtt Kután (ez éppen
az 'Értemegy' őrzője.)



Mivel

az (1)-beli üres:=0 (az üres eggyel csökkentése) a Kelőtt:=Kelőtt+1
(definíció szerint),

a (2)-beli üres:=1 (az üres eggyel növelése) Mután:=Mután+1,

a (3)-beli tele:=0 (a tele eggyel csökkentése) a Melőtt:=Melőtt+1,

a (4)-beli tele:=1 (az tele eggyel növelése) Kután:=Kután+1
értékadással ekvivalens,

ezért elhagyva a fölöslegessé vált Kelőtt, Kután, Melőtt és Mután
változókat, az alábbi végleges megoldást kapjuk:

Változó puf: T
üres, tele: BinSzemafor (1,0) {TF-fel ekvivalens
invariáns: üres+tele{0,1} igaz}

Folyamat Termelő(i: 1..M):
... nem változik ...
Folyamat vége.

Folyamat Fogyasztó(i: 1..N):
... nem változik ...
Folyamat vége.

Eljárás Elküld(üzenet: T):
P(üres); puf:=uzenet; V(tele)
Eljárás vége.

Eljárás Értemegy(üzenet: T):
P(tele); uzenet:=puf; V(üres)
Eljárás vége.

Összegezve a fentieket egy fontos általános gondolat fogalmazható meg a
hasított bináris szemaforokról. Tudniillik: b hasított bináris szemaforként
használható, ha b=b1,...,bN: BinSzemaforok, továbbá teljesíti a HASÍT(b):
(i=1..N bi{0,1} feltételt.

3.3. Egy osztott adatbázis olvasási és írási mûveletei – a stafétabot
továbbadása


L1. A probléma:

Egy adatbázison osztozik két típusú folyamat. Az Olvasók olvashatnak
belőle, akár egyszerre többen is, az Írók írhatják, de ők csak
"egymagukban". Ezt az elvárást fejezi ki az alábbi állítás:

ÍO: (oDb=0 ( íDb=0) ( íDb(1

ahol az oDb az olvasó(folyamato)k számát, az íDb az írók számát jelöli.

L2. A megoldásvázlat és inicializálások.

Változó oDb,íDb: Egész (0) {ÍO igaz}

Folyamat Olvasó(i: 1..M):
Ciklus
< oDb:=oDb+1 >; Olvas; < oDb:=oDb-1 >
Ciklus vége
Folyamat vége.

Folyamat Író(i: 1..N):
Ciklus
< íDb:=íDb+1 >; Ír; < íDb:=íDb-1 >
Ciklus vége
Folyamat vége.

L3. Gondoskodni kell arról, hogy a ÍO állítás igaz maradhasson (volt is és
legyen is) a mûködés közben is. Ehhez vizsgálnunk kell az atomi
tevékenységeket. Azaz:

< oDb:=oDb+1 > , < oDb:=oDb-1 > , ill.
< íDb:=íDb+1 > , < íDb:=íDb-1 >.

Az elsőhöz tartozó meggondolásaink a következők. M3 alapján

"Lf( oDb:=oDb+1, (oDb=0 íDb=0) íDb1 ) "("
" "1"
" ")"


"
" (oDb+1=0 íDb=0) íDb1 "("
" "2"
" ")"


"
" (oDb=-1 íDb1) (íDb=0 íDb1) "("
" "3"
" ")"


"
" íDb=0 " "


"(1) ekvivalencia M1a) miatt igaz, (2) azonos átalakítás és a
disztributivitás miatt igaz, (3) után az 1. tag az oDb0 ÍO igaz volt az atomi
utasítás előtt (l. L2 programban!). Így kapjuk, hogy

< oDb:=oDb-1 >

Az előbbiekhez hasonlóan adódik, M3 alapján

"Lf( íDb:=íDb+1, (oDb=0 íDb=0) íDb1 ) "("
" "1"
" ")"


"
" (oDb=0 íDb+1=0) íDb+11 "("
" "2"
" ")"


"
" (oDb=0 íDb=-1) íDb0 "("
" "3"
" ")"


"
" oDb=0 íDb=0 " "


"(1) ekvivalencia M1a) miatt igaz, (2) azonos átalakítás miatt igaz; (3)
után az 1. tényező az íDb0 miatt redukálható, ugyanezen indokkal alakítható
a 2. tényező. Így kapjuk, hogy



Az -re vonatkozó meggondolásokkal haladva

"Lf( íDb:=íDb-1, (oDb=0 íDb=0) íDb1 ) "("
" "1"
" ")"


"
" (oDb=0 íDb-1=0) íDb-11 "("
" "2"
" ")"


"
" (oDb=0 íDb=1) íDb2 IGAZ "("
" "3"
" ")"


"(1) ekvivalencia M1a) miatt igaz, (2) azonos átalakítás miatt igaz, (3)
igaz, mivel íDb>0 ÍO igaz volt az atomi utasítás előtt (l. L2
programban!). Így kapjuk, hogy

< íDb:=íDb-1 >

Az eredményeket így foglalhatjuk össze:

Változó oDb,íDb: Egész (0) {ÍO igaz}

Folyamat Olvasó(i: 1..M):
Ciklus

Olvas
< oDb:=oDb-1 >
Ciklus vége
Folyamat vége.

Folyamat Író(i: 1..N):
Ciklus

Ír
< íDb:=íDb-1 >
Ciklus vége
Folyamat vége.

L4. Kódolás.

Itt a két őrt álló feltételnek van közös része, ezért a változók cseréje
módszer nem használható az atomi utasítások implementálására. (Nem teljesül
a V1. feltétel.) Ennek az a magyarázata, hogy egyetlen szemafor nem képes
elválasztani a két örző feltételt. Új módszer kell tehát: az ún. stafétabot
továbbadása.

Ennek lényege röviden a következő. Kétféle atomi utasítás van:

F1: < Si >, illetve F2:

Ezek implementálhatók bináris szemaforok hasításával. Mégpedig így:

1. Legyen e bináris szemafor 1 kezdőértékkel. Ez kontrollálja egy
(tetszőleges) atomi utasításba való belépést.

2. Legyen cj bináris szemafor, dj számláló[14] a várakozók számát
adminisztrálandó (kezdetben 0 értékkel), minden egyes szemantikusan
eltérő őrző feltételhez.

F1-nek megfeleltetjük az

F1: P(e)
{I}
Si
{I}
SIGNAL

F2-nek pedig az

F2: P(e)
{I}
Ha nem Bj akkor dj:=dj+1; V(e); P(cj);
itt adja át a stafétabotot mielőtt sorba állna
{IBj}
Sj
SIGNAL

ahol az I a szinkronizációs invariánst, és a SIGNAL a következő
programdarabot jelöli:

SIGNAL: Elágazás
B1 és d1>0 esetén {IB1} d1:=d1-1;
V(c1) itt aktivizál egy várakozót
. . .
BN és dN>0 esetén {IBN} dN:=dN-1;
V(cN) itt aktivizál egy várakozót
egyéb esetben {I} V(e)
itt aktivizál egy várakozót
Elágazás vége

Néhány megjegyzést kell fûznünk a e programdarabokhoz:

1. Ha létezne a W függvény, akkor F2 egyszerűsödne:

F2: P(e)
{I}
Ha nem Bj akkor V(e); P(cj);
{IBj}
Sj
SIGNAL

2. A SIGNAL betét is rövidebben lenne megfogalmazható:

SIGNAL: Elágazás
B1 és W(c1) esetén {IB1} V(c1)
. . .
BN és W(cN) esetén {IBN} V(cN)
egyéb esetben {I} V(e)
Elágazás vége

3. A SIGNAL-beli elágazás egy nem determinisztikusan választó alternatív
szerkezet, amely az igaz-értékû ágak közül választ egyet nem
determinisztikusan. Természetesen az egyéb feltétel csak rövidíti a
"megelőző" feltételek nem teljesülését megfogalmazó feltételt.

4. A feltételek első része (Bj) akkor igaz, ha az Sj végrehajtható, míg
a második tényezője (dj>0) akkor, ha van az adott atomi tevékenységre
várakozó.

5. Az elágazó ágak utolsó dolguk, hogy átadják (egyszerre persze csak
egyikük) a stafétabotot azzal, hogy a V(cj)-vel szabadra állítják a
saját szemaforukat.

Vegyük észre az e bemeneti szemafor szerepét! Az e megakadályozza, hogy
több párhuzamos folyamat több (természetesen különböző) szemafort
párhuzamosan kezeljen. Ez azért okozna bajt, mert a szemaforok
"összekuszálódása" olyan folyamatokat is útnak indíthatnának, amelyek
valójában egymást ki kellene zárniuk. (Emlékezzünk, korábban épp ilyen
probléma akadályozta a változók cseréje egyszerû módszerének
alkalmazását[15])

Jelen esetben a szemaforok egy hasított bináris szemafort alkotnak, mivel
egyidejüleg közülük legfeljebb egy lehet 1-értékû, és minden végrehajtási
út egy P-vel kezdődik és egy V-vel végződik. Vagyis a P és V közti
utasítások kölcsönösen kizárva hajtódhatnak csak végre. Az I
szinkronizációs invariáns igaz lesz minden V mûvelet előtt, ugyancsak igaz
valahányszor a szemaforok egyike 1-értékû. Továbbá Bj garantáltan teljesül,
amikor Sj végrehajtódik, hisz ha Bj nem lenne igaz, akkor cj szemafornál
kényszerül a folyamat várakozni Bj igazzá válásáig. Végezetül a
transzformáció nem tartalmaz holtpontot, hiszen cj jelzi, hogy valamely
folyamat várakozik vagy várakozni készül a cj-nél.

Ezt a sémát alkalmazzuk az "írók-olvasók" probléma megoldására! Vezessük
be a következő jelöléseket:

o – szemafor az (oDb=0) feltételre váró olvasóhoz,
í – szemafor az (oDb=0 és íDb=0) feltételre váró íróhoz,
b – belépési szemafor,
dO – számláló az (oDb=0) feltételre váró olvasóhoz,
dÍ – számláló az (oDb=0 és íDb=0) feltételre váró íróhoz,

A megoldás tehát:

Változó oDb,íDb: Egész (0) {ÍO igaz}
o,í: BinSzemafor(0)
b: BinSzemafor(1) {o+í+b{0,1}}
dO,dÍ: Egész(0) {dO0 és dÍ0}

Folyamat Olvasó(i: 1..M):
Ciklus
P(b)
Ha íDb0 akkor dO:=dO+1; V(b); P(o)
oDb:=oDb+1;
SIGNAL1

Olvas

P(b)
oDb:=oDb-1
SIGNAL2
Ciklus vége
Folyamat vége.

Folyamat Író(i: 1..N):
Ciklus
P(b)
Ha oDb0 vagy íDb0 akkor dÍ:=dÍ+1; V(b); P(í) ha itt
elakad, akkor csak ott
íDb:=íDb+1
SIGNAL3

Ír

P(b)
íDb:=íDb-1
SIGNAL4
Ciklus vége
Folyamat vége.

SIGNALi: Elágazás
íDb=0 és dO>0 esetén dO:=dO-1; V(o)
íDb=0 és oDb=0 és dÍ>0 esetén dÍ:=dÍ-1; V(í)
ott: indítható tovább
egyéb esetben V(b)
Elágazás vége

Megjegyzések:

1. Az atomi utasításokat helyettesítő részeket dőlten szedve emeltük ki.

2. Az egyéb esetet a későbbiek miatt részletezve is megadjuk:

(íDb0 vagy dO=0) és (íDb0 vagy oDb>0 vagy dÍ=0)

Többnyire –mint jelen esetben is– a SIGNAL rész redundáns, tartalmaz
egyszerûsíthető, elhagyható részeket. A fenti algoritmusban szereplő négy
SIGNAL-t vesszük sorra, figyelembe véve azt a helyet, ahol ő valójában
található.

A SIGNAL1 előtt biztosan igaz, hogy (íDb=0 és oDb=0), tehát az elágazás
első feltétele egyszerûen dO>0; a második ág hamis, tehát elhagyható; a
harmadik ág feltételéből mindössze dO=0 marad. Azaz

Elágazás
dO>0 esetén dO:=dO-1; V(o)
dO=0 esetén V(b)
Elágazás vége

A SIGNAL2 előtt tudjuk, hogy (íDb=0 és dO=0) igaz, hisz nincs író
folyamat, ami sorba kényszerített volna akár egyetlen olvasót is. Így az
első feltétel hamis, elhagyható; a második ág feltétele egyszerûbb: (dÍ>0
és oDb=0); a harmadik ág (oDb>0 vagy dÍ=0) marad:

Elágazás
oDb=0 és dÍ>0 esetén dÍ:=dÍ-1; V(í)
oDb>0 vagy dÍ=0 esetén V(b)
Elágazás vége

Hasonlóan kell végigjárni a maradék két SIGNAL részletet is. Miután a
végeredmény így alakul:

Változó oDb,íDb: Egész (0) {ÍO igaz}
o,í: BinSzemafor(0)
b: BinSzemafor(1) {o+í+b{0,1}, ui. BinSzem
hasítás}
dO,dÍ: Egész(0) {dO0 és dÍ0}

Folyamat Olvasó(i: 1..M):
Ciklus
P(b)
Ha íDb0 akkor dO:=dO+1; V(b); P(o)
oDb:=oDb+1;

Elágazás
dO>0 esetén dO:=dO-1; V(o)
dO=0 esetén V(b)
Elágazás vége

Olvas

P(b)
oDb:=oDb-1
Elágazás
oDb=0 és dÍ>0 esetén dÍ:=dÍ-1; V(í)
oDb>0 vagy dÍ=0 esetén V(b)
Elágazás vége
Ciklus vége
Folyamat vége.

Folyamat Író(i: 1..N):
Ciklus
P(b)
Ha oDb0 vagy íDb0 akkor dÍ:=dÍ+1; V(b); P(í)
íDb:=íDb+1
V(b)

Ír

P(b)
íDb:=íDb-1
Elágazás
dO>0 esetén dO:=dO-1; V(o)
dÍ>0 esetén dÍ:=dÍ-1; V(í)
dO=0 és dÍ=0 esetén V(b)
Elágazás vége
Ciklus vége
Folyamat vége.

Példafeladatok


1. Filozófusok


A filozófusok egy kerek asztal körül ülnek, közöttük egy-egy villa fekszik
az asztalon. Az asztal közepén egy nagy tányéron van az étel, amelyből csak
két villa felhasználásával tudnak enni. Mindenki csak a jobbján, illetve a
balján lévő villákat használhatja. Minden filozófus a következő
tevékenységeket ciklikusan végzi:

gondolkodik,
eszik.

A filozófus a villák helyzetével meghatározott állapotot azzal
változtatja meg, hogy a balján és a jobbján levő villákat –egyszerre!–
megragadja, ill. visszahelyezi.

A megoldás:

L1. Problémadefiníció:

Azonosítsa a Philos(1..M) a filozófusok "mûködési folyamatait".
Erőforrás, amin meg kell osztozniuk: a villa, pontosabban a szomszédos
filozófus(-folyamat)ok a köztük lévő villán osztoznak. Így kritikus
szakaszban akkor tartozkodik egy folyamat, amikor két villát használ, azaz
eszik. Az egyes folyamatokhoz –értelemszerûen– rendelhetünk egy-egy bináris
szemafort, az alábbi értelmezéssel:

Legyen eszik(1..M) 1, ha az adott filozófus eszik, máskülönben 0.

A feladat feltételei szerint állandóan teljesülnie kell (azaz invariánsan
igaz), hogy ha egy filozófus eszik, akkor ugyanezt nem teheti egyik
szomszédja sem, másrészt viszont, ha ő nem eszik, akkor bármelyik
szomszédja ehet (legalábbis ő miatta). Formálisan ugyanez:

Ph: (i([1..M]: (eszik(i)=1 ( eszik(«i)+eszik(»i)=0) ( (eszik(i)=0 (
0(eszik(«i)+eszik(»i)(2) [16]

ahol a « és a » operátorok az előző és következő index kiválasztását végzik
ciklikusan, azaz

»i = j, ahol j ( i+1 mod M, illetve

«i = j, ahol j ( i-1 mod M

L2. Megoldásvázlat

Változó eszik: Tömb(1..M: Egész) (1..M: 0) {a Ph triviálisan igaz,
hisz enni nem kötelező}

Folyamat Philosz(i: 1..M):
Ciklus
Gondolkodik
{eszik(i)=0} {eszik(i)=1}
Eszeget
{eszik(i)=1} {eszik(i)=0}
Ciklus vége
Folyamat vége.

L3. Az invariancia (további) biztosítása:

Vizsgálnunk kell, az alábbi atomi tevékenységek milyen feltétellel
biztosítják a Ph szinkronizációs invariánst:

,

"Lf(, Ph) "("
" "1"
" ")"


"
"Lf(, "("
"[«i. filozófus:] ( (eszik(«i)=1 eszik(««i)+eszik(i)=0) "2"
"(eszik(«i)=0 0eszik(««i)+eszik(i)2) ) ")"
"[i. filozófus:] ( (eszik(i)=1 eszik(«i)+eszik(»i)=0) " "
"(eszik(i)=0 0eszik(«i)+eszik(»i)2) ) " "
"[»i. filozófus:] ( (eszik(»i)=1 eszik(i)+eszik(»»i)=0) " "
"(eszik(»i)=0 0eszik(i)+eszik(»»i)2) ) " "
") " "


"
" [«i. filozófus:] ( (eszik(«i)=1 eszik(««i)+1=0) (eszik(«i)=0"("
"0eszik(««i)+12) ) "3"
"[i. filozófus:] ( (1=1 eszik(«i)+eszik(»i)=0) (1=0 ")"
"0eszik(«i)+eszik(»i)2) ) " "
"[»i. filozófus:] ( (eszik(»i)=1 1+eszik(»»i)=0) (eszik(»i)=0 " "
"01+eszik(»»i)2 ) " "


"
" [«i. filozófus:] ( (eszik(«i)=1 eszik(««i)=-1) (eszik(«i)=0 "("
"-1eszik(««i)1) ) "4"
"[i. filozófus:] ( (1=1 eszik(«i)+eszik(»i)=0) (1=0 ")"
"0eszik(«i)+eszik(»i)2) ) " "
"[»i. filozófus:] ( (eszik(»i)=1 eszik(»»i)=-1) (eszik(»i)=0 " "
"-1eszik(»»i)1) ) " "


"
"[«i.filozófus:] (eszik(«i)=0) "("
"[i.filozófus:] (eszik(«i)+eszik(»i)=0) "5"
"[»i.filozófus:] (eszik(»i)=0 ")"


"
" (eszik(«i)+eszik(»i)=0) " "


"(1) ekvivalencia amiatt teljesül, mivel az i. filozófusnak közvetlen
hatása csak két szomszédjára van, így elegendő a Ph-nak «i-re, i-re és »i-
re vonatkozó részét vizsgálni. A (2) M1a) miatt igaz; (3) azonos
átalakítást és az azonosan igaz részfeltételek elhagyását jelenti. (4)-nél
figyelembe vettük az eszik(j) értékkészletére vonatkozó ismereteinket,
továbbá elhagytuk az elhagyható tagjait a kifejezésnek. Így kapjuk, hogy



Másrészt

"Lf(, Ph) "("
" "1"
" ")"


"
"Lf(, "("
"[«i. filozófus:] ( (eszik(«i)=1 eszik(««i)+eszik(i)=0) "2"
"(eszik(«i)=0 0eszik(««i)+eszik(i)2) ) ")"
"[i. filozófus:] ( (eszik(i)=1 eszik(«i)+eszik(»i)=0) " "
"(eszik(i)=0 0eszik(«i)+eszik(»i)2) ) " "
"[»i. filozófus:] ( (eszik(»i)=1 eszik(i)+eszik(»»i)=0) " "
"(eszik(»i)=0 0eszik(i)+eszik(»»i)2) ) " "
") " "


"
" [«i. filozófus:] ( (eszik(«i)=1 eszik(««i)+0=0) (eszik(«i)=0"("
"0eszik(««i)+02) ) "3"
"[i. filozófus:] ( (0=1 eszik(«i)+eszik(»i)=0) (0=0 ")"
"0eszik(«i)+eszik(»i)2) ) " "
"[»i. filozófus:] ( (eszik(»i)=1 0+eszik(»»i)=0) (eszik(»i)=0 " "
"00+eszik(»»i)2) ) " "


"
" [«i. filozófus:] ( (eszik(«i)=1 eszik(««i)=0) (eszik(«i)=0 "("
"0eszik(««i)2) ) "4"
"[i. filozófus:] ( (0eszik(«i)+eszik(»i)2) ) ")"
"[»i. filozófus:] ( (eszik(»i)=1 eszik(»»i)=0) (eszik(»i)=0 " "
"0eszik(»»i)2) ) " "


"
" [«i. filozófus:] ( (eszik(«i)=1 eszik(««i)=0) (eszik(«i)=0) "("
") "5"
"[i. filozófus:] ")"
"[»i. filozófus:] ( (eszik(»i)=1 eszik(»»i)=0) (eszik(»i)=0) )" "
" " "


"
" (eszik(«i)=1 eszik(»i)=1) "("
" "6"
" ")"


"
" Igaz " "


"Most is a fentihez hasonló lépéseket végeztük el a (4)-ig. (5)-nél az
((AB)A)((AB)A))(AB) azonos átalakítást végeztük; a (6) a Ph invaranciáját
tudva teljesül. Így kapjuk, hogy

< eszik(i):=0 >

L4. Az atomi tevékenységek implementálása:

Alkalmazzuk a stafétabot továbbadása módszert! Bevezetjük a b (belépési),
a c(1..M) (B(i)= eszik(«i)+eszik(»i)=0 feltételre várakozáshoz tartozó)
bináris szemaforokat, valamint a Db(1..M) (B(i) feltételre várakozáshoz
tartozó) számlálókat.

Változó eszik: Tömb(1..M: Egész) (1..M: 0) {a Ph triviálisan igaz,
hisz enni nem kötelező}
b: BinSzemafor(1)
c: Tömb(1..M: BinSzemafor) (1..M: 0) {b+c(í){0,1}, ui.
BinSzem hasítás}
Db: Tömb(1..M: Egész) (1..M: 0) {Db(i)0}

Folyamat Philosz(i: 1..M):
Ciklus
Gondolkodik
P(b)
Ha eszik(«i)+eszik(»i)0 akkor Db(i):=Db(i)+1; V(b);
P(c(i))
eszik(i):=1;
SIGNAL1

Eszeget

P(b)
eszik(i):=0
SIGNAL2
Ciklus vége
Folyamat vége.

SIGNALi: Elágazás
eszik(M)+eszik(2)=0 és Db(1)>0 esetén Db(1):=Db(1)-1;
V(c(1))
eszik(1)+eszik(3)=0 és Db(2)>0 esetén Db(2):=Db(2)-1;
V(c(2))
...
eszik(«i)+eszik(»i)=0 és Db(i)>0 esetén
Db(i):=Db(i)-1; V(c(i))
...
eszik(M-1)+eszik(1)=0 és Db(M)>0 esetén
Db(M):=Db(M)-1; V(c(M))
egyéb esetben V(b)
Elágazás vége

Megjegyzések:

1. Az 'egyéb'-feltétel gyanánt megfelel a Db(1)=0 ( ... ( Db(M)=0,
hiszen a B(i)=(eszik(«i)+eszik(»i)=0) és D(i)=(Db(i)>0) jelölésekkel az
'egyéb' nem más, mint
((B(1)(D(1))(.. (((B(M)(D(M)), ami pedig ((B(1)(...(B(M)) ((
(D(1)(...(D(M)), s az első tényező azonosan igaz volta miatt elhagyható,
amiután már nyilvánvalóan a keresett formulánál vagyunk.

2. A Db(i):=Db(i)+1 helyett Db(i):=1 is elegendő, hisz csak az i.
filozófus várhat a B(i) feltétel teljesülésére. Hasonló ok miatt a
Db(i):=Db(i)-1 helyett Db(i):=0 is megfelelő.

3. Mivel a Db(i):=1 a P(c(i))-vel, a Db(i):=0 pedig a V(c(i))-vel együtt
szerepel, ezért a programban a c(i)=1-Db(i) mindig igaz, így a Db(i)>0
helyettesíthető a c(i)=0 feltétellel, s a Db-k elhagyhatók a
programból.[17]

A holtpontmentességhez be kell látnunk: nem következhet be, hogy
mindegyik filozófus várakozik a sorára, azaz Db(1)>0 (... ( Db(M)>0
(vagyis a c(1)=0 ( ... ( c(M)=0). Ami egyszerû következménye az algoritmus
fenti szervezésének.

Ezen a ponton érdemes egy csöppet elidőzni, s meggondolni, hogy nem is
csekélység az az elvárás, amit a szemaforokkal szemben támasztottunk. Ti.
hogy: a kritikus szakaszba való többszörös belépés megelőzésére állítsa
várakozási sorba a "többletfolyamatokat". Ez az eset –méghozzá különösen
nehéz eset– lép föl akkor is, amikor párhuzamosan érkezik hozzá több
folyamat. Milyen mechanizmusra van szükség ahhoz, hogy a "valóban"
egyidőben érkező két, vagy több folyamat zavarmentesen vegye igénybe az
"oszthatatlan" szemafor szolgáltatásait? Például tegyük föl, hogy a
kritikus szakaszban éppen nem tartózkodik folyamat, amikor egyszerre két
folyamat érkezik oda. Élesítsük tovább a kérdést! Hogy lehet az, hogy a
kettő közül csak az egyiket engedi tovább, a másikat meg nem; az egyiknek
foglaltat, a másiknak szabadot mutat, jól lehet ugyanakkor még semmilyen
folyamat sincs a védett szakaszban? Nos, többféle mechanizmussal is
megoldható ez a komoly kihívás. Egy ilyenről olvashatunk a függelékben.

2. "Balkezes" filozófusok


Az előző filozófus kerekasztal problémának tekintsük egy tipikus
módosítását! Tegyük azt a kiegészítést, hogy "konfliktus esetben" a
jobboldali[18] filozófussal szemben elsőbbsége legyen a tőle balra ülő
szomszédjának. A "körbe várakozás" elkerülésére tegyük föl, hogy az 1-es
számú filozófusnak mindkét szomszédjával szemben előnye van.

A megoldás:

L1. Problémadefiníció:

Most is a Philos(1..M) azonosítsa a filozófusok "mûködési folyamatait".
Az előző feladathoz képest a módosítás az elsőbbség bevezetése; kérdés
tehát az, hogy miként lehet ezt a "megbomlott" szimmetriát az
invarianciában (s majd a folyamatok algoritmusaiban) figyelembe venni.

Ha megpróbáljuk követni az előző felaadat megoldásánál követett
gondolatmenetet, előbb-utóbb rájövünk, hogy valami "újítást", nevezetesen a
filozófusok egy "közbülső" állapotát kell bevezetnünk. Ez az állapot a
filozófus azon szándékát fejezik ki, hogy enni óhajt. Lássuk be, hogy egy
ilyen állapotra valóban szükség van.

Induljunk ki az előző megoldásalgoritmusból azt a módosítást elvégezve,
hogy egy, az elsőbbséget is figyelembe vevő örzőfeltételt (B(i)) illesztünk
az ottani (eszik(«i)+eszik(»i)(0) helyére.[19] Kövessük, mi történhet
akkor, amikor két, szomszédos, "evésre jogosult" filozófus egyszerre akar
enni. Mivel egyidőben érik el a atomi
mûveletet felügyelő P(b) szemaformûveletet, egyikük beléphet az őrfeltétel-
kiértékelő végrehajtási fázisba, a másik azonban a b szemafornál vár a
belépésre. Hogy melyik, az nemdeterminisztikusan dől el. Ha történetesen a
jobboldali ez a "szerencsés", akkor ő úgy érzékeli, hogy szabadon
belefoghat az étkezésbe, s végrehajtja az eszik(i):=1 mûveletet. Amikor ezt
követően "illedelmesen" átadja a SIGNAL-nál a stafétabotot a másiknak, az
már a villát fölvett állapotban találja, így nem tehet másként, mint várja
a villa felszabadulását. Így sérült meg a prioritás szabálya.

Tegyük föl már most, hogy minden filozófus a következő tevékenységeket
végzi ciklikusan:

gondolkodik,
megéhezik (s bejelenti igényét a két mellette fekvő villára),
eszik.

A kritikus szakasz ezesetben meghosszabodott: elkezdődik már a
"megéhezéssel", s tart, míg a filozófus falatozik. Az egyes folyamatokhoz
most rendeljünk egy-egy (nem bináris, hanem!) 3-értékû szemafort, az alábbi
értelmezéssel:

Legyen eszik(1..M) 2, ha az adott filozófus eszik; 1, ha már megéhezett,
de még nem jutott villához; 0 máskülönben.

A feladat feltételei szerint állandóan teljesülnie kell, hogy egy
filozófus akkor ehet, ha jobboldali szomszédja nem eszik és a baloldali
szomszédja még csak nem is éhezik, másrészt viszont, ha ő nem eszik, akkor
bármelyik szomszédja ehet (legalábbis ő miatta). Az 1. és az M. filozófus
esetében kicsit más a helyzet: az 1. mindaddig ehet, amíg szomszédai
"legfeljebb" éheznek. Persze a gondolkodást és a megéhezést nem kell
korlátozzuk a szinkronizációs invariánsban. Formálisan ugyanez:

Ph: (i([1..M]: eszik(i)[0..2] (
(i([2..M-1]: ((eszik(i)=2 ( eszik(«i)=0 ( eszik(»i)(1) eszik(i)0 n3=0) (n1+1=0 n30) ) ( (n2>0 n4=0) (n2=0 n40) "1"
") ")"


"
" ( (n3=0) ) ( (n2>0 n4=0) (n2=0 n40) ) "("
" "2"
" ")"


"
" n3=0 " "


"Az (1)-nél az első logikai tényezőt, mint triviálisan igazat,
elhagytuk, továbbá a második tényező első tagját redukáltuk, a második
tagja (n1+1=0 n30) azonosan hamis az UK igaz volta mellett, így
elhagyható. A (2)-nél az UK korábbi teljesülését elegendő figyelembe venni.
Így kapjuk, hogy



hasonlóan kapható, hogy







Másrészt

"Lf(, UK) " "


"
" Lf(, ( i[1,4]: 0ni ) " "
"( (n1>0 n3=0) (n1=0 n30) ) ( (n2>0 n4=0) (n2=0 n40) ) ) " "


"
" ( i[1,4]: 0ni ) "("
"( (n1-1>0 n3=0) (n1-1=0 n30) ) ( (n2>0 n4=0) (n2=0 n40) "1"
") ")"


"
" ( (n1>1 n3=0) (n1=1 n30) ) ( (n2>0 n4=0) (n2=0 n40) ) "("
" "2"
" ")"


"
" Igaz " "


"Mind az (1), mind a (2) lépésben kihasználtuk az UK invarianciáját,
ill. azt szituációt (ti. hogy egy mûvelet utáni állapotban van a
folyamat), amelyben az érintett atomi mûveletre sor került. Hasonló
levezetési lépések után kapjuk mind a négy csökkentő atomi értékadásra,
hogy őrző feltétel nélkül alkalmazható:

< n1:=n1-1 >

< n2:=n2-1 >

< n3:=n3-1 >

< n4:=n4-1 >

L4. Az atomi tevékenységek implementálása:

A már jólbevált módszerrel kapjuk meg a program implementációját. Be kell
vezetnünk szemaforokat a belépéshez, s az örző feltételekhez ((n1=0),
(n2=0), (n3=0), ill. (n4=0)), s számlálókat. Ezeket rendre jelöljük a
korábbi programhoz hasonlóan: b, d1, d2, d3, d4; Db1, Db2, Db3, Db4.

Változó n1,nl2,n3,n4: Egész(0) {UK}
b: BinSzemafor(1)
d1,d2, d1, d2: BinSzemafor(0) {b+d1+d2{0,1}, ui.
BinSzemafor hasítás}
Db1,Db2,Db3,Db4: Egész(0)

Folyamat KNy(i: 1..DbKNy):
halad(Ny{felé})

P(b) {UK}
Ha n30 akkor Db1:=Db1+1; V(b); P(d1)
{UK n3=0}
n1:=n1+1
SIGNAL1

keresztez

P(b) {UK}
n1:=n1-1 {UK}
SIGNAL2

halad(Ny{felé})
Folyamat vége.

Folyamat NyK(i: 1..DbNyK):
halad(K{felé})

P(b) {UK}
Ha n40 akkor Db2:=Db2+1; V(b); P(d2)
{UK n4=0}
n2:=n2+1
SIGNAL3

keresztez

P(b) {UK}
n2:=n2-1 {UK}
SIGNAL4

halad(K{felé})
Folyamat vége.

Folyamat KD(i: 1..DbKD):
halad(Ny{felé})

P(b) {UK}
Ha n20 akkor Db4:=Db4+1; V(b); P(d4)
{UK n2=0}
n4:=n4+1
SIGNAL5

keresztez

P(b) {UK}
n4:=n4-1 {UK}
SIGNAL6

halad(D{felé})
Folyamat vége.

... a folytatás részben mechanikusan kapható meg, részben változatlan az
előzőhöz képest ...

SIGNALi: Elágazás
n1=0 és Db1>0 esetén Db1:=Db1-1; V(d1)
n2=0 és Db2>0 esetén Db2:=Db2-1; V(d2)
n1=0 és Db3>0 esetén Db3:=Db3-1; V(d3)
n4=0 és Db4>0 esetén Db4:=Db4-1; V(d4)
egyéb esetben V(b)
Elágazás vége

A feladatsor befejezéseként egy feladat: gondoljuk meg, hogy mit
jelentene az útkereszteződéses feladat olyan bővítése, amelyben megengedett
a kisívben történő kanyarodás is!

Implementációk


Ebben a fejezetben a párhuzamos végrehajtás konkrét nyelvi környezetben
történő megvalósításának problémáit és ezek feloldásait tekintjük át.
Először érdemes a "klasszikus" nyelvek egy fajtáját szemügyre venni e
szempontból. Választásunk a módszertani és elterjedtség szempontjából
ideálisnak mondható Pascal nyelv változatára esett: a Turbo Pascal 7.0.

A párhuzamosságot nem támogató nyelv példája után egy ezen hiányosságtól
mentes nyelvet választottunk ki: az Ada-t. Erre is igaz, hogy
módszertanilag kiválónak mondható, de a másik ismérv, az közismertség
jellemvonásával –ma még– nem igen dicsekedhet.

1. Egy szekvenciális –Turbo Pascal 7.0-nyelvû megoldás


1.1. Kontrollmentes párhuzamos mûködés


Az első tanulságos példa: egy –úgy is mondhatnánk– rossz példa lesz. Ui.
arról szól, hogy a párhuzamosan zajló folyamatok mindenfajta kontrollálása
nélküli megvalósítás gyakran jut holtpontra. Ebben a programpéldában ezt is
szemügyre vehetjük, de ami legalább ennyire érdekes, az a szekvenciális
programkörnyezetbeli megszervezése a párhuzamosságnak.

Nézzük elképzelésünket pontokba szedve:

1. Minden folyamatot egy időegység alatt végrehajtandó lépések
sorozatára bontjuk. Ezek alatt nem kommunikálhatnak egymással. Ez az a
feltevés, ami éppen a szinkronizáció hiányát jelenti. A lépések
kódrészeit elkülönítve tartalmazza a 'lepes' metódus. A lépések
végrehajtási sorrendje és a leírási sorrendje a 'lepes' metódusban
megegyezik. (Persze semmi akadálya nincs annak, hogy a lépéseket
ciklusokba zárjuk, vagy feltételekkel bővítsük ki.)

2. Az egyes folyamatok vezérlését a 'keret' metódus végzi, amely
meghívja a 'lepes' metódust a megfelelő lépéssorszámmal.

3. Hogy éppen melyik lépésnél tart, azt egy attributuma (az 'állapot'
mezője) tartja nyilván. Mint egy programszámlálót képzelhetjük el, külön-
külön minden egyes folyamathoz. Az állapotok, vagyis a lépések számát
rögzíti a 'VegAllapot' konstans.

4. Feltesszük, hogy a folyamatok egyetlen folyamat példányai. (Bár nem
lenne elvi akadálya annak sem, hogy különböző folyamatok szerepeljenek a
programban. Csak a kód hosszabbodna meg, lényeges többletmondanivaló
nélkül.)

5. A teljes rendszer vezérlését (a főfolyamat munkáját) a főprogram
végzi, amely időegységenként minden folyamatnak átadja egy lépés erejéig
a vezérlést. Ő gondoskodik az új folyamatok létrehozásáról, s itt
szûnnek meg a végállapotba jutottak.

Program FolyamatSzimulacio;

{ Párhuzamos folyamatok kvázipárhuzamos
szimulációja. }

{******* Folyamat-típus
******************************************************}
Const
VegAllapot = konkrét érték; {Az egyes folyamatok lépéseinek,
azaz állapotainak száma.}

Type
Lepesek = 1..VegAllapot;
Folyamat = Object
azon: Integer; {folyamatazonosító}
allapot: Byte;
Constructor indul(Const fa: Byte);
Procedure keret;
Procedure lepes(Const i: Lepesek);
End;

Constructor Folyamat.indul(Const fa: Byte);
Begin
azon:=fa; allapot:=1; {minden folyamat az 1-s állapotból
indul}
End;

Procedure Folyamat.keret; {az adott folyamat egy –a
következő– lépésének vezérlése}
Begin
Lepes(allapot); Inc(allapot);
End;

Procedure Folyamat.lepes(Const i: Lepesek);
Begin
Case i of
1: {az 1. lépés kódja};
2: {a 2. lépés kódja};
{... a további lépések ágai ...}
End;
End;

{******* Folyamat-típus
****************************************************}

Const
MaxN = 10; {Maximum ennyi folyamat lehet
egyszerre a rendszerben.}

Type
Folyamatok = Array [1..MaxN] of Folyamat;
Var
{a rendszer állapotparaméterei:}
F : Folyamatok;
N : Byte; {aktív folyamatok száma}
i,T : Integer;
{a rendszer bemenőparaméterei:}
P : Real; {új folyamat születésének valószínüsége}
SzulVarSzam: Byte; {az egyszerre születő folyamatok várható
száma}
{a rendszer kimenőparamétere:}
DbF: Integer; {összesen generált folyamatok száma}

Procedure General(Var fk: Folyamatok; Var n: Byte; Const db: Byte);
Var
i: Byte;
Begin
i:=1;
While (iK sáv foglalt}

{******* Autó-típus
********************************************************}
Type
Auto = Object(Folyamat)
...
End;

Constructor Auto.indul(Const fa: Byte);
Begin
azon:=(Integer(Random(2))*2-1)*(Random(3)*100+fa); {utolsó
2 számjegy egyedi}
allapot:=1;
End;

Procedure Auto.keret; {az adott folyamat egy – a következő-
lépésének vezérlése}
Begin
Lepes(allapot); Inc(allapot);[20]
End;

Az ütközés elkerülendő, ami a 'lepes' metódus feladata figyelemmel
kísérni.

Procedure Auto.lepes(Const i: Lepesek);
Begin
Case i of
1: {az 1. lépés kódja:}
Begin
If
({K->Ny}(azon>0) and (azonE }(azon>100) and (azonD }(azon>200) and fogl1) or
({Ny->K}(-azon>0) and (-azonE}(-azon>100) and (-azonD}(-azon>200) and fogl2

then Dec(allapot) {nem léphet} else if
{beléphet K-ről} azon>0 then
fogl1:=True
{beléphet Ny-ról}
else fogl2:=True
{EndIf};
End;

2: {a 2. lépés kódja:}
Begin
If
({K->D }(azon>200) and fogl2) or
({Ny->E}(-azon>100) and (-azon0 then
fogl1:=False {kiléphet}
{Ny-ról jött} else
fogl2:=False {kiléphet}
{EndIf};
End;
End{Case};
End;

{******* Autó-típus
********************************************************}

'Folyamatok' helyett persze 'Autok' tömbünk lesz.

Const
MaxN = 10;
Type
Autok = Array [1..MaxN] of Auto;
Var
{a rendszer állapotparaméterei:}
F : Autok;
...

Procedure General(Var fk: Autok; Var n: Byte; Const db: Byte);
...

Procedure Takarit(Var fk: Autok; Var n: Byte);

...

Némi –algoritmikai szempontból– lényegtelen módosítással a főprogram:

Begin {a rendszer (=folyamatok együttese) kvázipárhuzamos vezérlése:}
P:=1; SzulVarSzam:=10; fogl1:=False; fogl2:=False;
DbF:=0;
T:=1; General(F,N,Random(SzulVarSzam)+2{legálább 2 folyamattal
indul});
...
End.

Egy futás "históriáját" adjuk meg az alábbi táblázatban.

"Idő "Folyamat-a"Folyamat-lép"
" "zonosító "ésszám "


"
"1: "1 "1 "


"
" "-2 "1 "


"
"2: "1 "2 "


"
" "-2 "2 "


"
" "-3 "1 "


"
" "-104 "1 "


"
" "-105 "1 "


"
"3: "-3 "2 "


"
" "-104 "1 "


"
" "-105 "1 "


"
"4: "-104 "2 "


"
" "-105 "1 "


"
" "106 "1 "


"
" "7 "1 "


"
" "208 "1 "


"
" "-9 "1 "


"
" "-10 "1 "


"
" "11 "1 "


"
" "-12 "1 "


"
"5: "-105 "2 "


"
" "106 "2 "


"
" "7 "1 "


"
" "208 "1 "


"
" "-9 "1 "


"
" "-10 "1 "


"
" "11 "1 "


"
" "-12 "1 "


"
" "13 "1 "


"
"Idő "Folyamat-a"Folyamat-lép"
" "zonosító "ésszám "


"
"6: "-105 "2 "


"
" "7 "2 "


"
" "208 "1 "


"
" "-9 "1 "


"
" "-10 "1 "


"
" "11 "1 "


"
" "-12 "1 "


"
" "13 "1 "


"
" "214 "1 "


"
"7: "-105 "2 "


"
" "208 "2 "


"
" "-9 "1 "


"
" "-10 "1 "


"
" "11 "1 "


"
" "-12 "1 "


"
" "13 "1 "


"
" "214 "1 "


"
" "15 "1 "


"
"8: "-105 "2 "


"
" "208 "2 "


"
" "-9 "1 "


"
" "-10 "1 "


"
" "11 "1 "


"
" "-12 "1 "


"
" "13 "1 "


"
" "214 "1 "


"
" "15 "1 "


"
Mint látható a 7. időegységtől kezdődően a rendszer állapota befagy. Ui.
az 5. autó, amely nyugatról északra nagyívben (-105), a 8., amely pedig
keletről délre akar –szintén– nagyívben kanyarodni, egymásra várva állják
el a másik útját a kereszteződésbeli saját sávjukban. Tökéletes holtpont
helyzet.

1.2. Kontrollált párhuzamos mûködés – egy szemaforos változat


Az útkereszteződéses probléma a változók cseréje módszer szerinti
megoldását implementáljuk most. Megfigyelhető lesz, hogy miként lehet
szemaforokat kezelni és ezt beilleszteni a kvázipárhuzamos mûködésû
programba.

Kezdjük az elképzelés vázolásával, de csak az előzőekben már leírtakat
egészítjük ki, vagy módosítjuk alább.

ad 1. A kommunikáció tiltása természetesen csak a szemaformûveletekre
korlátozódik.

ad 5. ... Az inaktív –valamely szemafornál várakozó– folyamatok közül csak
az elsővel történhet valami (továbbléphet, vagy még várakozni
kényszerül).

6. A szemaformûveletek önálló, elemi mûveleteknek számítanak. A szemafor
P-müveletét két mûveletre szedjük:

a) a "normál" P-mûvelet, ami adott esetben a várakozási sorba állít;
és

b) a Q-mûvelet, amely ellenőrzi a várakozást, s adott esetben
továbbengedi. (Ez utóbbi nem tûnik föl az egyedi folyamat lépései
között, csak a főfolyamatban.)

A kereszteződés:

... ugyanaz, mint az előbb volt ...

A modell:

1. Egyszerû, egy-szemaforos szinkronizáció.

2. Generálás: időegységenként valahány (paramétertől függő) darab.

3. A célkód:

... ugyanaz, mint volt az előbb ...

4. A kereszteződésben csak egy autó lehet. A belépést a szemaforral
szinkronizáljuk.

5. Az autóknak 5 állapota van: a kereszteződés előtti, a szemaforállító
P-mûvelet végrehajtása alatti, a kereszteződésbeli, a szemaforállító V-
mûvelet végrehajtása alatti, ill. a kereszteződés utáni. (Nyilván most
sincs semmi akadálya nincs annak, hogy az előtti és utáni szakaszt
"finomabban" bontsuk föl.)

Várható eredmény:

Nincs halálos ölelés, de meglehetősen "darabos" az autók áramlása (a
modell 4. pontja miatt).

Program FolyamatSzimulacio_UtKeresztezodes2;

{ Párhuzamos folyamatok kvázipárhuzamos szimulációja,
szemaforos szinkronizációval. }

{******* Folyamat-típus
******************************************************}
Const
VegAllapot = 5; {állapotok: 1='a kereszteződés előtt',
2='P-mûvelet',
3='a
kereszteződésben',
4='V-mûvelet',
5='a kereszteződés
után'}

A Pascal programban egy osztályhierarchiát építünk föl. A legalapvetőbb
osztály maga a Folyamat osztály, amely lényegében megegyezik az előző
implementációbelivel. Majd, mivel a szemaforok egy-egy önálló sort
kezelnek, célszerû definiálni egy általános Sor osztályt, amit fölhasználva
definiáljuk a kellő konkrét sorokat. Mivel –sajnos– a Pascal osztályai nem
parametrizálhatók (nem ismeri a generic fogalmát), ezért a Sor osztály most
Integer típusú elemek kezelésére lesz alkalmas. (Ez által a sorba tehetők a
folyamatazonosítók.)

Type
FolAzo = Integer; {folyamatazonosító}
Lepesek = 1..VegAllapot;
Folyamat=Object
azonosito: FolAzo;
allapot: Byte;
Constructor indul(Const fa:Integer);
Procedure keret;
Procedure lepes(Const i:Lepesek);
End;
{******* Folyamat-típus
******************************************************

******* Sor-típus
***********************************************************}
Const
MaxSor = 10;
Type
Ido=Integer;
Sor=Object{Generic=FolAzo}
hossz, {sorbeli elem száma}
eleje, {az első, sorbeli elem
indexe}
vege : -1..MaxSor; {az utolsó, sorbeli elem indexe}
elem : Array [0..MaxSor-1] of FolAzo;
hiba : Boolean; {az utolsó sormûvelet sikeres volt-
e?}
Constructor inic;
Procedure Sorba(Const o:FolAzo);
Procedure Sorbol(Var o:FolAzo);
Procedure Elso(Var el:FolAzo);
Function SorHossz:Integer;
End;
{******* Sor-típus
***********************************************************

A későbbi általánosíthatóság miatt definiáljuk az IdőFolyamatSor osztályt,
amely a folyamatazonosító és (esemény-) idő kettősét tárolja egy
sorelemként. Az asszociált mûveletek paramétereiben akkurátusan megőrizzük
a kétféle, bár "alakilag" azonos, Integer paraméter típusát.

******* IdoFolyamatSor-típus
************************************************}
Type
IdoFolyamatSor=Object
ido: Sor{Ido};
fol: Sor{FolAzo};
Constructor inic;
Procedure Sorba(Const i:Ido; Const o:FolAzo);
Procedure Sorbol(Var i:Ido; Var o:FolAzo);
Procedure Elso(Var i:Ido; Var o:FolAzo);
Function SorHossz:Integer;
End;
{******* IdoFolyamatSor-típus
************************************************

A Szemafor osztály fölhasználja az imént definiált osztályt, mint a
várakozó folyamatokat tároló mezőjének típusát. Megjegyezzük, hogy a
Szemaforokhoz hozzárendelünk egy függvényt (SorHossz) is, amihez hasonlónak
a "praktikusságát" a korábbi elméleti részben már előre jeleztük.

******* Szemafor-típus
******************************************************}
Type
Szemafor=Object{Generic=Folyamat}
sz: Integer;
varoSor: IdoFolyamatSor; {az inaktív folyamatok sora:
idő + folyamatazonosító}
Constructor inic;
Procedure P(Const t:Ido; Var o:Folyamat);
{ha a szemafor=0, akkor a
paraméter Folyamatot a varoSor-ba
teszi, s o.allapot visszalép}
Procedure Q(Var o:Folyamat);
{ha a szemafor>0, akkor a
varoSor-beli első Folyamatot adja vissza,
egyébként "üres-Folyamatot"}
Procedure V(Const o:Folyamat);
Function SorHossz:Integer;
End;
{******* Szemafor-típus
******************************************************

Az aktív folyamatok kezelését a PFolyamat osztállyal definiáljuk. Ebbe
illesztettük bele –az előző implementációtól eltérően– a szimulációs időt,
s az aktív folyamatok (idő-folyamat-)sorát.

******* PFolyamat-típus
*****************************************************}
Type
PFolyamat=Object{Generic=Folyamat}
T : Word; {akt. idő}
aktivSor: IdoFolyamatSor; {az aktív folyamatok sora: idő +
folyamatazonosító}
Constructor inic;
Procedure FolyamatSzul; {folyamatot generál és tesz az
aktívSor utolsó elemévé}
Procedure MelyFolyamat(Var f:Folyamat; Var j:Integer);
{f.azonosito=>f=ok[j]
(ok-tömbből)}
Function FolyamatValtozott(Const f:Folyamat;
j:Integer):Boolean;
Procedure FolyamatModosit(Const f:Folyamat; j:Integer);
{ok[j]:=f}
Procedure FolyamatTemet(Const i:Integer);
Procedure Sorba(Const i:Ido; Const f:Folyamat);
Procedure Sorbol(Var i:Ido; Var f:Folyamat);
Procedure Elso(Var i:Ido; Var f:Folyamat);
Function SorHossz:Integer;
End;
{******* PFolyamat-típus
*****************************************************}

Const
UresFolyamat : Folyamat=(azonosito:-MaxInt);
MaxObj = 1000;

Az alábbiak a Pascal "szerencsétlenségei" miatt kerültek ide. Az ok, oDb,
oUt a későbbi PFolyamat-hoz tartoznak ugyan, de mivel a Szemafor is
használja, ezért ide, előre, globális változóként kerültek.

Type
Folyamatok = Array [1..MaxObj] of Folyamat;
Var
ok : Folyamatok; {az összes folyamat tömbje}
oDb: 0..MaxObj; {az összes folyamat darabszáma}
oUt : 0..MaxObj; {az összes folyamat utolsója}
Var
pf: PFolyamat; f : Folyamat; s : Szemafor;
P : Real; i,j,t,SzulVarSzam: Integer;

Constructor Folyamat.indul(Const fa:Integer);
Begin
azonosito:=fa; allapot:=1;
End;

Procedure Folyamat.keret; {az adott folyamat egy – a
következő- lépésének vezérlése}
Begin
Lepes(allapot); Inc(allapot);
End;

Az világos, hogy a Folyamat.lepes metódus tartalmazza azokat a konkrét
ismereteket, amitől ez a program épp a konkrét, útkereszteződéses
feladathoz tartozik. Az elemi lépésekre bontást kellene újra írni egy másik
feladat esetén.

Procedure Folyamat.lepes(Const i:Lepesek);
Begin
Case i of
1: Begin {az 1. lépés kódja}
End;
2: Begin {a 2. lépés kódja}
s.P(pf.T,self);
End;
3: Begin {az 3. lépés kódja}
s.V(self);
End;

4: Begin {a 4. lépés kódja}
End;
End;
End;

Constructor Sor.inic;
Begin
hossz:=0; eleje:=0; vege:=-1; hiba:=False
End{Sor.inic};

Procedure Sor.Sorba(Const o:FolAzo);
Begin
If hossz0 then
Begin
Dec(hossz); o:=elem[eleje]; eleje:=(eleje+1) Mod
MaxSor;
End
Else
Begin
hiba:=True
End;
End{Sor.Sorbol};

Procedure Sor.Elso(Var el:FolAzo);
Begin
If hossz>0 then el:=elem[0]
else hiba:=True
End{Sor.Elso};

Function Sor.SorHossz:Integer;
Begin
SorHossz:=hossz
End{Sor.SorHossz};

Constructor IdoFolyamatSor.inic;
Begin
ido.inic; fol.inic;
End{IdoFolyamatSor.inic};

Procedure IdoFolyamatSor.Sorba(Const i:Ido; Const o:FolAzo);
Begin
ido.Sorba(i); fol.Sorba(o);
End{IdoFolyamatSor.Sorba};

Procedure IdoFolyamatSor.Sorbol(Var i:Ido; Var o:FolAzo);
Begin
ido.Sorbol(i); fol.Sorbol(o);
End{IdoFolyamatSor.Sorbol};

Procedure IdoFolyamatSor.Elso(Var i:Ido; Var o:FolAzo);
Begin
ido.Elso(i); fol.Elso(o);
End{IdoFolyamatSor.Elso};

Function IdoFolyamatSor.SorHossz:Integer;
Begin
SorHossz:=fol.SorHossz
End{IdoFolyamSor.SorHossz};

Constructor Szemafor.inic;
Begin
sz:=1; varoSor.inic;
End{Szemafor.inic};

Procedure Szemafor.P(Const t:Ido; Var o:Folyamat);
Begin
If sz=0 then
Begin
varoSor.Sorba(t,o.azonosito); Dec(o.allapot)
End
Else
Begin
sz:=0
End;
End{Szemafor.P};

Procedure Szemafor.Q(Var o:Folyamat);
Var
t:Ido;
j:Integer;

Begin
If sz=1 then
Begin
varoSor.Sorbol(t{nem fontos},o.azonosito);
{kikerül, s átkerülhet az aktív folyamatok sorába}
pf.MelyFolyamat(o,j{nem fontos});
End
Else
Begin
o.azonosito:=UresFolyamat.azonosito
End;
End{Szemafor.Q};

Procedure Szemafor.V;
Begin
sz:=1
End{Szemafor.V};

Function Szemafor.SorHossz:Integer;
Begin
SorHossz:=varoSor.SorHossz
End{Szemafor.SorHossz};

Constructor PFolyamat.inic;
Begin
aktivSor.inic;
oDb:=0; {eddig generált folyamatok száma=0}
oUt:=0; {eddig generált folyamatok utolsója a "0".}
End{PFolyamat.inic};

Procedure PFolyamat.FolyamatSzul;
Begin
Inc(oDb);
Inc(oUt); ok[oUt].indul((Integer(Random(2))*2-
1)*(Random(3)*100+oDb));
aktivSor.Sorba(T,ok[oUt].azonosito);
{uf: minden generált elem egyedi azonosítóval rendelkezik}
End{PFolyamat.FolyamatSzul};

Procedure PFolyamat.MelyFolyamat(Var f:Folyamat; Var
j:Integer);

{f.azonosito=>f=ok[j] (ok-tömbből)}
Begin
{ef: van keresett azonosítójú elem}
j:=1;
While (ok[j].azonositof.azonosito) do Inc(j);
f.allapot:=ok[j].allapot
End{PFolyamat.MelyikFolyamat};

Procedure PFolyamat.FolyamatModosit(Const f:Folyamat;
j:Integer);
{ok[j]:=f}
Begin
ok[j]:=f;
End{PFolyamat.FolyamatModosit};

Function PFolyamat.FolyamatValtozott(Const f:Folyamat;
j:Integer):Boolean;
Begin
FolyamatValtozott:=f.allapotok[j].allapot;
End{PFolyamat.FolyamatValtozott};

Procedure PFolyamat.FolyamatTemet(Const i:Integer);
Var
j:Integer;
Begin
For j:=i+1 to oDb do ok[j-1]:=ok[j];
Dec(oUt);
End{PFolyamat.FolyamatTemet};

Procedure PFolyamat.Sorba(Const i:Ido; Const f:Folyamat);
Begin
aktivSor.Sorba(i,f.azonosito);
End{PFolyamatSor.Sorba};

Procedure PFolyamat.Sorbol(Var i:Ido; Var f:Folyamat);
Begin
aktivSor.Sorbol(i,f.azonosito); pf.MelyFolyamat(f,j{nem
fontos});
End{PFolyamatSor.Sorbol};

Procedure PFolyamat.Elso(Var i:Ido; Var f:Folyamat);
Begin
aktivSor.Elso(i,f.azonosito); pf.MelyFolyamat(f,j{nem
fontos});
End{PFolyamatSor.Elso};

Function PFolyamat.SorHossz:Integer;
Begin
SorHossz:=aktivSor.SorHossz
End{PFolyamat.SorHossz};

Elérkeztünk a program "vezérlő részéhez", amelynek rövid lényege a
következő: az inicializáló és néhány a kezdő pillanatban a rendszerbe lépő
autó generálása után a szimuláció "életciklusa" jön. Az egész addig folyik
míg a rendszerben tartózkodik legalább egy autó, legyen az akár aktív, vagy
akár inaktív állapotban. Minden egyes időegységben először az aktív
autókkal történik valami állapotváltozás, majd a rendszerben levő
szemaforoknál –jelen esetben: az egyetlennél– várakozó autók közül az első
próbál onnan kijutni (a Q-mûvelet segítségével). Az időegység végén
"szokásos" dolgokat kell végeznünk: a végállapotba jutott autókat a
rendszerből el kell távolítani, s gondoskodni kell esetleges új belépőkről.

Begin
P:=0.5; SzulVarSzam:=1;
pf.inic; s.inic; pf.T:=1;
For i:=1 to SzulVarSzam+2{legalább 2 folyamattal indul} do
If Random0) or (s.SorHossz>0) do
Begin
{az aktív folyamatok szimulációja:}
For i:=1 to pf.Sorhossz do
Begin
pf.Sorbol(t,f);
f.keret; {egyedi folyamat-szimuláció}
If pf.FolyamatValtozott(f,j) then
Begin
pf.FolyamatModosit(f,j); pf.Sorba(t,f);
End;

{Történt-e változás a szemaforok körül?
Az inaktív –a várakozási sor(ok)ban álló– folyamatok
szimulációja (azaz minden
szemaforra):}
If s.SorHossz>0 then
Begin
s.Q(f);
If f.azonositoUresFolyamat.azonosito then
Begin {továbblép:}
pf.MelyFolyamat(f,j);
f.keret;
pf.FolyamatModosit(f,j); pf.Sorba(T,f)
End;
End;
End;
{a végállapotba jutott folyamatok kihagyása:}
For i:=1 to pf.SorHossz do
Begin
pf.Sorbol(t,f); pf.MelyFolyamat(f,j);
If f.allapot=VegAllapot then pf.FolyamatTemet(j)
else
pf.Sorba(t,f);
End;
{új folyamatok beléptetése:}
For i:=1 to SzulVarSzam do If Random