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.

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

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

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

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

6 =<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 :()() = = = = ==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.

7 == =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:() 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.

8 =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.

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

10 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: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.