OMFOKM&TICA 11/11S78 
SilVi U LACS JA 
ST R EŽM n H SISTEMOV 
Z GPSS 
UDK: 681.3 : 518.682.6 VISOKA TEHNIŠKA ŠOLA, MARIBOIFI 
Članek obravnava reševanje najrazličnejših osnovnili liix>v strežnih sistemov s simulacijo z jezikom G1'SS. Podani so 
problemi pri vrednotenju rezultatov in priporočila za izboljšanje točnosU simulacije. 
QUEUE1NG SVSTEMS SIMULATION-WITH GPSS. This paper deals resolutlon of the most different fundainental types of 
queueing systems by the simulation with GPSS. The problems in validating simulation results and recomrnendations in 
improvement of simulation precision are considered. 
I,UVOD 
Problemi čakanja, ki jih uspešno rešujemo z metodami 
množične strežbe, pogosto obstojajo tudi v računalni­
ških sistemih, kjer se pojavljata neregularnost dolžine 
strežbe in neregularnost prihoda zahtev ali kjer mnogo 
zahtev uporablja eno ali več računalniškili strežnih na­
prav. Pomen strežnih sistemov in njihove analize je zla­
sti narasel s povečujočo uiX)rabo računalniških sistemov 
z delovanjem v realnem času (procesni računalniki, ra­
čunalniki s časovnim dodeljevanjem). Z metodami mno­
žične strežbe je možno oceniti zakasnitve pri obdelavi 
vseh vrst (programska ali elektronska oprema), velikost 
potrebnega pomnilnika, izkoriščenost ponmilnika in pro­
cesorja, dalje nam pomaga določiti najučinkovitejše 
strežno pravilo itd. 
Teorija množične strežbe je razvila eksaktne analitične 
metode, s katerimi pa je mogoče rešiti le nekatere ide­
alizirane strežne sisteme. Tako smo prisiljeni razvijati 
aproksimativno analizo iz kombinacij nekaj idealiziranih 
sistemov.Omenjene direktne analitične metode lahko 
nadomestijo drage simulacijske postopke, toda samo do 
neke meje, ko je potrebno zaradi večjega obsega in na­
tančnosti uporabiti simulacijo, ki jo izvedemo z računal­
niškimi jeziki za simulacijo diskretnih sistemov. 
Prednost simulacije pred analitičnimi metodami je v 
tem, da lahko obravnava nek zapleten detajl v logiki de­
lovanja sistema in izračuna učinek sprememb tega de­
tajla. Dalje lahko s simulacijo ocenimo medsebojni vpliv 
med več podsistemi. 
Simulacija tudi večinoma ni direktno orodje za sintezo. 
V splošnem je simulacija omejena na določitev, kako 
posebna konfiguracija reagira na posebno okolje. Se ved­
no iiEtane načrtovalcu funkcija analize rezultatov in odlo­
čitve, kje in kako izboljšati sistem, ali z drugimi bese­
dami, načrtovalec ostaja povratni element v načrtovalni 
zanki. 
11. SIMULACUSKI JEZIKI 
Simulacijske jezike (simulatorje) delimo v[lj : 
1. uporabnikove simulatorje, 
2. posebno namenske simulatorje in 
3. splošno namenske simulatorje. 
Kdorkoli hoče napisati svoj lastni simulacijski program 
(t.i. ufxjrabnikov simulator), mora imeti za to nasled­
nje razloge: 
- želene karakteristike modela niso niti primerne, niti 
možne v obstoječiti simulacijskih jezikih, 
- zahtevane so posebne vhodne in izhodne lastnosti ter 
- program se bo uporabljal dostikrat. 
Glavna prednost uporabnikovih simulatorjev je učinkovi­
tost. Cena za njihov razvoj mora biti poplačana v več­
kratni uporabi. Njihova slabost je nefleksibilnost. Pisa­
ni so seveda v višjih programskih jezikih. 
Posebno namenski simulator ima vgrajeno logiko poseb­
nega'strežnega sistema, tako da U[)orabniku ostane samo 
vstavljanje nekaterih parametrov. Število posebno na­
menskih simulatorjev je ogromno. Dobimo jih lahko pri 
prodajalcih računalnikov in konzultanskih organizacijah. 
Dokumentacija javnosti žal ni dostopna. Omenil bi samo 
tri jezike: 
1. GEH'1'S 111 QH je razširjega verzija GERT (Graphical 
Evaluation and Review Technique, [2] ). Razvili so ga 
za analizo sistemov s strežnimi napravami, ki zah­
tevajo večkratne izvore za izvršitev strežne aktivno­
sti. 
2. QAL (Oueuing Analysis Language, [3 j )- je visoko ni-
vojski jezik za poenostavitev reševanja tak« enostav­
nih kot kompleksnih modelov množične strežbe. Z 
njim zelo učinkovito simuliramo sodobne računalni­
ške sisteme, ki imajo vedno več paralelnosti v delo­
vanju. 
3. CSS (Computer System Simulator, [4] ) je manj 
splošen od Gl^SS. Uporablja precej tehnik iz GPSS, 
namenjen je za simulacijo računalniškega program­
skega sistema, predvsem oiaeracijskega sistema. 
Splošno namenski simulator je namenjen za simulacijo 
najrazličnejših strežnih sistemov. Najbolj razširjeni je­
ziki so GPSS, SIMSCRIPl' in SIMULA. 
Sam sem izbral GPSS, saj je bil to edini jezik, ki mi je 
bil dosto[X3n. Gi'SS (General I\ir[X3se Simulatipn System) 
so razvili pri IBM. Obstoja več verzij in je instaliran na 
večini računalniških sistemov. Ima naslednje pomembne 

73 
lastnosti: 
- je lahek za učenje, 
- zahteva velik hitri pomnilnik, 
- zaliteva daljši čas simulacije in 
- je primeren za simulacijo strežnih sistemov vseh 
vrst. 
lil.VREDNOTENJE REZULTATOV SIMULACIJE 
Vprašanje, ali je simulacijski rezultat pravilen, zahte­
va obravnavo dveh neodvisnih zalitev[l] : 
1. prva se nanaša na točnost modela 
2. druga pa na preciznost statičnih rezultatov. 
Ad. 1: Visoka stopnja natančnosti zahteva, da mnogo 
ix)enostavljenih ali izpuščenih detajlov bistveno 
ne vpliva iia sistemsko učinkovitost. S primer­
javo simulacijskih tekov z ali brez nekega de­
tajla lalilco izmerimo relativni efekt spremembe. 
Zmeraj spreminjamo samo en parameter ali 
spremenljivko, da lahko'ugotovimo njen vpliv. 
To je zlasti pomembno pri kompleksnih mode­
lih, saj se le tako Izognemo logičnim, t.i. si­
stematskim napakam. 
Ad. 2: Ta problem je posledica narave procesa v teh­
niki simulacije, ki temelji na odblrklh iz neke 
porazdelitve (statistiko). 1'roblem je določiti 
točko ali trenutek, ko je dosežena iskana pre­
ciznost. To dosežemo z nivojem zaupanja, kar 
pa je težko izvesti. 
Simulacijski rezultati navadno niso neodvisni, temveč 
imajo celo visoko korelacijo, kar ima za posledico tež­
ko določitev variance, ki je potrebna pri Izračunu In­
tervala zaupanjar 5] . V praksi opazujemo nekaj zapo­
rednih kumulativnih rezultatov in jih primerjamo med 
seboj. Če ti rezultati fluktulrajo v ozkem pasu, je pre­
ciznost dosežena, če opazimo njihov trend, povečamo 
število simulacijskih tokov. 
Potem je tu še nestaclonarnost porazdelitve odblrkov 
oziroma odvisnost od začetnih pogojev. Vpliv prehod­
nega pojava odpravimo na več načinov: 
a) Postavimo tipične začetne pogoje, kar pomeni, da 
moramo sistem že delno poznati, preden sploh za­
čnemo s simulacijo. 
b) Simuliramo daljši čas. 
c) Zl metodo paketne srednje vrednosti simuliramo 
krajši čas. 
N tekov razdelimo v p paketov dolžine n tekov 
(N=np). Učinek je enak učinku eksperimenta dolži­
no n tekov, ki ga ponovimo p-krat, tako da končno 
stanje enega teka postane začemo stanje naslednje­
ga simulacljskega teka. Prednost te metode je v 
tem, da ni potrebno odstraniti začetno periodo pri 
vsakem paketu in da zahteva majhen jramnllnlk, saj 
shranjuje samo vsoto paketnih srednjih vrednosti 
In vsoto njihovih kvadratov ter števila za tvorbo te­
koče paketne srednje vrednosti. 
d) Simuliramo nekaj tekov z netipičnimi začetnimi po­
goji, nato samo zbrišemo statistiko, ne da bi spre­
menili stanje sistema. Nato nadaljujemo s simula-
cljsklml teki ter Izračunamo novo statistiko. Toda 
žal ne eksistira preprosto pravilo, ki bi povedalo, 
koliko tekov moramo zbrisati. Metoda za določitev 
števila Izbrisanih tekov temelji na poznavanju fun­
kcije standardno devlaclje v odvisnosti od števila 
tekov pri simulaciji brez brisanja začetnih tekov. 
Pri GPSS je najlaže uporabiti zadnji način (stavek 
RESET za brisanje statistiko). 
Rezultat je nadalje odvisen od zaporedja naključnih 
števil [6] . Izkaže se, da je fluktuaclja še zmeraj 
opazna tiidi pri tisočem teku (cca 5 %) , no vseeno 
akumulirana povprečna vrednost leži k stacionarni 
povprečni vrednosti. Temu bi se izognili s p-kratno 
IKinovitvijo serije n simulacijskih tekov z različnimi 
zaporedji naključnih števil, kar pa s standardnimi 
progiramskimi instrukcijaml pri G1'SS ni mogoče. 
IV.SIMULACIJA Z JEZIKOM GPSS 
Narava In osnovni koncepti GPSS so taki, da omogočajo 
enostavno simulacijo vseh vrst streznili sistemov In 
mrež. GPSS Ima vgrajen program za izpis določenlli staf 
tlstlčnlh Izhodnih rezultatov (izkoriščenost strežnika, 
Intenzivnost prometa, povprečno in maksimalno število 
čakajočih enot v vrsti, delež enot, ki jim nI treba čaka­
ti v vrsti, povprečna dolžina strežLje, povprečna dolži­
na čakanja v vrsti Itd.). To so merila, ki nastopajo tudi 
pri analizi strežnih sistemov in jih laliko dobimo zato, 
ker G1'SS vsebuje generatorje psevdonaključnih števil. 
S pomočjo le teh In najrazličnejšili funkcijskih odvisno­
sti je možno predstaviti še tako zapleteno verjetnostno 
porazdelitev presledkov med zaporednima prihodoma 
enot in verjetnostno porazdelitev dolžine strežbe [7] . 
Moje izkušnje pri delu z Gl^SS 
Edini večji problem predstavljajo generatorji naključnih 
števil, saj nobeden od številnih učbenikov ne zajema 
kompleksno analizo njihovega delovanja. 
Zaporedje, ki ga generira eden Izmed 8 enakih genera -
torjev naključnih števil (RNl do RN8), spremenimo le s 
spremembo začetne vrednosti v algoritmu za generira-
nje naključnih števil (imenovano "seed"). 
1. Če imamo v nekem sistemu dva ali več naključnih 
procesov, tedaj ne smemo uporabiti različne genera-* 
torje z isto začetno vrednostjo, saj pride do neke 
vrste "resonance". Posledica tega je, da rezultati 
tudi pri mnogo simulacijskih tekov (cca 10.000) od­
stopajo od povprečnih vrednosti za cca 50 %. 
2. Sprememba enega ali več začetnih vrednosti naključ­
nih generatorjev spremeni rezultate pri cca 10,000 
simulacijskih tekov do 5 %, pri cca 20 simulacijskih 
tekov pa do 40 %. To pomeni, da je simulacija 2 ma­
lo teki nenatančna, 
3. Bloki z enakomerno porazdelitvijo (n.pr. ADVANCE 
80, 40; GENERATE 3,1 Itd.) uporabljajo vrednosti 
samo enega generatorja naključnih števtl, t.j. RNl. 
4. Če več naključnih procesov v strežnem sistemu ufx>-
rablja isti generator naključnih števil, ne moremo 
študirati vpliva prioritete, saj tedaj nastopi drugI 
vrstni red zaseganja števil Iz generatorja naključnih 
števil kot pri sistemu brez prioritet [7] . To pome­
ni , da se hkrati z vplivom prioritete vrine še drug 
vpliv, ki pokvari rezultate. Temu se izognemo tako, 
da vsakemu naključnemu procesu priredimo en ge­
nerator naključnih števil z različno začetno vredno­
stjo. Če imamo samo eno enakomerno porazdelitev, 
tedaj ji pustimo generator RNl, kar pa seveda nikjer 
v programu eksplicitno ne zapišemo (za druge na-

ključne procese tedaj ne smemo uporabiti HNl). 
5. 1'rlmerjava analitično Izračunanih vrednosti ter re­
zultatov simulacije pri ra/.ličnih številili tekov je 
pokazala, da jo |X)trebno simulirati 10.000 tekov oz, 
enot, ki cjredo skozi strežni sistem. Večina primer­
jav je dala odstopanje manjše od 5 %, edino v nekaj 
primerih sem dobil 8 t 12 % odstopanja od analitič­
no dobljene vrednosti. Primerjavo sem izvršil tudi 
z različnimi sokvencami naključnih števil (različne 
začetno vrednosti ijeneratorjev) in vsa odstopanja 
so bila v fjornjlh mejah. 
6. Primerjal sem tudi vrednosti, dobljene pri različno 
dolcjili ellminiranih začetnih iX)riodali (odprava pre­
hodnega |X)java) in nisem opazil hitrejše konvergen­
ce k analitičnim [X)vprečnim vrednostim. 
Mojo priporočilo jo sledečo: 
Upoštevati je treba podana priporočila v zvezi z upora­
bo generatorjev naključnih števil. Simulirati moramo 
tako, da bo šlo skozi strežni sistem cca 10.000 enot 
enega tipa, ne da bi upoštevali prehodni pojav. Rezul­
tat simulacijo bo z veliko verjetnostjo odstopal od ana­
litično dobljene vrednosti največ za 5 %. 
V. SIMULACIJA KAZLIČNIH 'lllOV 
STUEŽNlll SISTEMOV / GPSS 
GPSS je primeren za simulacijo strežnih sistemov vseh 
vrst. Z njim lahko enostavno simuliramo najbolj sploš­
no naključno porazdelitev. Izvor zahtev in (»razdelitev 
vhodnega toka omogoči blok (JENEUATE, porazdelitev 
dolžine strežbe blok AUVANCE. Enega strežnika pred­
stavimo z blokoma SEIZE in RELEASE, več paralelnih 
strežnikov pa z blokoma ENTER hi LEAVE. Vso statisti­
ko čakajočo vrste dobimo s pomočjo blokov QUEUE in 
DE1'ART, medtem ko se statistika strežnih naprav izvr-' 
šl avtomatsko. 
Pri simulaciji neliomogenih strežnih sistemov uporabi­
mo več enakih segmentov modela s samo različnimi 
bloklGENERATE. 
Pri cikličnih strežnih sistemih koristimo blok 
TRANSI'ER. 
Ne da bi bilo potrebno posebej specificirati, GPSS si­
mulira strežni sistem z neskončno kapaciteto in pravi­
lom ElEO. 
Sisteme z omejeno kapaciteto simuliramo s (»močjo 
blokov ENTER, AUVANCE 0 (s časovno zakasnitvijo 0) 
in LEAVE (poslednji blok LEAVE moramo i)Ostavitl za 
blok, ki označuje vstop enote v proces strežbe). 
Strežne sisteme s poljubnim neprioritetnim strežnim 
pravilom (n.pr. LIEO, RSS) simuliramo s pomočjo blo­
kov LINK in UNLINK. 
Pri sistemili z neprektnjevalnim prioritetnim strežnim 
pravilom je potrebno samo prirediti ustrezni prioritetr 
ni indeks določenemu tipu enot (uporabimo samo opo­
ra ud E v bloku GENERATE). 
Za simulacijo sistemov s preklnjevalnim prioritetnim 
strežnim pravilom z nadaljevanjem uporabimo |X)leg 
op.irand.) E v"l)lokili GENERATE 5o 1'UEEMl'r In RETURN 
namestc SI:UZE in RELEASE v segmentih modela s pre-
klnjevalnimi enotami. 
Pri simulaciji sistemov z drugimi prioritetnimi pravili 
moramo uiMrabiti še logične, testne in selektivne o[)ura-
C i je. 
Sisteme z grupno strežbo simuliramo s pomočjo opsran-
da H v blokili SEIZE in RELEASE oziroma ENTER in LEAVE. 
IM simulaciji strežnih sistemov z grupnim vhodnim to­
kom uiX)rabimo blok SPLIT. 
Simulacija mreže streznili sistemov je preprosta In ne 
zahteva kakih posebnili navodil, saj je glavna značilnost 
GPSS, da je bločni diagram nekega sistema ekvivalenten 
tako diagramu ixiteka kot glavnemu programu. 
VI. PRIMER SIMULACIJE Z GPSS 
V center za obdelavo sjX)ročil prihajata dva tipa (razre­
da) six)ročil s [Missonsko porazdelitvijo (^^=0,5 s"^, 
^2=0,1 s~^). Prvi tip zahteva krajšo in konstantno dol­
žino obdelave (bj [=0,2 s), drugi tip pa daljšo dolžino 
olxlelave z eksponentno porazdelitvijo. Primerjal som 
delovanje sistema: 
1. brez prioritet 
2. če uvedemo neprekinjevalno prioriteto sporočilu ti-
l>a 1 in J 
3. če uvedemo prekinjevalno prioriteto s[)oročilu tipa 1. 
Problem sem rešil analitično in s pomočjo simulacije. 
Naš primer predstavlja strežni sistem, ki ga označimo 
z razširjeno Kendallovo oznako Mj, M2/Bi, M2/l/<i>, 
co/oo, ooAIl^O (PRI). 
Za vse tri variante sem izračunal analitično povprečno 
dolžino zadrževanja za posamezen tip sporočila (Wt, 
W2) in za oba tipa skupaj (W). Analitično žal ni mogoče 
določiti povprečnih dolžin čakanj za posamezen lip s|X3-
ročila pri sistemu brez prioritet. 
Da se izognemo vplivu zaradi različnega zaseganja po 
. zaporedju naključnili števil, potem ko uvedemo priori­
teto (glej poglavje IV), priredimo vsaki porazdelitvi sa* 
mostojni generator naključnih števil, ki pa ne sme star-^ 
tati z isto začetno vrednostjo. 
Rezultati simulacije so podani v oklepaju zraven ustrez-
nlli analitičnih rešitev (tabela 1) in ustrezajo cca 
10.000 sporočilom 1. razreda in cca 2.000 sporočilom 
2. razreda, potem ko v statistiki nisem upošteval pre­
hodni pojav s 500 sporočili 1. razreda In 100 sfioročili 
2. razreda. 
Hitro opazimo, da s prioritetnimi strežnimi pravili pri 
enaki izkoriščenosti procesorja dosežemo krajše pov­
prečne dolžine zadrževanja in dolžine čakanja za oba 
razreda skupaj (W in Wci). IVekinjevalno strežno pravi­
lo je v toni primeru več kot 3-krat učinkovitejše od na­
vadnega pravila FIEO. 
w 
^1 
"^2 
brez 
prioritet 
7,25 (7,03) 
(6,20) 
(11,18) 
neprek. 
str. prav. 
4,5 (4,30) 
3,0 (2,78) 
12,0(11,91) 
prek. 
str. prav. 
2,26 (2,25) 
0,211 (0,212) 
12,55 (12,45) 
J 
Tabela 1 

75 
Študiral sem še relativna odstopanja od analitične vred­
nosti povprečnih dolžin zadrževanj v odvisnosti od šte­
vila simulacijskih tekov (prispelih sporočil v proces 
streženja) pri upoštevanju in neupoštevanju prehodnega 
pojava"(slika l). 
»M tinml r •/1 
o 
-4 
-8 
M 
-20 
2500 6000 1SO0 10.000 
sporolilai 
z upoštevanjem prehodnega pojava 
brez upoštevanja prehodnega pojava 
mulirati še tako kompleksen-strežni sistem ali mrežo 
strežnih sis(' v.iov. Njegovo moč veča tudi možnost kli­
canja subrutin v jeziku FORTRAN, Problematična je hi­
trost simulacije, ki bi jo lahko izboljšali z metodo paket­
ne srednje vrednosti z različnimi neodvisnimi zapored­
ji naključnih števil. 
Preseneča tudi relativno veliko odstopanje od analitično 
dobljenili vrednosti, za kar upravičeno sumim generator­
je naključnih števil, ki ne uporabljajo ravno najboljšega 
algoritma za generacijo naključnih števil. 
LITERATURA 
1. P.H. Seariian: " On teleprocessing system design. 
Part VI: The role of digital simulation", IBM Systems 
Journal, Vol. 5, No. 3, 1966 
2. M.J. Maggard and others: "GERTS III QR: A multiple 
resource constrained hetvvork simulation model", 
Management Datamatics, Vol. 5, No. 1, 1976. 
Slika 1 
VII. POVZETEK 
Današnja razvojna stopnja teorije množične strežbe ne 
dopušča detajlne analize kompletnega sistema, ampak 
le analizo podsistemov. Pri slednjih je teorija razvila 
vrsto kriterijev, ki jih lahko koristno U|X)rabljamo pri 
aproksimativni analizi in tudi pri simulaciji komplek­
snejših sistemov množične strežbe. 
Bilo bi napak, če bi trdil, da je najprimernejši jezik 
GPSS, saj je bil to edini jezik, ki mi je bil dostopen. 
Res pa je v ZiM to najbolj razširjen jezik za simulaci­
jo diskretnih sistemov. Z njim je mogoče z lahkoto si-
3. D.V. Poster and others: "A lanquage for analysis of 
queuing models", Modeling 8r Simulation, Vol. 5, 
Pittsburgh (USA), 24. • 26. april 1974. 
4. P.H. Seaman, R.C. Soney: "Simulating operating 
systems" IBM Systems Journal, Vol. 8, No.4, 1969. 
5. G. Gordon: "System Simulation", Prentice-Hall, 
Inc., New Jersey, 1969. 
6. N. Guid: "Uporaba metod množične strežbe pri ana­
lizi in načrtovanju računalniških in telekomunikacij­
skih mrež in sistemov", magistrsko delo. Fakulteta 
za elektrotehniko, Ljubljana, 1977. 
7. T.J. Schriber: "Simulation using GPSS'^ John Wiley 
& Sons, New York, 1974. 
R;; wire wrapping center (^R 
MOMlUNIIIUEmDlin 
DE«GN[D,MMIUFAaUREO 
ANDMARKETEDWOnDWIDE 
n 
oituamiinioKoiPouniii 
MOTHEiuiiNinpioiaia 
KSIGNED.MANUFAaURED 
AND MARKETED W0R1DWIDE 
n 
niUCKINEITOOKnraUIKHI 
UtOim UNtOUE PRODUn 
DESIGNED.MANUrAaURED 
AND MARKETED WORU)WIDE 
n 
OKMACHINE&TOOlCOltPOlUTlOfl 
lUKmiEt uHiouE noDiin 
DE5IGNED,MANUFAaURED 
AND MARKETED WORUWIDE 
n 
OIMACHIKElTOOLCORPOMnON 
5 
iKOTHES UHIOUE EltOnja 
DESIGNED.MANUFAaURED 
AND MARKETED WORLDWIDE 
IT 
O« lucHi« t Toa (nroumm 
OK MACHINE & TOOL CORPORATION