Die Bearbeitungszeit jeder Aufgabe ist bekannt.<\/li>\n<\/ol>\nScheduler-Metriken<\/h3>\n \n Neben einigen Annahmen zur Last ben\u00f6tigen wir auch ein Werkzeug zum Vergleich verschiedener Scheduling-Politiken: die Scheduler-Metriken. Eine Metrik ist lediglich ein Ma\u00df f\u00fcr etwas. Es gibt eine Reihe von Metriken, die verwendet werden k\u00f6nnen, um Scheduler zu vergleichen.<\/p>\n
Als Beispiel verwenden wir eine Metrik, die genannt wird Bearbeitungszeit<\/b> (turnaround time). Die Bearbeitungszeit einer Aufgabe wird als Differenz zwischen dem Abschlusszeitpunkt der Aufgabe und dem Zeitpunkt, an dem die Aufgabe im System ankommt, definiert.<\/p>\n
Tturnaround = Tcompletion \u2212 Tarrival<\/u><\/p>\n
Da wir angenommen haben, dass alle Aufgaben zur gleichen Zeit eingegangen sind, ist Ta = 0 und somit Tt = Tc. Dieser Wert wird sich nat\u00fcrlich \u00e4ndern, wenn wir die obigen Annahmen anpassen.<\/p>\n
Eine andere Metrik ist Fairness<\/b> (Fairness, Gerechtigkeit). Leistung und Fairness sind oft gegens\u00e4tzliche Eigenschaften im Scheduling. Ein Scheduler kann die Leistung optimieren, jedoch auf Kosten der Wartezeit anderer Aufgaben, wodurch die Fairness verringert wird.<\/p>\nFIRST IN FIRST OUT (FIFO)<\/h3>\n
\n Der grundlegendste Algorithmus, den wir umsetzen k\u00f6nnen, wird 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, w\u00e4hrend er die Aufgabe ziemlich gut erf\u00fcllt.<\/p>\n
Betrachten wir ein einfaches Beispiel. Angenommen, 3 Aufgaben wurden gleichzeitig eingereicht. Nehmen wir an, dass Aufgabe A etwas fr\u00fcher als die anderen eingetroffen ist, sodass sie im Ausf\u00fchrungsreihenfolge vor den anderen steht, 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
Es zeigt sich, dass unterschiedliche Ausf\u00fchrungszeiten von Aufgaben die Produktivit\u00e4t des FIFO-Algorithmus negativ beeinflussen. Angenommen, Aufgabe A ben\u00f6tigt 100 Sekunden, w\u00e4hrend B und C jeweils 10 Sekunden ben\u00f6tigen.<\/p>\n
Konvoieffekt<\/b>, wenn einige kurzzeitige Verbraucher einer Ressource hinter einem schweren Verbraucher in der Warteschlange stehen. Das ist vergleichbar mit einer Schlange im Supermarkt, wenn vor Ihnen ein Kunde mit einem vollen Einkaufswagen steht. Die beste L\u00f6sung f\u00fcr das Problem ist, an die n\u00e4chste Kasse zu wechseln oder einfach tief durchzuatmen und zu entspannen.<\/p>\nShortest Job First<\/h3>\n
\n Kann man eine solche Situation mit schweren Prozessen irgendwie l\u00f6sen? Nat\u00fcrlich. Ein anderer Planungstyp wird genanntShortest Job First<\/b> (SJF). Sein Algorithmus ist ebenfalls recht primitiv \u2013 wie der Name schon sagt, werden zuerst die k\u00fcrzesten Aufgaben nacheinander ausgef\u00fchrt.<\/p>\n
50 anstelle von 110 betr\u00e4gt<\/b>, was praktisch doppelt so gut ist.<\/p>\n
F\u00fcr die Annahme, dass alle Aufgaben gleichzeitig ankommen, scheint der SJF-Algorithmus der optimalste zu sein. Unsere Annahmen scheinen jedoch immer noch unrealistisch. Diesmal \u00e4ndern wir Annahme 2 und stellen uns vor, dass Aufgaben zu beliebigen Zeiten eintreffen k\u00f6nnen und nicht alle gleichzeitig. Welche Probleme k\u00f6nnte dies verursachen?<\/p>\n
Shortest Time-to-Completion First (STCF)<\/h3>\n \n Um die Situation zu verbessern, lassen wir die Annahme 3 falleng, dass das Programm l\u00e4uft und bis zur Fertigstellung arbeitet. Au\u00dferdem ben\u00f6tigen wir Hardwareunterst\u00fctzung und wie Sie vielleicht erraten haben, werden wir einen Timer<\/b> verwenden, um laufende Aufgaben zu unterbrechen und Kontexte zu wechseln.<\/b>So kann der Scheduler bei Eintreffen der Aufgaben B und V die Ausf\u00fchrung von Aufgabe A unterbrechen und die Aufgaben B und V zur Bearbeitung annehmen, um danach die Ausf\u00fchrung von Prozess A fortzusetzen. Ein solcher Scheduler wird genannt STCF<\/b>oder Preemptive Job First<\/b>.<\/p>\n
Metrik Reaktionszeit (Response Time)<\/h3>\n \n Daher, wenn wir die Laufzeit der Aufgaben kennen und wissen, dass diese Aufgaben nur die CPU nutzen, wird STCF die beste L\u00f6sung sein. In fr\u00fcheren Zeiten funktionierten diese Algorithmen ganz gut. Jetzt verbringt der Benutzer jedoch die meiste Zeit am Terminal und erwartet eine leistungsf\u00e4hige, interaktive Interaktion. So entstand die neue Metrik \u2014 Reaktionszeit<\/b> (Response Time).<\/p>\n
Die Reaktionszeit wird folgenderma\u00dfen berechnet:<\/p>\n
Tresponse=Tfirstrun\u2212Tarrival<\/u><\/p>\n
Damit wird die Reaktionszeit f\u00fcr das vorherige Beispiel wie folgt sein: A=0, B=0, V=10 (abg=3,33).<\/p>\n
Es stellt sich heraus, dass der STCF-Algorithmus in Situationen, in denen drei Aufgaben gleichzeitig ankommen, nicht so gut abschneidet \u2013 er muss warten, bis die kleinen Aufgaben vollst\u00e4ndig abgeschlossen sind. Daher ist der Algorithmus zwar gut f\u00fcr die Durchlaufzeit-Metrik, jedoch nicht geeignet f\u00fcr die Interaktivit\u00e4tsmetrik. Stellen Sie sich vor, Sie sitzen an einem Terminal und versuchen, Zeichen in einen Editor einzugeben, und m\u00fcssen dabei mehr als 10 Sekunden warten, weil eine andere Aufgabe die CPU beansprucht. Das ist alles andere als angenehm.<\/p>\n
Round Robin<\/h3>\n \n Zur L\u00f6sung dieses Problems wurde ein Algorithmus entwickelt Round Robin<\/b> (RR). Die Grundidee ist ziemlich einfach: Anstatt Aufgaben bis zur vollst\u00e4ndigen Fertigstellung zu starten, f\u00fchren wir die Aufgabe f\u00fcr einen bestimmten Zeitraum (genannt Quantenzeit) aus und wechseln dann zur n\u00e4chsten Aufgabe in der Warteschlange. Der Algorithmus wiederholt diesen Vorgang, bis alle Aufgaben abgeschlossen sind. Dabei muss die Laufzeit 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, muss die Gr\u00f6\u00dfe des Ausf\u00fchrungsfensters ein Vielfaches von 10 sein und 10, 20 oder x*10 betragen.<\/p>\n
Betrachten wir ein Beispiel: Die Aufgaben A, B und C kommen gleichzeitig im System an, und jede m\u00f6chte 5 Sekunden lang arbeiten. Der SJF-Algorithmus wird jede Aufgabe bis zum Ende ausf\u00fchren, bevor er eine andere startet. Im Gegensatz dazu wird der RR-Algorithmus mit einem Zeitfenster von 1 Sekunde die Aufgaben folgenderma\u00dfen durchlaufen (Abb. 4.3):<\/p>\n
Die durchschnittliche Reaktionszeit f\u00fcr den RR-Algorithmus (0+1+2)\/3=1, w\u00e4hrend sie f\u00fcr den SJF (0+5+10)\/3=5 betr\u00e4gt.<\/p>\n
Es liegt nahe, dass das Zeitfenster ein sehr wichtiger Parameter f\u00fcr RR ist: je kleiner es ist, desto h\u00f6her ist die Antwortzeit. Allerdings sollte es nicht zu klein gew\u00e4hlt werden, da auch die Kontextwechselzeit eine Rolle bei der Gesamtleistung spielt. Somit wird die Wahl der Ausf\u00fchrungszeit durch den OS-Architekten festgelegt und h\u00e4ngt von den Aufgaben ab, die darin geplant sind. Der Kontextwechsel ist nicht die einzige operationale T\u00e4tigkeit, die Zeit beansprucht \u2013 ein laufendes Programm bearbeitet auch viele andere Aspekte, wie verschiedene 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 ausgezeichneter Scheduler, wenn es nur um die Antwortzeit-Metrik geht. Aber wie verh\u00e4lt sich die Metrik der Durchlaufzeit bei diesem Algorithmus? Betrachten wir das oben genannte Beispiel, bei dem die Ausf\u00fchrungszeiten A, B, C=5s sind und sie zur gleichen Zeit eintreffen. Aufgabe A wird um 13s abgeschlossen, B um 14s und C um 15s, was zu einer durchschnittlichen Durchlaufzeit von 14s f\u00fchrt. Daher ist RR der schlechteste Algorithmus f\u00fcr die Durchlaufzeiten-Metrik.<\/p>\n
Allgemeiner gesagt ist jeder RR-Algorithmus fair, da er die CPU-Zeit gleichm\u00e4\u00dfig auf alle Prozesse verteilt. Dadurch k\u00f6nnen diese Metriken st\u00e4ndig miteinander in Konflikt geraten.<\/p>\n
So haben wir mehrere gegens\u00e4tzliche Algorithmen und es bleiben zudem einige Annahmen, n\u00e4mlich dass die Zeit f\u00fcr die 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, was nat\u00fcrlich nicht der Fall ist, da Prozesse auch auf andere Hardware zugreifen k\u00f6nnen.<\/p>\n
In dem Moment, in dem ein Prozess eine Ein-\/Ausgabeoperation anfordert, wechselt der Prozess in den Blockierungszustand, w\u00e4hrend er auf den Abschluss der I\/O wartet. Wenn die I\/O an eine Festplatte gesendet wird, kann diese Operation mehrere Millisekunden oder l\u00e4nger in Anspruch nehmen, w\u00e4hrend die CPU zu diesem Zeitpunkt unt\u00e4tig bleibt. In dieser Zeit kann der Scheduler die CPU mit einem anderen Prozess belegen. Die n\u00e4chste Entscheidung, die der Scheduler treffen muss, ist, wann der Prozess seine I\/O abgeschlossen hat. Wenn dies passiert, erfolgt eine Unterbrechung, und das Betriebssystem versetzt den den I\/O anfordernden Prozess in den Bereitschaftszustand.<\/p>\n
Betrachten wir ein Beispiel mit mehreren Aufgaben. Jede ben\u00f6tigt 50 ms CPU-Zeit. Die erste Aufgabe greift jedoch alle 10 ms auf I\/O zu (was ebenfalls alle 10 ms ausgef\u00fchrt wird). Prozess B verwendet einfach die 50 ms CPU ohne I\/O.<\/p>\n
Der Oracle ist nicht mehr<\/h3>\n \n Lassen Sie uns nun das Missverst\u00e4ndnis beseitigen, dass die Ausf\u00fchrungszeit einer Aufgabe bekannt ist. Dies ist im Grunde die schlechteste und unrealistischste Annahme auf der Liste. In der Tat wei\u00df das durchschnittliche Betriebssystem in der Regel sehr wenig \u00fcber die Ausf\u00fchrungszeit von Aufgaben. Wie kann man also einen Scheduler bauen, ohne zu wissen, wie lange eine Aufgabe ben\u00f6tigt? Vielleicht k\u00f6nnten wir einige Prinzipien des RR-Algorithmus nutzen, um dieses Problem zu l\u00f6sen?<\/p>\n
Zusammenfassung<\/h3>\n \n Wir haben die grundlegenden Ideen des Task-Schedulings betrachtet und uns zwei Gruppen von Schedulern angesehen. Der erste startet mit der k\u00fcrzesten Aufgabe und verbessert so die Bearbeitungszeit, w\u00e4hrend der zweite gleichm\u00e4\u00dfig zwischen allen Aufgaben aufschl\u00fcsselt und die Reaktionszeit erh\u00f6ht. Beide Algorithmen sind in den Situationen, in denen die jeweiligen anderen Algorithmen gut abschneiden, nicht optimal. Au\u00dferdem haben wir uns angeschaut, wie die parallele Nutzung von CPU und I\/O die Leistung verbessern kann, ohne jedoch das Problem der Vorhersagbarkeit des Betriebssystems zu l\u00f6sen. Im n\u00e4chsten Abschnitt werden wir einen Scheduler betrachten, der in die j\u00fcngste Vergangenheit schaut und versucht, die Zukunft vorherzusagen. Dieser wird als Multi-Level-Feedback-Warteschlange bezeichnet.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