Passage de l’état Running à l’état Blocked¶

Le passage de l’état Running à l’état Blocked advient lors de l’exécution d’un appel système bloquant appelé par le thread. Cet appel système bloquant peut être, par exemple, une demande d’entrée/sortie (écrire ou lire depuis le système de fichiers) ou un appel à une primitive de synchronisation comme par exemple pthread_mutex_lock(3posix) ou sem_wait(3posix). Les threads en état Blocked sont associés à une structure de donnée du noyau, qui joue le rôle de salle d’attente. Certaines de ces structures d’attente n’ont d’utilité que pour un seul thread, par exemple lorsque ce thread a demandé une lecture vers le système de fichiers. D’autres peuvent contenir plusieurs threads en attente. C’est le cas, par exemple, d’une structure d’attente pour un sémaphore. Il peut y avoir effectivement plusieurs threads ayant appelé sem_wait(3posix) (T12, T4 et T10). Un appel à sem_post(3posix) va libérer l’un de ces threads, qui passera alors en état Ready.

Passage de l’état Running à l’état Ready¶

Un thread passe de l’état Running à l’état Ready lorsqu’il libère le processeur sur lequel il exécute actuellement des instructions.

On observe qu’avec uniquement les mécanismes définis précédemment, un thread qui ne génère aucun appel système pourrait rester dans l’état Running indéfiniment. C’est le cas, par exemple, d’un thread bloqué dans une boucle infinie ne comportant pas d’appel à la librairie standard. Si tous les processeurs venaient à être bloqués par des threads dans cette situation, alors la machine devient inutilisable. Par ailleurs, sans même considérer des boucles infinies, le temps d’occupation du processeur par le thread en cours d’exécution (son CPU burst) pourrait être particulièrement long, ce qui peut être problématique lorsque d’autres threads sont sujets à des contraintes de réactivité (par exemple, la réaction aux commandes utilisateurs ou la visualisation).

Les systèmes comme Linux utilisent donc une source d’interruption matérielle périodique (une horloge système) pour permettre de redonner le contrôle au système d’exploitation. À l’occasion de ces traitements d’interruption, il est possible de reprendre un processeur à un thread en état Running, en provoquant un changement de contexte. On dit alors que le thread a subit une préemption. C’est le cas de T15 sur notre exemple.

Passage de l’état Ready à l’état Running¶

La dernière transition consiste à restaurer l’état précédemment sauvegardé d’un thread en état Ready sur un processeur, et à reprendre son exécution.

Objectifs¶

Il n’existe pas de scheduler parfait convenant à toutes les applications. Pour s’en convaincre, considérons les deux applications que sont la copie de fichier et l’application de calcul dans notre exemple précédent.

La priorité de l’application de copie de fichier est de subir le moins d’attente possible entre la disponibilité d’une valeur de retour d’un appel système vers le système de fichier, et l’envoi du prochain appel système pour continuer la copie, et éviter de ralentir l’opération de copie dans son ensemble. Pour ce thread, le délai d’attente entre sa mise en état Ready et l’obtention d’un processeur doit être la plus faible possible.

Pour l’application de calcul, le plus important est de pouvoir exécuter les instructions du long CPU burst avec le moins d’interruptions possibles. En effet, un changement de contexte est du temps perdu pour réaliser des opérations utiles (i.e., progresser dans la simulation). Par ailleurs, un thread qui est interrompu et replacé plus tard sur le processeur sera soumis à un phénomène de cache froid : les données qui étaient dans le cache, et donc accessibles avec un temps d’accès faible avant le changement de contexte, ont pu être remplacées par des données à des adresses différentes, utilisées par le thread qui a obtenu le processeur entre temps. Peupler de nouveau le cache avec les données nécessaire au calcul peut nécessiter de coûteux accès en mémoire principale et ralentir l’exécution.

Si l’on décide de privilégier l’application de copie, il est souhaitable d’interrompre le thread de l’application de calcul, mais cela va au détriment de ce dernier. À l’inverse, si on choisit de privilégier l’opération de calcul, alors l’opération de copie sera ralentie.

On peut définir cinq principaux critères pour mesurer la performance d’un scheduler :

