Clieni CPU

Tehnici de simulare pe computer: Tiv de introducere!1 2 2 3 7 3 b 4 9 6 5 9 6 MCL = Tarr Da Este CPU coad gol? Nu MCL = MCL + 1 O nou sosire evenimentul are loc O plecare evenimentul are loc b Este MCL = Tarr ? Da O nou sosire evenimentul are loc b b

Harry Perros

Tehnici de simulare pe computer: Introducerea definitiv!de

Harry Perros

Catedra de Calculatoare NC State University Raleigh, NC Toate drepturile rezervate 2009

Ctre cititori ...Aceasta carte este disponibil gratuit pentru download de pe site-ul meu: http://www.csc.ncsu.edu/faculty/perros//simulation.pdf Self-studiu: Putei utiliza aceast carte pentru a nva tehnicile de baz de simulare de unul singur! La sfritul capitolului 1, vei gsi trei exemple. Selectai una dintre ele i nu cesiune de calculator corespunztoare dat la finalul capitolului. Apoi, dup ce ai citit fiecare nou capitol, nu toate problemele de la sfritul capitol i, de asemenea, nu cesiune de calculator care corespunde la problema ta, pn la data cnd ajungei la sfritul anului carte, va s-au dezvoltat un model de simulare foarte sofisticat! Putei folosi orice limbaj de programare de nivel nalt v place. Erori: Eu nu sunt responsabil pentru eventualele erori n carte, i dac nu au gsit, mi-ar aprecia dac ai putea s-mi spunei (hp@csc.ncsu.edu). Confirmarea: V rugm s confirmai aceast carte, dac l utilizai ntr-un curs, sau ntr-o proiect, sau ntr-o publicaie. Drepturi de autor: V rugm s reinei c este ilegal s reproduc pri ale acestei cri sau a tuturor Rezervai in alte publicatii, fara acordul meu. A dori s mulumesc Attila Yavuz i Amar Shroff pentru ca ma ajuti la capitolele 2 i revizuiasc 4 i, de asemenea, mi datorit multor studeni pentru alte sugestiile lor. Bucurai-v! Harry Perros, Decembrie 2009

CUPRINSCapitolul 1. Introducere, 1 1.1 sau o anumit abordare, 1 1.2 Construirea unui model de simulare, 2 1.3 Metodologia de simulare de baz: Exemple, 5 1.3.1The main interferene model, 5 1.3.2A token-acces pe baz sistem, 11 1.3.3A n dou etape de fabricare a sistemului, 18 Probleme, 22 Computer sarcini, 23 Generarea de numere pseudo-aleatoare, 25 2.1 Introducere, 25 2.2 numere pseudo-aleatoare, 26 2.3 Metoda congruential, 28 Metode 2.3.1General congruencies, 30 2.3.2Composite generatoare, 31 2.4 generatoare Tausworthe, 31 2.5 generatoare lag Fibonacci, 32 2.6 Twister Mercenne, 33 2.7 Testele statistice pentru generatoarele de numrul pseudo-aleatoare, 36 2.7.1Hypothesis de testare, 37 2.7.2Frequency de testare (Monobit de testare), 38 2.7.3Serial de testare, 40 2.7.4Autocorrelation de testare, 42 2.7.5Runs de testare, 43 2.7.6Chi-ptrat de ncercare pentru buntatea de cuviin, 45 Probleme, 45 Computer sarcini, 46 Generaie de variates stocastice, 47 3.1 Introducere, 47 3.2 Metoda de transformare invers, 47 3.3 Prelevarea de probe de la de distribuie a probabilitii timp continuu, 49 3.3.1Sampling dintr-o distribuie uniform, 49 3.3.2Sampling dintr-o distribuie exponenial, 50 Capitolul 2. Capitolul 3.

ii Tehnici de simulare pe computer 3.3.3Sampling dintr-o distribuie Erlang, 51 3.3.4Sampling dintr-o distribuie normal, 53 3.4 Prelevarea de probe de la o distribuie de probabilitate discret-timp, 55 3.4.1Sampling dintr-o distribuie geometric, 56 3.4.2Sampling dintr-o distribuie binomial, 57 3.4.3Sampling dintr-o distribuie Poisson, 58 3.5 Prelevarea de probe de la o distribuie a probabilitii empirice, 59 3.5.1Sampling dintr-o distribuie de probabilitate discret-timp, 59 3.5.2Sampling dintr-o distribuie de probabilitate continu n timp, 61 3.6 Metoda Respingerea, 63 3.7 metode Monte-Carlo, 65 Probleme, 66 Computer sarcini, 68 Soluii, 69 Capitolul 4. Simulare modele, 71 4.1 Introducere, 71 4.2 Event-Advance Design, 71 4.3 Viitorul eveniment list, 73 4.4 matrice secvenial, 74 4.5 liste de legat, 75 4.5.1Implementation a unei liste eveniment viitor ca o list legat, 76 a. Crearea i tergerea noduri, 76 b. Funcia pentru a crea un nou nod, 78 c. Eliminarea unui nod, 79 d. Crearea de liste legate, Introducerea i scoaterea noduri, 79 e. Introducerea unui nod ntr-o list legat, 80 f. Eliminarea unui nod din list legat, 83 Complexitatea 4.5.2Time de liste legate, 86 Liste 4.5.3Doubly legate, 87 Unitatea de 4.6-timp n avans de proiectare, 87 4.6.1Selecting o unitatea de timp, 90 4.6.2Implementation, 91 4.6.3Event-avans fa de unitatea de timp n avans, 91 4.7 Activitatea de proiectare bazate pe simulare, 92 Exemple de 4.8, 94 4.8.1An inventar de sistem, 94 4.8.2Round-robin coad, 97 Probleme, 101 Computer sarcini, 102 Anexa A: de punere n aplicare o coad ca prioritate o movil, 104 A.1A heap, 104 A.1.1 de punere n aplicare o grmad utiliznd o matrice, 105 a. Meninerea proprietatea heap, 106 A.2A coad prioritate folosind un heap, 109 Complexitatea A.3Time de cozi de prioritate, 112

Cuprins A.4 Capitolul 5. De punere n aplicare o list eveniment viitor ca o coad de prioritate, 113 iii Tehnici de estimare pentru analiza datelor endogen create, 115 5.1 Introducere, 115 5.2 Colectarea de date create endogen, 115 5.3 stare tranzitorie in Raport cu starea de echilibru, de simulare, 118 5.3.1Transient-simulare de stat, 118 5.3.2Steady-simulare de stat, 119 5.4 Tehnicile de estimare pentru starea de echilibru, de simulare, 120 5.4.1Estimation a intervalului de ncredere a mediei de variabil aleatoare, 120 a. Estimarea coeficienilor autocorelare, 123 b. Lot mijloace, 128 c. Replicari, 129 d. Regenerativ metod, 131 5.4.2Estimation de alte statistici ale unei variabile aleatoare, 138 a. Probabilitatea ca o variabil aleatoare se afl ntr-o fix interval, 138 b. Percentila de o distribuie de probabilitate, 140 c. Variana distribuiei de probabilitate, 141 5.5 Tehnicile de estimare pentru simulare de stat tranzitorie, 142 5.6 experimente-pilot i proceduri secveniale pentru realizarea unui precizie necesar, 143 Replicari 5.6.1Independent, 144 5.6.2Batch mijloace, 144 Computer sarcini, 145 Validarea unui model de simulare, 149 Computer sarcini, 150 De reducere a Variance tehnici, 155 7.1 Introducere, 155 7.2 antitetic variates tehnica, 156 7.3 Controlul variates tehnica, 162 Computer sarcini, 165 Simulare de proiecte, 166 8.1 O reea avans de rezervare de sistem - sistem de blocare, 166 8.2 O reea avans de rezervare de sistem - sistemul ntrziat, 173 Capitolul 6. Capitolul 7. Capitolul 8.

