La famine, un problème que connaît aussi l’informatique
Avant toute chose, il est important de définir quelques principes à maîtriser pour bien comprendre ce phénomène de famine, qui peut se révéler problématique lors de la conception d’applications diverses.
Quelques bases
Premièrement, définissons ce qu’est un thread. Un thread est un mot anglais pouvant être traduit par un une tâche, un fil d’instruction chargé d’exécuter une partie du processus mais il est aussi couramment employé en français pour désigner un fil, une ficelle. Un processus contient donc au moins un thread, celui où démarre l’exécution du processus, et peut être découpé en plusieurs. Un thread correspond donc à une unité d’exécution, une séquence d’instructions déroulées séquentiellement qui peut être exécutée en parallèle d’une autre ou non.
On remarque bien sur la précédente illustration que les threads sont exécutés successivement, mais rapidement pour donner l’illusion de simultanéité. Quand les threads sont exécutés les uns à la suite des autres et qu’un seul coeur du processeur est utilisé, il s’agit de mono-threading. Quand ils sont exécutés parallèlement sur différents coeurs du processeur, il s’agit de multi-threading.
Il existe une technique de programmation permettant, grâce à une fonction, l’exécution en parallèle de plusieurs threads en même temps sur les différents cœurs du processeur. Si le processeur ne possède qu’un cœur, les threads suivront une même file d’exécution très rapide pour donner cette impression de parallélisme. Or, la plupart du temps, il y a plus de threads à exécuter que de cœurs du processeur disponibles.
Priorité et famine
Maintenant se pose donc la question : quel thread sera le prochain à accéder à la ressource (variable, fichier ou autre) ?
Le système d’exploitation joue un rôle majeur dans ce choix. Un composant de son noyau est conçu pour répondre à cette problématique. C’est l’ordonnanceur. Il permet à chacun des threads d’avoir accès à la ressource à un moment donné et utilise la meilleure stratégie d’ordonnancement selon l’utilisation globale.
C’est ici qu’une nouvelle notion primordiale fait son apparition : la priorité ! À chaque thread est affecté une priorité qui déterminera s’il doit avoir accès à la ressource de calcul avant les autres ou pas.
Prenons l’exemple du langage de programmation Java : la priorité d’un thread est représentée par un entier entre 1 et 10. Plus la priorité est élevée, plus tôt le thread aura accès à la ressource de calcul. Les threads très importants auront une priorité de 10, les threads ayant une priorité de 1, « les tâches de fonds », sont exécutés quand les autres sont inactifs. La priorité par défaut est, logiquement, de 5.
Voici un tableau reprenant le comportement de l’ordonnanceur et des choix qu’il fait au cours du temps. Chaque processus a un certain temps d’exécution, ici “Burst Time”, et une priorité précisée dans la colonne “Priority”. Les valeurs en bas correspondent au temps d’exécution de chaque processus exécutés les après les autres. On remarque que l’ordonnanceur choisit le processus 2 en dernier car il a bien la priorité la plus faible. Il est donc important de définir une priorité si on veut être sur de l’ordre dans la file d’exécution. Toutefois, il existe un danger à jouer avec les priorités de manière inconsciente. Le comportement d’une application peut différer d’une plateforme à l’autre. Il est possible que cela altère le comportement des cycles des processeurs et créée une situation problématique où un thread n’a plus accès à la ressource et reste en attente infinie.
On appelle ce phénomène la famine. Selon le scénario, ce n’est pas toujours le thread à faible priorité qui sera en état de famine. Prenons trois threads N1, N2 et N3 avec une priorité croissante. Si N1 attend une ressource verrouillée par N2 et N3 attend une ressource verrouillée par N1, N3 se retrouve en état de famine malgré sa forte priorité.
Une situation de famine peut également être la cause d’une mauvaise gestion des structures de contrôle, telle que des boucles infinies bloquant la ressource pendant un temps indéfini.
Mais comment éviter cette mauvaise gestion des tâches attribuées au processeur ?
Un premier élément de réponse serait d’éviter de jouer avec les priorités de threads sans aucune raison valable. Il faut que le changement soit primordial au bon fonctionnement de l’application car différentes plateformes d’exécution ne réagissent pas forcément de la même manière face à une situation de famine.
Puis, on peut aussi penser à un ajustement dynamique des priorités en fonction du temps d’attente mais cela augmenterait fortement la consommation en mémoire.
Enfin une politique « First In First Out » d’ordonnancement contrerait ce problème mais elle n’est pas équitable sur le temps d’attente par rapport au temps d’utilisation. Le traitement moyen serait donc plus élevé.
Pour conclure
On peut donc affirmer qu’il est très difficile de concevoir une application performante tout en garantissant qu’une situation de famine ne se déclare pas au cours de son exécution. Mais en réfléchissant bien à la politique d’ordonnancement adaptée à l’application, on peut s’en sortir sans impact notoire.
Sources:
- Brian Goetz, “Programmation concurrente en Java”, publié le 14 septembre 2011, page 222.
- https://apais.developpez.com/tutoriels/c++/multithread/#LIII-D
- https://netjs.blogspot.com/2017/10/thread-starvation-in-java-multi-threading.html
- https://www.geeksforgeeks.org/starvation-aging-operating-systems/