3.14. Simulación: Tareas de impresión

Una simulación más interesante nos permite estudiar el comportamiento de la cola de impresión descrita anteriormente en esta sección. Recuerde que a medida que los estudiantes envían tareas de impresión a la impresora compartida, las tareas se ubican en una cola para que se procesen por orden de llegada. Muchas preguntas surgen con esta configuración. La más importante de éstas puede ser si la impresora es capaz de manejar una cierta cantidad de trabajo. Si no puede, los estudiantes estarán esperando demasiado tiempo para imprimir y pueden perder la próxima clase.

Considere la siguiente situación en un laboratorio de computación. En cualquier día promedio, alrededor de 10 estudiantes están trabajando en el laboratorio a cualquier hora. Estos estudiantes suelen imprimir hasta dos veces durante ese tiempo, y la extensión de estas tareas oscila entre 1 y 20 páginas. La impresora en el laboratorio es vieja, es capaz de procesar 10 páginas por minuto en calidad de borrador. La impresora se puede ajustar para dar una mejor calidad, pero entonces se producen sólo cinco páginas por minuto. La velocidad de impresión más lenta puede hacer que los estudiantes esperen demasiado. ¿Qué tasa de páginas debe utilizarse?

Podríamos tomar una decisión al respecto mediante la construcción de una simulación que modele el laboratorio. Necesitaremos construir representaciones para los estudiantes, las tareas de impresión, y la impresora (ver Figura 4). A medida que los estudiantes presenten tareas de impresión, las agregamos a una lista de espera, una cola de tareas de impresión conectadas a la impresora. Cuando la impresora completa una tarea, examinará la cola para ver si hay otras tareas pendientes de procesar. Es de interés para nosotros la cantidad promedio de tiempo que los estudiantes esperarán a que sus trabajos sean impresos. Ésta es igual al promedio de tiempo que una tarea espera en la cola.

../_images/simulationsetup.png

Figura 4: Cola de impresión en un laboratorio de ciencias de la computación

Figura 4: Cola de impresión en un laboratorio de ciencias de la computación

Para modelar esta situación necesitamos usar algunas probabilidades. Por ejemplo, los estudiantes pueden imprimir un trabajo que tenga de 1 a 20 páginas de longitud. Si cada longitud de 1 a 20 es igualmente probable, la longitud real para una tarea de impresión se puede simular utilizando un número aleatorio entre 1 y 20 inclusive. Esto significa que hay igual probabilidad de que aparezca cualquier longitud de 1 a 20.

Si hay 10 estudiantes en el laboratorio y cada uno imprime dos veces, entonces en promedio hay 20 tareas de impresión por hora. ¿Cuál es la probabilidad de que, en un segundo determinado, se vaya a crear una tarea de impresión? El modo para responder a esto es considerar la proporción entre tareas y tiempo. Veinte tareas por hora significa que en promedio habrá una tarea cada 180 segundos:

\(\frac {20\ tareas}{1\ hora} \times \frac {1\ hora} {60\ minutos} \times \frac {1\ minuto} {60\ segundos}=\frac {1\ tarea} {180\ segundos}\)

Por cada segundo podemos simular la posibilidad de que se produzca una tarea de impresión generando un número aleatorio entre 1 y 180 inclusive. Si el número es 180, decimos que se ha creado una tarea. Tenga en cuenta que es posible que muchas tareas se creen una tras otra o quizás debamos esperar un buen rato para que aparezca una tarea. Ésa es la naturaleza de la simulación. Usted desea simular la situación real de la manera más cercana posible dado que conoce los parámetros generales.

3.14.1. Pasos principales de la simulación

Aquí está la simulación principal.

  1. Crear una cola de tareas de impresión. A cada tarea se le dará una marca de tiempo (marcaTiempo) a su llegada. La cola está vacía al comenzar.
  2. Para cada segundo (segundoActual):
    • ¿Se creó una nueva tarea de impresión? Si es así, agregarla a la cola con segundoActual como la marca de tiempo.
    • Si la impresora no está ocupada y si una tarea está esperando,
      • Extraer la siguiente tarea de la cola de impresión y asignarla a la impresora.
      • Restar marcaTiempo de segundoActual para calcular el tiempo de espera para esa tarea.
      • Añadir el tiempo de espera para esa tarea a una lista para su procesamiento posterior.
      • Con base en el número de páginas en la tarea de impresión, averigüe cuánto tiempo se requerirá.
    • La impresora ejecuta un segundo de impresión si es necesario. También resta un segundo del tiempo requerido para esa tarea.
    • Si la tarea se ha completado, en otras palabras, el tiempo requerido ha llegado a cero, la impresora ya no está ocupada.
  3. Una vez completada la simulación, calcule el tiempo de espera promedio usando la lista de tiempos de espera generados.

3.14.2. Implementación en Python

Para diseñar esta simulación crearemos clases para los tres objetos del mundo real descritos anteriormente: Impresora, Tarea y colaImpresion.

