Advanced Scheduler

Vista previa

En esta tercera tarea, talvez quiera prestar atención a los siguientes archivos:

• pintos/src/devices/

  • timer.h

  • timer.c

• pintos/src/threads/

  • thread.h

  • thread.c

En esta tarea usted deberá implementar un Multilevel Feedback Queue Scheduler (MLFQS).

Este tipo de calendarizador es usado para reducir el promedio de respuesta para las tareas en ejecución del sistema. Este calendarizador escoge el trhead a ejecutarse basándose en prioridades, sin embargo NO realiza donación de prioridades.

El propósito es poder balancear las distintas necesidades de calendarización de los threads. Por ejemplo, un thread que realice muchas operaciones de I/O requiere un tiempo de respuesta rápido para mantener ocupados a los dispositivos de input y output, pero necesita poco tiempo de CPU. Mientras que, aquellos threads vinculados a cómputo necesitan mucho tiempo de CPU para terminar sus tareas, pero no necesitan un tiempo rápido de respuesta. Pueden haber otros threads con necesidades intermedias entre esos dos casos. Por lo que un calendarizador bien diseñado puede organizar a los threads con esos requerimientos simultáneamente.

El calendarizador a implementar ahora, mantendra diversas colas de threads listos para ejecutarse, en donde cada cola tiene a los threads con cierta prioridad, distinta a los threads de las demas colas.

En cualquier momento, el calendarizador tomará al thread con mayor prioridad de alguna cola no vacía para ejecutarse. De haber varios con una misma prioridad alta, se ejecutarán bajo la política Round Robin.

Este tipo de calendarizador, tiene una base matemática y previene el problema de Starvation ya que nos garantiza que es "justo".

Para lograr este tipo de calendarizador, debemos tener claros los conceptos que se definirán a continuación:

Niceness

La prioridad de un thread es determinada de forma dinámica por el calendarizador usando una fórmula que se detalla más abajo. Cada thread tiene un valor entero nice que determina que tan "agradable" es este thread respecto a los demás threads. Un valor nice de cero no afecta la prioridad del thread. Un nice positivo, hasta un máximo de 20, disminuye la prioridad del thread y causa que ceda algo de tiempo de CPU que recibió. Por otra parte un nice negativo, hasta un mínimo de -20, causará que el thread tome tiempo de CPU de otros threads.

El valor inicial de nice de un thread inicia con cero, otros threads ppueden iniciar con un valor de nice que heredaron de su padre. Usted debe implementar las siguientes funcones que se encuentran en thread.c.

• int thread_get_nice (void) Retorna el valor de nice del thread actual.

• void thread_set_nice (int new_nice) Cambia el valor de nice del thred actual por new_nice y recalcula la prioridad del thread basado en este nuevo valor. Si el thread actual ya no tiene la prioridad más alta, cede (yields) el procesador.

Calculando la prioridad

El calendarizador tiene 64 prioridades, por lo tanto tiene 64 colas de threads listos, enumeradas de 0 (PRI_MIN) hasta 63 (PRI_MAX) en donde 0 es la prioridad más baja y 63 la más alta. La prioridad se calcula en la inicialización de un thread y es recalculada cada cuarto tick para cada uno de los threads. Se determina mediante la fórmula.

priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)

Donde recent_cpu (en la siguiente descripción lo veremos) es un estimado de tiempo de CPU que el thread ha usado recientemente y nice es el valor de nice de un thread. El resultado debe ser redondeado al entero más cercano. Esta fórmula nos ayuda a que un thread que ha recibido tiempo de CPU recientemente reduzca su prioridad para cuando sea reasignado al CPU la próxima vez por el calendarizador.

Esta es la clave para prevenir Starvation ya que un thread que no ha recibido tiempo de CPU recientemente tendrá un recent_cpu de cero y salvo a que tenga un alto valor nice se garantiza que recibirá tiempo de CPU pronto.

Calculando recent_cpu

recent_cpu = (2 * load_avg) / (2 * load_avg + 1) * recent_cpu + nice