|
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 |
Bibliographie
Con ference on Availability, Reliability and Security (ARES'06) (Washington, DC, USA, 2006), IEEE Computer Society, pp. 314-320.
Complément à la démonstration de H. Aydin Nous allons présenter ici la preuve que la récompense ne décroît pas lorsqu'une fonction concave de récompense fi(t) est utilisée avec des temps optionnels de tailles identiques pour tous les travaux de la tâche Ti. Cette preuve est utilisée dans la démonstration du théorème 2 (page 55) et est extraite de l'article [3]. Il faut donc prouver que: >2bi fi(tij) = bifi(t0 i ), (A.1) j=1 où t0 i = ti1+ti2+...+tibi bi et bi est le nombre de travaux de la tâche Ti jusqu'a l'hyperpé- riode. >Ibi Démonstration: Si fi(t) est une fonction linéaire de la forme fi(t) = ki · t, alors j=1fi(tij) = ki i , ce qui vérifie l'équation A. 1. (ti1 + ti2 + ... + tibi ) = kibit0 Observons à présent le cas plus général, où fi est concave et pourrait être non-linéaire avec la définition d'une fonction concave: afi(x) + (1 - a)fi(y) = fi (ax + [1 - a] y) , ?x,y 0 = a = 1 (A.2) La preuve de la validité de A. 1 est faite par induction. Si bi = 1, l'inégalité A. 1 est trivialement vérifiée. Supposons qu'elle tienne toujours avec bi = 2,3... m - 1. Cette hypothèse implique d'après A. 1 que:
En combinant les équations A.3 et A.4, nous obtenons: 1 m Xm j=1 (ti1 + ... + ti(m) ) fi(tij) = fi ?m. (A.5) m Ce qui établit la validité de A. 1. ut Code source de la simulation Nous présentons dans cette annexe le code source C++ de notre simulation ayant servi à obtenir les résultats exposés à la fin du chapitre 5. B.1 Système La classe système est la classe principale de notre simulation. Elle contient l'ensemble des tâches stockées dans un vecteur et la file des évènements triée sur base de l'instant de déclenchement de ceux-ci. L'algorithme qui permet de simuler l'ordonnancement du système jusqu'à l'hyperpériode est défini dans cette classe (simulation(Solution* solution)) tout comme les différentes méthodes heuristiques : la descente en cascade (desc_cascade()), le recuit simulé (recuit()) et la recherche tabou (tabousearch()) qui ont été présentées au chapitre 5. Nous avons également implémenté dans cette classe la méthode optimale avec des fonctions linéaires dont nous avons détaillé l'algorithme au chapitre 4 (page 59). Le calcul de la récompense obtenue par ces différentes méthodes est effectué par la fonction calcRew(). B.1.1 Systeme.h Listing B.1 - Systeme.h 1 #ifndef SYSTEM E_H #include "Tache. h" #include "Event.h" 6 #include "Solution.h" #include<queue> #include <vector> 11 using namespace std; typedef priority_queue<Event *, deque<Event *>, EventComparison> QUEUE; class Tache; 16 class Systeme{ QUEUE eventQueue;//~le qui contient les évènements triés par rapport à l 'instant de déclenchement double temps;//temps écoulé depuis le lancement de la simulation int hyperP;//l 'hyperpériode (ppcm des périodes) 21 int nbtaches; double reward; double d;//slack (durée disponible pour les parties optionnelles) bool ordo; 26 void tri (int deb, int fin); int partition (int deb, int fin); public: vector<Tache*> task; 31 vector<Tache*> sortedTasks; Solution * sol ; // solution à simuler //constructeur/destructeur Systeme(); 36 ~Systeme(); //accesseurs inline int getHyperP(){return hyperP ;}//hyperpériode inline int getNbTaches(){return nbtaches;} inline double getRew(){return reward;} 41 // méthodes void addEvent(Event* newEvent){eventQueue.push(newEvent) ;} inline void setOrdo(bool o){ordo=o;} int calcHyperPer(); double calcRew(); 46 void calcSlack(); Tache* addTask(Tache* T); Travail * getPriorJob(); //algorithmes 51 double linOPT();//Algorithme étalon optiomal dans le cas linéaire double recuit(); //Recuit simulé double desc_cascade() ;//Descente en cascade double tabousearch() ;//Recherche Tabou 56 int simulation(Solution* solution); void clean (); void displayTasks(); //affichage B.1 .2 Systeme.cpp Listing B.2 - Systeme.cpp 1 #include "Systeme.h" #include "Solution.h" 3 #include "Tache. h" #include <stdio.h> #include <time.h> #include <math.h> 8 #include <limits> #include <algorithm> #include <vector> #include <list> 13 using namespace std; Systeme: :Systeme() { hyperP=0;nbtaches=0;temps=0.0;ordo=true;reward=0.0; 18 } Systeme: :~Systeme() { sortedTasks.clear(); 23 for(unsigned i=0; i< task.size (); i++) { deletetask[i]; } task. clear (); 28 int taille =( int ) eventQueue.size(); for(int i=0; i < taille ; i++) eventQueue.pop(); } Tache* Systeme::addTask(Tache* T) 33 { task. push_back(T); T-->sys=this; nbtaches++; return T; 38 } int Systeme::calcHyperPer() { int d=0,i=0,ppcm,max; 43 max=task[0]-->getP(); for(i=0;i<nbtaches;i++) { if (task[ i ]-->getP() > max) max=task[i]-->getP(); } // max des période est la tâche i 48 for(ppcm=0;d!=nbtaches;) { ppcm+=max; d=0; for( i =0;i<nbtaches;i++) 53 { mf (ppcm%task[i]-->getP()==0) d++; } } 58 mf (d==nbtaches) { hyperP=ppcm; return ppcm; } 63 else return --1; } vomd Systeme : :calcSlack() { 68 mnt sum=0; for(mnt i=0; i<nbtaches;i++) { task[ i ]-->setb(getHyperP()/task[i]-->getP()); task[ i ]-->setw(task[i]-->getk()/(double)(task[i]-->getb())) ; // retour marginal de la fonction 73 sum+=task[i]-->getb()*task[i]-->getM(); } sortedTasks=task; tri (0, nbtaches--1); /* for(int i=0;i<nbtaches;i++) 78 { sortedTasks[i]-->Affiche(); }*/ // printf (" \n"); d=getHyperP() --sum; 83 } vomd Systeme::tri(mnt deb, mnt fin) { // Fonction QuickSort utilisée pour trier les tâches par rapport à leurs poids mnt middle; 88 mf (deb<fin) { middle = partition (deb, fin); tri (deb, middle); tri (middle+1, fin); 93 } } mnt Systeme::partition(mnt deb, mnt fin) { 98 double x = sortedTasks[deb]-->getw(); mnt i = deb--1; mnt j =fin+1; Tache* temp; do 103 { j----; }while (x >sortedTasks[j]-->getw()); 108 do { i++; }while (x<sortedTasks[i]-->getw()); if (i<j) 113 { temp=sortedTasks[i]; // swap des éléments aux positions i et j sortedTasks[i]=sortedTasks[j ]; sortedTasks[j]=temp; } 118 }while(i<j); return j ; // retourne l 'index du milieu } double Systeme::linOPT() 123 { int i,bi , oi ,bo; double div,slack = d; sol = new Solution(this,false); for ( i =0; i<nbtaches;++i) 128 { bi =sortedTasks[i]-->getb(); oi =sortedTasks[i]-->getO(); bo=bi*oi; if (bo<slack)//b_i*o_i<slack 133 { for(int j=0; j<bi;j++) { sol -->otime[sortedTasks[i]-->getid()--1][j]=(double)oi; // printf ("Temps optionnel[Tache no %d,Job no %d]: %lfln",sortedTasks[i]-->getid(),j+1,otime[sortedTasks[i]-->getid()--1][j]); 138 } slack--=bo; } else { for(int j=0; j<bi;j++) { sol -->otime[sortedTasks[i]-->getid()--1][j]=div; // printf ("Temps optionnel[Tache no %d,Job no %d]: %f\n",sortedTasks[i]-->getid(),j+1,otime[sortedTasks[i]-->getid()--1][j]); 148 } break; } } i++; 153 while(i<nbtaches) { bi =sortedTasks[i]-->getb(); for(int j=0; j<bi;j++) { 158 sol -->otime[sortedTasks[i]-->getid()-- 1 ][j]=0; // printf ("Temps optionnel[Tache no %d,Job no %d]: %f\n ",sortedTasks[i]-- >getid(),j+ 1, otime[sortedTasks[i]-->getid()-- 1][j]); } ++i; } 163 simulation(sol); sol-->printSol(); reward=sol-->rew; delete sol; return reward; 168 } double Systeme::recuit() { int sim=1, L=nbtaches, cou nter=0; 173 double diminPalier=0.97, moydeltaF=0; double* paliermax = new double[nbtaches]; for(int i=0;i<nbtaches;i++) paliermax[i]=min(task[ i ]-->getO(),task[i ]-->getP()--task[i]-->getM()); int cptnonordo=0; 178 double q,p,temper=nbtaches,alpha=0.95,deltaF=0,savrew; list <Modif*> modiflist; // solution initiale tous les travaux recoivent 0 comme temps optionnels Solution tempsol(this,true); 183 Solution bestsol(this, true); int cpt=0; while(cpt<1 00)//test pour trouver la moyenne deltaF { savrew = tempsol.rew; 188 tempsol .getSol Vois(sim,&modiflist, pal iermax); //mets la solution voisine dans tempsol si m=si mu lation(&tempsol) ;//simulation avec la solution temporaire if(sim<1) { //si ce n'est pas ordonnancable pendant 3 tours if (cptnonordo%3==0)for(int i=0;i<nbtaches;i++) paliermax[i]*=diminPalier; } else cptnonordo=0; 198 // printf ("paliermax = %f\n",paliermax); // printf ("Recompense: %f\n",reward); if (tempsol.rew > savrew) { //on continue à utiliser la nouvelle solution 203 if (tempsol > bestsol) bestsol = tempsol; else { q=hasard(0.0,1 .0); 208 deltaF=savrew -- tempsol.rew; moydeltaF+=deltaF; counter++; p=exp(--deltaF/temper); if (q>p)tempsol .back(&modjfl jst) ; //on revient 213 //sinon on continue à utiliser la solution (tempsol) } cpt++; if (cpt%L==0)temper*=alpha; clean (); 218 } cpt=0; moydeltaF/=cou nter; temper=moydeltaF/log(2.0); for ( int j =0; j <nbtaches ;j++)paljermax[j]=task[ j ]-->getP()--task[j]-->getM(); 223 tempsol.jnjt(); wh i le(cpt<900) { savrew = tempsol.rew; tempsol .getSol Vojs(sjm,&modjfljst, pal jermax); //mets la solution voisine dans tempsol 228 sjm=sjmulatjon(&tempsol) ;//simulation avec la solution temporaire if(sjm<1) { cptnonordo++; //si ce n'est pas ordonnancable pdt 3 tours 233 if (cptnonordo%3==0)for(int j=0;j<nbtaches;j++)paljermax[j]*=djmjnPaljer; } else cptnonordo=0; // printf ("paliermax = %f\n",paliermax); // printf ("Recompense: %f\n",reward); 238 if (tempsol.rew > savrew) { //on continue à utiliser la nouvelle solution if (tempsol > bestsol) bestsol = tempsol; 243 } else { q=hasard(0.0,1 .0); deltaF=savrew -- tempsol.rew; 248 p=exp(--deltaF/temper); if (q>p)//on revient à la solution précédente tempsol.back(&modjfljst); //sinon on continue à utiliser la solution (tempsol) } 253 cpt++; if (cpt%L==0)temper*=alpha; clean (); reward = bestsol.rew; 258 delete[] paliermax; bestsol. printSol (); return reward; } 263 double Systeme::desc_cascade() { mnt sim=1; double diminPalier=0.97, savrew; double* paliermax = new double[nbtaches]; 268 for ( mnt i =0; i <nbtaches ;i++) paliermax[i]=min(task[ i ]-->getO(),task[i ]-->getP()--task[i]-->getM()); mnt cptnonordo=0; list <Modif*> modiflist; // solution initiale tous les travaux recoivent 0 comme temps optionnels 273 Solution tempsol(thms,true); Solution bestsol(thms, true); mnt cpt=0; for ( mnt i =0; i <nbtaches ;i++)paliermax[i]=task[ i ]-->getP()--task[i]-->getM(); tempsol. init (); 278 whmle(cpt<1 000) { savrew=tempsol. rew; tempsol .getSol Vois(sim,&modiflist, pal iermax); Ilmets la solution voisine dans tempsol si m=si mu lation(&tempsol) ;//simulation avec la solution temporaire 283 mf(sim<1) { cptnonordo++; Ilsi c'est pas ordonnancable pdt 3 tours mf (cptnonordo%3==0) for(mnt i=0;i<nbtaches;i++)paliermax[i]*=diminPalier; 288 } else cptnonordo=0; II printf ("paliermax = %f\n",paliermax); II printf ("Recompense: %f\n",reward); mf (tempsol.rew > savrew) 293 { lion continue à utiliser la nouvelle solution mf (tempsol > bestsol) bestsol = tempsol; } else 298 { tempsol .back(&modiflist); lion revient ilsinon on continue à utiliser la solution (tempsol) } cpt++; 303 clean (); } reward = bestsol.rew; delete[] paliermax; bestsol. printSol (); 308 return reward; } double Systeme: :tabousearch() { 313 mnt sim,cpt=0,cptnonordo=0; vector<Solution*> V; mnt tailleV =41 *nbtaches;//sous voisinage list <Tabou> taboulist; mnt tabousize=1 0; const mnt cptmax=1 000/tailleV; 318 double diminPalier=0.97; double* paliermax=new double[nbtaches]; for(mnt i=0; i<nbtaches; i++) paliermax[i] = min(task[ i ]-->getO(),task[i ]-->getP()--task[i]-->getM()); vector<Solution*>:: iterator it; 323 Solution x(thms,true); // solution initiale tous les travaux recoivent 0 comme temps optionnels Solution bestsol(thms,true); Solution* voisine, *tmpbestsol; 328 sim = simulation(&x); clean () ; II on nettoie la simulation: remise du temps à 0, récompense,... wh m le(cpt<cptmax) { for ( mnt i =0; i < tai lleV ; i ++)// V=sous-- voisinage de x 333 { voisine = x. getSolVoisine(sim,paliermax); sim=simulation(voisine); mf (sim<1) { 338 cptnonordo++; // si c'est pas ordonnancable pdt 3 tours mf (cptnonordo%3==0) for(mnt i=0;i<nbtaches;i++) paliermax[i]*=diminPalier; // printf ("paliermax: %f\n ",paliermax); 343 } else cptnonordo=0; V. push_back(voisine); clean (); } 348 sort(V.begin(), V.end(), trisolutions ()); II tri décroissant par rapport à la récompense it =V.begin(); do { it++; } whmle(tmpbestsol-->tabou .isTabou (&tabou list) && it!=V.end()); mf ( it ==V.end()) 358 x=**(V.begin()); Ilmême s'il est tabou else x = *tmpbestsol; if (x > bestsol)bestsol=x; taboulist . push_front(x.tabou); //mise à jour de la liste tabou if (( int) taboulist .size ()>tabousize)taboulist.pop_back(); 363 for( it =V.begin(); it !=V.end(); it ++) delete *it ; V.clear() ; cpt++; } 368 delete[] paliermax; taboulist . clear () ; reward=bestsol.rew; bestsol. printSol () ; return reward; 373 } void Systeme::clean() { Event* ev; 378 int siz = (int)eventQueue.size(); for(int i=0; i < siz ; i++) { ev= eventQueue.top(); eventQueue.pop(); 383 } for(int t=0;t<nbtaches;t++) { task[t]-->clean(); 388 } reward=temps=0.0; } int Systeme::simulation(Solution *solution) 393 { double sumopt=0, sumtaski=0,remTimeBeforeNextEvent; int Mi,bi ; sol = solution ; for ( int i =0; i <nbtaches;i++) 398 { //on regarde d'abord si ça vaut la peine de simuler Mi=task[i]-->getM(); bi=task[i]-->getb(); for(int j =0; j<bi ; j ++) { 403 sumopt += sol-->otime[i][j]; } sumtaski += bi*Mi + sumopt; sumopt=0; } 408 if (sumtaski > getHyperP() + 0.00001) { // printf ("In******* PAS ORDONNANCABLE **********In"); // printf (" Il y a plus d'unites (%f) que l 'hyperperiode (%d)In",sumtaski,getHyperP()); sol -->rew=0; 413 reward=0; ordo=false; return --1; } 418 Travail * priorjob ; Event* nextEvent; //displayTasks(); for( int t =0 ;t<nbtaches;t++)//au début toutes les tâches envoient un job (départ simultané) { 423 addEvent(task[t]-->arrivee); } // printf ("*** Hyper--periode= %d ***In",getHyperP()); do//on exécute la simulation sur l ' intervalle d'étude P { 428 // printf ("I nInstant %f: In",eventQueue.top()-->temps); do { nextEvent = eventQueue.top(); temps = nextEvent-->temps; 433 ordo = nextEvent-->processEvent(); eventQueue.pop(); }while(ordo && fabs(temps -- eventQueue.top()-->temps) < 0.000001);//tant que l'instant est identique if (!ordo)break; 438 priorjob = getPriorJob() ; // politique EDF if ( priorjob !=NULL)//s'il y a au moins un job en attente { remTimeBeforeNextEvent = eventQueue.top()-->temps -- temps; if (( priorjob -->getRem() < remTimeBeforeNextEvent) || fabs(priorjob-->getRem() -- remTimeBeforeNextEvent) < 0.000001) 443 { priorjob -->finJob-->temps = temps + priorjob-->getRem(); addEvent(priorjob-->finJob); } else 448 { priorjob -->setRem(priorjob-->getRem()--remTimeBeforeNextEvent); } } }while(temps<getHyperP()); 453 if (ordo) { // printf ("I n******* Systeme ordonnancable ********** In"); calcRew(); return 1; 458 } sol -->rew=0; reward=0; // printf ("I n******* PAS ORDONNANCABLE **********In"); return 0; 463 } Travail * Systeme::getPriorJob() { double resttime, min=(double)INT_MAX; 468 Travail *job, *priorjob=NULL; for(int t=0;t<nbtaches;t++) { //EDF on compare chaque tâche et on garde le job actif dont l'échéance est la plus proche job = task[t]-->getJob(); if (job!=NULL) 473 { resttime=(double)job-->getP()--fmod(temps,(double)job-->getP());//temps restant avant la prochaine échéance if (resttime<min) { min=resttime; 478 priorjob =job; } } } return priorjob ; //retourne celui qui a le plus petit temps restant avant l 'échéance 483 } void Systeme::displayTasks() { for( int i =0; i <nbtaches;i++) 488 { task[ i]-->Affiche(); } } 493 double Systeme::calcRew() { double sum1 =0, sum2=0; int bi ; for( int i =0; i <nbtaches;i++) 498 { bi =task[ i ]-->getb(); sum1=0; for(int j =0; j<bi ; j ++) { 503 sum1+=task[i]-->fonction(sol-->otime[i][j]) ; } sum2+=sum1/(double)bi; } sol -->rew=reward=sum2; 508 return reward; B.2 Tâche Le système comporte un ensemble de tâches et chaque tâche est définie par certaines caractéristiques : sa période (P), la longueur de la partie obligatoire (M) et la longueur maximum de la partie optionnelle (O). Une instance de la tâche est séparée en deux parties : obligatoire (jobOblig) et optionnelle (jobOpt), nous enregistrons dans chaque tâche un pointeur vers ces deux parties. Chaque tâche possède une fonction de récompense, les fonctions des différentes tâches se différencient par un certain coefficient k. Un pointeur vers l'évènement Arrivée (d'un nouveau travail) est stocké et l'instant de déclenchement de l'arrivée est augmenté de P à chaque instance de manière à gérer l'arrivée suivante. B.2.1 Tache.h Listing B.3 - Tache.h 1 #ifndef TACHE_H #define TACHE_H #include "Travail .h" #include <math.h> 6 #include <list> using namespace std; class Travail; class Systeme; 11 classEvent; class Tache{ int id; int P;//période 16 int M;//longueur de la partie obligatoire int O;//longueur maximum de la partie facultative int b; // nb de fois que l'on peut placer la tâche dans l' intervalle d'étude (hyperpériode) Travail * jobOblig; Travail* jobOpt; 21 int numopt;//numéro du job actuel double k;//coeff de la fonction de récompense double w;//k/b: importance de la tâche (proportionnel au coef~cient) public: Tache(int ident, int per, int man, int opt, double coeff); 26 -'Tache(); Systeme* sys; Event* arrivee; //accesseurs inline int getid(){return id ;}; 31 inline int getP(){return P;}; inline int getM(){return M;}; inline int getO(){return O;}; mnlmne mnt getnumopt(){return numopt;} mnlmne mnt getb(){returnb;}; 36 mnlmne double getk(){return k;} mnlmne double getw(){return w;} mnlmne bool isJobRunning(){return jobOblig-->isRunning() || jobOpt-->isRunning() ;} // méthodes vomd sendJob(); 41 Travail* getJob(); vomd clean (); mnlmne vomd setb(mnt x){b=x;}; mnlmne vomd setw(double x){w=x;}; vomd setArriveeSuivante(); 46 vomd Affiche (); mnlmne double fonction(double t){return k* pow((double)2,(double)t/300);} vomd efface( Travail * job); }; #end mf B.2.2 Tache.cpp Listing B.4 - Tache.cpp 1 #mnclude "Tache. h" #mnclude "Travail .h" #mnclude "Systeme.h" 5 Tache::Tache(mnt ident, mnt per, mnt man, mnt opt, double coeff) { id=ident; P=per;M=man;O=opt;k=coeff; jobOblig = newTravail(thms,true); jobOpt = new Travail(thms,false); 10 arrivee = new Arrivee(thms,0); numopt=0; } Tache: :~Tache() { 15 delete jobOblig; delete jobOpt; delete arrivee; } vomd Tache::Affiche() 20 {
printf ("\nTache %d:\n\nPeriode: %d\nPartie obligatoire: %d\nPartie facultative: %d\nCoeff de recompense: %.2f\nRetour marginal:
%f\n",id, P,M,O,k,w); } Travail * Tache::getJob() 25 { mf (jobOblig-->isRunning()) return jobOblig; mf (jobOpt-->isRunni ng())return jobOpt; return NULL; void Tache::sendJob() { if (M>0.0) { 35 jobOblig-->setJob(); } if (sys-->sol-->otime[this-->getid()--1 ][numopt] > 0.000001) { //s' il y a un temps optionnel> 0 jobOpt-->setJob(); 40 } numopt++; } void Tache::clean() 45 { jobOblig-->stop(); jobOpt-->stop(); arrivee -->temps=0; numopt=0; 50 } void Tache: :setArriveeSu ivante() { sys-->addEvent(this-->arrivee); } B.3 Travail Dans notre simulation, une tâche lance à chaque période deux travaux, nous identifions par oblig le fait que le travail correspond à la partie obligatoire ou optionnelle de la tâche. Ce qui permet de choisir M comme temps d'exécution si la partie est obligatoire ou le temps optionnel (otime) déterminé par les méthodes heuristiques si la partie est optionnelle. B.3.1 Travail.h Listing B.5 - Travail.h 1 #ifndef TRAVAIL_H #define TRAVAIL_H class Tache; 6 #include<list> using namespace std; class Travail 11 { private: Tache* tache;//tâche à laquelle il appartient int P; 16 bool oblig; // partie obligatoire ou optionnelle bool running; public: Event* finJob; 21 //contructeur, destructeur Travail (Tache* tache, bool mandatory=true); ~Travail (); //accesseurs inline double getRem(){return
remtime;} inline bool isMand(){return oblig ;}; inline bool isRunning(){return running;}; //méthodes inline void stop(){running=false;} 31 inline void run(){running=true;} void setJob(); inline void setRem(double rem){remtime=rem ;}; }; 36 #endif B.3.2 Travail.cpp Listing B.6 - Travail.cpp 1 #include "Travail .h" #include "Tache. h" #include "Systeme.h" 4 Travail :: Travail (Tache* task, bool mandatory) { 9 this-->tache=task; running=false; P=task-->getP(); oblig =mandatory; finJob = new FinJob(this,0); 14 } void Travail ::setJob() { if(oblig) 19 { remtime=(double)tache-->getM(); // printf ('+ La tache %d envoie un travail obligatoire de %f unites\n ', tache-->getid(),remtime); } else 24 { // printf ("+ La tache %d envoie un travail optionnel avec t=%f\n", tache-->getid(),remtime); } running=true; 29 } Travail::-' Travail () { delete finJob; } B.4 Générateur La classe « Generateur » est utilisée pour créer un ensemble de systèmes. Les systèmes seront encodés dans un fichier de manière à récupérer aisément ceux-ci lors de l'exécution de la simulation. B.4.1 Generateur.h Listing B.7 - Generateur.h 1 #mfndef GENERATEUR_H 2 #define GENERATEUR_H #mnclude "Systeme.h" class Generateur 7{ publmc: vomd genStaticT(mnt nbsys, mnt n, char fichier []) ; // génère nbsys systèmes de n tâches dans fichier vomd genStaticU(mnt nbsys, double U, char fichier []) ; 12 // génère nbsys systèmes avec une
utilisation U dans fichier // retourne le système à la position pos dans le fichier }; #end mf B.4.2 Generateur.cpp Listing B.8 - Generateur.cpp 1 #mnclude "Generateu r. h" #mnclude "Divers.h" #mnclude "Tache. h" 4 vomd Generateur::genStaticT(mnt nbsys, mnt n, char fichier []) { //génère nbsys systèmes de n tâches indépendamment de l'utilisation FILE * simul; mnt i=O, P, M, O; 9 double currentload = O,coeff; simul = fopen (fichier , "w"); for( int k=0;k<nbsys;k++) { i =0; currentload=0; 14 while(i!=n) { P = genPeriode();//Période M = hasardint(0,P); O = P--M;//partie facultative max 19 coeff = hasard(1 , 100);// coefficient de la fonction if (currentload + (double)M/P <= 1) { currentload += (double)M/P; 24 fprintf (simul,"%d %d %d %lf\n",P,M,O,coeff);
i++; } } printf ("U=%lf\n",currentload); 29 fprintf (simul,"*\n") ; fclose(simul); } void Generateur::genStaticU(int nbsys, double U, char fichier[]) 34 { //génère nbsys systèmes dans le fichier avec une utilisation proche de U indépendamment du nombre de tâches FILE * simul; int i=0, P, M, O; double currentload = 0,coeff; simul = fopen (fichier , "w"); 39 for(int k=0;k<nbsys;k++) { i =0; currentload=0; while(currentload<=U--0.0005) { 44 P = genPeriode();//Période M = hasardint(0,P); O = P--M;//partie facultative max coeff = hasard(1 , 100) ;// coefficient de la fonction 49 if (currentload + (double)M/P <= U) { currentload += (double)M/P; fprintf (simul,"%d %d %d %lf\n",P,M,O,coeff); } 54 } printf ("U=%lf\n",currentload); fprintf (simul,"*\n") ; } fclose(simul); 59 } Systeme* Generateur::getNextSystem(long &pos,char fichier[]) { FILE* simul=fopen(fichier, "r"); 64 fseek(simul,pos,SEEK_SET); mnt P,M,O,cpt=0; Systeme *S = new Systeme(); double coeff; wh m le(true) 69 { //on crée le système suivant du fichier. cpt++; fscanf (simul, "%d %d %d %lf\n", &P, &M, &O, &coeff); S-->addTask(new Tache(cpt,P,M,O,1)); // printf ("%d %d %d %lf\n", P, M, O, coeff); 74 mf ((char)fgetc(simu l)=='*') break; fseek(simul, --1, SEEK_CUR); } S-->calcHyperPer(); S-->calcSlack(); 79 pos=ftell (simul); fclose(simul); return S; } B.5 Dmvers B.5.1 Dmvers.h Cette classe contient différentes fonctions de base utilisées par les autres classes, permettant de générer un nombre aléatoire entre deux bornes, de générer une période pour une tâche,... Listing B.9 - Divers.h 1 #mfndef DIVERS_H #define DIVERS_H 3 const mnt Matrix [5][3]={{2,2,4},{3,3,9},{5,5,25},{7,7,7},{1 1,1 1 ,1 1 }}; double hasard(double a, double b); mnt hasardint(mnt min, mnt max); double min(double x,double y); 8 // inline int round(double x){return(x)>=0?(int) ((x)+0.5) :( int) ((x)-- 0.5);} mnt genPeriode(); #end mf B.5.2 Dmvers.cpp Listing B.10- Divers.cpp 1 #mnclude "Divers.h" #mnclude<stdlib. h> 4 double hasard(double a, double b) return (a + (b--a)*((double) rand() / (RAND_MAX))); } 9 mnt hasardint(mnt min, mnt max) { return rand() % (max--min+1) + min; } double min(double x,double y) 14 { return x<y?x:y; } mnt genPeriode() { 19 mnt period = 1,p; for(mnt i=1;i<5;i++) { p = hasardint(0,2); period*=Matrix[i ][ p]; 24 } return period; } B.6 Event La classe Event permet de gérer les évènements lorsque ceux-ci se déclenchent. (voir description section 5.3, page 68) B.6.1 Event.h Listing B.1 1 - Event.h 1 #mfndef EVE NT_H #define EVENT_H 4 #mnclude<math.h> #mnclude<stdio. h> class Tache; class Travail; 9 class Event { publmc: Event(double t, mnt typ) : temps(t),type(typ){ } double temps; 14 mnt type; vmrtual bool processEvent() = 0; }; struct EventComparison {//comparateur utilisé pour l'insertion triée 19 bool operator () (Event* left, Event* right) const { if (fabs( left -->temps -- right-->temps)<0.000001) return left-->type > right-->type; return left -->temps > right-->temps; } 24 }; class FinJob:public Event{ public: FinJob(Travail* trav, double temps) : Event(temps,1), job(trav){} 29 Travail* job; virtual bool processEvent(); }; class Arrivee:public Event{ 34 public: Arrivee (Tache* tache, double temps): Event(temps,3), task(tache){} Tache* task; virtual bool processEvent(); }; 39 #endif B.6.2 Event.cpp Listing B.12 - Event.cpp 1 #include "Event.h" #include "Tache. h" #include "Travail .h" bool Arrivee :: processEvent() 6{ if (task-->isJobRunning()) return false;//test du respect de l 'échéance task-->sendJob();//on lance un nouveau travail temps+=task-->getP();//prochaine arrivee fixée à l'instant courant + période 11 task-->setArriveeSuivante();//repositionnement dans la
queue d'évènements } bool FinJob::processEvent() 16 { job-- >stop() ; //le travail se termine return true; } B.7 Solution Une solution, qui est en fait une tentative de solution et non la solution définitive, comprend un tableau otime[i][j] qui contient la longueur des parties optionnelles pour tous les travauxj de la tâche i. On passe d'une solution à l'autre en choisissant une solution voisine grâce à la fonction getSolVoisine() ou getSol Vois(). La fonction getSolVoisine() se différencie par le fait qu'elle enregistre les permutations dans la liste tabou. Une description de la façon dont est sélectionnée une solution voisine est présentée à la section 5.8, page 79. D'autre part, pour l'algorithme du recuit simulé, les modifications effectuées sont enregistrées grâce à la classe Modif, de manière à revenir facilement à la solution précédente sans devoir à chaque fois recopier tout le tableau otime. Cette solution est ensuite transmise en paramètre à la fonction simulation() qui va tester si le système est ordonnançable et si tel est le cas, calculer la récompense accrue avec ces temps optionnels. Cette récompense est enregistrée dans la variable rew qui sera comparée avec la récompense des solutions suivantes. B.7.1 Solution.h Listing B.13 - Solution.h 1 #ifndef SOLUTION_H #define SOLUTION_H #include<list> #include<vector> using namespace std; 6 class Systeme; class Modif { public: 11 int i; int j; double val; Modif(int k, int l, double value):i(k), j(l) ,val (value){} }; 16 21 class Tabou { int a; int c; int d; public: Tabou():a(--1 ),b(--1 ),c(--1 ),d(--1 ){} 26 Tabou(int a1,int b1,int a2,int b2):a(a1),b(b1),c(a2),d(b2){} Tabou (const Tabou & tab) :a(tab.a) , b(tab. b),c(tab.c) , d(tab. d) {} Tabou& operator=(const Tabou& tab); inline bool operator==(Tabou& x){return (x.a==this-->a && x.b==this-->b && x.c==this-->c && x.d==this-->d)II(x.a==this-->c && x.b==this-->d &&
x.c==this-->a &&
x.d==this-->b);} 31 bool isTabou ( list <Tabou>* taboulist); }; class Solution { 36 int nbtaches; int* b; Systeme* sys; public: Solution(Systeme* sys, bool init) ; 41
Solution(const Solution& s); Solution* getSolVoisine(int sim, double* paliermax); void getSolVois(int sim, list <Modif*>* backup,double* paliermax); 46 void back( list <Modif*>* modiflist) ; bool addModif(int i, int j , double val, list <Modif*>* modiflist) ; bool cherchejobO(int &i, int &j, double palier); void printSol () ; void init () ; 51 double ** otime; // Tableau des temps optionnels double rew;//récompense obtenue (calculée après la simulation) Tabou tabou; //Swap effectué sur la solution bool operator>(const Solution& s);//comparaison de la récompense 56 bool operator<(const Solution& s);//idem Solution& operator=(const Solution& s);//opérateur d'assignation }; struct trisolutions { 61 bool operator()(Solution const* s1, Solution const* s2) { if (!s1) return false; if (!s2) 66 return true; return s1-->rew > s2-->rew; } }; #endif B.7.2 Solution.cpp Listing B.14 - Solution.cpp 1 #include "Solution.h" #include "Systeme.h" #include "Tache. h" 5 Solution :: Solution(Systeme* systeme, bool init) { rew = 0; sys = systeme; 10 nbtaches = sys-->getNbTaches(); b = new int[nbtaches]; otime = new double*[nbtaches]; for ( int i =0; i<nbtaches;i++) { 15 b[ i ] = sys-->task[i]-->getb(); otime[i] = new double[b[i]]; if( init )for(int j=0;j < b[i ]; j++) otime[i ][j] = 0; } } 20 Solution : :~ Solution () { for(int i=0;i<nbtaches;i++) { delete[] otime[i]; 25 } delete[] b; delete[] otime; } 30 Solution :: Solution(const Solution& s) { rew = s.rew; sys = s.sys; tabou = s.tabou; 35 nbtaches = s.nbtaches; b = new int[nbtaches]; otime = new double*[nbtaches]; for(int i=0;i<nbtaches;i++) { 40 b[i] =s.b[i]; otime[i] = new double[b[i]]; for(int j=0;j < b[i ];j++) otime[i ][j] = s.otime[i ][j ]; } } 45 void Solution:: init () { for(int i=0;i<nbtaches;i++) { for(int j=0;j < b[i ];j++) otime[i ][j] = 0; 50 } rew=0; } Solution& Solution ::operator=(const Solution& s) { 55 rew=s.rew; sys = s.sys; tabou = s.tabou; nbtaches = s.nbtaches; for(int i=0;i<nbtaches;i++) 60 { b[i] =s.b[i]; for(int j=0;j < b[i ]; j++) otime[i ][j] = s.otime[i ][j ]; } return *this; 65 } bool Solution::operator>(const Solution& s) { return (this-->rew> s.rew); 70 } bool Solution ::operator<(const Solution& s) { return (this-->rew < s.rew); 75 } Solution* Solution :: getSolVoisine(int sim, double* paliermax) { int i = hasardint(0,nbtaches--1); 80 double palier=hasard(0.0,paliermax[i]); // printf (" palier = %lf, paliermax = %lfIn", palier,paliermax[i ]) ; int j = hasardint(0,b[i]--1); Solution* x = new Solution(*this);//copie if (sim==1)//si c'est ordonnançable on augmente un tij de palier ou =maxoptional 85 { double maxOptional = x-->sys-->task[i]-->getO(); // printf ("Tache %d, OMAX= %lfln",i+1,maxOptional); if (x-->otime[i][j]+ palier <= maxOptional) { 90 x-->otime[i][j]+=palier ; // printf ("On augmente otime[%d][%d] de %f --> = %fln",i,j,palier,x-->otime[i][j]); } else { 95 x-->otime[i][j]=maxOptional; // printf ("On augmente otime[%d][%d] a %f\n",i,j,x-->otime[i][j]); } } if (hasard(0,1)<0.5) 100 { //permutation de 2 temps optionnels au hasard sans dépasser oi int k = hasardint(0,nbtaches--1); int l = hasardint(0,b[k]--1); double backup =
min(x-->otime[i][j],x-->sys-->task[k]-->getO()); 105 x-->otime[k][l] = backup; // printf ("On swap t[%d][%d] et t[%d][%d]ln",i, j ,k, l); x-->tabou.set(i, j ,k, l ) ; } if (sim==--1)//pas ordonnançable car plus d'unités que l'hyperpériode 110 { if (x-->otime[i][j ] -- palier < 0.0001) x-->cherchejobO(i,j,palier) ; //on cherche un job qui possède un temps optionnel > palier 115 if (x-->otime[i][j ]--palier > 0.0001) { x-->otime[i][j]--=palier; // printf ("On diminue otime[%d][%d] de %f --> = %f\n",i,j,palier,x-->otime[i][j]) ; 120 } else { x-->otime[i][j ]=0; // printf ("On diminue otime[%d][%d] a 0ln",i,j); 125 } } return x; } 130 void Solution :: back( list <Modif*>* modiflist) { for( list <Modif*>:: iterator it = modiflist -->begin() ; it != modiflist -->end();) { otime[(* it )-->i][(* it )-->j]=(* it )-->val; 135 delete (* it ) ; it = modiflist -->erase(it); } } bool Solution ::addModif(int i, int j, double val, list <Modif*>* modiflist) 140 { for( list <Modif*>:: iterator it = modiflist -->begin() ; it != modiflist -->end();it++) { if ((* it )-->i==i && (*it)-->j==j)return false;// il y a déjà eu une modification sur ce job } 145 modiflist -->push_back(new Modif(i,j,val)); return true; //on a rajouté une modification } void Solution ::getSolVois(int sim, list <Modif*>* backup,double* paliermax) { 150 int i = hasardint(0,nbtaches--1); double palier=hasard(0.0,paliermax[i]); int j = hasardint(0,b[ i ]--1); if (sim==1)//si c'est ordonnançable { 155 double maxOptional = sys-->task[i]-->getO(); // printf ("Tache %d, OMAX= %lfln",i,maxOptional); if (otime[i ][ j ]+ palier <= maxOptional) { addModif(i,j ,otime[i ][ j ], backup); 160 otime[i ][ j]+= palier ; // printf ("On augmente otime[%d][%d] de %f --> = %fln",i,j,palier,otime[i][j]); } else { 165 addModif(i,j ,otime[i ][ j ], backup); otime[i ][ j]=maxOptional; // printf ("On augmente otime[%d][%d] a %f\n",i,j,otime[i][j ]) ; } 170 //permutation de 2 temps optionnels au hasard sans dépasser oi if (hasard(0,1 )<0.5) { int k = hasardint (0, nbtaches-- 1); int l = hasardint(0,b[k]--1); 175 double sav = min(otime[i][j ], sys-->task[k]-->getO()); addModif(i,j ,otime[i ][j ], backup); otime[i ][ j] = min(otime[k][ l ], sys-->task[i]-->getO()); addModif(k,l,otime[k][ l ], backup); otime[k][l] =sav; 180 // printf ("On swap t[%d][%d] et t[%d][%d]\n",i,j,k, l); } if (si m==-- 1 )//pas ordonnançable car plus d'unités que l'hyperpériode { if (otime[i ][j] -- palier <0.00001) 185 cherchejobO(i,j, palier); //on cherche un job qui possède un temps optionnel> palier if (otime[i ][ j]--palier > 0.00001) { addModif(i,j ,otime[i ][j ], backup); 190 otime[i ][j]--=palier; // printf ("On diminue otime[%d][%d] de %f --> = %f\n ", i,j,palier,x-->otime[i][j ]); } else { 195 addModif(i,j ,otime[i ][j ], backup); otime[i ][j]=0; // printf ("On diminue otime[%d][%d] a 0\n",i,j); } } 200 } bool Solution ::cherchejobO(int &i, int &j, double palier) // cherche au hasard un job > palier que l 'on peut diminuer { //de manière à ne pas boucler en retombant sur des doublons 205 bool trouve=false; list <int*> combi; for( int m=0;m<nbtaches;m++) { for(int n=0;n<b[m];n++) 210 { if (otime[m][n]>=palier) { int* coord = new int[2]; coord[0]=m; 215 coord[1]=n; combi.push_back(coord); } } } 220 int size=(int)combi.size(); if (size>0)//s' il y a au moins unjob>=palier int x = hasardint(0,size-1);//entre 0 et size-1 list <int*>:: iterator it = combi.begin(); 225 for( int h=0;h<x;h++)it++;//se positionner sur le xme élément i = (* it) [0]; j = (*it)[1]; trouve=true; } 230 for( list <int*>:: iterator it =combi.begin(); it !=combi.end(); it++)delete[](* it); combi.clear(); return trouve; } 235 void Solution:: printSol () { /* printf ("\ nRecompense: %lf",rew); for (int i=0;i<nbtaches;i.i-.i-) { 240 printf ("\ n\n Tache %d: ",i.i-1); for ( int j=0;j<b[i]; j.i-.i-) printf ("% lf , ", otime[i ][j]); J printf ("\ n"); */ } 245 //** ***************************** Tabou & Tabou: :operator=(const Tabou & tab) { a = tab.a; 250 b=tab.b; c = tab.c; d = tab.d; return *this; } 255 bool Tabou: :isTabou (l ist <Tabou> *tabou l ist) { for( list <Tabou>::iterator it =taboulist->begin();it!= taboulist ->end();it++) { if ((* it )==*this) return true; 260 } return false; } B.8 Main Chaque fichier simulation_i.txt représente un ensemble de 1000 systèmes ayant soit le même nombre de tâches (comme dans cet exemple), soit le même facteur d'utilisation. Nous appliquons les algorithmes sur tous les systèmes de chaque fichier. Ensuite, pour chaque fichier on compare la récompense entre les différents algorithmes. Le résultat des simulations est enregistré dans le fichier resultat.txt. B.8.1 Main.cpp Listing B.15 - Main 1 #include "Generateur.h" #include<stdio.h> 3 #include<time.h> #include <stdl ib. h> using namespace std; 8 int main() { srand((unsigned)time(NULL)); //initialise le random Generateur G; 13 const int TAILLE=1000;//nombre de systèmes à générer par fichier clock_t time1 = clock() ; FILE* resultat = fopen(" resultat . txt " ,"w"); fprintf ( resultat , "*************************\n"); 18 fclose ( resultat ) ; for(int i=1;i<12;i++) { char buffer [20]; sprintf ( buffer , "simulation%d.txt", i ) ; 23 //G.genStaticT(TAILLE,i, buffer) ;//génère un fichier statique de 1000 systèmes de i taches long pos=0; int nbsys,cpt=0; double rewopt=0, rewrecu it=0, rewtabo u =0, rewcascad e=0, m oy recu it=0, m oytabou =0, moycascade=0; for (nbsys=1;nbsys<=TAILLE;nbsys++) 28 { printf ("*** %d me systeme ***\n",nbsys); Systeme* S = G.getNextSystem(pos,buffer); rewopt=S-->linOPT(); S-->clean(); 33 rewrecuit=S-->recuit(); S-->clean(); rewtabou=S-->tabousearch(); S-->clean(); rewcascade=S-->desc_cascade(); 38 delete S; //rapport moyen entre les différentes méthodes et l'algorithme étalon moyrecuit += rewrecuit/rewopt; moytabou += rewtabou/rewopt; moycascade += rewcascade/rewopt; 43
printf ("****recuit ---- moyenne par rapport optimal: %lf\n",(moyrecuit)/nbsys);
printf ("****tabou --- moyenne par rapport optimal: %lf\n", (moytabou)/nbsys);
printf ("****cascade --- moyenne par rapport optimal: %lf\n",(moycascade)/nbsys);
} 48 resu ltat =fopen(" resu ltat. txt" ,"a") ; fprintf (resultat , "%d tâches: recuit=%f, tabou=%f, cascade=%f\n", i, (moyrecuit)/TAILLE, (moytabou)/TAILLE, (moycascade)/TAILLE); fclose( resultat); } clock_t time2=clock(); 53 printf ("Temps de la simulation : %f secondes\n", (double)(time2-time1)/CLOCKS_PER_SEC); return 0; } |
| ||||||||||||||||||||||
