Optimisation de l'ordonnancement sous contrainte de faisabilité, Scheduling optimisation under feasibility constraint

Mathieu Grenier

Description

Sous la direction de Françoise Simonot-Lion, Nicolas Navet
Thèse soutenue le 26 octobre 2007: INPL
L’objectif que nous nous sommes fixés dans ce travail est la conception d’algorithmes d’ordonnancement temps réel en-ligne faisables optimisant l’utilisation de la plate-forme d’exécution et/ou des critères applicatifs de qualité de service propres à l’application. Nous avons en particulier étudié l’ordonnancement d’activités sur une ressource unique. Deux cas ont été analysés : le cas de tâches indépendantes périodiques s’exécutant sur un processeur et le cas de flux de messages indépendants périodiques sur un réseau de terrain avec accès au médium priorisé. Nos contributions reposent sur le “modèle classique” de l’ordonnancement temps réel où le système est représenté par un ensemble d’activités périodiques indépendantes et deux problématiques ont été abordées : • optimisation de l’utilisation de la plate-forme d’exécution : utiliser au mieux le potentiel de la plate-forme d’exécution tout en garantissant le respect des contraintes temporelles imposées au système ; ceci optimise le nombre de configurations faisables, • optimisation des critères applicatifs de qualité de service propres à l’application (i.e., pris en compte des performances de l’application autre que la faisabilité) : garantir les contraintes de temps tout en optimisant les performances de l’application. Nous avons donc proposé : • des méthodes de configurations permettant d’optimiser l’utilisation de la plate-forme d’exécution (i.e., maximiser faisabilité) en fixant les paramètres des politiques ou des systèmes considérés d’une manière appropriée. Deux études ont été conduites dans ce cadre : • allocation des “offsets” dans les systèmes “offset free”, • allocation de priorités, de politiques et de quantum dans les systèmes conformes au standard Posix 1003.1b, • une nouvelle classe de politiques d’ordonnancement permettant d’optimiser des critères de performances propres à l’application. De plus, une analyse d’ordonnancement générique pour cette classe a été proposée
-Ordonnancement
-Priorité dynamique
-Priorité fixe
-Round-robin
-Systèmes d’exploitation
-Multi-tâches
-Ttemps réel
Our goal is to come up with feasible (i.e., all required time constraints are met) on-line real-time scheduling algorithms. These algorithms have to optimise 1) the utilisation of the execution platform (i.e., meet time constraints and use platform at its fullest potential) and/or 2) optimise the application dependent performance criteria. We study two cases : the case of independent periodic tasks scheduled on a processor and the case of periodic traffic streams scheduled on a priority bus. To deal with these two problems, we propose : • Configuration methods to allow to optmlise the utilisation rate of the execution platform by setting the parameters of the policies or of the activities of the considered system. We perform two studies : the allocation of offsets in Offset free systems (I.E., offsets can be chosen off-line) and the priorities, policies and quantum allocations in systems compliant to the standard Posix 1003.1B, • A new class of scheduling policies to allow optimising application performance dependent criteria
-Scheduling
-Round-robin
-Dynamic priority
-Real-time
-Operating systems
-Fixed priority
-Multi-tasking
Source: http://www.theses.fr/2007INPL076N/document

Sujets

• Multitâche
• Système d'exploitation
• Round-robin
• Ordonnancement

Informations

• Publié par: Thesee
• Nombre de lectures: 109
• Langue: Français
• Poids de l'ouvrage: 2 Mo

Extrait

AVERTISSEMENT



Ce document est le fruit d’un long travail approuvé par le jury de
soutenance et mis à disposition de l’ensemble de la communauté
universitaire élargie.
Il est soumis à la propriété intellectuelle de l’auteur au même titre que sa
version papier. Ceci implique une obligation de citation et de
référencement lors de l’utilisation de ce document.
D’autre part, toute contrefaçon, plagiat, reproduction illicite entraîne une
poursuite pénale.

Contact SCD INPL : [e-mail]




LIENS




