Die Laufzeit jedes Jobs ist bekannt.<\/li>\n<\/ol>\nMetriken des Schedulers<\/h3>\n \n Neben einigen Annahmen zur Arbeitslast ist auch ein gewisses Vergleichsinstrument f\u00fcr verschiedene Planungsstrategien notwendig: die Metriken des Schedulers. Eine Metrik ist lediglich ein Ma\u00df f\u00fcr irgendetwas. Es gibt eine Reihe von Metriken, die verwendet werden k\u00f6nnen, um Scheduler zu vergleichen.<\/p>\n
Als Beispiel verwenden wir die Metrik, die Durchlaufzeit<\/b> (turnaround time) genannt wird. Die Durchlaufzeit eines Jobs wird als die Differenz zwischen der Abschlusszeit des Jobs und der Ankunftszeit des Jobs im System definiert.<\/p>\n
Tturnaround = Tcompletion \u2212 Tarrival<\/u><\/p>\n
Da wir angenommen haben, dass alle Jobs zur gleichen Zeit eingetroffen sind, ist Ta=0 und somit Tt=Tc. Dieser Wert wird sich nat\u00fcrlich \u00e4ndern, wenn wir die oben genannten Annahmen \u00e4ndern.<\/p>\n
Eine andere Metrik ist die Fairness<\/b> (Gerechtigkeit, Fairness). Leistung und Fairness sind oft gegens\u00e4tzliche Merkmale in der Planung. Zum Beispiel kann ein Scheduler die Leistung optimieren, jedoch auf Kosten der Wartezeiten f\u00fcr andere Aufgaben, wodurch die Fairness verringert wird.<\/p>\nFIRST IN FIRST OUT (FIFO)<\/h3>\n
\n Der einfachste Algorithmus, den wir implementieren k\u00f6nnen, hei\u00dft FIFO oder first come (in), first served (out)<\/b>. Dieser Algorithmus hat mehrere Vorteile: Er ist sehr einfach zu implementieren und erf\u00fcllt alle unsere Annahmen, indem er seine Arbeit ziemlich gut erledigt.<\/p>\n
Betrachten wir ein einfaches Beispiel. Angenommen, 3 Aufgaben wurden gleichzeitig gestellt. Aber nehmen wir an, dass Aufgabe A etwas fr\u00fcher als alle anderen angekommen ist, daher wird sie in der Ausf\u00fchrungsliste vor den anderen stehen, genau wie B im Verh\u00e4ltnis zu C. Nehmen wir an, dass jede von ihnen 10 Sekunden ben\u00f6tigt. Wie w\u00e4re in diesem Fall die durchschnittliche Ausf\u00fchrungszeit dieser Aufgaben?<\/p>\n
Wie sich herausstellt, wirken sich unterschiedliche Ausf\u00fchrungszeiten der Aufgaben \u00e4u\u00dferst negativ auf die Produktivit\u00e4t des FIFO-Algorithmus aus. Angenommen, Aufgabe A ben\u00f6tigt 100 Sekunden, w\u00e4hrend B und C weiterhin jeweils 10 ben\u00f6tigen.<\/p>\n
Konvoieffekt<\/b>, wenn einige kurzfristige Verbraucher einer bestimmten Ressource hinter einem schwergewichtigen Verbraucher in der Schlange stehen. Das ist vergleichbar mit einer Warteschlange im Supermarkt, wenn vor Ihnen ein K\u00e4ufer mit einem vollen Einkaufswagen steht. Die beste L\u00f6sung f\u00fcr dieses Problem ist, an eine andere Kasse zu wechseln oder sich zu entspannen und tief durchzuatmen.<\/p>\nShortest Job First<\/h3>\n
\n Kann man eine solche Situation mit schweren Prozessen irgendwie l\u00f6sen? Nat\u00fcrlich. Ein anderer Typ der Planung nennt sichShortest Job First<\/b> (SJF). Sein Algorithmus ist ebenfalls recht primitiv \u2014 wie der Name schon sagt, werden zun\u00e4chst die k\u00fcrzesten Aufgaben nacheinander ausgef\u00fchrt.<\/p>\n
50 statt 110<\/b>, was praktisch doppelt so gut ist.<\/p>\n
Somit scheint der SJF-Algorithmus f\u00fcr die gegebene Annahme, dass alle Aufgaben gleichzeitig ankommen, der optimalste Algorithmus zu sein. Unsere Annahmen erscheinen jedoch immer noch unrealistisch. Dieses Mal \u00e4ndern wir Annahme 2 und stellen uns vor, dass Aufgaben zu beliebigen Zeiten ankommen k\u00f6nnen und nicht alle gleichzeitig. Welche Probleme k\u00f6nnte das mit sich bringen?<\/p>\n
Shortest Time-to-Completion First (STCF)<\/h3>\n \n Um die Situation zu verbessern, lassen wir die Annahme 3 fallen, dass das Programm gestartet wird und bis zur Fertigstellung l\u00e4uft. Au\u00dferdem ben\u00f6tigen wir Hardwareunterst\u00fctzung und wie Sie sich denken k\u00f6nnen, werden wir einen Timer<\/b> zum Unterbrechen der laufenden Aufgabe und zum Kontextwechsel<\/b>. Dadurch kann der Scheduler etwas unternehmen, wenn die Aufgaben B und C ankommen \u2014 die Ausf\u00fchrung von Aufgabe A beenden und die Aufgaben B und C bearbeiten, um danach die Ausf\u00fchrung von Aufgabe A fortzusetzen. Ein solcher Scheduler wird genannt STCF<\/b>oder Preemptive Job First<\/b>.<\/p>\n
Die Metrik Reaktionszeit (Response Time)<\/h3>\n \n Somit, wenn wir die Laufzeit der Aufgaben und die Tatsache wissen, dass diese Aufgaben nur die CPU nutzen, wird STCF die beste L\u00f6sung sein. Fr\u00fcher waren diese Algorithmen recht effektiv. Allerdings verbringt der Benutzer heutzutage die meiste Zeit an der Konsole und erwartet eine produktive interaktive Interaktion. So entstand die neue Metrik \u2014 Antwortzeit<\/b> (Response Time).<\/p>\n
Die Antwortzeit wird wie folgt berechnet:<\/p>\n
Tresponse=Tfirstrun\u2212Tarrival<\/u><\/p>\n
Somit wird die Antwortzeit f\u00fcr das vorherige Beispiel wie folgt sein: A=0, B=0, C=10 (abg=3,33).<\/p>\n
Und der STCF-Algorithmus ist nicht so gut in Situationen, in denen drei Aufgaben gleichzeitig ankommen \u2013 er muss warten, bis die kleinen Aufgaben vollst\u00e4ndig abgeschlossen sind. Somit ist der Algorithmus gut f\u00fcr die Durchlaufzeit-Metrik, aber schlecht f\u00fcr die Interaktivit\u00e4ts-Metrik. Stellen Sie sich vor, Sie sitzen an einem Terminal und versuchen, Zeichen in einen Editor zu tippen, aber Sie m\u00fcssten mehr als 10 Sekunden warten, weil eine andere Aufgabe den Prozessor besch\u00e4ftigt. Das ist alles andere als angenehm.<\/p>\n
Round Robin<\/h3>\n \n Um dieses Problem zu l\u00f6sen, wurde ein Algorithmus entwickelt Round Robin<\/b> (RR). Die Grundidee ist recht einfach: Anstatt Aufgaben bis zur vollst\u00e4ndigen Fertigstellung auszuf\u00fchren, f\u00fchren wir eine Aufgabe f\u00fcr einen bestimmten Zeitraum (genannt Zeitscheibe) aus und wechseln dann zu einer anderen Aufgabe aus der Warteschlange. Der Algorithmus wiederholt diese Arbeit, bis alle Aufgaben abgeschlossen sind. Dabei muss die Ausf\u00fchrungszeit des Programms ein Vielfaches der Zeit sein, nach der der Timer den Prozess unterbricht. Zum Beispiel, wenn der Timer den Prozess alle x=10 ms unterbricht, dann muss die Ausf\u00fchrungsfenstergr\u00f6\u00dfe ein Vielfaches von 10 sein und entweder 10, 20 oder x*10 betragen.<\/p>\n
Betrachten wir ein Beispiel: Die Aufgaben ABC kommen gleichzeitig im System an und jede von ihnen m\u00f6chte 5 Sekunden lang arbeiten. Der SJF-Algorithmus w\u00fcrde jede Aufgabe bis zum Ende ausf\u00fchren, bevor er die n\u00e4chste startet. Im Gegensatz dazu w\u00fcrde der RR-Algorithmus mit einem Zeitfenster von 1 Sekunde die Aufgaben wie folgt abarbeiten (siehe Abb. 4.3):<\/p>\n
Die durchschnittliche Reaktionszeit f\u00fcr den RR-Algorithmus betr\u00e4gt (0+1+2)\/3=1, w\u00e4hrend sie f\u00fcr SJF (0+5+10)\/3=5 betr\u00e4gt.<\/p>\n
Es ist logisch anzunehmen, dass das Zeitfenster ein sehr wichtiger Parameter f\u00fcr RR ist; je kleiner es ist, desto h\u00f6her ist die Antwortzeit. Man kann es jedoch auch nicht zu klein w\u00e4hlen, da die Zeit f\u00fcr den Kontextwechsel ebenfalls eine Rolle f\u00fcr die Gesamtleistung spielt. Daher wird die Wahl der Ausf\u00fchrungszeitfenster vom OS-Architekten festgelegt und h\u00e4ngt von den Aufgaben ab, die darin ausgef\u00fchrt werden sollen. Der Kontextwechsel ist nicht die einzige Dienstleistung, die Zeit kostet \u2013 das laufende Programm interagiert mit vielen anderen, beispielsweise verschiedenen Caches, und bei jedem Wechsel muss diese Umgebung gespeichert und wiederhergestellt werden, was ebenfalls viel Zeit in Anspruch nehmen kann.<\/p>\n
RR ist ein hervorragender Planer, wenn es nur um die Metrik der Antwortzeit geht. Aber wie verh\u00e4lt sich die Metrik der Durchlaufzeit bei diesem Algorithmus? Betrachten wir das obige Beispiel, bei dem die Ausf\u00fchrungszeiten A, B, C = 5s sind und gleichzeitig eintreffen. Aufgabe A wird um 13 Uhr, B um 14 Uhr und C um 15 Uhr abgeschlossen und die durchschnittliche Durchlaufzeit betr\u00e4gt 14s. Somit ist RR der schlechteste Algorithmus f\u00fcr die Durchlaufzeit-Metrik.<\/p>\n
Im Allgemeinen ist jeder Algorithmus vom Typ RR fair, da er die CPU-Bearbeitungszeit gleichm\u00e4\u00dfig zwischen allen Prozessen verteilt. Daher stehen diese Metriken st\u00e4ndig im Konflikt miteinander.<\/p>\n
Damit haben wir mehrere gegens\u00e4tzliche Algorithmen und es bleiben einige Annahmen \u2013 dass die Zeit der Aufgabe bekannt ist und dass die Aufgabe nur die CPU nutzt.<\/p>\n
Mischung mit I\/O<\/h3>\n \n Zun\u00e4chst entfernen wir die Annahme 4, dass der Prozess nur die CPU nutzt, das ist nat\u00fcrlich nicht der Fall und Prozesse k\u00f6nnen auch auf andere Hardware zugreifen.<\/p>\n
In dem Moment, in dem ein Prozess eine Ein- oder Ausgabeoperation anfordert, wechselt der Prozess in den Zustand 'blocked', in Erwartung des Abschlusses der I\/O. Wenn die I\/O an die Festplatte gesendet wird, kann eine solche Operation mehrere Millisekunden oder l\u00e4nger in Anspruch nehmen, und der Prozessor wird in dieser Zeit unt\u00e4tig sein. In dieser Zeit kann der Scheduler die CPU von einem anderen Prozess nutzen. Die n\u00e4chste Entscheidung, die der Scheduler treffen muss, besteht darin, wann der Prozess seine I\/O abgeschlossen hat. Wenn dies geschieht, tritt eine Unterbrechung auf und das Betriebssystem versetzt den den I\/O anfordernden Prozess in den Zustand 'ready'.<\/p>\n
Betrachten wir ein Beispiel aus mehreren Aufgaben. Jede davon ben\u00f6tigt 50 ms Prozessorzeit. Die erste wird jedoch alle 10 ms auf I\/O zugreifen (das ebenfalls alle 10 ms ausgef\u00fchrt wird). Der Prozess B hingegen verwendet einfach 50 ms Prozessor ohne I\/O.<\/p>\n
Der Oracle ist weg.<\/h3>\n \n Jetzt versuchen wir, die Annahme aufzugeben, dass die Laufzeit einer Aufgabe bekannt ist. Dies ist im Allgemeinen die schlechteste und unrealistischste Annahme aus der gesamten Liste. Tats\u00e4chlich wei\u00df das Betriebssystem in g\u00e4ngigen, durchschnittlichen Systemen normalerweise sehr wenig \u00fcber die Ausf\u00fchrungszeit von Aufgaben, wie w\u00fcrde man also einen Planer ohne das Wissen \u00fcber die Dauer der Aufgabe erstellen? Vielleicht k\u00f6nnten wir einige Prinzipien des RR verwenden, um dieses Problem zu l\u00f6sen?<\/p>\n
Fazit<\/h3>\n \n Wir haben die grundlegenden Ideen der Aufgabenplanung betrachtet und zwei Familien von Planern betrachtet. Der erste startet die k\u00fcrzeste Aufgabe zuerst und erh\u00f6ht so die Durchlaufzeit, w\u00e4hrend der zweite gleichm\u00e4\u00dfig zwischen allen Aufgaben wechselt und die Reaktionszeit erh\u00f6ht. Beide Algorithmen sind dort schlecht, wo die Algorithmen der anderen Familie gut sind. Au\u00dferdem haben wir gesehen, wie die parallele Nutzung von CPU und I\/O die Leistung verbessern kann, aber das Problem mit dem Hellsehen des Betriebssystems nicht gel\u00f6st. Im n\u00e4chsten Kurs werden wir einen Planer betrachten, der in die nahen Vergangenheit schaut und versucht, die Zukunft vorherzusagen. Er hei\u00dft Multi-Level-Feedback-Queue.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