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 =)
Introduction au planificateur
L'essence du problème : comment développer une politique de planification
Comment les cadres politiques sous-jacents des planificateurs devraient-ils être conçus ? Quelles devraient être les hypothèses clés ? Quelles mesures sont importantes ? Quelles techniques de base étaient utilisées dans les premiers systèmes informatiques ?
Hypothèses relatives à la charge de travail
Avant de discuter des politiques possibles, faisons d'abord quelques digressions simplificatrices sur les processus exécutés dans le système, qui sont collectivement appelés charge de travail. La définition de la charge de travail est un élément essentiel de l’élaboration de politiques, et plus vous en savez sur la charge de travail, meilleure sera la politique que vous pourrez rédiger.
Faisons les hypothèses suivantes sur les processus exécutés dans le système, parfois également appelés emplois (Tâches). Presque toutes ces hypothèses ne sont pas réalistes, mais sont nécessaires au développement de la pensée.
- Chaque tâche s'exécute pendant la même durée,
- Toutes les tâches sont définies simultanément,
- La tâche assignée fonctionne jusqu'à son achèvement,
- Toutes les tâches utilisent uniquement le CPU,
- Le temps d'exécution de chaque tâche est connu.
Métriques du planificateur
En plus de quelques hypothèses sur la charge, un autre outil pour comparer les différentes politiques de planification est nécessaire : les métriques du planificateur. Une métrique n’est qu’une mesure de quelque chose. Il existe un certain nombre de mesures qui peuvent être utilisées pour comparer les planificateurs.
Par exemple, nous utiliserons une métrique appelée délai d'exécution (délai d'exécution). Le délai d'exécution d'une tâche est défini comme la différence entre l'heure d'achèvement de la tâche et l'heure d'arrivée de la tâche dans le système.
Tretournement=Tachèvement−Tarrivée
Puisque nous avons supposé que toutes les tâches arrivaient en même temps, alors Ta=0 et donc Tt=Tc. Cette valeur changera naturellement lorsque nous modifierons les hypothèses ci-dessus.
Une autre métrique - justice (équité, honnêteté). La productivité et l’équité sont souvent des caractéristiques opposées en matière de planification. Par exemple, le planificateur peut optimiser les performances, mais au prix d'attendre que d'autres tâches soient exécutées, réduisant ainsi l'équité.
PREMIER ENTRÉ, PREMIER SORTI (FIFO)
L'algorithme le plus basique que nous pouvons implémenter s'appelle FIFO ou premier arrivé (entré), premier servi (sortir). Cet algorithme présente plusieurs avantages : il est très simple à mettre en œuvre, il s’adapte à toutes nos hypothèses et fait plutôt bien le travail.
Regardons un exemple simple. Disons que 3 tâches ont été définies simultanément. Mais supposons que la tâche A arrive un peu plus tôt que toutes les autres, elle apparaîtra donc dans la liste d'exécution plus tôt que les autres, tout comme B par rapport à C. Supposons que chacune d'elles sera exécutée pendant 10 secondes. Quel sera le temps moyen pour accomplir ces tâches dans ce cas ?
En comptant les valeurs - 10+20+30 et en divisant par 3, on obtient le temps moyen d'exécution du programme égal à 20 secondes.
Essayons maintenant de changer nos hypothèses. En particulier, l'hypothèse 1 et nous ne supposerons donc plus que chaque tâche prend le même temps à s'exécuter. Comment le FIFO se comportera-t-il cette fois-ci ?
Il s'avère que différents temps d'exécution des tâches ont un impact extrêmement négatif sur la productivité de l'algorithme FIFO. Supposons que la tâche A prenne 100 secondes, tandis que B et C prendront toujours 10 secondes chacune.
Comme le montre la figure, la durée moyenne du système sera de (100+110+120)/3=110. Cet effet est appelé effet de convoi, lorsque certains consommateurs à court terme d'une ressource feront la queue après un gros consommateur. C'est comme la file d'attente à l'épicerie lorsqu'il y a un client devant vous avec un panier plein. La meilleure solution au problème est d’essayer de changer de caisse ou de vous détendre et de respirer profondément.
Le travail le plus court en premier
Est-il possible de résoudre d’une manière ou d’une autre une situation similaire avec des processus lourds ? Certainement. Un autre type de planification est appeléLe travail le plus court en premier (SJF). Son algorithme est également assez primitif : comme son nom l'indique, les tâches les plus courtes seront lancées en premier, les unes après les autres.
Dans cet exemple, le résultat de l'exécution des mêmes processus sera une amélioration du délai d'exécution moyen du programme et il sera égal à 50 au lieu de 110, ce qui est presque 2 fois mieux.
Ainsi, dans l’hypothèse où toutes les tâches arrivent en même temps, l’algorithme SJF semble être l’algorithme le plus optimal. Cependant, nos hypothèses ne semblent toujours pas réalistes. Cette fois, nous changeons l'hypothèse 2 et imaginons cette fois que les tâches peuvent être présentes à tout moment, et pas toutes en même temps. À quels problèmes cela peut-il entraîner ?
Imaginons que la tâche A (100c) arrive en premier et commence à être exécutée. A t=10 arrivent les tâches B et C qui prendront chacune 10 secondes. Le temps d'exécution moyen est donc de (100+(110-10)+(120-10))3 = 103. Que pourrait faire le planificateur pour améliorer cela ?
Délai d'achèvement le plus court en premier (STCF)
Afin d'améliorer la situation, nous omettons l'hypothèse 3 selon laquelle le programme est lancé et se déroule jusqu'à son achèvement. De plus, nous aurons besoin d'un support matériel et, comme vous pouvez le deviner, nous utiliserons timer pour interrompre une tâche en cours et changement de contexte. Ainsi, le planificateur peut faire quelque chose au moment où les tâches B, C arrivent - arrêter l'exécution de la tâche A et mettre les tâches B et C en traitement et, une fois leur achèvement, continuer à exécuter le processus A. Un tel planificateur est appelé STCFou Travail préventif d'abord.
Le résultat de ce planificateur sera le résultat suivant : ((120-0)+(20-10)+(30-10))/3=50. Ainsi, un tel planificateur devient encore plus optimal pour nos tâches.
Temps de réponse métrique
Ainsi, si l’on connaît le temps d’exécution des tâches et que ces tâches n’utilisent que du CPU, STCF sera la meilleure solution. Et au début, ces algorithmes fonctionnaient plutôt bien. Cependant, l’utilisateur passe désormais la majeure partie de son temps devant le terminal et attend une expérience interactive productive. Ainsi une nouvelle métrique est née - Temps de réponse (réponse).
Le temps de réponse est calculé comme suit :
Tresponse = Tfirstrun−Tarrivée
Ainsi, pour l'exemple précédent, le temps de réponse sera : A=0, B=0, C=10 (abg=3,33).
Et il s'avère que l'algorithme STCF n'est pas si bon dans une situation où 3 tâches arrivent en même temps - il devra attendre que les petites tâches soient complètement terminées. L’algorithme est donc bon pour la métrique du délai d’exécution, mais mauvais pour la métrique de l’interactivité. Imaginez si vous étiez assis devant un terminal en train d'essayer de taper des caractères dans un éditeur et que vous deviez attendre plus de 10 secondes parce qu'une autre tâche occupait le processeur. Ce n'est pas très agréable.
Nous sommes donc confrontés à un autre problème : comment pouvons-nous créer un planificateur sensible au temps de réponse ?
Round Robin
Un algorithme a été développé pour résoudre ce problème Round Robin (RR). L'idée de base est assez simple : au lieu d'exécuter des tâches jusqu'à ce qu'elles soient terminées, nous allons exécuter la tâche pendant une certaine période de temps (appelée tranche de temps), puis passer à une autre tâche de la file d'attente. L'algorithme répète son travail jusqu'à ce que toutes les tâches soient terminées. Dans ce cas, la durée d'exécution du programme doit être un multiple du temps après lequel la minuterie interrompra le processus. Par exemple, si un minuteur interrompt un processus toutes les x=10 ms, alors la taille de la fenêtre d'exécution du processus doit être un multiple de 10 et être 10,20 ou x*10.
Regardons un exemple : les tâches ABC arrivent simultanément dans le système et chacune d'elles veut s'exécuter pendant 5 secondes. L'algorithme SJF terminera chaque tâche avant d'en commencer une autre. En revanche, l'algorithme RR avec une fenêtre de lancement = 1s effectuera les tâches comme suit (Fig. 4.3) :
(SJF encore (mauvais pour le temps de réponse)
(Round Robin (bon pour le temps de réponse)
Le temps de réponse moyen pour l'algorithme RR est (0+1+2)/3=1, tandis que pour le SJF (0+5+10)/3=5.
Il est logique de supposer que la fenêtre temporelle est un paramètre très important pour RR : plus elle est petite, plus le temps de réponse est élevé. Cependant, vous ne devez pas le rendre trop petit, car le temps de changement de contexte jouera également un rôle dans les performances globales. Ainsi, le choix de la fenêtre d'exécution est défini par l'architecte du système d'exploitation et dépend des tâches qu'il est prévu d'y exécuter. Le changement de contexte n'est pas la seule opération de service qui fait perdre du temps - le programme en cours d'exécution fonctionne sur beaucoup d'autres choses, par exemple divers caches, et à chaque changement, il est nécessaire de sauvegarder et de restaurer cet environnement, ce qui peut également prendre beaucoup de temps. temps.
RR est un excellent planificateur si nous parlions uniquement de la mesure du temps de réponse. Mais comment la mesure du délai d’exécution des tâches se comportera-t-elle avec cet algorithme ? Prenons l'exemple ci-dessus, lorsque le temps de fonctionnement de A, B, C = 5 s et arrivent en même temps. La tâche A se terminera à 13 s, B à 14 s, C à 15 s et le délai d'exécution moyen sera de 14 s. Ainsi, RR est le pire algorithme pour la mesure du chiffre d’affaires.
De manière plus générale, tout algorithme de type RR est équitable : il divise le temps CPU de manière égale entre tous les processus. Et donc, ces mesures sont constamment en conflit les unes avec les autres.
Ainsi, nous avons plusieurs algorithmes contrastés et en même temps il reste encore plusieurs hypothèses - que le temps de la tâche est connu et que la tâche utilise uniquement le CPU.
Mixage avec E/S
Tout d’abord, supprimons l’hypothèse 4 selon laquelle le processus utilise uniquement le CPU ; bien entendu, ce n’est pas le cas et les processus peuvent accéder à d’autres équipements.
Dès qu’un processus demande une opération d’E/S, le processus entre dans l’état bloqué, en attendant la fin de l’E/S. Si des E/S sont envoyées au disque dur, une telle opération peut prendre jusqu'à plusieurs ms ou plus, et le processeur sera inactif à ce moment-là. Pendant ce temps, le planificateur peut occuper le processeur avec n'importe quel autre processus. La prochaine décision que le planificateur devra prendre est de savoir quand le processus terminera ses E/S. Lorsque cela se produit, une interruption se produit et le système d'exploitation met le processus qui a appelé l'E/S à l'état prêt.
Regardons un exemple de plusieurs tâches. Chacun d’eux nécessite 50 ms de temps CPU. Cependant, le premier accédera aux E/S toutes les 10 ms (qui seront également exécutées toutes les 10 ms). Et le processus B utilise simplement un processeur de 50 ms sans E/S.
Dans cet exemple, nous utiliserons le planificateur STCF. Comment le planificateur se comportera-t-il si un processus comme A y est lancé ? Il fera ce qui suit : il élaborera d'abord complètement le processus A, puis le processus B.
L’approche traditionnelle pour résoudre ce problème consiste à traiter chaque sous-tâche de 10 ms du processus A comme une tâche distincte. Ainsi, lorsqu’on démarre avec l’algorithme STJF, le choix entre une tâche de 50 ms et une tâche de 10 ms est évident. Ensuite, lorsque la sous-tâche A est terminée, le processus B et les E/S seront lancés. Une fois les E/S terminées, il sera habituel de redémarrer le processus A de 10 ms au lieu du processus B. De cette manière, il est possible d'implémenter un chevauchement, où le CPU est utilisé par un autre processus pendant que le premier attend le E/S. En conséquence, le système est mieux utilisé : au moment où les processus interactifs attendent des E/S, d'autres processus peuvent être exécutés sur le processeur.
L'Oracle n'est plus
Essayons maintenant de nous débarrasser de l'hypothèse selon laquelle la durée d'exécution de la tâche est connue. Il s’agit généralement de l’hypothèse la pire et la plus irréaliste de toute la liste. En fait, dans un système d'exploitation ordinaire moyen, le système d'exploitation lui-même en sait généralement très peu sur le temps d'exécution des tâches, alors comment pouvez-vous créer un planificateur sans savoir combien de temps la tâche prendra pour s'exécuter ? Peut-être pourrions-nous utiliser certains principes de RR pour résoudre ce problème ?
Total
Nous avons examiné les idées de base de la planification des tâches et examiné 2 familles de planificateurs. Le premier commence par la tâche la plus courte et augmente ainsi le temps d'exécution, tandis que le second est partagé entre toutes les tâches de manière égale, augmentant ainsi le temps de réponse. Les deux algorithmes sont mauvais là où les algorithmes de l’autre famille sont bons. Nous avons également examiné comment l'utilisation parallèle du processeur et des E/S peut améliorer les performances, mais nous n'avons pas résolu le problème de clairvoyance du système d'exploitation. Et dans la prochaine leçon, nous examinerons un planificateur qui examine le passé immédiat et tente de prédire l'avenir. Et c’est ce qu’on appelle la file d’attente de commentaires à plusieurs niveaux.
Source: habr.com