La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Frédéric Ridouard - Thèse

De
1 page
École Nationale Supérieure de Mécanique et d’Aérotechnique /Université de PoitiersLaboratoire d’Informatique Scientifique et Industrielle (www.lisi.ensma.fr)ENSMA - Téléport 2-1 Avenue Clément Ader - BP 40109 - 86961 FUTUROSCOPE CHASSENEUIL Cedex - France« Contribution à des problèmes d’ordonnancement en-ligne :l’ordonnancement temps réel de tâches à suspension etl’ordonnancement par une machine à traitement par lot »Ordonnancement de tâches temps réel à suspensionCaractéristiques des tâches à suspension : ensemble de durées d’exécution avec les pires durées C , séparées par des suspensions X où chaque suspension peut représenter une i,k i,kexécution sur un processeur spécialisé. L’ensemble des grandeurs sont des pires durées possibles. Les tâches sont périodiques de périodes T 1 ≤i ≤n., Une suspension au plus par tâche Multiples suspensions par tâcheRésultats négatifs : Ordonnancer des tâches à suspension est NP-Difficile au sens fort- L’ordonnancement de tâches à suspension est NP-Difficile au sens fort; - Présence d’anomalies en ordonnancement à priorité sous RM,DM, EDF et LLF;- Il n’existe pas d’algorithme en-ligne optimal - Les techniques d’augmentation de ressource ne permettent pas de fournir des garanties de performances pour minimiser le nombre de tâches en retard.Analyse de compétitivité des calculs des pires temps de réponse : - ratios de compétitivité des tests connus entre 2.75 et 2.91667 (calculés par génération « brute force » de contre ...
Voir plus Voir moins
École Nationale Supérieure de Mécanique et d’Aérotechnique /Université de Poitiers
Laboratoire d’Informatique Scientifique et Industrielle
(www.lisi.ensma.fr)
ENSMA - Téléport 2-1 Avenue Clément Ader - BP 40109 - 86961 FUTUROSCOPE CHASSENEUIL Cedex - France
« Contribution à des problèmes d’ordonnancement en-ligne :
l’ordonnancement temps réel de tâches à suspension et
l’ordonnancement par une machine à traitement par lot »
Participants
• Francis Cottet
• Pascal Richard
• Frédéric Ridouard – Doctorant – MESR
Ordonnancement de tâches temps réel à suspension
Ordonnancement en-ligne d’une machine à traitement par lot
Support (machine à traitement par lot)
P
r
o
j
e
t
W
4
L
• Contrat avec la société Enginn’Software
Caractéristiques des tâches à suspension
: ensemble de durées d’exécution avec les pires durées
C
i,
k
, séparées par des suspensions
X
i
,k
où chaque suspension peut représenter une
exécution sur un processeur spécialisé. L’ensemble des grandeurs sont des pires durées possibles. Les tâches sont périodiques de périodes
T
,
1 ≤
i
n
.
Une suspension au plus par tâche
Multiples suspensions par tâche
Réduction depuis 3-Partition
Résultats négatifs
:
- L’ordonnancement de tâches à suspension est NP-Difficile au sens fort;
- Présence d’anomalies en ordonnancement à priorité sous RM,DM, EDF et LLF;
- Il n’existe pas d’algorithme en-ligne optimal
- Les techniques d’augmentation de ressource ne permettent pas de fournir des garanties de
performances pour minimiser le nombre de tâches en retard.
Analyse de compétitivité des calculs des pires temps de réponse
:
- ratios de compétitivité des tests connus entre 2.75 et 2.91667 (calculés par génération
« brute force » de contre exemples).
Ordonnancer des tâches à suspension est NP-Difficile au sens fort
Principales Publications
.
F. Ridouard, P. Richard, F. Cottet, “Negative results for scheduling independent hard real-time tasks
with self-suspensions”, proc. IEEE Symp. On Real-Time Systems (RTSS’04), 2004.
F. Ridouard, P. Richard, F. Cottet, K. Traoré, ”Some results on scheduling tasks with
self-suspensions”, Journal of Embedded Computing, 2 (2006) 301–312
Définition du problème.
Ordonnancement d’une machine à traitement par lot en parallèle : l’ensemble des tâches
d’un lot sont traitées en parallèle, la durée de traitement d’un lot est égale à la durée de la plus longue tâche dans le
lot. La capacité maximum d’un lot est noté
b
(nombre maximum de tâches dans un lot). Une tâche arrive à la date
r
i
et devra s’exécuté durant
C
i
unités de temps. L’objectif est de minimiser la durée totale de l’ordonnancement.
L’étude a porté sur les lots dont la taille n’est pas borné (b=
).
Ordonnancement en-ligne
: le nombre de tâches est inconnu, la fin de l’ordonnancement n’est connue que lorsque
la dernière tâche arrive dans le système (jobs are released over time). Rq: le problème hors ligne se résout en
temps polynomial si la taille des lots est non bornée, mais il est NP-Difficile au sens fort dans le cas
b
borné, y
compris s’il n’existe que des dates différente d’arrivée des tâches.
Notation du problème en ordonnancement classique :
Applications.
Analyse des échantillons dans les laboratoires pharmaceutiques.
Résultats
.
- Tout algorithme en-ligne conservatif est au mieux 2-compétitif
- L’algorithme en-ligne doit insérer des temps creux dans l’ordonnancement pour améliorer le ratio de compétitivité
- Proposition de 3 algorithmes et comparaison avec les meilleurs résultats connus. Nos algorithmes introduisent
moins de temps creux tout en conservant la meilleure garantie de performance possible.
Ratios de compétitivité obtenus et comparaison avec
ceux connus avec la littérature
Exemple
: principe de l’algorithme
α
H : à n’importe quel instant, quand la machine est inoccupée (c-à-d., qu’un
lot n’est pas en cours d’exécution), alors ne pas commencer le début du prochain lot avant la date
r
j
+
α
C
j
, ,la
meilleure garantie de performance possible est atteinte lorsqu’
α
est égal au nombre d’or.
Principale Publication
.
F. Ridouard, P. Richard, P. Martineau,
On-line scheduling on a batch processing machine with
unbounded batch size to minimize the makespan,
European Journal of Operational Research,
vol. 189 (3), Elsevier, 2008, pp. 1227-1242.
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin