Priority Scheduling

Vista previa

Una política de calendarización decide que thread tendrá tiempo de ejecución en el procesador, dado cierto conjunto de threads que se encuentran esperando en una lista (ready list).

La política de calendarización actual de Pintos es Round-robin (RR) Scheduling. En donde la ready list es una cola circular FIFO. Cada thread tiene un time quantum, el cual es el tiempo en el procesador que recibirá y en Pintos es igual a cuatro ticks por default. Cuando este tiempo expira, el thread actual (thread current) se mueve al final de la ready list y el siguiente thread en esta lista es calendarizado. No existen prioridades, todos los threads son tratados de forma equitativa.

En esta segunda tarea, usted deberá implementar en Pintos un Priority Scheduling y talvez quiera prestar atención a los siguientes archivos:

• pintos/src/threads/

  • thread.h

  • thread.c

  • synch.c

  • synch.h

Esto significaría que, cuando un nuevo thread sea añadido a ready list, y este tenga una mayor prioridad que el thread actual en ejecución, este thread en ejecución debe ceder inmediatamente el procesador al nuevo thread.

De la misma forma, cuando hayan varios threads que esperan por un lock, un semáforo o una variable de condición, el thread en espera con la más alta prioridad debe despertar primero.

Un thread podrá incrementar o reducir su propia prioridad en cualquier momento, pero si la reduce, de manera que no sea el thread de más alta prioridad, causará que ceda inmediatamente el procesador.

Las prioridades de un thread van de PRI_MIN (0) a PRI_MAX (63), de forma que un valor de prioridad cero es la prioridad más baja, y una prioridad igual a 63 es la más alta. La prioridad inicial es pasada como argumento a thread_create() y si no hay porque elegir alguna específica, se usa PRI_DEFAULT (31).

Donación de prioridades

En esta parte usted deberá implementar la funcionalidad de donación, para aquellos threads que deban donar su prioridad a los threads que están esperando. No deberá realizar donaciones di el thread objetivo tiene una prioridad más alta que el thread que quiere donar su prioridad.

Detalles de la inversión o donación de prioridades

Esta es la situación en donde, un thread de mayor prioridad no puede ser ejecutado, porque un thread de menor prioridad está reteniendo un recurso que el thread de mayor prioridad necesita, como por ejemplo un lock.

THREAD	PRIORIDAD	DESCRIPCIÓN
Thread 1	31	Tiene agarrado el Lock A
Thread 2	63	Está esperando por el Lock A

Este problema se puede solucionar siguiendo los siguientes pasos:

• El thread de mayor prioridad puede convertirse en donador, y donar su prioridad al thread con prioridad menor que retiene el recurso requerido.

• El thread de baja prioridad es entonces calendarizado debido a la donación previa.

• Cuando el thread de baja prioridad termine su tarea y suelte el recurso, su prioridad debe ser regresada a la prioridad original.

Casos de donación

Multiple Donation

En este escenario, hay multiples threads que esperan por el mismo lock que otro thread retiene. Por lo que el thread que retiene el lock, debe recibir la donación de mayor prioridad de los otros threads, al menos que esos otros threads tengan menor prioridad que el thread que retiene el lock.

• Escenario inicial:

THREAD	PRIORIDAD	DESCRIPCIÓN
Thread 1	31	Tiene agarrado el Lock A
Thread 2	63	Está esperando por el Lock A
Thread 3	41	Está esperando por el Lock A

• Luego de la donación:

THREAD	PRIORIDAD	DESCRIPCIÓN
Thread 1	63	Tiene agarrado el Lock A
Thread 2	63	Está esperando por el Lock A
Thread 3	41	Está esperando por el Lock A

• Una vez el Thread 1 suelte el Lock A, debe renunciar a las prioridades donadas por el Thread 2 y el Thread 3. Luego el Thread 2 agarra el Lock A ya que su prioridad es mayor en comparación a la del Thread 3, por lo que no hay donación.

THREAD	PRIORIDAD	DESCRIPCIÓN
Thread 1	31	Nada
Thread 2	63	Tiene agarrado el Lock A
Thread 3	41	Está esperando por el Lock A

Nested Donation

En este escenario la donación realizada se hace no solo al thread destinatario, sino también al thread por el cual el thread destinatario está esperando.

• Escenario inicial:

THREAD	PRIORIDAD	DESCRIPCIÓN
Thread 1	31	Tiene agarrado el Lock A
Thread 2	41	Tiene agarrado el Lock B
Thread 3	63	Está esperando por el Lock A Está esperando por el Lock B

• Luego de la donación:

THREAD	PRIORIDAD	DESCRIPCIÓN
Thread 1	63	Tiene agarrado el Lock A
Thread 2	63	Tiene agarrado el Lock B
Thread 3	63	Está esperando por el Lock A Está esperando por el Lock B

Donation Chain

Este escenario es similar a Nested Donation pero consiste en la propagación de donaciones a través de un número arbitrario de Nested Donations. El siguiente test pintos -v -k -T 60 –bochs – -q run priority-donate-chain evalúa esta funcionalidad, con un número de siete Nested Donations.

Funciones que debe implementar

Por último, en thread.c encontrará las siguientes funciones, que permiten examinar y modificar la prioridad de un thread, usted debe implementarlas según las descripciones:

• void thread_set_priority (int new_priority) Cambian la prioridad del thread actual a new_priority. Si el thread actual termina con una prioridad que ya no es la más alta, cede el procesador (yields).

• int thread_get_priority (void) Retorna la prioridad del thread actual. En precencia de donacion de prioridades, retorna la prioridad (donada) más alta.

Pistas

• Cuando calendarice a un nuevo thread, encuentre a aquel que tenga la prioridad más alta de entre los candidatos. Tome en cuenta que:

  • Los candidatos se encuentran en la ready list.

  • Debido a la primera tarea, Alarm Clock, los threads ingresan a la ready list cuando se cumplió su sleeping time y llamamos a thread_unblock. Y antes de eso los insertamos a lista_espera en la función insertar_lista_espera, ¿Qué pasa si en ésta función los hubiésemos insertado basándones en algún orden, como, por prioridad? ¿Existirá algo útil en src/lib/kernel/list.h y que nos ayude en cuanto a ordenamiento de listas?

• En synch.c/synch.h se encuentran los mecanismos básicos de sincronización como semáforos, locks, variables de condicion y barreras de optimización, sin embargo usted solo debe implementar donación de prioridades para los locks.

• Los threads en Nested Donation deben estar en la misma lista.