CAPITOLUL 1: INTRODUCERE

1.1 Sau abordare Sau o abordare fa de rezolvarea problemelor se caracterizeaz prin urmtorii pai: 1. Problem formularea 2. Construirea modelului 3. Validare a modelelor 4. Folosind modelul, s evalueze diverse alternative disponibile (soluie) 5. Punerea n aplicare i de ntreinere a soluiei Paii de mai sus nu se efectueaz o singur dat. Mai degrab, n cursul unei SAU exerciiu, un frecvent merge napoi la paii de mai devreme. De exemplu, n timpul validare a modelului o frecvent trebuie s examineze ipotezele de baz efectuate n paii 1 i 2. Caracteristica de baz a abordarea sau este acela de a cldire model. Operaiuni Cercetatorii place s se numeasc constructori model! Un model este o reprezentare a structura unui sistem real de via. n general, modelele pot fi clasificate dup cum urmeaz: iconic, analogice, i simbolice. Un model iconic este o replic exact a proprietilor sistemului de viaa real, dar n scar mai mic. Exemple sunt: avioane model, harti, etc Un model analogic foloseste un set de proprieti pentru a reprezenta proprietile unui sistem real de via. De exemplu, o hidraulic Sistemul poate fi utilizat ca un analog de trafic electrice i sistemelor economice. Simbolic modelele reprezint proprietile sistemului de viaa real prin intermediul mijloacelor de simboluri,

2 Tehnici de simulare pe computer cum ar fi ecuaii matematice i programe de calculator. Evident, modele de simulare sunt modele simbolice. Operaiuni de modele de cercetare sunt, n general, modelele simbolice si acestea pot fi clasificate n dou grupe, i anume modelelor deterministe i modele stocastice. Modelele deterministe sunt modele care nu conin elementul de probabilitate. Exemple sunt: programarea liniar, non-liniar de programare i de programare dinamica. Modele stochastice sunt modele care conin elementul de probabilitate. Exemple sunt: Teoria ateptare, procese stocastice, fiabilitate, i tehnici de simulare. Tehnici de simulare se bazeaz foarte mult pe elementul de dezordine. Cu toate acestea, tehnici deterministe de simulare, n care exist o ntmplare nu, nu sunt mai puin frecvente. Tehnici de simulare sunt uor de nvat i se aplic la o gam larg de probleme. Simularea este, probabil, handiest tehnica de a utiliza printre matrice sau modele. Argumentul spune ca, "atunci cnd orice altceva esueaza, atunci simula". Asta este, atunci cnd alte modele nu sunt aplicabile, apoi utilizai tehnici de simulare. 1.2 Construirea unui model de simulare Orice sistem real-via studiate prin tehnici de simulare (sau pentru aceast problem de ctre orice alte SAU model) este privit ca un sistem. Un sistem, n general, este o colecie de entiti care sunt corelate logic i care sunt de interes pentru o anumit aplicaie. Au caracteristici ale unui sistem sunt de interes: 1. Mediu: Fiecare sistem poate fi vzut ca un subsistem al unui sistem mai larg. 2. Interdependen: Nr activitate are loc n izolare total. 3. Sub-sisteme: Fiecare sistem poate fi defalcate la sub-sisteme. 4. Organizaie: Practic, toate sistemele sunt formate din elemente foarte bine organizate sau componente, care interactioneaza cu scopul de a ndeplini funcia de sistem. 5. Schimbarea: Starea actual sau de stat a sistemului, de obicei, variaz pe o perioad lung perioad de timp.

Introducere 3 Cnd construirea unui model de simulare a unui sistem de viata reala care face obiectul anchetei, unul dintre nu simula ntregul sistem. Mai degrab, o simuleaz acele sisteme care sunt subreferitoare la problemele la ndemn. Acest lucru implic pri modelarea sistemului de la diferite nivele de detalii. Acest lucru poate fi reprezentat grafic using piramida barba lui de conducere ca se arat n figura 1.1. Colectie de domenii de cerneluri forma acele pri ale sistemului care sunt ncorporate n model.Figura 1.1: piramida de conducere barba lui

Un model de simulare este, n general, folosite n scopul de a studia viaa real sistemele care nu exist n prezent. n special, unul este interesat de cuantificarea executarea unui sistem n temeiul studiu pentru diferite valori ale parametrilor de intrare sale. Astfel de msuri cuantificate de performan poate fi foarte util n procesul de decizie managerial. Paii de baz implicate n efectuarea unui exerciiu de simulare sunt prezentate n Figura 1.2. Toate variabilele relevante ale unui sistem n temeiul studiu sunt organizate n dou grupuri. Cele care sunt considerate ca fiind dat i care nu trebuie s fie manipulate (necontrolate variabil) i cele care urmeaz s fie manipulate astfel nct s ajung la o soluie (Variabile controlabile). Distincia ntre controlabile i necontrolabile variabile n principal, depinde de domeniul de aplicare al studiului.

4 Tehnici de simulare pe computerDefinirea problemei o Simulare de proiectare Experimente Analizeaza date (Alternative) Formularea Sub-Modele Pornete Simulator Combin de Sub-Modele S analizeze rezultatele Colectarea datelor Punerea n aplicare rezultate Scrie Simulare Program Debug Model de Validare Anterioare Pai o Figura 1.2: Paii de baz implicate n efectuarea unui studiu de simulare.

O alt caracterizare a variabilelor relevant este dac acestea sunt afectate sau nu n timpul unei rula simulare. O variabil a cror valoare nu este afectat este numit exogene. A variabil, avnd o valoare determinat de alte variabile n cursul procesului de simulare se numete endogen. De exemplu, atunci cnd simuleaz o coad singur server, cu urmtorul text variabile pot fi identificate i caracterizate n consecin. Variabile exogene 1. Intervalul de timp dintre dou sosiri succesive. 2. Timpul de serviciu ale unui client. 3. Numrul de servere.

Introducere 4. Prioritatea disciplina. Variabilele endogene 1. Medie timpul de ateptare n coad. 2. Numrul mediu de clieni n coada de ateptare. 5 Variabilele de mai sus pot fi controlabile sau necontrolabile, n funcie de experimente am dori s le desfoare. De exemplu, dac dorim s gsii cele mai de impact a numrul de servere pe timpul mediu de ateptare n coada de ateptare, apoi numrul de servere devine o variabil controlabil. Variabilele-restul de intervalul de timp dintre dou sosirile i timpul de serviciu, vor rmne fixe. (Variabile incontrolabile) Unele dintre variabilele de sistem care sunt de o importan capital sunt cele utilizat pentru a defini starea sistemului. Variabile, cum ar sunt cunoscute ca Starea variabile. Aceste variabile forma coloana vertebral a oricrui model de simulare. n orice caz, n timpul unei rula simulare, ar trebui s fie n msur s stabileasc modul n care stau lucrurile n sistem utiliznd aceste variabile. Evident, de selecie a acestor variabile este afectat de ce fel de informaii privind sistemul vrea s le menin. Vom ncepe acum de a identifica metodologia de simulare de baz, prin intermediul mijloacelor de cteva exemple de simulare. 1.3 1.3.1 Metodologia de simulare de baz: Exemple Aparatul interferene problema S ne considerm o list de ateptare singur server, cu o populatie finit cunoscut sub numele de main ingerin problem. Aceast problem a aprut iniial dintr-o nevoie de a modela comportamentul de maini. Ulterior, acesta a fost utilizat pe scar larg n modelarea pe calculator. S ne considerm M Maini. Fiecare main este operaional pentru o perioad de timp i apoi se stric. Noi presupunem c exist un depanator. O main rmne defalcate n funcie pn cnd este fixat de meterul. Maini defalcate sunt servite ntr-un mod FIFO, iar serviciul este

