A l'heure actuelle, un nombre important de solutions a été proposé pour ordonnancer des tâches temps réel à contraintes strictes. Plusieurs travaux s’en sont inspirés afin d’ordonnancer des transactions tout en respectant leurs caractéristiques ACID. Ces recherches se sont confrontées à deux problèmes majeurs : celui de la surcharge et du contrôle de concurrence. Cependant, au cours des dernières années, des applications "nouvelles" ont émergé pour lesquelles il n'est pas nécessaire de respecter toutes les échéances des tâches pourvu que les violations d'échéances soient suffisamment espacées dans le temps. Ces applications émergeantes dans les domaines des réseaux et du multimédia affichent des contraintes temps réel firm. En d'autres termes, les violations d'échéances autorisées entraînent uniquement des dégradations de Qualité de Service (QoS) sans compromettre le bon fonctionnement du système et sans mettre en danger son intégrité.
Dans cet axe, nous nous sommes intéressés à la combinaison de l'ordonnancement des transactions avec le contrôle de concurrence dans un contexte temps réel, multi-classes et soumis à des conflits de ressources. Nous avons considéré des applications temps réel souples, tolérants le dépassement de certaines échéances sur les transactions pourvu que les dépassements soient espacés dans le temps. Ces applications émergentes dans le domaine des réseaux et du multimédia affichent des contraintes dites (m,k)-firm où le paramètre m désigne le nombre d'échéances à respecter sur une fenêtre de k transactions consécutives. Nous avons travaillé sur un modèle de transactions à 3 classes où les transactions sont différenciées sur la base d'un paramètre Importance (haute, moyenne et faible) fixé par le développeur de l'application et où chaque classe de transactions est soumises à des contraintes (m,k)-firm différentes.
Dans ce contexte, l'ordonnancement consiste à extraire des transactions des files dans un ordre qui permet de respecter les contraintes (m,k)-firm des différentes files. Toutefois l'application directe des algorithmes de contrôle de concurrence n'est pas envisageable à ce modèle de transactions et l'ordonnancement ne doit pas être considéré indépendamment du contrôle de concurrence comme c'est le cas dans les SGBD classiques. En combinant l'ordonnancement des transactions avec le contrôle de concurrence, le résultat obtenu après l'ordonnancement n'est pas remis en question lors de l'exécution des transactions.
Nos recherches se sont soldées par la proposition d'un algorithme pour l'ordonnancement multi-classes de transactions Temps Réel appelé DBP_CC (Distance Based Priority with Concurrency Control). Cet algorithme est inspiré de DBP (Distance Based Priority) proposé par Hamdaoui en 1995, nous l'avons appelé DBP_CC le CC en référence au calcul de concurrence car il combine à la fois l'ordonnancement et le contrôle de concurrence pour les transactions.
Dans cet axe, nous nous sommes intéressés à la combinaison de l'ordonnancement des transactions avec le contrôle de concurrence dans un contexte temps réel, multi-classes et soumis à des conflits de ressources. Nous avons considéré des applications temps réel souples, tolérants le dépassement de certaines échéances sur les transactions pourvu que les dépassements soient espacés dans le temps. Ces applications émergentes dans le domaine des réseaux et du multimédia affichent des contraintes dites (m,k)-firm où le paramètre m désigne le nombre d'échéances à respecter sur une fenêtre de k transactions consécutives. Nous avons travaillé sur un modèle de transactions à 3 classes où les transactions sont différenciées sur la base d'un paramètre Importance (haute, moyenne et faible) fixé par le développeur de l'application et où chaque classe de transactions est soumises à des contraintes (m,k)-firm différentes.
Dans ce contexte, l'ordonnancement consiste à extraire des transactions des files dans un ordre qui permet de respecter les contraintes (m,k)-firm des différentes files. Toutefois l'application directe des algorithmes de contrôle de concurrence n'est pas envisageable à ce modèle de transactions et l'ordonnancement ne doit pas être considéré indépendamment du contrôle de concurrence comme c'est le cas dans les SGBD classiques. En combinant l'ordonnancement des transactions avec le contrôle de concurrence, le résultat obtenu après l'ordonnancement n'est pas remis en question lors de l'exécution des transactions.
Nos recherches se sont soldées par la proposition d'un algorithme pour l'ordonnancement multi-classes de transactions Temps Réel appelé DBP_CC (Distance Based Priority with Concurrency Control). Cet algorithme est inspiré de DBP (Distance Based Priority) proposé par Hamdaoui en 1995, nous l'avons appelé DBP_CC le CC en référence au calcul de concurrence car il combine à la fois l'ordonnancement et le contrôle de concurrence pour les transactions.
Une fois la priorité calculée, DBP_CC déroule un test pour l'extraction de la transaction qui datisfait au mieux à la fois les contraintes (m,k)-firm et les contraintes d'occupation de ressources.
Principe de l'algorithme DBP_CC
L'équipe dispose d'un simulateur de SGBDTR que nous avons modifié afin qu'il combine les aspects d'ordonnancement et de contrôle de concurrence. Nous avons ensuite intégré l'algorithme DBP_CC. Des simulations intensives de plusieurs algorithmes d'ordonnancement ont révélé des performances très satisfaisantes pour DBP_CC.
Publications sur l'algorithme DBP_CC:
- S. Limam, L. Baccouche, H. Ben Ghezala, Ordonnancement multi-classes de transactions temps réel sous contraintes (m,k)-firm, Actes des session doctorants, 5ème Ecole d'été Temps Réel, Nantes France, Sept. 2007.
- L. Baccouche, S. Limam, (m,k)-firm scheduling of real-Time transactions with concurrency control, in Proc. of ICONS '2007, IEEE computer society Press, USA, 2007.
