1 ley de little procesos estocásticos y teoría de filas primer semestre de 2003 luciano ahumada...
TRANSCRIPT
![Page 1: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/1.jpg)
1
Ley de Little
Procesos Estocásticos y Teoría de FilasPrimer Semestre de 2003
Luciano Ahumada Fierro
![Page 2: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/2.jpg)
2
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.
![Page 3: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/3.jpg)
3
Ley de Little: Introducción
Llegadas()
Sistema Salidaservidorfila
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.
![Page 4: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/4.jpg)
4
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)
(0,t)
(0,t)
N(t)
![Page 5: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/5.jpg)
5
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)
(t)
(t)
N(t)
ti
Para ti, N(ti) = 3
![Page 6: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/6.jpg)
6
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)
(t)
N(t)(t)
(0,t) tiene unidades de [clientes•segundo]
t
dttNt0
)(),0(
![Page 7: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/7.jpg)
7
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.
Ley de Little
![Page 8: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/8.jpg)
8
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.
![Page 9: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/9.jpg)
9
Ley de Little Se define la tasa de llegada promedio en el
intervalo [0,t] como (0,t) , donde:
)1(),0(
tt
t
Llegadas y Salidas
-2
0
2
4
6
8
10
Tiempo t
Nú
mer
o d
e C
lien
tes
(0,t)
t : Velocidad Media de Llegada
![Page 10: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/10.jpg)
10
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 entradas en el intervalo
(t): número de clientes que han estado en el sistema en [0, t]
(t)
N(t)
(t) : cantidad proporcional al tiempo acumulado por todos los clientes que han estado en el sistema.
t
dttNt0
)(),0(
![Page 11: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/11.jpg)
11
Ley de Little
De acuerdo a las definiciones anteriores, se tiene que :
)2(),0(),0(
),0(tt
tT
Por otra parte, se define
tN : número promedio de usuarios en el intervalo (0,t)
(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].
![Page 12: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/12.jpg)
12
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.
Ley de Little
tN
Combinando las ecuaciones (1), (2) y (3) se obtiene
)3()()(
0
tt
t
dttNN
t
t
)4(),0(),0( tTtN t
![Page 13: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/13.jpg)
13
Asumiendo que el sistema es estable, se cumplen los siguientes límites:
Ley de Little
Notese que la existencia de estos límites es la única condición que se ha impuesto al sistema
tt
tt
TlimT
lim
![Page 14: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/14.jpg)
14
Ley de Little
Si estos límites existen, también existe el límite para . Sea
)5(TN
tN tt
NN lim
Entonces se tiene que
“Ley de Little”
![Page 15: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/15.jpg)
15
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.
Ley de Little
TN
![Page 16: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/16.jpg)
16
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
Ley de Little
TN
![Page 17: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/17.jpg)
17
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)
Ley de Little
TN
![Page 18: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/18.jpg)
18
Ley de Little
TN Llegadas y salidas
0
1
2
3
4
5
6
7
0 1 2 3 4 5 6 7 8
tiempo
usua
rios
Arribos deterministasArribos aleatoriosdistribució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
![Page 19: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/19.jpg)
19
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.
Ley de Little
TN
![Page 20: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/20.jpg)
20
Ley de Little
Llegadas y salidas
0
1
2
3
4
5
6
7
0 1 2 3 4 5 6 7 8
tiempo
usu
ario
s
Llegadas y salidas
0
1
2
3
4
5
6
7
0 1 2 3 4 5 6 7 8
tiempo
usu
ario
s
Salidas deterministas Salidas aleatorias, distribución cualquieraEn ambos casos, la ley de little se cumple, ya que la
disciplina de atención no fue considerada en la deducción
![Page 21: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/21.jpg)
21
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.
Ley de Little
TN
![Page 22: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/22.jpg)
22
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
Ley de Little
TN
![Page 23: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/23.jpg)
23
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á:
3321211 tttttt
Tc
T primer usuario
T segundo usuario
T tercer usuario
t1
t2
t3 t1 +t2
t2t1
t1
t1 +t2 +t3
t3
![Page 24: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/24.jpg)
24
Ley de Little
3
ttttttT 321211
c
T primer usuario
T segundo usuario
T tercer usuario
t1
t2
t3 t1 +t2
t2t1
t1
t1 +t2 +t3
t3
Tc
t1 t1 +t2 t1 +t2 +t3
![Page 25: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/25.jpg)
25
Ley de Little En cambio, si se atiende al trabajo más largo primero:
3
ttttttT 123233
l
T tercer usuario
T segundo usuario
T primer usuario
t2
t3
t1
t3 t3 +t2
t2 t1
t3 +t2 +t1
t3
![Page 26: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/26.jpg)
26
Ley de Little
t2
t3
t1
Tl
t3 t3 +t2 t3 +t2 +t1
t3 t3 +t2
t2 t1
t3 +t2 +t1
t3
3
ttttttT 123233
l
T tercer usuario
T segundo usuario
T primer usuario
![Page 27: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/27.jpg)
27
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
![Page 28: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/28.jpg)
28
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
Ley de Little
![Page 29: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/29.jpg)
29
Ley de Little
N usuariosT tiempo medio de permanencia
N=T
fila
Nf=fTf
servidor
NS=STS
f S
Tf TS
NfNS
![Page 30: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/30.jpg)
30
Ley de Little
En general, para el análisis de un servidor se tiene que
servidor
=S
S
x
s sN x
Factor de utilización Tiempo medio de
servicio
![Page 31: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/31.jpg)
31
Ley de Little
N1 usuarios
T1 tiempo medio de permanencia
N=T
servidorfila
N1 usuarios
T1
1
N1=1T1
S1
sistema
![Page 32: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/32.jpg)
32
Ley de Little
N usuariosT tiempo medio de permanencia
servidorfila
N2 usuarios
T2
2
N2=2T2
servidorfila
N1 usuarios
T1
1
N1=1T1
servidorfila
N3 usuarios
T3
3
N3=3T3
N=T
![Page 33: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/33.jpg)
33
Ley de LittleN=T
![Page 34: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/34.jpg)
34
Ley de LittleN=T
Internet
![Page 35: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/35.jpg)
35
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/
Ejemplo M/M/1
servidorfila
N usuariosT
N=T
![Page 36: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/36.jpg)
36
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á:
Ejemplo M/M/1
1k
![Page 37: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/37.jpg)
37
Por lo tanto, la esperanza (valor medio) del tiempo de permanencia en el sistema (T) será
Ejemplo M/M/1
1
11
11
kT E
E k
E k
![Page 38: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/38.jpg)
38
Pero E[k]=N, por lo tanto,
Además, de acuerdo a la Ley de Little
Ejemplo M/M/1
11T N
NT
![Page 39: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/39.jpg)
39
Despejando T, N de ambas ecuaciones se logra:
Ejemplo M/M/1
1T
N
Tiempo medio de permanencia en
el sistema
Número medio de usuarios en
el sistema
![Page 40: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/40.jpg)
40
A partir de las ecuaciones anteriores se puede obtener:
Ejemplo M/M/1
1 1
Q
W
N
Tiempo medio de permanencia en
la fila
Número medio de usuarios en
la fila
![Page 41: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/41.jpg)
41
Análisis de un concentrador
Análisis de un computador de tiempo compartido
Ley de Little: Ejemplos
![Page 42: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/42.jpg)
42
Análisis de un Concentrador
Ley de Little: Ejemplos
TERMINAL
TERMINAL
TERMINAL
TERMINAL
CONCENTRADOR BUFFE
R
![Page 43: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/43.jpg)
43
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.
Análisis de un Concentrador
![Page 44: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/44.jpg)
44
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 = = ?– retardo medio en el sistema = T = ?– tiempo de espera promedio en la fila = W = ?
Análisis de un Concentrador
N
![Page 45: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/45.jpg)
45
Análisis de un Concentrador
segpaquetes 1.25 =
81 10 =
Modelo :– Para modelar el Buffer se usará una Fila M/M/1.
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:
Apéndice
![Page 46: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/46.jpg)
46
La tasa de servicio se calcula como:
Análisis de un Concentrador
segpaquetes 5.2
9602400 =
Entonces, el número medio de usuarios en el sistema (Buffer y Servidor) es (Fila M/M/1):
0.52.5
1.25 =
Por ende, la ocupación media del buffer es:
11
N
![Page 47: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/47.jpg)
47
Utilizando la Ley de Little, el tiempo medio de cada usuario en el sistema es:
Análisis de un Concentrador
segN
T 8.025.11
segTW 4.01
El tiempo medio de espera en el buffer es:
T
W T’=1/μ
![Page 48: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/48.jpg)
48
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
Análisis de un Concentrador
![Page 49: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/49.jpg)
49
Análisis de un computador de tiempo compartido
COMPUTADOR
R
P
T1
T2
TN
D
Arquitectura del sistema
Ley de Little: Ejemplos
![Page 50: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/50.jpg)
50
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
![Page 51: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/51.jpg)
51
Modelado del Problema
B1 / P
CPU
TERMINAL1
TERMINAL2
TERMINALN
R
R
R
T
D
P
R
A
Análisis de un computador de tiempo compartido
Time Sharing
![Page 52: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/52.jpg)
52
Condiciones del sistema:– N= Constante del sistema
Condición Máxima de Utilización:– Siempre existe un usuario con trabajo
cuando otro acaba de ser atendido.
Problema:– Encontrar los valores máximos y mínimos
de y T.
Análisis de un computador de tiempo compartido
![Page 53: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/53.jpg)
53
Debido a la hipótesis siempre existen N terminales procesando
Aplicando a Ley de Little entre los puntos (A) y (B)
TN /
Análisis de un computador de tiempo compartido
![Page 54: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/54.jpg)
54
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
Análisis de un computador de tiempo compartido
![Page 55: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/55.jpg)
55
Conclusión: P D NP Por lo tanto R + P T R + NP (1) Aplicando la Ley de Little en (1)
(2) Debido a que el procesamiento de un trabajo demora P,
se cumple que: (3)
N
R NP
N
R P
1
P
Análisis de un computador de tiempo compartido
![Page 56: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/56.jpg)
56
Combinando (2) y (3), se obtiene:
(4)
Usando la Ley de Little se obtienen los límites de tiempo para el sistema
(5)
},1
{PR
N
Pmin
NPR
N
max{ , }NP RP T R NP
Análisis de un computador de tiempo compartido
![Page 57: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/57.jpg)
57
Retardo Máximo y Mínimo del Sistema
T
NUMERO DE TERMINALES N
R
1
NP: mínimo
R+NP:máximo
zona de operación
R+P
Análisis de un computador de tiempo compartido
![Page 58: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/58.jpg)
58
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
![Page 59: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/59.jpg)
59
Throughput Máximo y Mínimo
NUMERO DE TERMINALES
TH
RO
UG
HP
UT
1 / P
1 + R / P
Análisis de un computador de tiempo compartido
},1
{PR
N
Pmin
NPR
N
![Page 60: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/60.jpg)
60
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
![Page 61: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/61.jpg)
61
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
Análisis de un computador de tiempo compartido
![Page 62: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/62.jpg)
62
Apéndices
![Page 63: 1 Ley de Little Procesos Estocásticos y Teoría de Filas Primer Semestre de 2003 Luciano Ahumada Fierro](https://reader035.vdocumento.com/reader035/viewer/2022070418/5665b4b71a28abb57c937a21/html5/thumbnails/63.jpg)
63
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.
1/2/3/4/5
Tiempo entre arribos
Tiempo de servicio
Número de servidores
Número de fuentes
Longitud de la cola
G : GeneralM : Exponencial
G : GeneralM : Exponencial
N : Número finito
InfinitoN :Finito
InfinitoL :Finito
Nota: Normalmente, los infinitos se omiten y la disciplina de atención es FIFO