Tema 5:
Teoría de colas
Ezequiel López Rubio
Departamento de Lenguajes y
Ciencias de la Computación
Universidad de Málaga
Sumario





Conceptos básicos
Cola M | M | 1
Cola M | M | c
Cola M | M | 1 | k
Redes de colas


Redes de Jackson abiertas
Redes de Jackson cerradas
Conceptos básicos
Concepto de cola

Una cola es una línea de espera para
determinado servicio


Este servicio lo proporciona uno o varios
dependientes
La teoría de colas analiza la causa de la
formación de la cola, que es la existencia de
momentos en los que hay una mayor
demanda de servicio que la capacidad de
servicio
Clasificación de sistemas de
colas


Llamaremos clientes, trabajos o tareas a los que
demandan servicio, y dependientes, empleados o
servidores a los que ofrecen servicio
Un sistema de colas viene dado por varias
características:

1º Modelo de llegada de clientes, El índice de
llegadas será el número medio de llegadas por unidad
de tiempo, Alternativamente podemos usar el tiempo
entre llegadas, que es el tiempo medio entre llegadas
sucesivas
Clasificación de sistemas de
colas


2º Modelo de servicio, Puede venir dado por el tiempo de
servicio o por el número de clientes atendidos por unidad
de tiempo, Tendremos una variable aleatoria o bien un
servicio determinista, Aquí supondremos que el modelo de
servicio es independiente del de llegada
3º Disciplina de la cola, Establece el orden en que se va
atendiendo a los clientes:




Por orden de llegada (FIFO)
Por orden inverso al de llegada (LIFO)
Selección aleatoria (RANDOM)
Según prioridades (PRIORITY, PR), Dos subtipos:



Con interrupción, Si llega un cliente de más prioridad, el trabajo que se
estaba sirviendo se interrumpe para atenderlo
Sin interrupción, No se pueden interrumpir los trabajos
Dentro de cada clase de prioridad se podrán aplicar disciplinas LIFO, FIFO
o RANDOM,
Clasificación de sistemas de
colas



4º Capacidad del sistema, Es el número máximo de
clientes que puede haber en el sistema (finito o infinito), Si
llega un cliente y el sistema está lleno, se marcha,
5º Número de canales de servicio, Es el número de
dependientes, Puede haber una cola para cada
dependiente o bien una sola cola global
6º Número de estados de servicio, Puede haber varias
partes en las que se subdivide el trabajo (estados), cada
una con su cola y su dependiente, que deben ser
completadas sucesivamente, P, ej,, tres estados:
Notación de Kendall

La notación de Kendall nos permite escribir
resumidamente todas las características que
hemos estudiado, Un sistema de colas se
notará como: A | B | X | Y | Z | V, donde:

A es el modelo de llegadas, Valores posibles:




M=tiempos entre llegadas exponenciales
D=tiempos entre llegadas deterministas
G=tiempos entre llegadas generales (cualquier
distribución)
B es el modelo de servicio, Puede tomar los
mismos valores que A
Notación de Kendall





X es el número de dependientes (servidores)
Y es la capacidad del sistema (número máximo
de clientes en el sistema), Se puede omitir si es
infinita
Z es la disciplina, Se puede omitir si es FIFO
V es el número de estados de servicio, Se puede
omitir si es 1
Por ejemplo, M | M | 1 |  | FIFO | 1 se
escribe abreviadamente M | M | 1
Medidas de rendimiento

Una vez descrito el sistema, nuestro objetivo
es evaluar su rendimiento, Para ello tenemos
varias medidas de rendimiento:




Número medio de clientes en el sistema, notado L
Tiempo medio de espera de los clientes, W
Número medio de clientes en la cola, Lq
Tiempo medio de espera en cola de los clientes,
Wq
Cola M | M | 1
Descripción del modelo



Hay una sola cola, cuya capacidad es infinita, y un
solo servidor, La disciplina será FIFO
Las llegadas se producen según un proceso de
Poisson de razón , donde  es el número medio de
llegadas por unidad de tiempo y 1/ es el tiempo
medio entre llegadas, Los tiempos entre llegadas se
distribuirán exponencialmente, Exp()
Los tiempos entre servicios también se distribuirán
exponencialmente, Exp(), de tal manera que  es
el número medio de clientes que el servidor es
capaz de atender por unidad de tiempo y 1/ es el
tiempo medio de servicio
Condición de no saturación

