C ORSO DI L AUREA IN I NFORMATICA
F ACOLTÀ DI S CIENZE
U NIVERSITÀ DI V ENEZIA
Appunti per il corso di
Sistemi di Elaborazione dell’Informazione:
valutazione delle prestazioni di sistemi
S. Balsamo
A.A. 1999 – 2000
S. Balsamo
Indice
Introduzione 2
Capitolo 1: Sistemi e Modelli 4
1.1 Definizione di sistemi e modelli 4
1.2 Classificazione di sistemi e modelli 8
1.3 Creazione ed uso di modelli: ciclo di modellamento 10
1.4 Modelli a sviluppo gerarchico 13
1.5 Modelli per la valutazione delle prestazioni di sistemi:
modelli analitici, simulativi e ibridi 18
Capitolo 2: Modelli matematici di sistemi 21
2.1 Processi Stocastici 21
2.2 Processo di Poisson 24
2.3 Processi di Markov 27
2.3.1 Catene di Markov a tempo discreto 27
2.3.2 Catene di Markov a tempo continuo 31
2.4 Processi di nascita-morte 34
Capitolo 3: Modelli a coda singola 38
3.1 Introduzione ai modelli a coda singola 38
3.2 Modelli basilari di code: i sistemi M/M/1 ed M/M/m 44 3.3 Modelli basilari di code: il sistema M/G/1 53
3.4 Discipline a priorità 55
3.5 Influenza dei fattori di scala 59
Capitolo 4: Modelli a rete di code 62
4.1 Introduzione ai modelli a rete di code 62
4.2 Modelli a rete di code Markoviane 66
4.3 Modelli a rete di code in forma prodotto 70
4.3.1 Reti di Jackson 71
4.3.2 Reti di Gordon-Newell 74
4.3.3 Reti BCMP 77
Capitolo 5: Algoritmi per modelli a rete di code 83
5.1 Analisi operazionale 83
5.1.1 Analisi asintotica dei limiti alle prestazioni di sistema 86 5.2 Algoritmi per modelli di code in forma prodotto 91
5.2.1 Algoritmo di Convoluzione 93
5.2.2 Algoritmo di Mean Value Analysis 98
5.3 Metodi di aggregazione e decomposizione 102
5.3.1 Metodi di aggregazione su processi stocastici 103 5.3.2 Metodi di aggregazione per modelli di code 107 Bibliografia 110
S. Balsamo - 2 - Introduzione
Il progetto e lo sviluppo dei sistemi di elaborazione dell’informazione richiede l’analisi di diversi aspetti che includono lo studio della funzionalità e correttezza, della affidabilità e sicurezza, di costo e di prestazioni (performance). Le prestazioni di un sistema sono valutabili sia qualitativamente che quantitativamente. L’analisi quantitativa si effettua definendo opportune figure di merito o indici di prestazione, quali, ad esempio, l’utilizzazione delle risorse e i tempi di risposta forniti dal sistema.
La valutazione delle prestazioni di un sistema (system performance evaluation) è un aspetto fondamentale nel progetto, nello sviluppo, nella configurazione e messa a punto di un sistema di elaborazione. Lo studio della valutazione delle prestazioni di sistemi costituisce un’area di ricerca in informatica che ha portato alla definizione di metodologie e di strumenti per la creazione ed analisi di modelli di sistemi (modeling) e allo sviluppo di tecniche di misurazione e caratterizzazione del carico. I modelli per la valutazione delle prestazioni di sistemi sono analizzati tramite metodi sia analitici che simulativi [DL 93, FER 78, FSZ 81, JAI 90, KAN 92, KIN 90, KLE 75, KOB 78, LAV 83, LAV 89, LZG 84, MBC 86, SC 79, SCH 87, TRI 82].
Introduciamo i principali modelli e metodi per la valutazione delle prestazioni di sistemi, con particolare enfasi sullo sviluppo ed applicazione dei modelli a rete di code che hanno avuto un notevole sviluppo negli ultimi anni.
Notiamo che i modelli e le metodologie qui descritte trovano ampia applicazione nella rappresentazione ed analisi non solo di diversi sistemi di elaborazione, ma anche di sistemi di comunicazione e telecomunicazione, così come di sistemi di produzione e di traffico. Presentiamo i metodi di analisi dei modelli basati su tecniche matematiche, mentre non trattiamo i metodi di analisi simulativi.
Nel capitolo 1 introduciamo brevemente una classificazione e definizione di sistemi e modelli, lo schema di creazione ed uso dei modelli e lo sviluppo gerarchico di modelli strutturati a diversi livelli di astrazione.
Nel capitolo 2 presentiamo i modelli di sistemi basati sui processi stocastici. In particolare consideriamo i processi stocastici Markoviani e fra questi i processi di nascita e morte.
Nei capitoli 3 e 4 definiamo ed analizziamo i modelli basati sulla teoria delle code, dove il sistema è rappresentato come un’unica risorsa (modelli a coda singola, capitolo 3) o come un insieme di risorse interconnesse ed interagenti (modelli a rete di code, capitolo 4).
I modelli basilari di teoria delle code sono definiti insieme ai metodi di analisi esatta, sotto diverse condizioni delle caratteristiche operative. In particolare nel
S. Balsamo - 3 -
capitolo 3 sono trattate le discipline di ordinamento (scheduling) o di servizio e l’influenza dei fattori di scala.
Fra i modelli a rete di code particolare attenzione è dedicata ai modelli in forma prodotto la cui analisi può essere efficientemente ottenuta sulla base di algoritmi a complessità polinomiale nel numero di componenti del modello. I due algoritmi più importanti, Convoluzione ed MVA, sono introdotti nel capitolo 5.
In tale capitolo vengono inoltre presentati metodi di analisi operazionale e metodi di aggregazione e decomposizione. I metodi di analisi operazionale costituiscono un semplice strumento applicabile ad una ampia classe di modelli che include le reti di code. Sulla base di semplici relazioni fra gli indici di prestazione del sistema si ricavano intervalli per gli stessi in condizioni asintotiche del carico del sistema. I metodi di aggregazione e decomposizione, infine, permettono di studiare e analizzare modelli di sistemi di grandi dimensioni e di elevata complessità strutturale. Tali metodi sono definiti sia per i processi stocastici Markoviani che per i modelli a rete di code.