6 Tehnici de simulare pe computer non-preemptive. Evident, timpul total de stabilire a unei maini este alctuit din momentul n care a are la "coad" pentru reparator i timpul necesar pentru reparator pentru a remedia problema. A masina devine operaional imediat dup ce acesta a fost fixat. Astfel, fiecare main urmeaz un ciclu de baz, aa cum se arat n figura 1.3, care se repet continuu.Figura 1.3: Ciclul de baz a unei maini.

n general, unul are informaii cu privire la durata de funcionare i timpul de reparaie de o main. Cu toate acestea, n scopul de a determina timpul n jos de o main, ar trebui s fie capabil s calculeze timpul de ateptare pentru depanator. Dac aceast cantitate este cunoscut, atunci o poate calcula de utilizare a unei maini. Alte cantiti de interes ar putea fi utilizarea de meterul. Depanator Finit Populaie de MasiniFigura 1.4: interferene problema main.

S ne uitm acum la coada meterul lui. Acest lucru poate fi vizualizat ca un singur server coada alimentat de o populaie finite ale clienilor, aa cum se arat n figura 1.4 Pentru simplitate, vom presupune c durata de funcionare a fiecrei maini este egal la 10 de uniti de timp. De asemenea, timpul de reparaie a fiecrei maini este egal cu 5 unitati de timp. n Cu alte cuvinte, vom presupune c toate mainile au identice ori constant operaionale.

Introducere 7 Ei au, de asemenea, ori identice i constant reparatii. (Acest lucru poate fi uor modificat pentru a mai mult cazurile complicate n cazul n care fiecare aparat are propriile sale ori aleatoare operaionale i reparaii.) Primul pas si cel mai important n construirea unui model de simulare de mai sus sistem, este de a identifica de baz evenimente a cror apariie va modifica Starea de sistem. Acest lucru aduce la problema de a trebui s defineasc statutul variabilele de mai sus problem. Selecia a variabilelor de stare depinde n principal de tipul de performan msurile pe care le dorii pentru a obine despre sistemul n studiu.O main descompune Depanator ocupat ? da Alturai-v coad Depanator devine ocupat Reparaie ncepe Figura 1.5: Un eveniment sosire.

n aceast problem, variabila statutul de cel mai important este n, numrul de spart Maini de jos, adic, cei care ateapt n coada de ateptare, plus una fiind reparate. Dac n = 0, atunci tim c coada este gol i reparator este inactiv. Dac n = 1, atunci coada este goale i reparator este ocupat. Dac n> 1, atunci reparator este ocupat i exist n-1 defalcate maini n coada de ateptare. Acum, exist dou evenimente a cror apariie va n cauza de a schimba. Acestea sunt: 1. O main se defecteaz, de exemplu, un sosirea are loc la coada.

8 Tehnici de simulare pe computer 2. O main este fix, de exemplu, plecarea are loc din coad. Diagramele-date n figurile 1.5, 1.6 i arat ce se ntmpl atunci cnd fiecare dintre aceste evenimente au loc.O main este reparat Alte Maini de care urmeaz s fie reparat? nu Depanator devine inactiv O nou reparaie ncepeFigura 1.6: Un eveniment de plecare.

n scopul de a ncorpora mai sus, dou evenimente de baz ale modelului de simulare, am nevoie de un set de variabile, cunoscut sub numele de ceasuri, care va ine evidena momente de la care un eveniment de plecare sau de sosire va avea loc. n special, pentru acest model specific, am trebuie s se asocieze un ceas pentru fiecare masina. Ceasul va arata pur si simplu instantanee de timp la care aparatul va rupe n jos, i. e., se va ajunge la coad meterul lui. Evident, la orice instan, numai ceasurile a mainilor operaionale sunt de interes. n plus fa de aceste ceasuri, am nevoie pentru a avea un alt ceas care prezinta instantanee momentul n care o main n curs de reparat va deveni operaional, i anume, aceasta va provoca o eveniment de plecare s apar. Astfel, n total, dac avem maini de m, avem nevoie de 1 m, ceasuri. Fiecare dintre aceste ceasuri este asociat cu apariia unui eveniment. n special ceasuri, m sunt asociate cu evenimente sosire m i un ceas este asociat cu evenimentul de plecare.

Introducere 9 n plus fa de aceste ceasuri, este util de a menine un maestru ceas, care pur i simplu ine evidena timpului simulat. Inima centre modelului de simulare n jurul valorii de manipulare a acestor evenimente. n special, folosind ceasurile de mai sus, modelul decide care dintre toate posibile evenimente vor avea loc urmtoarea. Apoi ceasul maestru este avansat la acest moment de timp, i Modelul ia msuri astfel cum este indicat n diagramele-date n figurile 1.5 i 1.6. Acest eveniment Abordarea manipulare este reprezentat n figura 1.7 . oO main Descompune Alege urmtorul eveniment O main este reparat Coad gol?

n oCrea funcionarea timp

oCoad gol? Generai un noul serviciu

voi s voi s o oGenerai un noul serviciu

n o oFigura 1.7: manipulare Eveniment.

Acum suntem gata s efectueze simularea mna de mai jos n tabelul 1. S ne presupunem c avem 3 masini. S CL1, CL2, CL3 i s fie asociate cu ceasurile masina de 1, 2, 3 i respectiv (ceasuri eveniment sosire). S CL4 fi ceasul asociate

10 Tehnici de simulare pe computer cu evenimentul de plecare. n cele din urm, s fie MC ceasul maestru, apoi permitei-R indic dac reparator este ocupat sau inactiv. Presupunem c la zero moment toate cele trei masini sunt operaional i c CL1 = 1, CL2 = 4, CL3 = 9. (Acestea sunt cunoscute sub numele de condiiile iniiale.)MC0 1 4 6

CL11 16 4 4 9 9 9 9

CL2

CL3

CL46 6 11

n

0 1 2 1 inactiv ocupat ocupat ocupat

9 1116

16 16-

2121

-

26

11 1621

2 11

ocupat ocupat

ocupat Tabelul 1: simulare de mn pentru problema interferene main

Am act de faptul c, n scopul de a programa o ora sosirii nou ne pur i simplu trebuie s stabileasc asociate ceas pentru MC 10. n mod similar, de fiecare dat cnd un serviciu de reparaii nou ncepe ne-am stabilit CL4 = MC 5. Un aspect foarte important al acestui model de simulare este c vom verifica doar sistemului la momente n care un eveniment are loc. Observm n mn de mai sus simulare c ceasul maestru n exemplul de mai sus ne ofer momente n care sa ntmplat ceva (de exemplu, un eveniment a avut loc). Aceste perioade sunt: 0, 1, 4, 6, 9, 11, 16, ... Noi act de faptul c n aceste momente-ntre nici un caz nu se produce i, prin urmare, starea sistemului rmne neschimbat. Avnd n vedere acest lucru, este suficient s se verifice sistemul de la momente la

care apare un eveniment. n plus, avnd grij de un eveniment, am pur i simplu n avans ceasul Master pentru urmatorul eveniment care are cel mai mic ceas de timp. De exemplu, n de mai sus simulare de alt parte, dup ce am avut grij de o plecare de timp 11, simulare va avansa la ora 16. Acest lucru se datoreaz faptului c n urma instantanee timp 11, exist trei evenimentele care sunt programate s aib loc n viitor. Acestea sunt: o sosire) de 1 la main timp 16; b) sosirea mainii de 2 la moment 21; i c) o main de plecare de 3 la ora 16. Evident, urmtorul eveniment s se ntmple este acest ultim caz, la momentul 16.

