Capitolo 3 - Modelli a singola coda In questo capitolo presentiamo i
by user
Comments
Transcript
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 -