Tema 5: Teoría de colas

1 Tema 5: Teor a de colasEzequiel L pez RubioDepartamento de Lenguajes y Ciencias de la Computaci nUniversidad de M lagaSumariozConceptos b sicoszCola M | M | 1zCola M | M | czCola M | M | 1 | kzRedes de colaszRedes de Jackson abiertaszRedes de Jackson cerradasConceptos b sicosConcepto de colazUna cola es una l nea de espera para determinado serviciozEste servicio lo proporciona uno o varios dependienteszLa 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 colaszLlamaremos clientes, trabajos o tareas a los que demandan servicio, y dependientes, empleados o servidores a los que ofrecen serviciozUn sistema de colas viene dado por varias caracter sticas:z1 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 sucesivasClasificaci n de sistemas de colasz2 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 llegadaz3 Disciplina de la cola, Establece el orden en que se va atendiendo a los clientes:zPor orden de llegada (FIFO)zPor orden inverso al de llegada (LIFO)zSelecci n aleatoria (RANDOM)zSeg n prioridades (PRIORITY, PR), Dos subtipos.

2 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 colasz4 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,z5 N mero de canales de servicio, Es el n mero de dependientes, Puede haber una cola para cada dependiente o bien una sola cola globalz6 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 KendallzLa 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:zA es el modelo de llegadas, Valores posibles:zM=tiempos entre llegadas exponencialeszD=tiempos entre llegadas deterministaszG=tiempos entre llegadas generales (cualquier distribuci n)zB es el modelo de servicio, Puede tomar los mismos valores que ANotaci n de KendallzX es el n mero de dependientes (servidores)zY es la capacidad del sistema (n mero m ximo de clientes en el sistema), Se puede omitir si es infinitazZ es la disciplina, Se puede omitir si es FIFOzV es el n mero de estados de servicio, Se puede omitir si es 1zPor ejemplo, M | M | 1 | | FIFO | 1 se escribe abreviadamente M | M | 1 Medidas de rendimientozUna vez descrito el sistema, nuestro objetivo es evaluar su rendimiento, Para ello tenemos varias medidas de rendimiento.

3 ZN mero medio de clientes en el sistema, notado LzTiempo medio de espera de los clientes, WzN mero medio de clientes en la cola, LqzTiempo medio de espera en cola de los clientes, WqCola M | M | 1 Descripci n del modelozHay una sola cola, cuya capacidad es infinita, y un solo servidor, La disciplina ser FIFOzLas 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( )zLos 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 servicioCondici n de no saturaci nzSe 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 : =<donde,1zNosotros s lo estudiaremos las colas que no se saturan, Cuando una cola no se satura, tambi n se dice que alcanza el estado estacionario,ProbabilidadeszEl 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 procesarloszSuponiendo que el sistema no se satura, se deduce la siguiente f rmula para las probabilidades pnde que haya n clientes en el sistema, donde n N:() =1nnpMedidas de rendimientozEl n mero medio de clientes en el sistema, L, se calcula as.

4 ()() = = = = ==00011jjjjjjjjpjL Sumamos la serie aritm tico-geom trica:..432432++++= + = S() =++++= ()() = = 1112 LMedidas de rendimientozLa 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: == =UUzComo 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 rendimientozEl 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.

5 () 11111000+=+=+= = = =LppjpjWjjjjjjTiempo que se pasaen el sistema sihay j por delanteal llegarProbabilidad de quehaya j por delanteal llegarMedidas de rendimientozPodemos simplificar algo m s: =+=11 LWzEl tiempo medio de espera en la cola Wqse hallar restando a W el tiempo que tarda en ser servido el trabajo (esto es v lido para cualquier tipo de cola): 1 =WWqzEn el caso particular de una cola M | M | 1, obtenemos: =qWEjemplozUnos 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 minzNota:Al resolver un problema de colas , tener siempre muy presente la coherencia de unidadesEjemplozTenemos dos opciones:zSin ayudante: 1/ 1= 5 min = 1/12 hzCon ayudante: 1/ 2= 4 min = 1/15 hzEn ambos casos, = 10 clientes/hzOpci n 1 (sin ayudante):mec nicos51210112101;12101111= = == LPor tanto, perdemos 5 (10 /h) = 50 /hEjemplozOpci n 2 (con ayudante):mec nicos21510115101.

