Cours

Les transparents du cours sur RT-POSIX sont disponibles ici.

TP

Introduction

Dans ce TP, nous allons nous intéresser à l’implémentation d’un sous-ensemble des modèles de tâches vus en cours d’ordonnancement mono-cœur.

Plus précisément, nous allons implémenter:

1. Un lot de tâches périodiques et sporadiques ordonnancés selon la politique RMS (Rate Monotonic Scheduling)
2. Un verrou utilisant la politique PCP

Voici quelques indications avant de commencer :

• Pour s’assurer qu’un programme prog s’éxecute sur un seul cœur alors que la machine dont vous disposez est multi-cœur, nous utiliserons dans ce TP l’utilisaire taskset. Voici deux exemples simple :

$ taskset –c 0 prog

Cette commande lance l’exécution du programme prog en forçant son allocation sur un seul cœur de la machine.

$ taskset –c 0 sudo prog

Cette commande lance l’exécution du programme prog en mode super utilisateur et en forçant son allocation sur un seul cœur de la machine.

• Certaines API utilisés dans ce TP nécessitent d’être utilisateur privilégié sous UNIX. Vous devrez donc faire ce TP sur une machine virtuelle. Suivez les instructions qui vous sont données en début de TP pour lancer la machine virtuelle.

• L’archive du TP, dans sa version « plus facile » se trouve ici. Une version plus difficile se trouve ici. Notez qu’un Makefile vous est fourni et que l’édition de lien s’appuie sur les librairies système « rt » et « pthread ». Ces librairies contiennent respectivement le code des fonctions liées aux horloges et au API pthread_***. Les parties à compléter sont clairement identifiés dans l’archive fournie. Normalement, vous ne devez pas modifier le code fournis en dehors des emplacements indiqués. Ceci dit, libre à vous de le faire si vous en avez besoin … Le nombre de ligne de code à ajouter n’est pas indiqué, à vous de proposer la solution qui vous paraît adéquate.

• En dehors des types de donnée POSIX, les types de données utilisés dans ce TP sont définis dans le fichier thread_ports.h

• Dernier petit conseil avant de commencer : envoyez-vous votre solution par email en fin de TP, le système de fichier de la machine virtuelle n’est pas synchronisé avec le système de fichier que vous utilisez habituellement.

Implémentation de tâches périodiques

Nous allons commencer ce TP par une implémentation de tâches périodiques. Vous devez donc compléter l’archive fourni afin d’obtenir un lot de 2 tâches périodiques, T1 et T2, ordonnancées selon la politique d’ordonnancement RMS vue en cours. T1 est de période 1000 ms et T2 de période 2000 ms.

Les instructions associées à cette partie du TP sont identifiées dans les fichiers main.c et threads_dispatch.c via les commentaires

