La lecture à portée de main
198
pages
Français
Documents
Écrit par
Damien Masson
Publié par
Thesee
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
198
pages
Français
Ebook
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Num´ero
2009–005
`THESE
En vue d’obtenir le grade de
´DOCTEUR DE L’UNIVERSITE PARIS-EST
Int´egration des ´ev´enements non p´eriodiques dans les
syst`emes temps r´eel – Application `a la gestion des
´ev´enements dans la sp´ecification temps r´eel pour Java
sous la direction de Gille Roussel et Serge Midonnet
Sp´ecialit´e Informatique
´Ecole doctorale Information, Communication, Mod´elisation et Simulation
Soutenue publiquement par Damien Masson
le 8 d´ecembre 2008
JURY :
MarylineChetto Universit´e de Nantes (rapporteur)
LaurentGeorge Universit´e Paris-Est
SergeMidonnet Universit´e Paris-Est
PascaleMinet INRIA Rocquencourt (rapporteur)
NicolasNavet INRIA Nancy – Grand Est
MarcRichard-Foy AONIX
GillesRoussel Universit´e Paris-Est
tel-00468692, version 1 - 31 Mar 2010ACe document a ´et´e ´edit´e avec LT X.E
tel-00468692, version 1 - 31 Mar 2010Aux lecteurs...
tel-00468692, version 1 - 31 Mar 2010iv
tel-00468692, version 1 - 31 Mar 2010Merci
Je tiens ici `a remercier en premier lieu SergeMidonnet, qui m’a ouvert les portes du
temps r´eel. C’est grˆace `a la confiance qu’il a su me t´emoigner d`es mon stage de DEA que
j’ai pu d´ecouvrir le monde de la recherche. Sans son enthousiasme, sa disponibilit´e et sa
patience, ce travail n’aurait pas ´et´e possible.
Mais les portes du temps r´eel se seraient bien vite referm´ees sans GillesRoussel qui
a accept´e de diriger cette th`ese; qu’il en soit donc ici remerci´e.
Je souhaite remercier chaleureusement Maryline Chetto et Pascale Minet d’avoir
rapport´e mon manuscrit. Le mois de d´ecembre ne voit pas seulement prolif´erer les p`eres
no¨el, c’est aussi la saison des soutenances de th`ese, et donc des sollicitations de cette
nature pour les chercheurs. Je les remercie par cons´equent de l’int´erˆet particulier qu’elles
ont port´e `a mes travaux de recherche en acceptant d’effectuer ce rapport et de participer
au jury de ma th`ese.
Que LaurentGeorge, NicolasNavet et MarcRichard-Foy se trouvent´egalement
remerci´es de l’int´erˆet qu’ils montrent pour ces travaux en acceptant´egalement de partici-
per `a ce jury.
Je souhaite remercier ´egalement l’ensemble des membres permanents et non perma-
nents du laboratoire d’informatique Gaspard-Monge que j’ai eu la chance de cˆotoyer ces
derni`eres ann´ees, pour savoir chaque jour transformer le quatri`eme ´etage du bˆatiment
Copernic en un endroit si particulier.
Je remercie particuli`erement PierrePeterlongo, LaurentBraud, PierreGuillon,
Fr´ed´eric Fauberteau et Florian padawan Sikora car ils ont successivement eu `a me
supporter dans leur bureau; Nicolas Bedon car il m’a offert ma premi`ere exp´erience
dans la recherche et d´ej`a sur Java; MarcZipstein mon tuteur enseignant sans qui l’IGM
connaˆıtrait une p´enurie de caf´e dont il ne se rel`everait pas; et puisqu’il est question de
caf´e Guillaume Blin avec qui ma balance commerciale dans ce domaine est certaine-
ment d´eficitaire. Avant de remercier ´egalement tous ceux que j’oublie, j’adresse un grand
`merci `a Line Fonfrede pour l’ensemble des services que cette ´eminence grise du labo-
ratoirerendchaquejour`atousleschercheursquilecomposent,ettoujoursaveclesourire.
Enfin je r´eserve ce dernier paragraphe `a ma famille qui a forc´ement sa part de m´erite
dans l’accomplissement des dix neuf ann´ees d’´etude que repr´esente ce manuscrit.
v
tel-00468692, version 1 - 31 Mar 2010vi REMERCIEMENTS
tel-00468692, version 1 - 31 Mar 2010R´esum´e
Lessyst`emestempsr´eelsontdessyst`emesinformatiquescompos´esdetˆachesauxquelles
sont associ´ees des contraintes temporelles, appel´ees ´ech´eances. Dans notre ´etude, nous
distinguons deux familles de tˆaches : les tˆaches temps r´eel dur et les tˆaches temps r´eel
souple. Les premi`eres poss`edent une ´ech´eance stricte, qu’elles doivent imp´erativement
respecter. Elles sont de nature p´eriodique, ou sporadique, et l’´etude analytique de leur
comportement fait l’objet d’un ´etat de l’art cons´equent. Les secondes sont de nature
ap´eriodique.Aucunehypoth`esesurleurmod`eled’arriv´eenisurleurnombren’estpossible.
Aucune garantie ne saurait ˆetre donn´ee sur leur comportement d`es lors que l’on ne peut
´ecarter les situations de surcharge, ou` la demande de calcul peut d´epasser les capacit´es
du syst`eme.
Laprobl´ematiquedevientalorsl’´etudedessolutionsd’ordonnancementmixtedetˆaches
p´eriodiques et ap´eriodiques qui minimisent les temps de r´eponse des tˆaches ap´eriodiques
toutengarantissantles´ech´eancesdestˆachesp´eriodiques.Denombreusessolutionsont´et´e
propos´ees ces vingt derni`eres ann´ees. On distingue les solutions bas´ees sur la r´eservation
de ressources, les serveurs de tˆaches, des solutions exploitant les instants d’inactivit´e du
syst`eme, comme les algorithmes de vol de temps creux.
La sp´ecification Java pour le temps r´eel (RTSJ) voit le jour dans les ann´ees 2000. Si
cette norme r´epond `a de nombreux probl`emes li´es `a la gestion de la m´emoireou `a l’ordon-
nancement des tˆaches p´eriodiques, celui de l’ordonnancement mixte de tˆaches p´eriodiques
et ap´eriodiques n’est pas abord´e.
Nous proposons dans cette th`ese d’apporter les modifications n´ecessaires aux algo-
rithmes principaux d’ordonnancement mixte, le Polling Server (PS), le Deferrable Server
(DS) et le Dynamic Approximate Slack Stealer (DASS) en vue de leur implantation avec
RTSJ. Ces algorithmes ne peuvent en effet ˆetre implant´es directement tels qu’ils sont d´e-
crits,carilssonttropli´es`al’ordonnanceurdusyst`eme.Nousproposonsdesextensionsaux
APIs RTSJ existantes pour faciliter l’implantation de ces m´ecanismes modifi´es, et nous
fournissons les interfaces utiles `a l’ajout d’autres solutions algorithmiques. Nous propo-
sons ´egalement des modifications sur les APIs existantes de RTSJ afin de r´epondre aux
probl`emesd’int´egrationetd’implantationd’algorithmesd’analysedefaisabilit´e.Nouspro-
posons enfin un algorithme d’estimation des temps creux, le Minimal Approximate Slack
Stealer (MASS), dont l’implantation au niveau utilisateur, permet son int´egration dans
RTSJ.
vii
tel-00468692, version 1 - 31 Mar 2010´ ´viii RESUME
tel-00468692, version 1 - 31 Mar 2010Abstract
In computer science, real-time systems are composed of tasks. To each task is asso-
ciated a timing constraint called a deadline. We distinguish two kinds of tasks : the hard
onesandthesoftones.Hardtaskshaveharddeadlines,whichmustberespectedtoensure
the correctness of the system. So hard tasks are in essence periodic, or sporadic. Their
behavior has been extensively studied. Soft tasks have soft deadlines that the system has
to try to respect. When a task arrivalmodel is unknown, i.e. when task is aperiodic,burst
arrivals situation can happens, which makes the tasks timing behavior unpredictable. So
aperiodic tasks can only have soft deadlines.
The studied problem in this thesis is then the joint scheduling of hard periodic tasks
with soft aperiodic events, where the response times of soft tasks have to be as low as
possible while the guarantee to meet their deadlines has to be given to hard tasks. A lot
of solutions have been proposed these past two decades. We distinguish solutions based
on resource reservation, like task servers, and solutions which take benefit from system
idle times, like the slack stealer techniques.
ThefirstversionoftheReal-TimeSpecificationforJava(RTSJ)wasproposedinearly
2000. This specification addresses a lot of problems related to the memory management
or the scheduling of periodic tasks. But if it proposes a model to write aperiodic events,
advanced mechanisms for the integration of such events to handle the above-mentioned
problem are not discussed.
We propose modifications to the main advanced mixed scheduling mechanisms like
the Polling Server (PS), the Deferrable Server (DS) or the Dynamic Approximate Slack
Stealer (DASS) in order to make their implementation possible with the RTSJ. Indeed,
these algorithms are deeply connected to the system scheduler, and have to be adapted in
ordertobeimplementedinauser-landlevel.WeproposeextensionstocurrentRTSJAPIs
inordertointegratethemodifiedalgorithmsandtoallowtheadditionofotheralgorithms
in a unified framework. We also propose some modifications to the RTSJ APIs in order
to solve some problems we encountered during the integration of modified algorithms,
especially in the field of the feasibility analysis algorithms integration in the specification.
Finally, we propose the Minimal Approximate Slack Stealer algorithm (MASS), which is
independent of the scheduler implementation and has a lower overhead than DASS.
ix
tel-00468692, version 1 - 31 Mar 2010x ABSTRACT
tel-00468692, version 1 - 31 Mar 2010