PROFDINFO.COM

Votre enseignant d'informatique en ligne

L'ordonnanceur temps réel

Les états d'une thread

Lorsqu'une thread s'exécute, elle peut être dans un état bloqué ou prêt. Plus spécifiquement, elle peut être dans un des états suivants:

État d'un thread

Voici une courte description des états les plus importants:

QNX Neutrino met à notre disposition l'outil psin qui permet d'obtenir les états de chacune des threads, leur algorithme d'ordonnancement, leur priorité et une foule d'informations utiles et ce, pour tous les processus s'éxécutant sur le système.

L'ordonnancement des threads

L'exécution d'une thread peut être arrêtée pour trois raisons différentes:

  1. La thread est bloquée (elle sommeille, attend qu'un mutex se libère, etc.)
  2. La thread cède sa place (voir sched_yield)
  3. La thread est suspendue (une thread de plus haute priorité est prête à être exécutée).

Lorsque l'exécution d'une thread est arrêtée, l'ordonnanceur temps réel doit choisir une autre thread pour que cette dernière s'exécute. Puisque les threads sont gérées globalement, la thread choisie peut très bien appartenir à un autre processus. Lors de sa création, chaque thread se voit assigner une priorité variant de 0 à 255. Les niveaux supérieurs (64 à 255) sont réservés pour les processus du système d'exploitation temps réel. L'ordonnanceur possède une file d'exécution pour chaque niveau de priorité. À chaque fois qu'une thread tombe à l'état READY, elle est placée à la fin de la file correspondant à sa priorité:

La file des priorités

Lorsqu'une thread tombe à l'état bloquée, elle est retirée de sa file. La thread idle est une thread spéciale au niveau de priorité 0 et qui est toujours READY.

L'ordonnanceur choisira toujours pour exécution la thread qui est READY et qui a la plus haute priorité. Par exemple si la thread D est suspendue, l'ordonnanceur temps réel choisira d'exécuter la thread A. Si deux ou plusieurs threads sont READY et ont le même niveau de priorité, la thread choisie dépendra de l'algorithme d'ordonnancement de la thread en cours d'exécution. Par exemple, Lorsque la thread A sera arrêtée, l'ordonnanceur pourra choisir entre les threads A, B ou C. Son choix dépendra de l'algorithme d'ordonnancement de la thread A. Les algorithmes d'ordonnancement sont:

  1. FIFO (first-in, first-out) : une thread avec l'algorithme d'ordonnancement FIFO s'arrêtera si:
    • elle bloque ou cède sa place;
    • une thread de plus haute priorité devient READY.
  2. Tourniquet (ou Round-robin) : une thread avec l'algorithme d'ordonnancement tourniquet s'arrêtera si:
    • elle bloque ou cède sa place;
    • une thread de plus haute priorité devient READY;
    • son quantum est écoulée.

    Le quantum est la plus petite période de temps qu'une thread peut être exécutée (sous QNX Neutrino le quantum est égal à 4 fois la période de l'horloge - la période d'horloge est de 1 ms sur les processeurs de plus de 40MHZ et de 10 ms sur les processeurs de moins de 40MHZ - voir clock_getres). Lorsqu'une thread a écoulé son quantum, la prochaine thread avec le même niveau de priorité est exécutée. L'algorithme du tourniquet permet à plusieurs threads de même priorité de s'exécuter tour à tour. C'est l'algorithme le plus utilisé sous QNX.

     

  3. Sporadique: une thread avec l'algorithme d'ordonnancement sporadique s'arrêtera si:
    • elle bloque ou cède sa place;
    • une thread de plus haute priorité devient READY;
    • son budget initial est écoulé.

    L'algorithme d'ordonnancement sporadique est utilisé pour limiter le temps d'exécution d'un processus sur un intervalle de temps donné. Il permet de répondre à des évènements sporadiques sans compromettre l'exécution de threads plus critiques. Lorsque le budget initial est écoulé, le niveau de priorité de la thread est diminué. Après une certaine période de temps, le niveau de priorité de la thread sera rétabli à son niveau normal. Voici un exemple d'exécution d'une thread avec l'algorithme d'exécution sporadique:

  4. L'algorithme sporadique

    Dans l'exemple précédent, la thread de priorité N a épuisé son budget initial de 15 ms. Sa priorité tombe donc au niveau L. Après 40 ms (le temps de remplissage) le niveau de priorité de la thread est rétabli à N.

Lors de sa création la thread hérite du niveau de priorité et de l'algorithme d'ordonnancement de son parent. On peut lire et modifier le niveau de priorité et l'algorithme d'ordonnancement d'une thread grâce aux fonctions pthread_setschedparam et pthread_getschedparam.

Questions: Pouvez-vous classer les algorithmes d'ordonnancement du plus égoiste au plus altruiste?

Exercice

Voici quatre threads :

 

Priorité

Algorithme d’ordonnancement

État

A

12

Tourniquet

READY

B

10

FIFO

JOIN

C

Normale:11

Réduite:9

Sporadique

Budget initial: 2 quanta (8 ms)

READY

D

10

Tourniquet

READY

a) Donnez l'ordre dans lequel les threads se termineront si la thread C a un temps de remplissage de 3 quanta (12 ms).

b) Donnez l'ordre dans lequel les threads se termineront si la thread C a un temps de remplissage de 6 quanta (24 ms).

Quantum et efficacité

Si Q représente le quantum du système temps réel et O le temps que l'ordonnanceur temps réel prends pour exécuter l'algorithme d'ordonnancement, alors l'efficacité, c'est-à-dire la proportion de temps consacrée aux tâches utiles est donnée par la formule E = (Q-O)/Q.

Thread vs processus

Une thread peut être vue comme étant la plus petite unité d'exécution. Chaque thread a sa pile, son pointeur de programme et ses registres. En ce sens, un processus est alors un conteneur de threads. Le processus définit le contexte dans lequel les threads s'exécuteront. Le contexte contient les threads, le code exécutable, les données, les descripteurs de fichiers, les outils de synchronisation, etc. Voici l'illustration d'un processus:

Processus vs threads

Le processus est confiné à un espace mémoire adressable par toutes ses threads. Ainsi un pointeur vers une donnée est utilisable par toutes les threads d'un même processus.

Une application temps réel peut être réalisée à l'aide d'un ensemble de processus travaillant ensemble. D'ailleurs, le système d'exploitation temps réel QNX Neutrino lui-même est souvent décrit comme une équipe de processus.

Le démarrage de processus

Un processus peut créer un autre processus à l'aide des fonctions suivantes:

La fonction wait permet à un processus parent de suspendre son exécution jusqu'à ce qu'un de ses processus enfants meurt. Tragique n'est-ce pas?