Una coda, o fila di attesa utenti serventi...Teoria delle Code (Sistemi di Flusso, di Servizio, o...

Università di Roma Tor Vergata AA 2012/13 Corso di Teoria dei Fenomeni Aleatori

1

Teoria delle File di Attesa

• Una coda, o fila di attesa, si forma quando degli utenti

attendono di essere serviti da uno o più serventi.

Esempi:

• Studenti agli sportelli della segreteria

• Utenti di un centro di calcolo

• Programmi eseguiti in multiprogrammazione

• Dati che devono essere trasmessi da un satellite.


2

Sistemi di Servizio

1

2

N

Capacità =K

Stazione di servizio

Coda

12

S

Sorgenti di traffico

Serventi

Strutture di un sistema di servizio


3

Sistemi di Servizio In un sistema di servizio in generale risultano aleatori:

• Gli istanti di tempo in cui si generano le richieste di

servizio.

In questo caso si ricorrere ad una descrizione statistica

dei tempi di interarrivo delle richieste oppure del

numero delle richieste in un certo intervallo di tempo.

• La durata di ogni servizio.


4

Teoria delle Code (Sistemi di Flusso, di Servizio, o “Queuing Systems”; File di Attesa)

Un punto di Poisson può rappresentare l’arrivo di un utente (persona ad uno

sportello, richiesta di collegamento ad un centralino telefonico, pacchetto dati ad

uno switch…) con assegnata intensità (o “frequenza di arrivo”) indicata con :

valore atteso del numero di arrivi in Il tempo di interarrivo ha densità di probabilità che nel caso markoviano è

esponenziale con parametro :

Δ

τt

t


5


SERVIZIOUtenti Utentiserviti

Il tempo di servizio può essere supposto con distribuzione esponenziale

(caso Markoviano) di intensità :

Il tempo totale “speso” nel sistema è e dipende da λ, da µ e dalle leggi

di arrivo e di servizio.


6


Per definizione, il numero medio di arrivi per unità di tempo è λ ed il numero

medio di servizi per unità di tempo è µ .

tempo

Utenti

0

1

5

10

n t( )

n t( ) = numero di utenti nel sistema

: arrivi: servizi


7

Sistemi di Servizio Il numero n di utenti nel sistema ad un certo istante è una

variabile aleatoria che dipende:

• Dalla statistica degli arrivi;

• Dalla statistica del tempo di servizio;

• Dalle condizioni iniziali.

Un sistema di servizio può essere trattato tramite la teoria

dei processi di nascita e di morte.


8

Processi di Nascita e Morte Sono processi di Markov in cui sono permesse solo le transizioni tra

stati contigui: , , .

j - 1 j + 1j

Qui interessa il caso tempo-continuo con transizioni permesse solo

da/a stati contigui: da a 1 (nascita) oppure da a (morte).


9

Processi di Nascita e Morte

i - 1 i + 1i

morte

nascita

Tasso di nascite per popolazione di dimensione i:

(analoga-mente per ).

e dipendono dallo stato ma non dal tempo catena di Markov

omogenea.


10

Sistemi di Servizio Un sistema di servizio è definito da:

• Il numero S delle sorgenti che generano richieste di

servizio.

• La statistica delle richieste di servizio.

• La capacita K della coda (massimo numero di richieste

che possono essere messe in attesa).

• La modalità di gestione della file d’attesa.

• Il numero N dei serventi.

• La statistica della durata dei servizi.


11

Sistemi di Servizio

Nella pratica S, K ed N sono finiti, ma dai casi limite per:

S , K , N→∞ →∞ →∞

risultano modelli semplificati che sono di particolare utilità in

alcune applicazioni.


12

Classificazione dei Sistemi di Servizio

• Sistemi a pura perdita: 0

Una richiesta di servizio viene soddisfatta senza attesa se c’è un

servente libero, altrimenti viene rifiutata.

• Sistemi a pura attesa: S K N≤ +

Tutte le richieste vengono soddisfatte.

• Sistemi ad attesa con perdite: S N K> +


13

Descrizione Sintetica di un Sistema di Servizio

Notazione di Kendall, costituita da 5 simboli:

1 2A / A / N / K / S in cui

• 1A definisce la distribuzione dei tempi di interarrivo;

• 2A definisce la distribuzione dei tempi di servizio;

• N numero di serventi;

• K capacità della coda;

• S numero di sorgenti.


14

Descrizione Sintetica di un Sistema di Servizio

Per 1A ed 2A i simboli più usati sono i seguenti: • M ~ Esponenziale (da Markoviana: senza memoria, si

vedano le proprietà del processo di Poisson)

• mE ~ Erlangiana di ordine m

• mH ~ Iperesponenziale di ordine m

• D ~ Deterministica (costante)

• G ~ Generale (descritta dal solo valore medio)

Se K ed S non figurano, si intende che essi sono di valore infinito.


15

Modalità di Gestione della File di Attesa I casi più frequenti sono i seguenti:

• FIFO (First In First Out) ovvero FCFS (First Come First

Served)

• LIFO (Last In First Out) ovvero LCFS (Last Come First

Served)

• SJF (Shortest Job First)

• LJF (Largest Job First)


16


• Nel nostro caso la grandezza di interesse è il numero di

utenti presenti (o perché in coda o perché vengono

serviti) nel sistema di servizio, che costituiscono il valore

del processo, denominato stato del processo.

• Indichiamo con ( )X t il valore (stato) del processo

all’istante t.

• ( )X t è un intero non negativo.


17

Proprietà dei Processi di Nascita e Morte

• ( )X t è un processo di Markov del primo ordine, cioè

gode della proprietà di assenza di memoria.

• La probabilità che si verificano nascite o morti a gruppi:

( ) ( ){ } ( )P X t h j X t i o h j i 2+ = = = − ≥

con h intervallo di durata “molto piccola”, è un

infinitesimo, ( )o h , di ordine superiore ad h.


18

Proprietà dei Processi di Nascita e Morte

• La probabilità che si verifichi una nascita:

( ) ( ){ } ( )iP X t h i 1 X t i h o h + = + = = λ ⋅ +

con h intervallo di durata “molto piccola”, dipende dallo

stato attuale del processo (cioè da i) ed è proporzionale

( iλ ) alla durata dell’intervallo h.


19

Proprietà dei Processi di Nascita e Morte • La probabilità che si verifichi una morte

( ) ( ){ } ( )iP X t h i 1 X t i h o h + = − = = μ ⋅ +

con h intervallo di durata “molto piccola”, dipende dallo stato

attuale del processo ed è proporzionale (con coefficiente di

proporzionalità iμ generalmente diverso da quello delle

nascite iλ ) alla durata dell’intervallo.

• I parametri iλ e iμ sono dette rispettivamente frequenze di

nascita e di morte.


20

Processi di Nascita e Morte Si possono considerare i seguenti eventi:

• { }A Avviene una Nascita in un intervallo infinitesimo=

( )X t i 1= − e ( )X t dt i+ =

(è possibile solo se i 1≥ )

• { }B Avviene una Morte in un intervallo infinitesimo=

( )X t i 1= + e ( )X t dt i+ =

• { }C Non Avvengono né Nascite né Morti=

( ) ( )X t dt X t i+ = =


21

Processi di Nascita e Morte Per le proprietà dei processi di nascita e morte si ha:

(trascurando gli infinitesimi di ordine superiore)

{ }

{ }

{ } ( )( ) ( )

i 1

i 1

i i i i

P A dt

P B dt

P C 1 dt 1 dt 1 dt

−

+

= λ

= μ

= − λ −μ ≅ − λ +μ

Per il teorema della probabilità totale, la probabilità che il

processo abbia valore i all’istante t dt+ è allora:


22

Processi di Nascita e Morte ( ){ }

( ){ } { } ( ){ } { } ( ){ } { }

( ){ } ( ){ } ( ){ } ( )i 1 i 1 i i

P X t dt i

P X t i 1 P A P X t i 1 P B P X t i P C

P X t i 1 dt P X t i 1 dt P X t i 1 dt− +

+ = =

= = − + = + + = =

= = − + = + + = − +⎡ ⎤⎣ ⎦λ μ λ μ

Questa espressione si può opportunamente riscrivere sotto

forma di equazione differenziale:

( ){ } ( ){ } ( ){ }

( ){ } ( ){ } ( ){ }( )i 1 i 1 i i

dP X t i P X t dt i P X t idt dt

P X t i 1 P X t i 1 P X t i− +

= + = − == =

= = − λ + = + μ − = λ +μ(1)


23


Nel caso particolare in cui i 0= si ha: 1 0−λ = e 0 0μ =

( ){ } ( ){ } ( ){ }1 0dP X t 0

P X t 1 P X t 0dt

== = ⋅μ − = ⋅λ (2)

La soluzione delle (1) e (2) non è in generale agevole,

inoltre occorre conoscere la distribuzione di probabilità degli

stati del processo a regime, cioè in condizioni di

stazionarietà. Questa distribuzione si ottiene ponendo:

( ){ } ( ){ }dP X t i dP X t 00 0

dt dt= =

= =


24


Da ( ){ }dP X t 0

0dt

== si ottiene:

( ){ } ( ){ }0

1P X t 1 P X t 0λ

= = =μ (3)

Dalla (1) per i = 1 si ha:

( ){ } ( ){ } ( ){ }( )0 2 1 1P X t 0 P X t 2 P X t 1= λ + = μ = = λ +μ

sostituendo la (3) in quest’ultima equazione, si ottiene:

( ){ } ( ){ } ( ){ }0 1 1

1 2 2P X t 2 P X t 0 P X t 1λ ⋅λ λ

= = = = =μ ⋅μ μ


25

Processi di Nascita e Morte Ripetendo la procedura per i = 2 si ottiene:

( ){ } ( ){ } ( ){ }0 1 2 2

1 2 3 3P X t 3 P X t 0 P X t 2λ ⋅λ ⋅λ λ

= = = = = =μ ⋅μ ⋅μ μ

In generale risulta:

( ){ } ( ){ }n 1

i

i 1i 0

P X t n P X t 0−

+=

λ= = =

μ∏ (4)

oppure

( ){ } ( ){ }n n 1P X t n P X t n 1 −= ⋅μ = = − ⋅λ (5)


26

Processi di Nascita e Morte La

( ){ } ( ){ }n 1

i

i 1i 0

P X t n P X t 0−

+=

λ= = =

μ∏

non permette ancora di ricavare le probabilità degli stati del

processo in quanto dipende da ( ){ }P X t 0= che è ancora

incognita.


27

Processi di Nascita e Morte Utilizzando la condizione che la somma delle probabilità di

tutti gli stati deve esse unitaria e ricordando che il numero

massimo di utenti nel sistema è la somma del numero di

serventi N e del numero K di posti in attesa:

( ){ }

( ){ } ( ){ }

N K

i 0

N K

i 1

P X t i 1

P X t 0 P X t i 1

+

=

+

=

= =

= + = =

∑

∑

ed utilizzando la (4), si ottiene:


28


( ){ } ( ){ }

( ){ }

( ){ }

N K i 1j

j 1i 1 j 0

N K i 1j

j 1i 1 j 0

N K i 1j

j 1i 1 j 0

P X t 0 P X t 0 1

P X t 0 1 1

1P X t 01

+ −

+= =

+ −

+= =

+ −

+= =

λ= + = ⋅ =

μ

⎡ ⎤λ⎢ ⎥= ⋅ + =

μ⎢ ⎥⎣ ⎦

= =λ

+μ

∑ ∏

∑∏

∑∏


29

Processi di Nascita e Morte Affinché esista una distribuzione di probabilità degli stati a

regime ( ){ }( )P X t 0 0= ≠ deve essere verificata:

N K i 1j

j 1i 1 j 0

+ −

+= =

λ< ∞

μ∑∏ (condizione di stabilità) (7)

altrimenti sia lo stato 0 che tutti gli altri stati avrebbero

probabilità nulla.

La condizione di stabilità è certamente soddisfatta se il

numero di stati del sistema (e quindi N + K) è finito.


30

Rappresentazione di un Processo di Nascita e Morte Grafo di transizione degli stati

0

0

1

1

1

2

2

23

N+ K

N+ K

N+ K-1

Le equazioni:

( ){ } ( ){ }n n 1P X t n P X t n 1 −= ⋅μ = = − ⋅λ

vengono dette equazioni di bilanciamento.


31

Fattore di Utilizzazione

Si definisce fattore di utilizzazione ρ la probabilità di utilizzo

e quindi (supponendo il processo stazionario ed ergodico) il

valore atteso della frazione di tempo in cui il sistema è

utilizzato.


32

Fattore di Utilizzazione Dall'espressione:

( ){ }0 N K i 1j

j 1i 1 j 0

1P P X t 01

+ −

+= =

= = =λ

+μ∑∏

si ricava: n 1

i

i 1n 1 i 0n 1

i

i 1n 1 i 0

1

∞ −

+= =∞ −

+= =

λμ

ρ =λ

+μ

∑∏

∑∏ (8)


33

Code M/M/1 Si consideri il caso stazionario di:

• arrivi e partenze Markoviane, parametri fissi;

• un solo servente;

• la coda può essere comunque lunga.

0 1 2 n

Grafo di transizione degli stati per la coda M/M/1


34

Code M/M/1

Si ha quindi: nλ = λ , nμ = μ per n 1,2,3,...=

Inserendo questi valori nella (7), si ottiene: nn 1

i

i 1n 1 i 0 n 11

∞ − ∞

+= = =

⎛ ⎞λ λ λ μ= =⎜ ⎟μ μ − λ μ⎝ ⎠∑∏ ∑ 1λ

<μ

per λ > μ la serie diverge.

Per il fattore di utilizzazione si ha:

0 P 1λ λρ = = −

μ μ


35

Code M/M/1 Ricordando l’espressione

( ){ } ( ){ }n 1 n 1

i in 0

i 1 i 1i 0 i 0

P P X t n P X t 0 P− −

+ += =

λ λ= = = = =

μ μ∏ ∏

noto nel caso M/M/1 si ottiene una

distribuzione Geometrica di parametro ρ:

( )n

nn 0P P 1⎛ ⎞λ= = −ρ ρ⎜ ⎟μ⎝ ⎠

Grandi valori di n (cioè elevate occupazioni) sono più

probabili per ρ vicino all’unità piuttosto che per ρ bassi.

0P 1 1λ= − = −ρ

μ


36

Code M/M/1

Distribuzione stazionaria del numero di utenti in un sistema

M/M/1


37

Code M/M/1 La probabilità che l’unico servente sia occupato è:

( ){ } ( ){ } ( )0P X t 0 1 P X t 0 1 P 1 1> = − = = − = − −ρ = ρ

Il numero medio di utenti nel sistema è:

[ ] ( ) nn

n 0 n 0

E n n P 1 n1

∞ ∞

= =

ρ= ⋅ = −ρ ⋅ρ =

−ρ∑ ∑

cioè tende a infinito per 1ρ→ .

Se si vuole un elevato fattore di utilizzazione occorre

accettare una coda alquanto lunga!


38

Code M/M/∞

Si consideri un sistema con un numero illimitato di serventi (N infinito), per cui ogni utente che entra nel sistema trova un servente libero (lunghezza nulla della coda). Siano

nλ = λ , n nμ = ⋅μ per n 1,2,3,...=

0 1 2 n

2 3 n (n+ 1) Grafo di transizione degli stati per la coda M/M/∞


39

Code M/M/∞

Inserendo tali espressioni in n 1

in 0

i 1i 0

P P−

+=

λ=

μ∏ , si ha:

( )

n n

n 0 0n 1

i 0

1 1P P Pn!

i 1−

=

⎛ ⎞ ⎛ ⎞λ λ= =⎜ ⎟ ⎜ ⎟μ μ⎝ ⎠ ⎝ ⎠

+∏ (a)

Dall’espressione generale di

0 i

i 1

1P e11i!

λ−μ

∞

=

= =⎛ ⎞λ

+ ⎜ ⎟μ⎝ ⎠∑ (b)


40

Code M/M/∞ per cui, dalle (a) e (b) si ottiene:

n An

ne eP An! n!

λ−

−μ⎛ ⎞λ= =⎜ ⎟μ⎝ ⎠

(c)

cioè la distribuzione del numero di utenti nel sistema è

Poissoniana di parametro A λ=μ .

• [ ]A E n= coincide col numero di serventi attivi. Nelle ipotesi per cui l’espressione (c) è valida [ ]E n dipende solo dal loro rapporto tra λ e μ.

• A è detto intensità di traffico o brevemente “traffico”.


41

Code M/M/N/∞

Si consideri il caso stazionario con le stesse ipotesi (processi Markoviani) dell’applicazione precedente ma con N serventi. Si ha:

nλ = λ per n 0,1,2,...= nn 0 n NN N n⋅μ < <⎧

μ = ⎨ ⋅μ ≤⎩

perper

0 1 2 n

2 3 N N Grafo di transizione del modello M/M/N/∞


42

Code M/M/N/∞

• Finché ci sono serventi liberi l’utente viene servito immediatamente, viceversa quando le N stazioni di servizio sono occupate l’utente è in coda.

• E' questo il caso di un servizio "con prenotazione".

( )( )

0 K NN 1

K 0

1P1

K ! N ! 1 N

−

=

=λ μ⎛ ⎞λ

+⎜ ⎟μ − λ μ⎝ ⎠∑

n

n 01P Pn!

⎛ ⎞λ= ⎜ ⎟μ⎝ ⎠

per n N≤


43

Code M/M/N/∞ Si può ora calcolare la probabilità *P che gli N serventi siano tutti occupati:

N 1*

nn 0

P 1 P−

=

= −∑

Utilizzando le precedenti espressioni si ricava la “formula C di Erlang”:

( ) ( )

( )( )

( ) ( )( )

N

N*

0 K NN 1

K 0

N ! 1 NN AP C M , PN ! N A

K ! N ! 1 N

−

=

λ μ− λ μ⋅

= λ μ =− λ μ λ μ

+− λ μ∑


44

Code M/M/N/0 Il sistema M/M/N/0 differisce dal precedente perché quando tutti gli N serventi sono occupati l’utente viene rifiutato (caso del servizio telefonico con N linee disponibili in centrale). Il sistema è del tipo "a perdita".

Si ha quindi: n n N

0 n Nλ <⎧

λ = ⎨ ≥⎩

sese n nμ = ⋅μ

0 1 2 N

2 3 N


45

nn 1i

0 0n i 1i 0

1P P n NP n!

0 n N

−

+=

⎧ ⎛ ⎞λ λ= ≤⎪ ⎜ ⎟= μ μ⎨ ⎝ ⎠

⎪>⎩

∏

11 nn 1 Ni

0i 1n 1 i 0 n 1

1P 1 1n!

−−∞ −

+= = =

⎛ ⎞⎛ ⎞ ⎛ ⎞λ λ= + = +⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟μ μ⎝ ⎠⎝ ⎠ ⎝ ⎠

∑∏ ∑

di conseguenza: n

n nN

n 0

1n!P

1n!

=

⎛ ⎞λ⎜ ⎟μ⎝ ⎠=⎛ ⎞λ⎜ ⎟μ⎝ ⎠∑

n N≤


46

Code M/M/N/0 Ponendo n = N si ricava la probabilità che l’utente venga

rifiutato perché gli N serventi sono occupati.

Nell’esempio, la probabilità di trovare “occupato”, è nota

come formula B di Erlang:

( )

N

nN

n 0

1N !B N ,

1n!

=

⎛ ⎞λ⎜ ⎟μ⎝ ⎠λ μ =⎛ ⎞λ⎜ ⎟μ⎝ ⎠∑


47

MISURA DEL TRAFFICO

• Il rapporto coincide con il “traffico”, misurato in Erlang. Nel caso

della telefonia, un utente che è sempre attivo “offre” il traffico di un

Erlang in quanto occupa una linea telefonica il 100 % del tempo.

• Più realisticamente, un utente attivo al 10 % del tempo offre il

traffico di: 0.1 E; dieci di tali utenti offrono il traffico di 1 E.

• Se ad uno sportello arrivano in media 2 persone al minuto e il

tempo medio per svolgere il servizio di sportello è di dodici

secondi, si ha (in ): e che corrisponde a 0.4

Erlang.


48

ESEMPIO

Una centralina telefonica serve un traffico offerto di 5 Erlang (ad esempio, 50

utenti, ciascuno dei quali offre 0.1 E, cioè occupa il sistema al 10 %).

a) Dimensionare il numero di collegamenti tra centralina e utenti in modo che