Introducere 11 Simularea de mai sus poate fi foarte usor de facut folosind un program de calculator. O schi de fluxul-chart a programului de simulare este prezentat n figura 1.8. Efectiv punerea n aplicare a acestui model de simulare este lsat ca un exerciiu.Iniia simulare MC = 0, CL1 = 1, CL2 = 4 CL3 = 9, n = 0, R = 0 (inactiv) A Sosire (Main i-lea) MC = CLI Urmtor eveniment Plecare (Main i-lea) MC = CL4 n = 0? da R=1 Nu n = n-1 n = n +1 Da n = 0? Nu R=0 A CL4 = MC 5 CL4 = MC 5 A CLI = MC 10 A

Figura 1.8: O diagrama de program de simulare.

1.3.2 Un cod de acces bazat pe sistemul Considerm o reea de calculatoare constnd dintr-un numr de noduri interconectate prin intermediul unui comun cu fir sau fr fir mediu de transport, aa cum se arat n figura 1.9. Acces la comun mediu este controlat de un jeton. Asta este, un nod nu poate transmite n reea cu excepia cazului n are token-ul. n acest exemplu, vom simula o versiune simplificat a unui astfel de acces sistem, astfel cum este descris mai jos.

12 Tehnici de simulare pe computerFigura 1.9: Noduri interconectate printr-un mediu comun

Exist un singur semn care viziteaz nodurile ntr-o anumit succesiune logic. Nodurile sunt logic conectate, astfel nct s formeze un inel logic. n cazul n care un autobuz sau pe baz de inelbazate pe mediu prin cablu, ordinea n care nodurile sunt legate n mod logic nu poate fi aceeai cu ordinea n care acestea sunt ataate la reea. Vom presupune c simbol nu se pierde. Un nod nu poate transmite cu excepia cazului n care le-a token-ul. Atunci cnd un nod primete ordine de idei, de la sale anterioare nod n amonte logic, ea le poate pstra pentru o perioad de timp de pn la T. In acest timp, nodul transmite pachete. Un pachet se presupune s fie alctuit de date i un antet. Antetul este format din adresa expeditorului, adresa de destinaie, precum i diverse domenii de activitate de control. Nodul renun la tokenul atunci cnd: un timp) T sa epuizat, sau b), le-a transmis toate pachetele din coada acestuia nainte de expirarea T, sau c) primete tokenul ntr-un moment cnd nu are pachetele n coad sarcina de a transmite. Dac momentul T ruleaza afar i nodul se afl n procesul de transmitere a unui pachet, se va finaliza de transport i apoi se va preda token-ul. Predarea nseamn token, c nod va transmite urmtorul su vecin logic n aval. Conceptual, aceast reea poate fi vzut ca incluznd un numr de cozi, o pe nod. Numai coada care are token-ul poate transmite pachete. Token-ul poate fi vzut ca un server, care comut ciclic ntre cozile de ateptare, aa cum se arat n figura 1.10. Dat token-ul este trecut la o coad, pachete de ateptare n aceast coad pot fi transmise pe de reea. Timpul maxim pe care-o coad poate pstra token-ul este unitile de timp T, i token este predat n conformitate cu normele descrise mai sus. Timpul necesar pentru jeton pentru a comuta de la o coad la alta este cunoscut sub numele de comuta-a lungul timpului. Astfel de coad sisteme sunt denumite n continuare sisteme de votare, iar acestea au fost studiate n literatura de specialitate sub o varietate de ipoteze.

Introducere 13 jeton

Figura 1.10. Conceptual coad de sistem.

Este mult mai simplu s utilizeze modelul de ateptare dat n figura 1.10 atunci cnd construirea modelului de simulare a acestui sistem de acces. Urmtoarele evenimente trebuie s fie luate n considerare n aceast simulare. Pentru fiecare coad, exist un eveniment sosire i servicii finalizarea evenimentului. Pentru token-ul, exist un timp de sosire la eveniment coada urmtoare i momentul n care simbolul trebuie s fie predat la nodul urmtor, cunoscut sub numele de time-out. Pentru fiecare coada, am ine evidena timpului de sosire a pachetului urmtor, numrul de clienilor n coada de ateptare, iar timpul de un pachet este programat s plece, n cazul n care este n curs de transmise. Pentru token, urmarim de ora de sosire la coada urmtoare, numrul de coad care pot deine token-ul, i time-out. n alt simulare de mai jos vom presupune c reeaua token-bazate pe const din trei noduri. Aceasta este, sistemul de ateptare n figura 1.10 const din trei cozi. Ori inter-sosire la cozile de 1, 2, si 3 sunt constante i acestea sunt egale cu 10, 15, i 20 de ori unitate, respectiv. T se presupune a fi egal cu unitatea de ori 15. n momentul n care ia de a transmite un pachet se presupune a fi constant egal cu unitatea de ori 6. Comutatorul de peste timpul este egal cu unitatea de timp 1. Pentru condiiile iniiale, vom presupune c sistemul este gol zero, timp, i prima sosire la cozile de 1, 2, si 3 va avea loc la ora 2, 4 i 6 respectiv. De asemenea, la ora zero, token-ul este n ateptare 1. n cazul n care o sosire i o de plecare s apar simultan la aceeai coad, vom presupune c are loc de sosire primul. n plus, n cazul n care token-ul i un pachet ajunge la o coad, n acelai timp, vom presupune c pachetul ajunge primul. Urmtoarele variabile reprezinta ceasurile utilizate n fluxul-diagrame:

...

14 Tehnici de simulare pe computer a. MC: Masterat ceas b. ATeu: Ceas de timp Sosire la coad i, i = 1,2,3 c. DTeu: Ceas de timp de plecare de la coad i, i = 1,2,3 d. TOUT: Pauza ceas pentru jeton e. ANH: ceas de timp Sosirea simbolic la coad urmtoare Logica pentru fiecare dintre evenimentele n aceast simulare este rezumat n cifre la 1.11 1.14. Concret, n figura 1.11 ne arat ce se ntmpl atunci cnd un loc de sosire, figura 1.12 se ocup de cazul n care un serviciu este finalizat la coad i, Figura 1.13 descrie aciunile ntreprinse atunci cnd un time-out are loc, i figura 1.14 rezum msurile luate atunci cnd token-ul ajunge la o list de ateptare. Setul de toate posibilele evenimente care pot aprea la un moment dat ntr-o simulare este cunoscut ca figura 1.13 lista evenimentelor. Acest eveniment-list trebuie s fie cutat de fiecare dat, n vederea pentru a localiza urmtorul eveniment. Aceast manipulare eveniment constituie baza de simulare, i-l este rezumat n figura 1.15.Sosire apare MC = ATi Alturai-v coad qi = qi + 1 Program Urmtorul Sosire Sosiri ntoarcere ATi = MC + noi inter-la ora sosirii

Figura 1.11: eveniment Sosire la coad i.

Introducere 15Serviciul este terminat MC = DT i Plecare de la coad q = q-1 Coad gol? nu Jeton time-out ? nu Program nou serviciu da Trece jeton Program de sosire timp H = (H +1) mod3 ANH = MC + comutator-a lungul timpului da ntoarcere DTi = MC + noul serviciu timp ntoarcere Time-out apare Acest lucru nseamn c nod este nc de emisie. Ridic o pavilion ntoarcere

Figura 1.12: finalizarea service la coad i.

Figura 1.13: Time-out of simbolic

16 Tehnici de simulare pe computerFigura 1.14: Sosirea simbolic la coad urmtoare.Initialize simulare Localiza urmtorul eveniment i. e. lista evenimentelor de cutare pentru cel mai mic numr Lua adecvat aciune n cazul n care evenimentele noi sunt programate urmtoarea actualizare eveniment i. e. ramur la partea corespunztoare a Programul (sau procedur) nu Este simulare peste ? da Capt

