Analyse et ordonnancement d'un jeu de sept tâches périodiques sur un processeur unique : mesure du WCET par échantillonnage statistique, vérification de l'ordonnançabilité, puis construction d'un ordonnancement non préemptif optimal minimisant le temps d'attente total par Branch and Bound.
PDF Rapport complet11 pages · WCET, ordonnançabilité, Branch and Bound Télécharger → Voir sur GitHub →Le temps d'exécution d'une tâche calculant le produit de deux entiers aléatoires sur 512 bits n'est pas constant : il varie selon les opérandes et des événements bas niveau (défauts de cache, interruptions). Sur 10 000 essais chronométrés, le temps médian est de 1,1 μs mais le pire cas observé atteint 83,1 μs — le WCET est fixé à 84 μs avec une marge de sécurité. Cette distribution très asymétrique illustre pourquoi le temps moyen ne peut jamais servir de borne sûre en temps réel.
for _ in range(N):
a, b = random.getrandbits(512), random.getrandbits(512)
t_start = time.perf_counter()
_ = a * b
elapsed_us = (time.perf_counter() - t_start) * 1e6
timings.append(elapsed_us)
wcet_us = math.ceil(max(timings)) # arrondi supérieur, marge de sécurité
Le jeu de sept tâches périodiques présente une utilisation processeur U ≈ 0,646, largement sous la borne de Liu & Layland pour Rate Monotonic (≈ 0,729 pour n = 7 tâches). Le jeu est donc ordonnançable sous RM, et a fortiori sous EDF. L'analyse du temps de réponse sur l'hyperpériode (80 ms, plus petit commun multiple des périodes, 29 jobs) confirme qu'aucune échéance n'est dépassée.
Le temps d'occupation processeur étant fixe (51,184 ms sur l'hyperpériode), minimiser le temps d'attente total revient à maximiser le temps d'inactivité. L'algorithme explore les tâches prêtes par ordre EDF et élague les branches dont la borne inférieure optimiste dépasse déjà la meilleure solution trouvée.
def branch(time, ready, remaining, schedule, total_wait):
if total_wait + lower_bound_wait(time, remaining) >= best_wait:
return # élagage : ne peut pas battre la meilleure solution
for job in sorted(ready, key=lambda x: x["deadline"]): # ordre EDF
if finish > job["deadline"]:
continue # échéance stricte violée : rejeté
branch(finish, new_remaining, new_sched, total_wait + wait)
| Métrique | Valeur |
|---|---|
| Temps d'attente total | 82,184 ms |
| Temps d'inactivité total | 28,816 ms |
| Temps d'occupation total | 51,184 ms |
| Échéances manquées | 0 |
En autorisant la tâche τ5 à dépasser son échéance (les six autres restant strictes), l'ordonnanceur modifié produit exactement le même temps d'attente total (82,184 ms) : aucun job de τ5 ne dépasse en réalité son échéance dans la solution optimale. La marge de sa période (40 ms) suffit déjà à l'absorber sans conflit avec les tâches plus contraintes — relâcher cette contrainte n'apporte donc aucun bénéfice pour ce jeu de tâches précis.
← Retour au portfolio