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 prioridades a los diferentes usuarios según algunas de sus características.

En sistemas finitos, en los que el número de usuarios en espera es limitado, es necesario establecer además qué sucede con aquellos usuarios que acceden al sistema cuando la cola de espera está completa. Por último, en los sistemas en que los usuarios son humanos, hay que tener en cuenta otros factores propios del comportamiento humano como el hecho de que hay individuos que no respetan el orden establecido en la cola o bien que hay usuarios que, a la vista de la cola, renuncian a acceder al sistema.

Otra característica importante de un sistema de colas es el diseño de la ejecución del servicio. El servicio puede estar ejecutado por uno o varios servidores. Si el tiempo que tardan los usuarios en salir del sistema es mayor que el intervalo entre llegadas, la cola aumentará indefinidamente y el sistema puede llegar a colapsarse. Por tanto es necesario diseñar

...