• Du point de vue du système dans son ensemble tout d’abord :

• On veut pouvoir maximimiser l’utilisation du ou des processeur(s), c’est à dire la proportion du temps où ceux-ci exécutent des instructions des applications. Les opérations de changement de contexte ne sont évidemment pas considérées comme du travail utile pour ce critère.
• On peut vouloir maximiser le débit applicatif, c’est à dire le nombre de processus qui peuvent terminer leur exécution en une unité de temps donné (par exemple en une heure).

• D’autres critères sont applicables, cette fois-ci du point de vue de chaque application individuellement. On pourra par ailleurs s’intéresser à la distribution de ces métriques pour l’ensemble des applications, afin de savoir s’il existe un déséquilibre entre la métrique telle que perçue par une application et la même métrique perçue par une autre application :

• Une application peut souhaiter minimiser son temps total d’exécution, entre la création du processus et sa terminaison. Ce critère n’est pas nécessairement valide pour tous les types d’applications, par exemple il n’a que peu de sens pour une application interactive (par exemple, un shell), mais il est important pour des applications de calcul ou l’exécution d’un script par exemple.
• Ensuite, une application peut souhaiter minimiser le temps d’attente moyen, c’est à dire le temps écoulé entre la mise en état Ready (par exemple après la fin d’une entrée/sortie) et l’obtention d’un processeur. Cette métrique est particulièrement importante pour les applications interactives, comme un jeu ou une interface graphique.
• Enfin, une application voudra minimiser son temps de réponse, qui correspond à la somme entre le temps d’attente et le temps nécessaire pour terminer l’exécution de son burst CPU.

Nous allons dans la suite de ce chapitre décrire plusieurs scheduler classiques, en commençant par les scheduler non préemptifs, puis les schedulers préemptifs, et enfin les schedulers hybrides combinant plusieurs stratégies.

Note : Nous considérerons pour la présentation des schedulers uniquement le cas d’un seul processeur pour des raisons de simplicité, mais les algorithmes présentés ici peuvent être aisément étendu pour fonctionner avec plusieurs processeurs.

Le scheduler FCFS (First-Come-First-Serve)¶

Une première approche est d’exécuter les CPU bursts des threads dans l’ordre exact dans lequel ils ont obtenu l’état Ready (premier arrivé, premier servi). Ce scheduler n’étant pas préemptif, chaque CPU burst s’exécute intégralement avant de libérer le processeur pour un autre thread. Le temps de réponse avec un scheduler non préemptif est toujours égal au temps d’attente plus la durée du burst CPU, donc nous nous intéresserons principalement à ce premier critère.

L’exemple ci-dessous montre deux exécutions possibles pour 4 threads disponibles en état Ready simultanément, mais pour lesquels l’ordre d’ajout en état Ready a été effectué dans un ordre différent (T1, T2, T3, puis T4 dans un premier cas; et T2, T3, T4 puis T1 dans le deuxième cas).

Ces figures présentent des diagrammes de Gantt, où le temps d’exécution de chaque CPU burst est représenté au cours du temps. En terme de débit applicatif et d’utilisation du processeur, cet algorithme est optimal, car il n’y a que trois changements de contexte : le temps perdu pour ces changements de contexte est donc minimal.

En revanche, si on considère le temps d’attente moyen pour chacun des threads, on observe que celui-ci diffère grandement entre le premier ordre d’arrivée et le second (de 7 unités de temps à 4.75 unités de temps). La raison est que dans la première configuration des CPU bursts courts (typiques des applications interactives ou utilisant de nombreuses entrées/sorties) se retrouvent coincées derrière un CPU burst long. Ce phénomène est appelé l’effet convoi (convoy effect en anglais). Il pénalise principalement les applications ayant des besoins d’interactivité.

Le scheduler SJF (Shortest Job First)¶

Le scheduler SJF (Shortest Job First) est un scheduler non préemptif qui a pour objectif de prévenir l’effet convoi. Lorsque plusieurs threads sont disponibles, le thread choisi est celui qui a le CPU burst à venir qui est le plus court. La figure ci-dessous montre le diagramme de Gantt où les threads obtiennent le processeur dans l’ordre du plus courte au plus long CPU burst.

