Ley de Little
Procesos Estocásticos y Teoría de Filas
Primer Semestre de 2003
Luciano Ahumada Fierro
1
Ley de Little: Introducción

La ley de Little relaciona los valores medios de
tres variables de importancia en un sistema:
– N : Número medio de usuarios en el sistema
– T : Tiempo promedio de un cliente en el sistema
–  : Tasa media de arribo al sistema

En este caso, “sistema” se utiliza en un sentido
amplio, que puede involucrar ya sea la fila y los
servidores, sólo la fila o sólo los servidores.
2
Ley de Little: Introducción
Sistema
Llegadas
()
fila
servidor
Salida
N usuarios
N
es una variable de interés desde el punto de vista del
sistema y permite dimensionar los buffers.
T, el tiempo de retardo, es una variable de interés desde
el punto de vista del usuario, ya que es lo que el debe
esperar en la fila antes de ser atendido.
La ley de Little relaciona estas variables a través de , la
velocidad de entrada al sistema.
3
Ley de Little

Se define :
– (0,t): número de entradas al sistema en el intervalo (0,t)
– (0,t): número de salidas del sistema en el intervalo (0,t)
N(t)
(0,t)
(0,t)
4
Ley de Little

Se define :
– N(t): número de usuarios en el sistema en el instante t

Se observa que N(t)=(0,t)-(0,t)
N(t)
(t)
(t)
ti
Para ti, N(ti) = 3
5
Ley de Little

Además, el área acumulada entre las dos curvas, (0,t) y
(0,t), es una medida del tiempo total que todos los
clientes han permanecido en el sistema en el intervalo de
tiempo [0,t]. Esta cantidad se denomina (0,t).
t
 (0, t )   N (t )dt
(t)
0
N(t)
(t)
(t)

(0,t) tiene unidades de [clientes•segundo]
6
Ley de Little


La cantidad (0,t) es similar al concepto de Horas
Hombre (HH).
Las horas hombre son un cantidad que permite
dimensionar la capacidad de un sistema.
7
Ley de Little

Por ejemplo:
a)
Una oficina dispone de 5 personas, cada una trabaja 8
horas diarias. La capacidad de la oficina es de 5•8 = 40
HH.
b)
La mantención de una maquinaria automática requiere que
un operador manualmente permanezca 10 horas
sustituyendo su función en la producción. Se dice entonces
que la mantención de la máquina requiere de 10 HH.
c)
En el caso de una fila, en un sistema fila-servidor, la
capacidad de la fila está dada por el (t) máximo,
correspondiente al área acumulada entre las curvas de
(0,t) y (0,t), de tal forma que la fila no se revalse.
8
Ley de Little
Se define la tasa de llegada promedio en el
intervalo [0,t] como (0,t) , donde:
 (0, t )
t 
t
(1)
Llegadas y Salidas
10
(0,t)
8
Número de Clientes

6
4
t : Velocidad Media de Llegada
2
0
-2
Tiempo t
9
Ley de Little


Sea T(0,t), el tiempo promedio que permanece un
usuario en el sistema, en el intervalo [0,t].
T(0,t) equivale al tiempo total que permanecen los
usuarios en el sistema dividido por el número de
t
entradas en el intervalo
 (0, t )   N (t )dt
0
(t): número de
clientes que han
estado en el sistema
en [0, t]
(t)
(t) : cantidad
proporcional al
N(t) tiempo acumulado
por todos los
clientes que han
estado en el
sistema.
10
Ley de Little

De acuerdo a las definiciones anteriores, se tiene
que :
 (0, t )
T (0, t ) 
 (0, t )
( 2)
(0, t) : proporcional al tiempo total de todos los clientes que han
permanecido en el sistema en el intevalo[0, t].
(0,t) : número de clientes que han entrado al sistema en el intervalo [0, t].

Por otra parte, se define
N t : número promedio de usuarios en el intervalo (0,t)
11
Ley de Little

puede calcularse como el cuociente entre una
cantidad proporcional al tiempo acumulado que han
estado los clientes en el sistema, (t), y el tiempo t.
Nt
t
Nt

N (t )dt  (t )



0
t
t
(3)
Combinando las ecuaciones (1), (2) y (3) se obtiene
N t   (0, t )T (0, t )
(4)
12
Ley de Little

Asumiendo que el sistema es estable, se cumplen
los siguientes límites:
  lim t
t 
T  lim Tt
t 

Notese que la existencia de estos límites es la
única condición que se ha impuesto al sistema
13
Ley de Little

Si estos límites existen, también existe el límite
para N t . Sea N  lim N t
t 

Entonces se tiene que
N  T
(5)
“Ley de Little”
14
Ley de Little
N  T