6 15101112= = == LPor 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 /hzEn 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 rendimientozEl 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:() = = = =11120 LpLLqzProbabilidad de que un cliente que llega pase m s de t unidades de tiempo en el sistema:()WtetW/ =()WtqetW/ = zProbabilidad de que un cliente que llega pase m s de t unidades de tiempo en la cola:EjemploszEjemplo: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:Ejemplosz1 El canal no se saturezSi tenemos k fuentes, llegar n a la cola 2k paquetes/seg, Por otro lado, 1/ = 0,025 seg = 40 paquetes/segzEl canal no se satura cuando <1:fuentes20120402< <===kkk Ejemplosz2 En media los paquetes no pasen en el sistema m s de 100 msegzTal como ocurr a en el apartado anterior, llegar n a la cola 2k paquetes/seg, y tendremos = 40 paquetes/segzNos exigen W 0,1 seg.

7 Fuentes151,024011 = =kkW Ejemplosz3 En el estado estacionario se garantice que al menos el 95% de los paquetes tenga un tiempo de respuesta que no exceda de 100 msegzTal como ocurr a en el apartado anterior, llegar n a la cola 2k paquetes/seg, y tendremos = 40 paquetes/segzNos 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:()() 05,0ln42,005,005,01,02401,0keWk)k que (ya fuentes 5021,52,005,0ln4N + kkkEjemploszEjemplo: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 1 (una sola cola), 1= , 1= : = =1111L = =11111 WzAlternativa 2 (n colas independientes), 2= /n, 2= /n :12212221111nLnnnnLnnnnni= = = = = = = Ejemplos1222111nWnWnn= = = = zComo la alternativa 1 tiene menores valores para ambas medidas de rendimiento, concluimos que la dicha alternativa es mejorzEsto nos indica que lo mejor es no dividir la capacidad de procesamiento, es decir, tener un nico servidor que atienda a todos los clientesTeorema de LittlezSea 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:WL =Teorema de LittlezExplicaci 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.

8 ZColocando un recaudador a la entrada del sistema, le cobrar como media W a cada uno de los trabajos que vea pasar por unidad de tiempozCada 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 sistemaTeorema de LittlezSi aplico el teorema a la cola, dejando fuera del sistema al servidor, obtengo el siguiente resultado, tambi n muy til:qqWL =zLas 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 citosCola M | M | cDescripci n del modelozHay una sola cola, cuya capacidad es infinita, y c servidores, La disciplina ser FIFOzLas 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( )zLos tiempos de servicio tambi n se distribuir n exponencialmente, Exp( )

9 , 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 servicioCondici n de no saturaci nzSe 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 : cdonde=<,1zNosotros s lo estudiaremos las colas que no se saturan, Cuando una cola no se satura, tambi n se dice que alcanza el estado estacionario,ProbabilidadeszSuponiendo que el sistema no se satura, se deducen las siguientes f rmulas para las probabilidades pnde que haya n clientes en el sistema, donde n N:()()1100!1! = + = cnnccncccp () ==caso otroen ,!,..,1,0 si ,!00pcccnpncpncnn Medidas de rendimientozN mero medio de clientes en cola:()2011! =+cpcLccqzUsamos razonamientos ya vistos para obtener: 1+=qWWqqWL =WL =Otras medidas de rendimientozN 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: cSS== =zProbabilidad de que un trabajo tenga que esperar para recibir su servicio (f rmula de retraso de Erlang):() =1!

10 0cpcqccEjemploszEjemplo:Usando L como medida de rendimiento, comparar estas dos alternativas: /2 /2 Alternativa 1:Alternativa 2:EjemploszAlternativa 1: =11 LzAlternativa 2: ===222()()11202202!21!22 = + = nnnp Ejemplos()()1221202124422421124 + += ++ = p() + = += 111222102p 221222222+=+= +==qqqWWWWL()()()() 211122124223202322++ =+ =+=pLLqEjemplos()()()()()() + =+ +=++ =1121122221123332L()() +< > +< 121011121zPara que la alternativa 1 sea mejor, ha de cumplirse que L1<L2:121< <+ zComo <1 siempre se cumple, tendremos que la alternativa 1 siempre es mejor, Es decir, no conviene dividir la capacidad de procesamiento en dos servidoresEjemploszEjemplo:Usando el n mero medio de clientes en el sistema como medida de rendimiento, comparar estas dos alternativas: /2 /2 /2 /2 Alternativa 2:Alternativa 1: /2 /2 EjemploszAlternativa 1 (n tese que hay 2 colas ): = = =donde,1212111 LzAlternativa 2 (es la alternativa 2 del ejemplo anterior).