Capitolo 3 - Modelli a singola coda In questo capitolo presentiamo i

Capitolo 3 - Modelli a singola coda
In questo capitolo presentiamo i modelli a coda singola che rappresentano il
sistema oggetto di studio ad un elevato livello di astrazione, come un’unica risorsa.
Vengono introdotti i modelli basilari e lo studio delle discipline di ordinamento di
coda.
3.1 Introduzione ai modelli di code
Un modello a coda è costituito dalla rappresentazione di un sistema di congestione
in cui utenti che provengono da una popolazione si accodano per ottenere il servizio da
un insieme di risorse o serventi, ottenuto il quale lasciano il sistema.
Un esempio di sistema a coda è illustrato in Fig. 3.1 e la sua usuale rappresentazione
in termini di modelli di code in Fig. 3.2. Una coda è una linea di attesa per un
servizio. Il servizio è fornito da un servente singolo o da serventi multipli che operano
in parallelo. L’insieme formato da coda e serventi è detto centro di servizio. Un
utente che arriva al centro di servizio, dopo una eventuale attesa in coda per un
servente libero, viene assegnato ad un servente dal quale riceve il servizio al termine
del quale lascia il centro.
Esempio. I messaggi generati da una sorgente devono essere trasmessi uno
alla volta su una linea di comunicazione. Quando un messaggio è generato,
se trova la linea occupata aspetta temporaneamente in un buffer. Quando la
linea si libera, se il buffer non è vuoto, uno dei messaggi viene prelevato dal
buffer e viene trasmesso sulla linea. Tale sistema può essere rappresentato
da un modello a code in cui i messaggi sono gli utenti, la linea di
comunicazione è il servente, la trasmissione del messaggio è il servizio e i
messaggi che aspettano nel buffer formano la coda.
Esempio. Un sistema di elaborazione uniprocessore può essere
rappresentato da un semplice sistema di code dove i programmi da elaborare
sono gli utenti, la coda dei processi pronti per l'esecuzione formano la coda,
il processore è il servente, il servizio è l’esecuzione del programma sul
processore.
servente 1
servente 2
coda
servente m
popolazione
Fig. 3.1 - Sistema di congestione -
S. Balsamo
- 38 -
q
w
s
1
2
∆
m
t
t
w
s
tq
Fig. 3.2 - Modello a coda singola Un sistema a coda è caratterizzato da alcune grandezze, rappresentate dalle
seguenti variabili, illustrate in Fig. 3.2:
• ∆ tempo di interarrivo
• w numero di utenti in coda e tw tempo di attesa in coda
• s numero di utenti in servizio e t s tempo di servizio
• q numero di utenti nel sistema e tq tempo di risposta.
∆ rappresenta il tempo che intercorre fra un arrivo ed il successivo, w, s e q sono
variabili a valore intero, (w≥0, q≥0, 0≤s≤m) e per definizione
q=w+s
(3.1).
tw è il tempo che intercorre fra l’arrivo di un utente alla coda e l’istante in cui esso
entra in servizio, ts è il tempo fra l’inizio ed il completamento del servizio, mentre tq
è il tempo fra l’arrivo e la partenza dal sistema dello stesso utente. Per definizione,
tali variabili di tempi sono legati dalla seguente relazione:
tq = tw + ts
(3.2).
Le variabili introdotte sono variabili aleatorie caratterizzate da una distribuzione
di probabilità. Fra queste tipicamente alcune sono parametri del sistema, quali t s e ∆,
mentre le altre sono oggetto di analisi e di valutazione.
Per specificare completamente un sistema di code è necessario descrivere [LAV 83]:
• il processo di arrivo al sistema
S. Balsamo
- 39 -
•
•
•
•
•
il processo di servizio
il numero di serventi e la velocità di servizio
la disciplina di coda (o di servizio)
la dimensione della coda e
la popolazione.
Processo di arrivo
Assumiamo che il tempi di interarrivo ∆ siano variabili casuali statisticamente
indipendenti con la stessa distribuzione di probabilità. Ad esempio, se i tempi di
interarrivo sono variabili random esponenziali, il processo di arrivo è un processo di
Poisson (vedi capitolo 2, sezione 2). Nei modelli in cui si distinguono diversi tipi di
utente ad ogni tipo è associato un processo di arrivo.
Domanda di servizio, tasso di servizio e tempo di servizio
La quantità di servizio richiesta da un utente ad un centro di servizio è detta
domanda di servizio ed è espressa in unità di tempo. Si assume che le domande di
servizio di successivi utenti siano variabili casuali statisticamente indipendenti. Utenti
dello stesso tipo effettuano domanda di servizio avente la medesima distribuzione di
probabilità, mentre utenti di tipo diverso possono richiedere domande di servizio con
distribuzione di probabilità diverse.
La velocità o tasso di servizio di un servente è una caratteristica del servente, ovvero
della risorsa, ed è espressa in unità di servizio per unità di tempo. Assumiamo che
tutti i serventi di un centro di servizio abbiano la stessa velocità.
Componendo le domande ed il tasso di servizio definiamo il tempo di servizio di un
utente come il rapporto: tempo di servizio = (domanda di servizio / velocità di
servizio) espresso quindi in unità di tempo
Esempi. Consideriamo un sistema costituito da una linea di comunicazione
per trasmettere messaggi, in cui il servizio corrisponde alla trasmissione. La
domanda di servizio è esprimibile in unità di bit da trasmettere
(indipendente dalla velocità) ed il tasso di servizio in bit/sec.
Consideriamo un processore che elabora programmi per cui il servizio
corrisponde alla elaborazione delle istruzioni. Allora un programma è
rappresentato nel modello da un utente che effettua una domanda di servizio
esprimibile in unità di istruzioni. Il processore corrisponde nel modello di
code ad un servente che è caratterizzato dal tasso di servizio espresso in
istruzioni/sec.
Disciplina di servizio
Una disciplina di servizio è un algoritmo di ordinamento degli utenti in coda in
base al quale viene selezionato l'utente da servire, ovvero l’ordine con cui estrarre gli
utenti dalla coda. La disciplina di servizio può dipendere
S. Balsamo
- 40 -
• dall’ordine di arrivo alla coda
• dalla priorità assegnata all’utente
• dalla quantità di servizio già fornito all’utente.
Nel seguito, se non specificato diversamente, assumiamo che la disciplina
indipendente dalla domanda di servizio del singolo utente.
Classici esempi di discipline di servizio dipendenti solo dall’ordine di arrivo
centro di servizio sono la FIFO (first-in-first-out) che serve gli utenti in ordine
arrivo e la LIFO (last-in-first-out) che serve gli utenti in ordine inverso al tempo
arrivo, ovvero serve per primo l’ultimo utente arrivato in coda.
si
al
di
di
Esempi. In una rete di comunicazione i messaggi (utenti) vengono trasmessi
(serviti) nell’ordine di arrivo al nodo di trasmissione.
In un sistema di elaborazione con schema di memoria ad accesso diretto le
richieste di trasferimento di record (utenti) sono spesso trasferite (servite)
una alla volta in ordine di arrivo.
La disciplina di servizio RAND determina l’utente da estrarre dalla coda e servire
in modo casuale, secondo la distribuzione unforme discreta.
Una caratteristica di alcune discipline di servizio è il prerilascio delle risorse o
prelazione. In tal caso è ammesso che un utente che viene selezionato per essere
servito interrompa l’utente attualmente in servizio, ottenga l’assegnamento del
servente ed inizi il proprio servizio. Al termine del servizio l’utente interrotto più
recentemente riprende il servizio. La ripresa del servizio può essere con o senza
perdita in base alla possibilità che il servizio precedentemente ottenuto sia ancora
utilizzabile.
Ad esempio la disciplina LIFO con prelazione serve l’ultimo utente in arrivo
interrompendo l’attuale servizio.
Le discipline a priorità determinano l’ordine di servizio degli utenti sulla base di
priorità assegnate ad esse.
Le priorità possono essere assegnate agli utenti in modo statico o dinamico. Esse
possono essere basate su informazioni non dipendenti dalle richieste di servizio
(astratte) oppure basate sulla domanda di servizio.
Anche le discipline a priorità possono essere con prelazione, quando si può
interrompere il servizio, e senza prelazione quando il servizio non è interrompibile.
L’utente con priorità più alta ottiene il servizio ed utenti con uguale priorità vengono
serviti in accordo ad una disciplina di quel livello, tipicamente FIFO.
Esempi. In alcune reti di comunicazione i messaggi (utenti) di controllo
hanno maggiore probabilità di trasmissione (servizio) su altri messaggi,
inoltre il servizio non può essere interrotto. I messaggi di controllo vengono
trasmessi in ordine FIFO (priorità senza prelazione).
S. Balsamo
- 41 -
Nei sistemi operativi i programmi di sistema (utenti) hanno priorità
maggiore rispetto a programmi di utente per l’esecuzione sul processore
(servente). Un programma utente può essere interrotto e riattivato
successivamente (priorità con prelazione).
La disciplina round robin è un esempio di disciplina che dipende dalla quantità di
servizio già assegnato. Tale algoritmo assegna il servente ciclicamente agli utenti per
un intervallo massimo di tempo detto quanto. Se la domanda di servizio dell’utente
non è soddisfatta durante il quanto, l’utente viene posto in coda in attesa del prossimo
quanto. Tale disciplina di servizio favorisce gli utenti che presentano brevi richieste
di servizio a scapito degli utenti con lunghe domande di servizio.
Esempio. La disciplina round robin è adatta in sistemi operativi in sistemi
time-sharing per lo scheduling del processore.
Se consideriamo il quanto molto piccolo la disciplina round robin apparentemente
tende a servire tutti gli utenti simultaneamente. Al limite per il quanto tendente a zero,
quando nel centro di servizio sono presenti q utenti, ognuno apparentemente riceve
servizio con velocità pari ad (1/q) del tasso di servizio. Tale disciplina di servizio in
cui tutti gli utenti ricevono servizio simultaneamente dal servente in uguale porzione
viene detta processor sharing (PS).
Esempio. Tre processi (utenti) serviti con disciplina PS da un processore
(servente) di 3 MIPS (tasso di servizio), ricevono servizio ciascuno a
velocità di 1 MIPS.
Notazione di Kendall. Per descrivere e definire i modelli a coda singola Kendall
ha introdotto la seguente notazione:
A/B/c/n/p/Z
dove i simboli denotano:
A : distribuzione del tempo di interarrivo ∆
B : distribuzione del tempo di servizio ts
c : numero di serventi m
n : dimensione della coda ovvero la capacità del centro, q,
p : dimensione della popolazione
Z : disciplina di servizio.
Tale notazione si semplifica in A/B/c quando coda e popolazione sono illimitate e
la disciplina di servizio è FIFO, ovvero se n=p=∞ e Z=FIFO.
Le distribuzioni di probabilità A e B sono rappresentate da simboli che le
denotano. Ad esempio D denota la distribuzione deterministica o costante, M la
S. Balsamo
- 42 -
distribuzione esponenziale negativa, H h l’iperesponenziale ad h stadi, E k l’Erlangiana
a k stadi e G la generale.
Esempi. Il sistema D/D/1, denota un sistema con un servente, distribuzione
del tempo di interarrivo e del tempo di servizio deterministiche.
Il sistema M/M/m (m>0), denota un sistema con m serventi, distribuzione
del tempo di interarrivo e del tempo di servizio esponenziale.
Il sistema M/G/1 denota un sistema con un servente, distribuzione del
tempo di interarrivo esponenziale e distribuzione del tempo di servizio
generale.
Notiamo che anche se le distribuzioni di interarrivo e di servizio sono identiche
(A=B), i parametri possono essere diversi.
Il comportamento del sistema nel tempo può essere analizzato in un tempo finito.
In tal caso si parla di analisi transiente. Quando il sistema raggiunge le condizioni di
equilibrio in un tempo che tende ad infinito, ovvero se il sistema è stabile si effettua
l’analisi stazionaria.
L’analisi dei sistemi a coda singola può essere spesso ricondotta all’analisi dei
processi stocastici sottostanti che rappresentano l’evoluzione nel tempo del sistema,
utilizzando, in particolare, processi stocastici di Markov e processi di nascita e morte.
Tale analisi porta alla valutazione degli indici di prestazione del sistema di code, in
particolare di:
• numero di utenti nel sistema
q
• numero di utenti in coda
w
• tempo di risposta
tq
• tempo di attesa
tw
• utilizzazione
U
• throughput
X.
Le prime quattro sono variabili casuali di cui si valuta la distribuzione di probabilità,
e/o i momenti. L'utilizzazione è definita come la percentuale di tempo in cui il
sistema è occupato e può essere interpretata anche come probabilità. Il throughput o
produttività è una misura media della velocità di uscita dal sistema, ovvero il numero
medio di utenti serviti per unità di tempo.
Dalle relazioni (3.1) e (3.2) possiamo scrivere immediatamente le seguenti
relazioni fra i valori medi:
E[q] = E[w] + E[s]
E[tq] = E[tw] + E[ts]
S. Balsamo
(3.3)
(3.4).
- 43 -
Una relazione fondamentale nella teoria delle code è rappresentato dal teorema di
Little il quale stabilisce che il numero medio di utenti in un sistema è uguale al
prodotto fra il throughput e il tempo medio di risposta, ovvero:
E[q] = X E[tq]
E[w] = X E[tw]
(3.5)
(3.6).
Tale teorema è valido sotto ipotesi molto generali ed è applicabile a diversi livelli
(coda, sistema, sottosistema), come discutiamo nel capitolo 5.
Inoltre tale relazione è fondamentale negli algoritmi di soluzione di reti di code in
forma prodotto [LAV 83, KLE 75].
3.2. Modelli basilari di code: i sistemi M/M/1 ed M/M/m
Questo semplice modello può essere utilizzato per rappresentare sistemi formati da
una singola risorsa, o sistemi semplici rappresentati ad un livello di astrazione elevato.
Inoltre il modello M/M/1 costituisce la base per la definizione di modelli più
complessi a struttura reticolare e per lo sviluppo gerarchico di modelli a diversi livelli
di astrazione.
Nella notazione di Kendall il sistema di code M/M/1 denota un sistema aperto
formato da un singolo centro di servizio con
• distribuzione del tempo di interarrivo esponenziale, di parametro λ,
• tempo di servizio degli utenti indipendente e con identica distribuzione
esponenziale di parametro µ,
• singolo servente.
La disciplina di servizio è FIFO e sia la memoria che la popolazione sono infinite.
Il sistema M/M/1 è illustrato in Fig. 3.3. Consideriamo il processo stocastico {q(t) | t
≥0} dove q(t) denota il numero di utenti presenti nel sistema al tempo t. Lo spazio
degli stati del processo è l’insieme dei naturali N. Per le ipotesi di esponenzialità dei
tempi di interarrivo e di servizio, gli unici eventi possibili che si osservano in un
intervallo di tempo dt quando nel sistema vi sono k utenti sono i seguenti:
• nessun arrivo e nessun completamento di servizio (permanenza nello stato k);
• un arrivo e nessun completamento di servizio (transizione dallo stato k allo stato k+1
con probabilità λdt);
• nessun arrivo e un completamento di servizio (transizione dallo stato k allo stato k-1
con probabilità µdt);
• uno o più arrivi e uno o più completamenti di servizio (transizione con probabilità
trascurabile rispetto alle altre transizioni per l’ipotesi di esponenzialità).
S. Balsamo
- 44 -
µ
λ
Fig. 3.3 - Sistema M/M/1 Quindi il processo stocastico considerato è di nascita e morte, con tassi di nascita
λ k=λ, k≥0 e con tassi di morte µ k=µ, k≥1.
Analisi transiente
La distribuzione di probabilità di stato al tempo t+δt può essere ottenuta in
funzione della probabilità di stato al tempo t come segue:
π 0 (t + δt) = π 0(t) (1-λ δt) + π 1(t) (1-λ δ t ) µ δt + o (δt)
πk (t + δt) = πk (t) [ (1-λ δt) (1- µ δt)] + πk +1 (t) (1-λ δt) µ δt + πk -1(t) λ δt (1-µ δt)+
+
o(δt)
k>0
da cui si ricavano le equazioni differenziali del tipo (2.12)
d π 0 (t)
dt
d π k (t)
dt
= - λ π 0 (t) + µ π 1 (t)
= - (λ + µ) π k (t) + µ π k+1 (t) + λ π k-1 (t)
k>0
da cui, con la condizione iniziale di sistema vuoto (π 0(0) = 1, πk(0) = 0, ∀k≠0) [KLE
75], si ricava la seguente soluzione π k(t) che fornisce le probabilità di osservare k
utenti nel sistema al tempo t, t>0, k≥0:
-(λ+µ)t
π k (t) = e
ρ
k-i
2
Ik-i (at) + ρ
k-i-1
2
∞
Ik+i+1 (at) + (1-ρ) ρ
k
∑
ρ
-
j
2
Ij (at)
j = k+i+2
dove
ρ=λ
µ
∞
a=2µρ
1/2
Ik (x) =
∑
m=0
k+2m
(x/2)
(k+m)! m!
k ≥ -1
Analisi stazionaria
Poiché il processo {q(t) | t ≥0} è un processo di nascita e morte con tassi costanti
λ e µ, se esso soddisfa la condizione di stazionarietà la soluzione stazionaria può
essere
S. Balsamo
- 45 -
immediatamente calcolata dalle formule (2.16) e (2.17).
Definiamo l’intensità di traffico del sistema come rapporto fra tempo medio di
servizio e tempo medio di interarrivo, denotato da ρ = λ / µ. La condizione di
stazionarietà del sistema M/M/1 richiede che ρ <1, ovvero che il tasso di arrivo al
sistema sia minore del tasso di servizio, λ < µ.
In tal caso il sistema è stabile ed esiste la distribuzione di probabilità di stato in
equilibrio e dalle formule (2.16) e (2.17) si ricava:
π 0 = 1-ρ
π k = ρ k π 0 = ρ k (1-ρ)
k>0
(3.7).
Notiamo che la distribuzione di probabilità del numero di utenti nel sistema in
condizioni stazionarie è geometrica a ragione ρ. Il numero medio di utenti nel sistema,
che denotiamo con N=E[q], si può immediatamente ricavare come:
N = ρ / (1-ρ)
(3.8)
e la varianza del numero di utenti, denotata da Var[q], è
Var[q] = ρ / (1-ρ)2.
Con la formula (3.7) abbiamo ricavato una caratterizzazione completa della
variabile casuale q, numero di utenti presenti nel sistema, in condizioni stazionarie.
Consideriamo ora altri indici di interesse del sistema M/M/1: il numero di utenti
presenti nella sola coda del sistema, denotato da w∈N, il numero di utenti presenti nel
servente s∈{0,1}, il tempo di attesa di un utente in coda tw ∈R 0+ e il tempo di
risposta di un utente tq ∈R 0+. Di tali grandezze è interessante ricavare la distribuzione
di probabilità o almeno i valori medi.
Per la relazione (3.3) ricaviamo immediatamente il numero medio di utenti in coda,
denotato da W=E[w], poiché E[s] = ρ ed E[q]=N:
W = N - ρ = ρ 2 / (1-ρ)
(3.9).
Il tempo medio di risposta, denotato da R=E[tq], si ricava dal teorema di Little
ovvero dalla equazione (3.5) che per il sistema M/M/1 assume la forma N= λ R, e
dall’equazione (3.8):
R = (1/µ) / (1-ρ)
S. Balsamo
(3.10).
- 46 -
Infine il tempo medio di attesa in coda, Tw= E[tw] si ottiene o dal teorema di Little
(formula (3.6)) come W = λ Tw o dalla relazione (3.4) ovvero R = T w + Ts, dove T s
= 1/ µ denota il tempo medio di servizio, da cui si ricava:
Tw = (ρ /µ ) / (1-ρ)
(3.11).
L’utilizzazione è esprimibile per il sistema M/M/1 per la formula (3.7) come:
U = 1 - π0 = ρ
N
(3.12).
30
0
0.0
0.2
0.4
0.6
0.8
1.0
1.2
1.4
ρ
Fig. 3.4 - Numero medio di utenti (N) in un sistema M/M/1 in funzione dell’intensità
di traffico ρ -
R
20
0
0.0
0.2
0.4
0.6
0.8
1.0
1.2
1.4
ρ
Fig. 3.5 - Tempo medio di risposta (R) in un sistema M/M/1 in funzione dell’intensità
di traffico ρ -
S. Balsamo
- 47 -
Notiamo che gli indici medi di prestazione del sistema M/M/1, ovvero il numero
medio di utenti nel sistema e in coda e i tempi medi di risposta e di attesa, tendono ad
infinito, per ρ→1, come si osserva dalle espressioni (3.8)-(3.11). Tale comportamento,
del numero medio di utenti nel sistema e del tempo medio di risposta è illustrato nelle
Figure 3.4 e 3.5 ed è caratteristico dei sistemi di code in cui si osserva il fenomeno
della saturazione del sistema che si manifesta all’aumentare della congestione del
sistema.
Dalla distribuzione di probabilità (3.7) possiamo calcolare la probabilità con cui si
osservano almeno k utenti nel sistema in condizioni di equilibrio:
Prob { numero di utenti nel sistema ≥ k }= Σi≥k π i = (1-ρ) Σi≥k ρ i = ρ k (3.9).
Questa espressione può essere utilizzata per risolvere problemi di
dimensionamento della coda. Ad esempio, per realizzare un sistema con buffer finito
di dimensione K, rappresentabile con un modello M/M/1, si può scegliere il valore di
K come il minimo k>0 tale che Prob{numero di utenti nel sistema ≥ k }< ε, per un
ε prefissato, ovvero K= logρ ε .
Se la condizione di stazionarietà del sistema M/M/1 non è soddisfatta, cioè se ρ ≥ 1
allora il sistema è instabile e non esiste la distribuzione stazionaria di probabilità. In
questo caso la coda tende a crescere in modo illimitato così come il tempo medio di
risposta degli utenti.
Casi particolari
Diverse variazioni del sistema M/M/1 possono essere analizzate ancora come
processi di nascita e morte, con opportuni tassi di nascita e di morte. Vediamo alcuni
casi rappresentativi al variare del numero di serventi e della dimensioni della memoria
e/o della popolazione. Per una trattazione dettagliata si veda [KLE 75].
Sistema M/M/∞
(Infiniti serventi)
Consideriamo un sistema aperto con processo di arrivo Poissoniano di parametro λ,
con distribuzione del tempo di servizio esponenziale di parametro µ e con infiniti
serventi. Un modello M/M/∞ permette di rappresentare un sistema nel quale ad ogni
arrivo vi è sempre un servente libero. In un sistema di questo tipo non si forma quindi
mai coda, poiché ogni utente riceve immediatamente servizio dall’istante in cui arriva
al sistema. Tale modello equivale ad un modello M/M/1 in cui il tasso medio di
servizio dipende dallo stato k in modo lineare, ovvero µ(k) = k µ, k ≥0.
Il processo stocastico {q(t) | t>0} associato al sistema M/M/∞ è un processo di
nascita e morte con tassi di nascita λk=λ, k≥0, e con tassi di morte µ k= k µ, k≥1. La
condizione di stazionarietà è certamente sempre soddisfatta, in quanto esiste
S. Balsamo
- 48 -
certamente un valore k 0 tale che ∀ k>k0 si ha λk<µ k, e.g,. k0 =[λ/µ]. Quindi il
sistema è sempre stabile, esiste la distribuzione stazionaria del numero di utenti nel
sistema, che coincide con il numero di serventi occupati ed è definita dalle formule
(2.16) e (2.17) da cui si ricava:
k
ρ -ρ
πk =
e
k!
k≥0
(3.13)
dove ρ = λ/µ. Notiamo che tale distribuzione è Poissoniana di parametro ρ.
Si ricava immediatamente il numero medio di utenti nel sistema
N=ρ
(3.14).
Dato che nel sistema M/M/∞ gli utenti non sperimentano mai coda, il tempo medio
di risposta coincide con il tempo medio di servizio:
R = Ts = 1/µ
(3.15).
Sistema M/M/m
(serventi multipli)
Il sistema aperto M/M/m è caratterizzato da un processo di arrivo Poissoniano di
parametro λ, distribuzione del tempo di servizio esponenziale di parametro µ e un
numero di serventi m>0. Un utente che arriva al sistema viene posto immediatamente
in servizio se vi è un servente libero (ovvero se vi sono meno di m utenti già presenti
nel sistema), altrimenti viene posto in coda. La disciplina di coda è FIFO. Anche
questo modello, come il precedente, equivale ad un modello M/M/1 in cui il tasso
medio di servizio dipende dallo stato k secondo la seguente funzione µ(k) = k µ,
0≤k≤m, e µ(k) = m µ, k>m.
Il processo stocastico {q(t) | t>0} associato al sistema M/M/m è un processo di
nascita e morte con tassi di nascita λk=λ, k≥0, e con tassi di morte µ k= min{k, m}µ,
k≥1. Definiamo l’intensità di traffico come ρ = λ/mµ. La condizione di stazionarietà
può essere riscritta come λ<mµ, o anche ρ<1. Quindi il sistema è stabile soltanto se il
tasso di arrivo è minore del tasso di servizio complessivo dei serventi. In questo caso
esiste la distribuzione stazionaria del numero di utenti nel sistema definita dalle
formule (2.16) e (2.17) che possono essere riscritte come:
S. Balsamo
- 49 -
k
(mρ)
πk =
k!
m-1
π0 =
m
π0
1≤k≤m
k
π0
k>m
-1
∑ (mρ)
k!
k=0
m ρ
πk =
m!
k
m
+
(mρ)
m!
1
(3.16).
1-ρ
Il numero medio di serventi occupati E[s] è dato da
m-1
E[s] =
∑
k πk +
k=0
mπm
= mρ = λ
1-ρ
µ
(3.17)
dove ρ rappresenta l’utilizzazione di ogni singolo servente.
Il numero medio di utenti nel sistema è dato da
N = m ρ + πm
ρ
(3.18)
2
(1-ρ)
dove il primo termine è E[s], ed il secondo è il numero medio di utenti presenti in
coda.
Gli altri indici di prestazione possono essere calcolate le relazioni note; ad esempio
il tempo medio di risposta si ottiene applicando il teorema di Little N=λR ottenendo:
R = 1/µ + πm / (mµ (1-ρ) 2 )
(3.19).
Similmente, otteniamo il tempo medio di attesa:
TW = π m / (mµ (1-ρ) 2 )
(3.20).
La probabilità che un utente in arrivo trovi tutti i serventi occupati e quindi
sperimenti coda è
∞
∑
m
(mρ)
Prob{coda} =
πk = π0
m!
k=m
1
1-ρ
Questa formula, detta di Erlang-C, è stata applicata per lo studio di sistemi di
traffico telefonico per valutare la probabilità che una chiamata (un utente) trovi tutti i
canali di comunicazione (i serventi) occupati [KLE 75].
S. Balsamo
- 50 -
Naturalmente il sistema M/M/1 può essere visto come un caso particolare del
sistema M/M/m con m=1, per cui la formula (3.16) si riduce alla (3.7).
Una interessante applicazione del modello M/M/m consiste nello studio di
algoritmi di scheduling per la gestione di risorse multiple. Ad esempio il confronto fra
un modello M/M/m con m modelli di tipo M/M/1 può essere utilizzato per paragonare
un algoritmo di scheduling centralizzato con uno distribuito per la gestione di m
risorse rappresentabili con serventi esponenziali. Un esempio di tale applicazione
nell’ambito dei sistemi operativi è descritta in dettaglio in [DL 93].
Sistema M/M/1/K (memoria finita)
Consideriamo il sistema M/M/1 nel quale sono ammessi al più K utenti. Tale
modello permette di rappresentare sistemi caratterizzati dalla dimensione finita della
coda. Il processo di arrivo è Poissoniano di parametro λ, ma un utente che arrivando
trova il sistema completo, cioè con K utenti già presenti, non viene accettato e viene
perso. Il sistema M/M/1/K è un sistema con perdita. Nel caso particolare in cui K=1, al
più un utente è ammesso nel sistema e di conseguenza non si forma mai coda. La
distribuzione del tempo di servizio è esponenziale di parametro µ, vi è un singolo
servente, e la disciplina di coda è FIFO. Anche questo modello, per la proprietà di
assenza di memoria della distribuzione esponenziale, può essere visto come un
particolare sistema M/M/1 in cui il tasso di arrivo dipende dallo stato k secondo la
seguente funzione λ(k) =λ, 0≤k<K, e. λ(k) =0, k≥K.
Il processo stocastico {q(t) | t>0} associato al sistema M/M/1/K è un processo di
nascita e morte con spazio degli stati finito E={0,1,...,K} e tassi di nascita λ k=λ,
0≤k<K, e tassi di morte µ k= µ, 1≤k<K-1 e λ k=0 e µ k= 0 altrove. La condizione di
stazionarietà è certamente verificata, poiché il processo è finito e irriducibile e quindi
ergodico. Esiste quindi la distribuzione stazionaria del numero di utenti nel sistema
definita dalle formule (2.16) e (2.17) che diventano:
πk =
1-ρ
K+1
1-ρ
ρ
0≤ k≤K
π k= 0
k>K
dove ρ = λ / µ.
Nel caso particolare di K=1 lo spazio è formato da due soli stati e si ricava
π 0 = µ/(λ + µ) e π 1 = λ /(λ + µ).
S. Balsamo
- 51 -
Sistema M/M/1//M (popolazione finita)
Consideriamo il sistema M/M/1 assumendo che gli utenti provengano da una
popolazione finita, di dimensione M>0. Ogni utente si trova ad ogni istante o
all’interno del sistema (in coda o in servizio) o all’esterno. Assumiamo che ogni
utente, una volta che ha lasciato il sistema dopo essere stato servito, si ripresenti al
sistema stesso dopo un tempo esponenziale di parametro λ. Inoltre assumiamo che
ogni utente sia indipendente dagli altri. Questo comporta che, se vi sono k utenti nel
sistema (0≤k≤M) ed M-k all’esterno, il processo di arrivo totale è dato dalla
composizione di M-k processi di Poisson indipendenti, ognuno di parametro λ. Per la
proprietà di composizione dei processi di Poisson, anche il processo totale di arrivo al
sistema è ancora un processo di Poisson di parametro dipendente dallo stato λ(k) =
(M-k)λ, 0≤k≤M.
Il processo stocastico {q(t) | t>0} associato al sistema M/M/1//M è un processo di
nascita e morte con spazio degli stati finito E={0,1,...,M} e tassi di nascita λ k=(M-k)λ,
0≤k<M, e λk=0 per k≥M e tassi di morte µ k= µ, k ≥1. La condizione di stazionarietà è
certamente verificata, poiché il processo è finito e irriducibile e la distribuzione
stazionaria del numero di utenti nel sistema, dalle formule (2.16) e (2.17), può essere
riscritta come:
k
πk = π 0 ρ
M!
(M-k)!
M
π0=
∑ρ
k=0
k
0≤k<M
πk = 0
k ≥M
-1
M!
(M-k)!
dove ρ = λ / µ.
Altri casi particolari di sistemi di tipo M/M/1 in cui si considerano combinazioni
delle variazioni del numero di serventi, della memoria e della popolazione finita
possono essere risolti seguendo lo stesso approccio, definendo opportunamente il
relativo processo di nascita e morte. Tali combinazioni forniscono uno strumento per
definire modelli più adeguati a rappresentare sistemi con particolari caratteristiche
[KLE 75].
3.3 Modelli basilari di code: il sistema M/G/1
S. Balsamo
- 52 -
Un altro classico modello di teoria delle code, utile per rappresentare un sistema
come una singola risorsa, ma sotto ipotesi più generali rispetto al semplice il modello
M/M/1
è
il
sistema
di
code
1
, che denota un sistema aperto formato da un singolo centro di servizio con
•
distribuzione del tempo di interarrivo esponenziale, di parametro λ,
• tempo di servizio degli utenti indipendente e con identica distribuzione generale
B(t),
• singolo servente.
Denotiamo il valor medio del tempo servizio con µ= E[B], e il relativo coefficiente di
variazione con CB = Var[B] / E[B].
Per questo modello, il processo stocastico {q(t) | t ≥ 0} dove q(t) denota il numero di
utenti presenti nel sistema al tempo t non è Markoviano, poiché la distribuzione del
tempo di servizio non ha la proprietà di assenza di memoria. Per poter descrivere
l’evoluzione del processo occorre considerare anche il tempo di servizio residuo per
l’utente in servizio. Se definiamo X(t) come il tempo di servizio già ricevuto
dall’utente in servizio al tempo t>0, allora il processo stocastico {[q(t),X(t)] | t>0} è
Markoviano a tempo continuo e spazio bidimensionale E={(n,x) | n∈N, x∈R0+}.
Sfortunatamente tale processo Markoviano è piuttosto complesso da analizzare.
L’analisi del sistema M/G/1 può essere ricondotta a quella di un processo stocastico
più semplice, considerando la v.c. q(t) ad istanti particolari, ad esempio agli istanti di
partenza di un utente dal sistema. Allora indicando q*n=q(tn), n=1,2,... questi istanti
discreti di tempo, si può mostrare [KLE 75] che il processo stocastico {q*n | n=1,2...}
è Markoviano a tempo discreto e spazio discreto E=N. Tale processo è anche detto
catena di Markov immersa nel processo stocastico (non-Markoviano) {q(t) | t≥0}.
Con questa tecnica si studia il p.s. non Markoviano riportandolo ad un p.s.
Markoviano, e la soluzione stazionaria del primo processo è ottenuta dalla soluzione
stazionaria del secondo, ovvero:
lim t→∞ Prob{q(t) = k} = lim n→∞ Prob{q*n = k}.
Utilizzando questo approccio si ricava [KLE 75] la z-trasformata (o funzione
generatrice) G(z), della distribuzione di probabilità stazionaria del processo immerso,
in funzione di ρ=λ/µ e in funzione della trasformata di Laplace della distribuzione del
tempo di servizio B(t), denotata da LB(s), s∈C, come segue:
G(z) =
LB(λ−λz) (1-z) (1-ρ)
LB(λ−λz) - z
S. Balsamo
- 53 -
da cui è possibile, tramite le regole di trasformazione inversa, ricavare la distribuzione
di probabilità stazionaria e i suoi momenti. Il valor medio del numero di utenti nel
sistema si ottiene come N=limz→1 G'(z), da cui:
2
N= ρ+
2
ρ (1 + C B )
(3.21)
2(1-ρ)
nota come formula di Khintchine-Pollaczek [KLE 75].
Tale espressione è applicabile a sistemi M/G/1 con una qualunque disciplina di
servizio che sia indipendente dal tempo di servizio e senza prelazione, quali ad
esempio FIFO, LIFO, Random e a priorità astratta. Notiamo che N è proporzionale al
coefficiente di variazione del tempo di servizio ovvero dipende soltanto dai primi due
momenti della distribuzione e non da momenti di ordine superiore. Ciò significa che
due sistemi M/G/1 con diverse distribuzioni di servizio, ma con ugual coefficiente di
variazione, si comportano in modo identico, in termini di numero medio di utenti nel
sistema. Inoltre N è direttamente proporzionale alla varianza del tempo di servizio, per
cui i sistemi con distribuzioni del tempo di servizio più "sparse", ovvero con elevata
varianza, sono più congestionati di quelli con varianza limitata.
Nella equazione (3.21) il primo termine al membro destro, ρ, rappresenta il numero
medio di utenti in servizio, mentre il secondo termine è W, il numero medio di utenti
in coda in attesa di ricevere servizio.
Esempio. Consideriamo il caso particolare del sistema M/D/1 con
distribuzione del tempo di servizio deterministica (G=D), che per
definizione ha varianza nulla, ovvero B(t) = E[B] = 1/µ, t≥0, Var[B]=0, da
cui CB= 0. La formula (3.21) si semplifica come segue
N= ρ+
ρ
2
(3.22).
2(1-ρ)
Esempio. Consideriamo la distribuzione di servizio esponenziale (G=M) per
cui B(t)=1-e-µt , t≥0, E[B] = (Var[B])1/2 =1/µ e con C B= 1, ritroviamo il
sistema M/M/1 e dalla (3.21) ritroviamo l’espressione (3.8): N = ρ / (1−ρ).
Confrontando i sistemi M/D/1 ed M/M/1 si osserva che passando dal sistema con
coefficiente di variazione CB=0 (M/D/1) al sistema con CB=1 (M/M/1) il numero
medio di utenti in attesa W raddoppia, infatti, dalle formule (3.22) e (3.9) si ricava
WM/D/1= ρ 2 / 2(1−ρ) e WM/M/1= ρ 2 / (1−ρ).
S. Balsamo
- 54 -
Il tempo medio di risposta di un utente nel sistema si ottiene applicando il teorema
di Little, N = λ R, dove N è definito della formula (3.21). Analogamente il tempo
medio di attesa in coda si ottiene dalla relazione W = λ Tw, dove W = N-ρ.
Come già per il sistema M/M/1, anche per il sistema M/G/1 se il sistema è
congestionato, ovvero se ρ=1, gli indici medi N, W, R e T w tendono a crescere senza
limite.
3.4 Discipline a priorità
Le discipline a priorità determinano l’ordine in cui gli utenti vengono serviti in
base a priorità fisse loro assegnate. Le discipline a priorità possono essere con
prelazione e senza prelazione.
Non presentiamo una trattazione dettagliata delle discipline a priorità, ma solo
alcuni risultati, come riportati in [IAZ 78]. Si veda anche [KIN 90, LAV 83].
In un sistema senza prelazione la regola di priorità viene applicata solo quando deve
essere assegnato un nuovo utente al servente dopo un periodo di inattività oppure al
termine del servizio di un utente. Il servizio in corso non viene mai interrotto.
D’altro canto in un sistema a prelazione un utente che ha una priorità più alta di quella
dell'utente attualmente in esecuzione può interrompere il servizio in corso e
cominciare
λ
λ
1
1
2
2
S
λ
r
r
Fig. 3.6. - Sistema a coda singola con coda a disciplina di priorità il proprio servizio. In un sistema a priorità con prelazione gli utenti con priorità più
alta non sono influenzati dalla presenza di quelli con minor priorità, mentre al
contrario ciò avviene in un sistema senza prelazione.
Consideriamo dapprima le discipline prioritarie senza prelazione.
S. Balsamo
- 55 -
Consideriamo il caso di priorità astratta senza prelazione (PASP) per un sistema
con servente singolo, come illustrato in Fig. 3.6.
Consideriamo r classi di priorità dove la prima classe ha massima priorità.
All’interno di ogni classe viene utilizzata la disciplina FIFO.
Un arrivo di classe i viene servito se le code 1, 2, ..., i-1 sono vuote, e un arrivo di
classe i non interrompe il servizio in corso.
Definiamo i parametri relativi alla classe i, 1≤i≤r; sia λi la frequenza di arrivi, t si la
variabile casuale tempo di servizio, E[tsi] = 1/µi la sua media, Var[t si] la varianza e ρ i
= λ i/µi l’utilizzazione.
I valori medi complessivi E[w] ed E[tw] vengono calcolati in base al teorema di
Khintchine-Pollaczek, cioè il tempo medio di attesa su tutte le classi se per ogni i
valgono le seguenti relazioni: λ=λ i, E[ts]=E[tsi], Var[ts] Var[tsi], 1≤i≤r.
Il tempo medio di attesa di un utente appartenente ad una classe k, è denotato da
E[twk]. Esso dipende da tre fattori: il primo è il tempo medio necessario a completare
il servizio corrente, il secondo è il tempo medio necessario per servire gli utenti già
presenti nelle code a maggior priorità 1, 2,..., k-1, ed il terzo è il tempo medio
necessario a servire gli utenti nelle classi 1, 2, ..., k arrivati prima che inizi il servizio.
In altri termini si può scrivere:
1 r
λ i E[t2s ]
∑
i
2 i =1
E[t w k ] =
.
k−1
k
[1− ∑ ρ i ] [1− ∑ ρ i ]
i =1
i=1
Di conseguenza è facile verificare che se consideriamo due classi di priorità i e i+1,
vale la seguente relazione: E[t wi]≤E[twi+1], ovvero la classe a maggior priorità ha un
tempo di attesa minore.
Consideriamo ora una disciplina a priorità sul tempo senza prelazione (PTSP),
ovvero gli utenti che richiediono un tempo di servizio più breve hanno maggior
priorità. In altri termini se i<j allora E[tsi] ≤ E[tsj], per 1≤i,j≤ r.
Sia ts∈[0, D] e fissiamo 0=d0 < d1 < d2...< d r=D. Allora definiamo l’utent di classe i
se il tempo di servizio da lui richiesto è t s∈[d i-1, di]. In ogni classe la disciplina di
servizio è FIFO. Si può dimostrare che il tempo medio di attesa complessivo migliora
rispetto alla disciplina PASP, cioè vale:
E[tw]PTSP ≤ E[tw]PASP
S. Balsamo
- 56 -
e E[tw]PTSP si può calcolare nel modo seguente:
E[t w ]PTSP =
λ E[t2s ] r
∑
2
j=1
B(d j ) − B(d j−1 )
d j−1
[1− λ
∫
0
dj
t dB(t) ] [1 − λ ∫ t dB(t) ]
0
dove B(t) è la distribuzione cumulativa di ts.
Aumentando il numero di classi facendo sì che ogni classe contenga al più un
utente, si definisce la disciplina SPTF (Shortest Processing Time First) dove ha
priorità massima il job che richiede minor tempo di servizio. Il tempo medio di attesa
di un utente può essere calcolato come:
λ E[t 2s ]
E[t w ]SPTF =
2
∞
∫
ts =0 [1−
dB(t s )
ts
λ ∫ t dB(t) ]2
0
Fra le discipline a priorità senza prelazione SPTF è ottima in termini di tempo medio
di attesa, ovvero:
E[tw]SPTF ≤E[tw]PTSP ≤ E[tw]PASP.
Studiamo ora le discipline prioritarie con prelazione.
Nella disciplina a priorità astratta con prelazione (PACP) un utente in arrivo di
classe i interrompe il servizio se l’utente attualmente in servizio è di classe i+1, ..., r.
Quindi un utente di classe i in servizio è interrompibile da utenti di classe 1, 2, ..., i-1.
Il servizio interrotto può essere ripreso dal punto in cui è stato interrotto (disciplina
senza perdita) oppure deve essere reiniziato (disciplina con perdita). Il servizio senza
perdita è meno congestionato del servizio con perdita.
Esempi. Una disciplina a prelazione con perdita si può osservare in un
sistema di trasmissione in cui il servizio (trasmissione) eventualmente
interrotto è completamente perso e deve essere completamente rieseguito.
Una disciplina a prelazione senza perdita si osserva, per esempio, in un
sistema operativo nello scheduling di processori là dove i programmi
interrotti riprendono l’esecuzione (servizio) dal punto in cui erano stati
interrotti.
Rispetto alle discipline prioritarie senza prelazione valgono le seguenti relazioni
per ogni classe k:
S. Balsamo
- 57 -
E[twk] PACP ≤ E[twk] PASP
E[tsk] PACP ≥E[tsk] PASP.
In altri termini per le discipline con prelazione il tempo medio di attesa per classe
migliora (a causa della prelazione) mentre il tempo medio di servizio peggiora (per
l’interruzione del servizio).
Per gli utenti di classe k, 2≤k≤r il tempo medio di risposta è calcolabile come:
E[t q k ] =
1 k
λ i E[t2s ]
∑
i
2 i =1
k−1
k
[1− ∑ ρ i ] [1− ∑ ρ i ]
i =1
+
E[t s ]
k
k−1
1−
i=1
∑ ρi
i=1
mentre per gli utenti della classe 1 a priorità massima si ha:
E[t q1 ] =
λ1E[t 2s ]
1
2 (1 − ρ 1 )
+ E[t s1 ].
Se la priorità è indipendente dal tempo di servizio vale il teorema di KhintchinePollaczek. D’altra parte il tempo di permanenza globale degli utenti nel sistema è
minimizzato dalle discipline a priorità basate sul tempo di servizio.
Una disciplina a priorità detta a semi prelazione è basata sul tempo rimanente di
servizio richiesto. In tal caso un utente dinamicamente cambia classe di priorità al
passare del tempo. Tale disciplina è chiamata SRPTF (Shortest Remaining Processing
Time First). Le classi di priorità in tal caso sono basate sul tempo di servizio residuo.
Un utente appartiene alla classe i se il suo tempo corrente di servizio residuo t ∈ [di-1,
di], 1≤i≤r.
Riassumendo, per il tempo di attesa globale valgono le seguenti relazioni:
E[tw] SRPTF ≤ E[tw] SPTF ≤ E[tw] PTSP ≤ E[tw] PASP ≤ E[tw] FIFO.
Notiamo che le discipline a priorità, anche molto semplici, forniscono risultati
migliori in termini di tempo di attesa globale rispetto a discipline senza priorità. In
particolare tale miglioramento diventa sempre più evidente all’aumentare della
congestione nei sistemi [LAV 83].
S. Balsamo
- 58 -
3.5 Influenza dei fattori di scala
L’analisi delle prestazioni di sistemi basata sui modelli basilari di code introdotti
in questo capitolo ci permette di definire alcune semplici relazioni che legano gli
indici di prestazioni di diversi sistemi al variare di alcuni parametri. Consideriamo il
tasso di arrivo, il numero di serventi e la velocità di servizio. Confrontiamo diversi
sistemi a coda in termini di indici medi di prestazione ed in particolare tempo medio
di attesa e di risposta, facendo variare i parametri di un fattore di scala a>0. Tali
sistemi sono stati confrontati in [IAZ 78, LAV 83].
Sia C=1/µ la velocità del servente, espressa in operazioni al secondo e assumendo
che la domanda di servizio sia unitaria, esso coincide con il tempo medio di servizio.
λ è il numero medio di richieste in arrivo al secondo.
Confrontiamo le seguenti cinque configurazioni di sistemi rappresentate da cinque
modelli che hanno identica utilizzazione data da ρ = λ /µ.
(I)
(II)
(III)
(IV)
(V)
un sistema con tasso di arrivo λ, m serventi ognuno a velocità C/m
un sistema con tasso di arrivo λ, un servente a velocità C
un sistema con tasso di arrivo aλ, a serventi ognuno a velocità C
un sistema con tasso di arrivo aλ, m serventi ognuno a velocità aC/m
un sistema con tasso di arrivo aλ, un servente a velocità aC.
Adottiamo la seguente notazione per indicare gli indici medi di prestazione di un
sistema con tasso di arrivo λ, m serventi e velocità totale C (somma di tutte le
velocità):
E[tq] = R(m, λ, C)
E[tw] = Tw(m, λ, C).
Il confronto fra i sistemi a coda si basa sui modelli di tipo M/M/1 e M/M/m,
facendo riferimento alle formule (3.10), (3.11) e (3.19) e (3.20), rispettivamente per il
tempo medio di risposta e di attesa.
Confrontando i sistemi (I) e (II) che corrispondono, sotto l'ipotesi di
esponenzialità rispettivamente al sistema M/M/m con parametri λ, m e µ/m ed al
sistema M/M/1 con parametri λ e µ. Dalle rispettive formule per i tempi medi di
attesa si ottiene facilmente la seguente disequazione:
Tw(1, λ, C)≥ T w(m, λ, C)
mentre per il tempo medio di risposta:
S. Balsamo
- 59 -
(3.23)
R(1, λ, C) ≤ R(m, λ, C)
(3.24).
Notare che tale disequazione tra i tempi di risposta è opposta a quella che
intercorre tra i tempi di attesa (3.23). Questo risultato mostra l’importanza della scelta
dell’indice di riferimento nella valutazione delle prestazioni di un sistema.
Se la figura di merito è il tempo medio di attesa (Tw) allora i sistemi con potenza
ripartita tra più serventi sono superiori a quelli con potenza concentrata, mentre se il
tempo medio di risposta (R) è l'indice di riferimento allora si ha la conclusione
opposta.
Confrontiamo i sistemi (II) e (III) che corrispondono, sotto l'ipotesi di
esponenzialità, rispettivamente al sistema M/M/1 con parametri λ e µ ed al sistema
M/M/m con parametri aλ, m=a e µ. Sulla base della relazione (3.23), osservando che
nei due sistemi i serventi hanno lo stesso tempo di servizio 1/µ, possiamo subito
scrivere:
R(1, λ, C) ≥ R(a, aλ, aC)
(3.25).
Ciò significa che un aumento dello stesso fattore a del tasso di arrivo, del numero
di serventi, e della potenza (velocità di servizio) totale del sistema porta ad un
miglioramento delle prestazioni in termini di tempo medio di risposta. La
diminuzione del valore di tale indice nel sistema (II) si ottiene applicando le formule
(3.10) e (3.19) con gli opportuni parametri.
Confrontiamo infine i sistemi (I) ed (IV) oppure (II) ed (V) aventi la medesima
struttura e che si differenziano per un aumento simultaneo dello stesso fattore di scala
a del tasso di arrivo e della velocità di servizio. Sulla base delle relazioni sopra citate
possiamo scrivere:
R(m, aλ, aC) = 1/a R(m, λ, C)
Tw(m, aλ, aC) = 1/a Tw(m, λ, C)
(3.26)
(3.27).
Ciò significa che aumentando contemporaneamente i parametri tasso di arrivo e di
servizio dello stesso fattore si osserva una riduzione proporzionale dei tempi medi di
attesa e di servizio, quindi i sistemi (IV) e (V) sono da preferire rispetto ai sistemi (I)
e (II), rispettivamente. Notiamo però che i sistemi confrontati hanno identiche
prestazioni per quanto riguarda gli indici medi E[q] ed E[w]. Infatti osservando che il
rapporto fra i throughput dei due sistemi confrontati è proprio il fattore di scala a ed
applicando il teorema di Little, dalle relazioni (3.26) e (3.27) si ottiene la relazione di
S. Balsamo
- 60 -
uguaglianza di tali indici. Ovvero un aumento dello stesso fattore di scala dei
parametri λ e C non porta ad un miglioramento delle prestazioni in termini di numero
medio di utenti nel sistema ed in coda.
Le relazioni (3.23) - (3.27) si mantengono anche per il caso M/G/m e sono
sensibili alla disciplina di servizio.
Per sistemi di tipo G/G/m, invece la relazione (3.24) vale se C[ts]≤1, ad esempio
nel caso di distribuzioni esponenziali, erlangiane e deterministiche, mentre la formula
(3.25) è sempre applicabile.
Esempio. Confrontiamo le due seguenti configurazioni di un sistema di
comunicazione: una linea ad alta velocità per la trasmissione di messaggi o
un insieme di m linee parallele identiche più lente ognuna con velocità pari
a (1/m)-simo di quella della linea ad alta velocità. Dalla formula (3.24)
segue che la scelta migliore è la linea ad alta velocità.
Esempio. In un sistema di comunicazione con m linee parallele identiche
per la trasmissione di messaggi confrontiamo la configurazione del sistema
in cui vi è un singolo buffer per i messaggi in attesa condiviso tra le m linee
(scheduling centralizzato) o un buffer per ogni linea (scheduling
distribuito). Segue dalla formula (3.25) che la configurazione con un
singolo buffer condiviso è migliore in termini di tempo medio di risposta
del sistema.
S. Balsamo
- 61 -