Ordonnancement de T ches dans un Milieu H t rog ne

Objectifs et prérequis du TP sur l'ordonnancement de tâches hétérogène

Objectifs

Ce TP vise à enseigner les principes de l'ordonnancement de tâches indépendantes dans un environnement hétérogène. À l'issue de ce TP, vous serez capable de :

• Comprendre les concepts de base de l'ordonnancement de tâches.
• Appliquer différents algorithmes d'ordonnancement.
• Évaluer les performances des algorithmes à l'aide de métriques appropriées.
• Identifier et corriger les erreurs fréquentes dans l'ordonnancement.

Prérequis

Pour réaliser ce TP, vous aurez besoin des éléments suivants :

• Un environnement de programmation (par exemple, Python ou Java).
• Connaissances de base en algorithmique et en structures de données.
• Compréhension des concepts de tâches et de processeurs.

Procédure d'ordonnancement des tâches

Introduction à l'ordonnancement

Nous allons explorer l'ordonnancement de tâches indépendantes en utilisant trois algorithmes principaux : LS (List Scheduling), SPT (Shortest Processing Time) et LPT (Longest Processing Time). Chaque algorithme sera testé avec un ensemble de tâches et de processeurs.

Étape 1 : Configuration des tâches et des processeurs

Considérons un ensemble de n tâches avec des coûts respectifs c_j (j=1..n) à ordonnancer sur p processeurs de vitesses respectives v₁, v₂, ..., v_p. Par exemple, prenons n=8 avec les coûts suivants : 4, 6, 3, 10, 7, 3, 8, 3, et p=2 avec v₁=1 et v₂=1/2.

Étape 2 : Application de l'algorithme LS-1

Dans l'algorithme LS-1, les tâches sont prises dans l'ordre. Les tâches sont ordonnées comme suit : 4, 6, 3, 10, 7, 3, 8, 3. Le makespan M(2) est calculé comme suit :

M(2)=32

Étape 3 : Application de l'algorithme SPT-1

Pour l'algorithme SPT-1, les tâches sont triées par coût croissant. L'ordre des tâches devient : 3, 3, 3, 4, 6, 7, 8, 10, avec un makespan calculé :

M(2)=38

Étape 4 : Application de l'algorithme LPT-1

Pour l'algorithme LPT-1, les tâches sont triées par coût décroissant. L'ordre devient : 10, 8, 7, 6, 4, 3, 3, 3, avec un makespan :

M(2)=30

Dans ce cas, LPT-1 est le meilleur algorithme.

Résultats attendus de l'ordonnancement

Après avoir appliqué les trois algorithmes, les résultats suivants doivent être observés :

• LS-1 : M(2)=32
• SPT-1 : M(2)=38
• LPT-1 : M(2)=30

Il est important de noter que LPT-1 offre le meilleur équilibre de charge.

Erreurs fréquentes avec l'ordonnancement de tâches

Lors de l'application des algorithmes d'ordonnancement, plusieurs erreurs peuvent survenir :

• Ne pas respecter l'ordre des tâches dans LS.
• Oublier de trier les tâches correctement dans SPT et LPT.
• Confondre les vitesses des processeurs lors du calcul des charges pondérées.

Pour éviter ces erreurs, il est crucial de vérifier chaque étape et de s'assurer que les calculs sont effectués correctement.

Questions fréquentes

Qu'est-ce que l'ordonnancement de tâches hétérogène ?

L'ordonnancement de tâches hétérogène concerne la distribution de tâches indépendantes sur plusieurs processeurs ayant des vitesses différentes, afin de minimiser le temps d'exécution total.

Quels sont les algorithmes d'ordonnancement les plus courants ?

Les algorithmes d'ordonnancement les plus courants incluent LS (List Scheduling), SPT (Shortest Processing Time) et LPT (Longest Processing Time), chacun ayant ses propres méthodes d'allocation des tâches.

Comment évaluer les performances des algorithmes d'ordonnancement ?

Les performances des algorithmes peuvent être évaluées à l'aide de métriques telles que le makespan, qui est le temps total nécessaire pour exécuter toutes les tâches sur les processeurs.

Quelles erreurs fréquentes peuvent survenir lors de l'ordonnancement ?

Les erreurs fréquentes incluent des erreurs de tri des tâches, des erreurs de calcul des charges pondérées et des erreurs dans l'affectation des tâches aux processeurs.