Figura 1.15: manipulare Eveniment.

Introducere Simularea de mn este dat n tabelul 2. 17MC Queue1Queue2Queue3 ArrDepart QueueArrDepart QueueArrDepart coad Ceas ClocksizeClock ClocksizeClock Dimensiune ceas 2 2 12 12 12 12 12 12 22 22 22 22 32 32 32 32 32 42 42 42 42 52 52 52 30 30 36 36 36 42 42 42 9 9 9 0 0 1 1 1 1 0 0 1 1 1 1 2 2 2 2 1 2 2 1 1 2 1 1 4 4 4 4 19 19 19 19 19

19 19 34 34 34 34 34 34 34 49 49 49 49 49 49 49 16 16 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 2 2 2 2 2 2 6 6 6 6 6 26 26 26 26 26 26 26 26 26 26 46 46 46 46 46 46 46 46 46 23 23 23 0 0 0 0 0 1 1

1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 Jeton Timp de nod NoOut Ceas 1 2 3 1 1 1 1 2 2 2 3 3 3 3 1 1 1 1 1 1 1 1 1 2 58 39 39 39 39 39 39 * * 32 32 32 25 25 18 18 18 Sosire Urmtor Nod 1 2 3 0 1 2 3 4 6 9 10

12 16 17 19 22 23 24 26 30 32 34 36 39 42 42 43 10 17 24 43 Tabelul 2: simulare de mn pentru sistemul de acces pe baza de token-

18 1.3.3 Un dou etape de fabricare a sistemului Tehnici de simulare pe computer S considerm un sistem cu dou etape de fabricare a cum este el descris de ctre reeaua de ateptare prezentate n figura 1.16. Etapa 1 const ntr-o coad capacitate infinit, denumite n continuare coad 1, deservite de un singur server, mentionat ca serverul 1. Etapa 2, const ntr-o capacitate finit coad, denumite n continuare coada de 2, deservite de un singur server, mentionat ca server 2.Etapa 1 Etapa 2

Coad 1 Server 1 Coad 2 Server 2Figura 1.16: O reea n dou etape de ateptare.

Atunci cnd coada de 2 devine complet, Server 1 se oprete. Mai precis, la serviciu finalizarea la serverul 1, serverul se blocheaz dac coada de 2 este plin. Aceasta este, serverul nu poate servi orice ali clieni care ar putea fi de ateptare n coada de ateptare 1. Server 1 va rmne blocate pn cnd un client se ndeprteaz de la coad 2. n acest caz, un spaiu va deveni disponibil n coad 2 i client servit n faa server 1 vor putea s se mute n coad 2, elibernd astfel server pentru a servi alt client n ateptare 1. Fiecare server poate rupe, de asemenea, n jos. Pentru simplitate, vom presupune c un server se pot rupe n jos, dac acesta este ocupat sau inactiv. Un server de stabilire a rupt nu poate furniza servicii pn cnd este reparat. Dac un client a fost n serviciu atunci cnd a avut loc defalcarea, clientul va relua serviciul su dup ce serverul este reparat, fr nici o pierdere la serviciu le-a primit pn la momentul de defalcare. Aceasta este, dup serverul devine operaional din nou, clientul va primi soldul serviciilor sale. Urmtoarele evenimente (i ceasuri asociate) pot s apar: 1. Sosirea unui client la coad 1 (ceas AT) 2. Finalizarea service la serverul 1 (ceas DT1) 3. Finalizarea service la serverul 2 (DT2 ceas) 4. Server 1 descompune (ceas BR1)

Introducere 5. Server 1 devine operaional (ceas OP1) 6. Server 2 pauze de jos (ceas BR2) 7. Server 2 devine operaional (ceas OP2) 19 Mai jos, vom descrie pe scurt evenimentele care pot fi declanate atunci cnd fiecare dintre Evenimentele de mai sus apare. 1. Sosire la coad 1. a. Sosire la coad 1 (valoare nou pentru AT ceas): Acest eveniment este ntotdeauna programat de fiecare dat cnd apare o sosire. b. Finalizarea service la serverul 1 (valoare nou pentru DT1 ceas): Acest eveniment va fi declanat n cazul n care constat sosirea noului server inactiv. 2. Finalizarea service la serverul 1: a. Finalizarea service la serverul 1 (valoare nou pentru DT1 ceas): Acest eveniment va ntmpla dac nu exist unul sau mai muli clieni n coada de ateptare 1. b. Finalizarea service la serverul 2 (DT2 valoare nou pentru ceas): Acest eveniment va s apar n cazul n care clientul care a completat doar serviciul su de la serverul 1 gaseste server 2 inactiv. Apariia unui eveniment finalizare serviciu de la server 1 poate provoca serverul de la 1 la sa blocat, n cazul n care coada 2 este plin. 3. Finalizarea service la server 2: a. Finalizarea service la serverul 2 (valoare nou pentru D21 ceas): Acest eveniment va ntmpla dac nu exist unul sau mai muli clieni n coada de ateptare 2. b. Finalizarea service la serverul 1 (valoare nou pentru DT1 ceas): Acest eveniment va s apar dac serverul 1 a fost blocat. 4. Server 1 concediu jos: a. Server 1 devine operaional (valoare nou pentru OP1 ceas): Acest eveniment ofer timp n viitor, cnd serverul va fi reparat i va deveni operaionale. n cazul n care serverul a fost ocupat atunci cnd este rupt n jos, s actualizeze ceasul serviciului finalizarea evenimentului la server 1, pentru a reflecta ntrziere ca urmare a reparaii.

20 Tehnici de simulare pe computer 5. Server 1 devine operaional: a. Server 1 descompune (valoare nou pentru BR1 ceas): Acest eveniment ofer timp n viitor, cnd serverul se va rupe n jos. n acest timp, server este operaional. b. Finalizare timp de serviciu (valoare nou pentru DT1): n cazul n care serverul a fost inactiv atunci cnd sa rupt n jos, i coada 1 nu este gol n momentul n care devine operaional, apoi un nou serviciu va ncepe. 6. Server 2 pauze de jos: a. Server 2 devine operaional (valoare nou pentru OP2 ceas): Acest eveniment ofer timp n viitor, cnd serverul 2 va fi reparat, si, prin urmare, se va devin operaional. In acest timp serverul este defalcat. Dac serverul 2 a fost ocupat atunci cnd este rupt n jos, s actualizeze ceasul al serviciului eveniment la finalizarea server 2, pentru a reflecta ntrziere ca urmare a repara. 7. Server 2 devine operaional: a. Server 2 pauze de jos (valoare nou pentru BR2 ceas): Acest eveniment ofer timp n viitor, cnd 2 serverul se va rupe n jos. n acest timp, server este operaional. b. Finalizare timp de serviciu (valoare nou pentru DT2): n cazul n care serverul a fost inactiv atunci cnd sa rupt n jos, i 2 coad nu este gol n momentul n care devine operaional, apoi un nou serviciu va ncepe. n mna-simulare prezentate n tabelul 3, se presupune c capacitatea de tampon de coada este de 4 secunde (aceasta include client n funciune). Toate orele de serviciu, interorele de sosire, operaionale i de reparaii ori sunt constante cu urmtoarele valori: interora de sosire = 40, timp de serviciu de la nodul 1 = 20, timp de serviciu la nodul 2 = 30, operaionale timp pentru serverul de 1 = 200, durata de funcionare pentru server 2 = 300, timpul de reparaie pentru serverul de 1 = 50, i timpul de reparaie pentru server 2 = 150. Iniial sistemul se presupune a fi gol. Primul sosirea are loc la ora 10, serverul 1 va rupe n jos pentru prima dat la timp 80, i server 2 la ora 90.