Code de la propriété intellectuelle. Articles L 122.4
Code de la propriété intellectuelle. Articles L 335.2 – L 335.10
http://www.cfcopies.com/V2/leg/leg_droi.php
http://www.culture.gouv.fr/culture/infos-pratiques/droits/protection.htm
D´epartement de formation doctorale en informatique
Institut National ´Ecole doctorale IAEM Lorraine
Polytechnique de Lorraine
Optimisation de l’ordonnancement sous
contrainte de faisabilit´e
`THESE
pr´esent´ee et soutenue publiquement le 26 octobre 2007
pour l’obtention du
Doctorat de l’Institut National Polytechnique de Lorraine
(sp´ecialit´e informatique)
par
Mathieu Grenier
Composition du jury
Pr´esident : Maryline Silly-Chetto
Rapporteurs : Pascal Richard
Gilles Muller
Examinateurs : Franc¸oise Simonot-Lion
Nicolas Navet
St´ephan Merz
Maryline Silly-Chetto
Jo¨el Goossens
Laboratoire Lorrain de Recherche en Informatique et ses Applications — UMR 7503Mis

la
en
thloria.
page
avecRaoul
déplacemen
Reb
Remerciemen
vier
ts
de
Cette
l'enseignemen
thèse

a
F
été
i
réalisée
Je
au
leurs
sein
p
de
tiens
l'équip
our
e
our
T
Lu,
emps
les
Réel
v
et
mon
In
Jean-Pierre
terOp
hel
érabilité

(TRIO)
merci
du
informa-
LORIA
gestion
dirigée
p
par
San
F
visés
rançoise
Ha
Simonot-Lion.
Jia
Mes
Boughami,
plus
Sh
vifs
Hub
remerciemen
de
ts
our
v
fait
on
er
t
de
à
égalemen
F
Xa
rançoise
et
Simonot-Lion
p
et
et


Na
Un
v

et
ses
mes
lors

et
de
e.
thèse
à
sans
leur
qui


Marques
thèse

n'aurait
senior),
pu
mougin,
ab
et
outir.
rozzen
Leur
Fla
appui
Na
et
Li,
l'in
Ch
térêt
(dit
qu'ils
Philipp
on
et
t
mem
manifestés
e
à
p
mon
m'a
égard
oir
m'on
l'honneur
t
particip
p
à
ermis
jury
de
thèse.
réaliser
remercie

t
thèse
Thomesse,
dans
vier
les
euf
meilleures


Dufner
Ils
our
m'on

t
leur

oration
b
t
eaucoup
t.
de
grand
temps
à
et
Benini
de
our

précieuses

tions
qui
des
m'a
ts
p
la
ermis
administrativ
d'améliorer
Je
l'organisation
aussi
de
remercier
mes
our

agréables
herc
Liliana
hes

et
tos
la
(p

leurs
de
a
mes
de
idées.
Xa
Je
Grand-
tiens
Lionel
à
v
exprimer
(p
mes
F
vifs
bubbles),
remerciemen
Ning,
ts
via
à
elicioni,
Madame
jet
Maryline
Jian
Silly-Chetto
Liping
et
Chen
Messieurs
ung
P
ue

Calvin),

Brito,
hard,
e
Gilles
ert
Muller,
tous
Jo
autres
ël
bres
Go
l'équip
ossens,
TRIO.
Stéphan
MerziiEt
famille.
toute
A
soutien.
Emilie
à
p
ma
our
iii
soniv2.2.3
.
.
able
.
des
.
matières
.
P
.
artie
12
I
d'algorithmes
In
.
tro
.


Chapitre
2.2.1
1
.
Con
.
texte
.
et
.
problématique
.
1.1
.
T
.
emps
.
réel
.
et
.

.
t
.
.
paramètres
.
Syn
.
.
.
paramètres
.
.
.
de
.
.
.
.
.
.
.
.
.
des
.
.
.
des
.
.
.
Conclusion
.
.
.
.
.
.
.
.
.
.
.
9
.
.
.
.
.
.
.
.
.
a
.
p
.
.
.
de
.
.
.
.
3
11
1.1.1
.
Dénitions
.
du
.
temps
nouv
réel
.
.
.
.
.
.
t
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
.
.
.
.
.
.
.
.
.
.
.
.
.
Optimisation
4
.
1.1.2
.

.
t
.
temps
.
réel
.
.
.
.
.
.
délisation
.
t
.

.
diques
.
.
.
11
.
l'ensem
.
hes
.
.
.
.
.
.
.
.
.
.
.
Ajuster
.

.
.
.
.
.
.
.
.
.
.
.
Utilisation
.
mo
.
hes
.
.
.
.
.
.
4
.
1.1.3
.
Classication
olitiques
des
.
algorithmes
.

.
t
.
.
.
.
.
.
2.2.4
.
t
.
.
.
.
.
.
.
.
.
2.2.4.1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5
2.2.4.2
1.2
.
Mo
.
délisation
.
du
.
système
.
.
.
.
.
.
15
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.2
.
de
.
t
.
.
.
.
.
.
.
.
5
.
1.2.1
.
Système
.
mono-pro
.

.
:
.
mo
.
dèle
.
de
.

.
he
10
.
Mo
.
et
.
justemen
.
des
.
des
.
hes
.
ério
.
.
.
.
.
.
.
.
.
2.2.1.1
.
thétiser
.
ble
.

.
.
.
.
.
.
.
.
6
.
1.2.2
.
Système
.
distibué
.
:
.
mo
.
dèle
.
de
2.2.1.2
ux
les
.
des
.
hes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.2.2
.
de
.
eaux
.
dèles
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7
.
1.2.3
.
Génération
13
aléatoire
P
des

ensem
en-ligne
bles
.
de
.

.
hes/ux
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
13
.
Construction
.

.
.
.
.
.
.
.
.
.
.
.
.
7
.
1.3
.
Problématique
.
traitée
14
.
Métho
.
hors-ligne
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
14
.
Métho
.
en-lignes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.3
.
.
.
.
.
.
7
.
Chapitre
.
2