Le temps d'ex\u00e9cution de chaque t\u00e2che est connu.<\/li>\n<\/ol>\nM\u00e9triques du Planificateur<\/h3>\n \n En plus de certaines hypoth\u00e8ses sur la charge, un outil suppl\u00e9mentaire pour comparer diff\u00e9rentes politiques de planification est n\u00e9cessaire : les m\u00e9triques du planificateur. Une m\u00e9trique n'est rien d'autre qu'une mesure de quelque chose. Il existe un certain nombre de m\u00e9triques qui peuvent \u00eatre utilis\u00e9es pour comparer les planificateurs.<\/p>\n
\u00c0 titre d'exemple, nous utiliserons la m\u00e9trique appel\u00e9e temps de rotation<\/b> (turnaround time). Le temps de rotation d'une t\u00e2che est d\u00e9fini comme la diff\u00e9rence entre le temps d'ach\u00e8vement de la t\u00e2che et le moment o\u00f9 la t\u00e2che est arriv\u00e9e dans le syst\u00e8me.<\/p>\n
Tturnaround=Tcompletion\u2212Tarrival<\/u><\/p>\n
Puisque nous avons suppos\u00e9 que toutes les t\u00e2ches sont arriv\u00e9es en m\u00eame temps, alors Ta=0 et donc Tt=Tc. Cette valeur changera naturellement lorsque nous modifierons les hypoth\u00e8ses \u00e9nonc\u00e9es ci-dessus.<\/p>\n
Une autre m\u00e9trique est fairness<\/b> (\u00e9quit\u00e9). La performance et l'\u00e9quit\u00e9 sont souvent des caract\u00e9ristiques oppos\u00e9es dans la planification. Par exemple, un planificateur peut optimiser la performance, mais au prix d'un temps d'attente pour d'autres t\u00e2ches, ce qui r\u00e9duit l'\u00e9quit\u00e9.<\/p>\nFIRST IN FIRST OUT (FIFO)<\/h3>\n
\n L'algorithme le plus basique que nous pouvons mettre en \u0153uvre s'appelle FIFO ou premier arriv\u00e9, premier servi<\/b>Cet algorithme pr\u00e9sente plusieurs avantages : il est tr\u00e8s simple \u00e0 mettre en \u0153uvre et il convient \u00e0 toutes nos hypoth\u00e8ses, en effectuant le travail de mani\u00e8re assez efficace.<\/p>\n
Consid\u00e9rons un exemple simple. Supposons que 3 t\u00e2ches soient lanc\u00e9es simultan\u00e9ment. Mais supposons que la t\u00e2che A arrive un peu avant les autres, donc elle figurera en t\u00eate de la liste d'ex\u00e9cution, tout comme B par rapport \u00e0 V. Supposons que chacune d'elles sera ex\u00e9cut\u00e9e pendant 10 secondes. Quel sera alors le temps moyen d'ex\u00e9cution de ces t\u00e2ches ?<\/p>\n
Il s'av\u00e8re que diff\u00e9rents temps d'ex\u00e9cution des t\u00e2ches nuisent fortement \u00e0 la productivit\u00e9 de l'algorithme FIFO. Supposons que la t\u00e2che A s'ex\u00e9cute pendant 100 secondes, tandis que B et V continuent \u00e0 s'ex\u00e9cuter chacune pendant 10.<\/p>\n
l'effet de convoi<\/b>, lorsque certains consommateurs de ressources \u00e0 court terme se retrouvent en attente derri\u00e8re un consommateur plus lourd. C'est comme faire la queue dans un magasin d'alimentation, lorsque devant vous se trouve un client avec un chariot plein. La meilleure solution au probl\u00e8me est d'essayer de changer de caisse ou de se d\u00e9tendre et de respirer profond\u00e9ment.<\/p>\nShortest Job First<\/h3>\n
\n Peut-on r\u00e9soudre une telle situation avec des processus lourds ? Bien s\u00fbr. Un autre type de planification s'appelleShortest Job First<\/b> (SJF). Son algorithme est \u00e9galement assez primitif \u2014 comme le sugg\u00e8re son nom, les t\u00e2ches les plus courtes seront ex\u00e9cut\u00e9es les premi\u00e8res, les unes apr\u00e8s les autres.<\/p>\n
50 au lieu de 110<\/b>, ce qui est pratiquement deux fois mieux.<\/p>\n
Ainsi, pour l'hypoth\u00e8se donn\u00e9e selon laquelle toutes les t\u00e2ches arrivent en m\u00eame temps, l'algorithme SJF semble \u00eatre le plus optimal. Cependant, nos hypoth\u00e8ses semblent encore irr\u00e9alistes. Cette fois, nous allons modifier l'hypoth\u00e8se 2 et supposer que les t\u00e2ches peuvent arriver \u00e0 tout moment, et non toutes en m\u00eame temps. Quels probl\u00e8mes cela pourrait-il entra\u00eener ?<\/p>\n
Shortest Time-to-Completion First (STCF)<\/h3>\n \n Pour am\u00e9liorer la situation, nous allons abandonner l'hypoth\u00e8se 3, selon laquelle le programme est lanc\u00e9 et fonctionne jusqu'\u00e0 sa terminaison. De plus, nous aurons besoin de support mat\u00e9riel et comme vous l'avez peut-\u00eatre devin\u00e9, nous allons utiliser un minuteur<\/b> pour interrompre la t\u00e2che en cours et changer de contexte<\/b>. Ainsi, le planificateur peut agir au moment de l'arriv\u00e9e des t\u00e2ches B et C : interrompre l'ex\u00e9cution de la t\u00e2che A et traiter les t\u00e2ches B et C, puis continuer l'ex\u00e9cution du processus A apr\u00e8s leur ach\u00e8vement. Un tel planificateur est appel\u00e9 STCF<\/b>ou Preemptive Job First<\/b>.<\/p>\n
M\u00e9trique Temps de r\u00e9ponse (Response Time)<\/h3>\n \n Donc, si nous connaissons le temps de fonctionnement des t\u00e2ches et que ces t\u00e2ches utilisent uniquement le CPU, le STCF sera la meilleure solution. Et, \u00e0 une \u00e9poque, ces algorithmes fonctionnaient assez bien. Cependant, d\u00e9sormais, l'utilisateur passe le plus clair de son temps devant le terminal et s'attend \u00e0 une interaction interactive performante. C'est ainsi qu'une nouvelle m\u00e9trique est n\u00e9e \u2014 le temps de r\u00e9ponse<\/b> (response time).<\/p>\n
Le temps de r\u00e9ponse se calcule comme suit :<\/p>\n
Tresponse = Tfirstrun \u2212 Tarrival<\/u><\/p>\n
Ainsi, pour l'exemple pr\u00e9c\u00e9dent, le temps de r\u00e9ponse sera le suivant : A = 0, B = 0, C = 10 (abg = 3,33).<\/p>\n
Il s'av\u00e8re que l'algorithme STCF n'est pas si performant dans une situation o\u00f9 trois t\u00e2ches arrivent simultan\u00e9ment \u2014 il devra attendre que les petites t\u00e2ches soient compl\u00e8tement termin\u00e9es. Ainsi, l'algorithme est efficace pour la m\u00e9trique du temps de rotation, mais peu adapt\u00e9 pour celle de l'interactivit\u00e9. Imaginez que, assis devant un terminal, vous deviez attendre plus de 10 secondes pour taper des caract\u00e8res dans un \u00e9diteur, car une autre t\u00e2che monopolise le processeur. Ce n'est pas tr\u00e8s agr\u00e9able.<\/p>\n
Round Robin<\/h3>\n \n Pour r\u00e9soudre ce probl\u00e8me, un algorithme a \u00e9t\u00e9 d\u00e9velopp\u00e9 Round Robin<\/b> (RR). L'id\u00e9e principale est assez simple : au lieu d'ex\u00e9cuter les t\u00e2ches jusqu'\u00e0 leur compl\u00e9tion, nous ex\u00e9cuterons une t\u00e2che pendant un certain intervalle de temps (appel\u00e9 quantum de temps) puis basculerons sur une autre t\u00e2che dans la file d'attente. L'algorithme continue son fonctionnement jusqu'\u00e0 ce que toutes les t\u00e2ches soient termin\u00e9es. Le temps d'ex\u00e9cution du programme doit \u00eatre un multiple du temps apr\u00e8s lequel le minuteur interrompt le processus. Par exemple, si le minuteur interrompt le processus toutes les x=10 ms, la taille de la fen\u00eatre d'ex\u00e9cution du processus doit \u00eatre un multiple de 10 et \u00eatre 10, 20 ou x*10.<\/p>\n
Consid\u00e9rons un exemple : les t\u00e2ches ABC arrivent simultan\u00e9ment dans le syst\u00e8me et chacune d\u2019elles souhaite fonctionner pendant 5 secondes. L'algorithme SJF ex\u00e9cutera chaque t\u00e2che jusqu'\u00e0 la fin avant de lancer une autre. En revanche, l'algorithme RR avec une fen\u00eatre d'ex\u00e9cution = 1s parcourra les t\u00e2ches de la mani\u00e8re suivante (fig. 4.3) :<\/p>\n
Le temps de r\u00e9ponse moyen pour l'algorithme RR (0+1+2)\/3=1, tandis que pour SJF (0+5+10)\/3=5.<\/p>\n
Il est logique de supposer que la fen\u00eatre temporelle est un param\u00e8tre tr\u00e8s important pour le RR ; plus elle est courte, plus le temps de r\u00e9ponse est \u00e9lev\u00e9. Cependant, il ne faut pas la rendre trop petite, car le temps de commutation de contexte joue \u00e9galement un r\u00f4le dans la performance globale. Ainsi, le choix de la dur\u00e9e de la fen\u00eatre d'ex\u00e9cution est fix\u00e9 par l'architecte du syst\u00e8me d'exploitation et d\u00e9pend des t\u00e2ches qui doivent y \u00eatre ex\u00e9cut\u00e9es. La commutation de contexte n'est pas la seule op\u00e9ration utilitaire qui consomme du temps : un programme en cours d'ex\u00e9cution interagit \u00e9galement avec divers caches, et \u00e0 chaque commutation, il est n\u00e9cessaire de sauvegarder et de restaurer cet environnement, ce qui peut \u00e9galement prendre beaucoup de temps.<\/p>\n
Le RR est un excellent planificateur, si l'on consid\u00e8re uniquement la m\u00e9trique du temps de r\u00e9ponse. Mais comment la m\u00e9trique du temps de rotation des t\u00e2ches se comportera-t-elle avec cet algorithme ? Prenons l'exemple pr\u00e9c\u00e9dent, o\u00f9 les temps d'ex\u00e9cution A, B, C = 5s et arrivent en m\u00eame temps. La t\u00e2che A se terminera \u00e0 13s, B \u00e0 14s, C \u00e0 15s, et le temps de rotation moyen sera donc de 14s. Ainsi, le RR est le pire algorithme pour la m\u00e9trique de rotation.<\/p>\n
Pour le dire plus simplement, tout algorithme de type RR est \u00e9quitable ; il r\u00e9partit le temps de travail sur le CPU \u00e9galement entre tous les processus. Ainsi, ces m\u00e9triques entrent constamment en conflit les unes avec les autres.<\/p>\n
Ainsi, nous avons plusieurs algorithmes oppos\u00e9s et il reste encore quelques hypoth\u00e8ses \u2014 que le temps de la t\u00e2che est connu et que la t\u00e2che utilise uniquement le CPU.<\/p>\n
M\u00e9lange avec l'I\/O<\/h3>\n \n Tout d'abord, \u00e9liminons l'hypoth\u00e8se 4, selon laquelle le processus utilise uniquement le CPU ; ce n'est naturellement pas vrai, et les processus peuvent \u00e9galement acc\u00e9der \u00e0 d'autres \u00e9quipements.<\/p>\n
Au moment o\u00f9 un processus demande une op\u00e9ration d'entr\u00e9e\/sortie, le processus passe \u00e0 un \u00e9tat bloqu\u00e9, attendant que l'I\/O se termine. Si l'I\/O est adress\u00e9e \u00e0 un disque dur, cette op\u00e9ration peut prendre jusqu'\u00e0 plusieurs ms ou plus, et le processeur sera inactif pendant ce temps. \u00c0 ce stade, le planificateur peut utiliser le processeur pour un autre processus. La prochaine d\u00e9cision que le planificateur devra prendre est de d\u00e9terminer quand le processus terminera son I\/O. Lorsqu'un tel \u00e9v\u00e9nement se produit, une interruption se produira et le syst\u00e8me d'exploitation transf\u00e9rera le processus ayant demand\u00e9 l'I\/O \u00e0 l'\u00e9tat pr\u00eat.<\/p>\n
Consid\u00e9rons un exemple avec plusieurs t\u00e2ches. Chacune n\u00e9cessite 50 ms de temps processeur. Toutefois, la premi\u00e8re va faire appel \u00e0 l'I\/O toutes les 10 ms (qui sera \u00e9galement ex\u00e9cut\u00e9 toutes les 10 ms). Le processus B utilise simplement 50 ms de processeur sans I\/O.<\/p>\n
L'oracle n'est plus l\u00e0.<\/h3>\n \n Essayons maintenant de nous d\u00e9barrasser de l'hypoth\u00e8se selon laquelle le temps d'ex\u00e9cution d'une t\u00e2che est connu. C'est de loin la pire et l'hypoth\u00e8se la plus irr\u00e9aliste de toute cette liste. En fait, dans les syst\u00e8mes d'exploitation ordinaires, le syst\u00e8me d'exploitation sait g\u00e9n\u00e9ralement tr\u00e8s peu sur le temps d'ex\u00e9cution des t\u00e2ches, alors comment construire un planificateur sans savoir combien de temps une t\u00e2che va s'ex\u00e9cuter ? Pourrait-on utiliser certains principes de RR pour r\u00e9soudre ce probl\u00e8me ?<\/p>\n
Conclusion<\/h3>\n \n Nous avons examin\u00e9 les id\u00e9es de base sur la planification des t\u00e2ches et \u00e9tudi\u00e9 deux familles de planificateurs. Le premier ex\u00e9cute la t\u00e2che la plus courte en premier et augmente ainsi le temps de rotation, tandis que le second se divise \u00e9galement entre toutes les t\u00e2ches, am\u00e9liorant le temps de r\u00e9ponse. Les deux algorithmes sont mauvais l\u00e0 o\u00f9 les algorithmes de l'autre famille sont bons. Nous avons \u00e9galement examin\u00e9 comment l'utilisation parall\u00e8le du CPU et de l'I\/O peut am\u00e9liorer les performances, mais nous n'avons pas r\u00e9solu le probl\u00e8me de la clairvoyance de l'OS. Lors de la prochaine s\u00e9ance, nous \u00e9tudierons un planificateur qui regarde le pass\u00e9 r\u00e9cent et essaie de pr\u00e9dire l'avenir. Il s'appelle la file d'attente \u00e0 r\u00e9troaction multi-niveau.habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"\u0412\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440! \u0425\u043e\u0447\u0443 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0432\u0430\u0448\u0435\u043c\u0443 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u044e \u0441\u0435\u0440\u0438\u044e \u0441\u0442\u0430\u0442\u0435\u0439-\u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u0432 \u043e\u0434\u043d\u043e\u0439 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0439 \u043d\u0430 \u043c\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043b\u0438\u0442\u0435\u0440\u0430\u0442\u0443\u0440\u044b \u2014 OSTEP. \u0412 \u044d\u0442\u043e\u043c \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0433\u043b\u0443\u0431\u043e\u043a\u043e \u0440\u0430\u0431\u043e\u0442\u0430 unix-\u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u043e\u043d\u043d\u044b\u0445 \u0441\u0438\u0441\u0442\u0435\u043c, \u0430 \u0438\u043c\u0435\u043d\u043d\u043e \u2014 \u0440\u0430\u0431\u043e\u0442\u0430 \u0441 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0430\u043c\u0438, \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u043c\u0438 \u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0449\u0438\u043a\u0430\u043c\u0438, \u043f\u0430\u043c\u044f\u0442\u044c\u044e \u0438 \u043f\u0440\u043e\u0447\u0438\u0438\u043c\u0438 \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u043c\u0438 \u043a\u043e\u043c\u043f\u043e\u043d\u0435\u043d\u0442\u0430\u043c\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e \u041e\u0421. \u041e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0432\u0441\u0435\u0445 \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u043e\u0432 \u0432\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0432\u043e\u0442 \u0442\u0443\u0442. […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":23990,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-32158","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t