CPU-Scheduling - Zusammenfassung Wirtschaftsinformatik 2 PDF

Preview

Summary

Sommersemester, Wirtschaftsinformatik 2...

Description

CPU-Scheduling Scheduling-Algorithmen sind für Realtime-System sinnvoll? - Minimal Deadline First: Prozess mit kleinster Zeitschranke zuerst - Polled Loop: alle Geräte (Ereignisquellen) werden zyklisch nach ansthendem Ereignis abgefragt, dieses wird gleich bearbeitet - Interrupt gesteuert: diese Systeme warten z. B. in Warteschleife auf Interrupts von Ereignisquellen und führen dann geeignete ISR aus - Echtzeitsysteme haben andere Strategie bei Auswahl des nächsten Jobs als batch- und dialogorientierte Systeme - Schnelle, berechenbare Reaktion wichtig - Hard real time, muss schnell ragieren - Soft real time, gewisse Verzögerung ok Aufgabe Dispatcher und Scheduler im Prozess-Managment? - Scheduler: Komponente für Planung der Betriebsmittelzuteilung - Dispatcher: Komponente die dann tatsächlichen Prozesswechsel ausführt Geeignete Scheduling-Verfahren für Batch- und Dialogsysteme? - Batchsysteme: - First Come First Serve (FCFS): Aufträge werden vom System in der Reihenfolge des Eintreffens bearbeitet - Shortest Job First (SJF): Job bzw. Prozess mit der geringsten Bedienzeit zuerst - Dialogsysteme: - Round Robin (RR): FCFS in Verbindung mit einer Zeitscheibe (Quantum). Alle Prozesse gleich wichtig. Prozess erhält Quantum, nach Ablauf wird Prozess unterbrochen und anderer Prozess erhält die CPU. Unterbrochener Prozess kommt hinten in Warteschlange und kommt erst dran wenn andere Prozesse ihr Quantum verbraucht oder unterbrochen wurden. Wichtig ist die Länge der Zeitscheibe für Leistung des Systems. - Priority Scheduling (PS): Prozess mit höchster Priorität zuerst  Verwaltung von Prozessen ist Voraussetzung Preemptive vs. Non-preemptive Scheduling? - non-preemptive: heißt auch “run-to-completion”-Verfahren - Prozess darf nicht unterbrochen werden, bis er seine Aufgaben vollständig erledigt hat - Bsp. First Come First Serve (FCFS), Shortest Job First (SJF) Windos und Linux sind keine echten Realtime-Systeme, wieso? - können keine harten Realzeitbedingungen unterstützen - „Realtime-Prozesse“ vorhanden, aber Kontextwechsel für diese ist nicht deterministisch Wie verhindert Windows, dass Threads mit niedriger Priorität verhungern? - verhungern möglich, da rechenintensive Threads mit höherer Priorität immer bevorzugt werden - Mechanismus ist implementiert, der einmal pro Sekunde prüft, ob ein Thread schon 300ms oder länger die CPU trotz aktiven Zustand nicht mehr hatte

-

Im positiven Fall wird Priorität auf 15 angehoben und das Quantum verdoppelt Nach CPU erhalt wird er wieder auf alten Zustand gesetzt

Scheduling Algorithmus Shortest Remaing Time First (SRTF) realisierbar? - Prozess mit kürzester noch verbleibender Zeit wird als nächstes gewählt (optimal für Dialogprozesse) - Kaum realisierbar da im Betriebssystem keine Informationen über verbleibende Prozesszeit vorliegen Aufbau und Nutzung Run-Queue unter Linux? - ist zentrale Datenstruktur des Schedulers - für jede CPU wird eigene Run-Queue verwaltet - Loadbalancing-Mechanismus verteilt Prozesse auf CPU´s - Datenstruktur enthält Zeiger auf eigentliche Prozess-Queues - Werden durch Datenstruktur prio_array repräsentiert - Unterscheidung von aktiven und abgelaufenen (expired) Prozesen - Aktive Queue: Prozesse mit einem Quantum >0 - Expired Queue: Prozesse mit abgelaufenem Quantum, Prozess wird umgehend umgehängt - Wenn alle Prozesse der active-Queue ihr Quantum abgearbeitet haben wird Quantum für alle expired-Queue Prozesse neu ermittelt - Zeiger werden entsprechend verwaltet und ausgetauscht Statische und effektive (dynamische) Priorität, der Bonus und Quantum für Linus-Scheduling? - statische Priorität wird bei Prozessstart vergeben - effektive Priorität wird zur Laufzeit ermittelt - Kernel verwaltet für jeden Prozess einen Bonuswert der wird zur statischen Priorität addiert - Auswahl des nächster Prozess wird davon unmittelbar beeinflusst - Wertbereich des Bonus liegt bei -5 ( Verbesserung der Priorität, weil 0 am besten) und +5 (Verschlechterung der Prioriät) - Prozesse die auf Ein- und Ausgabe warten (schlafen) erhalten Bonus  interaktive Prozesse begünstigt - Quantum wird anhand statischer Priorität ermittelt - Höhere Priorität, umso höher auch Quantum Ermittlung des nächsten zu aktivierenden Prozess unter Linus-Scheduler? - in run-queue wird für jede Priorität eine Liste von Prozessen in RRVerfahren - verbraucht der aktive Prozess sein Quantum oder wird unterbrochen, wird nächster Prozess mit höchster Priorität aus RR-Queue aktiviert - alle Prozesse einer Prioritätsqueue müssen abgearbeitet sein, bevor die nächst niedrigere Prioritätsqueue abgearbeitet - laufende Prozess wird unterbrochen wenn ein Prozess mit höherer Priorität ablaufbereit wird Priority Boost unter Windows? - Priorität des Thread wird angehoben wenn er auf Ein-/Ausgab wartet

-

Er bekommt so nach der Wartezeit die CPU schneller wieder zugeteilt Priorität wird maximal auf 15 angehoben Anhebung hängt davon ab worauf gewartet wird Gerätetreiber des Gerätes, an dem gewartet wird entscheidet Priorität wird aber anschließend wieder Zug für Zug herabgesetzt Solange Basispriorität erreicht wird, setzt jedes abgelaufene Quantum die Priorität des Threads um eins zurück Höher priorisierte Threads können bei der Reduktion ein Zeitquantum jederzeit unterbrechen Zeitquantum wird erst aufgebraucht bevor die Priorität eins runter gesetzt wird Priority Boost kann durch erneutes Warten auf Ein-/Ausgabe erneut ausgelöst werden

Quantum Stretching bei Windows? - Quantum Stretching: lange wartende GUI-Threads bekommen Priorität 14 und das Quantum wird verdoppelt - Nach Abarbeitung des Zeitquantums wird Priorität wieder auf Basispriorität herabgesetzt und Zeitquantum zurückgesetzt - Dynami Boost: Unterstützung von typischen GUI-Threads mit langen Ein-/Ausgabe Wartezeiten durch eine Kombination aus einer Veränderung der dynamischen Priorität...