En la teoría de colas , una disciplina dentro de la matemática teoría de la probabilidad , un M / G / 1 cola es un modelo de cola donde las llegadas son M arkovian (modulada por un proceso de Poisson ), los tiempos de servicio tienen un G eneral distribución y hay un único servidor . [1] El nombre del modelo está escrito en notación de Kendall y es una extensión de la cola M / M / 1 , donde los tiempos de servicio deben distribuirse exponencialmente . La aplicación clásica de la cola M / G / 1 es modelar el rendimiento de un disco duro de cabezal fijo . [2]
Definición de modelo
Una cola representada por una cola M / G / 1 es un proceso estocástico cuyo espacio de estado es el conjunto {0,1,2,3 ...}, donde el valor corresponde al número de clientes en la cola, incluido cualquier ser servido. Las transiciones del estado i al i + 1 representan la llegada de un nuevo cliente: los tiempos entre dichas llegadas tienen una distribución exponencial con el parámetro λ. Las transiciones del estado i al i - 1 representan a un cliente que ha sido atendido, terminando de ser atendido y partiendo: el tiempo necesario para atender a un cliente individual tiene una función de distribución general. Los períodos de tiempo entre llegadas y períodos de servicio son variables aleatorias que se supone que son estadísticamente independientes .
Políticas de programación
Los clientes que generalmente se ofrecen en un primer llegado, primer servido base, otras políticas de planificación populares incluyen
- Procesador compartido donde todos los trabajos en la cola comparten la capacidad de servicio entre ellos por igual
- el último en llegar, el primero en ser atendido sin preferencia cuando un trabajo en servicio no se puede interrumpir
- último llegado, primero servido con preferencia cuando un trabajo en servicio es interrumpido por llegadas tardías, pero el trabajo se conserva [3]
- Programación generalizada de primer plano y fondo (FB), también conocida como servicio menos logrado, en la que los trabajos que han recibido el menor tiempo de procesamiento hasta ahora se atienden primero y los trabajos que han recibido la misma capacidad de servicio de tiempo compartido de servicio utilizando el uso compartido de procesador [3]
- trabajo más corto primero sin preferencia (SJF) donde el trabajo con el tamaño más pequeño recibe servicio y no se puede interrumpir hasta que se complete el servicio
- primero el trabajo preventivo más corto en el que en cualquier momento se entrega el trabajo con el tamaño de original más pequeño [4]
- el tiempo de procesamiento restante más corto (SRPT) en el que el siguiente trabajo a entregar es el que tiene el requisito de procesamiento restante más pequeño [5]
Las políticas de servicio a menudo se evalúan comparando el tiempo medio de permanencia en la cola. Si los tiempos de servicio que requieren los trabajos se conocen a la llegada, la política de programación óptima es SRPT. [6] : 296
Las políticas también se pueden evaluar utilizando una medida de equidad. [7]
Longitud de la cola
Método Pollaczek-Khinchine
La función generadora de probabilidad de la distribución de la longitud de la cola estacionaria viene dada por la ecuación de la transformada de Pollaczek-Khinchine [2]
donde g ( s ) es la transformada de Laplace de la función de densidad de probabilidad de tiempo de servicio. [8] En el caso de una cola M / M / 1 donde los tiempos de servicio se distribuyen exponencialmente con el parámetro μ , g ( s ) = μ / ( μ + s ).
Esto se puede resolver para las probabilidades de estados individuales mediante cálculo directo o mediante el método de variables complementarias . La fórmula de Pollaczek – Khinchine proporciona la longitud media de la cola y el tiempo medio de espera en el sistema. [9] [10]
Método analítico matricial
Considere la cadena de Markov incrustada de la cola M / G / 1, donde los puntos de tiempo seleccionados son inmediatamente posteriores al momento de la salida. El cliente que está siendo atendido (si hay uno) ha recibido cero segundos de servicio. Entre salidas, puede haber 0, 1, 2, 3, ... llegadas. Entonces, desde el estado i, la cadena puede moverse al estado i - 1, i , i + 1, i + 2, .... [11] La cadena de Markov incrustada tiene una matriz de transición
dónde
y F ( u ) es la distribución del tiempo de servicio y λ la tasa de llegada de trabajos de Poisson a la cola.
Las cadenas de Markov con matrices generadoras o matrices de bloques de esta forma se denominan cadenas de Markov de tipo M / G / 1, [12] término acuñado por MF Neuts. [13] [14]
Una cola M / G / 1 tiene una distribución estacionaria si y solo si la intensidad del tráfico es menor que 1, en cuyo caso la única distribución tiene una función generadora de probabilidad : [15]
dónde es la función generadora de momentos de un tiempo de servicio general. La distribución estacionaria de un modelo de Markov de tipo M / G / 1 se puede calcular utilizando el método analítico matricial . [dieciséis]
Periodo ocupado
El período ocupado es el tiempo transcurrido en los estados 1, 2, 3, ... entre visitas al estado 0. La duración esperada de un período ocupado es 1 / (μ − λ) donde 1 / μ es la duración esperada del servicio tiempo y λ la tasa del proceso de Poisson que rige las llegadas. [17] La función de densidad de probabilidad del período ocupado puede demostrarse que obedece a la ecuación funcional de Kendall [18] [19] : 92
donde g es la transformada de Laplace-Stieltjes de la función de distribución del tiempo de servicio. Esta relación solo se puede resolver exactamente en casos especiales (como la cola M / M / 1 ), pero para cualquier s se puede calcular el valor de ϕ ( s ) y, mediante iteración con los límites superior e inferior, la función de distribución se calcula numéricamente. [20]
Tiempo de espera / respuesta
Escribir W * ( s ) para la transformada de Laplace-Stieltjes de la distribución del tiempo de espera, [21] viene dada por la transformada de Pollaczek-Khinchine como
donde g ( s ) es la transformada de Laplace-Stieltjes de la función de densidad de probabilidad de tiempo de servicio.
Teorema de llegada
Como las llegadas están determinadas por un proceso de Poisson, el teorema de la llegada se cumple.
Varios servidores
Muchas métricas para la cola M / G / k con k servidores siguen siendo un problema abierto, aunque se conocen algunas aproximaciones y límites.
Ver también
- Cola M / M / 1
- Cola M / M / c
Referencias
- ^ Gittins, John C. (1989). Índices de asignación de bandidos de varios brazos . John Wiley e hijos. pag. 77. ISBN 0471920592.
- ^ a b Harrison, Peter ; Patel, Naresh M. (1992). Modelado de rendimiento de redes de comunicación y arquitecturas informáticas . Addison – Wesley.
- ^ a b Harchol-Balter, M. (2012). "Programación: políticas preventivas, no basadas en tamaño". Modelado y Diseño de Performance de Sistemas Computacionales . pag. 482. doi : 10.1017 / CBO9781139226424.038 . ISBN 9781139226424.
- ^ Harchol-Balter, M. (2012). "Programación: políticas preventivas basadas en el tamaño". Modelado y Diseño de Performance de Sistemas Computacionales . pag. 508. doi : 10.1017 / CBO9781139226424.040 . ISBN 9781139226424.
- ^ Harchol-Balter, M. (2012). "Programación: SRPT y equidad". Modelado y Diseño de Performance de Sistemas Computacionales . pag. 518. doi : 10.1017 / CBO9781139226424.041 . ISBN 9781139226424.
- ^ Gautam, Natarajan (2012). Análisis de colas: métodos y aplicaciones . Prensa CRC. ISBN 9781439806586.
- ^ Wierman, A .; Harchol-Balter, M. (2003). "Clasificación de las políticas de programación con respecto a la injusticia en un M / GI / 1" (PDF) . Revisión de la evaluación del desempeño de ACM SIGMETRICS . 31 : 238. doi : 10.1145 / 885651.781057 .
- ^ Peterson, GD; Chamberlain, RD (1996). "Rendimiento de aplicaciones en paralelo en un entorno de recursos compartidos" . Ingeniería de Sistemas Distribuidos . 3 : 9-19. doi : 10.1088 / 0967-1846 / 3/1/003 .
- ^ Pollaczek, F. (1930). "Über eine Aufgabe der Wahrscheinlichkeitstheorie". Mathematische Zeitschrift . 32 : 64–75. doi : 10.1007 / BF01194620 .
- ^ Khintchine, A. Y (1932). "Teoría matemática de una cola estacionaria" . Matematicheskii Sbornik . 39 (4): 73–84 . Consultado el 14 de julio de 2011 .
- ^ Stewart, William J. (2009). Probabilidad, cadenas de Markov, colas y simulación . Prensa de la Universidad de Princeton. pag. 510 . ISBN 0-691-14062-6.
- ^ Neuts, Marcel F. (1981). Soluciones matrices-geométricas en modelos estocásticos: un enfoque algorítmico (Estudios de Johns Hopkins en Ciencias Matemáticas) . Prensa de la Universidad Johns Hopkins . pag. 2. ISBN 0-486-68342-7.
- ^ Neuts, M. F. (1989). "Matrices estocásticas estructuradas de tipo M / G / 1 y sus aplicaciones". Nueva York: Marcel Dekk. Cite journal requiere
|journal=
( ayuda ) - ^ Meini, B. (1998). "Resolución de cadenas de markov tipo m / g / l: avances y aplicaciones recientes". Comunicaciones en estadística. Modelos estocásticos . 14 : 479–496. doi : 10.1080 / 15326349808807483 .
- ^ Grimmett, GR ; Stirzaker, DR (1992). Probabilidad y procesos aleatorios (segunda ed.). Prensa de la Universidad de Oxford. pag. 422. ISBN 0198572220.
- ^ Bini, DA; Latouche, G .; Meini, B. (2005). "Métodos numéricos para cadenas de Markov estructuradas". doi : 10.1093 / acprof: oso / 9780198527688.001.0001 . ISBN 9780198527688. Cite journal requiere
|journal=
( ayuda ) - ^ Ross, Sheldon M .; Seshadri, Sridhar (1999). "Golpear el tiempo en una cola M / G / 1" (PDF) . Revista de probabilidad aplicada . 36 : 934–940. doi : 10.1239 / jap / 1029349991 . JSTOR 3215453 .
- ^ Abate, J .; Choudhury, GL; Whitt, W. (1995). "Cálculo de la densidad del período ocupado M / G / 1 y la distribución del tiempo de espera LIFO por inversión de transformación numérica directa" (PDF) . Cartas de investigación operativa . 18 (3): 113-119. doi : 10.1016 / 0167-6377 (95) 00049-6 .
- ^ Mitrani, I. (1997). "Sistemas de colas: rendimiento medio". Modelado probabilístico . Prensa de la Universidad de Cambridge. págs. 74-121. doi : 10.1017 / CBO9781139173087.004 . ISBN 9781139173087.
- ^ Abate, J .; Whitt, W. (1992). "Resolución de ecuaciones funcionales de transformación de probabilidad para inversión numérica" (PDF) . Cartas de investigación operativa . 12 (5): 275-281. doi : 10.1016 / 0167-6377 (92) 90085-H .
- ^ Daigle, John N. (2005). "El sistema de colas básico M / G / 1". Teoría de las colas con aplicaciones a las telecomunicaciones por paquetes . pp. 159 -223. doi : 10.1007 / 0-387-22859-4_5 . ISBN 0-387-22857-8.