L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation pour cette épreuve est Caml Light.
Ordonnancement de graphes de tâches
Introduction
Voici un problème important qui se pose à chacun et chacune de nous tous les jours! J'ai un certain nombre de tâches à exécuter aujourd'hui; comment planifier à quelle heure chacune va être exécutée? Par exemple, je peux avoir aujourd'hui à terminer un devoir en mathématiques, faire ma lessive à la laverie, avancer un projet en informatique, aller faire quelques courses et repasser mon linge. Chacune de ces tâches va me prendre une certaine durée, que je peux estimer. Même si ce n'est pas tout à fait le cas dans la vie courante, on peut ici supposer que les tâches ne sont pas interrompues; je ne commence une nouvelle tâche que lorsque la tâche en cours est terminée.
Dépendances. Le plus souvent, il existe des dépendances entre les tâches, en ce sens qu'il est nécessaire d'exécuter une tâche avant d'exécuter une tâche . Par exemple, il est nécessaire de laver le linge avant de le repasser. Mais, si je n'ai plus de lessive, il est nécessaire de passer faire les courses avant d'aller à la laverie. Ces dépendances peuvent être modélisées par un graphe orienté. Les nœuds sont les tâches, les arcs orientés sont les dépendances. Il y a un arc si la tâche doit être terminée avant que la tâche puisse commencer. Notez qu'il n'est pas du tout nécessaire de passer reprendre son linge à la laverie dès que la machine s'arrête. La tâche peut être ordonnancée longtemps après que la tâche sera terminée.
Ordonnancement. Un ordonnancement est la donnée d'une heure d'exécution pour chacune des tâches qui respecte cette contrainte qu'une tâche commence seulement lorsque toutes celles dont elle dépend sont terminées. Notez qu'il peut y avoir des moments de repos où aucune tâche n'est en exécution. La mesure intéressante est alors la durée d'exécution totale, c'est-à-dire la durée écoulée entre l'heure à laquelle l'exécution de la première tâche commence et l'heure à laquelle celle de la dernière tâche se termine.
Parallélisme. Si je suis seul, je ne peux exécuter qu'une tâche à la fois. Mais je peux aussi me faire aider! Il est alors possible d'exécuter plusieurs tâches en parallèle. Par exemple, je peux demander à quelqu'un de faire ma lessive à la laverie, pour aller faire mes courses pendant ce temps et ensuite revenir la prendre pour la repasser. En termes informatiques, on parle de multiples processeurs qui collaborent pour le traitement des tâches. Dans notre exemple, deux processeurs travaillent en parallèle : l'un pour faire la lessive, l'autre pour faire les courses. À chaque instant, plusieurs tâches peuvent être exécutées, au plus autant que de processeurs. Notez qu'il est cependant possible qu'un processeur soit forcé de rester inactif un certain temps, par exemple parce que la tâche qu'il doit exécuter dépend d'une autre tâche qui est en cours d'exécution sur un autre processeur.
Défi algorithmique. Les exemples ci-dessus sont bien sûr des illustrations simplifiées. En pratique, on va considérer des graphes de tâches de taille gigantesque, par exemple l'ensemble des actions nécessaires pour assembler un avion. Ces graphes comptent des millions de tâches avec des dépendances complexes. Les tâches seront allouées à des ouvriers. Ceux-ci travaillent à l'intérieur d'horaires fixés, avec des périodes de repos, des vacances, des arrêts imprévus pour cause de maladie ou de panne de machine. L'objectif sera de trouver le meilleur ordonnancement possible pour l'assemblage selon une mesure donnée. Notez que dans ce cas, le graphe est fixe, mais le nombre d'ouvriers peut varier : on peut par exemple embaucher plus d'ouvriers pour réduire la durée d'exécution totale. Cela augmente le coût de production mais réduit les délais de livraison. Trouver un ordonnancement optimal est alors un défi algorithmique majeur.
Plan du sujet proposé. La partie I introduit la notion d'ordonnancement d'un graphe de tâches. La partie II s'intéresse à quelques propriétés des graphes de tâches acycliques. La partie III étudie une première approche pour la recherche d'un ordonnancement d'un graphe de tâches. L'ordonnancement produit est optimal avec processeur, mais pas avec . La partie IV étudie comment modifier cette approche pour produire un ordonnancement optimal avec processeurs dans le cas particulier des arbres arborescents entrants. La partie V décrit comment compléter cette approche et obtenir un ordonnancement optimal avec processeurs dans le cas général.
Les parties peuvent être traitées indépendamment. Néanmoins, chaque partie utilise des notations et des fonctions introduites dans les parties précédentes.
La complexité, ou le coût, d'un algorithme ou d'une fonction Caml est le nombre d'opérations élémentaires nécessaires à son exécution dans le pire cas. La notion d'opération élémentaire sera précisée dans chaque cas par le sujet. Lorsque cette complexité dépend d'un ensemble de
Figure 1 - Quelques exemples de graphes de tâches.
paramètres ( ), on pourra donner cette estimation sous forme asymptotique. On rappelle qu'une application est dans la classe s'il existe une constante telle que , pour toutes les valeurs de assez grandes.
I Définitions de base
Graphe de tâches. Un graphe de tâches est constitué d'un ensemble fini et non vide de tâches notées , etc.
L'application associe à chaque tâche du graphe sa durée. Dans tout ce problème, on supposera que la durée d'une tâche est unitaire : .
L'ensemble est un ensemble d'arcs (dirigés) entre ces tâches ( pour dépendance, voir plus loin). L'existence d'un arc ( ) dans est notée . On suppose qu'il n'y a pas d'arc entre une tâche et elle-même : .
Il y a un arc dirigé ( ) d'une tâche vers une autre tâche distincte, , si la tâche doit être exécutée avant la tâche . On dit alors que la tâche dépend de la tâche en ce sens que ne peut commencer qu'une fois que est terminée. On dit alors que précède ou que la tâche succède à la tâche . On peut donc parler de l'ensemble des tâches qui précèdent et de l'ensemble des tâches qui succèdent à . Notez que ces ensembles peuvent être vides.
Une tâche qui n'a aucun prédécesseur s'appelle une racine. Une tâche qui n'a aucun successeur s'appelle une feuille.
La taille d'un graphe de tâches est le nombre de ses tâches.
La figure 1 propose quelques exemples de graphes de tâches de petite taille.
Ordonnancement. Un ordonnancement d'un graphe de tâches est une application à valeurs entières qui associe une date d'exécution à chaque tâche du graphe, dans le respect des contraintes de dépendance spécifiées par la formule (1) ci-dessous.
Une tâche est exécutée de manière ininterrompue par le processeur qui en a la charge aux instants tels que . Une tâche qui dépend de ne peut être exécutée qu'après la terminaison de , donc à partir de l'instant . Un ordonnancement doit donc respecter la contrainte suivante :
L'instant du début de l'ordonnancement du graphe de tâches est l'instant où la première tâche est exécutée : .
L'instant de la fin de l'ordonnancement est l'instant où la dernière tâche est terminée : .
La durée d'exécution totale de l'ordonnancement est .
L'ensemble des tâches en cours d'exécution à l'instant est défini par :
Dans notre cas, pour toute tâche et cette formule se simplifie :
On dit qu'un ordonnancement utilise (au plus) processeurs si cardinal à tout instant .
On dit qu'un ordonnancement est optimal pour un graphe de tâches avec processeurs si sa durée d'exécution est minimale parmi tous les ordonnancements possibles de avec processeurs.
La figure 2 propose quelques exemples d'ordonnancements de graphes de tâches. On rappelle que chaque tâche dure une unité de temps : . La date d'exécution de chaque tâche est indiquée à gauche de cette tâche.
L'ordonnancement présenté en figure 2a a une durée d'exécution totale de 10 avec processeur. Il n'est pas optimal. En effet, aucune tâche n'est exécutée à l'instant 5 où la tâche est prête; il serait donc possible de réduire la durée d'exécution totale à 9 . Ce serait alors optimal puisqu'il y a 9 tâches, chacune de durée 1 .
L'ordonnancement présenté en figure 2 b a une durée d'exécution totale de 5 avec processeurs. Comme il y a 8 tâches pour 2 processeurs, tout ordonnancement a une durée au moins égale à 4 . Cependant, les contraintes de dépendance ne permettent pas de réaliser un ordonnancement de durée 4 . Un ordonnancement de durée d'exécution totale 5 est donc optimal.
Le graphe de tâches de la figure 2c comporte un cycle : . Aucune tâche d'un cycle ne peut être exécutée en respectant les contraintes de dépendance.
Figure 2 - Quelques exemples d'ordonnancement de graphes de tâches.
Objectif. L'objectif de ce problème va être de déterminer des ordonnancements optimaux pour certaines classes de graphes de tâches pour un nombre donné de processeurs.
II Graphe de tâches acyclique
Un chemin de dépendance dans un graphe de tâches d'une tâche à une tâche est une suite de tâches , avec et et en dépendance successive: , .
La longueur du chemin est le nombre d'arcs de dépendance, c'est-à-dire l'entier . La tâche initiale du chemin est , sa tâche terminale . Notez qu'une tâche peut apparaître plusieurs fois dans un chemin. Notez aussi qu'un chemin peut être de longueur nulle. Il a alors la même tâche initiale et terminale.
Une tâche est atteignable depuis une tâche s'il existe un chemin qui a pour tâche initiale et pour tâche terminale .
Un cycle dans un graphe de tâches est un chemin de longueur qui a même tâche initiale et terminale : .
Un graphe de tâches est dit acyclique s'il ne possède pas de cycle. Les graphes de tâches des figures 1a et 1b sont acycliques, celui de la figure 1c possède un cycle.
On veut maintenant montrer qu'il n'existe pas d'ordonnancement pour un graphe de tâches qui possède un cycle.
Question 1. Soit un graphe de tâches qui admet un ordonnancement . Démontrez que s'il existe un chemin de dépendance de longueur non nulle d'une tâche vers une tâche dans , alors . En déduire que est nécessairement acyclique.
let graph = make_graph ();;
add_task a graph;;
add_dependence a c graph;;
let make_task 1 "a";;
add_task b graph;;
add_dependence a d graph;;
let make_task 1 " b ";;
add_task c graph;;
add_dependence b d graph;;
let make_task 1 " c ";;
add_task d graph;;
add_dependence b g graph;;
add_dependence c e graph;;
let make_task 1 " d ";;
add_task e graph;;
add_dependence d f graph;;
let e = make_task 1 "e";;
add_task f graph;;
add_dependence e h graph;;
let make_task 1 " ";;
add_task g graph;;
add_dependence f h graph;;
let make_task 1 " ;;
add_task h graph;;
add_dependence g h graph;;
Table 1 - Comment construire le graphe de la figure 1b avec la bibliothèque Graph.
Avant de chercher un ordonnancement d'un graphe de tâches, il faut donc vérifier qu'il est acyclique. La propriété suivante fournit une condition nécessaire. On rappelle qu'un graphe de tâches est constitué d'un nombre fini et non nul de tâches.
Question 2. Soit un graphe de tâches. Montrez que si est acyclique, alors a nécessairement au moins une racine et une feuille.
Dans toute la suite du problème, on suppose qu'on dispose d'une certaine bibliothèque Caml appelée Graph qui permet de manipuler des graphes de tâches. Cette bibliothèque regroupe des fonctions qui sont disponibles pour les utilisateurs, même s'ils n'en connaissent pas le code. On pourra donc utiliser librement toutes les fonctions de cette bibliothèque sans les réécrire. Cette bibliothèque définit deux types de données : graph pour les graphes de tâches, et task pour les tâches. Elle propose les fonctions listées en table 2 pour manipuler ces deux types. La table 1 montre comment on pourrait construire le graphe de la figure 1b avec ces fonctions.
On rappelle quelques fonctions Caml Light permettant de manipuler les tableaux et d'imprimer.
make_vect n a renvoie un nouveau tableau de n éléments qui contiennent tous la même valeur a.
vect_length tab renvoie la longueur (le nombre d'éléments) du tableau tab. Ceux-ci sont indexés de 0 à inclus.
tab.(i) renvoie la valeur de l'élément d'indice i du tableau tab.
tab.(i) <- a affecte la valeur a à l'élément d'indice i du tableau tab.
sub_vect tab i n renvoie le sous-tableau de tab constitué de n éléments à partir de l'indice i inclus.
print_int n imprime l'entier n .
print_string s imprime la chaîne s.
print_newline () passe à la ligne suivante.
Voici par exemple comment imprimer l'ensemble des successeurs d'une tâche :
let print_successors t =
let tab = get_successors t in
for i = 0 to (vect_length tab) - 1 do
print_string (get_name (tab.(i))); print_string "ப"
done;
print_newline ();;;
make_graph: unit -> graph
Crée un graphe vide.
make_task: int -> string -> task
Crée une tâche d'une durée donnée avec un nom donné.
(Attention, une erreur se produit si le nom a déjà été utilisé pour la création d'une autre tâche.)
empty_task: task
Une tâche vide, différente de toutes les tâches créées par la fonction make_task.
(Attention, une erreur se produit si on applique les fonctions de manipulation de tâches ci-dessous autres que is_empty_task à cette tâche.)
is empty _task: task -> bool
Teste si une tâche est la tâche empty_task
get_duration: task -> int
Renvoie la durée d'une tâche.
get name: task -> string
Renvoie le nom d'une tâche.
add task: task -> graph -> unit
Ajoute une tâche au graphe.
get tasks: graph -> task vect
Renvoie le tableau des tâches du graphe.
add_dependence: task -> task -> graph -> unit
Ajoute un arc de dépendance au graphe, de la première vers la seconde tâche.
(Attention, une erreur se produit si les tâches n'existent pas dans le graphe.)
get _successors: task -> graph -> task vect
Renvoie le tableau des tâches successeurs d'une tâche donnée.
(Attention, une erreur se produit si la tâche n'existe pas dans le graphe.)
get _predecessors: task -> graph -> task vect
Renvoie le tableau des tâches prédécesseurs d'une tâche donnée.
(Attention, une erreur se produit si la tâche n'existe pas dans le graphe.)
Table 2 - La table des fonctions de la bibliothèque Graph de manipulation de graphes de tâches.
Question 3. Écrivez en Caml les fonctions suivantes :
count_tasks: graph int : renvoie le nombre de tâches d'un graphe de tâches.
count_roots: graph int : renvoie le nombre de ses tâches racines.
Question 4. Écrivez en Caml une fonction make_root_array: graph task vect qui renvoie le tableau des tâches racines du graphe. On pourra si nécessaire renvoyer un tableau plus grand que le nombre de racines. Il sera dans ce cas complété par la tâche empty_task.
Un tableau est complété par une valeur u si cette valeur n'apparaît pas dans le tableau, ou alors, si elle apparaît, elle n'apparaît pas jusqu'à un certain indice, puis seule cette valeur apparaît au-delà de cet indice.
III Ordonnancement par hauteur
On s'intéresse à la recherche d'un ordonnancement d'un graphe acyclique donné de tâches sur un ensemble de processeurs. On rappelle que chaque tâche dure une unité de temps : .
set_tag: int -> task -> unit
Affecte une étiquette à une tâche.
(Attention, une erreur se produit si une étiquette a déjà été affectée à cette tâche.)
get_tag: task -> int
Renvoie l'étiquette d'une tâche.
(Attention, une erreur se produit si aucune étiquette n'a été affectée à cette tâche.)
has_tag: task -> bool
Renvoie vrai si l'étiquette de la tâche a été définie par la fonction set_tag et faux sinon.
TABLE 3 - La table des fonctions complémentaires pour la manipulation des étiquettes à valeurs entières des tâches.
Une tâche peut être ordonnancée seulement si toutes les tâches dont elle dépend l'ont déjà été. Trouver un ordonnancement d'un graphe acyclique avec un seul processeur revient donc à énumérer les tâches de ce graphe dans un ordre (total) qui respecte les contraintes de dépendance. Il est donc intéressant d'étiqueter le graphe de tâches selon ces contraintes.
Pour manipuler les étiquettes à valeurs entières des tâches, on étend la bibliothèque Graph avec les fonctions sur les tâches décrites en table 3 .
Cet étiquetage fonctionne de la manière suivante : une tâche reçoit une étiquette tag( ) portant un numéro strictement supérieur à celui de toutes les étiquettes tag des tâches telles que . Notez que plusieurs tâches peuvent recevoir la même étiquette.
Algorithme 1 (étiquetage par hauteur depuis les racines).
Initialement, aucune tâche n'est étiquetée.
À l'itération d'ordre , on parcourt l'ensemble des tâches et on affecte l'étiquette 0 aux tâches racines.
À l'itération , on parcourt l'ensemble des tâches en repérant toutes les tâches qui n'ont pas encore été étiquetées mais dont toutes les tâches prédécesseurs sont déjà étiquetées. On affecte ensuite à chacune de ces tâches l'étiquette .
L'algorithme termine quand toutes les tâches sont étiquetées.
On dira d'une tâche qui a reçu l'étiquette qu'elle porte l'étiquette .
La figure 3a présente un exemple d'étiquetage selon l'algorithme 1. Les étiquettes sont notées dans les cercles grisés à droite des tâches.
Question 5. Écrivez une fonction Caml check_tags_predecessors: task bool qui prend en paramètre une tâche et renvoie vrai si toutes ses tâches prédécesseurs dans le graphe de tâches sont étiquetées et faux sinon. En particulier, la fonction renvoie vrai si la tâche ne dépend d'aucune tâche (c'est une racine).
Question 6. Écrivez une fonction Caml label_height: graph -> unit qui prend en paramètre un graphe de tâches et affecte à chaque tâche une étiquette selon l'algorithme 1. Veillez bien à ce qu'aucune erreur ne puisse se produire lors des appels des fonctions de la bibliothèque Graph.
Figure 3 - Un exemple d'étiquetage par hauteur et un ordonnancement associé.
Pour chaque valeur de l'étiquette , on pourra par exemple dans un premier temps repérer l'ensemble des tâches à étiqueter, puis dans un second temps étiqueter ces tâches. Chacune de ces deux actions pourra être implémentée par une fonction auxiliaire.
Soit un graphe de tâches. Soit une tâche de . Soit l'ensemble des chemins de la forme , où est une racine de et . La tâche admet un chemin critique amont si est non vide et si l'ensemble des longueurs des chemins de est majoré. Les chemins critiques amont de sont alors les chemins de de plus grande longueur. En particulier, le chemin critique amont d'une racine est de longueur nulle et il est unique.
Considérons un graphe de tâches qui possède un cycle. Soit une tâche d'un cycle de . Supposons que soit non vide. Alors, il existe une racine de telle que soit atteignable de cette racine. On peut produire des chemins arbitrairement longs de à en parcourant le cycle de manière répétée. La tâche n'admet donc pas de chemin critique amont.
Question 7. Soit un graphe de tâches acyclique. Montrez que toutes ses tâches admettent des chemins critiques amont.
Question 8. Supposons que soit acyclique. Démontrez qu'une tâche u reçoit l'étiquette de valeur dans l'algorithme 1 si et seulement si la longueur commune des chemins critiques amont de est .
Question 9. En déduire que l'algorithme termine si et seulement si le graphe est acyclique. Montrez par un exemple ce qui se produit si le graphe possède un cycle.
Question 10. Démontrez que si une tâche porte une étiquette , alors elle ne pourra être ordonnancée qu'au moins unités de temps après que la première tâche a été ordonnancée, quel que soit l'ordonnancement mais aussi quel que soit le nombre de processeurs utilisés.
Soit un graphe de tâches acyclique. Soit la valeur maximale des étiquettes attribuées aux tâches de par l'algorithme 1. Soit l'ensemble des tâches de qui reçoivent cette étiquette . Les chemins critiques amont des tâches de sont appelés chemins critiques de . Ces chemins comportent tâches de durée unitaire. Selon la question 10, la durée d'exécution totale du graphe de tâches est donc minorée par .
Une fois un graphe de tâches étiqueté selon l'algorithme 1, il est possible de déterminer un ordonnancement avec processeurs en exécutant les tâches par niveau selon la valeur de leurs étiquettes. Soit l'ensemble des tâches qui portent l'étiquette .
Algorithme 2 (algorithme d'ordonnancement par hauteur pour processeurs). Pour chaque valeur de entre 0 et , on exécute les tâches de par lots de tâches. Pour chaque valeur , le dernier lot pourra être incomplet. Les processeurs inutilisés sont alors inactifs.
Les figures 3b et 3c présentent des ordonnancements obtenus par cet algorithme à partir de l'étiquetage de la figure 3a, respectivement pour et processeurs. On notera en particulier que dans la figure 3c la tâche reçoit l'étiquette 4 et non 3 .
Un ordonnancement sera imprimé de la manière suivante. Chaque ligne entre Begin et End liste les tâches exécutées à un instant donné. Il y a une ligne par instant entre le début et la fin de l'ordonnancement. Le nombre de ligne est donc la durée totale d'exécution de l'ordonnancement.
On pourra utiliser la fonction get_name de la bibliothèque Graph pour obtenir le nom des tâches et utiliser la fonction print_string pour l'imprimer.
Question 11. Écrivez une fonction Caml schedule_height: graph int unit qui prend en paramètres un graphe de tâches étiquetées par l'algorithme 1 et un nombre de processeurs et qui imprime pour chaque instant la liste des noms des tâches (au plus p) exécutées selon l'algorithme 2 selon le format ci-dessus.
On pourra par exemple diviser le traitement en plusieurs actions implémentées par des fonctions auxiliaires. Pour chaque valeur de l'étiquette , on extrait l'ensemble des tâches portant cette étiquette. On imprime ensuite cet ensemble par lots de tâches, avec un lot par ligne, le dernier lot étant éventuellement incomplet.
Une opération élémentaire de l'algorithme est d'accéder à une tâche par l'une des fonctions des bibliothèques présentées dans les tables 2 et 3 . On suppose que chaque opération élémentaire coûte 1 .
Question 12. Estimez la complexité de votre fonction schedule_height pour l'ordonnancement d'un graphe de tâches étiquetées par l'algorithme 1 avec processeurs.
Question 13. Justifiez que l'ordonnancement ainsi obtenu est optimal pour un seul processeur, c'est-à-dire quand .
Un graphe de tâches acyclique arborescent sortant est un graphe avec une unique racine dans lequel chaque tâche sauf cette racine a exactement un prédécesseur. C'est par exemple le cas du
Figure 4 - Quelques exemples de graphes de tâches arborescents.
graphe de la figure 4a. Un graphe de tâches acyclique arborescent entrant est un graphe avec une unique feuille dans lequel chaque tâche sauf cette feuille a exactement un successeur. C'est par exemple le cas du graphe de la figure 4 b .
Question 14. Appliquez l'algorithme 1 aux deux graphes de tâches de la figure 4 pour processeurs. Quelle est la durée totale d'exécution des ordonnancements produits? Montrez que ces ordonnancements ne sont pas optimaux pour processeurs en décrivant pour chacun des graphes un ordonnancement dont la durée totale d'exécution est strictement plus courte.
IV Ordonnancement par profondeur : l'algorithme de Hu
On suppose dans toute la suite du problème que tous les graphes de tâches considérés sont acycliques.
L'étiquetage par hauteur ne fournit pas assez d'informations pour ordonnancer les tâches de manière optimale car il s'appuie sur la structure du graphe en amont des tâches étiquetées. La figure 5 décrit par exemple deux ordonnancements du même graphe dans lequel les tâches exécutées sont exécutées dans l'ordre croissant des étiquettes de hauteur. Cependant, l'ordonnancement 5 a conduit l'un des processeurs à rester inactif alors que l'ordonnancement 5 b permet l'utilisation constante des deux processeurs.
L'idée de cette partie est de mettre en place un autre étiquetage, cette fois-ci fondé sur les plus longs chemins de tâches en aval. En effet, la question 16 ci-dessous montrera que la longueur des plus longs chemins de tâches en aval d'une tâche limite inférieurement la durée d'exécution au-delà de cette tâche. Il sera donc intéressant d'exécuter les tâches avec les plus longs chemins de tâches en aval le plus tôt possible. C'est ce que nous ferons dans l'algorithme 4 ci-dessous dû à Hu.
Figure 5 - Un graphe de tâches pour lequel la méthode d'ordonnancement par hauteur de la section III ne fournit pas un ordonnancement optimal pour processeurs.
Il suffit donc d'adapter l'algorithme 1 pour étiqueter les tâches à partir des feuilles au lieu des racines.
Algorithme 3 (étiquetage par profondeur depuis les feuilles).
Initialement, aucune tâche n'est étiquetée.
À l'itération d'ordre , on parcourt l'ensemble des tâches et on affecte l'étiquette 0 aux tâches feuilles.
À l'itération , on parcourt l'ensemble des tâches en repérant toutes les tâches qui n'ont pas encore été étiquetées mais dont toutes les tâches successeurs sont déjà étiquetées. On affecte à chacune de ces tâches l'étiquette .
L'algorithme termine quand toutes les tâches sont étiquetées.
La figure 5 c présente un exemple d'étiquetage obtenu par l'algorithme 3.
Question 15. Expliquez comment adapter la fonction label_height de la question 6 pour obtenir une fonction label_depth: graph -> unit qui affecte à chaque tâche une étiquette selon l'algorithme 3.
Soit un graphe de tâches. Soit une tâche de . Soit l'ensemble des chemins de la forme , où et est une feuille de . La tâche admet un chemin critique aval si est non vide et si l'ensemble des longueurs des chemins de est majoré. Un chemin critique aval de est un chemin de plus grande longueur dans l'ensemble .
Considérons un graphe de tâches . (On rappelle que les graphes de tâches sont supposés acycliques ici.) Comme pour les chemins critiques amont, toutes les tâches de admettent des chemins critiques aval. La profondeur d'une tâche , depth , est la longueur commune des chemins critiques aval de .
Question 16. Soit un graphe de tâches acyclique. Soit u une tâche de de profondeur . Supposons que u soit exécutée à l'instant . Montrez que l'ordonnancement de ne pourra pas terminer avant l'instant quel que soit le nombre de processeurs utilisés.
Init, Ready, Done
Les valeurs du type state.
set _state: state -> task -> unit
Affecte un état à une tâche.
get_state: task -> state
Renvoie l'état d'une tâche. (On suppose que l'état des tâches est initialisé à Init lors de leur création.)
Table 4 - La table des fonctions complémentaires pour la manipulation des états des tâches.
Une tâche est dite prête à être exécutée à un instant si toutes les tâches dont elle dépend ont été déjà exécutées.
Algorithme 4 (algorithme de Hu pour processeurs). Soit un graphe de tâches acyclique. On construit un ordonnancement de pour processeurs de manière suivante.
L'ordonnancement commence à l'instant .
À chaque instant , on considère l'ensemble des tâches de prêtes à être exécutées. Soit le cardinal de cet ensemble.
Si , on choisit pour être exécutées à l'instant les tâches de et processeurs restent inactifs.
Sinon, on trie les tâches de par ordre décroissant de profondeur et on choisit pour être exécutées à l'instant les premières tâches.
L'ordonnancement se termine quand toutes les tâches de ont été exécutées.
On notera que le caractère acyclique de garantit qu'il y a toujours au moins une tâche prête tant qu'il reste dans une tâche non exécutée.
Question 17. Appliquez l'algorithme de Hu aux graphes de tâches des figures 4 a et pour processeurs. Quelles sont les durées d'exécution totales obtenues?
Pour écrire l'algorithme en Caml, il sera commode de manipuler les états des tâches grâce aux fonctions de la table 4 . Ces états appartiennent à un type state qui contient les valeurs suivantes. Une tâche est dans l'état initial Init si elle n'a pas encore été traitée. C'est en particulier le cas lors de sa création par la fonction make_task. Elle est dans l'état Ready si toutes les tâches dont elle dépend ont été exécutées. Elle est dans l'état Done si elle a été exécutée.
L'état de la tâche empty_task n'est pas défini. bool qui renvoie vrai si toutes les tâches dont dépend la tâche passée en argument sont dans l'état Done et faux sinon. En particulier, la fonction renvoie vrai si la tâche passée en argument ne dépend d'aucune tâche.
Pour implémenter l'algorithme 4, il faudra trier les tâches du graphe selon la valeur de leurs étiquettes, par ordre décroissant. On supposera donc qu'on dispose d'une fonction Caml sort_tasks_by_decreasing_tags: task vect -> task vect qui réalise une telle opération. Attention, une erreur se produit si l'étiquette d'une des tâches du tableau n'est pas définie, sauf si c'est la tâche spéciale empty_task. Cette tâche est considérée plus petite que toutes les autres tâches dans le tri.
Figure 6 - Un graphe de tâches... un peu pathologique.
Question 19. Écrivez une fonction Caml schedule_Hu: graph int unit qui prend en paramètres un graphe de tâches étiquetées par l'algorithme 3 et un nombre de processeurs et qui imprime pour chaque instant la liste des tâches (au plus p) exécutées selon l'algorithme de Hu. L'impression doit avoir la même forme que pour la question 11.
On pourra par exemple diviser le traitement en plusieurs actions implémentées par des fonctions auxiliaires.
Une opération élémentaire de l'algorithme est d'accéder à une tâche par l'une des fonctions des bibliothèques présentées dans les tables 2,3 et 4 . On suppose que chaque opération élémentaire coûte 1. On suppose que l'appel à la fonction sort_tasks_by_decreasing_tags sur un tableau de taille coûte .
Question 20. Estimez la complexité de votre fonction schedule_Hu pour l'ordonnancement d'un graphe de tâches étiquetées par l'algorithme 3 avec processeurs.
On peut montrer que l'algorithme de Hu est optimal pour les graphes de tâches arborescents entrants comme celui de la figure 4 b avec un nombre de processeurs arbitraire. La preuve de ce résultat est délicate, mais l'une des clés de la preuve est la propriété suivante.
Question 21. Soit un graphe de tâches arborescent entrant avec processeurs. Montrez que dans l'algorithme de Hu le cardinal de l'ensemble de tâches prêtes dans ne peut pas croître au cours de l'algorithme.
Cette propriété est spécifique du caractère arborescent entrant comme le montre l'exemple de la figure 6.
Question 22. Montrez que l'algorithme de Hu ne conduit pas nécessairement à un ordonnancement optimal avec processeurs pour le graphe de tâches de la figure 6 .
On montrera qu'il existe réarrangement trié des tâches de ce graphe qui conduit à un ordonnancement non optimal.
Question 23. Montrez que l'algorithme de Hu est optimal pour les graphes de tâches arborescents entrants avec processeurs.
Cette preuve est délicate. Un approche possible est d'examiner l'activité des processeurs au cours d'un ordonnancement. On peut montrer qu'à partir de l'instant où les processeurs ne sont plus tous actifs, l'exécution est conditionnée par un chemin critique du graphe. Ainsi, l'ordonnancement utilise toujours au mieux les processeurs disponibles.
V Conclusion
Ce problème a été initialement étudié par T. C. Hu du centre de recherche IBM de Yorktown Heights en 1961. À l'époque, il s'agissait d'organiser le travail d'ouvriers sur une ligne de montage. La preuve d'optimalité dont ce sujet s'est inspiré a été proposée par James A. M. McHugh en 1984.
L'algorithme de Hu consiste en fait à définir une mesure de priorité sur les tâches à ordonnancer. La mesure considérée est la profondeur de la tâche. Les tâches sont ordonnancées en privilégiant celles de plus grande priorité. L'exemple de la figure 6 montre que cette approche n'est cependant pas adaptée à des graphes où des tâches ont des dépendances multiples. Dans ce cas, il est important de privilégier certaines tâches par rapport à d'autres parmi toutes les tâches de même profondeur.
En 1972, E. G. Coffman, Jr. et R. L. Graham ont proposé une amélioration de cette mesure de priorité. L'idée est de départager les tâches de profondeurs égales en privilégiant parmi elles celles qui ont les successeurs les plus profonds en un certain sens. Cet algorithme conduit à un ordonnancement optimal pour les graphes de tâches quelconques, pour processeurs.
Malheureusement, il ne l'est pas pour le cas . Cependant, on peut montrer que tous les algorithmes étudiés ci-dessus conduisent à des ordonnancements dont la durée d'exécution totale n'est pas plus du double de la durée optimale. Cette approximation est heureusement suffisante dans un grand nombre d'applications.
On pourra procéder par récurrence sur la longueur du chemin après avoir soigneusement spécifié la propriété démontrée par récurrence.
X ENS Option Informatique MP 2015 - Version Web LaTeX | WikiPrépa | WikiPrépa