Se demuestra que si , el sistema se satura,
es decir, el número de clientes en la cola crece
indefinidamente con el tiempo, Por consiguiente,
la condición de no saturación será:
  1,

donde
 


Nosotros sólo estudiaremos las colas que no se
saturan, Cuando una cola no se satura, también
se dice que alcanza el estado estacionario,
Probabilidades


El parámetro  se llama carga, flujo o
intensidad de tráfico del sistema, puesto que
mide la relación entre la cantidad de trabajos
que llegan y la capacidad de procesarlos
Suponiendo que el sistema no se satura, se
deduce la siguiente fórmula para las
probabilidades pn de que haya n clientes en
el sistema, donde nN:
pn  
n
1   
Medidas de rendimiento

El número medio de clientes en el sistema, L, se
calcula así:

L 


j pj 
j0


j 
j
j0
1     1   
j0
Sumamos la serie aritmético-geométrica:
S    2   3   4   ...
2
 S 
1   S
3
4
   2   3   ...
2
3
4
         ... 
2
 L  1   
3

4

1   
2

1 

1 
j 
j
Medidas de rendimiento

La utilización del dependiente, notada U, es la fracción
de tiempo (en tanto por uno) que el dependiente
permanece ocupado, Para hallarla, nos valemos de
que cuando no hay saturación, el número medio de
clientes que entran en el sistema debe ser igual al
número medio de clientes que salen de él:
  U  U 



 
Como para deducir la anterior fórmula no hemos
usado ninguna característica especial del modelo de
entrada ni del de salida, dicha fórmula es válida para
colas G | G | 1
Medidas de rendimiento

El tiempo medio de respuesta W es el tiempo medio que
un trabajo permanece en el sistema, Si suponemos que
un trabajo, al llegar al sistema, se encuentra con que
hay por delante de él otros j trabajos, el tiempo medio
que tardará en salir del sistema será j+1 veces el tiempo
medio de servicio, Por lo tanto:

W 
1
  j  1 
j0
Tiempo que se pasa
en el sistema si
hay j por delante
al llegar

pj 

j0
j
1


pj 

j0
1

pj 
L

Probabilidad de que
haya j por delante
al llegar

1

Medidas de rendimiento

Podemos simplificar algo más:
W 

L


1


 
El tiempo medio de espera en la cola Wq se hallará
restando a W el tiempo que tarda en ser servido el
trabajo (esto es válido para cualquier tipo de cola):
Wq  W 

1
1

En el caso particular de una cola M | M | 1, obtenemos:
Wq 

 
Ejemplo


Unos mecánicos llegan a una media de 10 por hora
a recoger piezas de repuesto, Estas piezas se las
da un dependiente pagado con 5 €/hora y que tarda
como media 5 min en servir, Cada hora que tiene
que esperar un mecánico (en el sistema) le cuesta
al taller 10 €, Queremos saber si merece la pena
contratar a un ayudante de dependiente, pagado
con 4€/hora, de forma que el tiempo medio de
servicio se reduzca a 4 min
Nota: Al resolver un problema de colas, tener
siempre muy presente la coherencia de unidades
Ejemplo

Tenemos dos opciones:




Sin ayudante: 1/1 = 5 min = 1/12 h
Con ayudante: 1/2 = 4 min = 1/15 h
En ambos casos,  = 10 clientes/h
Opción 1 (sin ayudante):
10
1 
10
12
;
L1 
1
1  1

12  5
10
1
12
mecánicos
Por tanto, perdemos 5·(10€/h) = 50€/h
Ejemplo

Opción 2 (con ayudante):
10
2 
10
15
;
L1 
1
1  1

15  2
10
1
15
mecánicos
Por tanto, perdemos 2·(10€/h) = 20€/h debido a la
espera de los mecánicos, Pero también
perdemos 4€/h debido al sueldo del ayudante,
Por tanto, las pérdidas totales son 24€/h
 En la opción 1 perdemos 50€/h y en la opción 2
perdemos 24€/h, con lo cual la más ventajosa es
la opción 2,
Más medidas de rendimiento

El número medio de trabajos en la cola Lq, se
calcula restándole a L el número medio de trabajos
que están siendo servidos:
L q  L  1  p 0   L   

1 
 

2
1 
Probabilidad de que un cliente que llega pase más
de t unidades de tiempo en el sistema:
W t   e


t /W
Probabilidad de que un cliente que llega pase más
de t unidades de tiempo en la cola:
W q t    e
t /W
Ejemplos

