Introduction aux systèmes d'exploitation
Hé Habr ! Je voudrais porter à votre attention une série d'articles-traductions d'une littérature intéressante à mon avis - OSTEP. Ce matériel traite assez en profondeur du travail des systèmes d'exploitation de type Unix, à savoir le travail avec les processus, divers planificateurs, la mémoire et d'autres composants similaires qui composent un système d'exploitation moderne. Vous pouvez voir l'original de tous les matériaux ici . Veuillez noter que la traduction a été faite de manière non professionnelle (assez librement), mais j'espère avoir conservé le sens général.
Les travaux de laboratoire sur ce sujet peuvent être trouvés ici:
Autres parties:
Vous pouvez également consulter ma chaîne sur =)
Planification : file d'attente de commentaires à plusieurs niveaux
Dans cette conférence, nous parlerons des problèmes liés au développement de l'une des approches les plus célèbres de
la planification, appelée File d'attente de commentaires à plusieurs niveaux (MLFQ). L'ordonnanceur MLFQ a été décrit pour la première fois en 1962 par Fernando J. Corbató dans un système appelé
Système de partage de temps compatible (CTSS). Ces travaux (y compris les travaux ultérieurs sur
Multics) ont ensuite été nominés pour le Turing Award. Le planificateur était
par la suite amélioré et acquis l'apparence que l'on retrouve déjà dans
certains systèmes modernes.
L'algorithme MLFQ tente de résoudre 2 problèmes fondamentaux qui se chevauchent.
D'abord, il tente d'optimiser le temps d'exécution qui, comme nous l'avons vu dans la leçon précédente, est optimisé par la méthode consistant à commencer le plus au début de la file d'attente.
tâches courtes. Cependant, le système d'exploitation ne sait pas combien de temps un processus particulier sera exécuté, et cela
connaissances nécessaires au fonctionnement des algorithmes SJF, STCF. deuxièmement, MLFQ essaie
rendre le système réactif pour les utilisateurs (par exemple, pour ceux qui sont assis et
regarder l'écran en attendant que la tâche soit terminée) et ainsi minimiser le temps
réponse. Malheureusement, les algorithmes comme RR améliorent le temps de réponse, mais extrêmement
avoir un impact négatif sur la mesure des délais d’exécution. D'où notre problème : comment concevoir
un planificateur qui répondra à nos exigences sans rien connaître
la nature du processus en général ? Comment le planificateur peut-il apprendre les caractéristiques des tâches,
qu'il lance et ainsi prendre de meilleures décisions de planification ?
Le fond du problème : Comment planifier la définition des tâches sans une parfaite connaissance ?
Comment concevoir un planificateur qui minimise simultanément le temps de réponse
pour les tâches interactives tout en minimisant les délais d'exécution sans savoir
connaissance du temps d’exécution des tâches ?
Remarque : nous apprenons des événements précédents
La file d'attente MLFQ est un excellent exemple de système qui apprend de
événements passés pour prédire l’avenir. Des approches similaires sont souvent
trouvé dans OS (et dans de nombreuses autres branches de l'informatique, y compris les branches
prédictions matérielles et algorithmes de mise en cache). Voyages similaires
sont déclenchés lorsque les tâches comportent des phases comportementales et sont donc prévisibles.
Cependant, vous devez être prudent avec cette technique car les prédictions sont très simples.
peut s'avérer incorrect et conduire le système à prendre de pires décisions que
serait sans aucune connaissance.
MLFQ : règles de base
Regardons les règles de base de l'algorithme MLFQ. Et bien que les implémentations de cet algorithme
Il en existe plusieurs, les approches de base sont similaires.
Dans la mise en œuvre que nous allons examiner, MLFQ aura plusieurs
des files d'attente distinctes, chacune ayant une priorité différente. À tout moment,
une tâche prête à être exécutée se trouve dans une file d'attente. MLFQ utilise des priorités,
pour décider quelle tâche exécuter pour exécution, c'est-à-dire tâche avec plus haut
la priorité (la tâche de la file d'attente ayant la priorité la plus élevée) sera lancée en premier
file d'attente.
Bien entendu, il peut y avoir plusieurs tâches dans une file d'attente donnée.
ils auront donc la même priorité. Dans ce cas, le mécanisme sera utilisé
RR pour planifier une exécution parmi ces tâches.
Nous arrivons ainsi à deux règles de base pour MLFQ :
- 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&B sont démarrés en utilisant RR
Sur la base de ce qui précède, les éléments clés de la planification du MLFQ
sont des priorités. Au lieu de donner une priorité fixe à chacun
tâche, MLFQ change de priorité en fonction du comportement observé.
Par exemple, si une tâche demande constamment du travail au processeur en attendant une saisie au clavier,
MLFQ maintiendra une priorité de processus élevée car c'est ainsi
un processus interactif devrait fonctionner. Si, au contraire, la tâche est constamment et
utilise beaucoup le CPU sur une longue période, MLFQ le réduira
une priorité. Ainsi, MLFQ étudiera le comportement des processus pendant leur exécution
et utiliser des comportements.
Tirons un exemple de ce à quoi pourraient ressembler les files d'attente à un moment donné
temps et vous obtenez quelque chose comme ceci :
Dans ce schéma, 2 processus A et B sont dans la file d'attente la plus prioritaire. Processus
C se situe quelque part au milieu et le processus D se trouve à la toute fin de la file d’attente. D'après ce qui précède
Selon les descriptions de l'algorithme MLFQ, le planificateur exécutera les tâches uniquement avec le plus haut
priorité selon RR, et les tâches C, D seront sans travail.
Naturellement, un instantané statique ne donnera pas une image complète du fonctionnement de MLFQ.
Il est important de comprendre exactement comment la situation évolue au fil du temps.
Tentative 1 : Comment changer la priorité
À ce stade, vous devez décider comment MLFQ modifiera le niveau de priorité.
tâches (et donc la position de la tâche dans la file d'attente) au fur et à mesure de sa progression dans son cycle de vie. Pour
il est nécessaire de garder à l'esprit le workflow : un certain montant
tâches interactives avec des durées d'exécution courtes (et donc des versions fréquentes
CPU) et plusieurs tâches de longue durée qui utilisent le CPU tout leur temps de travail, tandis que
Le temps de réponse n'est pas important pour de telles tâches. Et de cette façon, vous pourrez faire votre premier essai
implémentez 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 le score le plus élevé.
- priorité.
- Règle 4a : Si une tâche utilise toute la fenêtre de temps qui lui est impartie, alors elle
- la priorité est réduite.
- Règle 4b : si une tâche libère le processeur avant l'expiration de sa fenêtre de temps, elle
- reste avec la même priorité.
Exemple 1 : tâche unique de longue durée
Comme on peut le voir dans cet exemple, la tâche d'admission est définie avec le niveau le plus élevé
priorité. Après une fenêtre de temps de 10 ms, le processus est rétrogradé en priorité
planificateur. Après la fenêtre temporelle suivante, la tâche est finalement rétrogradée à
priorité la plus basse dans le système, là où elle reste.
Exemple 2 : livré une tâche courte
Voyons maintenant un exemple de la manière dont MLFQ tentera d'approcher SJF. En cela
exemple, deux tâches : A, qui est une tâche de longue durée en permanence
occupant CPU et B, qui est une courte tâche interactive. Supposer
que A travaillait déjà depuis un certain temps au moment où la tâche B est arrivée.
Ce graphique montre les résultats du scénario. La tâche A, comme toute tâche,
L'utilisation du processeur était tout en bas. La tâche B arrivera à l'instant T=100 et
placé dans la file d’attente la plus prioritaire. Sa durée de fonctionnement étant courte, alors
il se terminera avant d'atteindre la dernière file d'attente.
À partir de cet exemple, il faut comprendre l’objectif principal de l’algorithme : puisque l’algorithme ne
sait si une tâche est longue ou courte, alors il suppose tout d'abord que la tâche
court et lui donne la plus haute priorité. S'il s'agit d'une tâche très courte, alors
elle sera achevée rapidement, sinon si c'est une tâche longue, elle avancera lentement
priorité vers le bas et prouvera bientôt qu'il s'agit effectivement d'une tâche longue qui ne le fait pas
nécessite une réponse.
Exemple 3 : qu'en est-il des E/S ?
Regardons maintenant un exemple d'E/S. Comme indiqué dans la règle 4b,
si un processus libère le processeur sans utiliser la totalité de son temps processeur,
il reste alors au même niveau de priorité. Le but de cette règle est assez simple
- si le travail interactif effectue de nombreuses opérations d'E/S, par exemple en attente
à partir des touches utilisateur ou des pressions de la souris, une telle tâche libérera le processeur
avant la fenêtre impartie. Nous ne voudrions pas diminuer la priorité d'une telle tâche,
et donc il restera au même niveau.
Cet exemple montre comment l'algorithme fonctionnera avec de tels processus - tâche interactive B, qui n'a besoin de CPU que pendant 1 ms avant son exécution.
Processus d'E/S et travail A de longue durée, qui passe tout son temps à utiliser le processeur.
MLFQ maintient le processus B avec la plus haute priorité car il continue
libérer le processeur. Si B est une tâche interactive, alors l’algorithme a atteint
Votre objectif est d'exécuter des tâches interactives rapidement.
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
fait bien et honnêtement son travail, en répartissant équitablement le temps CPU entre
tâches longues et permettant des tâches courtes ou à volume élevé
travailler rapidement sur les E/S. Malheureusement, cette approche contient plusieurs
Problèmes sérieux.
D'abord, le problème de la faim : si le système comporte de nombreux
tâches, alors elles consommeront tout le temps processeur et donc pas une seule pendant longtemps
la tâche ne pourra pas être exécutée (ils meurent de faim).
deuxièmement, les utilisateurs intelligents pourraient écrire leurs programmes de manière à ce que
tromper le planificateur. La tromperie consiste à faire quelque chose pour forcer
Le planificateur donne au processus plus de temps CPU. Algorithme qui
décrit ci-dessus est assez vulnérable à des attaques similaires : avant que la fenêtre de temps ne soit pratiquement
terminé, vous devez effectuer une opération d'E/S (pour certains, quel que soit le fichier)
et ainsi libérer le CPU. Un tel comportement vous permettra de rester dans le même
la file d'attente elle-même et obtenez à nouveau un pourcentage plus important de temps CPU. Si tu fais
c'est correct (par exemple, exécuter 99% du temps fenêtre avant de libérer le CPU),
une telle tâche peut simplement monopoliser le processeur.
Enfin, un programme peut modifier son comportement au fil du temps. Ces tâches
qui a utilisé le CPU peut devenir interactif. Dans notre exemple, similaire
les tâches ne recevront pas le traitement qu'elles méritent de la part du planificateur comme d'autres le feraient
tâches interactives (initiales).
Question pour le public : quelles attaques contre le planificateur pourraient être menées dans le monde moderne ?
Tentative 2 : priorité croissante
Essayons de changer les règles et voyons si nous pouvons éviter les problèmes avec
jeûne. Que pouvons-nous faire pour garantir que les
Les tâches CPU auront leur temps (même si ce n'est pas long).
Comme solution simple au problème, vous pouvez suggérer périodiquement
augmenter la priorité de toutes ces tâches dans le système. Il existe de nombreuses façons
Pour y parvenir, essayons d'implémenter quelque chose de simple à titre d'exemple : traduire
toutes les tâches reçoivent immédiatement la priorité la plus élevée, d'où la nouvelle règle :
- Rule5: Après une certaine période S, déplacez toutes les tâches du système vers la file d'attente la plus élevée.
Notre nouvelle règle résout deux problèmes à la fois. Premièrement, les processus
sont assurés de ne pas mourir de faim : les tâches les plus prioritaires seront divisées
Temps CPU selon l'algorithme RR et ainsi tous les processus recevront
Temps CPU. Deuxièmement, si un processus précédemment utilisé
seul le processeur devient interactif, il restera dans la file d'attente avec le plus haut
priorité après avoir reçu une augmentation unique de la priorité au plus élevé.
Regardons un exemple. Dans ce scénario, considérons un processus utilisant
CPU et deux processus courts et interactifs. À gauche de la figure, la figure montre le comportement sans promotion prioritaire, et ainsi la tâche de longue durée commence à mourir de faim après l'arrivée de deux tâches interactives dans le système. Dans la figure de droite, une augmentation de priorité est effectuée toutes les 50 ms et ainsi tous les processus sont garantis de recevoir du temps CPU et seront lancés périodiquement. 50 ms dans ce cas est pris comme exemple ; en réalité ce nombre est légèrement plus élevé.
Évidemment, l’ajout du temps d’augmentation périodique S conduit à
une question logique : quelle valeur définir ? L'un des honorés
les ingénieurs système John Ousterhout ont qualifié de telles quantités dans les systèmes de vaudou
constant, car ils nécessitaient d'une manière ou d'une autre de la magie noire pour corriger
exposant. Et malheureusement, S a un tel parfum. Si vous définissez également la valeur
les tâches importantes et longues commenceront à mourir de faim. Et si vous définissez une valeur trop basse,
Les tâches interactives ne recevront pas le temps CPU approprié.
Tentative 3 : une meilleure comptabilité
Nous avons maintenant un autre problème à résoudre : comment ne pas
permettre à notre planificateur de se laisser berner ? Les personnes responsables de cette possibilité sont
les règles 4a, 4b, qui permettent à un travail de conserver la priorité, libérant ainsi le processeur
avant l'expiration du délai imparti. Comment gérer cela ?
La solution dans ce cas peut être considérée comme une meilleure prise en compte du temps CPU sur chaque
Niveau MLFQ. Au lieu d'oublier l'heure utilisée par le programme
processeur pour la période impartie, il doit être pris en compte et sauvegardé. Après
le processus a épuisé le temps qui lui était imparti, il doit être rétrogradé au suivant
niveau de priorité. Désormais, peu importe comment le processus utilisera son temps - comment
calculant constamment sur le processeur ou sous forme d'un certain nombre d'appels. Ainsi,
la règle 4 doit être réécrite sous la forme suivante :
- Rule4: Une fois qu'une tâche a utilisé le temps qui lui est alloué dans la file d'attente actuelle (peu importe le nombre de fois où elle a libéré le processeur), la priorité de cette tâche est réduite (elle descend dans la file d'attente).
Regardons un exemple :
»
La figure montre ce qui se passe si vous essayez de tromper le planificateur, comme
si c'était avec les règles précédentes 4a, 4b, le résultat à gauche serait obtenu. Bonne nouvelle
la règle est le résultat à droite. Avant la protection, n'importe quel processus pouvait appeler des E/S avant la fin et
domine ainsi le CPU, après avoir activé la protection, quel que soit le comportement
I/O, il descendra toujours dans la file d'attente et ne pourra donc pas malhonnêtement
prendre en charge les ressources du processeur.
Améliorer MLFQ et d'autres problèmes
Les améliorations ci-dessus entraînent de nouveaux problèmes : l'un des principaux
Questions - comment paramétrer un tel planificateur ? Ceux. Combien devrait-il être
des files d'attente ? Quelle doit être la taille de la fenêtre du programme dans la file d’attente ? Comment
La priorité du programme devrait souvent être augmentée pour éviter la famine et
prendre en compte le changement de comportement du programme ? Il n'y a pas de réponse simple à ces questions
réponse et uniquement des expériences avec des charges et une configuration ultérieure
Le planificateur peut conduire à un équilibre satisfaisant.
Par exemple, la plupart des implémentations MLFQ vous permettent d'attribuer différents
intervalles de temps pour différentes files d'attente. Files d'attente haute priorité généralement
de courts intervalles sont prescrits. Ces files d'attente sont constituées de tâches interactives,
la commutation entre les deux est assez sensible et devrait prendre 10 ou moins
MS. En revanche, les files d'attente de faible priorité sont constituées de tâches de longue durée qui utilisent
CPU. Et dans ce cas, les intervalles de temps longs s'adaptent très bien (100 ms).
Dans cet exemple, 2 tâches ont fonctionné dans la file d'attente haute priorité 20.
ms, divisé en fenêtres de 10 ms. 40 ms dans la file d'attente du milieu (fenêtre de 20 ms) et dans la priorité basse
La fenêtre de temps d'attente est passée à 40 ms lorsque les tâches ont terminé leur travail.
L'implémentation de MLFQ dans le système d'exploitation Solaris est une classe de planificateurs de temps partagé.
Le planificateur fournira un ensemble de tableaux qui définissent exactement comme il se doit
la priorité du processus change au cours de sa vie, quelle devrait être la taille
fenêtre allouée et à quelle fréquence vous devez augmenter les priorités des tâches. Administrateur
les systèmes peuvent interagir avec cette table et faire en sorte que le planificateur se comporte
différemment. Par défaut, ce tableau comporte 60 files d'attente avec une augmentation progressive
taille de fenêtre de 20 ms (priorité élevée) à plusieurs centaines de ms (priorité faible), et
également avec un boost de toutes les tâches une fois par seconde.
Les autres planificateurs MLFQ n'utilisent pas de tableau ni de
règles décrites dans cette conférence, au contraire, ils calculent les priorités en utilisant
formules mathématiques. Par exemple, le planificateur FreeBSD utilise une formule pour
calculer la priorité actuelle d'une tâche en fonction de la durée du processus
CPU utilisé. De plus, l'utilisation du processeur diminue avec le temps, et donc
Ainsi, l’augmentation de la priorité se produit quelque peu différemment de ce qui est décrit ci-dessus. C'est vrai
appelés algorithmes de désintégration. Depuis la version 7.1, FreeBSD utilise le planificateur ULE.
Enfin, de nombreux planificateurs disposent d’autres fonctionnalités. Par exemple, certains
les planificateurs réservent les niveaux les plus élevés pour le fonctionnement du système d'exploitation et ainsi
Ainsi, aucun processus utilisateur ne peut recevoir la priorité la plus élevée dans
système. Certains systèmes permettent de donner des conseils pour aider
le planificateur peut définir correctement les priorités. Par exemple, en utilisant la commande agréable
vous pouvez augmenter ou diminuer la priorité d'une tâche et ainsi augmenter ou
réduire les chances du programme d'utiliser le temps CPU.
MLFQ : Résumé
Nous avons décrit une approche de planification appelée MLFQ. Son nom
enfermé dans le principe de fonctionnement - il dispose de plusieurs files d'attente et utilise le feedback
pour déterminer la priorité des tâches.
La forme finale du règlement sera la suivante :
- Rule1: Si priorité(A) > Priorité(B), la tâche A sera lancée (B pas)
- Rule2: Si priorité (A) = Priorité (B), A&B sont démarrés en utilisant RR
- Rule3: Lorsqu'une tâche entre dans le système, elle est placée dans la file d'attente la plus prioritaire.
- Rule4: Une fois qu'une tâche a utilisé le temps qui lui est alloué dans la file d'attente actuelle (peu importe le nombre de fois où elle a libéré le processeur), la priorité de cette tâche est réduite (elle descend dans la file d'attente).
- Rule5: Après une certaine période S, déplacez toutes les tâches du système vers la file d'attente la plus élevée.
MLFQ est intéressant pour la raison suivante - au lieu d'exiger des connaissances sur
nature de la tâche à l'avance, l'algorithme étudie le comportement passé de la tâche et définit
priorités en conséquence. Ainsi, il essaie de s'asseoir sur deux chaises à la fois - pour atteindre la productivité pour les petites tâches (SJF, STCF) et pour courir honnêtement longtemps,
Travaux de chargement du processeur. Par conséquent, de nombreux systèmes, y compris BSD et ses dérivés,
Solaris, Windows et Mac utilisent une forme d'algorithme comme planificateur
MLFQ comme référence.
Matériaux supplémentaires:
- (l'informatique)
Source: habr.com