Changes between Version 1 and Version 2 of thead_scheduling


Ignore:
Timestamp:
May 20, 2016, 1:24:48 PM (6 years ago)
Author:
alain
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • thead_scheduling

    v1 v2  
    11= Ordonnancement des threads =
    22
    3 1) Problèmes liés à la distribution des thread
     3== 1) Généralités ==
    44
    55Dans ALMOS, comme dans ALMOS-MK, il existe un ordonnanceur par CPU.
     
    77
    88Un thread peut être dans 6 états en cours d’exécution:
    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 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.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.
    1414
    15 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).
     15== 2) Problèmes liés à la distribution des threads ==
     16
     17Dans 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).
    1618
    1719Les files d’attente de type WAIT posent un problème particulier pour ALMOS-MK.
    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”.
     20En 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''.
    2221
    23 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).
     22Le 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 la liste doublement chaînée interne ''rope'', 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''.
    2423
    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.
     24Ces 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''.
    2925
    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().
     26Un 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.
    3129
    32 2) Solutions envisagées
     30Le 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().
    3331
    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'' ===
     35Cette 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.
    3836
    3937Le principal avantage de cette solution est d’éviter le coût des RPCs, son principal
    4038inconvénient est que la re-écriture du code des schedulers peut constituer un travail important. 
    4139
    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'' ===
     41L’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.
     42Les 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.
    4943
    50 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.
     44Le 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.