IntroducereEtapa 1MC 10 30 50 60 70 80 90 90 130 130 150 170 170 190 210 230 240 250 250 270 280 290 310 310 330 330 340 370 370 380 AT 50 50 90 90 90 90 90 130 170 170 170 210 210 210 250 250 250 290 290 290 290 330 330 330 370 370 370 410 410 410 # Cust 1 0 1 1 0 0 0 1 2 2 1

2 1 0 1 1 1 2 1 1 0 1 1 0 1 1 1 2 2 2 350 400 400 400 400 400 580 310 310 270 230 150 150 150 170 170 190 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 330 380 380 380 380 70 70 DT1 30 BR1 80 80 80 80 80 130 130 130 130 OP1 Server Stare ocupat inactiv ocupat

ocupat inactiv jos jos jos jos ocupat ocupat ocupat ocupat inactiv ocupat blocat blocat blocat ocupat blocat inactiv ocupat ocupat inactiv ocupat jos jos jos jos ocupat 1 1 0 1 1 1 1 1 1 2 2 3 4 4 4 4 4 4 4 4 4 3 4 4 4 3 3 2 2 100 100 250 250 250 250 250 250 250 250 250 250 250 250 280 280 310 310 340 340

340 340 370 370 400 400 540 540 540 540 540 540 540 540 540 540 540 540 540 540 60 60 # Cust DT2

21

Etapa 2BR2 90 90 90 90 90 90 240 240 240 240 240 240 240 240 240 240 OP2 Server Stare inactiv ocupat ocupat inactiv ocupat ocupat jos jos jos jos jos jos jos jos jos jos ocupat ocupat ocupat ocupat ocupat ocupat ocupat ocupat ocupat ocupat ocupat ocupat ocupat ocupat

Tabelul 3: simulare de mn pentru sistemul de fabricaie n dou etape

22 Tehnici de simulare pe computer ntruct avem de a face cu numere ntregi, este posibil ca mai mult de un ceas poate avea aceeai valoare. Asta este, mai mult de un eveniment poate s apar n acelai timp. n aceast simulare special, evenimente simultane pot fi luate de ngrijire n orice ordine arbitrar. n general, cu toate acestea, ordinea cu care astfel de evenimente sunt tratate cu materia poate, i le-a care urmeaz s fie luate n considerare n simulare. ntr-o simulare, de obicei, ceasurile sunt reprezentate de numere reale. Prin urmare, nu este posibil de a avea evenimente care au loc n acelai timp. Probleme 1. Nu simulare mna a problemei interferen main, discutat n seciunea 1.3.1, pentru urmtoarele cazuri: a. Varia n funcie ori de reparaii i operaionale. b. Varia n funcie de numrul de reparatorii. c. S presupunem c mainile nu sunt reparate ntr-un mod FIFO, dar n conformitate cu care masina are cel mai scurt timp de reparaii. 2. Nu simulare mna a schemei de acces pe baz de jeton, descrise n seciunea 1.3.2, pentru urmtoarele cazuri: a. Varia n funcie ori inter-sosire. b. Varia n funcie de numrul de cozi. c. Presupunem c pachetele au prioritate 1 sau 2 (1 fiind cea mai mare). Pachetele ntr-o coada de ateptare sunt servite n funcie de prioritatea lor. Pachete cu aceeai prioritate sunt servit ntr-un mod FIFO. 3. Nu simulare mna a sistemului de fabricaie n dou etape, descrise n seciunea 1.3.3, pentru urmtoarele cazuri: a. Nu isi asuma nici defalcri. b. S presupunem c un sistem cu trei etape de fabricaie. (A treia etap este similar cu cel a doua etap.)

Introducere Computer misiuni 23 1. Scrieti un program de calculator pentru a simula problema interferena main aa cum este descris la punctul 1.3.1. De fiecare dat cnd apare un eveniment, imprim o linie de ieire pentru a afia valorile curente ale ceasurilor i a altor parametri de stare (ca n mn simulare). Rulai simulare pn cnd ceasul maestru este egal cu 20. Verificai cu mna dac avansuri de simulare de la eveniment la eveniment n mod corespunztor, i dac-l actualizri ceasuri i ali parametri de stare corect. 2. Scrieti un program de calculator pentru a simula sistemul de token-acces bazat pe aa cum este descris n pct. 1.3.2. De fiecare dat cnd apare un eveniment, imprim o linie de ieire pentru a afia curent Valorile de ceasuri i a altor parametri de stare (ca i n simulare mn). Rulai simulare pn cnd ceasul maestru este egal cu 100. Verificai cu mna, dac avansuri de simulare de la eveniment la eveniment n mod corespunztor, i dac-l actualizeaz ceasuri i ali parametri de stare corect. 3. Scrieti un program de calculator pentru a simula sistemul bazat pe dou etape de fabricaie, descris la punctul 1.3.3. De fiecare dat cnd apare un eveniment, imprim o linie de ieire pentru a arat valorile curente ale ceasurilor i a altor parametri de stare (ca n mn de simulare). Rulai simulare pn cnd ceasul maestru este egal cu 500. Verificare de mn, dac avansuri de simulare de la eveniment la eveniment n mod corespunztor, i dac aceasta actualizeaz ceasurile i ali parametri de stare corect.

CAPITOLUL 2: Generarea de pseudo-aleatoare NUMERE

2.1 Introducere Vom lua n considerare metode de generare de numere aleatoare uniform distribuite. Bazat cu privire la aceste metode, vom proceda apoi, n capitolul urmtor s ia n considerare metode de generatoare de numere aleatoare, care au o anumit distribuie, i anume, exponenial, normal, etc Numere alese la ntmplare sunt utile ntr-o varietate de aplicaii. De exemplu, n analiza numerica, numere aleatoare sunt utilizate n soluia de integrale complicate. n programare pentru calculatoare, numere aleatoare de a face o buna sursa de date pentru testarea eficienei algoritmi de calculator. Numere aleatoare de joac, de asemenea, un rol important n criptografie. n simulare, numere aleatoare sunt folosite pentru a introduce dezordinii n model. De exemplu, s ne gndim pentru un moment de simulare interferene main Modelul discutat n capitolul precedent. n acest model sa presupus c durata de funcionare de o main a fost constant. De asemenea, sa presupus c timpul de reparaie a unui masina a fost constant. Este posibil ca s-ar putea identifica situaii din viaa real n cazul n care aceste dou ipoteze sunt valabile. Cu toate acestea, n cele mai multe cazuri se va observa c momentul n care o masina este operaional variaz. De asemenea, timpul de reparaie poate varia de la main la main. Dac suntem capabili s observe ori de funcionare a unei maini pe o rezonabil de lung perioad, vom constata c acestea sunt de obicei caracterizate printr-o teoretic sau un empirice probabilitate de distribuie. n mod similar, timpii de reparaie poate fi, de asemenea, caracterizat printr-o teoretice sau empirice de distribuie. Prin urmare, n scopul de a face modelul de simulare mai realist, ar trebui s fie n msur s numere n mod aleatoriu care urmeze un anumit teoretic sau empirice de distribuie.

