> For the complete documentation index, see [llms.txt](https://francisco-hernandez.gitbook.io/la-guia-del-frijol/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://francisco-hernandez.gitbook.io/la-guia-del-frijol/fase-1-threads/advanced-scheduler.md).

# 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).**

![](https://1784352645-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M8Z5z6dOabzvVbwFJyr%2F-M8e7tZTyyrNsYB1h8WI%2F-M8eJcTvsYsuhb7JUvEc%2Fmlfqs.gif?alt=media\&token=33c6573a-53ba-4e69-a6bf-e2f260a4e675)

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.<br>
* 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