Í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.

 

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.

 

 

                     

   Anterior          Índice          Siguiente

Para mayor información, seleccione una opción:

Número de visitas efectuadas desde el 17/12/2001: 
 
Estadísticas diarias desde el 10/07/2002:    

Número de visitantes actuales disponible desde el 14/07/2002:

 

AddFreeStats.com Free Web Stats in real-time !  

 

 

 

Autor: lrmdavid@exa.unne.edu.ar

Ó FACENA - http://exa.unne.edu.ar

Servicios WEB: webmaster@exa.unne.edu.ar