ÍNDICE
Temas
pág.
Introducción al modelado analítico y
teoría de colas...................................................2
Fuente,
Llegadas y Llegadas de
Poisson.........................................................................3
Llegadas
de
Poisson...........................................................................................................3
Tiempos
de servicio, capacidad de la cola y número de servidores en el
sistema.................................................................................................................................4
Disciplinas
de colas
...........................................................................................................5
Intensidad
de tráfico y utilización del
servidor............................................................ 6
Estado
estable en función de soluciones transitorias
resultado de Little ..................7
Resumen del proceso de
Poisson.....................................................................................8
Análisis
de un sistema de colas M/M/1............................................................
9
Análisis
de un sistema de colas M/M/C......................................................................
10
Procesos
de
Markov.........................................................................................................
11
Procesos
de nacimiento y muerte....................................................................................12
Análisis
del rendimiento de un subsistema de
disco....................................................12
INTRODUCCION AL MODELADO ANALITICO Y
TEORIA DE COLAS
LAS TECNICAS DEL MODELADO
ANALITICO SON:
·
LA
TEORIA DE COLAS.
·
LOS
PROCESOS DE MARKOV
Los
modelos analíticos:
§
Son
las representaciones matemáticas de los sistemas.
§
Permiten al evaluador del
rendimiento sacar conclusiones acerca del comportamiento del sistema.
El
término matemático Cola significa una línea de espera.
Las colas pueden
ser:
§
Limitadas: solo pueden contener
un número fijo de clientes en espera y quizás hasta ninguna.
§
Ilimitadas: pueden crecer tanto como sea necesario para contener a los
clientes que esperan.
FUENTE, LLEGADAS Y
LLEGADAS DE POISSON
FUENTES: los
clientes son proporcionados a un sistema de colas desde una fuente que puede
ser:
§
FINITA: para una fuente finita la cola de servicio puede ser limitada.
§
INFINITA: la cola de servicio puede
llegar a ser arbitrariamente grande.
LLEGADAS: los clientes llegan de uno en uno y nunca hay una colisión.
§
Tk
se denomina "TIEMPOS ENTRE LLEGADAS" :son variables aleatorias
independientes y estan idénticamente distribuidas.
§
Tk = Tk - Tk -1 , con (k >1).
LLEGADAS DE POISSON.
Las llegadas pueden seguir
distintos patrones arbitrarios que forman un proceso de llegadas de Poisson:
§
Los
tiempos entre llegadas están distribuidos exponencialmente:
P(t ≤ t) = 1
- e-λt
§
La
probabilidad de que lleguen exactamente n clientes en cualquier intervalo de
longitud t es:
[e-λt(λt)n]
/ n! (n = 0, 1, 2, ...).
§
l Es una tasa promedio de llegadas constante expresada en
“clientes por unidad de tiempo”.
TIEMPOS DE SERVICIO, CAPACIDAD DE LA COLA Y NUMERO
DE SERVIDORES EN EL SISTEMA
TIEMPOS
DE SERVICIO: Se
supone que los tiempos de servicio son aleatorios.
“sk” es el tiempo de servicio que el k-esimo
cliente requiere del sistema.
Un tiempo de servicio arbitrario se designa por “s”.
La distribución de los tiempos de servicio es:
Ws (t) = p(s ≤ t).
Para un servicio aleatorio con una tasa promedio de
servicio “m”:
Ws
(t) = p(s ≤
t) = 1 - e-mt (t
≥ 0).
CAPACIDAD DE LA COLA.
§
Capacidad infinita: cada cliente que llegue puede
entrar en el sistema de colas y
esperar, independientemente de cuantos clientes hay en espera
§
Capacidad cero: los clientes que
llegan cuando la instalación de servicio esta ocupada no podran ser admitidos.
§
Capacidad positiva: los clientes que llegan solo
esperan si hay lugar en la cola
NUMERO DE SERVIDORES EN
EL SISTEMA.
Los sistemas de colas se pueden categorizar según el n° de
servidores en:
·
sistemas
de un solo servidor: tiene un solo servidor y solo dan servicio a un solo
cliente.
- sistemas de servidores múltiples: tienen
C servidores con idéntica capacidad y pueden dar servicio a C clientes a
la vez.
DISCIPLINAS DE COLAS
Son las reglas usadas para elegir al siguiente cliente de
cola que va a ser servido.
Generalmente
se utilizan las siguientes notaciones:
·
Notación kendall: A: distribución de tiempos entre llegadas.
B: distribución de tiempos de servicio.
C: n° de servidores.
K: capacidad de cola del sistema.
M: n° de clientes en la fuente.
Z: disciplina de cola.
·
Notación kendall Abreviada: no hay limite en la longitud de la cola.
La fuente es infinita.
La disciplina de cola es “fcfs”.
“a” y “b” pueden ser:
Gi: para tiempo entre llegadas
general independiente.
G: para tiempo de servicio
general.
Ek: para las
distribuciones de tiempos entre llegadas o de servicio erlang-k.
M: para las distribuciones de
tiempos entre llegadas o de servicio exponenciales.
D: para las distribuciones de
tiempos entre llegadas o de servicio deterministicos.
Hk:
para las distribuciones de tiempos entre llegadas o de servicio
hiperexponenciales (con “k” estados).
INTENSIDAD DE TRAFICO Y UTILIZACION
DEL SERVIDOR
INTENSIDAD DEL TRÁFICO
Es una medida de la
capacidad del sistema para dar servicio efectivo a sus clientes.
Se define como la Razón
de la Media del Tiempo de Servicio E(s) y la Media del Tiempo entre
Llegadas E(r).
INTENSIDAD DE TRAFICO “u” ES:
u = [E(s)] / [E(t)] =
E(s) = (λ / m):
λ: TASA DE
LLEGADAS.
m: TASA DE SERVICIO.
UTILIZACION DEL SERVIDOR
Se
define como la intensidad de trafico por servidor:
r = u / c = λ / (m c).
Es la
probabilidad de que un servidor determinado se encuentre ocupado.
En
sistemas de un solo servidor es igual a la intensidad de tráfico.
ESTADO ESTABLE EN FUNCION DE SOLUCIONES TRANSITORIAS
RESULTADO DE LITTLE
n
Estado
estable en función de soluciones transitorias: los sistemas de Colas que se han
asentado se dice que están operando en estado estable.
La operación inicial de un sistema no es
indicativa de su comportamiento periódico. Los sistemas de colas deben pasar
por un periodo inicial de operación antes de tener un funcionamiento :
·
Uniforme
·
Predecible
§
Resultado
deLittle: es
una de las mediciones mas sencillas y útiles del rendimiento de un sistema de
colas.
Relaciona las siguientes cantidades:
Wq: tiempo medio que
emplea un cliente en una cola.
λ: tasa de llegadas.
Lq: n° de clientes en la cola.
W: tiempo medio que emplea un
cliente en el sistema.
L: n° de clientes en el sistema.
el
resultado de Llittle se expresa como:
Lq
= λ
Wq
L = λ W
RESUMEN
DEL PROCESO DE POISSON
Un
proceso es de Poisson si y solo si:
Para
intervalos apropiadamente pequeños dt:
·
P(k,t) = :
λDt
para k = 1 (λ )es la tasa
promedio de llegadas.
1 - λDt
PARA k = 0.
0 PARA k > 1.
Si la
variable aleatoria “k” indica el n° de llegadas:
·
La
probabilidad de, exactamente, “k”
llegadas en un intervalo de longitud “t” es:
P(k,t) = [(λt)k
e-λt] / k! t
≥ 0; k = 0, 1, 2, ...
·
El
valor esperado o valor medio de k es:
E(k) = λ t.
·
La
varianza de k es:
(sk)2
= λ t.
ANALISIS DE UN SISTEMA DE COLAS M/M/1
Formulas de estado para el
sistema de colas m/m/c:
·
Intensidad
de trafico:
u
= λl
/ m = λ
E(s).
·
Utilización
del servidor:
r
= u / c.
·
Tiempo
Promedio en la Cola:
Wq = [C(c,u) E(s)] / [c (1 -
r)].
·
Tiempo
Promedio en el Sistema:
W
= Wq + E(s).
- Se
deducen de las anteriores:
·
C(c,u)
= r = λ E(s).
·
Wq = [r
E(s)] / (1 - r).
·
W = E(s) / (1 - r).
·
pq(90) =
W [ln(10 r)].
Conclusión:
·
Un solo equipo no es suficiente
para hacer frente a las necesidades de los operadores sin provocar esperas
excesivas.
ANALISIS
DE UN SISTEMA DE COLAS M/M/C
Si la
decisión es adquirir mas equipos, los interrogantes son los siguientes:
¿cuántos equipos adicionales
deberán adquirirse para mantener el percentil 90 de tiempo en espera por debajo
de 10 minutos?.
¿deberán mantenerse todos los
equipos en un lugar central, o deberán
distribuirse por todo el edificio?.
Colocando
los equipos en diferentes lugares de la empresa:
- Colocando
1, 2, 3, 4 o 5 equipos en localidades separadas obtenemos los siguientes
valores:
n
Utilización del servidor: r: 2/3;
1/3; 2/9; 1/6 y 2/15.
n
Tiempo
de Espera de servicio: e(s): 20 minutos en todos los casos.
n
Tiempo de Espera en la cola: wq:
40; 10; 5,7; 4 y 3,1 minutos.
n
Tiempo de espera en el sistema:
w: 60; 30; 25,7; 24 Y 23 minutos.
n
Percentil 90 de tiempo de espera
en la cola: pq(90): 113,8; 36,1; 20,5; 12,3 y 6,6 minutos.
Conclusiones:
·
Los tiempos de espera en la cola
bajan muy rápido tan pronto como se añade el segundo equipo M/M/1.
·
El Percentil 90 de tiempo de espera en la cola es superior a 10 min.
Hasta que se añade el quinto equipo.
- Utilizando
las formulas de los sistemas m/m/c se obtienen los siguientes valores:
·
Intensidad de trafico: u: 2/3.
·
utilizacion del servidor: r: 1/3.
·
probabilidad de que todos los
servidores se encuentren en este momento
en uso, por lo que un cliente que llega debe esperar: c(c,u): 1/6.
·
tiempo promedio en la cola: wq:
2,5 minutos.
·
tiempo promedio en el sistema: w:
22,5 minutos.
·
percentil 90 de tiempo de espera
en la cola: pq(90): 7,66 minutos.
Conclusiones:
·
Con solo 2 equipos centralizados
en una posición se pueden eliminar los problemas de espera del sistema de un
solo equipo.
·
para asegurar un percentil 90 de
tiempo de espera en la cola inferior a 10 minutos serán necesarios:
·
5
equipos m/m/1 distribuidos, o.
·
2
equipos en una configuracion m/m/2 central.
PROCESOS DE MARKOV
Es un
modelo adecuado para describir el comportamiento de sistemas donde:
n
El sistema esta
situado en uno de un conjunto de estados discretos mutuamente excluyentes y
colectivamente exhaustivos s0,s1, s2,...., sn.
El
estado presente del sistema y las probabilidades de transicion entre varios
estados del sistema:
·
Caracterizan
el comportamiento futuro del sistema, este comportamiento no depende de su
historia anterior a su entrada a ese estado.
·
Un
cambio de estado en un proceso de Markov de transición continua puede producir
cambios de estado en cualquier instante de una escala de tiempo continua.
PROCESOS DE NACIMIENTO Y MUERTE
Son un
caso importante de los procesos de Markov.
Son
particularmente aplicables al modelado de sistemas de computación.
Un
proceso de Markov de nacimiento y muerte continuo tiene la propiedad de que:
λ ij = 0
si j ≠ i + 1
y j ≠ i - 1.
La
resolución de un proceso de nacimiento y muerte continuo significa determinar
los diferentes pi usando las relaciones:
pi + 1 = (bi / di + 1) pi.
∑ pi = 1.
ANALISIS DEL RENDIMIENTO DE UN SUBSISTEMA DE DISCO
Se
supone la siguiente situación:
·
las peticiones de acceso a disco llegan como un proceso de Poisson.
·
si el disco esta en uso la petición se
coloca en una cola primero en llegar primero en ser servido.
·
cuando el disco queda disponible se
sirve la primera petición de la cola.
·
el tiempo de servicio es una variable
aleatoria exponencialmente distribuida.
·
la tasa promedio de servicio es de u
peticiones por minuto.
Se debe
determinar, para c / u de los casos:
·
El valor esperado para el No. Total de
peticiones al disco pendientes.
·
Las
probabilidades del estado limite.
Caso
I:
ü
El
dispositivo de disco contiene un solo brazo.
ü
Solo
puede dar servicio a una petición a la vez.
ü
La
tasa de servicio es u.
Caso
II :
ü
El
dispositivo de disco contiene gran No. de brazos moviles.
ü
Cada
brazo puede dar servicio a una petición de disco.
ü
Se
supone que un No. finito de peticiones pueden recibir servicio paralelo.
Solución al Caso I :
ü
Sj
es el estado del sistema cuando hay j peticiones de disco al dispositivo
de servicio de disco.
ü
La
tasa de llegadas de peticiones independiente del estado del sistema: Si -> Si + 1.
Se considera al sistema como un proceso de
nacimiento y muerte continuo de cadena sencilla y estados infinitos con:
di =
0
i = 0.
di =
m
i = 1, 2, 3, ...
bi = λ i = 0, 1, 2, ...
Solo
una petición puede ser servida en un momento dado y se sirve a una tasa m.
m >
l.
Se
utilizan las relaciones:
pi + 1 = (bi / di + 1) pi. i = 0, 1, 2, ...
∑ pi = 1.
i
p1 = (λ
/ m) p0.
p2 = (λ
/ m) p1 = (λ
/ m)2 p0.
pi = (λ
/ m)i p0.
∑ pi = 1 = s (λ
/ m)i p0 =
1/ [1 - (λ / m)] p0
.
p0 = 1 - (λ / m): probabilidad de que el sistema se
encuentre ocioso.
pi = (λ / m)i p0
= [1 - (λ / m)] (λ / m)i. i = 0, 1, 2, ...
pi = [1 - (λ / m)] (λ / m)i:
probabilidad que hayan i peticiones pendientes
el n° promedio de peticiones pendientes es:
e(i) =∑ ipi = s i [1 - (λ
/ m)] (λ / m)i = [1 - (λ
/ m)] s i (λ
/ m)i =
e(i) = [1 - (λ
l / m)] ((λ
/ m) ∑ i (λ
/ m)i - 1 =
e(i) = [1 - (λ / m)] (λ / m) {1 /[1 - (λ / m)2]} =
e(i) = (λ / m) [1 - (λ / m)-1].
Solución
al Caso II:
ü La
probabilidad de que una petición en particular acabe siendo servida dentro del
siguiente At .
ü cualquiera
de las i peticiones puede terminar provocar un cambio de estado.
El sistema se ve como un proceso de nacimiento
y muerte continuo de cadena sencilla y de estados infinitos con:
bi =
l
i = 0, 1, 2, ...
di =
0
i = 0.
di =
im
i = 1, 2, 3, ...
Ningún cliente tiene que esperar ya que se suponen
infinitos servidores en paralelo.
- Se
utilizan las relaciones:
Pi + 1 = (bi / di + 1) Pi. i = 0, 1, 2, ...
∑ Pi = 1.
P1 = (λ / m) P0.
P2 = (λ
/ 2m) P1 = (1 / 2) (λ
/ m)2 P0.
P3 = (λ
/ 3m) P2 = (1 / (3 . 2)) (λ / m)3 P0.
Pi = (1 / i!) (λ / m)i P0.
∑ Pi = 1 = S (1 / i!) (λ /
m)i P0.
∑ (xn / n!) = ex.
n
∑ Pi = 1 = ∑ (1 / i!) (λ
/ m)i P0 = e λ / m P0.
i
i
P0 = e- λ / m .
Pi = (λ
/ m)i [(e- λ / m ) / i!].
E(i) =∑ iPi = ∑ i (λ /m)i
[(e- λ /m ) / i!] = (e-l / m ) ∑ i
(λ /m)i (1/i!) =
E(i) = (e- λ / m ) ∑ (λ
/ m) (λ / m)i - 1
[1 / (i - 1)!] =
E(i) = (e- λ / m ) (λ
/ m)
∑
[1 / (i - 1)!] (λ / m)i - 1 =
E(i) = (e- λ / m ) (λ
/ m) (e
λ / m ) =
E(i) = (λ / m).
Conclusiones :
ü
En el sistema de un solo servidor
si una petición que llega encuentra ocupado el dispositivo , debe esperar.
ü
En el sistema de
servidores infinitos las peticiones que llegan , entran al servicio de
inmediato.
ü
En el sistema de un
solo servidor las peticiones que llegan esperan.
ü
En el sistema de
servidores infinitos el No. promedio de peticiones pendientes tiende a 1.