/* Q1 : …

Nous allons décomposer ce problème en plusieurs sous-problèmes:

1. Le main doit attendre (indéfiniment) la fin des tâches T1 et T2.
2. Il faut mettre à jour la priorité des threads (dans threads_dispatch.c) pour que les threds soient effectivment créés (voir commentaire /* Q1: … dans threads_dispatch.c).
3. Les tâches T1 et T2 ne doivent commencer leur exécution, en même temps, après initialisation de chacune d’entre elle. Il faut donc implémenter une barrière de sorte que T1 attende que T2 soit prête à démarrer et inversement. Une fois que toutes les tâches sont prêtes, le thread principale le libère.
4. Après une exécution, la tâche T1 attend jusqu’à sa prochaine date de réveil. Pour éviter les dérives, nous allons calculer cette date de prochain réveil à partir d’une date de début. Cette date est mise à jour dans le thread principal via l’appel à la fonction set_start_time. Le code correspondant à la détermination de la date de début est fourni, mais il faut implémenter le code d’attente (fonction await_periodic_dispatch). La structure periodic_thread_t contient pour cela le champ iteration_counter (compteur du nombre d’itération de la tâche) et un champ period qui correspond à la valeur de la period de la tâche. La date de prochain réveil, après une itération i-1, est:
   start_date+Période*i.

A l’issue de cette partie, vous devez obtenir une trace d’exécution du type :

$taskset -c 0 sudo ./first_rt_posix_app
Start thread T1 - date: 0 sec: 7357 nsec - iteration 0
Finish thread T1
Start thread T2 - date: 0 sec: 400106240 nsec - iteration 0
Start thread T1 - date: 1 sec: 9877 nsec - iteration 1
Finish thread T1
Finish thread T2
Start thread T1 - date: 2 sec: 9028 nsec - iteration 2
Write in index 1, 3 
Finish thread T1
Start thread T2 - date: 2 sec: 400043476 nsec - iteration 1
Start thread T1 - date: 3 sec: 3544 nsec - iteration 3
Finish thread T1
Finish thread T2
Start thread T1 - date: 4 sec: 7737 nsec - iteration 4
Finish thread T1
Start thread T2 - date: 4 sec: 400046013 nsec - iteration 2
Start thread T1 - date: 5 sec: 4525 nsec - iteration 5
Write in index 2, 6 
Finish thread T1
Finish thread T2
Start thread T1 - date: 6 sec: 5687 nsec - iteration 6
Finish thread T1
Start thread T2 - date: 6 sec: 400026420 nsec - iteration 3
Start thread T1 - date: 7 sec: 6076 nsec - iteration 7
Finish thread T1
Finish thread T2
Start thread T1 - date: 8 sec: 9369 nsec - iteration 8
Write in index 3, 9 
Finish thread T1
Start thread T2 - date: 8 sec: 400035466 nsec - iteration 4
Start thread T1 - date: 9 sec: 5558 nsec - iteration 9
Finish thread T1
Finish thread T2
Start thread T1 - date: 10 sec: 9625 nsec - iteration 10
Finish thread T1
Start thread T2 - date: 10 sec: 400032501 nsec - iteration 5
Start thread T1 - date: 11 sec: 3601 nsec - iteration 11
Write in index 4, 12 
Finish thread T1
Finish thread T2
Start thread T1 - date: 12 sec: 9200 nsec - iteration 12
Finish thread T1
Start thread T2 - date: 12 sec: 400033450 nsec - iteration 6
Start thread T1 - date: 13 sec: 5835 nsec - iteration 13
Finish thread T1
Finish thread T2
...

Ce qu’il est important de vérifier sur la trace:

• La tâche T1 n’est jamais pré-emptée par la tâche T2
• Les dates de démarrage de T1 correspondent bien à i*Période ou i est le compteur du nombre d’itérations de T1. La gigue sur la date de démarrage en question doit être relativement faible, et il ne doit pas y avoir de dérive.
• Les dates de démarrage de T2 correspondent bien à (i*Période+temps d’exécution de T1).

Interblocage et PCP

Le second exercice va consister à configurer et utiliser des verrous, lock1 et lock2, pour simuler un accès à des données partagées. Les instructions associées à cette partie du TP sont identifiées dans les fichiers main.c via les commentaires

/* Q2_a : …

Dans un premier temps, n’utilisez pas la politique PCP et observez un interblocage.

Vous devez obtenir la trace d’exécution suivante (le lot de tâche est en deadlock):

taskset -c 0udo ./first_rt_posix_app
Start thread T1 - date: 0 sec: 7685 nsec - iteration 0
Finish thread T1
Start thread T2 - date: 0 sec: 400104199 nsec - iteration 0
Start thread T1 - date: 1 sec: 5052 nsec - iteration 1

Dans un deuxième temps, utilisez la politique PCP et observez que l’interblocage est résolu. Les instructions associées à cette partie du TP sont identifiées dans les fichiers main.c via les commentaires:

/* Q2_b : …

La trace d’exécution à observer est la même qu’à la partie 1.

Implémentation de tâches sporadiques

Nous allons maintenant implémenter une tâche sporadique, c’est à dire un tâche aprériodique avec un délai minimal entre deux réveils. Nous considérons une tâche sporadique T3, dont la période (délai minimal entre deux réveils) est de 6000 ms. T3 est réveillé sur réception de messages envoyées par T1 (T1 envoie un message 1 fois sur trois). Ces messages sont stockés dans une file d’attente implémentée par un tableau circulaire. La structure de donnée, ainsi que les fonctions de manipulations de cette file d’attente sont données (voir l’initialisation de T3_info et le code associé dans threads_ports.c).

Les instructions associées à cette partie du TP sont identifiées dans les fichiers main.c et threads_dispatch.c via les commentaires

/* Q3 : …

Il est fortement recommandé de lire le code des fonctions ReceiveInputs_runtime, NextValue_runtime, SendOutput_runtime ainsi que leur usage dans le fichier main.c afin de comprendre le fonctionnement de la file de message.

Vous devez obtenir la trace d’exécution suivante :

taskset -c 0 sudo ./first_rt_posix_app
Start thread T1 - date: 0 sec: 4293 nsec - iteration 0
Finish thread T1
Start thread T2 - date: 0 sec: 400060462 nsec - iteration 0
Start thread T1 - date: 1 sec: 4501 nsec - iteration 1
Finish thread T1
Finish thread T2
Start thread T1 - date: 2 sec: 49159 nsec - iteration 2
Write in index 1, 3 
Finish thread T1
Start thread T2 - date: 2 sec: 400101536 nsec - iteration 1
Start thread T1 - date: 3 sec: 9510 nsec - iteration 3
Finish thread T1
Finish thread T2
Receive inputs: number of discarded messages is 0
Receive inputs: first: 0, last: 1
Start thread T3
T3, received data: 0
Start thread T1 - date: 4 sec: 5257 nsec - iteration 4
Finish thread T1
Start thread T2 - date: 4 sec: 400026456 nsec - iteration 2
Start thread T1 - date: 5 sec: 26320 nsec - iteration 5
Write in index 2, 6 
Finish thread T1
Finish thread T2
Finish thread T3
Start thread T1 - date: 6 sec: 24646 nsec - iteration 6
Finish thread T1
Start thread T2 - date: 6 sec: 400055912 nsec - iteration 3
Start thread T1 - date: 7 sec: 5494 nsec - iteration 7
Finish thread T1
Finish thread T2
Start thread T1 - date: 8 sec: 64738 nsec - iteration 8
Write in index 3, 9 
Finish thread T1
Start thread T2 - date: 8 sec: 400121274 nsec - iteration 4
Start thread T1 - date: 9 sec: 5013 nsec - iteration 9
Finish thread T1
Finish thread T2
Receive inputs: number of discarded messages is 1
Receive inputs: first: 2, last: 3
Start thread T3
T3, received data: 6
Start thread T1 - date: 10 sec: 7885 nsec - iteration 10
Finish thread T1
Start thread T2 - date: 10 sec: 400054705 nsec - iteration 5
Start thread T1 - date: 11 sec: 5118 nsec - iteration 11
Write in index 4, 12 
Finish thread T1
Finish thread T2
Finish thread T3
Start thread T1 - date: 12 sec: 36662 nsec - iteration 12
Finish thread T1
Start thread T2 - date: 12 sec: 400098384 nsec - iteration 6
...

Question complémentaire (difficile): en considérant la structure de donnée et les fonctions de communication implémentées dans threads_ports.c, expliquez comment ce code traite les risques d’interblocages sur accès aux files d’attentes de messages échangés entre threads.

La correction de ces exercices vous est fournie ici. Elle propose une solution pour chaque partie, en identifiant le code correspondant avec les macros Sol_q1, Sol_q2_a, Sol_q2_b, et Sol_q3.

Une variante de la solution à la parti 1 est également fournie, cette solution implémente le modèle de tâches périodiques en s’appuyant sur la génération périodique de signaux grâce à des timers.

Exercices supplémentaires

verrou à héritage de priorité

On va utiliser les extensions temps réel de la bibliothèque de threads POSIX pour faire hériter un thread de la priorité du verrou qu’il vient de prendre.
On met en jeu deux threads T0 et T1 et un verrou M1 tels que :

 
Priorité de M1 > Priorité de T1 > Priorité de T0.

Scénario : main va créer un thread T0 et un verrou M1 dont l’attribut est PRIO_PROTECT. Ensuite main attend la fin de T0. Le thread T0 va créer le thread T1, puis prendre le verrou M1 (dont il hérite la priorité). Ensuite il éléve la priorité de T1 à une priorité supérieure à la sienne. Mais T1 ne va PAS démarrer puisque T0 a hérité de la priorité de M1. Lorsque T0 rend M1 (unlock), T1 démarre.

fonctionnement de main :
crée un verrou M1 dont la priorité est MAX-5
crée ensuite une thread T0
attend la fin de la thread T0

fonctionnement de T0:
crée une thread T1
fait un lock sur le verrou M1, donc éléve sa propre priorité à MAX-5.
éléve la priorité de T1 à (MAX-10). T1 ne doit donc pas démarrer parce qu'on a maintenant : Prio(T0) > Prio(T1).
effectue un calcul
fait unlock sur le verrou M1
attend la fin de la thread T1
se termine

fonctionnement de T1 :
effectue un calcul
fait un trylock sur le verrou M1
effectue un calcul
fait unlock sur le verrou M1
se termine

Le programme à compléter se trouve ici . La trace de l’exécution doit ressembler à la suivante :

main : tid de main : 0x00000001
main : Prio. min et max en FIFO : 0 59
main : main-setshared-status = 0
main : mutexattr_setprotocol = 0
main : ceiling de M1 = 54
main : mutexattr_getprotocol = 32
protocole du mutex : PTHREAD_PRIO_PROTECT
Task 0 : tid de Task 0  : 0x00000002
Task 0 : AVANT lock(M1) - priorite = 0
Task 0 : lock, status = 0
Task 0 : apres lock(M1) - priorite = 0
policy : FIFO
Task 0 : creation de Task_1, tid  : 0x00000003
Task 0 : getschedparam pour T1 - priorite = 0
Task 0 : getschedparam pour T1 - sched = 1
policy : FIFO
Task 0 : getschedparam pour T1 - priorite = 52
Task 0 : getschedparam pour T1 - sched = 1
policy : FIFO
Task 0 : debut de calcul
Task 0 :  i = 0
Task 0 :  i = 1000000
Task 0 :  i = 2000000
Task 0 :  i = 3000000
Task 0 :  i = 4000000
Task 0 :  i = 5000000
Task 0 :  i = 6000000
Task 0 :  i = 7000000
Task 0 :  i = 8000000
Task 0 : fin de calcul
Task 1 (3) : debut de calcul
Task 1 :  i = 0
Task 1 :  i = 1000000
Task 1 :  i = 2000000
Task 1 :  i = 3000000
Task 1 :  i = 4000000
Task 1 :  i = 5000000
Task 1 :  i = 6000000
Task 1 :  i = 7000000
Task 1 :  i = 8000000
Task 1 (3): fin de calcul
Task 1 (3): essaie de prendre M1
Task 1 (3): trylock, status = 0
Task 1 (3): mutex M1 pris, va calculer
Task 1 (3): exit
Task 0 : unlock M1 -status = 0
Task 0 : priorite  = 0
Task 0 : join T1, status = 0
main : creation de Task_0, tid  : 0x00000002
main : join T0, status = 0

inversion de priorité

On va maintenant illustrer le problème de l’inversion de priorité.
On met en jeu trois threads T0, T1 et T2 tels que :

Priorité de T2 > Priorité de T1 > Priorité de T0.

On utilise aussi un verrou M1.

Scénario :
main va créer les trois threads threads et le verrou M1.

Activité des threads :
– Le thread T0 prend le verrou M1.
– Le thread T1 fait d’abord sleep (4) puis démarre et exécute une très long travail,
– Le thread T2 fait d’abord sleep (2), démarre et essaie de prendre le verrou M1.

Déroulement du scénario :
– Le thread T0 démarre le premier et prend le verrou M1.
– Le thread T2 démarre ensuite et se bloque sur le verrou M1, déja pris par T0.
– Le thread T1 démarre alors et ne s’arrête pas. Il empêche T0, qui bloque T2 de rependre son exécution. T2 le plus prioritaire ne peut plus travailler (inversion de priorité).

Questions :

1. En vous inspirant de l’exemple précédent, on vous demande de mettre en oeuvre ce scénario et d’en constater le dysfonctionnement.

2. Donner au verrou les attributs convenables pour résoudre ce problème d’inversion de priorité. Exécuter le programme pour montrer le bon fonctionnement du scénario.

Scénario correct :
– Le thread T0 démarre le premier, prend le verrou M1et voit sa priorité AUGMENTEE au niveau de celle de T2.
– Le thread T2 démarre ensuite et se bloque sur le verrou M1, déja pris par T0.
– Le thread T1 se réveille mais ne prend pas la main parce que sa priorité est inférieure à celle de T0.
– Le thread T0 progresse dans sa section critique, fait unlock, perd sa priorité,
donc le thread T2, le plus prioritaire, reprend son exécution et entre dans sa section critique,