AFDELING DER ELEKTROTECHNIEK TECHNISCHE HOGESCHOOL EINDHOVEN Vakgroep Meten en Regelen (ER) E.:;,DHC'{::fFi
~~Ttr~;L~:"B~ l:'~~i::~:~ .~. ~ ,LL';"
j
i" • ":.,;,,,t~"~l< ; . ~.
i~,,>,.._,,,,,,,,,,,,-,,,=,,",-,,,,,,,.,~,,,~--~,,,,,••,"";""~(;"~~~~J,
MODELERING VAN EEN RECOVERYACTIE IN EEN
T~~SACTIE
GEORIENTEERD SYSTEEM door C.J. Kreijns
Verslag van het afstudeerwerk uitgevoerd van oktober 1981 tim december 1982 in opdracht van prof.
~r.
F.J. Kylstra
onder begeleiding van
~r.
V.F. Nicola
De afdeling der elektrotechniek van de Technische Hogeschool Eindhoven aanvaardt geen verantwoordelijkheid voor de inhoud van Stage- en Afstudeerverslagen.
I
Voorwoord De laatste jaren is er een groeiende belangstelling waarneembaar voor informatie systemen welke geimplementeerd zijn in een computer-systeem. Deze belangstelling is niet ongegrond omdat een computer vele voordelen biedt waaronder: ~ het is mogelijk om grote hoeveelheden informatie op te slaan in een relatief kleine ruimte. ~ informatie is snel op te halen in een vorm die men wenst. ~ modificaties op de gegevens is op eenvoudige wijze realiseerbaar. ~ meerdere mensen kunnen "gelijktij dig" toegang hebben tot dezelfde gegevens. ~ toegang tot de gegevens is plaatsonafhankelijk mits men verbinding met het computer-systeem heeft. ~ de hoge betrouwbaarheid van de gegevens en de verwerking ervan. Om die hoge betrouwbaarheid te garanderen zijn in het informatie systeem faciliteiten ingebouwd welke tot doel hebben redundantie in het systeem te brengen. Van deze redundantie kan in hat geval dat het systeem onbetrouwbaar raakt gebruik worden gemaakt. Een vraag die hier naar voren komt is op welke wijze daze redundantie dan weI moet worden verkregen en hoe die redundantie n~oet worden gebruikt. Vaak wordt een checkpoint-rollback-recovery mechanisms toegepast. Checkpointing houdt in dat periodiek informatie zal I.Licrden verzameld welke de bedoelde redundantie in het systeem brengt. Hoe vaak checkpointing gedaan moet worden is een praktische vraag die evenwel tot op heden onvoldoende is beantwoord, maar waarnaar vesl onderzoek wordt gedaan. Binnen dit kader speelt zich het promotie-onderzoek af van mijn coach, ir. V.F. Nicola. Oit onderzoek heeft tot doel om op b~vengenoemde vraag een afdoend antwoord te geven, waarbij dan transactie georienteerde systemen worden beschouwd. Mijn afstudeerwerk omvat een gedeelte van zijn onderzoak, namelijk de validatie van een van de ontwikkelde mathsmatische modellen. Validatie houdt in dat het mathematisch model moet worden vergelaken met een bestaand transactie georienteerd systeem. Omdat een bsstaand transactie georienteerd systeem niet voorhanden is is een computeC'-simulatie van een transactie georienteerd systeem geconstrueerd.
II
Samenvatting Een hypothetisch transactie georienteerd systeem ondersteund met checkpointing en recovery faciliteiten wordt beschouwd. Oit systeem, dat checkpoint-rollback-recovery (=CRR)-systeem zal worden genoemd, is onderhevig aan fouten die poisson verdeeld arriveren. De recoveryduur na een fout wordt gelijk genomen aan de gemeten busytijd sinds hat laats genomen checkpoint. De gedachte die hieraan ten grondslag ligt is dat in werkelijke systemen transacties op de audit trail in een recovery-actie opnieuw verwerkt worden. In het CRR-systeem wordt aangenomen dat het opnieuw verwerken van de transacties even lang duurt als toen deze voor de eerste keer werden verwerkt. Het is vooralsnog niet mogelijk geweest het CRR-systeem in een mathematisch model te representeren. De moeilijkheid ligt in het feit dat de totale gemeten busytijd sinds het laatst genomen checkpoint onthouden moet worden. Om tach uitspraken over het CRR-systeem te doen is hiermee een Markovmodel geassocieerd. oit model is een M/M/1 -systeem, waarbij de volgende vier veronderstellingen met betrekking tot de recovery-duur in het CRR-systeem zijn gemaakt: 1. De distributie van de recovery-duur is exponentieel. 2. De gemiddelde recovery-duur. is k maal de gemiddelde intercheckpaint-tijd. k is een constante. 3. De recovery-duur is onafhankelijk van het interval waarin die busytijc is gemeten. 4. De recovery-duren zijn onderling onafhankelijk. Met een simuI3':ieprogramma, waarin het CRR-systeem is geimplementeerd, is nagegaan in hoeverre de veronderstellingen juist zijn. Het eigenlijke validiteitsonderzoek houdt in dat onderzocht moet worden: 1. In hoeverre de availability, berekend met behulp van het Markov-model, overeenkomt met de availability in het CRR-systeem. 2. Idem, maar dan voor de gemiddelde queuelengte. Met hetzelfde simulatieprogramma zijn de gemiddelde queuelengte en de availability gemeten. De berekende en de gemeten waarde worden met elkaar vergeleken.
Inhoud
III
Vaarwoord ••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••• ! Samenvatting ••••••••••••••••••••••••••••••••••••••••••••••••••••••••• ~ .•• II Inhoud•••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••• I I I
Hoofdstuk 1: Inleiding 1.1. Checkpainting & Recovery ••••••••••••••••••••••••••••••••••••• 1 1.2. Prableemgebied ••••••••••••••••••••••••••••••••••••••••••••••• 2 1 .3. Opzet van dit verslag •••••••••••••••••••••••••••••••••••••••• 2 Hoofdstuk 2: Een Markov-model 2.1. Inleiding •••••••••••••••••••••••••••••••.•.•••••••.•••••••••• 4 2.2. Hat Markav-model ••••••••••••••••••••••••••••••••••••••••••••• 4 Hoofdstuk 3: De distributie van de intercheckfailure-tijd. 3.1. Inleiding ••••••••.•••••••.••••••.••••••••.•••.••••••••••••••• 7 3.2. Bepaling van de distributie van de intercheckfailuretij d. 3.2.1. De berekening:Algemeen ••••.•••••.••••••••••••..••••••• 7 3.2.2. Overzicht van de berekende distributie van de intercheckfailure-tij d•••••.•.••.•••••.•••••..•••••••• 9
Het algol Simulatieprogramma llIntercheckfailure-tij d". 3.3.1. Inleiding ••••••••••••••.••••••••••.••••.•..•.••.••••• 11
3.3.2. Het simulatieprogramma: 3.3.3. Het simulatieprogramma: 3.3.4. Het simulatieprogramma: 3.3.5. Het simulatieprogramma: 3.4. De simulatie.
de de de de
kern •••••••••••••••••••••• 11 statistiek •••••••••••••••• 12 frequentieverdelingen ••••• 12 procedures •••••••••••••••• 13
3.4.1. Inleiding •••••••••••••.••••••••.•.•••.•••••••••••••.• 15 3.4.2. Voarbereiding .••••••.••••••.••••••••••..•••••••.••••. 15 3.4.3. Simulatieresultaten ••••.•.••••••••.•••••••.•••••••••• 16 Hoofdstuk 4: Validatie van het Markov-model met C/=01/ J<. en lfi . 4.1 • Inleiding •••••••••.••••••••••••••••.••••••••••••••.•.••••••• 17
k::t
4.2. Het f'larkov-model met ,/~o(/J<,;
hj/fi.
4.2.1. Inleiding ••••••••••••••••••••••••••.•••.••••••••••••• 21
4.2.2. Het ergodiciteitsonderzoek. 4.2.2.1. Inleiding ••••••••••••••••••••••••••••••••••• 22
4.2.2.2. De ergodiciteitseis••••••••••••••••••••••••• 22 4.2.2.3. De ergodiciteitseis in het {a";f)-vlak••••••• 22 4.2.2.4. Bepaling van de ergodiciteitsgrenzen -J - , -1 23 ~ L. .J c< A .e,N1 4.2.3. De availability R k (fX,f)' 4.2.3.1. Het maximum Van availability indien fl :::::constant en indien 01. :::::constant•••••••• 23 4.2.~.2. De ~~~A -lijn en de availability-nullijn •••• 24
to ..............................
4.2.4. Over1ge •••••••••••••••••••••••••••••••••••••••••••••• 24
4.3. Het CRR- simulatieprogramma. 4.3.1. Inleiding •••••••••••••••••••••••••••••••••••••••••••• 29
4.3.2. De kern van het CRR-simulatieprogramma. 4.3.2.1. Inleiding ••••••••••••.•••••••••••••••••••••• 29
4.3.2.1. Implementatie van de kern ••••••••••••••••••• 3D 4.3.3. Het verzamelen en verwarken van de statistiek. 4.3.3.1. Inleiding ••••••••.•••••••.•••••••••••••••••• 33 4.3.3.2. De statistiek van het voor~nderzoek ••• 33 4.3.3.3.. Meting van ·de availabill ty en de queue lengte •••••••••••••.••••• , ••.••••••••••••••• 39
IV
4.3.3.4. Meting van de k-waarde tijdens een sample-points ••••••••••••••••.••••••••••••• 39 4.3.4. De procedures en de presentatie van de statistiek. 4.3.4.1. De procedures•••••••••••••••••••••••••••••• 42 4.3.4.2. De presentatie van de gegevens ••••••••••••• 43 4.3.4.3. Invoer van de parametar-waarden •••••••••••• 44 4.4. De simulatie •. 4.4.1. De voorbereiding •••••••••••••••••••••••••••••••••••• 46 4.4.2. De meetgegevens & bespreking daarvan. 4.4.2.1. Meetgegevens betreffende de aangenomen veronderstellingen in hat Markov-model ••••• 47 4.4.2.2. Meetgegevens betreffende queuelengte en availabity ••••••••••••••••••••••••.••••• 62 4.4.2.3. Conclusies••••••••••••••••••••••••••••••••• 63 Literatuurlijst•••••••••••••••••••••.•••••••••••••.••.••••••••••••••••••• 65 Appendix A••••••••••••••••••••••••••••••••••••••••••••.•••••••••••.•••••• 66
1
Hoofdstuk 1: Inleiding .1
Checkpointing & Recovery Een veel toegepaste methode om de integriteit van transactie-georienteerde systemen te verhogen is om op zekere tijdstippen - checkpoints genoemd relevante informatie betreffende het systeem te verzamelen en deze op te slaan in een secondary storage device zoals b.v. een disk of een tape.In het geval dat een fout het systeem onbetrouwbaar maakt,moet de opgeslagen informatie voldoende zijn om te waarborgen dat terug gegaan kan worden naar het punt waar die informatie is verzameld om vandaar uit opnieuw te starten. Vaak houden de transactie-georienteerde systemen een lUst bij waarop de transacties vermeld staan die sinds het laatst genomen checkpoint verwerkt zijn.Deze lijst wordt meestal journal file,image log of audit trail genoemd. Zodra een fout wordt gedetecteerd zal een recovery operatie worden gestart. Een recovery operatie omvat aIle acties welke ondernomen moeten worden om de status van het systeem te herstellen tot op het moment waar de fout optrad.We spreken daarom ook weI van een recovery-actie.Samenvattend zijn de acties in volgorde: 1. aIle binnenkomende transacties worden in een queue geplaatst. 2. indien nodig moet de foutenoorZqak worden gerepareerd. 3. de status van het systeem wordt hersteld tot op het moment waarop h~t laatste checkpoint is genomen door middel van de op dat checkpoint verzamelde informatie. 4. aIle transacties welke op de audit trail staan vermeld worden opnieuw verwerkt.Is dit proces afgelopen dan is de status van het systeem hersteld tot op het moment waarop de fout optrad en is de recovery-actie beeindigd.Alle acties die in de queue staan worden nu verwerkt. We nemen aan dat gedurende een checkpoint of recovery-actie geen transacties verwerkt kunnen worden. Omdat in de recovery-actie aIle transacties die op de audit trail vermeld staan opnieuw worden verwerkt zal de recovery-duur - dit is de tUd welke gespendeerd wordt aan de recovery-actie - in hoge mate afhankelijk zUn van de tijd tussen het laatst genomen checkpoint en het moment waarop de fout is opgetreden.Immers hoe langer dit interval duurt,des te meer transacties genoteerd zullen worden op de audit trail. Hoe groter de gemiddelde interval tussen twee checkpoints des te meer tUd zal het systeem spenderen aan het uitvoeren van een recovery.actie.Andersom, hoe korter het gemiddelde interval tussen twee checkpoints duurt,des te meer tijd zal het systeem spenderen aan het uitvoeren van een checkpoint. Het is duidelijk dat er een optimaal interval bestaat tussen twee checkpoints. Om dit optimum interval te berekenen moet er een wiskundig model geconstrueerd worden die het beschouwde transactie systeem zo nauwkeuriQ mogelUk representeerd binnen de conditie dat aIleen die essentiale aspecten in rekening moe ten warden gebracht die de bepaling van dat optimum interval in belangrijke mate beinvloeden.Alle aspectsn beschouwen maken het model aIleen maar gecom liceerder en vaak onhanteerbaar.
2
J.W. Young lit.3 en K.~'. Chandi lit.4 hebben reeis modellen geconstrueerd waarmee een constant optimum interval tussen de checkpoints te berekenen is. Het optimum interval is berekend door de availability te maximaliseren. De avilability is de fractie van de tUd waarin het systeem beschikbaar is voor het verwerken van transacties.Het grote nadeel van hun modellen is dat queueing van transacties niet in rekening zUn gebracht. queueing van transacties wordt weI in het model van E. Gelenb~ lit.6 in rekening gebracht.In dit stochastisch model wordt een exponentials verdeling van de intercheckpoint-tijd verondersteld.Door de availability te maximaliseren of door de gemiddelde responstUd van een transactie te minimaliseren wordt een optimaal gemiddelde interval tussen de checkpoints bepaald.De responstUd is de verblijftUd van een transactie in het systeem.Het model van E. Gelenb~ is door V.F. Nicola lit.1 uitgebreid door in het model ook toestandsafhankelUke parameters te introduceren.Queueing van transacties wordt beperkt door de introductie van een eindige wachtruimte • •2
Probleemgebied Hoewel men veronderstelt dat de geconstrueerde modellen in meerdere of mindere mate een realistische representatie van bestaande transactie-systemen zUn,is nooit nagegaan inhoeverre dit ook zo is.Een bestaand transactie-systeem zal onderzocht moeten worden. Door middel van metingen zal moeten worden nagegaan of de veronderstellingen welke voor het model gemaakt zUn inderdaad juist zUn.En of de met het model berekende performance variabelen overeenkomen met de gemeten waarden. Vaak zal echter - zoals in het onderzoek dat voIgt - geen bestaand systeem voorhanden zUn zodat naar een tussenoplossing moet worden gezocht. In dit verslag zal als tussenoplossing een hypothetische systeem worden geintroduceerd.oit hypothetisch systeem is voorzien van checkpointing en recovery faciliteiten.Het systeem zal een checkpointing-rollback-recovery (= CRR ) systeem worden genoemd. Overeenkomstig het principe dat transacties vermeld op de audit trail in een recovery-actie opnieuw verwerkt zullen worden,zal in het CRR-systeem de recovery-duur gelUk worden genomen aan de totale gemeten verwerkingsduur van de transacties welke gearriveerd zUn na het laatst genomen checkpoint. oi t laatste vereist dat in het CRR-systeem een geheugen aanwezig moet zijn die die verwerkingsduur opslaatooeze geheugenfunctie belemmert de formulering van een mathematisch model.Om toch inzicht in de gedragingen van het CRR-systeem te verkrUgen wordt hiermae een Markov-model geassocieerd.Dit Markov-model is een M/M/1-systeem,onderhevig aan fouten die poisson verdeeld arriveren. De vraag rijst nu in hoeverre di t l"larkov-model een goede representatie is van dit hypothetisch systeem. De beantwoording van deze vraag vormt het onderwerp van dit verslag •
•3
Opzet van dit verslag Het bovengenoemde i'larkov-model is gebaseerd op hat f'larkov-model dat ui tvoerig is behandeld in lit.1 oit Markov-model zal in het volgende hoofdstuk globaal worden behandeld.Formules voor de availability en de queuelengte worden gegeven. In het CRR-systeem speelt de distributie van tUd tussen het laatst genomen checkpoint en het moment waarop een fout optreedt een grate role
3
In hoofdstuk 3 zal deze distributie worden gegeven voor 4 verschillende distributies van de tUd tussen de checkpoints. Hoofdstuk 4 behandelt het CRR-systeem en het Markov-model dat ermee is geassocieerd.Het CRR-systeem is getmplementeerd in sen CRR-simulatieprogramma. Meetresultaten verkregen uit het CRR-simulatieprogramma worden vergeleken met de berekende waarden.En tenslotte zullen conclusies worden getrokken.
4
Hoofdstuk 2: [en Markov-model .• 1
Inleiding Het Markov-model,welke in dit hoofdstuk wordt geintroduceerd,is uitvoerig behandeld in lit.1 Derhalve zal in dit hoofdstuk alleen de voor het onderzoek relevante zaken worden behandeld. Het Markov-model kent twee tijdassen~ 1. de aVailable-tijdas:op de available-tijdas spelen checkpoint- en recovery duur geen rol. 2. de absolute-tijdas :op de absolute-tijdas spelen checkpoint- en recovery duur wel een rol. In het Markov-model vinden processen op beide tijdassen plaats. lie figuur 2.1 (a) en (b) figuur 2.1 (a) checJcpt>ln.cservice au.....,.
ab~-b~ _--I~~
-{
F
awitable.~
I I
I
)---~(
figuur 2.1 (b)
... :
I,,. I'
C
~,---_F-}-----{D---. i"IIII
"i
ina:JtI&y-dl.4A.lr i
~
~.2
Het Markov-model Het hier beschreven Markov-model is een representatie van een M/M/1-systeem onderhevig aan poisson verdeelde interrupts. Het model heeft drie basistoestanden waarin het systeem zich kan bevinden. In mode a is het systeem "available" d.w.z.het systeem kan transacties verwerken. - In mode C is het systeem bezig met het nemen van een checkpoint. In mode ~ is het systeem bezig met aen recovery-actie. Om het aantal transacties in het systeem aan te geven (wachtend of in uitvoering) is elk van de basistoestanden onderverdeeld in n+1 deeltoastanden, waarin n het maximale aantal transacties voorstalt dat het systeem kan bevatten. Zie figuur 2.2
5
figuur 2.2 ",-1-
A ;
~-; d-~ -i ~
;
t'~ qP-~
gemiddelde tUd tussen twee transacties gemiddelde processing tUd van de transacties gJ.dddelde intercheckpointtUd gemiddelde checkpointserviceduur gemiddelde tUd tussen twee failures gemiddelde recovery duur
Uit dit model zien we dat:
-
transacties in de absolute tijd poisson verdeeld arriveren. transacties in de available-tUd worden verwerkt. fouten in de available-tijd poisson-verdeeld arri veren. checkpoints in de available-tUd poisson-verdeeld arriveren. het nemen van de recovery-actie in de absolute-tijd gebeurt. het nemen van een checkpoint in de absolute-tUd gebeurt.
Doordat zowel checkpoints als fouten in de available-tUd poisson verdeeld arriveren zullen nooit checkpoints kunnen arriveren als het systeem bezig is met checkpointing. checkpoints kunnen arriveren als het systeem bezig is met een recoveryactie. fouten kunnen arriveren als het systeem bezig met checkpointing. fouten kunnen arriveren als het systeem bezig is met een recovery-actie. De volgende performance variabelen zUn in lit.1 bestudeerd: • system utilization. De system utilization U is de kans dat het systeem niat idle is,d.w.z.hoewel available,zUn er geen transacties om verwerkt te worden.
u
~ i- p(a~o)
• system availability. De system availability bU A is de kans dat het systeem beschikbaar is voor het verwerken van transacties
A=
z: tV
L=-O
p(a~i)
6
~ het gemiddelde aantal transactias in hat systeam
~ de gemiddelde responstUd van san transactie
R=N/A LlaUe.) indian
n~OQ
dan geldt:
R
tv
7
HOOFDSTUK 3: De distributie van de intercheckfailure-tijd 3.1
Inleiding: De intercheckfailure-tijd is de tijd gemeten tussen het laatst genomen checkpoint en sen failure point.De distributie van de intercheckfailure-tUd is afhankelijk van: 1. De distributie van de aankomsten van de failurepoints. 2. De distributie van het tUdsverloop tussen checkpoints. De distributie van de intercheckfailure-tijd zal analytisch worden berekend in het geval dat de distributie van het tijdsverloop tussen de checkpoints: 1. Deterministisch is. 2. Exponentieel verdeeld is. 3. Erlang-2 verdeeld is. 4. Hyper-2 verdesld is. In aIle gevallen zal de distributie van de aankomsten van de failurepoints poisson verdeeld worden verondersteld. Vervolgens wordt middels een Algol-simulatie programma gekeken of een simulatie de analytisch berekende distributie van de intercheckfailurepoint-tijd ondersteund. Dit hoofdstuk valt daarom in drie gedeelten uiteen: 1. Hat analytisch gedeelte. Hierin wordt aangegeven hoe de berekening voorde distributie van de intercheckfailure-tijd verloopt. De resultaten worden in sen overzicht gegeven. 2. Bespreking van het Algol-simulatieprogramma. 3. De simulatie zelf. Resultaten worden besproken.
3.2
Bepaling van de distributie van de intercheckfailure-tijd
3.2.1
De berekening: Algemeen De berekening kan in de volgende stappen worden genomen: 1. Berekening van de kans op precies n-failurepoints in een intercheckpointinterval.De tijd tussen twee checkpoints wordt aangeduid met ict (= intercheckpoint-tijd) • 00
QO
PLn=n.L:!P[n=I'l, Lct:b] = jP[tJ=nli.cl:=tlP[M=/;] 1:.0
= CaO
j
00
(ftf~;.1/.-
;t J:
f
1:.0
p[ Lct= b]
•
immers de aankomsten van de failurepoints is poisson-verdeeld. Afis het gemiddeld aantal failurepoints per tijdseenheid. 2. Barekening van de distributie h".+1.(l:). De verdelingsfunctie hnt 1. (tJ geeft de verdeling van de tijd gemeten tussen het laatst genomen checkpoint en de (n+1)-ste failurepoint.
8
waarbU ~+1een evenredigheidsconstante is,zodanig gekozen dat:
o
/i".< Cll
d/;
=i
Rekening houdende dat de aankomstverdeling van de failurepoints poisson-verdeeld is,levert dit:
3. Berekening van de kans ~n+1 pn+1 is als voIgt gedefinieerd:
j3n+1= De interpretatie vanj3nt1wordt in de volgende berekeningsstap gegeven. 4. Berekening van de distributie van de intercheckfailuretUd. Deze distributie wordt aangeduid met .i1(t) • !2~)duidt de kans aan om op tijdstip ~=t een failurepoint aan te treFfen,waarbij het niet ter zake doet of het een eerste,tweede, ••• ,n-de, (n+1)-ste failurepoint is. De kans om op tijdstip ~=t een (n+1)-ste failurepoint aan te treffen is gegeven door~n~~Ct),op voorwaarde dat er minstens n+1 failurepoints aanwezig zijn. De kans om de verdelingsfunctie hflH (I:) te selecteren wordt nu gegeven doorj3"+L welke de genormaliseerde kans is op minstens n+1 failurepoints: 00
L
n=O
j3n..+L
=i
De kans om op tijdstip dus:
~=t
een (n+1)-ste failurepoint aan te treffen is
en dus is: QO
n Cn = L.
'1'l=0
f3n.~L
An.H (~)
5. Berekening van het gemiddelde aantal failurepoints tussen twee checkpoints: 00
m. =
L:
f'L.=o
/Y1..
7'[ trl:- = n.]
9
.2.2
Overzicht van de berekende distributie van de intercheckfailure-tijd Definieer: ~V= de distributie van de intercheckpoint-tijd t~ = de gemiddelde intercheckpoint-tijd. J1(~)= de berekende distributie van de intercheckfailure-tijd. ~= de gemiddelde intercheckfailure-tijd. n = het gemiddeld aantal failurepoints 1. De distributie van de intercheckpoint-tijd is deterministisch.
fjti)= 6 ( ~ - L )
~'f =
na)=
0
f r<5 Ct:- L) cJ); = L
"ilL
O~ t <.
;
L
Ll. = i)J~/L =. Y2 L
n.. = A..fL 2. De distributie van de intercheckpoint-tijd is exponentisel.
CP)= A. c ~- ~ .. I:: - /00 _? t t er = 0 t: Ac.e. dJ:; = il~c.. c.
J1(~= ).c:. e.- A<;.t-
[-'1. = ij ~c.
n
= 'AI-lAc. 3. De distributie van de intercheckpoint-tijd is hyper-exponentieel. q(1:)= Ll;tc~-Ac.l; + (1_p)r';tc..e..- r J.C.1:: . o~p~1.; r)o //-
QO
'
t'( = Pol/:; Ac. e-?.c.'=dJ:.
+ CI-p)
o
ftr Ir.c. e-/")...1::di=
1/;(c. erp +r:.1(I-P)) .nLt)= (p + (';p)) -PAc e.-Ac.t: + (i- p) :lc. e -rAce} b = (p+ Cl r-p))-lf p j;).c. e -1')::(jk + (J.r-P) j;rAc.e- -rAr.J:: dJ= =
t
.il.
1 . "
c)
.4. rp =
-+CI-p) )..c. r"lop + r (I-p)
ii = X;/ ').
G
(p +
i- P ,..
)
4. De distributie van de intercheckpoint-tijd is hypo-exponentisel. q('=)= .2 A.c. C2Ac. t) e -.2.Ac.C L
'I
A
J~
-2?".1::
il
=.2 c. " c .z )..c.. e. dA:::: I' :Ac.. .n(1:.)= A.c. (I r 2. Ael:: ).fL. -z.1c. Co r:;
fJ).. = ~. :1./.:tc. n.. = )..5/?c:.. Voor elk van de vier distributies qrt.) is sen diagram getekend in figuur 3.1 met de bijbehorende distributiell~).
figuur 3.1
;1.1'
hjpere:rrentli.k vtrdtu"J \-tlOr
if )
1..6
1.4 :t.1.
1.0'+-..,.---
1
':nlO"1 0.1i
01>
0.4
0.4 0.1
03.
1M
0.6
0.8
1.2 1.4 1.6 fl<JF10 tf..n: 132
1.0
1.1
1.0
1.2
1:4
0.2
a...
D.6
0.6
tCA=OS
1 ~2. ti,,,1.0
J.O
J.4
J.6
1.4
.l.o
1.1
.1.4 4
a
16
1.6
14
1....
1.2 1.0 0.19
0.6
0.6
0.'1 0.1
0%
0.4
o.b
0.19
/ :a-Q1S
.~
J.'1
fi~.1.0
1"f
1.6
1.8
1.0
1.t
.M
~
~
~
u
U
tl
U
t~=r.,=l.O
U
u
u
u.~
1"1
3~3 3~
3.1
3~3~2
Het Algo·l Simulatieprogramma "Intercheckfailure-tijd" Inleiding: Voor het geval dat de distributie van de intercheckpointtijd exponentieel is,is er een simulatieprogramma geschreven die de verkregen expressie van iJ{1:) veri fieert voor verschillende waarden van)...;. bij constante ~ • De kern Van het programma zal eerst worden behandeld,dan de de statistiek en frequentieverdeling en vervolgens in het kort de gebruikte procedures. Het simulatieprogramma:de kern.
% INITIATION % L:= 0; ICFT:= 0; NCT:= -IATCxLN(RANDOM(I»; %END OF INITIATION % WHILE L NN DO BEGIN -ICFT:= ICFT - IATFxLN(RANOOM(I»; WHILE ICFT NCT.Mill L NN
m. BEGI~J
L:= L+1;
%verzamel statistiek met betrekking tot %waargenomen fouten in de betreffende
het aantal %
%intercheckpoint-interval ~l:=
% %
0;
ICFT:= ICFT - NCT; NCT:= -IATCxLN(RANDOM(I»; END; IF
L
NN
.I!:iQ!. BEGIN M:= M+1;
%verzamel
statistiek met betrekking tot de
%intercheckfailure-tijd
END
De gebruikte variabelen z~Jn: 1 teller,houdt het aantal checkpoints bij. nn nn geeft het maximale aantal intercheckpoint-intervallen dat beschouwd wordt.nn wordt ingelezen. icft variabele welke de intercheckfailure-tijd representeert. nct variabele welke de next checktime aangeeft. m : m houdt het aantal fouten in een intercheckpoint-interval bU. i : variabele welke nodig is voor de randomgenerator.i krijgt een initiale waarde bij aanvang van het programma. . iatc : variabele welke de gemiddelde interarrivaltime tussen de checkpoints aangeeft. iatc =1./~c. • iatf : variabele welke de gemiddelde arrival time tussen de failurepoints aangeeft. iatf = if')..f • Het programma is globaal samen te vatten als: Zolang de intercheckfailuretijd (icft) kleiner of gelUk is aan de next checktime (=nct) wordt een nieuwe icft
1'2
bepaald,anders wordt een nct bepaald. AIle tUden zUn relatief t.o.v. het begin van het intercheckpointinterval, welke met nct is geassocieerd. Het simulatieprogramma : de statistiek Statistiek met betrekking tot het aantal waargenomen fouten in een intercheckpointinterval alsmede met betrekking tot de intercheckfailure-tUd zal worden verzameld.Het gemiddelde en de standaarddeviatie worden bepaald volgens:
$=
~(N-i) {Hr. i
X- i -
':1
i
N
(N l2
1=1.
'Xi
)2J'
waarbU n het aantal observaties voorstelt van de beschouwde stochastische variabele,en Xi de waarnemingswaarde welke de stochastische variabela bU de i-de observatie aanneemt. Variabelen met betrekking tot de statistiek van het aantal fouten in een intarcheckpoint-interval zUn: nma : variabele welke het totaal aantal observaties noteert voor m, de i-de observatie voor m aanduidt met nrna is hier gelUk aan nne tsma geeft de totale sm van de rni. - waarden:
~~ma.= tsqma
rom.
Li-1 m·
L
geeft de n",. totale som van het kwadraat van de
~i-
waarden:
E
tsqma.. = i,. 1- rn~ Variabalen met betrekking tot de statistiek van de intercheckfailure-tUd: ncpf : variabele welke het totaal aantal observaties noteert voor icft, de i-de observatie voor icft aanduidt met icft tspcf : geeft de totale som van de icfti -waarden: ru:pf
t$pcf.=
L
Left/,
i= i
tsqpcf
geeft de totale som van het kwadraat van de icft i -waarden: ncpf
I:sqpcf =
D {cfl: t
i= 1-
De variabelen nn,icft en m zUn reeds in 3.3.2 gedefinieerd. Met behulp van deze variabelen worden in procedure text 1 het gemiddelde en de standaarddeviatie bepaald. i.3.4
Het simulatieprogramma : de frequentie'erdelingen Voor het maken van de frequentieverdeling van de waarnemingswearden ~i worden deze waarnemingswaarden in klassen onderverdeeld.De gebruiker geeft
op hoeveel klassen hij wilt beschouwen.Het aantal klassen is inclusief een underflow- en overflow-klasse.Er is sprake van underflow indien de meetwaarde ~o is.Er is overflow indien een meetwaarde grater is dan een bepaalde limiet, hier aangegeven door de variabele range.Het gebied tussen 0 en range is het voor ons interessante gebied.Range wordt door het programma bepaald aan de hand van het theoretisch gemiddelde ~Len de standaarddeviatie 6. range = fL1. .J-46 . kJ. 5 1 2 3 l · " i l .~.. l-2 r le -!
J=
I
a senummer LAndujlolJ< •
Een waarnem2ngswaarde
~i
rqn.~eb,~
0
valt in klasse j indien
1_/<'_ _
) OlluftelJ" r.a1?!fe.
Waarnemingen voor de intercheckfailure-tijd worden op deze wijze verwerkt. Waarnemingen voor het aantal fouten in een intereheekpointinterval worden oak op bovenstaande wijze verwerkt,doch de bepaling van het rangegebied kan afwijken.Het aantal klassen dat de gebruiker heeft opgegeven kan tevens ook door het programma gemodificeerd worden.Zie oak appendix A. Addi tionele variabelen zijn: tmeanma : theoretisch gemiddalde van m. tmeanma = iate/iatt. rangema geeft het rangegebied voor m. kma kma geeft het aantal klassen weer waarin de waarnemingswaarden voor m onderverdeeld kunnen worden. Uma iima is een array met kma plaatsen.iima vormt het geheugen waarin de informatie Van de frequentieverdeling voor m is opgeslagen. tmeanpcf theoretisch gemidd'3lde van de intereheckfailure-tijd. tmeanpcf = iate (N.8. deze veronderstelling wordt in de simulaties onderzoeht). rangepef geeft het rangegebied voot ieft. kpcf kpef g8eft het aantal klassen weer waarin de waarnemingswaarden voor {cft onderverdseld kunnen warden. iipef iipef is een array met kpef plaatsen.iipef vormt het geheugen waarin de informatie van d~ frequentieverdeling van ieft is opgeslagen. 3.3.5
Het simulatieprogramma : de procedures Het simulatieprogramma gebruikt een viertal procedures: 1. Grafies 2. Text 1 3. Text 2 4. Error Ad 1. PROCEDURE GRAFICS(II,K, YAX); INTEGER K; BfB1 ARRAY II x ; BOOLEAN VAX; De procedure grafies produceert een histogram van de te beschouwen frequentieverdeling. Scaling wordt automatiseh verzorgt. Meer dan 120 klassen kan niet worden geprint. In dat gevel wordt de gebruiker hierop geattendeerd. Zie oak appendix A.
114
Verklaring van de formele parameters ii array waarin de informatie van de te beschouwen frequentieverdeling is opgeslagen. k : het aantal klassen. yax : variabele waarmee aangegeven kan worden of een y-as gewenst (yax= ~) is of niet (yax = false).
Ad 2. PROCEDURE ~ 1 (N,TS,TSQ,TEXT); INTEGER N; REAL TS, TSQ; BOO LEAN TEXT; Verklaring van de formele parameters: n het aantal observaties voor de stochastische variabele x ts : totale sam van de n waarnemingswaarden x tsq totale sam van het kwadraat van de n waarnemingswaarden x text : variabele waaemee aangegeven wordt of text gewenst (text = true) is of niet (text =~). De procedure text 1 print respectievelUk n,het gemiddelde,de standaarddeviatie en ts
Ad 3. PROCEDURE TEXT 2 (II,K,N,TS,TSQ,RANGE); INTEGER K,N; REAL TS, TSQ, RANGE; INTEGER ARRAY II[*]j Verklaring van de formele parameters: ii : array waarin de informatie van de te beschouwen frequentieverdeling is opgeslagen. k het aantal klassen n het aantal observaties voor de stochastische variabele x ts totale sam van de n waarnemingswaarden x tsq totale sam van het kwadraat van de n waarnemingswaarden x range geeft het rangegebied weer waarbinnen de waarnemingswaarden zUn geklassificeerd.
· ··
De procedure text 2 drukt per frequentieklasse de relevante gegevens af. Voor details zie appendix A.
Ad 4. PROCEDURE ERROR (ERRORNUMBER); INTEGER ERRORNUMBER; Verklaring van de formele parameters: errornumber : geeft aan welke fout is opgetreden. De procedure error genereert texten in geval er een fout optreedt. Invoer Van de gegevens: Het programma vraagt achtereenvolgens de gegevens voor: - nn - iatc - iatf kma kpcf i
15
Oe Simulatie 3.4.1
Inleiding:
1.4.2
Voorbereiding omdat de corresponderende intercheckfailure-tijden van de failurepoints binnen een intercheckpoint-interval in hoge mate met elkaar zijn gecorreleerd, moeten al deze intercheckfailure-tijden als ~~n meting gelden. Ouiden we dit aan ala ~~n onafhankelijke meting, dan is voor: ~~1 ~~n on~fhankelijke meting per intercheckpoint-interval -p~<1 N.8.;P~is
r~et behulp van het Algolprogramma " Intercheckfailure-tij d" zal voor het het geval dat de distributie van de intercheckpoint-tijd exponentisel is nagegaan worden of de verkregen expressie voor .n(~)ook uit de simulatie naar voren komt. J2U:)::A.c .e.-A.c. t
aanwez~g.
gemiddel~~1intercheckpoint-intervallennodig om ~~n onafhankelijke meting te verkrijgen. het gemiddeld aantal failurepoints in een intercheckpoint-interval.
Het aantal intercheckpoint-intervallen dat in een simulatie ge8xecuteerd zal worden,wordt zo gekozen dat het theoretisch gemiddeld aantal onafhankelUke metingen voor aIle aimulaties constant is.Elke simulatie heeft een andere waarde voor Af. Simulatie 1
NN= 5000 iatc= 10 iatf= 1
Hieruit volgt:)J",= 10 ; ~= 10.49 totaal onafhankelUke metingen= 5000 totaal aantal failurepoints= 5000~;U~= 50000 Simulatie 2
NN= 5000 iatc= 10 iatf= 10 Hieruit volgt:!,,,,= 1 ; 6",,= 1.41 totaal aantal onafhankelUke metingen= 5000 totaal aantal failurepoints= 500o~m= 5000
Simulatie 3
NN= 50000 iak= 10 iatf= 100 Hieruit volgt:}I",= 0.1 ;d",= 0.33 totaal onafhankelUke metingen= 5000 totaal aantal failurepoints= 5oooo./~= 5000
Voor de berekening van 6
""
wordt U verwezen naar Appendix A.
16
Simulatieresultaten We vatten de resultaten van de drie simulaties samen in de vorm van een tabel
Simulatierun 1
ingestelde/berekende waarden ft" -= ~/'A.. = 10
=
~" j./ 'J-c.. = 10 6c.j)Ac. = 1
pm = 10 6_= 10.488
Simulatierun 2
/-Lc.= il:;tG= 10 t5e. -= if ')..,,= 10 r5e f;u<-
= 1
Pm = 1 6,..=1.414
Simulatierun 3
=
1./?toe. = 10 6 G -:: 1./ 'J.... = 10 ~!f'c. = 1
J,lc.
)'",= 0.1 ~= 0.332
verkregen waarden X~=10.002
SA. = 10.002 Sn./~A = 1.000
iii = 9.784 S"" = 10 • 392
Xn. = 9.740 SA. = 9.658
~/.XA. = 1 .008
m=
1.001
J", = 1 .407
XA = 9.973 S.n.. = 10.173 ~/~= 0.980 in
= 0.101 s,... = 0.336
We zien dus dat de simulaties de theoretisch verkregen waarde voorJl~) = Ac.e-?c. C ondersteunt. Tevens zien we dat de verkregen expressies voor)"",., en 6 nv correct zijn.
17
HOOFDSTUK 4: Validatie van het Markov-model met ij)=ot./k en k=PIA. Inleiding In dit hoofdstuk wordt een hypothetisch systeem beschouwd ondersteund met checkpointing en recovery-strategieen. De recovery-duur na een fout wordt in dit systeem gelijk genomen aan de gemeten busytijd in het ermee corresponderende intercheckfailurepoint-interval. De busytijd is de tijd die besteed wordt aan het verwerken van transacties. Zie ook figuur 4.1 • We zullen het hypothetisch systeem het checkpointrOllback-recovery systeem noemen, afgekort met CRR-systeem. In het CRR-systeem veronderstellen we verder dat: • De available-tijd tussen twee checkpoints exponentieel verdeeld is met gemiddelde intercheckpoint-tijd ~.~ De available-tijd is de tijd waarin checkpoint- en recovery-duur geen rol spelen. • De checkpointservice-duur exponentisel verdeeld is met gemiddelde checkpointservice-duur f3-~ • De fouten in de available-tijd poisson verdeeld arriveren. Fouten kunnen dus niet arriveren tijdens het nemen van een checkpoint of tijdens een recovery-actie. ~= de failurerate. • De transacties in de absolute-tijd poisson verde~ld arriveren met een gemiddelde inter arrival tijd ~-~ De absolute tijd is de tijd waarin checkpoint- en recovery-duur weI een rol spelen. Transacties kunnen daarom tijdens het.nemen van een checkpoint of tijdens een recovery-actie arriveren. • De servicetijd om de transacties te verwerken is exponentisel verdeeld met gemiddelde serviceduur fL-~
..
.I
figuur 4.1
!~iu.r.tpoi"t.L i. c: i :. dledt:pOinl;
F i -::
cJ,edcpoinI:su~
~:
.
;...~ reccary-
De blokjes op de available-tijdas stellen de busy momenten voor. De available-tijdas is de tijdas waarin checkpoint- en service-duur geen rol spelen. De available-tijdas toont daarom slechts afwisselend busy- en idle-momenten. Idle momenten zijn die momenten waarin het systeem hoewel beschikbaar geen transacties verwerkt. Om toch checkpoint-duren aan te geven zijn boven de available-tijdas driehoekjes getekend: de lengte van de zijde pa~allel aan de available-tijdas komt overeen met de checkpoint-duur. Op dezelfde wijze worden recovery-duren aangeven maar dan met driehoekjes onder de available-tijdas. Hoewel het erop lijkt dat het CRR-systeem in een Markov-model te representeren is is dit niet zoo Immers het'CRR-systeem vereist een geheugen dat de totale busytijd sinds het laatst genomen checkpoint opslaat, terwijl het Markov-model per definitie geheugenloos is. Qm toch uitspraken te doen over het CRR-systeem wordt hiermee een Markovmodel geassocieerd. Dit Markov-model is het Markov-model welke we in
18
hoofdstuk 2 hebben behandeld,waarbij wij veronderstellen dat
r.t=cxjk met k:=f/t:l·
In dit Markov-model zijn ten opzichte van het CRR-systeem 4 veronderstellingen gemaakt; 1 de distributie van de recovery-duur is exponentieel. 2 de gemiddelde recovery-duur is k./ot. 3 de recovery-duur is onafhankelijk van de ermee corresponderande intercheckfailue-tijd. 4 de recovery-duren zijn onderling onafhankelijk We zullen eerst op de punten 1 en 2 ingaan. De genoemde veronderstellingen hebben de volgende grond: Beschouw een (oneindig) lang interval waarin het CRR-systeem geobserveerd wordt.Dit observatie interval met tijdsduur T,gemeten in absolute tijd,zal een (oneindig) aantal intercheckpoint-intervallen bevatten. ~ Het verwachte aantal transacties in T is AT. iE De verwachte totale busy-tijd in T is ')..T/Ji'- =pT ~ De verwachte available-tijd in T Ls AT Ous is de fractie van de totale busy-tijd in de available-tijd gelijk aan pT/AT=f/A~k.. Aangenomen wordt nu dit ook geldt voor niet oneindig lange intervallen.Oeze intervallen zijn hierbij willekeurig te kiezen en mogen dus ook intercheckfailurepoint-intervallen zijn. De recover~!-duur wordt overeenkomstig het CRR-systeem gelijk gesteld met de totale busy-tijd van het ermee corresponderende intercheckfailurepoint-interval: recovery-duur = k x intercheckfailure-tijd. In het vorige hoofdstuk hebben we gezien dat intercheckfailure-tijden (bij exponentieel verdeelde intercheckpoint-intervallen en een poisson verdeelde aankomstpatroon Van fouten) eveneens exponentieel verdeeld zijn met hetzelfde gemiddelde als die van de intercheckpoint-intervallen. Wij kunnen daarom concluderen dat de recovery-duur exponentieel verdeeld is met gemiddeld k.oc..-1.. De twee laatste punten 3 en 4 zijn een automatisch gevolg ui t het r'1arkov-model. Het Markov-model vereist dat deze veronderstellingen worden genomen. In hoeverre de vier veronderstellingen juist zijn met betrekking tot het CRR-model zal hieronder worden besproken. Wat de distributie van de recovery-duur in het CRR-systeem betreft ,het is niet met zekerheid te zeggen hoe deze eruit ziet.Zeker is in ieder geval dat de totale busy-tijd in een bepaald interval met tijdsduur t·niet gelijk is aan kt( met k een (willekeurige) constante. L , De totale busy-tijd in een interval met tijdsduur t L is een stochast met een distributie die afhankelijk is van de tijdsduur t L Stel tbis de totale busytijd en ti is de interval-tijdsduur, dan is:
P[ h db I !;l= tJ = met bl.(l) is tijds~uur ti dan nemen we (4 1) wordt
./\.,W d1:
(4 1 )
de verdelingsfunctie van de totals busytijd in esn interval met • Keren we terug naar ons onderwerp, de recovery-duur distributie, als interval de intercheckfailurepoint-interval met tijdsduurt • overeenkomstig: l.f
P[tb~tb)-'cf=tefJ= / o
Co
h/;cf(tJdJ..
(4.2)
19
Wij zijn geinteresseerd in de distributie b(tb)van de totale busy-tijd waarbij de voorwaardelUke eis omtrent de duur van de intercheckfailurepoint-interval komt te vervallen: ~
Prh,,;; ~bJ
Hierbij is geldt nu:
-j •{jb~
CO.fl (tel) d'=cf } cit (4 3) J2 ceq) de verdelingsfunctie van de intercheckfailure-tijd. Voor bO:J.) 00
b (-tb)
==
"I b
I:cf
CbJ..n. Lt:C;\::U::Gf
(4 .4 ")
(f,.) -D- etc-! )at:cf
( 4.5 )
De recovery-duur b,. is gelijk genomen aan de totale busy-tijd in de corresponderende intercheckfailurepoint-interval.De distributie van de recovery-duur,voorgesteld door rCI:,.)is daarom gelijk aan bC!::.,.) r(c ,.),...b(f r ) 00
r (C,.) =-
oj
bcc;
Opmerking: In onze beschouwing met betrekking tot de eerste twee veronderstellingen,betreffende het Markov-model,is in eerste instantie aangenomen: tb= k; '=cf ofweI: bl: Ct;) =-0 (/;b-kJ: ), dus q cf = -~~e ?'C.l::cf ~ Ie'"
r (tr)=:.
!
6 Ct/'"-ktcj)
-
Ae. i.
dt:q.
=
-E:- P..
o ~ waarmee de juistheid van (4.5) geverifieerd is.
Samenvattend kunnen we zeggen dat om de distributie van r(L r ) in het CRR-systeem te bepalen we de distributie b, (tb) moeten kennen.Deze distributie is nog niet bepaald. '-/ Verder is in het CRR-systeem de totale busy-tijd en daarmee dus ook de recoveryduur altijd in hoge mate gecorreleerd met de ermee corresponderende intercheckfailure-tij d. Ook zijn de recovery-duren in hoge mate met elkaar gecorreleerd indien de bijbehorende failurepoints in hetzelfde intercheckpoint-interval vallen.Immers de totale busy-tijd sinds het laatste checkpoint heeft een cumulatief karakter naarmate de tijd voortschrijdt en derhalve zullen de recoveries langer duren naarmate ze later plaatsvinden. De vraag rUst nu in hoeverre de met het Markov-model gedane uitspraken betrouwbaar zUn.Voorspellen zij het gedrag van het CRR-systeem juist? De vraag kan worden beantwoord door een validiteitsonderzoek te doen.Allereerst dient een vooronderzoek gedaan te worden.Onderzocht moet worden: 1 in hoeverre de distributie van de recovery-duur de exponentieele verdeling benadert en in hoeverre de gemiddelden met elkaar overeenstemmen. 2 in hoeverre er een afhankelijkheid is tussen de recovery-duur en de ermee corresponderende intercheckfailure-tijd. 3 in hoeverre er tussen de recovery-duren onderling een afhankelijkheid bestaat. Het eigenlijke validiteitsonderzoek houdt in: 1 in hoeverre de availability,berekend met behulp van het Markov-model,overeenkomt met de aVailability van het CRR-systeem. 2 idem, maar dan voor de queuelengte Het vooronderzoek en het validiteitsonderzoek vormen het onderwerp van dit hoofdstuk.Oerhalve zal eerst het Markov-model dat met het CRR-systeem is geassocieerd nader beschouwd worden.
20
Het validiteitsonderzoek vereist dat er een CRR-systeem aanwezig is.Daar er (voorlopig nog) geen wiskundig model voorhanden is,is er een simulatie-model geconstrueerd in de vorm van een Algolprogramma. Oit Algol simulatieprogramma,dat we CRR-simulatieprogramma zullen noemen,zal aIle benodigde statistieken en gegevens produceren.Het simulatieprogramma wordt na het Markov-model behandeld.Vervolgens worden de uit de simulatie verkregen statistieken en gegevens vergeleken met uitkomsten verkregen met het Markov-model.Getracht zal worden afwijkingen te verklaren. Afgezien van deze inleiding bevat dit hoofdstuk,evenals het vorige,dus drie gedeelten: 1 behandeling van het Markov-model 2 behandeling Van het CRR-simulatieprogramma 3 evaluatie van de verkregen statistieken en gegevens.
21
!l=ot!k;.k=fJlR • ;
.2
Het Markov-model met
.2.1
Inleiding In het r~arkov-model welke in hoofdstuk 2 is behandeld zal aan o(/Jv worden gesteld met k=f/~ •
if gelijk
De uitdrukkingen voor de availability en de queuelengte zijn dan respectievelijk:
figuur 4.2
{lk(et'f)
=.
( i+
f
+
k
t 0(
)-1-
.
(4. 6)
d=t) [f· lAY;, e!.)J~l
Nk (<>., f) =
+
nvA ,L
%k(oc-r)
(1 8)
De availability en de k-waarde in (4.6) en (4.8) kunnen herleid worden tot de volgende uitdrukkingen:
Ak (DtJf) = (1-f ~ )(i 1<-=
(1<-P(~-!z-
+-
ft yi
( 4·9)
r
(4.10)
In deze paragraaf zijn we geinteresseerd in de grenzen waarbinnen de formules voor de availability en queulengte geldig zUn.Dit wordt het ergodiciteitsonderzoek genoemd.Verder zUn wij geinteresseerd hoe de availability en de queulengte beinvloed worden door de parameters.Het ergodiciteitsonderzoek zal het eerst worden behandeld maar voordat wU hiertoe overgaan zal eerst gekeken worden welke van de parameters wij zullen vari~ren en welke wij constant houden.Dit om het overzicht te houden. Van de parameter ot.., kunnen we zeggen dat we deze zeker variabel moeten maken omdat zij als enige ons in staat stelt om direct invloed op het systeem te kunnen uitoefenen.Immers de parameters en zUn van buiten af bepaald en de parameters l' en p- zijn door een programma bepaald. De laatste twee zijn weliswaar te beinvloeden door het programma te veranderen maar -is eenmaal het programma veranderd- dan blUven ~ enfL een vaststaand gegeven. Er is dus weI flexibili tei t in f' en)-l- maar zij is niet doorslaggevend.In feite behoeft aIleen parameter~ variabel gemaakt te worden.Omdat we ook gelnteresseerd zijn hoe het systeem zich voor verschillende waarden van p gedraagt moet sen van de parameters ) of ~ variabel gemaakt worden.
t
A
22
Gekozen is am p. variabel te maken en gezien onze interesse voor de parameter}' is het beterf' te beschouwen danfL .• variabel Samenvattend: Oi = checkpointing rate variabel = load constant = failurepoints rate :constant = service rate checkpoints :constant ~ = transaction arrival rate Omdat de parameters IX en variabel zijn worden availability en queuelengte geschreven als:
E t I?
p
Ak = Ak. (Ci.~p) Nk. = Nk. (cI..,p) De index k geeft aan dat het hier een model betreft met,! =t;;(/k waarbij k= A!<JCcx..)~). Eventueel zal aan keen waarde worden gegeven. Tevens is met ex enR een "vlak" geassocieerd dat we ("C~p)-vlak zullen noemen. In dit (o(~p)-vlak zullen we de availability en de queuelengte bestuderen.De vorm van de krommen,welke we later in dit (ot~/p)-vlak zullen tekenen,blijken uitsluitend afhankelijk te zijn van 't'enf •
pi
• 2.2
Hat ergodiciteitsonderzoek •
• 2.2.1
Inleiding In het (~-:p)-vlak zal het gebied worden bepaald waarbinnen de formule voor de queuelengte( 4.7 ) geldig is.Dit gebied wordt begrensd door de zogenaamde ergodicitaitsgrens. Expressies voor de "linker- u en lI rec hter ergoci tai tsgrans lf , respactievelijk met c:xten oc;/aangeduid worden gageven. De ergodici tei tsgrenzen C(L- 1 en CiR,-1 gelden voor constante .Eveneens is voor constanta O{~een ergodici tei ts grens bepaald •
f
po
• 2.2.2
De ergodiciteitseis. Beschouw een (oneidig) lang observatie interval met tijdsduur T gemeten in absolute tijd.De obsarvatie interval bevat een (oneindig) groat aantal intercheckpointintervallen. Het verwachte aanta l transacties in T is AT De verwachte totale busy-tijd in T is )T/~ De verwachte available tUd in T is AT Voor een stabiel systeem moet gelden < AT dus <: 1 (4.1 i )
pT
.2.2.3
PIA
De ergodiciteitseis in het (0<-1. ) -vlak De ergodici tei tsgrens in he ( 0<. -;f) -v ak is de curve waarvoor geldt
Hieruit voIgt met ( 4.9.)
f= (i+~ ~!)-i - lii{d:~t)
(A, 13)
Veor de ergodiciteitsgrens geldt k = 1 Voor een bepaalde waarde van~ is in het (oI..-;f) -vlak een maximum veor te vinden.We geven dit punt aan met (O<~)f )ptylQ,X)'
f
Z3
p",..".,
vinden we door ( 4.13) naar ()(" te di fferentieren en de verkregen uitdrukking gelUk 0 te stellen.
(4.15 )
~.2.2.4 Be alin
van de ergodiciteitsgrenzen dZia, -~en . Houden we in het oJ.-~p - vlak p constant, dan legt de ergodiciteitsgrens ( 4.12 ) de ergodici tei tsgrenzen CX/._I en 0( i' vast waarbinnen 0(-' mag varieren. Er geldt eXt_I ~ 0(11.- 1 .Op dezelfde wijze legt de ergodici tei tsgrens ( 4.12 ) de ergodici tei tsgrens fJo vast indien we in het (o(-~ f ') -vlak 0( constant houden. kan dan varieren tussen 0 en ';>0
f
We bepalen
1 o(L-
en
Hieruit voIgt:
O(~/: j>=t:J,{cx/)} ..~ f
~ 0(1.+ {f- 1 )d. oJ-I i =
0
Deze tweedegraads vergelijking heeft als wortels
"',= ifC f1 +f1oiR met C
0(1..
en IXIl..
Jrt.. ' 1
=~ 1" C {i - ~ 1. - ~~
7. '
1
(4, it)
= A::B. ?
We bepalen
fo:
(4.18 ) (4. i9) ~.2. 3
De availability Ak.{ot.Jf)
~.2. 3.1
Het maximum van availability indien We bepalen eerst het maximum indien optreedt duiden we aan met c1rrp/:.,A.
p=
)0=
d-Aj( lcl./,P) =/1+ ~)-2..(P4 +-
de/..
l
f'
0(2
constant en indien ex = constant. constant.De o(waarvoor dit maximum
P-!- _;31. + o(~ M-)
r;<~
=0
Hieruit voIgt:
(4.20)
24
De p waarvoor er een maximum optreedt indien 0(= constant duiden we aan met J:ope.,q Uit ( 4.9 ) voIgt dat voor ~= constant de availabilty een lineaire functie isvatlpooe afgeleide is negatief zodat: 0
f6pJ;,A ~.2.3.2
=- 0
(4.21)
De d,;p/:, ~ -lijn en de availability- nullijn. De 0<6'1''', ~ -lijn is de kromme In het (t><;f)-vlak waarvoor geldt:
~
A Cd.
t) =
(?J/+,.:,Cci,f) dOl ~
Ie,
a~k.{d.J)J) -= ap
~
(0,) __0
0«1 +-~)
)
met andere woorden de ~A -lijn is de verzameling van aIle (o(~,A'f") punten.r·let behulp van ( leiden we de ui tdrukking voor de Q(~ A -lijn af. J
4.20 )
De avilability-nullijn is de kromme in het (~~p)-vlak waarvoor de availability 0 is.Vanwege ( 4.14 ) ligt deze availability-nullijn buiten het ergodiciteitsgebied.Uit ( 4.9 ) voIgt direct voor de availability-nullijn:
ot.
.2.4
p= t
(4.23)
Overige We kunnen ons afvragen of op de D<.ept}A -lijn te vinden is:
Ak (IX)f) = A)( (eX) {{(~ De availability op de
()(~,
sen maximum voor de availabili ty
12)J-1) = (1+1%)-1
A -lijn is dus monotoon dalend met toenemende 0<
Een vijftal snijpunten zal hieronder worden gegeven. 1. Het snijpunt van de eXtlpl:, p, -lijn en de ITjn tX = met H =
'tH
(
5j.:a (c<,f)~ = (6'H) H( ~( ~ +2))-~) 2. Het snijpunt van de
o(~A-lijn .J
""api,A
(4.24 )
en de ergodiciteitsgrens is:
51 = (o.~p\= ({(ff H) 3. Het sn'jpunt van de
1t;1
1+2V't/~ lis:
-l'jn en de 11j;
f:=
{if;
is'
~= ~Jf)D= ((3 (/1+\ff -1)- ~ ~)
4. Het snijpunt van de availability-nullijn met de lijn «='{ij)is:
~= (c(,f)4= (V'f~ ,~ ~) 5. Het snijpunt van de availabili ty-nullijn met de lijn
f
$5'=- Co.Jf\= ('iH~ H)
=}..f is:
CLl.28)
Merk op dat 51 overeenkomt met (4.15). In figuur 4.3 zijn de ~~A -lijn, de ergodiciteitsgrens en de availabilitynUllijn getekend voor J-l 1000 en 13-'= 150. Tevens zijn aangegeven: ~ de snijpunten S1 tot en met s? . ~ ~ voor 0.3 de ergodiciteitsgrenzen otL.en ~ voor 0( '= 800 de ergodici tei tsgrens fo .
=
p_ =
c/..i.'.
.
-
25
-/
4i'
0 0
N
0 0
~
8ID
~t---~-----I I
I I
I
0 0
CD
0 0 0
0 0
0 0
0 0 ID
... ... ... ---- - -----N
~
8
o
I
I I
I I
...
1
0.8
figuur 4.3
4
We kunnen de ergodiciteitsgrens en de availability-nullUn ook beschouwen als krommen in het (0<:;0) -vlak waarvoor de k-waarde constant is. Met ( 4.8 ) krUgen we:
(4.29 )
26
De availability null Un is de kromme waarvoor k
i+q!-i-kl
-
km. k.-oo 1.
i +!c<
of
t
:00
==
k (3 cJ. De ergodiciteitsgrens is de kromme waarvoor geldt k : 1. De 1 ij n jJ = a is de kromme waarvoor k : O. De krommen waarvoor k constant is hebben in het (o(p)-vlak een maximale waarde voor? bij een bepaaldeot, welke we otlpb,1c. zullen noemen.Door ( 4.29 ) naar 0(. te d~fferenti8ren en gelijk a te stellen vinden we:
cX.ttpi., k.
Ie,
ot
{':J
= Vk f>:t '
(4.30)
( 4.30 ) in ( 4.29 ) gesubstitueerd levert:
.At
f=
~k
(4.31)
1+2 Vk£"
De -lUn is de J;omme die door de maxima gaat van de krommen waarvoor k : constant. ( 4.30 ) levert:
k=
0/.2
( 4.32)
p2t
Substitueer
(4.32) in ( 4.31 ):
. p~Ii{i+2~firr=E(~+2)} O
k., -lijn overeenkomt met de tX4pI::,A -lijn.ln figuur 4.4 zijn voor en) If': 150 diverse krommen getekend waarvoor k : constant. Tevens is ook de O<6p~k. -lijn getekend.
zodat de
a-I: 1000
figuur
4.4
-0'-'
200
400
500
-
1000
1400
1200
1500
1800
" ....A-.Lij""
k.cJ.125
0.1
}
k.cJ.250
0.2
k.cJ.500
0.3
0 ••
0.5
0.8
-«!
.;~
0.7
.~
~'
0.8
'1'
-I
,"
cI1ag.... toont Ujn.. _t _tonu k_u_
~ ... Ujn
_t k.l 10 .....gM101u1ug....
27
In figuur 4.5 op pagina V is de availability
Ak.lo<,f)
binnen het ergodici-
tei tsgebied getekand als functie van 0(-1 en p Figuur 4.6 toont de queulengte Nk,. (iX,f)als functia van ci- I voor verschillende waarden van p, waarbij de bijbehorende ergodici tei tsgrenzen 0
oo~ - - - _._ .. _----_._._--
figuur 4.6
figuur 4.7
63095.1J
39810.12 25118.86
15848.93
2.4
63095.73
2.3
39810.72
2.2
25118.86
2.1
lSO.8.93
2.0
1ססOO.00
10000.00 _ 6309.57
6309.57
J98t .07
3901.07
1.8
2511.89
1.7
2511.89
1584.89
1.6
1584.09
1000.00
1.5
1000.00
1.4
630.96
1.3
398.11
251.19
1.2
251.19
158.49
1.1
158.49
1.0
100.00
63.10
0.9
63.10
39 .. 81
0.8
39.81
IV
25.12
25.12
15.85
15.85
10.00
10.00
rn
6.31
f ~ a
o.
3.98
t' ::l o.
2.51
~i
1.50
01 sgulIl wont de queueJ enQte
al. runcUe \Ian of:'voor vetachJllondo lIlasrdon
2.51
f'sa
11.00
Wi!lllf
•
"."..
"
'""
"g
g
"
. c
0.1 0.0
..'"
4----.--r-...-.---.-,..-.--,r_-r-,..-rl~r_...J
...g
."".
"":?
1.00
n
29
4.3
Hat CRR- simulatieprogramma
4 .3.1
Inleiding Hat CRR-systeem is in de vorm van een Algolsimulatieprogramma geImolemanteerd. Dit simulatieprogramme dat we CRR-simulatieprogramma zullen noemen zal alle benodigde statistiek en gegevens producer en welke nodig zijn om na te gaan in hoeverre da voor het Markov-model gemaakte veronderstellingen aannemelijk zijn en om na te gaan in hoeverre avalability en queuelengte juist zijn. In deze pa~agraaf zal eerst de kern van het CRR-simulatieprogramma worden behandeld. De kern beschrijft uitsluitend die processen welke zich in het CRR-systeem afspelen, waarbij alle voor de statistiek benodigde prgrammadelen zijn weggelaten. Vervolgens worden de programmadelen besproken die zich bezighouden met het verzamelen en het verwerken van statistiek. Tenslotte worden de procedures besproken en de wijze waarop de" statistiek gepresenteerd wordt De kern van het CRR-simulatieprogramma
~.3.2.1
Inleiding De kern V2n het CRR-simulatieprogramma is een beschrijving van de proce sen welke in het CRR-systeem plaats hebben. In de kern zijn alle voor de statistiek benodigde orogrammadelen weggelaten. Hierop is een uitzondering gemaakt. Bepaald wordt wanneer sample-points genomen worden. Sample-points zijn tijdstippen waarop gegevens kunnen worden verzameld. De busytijd en de queuelengte worden weliswaar gemeten, maar zij vormen een wezenlijk onderdeel van de kern. Een belangrijk begrip in de kern is het next-event-moment. Een next-event moment kan een checkpoint, failurepoint of een samplepoint zijn. Met het next-event-moment zijn de volgeride twee variabelen geassacieerd:
-nem
= next-event-moment:
bepaald het tijdstip waarop een next-event-moment geexecuteerd moet worden. -cfdur = checkpoint of failurepoint duration: geeft de executieduur van een next-event-moment aan. Kenmerk van een next-event-moment is dat gedurende de ermee geassocieerde executieduur transacties blijven .arriveren, maar er worden geen transacties verwerkt. Verder hebben alle variabelen welke de statistiek bijhouden allen een geldige waarde. Zo ook de busytijd en de queuelengte, gesymboliseerd door respectievelijk busyt en queuel. Met de transacties zijn de volgende twee variabelen geassocieerd: -ntt = next-transaction-time: bepaald het moment waarop een transactie het systeem binnenkomt. -ndt = next-depart-time: bepaald zolang de queue niet leeg is het moment aan waarop een transactie hat systeem verlaat. De queuelengte is inclusief de transactie welke verwerkt wordt.
30
Kart samengevat komt de werking van de kern op het volgende neer: van ntt, ndt en nem wordt de kleinste bepaald. De actie die daarmee geassocieerd is wordt uitgevoerd, en het volgende moment waarop dezelfde actie moet plaatsvinden wordt bepaald. Het proces begint dan van vooraf aan. 4.3.2.2
Implementatie van de kern De feitelijke kern bestaat uit vier consecutieve segmenten: 1- in het eerste segment blijven transacties arriveren zolang ntt~nem. Zolang de queue niet leeg is worden er transacties verwerkt. 2- in het tweede segment is ntt) nem. Zolang de queue niet leeg is en ndt~ nem worden er transacties verwerkt. Na het verlaten van het tweede segment geldt dat ntt'»nem en ndt > nem, zodat de bij het next-event-moment behorende acties moeten worden ondernomen. 3- in het derde segment wordt bepaald of het next-event-moment een checkpoint, failurepoint of een samplepoint is. Afhankelijk hiervan wordt aan cfdur een bepaalde waarde toegekend. Transacties blijven arriveren die de queue vergroten. Omdat we in dit lineaire recovery model een available-tijdas hebben, worden tens lotte alle tijden bijgewerkt. 4- Omdat we de available-tijd relatief nemen ten opzichte van het einde van een checkpointserviceduur zal in het vierde segment,in het geval dat het next-event-moment een checkpoint was, alle tijden bijgewerkt. In de kern komen nag de volgende variabelen voor: - L: geeft het aantal reeds doorlopen cycli weer. nn: geeft het maximale aantal cycli weer dat geexecuteerd moet worden. nn wordt door de gebruiker opgegeven. stpt = startpoint: variabele welke nodig is am de totale busy-tijd te berekenen. tsample: geeft de tijdsduur tussen twee samplepoints aan icft = intercheckfailure-tijd: geeft het tijdstip aan waarop een failure point geexecuteerd moet worden. nct = next checkpoint time: geeft het tijdstip aan waerop een checkpoint geexecuteerd moet worden. nst = next sample time geeft het tijdstip aan waarop een sample genomen kan worden. iatf = interarrival time failure points. iatc = interarrival time checkpoints. tsample: geeft de tijdsduur tussen twee samplepoints aan filledbefore: geeft aan of de queue leeg was op het moment dat een next-event-moment geexecuteerd wordt. Het programma voor de kern van het CRR-simulatieprogramma ziet er als volgt uit:
31
% INITIATION % ICFT:= -IATFxLN(RANoOM(I»; NCT:= -IATCxLN(RANOOM(I»; NTT:= -IATTxLN(RANOOM(I»; QLENGTH:= 0; STPT:= 0; NoT:= 0; 8USYT:= 0; L:= 0; REAo(INPUT,/,NN,TSAMPLE); NST:= TSAMPLE; % END OF INITIATION % WHILE L
FILLEDBEFDRE:= FALSE; lE. QLnJGTH=i=0 THEN BEGIN SUSYT:= BUSYT+(NEM-STPT); STPT:= NEI'1; FILLEDBEFDRE:= TRUE Qill.
END" '
32
%SEGMENT 3: CALCULATE QUEUEGROWTH DURING A CHECKPOINT %
%
OR A rAILUREPOINT DURATION
BEGIN
1.E
Icn~MIN(I~ST
,NCT) crOUR:= BUSYT f!:.§f lL NST
..Q!Q;
%ADJUST NTT BECAUSE or AVAILABLE-TIME AX % NTT:= NTT-CFOUR;
.!I (QLENGTH>O) .I!:!.lli BEG I N
~
NOT FILLEDBEFORE
STPT:= NEM; NDT:= STPT-SERTxLN(RANOOM(I))
Q!Q.
END; %:SEGMENT 4: A~INISTRATION % BEGIN
.!I
NST~MIN(IcrT,NCT)
THEN NST:= NST+TSAMPLE;
.!I
ICFT~MIN«(NST-TSAMPLE),NCT)
lbfli
Icn:= Icn-IATFxLN(RANOOM(I))
f!:.§f.!I
NCT~(NST-TSAMPLE)
.It!Qi BEGIN
Icn:= ICFT-NEM; STPT:= STPT-NEM; NOT:= NOT-NEM; NTT:= NTT-NEM; NST: = TSAI"lPLE; NCT:= -IATCxLN(RANOOM(I)); BUSYT:= 0; L:= L+1 Qill.
END Q!Q. %OF WHILE-LOOP "L
%
33
,3.3
Het verzamelen en verwerken van de statistiek
.3.3.1
InleidinQ De voor het Markov-model gemaakte verondarstellingen dianen ondarzocht te worden in hoeverre zij aannemelijk zijn. Daartoe moet statistiek worden verzameld. Deze statistiek moet inzicht geven in 1. de distributie van de recovery-duur 2. de afhankelijkheid tussen de recovery-duur en de ermee corresponderende intercheckfailure-tijd 3. de afhankelijkheid tussen de recovery-duren onderling De statistiek welke zich met bovenstaande drie punten zijn geassocieerd zal in de navolgende paragraaf worden behandeld. We zullen dit de statistiek van het vooronderzoek noemen. Varvolgens zal daarna de statistiek worden besproken welke is geassocieerd met het eigenlijke validiteitsonderzoek.De availability en de queuelengte worden gemeten.Omdat in het Markov-model de waarde van keen rol speelt, zal oak hierop worden ingegaan •
.3.3.2
De statistiek van het vooronderzoek Van de recovery-duur zal het gemiddelde en de standaard deviatie worden gemeten.De variabalen,welke hiermee geassocieerd zijn,zijn: - ncfdur geeft het aantal failurepoints weer. - tscfdur geeft de totale sam van de recovery-duren weer. -tsqcfdur geeft de totale sam van het kwadraat van elk van de recoveryduren weer. Op dezelfde wijze als aangegeven in het vorige hoofdstuk in §~~ wordt hieruit hat gemiddelde en de standaarddeviatie berekend. De gemeten recovery-duren worden in klassen onderverdeeld.Ook dit gebeurt op precies dezalfde wijze als beschreven in §3.'3Avan het vorige hoofdstuk. De volgende variabelen zijn hiermee gaassocieerd: - tmeancfdur : theoretisch gemiddelde van de recovery-duur,berekend met behulp van het Markov-model. rangecfdur range-gebied. kcfdur : het totaal aantal klassen. fcfdur1 = array fcfdur [1: kcfdur] : array in welke de gegevens van de frequentie zijn opgeslagen. De afhankelijkheid tussen twee stochasten x en y wordt berekend met behulp van de kruis-correlatieco~fficient t~,welke is gedefinieerd als: ( 4.34)
D
-=
E'L 1:-p.,.. d
tr
'i.-J.A.t.J
d'j met dx.'J= E[("f-).L,)(~ -}.1.y > 6 11';j wordt de covariantie genoemd. Indien 'X.: v dan is d. = 62., de variatie van 'X - L XX.;( rxy
Men kan bewijzen dat geldt: ( 4.35)
pxy ~1.
Een zuivere schatter voor de covariatie ( 4.36 )
S-x = -
cy
1
N-l
6xy
is:
(N2:~. .- 1:. n L . j= 1 'J 1, N J=~ J-::1.1; }J
IV
Defini!ren we de rij van meetwaarden voor de
)
stochast~
a1s:
34
Xi' X2 , X 3 ' ••• , Xj' ••• , x N' dan is Xj het j-de elemant hieruit. Definieren we op dezelfde wUze de rij va~ meetwaarden voor de stochast Y als Yj' YJ , Y3' ••• , YJ' ••• , Y,." dan is Yi het j-de element hieruit. Wensen we de rij van y-meetwaarden te verschuiven t.o.v. de rij van x-meetwaarden over i meetwaarden,dan krijgen we:
( 4.37 )
$
li)~ N-L-, 1 xy 1
N-i
(
f..; j=1.
~
(-Xi-X(O)(YJ+i.-YCO) #
met
N-i ( 4.38 )
-
'X( i) = -
.1
N-i
( 4.39 )
yO') =
0
Z2
'X'
J= 1- i
en
N
1.
;;'1. Yj
De uitdrukking voor de schatter van de covariatie is ook te schrUven als: tJ-i I'J-i /J-i (L) N 1.-1 ( rx.iYJ'l-i - X(i.) Yi+£ Xi + J J.... , tI J-= (/ J-=I d
~ll\l
= =
(4,40)
~1 ym B (~-(J X[i)v(i) 1. (r:'_ 1 X ,/1,,'+;, - 'X~Cd L-J. ff Yk ) N - 1.-1 (fV1.. ~ 'X' 'j , - --:- Z x' 12 :J; N-L-J. J J~l '=~rl
= ~
=
?:j.
d~,t
J:;I
d
(/
k~L~~ tJ-t
tJ-L
':1
r;.; .
.. ,..
L
De schatter voor de kruis-correlatieco~fficient pxy is Vers(hui ven we wederom de y-meetwaarden t.o.v. de rij x-meetwaarden over i meetwaarden,dan krijgen we:
( 4.41 )
met ( 4.42 )
en
( 4.43 ) Definieer nu ( 4.44 ) ( 4.45 )
( 4.46 )
..J
)
35
Hierbij laten we x overeenkomen met de recovery-duur en y met de ermee corresponderende intercheckfailure-tijd. Oerhalve schrijven we in plaats van een "x" een tlcf tl , en voor If y " een "ic ll • In het CRR-simulatieprogramma zijn de berekeningen voor de correlatiecoefficienten refe f(i), r.IC.C f(i) en r c f (.c. (i) vereenvoudigd. We nemen aan d a t aI s : 1. het aantal meetwaarden, aangegeven door n groot is en 2. de verschuiving over i meetwaarden klein we voor het gemiddelde x(i) en de standaard deviatie sCi) mogen schrijven: fJ 1)7
IJ- j
- "'XCi) Cf (i.)
=
( 4.47 ( 4.48
S,{l)
= -;;-l' -1.
rv-
= 'CjUj = -;:.
n ~ CfJ :::, J~J.
:i-1
(~ c~ -
~_ t
(Jl;- c~
~-
~ LJ cf:= 0/(0) ;.;
,. J=:t
1 -
= r-L J
(N-i) cFdJ.) =
N
Cf)
=:
S <J{0 )
= S cf-
De exponentiale distributie voor de intercheckpoint-tijd is programmatisch vastgelegd, waarvan de gemiddelde intercheckpoint-tijd door de gebruiker wordt ingesteld. We nemen aan dat voor de intercheckfailure-tijd geldt: y{i)={,c[i)=
( 4.49 en
C;y[i)
( 4.50 )
=
Sef
(J.. ) -;:
'" -.1 /Ie..
');:1-
waarbij A-'de gemiddelde inter arrival time is van de checkpoints. Co
We krijgen derhalve voor de auto correlatiecoefficient:
(l),.., 1/Jcfcf (0 -
( 4.51 )
Y-
( 4.52 )
Y",'c.c (i).z ,Yiu,f (i) -
W-0 Zf c7
~fc.f ,..... (N- L'-l) ~e.j. Scf en voor de beide kruis correlatie-cosfficienten:
( 4.53 )
f ref (c
,
(N-i-l) .
~-i) 'A c-1.Z[
~c-' 5
cf
-
_j
1.)!c.f lc (l. ) - (N- i) cf Ac. t /II - i -1) 'S cf /I ;' 1/) We zullen behandelen hoe de berekeiling van 1fc/c./(i),·fi c. e f {() -;::.
10
(i) en'1'e-j-,-c.(i) is gerealiseerd, doch voordat we hiertoe overgaan zal eerst een voorbeeld gegeven worden waarin de te volgen gedachtegang te zien is. voorbeeld 1 veronderstel De rij
~e8tgegevens
voor de recovery-duur lS:
3, 1 , 3, 8 , 2, 5 , 4
en De rij meetgegevens voor De inLsrcheckfailurs-ti.id is: 1,7,6,3,2,5,9
Deze twes rijan r::ectgegeovens sc"'ri iven we onder elka2r. l..f./c.fi.c{O)wordt nu aIs viJIJt berekend: elk,e,.al uit de bovenste rij wordt vermeci~vuldigd met hat co;res~onderende get a 1 u Ltd eon d e I' c' t e I' i j. Ve I' v a 1. :; ens wIJ I' den 2 1 d e z eve I' me _ n i 9 v u 1 d i .J i n, e n b i j elk a . I' 0 '~ ;) eta 1 d. [ m l/{ft:.C. Ci) t e be I' eke n e n word~ de once~ste rij.i-elemerten nEar links verschoven, ~n vlndt ceze~fc2 man18r V2n Ie enen ~ls =oven ola?ts. uaar waar jeen corresDoncerendeletal uit ce on~erste verschoven rij te vincen is, vervalf 06 vermenig' uldi~inJ.
36
o us
va a r deb ere ken i n 9 l.flcfU!. met i = 0, 1 , 2 , :t, en 4 k r i j 9 e n we:
rij cf-meetwaarden:
3,1,3,8,2,5,4
rij ic-meetwaarden:
1,7,6,3,2,5,9 7,6,3,2,5,9,0 6,3,2,5,9,0,0 3,2,5,9,0,0,0 2,5,9,0,0,0,0
1 1,7 1,7,6 1,7,6,3 3+ 21+ ~23 == 18+ 9+ (4)= 6+
"lfcf'cCT \1 =
7+ 18+ 24+ 4+ 25+ 36 6+ 9+ 16+ 10+ 45+ 3+ 6+ 40+ 18+ 0+ 2+ 15+ 72+ 0+ 0+ 5+ 27+ 0+ 0+ 0+
20 kr i j gen we op de z e1 fde wi j z e
tp,oC'f(Oj= 1 = 2 = 3)= (4)=
1
3+ 1+ 3+ 8+ 2+
(0-p1aatsen verschoven~ (1-p1aats verschoven \2-p1aatsen verschoven) \3-p1aatsen verschoven) (4-p1aatsen verschoven)
7+ 21+ 56+ 14+ 35+
18+ 24+ 4+ 25+ 48+ 6+ 10+ 20+ 12+ 15+ 8+ 0+ 30+ 12+ 0+ 0+ 24+ 0+ 0+ 0+
9+ 3+ 9+ (3~= 24+ (4 = 6+
°°° ° voor 1.fJLcc/.i)e n 1fe f (i) : f 36 °° °° c
1+ 9+ 64+ 4+ 25+ 36 3+ 24+ 16+ 10+ 20+ 8+ 6+ 40+ 8+ 0+ 2+ 15+ 32+ 0+ 0+ 5+ 12+ 0+ 0+ 0+ (einde voorbee1d)
tj/cfc.of " 0 ) =
(1)= (2)=
°°° °
We definieren de velgende twee buffers: -de buffer welke geassecieerd is met de rij meetgegevens veer de recovery-duur.Deze buffer wordt gesymboliseerd door de variabele bufcfdur = array bufcfdur [0 :mul t-1] • -de buffer welke geassocieerd is met de rij meetgegevens voor de intercheck failure-tijd.Deze buffer wordt gesymboliseerd door de variabele buficft = array buficft (0:mult-1] • Beide buffers zijn circulair.Meetwaarden die niet meer nodig zijn voor de berekening van de correlatiefuncties (4.44),(4.45) en (4.46) worden door nieuwe meetwaarden pverschreven.Er is dus in de buffer een "oudste-waarde" aanwezig welke aan de beurt is om overschreven te worden.Een pointer, gesymboliseerd door de variabele point,wijst naar deze oudste-waarde.lndien we de correlatiefuncties voor maximaal i~verschuivingen willen beschouwen dan moeten de buffers i. +1 plaatsen bevatten.i +1 wordt gesymboliseerd .1. /illaA door mu 1 .... De correlatiefuncties zelf worden gesymboliseerd door: . -autocfcf = array autocfcf [0:mult-1] :Het i-de element stelt Ve;c/liJvoor. -crossiccf = array crossiccf :mult-1 ] :Het i-de element stelt ificc.j a) voor. -crosscfic = array crosscfic 0:mult-1] :Het i-de element stelt 7fJ I"i)voor.
Eo
rCfu.. l..'
De berekening van de correlatiefuncties verloopt als volgt:zodra een nieuwe
37
meetwaarde binne~komt wordt deze meetwaarde meteen verwerkt.De oudste-waarde in de buffer wordt overschreven door deze nieuwe meetwaarde en de pointer "ge-update". Voor bij voorbeeld tflch~Dmet O~ i~t__ 1 wordt aan de inhoud van crosscfic [i] de volgende vermenigvuldiging bi) opgesteld: crosscfic [i1 :~rosscfic [ij + bufcfdur Lpointl x buficft [(point + 1) mod mult] Aan het einde van de simulatie bevatten de buffers nog meetgegevens die verwerkt moeten worden.Bij elke vermenigvuldiging wordt de oudste-waarde door een 0 overschreven en de pointer "ge-update". [en en ander zal met behulp van onderstaand voorbeeld worden verduidelijkt.
voorbeeld 2 De rij meetgegevens van de recovery-duur is: 3,1,3,8,2,5,4. De rij meetgegevens van de inter checkpointtijd is: 1,7,6,3,2,5,9. In totaal zlJn er dus 7 meetwaarden voor elk van de rij meetgegevens.We stellen i~~ 4, dus mult is 5. In onderstaand figuur 4.a~a) is de inhoud van beide buffers getekend telkens nadat er een nieuwe meetwaarde voor de recovery-duur en de intercheckpoint-tijd is binnengekomen. De buffer bufcfdur is boven getekend. 7fc.f i c. (0) wordt nu als voIgt berekend: voor elk van de bufferinhouden boven en onder wordt de inhoud van de bovenste buffer aangewezen door de aangewezen door de pointer vermenigvuldigd met de inhoud van de onderste buffer, aangewezen door ce bijbehorende pointer. (NB. deze pointer is dezelfde pointer die de oudste waarde in de buffer aanwijst). Al de vermenigvuldigingen worden bij elkaar opgeteld. figuur 4.8\.a) inhoud buffer bufcfdur:
1 3~
8~'
2
.5-
inhoud buffer buficft:
~IT·~] } ~T' ~ J'-tj ~ J-~-] ~. I~~ l~-~. ~--i'}+rl ~ o o
+ 0 + a + 0 + 3 + 7 +18 + 0 + 0 + 0 + 9 + 2 +15
38
De berekening vanVq;,~)wordt aan het einde van de simulatie afgerond. In figuur 4.8'b) is de inhoud van beide buffers getekend telkens nadat een 0 is ingevuld voor de oudste-waarde. Het afrondsn van de berekening van Yq(c~)verloopt op dezelfde wijzs als boven. We zien dat~'fic(O) overeenkomt met'¥e-lilo)van voorbseld 1 "7 figuur 4.8 (b) inhoud buffer bufcfdur:
inhoud buffer buficft:
rg'J
! 9 ....J -:.' 9 ' f .r-g','J JL 10+liOO !3' ~o 10 '0 121:~,:o 0-
i~
L:::....
~5.~O -'-'. 1 _
.L.J
+ 24+ 4+ 25+ 36 + 72+ 0+ 0+ 0 Op dezelfde wlJze kan 1fchc(3) worden berekend. Aileen moet aan de pointer van de buffer buficft een offset 3 worden gegeven.
(einde voorbeeld)
Uit hat voorbsald zien we dat hat gaan zin heaft een vermenigvuldiging uit te voeren als de buffer nog niet vol is.oe berekening wordt gestart zodra de conditie nf=mult waar is. nf is het aantal fouten. (N.B. nf is gelijk aan ncfdur)
Samenvattend kunnen we zeggen: de auto-correlatieco~fficiMnt ~/qa)geeft inzicht in de afhankelijkheid tussen de recovery-duren ondarling. - de kruis-correlatieco~fficienten ref it: (0) en "(.e. c/ (0) geven inzicht in de afhankelij kheid tussen de recovery-duur en de ermee cor"esponderende intercheckfailure-tijd.
39
4 . 3. 3 . 3
~l e tin 9 van Ge a v ail aJLi 1 i tv end e 9 u e u e ..lan 9 t e • Met de availability zijn de volgende twee variabelen geassocieerd: - CIQ geeft de totale gesimuleerde tijd weer. - tut = total unavailable time: geeft de totale jesimuleerde tijd weer waarin het systeem bezig is geweest met een checkpoint of een failurepoint. De availability is nu: clg - tut clq
Met de queue ZlJn de volgende variabelen geassocieerd: - CIQ geeft de totale gesimuleerde tijd weer. - nq geeft het totaal aantal transacties l=entries) weer. - maxq: geeft de maximale queuelengte weer welke in de simulatie is geregistreerd. geeft het totaal aantal transacties weer welke na - zq aankomst direct verwerkt konden worden. - ctiq= cumulative time integral queuelength: geeft de sam van de pradukten tussen de queuelengte en de tijdsduur waarover die queuelengte geldt. Zie figuur 4. - stti: hulpvariabele: variabele welke nodig am de cumulatieve tijd integraal van de queuelengte te berekenen. - glength: geeft de queuelengte weer. De gemiddelde queuelengte is nu: ctig clq figuur 4.9
J~
D_
t. cJ tot cs t:.(. --~~ I:. ctiq= l-(t -t )+2-(t -t )+l~\t -t )+l·lt -t ) 2 i J:2 4 J b Ii I:.,
4.3.3..
Meting van de k-waarde tijdens een sample-points zullen eerst onderzoeken hoe de verdeling is van het aantal sample-points. ~e veronderstellen hierbij dat: de intercheckpaint-tijden exponentieel verdeeld zijn met gemiddelde A,-1 de sample-points equidistant zijn. De tijd tussen twee sample-points is L~ samples worden alleen in de available-tijd genomen de tijd tussen het eerste sample-point en het laatst genomen checkpoint is L$ Zie oak figuur 4.10
~e
40
figuur 4.10
Het aantal sample-points in een inter checkpoint-interval wordt voorgesteld door n. De tijd tussen twee checkpoints wordt aangeduid met ict. 00
P[;rJ=n.]:= o :=.
f P[t!2:=.nl
ie/;
Ch-t')~
ji
/Lc. e - ?c. edf
n4
- -e.. ( 4.54 ) waarbij:
- .e
=l:Jrc iet::!;]
- ?.cLin
- ).c.
L~ /J7.
-e. (
-).c L~ (n+1)
:1-i?..
- .Ac..
/
0 iPIdivn.
r[
=- f J :=:. ~ :1
.n. () I:. = {:1. -.e.
-;"cLp)n
rrJ. == n J ic t
L$) t. ~ [nL;t /lH-l)Ls)
~11
l/VIcbvYl. /:; e. [n L$ J ) L1 ) NB. Uit ( 4.54) is meteen te zien dat de distributielllt) van de tijden tussen het laatst genomen checkpoint en een sample-point is gegeven door:
l 4.55 )
L-1
h;;o
e
-)cL,n
6 (-t ..(n+ ,)L:5)
.
Tijdens de sample-points wordt de k-waarde bepaald.Deze kwaarde is: busyt nst waarbij (zie ~1.3.2.1. en §1.3.2.2) busyt de totale busytijd geeft tot aan het sample-point, en nst het tijdstip waarop het sample-point is genomen. We willen het verloop van de verhouding busyt / nst voor de verschillende sample-point tijdstippen bestuderen.Voor elk sample-point tijdstip wordt een frequentieverdeling gemaakt van de bij dat sa~ple-point behorende gemeten verhoudingen busyt / nst. Van deze frequentie verdeling wordt het gemiddelde en de standaarddeviatie berekend. Tenslotte wordt het gemiddelde over aIle gemeten verhoudingen busyt / nst bepaald. We definieren de volgende variabelen: - tmeanicft: theoretisch gemiddelde intercheckpoint tmeanicft:=ia c
411
- rangeicft
geeft het~ngeg~bied aan waarin we de verschillende sample-pol~t tijdstippen willen bestuderen (=~+ 96). rangeicft:= rangeicft:= lOx tmeanicft. - kicft geeft het aantal klassen weer, inclusief een over- en underflow-klasse. Het aantal klassen waarin rangeicft wordt verdeeld is (kicft -2) Elke klasse binnen het rangegebied (klasse 2 tim klasse (kicft-l)) komt overeen met een sample-point. De gebruiker geeft een waarde voor kicft. Het programma berekend daaruit wat de tijdsduur ,tussen twee sample-points moet zijn. Deze tijdsduur wordt gesymboliseerd door de variabele tsample: tsample:= rangeicft l(kicft-2) Merk op dat de underflow klasse (klasse 1) nooit gevuld zal worden, omdat geen samplepoint samenvalt met tijdstip waarop de checkpoint-duur eindigt. - rangerbi geeft het rangegebied aan waarin we de verhouding busyt I nst willen bestuderen. Er geldt busyt I nst~ 1 zodat rangerbi nooit grater kan zijn dan 1. Rangerbi wordt door de gebruiker gegeven. - krbi : geeft het aantal klassen weer waarin de verhouding busyt I nst in onderverdeeld moet worden. -frbi = array frbi ~: kieft, 1: krbi]: De i-de rij van deze matrix bevat de frequentieverdeling welke bij het i-de sampe-point behoort. nrbi = array nrbi [1: kicft ] : Het i-de element bevat de totale sam van het aantal observaties voor de verhouding busyt I nst welke bij het ide sample-point behoort. tsrbi = array tsrbi [1: kicftJ : Het i-de element bevat de totale sam van de verhoudingen busyt I nst welke bij het i-de sample-point behoort. tsqrbi = array tsqrbi [1: kicft] : Het i-de element bevat de totale sam van het kwadraat van de verhoudingen welke bij het i-de sample-point behoort. Het gemiddelde van de verhouding busyt het i-de sample-point is:
t s r b i [iJ I n r b i en de standaarddeviatie is : s qr t
I
nst behorende bij
[11
(t s q r b i ~i] - t s r b i CiJ
*"
t s r bi
rill nr(nrbi b i [il
Het gemiddelde over alle gemeten verhoudingen busyt is: 4.iCfe / Jdej1-
iF1.
De procedures en de
tFK.b i
[d
l~
nrbi
[i J
presentatie van de statistiek
I
~-i-
nst
-1)
42
4.3.4. 1 0 e De 1. 2. 3. 4. 5. 6.
pro c e d ures volgende procedures worden gebruikt: grafics text 1 text 2 text 3 snap error
De procedures 1,2.3 en 6 zijn reeds in §3.3.5 van het vorige hoofdstuk behandeld. ad 4 procedure text 3 (max,n,z,cti, queuel, tuum, cl); inleger max, n,Z, queoel, tnum; real ctl, cl; verklaring van de formele parameters max ~ geeft de maximale queuelengte welke in de simulatie is geregistreerd. n het totaal aantal transacties (=entries) z het totaal aantal transacties die direct na aankomst verwerkt konden worden (=zero-entries) cti = cumulative time integral: geeft de sam van de productten tussen de queuelengte en de tijdsduur waarover die queuelengte geldt. queuel: geeft de momentane queuelengte weer tnum = table number: identificatienummer voor de queuegegevens ingeval meerdere queues aanwezig zijn: cl : geeft de totale gesimuleerde tijd weer. De proceduretext 3 drukt in volgorde af: max, de gemiddelde gueuelen~te (=ctilcl), n, z, het percentage zero-entries \=z/~*lOO), de gemiddelde tijd dat een transactie in het systeem aanwezig is (=cti In), de gemiddelde tijd dat een transactie in het systeem aanwezig is indien de zero-entries worden verwaarloosd (=cti/(n-z), tnum en teslotte cl. ad 6 procedure snap (snapnr, 1, ciq, ctiq, tut, nf, ng, nn, mean, text, final); inleger snapnr, 1, nf, ng, nn; real clq, ctiq, tut, mean; bOOT'8'an text, final; Verklaring van de formule parameters: snapnr= snap report namber: geeft het nummer van het tussentijdse rapport weer. 1: geeft het aantal doorlopen cycli weer. Onder een cyclus wordt verstaan de periode tussen het einde van de (i-l ) checkpointsewiceduur en het einde van de i-de checkpointse iceduur. clq: geeft de gesimuleerde tijd weer. ctiq = cumelative time integral: geeft de sam van de produc~en tussen de queuelengte en de tijdsduur waarover die queuelengte geldt • tut = total unavailable time: geeft de gesimuleerde tijd weer waarin het systeem bezig is geweest met een checkpoint of een failure point. nf(=ncfdur ): geeft het aantal fouten weer.
ng: geeft het aantal transacties weer. nn: geeft het maximaal aantal te doorlopen cycli weer. mean: aan deze variabele moet het gemiddelde overalle gemeren verhoudingen busyt/ nct worden toegekend. text: met text kan aangegeven worden of tekst afgedrukt moet worden boven de kolommen. final: door aan final de waarde true toe te kennen wordt een final report geproduceerd. Met behulp van de procedure snap kunnen tussentijdse rapporten worden geproduceerd. De tussentijdse rapporten geven inzicht in has het convergentieproces verloopt. Achtereenvolgens wordt afgedrukt: - het snapnr - het aantal doorlopen cycli. de availability (= (clq - tut) / clq)) - de gemiddelde queuelengte (= ctiq / clq) - de k-waarde ~~
L
i= 1.
(;~rbi
Cd
It.
nrbl [i] . ) gemiddelde aantal transacties l=nq/l totaal aantal transacties (=nq) gemiddelde aantal fouten (= nf/2) totaal aantal fouten (=nf) t-
4.3.4.2
j
het - het - het - het De presentatie van de gegevens De gegevens warden in de vorm van rapporten gepresenteerd. Afgedrukt warden successievelijk: - de snap printout reports. Deze rapporten warden door de procedure snap geproduceerd. het rapport aver de verdelingsfunctie van de recoveryduur. Dit rapport is vrij uitgebreid. Afgedrukt wordt: - het gemiddelde en de standaorddeviatie. Dit wordt gedaan met procedure text 1. - de verhouding van de standaarddeviatie en het gemiddelde. - de frequentie-tabel, geproduceerd met behulp van procedure text 2 - frequentie-dia~ram, verzorgt door de procedure grafics. - een tabel waarin per frequentiekla~se - het percentage wacrgenomen abservaties wordt vergeleken mEt het percentage dot we in die frequentieklasse verwachten. Hierbij gaan we uit dat de recovery-duren exponentisel verdeeld zijn met gemiddelde k x iatc ; k=p/A - de absolute afwijking: absolute afwijking= gemeten - berekend - de relatieve afwijking: relatieve afwijking= - de verhouding gemeten/berekend.
gemeten-berekend berekend x
lOO~ /0
44
- het rapport voor de correlatie functies (4.44),(4.45) en (4.46). Afgedrukt wordt: - het aant~l waarover gesommeerd wordt. oit aantal is het totaal aantal transacties verminderd met de index n waarover verschoven is. -de index n waarover verschoven is. - de auto-correlatiefunctie V~qC~) - de kruis-correlatiefunctie ~~ce!C~) - d e kr u i s - cor r el a tie f U Ii C tie 1j '-he C~ ") - het rapport voor de correlatieco§ffici~nten. oit rapport heeft dezelfde structuur als het rapport voor de correlatiefuncties In plaats van de correlatiefuncties worden de correlatiecoeffieienten r"Cfcf Crt), rCc.cfCn..) -e,n.. reflcC.n..) afgedrukt. - het rapport over de k-waarde. Afgedrukt wordt: - voor elk sample-point (welke overeenkomt met een klasse) het gemiddelde en de standaarddeviatie van de bijbehorende frequentieverdeling. - een diagram waar per sample-point het gemiddelde wordt afgedrukt. Uitgezat is dus de k-waarde tegen de tijdstippen waarop de samples zijn genomen. - de matrix frbi. Elke rij komt overeen met een sample-point, en toont de bijbehorende frequentieverdeling. Elk kolom is dus een klasse. De interpreeatle van het element frbi [i,j] is dus: het aantal observaties in de j-de klasse van de frequentieverdeling behorende bij het i-de sample-point is frbi [i,jJ - het queuereport. oit report wordt geprodueeerd met de procedure text 3 - Tenslotte wordt er een final reoort geproduceerd. 4.3.4.3
~nvoer van de parameter-waarden Aan de volgende parameters moet een waarde worden toegekend. - p, 9 e s Ymb 0 lis e e r d door rho - ~-i, 9 e s Ymb 0 lis e e r d d 00 r c-.t.f - "', 9 e s Ymb 0 lis e e r d d 0 0 r sur:: -)l~ gesymboliseerd door sui: - nn, het aantal cycli dat gesimuleerd moet worden. kieft, hiermee wordt tsample (= de tijdsduur tussen twee sample-points) bep2~ld:
_ IOdate tsample - (kicft _ 2) - krbi, het aantal klassen waarin de gemeten verhoudingen busyt / nst worden onderverdeeld. - kcfdur, het aantal klassen waarin de gemeten recoveryDuren worden onderverdeeld. i, het initiatie getal.
45
rangebi, het r~nge-gebied waarin we de gemeten verhoudingen busyt / nst willen besehouwen. - snapint, geeft het interval aan, uitgedrukt in eyeli, tussen twee snap printout reports. - mult, geeft de maximale versehuiving aan dat we willen besehouwen bij de eorrelatiefuneties en bij de eorrelatieeoeffieienten. De volgorde waarin de parameters aan het CRR-simulatieprogramma moet warden aangeboden is: Data-kaart 1: rho, iatf, sere, iate Data-kaart 2: nn, kieft, krbi, kefdur, i, rangerbi, snapint, mult,
46
4
De Simulatie
4.1
De voorbereiding Alvorens we het CRR-systeem gaen simuleren met het CRR-simulatieprogramma moet een goede keus worden gemaakt voor de waarde die aan de parameters en~ moet worden toagekend. Daze twee parameters bepalen immers in het r~arkov-model de O(ap!., A -lijn, de ergodici tei tsgrens en de availabili tynullijn in het (01. -Jip)-vlak. Een goeda keus blijkt 1000 en i~ 150 ta zijn. De bovengenoemde curven zijn in figuur 4.11 getekend. Zie ook de figuren 4.3 tot en met 4.7 in 34 • 24 • Binnen hat ergodiciteitsgabied is de maximale variatiegebied voor? gegeven =(Vtt)"1 3~~.29B ( Zie 4.2.2.3), waarvoor
t
ri:
bijC<.;tt
jJo == (1+.2. Figuur 4.11
(f) ,-
a a
N
a
a
.q
== 0.56
a a
\0
-
a a
co
a a a
....
a
a a
.... N
a
-tr
....
a a
.... \0
a a
co
....
a a a N
a a
N N
a a
a a
a a
N
N
N
-tr
_.&._--+.-------- - - - - - - - - - +
0.1
0.2
+
+
0.3
+
+
0.4 0.5 0.6
0.7 0.8
0.9 1.0
+
\0
co
47
Binnen het ergodiciteitsgebied worden een aantal punten geselecteerd waarvoor het CRR-systeem gesimuleerd zal worden. De in totaal 36 punten zijn in figuur 4.9 getekend.De simulatieduur wordt bepaald door het aantal te verwachten fouten, die we ± 5000 stellen.Hieruit wordt het aantal cycli berekend. AIle parametergegevens zijn in tabel 4.1 onderbracht. TA8EL 4.1 Overzieht ven de perametergegevens rho
iatf
sere
sert
iate
nn
kieft
krbi
kefdur
i
rangerbi
snapint
mult
0.10 0.20 0.30 0.35 0.10 0.20 0.30 0.35 0.40 0.45 0.50 0.10 0.20 0.30 0.35 0.40 0.45 0.50 0.10 0.20 0.30 0.35 0.40 0.45 0.10 0.20 0.30 0.35 0.40 0.10 0.20 0.30 0.10 0.20 0.10 0.20
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150 150
1.0 2.0 3.0 3.5 1.0 2.0 3.0 3.5 4.0 4.5 5.0 1.0 2.0 3.0 3.5 4.0 4.5 5.0 1.0 2.0 3.0 3.5 4.0 4.5 1.0 2.0 3.0 3.5 4.0 1.0 2.0 3.0 1.0 2.0 1.0 2.0
200 200 200 200 400 400 400 400 400 400 400 600 600 600 600 600 600 600 800 800 600 BOO 800 BOO 1200 1200 1200 1200 1200 1600 1600 1600 2000 2000 2400 2400
25000 25000 25000 25000 12500 12500 12500 12500 12500 12500 12500 8333 8333 8333 8333 8333 8333 8333 6250 6250 6250 6250 6250 6250 4167 4167 4167 4167 4167 3125 3125 3125 2500 2500 2083 2083
102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102 102
22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22
52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52 52
1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980 1174980
1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0
200 200 200 200 100 100 100 100 100 100 100 67 67 67 67 67 67 67 50 50 50 50 50 50 33 33 33 33 33 25 25 25 20 20 15 15
51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51 51
4.2
De meetgegevens & bespreking daarvan
4.2.1
Meetgegevens betreffende de aangenomen veronderstellingen in het Markovmodel. We herhalen de aangenomen veronderstellingen: 1. De distributie van de recovery-duur is exponentiael. 2. De gemiddelde recovery-duur is k maal de gemiddelde duur tussen twee checkpoints. 3. De recovery-duur is onafhankelijk van de ermee corresponderende intercheckfailure-tijd. 4. De recovery-duren zijn onderling onafhankelijk.
48
Alvorens we op de bestudering van de distributie van de recovery-duur ingaan zullen we de gemiddelde k-waarde van elk van de verschillende sample-points bestuderen.De gemiddelde k-waarde behorende bU het i-de sample-point wordt berekend volgens:
tsrbi[ iJ nrbi. [L] We zetten deze gemiddelde k-waarden uit tegen het bUbehorende samplepoint.Omdat het sample-point overeenkomt met een vast interval tussen het laatst genomen checkpoint en het sample-point kunnen we ook zeggen de gemiddelde k-waarden worden ui tgezet tegen de bijbehorende vaste intervall en • Opmerking: In de inleiding §4.1 hebben we geschreven:
Ib~J<) II: b~.U) It b~Jc)
PUb~tbl ~,=U =
tb
(41
dI:
J
o
zodat de gemiddelde k-waarde die we meten overeenkomt met: Ci ti
k/:.:.1.t· l
L
0
L
de :.
0
L ~i
d.1:
(4.56)
waarbU k!.de k-waarde is bU een vaste interval met tUdsduur L Voor het punt figuur 4.12.
p=
ti'
0.3 en iatc = 600 krijgen we het diagram getekend in
Figuur 4.12 0.9
Qr 06 O.:l
In het diagram kunnen we drie gebieden onderscheiden: Gebied I : Voor zeer korte intervallen is de gemiddelde k-waarde groot. Deze neemt sterk af als de interval-tUdsduur groter wordt. Gebied II In dit gebied neemt de gemiddelde k-waarde langzaam toe met toenemende interval-tUdsduur. Gebied III : In dit gebied neemt de gemiddelde k-waarde sterk toe,en nadert voor zeer grote intervallen naar 1. In figuur 4.1 3 is een gestyleerde diagram getekend.
49
Figuur 4.13
1.0
P.z>f,
0.8
0.6 0.4
kb·
r
, 1IJ:
02-
I
7
I
0.0
-"~-"/f~ti.
We beginnen eerst het verloop van de k-waarde in de gebieden II en III te verklaren. 1. Beschouw in gebied II een willekeurig gekozen interval. Treedt in dit interval een fout op,dan zal er tUdens de recovery-actie een queueopbouw plaatsvinden.Deze queue wordt direct na de recoveryactie verwerkt,wat een extra toename van de totale busytijd betekent. De extra toename in de totale busytUd heeft gevolgen voor de volgende recovery-actie die daardoor langer duurt dan wanneer de vorige recoveryactie niet plaats zou hebben gehad.Dit heeft weer gevolgen voor de queueopbouw tUdens die volgende recovery-actie en dus ook voor de verwerkingstUd ervan.We zien dat hier een meekoppelend effect optreedt. Dit meekoppelend effect is er de oorzaak van dat de gemiddelde k-waarde in gebied II een groeiend verloop heeft. Op een gegeven moment zal de interval-tUdsduur zo groot geworden zijn dat het interval een punt zal bevatten van waaraf de gemiddelde queueopbouw zo groot is geworden dat deze queueopbouw niet meer afgebroken kan worden in de gemiddelde available-tijd tussen de failurepoints.Op dat moment vindt de overgang naar gebied III plaats. 2. In gebied III zullen de availabletUden tussen de failurepoints vanaf het bovengenoemde punt,dat we verzadigingspunt zullen noemen,een hoge bezettingsgraad hebben.Deze bezettingsgraad nadert tot 1 (=volledige bezetting van de availabletijd) naarmate de availabletUden verder van het verzadigingspunt zijn verwUderd. De bijdrage van deze hoog bezette availabletijden tot de gemiddelde k-waarde verklaren het verloop van de k-waarde in gebied III. Omdat na het verzadigingsspunt de queueopbouw niet meer wordt afgebroken zal de queue blUven groeien.We zeggen dat intervallen in gebied III explosief zUn. 3. Beschouw nu gebied I.Net zoals er tUdens een recovery-duur een queueopbouw aanwezig is,is er een queueopbouw tijdens een checkpoint.De afbouw van deze queue zal vee I van de available-tUd direct na een checkpoint in beslag nemen. Vandaar dat voor zeer korte intervallen de k-waarde groot is. Samenvattend kunnen we zeggen: • De queueopbouw tijdens een checkpoint is verantwoordelUk voor het gebied I. • Het meekoppelend effect is verantwoordelUk voor de toename van de k-waarde in gebied II. • Het explosief karacter welke voor lange intervallen optreedt is verantwoordelijk voor gebied III.
50
Het toenemen van de gemiddelde k-waarde in de gebieden II en III zijn het directe gevolg van de afhankelijkheid tussen de recovery-duren onderling in een en hetzelfde interval.lndien deze afhankelijkheid afwezig is,zoals in het Markov-model,dan zal de k-waarde een horizontaal verloop in de gebieden II en III hebben.Het verloop van de k-waarde zoals in gebied I zal ook voor onafhankelijke recovery-duren aanwezig zijn. De overgang van gebied I naar gebied II is afhankelijk van: 1. De gemiddelde tijd welke nodig is om de gemiddelde queueopbouw tijdens de gemiddelde checkpointsduur af te breken. Deze tijd is:
(4.51 ) 2. TIjdens het afbreken van bovengenoemde queueopbouw zal,doordat transacties blijven arriveren,er een extra queueopbouw ontstaan.De gemiddelde tijd om daze extra queueopbouw af te breken is:
f
(i )-1 ).L.i =
73.A
TIjdens deze tijd ontstaat weer een queue die ook weer afgebroken moet worden. Dit gaat zo verder,zodat de totale gemiddelde tijd om al deze extra queueopbouw af te breken is:
p'J. oo
pn._
~ ~
P>
fl.:.0
-
~
1:. --E-
f3
1.-
f
(
\
4.59 )
Samenvattend: De overgang van I naar II is afhankelUk van:
P+P ..E..-)_.i. -E( j3 [3 ·1-p - f>' :J..-p
(460)
.
In diagram 4.13 zal gebied I naar links verschui ven indien ~.6D)kleiner wordt. De overgang van gebied II naar gebied III is afhankelijk van: 1. Het meekoppelend effect. Hoe groter het meekoppelend effect des te eerder zal het verzadigingspunt worden bereikt. Het meekoppelend effect is afhankelijk van: 1. De loadp. Een grotere p zal een hogere bezettingsgraad van de available-tijd inhouden. Dit houdt in dat ook de gemiddelde busytijd tot aan een failurepoint groter wordt, waardoor de bijbehorende recovery-actie langer zal duren, waardoor ••• etc •• Het meekoppelend effect wordt bij grotere p vergroot. 2. De failure rate t . Hoe groter de failurerate des te vaker zal er een fout optreden, en dus zal er vaker een recovery-actie plaats vinden. De queueopbouw tijdens deze recovery-acties zorgen ervoor dat het meekoppelend effect wordt vergroot. 3. De intercheckpoint-tij d cx-~ ~ Laatot\oenemen bij constantejO. De gemiddelde queuelengte zal toenemen omdat: 1. Het aandeel van de queueopbouw in de explosieve intervallen zal toenemen in de berekening van de gemiddelde queuelengte
51
over aIle intervallen. 2. De gemiddelde queueopbouw in een explosief interval toeneemt naarmate dat interval langer duurt. Een groter gemiddelde queuelengte betekend dat de verwerking eruan langer zal duren,en dus zal de gemiddelde busytUd tot aan een failure point toenemen, waardoor de recovery-actie langer zal duren, waardoor ••• etc •• off Laato(~fnemen bij constante p. Het aandeel van de queue in de korte intervallen zal toenemen in de berekening van de gemiddelde queuelengte over aIle intervallen. Voor de korte intervallen zal de bijbehorende interval-tijdsduur onvoldoende zijn om de gemiddelde queueopbouw tijdens een checkpoint af te breken. Deze queueopbouw zal tijdens volgende intervallen afgebroken moeten worden. Een groter gemiddelde queuelengte is hiervan het gevolg. Deze gemiddelde queuelengte zal verder toenemen wanneer~·1 kleiner wordt. Een groter gemiddelde queuelengte zal zoals we boven hebben gezien een groter meekoppelend effect veroorzaken. Merk op dat bij toenemende oc.-het meekoppelend effect zichzelf versterkt. Samenvattend: Het meekoppelend effect is afhankelijk ten: 1.
pt 0(.-1
(4.61) (4.62)
2. ad1. Hoe groterptdes te eerder zal het verzadigingspunt worden bereikt. Gebied III verschuift in de diagram in figuur 4.14 near links. ad2. Kies op de lijn jJ= constant een ot1voldoende klein zodat het affect van korte intervallen op de gemiddelde queuelengte zichtbaar is. Laat ~·1toenemen, dan zal het meekoppelend effect in eerste instantie afnemen en zal toenemen wanneer het effect van de explosieve intervallen op de gemiddelde queuelengte zichtbaar wordt. Gebied III zal dus in eerste instantie naar rechts verschuiven en dan naar links • 2. Indien de failurerate t toeneemt zal behalve dat het meekoppelend effect groter wordt, de available-tijd tussen twee failurepoints korter worden. Hierdoor zal er minder tijd aanwezig zijn om de queueopbouw tijdens een recovery-actie af te breken. Het verzadigingspunt zal daardoor (afgezien van het meekoppelend effect) eerder bereikt worden.
Het meekoppelend effect is de oorzaak dat in gebied II de k-waarde een groeiend verloop toont. Door hat meekoppelend effect groter te maken, zal het groeiend verloop sterker worden. In figuur 4.14 zijn de gemeten diagrammen voor de k-curve te zien voor respectievelijk p= 0.1, p= 0.3 en p= 0.5. De intercheckpoint-tijd is constant:~-~ 600. De effecten als boven beschreven zijn hier duidelijk te zien. In figuur 4.1 5 zijn de gemeten diagrammen voor de k-curve te zien voor respectievelijk 0/-'=400, ",-'= 6 00, ",-'= 8 00 an 0(=1200. p is constant: .P = 0.35.
52
f ill-t.Lur 4.14
1.
"----~p,,~o.s--------~-----------------
a6 Q5 :D.~
a4
a3 Q:Z
.J
r
Ql
~
n .. C).I J
figuur 4.15
53:
Overeenkomstig het (ci;p)-vlak, behorende bij het Markov-model, bevat het (o(~ p )-vlak, behorende bij het CRR-systeem een ergodici tei tsgrens. Beschouw in dit (o€"; p )-vlak dQ lijn p= constant, dan bevinden zich op deze lijn de ergodic~teitsgrenzen o(~J.eno<.~J., waarbinnen o(-:l.mag variaren. if Kies een o<'-~odanig dat het CRR-systeem stabiel is. Laat oCLafnemen, dan zal een punt~L-Jbereikt worden waar de gemiddelde intercheckpoint,tijd ontoereikend is om de gemiddelde queueopbouw tijdens een checkpoint volledig af te breken. De queuelengte zal dan onbeperkt blijven groeien. Het systeem is dan instabial. Het punt a~Lop de lijn )0= constant zal groter worden indien de lijn )D = constant voor een grotere waarde van jO wordt beschouwd. Dit is te verklaren doordat de verwerking van de queueopbouw tijdens een checkpoint afhankelijk is van p. Daze verwerking zal langer duren naarmata .p groter wordt. Hat punt OI'/zal daarom bij afnemende 0(-1eerder bereikt worden. .~ if Kies een oc-1 zodanig dat het systeem stabiel is. Laat 0( toenemen. Dan zal: 1. Het aantal explosieve intervallen in een (oneindig) lang beschouwings interval toanemen. 2. De queueopbouw tijdens een explosief interval in de volgende intervallen moeten worden afgebroken. Hierdoor zullen deze volgende intervallen een hogere bezettingsgraad hebben. Door het meekoppelend effect heeft dit gevolgen voor de eigen queueopbouw, waarvan de verwerking ook opgeschoven zal worden. Zijn er voldoende korte intervallen aanwezig, dan zal uiteindelijk de queueopbouw volledig worden afoebroken. Blij ft 0(-1 toenemen dan zal op - een gegeven moment een punt O(;lworden worden bereikt waarin het aantal korte intervallen onvoldoende is am de queueopbouw tijdens een explosief interval volledig af te breken. Het systeem is dan instabiel, en de queuelangte zal onbeparkt blijven groeien. Het punt d~10p de lijn }'= constant zal kleiner worden indien de lijn p = constant voor een grotere waarde voor fJ wordt beschouwd. Di t is te verklaren doordat het meekoppelend effect afhankelijk is van jO waardoor het verzadigingspunt in een interval eerder wordt bereikt, waardoor het aantal explosieve intervallen in een (oneindig) lang beschouwings interval zal trenemen, waardoor het aantal korte intervallan zal afnemen, waardoor net punt ~:~erder wordt bereikt. De punten 0(1 en 0(;" op de lijn f = constant zal voor een zekere f aan elkaar gelijk worden. Buiten het ergodiciteitsgebied zal voor hat CRR-systeem in een (oneindig) lang beschouwings interval gelden : k = 1. In het Markov-model hebben we gezien dat bui ten het ergodici tei ts gebied k? 1 is. Beschouw het ergodici tei tsgebied in het (cx'-~f )-vlak, behorende bij het CRR-systeem. if Dicht bij de ergodiciteitsgrens geldt: 1. k nadert tot 1. 2. Derhalve zal de busytijd t b de intercheckfailuretijd tcfbenaderen. 3. Derhalve zal de distributie van de busytijd en derhalve de distributie van de recovery-duur t r de exponentiale distributie benaderen met een gemiddelde (['. if Beschouw de lijn p = constant met p« 1. Dan is in de uitdrukking (4.60) voor de gemiddelde verwerkingsduur de tweede term (4.59) te verwaarlozen. De gemiddelde verwerkingsduur voor
54
de queueopbouw ti~dens een checkpoint wordt dan: jP/~. 1. Veronderstel 0( 'is voldoende klein, d.w.z.:
* * *
cCj.
>p/f3 .
.1
De busy-perioden tussenp/f3 en 0( zijn te verwaarlozen. De bijdrage van intervallen, met een tijdsduur t, die kleiner zijn dan p7~, tot de distributie van de recovery-duur is verwaarloosbaar. De distributie van de recovery-duur zal onder bovenstaande voorwaarden de hypo-exponentiale distributie benaderen. Immers: 1. Beschouw intervallen met een tij dsduur t i waarvoor .p/~ ~ 1:.1. <. oC 1geldig is. 2. Deze intervallen zullen allen dezelfde busytijd meten waardoor de variantie in de gemeten busy-tijd en dus de recovery-duur klein is. Een kleinere variantie in de recovery-duur betekend dat de distributie hiervan de hypo-exponentiale distributie benadert. 2. Laat toenemen onder de volgende condities: De busy-perioden tussen P /(!J en ~zijn niet meer verwaarloosbaar. De bijdrage van intervallen, waarin het meekoppelend duidelijk zichtbaar is, tot de distributie van de recovery-duur is verwaarloosbaar. Dan zal de distributie van de recovery-duur de exponentiale distributie benaderen. Immers: 1. Voor een lage load geldt: t b = k timet k=1'111. 2. Derhalve zal de distributie van de recovery-duur de exponentiale verdeling benaderen met een geniddelde k/cC'. 3. Laat 0(-1 verder to enemen, waarin: De bijdrage van intervallen, waarin het meekoppelend effect duidelijk zichtbaar is, tot de distributie van de recovery-duur niet meer verwaarloosbaar is. Dan zal de distributie van de recovery-duur de hyper-exponentiale distributie benaderen. Immers: 1. Het meekoppelend effect is de oorzaak dat voor intervallen waarin dit effect duidelijk zichtbaar is de busy-tijd meer dan lineair toeneemt met toenemende interval-tijdsduur t i • 2. Hierdoor zal de bijdrage van grote busy-tijden toenemen en de bijdrage van korte busy-tijden afnemen. 3. Hierdoor zal de variantie in de gemeten busy-tijden toenemen. Derhalve zal de distributie van de recovery-duur de hyperexponentiale distributie benaderen 4. Indien Q(-J nog verder toeneemt, dan zal de ergodici tei tsgrens worden benadert. De distributie van de recovery-duur zal de exponentiale distributie benaderen met een gemiddelde D(-I. Samenvattend: Kies een d-/dicht in de buurt van O(Z'. Dan benadert de distributie van de recovery-duur bij toenemende or'achtereenvolgens de: 1. exponentiale distributie met gemiddelde p(.-/ • 2. hypo-exponentiale distributie. 3. exponentiale distributie met gemiddelde k 0<.'. 4. hyper-exponentiale distributie 5. exponentiele distributie met gemiddelde ~-~ • Beschouw de lijn f= constant met p« 1. Laat p toenemen. Dan is in de uitdrukking (4.60) voor de gemiddelde verwerkingsduur voor de queueopbouw tijdens een checkpoint de tweede term (4.59) niet meer te verwaarlozen. De busy-perioden tussen ~·4 en ci' zijn niet meer te verwaarlozen. Het llhypo-exponentiale II gedeelte op de lij n .p = constant zal bij toenemende derhalve verdwijnen.
* *
*
f
55
Samenvattend kunnen we concluderen dat er binnen het ergodiciteitsgebied gebieden zijn aan te wijzen waar de distributie van de recovery-duur een benadering is van de: ~ exponentiele distributie (64U=1). ~ hypo-exponentiale distributie (~<1). ~ hyper-exponenti~le distributie (~)1). Noeman we deze gebieden raspectievelijk het exponentiele- , het hypo- en het hyper-gabied. Bestuderen we de metingen met batrakking tot de recovery-duur. De Qemeten standaard daviatia s an hat gemeten gemiddelde is in tabel 4.3 voor elk van de simulatiepunten samengevat. De verhouding six is berekend. Met behulp van de tabel zijn de beide diagrammen in figuur 4.18a en b getekend: ~ In de diagram in figuur 4.18a is de verhouding six uitgezet tegen pvoor verschillende waardan van de intercheckpoint-tijd, uitgedrukt in iatc. ~ In de diagram in figuur 4.18b is de verhouding six uitgezet tegen de intercheckpoint-tijd voor verschillende waarden van p .
x
De tabel toont aan dat er gebieden zijn aan te wijzen die overeenkomen met de bovengenoemde exponentiele-, hypo- en hyper-gabied. Oak komt de ligging van deze gebieden overeen met waar we ze verwachten. Voor enkele curven is niet het volledige te verwachten verloop te zien omdat hiervoor nag te weinig simulatiepunten zijn genomen. In tabel 1. 2. 3.
4.2 is voor elk van de simulatiepunten gegeven: Het gemeten gemiddelde x De met het Markov-model berekende gemiddelde De absolute afwijking: absolute afwijking= gemeten waarde - berekende waarde
4. De relatieve afwijking: relatieve afwijking
__ gemeten waarde - berekende waarde berekende waarde
Met behulp van de tabel zijn de beide diagrammen in figuur 4.17a en b getekend • • In de diagram in figuur 4.17a is de relatieve afwijking uitgezet tegen de intercheckpoint-tijd voor verschillende waarden van p . ~ In de diagram in figuur 4.17b is de relatieve afwijking uitgezet tegenjO voor verschillende waarden van de intercheckpoint-tijd. De grootste relatieve afwijking die de tabel toont is 13.409 voor 1600 en p= 0.2 • We zien dat de relatieve afwijking een ongeordend positief negatief verloop heeft. We kunnen daarom concluderen dat het Markov-model de gemiddelde recovery-duur juist voorspelt. iatc~
In figuur 4.16· is voor iatc=200 en p= 0.2 de gemeten distributie voor de recovery-duur getekend. We herkennen hier duidelijk een hypo-exponentiele distributie, zodat dit simulatiepunt in hat hypo-gebied ligt.-
56
figuur 4.16
08
a1 06 a5 04
~~03
l~O.2
r ~~""-'--'-'-""1'"""T"'"'T""T'""T"""T"T--.--r-rT~~=;:::;::::;:'::::;:::r=;:::r"'!9"9"""l'...,.-rr"l'-r-?, °rl"1
Om de afhankelljkheid tussen de reeovery-duren onderling te bestuderen is voor p= 0.1, p= 0.3 en p= 0.5 de auto-correlatiecoefficient in een diagram getekend voor versehillende waarden van iate (zie respeetievelljk de figuren 4.19 (a), 4.20 (a) en 4.21 (a).Elk van de diagrammen toont aan dat van toenemende iate de auto-eorrelatieeoeffieient toeneemt.Oit was ook te verwaehten,immers voor toenemende iate zal het gemiddelde aantal fouten iate ook toenemen.Is de gemiddelde intereheekpoint-tljd constant bij toenemende , dan is geen toename in de auto-eorrelatieeoeffieient te verwaehten.In de diagrammen in figuur 4.22 (a) en (b) is respeetisvelUk voor iate= 400 en iate= 800 de auto-eorrelatieeoeffieient voor versehillende waarden van p getekend.Oe diagrammen bevestigen ons vermoeden alhoewel in de diagram van figuur 4.22 (b) een liehte toename van de auto-correlatie coefficient met toenemende p waarneembaaI" is. Om de afhankelljkheid tussen de recovery-duur en de bljbehorende intereheekfailure-tljd te bestuderen is op dezelfde wijze als boven voorp= 0.1, p= 0.3 en p= 0.5 de kruis eorrelatiecoeffieient in een diagram getekend voor versehillende waarden van iatc (zie respeetievelUk de figuren 1.19 (b) 4.20 (b) en 4.21 (b).Voor i= 0 zien we dat er een hoge correlatie bestaat. Ook dit was te verwaehten.
lA8El 4.2 ~atting maetresultaten; RBcouer~duur
lA8El
4.3
Del.
p
~tting meetresultaten: Recouery-duur
",-1
P
!lemeten
berekend
abs.af",.
rel. af",.
200 200 200 200
0.10 0.20 0.30 0.35
35.995 73.799 109.700 130.026
35.714 72.917 111.702 131. 720
0.281 0.882 -2.002 -1.694
0.787 1.210 -1. 792 -1.286
400 400 400 400 400 400 400
0.10 0.20 0.30 0.35 0.40 0.45 0.50
57.232 120.278 187.406 221.132 259.710 303.072 339.000
57.292 119.565 187.500 223.837 261.905 301.829 343.750
-0.060 0.713 -0.094 -2.705 -2.195 1.243 -4.750
-0.105 0.596 -0.050 -1.208 -0.838 0.412 1.382
600 600 600 600 600 600 600
0.10 0.20 0.30 0.35 0.40 0.45 0.50
79.365 168.353 279.708 343.373 409.706 462.602 539.689
79.787 170.455 274.390 332.278 394.737 462.329 535.714
-6.422 -2.102 5.318 11.095 14.969 0.273 3.975
-0.529 -1.233 1.938 3.339 3.792 0.059 0.742
800 800 800 800 800 800
0.10 0.20 0.30 0.35 0.40 0.45
104.730 225.014 376.275 453.093 550.674 681.092
103.261 226.190 375.000 461.806 558.824 667.969
1.469 -1.176 1.275 -8.713 -8.150 13.123
1.423 -0.520 0.340 -1.887 -1.458 1.965
1200 1200 1200 1200 1200
0.10 0.20 0.30 0.35 0.40
147.367 342.737 596.264 861.561 953.069
153.409 355.263 632.813 814.655 1038.462
-6.042 -11.526 -36.549 46.906 -85.393
-3.938 -3.244 -5.776 5.758 -8.223
1600 1600 1600
0.10 0.20 0.30
203.625 583.722 1015.138
208.333 514.706 1009.615
-4.708 69.016 5.523
-2.260 13.409 0.547
2000 2000
0.10 0.20
264.619 715.511
268.750 716.667
-4.131 -1.156
-1.537 -0.161
2400 2400
0.10 0.20
342.440 962.130
335.526 980.769
6.919 -18.639
2.061 -1.900
X
s
six
200 200 200 200
0.10 0.20 0.30 0.35
35.995 73.799 109.700 130.026
28.463 64.696 96.091 121.825
0.79074 0.87665 0.87594 0.93692
400 400 400 400 400 400 400
0.10 0.20 0.30 0.35 0.40 0.45 0.50
57.232 120.278 187.406 221.132 259.710 303.072 339.000
49.847 107.135 175.218 214.982 256.537 303.093 326.651
0.87096 0.89073 0.93497 0.97219 0.98778 1.00007 0.96357
600 600 600 600 600 600 600
0.10 0.20 0.30 0.35 0.40 0.45 0.50
79.365 168.353 279.708 343.373 409.706 462.602 539.689
72.451 163.266 285.541 394.123 432.464 466.976 553.169
0.91208 0.96978 1.02085 1.14780 1.05555 1.00945 1.02490
800 800 800 800 800 800
0.10 0.20 0.30 0.35 0.40 0.45
104.730 225.014 376.275 453.093 550.674 681.092
105.005 239.215 403.643 492.501 582.045 715.710
1.00263 1.06311 1.07273 1.00697 1.05697 1.05083
1200 1200 1200 1200 1200
0.10 0.20 0.30 0.35 0.40
147.367 343.737 596.264 861.561 953.069
155.525 378.852 665.518 959.249 965.506
1.05536 1.10216 1.11615 1.11338 1.01305
1600 1600 1600
0.10 0.20 0.30
203.625 583.722 1015.138
217.356 843.197 1291.170
1.06743 1.44452 1. 27192
2000 2000
0.10 0.20
264.619 715.511
334.991 959.076
1.26594 1.34041
2400 2400
0.10 0.20
342.440 962.130
451.390 1299.035
1.31816 1. 35017
13
58
13
12
12
11 10
'0
§
~
i0
Ii
a
~
~
Q,
Q,
S co
oS
4
S
oS'"
~
4
~
.=
l
.•
0,1
>
~i
I.'" "A
~
...
1
~ra
~
....
Zao
~
0,5
_1
---.E.....
-1
-2
-2
-J
-3
~
-s
-6
-6
-7
-7
-II
-II
~~
-a -10
~ toant __ _ do
I"'"
""aU.v• •'''djld.ng...v.. do _ apz1abtoo
d:l.agl''' toont .. ral.aUav. 1Ih11jk1ng v., eM g. . . ten recavery-dtAll' ten opzichte van . . ber_ende YOO1' vel'.chillenda • ••rd8n ven IArt: b1j . ~ _ p.
~
-a
eM benkende vour ftrach.111ende . - v. . f' bij vui'randol IArt:.
_10
-"
-11
-12
-12
-13 -14
1100
-4
-6
-13
figuur 17(a)
figuur 17(b)
-14
-'5
-15
1.26 1.26 1.24 1.24
1.22 1.22
1.20 1.20 1.1a
1.1S 1.1tS
1,16 1.14
1.14 1.12
1.12 1.10
1.10 I,OB 1.OS
'.06
lDJ'C 1.015
.s,'" £
.04
."
.02
1.04
=r·
.00
"'C
02
-
1.00
1400
1.ge 0.98 1.96
0.96
IA7C
1.94
0.94 1.92 0.92 1.90 1.88
1.8115
-
0.90 0.88
I
0.86
1.84
0.84
Zoo •
diagl''' toant d. vemaud1ng ...en d. g...ten standurddev1.U• • en h.t gemeten g-.1dd.ld1i i ven eN r.cavary-duur ,"001' verach1l1.,cte ...aerden van lATe bij \lui'ten" f' .
0.e2 o.SO
.; 0.78
f iguur' 1S( a)
IIII1.rda" van
p
bij v81'iil'Bnde lATe.
figuur l8(b)
0.76 0.74 0.72
diagr_ toont de vemouding van de g...ten _ gtand••rddeviatia s an hat g_ten gp1ddlilde )( van de recovery-dIAIl' VOOl' varschilland•
1
10
1.00
'5
0.95
10
59
0.90
f iguur 119(a)
L5
0.95
II
0.90
'9
0.75
'0
0.70
is
0.65
II
0.60
,5
0.55
0
0.50
5
0.45
0
0.40
5
0.35
0
figuur T9( b) ,-
0.:30 ~
c
=
5
E g
0
24DO
0
2a:D
~
0.25 0.20 0.15
~
0.10
0 0
~t 0.05
1
5
-
a~oo
.:Jt
in_i
1 indek 1
-
d189.... t-.~ dll ... to-corr.l.t1l1COlff1ciln~ "'8ft dB recov_ry-duur VOOI' ".r.chill8nd. ••ardon von lATe bij
d iagr_ toont d. kru1a-eorr.laUecolfflcilnt tuII• ., d. racav.ry-duur en d. reed. v.rlop.... .va11abl~Ujd vaal' v.uchilland. . . .rd.... "'8ft
-
p.-J.l •
lATe bij
-
p.-J.l .
-
figuur 20 (a)
figuur 20(b)
0.90 1 0.95
S
0.80 0.75
1
0.70 0.65 0.60 0.55 0.50 0.45 0.40 0.35 0.:30 0.25 0.20
1600
0.15 0.10 • 0.05
j
1
1ntl.x i d ugr.. toont d. 8uto-carnlatieco.rrlciUnt van de r8Cov.ry-dUur vaal' vl!iIl'lIchillende ".arden v., I ATe blj p=O.:3 .
0.00
1
-
index 1
diagram toont de krula-eorulatiscolffflciUnt tUBesn de rBcovery-duur an de reeds vlllr!oDItI"I
3vailable-tijd voor verBchil1ende wear-den van lATe bij poll.3 •
1.00
1.00
l.gS
o.gS
figuur 21 ( a)
f.lIO
figuur 21(b)
:I. ,0
1.85
0.85
1.80
0.80
1.75
0.75
1.70
0.70
1.65
0.65
1.60
0.60
1.55
0.55
1.50
0.50
1.45
0.45
1.40
0.40
1.35
0.35
i.JD
0.30
~
.25
0.25
E ..
.20
0.20
g
.15
~
0.15
E
0.10
it
0.05
~
.10
0
.05
60<;
.00
60
-
8
1
400
index 1
0.00
1
~.05
diagr_ toant de kruia-canalaUacolrrlcilnt tu..., de r.covery-dUUr lIf"I de rMda verlop., 8vailebl.-t1jd vaGI' vareah111.,. w..r~ v., IAn: bij poll.5 •
600 -iOO
~.10
inaex 1 d.1eor_ taont de auto-cornlat1ecol rriailnt
".. de recavery-clUur voor nreohill.. de
..,••rd8n ". . I ATe bij
poll.5 •
~.15 ~.20 ~.25 ~.30
~.35 ~.4O
1.00 0.g5
figuur 22( a)
figuur 22(b)
o.go 0.85 0.80 0.75 0.70 0.65 0.60 0.55 0.50
0.45 0.40 0.35 0.30
§
.E.
0.25 0.20
0
~ ..=
E
0.15 0.10
1r· 0
0
1
It
2
in_1
0.'
05
0.00
~.O5
d1egr.. t.oont de auto-cornlatiecoll"rlcilnt
van de recovery-duur voar "er9ch111llf"lde w..rdoIn von P bij IATC. 400.
~.10
d1agrBll toont dB auto-correlatiacolrrlclDnt \Ian d8 rtlcove~uur voaE' verschillsnde p b1j IATC.aOO.
w..rden van ~.1S
~.20 ~.25
~.30
1
-
index i
~.35
0<
6.5
61
6.0
figuur 23:(a)
5.5
figuur 23(b)
'S.~
5.0
5.0
4.5
4.5 4.0
.
3.5
0.
2.5
!c e .s .s
3.0
0
2.0
00
.
'" :I
1.5
...
1.0
0.5
-
Z4DO lATe
1.5
Z-
~t l:
1.0 0.5 0.0 -0.5
-.-
_1.0
-1.5
_1.5
002,0
002.0 -2.S -.3.0 -.3.5
-4,0
-4.0
dl..gr_ _ t de ".laU••••""ljk1ng _
die'). . . toont 11M lW1.aUe" et"w1jk1ng "'., de _ton •••Uabillty ton ....dchta • .,• ., de P be r vondtUlanclo
-4.5
~ _
Il1j ••d...... lAye.
-S.O
de
_ton ••a11ob1U ty ton ....dchta • ., de b
bij .eri
VDer venchiUenM 1IIaa1'dw1 v. . lATe
l'.
-S.5
figuur 24(b)
figuur 24(a)
520
520
1....
480
480
44lI
440
400
400
360
360
320
320
280
c
:
240
iu
e .s ...c
200
160 120 80 40
,0.1
20
ro
01
aJ
"35
o.
-
""" ":..E..
diag. . . tQont de relAtieve atv.1jking v." de ~.ten
280 240
0.
200
00
160
..
~
120
Z-
,.DD
040 80
6tJo
..'
qu........langta ten opzichta van d. benk", voar lter.chiU_"_ .....ardiM UTe Il1j ....i . . . .d. p.
It'"
iO
>
~r
40
-
~OOlATe
-40
-aD -120
.160
diegr_ toont de ruaUe"e .rw1jk1ng v.., de g_ten qIMu-leng'tli ten ~zichte \tan de berM.,. . YOO~ ".rachJ.~ ... rode" VWI P Ilij ••d ....de lATe.
62
4.2.2
Meetgegevens
betreffende queuelengte en availabity.
8estuderen we de meetgegevens met betrekking tot de availability. In tabel 4.4. is voor elk van de simulatie-punten gegeven: 1. de gemeten aVailability 2. de met het M~kov-model berekende availability 3. de absolute afwijking 4. de relatieve afwijking Met behulp van de tabel zijn beide diagrammen in figuur 4.23 (a) en (b) getekend. ~ In het diagram in figuur 4.23 (a) is de relatieve afwijking uitgezet tegen de intercheckpoint-tijd voor verschillende waarden vanp. ~ In het diagram in figuur 4.23 (b) is de relatieve afwijking uitgezet tegen p voorverschillende waarden van de intercheckpointtij d. De tabel toont aan dat de availability overal in het ergodiciteitsgebied goed door het Markov-model is voorspeld. 8estuderen we de meetgegevens met betrekking tot de queuelengte. In tabel 4.5 is voor elk van de simulatiepunten gegeven: 1. de gemeten queuelengte 2. de met het M£kov-model berekende queuelengte 3. de absolute afwijking 4. de relatieve afwijking Met behulp van de tabel zijn beide diagrammen in figuur 4.22 (a) en (b) getekend ~ In het diagram in figuur 4.24 (a) is de relatieve afwUking uitgezet tegen p voor verschillende waarden van de intercheckpoint-tijd. ~ In het diagram in figuur 4.24 (b) is de relatieve afwijking uitgezet tegen de intercheckpoint-tijd voor verschillende waarden vanp De gemeten queuelengte hangt af van de distributie van de recovery-duur. - In het hypogebied verwachten we een klein ere gemiddelde queuelengte. (relatieve afwijking < 1) - In het exponenticle-gebied verwachten we dat de gemeten gemiddelde queuelengte overeenkomt met de berekende. (relatieve afwijking ~ 1) - In het hyper-gebied verwachten we een grotere gemiddelde queuelengte. (relatieve afwijking > 1) De beide diagrammen tonen inderdaad het verwachte verloop.Naderen we de ergodiciteitsgrens dan zal vanwege toenemende instabiliteit de gemeten gemiddelde queue onbetrouw~r worden. (Random effecten zijn dan te verwachte~.
63
4.2.3
Conclusies - De veronderstelling dat de distributie van de reeovery-duur exponentieel is,blljkt maar ten dele waar.8innen hat ergodicitaits-gebied zljn een Hyper-, een Hypo-, en sen e~onentieel-gebied aan te wljzen. De gemiddelde recovery-duur komt redelljk ove~Een met het berekende gemiddelde. Afhankelljkheid tussen de recovery-duren zal toenemen indien iate toenesmt. Afhankelljkheid tussen de reeovery-duur en het bljbehorende interval altljd aanwezig is. De qU6uelengte afhankelUk is van de distributie van de recovery-duur. De availability goed met hat Markov-model voorspeld is. Derhalve: Indien we de availability in een CRR-systeem willen bepalen,dan voldoet het Markov-model voor elk punt binnen het ergodiciteit gebied. ~ Indien we de queuelengte in het CRR-systeem willen bepalen,dan voldoet het Markov-model aIleen voor punten binnen het exponentiale gebied. ~
TA8El
4.4
TA8El 4.5 ~tting meetresultatan: Queuelengte
Samenuatting meetresultaten: Auailability Ol-t
P
gemeten
berakend
aba.af...
rel.al\l.
ot.-t
200 200 200 200
0.10 0.20 0.30 0.35
0.56168 0.54668 0.53725 0.53042
0.56000 0.54857 0.53714 0.53143
0.00168 -0.00189 0.00009 -0.00101
0.30000 -0.34453 0.01676 -0.19005
200 200 200 200
400 400 400 400 400 400 400
0.10 0.20 0.30 0.35 0.40 0.45 0.50
0.69707 0.66690 0.63072 0.62557 0.60997 0.59639 0.58636
0.69818 0.66909 0.64000 0.62545 0.61091 0.59636 0.58182
-0.00111 -0.00219 -0.00120 0.00012 -0.00094 0.00003 0.00454
-0.15898 -0.32731 -0.20000 0.01919 -0.15387 0.00503 0.78031
600 600 600 600 600 600 600
0.10 0.20 0.30 0.35 0.40 0.45 0.50
0.75397 0.70429 0.65466 0.63143 0.60442 0.50506 0.55796
0.75200 0,70400 0.65600 0.63200 0.60800 0.56400 0.56000
0.00197 0.00029 -0.00132 -0.00057 -0.00356 0.00166 -0.00204
800 600 800 800 600 000
0.10 0.20 0.30 0.35 0.40 0.45
0.77520 0.70660 0.64231 0.60954 0.57604 0.54192
0.77474 0.70737 0.64000 0.60632 0.57263 0.53895
1200 1200 1200 1200 1200
0.10 0.20 0.30 0.35 0.40
0.70421 0.68040 0.58230 0.51067 0.40473
1600 1600 1600
0.10 0.20 0.30
2000 2000 2400 2400
gameten
berekend
aba.af...
rel.af...
0.10 0.20 0.30 0.35
7.95056 10.68417 15.84189 21.27365
7.97391 10.74520 16.47057 22.14196
-0.02335 -0.06103 -0.62868 -0.86831
-0.29283 -0.56797 -3.81699 -3.92156
400 400 400 400 400 400 400
0.10 0.20 0.30 0.35 0.40 0.45 0.50
4.90332 7.12279 11.96051 16.62341 26.40030 46.96862 81.87526
5.01846 7.15899 11.89412 16.37462 23.98809 38.87939 70.27273
-0.11514 -0.03620 0.06639 0.24879 2.41221 8.08923 3.60253
-2.29433 -0.50566 0.55017 1.51936 10.05587 20.80596 4.60254
0.26197 0.04119 -0.20122 -0.09019 -0.58682 0.31649 -0.36429
600 600 600 600 600 600 600
0.10 0.20 0.30 0.35 0.40 0.45 0.50
3.84742 6.96252 18.73761 42.12166 59.17608 93.03950 384.44625
3.95804 6.94159 14.47685 22.19092 36.28000 87.30567 177.93333
-0.11062 0.02093 4.26076 19.93074 22.89608 5.73387 206.51292
-2.79402 0.30152 29.43154 89.81484 6.56753 116.06197
0.00046 -0.00077 0.00231 0.00322 0.00621 0.00297
0.05937 -0.10665 0.36094 0.53107 1.06447 0.55107
800 800 800 800 800 800
0.10 3.62144 8.92782 0.20 0.30 29.64560 0.35 69.19485 0.40 . 157.61712 0.45 462.70728
3.59860 8.21354 21.21176 35.98658 66.97638 159.94774
0.02284 0.71428 6.43384 33.20827 90.64074 302.75954
0.63469 8.69637 39.76021 92.27959 135.33240 189.20654
0.78222 0.67556 0.56809 0.51556 0.46222
0.00199 0.00404 0.01349 -0.00489 0.02251
0.25440 0.71644 2.37128 -0.94848 4.86998
1200 1200 1200 1200 1200
0.10 0.20 0.30 0.35 0.40
3.91856 17.60946 91.34719 324.82871 693.70676
3.93898 14.33209 51.57080 111.67472 383.15238
-0.02042 3.35737 39.77639 213.15399 310.55430
-0.51841 23.42554 77.12967 190.87040 81.05245
0.77042 0.59815 0.40214
0.76600 0.62171 0.47543
0.00242 -0.02356 0.00671
0.31510 -3.78955 1.41135
1600 1600 1600
0.10 0.20 0.30
5.60089 115.53819 798.42691
5.22371 26.04502 134.85750
0.37718 89.49317 663.56941
7.22054 343.60953 492.05228
0.10 0.20
0.74480 0.56099
0.74419 0.55814
0.00061 0.00285
0.08197 0.51062
2000 2000
0.10 0.20
11.11557 173.68857
7.33179 46.21232
3.78378 127.47625
51.60786 275.84906
0.10 0.20
0.71029 0.49390
0.71529 0.40941
-0.00500 0.00457
-0.00699 0.93378
2400 2400
0.10 0.20
18.77991 354.71851
10.30348 81.07671
8.47643 273.64180
82.26764 337.50975
p
63.111~37
65
LITERATUURLIJST 1. V.F. Nicola Part 1: "A model with state-dependent parameters" EUT Report 82-E-128 ISBN 90-6144-128-5 ISSN 0167-9708 August 1982 2. V.F. Nicola Part 2: "A model with a specified number of completed transactions between checkpoints" EUT Report 82-E-129 ISBN 90-6144-129-3 ISSN 0167-9708 August 1982 3. Young, John W. "A First Order Approximation to the Optimem Checkpoint Interval" Communications of the ACM September 1974, Volume 17, Number 9, pages 530-531 4. K. Mani Chandy, James C. Browne, Charles W. Dissly & Werner R. Uhrig "Analytic Models for Rollback and Recovery Strategies in Data Base System" IEEE transactions on software Engeneering March 1975, Volume SE-l, No 1, pages 100-110 5. K. ~1. Chan d y "A Survey of Analytic Models of Rollback and Recovery Strategies" Computer May 1975, Volume 8, No 5, pages 40-47 6. E. Gelenbe en D. Derochette "Performance of Rollback Recovery Systems under Intermittent Faillures" Communications of the ACM June 1978, Volume 21, No 6, pages 493-499 7. Guy M. Lohman & John A. Muckstadt "Optimal Policy for Batch Operations: Backup, Checkpointing, Reorganization, and Updating" ACM transactions on Data Base Systems September 1977, Volume 2, No 3, pages 209-222 8. C.J. Kreijns "Inventarisatie van ae fouten bronnen en daaropvol,]ende herstelacties in eEn Database systeem" September 1981, Stage verslag, Technische Hogeschool Eindhoven
9. E. Gelenbe, "On the Optimum Checkpoint Interval" JACM, Vol. 26, 1979, p. 259-270.
66
Appendix A Bepaling van rangema en kma Het rangebied wordt gewoonlUk bepaald door: ran gema=;'r+4 6 Het aantal klassen wordt door de gebruiker opgegeven in kma. Hieronder zal de standaarddeviatie 6~worden berekend om rangema te bepalen:
p [(!1 =m] = (1:;) ( 1
~m = =
lS
$l.
(
,,":0 I)?i,
Ac. ) ( }..J
Ac..
1\.; of
)tn Ac.
o
t1.
-jA-:J..
(~)( At' \3 ~ rn.(rn-t)( Af \1n-2. '2.. Af ~':f +- .A c ) 1"=0 ),f rAe) /"'I/'" 2. (~)\ (.A f ) _ (.2£)::7.. At:.
6,." -=
It:: ).~ )M~1ftc.
). c.
V;u,0,+-1.)' ; jAr -= !fe
r.;;ngJema =::. )<1 +
~ (PI t)-'I.J. I) I
Omdat m slechts positieve gehele waarden inclusief sebreedte positief geheel zUn,dus:
0
kan aannemen moet de klas-
klassebreedte= 1; 2; 3; ••• In eerste instantie zal het programma controleren of da klassebreedte niet kleiner is dan 1.18 dit weI hat geval,dan wordt kma gemodificeerd (de door de gebruiker opgegeven waarde van kma wordt verlaten): kma:= integer (rangema + 2) Lage waarden voor kma zUn ta verwachten wanneer rangema te klein is waardoor er te weinig klassen zijn. i~et "klein rr wordt hier bedoeld een rangegebied bij Y,~ 1.. Derhalve wordt voor het geval)J,~1. rangema= 1+4'11. kma is dan integer(3-l"4 (Il). Vervolgens wordt de klassebreedte positief geheel gemaakt. We krUgen het onderstaande programmagedeelte:
RANGEMA:= n~EANMA+4xSQRT(TMEANx(~lEANMA+1)); RANGEMA/(KMA-2) 1 THEN BEGIN IF RANGOiA 1 -THEN RANGEMA:= 1+4xSQRT(2); KMA:= INTEGER(RANGEMA+2)
1L
END;
PSRANGEMA:= INTEGER(RANGEMA/(KMA-2))x(KMA-2); De klassebreedte wordt nu als voIgt bepaald: kla8sebreedte= psrangema/(kma-2)
67
Opmerking: Zolang rangema/(kma-2)~1 zal noch rangema noch kma aangepast worden. De procedure text 2 De procedure text 2 drukt per frequentieklasse achtereenvolgens de volgende gegevens af: - het klassenummer het intervalgebied,aangegeven door een onder- en bovengrens welke correspondeert met die frequentieklasse. het totaal aantal waarnemingen in die frequentieklasse het totaal aantal waarnemingen in die frequentieklasse uitgedrukt in percentage van het totaal.
%
J
ii [klasse..nummer "* 100 n het totaal aantal waarnemingen in die frequentieklasse plus die van lagere frequentieklassen uitgedrukt in percentage van het totaal (=eumulatieve perk centage)I~ __.._tnd
[!, a [A.]
J(-100%
.t,.1 ~
de som van het totaal aantal waarnemingen in hogere frequentieklasse uitgedrukt in percentage van het totaal (=eumulatieve rest)
100 ;, o~
~flUI'II"'U'"
_
i ~ i.i. [kJ fl.,,::: 1
Jf
iDa
%
het getal dat het veelvoud van het gemiddelde aangeeft Oefinieer: Ul = bovengrens Van het intervalgebied. mean. = T$lrv Afgedrukt wordt: ULI m~n.. - de afwUking van het gemiddelde Oefinieer: Sdel/=-j Afgedrukt wordt:
rf:1. (t.sq, - h ts2.)
(UL-mean.)
sdtw" De procedure grafics Voor een goede werking Van deze procedure moet in de wfl-statements filetype 9 worden gespecificeerd voor file output: FILE OUTPUT(KINO=iJRINTER, FILETYPE = 9);
Gevolg is weI dat het hele programma op filetype 9 georienteerd moet worden. Voor het afdrukken van de histogram gebruikt grafics 50 regels. Het aantal kolommen hangt af van het aantal klassen. Berekend wordt hoeveel kolommen een klasse maximaal kan omvatten opdat aIle klassen afgedrukt kunnen worden. Maximaal 120 klassen kunnen worden afgedrukt. Elke klasse omvat dan 1 kolom. (N.B. wfl= work flow language) Afdruk Van het programma plus voorbeeld Als voorbeeld is de tweede simulatierun genomen, dus: - nn= 5000 iatc= 10 - iatf= 10
68 BURROUGHS 87700 ALGOL COMPILER.
N S ,
R
B~~I
VERSIOM n.Z8 (THE"RC). 2.560.17 ••
R
N T
A I
E
I'IOlrrfO",1.
iZ/15/1lZ.
IlI.'S! P".
U R
UtIVIOOOO:~
N fILE INPUT.OUTPur; a.JOOJ
IS
SEGM~HT
OU')
DATA IS aOJ"
,1<""
NN,"'H'"
IN TEGER I, J. "'" L" MPcr" r SM "'. rSQ'tA RE AL TSPCF, TSOPCF. T~EAN~ A. TKE ANPCF, HUl P, ,'tCl" [CrT" [A, TC" I AIr. RANG (lU. P~OCEDURE ERRDRtERR~RNU.JERH INH~ER ERRDRHUHBER; BE~
KPC r" I HULP. eel ASS 8:
on3:oQO~
lUNG 'P cr;
THEN
WRITE(OUT~UT .. <·NO VALUE 3F~IN IF ERROftNUNBER22
;t
u"3:UOOll :1 C,I"I]:O"..A" :\ ~n]o: ""llll: 1 'D) '0000" onJ:..I'lJO :1 "" p"n'l ;:'1
IH IF ERRORNUfl8FR'1 ELSE
LONG
OAIA IS 'OH LON~ OO]:Qllon :l
E~COUNTEffED""'»
1):'1 ].I)OJ_.II.
aU]:~"'J7n
THEN "RITElOUTPUI.<"TOC HAHY CLASSES TO PRIH.",'.)
1)1'lJ.uI\0J:t 015 :0t)\)0;2'
ENO;
U')]'OOoD:J P~OCEOURE
GRAr]'CS(J~,K.y
I)O)lM~O"
... X);
()(']:onoO:J
300lEAN TAXI INIEGER (: REAL ARRAY Ill'); 3FG IH IHIEGER I. J. L. CLASB; ~~AFICS
RE AL
"u.~o
105,ono:) OQ J 'uO. 0 l) n":HfJ"
CLAssah12(' OJ'1 1(; IF < 1
O'J &:(J'IO": L 00&:001)1 a 0l)6:(}011 1:41,1)6:1)1"1" ]:n
cuna
THEH EPROR(2) ELSE BE~IN INIEGER ARRAY
IIHULPClaJi
a.. ~O"l
006'0'"~"
(S
SEGH(NT (\01)7 JH'01JZ'~
BiOOLEAN ARRAY YNCl:tOi
on7 :\),l0'5:3 uH:OOQ6 '1
!'UX:zOi FOR 1"1 SHP I UNTIL K DO IF IICII'.A' THn .H"IllIl) FOR 1:'1 SHP I UNTIL K 00
BEGIN
a.J7:0l)~6a
uIl1:0nIlF:Z
Q07:00H'$ u!)7:(Jnl7:5
(IHULPClllzINTEGERClt(I]I1'U,XIt')CI).
YNIII 'sF 'UE END; WR!TEl OUTPUT{ SP ACE I 2) I ); FOR I,sO STEP I UNTIL $0 DO BE~IN J~=~~-I;
~"7:0nl9z"
1)07:0019:'S
W~lT((aUTPUT.
OH:OOIE'Z U07:00\E'$ OH'OOIF'O
·~.J.~'X/50);
(J07~Oll291Z
IF YN(lI THEK WRITECOUTPUT.,<.(-"-»
ELSE
\107:0~2IU'j
,CLASSo)
lEGIN IF IIHULPIU"J IHEN 2~GIN YNCl!:.TRUE) ~RI IE (OUr PUT.<.( •• -» END ~LSC:
on7:00l0'5 ;»0110I)J2:}
.e LA SStt)
007'003"'5 0~7:0Ql7:$
007:00)9:2 007:0HFn
IU:ITE(OUTPUr,<e(- ·,».C...... SiB)
ENOl
007:00_3 :2 0"7:0043:2
IF YAX THEN WR(1E(OUJPUT,<-t-,.);
FOR L'sZ STEP 1 UNTIL K 00 IF INOT YNILll 'NO ITHULPtLl"J THEN BEGIN YNCL l: -TRUE; liRI TE (OUTPUT, < .( - •• )>> .. CL,lSSB ) END ELSE 3EGIN IF fNIL I JHI:If
UO'11l01l,12
00"0049'5 00710"51) 13
DOT '0051" 007:0056 :) 00r:005 . . Z 601:(,I05A:-;
WRnE(OUJPUJ.~.(·.·».CLASS3)
007:0053'5 oor :o'!5F'~ 00"0067'1 uu"uO&B'$ 0"'006E'$
EL S( NR ITE 10UTPUI. HI - "J •• CLAS SB) (NO;
A1RITE(OUTPUT,
~/~)
EN'
001:1)071'):2
END
END;
007.,~71'1
j.UODun)7') P~DCiOU'R£
TEXTUN"
INTEGER N; TS.TSQj BOOLEAN rBr; 3EG I'
T~ ..
TSQ. TEXT);
unJ:OJoOH 1'03:000D:3 0:11 H'. .lD 0;]
RrAiL
ROL
IF
~EA••
00)'0000.) 00)'00'0:3
son,
TEXT
THEN ,.RI T «DU fPUT
.<-
rEXTi.
IS S E ~"EN T "Oil B U~8:1)"';'0:1
EN TiUES-. '( 8, -"'E ...N-, '( 9. ·ST ...."40 AR!l-, '(6.
·SUM or-,I.-! ..,
000'0000'1 01) 3: JflJ2;5 ,J;)S:fJU02;5
T&.~L[·, x&,·liRGiJ"E~H·.X&.
-DEW I ... rIO .. • .. ),6 ,·ARGU:04ENTS-", /> l
j
ooa. 00U6:2
IF N»"'2
I"EN
onj:onQ6='t
BF~U
,,,,rliN:=TS/N; ~a£v: =SQR J( (TS~ -( TS. rS/~») I'~- LI); '" Rt Tt (l)U TP uJ . < ( ~. '( ";' F"" . 311:< 6. r 9. 3 .. XJ , r ~t
008:00117':4 ",ndtonB9 :1 1~
.3 , x3:)0 •
Und:on.j0:2 0"8:0 1\10:.\
.. M£&N.50l'f,TS)
on8;O!)1 .. a
(NO ELSE aEea (F'
(,HI(S:01l1~12 ~h::
T HEN
vO j:OO 18'$ 0"9:0"19:1
1 lIl~n[(
OUTPuT .. < (~.:t 5,FI.'). 3.
~&II"( .... ) .. :t
3.. r 12.3 .. 0>,
t>rttl:nnl C:-;
1-T5,9,T5)
on8.:Qn21 :J ')('j:I)"2";4
ELSE lIIRl TE( OUTPUT. <1-" .. '( 5,. ( ..... ),'( 6, .( - •• ) .X3.r 12: .hx3., u. 'I .. 'I. TS)
008:0020:5
END: "R ITE lOUT PUT , <"NON "EtGHTEO", ,. I E:NO
ooe:oo.HP~
003'0054 :z IS nOlO L~'G
j
PROC;: OURE TEXT2( ll.~, N. TS. TSO.R ANGEl , INTEGER K.Hl RFliL T5"TSQ.IUNGEj [NT(GFR AJfrfAY (I C·); BEelN l:ITEGER J) REAL SOEV, MEAN" LL, Ul, HUlF' 1, HULP2; IF' N> 'lI:l
IHEN
(S 01>1'l5 LDHG
GRAnCSCnJ6 ) IS n009 lONG uOl:OOuO:l 2
)E~IN
MR I TE