Frédéric Ridouard - Thèse

Baronm

Description

É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 ...

Informations

• Publié par: Musog
• Nombre de lectures: 51
• Langue: Français

Extrait

É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.