Priority Scheduler ⌚
Esta es la segunda asignación del proyecto de Threads.
¿En que consiste?
El calendarizador que tiene el PintOS por default es un calendarizador Round Robin, entonces la tarea de esta asignación es convertir ese calendarizador Round Robin a un calendarizador basado en prioridades.
Este cambio de calendarizador no solo afecta como se decide cual es el siguiente thread si no también afecta temas de sincronización.
Priority Scheduler
En pintOs, los threads que están listos para ser calendarizados se encuentran en la ready_list. Entonces la manera en la que se implementó el Priority Scheduler fue insertar de manera ordenada por la prioridad los threads a la ready_list, para se debe de analizar el ciclo de vida de un thread y en que momento ingresan a la ready_list.
Ciclo de vida del thread
El thread empieza en la función create_thread
El thread se inicializa e inmediatamente se bloquea, entonces entra a block_list.
Cuando se termina de inicializar se desbloquea y pasa por primera vez a ready_list.
Cuando se calendariza pasa de estado READY a estado RUNNING.
Cuando ocurre el timer interrupt pasa de RUNNING a READY, vuelve a la ready_list.
Si el thread cede el procesador puede volver a la ready_list.
Finalmente, el thread termina y sale de todas las colas.
Al analizar el ciclo de vida se puede notar que solo hay tres instancias en que un thread pasa a la ready_list:
thread_yield
thread_unblock
Los threads luego son desencolados en la función next_thread_thread()
donde se hace un pop_back(list)
a la lista, ya que los threads están ordenados de menor a mayor prioridad.
¿Cómo ordenar las listas de pintOS?
Ordena la lista de acuerdo a la función priority value less.
La lista está ordenada de menor a mayor prioridad, si las prioridades son iguales conserva el orden de llegada.
Thread Yield
En la función thread_yield() se llama cuando el thread quiere ceder su tiempo en el procesador. Cuando cede su tiempo en el procesador va a regresar inmediatamente a la lista ready_list.
Thread Unblock
Cuando un thread regresa del estado BLOCK a estado READY llama a esta función que lo ingresa de nuevo a la cola ready_list. Es importante notar que todos los threads cuando se están creando empiezan en el estado BLOCK y luego se desbloquean con thread_unblock(thread).
Priority Scheduler: Sincronización
PintOS tiene tres formas de sincronizar porciones de código. Estas estructuras de sincronización también se debe de ser programadas de acuerdo a su prioridad.
Locks
Semáforos
Monitores o variables de condición
Locks
Los locks son una herramienta para sincronizar segmentos de código. El thread para acceder a cierto segmento de código debe de pedir el lock y si el kernel no se lo da, debe de ingresar a un cola de espera.
En PintOS, los locks se implementan con un semáforo binario y se utiliza la lista de espera del semáforo para guardar los threads que estén esperando el lock. Por está razón los cambios para tomar en cuenta la prioridad se implementaron en los semáforos.
Como el calendarizador toma en cuenta la prioridad puede pasar que un thread con baja prioridad obtenga el lock y nunca vuelva a ser programado por su baja prioridad, esto es una causa de deadlock, pero se puede solucionar al implementar las donaciones de prioridad.
Semáforo
Los semáforos se utilizan para permitir a n cantidad de threads acceder a una sección crítica de código. Se inicia con un valor n que sea positivo que indica cuantos threads pueden acceder y ningún thread puede ver el valor del semáforo. Tiene dos métodos principales para modificar el semáforo.
sema_up() o V():
Incrementa el valor del semáforo, y si hay threads esperando despierta al que tiene la mayor prioridad.sema_down() o P()
: Disminuye el valor del semáforo, y si el valor del semáforo es 0 lo encola a la lista de espera ordenada por prioridad.
Se utiliza la función priority value less es la misma que se define para insertar por prioridades a la ready_list.
Si el thread que salió de la lista de espera del semáforo tiene una prioridad mayor que el thread actual, el thread actual cede el procesador.
Monitores
Los monitores son una herramienta de sincronización con un grado de abstracción mayor que el de los semáforos y los locks. Se necesita tener un lock y una o más variables de condición, el flujo del uso del monitor es el siguiente:
Se toma un lock sobre una sección crítica.
Se modifica información.
Si no se cumple una condición, por ejemplo, "No se ha recibido la data del usuario", se puede esperar o "dormir" con el lock.
Entidad externa desbloquea el thread de la lista de espera.
Se suelta el lock.
Se debe de tomar en cuenta la prioridad al momento de sacar un thread de la lista de espera.
Se utiliza la función priority value less es la misma que se define para insertar por prioridades a la ready_list.
Donación de Prioridades
Cuando se toma en cuenta las prioridades para programar cada thread puede causar que un thread con baja prioridad tome un lock, luego entre un thread de prioridad más alta que intente tomar el lock pero como el thread de baja prioridad lo tiene va a entrar a la lista de espera del lock. Si hay varios threads esperando que el thread de baja prioridad libere el lock puede causar deadlocks y que todos tomen más tiempo en ejecutarse.
Para solucionar esto se realizó la donación de prioridades.
Cambios a la struct lock, struct thread y una nueva struct.
Se le agrego un id para poder compararlo con otros locks, una struct donation donde está la información de la donación que tiene actualmente el thread y un list_elem para ingresar el lock a una lista.
Lock Acquire
En la función lock_acquire se realizó la implementación de las donaciones de prioridad. Se debe de tomar en cuenta 4 casos:
Donación simple: Un thread A le dona su prioridad al thread B
Donación múltiple: Un thread A le dona su prioridad al thread B, y también el thread C le dona su prioridad al thread B.
Donación anidadas : Un thread A tiene el lock 1, el thread B tiene el lock 2 y está esperando por el lock 1 del thread A y luego el thread C pide el lock 2 del thread B. Entonces el thread C le dona su prioridad
Donaciones en cadena: Es una forma de donaciones anidadas con una recursión de 8 niveles.
Caso #1: Donación Simple
Para implementar las donaciones simples se hace el pseudocódigo anterior. En el se hace la donación si y solo si, la prioridad del thread actual o donante es mayor que el thread que tiene al lock.
Caso #2: Donación Múltiple
Para la donación múltiple si se cumple la condición que el current
tiene una prioridad menor que el lock_holder
entonces se debe de revisar si el lock_holder
ya le donaron una vez, de ser así se debe de revisar si la donación previa tiene una prioridad mayor que el de current
y si eso se cumple hay que cambiar la prioridad de la donación.
En el caso que no tenga donaciones se realiza la donación simple.
Caso #3 y #4: Donación anidada y en cadena
Para las donaciones anidadas se implemento con un ciclo. Al final de realizar una donación se cambia el lock_holder
por el lock que está esperando el lock_holder.
Las donaciones anidadas se van a realizar 8 veces.
Lock Release
Cuando un thread libera el lock, si otro thread le donó su prioridad se debe de liberar la prioridad donada y cambiar a la prioridad original del thread.
¿Cómo afectan la donación de prioridades al Priority Scheduler?
SET PRIORITY
Los threads pueden cambiar su prioridad en cualquier momento de su ejecución, entonces si tienen una donación al momento de cambiar su prioridad no deben de perder la prioridad donada. La prioridad debe de cambiar hasta que regresen la donación.
La struct thread tiene el miembro original_priority
para solucionar este problema.
SEMA UP
Hay que ordenar la lista de espera antes de despertar a un thread porque la donación puede cambiar la prioridad de un thread que este en la lista de espera
Last updated