Ejemplo: Un canal de comunicación se usa para
enviar datos desde unos ordenadores fuente a uno
central, Cada fuente envía paquetes de datos según
un proceso de Poisson de razón 2 paquetes/seg,
Además cada fuente envía independientemente de
las otras, Todos los paquetes son idénticos, esperan
en una cola común y después se transmiten de uno
en uno, Los tiempos de transmisión se distribuyen
exponencialmente, con media 25 mseg, Determinar
el número máximo de fuentes que se pueden
conectar al canal de tal manera que:
Ejemplos

1º El canal no se sature


Si tenemos k fuentes, llegarán a la cola 2k
paquetes/seg, Por otro lado, 1/ = 0,025 seg  
= 40 paquetes/seg
El canal no se satura cuando <1:
 



2k
40

k
20
 1  k  20 fuentes
Ejemplos

2º En media los paquetes no pasen en el
sistema más de 100 mseg


Tal como ocurría en el apartado anterior, llegarán a
la cola 2k paquetes/seg, y tendremos  = 40
paquetes/seg
Nos exigen W0,1 seg:
W 
1
 

1
40  2 k
 0 ,1  k  15 fuentes
Ejemplos

3º En el estado estacionario se garantice que al
menos el 95% de los paquetes tenga un tiempo de
respuesta que no exceda de 100 mseg


Tal como ocurría en el apartado anterior, llegarán a la cola
2k paquetes/seg, y tendremos  = 40 paquetes/seg
Nos exigen que la probabilidad de que un paquete pase
más de 100 mseg en el sistema sea inferior al 5%, es
decir, W(100 mseg)0,05:
W 0 ,1  0 , 05  e
k 
4  ln 0 , 05
0,2
 0 ,1  40  2 k 
 0 , 05  0 , 2 k  4  ln 0 , 05 
 k  5 , 021  k  5 fuentes (ya que k  N )
Ejemplos

Ejemplo: Supongamos que una cola M|M|1 con parámetros 
y  se sustituye por n colas M|M|1 independientes de
parámetros /n y /n, Es decir, dividimos la carga de trabajo y
la capacidad de proceso en n partes iguales, Evaluar el
efecto del cambio usando como medidas de rendimiento el
tiempo medio de respuesta y el número medio de trabajos en
el sistema
/n
/n

…

/n
/n
Ejemplos

Alternativa 1 (una sola cola), 1=, 1=  :
L1 
W1 

1

1  1
1
 1  1


 
1
 
Alternativa 2 (n colas independientes), 2=/n,
2=/n :


n
n
L2 
2
 1 
i 1
n
2
2
1 2
n

n
1

n

n

n
1 
n


 
 nL 1
Ejemplos
W2 


1
 2  2

1

n

n

n
1
 
 nW 1
Como la alternativa 1 tiene menores valores
para ambas medidas de rendimiento,
concluimos que la dicha alternativa es mejor
Esto nos indica que lo mejor es no dividir la
capacidad de procesamiento, es decir, tener un
único servidor que atienda a todos los clientes
Teorema de Little

Sea un sistema de colas con cualquier
distribución de llegadas y servicios y cualquier
estructura, Sean L el número de trabajos
presentes en el sistema en el estado
estacionario, W es tiempo medio de respuesta
en el estado estacionario y  la razón de
llegadas al sistema, Entonces:
L  W
Teorema de Little
Explicación intuitiva: Supongamos que cobramos
1€ a cada trabajo por cada unidad de tiempo que
pasa en el sistema, Habría dos maneras
equivalentes de medir las ganancias:



Colocando un recaudador a la entrada del sistema,
le cobrará como media W a cada uno de los 
trabajos que vea pasar por unidad de tiempo
Cada vez que transcurre una unidad de tiempo,
cobro 1 € a cada uno de los L trabajos que como
media hay en ese instante en el sistema
Teorema de Little

Si aplico el teorema a la cola, dejando fuera
del sistema al servidor, obtengo el siguiente
resultado, también muy útil:
Lq   W q

Las dos fórmulas obtenidas nos sirven para
ayudarnos a obtener los valores de las
medidas de rendimiento, aunque
necesitaremos otras ecuaciones para poder
conseguir resultados explícitos
Cola M | M | c
Descripción del modelo