On peut facilement montrer que le temps d’attente moyen avec le scheduler SJF est le meilleur possible : toute permutation d’ordre ne peut qu’augmenter ce temps d’attente moyen. Toutefois, cet algorithme n’est pas réalisable en pratique et ne peut donc servir que de mètre étalon pour analyser la performance d’autres algorithmes. Il n’est en effet pas possible de connaître à l’avance la durée d’un CPU burst, car celle-ci dépend de l’exécution du code du thread, et donc de ses boucles, conditionnelles, appels de fonctions, etc.

En revanche, il est possible de tenter d’approcher cet algorithme en partant de l’observation suivante : la durée des CPU bursts pour un thread donné a souvent tendance à être régulière dans le temps. C’est à dire qu’un thread utilisant le CPU pour de courtes périodes de temps régulièrement aura souvent tendance à répéter ce comportement (c’est le cas, par exemple, des trois threads du jeu présenté précédemment). À l’inverse, un thread utilisant régulièrement le CPU pour de longues périodes de temps sera souvent (mais pas toujours) plus susceptible d’avoir un prochain CPU burst qui sera long.

Un scheduler estimant SJF pourrait ainsi conserver dans une structure de données la durée des x derniers CPU bursts de chaque thread. En appliquant une moyenne sur cette durée, le scheduler peut alors tenter de prédire la durée du prochain CPU burst, et choisir le thread dont la durée prédite est la plus courte.

On note toutefois que, si SJF est optimal en terme de temps d’attente moyen, il n’offre que peu de propriétés d’équité. Si il existe de nombreux threads avec des CPU bursts à venir courts (ou prédits comme tels) alors un thread avec un CPU burst long (ou prédit comme tel) pourrait ne jamais avoir accès au processeur, ou bien n’y avoir accès que bien plus tard.

Le scheduler préemptif RR (Round Robin)¶

Un scheduler préemptif peut choisir de préempter un thread en cours d’exécution sur un processeur, c’est à dire de passer ce thread en état Ready pour libérer le processeur pour un autre thread. Une décision de préemption peut être prise lorsque le système d’exploitation reprend la main sur le processeur lors de l’arrivée d’une interruption. Une horloge système dédiée à cet usage génère une interruption matérielle (tick) de manière périodique.

Un premier scheduler préemptif est le scheduler RR (Round Robin), expression anglaise que l’on pourrait traduire en français par “chacun son tour” [1]. Les threads en mode Ready sont placé dans un ordre arbitraire, sur laquelle on boucle (une fois la fin de cet ordre atteint, on recommence avec le premier thread, et ainsi de suite). À chaque tick d’horloge, le scheduler décide de systématiquement préempter le thread en cours d’exécution, sauf s’il n’existe aucun autre thread en état Ready. Le thread choisi pour passer en état Running est alors le suivant dans la liste. Celui-ci peut alors exécuter une fraction de son burst CPU avant d’être lui même préempté. La figure suivante illustre ce principe avec les mêmes threads que dans les exemples précédents, et avec un tick d’horloge toutes les deux unités de temps.

On observe que le thread T1 n’exécute que deux unités de temps sur les 7 de son burst CPU avant d’être préempté pour laisser la place à T2, qui laisse la place à T3 et ainsi de suite. Le troisième accès du thread T3 au processeur permet à ce thread de terminer son burst par une opération bloquante. .. On suppose dans cet exemple que le système d’exploitation remet l’horloge à 0 suite à la fin du thread en cours (ce n’est pas obligatoire).

Le scheduler RR permet à chaque thread d’accéder au processeur équitablement : même si un thread comme T1 ou T4 a un burst CPU long, les threads avec des bursts CPU courts comme T2 ou T3 auront accès au processeur de la même manière. En d’autres termes, le temps d’attente pour un thread sera toujours borné par le nombre de threads en état Ready multiplié par le durée du pas de temps.

On voit toutefois que ce scheduler n’est pas très efficace pour plusieurs raisons :

