Ordonnancement des threads

1) Généralités

Dans ALMOS, comme dans ALMOS-MK, il existe un ordonnanceur par CPU. Chaque ordonnanceur gère un nombre borné de threads, qui sont attachés à un CPU au moment de la création du thread, et qui restent attachées à ce CPU jusqu'à la destruction du thread (pas de migration en cours d’exécution).

Un thread peut être dans 6 états:

• Dans l’état READY, le thread est éligible pour s’exécuter sur le CPU auquel elle est attachée. Tous les thread éligibles pour s'exécuter sur un CPU sont enregistrés dans une file d’attente. Il existe une file d’attente de type READY pour chaque CPU.
• Dans l’état WAIT, le thread est bloqué en attente de la disponibilité d’une ressource. Il est enregistré dans une file d’attente de tous les threads en attente de cette ressource. Il existe donc autant de files d’attentes que de ressources partagées.
• Dans les états USR ou KERNEL, le thread est en cours d’exécution sur son CPU, soit en mode user, soit en mode kernel. Il n’est enregistré dans aucune file d’attente.
• Les états CREATE et DEAD, sont des états transitoires lors de la création ou de la destruction du thread. Les threads dans l'état CREATE sont dans la même file d'attente que les threads dans l'état READY.

2) Problèmes liés à la distribution des threads

Dans ALMOS, les files d’attente utilisées dans les états READY et WAIT sont implémentées comme des listes doublement chaînées internes grâce au champs list de la structure thread_t. Ces listes chaînées ont une racine, qui est enregistrée dans la structure scheduler_t (pour les listes READY), ou dans la structure représentant la ressource convoitée (pour les listes WAIT).

Les files d’attente de type WAIT posent un problème particulier pour ALMOS-MK. En effet une liste READY est toujours locale à un cluster, mais une liste WAIT peut contenir un nombre quelconque de threads s’exécutant dans différents clusters. Le listes WAIT sont donc des listes chaînées trans-cluster.

Le même problème se pose pour les listes représentant l’ensemble des threads appartenant à un même processus, qui sont représentées dans ALMOS par une liste doublement chaînée interne (champs rope de la structure thread_t). La racine de cette liste chaînée est enregistrée dans la structure task_t représentant le processus. Les threads d’un même processus pouvant être distribués sur tous les clusters de l’architecture cette liste ROPE est également une liste chaînée trans-cluster.

Ces listes chaînées trans-cluster sont incompatibles avec la politique de confinement de l’approche multi-kernels, et le premier problème est donc la représentation de ces files d’attentes trans-cluster.

Un second problème est lié à la mise à jour dynamique les listes READY et WAIT lors des opérations d’ordonnancement liées aux accès aux ressources partagées :

1. prise de la ressource: un thread T s’exécutant sur un CPU P dans un cluster K se trouve bloqué sur une certaine ressource partagée située dans un cluster J (par exemple prise d’un mutex). Le noyau du cluster K doit enregistrer le thread T dans la liste WAIT dont la racine est dans le cluster J, avant de sélectionner un nouveau thread à exécuter sur le CPU P.
2. libération de la ressource: un thread T s’exécutant sur un CPU P dans un cluster K relâche une ressource partagée situé dans un cluster J (par exemple libération d’un mutex). Le noyau du cluster K doit identifier dans la liste WAIT le premier thread T’ en attente sur le mutex, retirer T’ de la liste WAIT dont la racine est dans le cluster J, et insérer le thread T' dans la liste READY du CPU chargé d’exécuter T’, qui peut se trouver dans un troisième cluster L.

Le second problème est donc lié à la modification à distance des files d’attente READY et WAIT, puisque dans ALMOS-MK, le noyau d'un cluster K ne peut accéder à des structures de données situées dans un autre cluster J qu’en utilisant soit des RPCs, soit des accès spéciaux remote_read() / remote_write().

2) Solutions envisagées

2.1) Solution pointeurs étendus

Cette solution consiste à modifier la bibliothèque de manipulation des listes double chaînées, de façon à utiliser des pointeurs étendus (PTR / CID) sur 64 bits pour les listes chaînées internes WAIT et ROPE. Il faut évidemment re-écrire les fonctions et macros de parcours de listes, mais la structure générale n’est pas modifiée. Pour ce qui concerne les modifications de ces listes, il est possible d’utiliser systématiquement des lectures / écritures distantes, puisque les modifications sont locales, et que chaque liste est protégée par un verrou, ce qui permet d'éviter les RPCs, mais qui peut créer des situations de contention.

Le principal avantage de cette solution est d’éviter le coût des RPCs, son principal inconvénient est que la re-écriture du code des schedulers peut constituer un travail important.

2.2) Solution listes chaînées externes

L’idée directrice est de supprimer toutes les listes chaînées “trans-clusters”. En effet, les listes READY sont déjà mono-cluster par construction. Les listes WAIT peuvent implémentées au moyen d’une liste chaînée externe, exclusivement gérée par le noyau du cluster K contenant la ressource partagée, et entièrement stockées dans le cluster K. La liste interne ROPE des thread d’un processus peut être représentée par un tableau (ou par un arbre) entièrement stocké dans la structure task_t représentant le processus. Dans cette approche, toutes les modifications des listes WAIT, READY sont réalisées par des RPCs.

Le principal avantage de cette solution est de respecter la philosophie générale de l’approche client/serveur. Son principal inconvénient est le coût des RPCs à chaque modification d'une liste WAIT.