La clase Impresora (ver el Programa 2) tendrá que verificar si tiene una tarea actual. Si así es, entonces está ocupada (líneas 13-17) y la cantidad de tiempo necesario se puede calcular a partir del número de páginas de la tarea. El constructor también permitirá que se inicialice la característica de número de páginas por minuto. El método tictac disminuye el temporizador interno y pone la impresora en disponible (línea 11) si la tarea se ha completado.

Programa 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Impresora:
    def __init__(self, paginas):
        self.tasaPaginas = paginas
        self.tareaActual = None
        self.tiempoRestante = 0

    def tictac(self):
        if self.tareaActual != None:
            self.tiempoRestante = self.tiempoRestante - 1
            if self.tiempoRestante == 0:
                self.tareaActual = None

    def ocupada(self):
        if self.tareaActual != None:
            return True
        else:
            return False

    def iniciarNueva(self,nuevaTarea):
        self.tareaActual = nuevaTarea
        self.tiempoRestante = nuevaTarea.obtenerPaginas() \
        * 60/self.tasaPaginas

La clase Tarea (ver el Programa 3) representará una sola tarea de impresión. Cuando se crea la tarea, un generador de números aleatorios proporcionará un número entre 1 y 20 que corresponderá al número de páginas del trabajo. Hemos elegido utilizar la función randrange del módulo random.

>>> import random
>>> random.randrange(1,21)
18
>>> random.randrange(1,21)
8
>>>

Cada tarea también tendrá que mantener una marca de tiempo que se utilizará para calcular el tiempo de espera. Esta marca de tiempo representará la hora en que se creó la tarea y se colocó en la cola de impresión. El método tiempoEspera puede utilizarse para obtener la cantidad de tiempo que la tarea pasó en la cola antes de que comience su impresión.

Programa 3

import random

class Tarea:
    def __init__(self,tiempo):
        self.marcaTiempo = tiempo
        self.paginas = random.randrange(1,21)

    def obtenerMarca(self):
        return self.marcaTiempo

    def obtenerPaginas(self):
        return self.paginas

    def tiempoEspera(self, tiempoActual):
        return tiempoActual - self.marcaTiempo

La simulación principal (ver el Programa 4) implementa el algoritmo descrito anteriormente. El objeto colaImpresion es una instancia de nuestro TAD Cola existente. Una función auxiliar booleana, nuevaTareaImpresion, decide si se ha creado una nueva tarea de impresión. De nuevo, hemos elegido utilizar la función randrange del módulo random para devolver un número entero aleatorio entre 1 y 180. Las tareas de impresión aparecen una vez cada 180 segundos. Podemos simular este evento aleatorio eligiendo arbitrariamente 180 de entre el rango de enteros aleatorios (línea 32). La función de simulación nos permite ajustar el tiempo total y la tasa de páginas por minuto de la impresora.

Programa 4

import random

from pythoned.basicas.cola import Cola

def simulacion(numeroSegundos, paginasPorMinuto):

    impresoraLaboratorio = Impresora(paginasPorMinuto)
    colaImpresion = Cola()
    tiemposEspera = []

    for segundoActual in range(numeroSegundos):

      if nuevaTareaImpresion():
         tarea = Tarea(segundoActual)
         colaImpresion.agregar(tarea)

      if (not impresoraLaboratorio.ocupada()) and \
                (not colaImpresion.estaVacia()):
        tareaSiguiente = colaImpresion.avanzar()
        tiemposEspera.append(tareaSiguiente.tiempoEspera(segundoActual))
        impresoraLaboratorio.iniciarNueva(tareaSiguiente)

      impresoraLaboratorio.tictac()

    esperaPromedio=sum(tiemposEspera)/float(len(tiemposEspera))
    print("Tiempo de espera promedio%6.2f segundos %3d tareas restantes."%(esperaPromedio, colaImpresion.tamano()))


def nuevaTareaImpresion():
    numero = random.randrange(1,181)
    if numero == 180:
        return True
    else:
        return False

for i in range(10):
    simulacion(3600,5)

Cuando ejecutamos la simulación, no debemos preocuparnos de que los resultados sean diferentes cada vez. Esto se debe a la naturaleza probabilística de los números aleatorios. Estamos interesados en las tendencias que pueden estar ocurriendo a medida que se ajustan los parámetros de la simulación. Estos son algunos resultados.

En primer lugar, ejecutaremos la simulación durante un período de 60 minutos (3.600 segundos) utilizando una tasa de páginas de cinco páginas por minuto. Además, ejecutaremos 10 ejecuciones independientes. Recuerde que debido a que la simulación funciona con números aleatorios, cada ejecución retornará resultados diferentes.

>>>for i in range(10):
      simulacion(3600,5)