Hay una sola cola, cuya capacidad es infinita, y c
servidores, La disciplina será FIFO
Las llegadas se producen según un proceso de
Poisson de razón , donde  es el número medio de
llegadas por unidad de tiempo y 1/ es el tiempo
medio entre llegadas, Los tiempos entre llegadas se
distribuirán exponencialmente, Exp()
Los tiempos de servicio también se distribuirán
exponencialmente, Exp(), de tal manera que  es
el número medio de clientes que cada servidor es
capaz de atender por unidad de tiempo y 1/ es el
tiempo medio de servicio
Condición de no saturación

Se demuestra que si c, el sistema se satura,
es decir, el número de clientes en la cola crece
indefinidamente con el tiempo, Por consiguiente,
la condición de no saturación será:
  1,

donde
 

c
Nosotros sólo estudiaremos las colas que no se
saturan, Cuando una cola no se satura, también
se dice que alcanza el estado estacionario,
Probabilidades

Suponiendo que el sistema no se satura, se
deducen las siguientes fórmulas para las
probabilidades pn de que haya n clientes en el
sistema, donde nN:
1
n
c
c
c 1
 c 

c  

p0  

 c! 1   
n! 
n0

 c   n
p 0 , si n  0 ,1,..., c

 n!
pn  
c
n
c


p 0 , en otro caso

 c!
Medidas de rendimiento

Número medio de clientes en cola:
c 
c
Lq 

c 1
p0
c! 1   
2
Usamos razonamientos ya vistos para obtener:
W  Wq 
Lq  W q
1

L  W
Otras medidas de rendimiento

Número medio de servidores ocupados, S, En
el estado estacionario, la razón de las salidas
será igual a la razón de las llegadas:
S    S 



 c
Probabilidad de que un trabajo tenga que
esperar para recibir su servicio (fórmula de
retraso de Erlang):
c  p0
c
q
c
c! 1   
Ejemplos

Ejemplo: Usando L como medida de
rendimiento, comparar estas dos alternativas:
Alternativa 1:

Alternativa 2:

/2

/2
Ejemplos

Alternativa 1:
L1 


1 
Alternativa 2:


2 

 


2
2
 2 


 2! 1   

2
p 02
2
2 1

n0
2  
n!
n




1
Ejemplos
 4
 
1 2
 2 1   
2
p 02
p 02




1
 4  2  2  4  4
 
2 1   

2
 2  2 

 
 2 1    
1

2
1 
1 

1 
2
L 2   W 2    W q 2      W q 2 
 Wq2  2

2 

4  p 02
3
L2  Lq 2  2  
2 1   
2  1   
3
2
 2 
1    1   
2
 2




1
Ejemplos
L2 

2
3
2  2  2
3
1   1   
 2 
1   1   
2
3

1   1   
Para que la alternativa 1 sea mejor, ha de
cumplirse que L1<L2:

2
 

2

 
 0  1 
1   1     1  
1 
1 

 1   2    1

Como <1 siempre se cumple, tendremos que
la alternativa 1 siempre es mejor, Es decir, no
conviene dividir la capacidad de procesamiento
en dos servidores
Ejemplos

Ejemplo: Usando el número medio de clientes en el
sistema como medida de rendimiento, comparar
estas dos alternativas:
Alternativa 2:
Alternativa 1:
/2
/2
/2

/2
/2
/2
Ejemplos

Alternativa 1 (nótese que hay 2 colas):
L1  2

1
1  1

2
1 
,
donde
 


Alternativa 2 (es la alternativa 2 del ejemplo
anterior):
2 



 


2
2
L2 
2
1   1   
Ejemplos

Para que la alternativa 2 sea mejor, ha de
cumplirse que L1>L2:
2
2
 2

1

 
 0  1 
1   1     1  
1 
1 

 1   1   0

Como >0 siempre se cumple, tendremos que
la alternativa 2 siempre es mejor, Es decir, no
conviene poner dos colas, sino tener una única
cola global
Ejemplos


Ejemplo: En una copistería se dispone de 3
máquinas fotocopiadoras a disposición del público,
Cada máquina es capaz de servir, por término
medio, 8 trabajos cada hora, A la copistería llegan
como promedio 5 clientes a la hora,
Parámetros del sistema:  = 5 clientes/h,  = 8
clientes/h, c = 3 servidores, El sistema no se satura
porque <1,
 

c

5
3·8

5
24
Ejemplos

¿Cuál es la probabilidad de que las tres máquinas
estén libres a la vez?
 c 
p0  

 c! 1   

c
c
c 1

c  
n0
n!
0
1
2
 33  3



3 
3 
3 




 3! 1   