Este es el resultado final de la ley de Little, y
establece que el número medio de usuarios en un
sistema, es igual a la tasa media de llegadas al
sistema multiplicado por el tiempo medio de
permanencia de un usuario en el sistema.
15
Ley de Little
N  T




La Ley de Little relaciona una variable temporal (T, tiempo
de retardo) con una variable espacial (N, por ejemplo,
tamaño de un buffer)
N y T se relacionan a través de , velocidad de llegada.
 es en general la variable independiente, “la entrada al
sistema” .
La ley de Little es útil para evaluar el desempeño de un
sistema en términos de su capacidad
16
Ley de Little
N  T



Es importante notar que para la deducción de esta ley,
no se ha hecho ninguna suposición acerca de la
distribución de probabilidad de las llegadas
Es decir, las llegadas pueden tener, una distribución de
Poisson (M), Erlang (Er), determinista (D), llegadas
múltiples, etc...
En otras palabras, se tiene que, según la notación de
Kendall, la ley de Little es válida para una fila con
distribución de llegadas general (G)
17
Ley de Little
N  T
Llegadas y salidas
7
6
usuarios
5
4
3
2
1
0
0
1
2
3
4
5
6
7
8
tiempo
Arribos deterministas
Arribos aleatorios
distribución cualquiera
En ambos casos, la ley de little se cumple, ya que la
distribución de las llegadas no fue considerada en la
deducción
18
Ley de Little
N  T




Tampoco se ha hecho ninguna suposición acerca de la
distribución de probabilidad del tiempo de atención.
Esta distribución puede ser cualquiera. Según la
notación de Kendall, la ley de Little es válida para una
distribución de tiempo de servicio General (G).
Además, el número de servidores en un sistema también
es arbitrario.
La única condición que se impone es que el factor de
utilización  del sistema sea menor que 1.
19
Ley de Little
Llegadas y salidas
7
7
6
6
5
5
usuarios
usuarios
Llegadas y salidas
4
3
4
3
2
2
1
1
0
0
0
1
2
3
4
5
6
tiempo
Salidas deterministas
7
8
0
1
2
3
4
5
6
7
8
tiempo
Salidas aleatorias,
distribución
cualquiera
En ambos casos, la ley de little se cumple, ya que la
disciplina de atención no fue considerada en la deducción
20
Ley de Little
N  T



Tampoco se ha hecho ninguna suposición acerca
de la disciplina de atención que se esté utilizando.
En particular, la disciplina de atención podría ser
FIFO, LIFO, o con prioridad.
En cualquiera de estos casos, la ley de Little puede
aplicarse, ya que en su deducción no se supuso
ninguna disciplina en particular.
21
Ley de Little
N  T


Es importante dejar en claro que un cambio en la
disciplina de atención produce cambios en los
resultados específicos de N, T y 
Sin embargo, la relación entre las tres variables se
sigue cumpliendo
22
Ley de Little


Por ejemplo, a un sistema llegan tres usuarios. Los tiempos de
servicio para cada uno son t1<t2<t3.
Si se atiende al trabajo más corto primero (asumiendo que en el
instante t todos están presentes) el tiempo de permanencia promedio
será:
t1
t2
t1
t3
t2
t1
T primer
usuario
T segundo
usuario
t3
t1 +t2
t1 +t2 +t3
T tercer
usuario
t1  t1  t 2  t1  t 2  t3
Tc 
3
23
Ley de Little
t1
t2
t1
t3
t2
t1
T primer
usuario
t3
t1 +t2
T segundo
usuario
t1 +t2 +t3
T tercer
usuario
t1  t1  t 2  t1  t 2  t 3
Tc 
3
t1
t1 +t2
Tc
t1 +t2 +t3
24
Ley de Little

En cambio, si se atiende al trabajo más largo primero:
t1
t2
t3
t3
t2
t3
T tercer
usuario
T segundo
usuario
t1
t3 +t2 t3 +t2 +t1
T primer
usuario
t 3  t 3  t 2  t 3  t 2  t1
Tl 
3
25
Ley de Little
t1
t2
t3
t3
t2
t3
T tercer
usuario
T segundo
usuario
t1
t3 +t2 t3 +t2 +t1
T primer
usuario
t 3  t 3  t 2  t 3  t 2  t1
Tl 
3
t3
t3 +t2
t3 +t2 +t1
Tl
26
Ley de Little



Del gráfico anterior claramente Tl es mayor que Tc
En este caso, los valores de los tiempos de
permanencia promedio varían al cambiar la disciplina
de atención
Sin embargo, la ley de Little se cumple en ambos
sistemas
27
Ley de Little



