Modèle de Réplication des Interactions

Modèle de Réplication des Interactions

Modèle de concurrence

La programmation d’applications de type mondes virtuels que sont les jeux-vidéo se fait bien plus naturellement en utilisant le paradigme de la programmation concurrente. En eet, il paraît tout naturel de décrire séparément le comportement des différents objets constituant le monde, au lieu de décrire séquentiellement à chaque instant la manière dont l’état global du monde apparaît. Ainsi, dans notre modèle, l’exécution d’un réflexe qui concerne un état/objet du monde peut représenter un traitement arbitrairement lourd en terme de ressources. La concurrence est donc une nécessité pour permettre à l’utilisateur de partager les ressources entre les réflexes selon leur complexité. Nous allons dans cette partie discuter et présenter la manière dont nous avons choisi d’introduire la concurrence dans le traitement des réflexes associés aux modèles de réplication. 

Un ordonnanceur équitable

Comme nous l’avons vu dans le chapitre 3, Les approches préemptives traditionnelles de la programmation parallèle sourent de plusieurs inconvénients par rapport aux objectifs que nous nous sommes xés, et principalement à celui qui consiste à essayer de simplier la vie de l’utilisateur. Ce style de programmation est complexe, à cause de la nécessité de contrôler l’accès à des données partagées, et de la diculté à déterminer quand auront lieu les changements de contexte. De plus, chercher les erreurs dans un programme écrit à l’aide de ce modèle devient très vite un cauchemar à cause de la non reproductibilité qu’il implique souvent, d’une exécution du programme à l’autre. Le modèle que nous avons choisi est inspiré par le modèle Cooperative Fair-Thread [20], coopératif et équitable, étudié au chapitre 3 (voir section 3.1.3, page 75). Notre modèle est coopératif, et donc plus facile à manipuler pour l’utilsateur qui contrôle, à l’aide d’une instruction cooperate quand chaque tâche rend la main à l’ordonnanceur pour qu’il passe à une autre tâche en cours. Le modèle d’ordonnancement des tâches est reproductible et équitable, donnant la main à chaque tâche à tour de rôle. Ainsi, modulo les événements provenant du réseau et des autres processus extérieurs au framework pouvant modier l’état local du jeu (comme par exemple une interface graphique), la sémantique de l’exécution du programme est clairement dénie, facilitant les tests, la mise au point et la maintenance de l’application. On se retrouve donc avec un modèle de concurrence à deux niveaux :  le premier est préemptif, et consiste à gérer l’accès à la mémoire partagée des différents processus principaux : réception des réplications arrivant par le réseau, des événements de l’interface utilisateur, rendu graphique, et de l’ordonnanceur équitable qui organise l’exécution des réflexes. Il correspond au découpage présenté au chapitre précédent dans la gure 4.2 ;  le deuxième niveau est coopératif et équitable. C’est l’ordonnanceur équitable des réflexes. Chacun des réflexes représente une tâche, qui sera exécutée par l’ordonnanceur dans un processus léger. Les réflexes sont attachés à la le d’exécution de l’ordonnanceur dans l’ordre dans lequel ils ont été déclenchés par leur temporalité. Un réflexe est déni par l’utilisateur comme une suite de sections critiques d’instructions, entre chaque invocation de l’instruction cooperate qui redonne la main à l’ordonnanceur. Lorsqu’un réflexe est déclenché, le code correspondant est attaché à la le d’exécution de l’ordonnanceur. Les segments d’instructions sont ensuite exécutés de manière équitable : quand plusieurs réflexes sont en cours d’exécution en parallèle, l’ordonnanceur exécute tour à tour dans l’ordre dans lequel elles ont été déclenchées, les premières sections critiques encore à traiter de chacun d’entre eux. Quand un réflexe est attaché à la le de l’ordonnanceur, sa première section critique sera traitée dès que les réflexes en cours d’exécution seront terminés ou auront rendu la main à l’ordonnanceur. Le mécanisme d’ordonnancement est illustré par la gure 5.1 : elle présente l’ordonnancement de l’exécution de trois réflexes dans trois processus légers, divisés en plusieurs sections critiques à l’aide de l’instruction cooperate.  Les deux premiers réflexes ont été ajoutés simultanément à la le d’exécution. Le troisième a été attaché à l’ordonnanceur à un moment donné de l’exécution des deux premières sections critiques des deux premiers réflexes.