0
!
1
!
2!


n








1
1
 3 


 3! 1   

3
3
2

3  
n0
5
25 
 125

1 

8 128 
 2432
n
n!
1





1

304
 0,5342706
569
¿Cuál es el número medio de clientes en la cola?
c 
c
Lq 
c 1
p0
c! 1   
2
3 
3

4 304
569
2
3! 1   

302
41791
 0,00722643
clientes
Ejemplos

¿Cuál es el tiempo medio de espera en la cola?
Wq 

Lq

52

5·41791
 0 ,00144529
h
35979
¿Cuál es el tiempo medio de espera en el sistema?
W  Wq 

302

1


52

35979
1
8

514
 0 ,126445
h
4065
¿Cuál es el número medio de clientes en el
sistema?
L   W  5·
514
4065

514
813
 0.632226
clientes
Cola M | M | 1 | k
Descripción del modelo



Hay una sola cola, cuya disciplina será FIFO, La
capacidad del sistema es limitada, de tal modo que
sólo puede haber k clientes como máximo en el
sistema, Por lo tanto, el número máximo de clientes
en la cola es k–1, Si un cliente llega y el sistema
está lleno, es rechazado y nunca más regresa
Las llegadas se producen según un proceso de
Poisson de razón , Los tiempos entre llegadas se
distribuirán exponencialmente, Exp()
Los tiempos entre servicios también se distribuirán
exponencialmente, Exp(), de tal manera que  es
el número medio de clientes que el servidor es
capaz de atender por unidad de tiempo
Probabilidades


El sistema nunca se satura, ya que la
capacidad es limitada
Se deduce la siguiente fórmula para las
probabilidades pn de que haya n clientes en
el sistema, donde n{0, 1, 2, …, k}:
  n 1   
, si   1

k 1
 1 
pn  
 1
, si   1
 k  1
Probabilidades

El valor de  determina cómo varían los pn:




Si <1, los estados más probables son los de menor
número de clientes, porque la oferta de servicio supera a
la demanda
Si >1, los estados más probables son los de mayor
número de clientes, porque la demanda de servicio supera
a la oferta
Si =1, todos los estados son equiprobables, Podemos
llegar a la fórmula del caso =1 aplicando la regla de
L’Hôpital al límite para 1 de la fórmula del caso 1
Si hacemos k, llegamos al modelo M | M | 1
Medidas de rendimiento


Tasa efectiva de llegadas, ef, Es el número medio
de clientes admitidos al sistema por unidad de
tiempo de entre los  que intentan entrar (ef<):
 ef   1  p k 
Número medio de clientes en el sistema (este
valor siempre debe ser inferior a k):
 
k  1 k  1

, si   1

k 1
1  
1 
L 
k
, si   1
 2
Medidas de rendimiento

Podemos obtener las demás medidas de
rendimiento mediante razonamientos ya
vistos, teniendo en cuenta que la tasa
efectiva de llegadas al sistema es ef:
W  Wq 
L q   ef W q
1

L   ef W
Ejemplo


A un taller mecánico llegan vehículos para el cambio de
pastillas de freno, Los coches llegan a un promedio de
18 a la hora según un proceso de Poisson, El espacio
físico del taller sólo permite que haya 4 vehículos, y las
ordenanzas municipales prohíben esperar fuera, El taller
puede servir a un promedio de 6 coches por hora de
acuerdo a una distribución exponencial,
Parámetros del sistema:  = 18 vehículos/h,  = 6
vehículos/h, k = 4 vehículos
 
18
6
3
Ejemplo

¿Cuál es la probabilidad de que no haya ningún vehículo
en el taller?
p0 


0
1   
1 
4 1

1 3
1 3
4 1
2

 242
1

 0,00826446
121
¿Cuál es el promedio de vehículos que hay en el taller?
L

1 
3
2


k  1   k  1
1 
1215
 242

k 1
426
121

3
1 3

 3,5206611
4  13 4  1
1 3
4 1
vehículos

Ejemplo

¿Cuánto tiempo pasa por término medio un
coche en el taller?
 ef
k

 1    

  1  p k     1 
k 1 
1 


4

3  2   720

18  1 
 5,950413
5


1  3  121

W 
L
 ef
clientes/h
426
426
71
121



 0,5916666
720
720
120
121
horas
Ejemplo

¿Cuánto tiempo esperan por término medio en la
cola los coches?
Wq  W 

1


71
120

1
6

17
 0 , 425 horas