Además, este resultado es válido tanto para el
sistema fila-servidor en su totalidad, como para
alguna de sus partes
Es decir, la ley de Little puede también aplicarse a
los servidores o a la fila por separado.
En el siguiente ejemplo, se parte considerando la
fila y el servidor por separado, para luego ir
escalando el tamaño del objeto modelado hasta un
sistema de gran envergadura. La ley de Little se
cumple en cada uno de los sistemas por separado,
así como en el sistema global
28
Ley de Little
N=T
Nf=fTf
fila
f
NS=STS
Nf
servidor
NS
S
Tf
TS
N usuarios
T tiempo medio de permanencia
29
Ley de Little

En general, para el análisis de un
servidor se tiene que
=S x
servidor
S
Ns    s x
Factor de utilización
Tiempo medio de
servicio
30
Ley de Little
N=T
N1=1T1
sistema
1
servidor
fila
S1
N1 usuarios
T1
N1 usuarios
T1 tiempo medio de permanencia
31
Ley de Little
N=T
N1=1T1
fila
servidor
N3=3T3
1
N1 usuarios
T1

fila
servidor
3
N2=2T2
fila
servidor
N3 usuarios
T3
2
N2 usuarios
T2
N usuarios
T tiempo medio de permanencia
32
Ley de Little
N=T
33
Ley de Little
N=T
Internet
34
Ejemplo M/M/1
N=T

fila

Supongamos que el cliente
“A” llega a una fila donde
existen “k” clientes antes
que él (k-1 en la fila y 1 en el
servidor).

Asumiendo tiempo de
servicio exponencial de
parámetro , es posible
concluir que el tiempo medio
de servicio será 1/
servidor
N usuarios
T
35
Ejemplo M/M/1

Esto significa que el cliente que está siendo servido,
los k-1 clientes esperando en la fila y el Cliente A
tendrán un tiempo de servicio promedio de 1/ cada
uno.

De allí entonces que el tiempo de permanencia
promedio en el sistema del cliente A, condicionado a
que existen k usuarios antes será:
k 1

36
Ejemplo M/M/1

Por lo tanto, la esperanza (valor medio) del tiempo
de permanencia en el sistema (T) será
 k  1
T E

  
1
 E  k  1


E  k   1


1
37
Ejemplo M/M/1

Pero E[k]=N, por lo tanto,
T

1

 N  1
Además, de acuerdo a la Ley de Little
T
N

38
Ejemplo M/M/1

Despejando T, N de ambas ecuaciones se logra:
1
T
 
N

 
Tiempo medio de permanencia en
el sistema
Número medio de usuarios en
el sistema
39
Ejemplo M/M/1

A partir de las ecuaciones anteriores se puede
obtener:
1
1
W

  
NQ 

 

Tiempo medio de permanencia en
la fila
Número medio de usuarios en
la fila
40
Ley de Little: Ejemplos
Análisis de un concentrador
Análisis de un computador de
tiempo compartido
41
Ley de Little: Ejemplos
 Análisis de un Concentrador
TERMINAL
TERMINAL
TERMINAL
CONCENTRADOR
BUFFER
TERMINAL
42
Análisis de un Concentrador


La ocupación promedio de un buffer de un
concentrador de datos puede ser calculada para
diferentes casos.
En este tipo de equipos los paquetes entrantes de
terminales conectados a él son almacenados en
orden de llegada en un buffer, y son entonces leídos
en FIFO sobre un enlace de salida de transmisión.
43
Análisis de un Concentrador
Suponganse las siguientes condiciones:
 10 terminales están conectados al concentrador.
 Cada uno genera, en promedio, un paquete cada 8
segundos (distribuidos exponencialmente)
 Los paquetes tiene un largo promedio de 960 bits
 Se usa una línea de salida de capacidad de 2400 b/s.
– ocupación promedio del Buffer = N = ?
– retardo medio en el sistema
= T =?
– tiempo de espera promedio en la fila = W
=?
44
Análisis de un Concentrador

Modelo :
– Para modelar el Buffer se usará una Fila M/M/1.

Apéndice
Tasa de arribo de paquetes:
– Cada terminal genera paquetes de acuerdo a una
distribución exponencial a una tasa de 1/8 [paquetes /seg]
– La llegada de paquetes al concentrador tendrá también
distribución exponencial, y la tasa de llegada será la suma
de las tasas a la que genera cada terminal, es decir:


 = 10  1 = 1.25  paquetes
seg 
8


45
Análisis de un Concentrador

La tasa de servicio se calcula como:

 = 2400  2.5  paquetes
seg 

960



Por ende, la ocupación media del buffer es:
 1.25
 =
 0.5
 2.5
Entonces, el número medio de usuarios en el sistema
(Buffer y Servidor) es (Fila M/M/1):
N

1 
1
46
Análisis de un Concentrador

Utilizando la Ley de Little, el tiempo medio de cada
usuario en el sistema es:
1
T

 0.8seg 
 1.25
N

El tiempo medio de espera en el buffer es:
W T 
1

 0.4seg 
T’=1/μ
W

T
47
Análisis de un Concentrador





