4 Algoritmo de robo de trabajo¶

Intro¶

Como ya hemos dicho, cada hilo del threadpool del ejecutor posee su propia cola de trabajo (work queue) de la que se extrae una a una las tareas para ejecutarlas y en la que se insertan nuevas tareas que deben ser ejecutadas.

La cola de trabajo de cada hilo corresponde a lo que se conoce como una cola de doble extremo (dequeue, double-ended queue), es decir, una cola en la que se pueden realizar inserciones y extracciones por ambos extremos. Uno de los extremos recibe el nombre de head y el otro extremo recibe el nombre de tail.

Cada hilo trabajador se encuentra ejecutando una especie de bucle infinito en el que conforme termina de ejecutar una tarea, extrae otra del head de la dequeue (operación pop) y la ejecuta. Dado que cada hilo dispone de su propia dequeue, no debe competir con otros hilos y por tanto se disminuye la contención (el hecho de tener que bloquear un hilo por estar esperando en un cerrojo).

Cuando una tarea padre hace fork() sobre una subtarea, dicha subtarea es insertada en el head de la dequeue de trabajo asociada al mismo hilo en el que se está ejecutando la tarea padre (operación push). Por tanto, si la tarea padre hace fork() de varias subtareas, éstas se van encolando en orden LIFO (last input first output), de manera que la última subtarea sobre la que se ha hecho fork() es la que ocupará el head de la dequeue de trabajo (como si fuera una pila).

Cuando durante su ejecución una tarea padre hace join() sobre una subtarea porque necesita esperar a que ésta termine su ejecución, la tarea padre queda bloqueada y el hilo trabajador es asignada a otra tarea.

Con el objetivo de tener a los hilos del threadpool del ejecutor lo más ocupados que sea posible, éstos implementan el conocido como algoritmo de robo de trabajo (work-stealing algorithm), que consiste en que si un hilo del threadpool debe extraer una nueva tarea del head de su dequeue de trabajo y detecta que ésta está vacía, comprueba las dequeue de trabajo del resto de hilos del threadpool del ejecutor y, de entre aquellas que contengan tareas pendientes de ejecución, elige una aleatoriamente para extraer del tail de dicha dequeue de trabajo una tarea (operación poll) y comenzar su ejecución.

Como vemos, las tareas extraen del tail de otra dequeue de trabajo, por lo que digamos que "se roban" en orden FIFO (fist input first output), es decir que las subtareas sobre las que se hicieron primero fork() en el hilo original son las primeras en poder ser robadas por otros hilos (como si fuera una cola). El objetivo de que el robo se realice desde el extremo contrario al que se extraen las tareas normalmente para su ejecución es minimizar la contención entre el hilo poseedor de la dequeue y el hilo que pretende hacer el robo, dado que los dos extremos de la dequeue están protegidos por mecanismo de locking distintos.

Si el hilo no encuentra ninguna tarea que "robar" de las colas de trabajo del resto de hilos, el hilo accede a la cola común del ejecutor, extrae una tarea de ella y comienza su ejecución.

Si dos hilos tratan de "robar" tareas de la misma cola de trabajo, se producirá contención, pero ésta es normalmente insignificante.

Antes hemos comentado que cuando durante su ejecución una tarea padre hace join() sobre una subtarea porque necesita esperar a que ésta termine su ejecución, la tarea padre queda bloqueada y el hilo trabajador es asignada a otra tarea. Pero ¿a qué otra tarea?:

• Si, para cuando la tarea padre llama a join() sobre una subtarea, dicha subtarea aún no ha comenzado su ejecución, dicha subtarea será extraída de la pila y el hilo que antes estaba asignado a la tarea padre será asignado a la subtarea, que comenzará su ejecución.
• Si, para cuando la tarea padre llama a join() sobre una subtarea, dicha subtarea ya ha comenzado su ejecución porque ha sido robada por otro hilo trabajador, el hilo que estaba asociado a la tarea padre extrae la siguiente tarea de la head de su cola de trabajo y la ejecuta en dicho hilo, o "roba" una tarea de la cola de trabajo de otro hilo, si su cola de trabajo está vacía, y así sucesivamente, hasta que la subtarea sobre la que se hice join() termine su ejecución en el hilo que la "robó".

Cada vez que el hilo termina de ejecutar una tarea, comprueba si la subtarea sobre la que había hecho join() ha termina su ejecución, de manera que en el momento en el que eso sea cierto, en vez de obtener otra tarea de su cola de trabajo para ejecutarla (o robar otra tarea), continúa con la ejecución de la tarea padre.