40
¿Cuál es la longitud media de la cola?
720 17
306
L q   ef W q 
·

 2,52893
121 40
121
vehículos
Redes de colas
Redes de colas


Una red de colas es un sistema donde
existen varias colas y los trabajos van
fluyendo de una cola a otra
Ejemplos:




Fabricación (trabajos=artículos)
Oficinas (trabajos=documentos)
Redes de comunicaciones (trabajos=paquetes)
Sistemas operativos multitarea (trabajos=tareas)
Enrutado de trabajos

Criterios para decidir a qué cola se dirige un
trabajo que acaba de salir de otra:


Probabilístico: se elige una ruta u otra en función
de una probabilidad (puede haber distintos tipos
de trabajos, cada uno con sus probabilidades)
Determinista: cada clase de trabajo se dirige a
una cola fija
Tipos de redes de colas

Se distinguen dos tipos de redes de colas:

Abiertas: Cada trabajo entra al sistema en un
momento dado, y tras pasar por una o más colas,
sale del sistema, Dos subtipos:



Acíclicas: Un trabajo nunca puede volver a la misma
cola (no existen ciclos)
Cíclicas: Hay bucles en la red
Cerradas: Los trabajos ni entran ni salen del
sistema, Por lo tanto permanecen circulando por
el interior del sistema indefinidamente,
Usualmente existe un número fijo de trabajos,
Red abierta acíclica
Red abierta cíclica
Red cerrada
Redes de Jackson
abiertas
Definición

Una red de colas abierta se dice que es de Jackson
sii:





Sólo hay una clase de trabajos
Los enrutados son probabilísticos, donde rij  0 es la
probabilidad de ir al nodo j después de haber salido del
nodo i, Por otro lado, ri0 es la probabilidad de abandonar
del sistema después de haber salido del nodo i, donde ri0 =
1– ∑jrij
Cada nodo i es una cola .|M|ci
La tasa de llegadas externas al nodo i se notará i
El número total de nodos de la red se notará K
Ecuaciones de equilibrio

Dado que el flujo total de entrada a un nodo
debe ser igual al flujo total de salida del
nodo, tendremos que:
K
i  i 
  j r ji ,
 i  1,..., K 
j 1

Las K ecuaciones anteriores forman un
sistema lineal con solución única, que
resolveremos para hallar las tasas de
llegada a cada nodo i
Condición de no saturación

Para que ninguna de las colas del sistema se
sature, es preciso que se cumpla la siguiente
condición:
 i  1, 2 ,..., K ,

 i  1,
donde
i 
i
ci  i
Nota: Se trata de la condición de no
saturación del modelo M|M|c, aplicada a
cada uno de los nodos por separado
Teorema de Jackson para
redes abiertas

Teorema: Sea una red de Jackson abierta que
cumple la condición de no saturación, Entonces en
el estado estacionario, la distribución del número de
clientes en cada nodo es la que sigue:
K
p (n ) 

p i ( n i ),
 n1 ,
, nK  0
i 1
donde pi(ni) es la probabilidad de que haya ni clientes
en el nodo i, calculada según las ecuaciones del
modelo M|M|c
Consecuencias del teorema

Corolario: Las medidas de rendimiento para
cada nodo se calculan según las ecuaciones
del modelo M|M|c, Además se tendrán las
siguientes medidas:

Tasa global de salidas del sistema (throughput),
que es el número medio de trabajos que salen del
sistema por unidad de tiempo, Coincide con el
número de trabajos que entran en el sistema:
K
 red    i
i 1
Consecuencias del teorema

Número medio de trabajos en el sistema, Lred,
que es la suma de los número medios de
trabajos en cada uno de los nodos:
K
L red   Li
i 1

Tiempo medio en el sistema, Wred, que es el
tiempo medio que pasa una tarea desde que
entra en la red hasta que sale de ella:
W red 
L red
 red
Consecuencias del teorema

Razón de visitas al nodo i, Vi, que es el número
medio de veces que un trabajo visita el nodo i
desde que entra en la red hasta que sale:
 i  1, 2 ,..., K ,
Vi 
i
 red
Nota: en una red acíclica habrá de cumplirse que
Vi1 i{1,2,,,,,K}, ya que cada tarea visitará
cada nodo a lo sumo una vez
Ejemplo (red acíclica)
1,5
1
2
4
3
5
0,5
6
i  2
 i  1, 2,.., 6
Ejemplo (red acíclica)

