Université des Sciences et Technologies de Lille

Licence Miage - Programmation 1 - TP

Répartition de charges

Un problème d'ordonnancement, dans sa version la plus simple, peut être formulé ainsi. On dispose d'un côté de n tâches, de l'autre d'une machine multi-processeurs sur laquelle les tâches doivent s'exécuter. Il s'agit de savoir dans quel ordre traiter les tâches, et sur quel processeur les affecter pour obtenir une durée globale d'exécution satisfaisante.

Ici, nous acceptons les hypothèses suivantes :

chaque tâche est caractérisée par sa durée (un entier),
une tâche n'est pas interruptible : quand un job est affecté à un processeur, il s'exécute jusqu'au bout,
tous les processeurs de la machine sont identiques.

1ère Méthode

Une solution pour ce problème consiste à traiter les n tâches par ordre de durée décroissante, et à affecter une tâche dès qu'un processeur est libre.

Écrire une procédure Ordonnancement qui prend en arguments un ensemble de tâches, figuré par un tableau d'entiers, un nombre k de processeurs, et qui affiche l'affectation de chacune des tâches, ainsi que la durée globale d'exécution. Bien sûr, vous pouvez (et même, vous devez) utiliser votre travail précédent sur les tris.

La procédure Ordonnancement fournit-elle toujours la solution optimale, c'est-à-dire celle de durée minimale ? Regardez ce qui se passe avec l'affectation de cinq tâches de durée 6, 6, 4, 4 et 4 sur deux processeurs.

2ème Méthode

Devant l'échec relatif de la première approche, nous allons essayer une autre voie. Le nouvel algorithme procède par examen systématique de toutes les affectations possibles et conserve la meilleure. Pour simplifier le problème, on se restreint à des machines bi-processeurs (k=2). Une affectation globale est alors représentée par un tableau de booléens : True pour le premier processeur, False pour le second, par exemple. On définit le type

     type Affectation is array(Natural range <>) of Boolean;

1. Le premier travail demandé par l'algorithme est de savoir énumérer toutes les affectations possibles de n tâches sur deux processeurs. Pour cela, on peut classer les affectations comme des nombres binaires, de (False, ..., false) à (True, ..., True). Écrire une fonction

     Suivante(A:Affectation) return Affectation

qui retourne l'affectation qui succède à A dans l'ordre d'énumération.

2. Écrire une fonction Duree qui prend en argument un ensemble de tâches, une affectation et renvoie la durée globale d'éxécution.

3. Écrire une procédure Ordonnancement2 qui prend en argument un ensemble de tâches et qui affiche l'affectation optimale, ainsi que la durée globale d'exécution. Que pensez-vous de la complexité de ce nouvel algorithme ?