Introduction aux systèmes d'exploitation
Bonjour, Habr ! Je souhaite vous présenter une série d'articles traduits d'une littérature que je trouve intéressante — OSTEP. Ce matériel explore en profondeur le fonctionnement des systèmes d'exploitation de type Unix, en particulier — le travail avec les processus, les différents planificateurs, la mémoire et d'autres composants similaires qui forment un système d'exploitation moderne. Vous pouvez voir l'original de tous ces matériaux ici . Je vous demande de prendre en compte que la traduction a été réalisée de manière non professionnelle (assez libre), mais j'espère que le sens général a été conservé.
Les travaux pratiques sur ce sujet peuvent être trouvés ici :
Autres parties :
Vous pouvez également visiter ma chaîne sur =)
Planification : File d'attente à rétroaction multi-niveaux
Dans cette leçon, nous allons discuter des problèmes de développement de l'une des approches les plus connues de
planification, qui s'appelle Multi-Level Feedback Queue (MLFQ). Le planificateur MLFQ a été décrit pour la première fois en 1962 par Fernando J. Corbató dans un système appelé
Compatible Time-Sharing System (CTSS). Ces travaux (y compris les travaux ultérieurs sur
Multics) ont ensuite été proposés pour le prix Turing. Le planificateur a été
ultérieurement amélioré et a pris une forme que l'on retrouve déjà dans
certaines systèmes modernes.
L'algorithme MLFQ tente de résoudre 2 problèmes fondamentaux qui se chevauchent.
Tout d'abord, il essaie d'optimiser le temps de rotation, qui, comme nous l'avons vu dans la leçon précédente, est optimisé par la méthode de lancement au début de la file d'attente des tâches les plus
courtes. Cependant, le système d'exploitation ne sait pas combien de temps va durer tel ou tel processus, et cela
est une connaissance nécessaire pour le fonctionnement des algorithmes SJF, STCF. Deuxièmement, MLFQ essaie de
rendre le système réactif pour les utilisateurs (par exemple, ceux qui sont assis et
fixent l'écran en attendant la fin de la tâche) et ainsi minimiser le temps
de réponse. Malheureusement, des algorithmes comme RR réduisent le temps de réponse, mais ont un impact très
négatif sur la métrique du temps de rotation. D'où notre problème : Comment concevoir un
planificateur qui répondra à nos exigences tout en ne sachant rien de la
nature du processus, en général ? Comment le planificateur peut-il apprendre les caractéristiques des tâches,
qu'il exécute et ainsi prendre de meilleures décisions de planification ?
Essence du problème : Comment planifier la soumission de tâches sans connaissance parfaite ?
Comment développer un planificateur qui minimise simultanément le temps de réponse
pour les tâches interactives tout en minimisant le temps de rotation sans connaissance préalable
du temps d'exécution de la tâche ?
Remarque : apprentissage d'événements passés
La file d'attente MLFQ est un excellent exemple d'un système qui apprend des
événements passés pour prédire l'avenir. De telles approches sont souvent
rencontrées dans les systèmes d'exploitation (et dans de nombreux autres domaines de l'informatique, y compris les branches
de prévisions dans le matériel et les algorithmes de mise en cache). De telles approches
s'avèrent efficaces lorsque les tâches ont des phases comportementales et sont donc prévisibles.
Cependant, avec une telle technique, il faut être prudent, car les prédictions peuvent facilement
s'avérer incorrectes et conduire le système à prendre de pires décisions que
sans aucune connaissance.
MLFQ : Règles de base
Examinons les règles de base de l'algorithme MLFQ. Bien qu'il existe plusieurs
implémentations de cet algorithme, les approches de base sont similaires.
Dans l'implémentation que nous allons examiner, le MLFQ comportera plusieurs
queues distinctes, chacune ayant une priorité différente. À tout moment,
une tâche prête à être exécutée se trouve dans l'une des queues. Le MLFQ utilise les priorités
pour décider quelle tâche exécuter, c'est-à-dire qu'une tâche avec une
priorité plus élevée (tâche provenant de la queue de la plus haute priorité) sera exécutée en premier.
Il est certain qu'il peut y avoir plus d'une tâche dans une queue particulière, de sorte
qu'elles aient toutes la même priorité. Dans ce cas, le mécanisme
RR sera utilisé pour planifier l'exécution parmi ces tâches.
Ainsi, nous en venons à deux règles de base pour le MLFQ :
Règle 1 : Si priorité(A) > Priorité(B), la tâche A sera exécutée (B ne le sera pas)
- Règle 2 : Si priorité(A) = Priorité(B), A et B seront exécutées en utilisant RR
- À partir de ce qui précède, les éléments clés de la planification MLFQ
sont les priorités. Au lieu d'assigner une priorité fixe à chaque
tâche, le MLFQ modifie sa priorité en fonction du comportement observé.
Par exemple, si une tâche passe constamment du temps à attendre une entrée du clavier,
le MLFQ maintiendra la priorité du processus à un niveau élevé, car c'est ainsi que
un processus interactif doit fonctionner. En revanche, si une tâche utilise de manière constante et
intensive le CPU pendant une longue période, le MLFQ abaissera sa
priorité. Ainsi, le MLFQ apprendra le comportement des processus au moment où ils fonctionnent
et adaptera son comportement.
Illustrons un exemple de l'apparence des queues à un moment donné
et obtenons quelque chose comme ceci :
Dans ce schéma, 2 processus A et B se trouvent dans la queue de la plus haute priorité. Le processus
C est au milieu, et le processus D à la fin de la queue. Selon les descriptions ci-dessus
de l'algorithme MLFQ, le planificateur n'exécutera que les tâches de la plus haute priorité.
Selon la description de l'algorithme MLFQ, le planificateur n'exécutera que les tâches ayant la plus haute priorité.
avec priorité selon RR, tandis que les tâches C et D ne seront pas à l'ordre du jour.
Évidemment, un instantané statique ne donnera pas une image complète de ce à quoi ressemble MLFQ.
Il est important de comprendre comment la situation évolue au fil du temps.
Essai 1 : Comment modifier la priorité
À ce moment, il est nécessaire de décider comment MLFQ modifie le niveau de priorité
des tâches (et donc leur position dans la file d'attente) tout au long de leur cycle de vie. Pour
cela, il est important de garder à l'esprit le flux de travail : un certain nombre
de tâches interactives avec un temps de travail court (et donc un dégagement fréquent
de CPU) et plusieurs tâches longues qui utilisent le CPU tout le temps de travail, tout en
ayant un temps de réponse non important pour ces tâches. Ainsi, nous pouvons effectuer la première tentative
de mettre en œuvre l'algorithme MLFQ avec les règles suivantes :
- Règle 3 : Lorsqu'une tâche entre dans le système, elle est placée dans la file d'attente avec la plus haute
- priorité a été attribuée aux Ingester.
- Règle 4a : Si une tâche utilise complètement la fenêtre de temps qui lui est allouée, alors sa
- priorité est abaissée.
- Règle 4b : Si la Tâche libère le CPU avant la fin de sa fenêtre de temps, alors elle
- garde sa priorité initiale.
Exemple 1 : Une tâche à long terme
Comme on peut le voir dans cet exemple, la tâche est placée avec la plus haute
priorité à son arrivée. Après un délai de 10 ms, le processus est abaissé en priorité
par le planificateur. Après la fenêtre de temps suivante, la tâche est enfin abaissée à
la plus basse priorité dans le système, où elle reste.
Exemple 2 : Une courte tâche a été ajoutée
Maintenant, voyons un exemple de la façon dont MLFQ essaiera de se rapprocher de SJF. Dans cet
exemple, il y a deux tâches : A, qui est une tâche à long terme utilisant constamment
le CPU et B, qui est une tâche interactive courte. Supposons que
A ait déjà fonctionné un certain temps au moment où la tâche B est arrivée.
Sur ce graphique, on peut voir les résultats du scénario. La tâche A, comme toute autre tâche,
utilisant le CPU se retrouve en bas. La tâche B arrivera à T=100 et sera
placée en file d'attente avec la plus haute priorité. Comme son temps d'exécution est limité, elle
terminera avant d'atteindre la dernière file.
De cet exemple, on peut comprendre l'objectif principal de l'algorithme : comme l'algorithme ne
sait pas si une tâche est longue ou courte, il suppose d'abord que la tâche
court et a la plus haute priorité. Si c'est réellement une tâche courte, alors
elle s'exécutera rapidement, sinon si c'est une tâche longue, alors elle avancera lentement
dans la priorité inférieure et prouvera bientôt qu'il s'agit vraiment d'une tâche longue qui ne
requiert pas de réponse.
Exemple 3 : Qu'en est-il de l'entrée-sortie ?
Jetons maintenant un coup d'œil à l'exemple de l'entrée-sortie. Comme il a été affirmé dans la règle 4b,
si un processus libère le processeur sans avoir utilisé complètement son temps processeur,
il reste au même niveau de priorité. L'intention de cette règle est assez simple
— si une tâche interactive effectue beaucoup d'opérations d'entrée-sortie, par exemple en attendant
des pressions de touche ou des clics de souris de l'utilisateur, cette tâche libérera le processeur
plus tôt que prévu. Nous ne voudrions pas réduire cette tâche en priorité,
et ainsi elle restera au même niveau.
Cet exemple montre comment l'algorithme fonctionnera avec de tels processus — la tâche interactive B, qui a besoin du CPU pendant seulement 1 ms avant d'effectuer
le processus d'entrée-sortie et la longue tâche A, qui utilise tout son temps sur le CPU.
MLFQ maintient le processus B avec la plus haute priorité, car il continue constamment
à libérer le CPU. Si B est une tâche interactive, l'algorithme atteint ainsi
son objectif d'exécuter rapidement les tâches interactives.
Problèmes avec l'algorithme MLFQ actuel
Dans les exemples précédents, nous avons construit une version de base de MLFQ. Et il semble qu'il
fasse bien son travail et honnêtement, en répartissant le temps CPU équitablement entre
les longues tâches et en permettant aux tâches courtes ou à celles intensément
axées sur l'entrée-sortie de s'exécuter rapidement. Malheureusement, cette approche contient plusieurs
problèmes sérieux.
Tout d'abord, problème de famine : si le système comporte de nombreuses tâches interactives,
elles consommeront tout le temps CPU et donc aucune tâche longue
n'aura la possibilité de s'exécuter (elles sont affamées).
Deuxièmement, des utilisateurs malins pourraient écrire leurs programmes de manière à
tromper le planificateur. Le piège réside dans le fait de faire quelque chose pour inciter
le planificateur à accorder plus de temps CPU au processus. L'algorithme qui
décrit ci-dessus est tout à fait vulnérable à de telles attaques : avant que la fenêtre de temps ne soit pratiquement
épuisée, il est nécessaire d'effectuer une opération d'entrée-sortie (sur un fichier quelconque, peu importe lequel)
et ainsi libérer le CPU. Un tel comportement permettra de rester dans la même
file d'attente et de recevoir à nouveau un plus grand pourcentage de temps processeur. Si cela est fait
correctement (par exemple, être actif 99 % du temps de la fenêtre avant de libérer le CPU),
cette tâche pourrait simplement monopoliser le processeur.
Enfin, le programme peut changer son comportement au fil du temps. Les tâches,
qui utilisaient le CPU, peuvent devenir interactives. Dans notre exemple, de telles
tâches ne recevraient pas le traitement adéquat de l'ordonnanceur, comme elles recevraient d'autres
(initiales) tâches interactives.
Question au public : quelles attaques sur l'ordonnanceur pouvaient être menées dans le monde moderne ?
Essai 2 : Élévation de priorité
Essayons de changer les règles et voyons si nous pouvons éviter les problèmes de
famine. Que pourrions-nous faire pour garantir que les tâches liées au
CPU reçoivent leur temps (même si ce n'est pas long).
Comme solution simple au problème, on peut proposer d'élever périodiquement
la priorité de toutes ces tâches dans le système. Il existe de nombreuses façons
d'y parvenir, essayons de mettre en œuvre quelque chose de simple : transférer
toutes les tâches à la priorité la plus élevée, d'où la nouvelle règle :
- Règle5: Après un certain temps S, transférer toutes les tâches dans le système à la file d'attente la plus élevée.
Notre nouvelle règle résout deux problèmes à la fois. Premièrement, les processus
ne souffrent pas de famine : les tâches dans la file d'attente supérieure partageront
le temps processeur selon l'algorithme RR et ainsi tous les processus recevront
du temps processeur. Deuxièmement, si un processus, qui auparavant n'utilisait que
le processeur, devient interactif, il restera dans la file d'attente avec la plus haute
priorité après avoir reçu une élévation de priorité à son plus haut niveau.
Considérons un exemple. Dans ce scénario, examinons un processus utilisant
Le CPU et deux processus interactifs et courts. À gauche, l'image montre le comportement sans augmentation de priorité, et ainsi une tâche de longue durée commence à manquer de ressources après l'arrivée dans le système de deux tâches interactives. À droite, chaque 50 ms, une augmentation de priorité est effectuée, garantissant ainsi que tous les processus obtiennent du temps CPU et seront exécutés périodiquement. 50 ms est un exemple, ce nombre est en réalité un peu plus élevé.
Il est évident que l'ajout de temps d'augmentation périodique S entraîne la
question légitime : quelle valeur devrait être définie ? Un des ingénieurs système réputés, John Ousterhout, qualifiait de telles valeurs dans les systèmes de "voo-doo"
constante, car elles nécessitaient en quelque sorte de la magie noire pour être correctement
définies. Et, malheureusement, S a cette connotation. Si on définit une valeur trop
élevée, les tâches longues commenceront à manquer de ressources. Et si on la définit trop basse,
les tâches interactives ne recevront pas le temps CPU adéquat.
Tentative 3 : Meilleur comptage
Nous avons maintenant un autre problème à résoudre : comment ne pas
permettre à notre planificateur d'être contourné ? Les responsables de cette possibilité sont
les règles 4a, 4b, qui permettent à une tâche de conserver sa priorité tout en libérant le CPU
avant l'expiration du temps alloué. Comment faire face à cela ?
La solution dans ce cas serait le meilleur comptage du temps CPU à chaque
niveau MLFQ. Au lieu d'oublier le temps que le programme a utilisé
le CPU pendant la période allouée, il faudrait le comptabiliser et le sauvegarder. Une fois que
le processus a épuisé le temps qui lui a été attribué, son niveau de priorité doit être abaissé au
niveau suivant. Peu importe comment le processus utilisera son temps — que ce soit
de manière constante sur le processeur ou par de multiples appels. Ainsi,
la règle 4 devrait être réécrite comme suit :
Règle 4
- : Une fois qu'une tâche a épuisé son temps alloué dans la queue actuelle (peu importe combien de fois elle a libéré le CPU) sa priorité est diminuée (elle descend dans la queue).Prenons un exemple :
L'image montre ce qui se passe si l'on tente de contourner le planificateur, comment
»
L'illustration montre ce qui se passe si l'on essaie de tromper le planificateur, comme
si cela avait été avec les règles précédentes 4a, 4b, le résultat serait à gauche. Avec la nouvelle
règle — le résultat est à droite. Avant la protection, tout processus pouvait provoquer des I/O jusqu'à la fin et
ainsi dominer le CPU, après l'activation de la protection, indépendamment du comportement des
I/O, il sera néanmoins rétrogradé dans les files d'attente et ne pourra donc pas accaparer
indûment les ressources CPU.
Nous améliorons le MLFQ et d'autres problèmes
Avec les améliorations ci-dessus, de nouveaux problèmes surviennent : l'une des principales
questions est de savoir comment paramétrer un tel planificateur ? C'est-à-dire, combien doit-il y avoir
de files d'attente ? Quelle doit être la taille de la fenêtre de travail d'un programme dans une file d'attente ? À quelle
fréquence doit-on élever le priorités de programme pour éviter la famine et
prendre en compte l'évolution du comportement du programme ? Il n'y a pas de réponse simple à ces questions, et seul
des expériences avec des charges de travail et une configuration ultérieure
du planificateur peuvent mener à un équilibre satisfaisant.
Par exemple, la plupart des implémentations de MLFQ permettent d'attribuer différents
intervals temps à différentes files d'attente. Les files d'attente hautes priorités se voient généralement
attribuer de courts intervalles. Ces files se composent de tâches interactives,
le changement entre lesquelles est assez sensible et doit prendre 10 millisecondes ou moins.
À l'inverse, les files d'attente basses priorités sont constituées de tâches longues qui utilisent
le CPU. Dans ce cas, de longs intervalles de temps conviennent très bien (100 ms).
Dans cet exemple, il y a 2 tâches qui ont travaillé dans une file d'attente haute priorité pendant 20
ms, éclatées en fenêtres de 10 ms. 40 ms dans la file d'attente moyenne (fenêtre de 20 ms) et dans la basse priorité
la fenêtre de temps est devenue 40 ms, où les tâches ont terminé leur travail.
L'implémentation de MLFQ dans le système d'exploitation Solaris — une classe de planificateurs, fonctionne par tranches.
Le planificateur fournit un ensemble de tableaux qui définissent exactement comment
le priorités du processus doivent changer au cours de sa vie, quelle doit être la taille
des fenêtres allouées et à quelle fréquence il faut élever les priorités des tâches. L'administrateur
système peut interagir avec ce tableau et forcer le planificateur à se comporter
différemment. Par défaut, ce tableau contient 60 files d'attente avec un éventail croissant
de taille d'intervalle de 20 ms (haute priorité) à plusieurs centaines de ms (basse priorité), mais
aussi avec une impulsion pour toutes les tâches une fois par seconde.
D'autres planificateurs MLFQ n'utilisent pas de tableau ou de règles spécifiques
décrites dans cette leçon, au contraire, ils calculent les priorités en utilisant
des formules mathématiques. Par exemple, le planificateur de FreeBSD utilise une formule pour
calculer la priorité actuelle d'une tâche, en fonction de combien de temps le processus
a utilisé le CPU. De plus, l'utilisation du CPU se dégrade avec le temps, et de cette
manière, l'augmentation de la priorité se produit quelque peu différemment de ce qui est décrit ci-dessus. Ce sont les
appelés algorithmes de dégradation. Depuis la version 7.1, FreeBSD utilise le planificateur ULE.
Enfin, de nombreux planificateurs ont d'autres caractéristiques. Par exemple, certains
planificateurs réservent des niveaux plus élevés pour le fonctionnement du système d'exploitation, et de cette
manière, aucun processus utilisateur ne peut obtenir la priorité maximale dans
le système. Certains systèmes permettent de donner des conseils pour aider
le planificateur à définir correctement les priorités. Par exemple, à l'aide de la commande nice
on peut augmenter ou diminuer la priorité d'une tâche et ainsi augmenter ou
diminuer les chances d'un programme d'obtenir du temps processeur.
MLFQ : Résumé
Nous avons décrit une approche de planification appelée MLFQ. Son nom
est lié à son fonctionnement — elle a plusieurs files d'attente et utilise un retour d'information
pour déterminer la priorité d'une tâche.
La forme finale des règles sera la suivante :
- Règle 1: Si Priorité(A) > Priorité(B), la tâche A sera lancée (B ne le sera pas)
- Règle 2: Si Priorité(A) = Priorité(B), A et B sont lancées en utilisant RR
- Règle 3: Lorsqu'une tâche arrive dans le système, elle est placée dans la file d'attente avec la priorité la plus élevée.
- : Une fois qu'une tâche a épuisé son temps alloué dans la queue actuelle (peu importe combien de fois elle a libéré le CPU) sa priorité est diminuée (elle descend dans la queue).Prenons un exemple :
- Règle5: Après un certain temps S, transférer toutes les tâches dans le système à la file d'attente la plus élevée.
MLFQ est intéressant pour la raison suivante : au lieu d'exiger une connaissance préalable de
la nature de la tâche, l'algorithme analyse le comportement passé de la tâche et attribue
des priorités en conséquence. Ainsi, il essaie de jongler entre deux objectifs — atteindre une performance pour les petites tâches (SJF, STCF) et exécuter équitablement les longues
tâches lourdes pour le CPU. Par conséquent, de nombreux systèmes, y compris BSD et ses dérivés,
Solaris, Windows, Mac utilisent une forme de l'algorithme MLFQ comme base.
manpages.debian.org/stretch/manpages/sched.7.en.html
Documents supplémentaires :
- chebykin.org/freebsd-process-scheduling
Source : habr.com