Ecuaciones de equilibrio:
1  1;
 4   3 r 34 ;

 2   1 r12 ;
 3   1 r13 ;
 5   3 r 35   6 r65 ;
6  6
En el ejemplo, 1=1,5; r12=0,2; r13=0,8; r34=0,6; r35=0,4;
6=0,5; r65=1; con lo cual la solución es:
 1  1, 5;
 4  0, 72;
 2  0, 3;
 5  0, 98;
 3  1, 2;
 6  0, 5
Ejemplo (red acíclica)

Condición de no saturación (se cumple porque i<1):
i 
i

i
 1  0, 75;
 4  0, 36;

 2  0,15;
 5  0, 49;
 3  0, 6;
 6  0, 25
Medidas de rendimiento (ecuaciones del modelo M|M|1):
Li 
i
1  i

L1  3;
L4  0, 5625;
L2  0,1764;
L5  0, 9607;
L3  1, 5;
L6  0, 3333
Ejemplo (red acíclica)
Wi 
1
 i  i
W1  2;

W 4  0, 78125;
W qi  W i 
1
i

W 5  0, 9803;
W q 1  1, 5;
W q 4  0, 28125;
W 2  0, 5882;
W 3  1, 25;
W 6  0, 6666
W q 2  0, 0882;
W q 5  0, 4803;
W q 3  0, 75;
W q 6  0,1666
Red abierta cíclica
0,2
1
2
4
0,8
3
5
i  3
 i  1, 2, 4 
i  4
 i  3, 5
0,6
Ejemplo (red cíclica)

Ecuaciones de equilibrio:
1  1;
 2   1 r12 ;
 4   3 r 34 ;

 3   3   1 r13   5 r53 ;
 5   3 r 35
En el ejemplo, 1=0,2; r12=0,3; r13=0,7; 3=0,8; r53=0,6;
r34=0,1; r35=0,9; con lo cual la solución es:
 1  0, 2;
 2  0, 06;
 4  0, 2043;
 3  2, 0434;
 5  1,8391
Ejemplo (red cíclica)

Condición de no saturación (se cumple porque i<1):
i 
i
i
 1  0, 0666;

 4  0, 0681;

 2  0, 02;
 3  0, 5108;
 5  0, 4597
Medidas de rendimiento (ecuaciones del modelo M|M|1):
Li 
i
1  i

L1  0, 0714;
L4  0, 0731;
L2  0, 0204;
L5  0,8511
L3  1, 0443;
Ejemplo (red cíclica)
Wi 
1
 i  i

W1  0, 3571;
W 4  0, 3576;
W qi  W i 
1
i

W 2  0, 3401;
W 5  0, 4627
W q 1  0, 0238;
W q 4  0, 0243;
W 3  0, 5111;
W q 2  0, 0068;
W q 5  0, 2127
W q 3  0, 2611;
Redes de Jackson
cerradas
Definición

Una red de colas cerrada se dice que es de
Jackson sii:





Sólo hay una clase de trabajos
Los enrutados son probabilísticos, donde rij  0 es la
probabilidad de ir al nodo j después de haber salido del
nodo i,
Cada nodo i es una cola .|M|ci
Hay una cantidad constante M de trabajos en el sistema
El número total de nodos de la red se notará K
Ecuaciones de equilibrio

Dado que el flujo total de entrada a un nodo debe
ser igual al flujo total de salida del nodo, tendremos
que:
K
 
*
i
  j r ji ,
*
 i  1,..., K 
j 1

Las K ecuaciones anteriores forman un sistema
lineal indeterminado con un grado de libertad, que
resolveremos para hallar las tasas de llegada
relativas a cada nodo i*, Para ello fijaremos un
valor positivo arbitrario para una incógnita, por
ejemplo 1*=1
Análisis del valor medio

Hallaremos las siguientes medidas de
rendimiento para M tareas en el sistema:




Li(M)=Número medio de tareas en el nodo i
Wi(M)=Tiempo medio que cada tarea pasa en el
nodo i cada vez que lo visita
i(M)=Tasa real de salidas del nodo i
Se trata de un algoritmo iterativo que va
calculando Li(m), Wi(m) para valores
crecientes de m a partir de m=0
Análisis del valor medio

Las ecuaciones son:
W j (m ) 
1
j
L j ( m  1)

c j j
 jW j ( m )
,
 j  1,..., K   m  1,..., M

,
 j  1,..., K   m  1,..., M

