| 9 | | - Dans l’état READY, le thread est éligible pour s’exécuter sur e CPU auquel elle est attachée. Tous les thread éligibles pour un CPU sont enregistrés dans une file d’attente de tous les threads éligibles pour ce CPU. Il existe une file d’attente de type READY pour chaque CPU.(champs “list” de la structure thread_t) |
| 10 | | - Dans l’état WAIT, le thread est bloqué en attente de la disponibilité d’une ressource. Le thread est enregistré dans une file d’attente de tous les threads en attente de cette ressource. Il existe autant de files d’attentes que de ressources partagées. |
| 11 | | - Dans les états USR ou KERNEL, le thread est en cours d’exécution sur son CPU, |
| 12 | | |
| 13 | | - Les état CREATE et DEAD, sont des états transitoires lors de la création ou de la destruction du thread.e thread |
| | 9 | * 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. |
| | 10 | (champs “list” de la structure thread_t) |
| | 11 | * 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. |
| | 12 | * 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. |
| | 13 | * Les état '''CREATE''' et '''DEAD''', sont des états transitoires lors de la création ou de la destruction du thread. |
| 18 | | 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. |
| 19 | | Il s’agit donc de listes chaînées “trans-clusters”. |
| 20 | | De même, l’ensemble des threads appartenant à un même processus est représenté |
| 21 | | dans ALMOS par une liste doublement chaînée interne, grâce au 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 thread 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-clusters”. |
| | 20 | 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. Il s’agit donc de listes chaînées ''trans-clusters''. |
| 25 | | Un second problème est lié à la mise à jour dynamique les listes READY et WAIT lors des opérations d’ordonnancement liées aux ressources partagées : |
| 26 | | - premier scénario: 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. |
| 27 | | - second scénario: 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 le premier thread T’ en attente sur le mutex, |
| 28 | | retirer T’ de la liste WAIT dont la racine est dans le cluster J, et l’introduire dans la liste READY du CPU chargé d’exécuter T’, qui peut se trouver dans un troisième cluster L. |
| | 24 | 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-clusters''. |
| 30 | | Le second problème est donc lié à la modification à distance des files d’attente READY et WAIT, puisque ALMOS-MK ne peut accéder à des structures de données distantes qu’en utilisant soit des RPCs, soit des accès directs remote_read() / remote_write(). |
| | 26 | 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 : |
| | 27 | 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. |
| | 28 | 1. 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. |
| 34 | | 2.1) Solution “pointeurs étendus” |
| 35 | | Elle consiste à modifier la bibliothèque de manipulation des listes double chaînées, |
| 36 | | pour utiliser des pointeurs étendus (PTR / CID) sur 64 bits pour représenter les listes 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. |
| 37 | | 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. |
| | 32 | == 2) Solutions envisagées == |
| | 33 | |
| | 34 | === 2.1) Solution ''pointeurs étendus'' === |
| | 35 | 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. |
| 42 | | 2.2) Solution “listes externes” |
| 43 | | L’idée directrice est de supprimer toutes les listes chaînées “trans-clusters”. |
| 44 | | Les listes READY sont déjà mono-cluster par construction. |
| 45 | | Les listes WAIT sont implémentés au moyen d’un chaînage “externe” et sont entièrement stockées dans le cluster K contenant la ressource partagée, et |
| 46 | | exclusivement gérées par le noyau du cluster K. |
| 47 | | La liste des thread d’un processus est représentée par un tableau (ou un arbre) stocké dans la structure task_t représentant le processus (au lieu de la liste ROPE |
| 48 | | distribuée). Dans cette approche, toutes les modifications des listes WAIT sont réalisées par des RPCs. |
| | 40 | === 2.2) Solution ''listes chaînées externes'' === |
| | 41 | 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. |
| | 42 | 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. |
