Tráfico Y Cola

ELEMENTOS DE TEORÍA DE COLAS

Descripción de un sistema de colas

La teoría de colas aparece a principios del presente siglo para estudiar los problemas de congestión de tráfico que se presentaban en las recientemente inventadas comunicaciones telefónicas. Entre 1903 y 1905, Erlang es el primero en tratar el tráfico telefónico de forma científica, y establece la unidad de tráfico telefónico, que recibe su nombre. Posteriormente esta teoría se ha aplicado a multitud de problemas de la vida real, como el tráfico de automóviles, la regulación de semáforos en una ciudad, la determinación del número de cajeros en los hipermercados, o el control de los tiempos de espera de los procesos que acceden al procesador de un ordenador que trabaja en tiempo compartido.

Lo elementos más importantes de un sistema de colas son: las llegadas, la cola, el servicio y la salida.

En general, un sistema de colas consiste en uno o varios servidores que prestan un servicio a uno o varios usuarios que acceden al sistema. El proceso de llegadas lo regula una fuente generadora de usuarios y, en general, estas llegadas serán de forma aleatoria. Esta fuente generadora de usuarios puede ser finita o infinita.

Interesa saber cuál es el intervalo de tiempo entre las llegadas de dos usuarios consecutivos. Además, según cómo sea el proceso de llegadas, los usuarios pueden llegar individualmente o en grupos

Si cuando un usuario llega al sistema el servidor está libre, se le da servicio. Si el tiempo de servicio es mayor que el intervalo entre llegadas, el siguiente usuario, cuando accede al sistema, encuentra que el servidor está ocupado, por lo que debe quedar en espera, formando la cola.

Otra cuestión importante es saber cuánto tiempo debe esperar un usuario que llega al sistema hasta que recibe el servicio, lo cual entra dentro del concepto QOS (Quality of Service, calidad de servicio). Cuando en la cola hay más de un usuario, al quedar el servidor libre hay que determinar cuál de los usuarios en espera será el que pase a recibir servicio. Es decir, es necesario un proceso para decidir qué usuario va a ser llamado de la cola; esto es lo que se llama disciplina de la cola. Los modelos más importantes son los siguientes:

FIFO (First-In-First-Out): se le da servicio al primero que ha llegado, de forma que la cola está ordenada según el orden de llegada de los usuarios.

LIFO (Last-In-First-Out): se le da servicio al último que ha llegado, de forma que la cola está ordenada en orden inverso al de llegada de los usuarios.

SIRO (Service-In-Random-Order): Se sortea aleatoriamente cuál de los usuarios en espera accederá al servicio.

No obstante, otro procedimiento para establecer la disciplina de la cola puede ser el de establecer determinadas

...