26 Tehnici de simulare pe computer n scopul de a genera astfel de numere aleatorii unul trebuie s fie n msur s genereze uniform distribuite numere aleatoare, altfel cunoscut sub numele de pseudo-aleatoare de numere. Aceste numere pseudo-aleatoare pot fi utilizate fie de ctre ei nii sau pot fi folosite pentru a genera numere aleatoare de la diferite distribuii teoretice sau empirice, cunoscut sub numele de variates aleatoare sau variates stocastice. n acest capitol, ne vom concentra pe discutia noastra generarea i testarea statistic de numere pseudo-aleatoare. Generaie de stocastice variates este descris n capitolul 3. 2.2 Pseudo-aleatoare numere n esen, nu exist nici un astfel de lucru ca o singur de numere aleatoare. Mai degrab, vorbim de un secven de numere aleatoare care urmeaz o distribuie specificat teoretice sau empirice. Exist dou abordri principale pentru generarea de numere aleatoare. n prima abordare, o fenomen fizic este folosit ca o surs de dezordine, de unde numere aleatoare pot fi generate. Numere aleatoare generate n acest fel se numesc adevrat aleatoare numere. Un generator de numere aleatoare adevrat nevoie de un complet imprevizibil i nonreproductibile surs de dezordine. Aceste surse pot fi gsite n natur, sau acestea pot fi creat de la hardware i software. De exemplu, timpul scurs ntre emisiile de particulelor n timpul dezintegrarii radioactive este o surs de bine-cunoscute randomizate. De asemenea, termice zgomot de la o dioda semiconductoare sau rezisten poate fi folosit ca o surs de randomizat. n cele din urm, prelevare de probe procese de interactiune om computer, cum ar fi tastatura sau mouse-ul de activitate un utilizator, poate da natere la o surs de randomizat. Numere aleatoare adevrat sunt ideale pentru aplicaii critice, cum ar fi din cauza criptografie lor natura aleatorie imprevizibile i realiste. Cu toate acestea, ele nu sunt utile n simulare pe calculator, n cazul n care dup cum se va vedea mai jos, trebuie s fim capabili de a reproduce o avnd n vedere secven de numere aleatoare. n plus, n ciuda atractive lor mai multe proprieti, producerea i stocarea de numere aleatoare adevrat este foarte costisitoare. O abordare alternativ la generarea de numere aleatoare, care este cel mai popular abordare, este de a utiliza un algoritm matematic. Algoritmi eficienti au fost dezvoltate care pot fi uor puse n aplicare ntr-un program de calculator pentru a genera un ir de aleator

Generarea numere pseudo-aleatoare 27 numere. Aceste algoritmi produce un numr ntr-un mod determinist. Aceasta este, avnd n vedere o valoarea de pornire, cunoscut sub numele de de semine, aceeai secven de numere aleatoare poate fi produse de fiecare dat, att timp ct seminelor rmne aceeai. n ciuda modului deterministe n care numerele aleatorii sunt create, aceste numere par a fi aleatorie, deoarece acestea treci o serie de teste statistice proiectate pentru a testa diferite proprieti de numere aleatoare. Avnd n vedere acest lucru, aceste numere aleatoare sunt denumite n continuare pseudo-aleatoare de numere. Un avantaj de generatoare de numere pseudo aleatoare ntr-o manier determinist este c acestea sunt reproductibile, deoarece aceeai secven de numere aleatoare este produs fiecare timp, vom rula un generator de pseudo-aleatoare avnd n vedere c noi folosim semine de aceeai. Acest lucru este util cand se depaneaza un program de simulare, dup cum am de obicei, doresc s reproduc aceeai succesiune de evenimente, n scopul de a verifica acurateea simulare. Pseudo-aleatoare numere i, n general, numere aleatorii sunt de obicei generate la cerere. Aceasta este, de fiecare dat un numr aleator este necesar, generator de adecvat este numit pe care le returneaz apoi un numr aleator. n consecin, nu este nevoie de a genera un set mare de numere aleatoare n avans i a le stoca ntr-o matrice pentru o utilizare viitoare ca i n cazul numerelor adevrat aleatoare. Am act de faptul c termenul de numere pseudo-aleatoare este de obicei rezervat pentru aleatorie numerele care sunt uniform distribuite n spaiu [0,1]. Toate celelalte numere aleatoare, inclusiv cele care sunt uniform distribuite n cadrul oricrui alt spaiu dect [0,1], sunt denumite n continuare variates aleatoare sau variates stocastice. Pentru simplificare, ne vom referi la pseudo-aleatoare numere ca numere aleatoare. n general, o metod acceptabil pentru generarea de numere aleatoare trebuie s produc secvene de numere sau de bii, care sunt: a. uniform distribuite b. statistic independente c. reproductibile, i d. non-repetarea pentru orice lungime dorita. Punct de vedere istoric, prima metod de a crea numere aleatoare de ctre calculator a fost Von Neuman jumtatea anilor ptrat metod. Ideea lui era s ia ptrat a aleatoare precedente

28 Tehnici de simulare pe computer numrul i pentru a extrage cifre mijloc. De exemplu, s presupunem c suntem 10-generatoare de cifre i c valoarea precedent a fost 5772156649. Ptrat de aceast valoare este 33317792380594909291, iar numrul urmtor este 7923805949. Cu privire la ntrebarea care apare aici este modul n care o astfel de metod poate da o secven de numere aleatoare. Ei bine, nu, dar pare a fi! Metoda mijlocul ptrat a fost relativ lent i statistic nesatisfctoare. Acesta a fost mai trziu a abandonat n favoarea altor algoritmi. n urmtoarele seciuni, vom descrie congruential metod, generatoare Tausworthe, generatoare lag Fibonacci, i Mersenne Twister. 2.3 Metoda congruential Aceasta este o metoda foarte populara si cea mai mare parte cod de computer disponibile pentru generarea de numere aleatoare de utilizare o variant a acestei metode. Avantajul acestui congruential metod este faptul c este foarte simplu, rapid, i-l produce pseudo-aleatoare numerele care sunt statistic acceptabil pentru simulare pe computer. Metoda congruential utilizeaz urmtoarea relaie recursive pentru a genera numere aleatoare. xi +1 = AXI + c (mod m) n cazul n care XI, A, C i m sunt toate numerele non-negativ. Avnd n vedere c anterior aleatoare Numrul a fost xi, n urmtorii numere aleatoare xi +1 pot fi generate dup cum urmeaz. nmulii xi de a i apoi se adaug C. Apoi, calcula m modulul rezultat. Aceasta este, mprii rezultatul de m i a stabilit xi +1 egal cu restul de aceast divizare. De exemplu, dac x0 = 0, a = c = 7, i m = 10, atunci putem obine urmtoarea secven de numere: 7, 6, 9, 0, 7, 6, 9, 0, ... Metoda folosind expresia de mai sus este cunoscut sub numele de mixt congruential metod. O variant mai simpl a acestei metode este multiplicativ congruential metod. Aceast metod utilizeaz relaia xi +1 = AXI (mod m). Punct de vedere istoric, multiplicativ Generatoare de congruential a venit nainte de generatoare mixt congruential. Mai jos vom limita nostru de discuii pentru a generatoarelor mixte congruential.

