|
Sécurité dans les systèmes temps réel( Télécharger le fichier original )par Thomas Vanderlinden Université Libre de Bruxelles - Licence en Informatique 2007 |
Chapitre 5Simulations5.1 Introduction Le but principal de ce chapitre sera d'essayer en se basant sur l'idée développée au chapitre 4 de développer un algorithme permettant d'attribuer des durées plus ou moins longues aux parties optionnelles des différents travaux, lorsque la récompense évolue de manière convexe en fonction de ce temps. Pour parvenir à ce but, nous avons du implémenter un simulateur nous permettant de tester si le système est toujours ordonnançable avec les durées choisies. Nous allons donc dans ce chapitre montrer comment nous générons un ensemble de tâches formant ce système. Ensuite nous présenterons deux méthodes heuristiques que nous avons implémentées : le recuit simulé et la recherche tabou. Nous ferons une comparaison des résultats obtenus avec ces méthodes par rapport à l'algorithme présenté dans le chapitre précédent (section 4.2.7) qui est optimal dans le cas où les fonctions de récompense sont linéaires et nous effectuerons ensuite une comparaison avec des fonctions convexes de récompense. 5.2 Génération d'un système 5.2.1 Génération des périodes Un système est composé de tâches, chaque tâche Ti lance une instance (un travail) à chaque instant kPi V k = 0. La simulation devant être effectuée sur l'intervalle [0, P], il est indispensable lors de la génération de cet ensemble de tâches, de choisir judicieusement les valeurs des périodes Pi des différentes tâches. En effet, si Pi est choisi de manière arbitraire entre deux bornes, et si le nombre de tâches est important, cela pourrait nous amener à ce que le plus petit commun multiple de ces valeurs soit énorme. La simulation serait donc beaucoup plus longue à effectuer étant donné qu'il faut simuler l'évolution du système jusqu'à l'hyperpériode P = ppcm {Pi} V Ti. Nous avons donc décidé, afin de faciliter nos simulations d'utiliser la technique exposée dans [8] qui consiste à choisir la période comme un multiple des premières puissances de nombres premiers: YPi = pup {p|p est premier} où p est un nombre premier et up est la puissance de p sélectionnée au hasard. Une matrice contient un ensemble de nombres premiers et leurs premières puissances (ex : 21, 22, ...). De manière à ne pas obtenir des périodes trop importantes, nous avons construit cette matrice avec de petits nombres premiers (p | p est premier E [2, 11]) et surtout de petites puissances (u p E [1,2]), nous avons choisi d'utiliser dans notre simulation la matrice ÷ :
L'algorithme (repris de [8]) qui retourne une période à partir de la matrice ÷ est décrit ci-dessous :
Algorithme 4: Détermine la période Sur chaque ligne, l'algorithme sélectionne une valeur et il multiplie les valeurs sélectionnées entre elles. Avec la matrice x, la période maximum est donc : 4 x 9 x 25 x 7 x 11 = 69300, c.-à-d. le produit des valeurs les plus importantes sur chaque ligne, c'est aussi la taille de la plus grande hyperpériode car n'importe quelle autre période calculée sera automatiquement un diviseur de 69300. 5.2.2 Génération de l'ensemble de tâches Nous générons ensuite l'ensemble des tâches Ti avec leurs caractéristiques: - Pi : La période, générée par l'algorithme 4 ci-dessus; - mi : le temps d'exécution de la partie obligatoire; - oi : le temps d'exécution maximal de la partie optionnelle. - coeffi : qui est le coefficient de la fonction de récompense de la tâche Ti, nous le choisirons au hasard entre 1 et 100. L'instant d'arrivée Ai = 0 V Ti et l'échéance Di = Pi V Ti, car nous travaillons sur des systèmes à départ simultané et à échéance sur requête. Il s'avère compliqué de générer au hasard un système composé d'exactement n tâches avec un facteur global d'utilisation Um, n et Um étant fournis en entrée à l'algorithme. Soit le nombre de tâches est correct mais l'utilisation n'est pas proche de Um, soit l'utilisation est proche de Um mais le nombre de tâches est différent de n. Nous avons donc écrit deux algorithmes : l'algorithme 5 génère un système d'exactement n tâches indépendamment de l'utilisation, l'algorithme 6 génère un certain nombre de tâches avec un facteur d'utilisation des parties obligatoires se rapprochant le plus possible de Um passé en paramètre. Entrée : n Sortie : Ensemble de tâches i<--0 utilisation_courante <-- 0 Tant que (i n) faire P <-- période générée par l'algorithme 4 m <-- random(0, P)) o <-- P -- m coeff <-- random(1,100) taskU <-- mP Si (utilisation_courante + taskU < 1) Alors utilisation_courante <-- utilisation_courante + taskU AjoutTache(P, m, o, coeff) i <-- i + 1 Fin Si Fait Algorithme 5: Génération d'un ensemble de n tâches
Algorithme 6: Génération d'un ensemble de tâches avec un facteur d'utilisation proche de Um L'utilisateur donne en paramètre l'utilisation du système par les parties obli- mi gatoires (pour rappel : Um = Pn Pi ) dont il voudrait se rapprocher ou le nombre i=1 de tâches : n. Tant que l'on ne dépasse pas le facteur d'utilisation ou le nombre de tâches désiré selon l'algorithme, on génère une nouvelle tâche. La période est calculée à partir de l'algorithme 4, le temps d'exécution de la partie obligatoire est choisi au hasard entre 0 et la période jusqu'à ce que le système ait atteint l'utilisation ou le nombre de tâches désiré. Nous avons d'autre part décidé de choisir des durées maximales pour les parties optionnelles de mêmes longueurs que le temps restant avant l'échéance laissé par les parties obligatoires, soit pour chaque tâche Ti, oi = Pi - mi. Dans l'algorithme 6, si l'utilisation courante en tenant compte de la tâche venant d'être générée ne dépasse pas Um, nous rajoutons la tâche et augmentons l'utilisation courante. Dans l'algorithme 5, nous vérifions uniquement que les parties obligatoires soient ordonnançables après avoir ajouté la tâche (utilisation_courante + taskU < 1). 5.3 L'algorithme orienté évènement Comme nous l'avons expliqué au chapitre précédent, il nous a fallu mettre au point un algorithme d'ordonnancement basé sur la notion d'évènements et non plus un algorithme qui effectue une incrémentation du temps à chaque tour de boucle. Dans cette section, nous fournirons au lecteur une description de l'algorithme « Event-driven » 7 et de la façon dont nous avons implémenté celui-ci. Nous utiliserons les termes : - « Arrivée » : pour désigner l'évènement qui, pour une tâche donnée, annonce l'arrivée dans le système d'un nouveau travail et l'échéance du travail précédent de cette tâche par la même occasion; - « FinJob » : pour l'évènement qui annonce la terminaison d'un travail. Le système comporte en plus des caractéristiques des différentes tâches, une file d'évènements. Chaque évènement que l'on peut insérer dans cette file comporte 4 informations : 1. le temps : c'est-à-dire l'instant auquel cet évènement doit se déclencher;
5.3.1 La gestion des évènements Comme nous l'avons mentionné plus haut, il y a deux types d'évènements possibles. Lorsqu'un de ceux-ci se déclenche, l'algorithme fait appel à sa routine de gestion. Voici comment celle-ci procède en fonction du type de l'évènement. - Arrivée : Lorsqu'une arrivée survient pour la tâche Ti, on vérifie premièrement le respect de l'échéance, c.-à-d. qu'on vérifie que le travail précédent soit bien terminé, si tel n'est pas le cas, le système n'est pas ordonnançable et la simulation peut donc s'arrêter. Ensuite, on signale qu'un travail est prêt à être exécuté pour Ti et on insère l'arrivée suivante à l'instant t + Pi dans la file des évènements, où t est l'instant courant. - FinJob : Le travail qui se termine est marqué comme terminé. L'insertion triée dans la file des évènements se base à la fois sur l'instant de déclenchement, mais aussi sur le type de l'évènement à rajouter. Il est indispensable de gérer les évènements qui se produisent au même instant dans l'ordre suivant:
La gestion de l'événement « Arrivée » comprend également la gestion des échéances qui contrôle premièrement l'échéance du travail précédent avant d'en lancer un nouveau. Etant donné que nous travaillons sur des systèmes à échéance sur requête, il est inutile de gérer un évènement « Echéance ». En effet, si la fin d'un travail survient au même instant que l'échéance de sa tâche, le système est ordonnançable. Il faut donc que le travail soit marqué comme terminé avant de tester s'il reste un travail pour cette tâche. Dans le cas contraire, la gestion de l'échéance nous renverrait qu'il y a encore un travail en cours d'exécution et que le système n'est donc pas ordonnançable, ce qui est faux. Il ne faut donc pas non plus lancer un travail 'rij avant de tester l'échéance de 'ri ,j-1, pour les mêmes raisons. 5.3.2 L'algorithme Basant notre simulation sur des systèmes à départ simultané, au début de l'exécution de l'algorithme nous rajoutons dans la file d'évènements une Arrivée à l'instant 0 pour chaque tâche présente dans le système.
Voici l'algorithme de la simulation basée sur les évènements en pseudocode (algorithme 7). currenttime ? O; Pour Chaque tâche T faire insère Arrivée(T, instant O) Fin Pour Tant que (currenttime = hyperpériode) faire Tant que (currenttime = temps de l'évènement au sommet) faire EV ? évènement au sommet de la file currenttime ? temps de l'évènement EV gérer EV (voir section 5.3.1) supprimer EV Fait PRIOR ? travail le plus prioritaire rem ? temps de l'évènement suivant -currenttime Si (remjob = rem) Alors insère FinJob(PRIOR, currenttime + remjob) Sinon remjob ? remjob - rem /*remjob est une variable appartenant au travail le plus prioritaire actuel et initialisée à son temps d'exécution.*/ Fin Si travail courant ? état wait PRIOR ? état run Fait Algorithme 7: Ordonnanceur basé sur la gestion d'évènements Il serait possible de rendre ce simulateur plus général, de façon à ce qu'il puisse gérer les échéances arbitraires et les départs différés (ce qui ne nuit pas à l'optimalité d'EDF). Il faudrait alors en ajoutant un évènement « Echéance », séparer la gestion des arrivées dans laquelle on vérifiait que l'échéance soit respectée en même temps que la gestion de l'arrivée du travail suivant. L'instant de départ Ai pouvant être différent d'une tâche Ti à l'autre il faudra effectuer le test d'ordonnançabilité sur un intervalle : [min {Ai} , P + max {Ai}]. Cependant, ici nous nous focaliserons sur des systèmes à départ simultané et à échéance sur requête, inutile donc de rendre la simulation plus longue en temps de calcul. 5.4 Rappel du problème d'optimisation des temps optionnels Nous allons maintenant reprendre le problème d'optimisation analysé dans le chapitre précédent. Problème:
à condition que 0 tij oi i = 1, ... , n j = 1, ... , bi (5.2) Il existe un ordonnancement faisable avec les valeurs {mi} et {tij}. (5.3) où bi pour rappel, est le nombre de fois que l'on peut placer la période de la tâche Ti dans l'hyperpériode, soit bi = P/Pi. La fonction à maximiser représente la somme des moyennes des récompenses pour chaque tâche du système, la récompense d'un travail ôij étant obtenue par la fonction fi(tij). Ci Si le facteur d'utilisation U = Pn Pi 1 alors un algorithme utilisant EDF i=1 comme politique d'ordonnancement trouverait un ordonnancement faisable. Mais étant donné que les tij peuvent être de durées différentes, nous ne pouvons pas utiliser cette condition nécessaire et suffisante sur la faisabilité de l'ordonnancement. En effet, dans notre cas, le temps d'exécution Ci = mi + tij peut varier d'un travail à l'autre comme les tij ne sont pas forcément identiques pour une tâche Ti donnée, le calcul du facteur d'utilisation du système n'a donc plus de sens. Nous continuerons néanmoins à parler d'utilisation en ne prenant en compte que les parties obligatoires des tâches. D'après nos contacts avec H. Aydin, il n'existe pas d'autres moyens que celui de simuler l'ordonnancement jusqu'à l'hyperpériode P. Il est néanmoins possible de poser une condition nécessaire supplémentaire de manière à ne pas avoir à simuler l'ordonnancement jusqu'à l'hyperpériode lorsque celle-ci n'est pas respectée. Xn bimi + Xn Xbi tij P (5.4) i=1 i=1 j=1 Si la condition 5.4 n'était pas respectée, cela reviendrait à dire qu'il y aurait plus d'unités d'exécution, parties obligatoires et optionnelles confondues, que le nombre d'unités disponibles entre l'instant 0 et l'hyperpériode. Cette condition n'est malheureusement pas suffisante pour garantir que le système est faisable. Il est possible de réexprimer l'équation 5.4 de ce problème comme: >2n >2bi tij = d = P -- >2n bimi i=1 j=1 i=1 Où d est la latitude maximum disponible après avoir déjà ordonnancé les parties obligatoires jusqu'à l'hyperpériode P. Nous pourrons donc ordonnancer dans ces d unités de temps oisives les parties optionnelles. Il nous faut trouver les valeurs des tij qui maximisent l'équation 5.1 tout en respectant les contraintes formulées par les équations 5.2 et 5.3. Comme nous l'avons montré au chapitre 4 (page 45), l'augmentation de la sécurité en fonction du temps est mieux représentée par une fonction convexe, mais le problème étant NP-COMPLET lorsque les fonctions de récompenses sont convexes, nous utiliserons des méthodes heuristiques pour trouver une solution se rapprochant le plus possible de la solution optimale. Nous citerons et décrirons dans ce chapitre les méthodes heuristiques de base permettant de répondre à ce problème d'optimisation. 5.5 Notations utilisées Nous utiliserons quelques notations pour présenter ces algorithmes : - xn : est la solution courante à l'étape n, dans notre problème elle sera constituée de : - un tableau stockant les valeurs des tij; - la récompense obtenue avec ces valeurs. Remarque: Notons que nous utilisons ici le terme « solution » pour désigner ce qui n'est en réalité qu'une tentative de solution et non la solution finale au problème. Cette solution courante peut ne pas être ordonnançable et ne sera alors très certainement pas retenue comme la meilleure solution. - X : est l'ensemble de toutes les solutions valables (qui respectent les contraintes 5.1, 5.2 et 5.3) dans lequel la solution finale sera choisie par l'algorithme utilisé. - V(xn) : est le voisinage de la solution xn, c'est donc un ensemble de solu- tions qui se rapprochent par leurs caractéristiques de la solution xn. Toute la difficulté étant de trouver une manière de définir ce rapprochement dans le contexte de l'ordonnancement des parties optionnelles. Nous expliquerons dans la section 5.8 comment nous obtenons une solution voisine. - F(xn) : représente le retour de la fonction objectif, autrement dit la récompense obtenue avec cette solution xn. Dans notre contexte, cela représente donc la récompense accrue par les tij de la solution x n (équation 5.1). Si le système n'est pas ordonnançable après avoir effectué une simulation avec xn, F(xn) sera nul. 5.6 Le recuit simulé Le principe de cet algorithme est basé sur les techniques de recuit utilisé en sidérurgie. Le métal est chauffé de manière à fournir une certaine énergie au système qui permet aux atomes de se déplacer. Les atomes se positionnent de façon à libérer le métal de toutes tensions internes dues aux déformations ayant été appliquées au métal. Ensuite la baisse de température fige lentement les atomes dans une position d'énergie minimale. L'algorithme du recuit simulé gardera donc ce même principe. Au début de son exécution, l'algorithme autorise des changements importants de la solution courante ensuite la solution se fige peu à peu et le système finit par se geler dans un optimum global. On part de la solution initiale x0, pour laquelle tous les temps optionnels (tij) valent O, la récompense est donc minimale étant donné qu'on travaille sur des fonctions non-décroissantes. En toute logique, on pourrait même travailler avec des fonctions de récompense de la forme fi(0) = O ?i car une récompense n'est pas utile si la partie optionnelle est nulle. A chaque étape n, une solution voisine x de la solution courante xn (c'est-àdire ? V(xn)) est choisie au hasard, nous expliquerons à la section 5.8 comment nous sélectionnons la solution voisine. Si la récompense accrue grâce à cette solution est meilleure qu'avec la précédente, c.-à-d. si F(x ) est meilleur que F(xn), x devient la nouvelle solution courante. Autrement, on tire au sort selon une certaine probabilité p, le fait de garder la solution x n ou de choisir x comme nouvelle solution pour l'étape n+ 1. Remarque: Même si ce nouvel ensemble de durées pour les parties optionnelles est moins intéressant au niveau de la récompense, cela pourrait devenir par après plus avantageux car nous pourrions rebondir sur une meilleure solution que xn par la suite, c'est ce qu'on appelle la phase de diversification. Nous notons p, la probabilité de prendre x comme nouvelle solution malgré le fait que la récompense obtenue avec x soit inférieure à celle obtenue avec la solution précédente xn. La probabilité p diminue lorsque la température T baisse, et ce de manière à figer petit à petit la solution. p est donc calculé en fonction de la température T mais aussi en fonction de la diminution de récompense IF subie en acceptant x comme nouvelle solution. IF = F(xn) - F(x ) La fonction p(T, IF) a été reprise par analogie au recuit en sidérurgie, il s'avère expérimentalement que la distribution de Boltzmann ci-dessous est un bon choix pour calculer p [20]. T p(T,IF) = e- ÄF La température T quant à elle est fonction du temps et diminue par palier de manière géométrique, tous les L tours de boucle de l'algorithme. On choisit une température initiale T0 qui ne diminue pas durant L tours, ensuite la température diminue à T1 = aT0 après L tours, T2 = a2T0, et ainsi de suite. Après kL tours de boucle la température vaudra Tk = akT0. Les valeurs T0, L et a doivent être choisies expérimentalement: - La température initiale T0 est calculée par rapport à la probabilité p souhaitée au début de l'exécution de l'algorithme. Exemple : Si l'on souhaite obtenir une probabilité de 50% d'accepter une solution qui est moins bonne que la solution courante, il faut que e 50%, autrement dit, que T0 = hÄFi ln 2 . (IF) est la moyenne des détériorations déduite par simulation. Avant l'exécution à proprement parlé du recuit simulé, nous effectuons 100 tours de boucle afin de calculer cette moyenne et de fixer la valeur T0. - L, dépend de l'importance du voisinage de la solution. En effet, la phase d'exploration devra durer plus longtemps avant de diminuer la température si le nombre de solutions voisines est important. Le nombre de possibilités de solutions voisines dépend ici du nombre de travaux présents jusqu'à (ÄF) T0 = l'hyperpériode, qui est proportionnel au nombre de tâches dont est composé le système. Nous avons donc décidé de donner comme valeur à L ce nombre de tâches. - Plus á est important, plus le refroidissement sera lent, nous avons choisi á = 0,95. Ci-dessous, nous avons repris un algorithme de base (issu de [20]) en le modifiant légèrement, sans entrer dans les détails du calcul des variables, pour présenter de manière intuitive le principe de fonctionnement de celui-ci au lecteur.
Algorithme 8: Recuit simulé - Squelette de base où Fà est la sauvegarde du meilleur retour obtenu par la fonction objectif. La condition d'arrêt peut être de différents types: - Pour reprendre l'analogie avec le recuit en sidérurgie, nous pourrions nous arrêter lorsque la température est descendue en dessous d'une certaine borne; - ou lorsque la fonction F n'a pas augmenté de 0, 1% pendant 100 paliers consécutifs; - mais afin de comparer le plus justement possible le recuit simulé avec la recherche tabou (que nous analyserons à la section 5.7), nous stopperons la recherche après un nombre fini d'itérations (1000) afin d'attribuer le même temps processeur aux deux algorithmes. 5.7 La recherche tabou Le principe de la recherche tabou est d'associer à l'algorithme de base, une mémorisation des solutions visitées. L'algorithme de la recherche tabou ne prend pas en compte le facteur température utilisé dans le recuit simulé. La mémoire est constituée d'une liste « tabou », qui empêche de multiples cycles dans l'algorithme, elle est appelée tabou car une solution dont les caractéristiques correspondent à celles rencontrées dans la mémoire ne sera pas reprise comme solution courante. Nous parlons ici de caractéristiques car il est possible de limiter la taille de la mémoire tabou en ne prenant en compte que quelques caractéristiques au lieu de devoir comparer tout le tableau des valeurs tij. Nous enregistrerons dans cette liste les permutations effectuées sur les parties optionnelles lors de l'obtention d'une solution voisine (voir section 5.8). La liste tabou est gérée de manière FIFO (First in / First out), ce qui veut dire que les changements récents remplacent les plus anciens, cela empêche donc de refaire un changement que l'on vient d'effectuer et de cycler sur les permutations. Cependant, il est à noter qu'un cycle plus long que la taille de la mémoire reste possible, mais nous avons remarqué qu'avec une taille suffisante de permutations enregistrées (à partir de 10, valeur que nous avons choisie pour notre implémentation de l'algorithme) les situations de cycles restent rares, le nombre de choix parmi les temps optionnels des travaux à permuter pouvant être important. A chaque étape n, on extrait du voisinage de la solution courante V(xn), un sous-voisinage que nous notons V*. Une fois V* extrait, toutes les solutions de cet échantillon sont comparées et la meilleure solution (x*) dont les caractéristiques ne sont pas tabou, est enregistrée dans la mémoire et comme nouvelle solution courante xn+1. Le fait que x n offre une meilleure récompense n'a pas d'importance. Cela permet de garder le principe d'exploration des solutions et de ne pas rester calé dans un maximum local. Cependant il est possible de rajouter des critères qui pourraient autoriser une solution tabou à être réutilisée. Une augmentation forte de la récompense pourrait être un critère. Nous réutilisons une solution tabou si toutes les solutions de V* sont tabou, nous sélectionnons alors la meilleure parmi celles-ci. Si c'était possible, on prendrait V* = V(xn) mais dans notre cas, cela serait fort coûteux en temps de calcul de trouver la meilleure solution de tout le voisinage. Nous préférons donc tirer au sort un échantillon de V(xn) afin d'obtenir V*. Nous nous sommes à nouveau basé sur l'algorithme issu de l'ouvrage [20] que nous avons légèrement modifié pour présenter la structure de base de la recherche tabou que voici :
Algorithme 9: Recherche Tabou - Squelette de base Nous avons effectué des simulations afin de déterminer la taille idéale L du sous-voisinage V*. Cette taille dépend du nombre de tâches étant donné que chaque tâche possède sa propre fonction de récompense. Nous avons donc choisi de calculer cette taille par la formule 5.5. L = x. nbtaches (5.5) où nbtaches est le nombres de tâches présentes dans le système et x est un coefficient que nous avons déduit par simulation. Nous avons effectué 1000 simulations de l'algorithme de la recherche tabou pour plusieurs valeurs de x différentes, sur un même système composé de 6 tâches. Nous avons comparé la récompense moyenne par rapport à l'algorithme optimal, pour chaque valeur de x, voir graphique 5.1. Nous en sommes arrivés à la conclusion que la meilleure valeur pour la taille de V est L = 41 nbtaches
FIG. 5.1 - Recherche de la meilleure taille du sous-voisinage 5.8 Obtention d'une solution voisine Sur base d'une solution xn, l'algorithme du recuit simulé doit construire une solution voisine x qui se rapproche par ses caractéristiques de la solution xn, l'algorithme de la recherche tabou doit fournir un voisinage V(xn), c.-à-d. un ensemble de solutions voisines de xn. Après avoir simulé le système avec la solution xn, nous procédons comme suit pour obtenir une solution voisine :
In i=1 bimi + In Ibi j=1 tij P a été violée, le système n'est pas ordonnan- i=1 çable, on sélectionne alors un
tij au hasard parmi un ensemble S
constitué En effet, diminuer les temps optionnels est dans ce cas le seul moyen de récupérer un système ordonnançable. S'il n'existe pas de tels travaux (S est vide), rien n'est diminué mais lorsque le palier aura atteint une valeur suffisamment petite, S ne sera plus vide. 3. De plus, nous permutons (avec une probabilité de 50%) deux tij du tableau afin de diversifier la recherche pour que l'algorithme ne reste pas calé dans un maximum local. Le palier dépend de la tâche et est sélectionné au hasard entre 0 et paliermaxi. paliermaxi est la valeur maximale que peut atteindre le palier de Ti. Le palier est sélectionné entre ces deux bornes de manière à ce que le palier ne soit pas contraint à être uniquement diminué. Nous initialisons paliermaxi à min(oi, Pi - mi), c.-à-d. le temps maximum restant pour la partie optionnelle de Ti. Nous avons donc décidé d'après nos tests, de diminuer paliermaxi V Ti de manière géométrique avec un facteur diminpalier = 0.97 (paliermaxi ? paliermaxi. diminpalier) à chaque fois que trois simulations consécutives renvoient que le système n'est pas ordonnançable. Pour déterminer ce facteur, nous avons fixé 3 comme le nombre de fois qu'une tentative de solution obtenue peut ne pas être ordonnançable avant de diminuer le palier. Ensuite, à partir de cette constante fixée, nous avons effectué des tests avec différents facteurs et comparé la récompense obtenue par rapport à l'algorithme optimal (voir figure 5.2).
FIG. 5.2 - Ajustement du facteur de diminution du palier maximum 5.9 Expérimentation Nous avons effectué des tests afin de comparer la récompense obtenue par les deux méthodes heuristiques. Pour cela, nous avons d'abord généré différents fichiers contenant chacun les spécifications de 1000 systèmes tous composés de n tâches. Les résultats produits par nos tests sur de petits ensembles de 100 systèmes divergeaient d'une simulation à l'autre mais restaient identiques entre eux avec un ensemble de 1000 systèmes et similaires aux résultats produits par un ensemble de 10000 systèmes, nous avons donc estimé qu'il s'agissait d'un bon compromis entre le temps de calcul et la qualité du résultat. Pour chaque tâche, nous enregistrons la période, le temps d'exécution obligatoire, le temps optionnel maximum et le coefficient utilisé dans la fonction de récompense. Les tests ont été faits en donnant le même temps processeur aux deux algorithmes1, le temps processeur dépendant essentiellement du nombre de simulations effectuées avec les différentes solutions. Nous nous limiterons à 1000 simulations par algorithme, soit à 900 itérations de la boucle principale pour le recuit simulé car 100 itérations sont utilisées pour déterminer la température initiale et à1000 L pour la recherche tabou étant donné qu'il faut comparer et donc simuler L (la taille du sous-voisinage V*) systèmes à chaque tour de boucle. 5.9.1 Limites des algorithmes Nous remarquons que l'efficacité de l'algorithme dépend principalement du nombre de travaux à simuler jusqu'à l'hyperpériode et ce pour deux raisons, la présence d'un nombre important de travaux:
1implémentationsdu recuitsimulé : recuit() etdelarecherchetabou : tabousearch() dans l'annexe B, section B. 1. Problème de lenteur d'exécution Nous avons fortement été ralenti par l'optimisation de la simulation et le choix de structures de données adéquates: - utilisation d'une file à priorité pour gérer les évènements; - stockage des évènements et travaux statiquement pour éviter les allocations et désallocations continuelles de la mémoire; - enregistrement des modifications effectuées sur le tableau des temps optionnels afin de ne pas devoir recopier entièrement le tableau à chaque fois que l'on revient à une solution précédente,... A chaque travail correspond un évènement « Arrivée » et « FinJob ». S'il y a 100 travaux à simuler jusqu'à l'hyperpériode, il y aura donc pour chaque simulation avec une solution xn, 200 évènements à gérer. Comme nous autorisons l'algorithme à faire 1000 simulations, qu'il y a 1000 systèmes différents par fichier et que nous testons nos 2 méthodes sur 12 fichiers différents, chaque fichier se distinguant par le nombre de tâches des systèmes qui composent celui-ci. Un rapide calcul permet de conclure qu'une instruction de 1us dans la gestion des évènements équivaut à 10-6s x 200 x 1000 x 1000x2 x 12 = 4800s = 80 minutes supplémentaires sur la simulation totale. Problème du choix des temps optionnels à modifier Il est bien entendu évident que si le nombre de travaux optionnels est important, le choix de la partie optionnelle dont on va augmenter le temps d'exécution est primordial et cela reste le cas malgré le fait qu'on joue sur la granularité en augmentant fortement les temps optionnels au début de l'exécution de l'algorithme et en diminuant cette augmentation par le système de palier. Or, le recuit simulé choisi au hasard tij qu'il va modifier. Si le choix se porte sur un travail ôij qui n'augmente que de très peu la récompense, à l'étape suivante nous risquons de continuer à travailler sur une solution qui n'est pas très intéressante. Dans la recherche tabou, c'est la solution de V* qui rapporte le plus au système qui sera sélectionnée avant de passer à l'étape suivante. C'est pourquoi la recherche tabou fournit un bien meilleur résultat lorsque le nombre de tâches est important. En effet, si le nombre de tâches est important, la probabilité d'avoir plus de travaux est beaucoup plus importante également et l'algorithme aura plus de chance de choisir un travail dont la tâche possède un coefficient plus élevé dans la fonction de récompense. Voilà pourquoi nous avons essayé de réduire le nombre de travaux par la méthode donnée à la section 5.2 en choisissant la période de manière plus sélective que totalement aléatoirement entre deux bornes. 5.9.2 Analyse avec des fonctions linéaires de récompense La comparaison est faite par rapport à l'écart de récompense entre le recuit simulé, la recherche tabou et la méthode optimale (présentée au chapitre 4) selon le nombre de tâches. Pour rappel, la méthode optimale n'est effectivement optimale que lorsque les fonctions de récompense sont linéaires. Dans ce cas, les méthodes heuristiques n'ont donc aucun intérêt, mais c'est notre seul moyen de comparaison étant donné que la méthode optimale dans le cas linéaire ne l'est plus avec des fonctions de récompense convexes. Nous avons donc premièrement effectué un test où chaque tâche possédait une fonction linéaire de récompense de la forme: f (tij) = ki . tij (5.6) Les résultats de nos simulations sont représentés sur la figure 5.3, l'abscisse représente le nombre de tâches dont sont composés les 1000 systèmes et l'ordonnée représente le rapport moyen de la récompense sur ces 1000 systèmes par rapport à l'algorithme optimal (algorithme étalon). Nous remarquons que le rapport diminue en fonction du nombre de tâches comme nous l'avons expliqué dans la section précédente et que la recherche tabou fourni effectivement de meilleurs résultats que le recuit simulé, malgré que la récompense moyenne totale vaille 80% de celle obtenue avec l'algorithme optimal sur des systèmes de 12 tâches générés comme présenté à la section 5.2.2. Ce rapport est néanmoins une bonne performance pour une méthode heuristique. 5.9.3 Simulation avec des fonctions convexes de récompense Ensuite, nous avons trouvé intéressant de comparer l'efficacité des algorithmes lorsque les fonctions de récompense sont de type convexe étant donné que le niveau de la sécurité d'un système et donc la récompense augmente de manière convexe en fonction du temps utilisé pour appliquer celle-ci. Ce serait donc selon nous le type de fonction qui pourrait caractériser au mieux l'augmentation de la valeur en sécurité en fonction du temps. Nous avons choisi pour cela
FIG. 5.3 - Cas linéaire -- Comparaison entre le recuit simulé, la recherche tabou et l'algorithme optimal une fonction de la forme: f (tij) = ki . t2 ij , (5.7) Nous avons réutilisé les mêmes ensembles de systèmes pour effectuer cette simulation, le coefficient ki reste donc également identique (sélectionné pour rappel entre 1 et 100). Nous nous rendons compte que nos méthodes heuristiques ne fournissent un meilleur rapport de récompense par rapport à l'algorithme étalon (l'algorithme optimal avec des fonctions linéaires) que lorsque le nombre de tâches est très faible (2 ou 3 tâches). Ce rapport décroît très vite lorsque le nombre de taches augmente étant donné que lorsque le nombre de tâches augmente, le nombre de travaux jusqu'à l'hyperpériode deviendra plus important. Une erreur dans le choix des parties optionnelles à modifier est alors beaucoup plus pénalisante que dans le cas des fonctions linéaires de récompense. Nous avons également comparé nos deux méthodes par rapport à l'algorithme de la descente en cascade2. Cet algorithme ressemble à l'algorithme du recuit simulé, excepté qu'on ne tient pas compte de l'évolution de la température. Lorsqu'une solution n'est pas meilleure que la précédente on ne la reprend pas à l'étape suivante, autrement dit la probabilité p (utilisée dans le recuit simulé) de continuer avec une solution fournissant une moindre récompense est nulle. 2voir fonction desc_cascade() dans l'annexe B, section B.1. Nous constatons que l'algorithme de la descente en cascade offre pour ce problème une meilleure récompense moyenne que le recuit simulé. Ceci est dû au fait qu'en acceptant dans le recuit simulé de repartir à l'itération suivante sur une solution fournissant une moins bonne récompense, nous risquons aussi de partir sur une mauvaise voie. Nous remarquons qu'il est donc préférable de n'accepter la solution obtenue que si celle-ci est meilleure que la solution précédente, ce qui nous amène à la conclusion que le recuit simulé n'est pas adapté à notre problème. Cela dit, il est évident que la récompense moyenne fournie par les méthodes heuristiques est supérieure en comparaison à celle fournie par un algorithme qui choisirait au hasard les valeurs tij sans aucune forme d'intelligence et qu'on laisserait s'exécuter sur le même temps processeur que les méthodes heuristiques citées plus haut. En effet, le système ne serait pas ordonnançable la plupart du temps et la récompense serait alors nulle. Les résultats de cette simulation sont représentés sur la figure 5.4. La recherche tabou surpasse à nouveau largement le recuit simulé pour la même raison que dans le cas linéaire, mais nous ne sommes pas parvenus à dépasser la récompense moyenne obtenue avec l'algorithme étalon.
FIG. 5.4 - Cas convexe -- Comparaison entre le recuit simulé, la recherche tabou, l'algorithme de la descente en cascade et l'algorithme étalon en fonction du nombre de tâches Comparaison par rapport à l'utilisation Nous avons ensuite généré 10 fichiers contenant chacun les spécifications de 1000 systèmes. Les systèmes enregistrés dans un fichier possèdent tous le même facteur d'utilisation Um (par les parties obligatoires), ces systèmes sont générés grâce à l'algorithme 6 présenté à la section 5.2. Um varie d'un fichier à l'autre entre 0, 1 et 1 par pas de 0, 1, le nombre de tâches pouvant ici être différent d'un système à l'autre pour un même fichier. Si l'utilisation augmente, cela signifie que le rapport entre la durée des parties obligatoires et de la période s'intensifie, il y aura donc moins de temps disponible pour l'exécution des parties optionnelles. Cela implique que la récompense attribuée à l'ordonnancement s'en verra diminuée étant donné que celle-ci n'est attribuée qu'à la partie optionnelle. Pour montrer cela, nous avons effectué une simulation sur laquelle les tâches possèdent toutes la même fonction de récompense : f(tij) = 2tij/300. Nous avons choisi une fonction exponentielle de manière à nous rapprocher le plus possible de l'évolution de la valeur en sécurité du système en fonction du temps. Remarque: L'exposant tij est divisé par 300 de manière à réduire considérablement la récompense, étant donné que les parties optionnelles peuvent être relativement importantes lorsque l'utilisation par les parties obligatoires est faible. Si cette division n'était pas effectuée, le résultat du calcul de la récompense serait trop important. Nous présentons les résultats de cette simulation sur la figure 5.5. Sur ce graphe dont l'abscisse est graduée à l'échelle logarithmique, nous constatons que la récompense moyenne régresse effectivement de manière exponentielle en augmentant le facteur d'utilisation Um. Lorsque Um = 1, la partie optionnelle est nulle et il en découle donc également une récompense nulle, quelque soit l'algorithme utilisé. Dans ce cas, le rapport est de 100% par rapport à l'algorithme étalon aussi bien pour le recuit simulé que pour la recherche tabou. Cependant, lorsqu'il y a des parties optionnelles à ordonnancer, les performances des méthodes heuristiques dépendent encore du nombre de tâches comme nous l'avons vu plus haut. Ceci explique l'irrégularité des résultats obtenus sur la figure 5.6 étant donné que pour réussir à obtenir l'utilisation désirée, le nombre de tâches n'est pas fixé et varie d'un système à l'autre, il suffit par exemple qu'un fichier comporte beaucoup de systèmes composés de deux tâches pour que le rapport de récompense entre les heuristiques et l'algorithme
FIG. 5.5 - Récompense en fonction du facteur d'utilisation étalon soit plus élevé.
FIG. 5.6 - Cas convexe - Rapport de la récompense en fonction de l'utilisation 5.10 Conclusion Nous avons expliqué dans ce chapitre comment nous avons effectué nos simulations. Nous avons montré comment les tâches sont générées et avons présenté la méthode basée sur des évènements qui fait appel à l'ordonnan- ceur EDF. Une fois la simulation de l'ordonnancement présentée, nous avons développé deux méthodes heuristiques : le recuit simulé et la recherche tabou qui utilisent notre simulation de manière à résoudre le problème d'optimisation évoqué au chapitre 4 et décrit à nouveau dans ce chapitre en utilisant ici des fonctions de récompense convexes. D'après les résultats de ces simulations que nous avons exposés à la section 5.9, nous avons fait remarquer que le recuit simulé n'est pas adapté à ce problème. Etant donné la taille du problème, il est préférable d'effectuer à chaque étape des comparaisons entre différentes solutions possibles avant d'en choisir une pour servir de base à l'étape suivante. L'algorithme de la recherche tabou effectue ces comparaisons et offre donc de meilleurs résultats au niveau de la récompense apportée par la sécurité. Nous avons prouvé par nos résultats que la qualité de la récompense dépend du nombre de tâches présentes dans le système et que cette récompense diminue en fonction du facteur d'utilisation des parties obligatoires. |
|