Les copies d’états et les instructions ash et update

Il y a un autre problème à prendre en considération, introduit par l’utilisation d’un ordonnanceur pour gérer l’exécution des réflexes : certains calculs sont plus faciles à décrire par un réflexe utilisant les valeurs des états au moment de leur déclenchement : par exemple, le contrôle de la validité du mouvement d’un joueur, ou, plus généralement, quand la condition utilisée par l’attribut de temporalité de l’ordonnançable n’est plus vériée lors du traitement effectif du réflexe. Or, les valeurs des états intervenant dans le calcul peuvent avoir été modiées avant l’exécution du réflexe par l’ordonnanceur, soit par un réflexe exécuté dans l’intervalle, soit par un des autres processus écrivant dans la mémoire partagée locale de l’application. Cependant, d’autres styles de calcul sont plus facilement décrits lorsqu’on peut disposer de valeurs à jour des états : par exemple, lorsqu’on veut ajouter ou retrancher une valeur d’un état donné. On peut aussi vouloir détecter facilement le fait qu’un calcul devienne obsolète entre le déclenchement et l’exécution d’un réflexe, comme un calcul de recherche de chemin. Pour pouvoir utiliser les deux formes de calcul, qui correspondent aux deux manières traditionnelles de traiter les mises à jour de l’état d’une application (passage de message et mise à jour par delta), les réflexes sont exécutés avec des copies des états, eectuées lors du déclenchement de l’ordonnançable, avant leur rattachement à l’ordonnanceur. L’utilisateur précise la manière dont ces copies sont synchronisées avec les états à jour de la mémoire partagée. Pour dénir un ordonnançable, l’utilisateur décrit les états dont il a besoin pour le calcul des conditions de déclenchement et le réflexe associé. Il utilise pour ce faire les deux instructions ash et update, dont nous allons dénir le comportement pour les deux catégories auxquelles peuvent appartenir ces états.  l’ensemble des états en entrée : ce sont les états utilisés dans le calcul et les attributs des réflexes. Les valeurs de ces états sont copiées localement quand le réflexe est déclenché.  l’ensemble des états en sortie : ce sont les états modiés par les réflexes. L’instruction ash, utilisable dans le code d’un réflexe, réactualise toutes les copies d’états en entrée et en sortie avec les valeurs à jour des états de la mémoire partagée. Cette instruction est récursive sur les sous-états. Quand le calcul nécessite des valeurs d’état à jour, le développeur peut utiliser l’instruction ash, pour synchroniser les copies des états avec leurs valeurs à jour. Le caractère récursif de cette instruction a été décidé pour simplier la description des ordonnançables, ainsi que nous le verrons plus loin. Définition 5.2.3 L’instruction update, utilisable dans le code d’un réflexe, aecte la valeur d’une copie d’état en sortie à l’état correspondant de la mémoire partagée. Cette instruction n’est pas récursive sur les sous-états. Le développeur est donc responsable de la synchronisation du résultat d’un calcul avec la mémoire partagée. Selon cette sémantique, l’utilisateur a la garantie qu’entre une instruction ash et une instruction cooperate, la valeur d’un état ne peut pas être modiée par l’exécution d’un autre réflexe. Donc, si l’application est conçue an qu’un état donné ne soit pas directement modiable par le réseau (comme c’est par exemple le cas pour un état purement local qui n’est pas sujet à une réplication par hôte distant) ou un autre processus extérieur au framework et opérant sur la mémoire partagée, la valeur d’un état et la valeur de sa copie locale pour le réflexe correspondent d’un ash à un cooperate. Ainsi, notre modèle permet d’utiliser les deux styles de gestion d’état, par message ou mise à jour par delta, sans trop sacrier à la simplicité d’utilisation du modèle d’ordonnancement : la sémantique de l’exécution des réflexes est reproductible modulo les événements provenant des tâches gérées par la couche supérieure préemptive. Nous dénissons ainsi un modèle dont le seul mode de communication entre les réflexes se fait par le biais d’une mémoire partagée, ce qui constitue la principale diérence avec l’approche réactive des Fair-Threads.