Home

Rapport de Stage - Université de Bretagne Occidentale

Contents

1. Ex cution normale Section critique Evolution des priorit s FIG 3 7 Application de PCP Le temps de blocage avec PCP Avec PCP le temps de blocage est r duit la dur e de la plus longue section critique La difficult est d identifier l ensemble des sections critiques susceptibles de bloquer une tache Pour une section critique ex cut e par une tache J utilisant une ressource Rg on montre qu elle peut bloquer une tache J seulement si Pj textlessP et II R amp gt Pj Le temps de blocage est donc B dur e de la plus grande section critique parmi celles des taches de priorit lt P et dont la ressource relative R est telle que R gt Pj Prenons Dj k la dur e de la section critique de la tache J utilisant Ry on a B DAI h P lt Piet Re gt P nb R y est la priorit de la tache de plus haute priorit acc dant a Rr Page 40 sur 71 CHAPITRE 3 LA TACHE R ALIS E 3 1 LES RESSOURCES PARTAG ES Section critique FIG 3 8 Temps de blocage avec PCP Soit P lt P lt P lt P T1 est donc la tache la plus prioritaire Consid rons la tache T2 pour le calcul du temps de blocage Pour T PA lt P T est plus prioritaire que T2 donc Tj n est pas a consid rer dans l algorithme Pour T Ps gt P2 Tz est plus prioritaire que 73 La
2. Jitter Size Capacity Priority Offsets doit tre doit tre doit tre doit tre doit tre Unique Non vide lt Deadline si p riodique gt 0 gt 0 entre 1 et 253 Validit FIG A 2 Arbre de test des param tres Page 70 sur 71 ANNEXE A ARBRES DE TEST A 2 OP RATION SUR LES MESSAGES A 2 Op ration sur les Messages Voici l arbre de test des op rations sur les messages Il r pertorie tous les tests de fonctionnement effectu s et leur r sultats Les tests de suppression de messages ont montr s que les d pendences de ceux ci sont bien supprim es Messages Create message Name Jitter Deadline Period Size Message Delete Message dependencies FIG A 3 Arbre de test des messages A 2 1 Validit des param tres Voici l arbre de test de validit des param tres Il r pertorie tous les tests de fonctionnement effectu s et leur r sultats Le contr le de non n gativit est Ok Jitter Unique doit tre Non vide doit tre lt Deadline si p riodique doit tre FIG A 4 Arbre de test des param tres Page 71 sur 71
3. 59 interface de mise jour des messages 60 Ajout d uw TAMPON re Rd de has eating te Aa he ad lee hr ee a Se 62 Modication de tampon 63 ic ne QU CANVAS 506 ae V e ete de ana de ewe doa de wee ede de 74 64 Interface de modification d une ressource 64 Interface de modification d une ressource 65 Interface de modification d une ressource 65 TABLE DES FIGURES TABLE DES FIGURES A1 Arbre de test des t ches ee 69 A2 Arbre de test des param tres 70 A 3 Arbre de test des messages 71 A4 Arbre de test des param tres 71 Page 6 sur 71 Introduction Dans le cadre de la Licence Informatique il nous a t demand d effectuer un stage de fin d ann e d une dur e de deux mois Ce stage a pour but d am liorer nos connaissances et surtout de nous permettre de mettre en pratique l enseignement de licence Nous avons effectue ce stage l Universit de Bretagne Occidentale dans le d partement in formatique sous la direction de Franck Singhoff professeur dans ce d partement et chercheur au laboratoire LIMI Ce stage consiste a poursuivre le d veloppement d un outils d ordonnancement appel Cheddar Celui ci a commenc a tre d velopp s par diff rents groupes d
4. Ressource PCP Methode de calcul PCP Ressource PIP Methode de calcul PIP Ressource g n rique Resource sans protocol we Pas de calcul Taches affect es FIG 3 1 L objet ressource 3 1 2 Les algorithmes de partage Les probl mes d inversion de priorit Il existe des algorithmes classiques d ordonnancement optimaux pour les syst mes de taches ind pendantes mais comme tout syst me multit che un syst me temps r el doit permettre aux taches d acc der a des ressources qu elles ont a partager Nous pr senterons ici un cas connu sous le nom d inversion de priorit qui montre que les r sultats d optimalit de certains algorithmes pr emptifs utilisant des priorit ne s appliquent plus dans le cas de partage de ressources Les algorithmes a priorit s statique Consid rons un syst me de trois taches t1 t2 t3 ayant comme priorit P lt P lt P P tant la tache la plus prioritaire et P la moins prioritaire Supposons que ta et t3 aient fini leur ex cution et attendent la fin de leur p riode respective pour tre r activ es t s ex cute en utilisant une ressource R to est r activ es et interrompt t1 qui n a pas lib re R t3 est r activ es et bien que plus prioritaire que les deux autres taches elle doit attendre la terminaison de t qui bloque t puis que t libre R Page 32 sur 71 CHAPITRE 3 LA TACHE R ALIS E 3 1 LES RESSOURC
5. 3 1 3 IHM de l objet ressource 922 lPr c denc s sica en acre E a A A ARR Go GS ho 3 21 Le Canvas su seit ie ne Monde Rc ode de HO hime he a die tt Bee 3 2 2 Contraintes de pr c dence 3 2 3 IHM Taches Messages Tampons 3 93 Manuel d tilisation aldo R ee 4 dal blah te Les a A A a A e AD a 3327 De CAVAS ii A E eee A ee A NE MARS OU EN 10 10 10 11 13 13 13 15 15 17 17 18 21 23 26 26 26 27 TABLE DES MATI RES TABLE DES MATI RES 3 3 9 JHM Ressources rs ea se 6 au tete dif ee a aie es 64 3 3 4 Modification d une ressource 65 3 3 5 Suppression d une ressource 65 Conclusion 66 A Arbres de test 69 A 1 Op ration sur les t ches 69 A 1 1 Validit des param tres ee ee 70 A 2 Op ration sur les Messages 71 A 2 1 Validit des param tres ee 71 Page 4 sur 71 Table des figures 1 1 1 2 2 1 2 2 2 3 2 4 2 5 2 6 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 3 10 3 11 3 12 3 13 3 14 3 15 3 16 3 17 3 18 3 19 3 20 3 21 3 22 3 23 3 24 3 25 3 26 Organigramme de lUBO 9 Cursus au d partement informatique 10 taches preemptible ato Me e pt AR EOE es TU Es ele 14 t ches non pr emptib
6. Structure d un programme Le bout de code ci dessous un fois compil avec le compilateur Gnat affiche une cha ne de caract res sur la sortie standard Le fichier contient une seule proc dure qui sera ex cut e La proc dure Put Line fait partie du sous package Text_I0 de Ada Donc pour utiliser cette proc dure on aurait pu l appeler par Ada Text_I0 Put_Line Ma chaine mais en pratique on peut utiliser toutes les fonctions et proc dures d un package en l incluant au d but du fichier source avec les clauses with et use Les Packages Les packages permettent de regrouper un ensemble de d clarations de proc dures et de fonc tions Un package est constitu de 1 La sp cification qui se trouve dans un fichier avec extension ads se d compose en deux parties e la partie publique dont le contenu est visible l ext rieur du package e une partie priv e visible depuis le package dans la partie priv e et dans le corps 2 Le corps qui se trouve dans un fichier avec extension adb C est dans ce fichier que les proc dures et fonctions d clar es dans le fichier de sp cification sont d finies Le fichier de sp cification ne peut pas contenir de corps body Par contre un package peut contenir un autre package En ce qui concerne le package d exemple ci dessus le type Point ne peut tre manipul directement En effet il faut utiliser les fonctions ou proc dures d finies dans la partie publique
7. Y JHodify Use Protocol Select a Resource 4 w No Protocol w PIP PCP 3 Task nane t1 Begin 0 End 8 Add Delete Cancel FIG 3 10 Interface de modification d une ressource Lors de la conception de l interface de modifications des ressources figure 3 10 plusieurs probl mes se sont pos s lors de la conception de cette fen tre la premi re fut l impossibilit de r cup rer le signal mis par 1 Option Menu de fa on fiable ce qui t r gler par son remplacement par une Combo_Box ou on peut r cup rer le signal lorsque le champ de la Gentry attach la Combo_Box est modifi Ensuite le protocol de la ressource devait tre modifi chaque changement de ressource un Option_Menu donc t utilis mais il c est retrouv que la fonction set_history du package Gtk_Option_ Menu tait bugg bien que la chaine de caract res visible tait bien celle voulue le pointeur associ tait toujours celui tant la premi re position de la liste associ a 1 Option _Menu on est donc pass une Combo_Box mais aucune fonction n tait d finie pour le faire et cr er cette fonction aurait t trop long on est donc pass au Radio_Button qui nous permis de palier au probl me mais au d triment d une volution facile de la liste des protocoles Page 44 sur 71 CHAPITRE 3 LA TACHE R ALIS E 3 1 LES RESSOURCES PARTAG ES support s par les ressources sans modification de l IHM Il a
8. che dans ce tableau Malheureusement un probl me subsiste Lors de la suppression d une t che les d pendances de celle ci sont bien supprim es mais elle n est pas ray e de la matrice La t che est toujours pr sente dans le tableau Task_Position et donc dans la matrice des d pendances Le probl me ayant t rep r trop tard il n est pas r gl Ce probl me peut tre r solu l aide d une m thode dans task_dependencies mettant a jour la matrice et le set des t ches Mise en place dans cheddar l impl mentation des d pendances tait d j pr sentes ainsi que celle des messages et des tam pons Ces structures sont utilis es par le canvas et permet de maintenir les informations relatives aux d pendances Quelques modifications minimes ont due tre effectu es e suppression de d pendances e modification de m thode de test Page 51 sur 71 3 2 PR C DENCES CHAPITRE 3 LA TACHE R ALIS E L utilisation d un package graph_dependencies permet d effectuer le lien entre le canvas et la structure de Cheddar Ce package traduit les diff rentes informations r colt es par le canvas et lance l enregistrement interne des modifications Il oriente les modifications en fonction de l tat du graph pr sent sur le canvas L enregistrement interne consiste a conserver les d pendances cr es par l utilisateur a l aide du canvas Ces d pendance sont maintenues dans la matrice d crite ci dessus Afin de cons
9. mes caract ristiques est cr La proc dure Update Buffer a donc t r crite de la m me mani re que Update Message cf section 3 2 3 et a le prototype suivant Page 62 sur 71 CHAPITRE 3 LA TACHE R ALIS E 3 2 PR C DENCES procedure Update _Buffer My_Buffers in out Buffers_Set Name in Unbounded_String New_Name in Unbounded_String Size in Natural Location in Unbounded_String Rules in Buffer_Rules_Table Cette proc dure met jour le tampon Name dans un set de tampons My_Buffers avec les nouvelles propri t s New_Name Size Location et Rules L IHM de mise jour de tampons fonctionne de la mani re suivante 1 il faut d abord s lectionner le buffer modifier via un combo box Une fois cela fait les propri t s du combo apparaissent droite du combo Ces informations sont modifiables di rectement et validables via un bouton Modifier 2 une fois le tampon s lectionn ses r les apparaissent dans une clist Pour modifier un r le il suffit de cliquer dessus dans la clist et ses propri t s sont affich es dans des champs modi fiables Il est de plus possible d ajouter ou de supprimer des r les pour un tampon donn Ci dessous une capture d cran de la fen tre de mise jour de tampon Producer Producer 2 Consuner Type Producer Add Delete Hodify Cancel Fic 3 22 Modication de tampon Lors d une mise jour de tampon s le se
10. peut cependant tout moment demander CVS de la mettre jour par rapport la derni re version disponible dans le repository autrement dit d incorporer dans sa copie de travail toutes les modifications apport es par tous les utilisateurs travaillant sur les m mes fichiers que lui Cette op ration s appelle un update Bien entendu le dialogue entre programmeurs peut viter ces petit d sagr ment Commande de CVS CVS offre un certain nombre de commandes aux programmeur Les plus utilis es peuvent tre au nombre de cinq e CVS checkout consiste a cr er un copie local d un ensemble de fichier ins crit dans le repository Page 24 sur 71 CHAPITRE 2 LE PROJET CHEDDAR 2 2 OUTILS CVS update permet la mise a jour des fichiers locaux par rapport au repository CVS commit synchronise la version locale du projet ou d un de ces modules avec le repository CVS add permet l ajout de l entr e d un fichier dans le repository cette action doit tre suivie d un CVS commit pour que la version local du fichier soit prise en compte CVS remove ne supprime pas les versions anterieures du fichier concern mais lors des update ou commit suivant ce fichier ne sera pas pris en compte Page 25 sur 71 2 3 2 8 AVANCEMENT DU PROJET CHAPITRE 2 LE PROJET CHEDDAR Avancement du projet 2 3 1 Le projet d but juin Au d but du stage voici les fonctionnalit s implant es dans cheddar Ajouter Supprimer Mettre
11. cadre de gauche et chacun d entre eux peut tre mis jour par dition du champ correspondant Lors d une mise jour du nom du message ou de plusieurs de ses champs sys messages est mis jour avec les nouveaux param tres du message identifi gauche La liste de droite est ensuite mise jour par rapport sys messages Le canvas est directement mis jour apr s une modification et les noms de message s modifi e s s il y a eu mise jour Page 60 sur 71 CHAPITRE 3 LA TACHE R ALIS E 3 2 PR C DENCES IHM de Buffer Un Tampon est une d pendance d arit n n C est dire que un tampon peut tre reli plusieurs t ches Un Buffer permet de stocker des informations temporaires concernant des t ches Il peut accueillir des informations sur plusieurs t ches Il faut aussi sp cifier au buffer le type d acc s aux donn es Consommateur ou Producteur La r servation des donn es pour une t che se fait par l interm diaire des R les Un buffer est limit par sa taille et la taille totale des r les doit tre inf rieure ou gale celle ci La structure de donn es Buffer Un Buffer est un objet dont la structure est la suivante type Buffer is new Dependency with record Name Unbounded_String To_Unbounded_String Location Unbounded_String To_Unbounded_String Size Natural OS Rules Buffer_Rules_Table end record type Buffer_Ptr is access all Buffer Class Un Buf
12. concerne donc que deux t ches Ces d pendances sont enregistr es dans une matrice Cette matrice est compos e de depends_set un set de pointeurs de d pendance Chaque ligne ou colonne est associ e une t che type Depends_Set is new Dep_Set Set with null record type Tasks_Table is array Dependencies_Range of Task_Ptr type Dependencies_Table is array Dependencies_Range Dependencies_Range of Depends_Set Le packet Set est un packet g n rique Le type Depends_Set d pend de ce packet il utilisera toutes les proc dures et m thodes du package Page 50 sur 71 CHAPITRE 3 LA TACHE R ALIS E 3 2 PR C DENCES from task t1 t2 t3 t4 tl E t2 wapa o t3 S Q 0 il N re FIG 3 13 repr sentation dans la matrice La structure Task_dependencies permet de maintenir les informations li es aux d pendances type Tasks_Dependencies is record Dependencies Dependencies_Table Task_Position Tasks_Table Number_0f_Tasks Dependencies_Range 0 end record Une variable dependencies est inclue dans la structure du packet system Cette variable est accessible a l aide de la variable publique sys par la notation point e sys dependencies Le tableau Task_Position permet d associer une position une t che La position dans la matrice d une t che est retrouv e l aide de l indice de la t
13. cr ation de messages Programmation PCP Mise en place des d pendances Cr ation fen tre de mise jour Fen tre de cr ation de buffers Semaine 5 D buggage fen tre de Programmation PIP cr ation de buffers D buggage fen tre de mise jour Fen tre de vue des buffers Fen tre de vue Gestion des d pendances Semaine 6 Mise en place d une nouvelle Modification fen tre de mise jour mise jour des taches Mise en place de Semi d pendences blocking Time compute et inject Mise en place de la mise jour des buffers Semaine 7 D buggage IHM tache Sauvegarde ressource D buggage d pendances Nettoyage du code D buggage de l IHM buffer D buggage PCP D buggage IHM message D buggage PIP Nettoyage du code D buggage IHM Rapport Rapport Semaine 8 Rapport Rapport Page 27 sur 71 2 8 AVANCEMENT DU PROJET CHAPITRE 2 LE PROJET CHEDDAR Page 28 sur 71 Chapitre 3 La tache r alis e Un certain nombre de fonctionnalit s et d am liorations ont t apport es Cheddar dont les principales sont e l ajout du concept de ressources l ajout d algorithmes d ordonnancement e Pajout d une vue graphe Cheddar e l interfacage d objets existant dans Cheddar le r interfacage de certains objets de Cheddar Ces modifications et ajouts sont expliqu s en d tails dans les sections suivantes 3 1 Les ressources partag es Nous allons introduire ici le concept de ressource nous parlerons ensuite des
14. de cliquer sur affect pour l ajouter la liste et cela autant de fois que n cessaire dans la limite fix pendant la compilation une fois fini il suffit de cliquer sur Ok pour valider la cr ation ou cancel pour annuler 3 3 4 Modification d une ressource On appel la fonction de modification via le menu Edit Update Update Resource Select a CPU Use Protocol A v No Protocol v PIP S PCP 2 Task nane t1 Begin o CS Add Delete Cancel FIG 3 25 Interface de modification d une ressource 3 3 5 Suppression d une ressource On appel la fonction de suppression via le menu Edit Delete delete Resource Give the resource nane r1 OK Cancel FIG 3 26 Interface de modification d une ressource Page 65 sur 71 3 3 MANUEL D UTILISATION CHAPITRE 3 LA TACHE R ALIS E Page 66 sur 71 Conclusion Ce stage nous aura permis de d couvrir le language ADA ainsi que GtkAda Avoir apris GtkAda nous permettra de pouvoir utiliser Gtk avec de tres nombreux language tant donn es l uniformit de ce toolkit Nous avons galement pu d couvrir les algorithmes d ordonnancements tels que RM et DM les notions de pr c dences de ressources partag es et de protocol de partage comme PCP PIP Ce travail en groupe a galement t tr s enrichissant particuli rement pour l utilisation cd CVS mal connu jusqu alors Globalement ce stage c est bien d roul nous avons pu re
15. de conna tre le type de protocole utiliser et de savoir quelle m thode est adapt e au traitement de cette ressource 1 type Resources_Type is 2 No_Protocol 3 Priority_Ceiling_Protocol 4 Priority_Inheritance_Protocol Une ressource est d finie par son nom son tat compteur d acc s un protocole utilise pour la gestion de cette ressource une liste de tache qui lui acc de et un processeur auquel elle est rattach e Un type Generic_ressource a t d clare pour symboliser cet objet 1 type Generic_Resource is abstract new Ada Finalization Controlled with 2 record 3 Name Unbounded_String To_Unbounded_String 4 State Natural 0 5 Protocol Resources_Type 6 Task_Tab Task_ List 7 Cpu Unbounded_String To_Unbounded_String 8 end record Il est indispensable pour une tache de conna tre les taches qui y acc de Il y avait deux possi bilit s pour cela La premi re tait de stocker dans chaque tache la liste des ressource quelle utilise ainsi que le d but et la fin d acc s en unit de temps La seconde tait de stocker dans la ressource elle m me le nom de la tache qui y acc de ainsi que le d but de son acc s et la fin C est la seconde solution qui a t retenue car pour l tape suivant Impl mentation des pro tocole PIP et PCP les algorithmes sont simplifies Un type Affected_Task_List a donc t d fini Ce type permet de conna tre le nom de la tache qui ac
16. la t l robotique les mod les et architectures pour les simulateurs de processus biologiques pour le test de cartes hybrides pour le d pannage Le LIMI a d velopp une expertise autour de la mod lisation des langages de supervision des syst mes r actifs et de la v rification de propri t s temporis es pour ces langages bas es sur les langages synchrones et les automates temporis s Le LIMI est galement expert dans les environnements de programmation pour la robotique mobile et la productique La recherche li e au LIMI est en partie enseign e dans l option de la ma trise informatique syst mes r actifs et intelligents ainsi que dans le module syst mes r actifs du DEA sciences et technologies de t l communications Page 12 sur 71 Chapitre 2 Le Projet Cheddar CHEDDAR est un simulateur d ordonnancement temps r el vocation ducatif d velopp en Ada95 et en GtkAda pour l interface graphique sous licence GPL Cheddar peut tre ex cut sous diff rents Syst mes d exploitation SunOS GNU Linux MS Windows Les objectifs de Cheddar et le travail faire sur celui ci sont pr sent s par la suite 2 1 Objectifs 2 1 1 Ordonnancement temps r el Principe de l ordonnancement temps r el L ordonnancement utilise des Algorithmes qui vont permettre de planifier l ex cution des t ches qui pourront r pondre diff remment suivant le syst me utilis Les Algorithmes d ordonnancement ont aussi pour but
17. le troisi me est la fonction que l on veut appeler quand le signal est captur et le dernier repr sente les donn es que l on souhaite passer cette fonction La fonction sp cifi e en troisi me param tre s appelle une fonction de rappel callback et doit tre de la forme 1 void fonction GtkWidget widget 2 gpointer donnee Le premier param tre de cette fonction est un pointeur vers un widget et le second est un poin teur vers les donn es pass es par le dernier param tre de la fonction gtk_signal_connect d crite plus haut Il est aussi possible de passer un objet Gtk en param tre d une fonction de rappel au lieu d une variable de type abstrait Dans ce cas on utilise la fonction gtk_signal_connect_object avec une fonction de rappel de la forme 1 void fonction GtkObject objet La valeur de retour des fonctions de connexion de signaux est de type gint Il s agit d un marqueur qui identifie la fonction de rappel Il est possible d utiliser autant de fonctions de rappel que l on veut par signal et par objet et chacune sera ex cut e son tour dans l ordre dans lequel elle amp t attach e Ce marqueur permet de d connecter un signal de sa fonction de rappel Page 20 sur 71 CHAPITRE 2 LE PROJET CHEDDAR 2 2 OUTILS 1 void gtk_signal_disconnect Gtk bject objet 2 gint id_rappel Le placement des widgets Dans n importe quel toolkit graphique les widgets sont dispos
18. message Page 59 sur 71 3 2 PR C DENCES CHAPITRE 3 LA TACHE R ALIS E Mise jour d un message L interface ci dessous est la mise jour des message None Jitter Deed1ine Period 5ize_____ 3 3 5 4 1 Jitter 1 Deadline 6 Period 1 Size 3 7 Hodify Delete AA le Ok Cancel FIG 3 20 interface de mise jour des messages La proc dure Update Message a donc t ajout e son prototype est le suivant procedure Update_Message My_Messages in out Messages_Set Name in Unbounded_String New_Name in Unbounded_String Size in Natural Period in Natural Deadline in Natural Jitter in Natural Cette proc dure modifie les param tres existant du message modifier les messages existant apparaissent dans une clist avec leurs param tres En cliquant sur un message de la liste ses pa ram tres remplissent les champs gauche et il est donc ensuite possible de modifier ceux ci Les modifications ne sont prises en compte que lorsque l on appuie sur le bouton modify Cette action remplace tous tous les champs de la tache qui est identifi par son nom par les valeurs des champs de gauche de l interface Il est aussi possible de supprimer un message par le bouton delete la tache supprim e est celle s lectionn e dans la clist Sur la figure 3 20 trois messages ont t cr s et le message m3 s lectionn Ces param tres sont affich s dans les champs du
19. objet Bien qu elle soit enti rement crite en C elle est impl ment e en utilisant la notion de classes et de fonctions de rappel pointeurs de fonctions Par exemple la classe du widget GtkLabel h rite de la classe GtkContainer qui h rite elle m me de GtkWidget qui h rite aussi de GtkObject D s lors on peut connecter des signaux un label puisque c est un GtkObject Pafficher c est un GtkWidget et changer son contenu c est un conteneur tout en pouvant changer ses propres caract ristiques Th orie des signaux Gtk est dirig par les v nements ce qui signifie qu il restera inactif dans sa boucle principale gtk_main jusqu ce qu un v nement survienne et que le contr le soit pass la fonction de rappel appropri e Ce passage de contr le est r alis en utilisant le concept de signal Lorsqu un v nement survient comme l appui sur un bouton le signal appropri est mis par le widget qui t press C est de cette fa on que Gtk r alise la plupart de son travail Pour qu un bouton r alise une action on configure un gestionnaire de signal pour capturer ces signaux et appeler la fonction ad quate Ceci est fait en utilisant une fonction comme gint gtk_signal_connect GtkObject object gchar nom GtkSignalFunc fonction gpointer func_donnees Le premier param tre est le widget qui mettra le signal le deuxi me est le nom du signal que l on souhaite intercepter
20. ou d une mise jour le canvas est reconstruit Plusieurs cas de figures sont alors possibles e soit le projet n est pas le m me Page 52 sur 71 CHAPITRE 3 LA TACHE R ALIS E 3 2 PR C DENCES e soit les modifications ont t effectu es sur le projet courant lorsque le projet est le m me au niveau des d pendences il suffit de prendre en compte les modifications La solution retenue f t de placer des appels de procedure dans les callbacks concern s Par exemple la suppression d un t che entra nera la suppression de toute ses d pendences Un changement de projet entra ne la reconstruction des diff rentes variables de la structure du syst me Pour mettre jour les semi_d pendences deux essais ont t effectu s e La premi re id e f t de mettre en place une proc dure permettant de synchroniser les va riables dependencies et half_dependencies de la structure du syst me Cette proc dure par coure le set des d pendences et ajoute les semi_d pendences correspondantes dans la variable half_dependencies Cette m thode contenait plusieurs boucle pour que les informations soient coh rentes et pour parcourir le set des d pendences e La seconde solution permet d viter l ajout de parcourt de set L ajout de semi_d pendences ce fait lors de la construction du set des d pendences Ainsi l algorithme est moins gourmand en ressource Pour chaque d pendence deux semi_d pendences sont ajout es Cependant ce
21. s hi rarchiquement dans des conteneurs meta widgets invisibles Dans plusieurs d entre eux en revanche les widgets sont positionn s de fa on fixe dans leurs conteneurs gtk offre cette possibilit n anmoins il est tr s rare que cette option soit choisie Le placement automatique est en effet pr f r par le biais de conteneurs de type boite ou table La taille et ou le placement des widgets est remis jour si la taille de la fen tre les contenant change videmment il existe aussi des fen tres qui sont aussi des conteneurs ne pouvant stocker qu un widget un autre conteneur par exemple Les diff rents bindings Une des caract ristiques qui fait la force de Gtk est d avoir une APT orient e objet tr s ho mog ne mais crite en C Il est donc possible de l utiliser depuis plusieurs langages comme le C le Perl le Python P Ada95 cf partie sur GtkAda Ces bindings ne sont pas tr s durs mettre en place car il ne constitue qu une encapsulation des fonctions de Gtk m me si certains ajoutent suppriment des fonctions ou fournissent de base pour des widgets suppl mentaires C est notamment le cas pour GtkAda 2 2 3 GtkAda le binding Ada de Gtk GtkAda est l adaptation en Ada de PAPI de Gtk Avec ce toolkit la cr ation d interfaces graphiques en Ada95 et multi platformes dont Unix et Win32 est ais e Bien que GtkAda soit bas sur son homologue en C il utilise les possibilit s de Ada telle
22. sont aussi cach s Beaucoup de probl mes sont apparus au cours du d veloppement de la vue graphes 1 Concernant la barre d outils un certain nombre de versions ont t n cessaires avant d arriver la version finale qui est simple d utilisation et facile comprendre 2 Le canvas a t dur a impl menter car le m canisme de cr ation et d affichage d items n est pas vident assimiler beaucoup de relations existent entre le syst me d objets de Cheddar et la vue graphes Par la suite le m canisme des contraintes de pr c dence va tre expliqu Page 49 sur 71 3 2 PR C DENCES CHAPITRE 3 LA TACHE R ALIS E 3 2 2 Contraintes de pr c dence Explications th oriques Les d pendances n ont de sens qu entre deux t ches Ces deux t ches sont alors li es par une contrainte de pr c dence Les d pendances peuvent tre de trois types diff rents type Dependency_Type is Precedence_Dependency Buffer_Dependency Communi cation_Dependency communication_dependency precedence_dependency X buffer_dependency FIG 3 12 types de d pendance La Premi re est une simple contrainte de pr c dence entre deux t ches La seconde inclue un tampon entre les deux t ches ce tampon contient des r gles Le tampon est d arit n n La troisi me inclue un message entre les deux t ches ce message contrairement au tampon est d arit 1 1 il ne
23. t demand que la ressource puisse tre chang e de processeur pour cela un Radio Button a t rajout qui lorsqu il est s lectionn fait appara tre une Combo_Box qui permettra de s lectionner le nouveau processeur cette approche a t choisi pour viter toute confusion du la pr sence de deux Combo_Box contenant le m me type d information lorsque le changement est pris en compte la Combo_Box est remasqu e Il est possible d ajouter de supprimer ou de modifier les t ches associ es a une ressource les changements effectu s sont fait chaque fois qu un bouton est press dans la limite ou le maximum de t ches pour une ressource n est pas d pass qui t fix 50 Il existe trois m thodes pour que les changements soit pris en compte e En modifiant le processeur courant e En modifiant la ressource courante e En cliquant sur le bouton Ok Pour viter qu une sauvegarde soit effectu alors qu il n y as pas eu de modification la valeur des champs est compar e aux valeurs se trouvant dans la structure de l objet ressource sans un nouveau parcours de la liste des ressources Pour cela la fonction Resource Modify a t d finie pour tre appel par les diff rentes m thodes cette fonction choisiras les param tres de sauvegarde qui correspondent aux champs qui ont t modifi es Page 45 sur 71 3 1 LES RESSOURCES PARTAG ES CHAPITRE 3 LA TACHE R ALIS E resource_Modify update_ressou
24. t che T1 la t che T1 commence son ex cution quand T2 fini mais ne peut pas finir son Page 14 sur 71 CHAPITRE 2 LE PROJET CHEDDAR 2 1 OBJECTIFS ex cution car T2 est plus prioritaire La t che T1 est donc pr empt et pourras finir son ex cution lorsqu aucune t che plus prioritaire ne voudras s ex cuter L algorithme Deadline Monotonic DM L algorithme Deadline Monotonic calcule la priorit par rapport aux d lais critiques plus le d lai critique sera petit plus la tache sera prioritaire Algorithmes priorit dynamique On retrouve aussi dans Cheddar des algorithmes priorit dynamique tel que EDF Earliest Deadline First LLF Least Laxity First HPF Hightiest Priority First 2 1 2 R sultat obtenu avec Cheddar La figure 2 4 contient trois t ches p riodiques et pr emptible ordonnanc avec l algorithme RM on peut voir que T2 est pr empt 13 fois pour permettre l ex cution de T1 qui une priorit plus basse et est donc plus prioritaire De plus T2 se trouve tre bloqu s cause d une ressource PCP 1 qui est utilis e par la t che T1 alors que T2 veut y acc der 2 1 3 Les contraintes de pr c dence Un autre objectif du stage est de r aliser une vue pour Cheddar Cette vue permet de dessiner et de visualiser les objets t ches tampons messages de Cheddar Elle doit tre ind pendante de Cheddar du point de vue de son utilisation cr ation destruction d items Elle doit de plus m
25. ES PARTAG ES Tache utilisant R TEL Tache n utilisant pas R 4 Activation de la tache FIG 3 2 Inversion de priorit Il n existe pas a ce jour d algorithmes polyn mial permettant d ordonnancer les syst mes de taches partageant les ressources Les algorithmes a priorit s dynamiques Le m me exemple sera utilis mais cette fois les priorit s ne seront pas fixe au d part Consid rons Valgorithme ED bri vement d crit dans la partie 2 et supposons les ch ances des taches not es Ri Ra et R3 telles que R gt R2 gt R3 On se retrouve dans le m me cas se figure que pour les algorithmes a priorit s statique Il existe une variante de ED qui utilise un protocole a priorit h rit es qui g re les inversion de priorit de la mani re suivante quand une tache est bloquante on lui donne la priorit de la tache qu elle bloque qui poss de la plus haute priorit et ce jusqu la lib ration de la ressource bloquante Cette m thode vite les inversions de priorit s mais sont fonctionnement n est pas optimal PIP Priority Inheritance Protocol Introduit par Sha Rajkumar et Lehoczky en 1990 le protocole PIP emp che les taches de priorit moyennes de pr empter la tache responsable du blocage d une tache de plus haute priorit et de prolonger ainsi son temps de blocage Principe L id e de base de PIP est d affecter temporairement la ta
26. L ensemble des sections critiques pouvant bloquer T est recherch pour chaque tache Tn ayant une priorit inf rieure a P priorit de T La plus grande des sections critique pour cette tache est retenue La somme de ces valeurs est calcul e En parall le le nombre de tache qui on au moins une section critique avec T sont comptabilis tape 2 Pour chaque ressource R l ensemble des sections critiques Sy qui utilisent cette ressource et peuvent bloquer T sont recherch La dur e maximale dans cet ensemble est retenue pour la ressource Rn La somme de ces valeurs est calcul e En parall le on compte le nombre de taches qui peuvent bloquer 7 Ensuite le nombre de taches qui bloque T est multipli avec la dur e maximale de la section critique calcule dans la premi re tape Par analogie le nombre de ressource bloquant 7 est multipli avec la somme des section critiques pour les taches Rj Le minimum de ces deux valeurs est gard e Page 36 sur 71 CHAPITRE 3 LA TACHE R ALIS E 3 1 LES RESSOURCES PARTAG ES Voici un exemple avec la premi re et la deuxi me tape d crites ci dessus Prenons pour le premier exemple Po lt P lt P lt P c est a dire que la tache prioritaire est 72 Les taches moins plus prioritaires que T n aurait pas t consid r es dans l algorithme La tache utilis e pour l algorithme est T2 Pour le second exemple on aura P lt P2 lt P P est la plus prioritaire La tache consi
27. Le Plafond de priorit d une ressource Ri est la plus haute priorit des taches acc dant a Ri et on la note R Le plafond de priorit courant su syst me not est gal au maximum des plafonds de priorit des ressources utilis s ou Q si aucune ressource n est utilis Q est une priorit plus base que n importe qu elle priorit Consid rons trois taches Jo J1 et J2 avec Po gt P gt P ainsi que trois ressources partag es Ro R et Ro telles que e JO utilise RO puis R1 e J utilise R2 e J2 utilise R2 puis R1 On a donc Ro Po I R1 Po et Re P e To Ja est activ peut prendre Ra car Pa gt I e Ti J pr empte Jo e To J ne peut prendre Ro car P n est pas gt R2 Jo h rite de la priorit de Jo et reprend son ex cution e T3 Jo peut prendre A car aucune ressource n est utilis TA Jo pr empte Jo e Ts Jo ne peut prendre R1 car aucune ressource n est utilis e Page 39 sur 71 3 1 LES RESSOURCES PARTAG ES CHAPITRE 3 LA TACHE R ALIS E e T Ja lib re R et reprend sa priorit P P Ja est alors pr empt par Jo et ce dernier prend Ro car on a Po gt I R2 e T7 Jo termine son ex cution J reprend la sienne et prend la ressource Ro e Tg Jo libere Ro et reprend sa priorit initiale Py J pr empte Jo et prend Ra car on a P gt II Q e To J termine son ex cution Jz peut reprendre et terminer la sienne
28. Pour que l utilisateur ne puisse pas entrer une t che qui n existe pas on utiliser une Combo_Box qui regroupe les t ches existant dans le syst me Pour l interface de modification des ressources des filtres sur les processeurs et les ressources sont utilis s leur but est d viter d avoir une liste ou on retrouverait des ressources sans savoir quelle processeur elles sont attach es et une liste de t che sans lien visible avec la ressource associ e Lors du choix des l ments que l utilisateur pourrait modifier il a t d cider d interdire la modification du nom de la ressource en effet le nom de la ressource est consid r comme tant un identifiant Ce cas a tait consid r diff remment dans la gestion des t ches ce qui peut conduire une incoh rence au niveau des t ches associ es une ressource la t che lors de la cr ation porte un nom quelconque mais son nom est modifi donc la ressource une t che qui lui est associ e qui n existe plus il est possible de r gler le probl me pendant la modification de la t che mais cette solution est tr s lourde en utilisation processeur si le nombre de ressources est important car il seras alors n cessaire de parcourir la liste des ressources puis celle des t ches associ es la ressource on se retrouve donc dans le cas le plus d favorable Max_Ressources Max_Tasks Max_Processors acc s m moires Select a CPU Resource State Integer 1 pz H r _
29. Rapport de Stage Cheddar Licence Informatique Philippe Normand Sebastien Herry Regis Prevot Wanig Guillo Gwendal Oliva 26 juillet 2002 Page 2 sur 71 Table des mati res Introduction 1 UBO LT Historique Abaco a E ee RM re A ns sa E 1 2 Le d partement Informatique 1 2 1 L UFR sciences et techniques 1 2 2 Le d partement informatique 1 3 Le Laboratoire LIMIT 2 Le Projet Cheddar 2 17 Objects cuina Bat amet ct thee Le are Sant ah ne PNR Eu a 2 1 1 Ordonnancement temps r el 2 1 2 R sultat obtenu avec Cheddar 2 1 3 Les contraintes de pr c dence 22 OUTIS ss ris aa RO agi has Mutant Qe Sle a me 2 2 1 Le Langage Ada95 2219 o Ces benne Ba Do ee es D Hd Be Be DE Ay eed an de eee BRE 2 2 3 GtkAda le binding Ada de Gtk De DAs MONS ae rene A ele Wooden oh od ae ce 2 3 Avancement du projet 2 341 Le projet d but jun a due a alu ek aa als GA hk ak 2 3 2 Am lioration uc A te nie ee A a ENE 2 353 Pl nnines e 40 hon RN 3 La tache r alis e 3 1 Les ressources partag es 3 1 1 Le concept de ressource 3 1 2 Les algorithmes de partage
30. Ro puis une autre R1 avant de lib rer Ro une autre tache J effectue l allocation de ressource inverse avec P gt P1 Pegen aa Ex ction normale Ex cution critique FIG 3 5 Inter blocage avec PIP e To J est activ e peut prendre Ry et entre en section critique e Ti Jo est activ e et pr empte J e To Jo peut prendre R car cette ressource est libre e T3 Jo ne peut pas prendre Ry car cette ressource est utilis e par J1 De m me J ne peut pas prendre R et on a une situation d inter blocage De plus PIP peut entra ner le ph nom ne de cha ne de blocage qui survient lorsque la tache la plus prioritaire est bloqu e une fois par toutes les autres taches Consid rons trois taches Jo J1 J9 avec Py gt P gt P2 ainsi que deux ressources Ro et R1 Jo utilise Ro puis Ro puis R1 J utilise Ry et Jo utilise Ro Page 35 sur 71 3 1 LES RESSOURCES PARTAG ES CHAPITRE 3 LA TACHE R ALIS E Calcul des temps de blocages Le calcul des temps de blocages avec PIP se fait gr ce aux d quations suivantes B tant le temps de blocage de la tache i P tant la priorit d une tache i D k tant la dur e de la section critique d une tache j pour la ressource k n Bi max D TI Rk gt Pi j i 1 F B Y max Dix Rk gt Pi k 1 J lt Bi min B Bs 2 Le calcul du temps de blocage se divise en trois tapes Prenons une tache T tape 1
31. a jour un processeurs Ajouter Supprimer Mettre a jour une tache Tracer un ordonnancement Contr ler la faisabilit d un ordonnancement Sauvegarder un projet Seulement tache et processeur Charger un projet Nettoyer l espace de travail Algorithmes d ordonnancements implant s RM DM EDF LLF HPF Il nous a t demand d am liorer les fonctionnalit existantes et d en ajouter 2 3 2 Am lioration Cheddar est compilable sous Windows Linux et Solaris Le seul probl me au cours de la compi lation est que certains fichiers ceux de l internationalisation du logiciel se compilent tr s lentement Ceci est d au nombre tr s important de variables temporaires Lb_Root_Title Francais To_Unbounded_String Cheddar un simulateur d ordonnancement temps r el Lb_File Francais To_Unbounded_String Fichier Lb_New Francais To_Unbounded_String Nouveau Lb_Open Francais To_Unbounded_String Ouvrir Il y a trop de To_Unbounded String ce qui provoque un warning du compilateur Ada et un contretemps norme en phase de d boggage A ce probl me deux solutions ont t propos es l utilisation de gettext a t envisag e Gettext permet de remplacer des cha nes de caract res d une certaine langue par d autres de langues diff rentes lors de l ex cution du programme la vol e Une macro est utilis e afin de pr fixer toutes les cha nes de caract r
32. algorithmes de par tage utilises pour la gestion de ces ressources et enfin le L interface homme machine qui permettent a Putilisateur de les utiliser 3 1 1 Le concept de ressource D finition Une ressource est une structure logicielle pouvant tre utilis e par une tache pour avancer dans son ex cution Par exemple un ensemble de variable la m moire partag e un fichier etc Une ressource est priv e si elle est d di e a une tache particuli re et partag e si elle est utilis e par plusieurs tache Dans ce dernier cas des s maphores assurent l acc s exclusif Le partage de ressources dan un syst me temps r el peut tre a l origine du ph nom ne d inver sion de priorit Pour viter ce genre de probl me il est possible d utiliser des protocole de partage de ressource dont le fonctionnement sera tudie plus tard Le partage de ressource permet a des taches diff rentes de pouvoir exploiter les m mes informa tions en m me temps et de mani re transparente pour l utilisateur Il est donc possible pour deux taches de lire le m me fichier ou la m me zone m moire par exemple 29 3 1 LES RESSOURCES PARTAG ES CHAPITRE 3 LA TACHE R ALIS E Impl mentation Dans Cheddar une ressource peut tre g r e par deux protocoles diff rents ou par aucun Un ressource poss de dons un protocole attache celui ci peut tre PIP PCP ou No_Protocole Pas de protocole Un type Ressource_type a donc t d finis celui ci permet
33. c de a la ressource le temps de d but de son acc s et le temps de fin de son acc s en unit s de temps Ce type sera stock dans un tableau de Max_Tasks l ments Par d faut Max_Tasks est gal a cinquante ce chiffre apr s mure r flexion nous a paru correcte ceci voulant dire qu une ressource peut avoir cinquante acc s diff rents 1 type Affected_Task_List is 2 record 3 Task_Name Unbounded_String To_Unbounded_String 4 Task_Begin Natural 0 5 Task_End Natural 0 6 end record type Task_List is Array Natural Range 1 Max_Tasks of Affected_Task_List L objet g n rique ressource a t d cline en plusieurs sous objet PCP_Ressource PIP_Ressource et NP_Ressource Page 30 sur 71 CHAPITRE 3 LA TACHE R ALIS E 3 1 LES RESSOURCES PARTAG ES 1 type PCP_Resource is new Generic_Resource with private 2 3 type NP_Resource is new Generic_Resource with private 4 5 type PIP_Resource is new Generic_Resource with private Chacun de ses objets disposes de m thodes d initialisation et de d claration de pointeurs Ces pointeurs permettent d utiliser les taches lors de recherches dans le set qui les contient En effet tous les objet ressources sont stockes dans une liste qui n est pas encore dynamique mais devrai le devenir Des m thodes d actes aux l ments de cette liste on t cr e dans le package set Page 31 sur 71 3 1 LES RESSOURCES PARTAG ES CHAPITRE 3 LA TACHE R ALIS E
34. ces pour Machines Intelligentes ou non LIMI anim e par L Marc e R alit virtuelle AREVI anim e par J Tisseau e Les deux parties de l quipe pour l U B O projets AS In Fo LIMI et pour PENIB AREVI ont actuellement des politiques et des financements ind pendants Elles organisent n anmoins en commun depuis 1996 annuellement une journ e de s minaires pour faire le point sur les avanc es de l ann e Le projet Langages et Interfaces pour Machines Intelligentes LIMI est n en 1990 suite la nomination Brest de L Marc comme Professeur d informatique Avant la cr ation de PEA 2215 le LIMI regroupait la communaut universitaire recherche en G nie Informatique localis e Brest ce qui lui a permis de se structurer en projets Suite l organisation de EA 2215 en projets le laboratoire LIMI s est r parti en plusieurs projets dont le projet LIMI ici d crit La probl matique g n rale est l tude des langages interfaces et environnements informatiques pour la supervision et l exploitation des machines intelligentes ou non plus g n ralement des syst mes voluant avec le temps avec comme applications les langages de sp cification et de contr le Page 11 sur 71 1 3 LE LABORATOIRE LIMI CHAPITRE 1 UBO d ex cution pour le temps r el les m thodes et les langages de sp cification pour la productique la t l productique les architectures logicielles et mat rielles pour la robotique
35. che responsable du blocage avec la priorit de la tache la plus prioritaire Chaque tache J poss de une priorit fixe d termin par RM ainsi qu une priorit actuelle P t Lorsqu une tache J demande une ressource Ry on a l une des situations suivantes e Si est libre J prend la ressource et entre en section critique e Si R n est pas libre J est bloqu e De plus la tache qui bloque J h rite de sa priorit actuelle Cette tache continue s ex cuter avec sa nouvelle priorit jusqu ce qu elle lib re la ressource Elle reprend alors sa priorit initiale c est a dire celle qu elle avait avant de prendre la ressource Page 33 sur 71 3 1 LES RESSOURCES PARTAG ES CHAPITRE 3 LA TACHE R ALIS E L h ritage de la ressource tant transitif il se peut qu une t che h rite plusieurs fois si elle bloque plusieurs taches Consid rons une ressource Ro partag e entre des taches Jo J et Ja telles que P gt P1 gt P2 Sans PIP ceci donnerai Ex cution normale Section critique FIG 3 3 Ordonnancement sans PIP e To Ja est activ e peut prendre Ro et entre en section critique e Ti Jo pr empte J2 et commence son ex cution e To Jo ne peut prendre R car la ressource n est pas libre J2 reprend son ex cution e T3 J est activ e et pr empte Jo e T Jo ne peut prendre R car la ressource n est pas libre J2 reprend son ex cutio
36. chiers et donc d tecter plus vite les erreurs de compilation Gnat est livr avec une suite d ex cutables dont le plus int ressant est gnatmake sachant qu l instar de javac le compilateur Java il compile un fichier cible et toutes ses d pendances Il n est donc pas forc ment obligatoire de s affranchir de l criture des Makefiles 2 2 2 Gtk Gtk est un toolkit graphique con u pour GNU Linux qui a t d velopp pour la conception de Gimp en tant qu alternative Motif Aujourd hui Gtk est utilis bien au del de Gimp et a suscit beaucoup d engouement de la part des d veloppeurs pour sa simplicit sa modularit et ses bin dings Publi sous licence GPL il est pl biscit dans de nombreux logiciels libres l environnement Gnome par exemple Gtk est un ensemble de 3 librairies Glib Gdk et Gtk qui correspondent trois couches d utilit bien distinctes Gtk Gdk Xlib Win32 FIG 2 5 Organisation hi rarchique de Gtk 4GNU Public Licence Page 18 sur 71 CHAPITRE 2 LE PROJET CHEDDAR 2 2 OUTILS Le r le de chacune de ces librairies va tre d taill par la suite Glib Glib est la couche la plus basse Elle a les caract ristiques suivantes Elle d finit des structures de donn es qui sont souvent utilis es listes chain es tables de hachage analyseur lexical et des fonctions permettant leur manipulation Elle augmente la portabilit de Gtk e
37. ck Gtk_Window_Record 15 fenetre Gtk_Window 16 begin 17 Gtk Main Init 19 Gtk_New fenetre 20 window_Cb Connect Fenetre delete_event 21 Window_Cb To_Marshaller Delete_Event_Handler 2 show fentre 23 24 6 gtk Main Main 25 end Test La gestion des signaux Contrairement Gtk C on ne peut pas passer des donn es quelconques gpointer donnees aux handlers En GtkAda Connect ne permet la fonction de rappel que de recevoir en param tre l objet qui a mis le signal La solution est d utiliser Object Connect qui permet d obtenir au niveau de la fonction de rappel toujours un seul param tre mais qui est un objet diff rent de celui qui a mis le signal Cela ne r gle pas tout le probl me mais la solution a t compl t e en ajoutant les donn es n cessaires dans l objet consid r Afin de pouvoir travailler efficacement en quipe CVS a t utilis CVS est un outil de gestion de versions de fichiers Il est beaucoup utilis au cours du d veloppement car il permet de sauve garder efficacement le travail de chacun dans un d p t centralis Ainsi Cheddar volue continuel lement au cours du d veloppement Les avantages et inconv nients de cet outils sont argument s dans la section suivante Page 22 sur 71 CHAPITRE 2 LE PROJET CHEDDAR 2 2 OUTILS 2 2 4 CVS Desciption de CVS CVS Concurent Versions System permet la gestion des sources d un projet un outi
38. d r e est ici T FIG 3 6 Temps de blocage avec PIP Dans le premier exemple il y a trois sections critiques une de 3 unit s de temps avec T une autre d une unit de temps avec T et une d une unit de temps avec T1 Pour la tache T il y aura donc un temps de blocage de 3 max 1 3 et de 1 pour 74 Dans ce cas il y a deux taches qui peuvent bloquer T2 Le r sultat obtenu pour la tache consid r e est Pour les taches 3 1 44x2 38 Pour les ressource 3 4 77 3 21 Le r sultat final min 8 21 8 Le temps de blocage de 72 est de 8 unit s de temps Page 37 sur 71 3 1 LES RESSOURCES PARTAG ES CHAPITRE 3 LA TACHE R ALIS E Les algorithmes ADA Voici une br ve descriptions des algorithmes d velopp s 1 PIP_Critical_Tasks Task_Name A Task Set A Resource _ Set Tasks_Critical Tasks_N e Task_Name Le nom de la tache pour laquelle l algorithme PIP se d roule e A_Task_Set L ensemble des taches su syst me e Resource Set L ensemble des ressources du syst me e Tasks_Critical La somme des section critiques calcul e e Tasks_N Le nombre de taches pouvant bloquer la tache Task Name Cette fonction retourne Task_critical et Task_N Elle permet de conna tre la sommes des section critiques pour une tache Task_Name et le nombre de taches qui peuvent la bloquer Elle correspond a l tape une vue pr c demment 1 PIP_Critica
39. d int grer les Ecoles d Ing nieurs et valorisent par la suite leur parcours universitaire original et formateur PUBO et PUFR Sciences et Techniques se tourne r solument vers l avenir avec et pour ses tudiants nouvelles technologies renouvellement p dagogique formations professionnelles d veloppement des relations internationales 1 2 2 Le d partement informatique Le D partement d Informatique est un d partement d enseignement et de recherche Le D partement est responsable des enseignements et g re les quipements relevant de ses activit s p dagogiques DEUG TECHNO DEUG MIAS SM Autres DEUGS CNAM option info option info BTS DUT autres Dipl me LICENSE INFORMATIQUE ENIB sortie possible REE pour emploi Maitrises Dipl me Ecoles sortie possible MAITRISE D INFORMATIQUE d ingenieurs pour concours DEA autres DESS DESS Brest puis THESE ecoles d ingenieurs Automatisation de la production J passage titre normal FIG 1 2 Cursus au d partement informatique Il est administr par un conseil de d partement lu constitu de e L ensemble des professeurs e Autant d autres enseignants qu il y a de professeurs e Autant d autres enseignants qu il y a de professeurs Page 10 sur 71 CHAPITRE 1 UBO 1 3 LE LABORATOIRE LIMI e Un repr sentant du personnel technique e Un tudiant de deuxi me cycle et un tudiant de troisi me cycle Le conseil de d partement lit parmi ses membres enseignants un respo
40. de permettre aux t ches de respecter leur ch ance une ch ance tant la dur e laquelle la t che doit avoir termin e Il existe deux cat gories de t che e Les t ches p riodiques qui seront le plus souvent utilis e pour le contr le L ch ance doit tre de dur e inf rieure ou gale la p riode e Les t ches ap riodiques qui n ont pas de d clenchement pr visible et qui peuvent tre activ es par des t ches p riodique en cas d urgence Les t ches peuvent aussi tre pr emptible ou non pr emptible dans le cas d une t che pr emptible figure 2 1 celle pourra tre interrompu par le syst me et mise en attente pour permettre 4 une t che de plus forte priorit d avoir acc s au processeur tandis que dans le cas d une t che non pr emptible figure 2 2 une t che ayant une priorit plus haute devra attendre la fin de l ex cution de la t che en cours pour pouvoir acc s au processeur C Capacit est la dur e de la t che P Est la priorit de la t che plus elle est base plus la priorit est haute ST Repr sente son temps de d part Chaque t che doit s ex cuter int gralement dans un intervalle de temps fixe qui d pend de la p riodicit de la t che des contraintes des caract ristiques du syst me et sera caract ris e temporellement par quatre valeurs num riques p riode ch ance Date d activation et la capacit Pour les ordonnancements priorit s fixe il exis
41. du package Enfin le corps du package peut contenir des exceptions qui servent g rer les diff rents cas d erreurs Les types d riv s et acc s Un type d riv est bas sur un type quelconque et lui est presque identique La d rivation de type inclut la copie des op rations primitives du type d origine h ritage et par cons quent on Gimp Toolkit 3GNU Image Manipulation Program Page 17 sur 71 2 2 OUTILS CHAPITRE 2 LE PROJET CHEDDAR ne peut m langer des l ments de deux types Le type d origine appel parent et le type d riv appartiennent la m me cat gorie de type si le type parent est un article le type d riv est aussi un article Les types d acc s sont l quivalent des pointeurs en C A la base les pointeurs contiennent l adresse m moire d une donn e que ce soit un entier ou le premier l ment d un tableau Il en existe deux sortes ceux permettant l acc s d autres l ments ou donn es ceux donnant l acc s des sous programmes Ada peut tre utilis comme un langage orient objet En effet il peut consid rer l h ritage l encapsulation et le polymorphisme Le compilateur Gnat Le compilateur Ada le plus utilis est Gnat Celui ci se base sur le compilateur Gcc pour produire un code natif ex cutable Une table des symboles les fichiers avec extension ali est cr e pour chaque package afin d acc l rer la recherche des symboles dans les fi
42. e Task_Name Nom de la tache pour laquelle calculer le blocking time e A_Task_Set Ensemble des taches du syst me e Resource Set Ensemble des ressources du syst me e retourne Le temps de blocage de la tache Task_Name Calcul le temps de blocage final pour une tache de nom Task_Name Cette fonction utilise la fonction PCP_Critical_Tasks d crite ci dessous 1 function PCP_Critical_Tasks Task_Name in Unbounded_ String 2 A_Task_Set in Tasks_Set 3 A_Resource_Set in Resources_Set 4 return Natural is Task_Name Nom de la tache pour laquelle calculer le temps de blocage e Task Set Ensemble des taches du syst me e Resource Set Ensemble des ressources su syst me e retourne retourne un premier r sultat qui sera trait dans la fonction blocking time Cette fonction permet de calculer un premier temps de blocage pour la tache Task_Name Page 42 sur 71 CHAPITRE 3 LA TACHE R ALIS E 3 1 LES RESSOURCES PARTAG ES 3 1 3 IHM de l objet ressource Choix technologique de la conception de THM Les IHM n cessaires l objet ressource sont aux nombres de quatre comme pour les autres objets existants Processeur T che savoir e L interface d ajout des ressources figure 3 9 e L interface de modification des ressources figure 3 10 e L interface de suppression des ressources e L interface de visualisation des ressources existantes Les interfaces graphiques ont t d co
43. e projets d iup par Mr Singhoff et Mr Legrand th sard Cet outil est utilis dans l enseignement au d partement informatique Il permet de simuler l ordonnancement de taches sur un ou plusieurs processeurs avec plusieurs protocoles d ordonnancement tel que RM et DM Il nous a t demand de poursuivre le d veloppement de cette application tous en essayant d am liorer les fonctionnalit s d j existantes Les principaux points sont l ajout des pr cedances et d un canevas permettant de les g rer ainsi que la mise en place du concept de ressources et de partage de celle ci Pour permettre un d veloppement de meilleure qualit il a t d cid de cr er deux groupes de d veloppements un pour les pr c dences et le canevas l autre pour les ressources D une part nous pr senterons l Universit de bretagne occidentale ainsi que le d partement informatique et le laboratoire LIMI ou nous avons effectu notre stage D autre part nous d crirons le projet cheddar les outils utilis durant ce stage et l tat d avancement du projet lors de notre arriv e Enfin nous exposerons la tache r alis lors de ces deux mois qui comprend la mise en place des contraintes de pr c dences et la cr ation des ressources partag es TABLE DES FIGURES TABLE DES FIGURES Page 8 sur 71 Chapitre 1 Pr sentation de l UBO 1 1 Historique L Universite de Bretagne Occidentale est constitue des UFR suivantes Lettres et Scie
44. erver toutes les informations li es aux d pendances le type half dep est n cessaire type Half _Dep_Type is To_Task To_Dependency to_dependency to_task FIG 3 14 types de semi_d pendence type Half_Dep is record The_task Task_Ptr The_Dep Dependency_Ptr The_Type Half_Dep_type end record les semi d pendences c est dire les liens t che tampon ou t che message permettent un main tient plus fin de l information li e a une d pendence Le premier essai n utilisait pas ces semi_d pendences mais comportait certaine contraintes d uti lisation Par exemple l utilisateur ne pouvait d finir de lien buffer t che ou message t che que si auparavant il avait saisi une semi d pendences entre une t che et ce m me buffer ou message Gr ce a l usage de cette structure ce probl me n est plus Toutes les configurations du graph sont enregistr es et peuvent tre modifi es sans perte d information les couples de semi_d pendence forme une d pendence C est pourquoi lors de la cr ation d une semi_d pendence la v rification de l existence de sa pair est n cessaire Ainsi si celle ci existe la d pendence correspondante est cr e Bien s r il en va de m me pour la suppression Une fois la structure mise en place le d buggage effectu la liaison avec les v nements de cheddar restait faire Bien entendu lors de l ouverture d un nouveau projet
45. es du programme Ensuite le programme zgettert permet d extraire ces cha nes et de constituer un fichier de r f rence avec un ensemble de couples msgid msgstr msgid correspond la cha ne traduire et msgstr sa traduction dans une certaine langue Il suffit de copier ce fichier de le renommer fr po pour le fran ais par exemple et de remplir les lignes msgstr H las cette solution a des lacunes au niveau de la portabilit et n a donc pas t adopt e l utilisation d une num ration double dimension pour fran ais et anglais Cette solution a l avantage d tre plus pratique d utilisation mais ne fait que contourner le probl me En effet le nombre de variables locales reste le m me Toutefois elle a t mise en oeuvre mais pas commit e sur le CVS Page 26 sur 71 CHAPITRE 2 LE PROJET CHEDDAR 2 8 AVANCEMENT DU PROJET 2 3 3 Planning Ci dessous le planning pr visionnel du stage durant ces deux mois il t suivi et permis de respecter les d lais eo Mise en place des pr c dences Ressources partag es Semaine 1 Apprentissage de 1 Ada Apprentissage de Ada et GtkAda et GtkAda Semaine 2 Canvas et toolbar Th orie sur PCP PIP RM DM Cr ation menu fen tre Semaine 3 Canvas et toolbar Analyse Scheduler Cheddar j greffe Finalisation de la toolbar Cr ation fen tre d ajout Fen tre de vue des messages suppression de ressources Programmation de l objet ressource Semaine 4 Fen tre de
46. ettre en vidence les contraintes de pr c dence que l utilisateur peut mettre en place dans Cheddar Priority Ceiling protocol Page 15 sur 71 2 1 OBJECTIFS CHAPITRE 2 LE PROJET CHEDDAR Cheddar a real time scheduling simulator File Edit View Tools Help Clelal lel SE16 P 3 Ge 2 De 3 S 6 Cpu P1 G es us M ou ul os os un jun Pe 7 C 5 O 7 S 9 Cpu P1 P 8 C 5 Dz 8 S 9 Cpu P1 E essor Pl Number of preenption 13 Periodic task missed its deadline deadline 7 completion time 21 Periodic task T2 missed its deadline deadline 7 completion time 36 Blocking Time 18 FIG 2 4 capture de Cheddar Page 16 sur 71 CHAPITRE 2 LE PROJET CHEDDAR 2 2 OUTILS 2 2 Outils Cheddar est d velopp en GtkAda qui est le binding Ada de Gtk Gtk est un toolkit graphique qui a t initialement crit pour The Gimp un logiciel de dessin fonctionnant sous GNU Linux 2 2 1 Le Langage Ada95 Ada est un langage qui ressemble a priori du Pascal et c est normal puisqu il a t cr en se basant sur celui ci Le langage fut baptis Ada en l honneur de Lady Ada Lovelace qui fut la fille de Lord Byron Le langage est caract ris par son typage fort son traitement de4s exceptions un abstraction des donn es une interface avec des programmes crits dans d autres langages De plus il ne respecte pas la casse diff renciation minuscules majuscules
47. fer est un objet identifi par son nom Il est localis sur un processeur a une taille pr d finie et un ensemble de Roles Le Type Buffer_Rules_Table est en fait un tableau d objets de type Buffer Rule type Rule is Norule Producer Consumer type Buffer_Rule is record The_Rule Rule Size Natural end record Page 61 sur 71 3 2 PR C DENCES CHAPITRE 3 LA TACHE R ALIS E L ajout de Tampon L utilisateur peut ajouter des tampons au syst me uniquement apr s avoir d fini un processeur et une t che Un buffer est reli un processeur a une taille et un identifiant son nom Un buffer peut contenir plusieurs Roles Chaque r le est associ une t che a une taille et est de type Producteur ou Consommateur Cette fen tre est bas sur l IHM d ajout de ressource figure3 9 Ainsi une certaine ho mog n it est assur e entre les deux types d objets Buffer Infornations Give buffer nane b1 On Cpu Rule task Size tl J n ee Producer Cancel FIG 3 21 Ajout d un tampon Cette fen tre contient un certain nombre de menus g n r s gr ce aux informations t ches processeurs de Cheddar Pour la gestion de ces donn es le widget Gtk_Option Menu a t pr f r pour son aspect graphique et sa programmation facile La mise jour de Tampon s Initialement la mise jour d un tampon se fait en le supprimant et un autre tampon ayant les m
48. g r via des IHM sp cifiques La construction des IHM T che Message et Tampons est d taill e par la suite Modification de l IHM tache Raisons Une IHM pour les taches tait d j pr sente dans cheddar cependant tant donn que l iden tifiant d une tache est son nom l impl mentation des d pendences a rendu le proc d existant ob sol te Dans l ancienne version de l update pour mettre jour une tache toutes les taches taient effac es puis reconstruites avec leurs nouveaux param tres Une proc dure Update Task a donc t cr e dans le package task_set de fa on a rendre l update compatible avec l impl mentation de d pendances cette proc dure modifie directement les champs de la tache a mettre jour dans sys tasks le set des taches du syst me L IHM de mise jour a donc du tre aussi modifi pour la rendre compatible au nouveau type d update et plus fonctionnelle Page 56 sur 71 CHAPITRE 3 LA TACHE R ALIS E 3 2 PR C DENCES Modifications Pour l impl mentation des d pendences la proc dure Update_Task a donc t ajout e son pro totype est le suivant procedure Update _ Task My_Tasks in out Tasks_ Set Name in Unbounded_String New_Name in Unbounded_String Location in Unbounded_String Start_Time in Natural Capacity in Natural Period in Natural Deadline in Natural Jitter in Natural Blocking_Time in Natural Priority in Priorit
49. hier historique Les fichiers historiques sont conserv s dans des repositories Chaque fois qu un utilisateur souhaite travailler sur un fichier ou un ensemble de fichier il demande CVS de produire partir du contenu du repository ad quat une copie priv e des fichiers souhait s dans la version d sir e Cette op ration est appel e checkout dans la terminologie CVS C est sur cette copie personnelle appel e copie de travail que l utilisateur effectue ses modifications tests etc Une fois satisfait de son travail l utilisateur demande CVS de mettre jour le repository en y incorporant les modifications qu il a r alis es sur sa copie de travail Cette op ration est appel e commit par CVS L utilisateur peut ensuite continuer travailler avec sa copie personnelle et demander CVS d incorporer ses modifications au repository chaque fois qu il le souhaite Une fois son travail termin si un utilisateur ne souhaite pas conserver sa copie de travail il peut l effacer et signaler CVS qu il ne poss de plus de copie personnelle gr ce un release Il pourra de toute fa on tout moment recr er une copie de travail partir du repository Dans le cas le plus g n ral plusieurs utilisateurs peuvent poss der une copie de travail des m me fichiers et faire chacun des modifications qui leur sont propres Pour le premier qui demandera CVS d int grer ses modifications dans le repository tout se passera co
50. isie c est produite il faudra remodifier la valeur du champs ou c est produit l erreur Le bouton OK valide les changements il est alors impossible de modifier les changements fait auparavant Page 46 sur 71 CHAPITRE 3 LA TACHE R ALIS E 3 2 PR C DENCES 3 2 Les contraintes de pr c dence 3 2 1 Le Canvas Le canvas est une vue de Cheddar qui n affiche que les syst mes d objets poss dant des pr c dences Tout autre syst me est cach dans cette vue Elle sert repr senter les objets cr s dans Cheddar de mani re graphique Le but initial de cette fen tre est de proposer une repr sentation sous la forme d un graphe compos d entit s et d arcs pour les relier De plus le graphe ne doit pas tre coercitif pas de circuit La fen tre doit aussi tre pourvue d une barre d outils comprenant des boutons qui donnent acc s aux fonctionnalit s du canvas La Barre d outils Choix des objets Plusieurs choix d objets et de disposition se pr sentent pour la barre d outils En effet tant donn le nombre d objets disponibles il existe plusieurs combinaisons pour chacun des champs n cessaires et un choix est donc obligatoire en fonction des contraintes requises et des fonctionnalit s de chaque objet Les diff rents objets de Gtk existant et compatibles avec les besoins de l interface sont combo box option menu buttons radio buttons check box pixmap entry toggle buttons clist Pendant la c
51. l de suivi de version I permet de conserver trace de l historique des modifications d un fichier ou d un ensemble de fichiers et de revenir simplement n importe quel tat ant rieur Pour garder cet historique il serait bien sur possible de conserver chaque version de chaque fichier que vous cr ez ou manipulez Cela prendrait videmment une place disque consid rable L int r t d utiliser un outil comme CVS est d abord qu il stocke seulement les diff rences entre deux versions successives r alisant ainsi un gain de place appr ciable Ensuite CVS enregistre automatiquement la date l auteur et un ventuel commentaire explicatif pour chaque modification Un autre avantage de CVS est qu il facilite le travail en groupe En effet travailler plusieurs dans un m me r pertoire demande une organisation sans faille et une attention de tous les instants afin de ne pas craser les modifications faites par un autre membre du groupe CVS permet chacun de travailler dans son propre r pertoire m me ventuellement sur sa propre machine et prend en charge l int gration du travail des diff rents membres du groupe Notons galement que CVS est un logiciel libre diffus sous licence GPL Il fonctionne sur une grande vari t de machines et de syst mes d exploitation Linux Solaris BSD MacOS MS Windows etc Principe de CVS CVS stocke tout l historique des volutions d un fichier sous forme compacte dans un fic
52. l utilisateur de placer des objets de les bouger avec la souris Les items peuvent tre connect s entre eux et les connections restent actives m me si les items sont boug s Ce widget supporte aussi les barres de d filement Gtk_Scrolled Window qui apparaissent quand le dessin d passe les dimensions de la fen tre H las certaines m thodes ou fonctions manquent dans ce widget la liste des items le nom d un item la recherche par nom l item s lectionn pour tra age de fl ches ult rieur le type des items taches messages tampons Le code source du widget Canvas a donc t repris sous le nom de my_canvas et les fonction nalit s manquantes ont t rajout es Fonctionnement g n ral du canvas La vue graphes peut fonctionner en parall le avec Cheddar c est dire que l on peut cr er des t ches dans Cheddar et l instant d apr s les afficher dans le canvas Cr ation d objets tree gt gt gt QQ SOV 4 v Arrow task v Message Buffer Choose the iten FIG 3 11 Le Canvas Quand l utilisateur d sire cr er un message il passe en mode cr ation il s lectionne le type d item qu il veut cr er dans la barre d outils et il clique quelque part sur le canvas ce moment une fen tre popup apparait et propose l utilisateur de Page 48 sur 71 CHAPITRE 3 LA TACHE R ALIS E 3 2 PR C DENCES cr er un nouveau message Dans ce cas la fen tre de cr ation de me
53. l_Resources Task_Name A_ Task_Set A Resource _Set Resources_Critical Res e Task_Name Le nom de la tache pour laquelle l algorithme PIP se d roule e A_Task_Set L ensemble des taches su syst me e _ Resource Set L ensemble des ressources du syst me e Resources_Critical La somme des section critiques calcul e pour les ressources e Resources_N Le nombre de ressources pouvant bloquer la tache Task_Name Cette fonction retourne Resources_Critical et Resources_N Elle permet de conna tre la somme des section critique des ressource pour une tache Task Name et le nombre de ressource pouvant la bloquer Elle correspond a l tape deux vue pr c demment Ces deux fonctions sont ensuite utilis es dans la fonctions suivantes 1 function Blocking_Time Task_Name in Unbounded_ String 2 A_Task_Set in Tasks_Set 3 A_Resource_Set in Resources_Set 4 return Natural is e Task_Name Le nom de la tache pour laquelle les deux algorithmes pr c dent seront ex cutes e A_Task_Set L ensemble des taches du syst me e Resource Set L ensemble de ressources du syst me e retourne Le temps de blocage de la tache Task_Name 1 procedure Make_Table Object_Name in Unbounded_String 2 Max in Natural 3 N in out Natural 4 Table in out Temp _ Table is Object _Name Nom de l objet a stocker Page 38 sur 71 CHAPITRE 3 LA TACHE R ALIS E 3 1 LES RESSOURCES PARTAG ES e Max Valeu
54. le 14 Exemple de l algorithme RM 14 capture de Cheddar 16 Organisation hi rarchique de Gtk 18 illustration du manque de dialogue 24 L objet ressource eases ar gene ee eR RT ns net 32 Inversion de priorit 41 24 ee o ad AAA 33 Ordonnancement sans PIP 34 Ordonnancement avec PIP 35 Inter blocage avec PIP 35 Temps de blocage avec PIP 37 Application de PCP 3 424 6 8ahe be he bea ed ad ee ee 40 Temps de blocage avec PCP 41 Interface d ajout d une ressource 43 Interface de modification d une ressource 44 Le Canvas da ue ideas ont eee Oe Se OR np enh Se ee da da 48 types de d pendance 50 repr sentation dans la matrice 51 types de semi _d pendence 52 exemple cheddar cx iia eee dee A E de Page de au de ue des 54 Suppression de bli We dre a Pe eo A oe a A A en aA a ti 55 Comparaison entre l ancienne et la nouvelle IHM Tache 58 Repr sentation dans le canvas 59 interface de cr ation d un message
55. mme s il tait seul Mais lorsque le deuxi me utilisateur incorporera ses modifications dans le repository CVS se rendra compte que ces modifications ont t port es sur une version plus ancienne que la version disponible dans le repository et combinera ces modifications celles effectu es par le premier utilisateur Il en profitera galement pour mettre jour la copie de travail du deuxi me utilisateur Il est possible cependant que CVS ne sache pas comment combiner deux ensembles de modi fications successives par exemple si le deuxi me utilisateur a modifi une ligne supprim e par le premier Dans ce cas il indique au deuxi me utilisateur les fichiers en conflit et lui laisse le soin de r soudre manuellement le probl me Page 23 sur 71 2 2 OUTILS CHAPITRE 2 LE PROJET CHEDDAR Tom Jerry ficher toto fichier toto Modifications Modifications CVS commit CVS commit CO Tom a eu de la chance ces jerry devra mettre ajour son fichier modifications sont prises en compte avant d enregistrer ses modifications avant celles de Jerry J FIG 2 6 illustration du manque de dialogue Il est noter que le premier utilisateur n est pas inform automatiquement des modifications apport es par le deuxi me sur les fichiers sur lequel il travaille S il ne fait rien de particulier il n en aura Connaissance que lors de son prochain commit Tout utilisateur poss dant une copie de travail
56. mpos es en deux parties une partie ne contenant que le code de la fen tre et des appels aux fonctions du second fichier qui contient les actions associ es aux boutons ou widgets nomfichier adb fichier1 Button_Callback Connect Update_Resources_Set Button_Add clicked Button_Callback To_Marshaller On_0k_Pressed access nomfichier callback adb fichier2 procedure On_Ok_Pressed Object access Gtk_Button_Record Class General Resource nane Resource State Integer Use Protocol On Cpu Affect Task nane Begin End Cancel FIG 3 9 Interface d ajout d une ressource L interface figure 3 9 d ajout des ressources est d une conception assez classique Elle est compos e de Widget Gentry pour les saisies au clavier Une Combo_Box pour lister les protocoles pouvant tre associ s la ressource un Option_Menu pour la liste des processeurs existants et Interface Homme Machine Page 43 sur 71 3 1 LES RESSOURCES PARTAG ES CHAPITRE 3 LA TACHE R ALIS E une CList pour afficher les t ches qui ont t associ es avec la ressource Dans cette interface 1 Option Menu aurait put tre remplac par une Combo_Box ou inversement Cependant bien que ces widgets semble r aliser les m mes fonctions il est impossible dans une Combo_Box de s lectionner un l ment par d faut afficher alors que d apr s la documentation GtkAda il est possible de le faire pour l Option Menu
57. n e T Jo lib re la ressource Ro Jo pr empte J et entre en section critique en prenant la ressource La dur e du blocage du a l inversion de priorit est gale a T5 To elle peut tre beaucoup plus importante que la dur e de la section critique de Jo car cette tache peut tre pr empt e par d autres taches de priorit sup rieure e T6 Jo lib r Ro Avec PIP ona e To Ja est activ e peut prendre Ro et entre en section critique e T Jo pr empte Ja et commence son ex cution e To Jo ne peut prendre R car la ressource n est pas libre Jo reprend son ex cution avec la priorit de Jo e T3 J est activ e mais sa priorit est d sormais inf rieure a celle de J qui continue son ex cution On voit ici que PIP introduit un nouveau type de blocage le blocage d h ritage de priorit e TA J2 Libere la ressource reprend sa priorit initiale et est pr empt e par Jo Jo peut prendre la ressource et rentre en section critique e T Jo termine son ex cution en lib rant la ressource Ro J peut commencer son ex cution Page 34 sur 71 CHAPITRE 3 LA TACHE R ALIS E 3 1 LES RESSOURCES PARTAG ES Ex cution normale Section critique FIG 3 4 Ordonnancement avec PIP PIP n emp che pas les situations d inter blocage qui peuvent survenir lorsqu il y a plusieurs ressources partag es Prenons une tache Jo qui attend une ressource
58. nces Sociales Droit conomie et gestion M decine Odontologie Sciences et Techniques Sport et ducation Physique Mais egalement d institut d enseignement et d ecoles Euro Institut d Actuariat EURIA l Institut d Administration des Entreprises IAE IUP Ing nierie Informatique l IUT de Brest et de Quimper d instituts de recherche et de services communs biblioth ques universitaires FIG 1 1 Organigramme de PUBO L UBO acceuille environ 18000 etudiants sur 3 sites differents Brest Morlaix Quimper elle reunie egalement 840 enseignants et chercheurs repartis en une cinquantaines de groupes de 9 1 2 LE D PARTEMENT INFORMATIQUE CHAPITRE 1 UBO recherche 1 2 Le d partement Informatique 1 2 1 L UFR sciences et techniques UFR Sciences et Techniques propose un large ventail de formations et de cursus complets allant du DEUG jusqu au DESS au DEA et au Doctorat Outre le choix entre de nombreuses disciplines Biologie Chimie Electronique G ologie Informatique Math matiques Physique Urbanisme chaque tudiant peut adapter son parcours et s orienter tout au long de sa formation Gage de qualit la plupart de ces formations s appuient sur des laboratoires de recherche de haut niveau reconnus tant sur le plan national qu international Ces formations sont une alternative aux pr parations aux grandes coles Un nombre croissant d tudiants passent en effet par l UFR Sciences avant
59. ncontrer de nombreux problemes que nous avons pu r soudre par une recherche personnel de documentation la plupart du temps et a l aide de Mr Singhoff autrement Quelques am liorations sont encore a aporter a cheddar mais par manque de temps nous n avons pas pu les r aliser 67 3 3 MANUEL D UTILISATION CHAPITRE 3 LA TACHE R ALIS E Page 68 sur 71 Annexe A Arbres de test A 1 Op ration sur les t ches Voici l arbre de test des op rations sur les t ches Il r pertorie tous les tests de fonctionnement effectu s et leur r sultats Les tests de suppression de t ches ont montr s que les d pendences de celle ci sont bien supprim es Il appara t quelque fois un bug sur update de p riode et Jitter mais sa cause reste inexpliqu Il semblerais que cela soit du une certaine utilisation de cheddar mais celle ci n as pas pu tre pr cis e Create task Name Processor Capacity Jitter Deadline Period Update Start time Priority Offsets act Offsets val Delete Se Task dependencies FIG A 1 Arbre de test des t ches 69 A 1 OP RATION SUR LES T CHES A 1 1 Validit des param tres ANNEXE A ARBRES DE TEST Voici l arbre de test de validit des param tres Il r pertorie tous les tests de fonctionnement effectu s et leur r sultats Le contr le de non n gativit est Ok
60. nsable et un responsable adjoint La dur e des divers mandats est de deux ans Le responsable actuel est Lionel Marc L Equipe p dagogique e 2 professeurs 16 ma tres de conf rences Un assistant Un PAST Un MCF associ 1 professeur agr g 1 attach temporaires d enseignement et de recherche Ces titulaires sont assist s par de nombreux vacataires notamment pour le monitorat en premier cycle et e Le tutorat 1 3 Le Laboratoire LIMI L EA 2215 unit INFORMATIQUE a t cr e il y a 8 ans l Universit de Bretagne Occiden tale Elle regroupe principalement les 25 enseignants chercheurs en informatique 27 me enseignant dans le d partement d informatique de l UFR Sciences et l IUP d ing nierie informatique et la dizaine d enseignants en informatique et g nie informatique 27 me et 61 me enseignant VENIB auxquels se rajoutent quelques enseignants dispers s sur l Universit en particulier l IUT L unit est dirig e par le Prof L Marc assist d un conseil d unit comprenant les MCF suivants M P Le Parc Melle S Gire M D Sarni M B Pottier M V Ribaud M V Rodin M J Tisseau L unit comprend 4 quipes e Architecture et Syst me A amp S anim e par B Pottier comprenant deux th matiques ap pliqu es en e g nie logiciel et en architecture de machines e Informatique Fondamentale In Fo anim e par D Sarni Ce projet comprend des th oriciens e Langages et Interfa
61. onstruction de cette toolbar diverses combinaisons ont t essay es pour arriver la solution de deux toolbars plac es l une sous l autre dans une Vbox La premi re toolbar est compos e d une combo box qui permet de choisir le mode d utilisation du canvas les modes pr sents sont cr ation s lection et suppression d item Viennent ensuite les fonctions de zoom respectivement zoom out et zoom in puis les diff rentes dispositions droit cercle et flux L icone suivante permet de fermer le canvas La seconde toolbar est compos e de radio buttons qui permettent de choisir l objet sur lequel va agir le mode s lectionn Ces radio buttons repr sentent respectivement les objets d pendance tache message et buffer Raisons de ces choix L affichage s lectionn pour le mode a donc t la combo box car elle offre une meilleure lisibilit pour l utilisateur et poss de les caract ristiques n cessaires ce champ Le choix des radio buttons s explique par le fait que cela hi rarchise les disponibilit s pour chaque mode L utilisation de pixmap pour les autres objets vient de la volont d homog n it avec les autres fen tres de Cheddar Page 47 sur 71 3 2 PR C DENCES CHAPITRE 3 LA TACHE R ALIS E La zone de dessin Afin de mettre en oeuvre la zone de dessin un widget de GtkAda a t tr s utilis le canvas widget GtkAdA Canvas Ce widget propose un ensemble de fonctions de haut niveau permettant
62. premi re section critique rencontr e est sur R3 et R3 gt Po La tache de plus haute priorit acc dant a R3 est T de priorit P gt Pa La seconde section critique rencontr e est sur la ressource Ra et R2 gt Po La tache de plus haute priorit acc dant a Ro est T2 or Pa Po il y a donc deux sections critiques a consid rer de 1 et 4 unit s de temps Pour T Pa gt P2 To est plus prioritaire que T1 La seule section critique rencontr e est sur Rs et encore une fois R3 gt P2 Il y a donc une section critique a consid rer de 3 unit de temps Une fois toutes les section critiques trouv es la plus grande valeur est conserv e ici le temps de blocage de To est de 4 unit s de temps Les algorithmes ADA 1 function Pi_Rk Resource_Name in Unbounded_String 2 A_Resource_Set in Resources Set 3 A_Task_Set in Tasks_Set 4 return Priority_ Range is e Resource _Name Nom de la ressource pour laquelle calculer le R e Resource Set Ensemble des ressources du syst me e A_Task_Set Ensemble des taches du syst me e retourne Rz Cette fonction permet de calculer le R d une ressource k de nom Resource name comme vu pr c demment Page 41 sur 71 3 1 LES RESSOURCES PARTAG ES CHAPITRE 3 LA TACHE R ALIS E 1 function Blocking_Time Task_Name in Unbounded_ String 2 A_Task_Set in Tasks_Set 3 A_Resource_Set in Resources_Set 4 return Natural is
63. r correspondante a l objet a stocker e N Nombre d l ments dans le tableau ou sont stock les objets e Table La table dans laquelle sont stock les objets Cette procedure permet de stocker dans un tableau Table des objets de nom Object_Name et leur valeur associ es Max N est mis jour chaque ajout d l ment dans la table Si Object_Name n existe pas lors de l appel de cette procedure il sera ajout dans la table avec sa valeur Max Si Object_Name existe la valeur Max est mise a jour si celle ci est inf rieure a la valeur Max pass e en param tre Ce syst me permet de stocker n importe quel type d objet ayant une valeur associ e Pour permettre ceci une structure Temp_table a t d finie Celle ci est un tableau de structure de Max_Tasks l ments PCP Priority Ceiling Protocol Principe D finis par Sha Rajkumar et Lehoczky en 1987 PCP est une am lioration de PIP permettant d viter les situations d interblocage ainsi que les cha nes de blocage Le support d ordonnancement est RM L id e de base de PCP est d tendre PIP avec des r gles pour prendre les s maphores ces r gles interdisant une tache d entrer en section critique s il y a des s maphores bloqu s susceptibles de bloquer cette tache Ce protocole suppose que chaque tache poss de une priorit fixe et que les ressources utilis es sont connues avant le d but de l ex cution Ce protocole est une protocol a plafond de priorit
64. rce_pkg callback adb if Protocol Protocol_Resource or A_Resource State State or Get_Active Update_Resources_Set Check_Change_CPU True then if Get_Active Update_Resources_Set Check_Change_CPU True then Changement de processeur la ressource CPU To_Unbounded_String Get_Text Get_Entry Update_Resources_Set Change_CPU_List Set_Active Update_Resources_Set Check_Change_CPU False hide Update_Resources_Set Change_CPU_List Update_Resource_CPU Sys Resources Update_Resources_Set Last_Resource_Selected CPU Protocol State else Changements des param tres if Update_Resources_Set Last_CPU_Selected then if A_Resource location To_Unbounded_String Get_Text Get_Entry Update_Resources_Set CPU then CPU To_Unbounded_String Get_Text Get_Entry Update_Resources_Set CPU Update_Resource_CPU Sys Resources Update_Resources_Set Last_Resource_Selected CPU Protocol State else Update_Resource_CPU Sys Resources Update_Resources_Set Last_Resource_Selected A_Resource location Protocol State end if end if end if end if Un m canisme d annulation t mis en place avant l ouverture de la fen tre l objet ressource est sauvegard si l utilisateur veut annuler les modifications effectu es l objet ressource est res taur cette m thode ne permet pas de faire des annulations sur une partie des changements elle permet juste de revenir un tat initial si une erreur de sa
65. s que les types tagg s les packages g n riques l acc s aux sous programmes les exceptions Pour des raisons d efficacit il n utilise pas les types contr l s mais s occupe efficacement de la gestion de la m moire Son fonctionnement tant similaire celui de son homologue en C seules les principales diff rences avec ce dernier seront d taill es Conventions de nommage Le binding GtkAda est organis en packages En C pour changer le texte d un label on ap pelle directement gtk_label_set_ text En Ada il faut appeler la fonction Set_text du package Gtk Gtk Label Les fonctions de rappel Ces fonctions ne sont pas des callbacks comme en Gtk C mais des handlers Il faut de plus utiliser des Marshallers qui sont des interm diaires entre le signal et sa fonction de rappel Malgr le fait que certains marshallers soient d finis il faut quand m me en d finir pour chaque widget que l on utilise Ceux ci font partie int grante des handlers Voici un exemple Page 21 sur 71 2 2 OUTILS CHAPITRE 2 LE PROJET CHEDDAR 1 with Glib use Glib 2 with Gtk 3 with Gtk handlers a with Gtk Main 5 with Gtk Widget use Gtk Widget 6 with Gtk Window use Gtk window 8 function Delete_Event_Handler Window gtk_Window return Gint is 9 begin 10 Code execute a la destruction de la fenetre 1 end Delete_Event_Handler 13 procedure Test is 14 package Window_Cb is new Gtk Handlers Callba
66. sion de t2 La t che t2 est supprim e Elle n est en fait pas supprim e au premier sens du terme elle est simplement cach e En effet une suppression dans le canvas quivaut a supprimer toutes les d pendences et semi_d pendences Le canvas tant une vue d un syst me poss dant des d pendences la t che t2 n a plus de raison d tre visible Elle est donc rendue non visible Les messages m1 et m2 n ont plus de d pendences et pourraient tre cach s leur tour Cependant ces messages pouvant servir ult rieurement avec d autre t che ils restent visibles L utilisateur peut aussi supprimer messages et buffers de la m me fa on Les d pendences et semi_d pendances li es a ces items seront alors supprim es Page 55 sur 71 3 2 PR C DENCES CHAPITRE 3 LA TACHE R ALIS E 3 2 3 THM Taches Messages Tampons Les objets Cheddar sont stock s dans des sets Ada Ces sets sont regroup s dans un record type System is tagged record Network Network_Ptr Tasks Tasks_ Set Resources Resources _set Messages Messages Set Dependencies Tasks_Dependencies Half _Dependencies Half_Depends_Set Processors Processors_Set Buffs Buffers_Set end record Une variable globale de type System est utilis e partout dans Cheddar elle s appelle sys Il y a un set par type d entit s Ainsi par exemple les taches sont stock es dans sys tasks Le contenu de chacun de ces sets est
67. ssage appara t l utilisateur renseigne les caract ristiques du message valide en appuyant sur Ok et l item est affich sur le canvas d importer un message de Cheddar Ainsi l item est simplement affich sur le canvas Afin de diff rencier les items sur le canvas leur nom est affich proximit de chacun L utilisa teur peut zoomer loisir sur le canvas De plus 3 types de disposition ont t mis en place H las les algorithmes utilis s pour ces positionnements sont revoir car il ne prennent pas en compte les d pendances et les contraintes de pr c dence Relations entre items Les items peuvent tre reli s entre eux via des fl ches qui sont en fait des courbes de Bezier Ceci permet au canvas de g rer les liens multiples entre items Ainsi quand plusieurs liens sont cr s entre deux items les fl ches ne sont pas superpos es les unes sur les autres mais tal es en courbes Suppression d objets Aucun item n est r ellement supprim du canvas mais cach Cela a plusieurs avantages am lioration des performances g n rales conservation de la coh rence des donn es avec les objets du syst me Cheddar En effet l utilit premi re du canvas est d afficher et ou de cr er des objets Cheddar mais pas de les supprimer Les items ainsi cach s peuvent tre r affich s par le biais de la proc dure de cr ation d items Quand un item est ainsi cach les liens partant et venant de lui
68. t de ses applications en fournissant au d veloppeur un acc s transparent certaines donn es selon le syst me d exploitation utilis par exemple g get home dir retourne le r pertoire Home de l utilisateur sous Linux et fournit un quivalent sous Windows Gmodule est une composante de la Glib qui permet de charger dynamiquement des greffons plugins Elle facilite le D buggage avec une gestion des exceptions sous forme de macro commandes Gdk Gdk est la couche interm diaire de Gtk Son r le est d encapsuler les primitives de dessin du syst me Xlib ou Win32 dans le cadre d une application n utilisant pas Gtk soit pour permettre Gtk de dessiner ses composants Gdk affranchit le d veloppeur de PAPI Xlib et optimise ses acc s en lib rant automatiquement les ressources allou es par le serveur X pixmaps par exemple Gimp Drawing Kit S Application Programming Interface Page 19 sur 71 2 2 OUTILS CHAPITRE 2 LE PROJET CHEDDAR Gtk C est la composante que beaucoup de monde tend assimiler Gtk sachant que la seule diff rence dans leur nom est le Gtk est la partie visible de l iceberg car c est le toolkit lui m me Il poss de bon nombre de composants graphiques les widgets qui suffisent une application standard Il existe plusieurs librairies aui en fournissent d autres et il est de m me tr s facile de concevoir ses propres widgets Gtk est essentiellement une API orient e
69. t sys buffers est modifi en cons quence Le canvas est aussi mis jour Ainsi la coh rence des donn es est conserv e Page 63 sur 71 3 3 MANUEL D UTILISATION CHAPITRE 3 LA TACHE R ALIS E 3 3 Manuel d utilisation 3 3 1 blah 3 3 2 Le canvas Pour ouvrir le canvas cliquez sur l icone FIG 3 23 ic ne du canvas la fen tre canvas est alors ouverte Si le projet 3 3 3 IHM Ressource Ajout d une ressource On appel la fonction d ajout de ressource via le menu Edit Add Add Resource General Resource nane Resource State Integer Use Protocol On Cpu Affect Task nane Begin End ta f affect task BeginfEnd t1 0 8 Cancel FIG 3 24 Interface de modification d une ressource Pr requis la cr ation d une ressource e Un processeur doit exister e Une t che doit exister Le nom de la ressource doit tre ensuite sp cifier ainsi que son tat initial on doit ensuite sp cifier le protocole partage de ressource PCP PIP No protocol et le processeur sur lequel Priority Ceiling Protocol Priority Inh rence Protocol Page 64 sur 71 CHAPITRE 3 LA TACHE R ALIS E 3 3 MANUEL D UTILISATION sera attach la ressource On peut aussi lui attacher des t ches il faut alors s lectionner la t che que l on veut parmi celle qui sont cr es et de sp cifier le d but et la fin de son acc s la ressource Et
70. t3 s lectionn e Ses param tres sont affich s dans les champs du cadre de gauche et chacun d entre eux peut tre mis jour par dition du champs correspondant a part le champs blocking time qui ne d pend que du protocole choisi pour la ressource laquelle la t che est affect e si c est le cas et est gal z ro sinon Lors d une mise jour du nom d une t che ou de plusieurs de ses champs sys tasks est mis jour avec les nouveaux param tres de la t che identifi e gauche La liste de droite est ensuite mise jour par rapport sys tasks Le canvas est directement mis jour apr s une modification et les noms de tache s modifi e s s il y a eu mise jour IHM message Un message est un type de d pendance servant de communication entre diff rentes t ches en plus de la fin de la t che pr c dente cela permet d ajouter une contrainte d attente d un message sp cifique L IHM pour les messages n existait pas la cr ation d interface cr ation mise jour et suppression a donc t impl ment e pour sys messages le set des messages du systeme Page 58 sur 71 CHAPITRE 3 LA TACHE R ALIS E 3 2 PR C DENCES free 1QQ SON 4 v Arrou task v Message Buffer FIG 3 18 Repr sentation dans le canvas Ajout d un message L interface ci dessous est la cr ation d un message Hane Jitter Deadline Period Size Ok Cancel FIG 3 19 interface de cr ation d un
71. te des algorithmes d ordonnancement optimaux 13 2 1 OBJECTIFS CHAPITRE 2 LE PROJET CHEDDAR T1 C1 8 P1 10 ST1 0 T2 C2 6 P2 2 S T2 2 T1 C1 8 P1 10 ST1 0 T2 C2 6 P2 2 ST2 2 FIG 2 2 t ches non pr emptible pour les syst mes de t ches ind pendantes mais un syst mes temps r el doit pouvoir acc der des ressources qui doivent tre partag es ce qui peut entra ner des probl mes dans le cas d un syst me avec des t ches pr emptive qui induisent que les r sultats d optimalit ne sont plus valide d autres algorithmes sont donc n cessaire et sont pr sent s dans la partie 3 Les ordonnancements priorit s dynamique se rapproche d un syst me temps partag s comme par exemple Unix ainsi les t ches ont leur priorit s modifi s lors de l ex cution de cette fa on une t che peu de chance de se retrouver bloqu es Pr sentation des algorithmes priorit fixe L algorithme Rate Monotonic RM L algorithme Rate Monotonic s applique aux taches p riodiques seulement les priorit s sont fix s au d part en la mettant gale l inverse de la p riodicit la plus forte priorit est lue Pr emption de T1 TI T2 Pi 10 5 EH HH Cil 4 2 0 2 5 7 9 10 Em Tache T1 Tache T2 El Inutilis FIG 2 3 Exemple de l algorithme RM Dans l exemple de la figure 2 3 la t che T2 est plus prioritaire car sa p riode est plus petite que la
72. tte m thode dans le cas du chargement d un buffer ayant plusieurs destinataire et plu sieurs sources l exceptionEXIST_ALREADY peut se lever Le probl me peut tre r gl en modifiant la m thode read_from_file du fichier task_dependencies adb chaque ajout d une semi_d pendences il faut g rer les exceptions car sinon ce type de projet ne peut tre charg e Un doute subsiste L exception n aie jamais apparue lors de nos test Ce cas est donc tester plus pr cis ment Page 53 sur 71 3 2 PR C DENCES CHAPITRE 3 LA TACHE R ALIS E Illustration par un exemple Create A Q E O F IS Arrow w task wv Message v Buf f er Qa lt Cr T E le DE Fic 3 15 exemple cheddar Cet exemple comporte plusieurs cas de figure illustrant les d pendences et semi_d pendences La t che t4 ne poss de qu une semi_d pendence vers le tampon b1 Cette t che n a donc pas de d pendence enregistr e Cependant si le canvas est recharg pour une raison quelconque cette t che restera apparente La t che t1 poss de une pr c dence avec la t che t2 cette d pendence n est pas enregistr e comme semi_d pendence Les buffers b2 et b3 ont une semi_d pendence avec t1 Ces semi_d pendences sont maintenues dans le set halph_depends Ce set fait parti de la structure syst me Page 54 sur 71 CHAPITRE 3 LA TACHE R ALIS E 3 2 PR C DENCES Tree 1QQ ION 4 wv Arrow task Message y Buffer FIG 3 16 Suppres
73. y_Range Offset E Offset_Table L ancienne version tait faite de Gtk_entry chaque ligne repr sentant une tache et chaque colonne un param tre de cette tache Sur cette version sys tasks tait vid puis r initialis avec les donn es de chaque ligne Cette r initialisation supprimait les liens des taches vers leurs d pendances Pour viter cela la nouvelle version modifie les param tres existant de la tache modifi au lieu de les supprimer puis les recr er Dans la nouvelle version les taches existantes apparaissent dans une clist avec leurs param tres En cliquant sur une tache de la liste ses param tres remplissent les champs a gauche et il est donc ensuite possible de modifier ceux ci Les modifications ne sont prises en compte que lorsque l on appuie sur le bouton modify Cette action remplace tous les champs de la tache qui est identifi e par son nom par les valeurs des champs de gauche de l interface Page 57 sur 71 3 2 PR C DENCES CHAPITRE 3 LA TACHE R ALIS E Ci dessous la capture d cran de l interface Canvas avant modification Deadline Jitter Priority ef fe fa A e C EXA CA E fs _ e sf Nane Processor Capacity Jitter Deadline Period Start tine Priority Blocking Tine Offsets Activations jl Ok Cancel Modify FIG 3 17 Comparaison entre l ancienne et la nouvelle IHM Tache Dans cet exemple quatre t ches ont t cr es et la tache

Download Pdf Manuals

Related Search

Related Contents

STIMULOPT User Manual    

Copyright © All rights reserved. Failed to retrieve file