En este ejemplo, se conoce la tasa media de llegada  :
lo que se quiere encontrar es N y T
En una primera aproximación, la ley de Little sólo nos
da la relación entre N y T
Para conocer los valores exactos de N y T se necesita
otro método para despejar alguna de las dos variables
En general, encontrar expresiones para el tiempo de
permanencia en la fila es más difícil
Se utilizan entonces los modelos de teoría de filas
“conocidos”, que permiten encontrar el número de
usuarios en la fila
48
Ley de Little: Ejemplos

Análisis de un computador de tiempo compartido
T1


T2
COMPUTADOR
P
TN
R
Arquitectura del sistema
D
49
Análisis de un computador de tiempo
compartido
Parámetros del Sistema:






N: Número de terminales
R: Tiempo medio de espera en cada terminal
P: Tiempo medio de procesamiento de cada
trabajo.
D: Tiempo medio desde que un trabajo es enviado
al computador hasta que acaba su ejecución.
T=R+D: tiempo medio de un trabajo en el sistema.
: Throughput del sistema
50
Análisis de un computador de tiempo
compartido

Modelado del Problema
TERMINAL
1
A
R
CPU

TERMINAL
2
1/P

B
R
TERMINAL
N
P
R
R
D
T
Time Sharing
51
Análisis de un computador de tiempo
compartido

Condiciones del sistema:

Condición Máxima de Utilización:

Problema:
– N= Constante del sistema
– Siempre existe un usuario con trabajo cuando
otro acaba de ser atendido.
– Encontrar los valores máximos y mínimos de  y
T.
52
Análisis de un computador de tiempo
compartido


Debido a la hipótesis siempre existen N terminales
procesando
Aplicando a Ley de Little entre los puntos (A) y (B)
  N /T
53
Análisis de un computador de tiempo
compartido


Retardo mínimo de un trabajo (procesador
desocupado)
Dmin = P
Retardo máximo de un trabajo ( todos los
terminales han enviado un trabajo al procesador)
Dmax = NP
54
Análisis de un computador de tiempo
compartido

Conclusión:
P  D  NP
Por lo tanto
R + P  T  R + NP
(1)
Aplicando la Ley de Little en (1)
N
N

R  NP
RP

(2)
Debido a que el procesamiento de un trabajo
demora P, se cumple que:
1
(3)

P
55
Análisis de un computador de tiempo
compartido

Combinando (2) y (3), se obtiene:
N
1 N
   min{ ,
}
R  NP
P RP

(4)
Usando la Ley de Little se obtienen los límites de
tiempo para el sistema
max{NP , RP }  T  R  NP
(5)
56
Análisis de un computador de tiempo
compartido
Retardo Máximo y Mínimo del Sistema
T
R+NP:máximo
NP: mínimo
R+P
R
NUMERO DE TERMINALES N
1
57
Análisis de un computador de tiempo
compartido


Al aumentar el número de terminales, el tiempo de
retardo aumenta
El mínimo tiempo de retardo se obtiene para N=1,
lo cual es de esperar por que en este caso el
terminal es atendido de inmediato cuando tiene un
trabajo
58
Análisis de un computador de tiempo
compartido
Throughput Máximo y Mínimo
THROUGHPUT
1/P
1+R/P
NUMERO DE TERMINALES
N
1
N
   min{ ,
}
R  NP
P RP
59
Análisis de un computador de tiempo
compartido




El máximo throughput es alcanzable cuando N es
mayor que 1+R/P
Se observa también que al aumentar el número de
términales, el throughput se acerca con seguridad
al máximo
Esto significa un mejor aprovechamiento de los
recursos
Sin embargo, desde el punto de vista del usuario, el
servicio se degrada debido a que aumenta el
retardo
60
Análisis de un computador de tiempo
compartido




En este ejemplo, no se trata de encontrar
expresiones finales para N, T y 
La idea es caracterizar el desempeño del sistema
(en términos de throughput y retardo) asumiendo
ciertas condiciones de operación
De esta forma se obtienen valores máximos y
mínimos para throughput y retardo en función del
número de terminales
En este caso, sin necesidad de un modelado del
sistema, la Ley de Little provee resultados útiles
61
Apéndices
62
Notación de Kendall para sistemas de filas
Corresponde a un formato abreviado para denotar las características
específicas de un proceso de nacimiento y muerte, como lo muestra la
figura siguiente.
Tiempo entre arribos
G : General
M : Exponencial
Tiempo de servicio
G : General
M : Exponencial
Número de servidores
N : Número finito
Número de fuentes
Infinito
N :Finito
Longitud de la cola
Infinito
L :Finito
1/2/3/4/5
Nota: Normalmente, los infinitos se
omiten y la disciplina de atención es
FIFO
63
Descargar

Ley de Little - WordPress.com