*
L j (m )  m
 i 1  W i ( m )
 j (m ) 
K
*
i
L j (m )
W j (m )
,
 j  1, ..., K   m  1, ..., M 
L j (0 )  0,  j  1,..., K 
Red cerrada
1
2
3
1
4
1
i  5
 i  1, 2,.., 6
Ejemplo (red cerrada)

Ecuaciones de equilibrio:
 1   3 r31   4 r41 ;
*
*
*
 3   2 r23 ;
*

 2   1 r12 ;
*
*
 4   1 r 14
*
*
*
En el ejemplo, r12=0,3; r14=0,7; r23=1; r31=1; r41=1; con lo
cual la solución es, tomando 1*=1:
 1  1;
*
 3  0, 3;
*
 2  0, 3;
*
 4  0, 7
*
Ejemplo (red cerrada)
W j (m ) 
L1 ( m )  m
L2 ( m )  m
L3 ( m )  m
L4 ( m )  m
1  L j ( m  1)
5
,
 j  1, ..., 4 
W1 ( m )
W 1 ( m )  0, 3  W 2 ( m )  0, 3  W 3 ( m )  0, 7  W 4 ( m )
0, 3  W 2 ( m )
W 1 ( m )  0, 3  W 2 ( m )  0, 3  W 3 ( m )  0, 7  W 4 ( m )
0, 3  W 3 ( m )
W 1 ( m )  0, 3  W 2 ( m )  0, 3  W 3 ( m )  0, 7  W 4 ( m )
0, 7  W 4 ( m )
W 1 ( m )  0, 3  W 2 ( m )  0, 3  W 3 ( m )  0, 7  W 4 ( m )
Ejemplo (red cerrada)

Primera iteración:
L j (0 )  0,  j  1, ..., 4   W j (1) 
L1 (1)  1 
L 2 (1)  1 
L3 (1)  1 
L 4 (1)  1 
0, 2
2, 3  0, 2
0, 3  0, 2
2, 3  0, 2
0, 3  0, 2
2, 3  0, 2
0, 7  0, 2
2, 3  0, 2
1  L j (0 )
5
 0,4347
 0,1304
 0,1304
 0,3043
 0, 2
 j  1, ..., 4 
Ejemplo (red cerrada)
m
W1(m)
W1(m)
W1(m)
W1(m)
L1(m)
L2(m)
L3(m)
L4(m)
0
--
--
--
--
0
0
0
0
1
0,2
0,2
0,2
0,2
0,4348
0,1304
0,1304
0,3043
2
0,2870
0,2261
0,2261
0,2609
0,9483
0,2241
0,2241
0,6034
3
0,3897
0,2448
0,2448
0,3207
1,5360
0,2895
0,2895
0,8849
4
0,5072
0,2579
0,2579
0,3770
2,1913
0,3343
0,3343
1,1401
5
0,6383
0,2669
0,2669
0,4280
2,9065
0,3646
0,3646
1,3644
6
0,7813
0,2729
0,2729
0,4729
3,6737
0,3850
0,3850
1,5564
7
0,9347
0,2770
0,2770
0,5113
4,4852
0,3987
0,3987
1,7173
Ejemplo (red cerrada)
L
16
14
Cola 1
12
10
8
6
4
Cola 4
2
Colas 2 y 3
0
0
2
4
6
8
10
12
14
16
18
20
m
Ejemplo (red cerrada)
W
3.5
3
Cola 1
2.5
2
1.5
1
Cola 4
Colas 2 y 3
0.5
0
0
2
4
6
8
10
12
14
16
18
20
m
Ejemplo (red cerrada)
Utilización
del
servidor (%)
U=/=
L/(W)
100
Cola 1
90
80
70
Cola 4
60
50
40
30
20
10
Colas 2 y 3
0
2
4
6
8
10
12
14
m
16
18
20
Cuellos de botella



Un cuello de botella en un sistema de colas es un
nodo cuya capacidad de procesamiento determina
el rendimiento de todo el sistema
Definición: Sea una red de Jackson cerrada.
Diremos que el nodo j es un cuello de botella sii
Lj(m) cuando m
En el ejemplo anterior el nodo 1 es un cuello de
botella. Trabaja al límite de su capacidad mientras
que los otros no (se quedan al 30% o al 70%). Para
mejorar el rendimiento global del sistema habría que
aumentar la capacidad de procesamiento del nodo
1
Descargar

Tema 4: Cadenas de Markov - Departamento de Lenguajes y