la probabilità di perdita (di trovare occupato) sia al più l’uno per cento.

Si calcola la formula B per 5 e valori crescenti del numero N di serventi,

cioè di linee.

Per N = 10, B = 1.83·10-2 1 %

Per N = 11, B = 8.29·10-3 1 %

Quindi si sceglie N = 11.


49

ESEMPIO (segue)

b) Calcolare il fattore di utilizzazione di una linea.

Traffico smaltito: .

Fattore di utilizzazione: .

Commento:

Per consentire una buona 0.01 qualità del servizio occorre

utilizzare le linee a meno del 50 %.

Università di Roma Tor Vergata Corso di Teoria dei Fenomeni Aleatori

50

Teoria delle Code – Esercizi

a) Dato un sistema di flusso del tipo M/M/1/1 (esempio: una sala di

lettura con una sola sedia e un posto in attesa) determinare le

probabilità degli stati al variare del tempo medio tra due arrivi e

del tempo medio di permanenza in lettura. Soluzione

0

0

2

2

1

1

1

0 0 00 1 11 1 2

ATTESA LETTURA TOT

Si ha: ,


51

Risolvendo le equazioni:

1

si ottiene

1 1

1


52

1 0.33 0.33 0.33

0.5 0.58 0.28 0.14

0.1 0.9 0.09 0.009

10 0.009 0.09 0.9

Commento: al crescere del rapporto tra durata media della

lettura e tempo medio tra due arrivi il rendimento 1 si

abbassa.


53

b) Come l’esercizio 1, con due serventi (due posti a sedere) e

nessun posto in coda (sistema “a perdita”). Soluzione

0 0 00 1 10 2 2

ATTESA LETTURA TOT

0

0

2

2

1

1

1

Si ha: ,

2


54

cioè

1 2 ; 1 2

2⁄ 1 2


55

1 0.4 0.4 0.2

0.1 0.905 0.09 0.0045

10 0.016 0.154 0.82

Commento: si hanno valori di più alti del caso precedente, in

quanto l’assenza di coda riduce l’efficienza di utilizzazione del

sistema a parità di traffico.


56

Esercizi da svolgere

c) Come il precedente esercizio (b) con un posto in attesa (coda

di capacità 1)

d) Come il precedente esercizio (a)con una coda di capacità

infinita.

Una coda, o fila di attesa utenti serventi...Teoria delle Code (Sistemi di Flusso, di Servizio, o...

Documents

Transcript of Una coda, o fila di attesa utenti serventi...Teoria delle Code (Sistemi di Flusso, di Servizio, o...