Embed Size (px)
Citation preview
Lıneas de espera y Teorıa de Colas
Sistema de lınea de espera o cola: cuando la demanda de un cierto
servicio excede la capacidad del sistema que la atiende, lo que da lugar a
una congestion previa al procesamiento (la cola).
X Procesadores informaticos:
Sistema al que acuden tareas (clientes) para ser procesadas (con demandas de servi-
cio), y que tiene una capacidad limitada de procesamiento (de servicio), lo cual causafenomenos de congestion de trabajos y de espera para ser procesads (espera en cola)
X Impresoras
X Tiendas de atencion al publico
X Cajeros: clientes humanos esperando formando una cola fısica.
X Servicios telefonicos/internet (servicios de tele-entrada)
X Servicios de urgencias
X Lista de espera sanidad: clientes humanos esperando formando una cola virtual (unsistema informatico realiza un seguimiento y control de los datos relevantes).
¿Por que se forman colas?
El problema de decision surge al enfrentar el coste del servicio con el coste del cliente:
a mayor rapidez del servicio, menor coste para el cliente y mayor para el servidor
1
Lıneas de espera y Teorıa de Colas
Los problemas de espera empezaron a estudiarse formalmente a partir de
1917, con los trabajo del ingeniero danes A.K. Erlang sobre el calculo de
probabilidades y el trafico telefonico.
Sus estudios iban encaminados a determinar la probabilidad de que una
centralita telefonica estuviera saturada y, por tanto, servıan de ayuda al
dimensionamiento de la misma.
Aplicacion: Diseno, dimensionamiento y operacion de redes de comuni-
cacion
X Sistemas telefonicos
X Redes de ordenadores
2
Proceso basico de colas: SISTEMAS ESTOCASTICOS
1. Los clientes llegan al sistema: habitualemnte no es posible conocer
con exactitud cuantos trabajos llegaran al sistema y cuando lo haran
Se generan a traves del tiempo en una fuente de entrada
2. Estos clientes entran al sistema:
a) Si hay algun servidor libre, pasan directamente a la realizacion del
servicio.b) En otro caso, se coloca en una cola de espera, hasta que el sistema
lo selecciona para realizar el servicio.
3. Los clientes salen del servicio: habitualmente no es posible conocer
con exactitud que tipo de servicio van a requerir
Fuente deentrada Cola
Mecanismode servicio
Clientes servidos
Sistema de colas
3
Proceso basico de colas: SISTEMAS ESTOCASTICOS (cont.)
¿Cual debe ser la capacidad exacta del sistema para atender la
demanda?
Dificultad de obtener un diseno que optimice el rendimiento del sistema
Objetivos del curso: describir y anzalizar el funcionamiento de sistemas
sencillos a partir del calculo de medidas de eficacia (rendimiento).
X Caracterısticas elementales de operacion del sistema:
– Proceso de llegadas, proceso de servicio y disciplina de la cola
– Tasa de llegada y de servicio, factor de utilizacion y estabilidad
X Principales medidas de eficacia y estudio de sus relaciones:
– Medidas de eficacia o rendimiento
– La Ley de Little
X Modelos Markovianos:
– Relacion del rendimiento del sistema con las caracterısticas de diseno del mismo
– Efectos del trafico pesado en el rendimiento
– Efecto marginal de un servidor
4
Descripcion de una cola
Proceso de llegadas
Se mide a traves del numero de llegadas por unidad de tiempo y el tiempo
entre las sucesivas llegadas.
Hay que tener en cuenta:
X si el numero medio de llegadas por unidad de tiempo es constante o
cambia con el tiempo
X si el numero medio de llegadas por unidad de tiempo es independiente
del numero de clientes presentes en el sistema o no
X Si la poblacion es finita o no: sistemas abiertos, sistemas cerrados
X si las llegadas al sistema se producen individualmente o por grupos
X si hay una o varias fuentes de llegadas al sistema
X es importante conocer el tipo de distribucion: determinista (los tiempos
de llegada de los clientes son conocidos), o probabilıstica (los tiempos
de llegada son aleatorios)
5
Descripcion de una cola
Proceso de servicio
Describe como son atendidos los clientes, y se caracteriza por el tiempo
empleado en dar servicio a un cliente y por el numero de servidores de
que se dispone.
Hay que tener en cuenta:
X tipo de distribucion: determinıstica o probabilıstica
X si el tiempo medio empleado en atender a un cliente es independiente
del tiempo y del numero de clientes presentes en el sistema
X si cada canal de servicio tiene su propia cola o existe una unica cola
para todos los canales
X si el servicio es individual o por grupos
6
Descripcion de una cola
Disciplina de la cola
Describe el orden en que se da servicio a los clientes.
La mas habitual es la FIFO (first–in–first–out), en la que el primer cliente
en llegar es tambien el primer cliente en ser atendido.
Algunos modelos asignan prioridades a ciertos clientes, o los seleccionan
aleatoriamente, round robin rule, LIFO (last–in–first–out).
Otras caracterısticas relevantes son:
X capacidad: limitada o ilimitada
X impaciencia: posibilidad de que se marchen clientes que llevan algun
tiempo en cola
X renuncias: clientes que no entran en cola al ser esta larga
X reintentos: clientes que abandonan la cola momentaneamente, pero
vuelven mas tarde
7
Ejemplos de Sistemas de Colas
ColaLlegadas Servidor Salidas
ColaLlegadas
Servidor
SalidasServidor
Servidor
ColaLlegadas
Servidor
SalidasServidor
ServidorCola
Cola
Llegadas Cola Servidor Cola SalidasServidor
8
Terminologıa
El estudio de una cola se hace a traves de las variables:
Tn, tiempo entre la llegada del cliente n − 1 y la del cliente n
Xn, tiempo de realizacion del servicio del cliente n
Ademas, se consideran los siguientes parametros:
λn, tasa de llegadas cuando el sistema tiene n clientes.
Si es constante, se nota por λ
En este caso, E(Tn) = E(T) = T = 1λ, para todo n
µn, tasa de servicio cuando el sistema tiene n clientes.
Si la tasa de servicio por servidor es constante, se nota por µ.
En este caso, E(Xn) = E(X) = X = 1µ, para todo n.
9
Intensidad de trafico
La cantidad de trabajo en un sistema de colas se suele medir en unidades
de tiempo.
Numero medio de llegadas por unidad de tiempo: λ
Cada llegada implica una carga media de trabajo: X.
Intensidad de trafico: carga media de trabajo por unidad de tiempo
λX = λ1
µ
Ejemplo
Si llegan 2 trabajos por minuto y cada trabajo requiere un servicio medio
de 0.4 minutos, la intensidad de trafico es de 0.8 minutos.
Si solo hay un servidor, el sistema esta ocupado el 80 % del tiempo, ¿y
si hay mas servidores?
10
Factor de utilizacion
Factor de utilizacion: porcentaje de tiempo esperado en que el sistema
esta ocupado
La carga media de trabajo por unidad de tiempo es: λµ
La capacidad del sistema por unidad de tiempo: m servidores
ρ =intensidad de trafico
capacidad del sistema=
λ/µ
m
El numero medio de llegadas por unidad de tiempo es: λ.
Si el sistema tiene m servidores, la capacidad de proceso es mµ trabajos.
ρ =tasa de llegadas
capacidad de procesamiento del sistema=
λ
mµ
Para sistemas con un unico servidor coincide con la intensidad de trafico.
Intuitivamente, puede considerarse como la probabilidad de que el sistema
este ocupado.
11
Estabilidad
Para poder ofrecer un servicio adecuado, la capacidad del sistema debe
ser mayor que la demanda: sistema estable
Ejemplo
Si llegan 4 trabajos por minuto y cada trabajo requiere un servicio medio
de 0.4 minutos, la intensidad de trafico es de 1.60 minutos.
Si solo hay un servidor, el sistema esta ocupado el 160 % del tiempo. La
congestion aumentara indefinidamente: sistema inestable
Si el numero de servidores es m, la condicion de estabilidad es:
ρ < 1 ⇐⇒ m > λX ⇐⇒ λ
µ< m
Para un sistema con un unico servidor, resulta: λµ
< 1
(la tasa de servicio debe ser mayor que la tasa de llegada)
12
Medidas de eficacia
El analisis de un sistema de colas esta encaminado a dar respuesta a
preguntas, tales como:
¿que fraccion de tiempo esta ocioso cada servidor?
¿cual es el tiempo medio de espera/respuesta para un cliente/trabajo?,
¿es razonable?, ¿se pierden clientes/trabajos por tiempos de espera
largos?
¿es conveniente anadir mas servidores para reducir el tiempo de es-
pera?
¿cual es el numero medio de clientes en cola?
¿cual es la probabilidad de que haya mas de un numero determinado
de clientes en cola en un tiempo determinado?
¿cual es la probabilidad de que la espera sea mayor que una determi-
nada longitud en un tiempo determinado?
A partir de la respuesta a estas preguntas se decide el diseno del sistema.
13
Medidas de eficacia
Para ello resulta adecuado contar con indicadores y medidas que cuan-
tifiquen la calidad del funcionamiento del sistema, medidas de eficacia del
sistema.
Algunas de las medidas de eficacia mas relevantes son:
Numero medio de clientes en espera (en cola): Q
Numero medio de clientes en el sistema: N .
Tiempo medio de espera (en cola): W
Tiempo medio de respuesta (en el sistema): S.
Numero medio de clientes en servicio: B
Medias a largo plazo: el sistema debe ser estable
Ejemplo: ver simulacion cola
W = lımn→∞
1
n
(
W1 + · · · + Wn
)
Wk = tiempo de espera (en cola) del cliente k-esimo
14
Relaciones entre medidas de eficacia.
Formulas de Little (1961)
Supongamos un sistema con las siguientes caracterısticas:
Tiene un unico servidor.
Los trabajos se sirven con una disciplina FIFO.
La tasa de llegadas al sistema es λ.
Un trabajo esta un tiempo medio de S en el sistema (tiempo medio
de respuesta).
15
Relaciones entre medidas de eficacia.
Desde que un trabajo llega al sistema hasta que sale transcurre un tiempo
igual a S.
La tasa de llegadas es de λ trabajos por unidad de tiempo ⇒ durante
todo ese tiempo al sistema llegaran una media de λS trabajos.
En el momento en que este trabajo se va, en el sistema quedan exacta-
mente todos los trabajos que han ido llegando desde que llego:
Por tanto, el numero medio de trabajos en el sistema, N es:
N = λS (1)
Si el tiempo medio de espera (en cola) es de W , el numero medio de
trabajos en espera (en cola), Q, es
Q = λW (2)
ya que, durante el intervalo W llegan un total de λW nuevos trabajos.
16
Relaciones entre medidas de eficacia.
Formulas de Little (1961)
N = λS
Q = λW
Por otro lado,
S = W + X = W +1
µ
B = N − Q
Entonces, como son cuatro medidas y tenemos tres ecuaciones que las
ligan, con conocer una de ellas es suficiente para obtener el resto.
17
Ejemplos
1. Una lınea de comunicaciones tiene un uso del 70 %. Calcular el cambio
en el uso si la tasa de llegadas se incrementa el 10 % y el tiempo medio
de servicio se reduce el 8 %
2. El uso de una cola con 5 procesadores es del 85 %. ¿Cual es el uso, si
sustituimos los 5 procesadores por 3 procesadores el doble de rapidos
3. Llegan tareas a un procesador con tasa 0,1 tareas/ms. Si el proce-
sador opera a 0,75 mips, derivar una cota para el maximo numero de
instrucciones por tarea para garantizar que el sistema es estable
4. El numero medio de trabajos en cola en un dispositivo E/S es 6,5.El
numero medio de trabajos en el sistema es 7,2. Si la tasa de llegadas
es 0,5 por segundo, determinar el tiempo medio de servicio y el tiempo
medio de respuesta.
18
Notacion en colas (Kendall)
A/B/m/c/d
Distribucion detiempos entre
llegadas
Distribucion deltiempo deservicio
Numero deservidores
Capacidaddel sistema
Disciplinade la cola
Distribuciones en el servicio y en las llegadas
M: exponencial.
D: determinısticos (tiempo entre llegadas o deservicio constante).
Ek: Erlang(k, λ), (suma de k exponenciales).
G: generales.
Disciplina de la cola:
FIFO: first–in–first–out, (por defecto).
LIFO: last–in–first–out.
SIRO: serve in random order queue discipline.
PRI: priority queue discipline, servicio con pri-oridades.
GD: disciplina general.
Capacidad del sistema:
Por defecto es infinita.
19
Colas Markovianas: cola M/M/1/ + ∞/FIFO
X Tiempo entre dos llegadas consecutivas:
X T1, T2, . . . independientes, identicamente distribuidas exp(λ)
X Tiempo medio entre llegadas: el tiempo medio entre las llegadas de
dos clientes consecutivos es de E(T) = 1λ unidades de tiempo
X Tasa de llegadas: el numero medio de llegadas por unidad de tiempo
es λ
X Tiempo de servicio:
X X1, X2, . . . independientes, identicamente distribuidas exp(µ)
X Tiempo medio de servicio: el tiempo medio de servicio de un cliente
es de E(X) = 1µ unidades de tiempo
X Tasa de servicio: el numero medio de clientes que un servidor es
capaz de atender por unidad de tiempo es µ
20
Cola M/M/1: la distribucion exponencial
Los modelos de colas mas estudiados suponen que las variables tiem-
po entre llegadas consecutivas y tiempo de servicio tienen distribucion
exponencial de parametros λ y µ, respectivamente.
Funcion de distribucion
FT (t) = P(T ≤ t) = 1 − e−λt ∀t ≥ 0
Funcion de densidad
fT (t) = λe−λt ∀t ≥ 0
Media y Varianza
T =1
λV ar(T) =
1
λ2
Coeficiente de Variacion
c.v.(T) =
√
V ar(T)
T= 1
21
Intermedio: la distribucion exponencial
Propiedad 1: fT (t) es estrictamente decreciente en t.
t
λ
fT(t)
P(0 ≤ T ≤ ∆t) > P(t ≤ T ≤ t + ∆t)
0,393 = P
(
0 ≤ T ≤ 1
λ
)
> P
(1
2
1
λ≤ T ≤ 3
2
1
λ
)
= 0,383
La probabilidad de que T tome un valor pequeno es mayor que de que
tome un valor alto.
Si T es el tiempo entre llegadas, esta propiedad descarta situaciones en
las que los clientes posponen la entrada si ven que entra otro cliente.
22
Intermedio: la distribucion exponencial
Propiedad 2: Perdida de memoria.
P{
T ≥ t + ∆t / T > ∆t}
= P{
T ≥ t}
La distribucion de probabilidad del tiempo que falta hasta la siguiente lle-
gada (o terminacion de servicio) siempre es la misma, independientemente
del tiempo ∆t transcurrido desde la ultima llegada.
Tiempos de llegada: la siguiente llegada no depende de cuando se produjo
la anterior.
Tiempos de servicio: el tiempo de servicio restante para terminar este
trabajo es independiente de cuando se ha empezado.
Totalmente aleatorio, no “regularidad” o pautas.
23
Intermedio: el proceso de Poisson
Nt =numero de llegadas en el intervalo de tiempo (0, t]
Si la variable tiempo entre dos llegadas consecutivos tiene distribucion
exp(λ) ⇒ Nt tiene distribucion P(λt)
Probabilidad de que lleguen n clientes en las siguientes t unidades de
tiempo:
P{Nt = n} = e−λt(λt)n
n!, para n = 0,1,2, . . .
Media y Varianza
Nt = λt V ar(Nt) = λt
En la practica, se habla de llegadas de Poisson y tiempos de servicio
exponencial
24
Intermedio: Ejemplo
Supongamos que a un ordenador van llegando trabajos siguiendo un pro-
ceso de Poisson.
Se sabe que en un periodo de longitud t, la probabilidad de que no llegue
ningun trabajo es 0,7.
Determinar la media y la varianza del numero de trabajos llegados en un
periodo de longitud 2t.
25
Intermedio: Ejemplo (cont.)
De la distribucion de la variable Nt, numero de llegadas en un periodo de
longuitud t, se tiene que
P{Nt = 0} = P{P(λt) = 0} = e−λt(λt)0
0!= e−λt = 0,7
De donde
λt = − ln(0,7) = 0,36
La media y la varianza del numero de llegadas en el intervalo (0, t) es
precisamente 0,36.
En el intervalo (0,2t), los valores seran exactamente el doble, 0,72.
26
Intermedio: Ejemplo
Supongamos que estamos estudiando los errores durante al ejecucion de
un programa.
Se sabe que la probabilidad de que se produzca un error o mas (de software
o hardware) en 15 minutos es del 5%.
¿Cual es la tasa de error?
¿Cual es la probabilidad de que no se produzca ningun error en tres horas
de ejecucion?
27
Intermedio: Ejemplo (cont.)
Sea λ la tasa de error.
La distribucion de la variable N15 es Poisson de parametro 15λ.
La probabilidad de que ocurra un error antes de 15 minutos es:
P{N15 ≥ 1} = 1 − P{N15 = 0} = 1 − e−15λ = 0,05
De donde
λ =− ln(0,95)
15,
y
P{N180 = 0} = e−180λ = (eln(0,95))18015 = (0,95)12 = 0,54
28
Intermedio: Ejemplo (cont.)
Sea λ la tasa de error.
La distribucion de la variable T es exponencial de parametro λ
La probabilidad de que ocurra un error antes de 15 minutos es:
F(t) = 1 − e−15λ = 0,05
De donde
λ =− ln(0,95)
15,
y la probabilidad de que no se produzca un error (llegada) en las proximas
3 horas es:
P(T > 180) = e−180λ = 0,54.
29
Intermedio: Union y division de procesos de Poisson
Sean dos secuencias de llegadas de dos procesos de Poisson indepen-
dientes con tasas de llegadas λ1 y λ2, respectivamente.
La union de las dos secuencias dara como resultado un nuevo proceso de
Poisson con tasa de llegada igual a la suma de los dos procesos: λ1 + λ2
Sea una secuencia obtenida de un proceso con tasa λ que se quiere dividir
en n secuencias.
Para ello, una llegada se asigna al proceso k con probabilidad pk, k =
1, . . . , n.
La secuencia k-esima es un nuevo proceso de Poisson con tasa de llegada
pkλ, k = 1, . . . , n.
30
Intermedio: Ejemplo
Un sistema de multiprocesamiento acepta envıos de trabajos de una fuente
de Poisson con tasa 6 trabajos/segundo. Supongamos que el 10 % del
trafico total se asigna aleatoriamente a cierto procesador:
1. ¿Cual es el tiempo medio trancurrido entre las llegadas de 2 trabajos
consecutivos al procesador?
2. ¿Cual es la probabilidad de que el siguiente trabajo que llegue tarde
mas de medio minuto?
3. ¿Cual es la probabilidad de que haya mas de 1 llegada al procesador
en un intervalo de tiempo de 1 minuto?
31
Intermedio: Ejemplo (cont.)
1. Los trabajos llegan al procesador segun un proceso de Poisson de tasa
0,1 · 6 = 0,6 trabajos/segundo ⇒
T tiene una distribucion exp(0,6) y E(T) = 10,6 = 1,6666 segundos
2. T , tiempo entre llegadas, tiene una distribucion exp(0,6), entonces:
P{T > 30} = 1−P{T ≤ 30} = F(30) = 1− e−30λ = 1− e−18 = 0,9999
3. N60, numero de llegadas en un intervalo de 1 minuto, tiene una dis-
tribucion P(60 · 0,6), entonces:
P{N60 ≥ 1} = 1 − P{N60 = 0} = 1 − e−60·0,6 ≈ 1
32
Intermedio: Ejemplo
Supongamos que a un ordenador con n procesadores llegan trabajos segun
un proceso de Poisson de tasa λ.
Una vez que un trabajo ha llegado, se asigna de forma cıclica a cada
procesador, de manera que si un trabajo se asigna al procesador k, el
siguiente trabajo se asignara al procesador k + 1 (o al primero si k = n).
Hallar el coeficiente de variacion.
33
Intermedio: Ejemplo (cont.)
Las llegadas a cada procesador no son independientes, ya que si se asigna
una llegada al procesador k, la siguiente llegada no va ser asignada al
procesador k.
El tiempo T entre dos llegadas consecutivas a un procesador es:
T = T1 + T2 + · · · + Tn
donde cada Tk tiene distribucion exponencial de media 1/λ.
T tiene una media de n/λ y una varianza de n/λ2.
El coeficiente de variacion es 1/√
n.
La funcion de densidad de T , que resulta de la suma de n exponenciales,
es: fT (t) = λ(λt)n−1 e−λt
(n − 1)!t ≥ 0 (Erlang(n,λ)).
34
Intermedio: Ejemplo
Supongamos un sistema con un unico procesador que admite tanto tra-
bajos locales como trabajos enviados desde otra maquina remota.
La maquina remota envıa trabajos con un tasa de 1 por hora y que los
dos procesos de llegada son de Poisson.
La desviacion tıpica de la variable T , tiempo entre dos llegadas consecu-
tivas, es de 15 minutos.
Determinar la tasa de envıo de trabajos de la maquina local.
35
Intermedio: Ejemplo (cont.)
La secuencia resultante es la union de dos secuencias independientes,
cada una correspondiente a los envıos de cada una de las dos maquinas,
local y remota.
Si la tasa de de envıos de la maquina local es λ1 y la de la maquina remota
es λ2, la tasa de envıos conjunta tiene tasa λ1 + λ2 = λ1 + 1.
La variable T tiene una distribucion exponencial de parametro λ1 + 1.
Su desviacion tıpica es:
15
60=
1
λ1 + 1=⇒ λ1 = 3.
36
Cola M/M/1: Factor de utilizacion, estabilidad
X El factor de utilizacion del sistema M/M/1 es:
ρ =intensidad de trafico
capacidad del sistema=
λ/µ
1=
λ
µ
X Condicion de estabilidad: ρ < 1 ⇒ tasa de servicio mayor que la tasa
de llegadas
En lo que sigue, supondremos que el sistema es estable y se encuentra en
estado estacionario. Comportamiento a largo plazo de sistemas estables.
37
Cola M/M/1: Medidas de eficacia
¿Como calcular N=numero medio de clientes en el sistema en equilibrio?
N =∞∑
n=0
npn
pn = probabilidad de que haya n clientes en el sistema en equilibrio
¿Como calcular pn? ⇔ ¿Como evoluciona el proceso “Numero de clientes
presentes en el sistema”?
Proceso de Nacimiento y Muerte: solo hay transiciones entre estados
(numero de clientes en el sistema) contiguos.
38
Cola M/M/1: Ecuaciones de balance de flujo
Diagrama de tasas de transicion
0 1 2 n-1 n n+1
Para que el sistema este en equilibrio pk tiene que permanecer constante.
Para ello, se deben satisfacer las ecuaciones de balance de flujo:
tasa de llegada al estado n = tasa de salida del estado n
pn−1λ + pn+1µ = pnλ + pnµ
39
Cola M/M/1: Probabilidades en equilibrio
Desarrollando estas formulas, resulta:
λp0 = µp1,
λp0 + µp2 = λp1 + µp1,
λp1 + µp3 = λp2 + µp2,
. . .
⇒
λp0 = µp1,
λp1 = µp2,
λp2 = µp3,
. . . ,
de donde
p1 =λ
µp0 = ρp0,
p2 =λ
µp1 = ρp1 = ρ2p0.
. . . .
pn =λ
µpn−1 = ρpn−1 = ρnp0
40
Cola M/M/1: Probabilidades en equilibrio
¿Como calculamos p0? A partir de∞∑
n=1
pn = 1, entonces
p0
∞∑
n=0
ρn = 1 ⇒ p0 =1
∑∞n=0 ρn
= 1 − ρ
X Probabilidades estacionarias:
pn = ρnp0 = ρn(1 − ρ), n = 0,1, . . .
X Numero medio de clientes en el sistema:
N =∞∑
n=0
n(1 − ρ)ρn = (1 − ρ)ρ∞∑
n=1
nρn−1 = (1 − ρ)ρ
∞∑
n=1
ρn
′=
= (1 − ρ)ρ
(
ρ
1 − ρ
)′= (1 − ρ)ρ
1
(1 − ρ)2=
ρ
1 − ρ
41
Cola M/M/1: Medidas de eficacia
X Por la Ley de Little (N = λS), el Tiempo medio de respuesta (en el
sistema):
S =N
λ=
λ
µλ(1 − ρ)=
1
µ(1 − ρ)
X Como S = W + 1µ, entonces el Tiempo medio de espera (en cola):
W = S − 1
µ=
ρ
µ(1 − ρ)
X Por la Ley de Little, el Numero medio de clientes en espera (en cola):
Q = λW = λρ
µ(1 − ρ)=
ρ2
1 − ρ
X Como B = N − Q, el Numero medio de clientes en servicio:
B =ρ
1 − ρ− ρ2
1 − ρ= ρ
42
Cola M/M/1. Ejemplo
Una lınea de comunicaciones transmite a 9600 bps.
Se producen llegadas de mensajes segun un proceso de Poisson con tasa
250 llegadas por minuto.
Los mensajes tienen longitud exponencial con media 1000 bits.
¿Que porcentaje de tiempo esta transmitiendo la lınea de comunica-
ciones?
¿Cual es la fraccion de tiempo en la que hay mas de dos mensajes?
43
Cola M/M/1. Ejemplo (cont.)
Tasa de llegadas: λ =250
60= 4,17 mensajes por segundo.
Tiempo medio de transmision: X =1000
9600= 0,1 segundos.
Tasa de transmision: µ = 1X
= 9,6 mensajes por segundo.
Uso del sistema: ρ = λµ = 4,17
9,6 = 0,43.
Probabilidad de que haya mas de dos mensajes en el sistema:
P{N ≥ k} = 1 − P{N ≤ k − 1} = 1 −k−1∑
n=0
ρn(1 − ρ) = 1 − (1 − ρ)(1 − ρk)
(1 − ρ)= ρk
P{N ≥ 3} = 1 − p0 − p1 − p2 = ρ3 = (0,43)3 = 0,079
Nota: Sk =k∑
n=1
an =a1 − akr
1 − r
44
Cola M/M/1. Ejemplo
La ventanilla de un banco realiza las transacciones en un tiempo medio
de 2 minutos. Los clientes llegan a una tasa de 20 clientes a la hora. Si
suponemos que las llegadas siguen un proceso de Poisson y el tiempo de
servicio es exponencial:
a) ¿Que porcentaje de tiempo esta el cajero desocupado?
b) En promedio, ¿cuanto tiempo esperan los clientes hasta ser atendidos?
c) ¿Que fraccion de clientes debe esperar en cola?
45
Cola M/M/1. Ejemplo (cont.)
Tasa de llegadas: λ = 20 clientes por hora.
Tiempo medio por transaccion: X =2
60horas.
Tasa de transaccion: µ = 1X
= 30 clientes por hora.
a) Proporcion de tiempo cajero desocupado = 1- Uso del sistema:
p0 = 1 − ρ = 1 − λ
µ= 1 − 20
30=
1
3
El 33’33 % del tiempo esta oocioso.
b) W =ρ
µ(1 − ρ)=
23
3013
=1
15hora
El tiempo medio de espera en cola es de 6015 = 4 minutos.
c) La fraccion de clientes que debe esperar en cola es
Q
N=
ρ2
1−ρρ
1−ρ
= ρ =2
346
Cola M/M/1. Ejemplo trafico pesado
Una linea de comunicaciones cuyo comportamiento se puede describir a
partir de una cola M/M/1 tiene un uso del 70 %. Calcular el numero medio
de clintes en el sistema:
N =ρ
1 − ρ=
0,7
0,3= 2,3333
¿Que ocurre si el uso aumenta en un 1 %?
ρ = (1,01)0,7 ⇒ N =0,707
0,293= 2,4129
Supone un incremento del 2,4129−2,33332,3333 100 = 3,41 %
¿Que habrıa ocurrido si la linea original hubiera tenido un uso del 99 %?
N =ρ
1 − ρ=
0,99
0,01= 99
y
ρ = (1,01)0,99 ⇒ N =0,9999
0,0001= 9999
Supone un incremento del 9999−9999 100 = 10000 %
47
Cola M/M/1. Congestion en funcion del uso del sistema
0.2 0.25
0.25 0.33333333
0.3 0.42857143
0.4 0.66666667
0.5 1
0.6 1.5
0.65 1.85714286
0.7 2.33333333
0.75 3
0.8 4
0.82 4.55555556
0.88 7.33333333
0.9 9
0.91 10.1111111
0.92 11.5
0.95 19
0.96 24
0.97 32.3333333
0.97 32.3333333
Congestión Media
0
5
10
15
20
25
30
35
0 0.2 0.4 0.6 0.8 1 1.2
Nivel de utilización
Nú
mero
med
io c
lien
tes s
iste
ma
48
Cola M/M/s: Factor de utilizacion y estabilidad
X La intensidad de trafico del sistema M/M/s es: λµ
Por la Ley de Little:
B = N − Q = λS − λW = λ
(
W +1
µ
)
− λW =λ
µ.
Se definio como la carga media de trabajo por unidad de tiempo, y tb
representa el numero medio de clientes en servicio.
X El factor de utilizacion del sistema M/M/s es:
ρ =intensidad de trafico
capacidad del sistema=
λ/µ
s=
λ
sµ
ρ = Bs ⇒ proporcion media de servidores ocupados.
X Condicion de estabilidad: ρ < 1 ⇒ tasa de servicio global (sµ) mayor
que la tasa de llegadas (λ)
Como antes, supondremos que el sistema es estable y se encuentra en
estado estacionario. Comportamiento a largo plazo de sistemas estables.
49
Cola M/M/s: Ecuaciones de balance de flujo
Para calcular las probabilidades estacionarias, {pn}n≥0, tenemos que plantear
las ecuaciones de balance de flujo del sistema:
Diagrama de tasas de transicion
0 1 2 s-1 s s+1
2 3 (s-1) s s s
Ecuaciones de balance de flujo:
tasa de llegada al estado n = tasa de salida del estado n
n = 0,1, . . . , s y n ≥ s
50
Cola M/M/s: Probabilidades en equilibrio
Desarrollando estas formulas, resulta:
p1µ = p0λ
p0λ + p22µ = p1λ + p1µ
p1λ + p33µ = p2λ + p22µ. . . . . .
ps−3λ + ps−1(s − 1)µ = ps−2λ + ps−2(s − 2)µ
ps−2λ + pssµ = ps−1λ + ps−1(s − 1)µ
ps−1λ + ps+1sµ = psλ + pssµ. . . . . .
pn−1λ + pn+1sµ = pnλ + pnsµ. . . . . .
⇒
λp0 = µp1,
λp1 = 2µp2,
λp2 = 3µp3,
. . . . . .
λps−2 = (s − 1)µps−1,
λps−1 = sµps,
λps = sµps+1,
. . . . . .
λpn = sµpn+1,
. . . . . .
51
Cola M/M/s: Probabilidades en equilibrio (cont.)
p1 = λµp0 = (λ/µ)p0,
p2 = λ2µp1 =
(λ/µ)2 p1 =
(λ/µ)2
2 p0,
p3 = λ3µp2 = ρ
3p2 = ρ3
3·2p0,
. . .
ps−1 = λ(s−1)µ
ps−2 =(λ/µ)s−1 ps−2 =
(λ/µ)s−1
(s−1)·(s−2)!p0,
ps = λsµps−1 =
(λ/µ)s ps−1 =
(λ/µ)s
s·(s−1)!p0,
ps+1 = λsµps =
(λ/µ)s ps =
(λ/µ)s+1
s·s! p0,
. . .
pn = λsµpn−1 =
(λ/µ)s pn−1 =
(λ/µ)n
sn−ss!p0,
. . . .
⇒pn =
(λ/µ)n
n! p0, n ≤ s
pn =(λ/µ)n
sn−ss!p0, n ≥ s
52
Cola M/M/s: Probabilidades en equilibrio (cont.)
¿Como calculamos p0? A partir de∞∑
n=1
pn = 1, entonces
p0
s−1∑
n=0
(λ/µ)n
n!+
∞∑
n=s
(λ/µ)n
sn−ss!
= 1 ⇒ p0 =1
s−1∑
n=0
(λ/µ)n
n!
+(λ/µ)s
s!(1−ρ)
,
ya que∞∑
n=s
(λ/µ)n
sn−ss!=
(λ/µ)s
s!
∞∑
n=0
(λ/µ)n
sn︸ ︷︷ ︸
ρn
=(λ/µ)s
s!· 1
1 − ρ
Nota. Probabilidad de que un nuevo cliente tenga que esperar es
pw = P{N ≥ s} =∞∑
n=spn = p0
∞∑
n=s
(λ/µ)n
sn−ss!=
(λ/µ)s
s!· p0
1 − ρ
53
Cola M/M/s: Medidas de eficacia
En este caso, la medida mas sencilla de obtener es el Numero medio de
clientes en espera (en cola):
Q =∞∑
k=0
kP{NQ = k} =∞∑
k=0
kP{N = k + s} =∞∑
k=0
k(λ/µ)(k + s)
sks!p0 =
=(λ/µ)s
s!p0
∞∑
k=0
k
(
(λ/µ)
s
)k
︸ ︷︷ ︸
ρk
=(λ/µ)s
s!p0ρ
∞∑
k=1
kρk−1
Como
∞∑
k=1
kρk−1 =
∞∑
k=1
ρk
′=
1
(1 − ρ)2,
entonces
Q =(λ/µ)s
s!p0ρ
1
(1 − ρ)2=
(λ/µ)sp0ρ
s!(1 − ρ)2
54
Cola M/M/s: Medidas de eficacia (cont.)
X Por la Ley de Little (Q = λW ), el Tiempo medio de espera (en cola):
W =Q
λ
X Como S = W + 1µ, entonces el Tiempo medio de respuesta (en el
sistema):
S = W +1
µ=
Q
λ+
1
µ
X Por la Ley de Little, el Numero medio de clientes en el sistema:
N = λS = Q +λ
µ
X Como B = N − Q, el Numero medio de clientes en servicio:
B = Q +λ
µ− Q =
λ
µ= sρ
55
Cola M/M/s. Ejemplo
Una empresa ha recogido datos de las llamadas telefonicas recibidas en
los ultimos anos en horas punta.
El tiempo entre llamadas sigue una distribucion exponencial con frecuen-
cia media de 84.3 por hora. El analisis de las conversaciones revela que
la duracion media de las llamadas es de 0.103 horas.
¿Cuantas centrales se necesitan como mınimo para que el sistema no se
colapse en las horas punta?
ρ =λ
sµ=
84,3
s(1/0,103)=
8,6829
s< 1 ⇒ s ≥ 9
Si por termino medio, se puede tolerar que los clientes reciban una senal
de lınea ocupada a razon de un cliente por cada dos horas. ¿Cual es el
numero apropiado de lıneas telefonicas que debe tener la central?
¿Cual es el menor valor de s ≥ 9 que garantiza Q(s) ≤ 12?
56
Cola M/M/s. Ejemplo (cont.)
Tenemos que obtener p0 y Q para cada valor de s ≥ 9:
p0(s) =
s−1∑
n=0
8,6829n
n!+
8,6829s
s!(
1 − 8,6829s
)
−1
,
Q(s) =8,6829sp0(s)
8,6829s
s!(
1 − 8,6829s
)2.
Se obtiene:
s ρ p0(s) Q(s)
9 0.965 0.0000402 24,147
10 0.868 0.0001135 3.814
11 0.789 0.0001449 1.3662
12 0.724 0.0001587 0.57622
13 0.668 0.0001647 0.2558
57
Cola M/M/s. Efecto marginal de anadir un servidor
Los trabajadores de una fabrica tienen que llevar su trabajo al departa-
mento de control de calidad antes de que el producto llegue al final del
proceso de produccion.
Hay un gran numero de empleados y las llegadas son aproximadamente
de 20 por hora, siguiendo un proceso de Poisson.
El tiempo para inspeccionar una pieza sigue una distribucion exponencial
de media 4 minutos. Calcula el numero medio de trabajadores en el con-
trol de calidad si hay 2 inspectores, ¿que pasa cuando se contrata a un
inspector mas?
58
Cola M/M/s. Efecto marginal de anadir un servidor (cont.)
Sistema M/M/2 con λ = 20 y µ = 604 = 15. Entonces
λ
µ=
4
3, ρ =
λ
2µ=
2
3, N = Q +
λ
µ= Q +
4
3,
donde
Q(2) =(λ/µ)s
s!p0(s)ρ
1
(1 − ρ)2=
(4/3)2
2!p0(2)
2
3
1
(1/3)2=
16
3p0(2)
p0(2) =
1∑
n=0
(4/3)n
n!+
(4/3)2
2!(1/3)
−1
=
(
1 +4
3+
8
3
)−1
=1
5
Luego
N = Q +4
3=
16
3
1
5+
4
3=
36
15= 2,4
59
Cola M/M/s. Efecto marginal de anadir un servidor (cont.)
Si se contrata a otro inspector, entonces sistema M/M/3 con λ = 20 y
µ = 604 = 15.
λ
µ=
4
3, ρ =
λ
3µ=
4
9, N = Q +
λ
µ= Q +
4
3,
donde
Q(3) =(λ/µ)s
s!p0(s)ρ
1
(1 − ρ)2=
(4/3)3
3!p0(3)
4
9
1
(5/9)2=
128
225p0(3)
p0(3) =
2∑
n=0
(4/3)n
n!+
(4/3)3
3!(5/9)
−1
=
(
1 +4
3+
8
9+
32
45
)−1
≈ 0,2542
Luego
N = Q +4
3≈ 128
2250,2542 +
4
3≈ 1,478
La reduccion es de un 2,4−1,4782,4 100 = 38,42 %
60
Cola M/M/s. Efecto marginal de anadir un servidor (cont.)
¿Cual habrıa sido la reduccion si la tasa de llegadas fuese λ = 25?
El nivel de utilizacion del sistema pasa del 66,66 % al 83,33 %)
N(2) = Q(2) +λ
µ= 3,7878 + 1,6666 = 5,4545
N(3) = Q(3) +λ
µ= 0,3747 + 1,6666 = 2,0414
La reduccion es de un 5,4545−2,04145,4545 100 = 62,57 %
61
Cola M/M/s. Relacion entre las colas M/M/1, M/M/2 y M/M/3
En un servidor de internet existen 3 nodos que atienden peticiones a
razon de 30 por minuto. El tiempo medio de servicio de cada nodo es de
5 segundos por peticion.
Se estan planteando cambiar la instalacion de los nodos y se preguntan
cual de las siguientes configuraciones sera mejor, si lo que les interesa es
reducir el tiempo medio de espera (en cola):
1. Mantener los 3 nodos actuales.
2. Sustituir los 3 nodos por 2 nodos, cada uno con capacidad de atender
18 peticiones por minuto.
3. Sustituir los 3 nodos por un unico nodo 3 veces mas rapido.
62
Cola M/M/s. Relacion entre las colas M/M/1, M/M/2 y M/M/3
1. Sistema M/M/3 con λ = 30, µ = 605 = 12, B = λ
µ = 2,5, y ρ = 303·12 = 5
6
2. Sistema M/M/2 con λ = 30, µ = 18, B = 53 y ρ = 30
2·18 = 56
3. Sistema M/M/1 con λ = 30, µ = 60(5/3)
= 36, B = ρ = 3036 = 5
6
Como W = Qλ y λ no cambia de una configuracion a otra, es suficiente
con comparar Q:
Q1 =2,53p1
0ρ
6(1 − ρ)2= 3,5112, Q2 =
(5/6)3p20ρ
2(1 − ρ)2= 3,7878, Q3 =
ρ2
1 − ρ=
25
6= 4,1666
donde p10 = 0,045 y p2
0 = 0,0909
Para un mismo nivel de utilizacion del sistema, el sistema M/M/1 es el
mas eficiente de los 3. Ademas, el sistema M/M/2 es mas eficiente que
el M/M/3.
¿Ocurrira siempre lo mismo?, ¿por que?
63
Cola M/M/s. Ejemplo (febrero 2006)
Considera una cola con tasa de llegadas λ, y 7 servidores identicos en paralelo, cada unode los cuales tiene tasa de servicio µ.
1. Formula la condicion que han de cumplir los parametros dados para que la cola seaestable.
2. Nos dan los siguientes datos:
(i) numero medio de servidores ocupados: 6
(ii) tiempo medio que un cliente permanece en el sistema (incluyendo su tiempo deservicio): 30 minutos
(iii) tiempo medio que un cliente permanece en espera: 18 minutos
Calcular: (1) el factor de utilizacion del sistema, (2) la tasa de llegada, (3) la tasade servicio, (4) el numero medio de clientes en el sistema, y (5) el numero mediode clientes en espera.
¿Es estable el sistema?
3. En el caso de que los tiempos entre llegadas de clientes y los tiempos de servicio fue-sen variables aleatorias exponenciales, representa el diagrama de tasas de transicionentre estados, y formula las ecuaciones de balance de flujo correspondientes.
64
Cola M/M/s. Ejemplo (febrero 2006)
1. Condicion de estabilidad:
ρ =λ
7µ< 1 ⇒ λ < 7µ
2. Nos dan los siguientes datos:
(i) numero medio de servidores ocupados: 6 = B (numero medio de clientes siendoatendidos)
(ii) tiempo medio que un cliente permanece en el sistema: 30 minutos= S
(iii) tiempo medio que un cliente permanece en espera: 18 minutos= W
Calcular:
(1) Factor de utilizacion del sistema:
ρ =λ
7µ=
B
7=
6
7
Como ρ < 1, el sistema es estable.
65
Cola M/M/s. Ejemplo (febrero 2006)
(2) Tasa de llegada: Como S = W + 1µ, entonces 1
µ= S − W = 30 − 18 = 12. Luego,
6 = B = λ1
µ⇒ λ = 6µ =
6
12= 0,5
(3) Tasa de servicio: µ = 112
(4) Numero medio de clientes en el sistema: N = λS = (0,5)(30) = 15
(5) Numero medio de clientes en espera: Q = N − B = 15 − 6 = 9
Diagrama de tasas de transicion:
Ecuaciones de balance de flujo:
66