• Premièrement, il génère un grand nombre de changements de contexte (7 dans notre exemple). Comme discuté précédemment, non seulement ces changements de contexte nécessitent du temps processeur qui n’est pas utilisé pour des opérations utiles, mais ils entrainent surtout un phénomène de cache froid à chaque redémarrage d’un thread sur le processus à la suite d’un autre ayant rempli le cache avec ses propres données.
• Deuxièmement, comme le burst CPU d’un thread peut être interrompu avant sa complétion, il n’y a pas de relation directe entre le temps d’attente et le temps de réponse, et ce dernier peut devenir particulièrement long. Par exemple, bien que T3 ait un temps d’attente de 3 unités de temps, son temps de réponse (le temps entre son placement en état Ready et la fin de son burst CPU) est de 11 unités de temps.
• Enfin, il n’y a pas de distinction entre les threads ayant besoin du processeur pour des bursts courts ou ceux ayant des bursts longs, ce qui peut conjointement réduire la réactivité des threads interactifs ou effectuant de nombreuses entrées/sorties et diminuer la performance de ceux réalisant des calculs.

Schedulers à priorité¶

Dans un même système informatique, plusieurs applications cohabitent et toutes n’ont pas nécessairement la même priorité d’accès aux ressources. Par exemple, lors de l’utilisation d’une interface utilisateur en mode graphique, l’application actuellement utilisée par l’utilisateur local (par exemple un navigateur web) peut avoir besoin pour assurer une bonne réactivité d’accéder plus rapidement au processeur afin de limiter ses temps de réponses. À l’inverse, une opération de maintenance utilisée par le système d’exploitation, comme la mise à jour d’une base de données des fichiers pour permettre la recherche rapide par la suite, peut se contenter d’accéder au processeur uniquement lorsque celui-ci n’est pas sollicité par d’autres applications.

Un scheduler à priorité alloue à chaque thread un niveau de priorité donné. Lorsque le scheduler doit sélectionner un thread à exécuter, il commence d’abord par parcourir les threads ayant une haute priorité. En pratique, un scheduler à priorité maintiendra une liste circulaire pour chaque niveau de priorité. Lorsque le scheduler est appelé, il sélectionnera toujours le thread ayant la plus haute priorité et se trouvant dans l’état Ready. Si plusieurs threads ont le même niveau de priorité, un scheduler de type round-robin peut être utilisé dans chaque niveau de priorité. Il faut toutefois faire attention au problème de famine : si il existe toujours des threads de plus haute priorité qu’un thread donné, ce dernier pourrait ne jamais obtenir l’accès au processeur. Une solution simple à ce problème est de considérer une priorité de base, et une priorité courante. Au démarrage d’un cycle, les threads reçoivent leur priorité de base. Lorsqu’ils obtiennent l’accès au processeur, leur priorité courante décroit. Ceci donne une opportunité aux threads de priorité de base plus faible de s’exécuter. Un nouveau cycle commence lorsque tous les threads en état Ready ou Running ont atteint une priorité courante de 0.

On peut combiner le principe de priorité avec celui de préemption. Un thread qui passe dans l’état Running obtient alors un crédit de temps, ou quantum. Lors de l’allocation d’un processeur à un thread, le kernel démarre une temporisation avec ce quantum, correspondant à un certain nombre de clicks de l’horloge système (la longueur du quantum doit donc être un multiple de la période de cette horloge). Si un burst CPU atteint la fin de son quantum avant de réaliser une opération bloquante, celui-ci est préempté.

Les systèmes UNIX utilisent souvent des schedulers à priorité dynamique avec un round-robin à chaque niveau de priorité, en ajoutant par ailleurs des mécanismes adaptant la priorité de base des threads pour favoriser les threads interactifs. Par exemple, un thread qui termine toujours ses quantum de temps en étant préempté est considéré comme intensif en processeur (CPU-intensive). Il se verra allouer une priorité de base plus grande, mais avec un quantum de temps plus long. En revanche, un thread qui termine toujours ses bursts CPU avant la fin des quantum alloués est considéré comme intensive en entrées/sorties (interactive). Ce thread pourra obtenir une priorité de base plus élevé, mais associée à un quantum de temps plus court.