Generarea numere pseudo-aleatoare 29 Numerele generate printr-o metod congruential sunt ntre 0 i m-1. Numere aleatoare uniform distribuite ntre 0 i 1 pot fi obinute prin simpla mprirea xi care rezult de m. Numrul de succesiv generat numere pseudo-aleatoare, dup care secven ncepe s se repete este numit perioad. n cazul n care perioada este egal cu m, atunci generator este c beneficiaz de o perioad complet. Teoremele de la teoria numerelor arat c perioad depinde de m. Cel mai mare valoarea lui m, cu att mai mare este perioada. n special, urmtoarele condiii pe un c,, si m garanta o perioad complet: 1. m i c nu au nici un divizor comun. 2. a = 1 (mod r) n cazul n care r este un factor de prim m. Asta este, dac r este un numr prim (divizibil numai de la sine si 1) care imparte m, apoi se imparte A-1. 3. o. = 1 (mod 4) Dac M este un multiplu de 4 Este important s reinei c nu ar trebui s foloseasc orice valori arbitrare pentru A, C, i m. Testarea sistematic a valorilor diferite pentru aceti parametri au dus la generatoare care au o perioad complet i care sunt statistic satisfctoare. Un set de astfel de valori este: a = 314, 159, 269, C = 453, 806, 245, i m = 232 (pentru o main pe 32 de bii). n scopul de a obine un generator de nceput, avem nevoie n continuare de o valoare iniial de semine pentru x. Ea va deveni evident mai trziu c valoarea seminele nu afecteaz secvena de numerele generate aleator dup un mic set de numere a fost generat. Punerea n aplicare a unui generator de numere pseudo-aleatoare implic o multiplicare, o completare i o divizie. Divizare pot fi evitate prin stabilirea m egal la dimensiunea a cuvntului calculator. Pentru c, n cazul n care valoarea total numeric a expresiei AXI + c este mai mic dect dimensiunea cuvntul, atunci acesta este, n sine, rezultatul operaiei AXI + c (mod m), unde m este setat egal cu dimensiunea cuvntului. Acum, s presupunem c expresia AXI + c d un numr mai mare dect dimensiunea cuvntul. n acest caz, atunci cnd calculul se efectueaz, o preaplin va avea loc. n cazul n care depirea nu are ca efect executarea programului care urmeaz s fie avortati, dar pur si simplu face ca cifrele semnificative care urmeaz s fie pierdut, apoi cifrele rmase din stnga n registru este restul mpririi (AXI + c) / m. Acest lucru se datoreaz faptului c a pierdut

30 Tehnici de simulare pe computer cifre semnificative va reprezenta multipli de valoarea lui m, care este raportul dintre de mai sus diviziune. n scopul de a demonstra ideea de mai sus, s ne ia n considerare o zecimal fictiv calculator a crui registru poate gzdui un maxim de 2 cifre. Evident, cel mai mare numr care pot fi pstrate n registru este de 99. Acum, ne-am stabilit m egal cu 100. Pentru a = 8, x = 2, i c = 10, avem ca AXI + c = 26, i 26 (mod 100) = 26. Cu toate acestea, dac x = 20, atunci avem c AXI + c = 170. n acest caz, AXI produsul (care este egal cu 8x20) va provoca o supraaglomerare s apar. Prima cifr semnificativ va fi pierdute i, astfel, registrul va conine numrul 60. Dac adugm acum c (care este egal cu 10) la rezultatul de mai sus va obine 70, care este, restul de diviziune 170/100. 2.3.1 General Metode de congruential Metoda mixt congruential descris mai sus poate fi considerat ca un caz special de Generator de text: xi +1 = f (xi, xi-1, ...) (mod m), n cazul n care f (.) este o funcie de generate anterior numere pseudo-aleatoare. Un caz special metodei generale de mai sus este congruential ptratic congruential generator. Acest are forma:2

xi +1 = a1xi + a2xi-1 + c (mod m). Cazul special al a1 = a2 = 1, c = 0 i m este o putere de 2 a fost dovedit a fi legate de la metoda midsquare. Un alt caz de construcii care a fost luat n considerare este aditiv metoda congruential, care se bazeaz pe relaia f (xi, xi-1, ..., xi-k) = a1xi + a2xi-1 + ... akxi-k.

Generarea numere pseudo-aleatoare Cazul de f (xi, xi-1) = xi + xi-1 a primit o atenie. 2.3.2 Generatoare de compozit 31 Putem dezvolta generatoare compozite prin combinarea a dou generatoare separate (de obicei, generatoare congruential). Prin combinarea generatoare separate, una sper s realizeze o mai bun Comportamentul statistice dect oricare generatorului individuale. Unul dintre exemple bune pentru acest tip de generator de utilizri congruential secunde generator shuffle de ieire a generatorului congruential primul. n special, primul generator este utilizat pentru a umple un vector de dimensiune n cu k primul su generat numere aleatoare. doilea generator este apoi utilizat pentru a genera un ntreg r aleatoare uniform distribuite peste numere de la 1, 2, ..., k. Numr aleator stocat n poziia rth a vectorului este returnat ca numrul aleatoriu primul generator de compozit. Primul generator apoi nlocuiete numrul aleatoriu n poziia rth cu un numr aleator nou. Urmtor de numere aleatorii care vor fi returnate de ctre generatorul compozit, este cea selectat de ctre doilea generator de vectorul actualizat al numere aleatoare. Procedura se repet se n acest mod. Sa demonstrat c un astfel de generator de combinat a bun proprietile statistice, chiar dac dou generatoare separate folosite sunt rele. 2.4 Tausworthe generatoare Generatoare de Tausworthe sunt generatoare de aditiv congruential obinut atunci cnd modulul m este egal cu 2. n special, xi = (a1xi-1 + a2xi-2 + ... + Anxi-n) (mod 2) n cazul n care xi poate fi 0 sau 1. Acest tip de generator produce un flux de bii {bi}. n innd seama de acest lucru, este suficient s se presupun c ai coeficieni sunt, de asemenea, binare. Astfel, xi este obinute de la expresia de mai sus prin adugarea unor precedente de bii i apoi transport un modulo 2 operaiune. Acest lucru este echivalent cu operaiunea SAU exclusiv, astfel cum notated i definit n tabelul de adevr de mai jos.

32 Tehnici de simulare pe computer A 0 0 1 1 B 0 1 0 1 AB 0 1 1 0 AB este adevrat (adic egal cu 1), atunci cnd fie A este adevrat i B false, sau A este fals i B adevrat. Bii generate pot fi puse mpreun pentru a forma un secvenial L-bii binar ntreg ntre 0 i 2L-1. Mai multe tehnici de selecie bii au fost sugerate n literatura de specialitate. n schema generatorului compozit discutat mai devreme, unul dintre generatoare (dar nu ambele) ar putea fi un generator Tausworthe. Generatoare Tausworthe sunt independente de calculator folosit i dimensiunea acesteia cuvnt i au cicluri foarte lungi. Cu toate acestea, ele sunt prea lent, deoarece acestea produc numai bii. A variaie rapid de acest generator este generatorul de trinom pe baz de Tausworthe. Dou sau mai multe astfel de generatoare trebuie s fie combinate pentru a obine o producie bun statistic. 2.5 Lag Fibonacci generatoare lag Fibonacci generatoare (LFG) reprezint o mbuntire important n generatoare congruential, i sunt utilizate pe scar larg n simulare. Ele se bazeaz pe bine-cunoscut Fibonacci secven, o recuren relaie aditiv, prin care fiecare element este calculat folosind cele dou elemente calculat anterior, dup cum se arat mai jos: xn = xn-1 + xn-2 n cazul n care x0 = 0 i x1 = 1. nceputul sirul lui Fibonacci este: 0, 1, 1, 2, 3, 5, 8, 13, 21. Bazat pe aceast relaie recuren, forma general de LFG poate fi exprimat ca urmeaz: xn = xn-j Oxn-k (mod m)

Generarea numere pseudo-aleatoare 33 n cazul n care 0 u) indic o operaiune de shiftright de ori u pentru variabila x. (X 1 LT =0 LT = LT - 1 nici o comand remarcabil =1 LT = 0 I=I+Q Pentru a a sosit T> T nu da Genera de zi cu zi a cererii D I = I-D b

Figura 4.27: Un design de uniti de timp de simulare a unui sistem de inventariere.

Simulare modele 97 inventar nceput, d) distribuii de probabilitate pentru variabile D i LT reprezentnd cererii de zi cu zi i timp de plumb, respectiv, e) T, timpul total de simulare, i C1 f), C2, C3, reprezentnd costul pe unitatea de exploataie pe unitatea de timp, costul de configurare pe comanda, iar costul pe unitatea de deficit pe unitatea de timp, respectiv. Parametrii de ieire sunt TC1, TC2, TC3 reprezentnd costurile totale exploataiei, configurare i, respectiv, lipsa.b I