Changes between Initial Version and Version 1 of thead_scheduling

Timestamp:

May 19, 2016, 7:33:15 PM (9 years ago)

Author:

alain

Comment:

--

thead_scheduling

@@ +1 @@
+= Ordonnancement des threads =
+
+1) Problèmes liés à la distribution des thread
+
+Dans ALMOS, comme dans ALMOS-MK, il existe un ordonnanceur par CPU.
+Chaque ordonnanceur gère un nombre borné de threads, qui sont attaché à un CPU au moment de la création du thread, et qui ne migrent pas en cours d’exécution. 
+
+Un thread peut être dans 6 états en cours d’exécution:
+- 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)
+- 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.
+- 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 état CREATE et DEAD, sont des états transitoires lors de la création ou de la destruction du thread.e thread
+
+Dans ALMOS, les files d’attente utilisées dans les états READY et WAIT sont implémentés 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 la liste READY), ou dans la structure de donnée 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.
+Il s’agit donc de listes chaînées “trans-clusters”. 
+De même, l’ensemble des threads appartenant à un même processus est représenté
+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”.
+
+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 de type WAIT. et READY ainsi que la représentation de l’ensemble des thread d’un processus (liste ROPE).
+
+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 :
+- 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.
+- 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,
+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.
+
+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().
+
+2) Solutions envisagées
+
+2.1) Solution “pointeurs étendus”
+Elle consiste à modifier la bibliothèque de manipulation des listes double chaînées,
+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.
+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.
+
+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 externes”
+L’idée directrice est de supprimer toutes les listes chaînées “trans-clusters”.
+Les listes READY sont déjà mono-cluster par construction.
+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
+exclusivement gérées par le noyau du cluster K.
+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
+distribuée). Dans cette approche, toutes les modifications des listes WAIT 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 pour chaque modification d’une liste WAIT.