6. Közös változóval rendelkez˝o párhuzamos program, Közös változó, Reynold kritérium. Atomi muvelet, ˝ atomi utasítás. szintaxis, szemantika, tulajdonságok. Szinkronizációs párhuzamos program, szintaxis, szemantika, tulajdonságok. P(s), V(s) utasítások: kölcsönös kizárás megoldása. Termel˝o fogyasztó modell. Megállapodás. Formális meghatározás. Absztrakt megoldás. Realizáció. Er˝oforrás közös használatának problémája. Kiéheztetés, monopolizálás. Kiéheztetés mentes vezérlés szinkronizációs problémája. Példa: adatbázis modell.(Két kapus megoldás) 6.1. Közös változóval rendelkez˝o párhuzamos program, Közös változó, Reynold kritérium. 6.1. Definíció (Közös változóval rendelkez˝o párhuzamos program): Párhuzamos programszerkezet két vagy több olyan folyamatot tartalmaz, amelyek egymással közös változó segítségével kommunikálnak. Folyamat a végrehajtás alatt lév˝o program. Kommunikáció azt jelenti, hogy a közös változó értékét párhuzamosan futó folyamatok kiolvassák, illetve felülírják. Adva S ≡ parbegin S1 || ... || Sn parend; 6.2. Definíció (Közös változó): Közös változó : olyan változó, amelyhez egynél több folyamat is hozzáférhet. Lokális változó: olyan változó, amelyhez csak egy folyamat férhet hozzá. A párhuzamosan történ˝o végrehajtás követelményei: 1. Követelmény: A közös változóhoz való hozzáférés követelményei: A hozzáférés a közös változóhoz: a változó értékének kiolvasása vagy felülírása. A közös változókhoz való hozzáférések atomi operációnak tekintend˝ok. 2. Követelmény (A végrehajtás követelményei): A végrehajtás sebessége minden, de nem fejez˝odött folyamat esetén pozitív és tetsz˝oleges, ( kivéve, ha a közös változóhoz való hozzáférésre vár). Ekkor azonban 1
a hozzáférés kell˝o id˝o után garantált és a végrehajtás folytatódhat. Az atomi m˝uveletek (közös változóhoz való hozzáférések) lineárisan sorba rendezettek, de a sorrend véletlenszer˝u. A közös változókhoz való hozzáférések lineárisan sorba rendezettek: • Megvárakoztatás. (blokkolt állapot). • Garantált a hozzáférés minden folyamat számára. (holtpont mentesség állapota). • Folyamatok végrehajtási sebessége pozitív érték, kivéve, ha a közös er˝oforrásra várnak. (fair követelmény). 6.3. Definíció (Reynold-féle kritérium): Ha az 1., 2. követelmények teljesülnek, a párhuzamos komponensek végrehajtása során érvényes a program állapotára vonatkozóan a nem determinisztikus egymás utáni atomi végrehajtás • a logikai kiértékelés és • a felülírás (feltéve, hogy a logikai kiértékelés és felülírás közös változót tartalmaz).
6.2. Atomi muvelet, ˝ atomi utasítás. Szintaxis, szemantika, tulajdonságok. 6.4. Definíció (Atomi m˝uvelet, atomi utasítás): Atomi (primitív) m˝uvelet, utasítás végrehajtása: meg nem szakítható végrehajtás, és aszinkron módon. Atomi muveletek: ˝ • Egy bool kifejezés kiértékelése. • Egy változó értékének a kiolvasása. • Értékadás egy változónak. 6.5. Definíció (Atomi utasítás):
Egy olyan S program szakasz,
• amelyet atomivá teszünk, • amelyet ciklust, vagy atomi utasítást nem tartalmaz. Jelölés: <S>; 2
6.6. Definíció (Közös változóval rendelkez˝o determinisztikus párhuzamos program szintaxisa): S::= skip | y ← t | S1 ;S2 | if α then S1 else S2 fi | while α do S1 od | parbegin S1 || S2 parend; 6.7. Definíció (Atomi program): 6.8. Definíció (Más jelölés):
<S>;
while α do S1 od: do α → S1 od;
6.9. Definíció (Szemantika): < S, σ >→< E, τ > << S >, σ >→< E, τ >
(1)
M [< S >](p) = M [S](p)
(2)
Tulajdonságok: 6.10. Lemma: A közös változóval rendelkez˝o párhuzamos program blokkolásmentes. Ugyanis, minden < S, σ > konfigurációnak S 6= E és σ ∈ Σ esetén van rákövetkez˝oje a → reláció szerint. 6.11. Lemma: Minden S párhuzamos program és σ ∈ Σ esetén a < S, σ > konfigurációnak véges számú rákövetkez˝oje van a → reláció mellett. (Következik a szintaktikai axiómákhoz, szabályokhoz rendelt tranzakciók relációinak definícióiból.) 6.12. Lemma: Adott S és σ ∈ Σ kezd˝o állapot. Mtot [S](σ) vagy véges számú állapotot tartalmaz, vagy csak a ⊥ virtuális állapotot. A bizonyítás a fákra vonatkozó König lemma [1927] adaptációjával mutatható ki. Ezt Knuth D. E. végezte el 1968-ban. Programhelyesség bizonyításánál feltesszük: Bool kifejezés, értékadás, skip, atomi régió mindegyike atomi akció, azaz • Meg nem szakíthatók, vagy • Egymás után hajtódnak végre, de a végrehajtás sorrendje nincs meghatározva. Egy hagyományos hardver ezt nem garantálja. Garancia: Általában a kritikus hivatkozások atomi kezelését garantálja, kizárólagos írási vagy olvasási atomi hozzáférést garantál az egyszer˝u, vagy indexes változók esetében. y ← f(x,y): < y ← f(x,y) > Atomi utasítások: • A párhuzamos program helyesség bizonyítását leegyszer˝usíti a virtuális <S> atomi definíció. • Minél kisebb egységre vonatkozik az atomi definíciónk annál inkább megfelel a valóságos végrehajtásnak. 3
• Minél nagyobb egységre vonatkozik az atomi definíciónk annál inkább megkönnyíti a program helyességének a bizonyítását. 6.13. Példa: S ≡ parbegin x ← y || y ← x parend; x ← y esetén atomi m˝uveletek: y kiolvasása, x értékének felülírása. x = 1 ; y = 2; esetén lehetséges eredmények: • x = y = 2; • x = y = 1; • x = 2 és y = 1. A parallel modell jelentése nem azonos a hagyományos hardware által nyújtott megoldással. Minden komponens program szoftver-akkumulátorok bevezetésével áttranszformálható egy olyan vele ekvivalens párhuzamos programmá, ahol minden atomi akció egy hozzáférést jelent a közös változóhoz: S’ ≡ parbegin AC1 ← y; x ← AC1 || AC2 ← x; y ← AC2 parend; A párhuzamosság atomi egységére vonatkozó < x ← y > szemantikai meghatározás az egyszer˝u kezelés célját szolgálja a helyességbizonyításnál. A párhuzamos program helyesség bizonyítását leegyszer˝usíti a virtuális <S> atomi definíció. Minél kisebb egységre vonatkozik az atomi definíciónk annál inkább megfelel a valóságos végrehajtásnak. Minél nagyobb egységre vonatkozik az atomi definíciónk annál inkább megkönnyíti a program helyességének a bizonyítását.
6.3. Szinkronizációs párhuzamos program, szintaxis, szemantika, tulajdonságok. Párhuzamos program szinkronizációval: A feltételes atomi utasítás szintaxisa: < b → S >; 6.14. Definíció:
Dijkstra - féle jelölés
await b then S ta; Speciális esetek • await "true" then S ta; • await b then skip ta; • await b then ta; • wait b tw; 4
A Dijkstra - féle atomi szemafor utasítások: P(s) : s ← s -1; if s < 0 then állj be az s-hez rendelt várakozó sorba fi; V(s): s ← s+1; if s ≥ 0 then induljon el egy folyamat az s-hez rendelt várakozó sorból fi ; Egyszeruimplementáció: ˝ P( s ) : await s > 0
t h e n s <− s −1 t a ;
V( s ) : a w a i t " t r u e " t h e n s <− s +1 t a ; Egy pontos implementáció: D i j k s t r a −f é l e s z e m a f o r u t a s í t á s o k P( s ) : a w a i t " t r u e " then b e g i n s <− s −1; i f s < 0 t h e n V[ j ] <− " f a l s e " f i ; end ta ; a w a i t V[ j ] t h e n t a V( s ) : a w a i t " t r u e " then b e g i n s <− s + 1 ; i f s >= 0 t h e n b e g i n v á l a s s z i −t , a h o l V[ i ] = " f a l s e " ; V[ i ] <− " t r u e " end f i end t a ; Szemantika: 6.15. Definíció (Az o˝ rfeltételes atomi utasítás jelentése): σ(b) = ”true” ⇒< S, σ >→< E, τ > << b → S >, σ >→< E, τ >
(3)
σ(b) = ”true” ⇒< S, σ >→< E, τ > (4) < await.b.then.S.ta, σ >→< E, τ > 6.16. Definíció (Holtpont állapot informális definíciója): Az S párhuzamos program holtpont állapotba jutott, ha a program végrehajtása nem fejez˝odött be és annak minden olyan komponense, amely nem fejez˝odött be, blokkolt állapotban van. 5
6.17. Definíció (Szintaxis): S::=
| S1 ; S2 | if b then S1 else S2 fi | while b do S od | parbegin S1 || S2 parend; Feltételes meg nem szakítható (atomi) utasítás : ; amely nem tartalmazhat iterációt, vagy másik atomi utasítást. Jelölés: parbegin S1 || ... || Sn parend; Más jelölések: cobegin S1 || ... || Sn coend; [ S1 || S2 ]; 6.18. Lemma: A párhuzamos program végrehajtása során, a σ állapotban, a p(σ) állítás mellett, az await b then S ta utasítáSn ál blokkolt állapotba kerül, ha p(σ) ∧ b = "true". 6.19. Definíció: Legyen S párhuzamos program és annak egy σ állapotára p(σ) = "true". Az <S, σ> konfigurációt holtpontnak nevezzük, ha • ∼(S ≡ E); • <S, σ> → <S’, σ’> tranzakció nem létezik. A holtpont virtuális állapot jele: 4. Az S program a σ állapotból holtpontra juthat, ha létezik olyan kiszámítás, amely holtpont konfigurációban végz˝odik. Az S program holtpontmentes, (p mellett) ha nem létezik olyan σ állapot p(σ) = "true" mellett, amelynél S holtpontra juthat. Az S párhuzamos program szemantikája: Parciális helyességi szemantikája σ kiindulási állapot mellett: M[S](σ) = { τ | < S, σ > → . < E, τ > } Gyenge teljes helyességi szemantikája σ kiindulási állapot mellett: Mwtot [S] (σ) = M[S](σ) ∪ { ⊥ | S divergál σ kezd˝o állapotból } Teljes helyességi szemantikája σ kiindulási állapot mellett: Mtot [S] (σ) = Mwtot [S] (σ) ∪ { 4 | S holtpontba jut σ kezd˝o állapotból } ( ⊥, 4, fail ∈ Σ virtuális állapotok)
6.4. P(s), V(s) utasítások: kölcsönös kizárás megoldása. 6.20. Definíció (Probléma): Adott egy er˝oforrás, amelyet n > 0 db folyamat használ feladatainak megoldása során. Követelmények • Kölcsönös kizárás Az er˝oforrást egy adott id˝opontban legfeljebb csak egy folyamat használhatja.
6
• Blokkolás mentesség A párhuzamos folyamatok futását a szinkronizáció ne függessze fel végtelen hosszú id˝ore. • Er˝oforráshoz való hozzáférhet˝oség Minden egyes folyamat, ha használni akarja az er˝oforrást, akkor véges id˝on belül használhassa azt. A követelmények formális megfogalmazása S : inicializálás; parbegin S1 || ... || Sn parend; ahol ∀ i, k, 1 ≤ i, k ≤ n ∧ i 6= k esetén [( var(N Ki ) ∪ var(EHi ))] ∩ [( var(EIk ) ∪ var(EFk ))] = { } (az el˝okészítés és er˝oforrás használatának változói különböznek az igénylés és a felszabadítás változóitól) Feltevés N Ki és EHi nem tartalmaz o˝ rfeltételes utasítást. Elnevezések • NK Nem közös változókat használó programrész • EI Er˝oforrás igénylés • EH Er˝oforrást használó programrész • EF Er˝oforrás felszabadítása Kölcsönös kizárás, blokkolás-mentesség: 6.21. Definíció (Kölcsönös kizárás): Az S végrehajtása során nem létezik olyan < parbegin R1 || ... | Rn parend, σ > konfiguráció, hogy valamely j, k ∈ {1, ..., n}, j 6= k esetén Rj ≡ at(EHj in Sj ); Rk ≡ at(EHk in Sk ) 6.22. Definíció (Blokkolás-mentesség): Nincs olyan végrehajtás σ ∈ Σ: <S, σ> → * amely holtpont konfigurációban végz˝odik. 6.23. Definíció (Dijkstra féle kölcsönös kizárás): S : out ← True; parbegin S1 || ... || Sn parend; P : passeren V : vrijgeven Szemaforral: s ← k; k > 0; P(out) ≡ await out then out ← False ta; V(out) ≡ out ← True; P(s) ≡ await s > 0 then s ← s - 1 ta;
7
out ∈ bool;
6.5. Termel˝o fogyasztó modell. Megállapodás. Formális meghatározás. Absztrakt megoldás. Realizáció. Termel˝o-fogyasztó modell - A probléma absztrakt megfogalmazása: Adott egy N ≥ 1 kapacitású közös tároló. Adott a folyamatok két csoportja, amelyek a tárolót használják. n ≥ 1 termel˝ofolyamat, m ≥ 1 fogyasztó folyamat. A termel˝o a tároló használatakor egy-egy terméket helyez el a tárolóban. A fogyasztó a tároló használatakor egy-egy terméket vesz ki a tárolóból. Termel˝o és fogyasztó közötti sorrendiség: A fogyasztó ugyan abban a sorrendben veszi ki a termékeket a tárolóból, amilyen sorrendben a termel˝o azt lehelyezte. Termel˝ofolyamatok közötti kölcsönös kizárás: A termel˝ofolyamatok közül egyszerre csak egy folyamat használhatja a tárolót. Fogyasztó folyamatok közötti kölcsönös kizárás: A fogyasztó folyamatok közül egyszerre szintén csak egy folyamat használhatja a tárolót. Termel˝ok és a fogyasztók közötti termék esetében példányonkénti kölcsönös kizárás: Ugyanazt a termék példányt a termel˝onem helyezheti el, a fogyasztó pedig nem veheti ki egyszerre. A megállapodás formális megfogalmazása Tároló: q ∈ sor, length(q) = N, N ≥ 1 Termel˝omuveletei: ˝ x ← a[i]; ; i = 0, ..., M - 1 Fogyasztó muveletei: ˝ <(q,y) ← (rem(q), read(q))}; b[j] ← y; j = 0, ..., M - 1 A sorrendiségi követelmények teljesülnek! i ← 0 ; j ← 0; { ( i, j ∈ integer) ∧ q ∈ queue ∧ 0 ≤ length(q) ≤ N ∧ ( a[0, M -1], b[0, M -1] ∈ vector) ∧ M ≥ 1 ∧ N ≥ 1 } parbegin producer || consumer parend; producer: w h i l e i < M do x <− a [ i ] ; wait l e n g t h ( q ) < N t a ; ; i <− i + 1 ; od ;
8
Consumer: w h i l e j < M do wait l e n g t h ( q ) > 0 t a ; <( y , q ) <− ( read ( q ) ,
rem ( q ) ) > ;
b [ j ] <− y ; j <− j + 1 ; od ; A kölcsönös kizárások teljesülnek. Megvalósítás - Realizáció: q buffer[0...N-1] ciklikus elhelyezéssel mod(N) Behelyezésnél az index: in Kiemelésnél az index: out El˝ofeltétel: M ≥ 1 ∧ N ≥ 1 Inicializálás: i ← 0; j ← 0; in ← 0; out ← 0; S program: parbegin producer || consumer parend; {( ∀ k, 0 ≤ k < M)(a[k] = b[k])}; wait length(q) < N ta: q ← add(q,x):
wait in - out < N ta; buffer[in mod N] ← x; in ← in + 1;
wait length(q) > 0 ta:
wait in - out > 0 ta;
(y,q) ← (read(q), rem(q));
y ← buffer[out mod N]; out ← out + 1;
producer: w h i l e i < M do x <− a [ i ] ; wait in − out < N t a ; < b u f f e r [ i n mod N] <− x ; i n <− i n + 1 >; i <− i + 1 ; od ; consumer: w h i l e j < M do wait in − out > 0 t a ; < y <− b u f f e r [ o u t mod N ] ; o u t <− o u t + 1> b [ j ] <− y ; j <− j + 1 ; od ;
9
6.6. Er˝oforrás közös használatának problémája. Kiéheztetés, monopolizálás. 6.24. Definíció (Informális leírás): Adott egy S : parbegin S1 || ... || Sn parend párhuzamos rendszer és egy e er˝oforrás. Az e er˝oforrás felhasználási módjai • A folyamatok egy csoportjának tagjai csak kizárólagosan használhatják az er˝oforrást. • A folyamatok egy másik csoportjának tagjai egyidej˝uleg akárhányan is használhatják az er˝oforrást. • A két csoport tagjai vegyesen nem használhatják az er˝oforrást. Probléma • Er˝oforrás monopolizálása, • Kiéheztetés Kiéheztetés, monopolizálás: Adott egy S: parbegin S1 || ... || Sn parend párhuzamos rendszer. 6.25. Definíció (Informális definíció: Kiéheztetés): a párhuzamos program végrehajtása nem fejez˝odik be, mert a folyamatok egy csoportja monopolizálja a párhuzamos rendszer közös er˝oforrását. 6.26. Definíció (Informális definíció : Er˝oforrás monopolizálása):
a párhuza-
mosan futó folyamatok között mindig van legalább egy olyan folyamat, amely lekötve tartja az er˝oforrást, miközben a velük párhuzamos folyamatok nem üres csoportjának tagjai folyamatosan várakoznak az er˝oforrásra. Lehetséges állapotok: : er˝oforrást használók; er˝oforrásra várakozók; lefutottak.
6.7. Kiéheztetés mentes vezérlés szinkronizációs problémája. Példa: adatbázis modell.(Két kapus megoldás.) 6.27. Definíció (Kiéheztetés-mentesség): Adott egy er˝oforrás, n ≥ 3 folyamat, amelyek az er˝oforrást használják, és egy párhuzamos rendszer p(σ) el˝ofeltétele. A folyamatok legalább két diszjunkt csoportot alkotnak:
10
Csoportok között teljesül a kölcsönös kizárás: Egy adott id˝opontban különböz˝ocsoporthoz tartozó folyamatok az er˝oforrást nem használhatják. Csoporton belüli közös használat: Létezik legalább egy olyan csoport, amelyben a folyamatok egy adott id˝opontban többen is használhatják az er˝oforrást. Kiéheztetés-mentesség: Ne fordulhasson el˝oaz, hogy az egyik csoportbeli folyamatok végtelen hosszú ideig várnak az er˝oforrásra, a másik csoport folyamatai közül mindig van legalább egy olyan, amely lekötve tartja azt. A rendszer formális megfogalmazása végtelenített rendszer esetén: S: inicializálás ; parbegin S1 || ... || Sn parend; n ≥ 3. ahol ∀ i, k, 1 ≤ i, k ≤ n ∧ i neq k -ra: [ változó (N Ki ) ∪ változó (EHi ) ] ∩ [ változó(EIk ) ∪ változó(EFk ) ] = { } Feltevés: N Ki és EHi nem tartalmaz megvárakoztató utasítást. Si Folyamatok szerkezete: w h i l e B do NKi : Nem k r i t i k u s s z a k a s z ; EIi :
E r o˝ f o r r á s i g é n y l é s e ;
EHi :
E r o˝ f o r r á s h a s z n á l a t a ;
EFi :
E r o˝ f o r r á s f e l s z a b a d í t á s a ;
od ; Kiéheztetés-mentesség feltételei, Holtpont-mentesség feltételei: Formális megfogalmazás: Legyen adott a párhuzamos rendszer p(σ) el˝ofeltétellel egy, a folyamatok által közösen használt er˝oforrás. A folyamatok két csoportot alkotnak. Legyenek az A csoport folyamatainak azonosítói: 1, 2, ..., n1 n1 ≥ 2. Legyenek a B csoport azonosítói: n1 +1, n1 +2, ... , n; n ≥ 3. A csoportok közötti kölcsönös kizárás: Nem létezik olyan < parbegin R1 || . . . || Rn parend , σ> konfiguráció, amelyre valamilyen i ∈ { 1, ... , n1 } és k ∈ { n1 +1, ... , n } esetén Ri ≡ at(EHi in Si ) és Rk ≡ at(EHk in Sk ).
11
Csoporton belüli közös használat: Adott p(σ) mellett létezhet olyan < parbegin R1 || ... || Rn parend , σ> konfiguráció, amelyre Ri ≡ at(EHi in Si ) és Rk ≡ at(EHk in Sk ), ha i, k? 1, ... , n1 Végtelen igénylés: Adott p(σ) mellett nem létezik olyan < parbegin R11 || . . . || Rn1 parend , σ1 > → < parbegin R12 || . . . || Rn2 parend , σ2 > → ... végtelen végrehajtási sorozat, ahol minden < parbegin R1i || . . . || Rni parend , σi > konfiguráció esetén (∼ ∃ i ∈ {1, ..., n1 } ∧ ∼ ∃ k ∈ {n1 +1,..., n})( Rji ≡ at (EHj in Sj ) ∧ Rk ≡ at(EIk in Sk )) Holtpont-mentesség: Adott p(σ) mellett a párhuzamos program végrehajtása nem végz˝odik holtpont állapotban: 4 ∈ / M(S)[p] Példa : Adatbázis modell: Készítsük el az adatbázis egy absztrakt modelljét a következ˝o specifikáció alapján, majd végezzük el a modell tulajdonságainak elemzését a kiéheztetés-mentesség szempontjából. Legyen n > 0 felújító és m > 1 lekérdez˝ofolyamat. A felújító folyamatok egymással, valamint a lekérdez˝ofolyamatokkal is kölcsönös kizárásban vannak az adatbázis használatakor. A lekérdez˝ofolyamatok egyszerre többen használhatják az adatbázist. Megoldás: A lekérdez˝ofolyamatok számolják, hogy hányan használják az adatbázist egyidej˝uleg. • Számláló: rcnt, kezd˝oértéke: 0, (számláláshoz kölcsönös kizárás kell) • Szemafor: sr, kezd˝oértéke: 1 • Kölcsönös kizárás szemaforja: w Példa: w ←1; rcnt ←0; sr ←1; parbegin writer1 || ... || writern || reader1 || ... || readerm parend; writeri : w h i l e " t r u e " do 12
I n f o r m á c i ó g y u˝ j t é s ; P (w ) ; Adatbázis f e l ú j í t á s ; V(w ) ; od ; readerk w h i l e " t r u e " do P( sr ); r c n t $ \ l e f t a r r o w $ r c n t +1; i f r c n t = 1 t h e n P (w) f i ; V( s r ) ; Adatbázis lekérdezés ; P( sr ); rcnt $ \ leftarrow$ rcnt − 1; i f r c n t = 0 t h e n V(w) f i ; V( s r ) ; Válasz k i é r t é k e l é s e ; od ; Követelmények: • A reader és a writer folyamatnak is legyen esélye hozzáféRn i az adatbázishoz. • A writer folyamatok ne monopolizálhassák az adatbázist. • A reader folyamatok ne monopolizálhassák az adatbázist. Megoldás: • A writer folyamatok továbbra is egy kapun keresztül léphetnek be az er˝oforráshoz, ahova akadály nélkül eljuthatnak, de belépéskor lezárják a küls˝okaput a reader folyamatok el˝ott. • A reader két kapun keresztül léphet be az er˝oforráshoz. A küls˝okaput a writer nyitja ki a reader el˝ott a felújítás befejeztekor, amikor megkezdi az er˝oforrás elengedését. • A bels˝okapu közös, ezért a writer és a reader egyforma eséllyel léphet be az er˝oforráshoz.
13
• Ha felújító folyamat használni akarja az adatbázist, akkor újabb lekérdez˝ofolyamat már ne férhessen az adatbázishoz. • Szemafor: who ∈ w, r , kezd˝oértéke: w w ← 1; sr ← 1; rcnt ← 0; r ←1; who ← w; parbegin writer1 || ... || writern || reader1 || ... || readerm parend;
w h i l e " t r u e " do I n f o r m á c i ó g y u˝ j t é s ; who $ \ l e f t a r r o w $ w; P (w ) ; Adatbázis f e l ú j í t á s ; a w a i t " t r u e " then V(w) who $ \ l e f t a r r o w $ r ta ; od ; w h i l e " t r u e " do w a i t who = r tw ; P( sr ); r c n t <− r c n t + 1 ; i f r c n t = 1 t h e n P (w) f i ; V( s r ) ; Adatbázis lekérdezés ; P( sr ); r c n t <− r c n t − 1 ; i f r c n t = 0 t h e n V(w) f i ; V( s r ) ; Válasz k i é r t é k e l é s e ; od ;
14