Tiempo de espera promedio 165.38 segundos 2 tareas restantes.
Tiempo de espera promedio  95.07 segundos 1 tareas restantes.
Tiempo de espera promedio  65.05 segundos 2 tareas restantes.
Tiempo de espera promedio  99.74 segundos 1 tareas restantes.
Tiempo de espera promedio  17.27 segundos 0 tareas restantes.
Tiempo de espera promedio 239.61 segundos 5 tareas restantes.
Tiempo de espera promedio  75.11 segundos 1 tareas restantes.
Tiempo de espera promedio  48.33 segundos 0 tareas restantes.
Tiempo de espera promedio  39.31 segundos 3 tareas restantes.
Tiempo de espera promedio 376.05 segundos 1 tareas restantes.

Después de ejecutar nuestros 10 ensayos podemos ver que la media de tiempos de espera promedio es 122.09 segundos. Usted también puede ver que hay una gran variación en el tiempo de espera promedio con un promedio mínimo de 17,27 segundos y un máximo de 376,05 segundos. También puede observar que en sólo dos de los casos todas las tareas fueron completadas.

Ahora, vamos a ajustar la tasa de páginas a 10 páginas por minuto, y ejecutaremos de nuevo los 10 ensayos, con una tasa de páginas más rápida nuestra esperanza es que más tareas se completarán en el espacio de una hora.

>>>for i in range(10):
      simulacion(3600,10)

Tiempo de espera promedio   1.29 segundos 0 tareas restantes.
Tiempo de espera promedio   7.00 segundos 0 tareas restantes.
Tiempo de espera promedio  28.96 segundos 1 tareas restantes.
Tiempo de espera promedio  13.55 segundos 0 tareas restantes.
Tiempo de espera promedio  12.67 segundos 0 tareas restantes.
Tiempo de espera promedio   6.46 segundos 0 tareas restantes.
Tiempo de espera promedio  22.33 segundos 0 tareas restantes.
Tiempo de espera promedio  12.39 segundos 0 tareas restantes.
Tiempo de espera promedio   7.27 segundos 0 tareas restantes.
Tiempo de espera promedio  18.17 segundos 0 tareas restantes.

Usted puede ejecutar la simulación por sí mismo en el ActiveCode 2.

3.14.3. Discusión

Estábamos tratando de responder a una pregunta acerca de si la impresora actual podría manejar la carga de tareas si fuera ajustada para imprimir con una mejor calidad, pero con una tasa de página más lenta. El enfoque que tomamos fue escribir una simulación que modeló las tareas de impresión como eventos aleatorios de varias longitudes y tiempos de llegada.

La salida anterior muestra que con una impresión de 5 páginas por minuto, el tiempo de espera promedio varió de un mínimo de 17 segundos a un máximo de 376 segundos (aproximadamente 6 minutos). Con una velocidad de impresión más rápida, el valor bajo fue de 1 segundo, con un máximo de sólo 28. Además, en 8 de cada 10 ejecuciones a 5 páginas por minuto había tareas de impresión que todavía esperaban en la cola al final de la hora.

Por lo tanto, tal vez estamos convencidos de que la desaceleración de la impresora para obtener una mejor calidad no es una buena idea. Los estudiantes no pueden darse el lujo de esperar tanto por sus trabajos, especialmente cuando tienen que estar pasando a su próxima clase. Una espera de seis minutos sería simplemente demasiado larga.

Este tipo de análisis de simulación nos permite responder a muchas preguntas, conocidas comúnmente como preguntas de “qué pasaría si”. Todo lo que necesitamos hacer es variar los parámetros utilizados por la simulación y podremos simular cualquier número de comportamientos interesantes. Por ejemplo,

  • ¿Qué pasaría si la matrícula aumenta y el número promedio de estudiantes aumenta en 20?
  • ¿Qué pasa si es sábado y los estudiantes no necesitan ir a clase? ¿Pueden darse el lujo de esperar?
  • ¿Qué pasaría si el tamaño de la tarea de impresión promedio disminuye ya que Python es un lenguaje tan potente que los programas tienden a ser mucho más cortos?

Estas preguntas podrían ser respondidas modificando la simulación anterior. Sin embargo, es importante recordar que la simulación es tan buena como las suposiciones que se usan para construirla. Los datos reales sobre el número de tareas de impresión por hora y el número de estudiantes por hora serán necesarios para construir una simulación robusta.

Autoevaluación

¿Cómo modificaría la simulación de la impresora para reflejar un mayor número de estudiantes? Supongamos que el número de estudiantes se duplicó. Usted tendría que hacer algunas suposiciones razonables sobre cómo se compuso esta simulación pero ¿qué cambiaría? Modifique el código. Suponga también que la longitud de la tarea de impresión promedio se redujo a la mitad. Cambie el código para reflejar ese cambio. Por último ¿Cómo parametrizar el número de estudiantes?, en lugar de cambiar el código nos gustaría que el número de estudiantes sea un parámetro de la simulación.

Next Section - 3.15. ¿Qué es una cola doble?