Structure de données pour systèmes temps-réel multiprocesseur : l'exemple des arbres rouge-noirs

Frédéric Fauberteau (1) , Serge Midonnet (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

Dans un système temps réel multitâches, le partage de structures de données impose la synchronisation des opérations de mise à jour et conduit à des accès séquentiels. Ce qui ne permet pas de profiter pleinement des ressources processeur disponibles. Dans cet article, nous présentons un nouveau type de structure de données adapté aux environnements temps réel multiprocesseur. Les données sont stockées dans les feuilles permettant une synchronisation locale. L'équilibrage de la structure n'est plus effectué lors des mises à jour mais dans les temps creux du système. Nous montrons son efficacité en mesurant les temps de réponse moyen et en estimant le comportement pire cas.

Domaines: Algorithme et structure de données [cs.DS]

Frédéric Fauberteau, Serge Midonnet. Structure de données pour systèmes temps-réel multiprocesseur : l'exemple des arbres rouge-noirs. 3ème Workshop sur la Cohérence des données en Univers Réparti (CDUR'09), Sep 2009, France. pp.7-10. ⟨hal-00620307⟩