Teoria De Colas

1. TEORÍA DE COLAS

En los computadores es frecuente encontrar a diversos trabajos compartiendo un número

limitado de recursos, tales como la CPU, los discos u otros dispositivos. Generalmente, sólo

uno (o unos pocos) de los trabajos puede utilizar el recurso mientras que los demás esperan en

cola. La teoría de colas de espera es una herramienta matemática que permite cuantificar el

fenómeno de formación de colas. A través de ella se intentará calcular el tiempo que pasa un

trabajo en cada una de las colas que se forman en un sistema (y por tanto, el tiempo total que

pasa un trabajo dentro del sistema o tiempo de respuesta), la longitud media de estas colas y

otra serie de parámetros que ayudarán a determinar las prestaciones del sistema. No es por

tanto sorprendente que la teoría de colas sea tan popular entre los que se dedican a evaluar las

prestaciones de los sistemas de computación.

1.1. CARACTERÍSTICAS DE UN MODELO DE COLAS

Se puede imaginar un grupo de estudiantes de informática esperando en la sala de terminales

del centro de cálculo. Existe un número determinado (y limitado) de terminales a disposición

de los alumnos. Si cuando llega un estudiante todos los terminales están ocupados, éste pasa a

esperar en la cola. En términos de teoría de colas, los estudiantes suelen llamarse clientes1.

Para abordar el estudio de la formación de colas de espera, se utilizará un modelo abstracto

que se denominará estación de servicio. La estación de servicio está compuesta por un

servidor o conjunto de servidores que representan al recurso y una cola de espera, que en cada

momento contendrá a aquellos clientes que a su llegada a la estación de servicio encuentran al

servidor o servidores ocupados (figura 3.1).

Figura 3.1.

En el ejemplo de los estudiantes, la estación de servicio es el centro de cálculo, los servidores

son los terminales y los estudiantes que llegan cuando todos éstos están ocupados forman la

cola de espera.

Para analizar este sistema se han de que especificar las siguientes características:

- Proceso de llegada. Si se denominan t1, t2, … , tj a los instantes en los que se producen las

llegadas de los estudiantes, las variables Tj = tj - tj - 1 representarán los tiempos entre

llegadas. El proceso de llegada más simple corresponde al caso T1 = T2 = … = Tj = … =

constante, que se denomina proceso de llegadas regulares o determinista. Sin embargo, para

muchas aplicaciones se trata de un modelo poco realista y que, además, no tiene un

tratamiento matemático sencillo. En general, se supondrá que las Tj forman una secuencia

de variables aleatorias idéntica e independientemente distribuidas (IID). El proceso de

llegadas que se utilizará con mayor frecuencia es el proceso de Poisson que corresponde al

caso en el que los tiempos entre llegadas tienen una distribución exponencial. En algunas

ocasiones se utilizan otros procesos, como los que corresponden al caso de tiempos entre

llegadas con una distribución de Erlang o hiperexponencial. De hecho hay muchos

resultados de la teoría de colas que son válidos para todas las distribuciones del tiempo

entre llegadas. En estos casos, se dice que el resultado es válido para una distribución

general.

1.

En estos temas se utilizarán los términos "cliente'', "trabajo'' o "tarea'' según convenga para hacer referencias

a lo que circula a través de las estaciones de servicio, esperando en la colas y recibiendo servicio en los

servidores

15

- Distribución del tiempo de servicio. Se necesita conocer cuál es el tiempo que cada

estudiante pasa en un terminal. Esto es lo que se denomina tiempo de servicio.

Generalmente se supondrá que el tiempo de servicio es una variable aleatoria IID. La

distribución más extensamente utilizada es la exponencial, aunque ocasionalmente se

utilizan la de Erlang, la hiperexponencial y la general. De nuevo, un resultado obtenido

para una distribución general es válido para todas las distribuciones.

- Número de servidores. Puesto que la sala de terminales puede contener uno o varios

terminales, se supondrá que todos los terminales son idénticos y que forman parte del

mismo sistema de colas. De esta forma cualquier terminal puede ser asignado a cualquier

estudiante.

- Tipo de servidores. Hace referencia al comportamiento de los servidores respecto de los

clientes. Pueden, por ejemplo, actuar buscando en la cola inmediatamente después de la

salida de un cliente o esperar un tiempo antes de hacerlo y si no encuentran ningún cliente

esperando dejar pasar un nuevo intervalo antes de volver a mirar en la cola.

- Capacidad del sistema. Es el máximo número de clientes que pueden permanecer en la

estación de servicio: haciendo uso de los servidores o esperando. Esta restricción puede

surgir debido a limitaciones de espacio o para evitar la formación de largas colas. Cuando

la capacidad del sistema es grande, suponer una capacidad infinita facilita el análisis

matemático. Nótese que la capacidad del sistema incluye a los que están recibiendo

servicio y a los que están esperando en la cola.

- Tamaño de la población. El número total de clientes que pueden llegar a la estación de

servicio es el tamaño de la población. En la mayoría de sistemas reales el tamaño de la

población es finito. Sin embargo, la población finita presenta mayor complejidad

matemática ya que, en un instante determinado, el número de clientes que ya está en la

estación de servicio afecta al número de clientes que potencialmente pueden llegar a la

estación. Por tanto, si la población es grande, se facilita el análisis suponiéndola infinita.

- Política de servicio. Es la forma de seleccionar cuál de los clientes que esperan en cola

pasará a utilizar un servidor, en el momento que uno de ellos quede libre. Hay varias

estrategias:

* First Come, First Served (FCFS) o FIFO, los clientes se sirven en el orden de llegada.

* Last Come, First Served (LCFS) o LIFO, los clientes se sirven en el orden inverso al de

llegada.

* Round-Robin (RR), se ofrece una cantidad de servicio fija y pequeña a cada cliente, de

forma circular.

* Procesador

...