Betriebssystem ZHAW

Problemstellung: Das grösste Problem des Scheduler ist, dass die benötigten Betriebsmittel für die einzelnen Prozesse nicht im Vorfeld bekannt sind. Darum lässt sich keine optimale Planung erstelle, sondern der Scheduler muss dynamisch auf geänderte Anforderungen reagieren.

Scheduler regelt die zeitliche Ausführung mehrere Prozesse in Betriebssystemen. Man kann in grob in unterbrechende(preemptive) und unterbrechende(nonpreemptive) aufteilen.

System und ihre Anforderungen an den Scheduler:

Batch-Systeme:

Ankommende Aufträge werde in eine Warteschlage eingereiht und jedes Mal, wenn in Job abgearbeitet ist, kommt der nächste aus der Schlange dran.

Interaktive Systeme (Desktop PC)

Der Benutzer legt Wert auf kurze Antwortzeit. Wenn er beispielweise in einem Texteditor eine Tastatureingabe tätigt, sollte der Text sofort erscheinen.

Real Time Systeme:

Das System muss garantieren, dass ein Prozess eine Aufgabe innerhalb einer vorgegebenen Zeitspanne abgearbeitet haben muss.

Hard --> in 100% Fällen garantiert

Soft --> Zeitlimit darf in kleinen Prozentsatz der Fälle überschritten werden.

Man kann in grob in unterbrechende(preemptive) und unterbrechende(nonpreemptive) aufteilen.

Bewertungskriterien:

Antwortzeit: Wie lange geht es bis Task reagiert?

Durchsatz: Wie viel Tasks pro Zeit werden verarbeitet?

Fairness: werden Tasks vernachlässigt?

Starvation: können Tasks nie an die Reihe kommen?

Implementierung/Overhead: wie aufdenig ist die Implementierung des Verfahrens?

Nonpreemptive Scheduling

• First Come First Served: Prozesse in ihrer Reihenfolge ihres Eingangs bearbeiten. Neuzuteilung der Prozess findet wieder statt, wenn der laufende Prozess zu warten beginnt oder seine Ausführung beendet ist.
• Shortest Job First: Die kleine Prozesse werden bevorzugt.Es lässt sich in Fällen einsetzen, in denen die benötigte Rechenzeit für die einzelne Aufgaben aus Erfahrungswerten gut vorhergesagt werden kann
• Priority Scheduling:Bei dieser Strategie wird jedem Prozess eine Priorität zugeordnet. Die Abarbeitung erfolgt dann in der Reihenfolge der Prioritäten.Diskussion: Prozesse mit tiefen Prioritäten können verhungern, mögliche Abhilfe --> dynamische Prioritäten, Prioritäten in Funktion der zeit anpassen.

Preemptive Scheduling

• Round Robin:  Wie bei FCFS aber mit kurzen zeitspannen(q). Einem Prozess wird die CPU für eine Zeitspanne zugeteilt.
• Multilevel Scheduling: In üblichen Systemen verschiedene Arten von Jobs: batch, interaktiv, systembezogen, rechenintesivJobs erhalten je nach Art verschiedene Prioritäten, für jede Priorität eine Queue, Scheduler wählt immer Jobs mit höchster Priorität
• Multilevel Feedback Scheduling: Bei diesem Verfahren gibt es mehrere Warteschlangen unterschiedlicher Priorität. Prozesse werden in Abhängigkeit von ihrem bisherige Ressourcenverbrauch dynamisch in eine dieser Warteschlangen eingeordnet

Unix Scheduling TRADITIONELL

Prioritäten:

• Basiert auf Prozesstyp und Geschichte (verbrauchte CPU-Zeit)
• Tiefer Wert = hohe Priorität

CPU und nice Komponenten so gewählt, dass Prioritätsband nicht verlassen werden kann.

Während dem Laufen:

        Wird ein Prozess mehrmals vom Zeitgeber unterbrochen(60 mal pro Sekunde)

        Der Usage Counter wird jeweils inkrementiert zu Beginn des Zeitintervalls

Unix fair Share Scheduling (FSS)

Versucht die CPU fair auf die verschiedenen Gruppen von Prozessen zu verteilen. Wenn beispielweise 4 Benutzer gleichzeitig jeweils einen Prozess ausführen teilt der Scheduler die verfügbaren CPU-Zyklen so, dass jeder Benutzer 25% aller Zyklen bekommt.

Real Time Systeme (Robotik, Laborexperimente, Luftfahrt usw.)

Systeme die auf Ereignisse in der „äusseren Welt“ reagieren, Ereignisse finden in der „reellen Zeit“ statt. Es gibt Hard und Soft Real Time Systeme

Typische Eigenschaften:

• zeitkritische Tasks wiederholen sich in regelmässigen Abständen
• Dauer und die benötigten Betriebsmittel sind bekannt

Systeme verhalten sich korrekt, wenn

• Das logische Resultat einer Berechnung stimmt
• Das Resultat zum richtigen Zeitpunkt ausgeliefert wird

Hard Real Time Systeme(Flugzeugsteuerung, Landeanflug)

• Deadlines müssen eingehalten werden, sonst Ausfall des Systems

Soft Real Time Systeme (Bank überweisung)

                Deadlines sollten eingehalten werden, sonst schwerwiegende Konsequenzen

3 Real Time Task Klassen

• Kritische Tasks(periodische, asynchrone, sporadische Tasks)
• Nicht kritische, aber notwendige Tasks
• Nicht notwendige Tasks(nice to have)

Rate Monotonic Scheduling (RMS)

Für unterbrechbare, periodische Jobs. Die Prioritäten werden statisch anhand Periodendauer eines Jobs festgelegt, je kürzer Periodendauer eines Jobs, desto höher ist seine Priorität.

Task müssen unterbrechbar, periodisch und unabhängig sein.

Was ist daran so interessant? Grenze für erfolgreiches Scheduling kann berechnet werden.

Rechenzeit(C)/Periode(T) = Auslastung(U≤1)à zu optimistisch, nur bei perfektem Schedule möglich

Korrekter Scheduler für n Tasks

Garantiert bei Einhaltung folgender Grenze

Bei Einhaltung obiger Grenze:

                Schedule immer garantiert, aber eher konservativ für grosse n für 70% CPU Auslastung

Deadline Scheduling

Idee: Tasks zum richtigen Zeitpunkt starten resp. Beenden

Funktionsweise: Alle zu dem betrachteten Zeitpunkt bereitstehende Task werden nach aufsteigenden Fertigstellungsterminen geordnet.

Der Task der als erste fertig sein muss erhält den Prozessor,

RT-Linux

Antwortzeiten in der Grössenordnung von Mikrosekunden

• Abhängig von Treibern: wie lange wird die CPU blockiert
• Abhängig von anderen RT-Tasks

Kritische real-time Tasksà foreground tasks

                Threads

                Direktzugriff auf Hardware & Interrupts

Nicht kritische Tasksà background tasks

                Linux tradionell asl taks

                Visualisierung

                Vernetzung etc.

Beispiel Vorlesung, Milch Kaufen gehen 2 Mitbewohner "Kühlschrank-Problem"

Race Condition

• Mindestens 2 Tasks greifen auf gemeinsame Daten zu
• Mindestens 1 Zugriff ist ein Schreibzugriff
• Das Resultat hängt von Ausführungsreihenfolge der beteiligten Tasks ab

Mögliche Abläufe der Programme

• Unabhängig
  • Keine gegenseitige Beeinflussung
  • Nutzung verschiedener Ressourcen
  • Keine Synchronisation/Koordination notwendig
• Abhängig
  • Programm kooperieren
  • Nutzen Daten und Ressourcen gemeinsam
  • Zugriff muss synchronisiert bzw. koordiniert werden

Lösung für Kühlschrankproblem --> kritischer Abschnitt (abschliessbarer Kühlschrank, der, der einkaufen geht hat den Schlüssel)

Taskzugriff auf gemeinsame Daten/Ressourcen --> Task befindet sich in seinem kritischen Abschnitt

Aufenthalt im kritischen Abschnitt, muss gegenseitig ausschließend seinà zu jedem Zeitpunkt befindet sich höchstens ein Task im kritischen Abschnitt

Zutritt zum kritischen Abschnitt --> nur über „Erlaubnis“

Gegenseitiger Ausschluss --> Mutual exclusion = Mutex

Support für gegenseitigen Ausschluss muss folgende Anforderungen erfüllen:
- nur ein Task darf sich in seinem kritischen Abschnitt aufhalten (Tasks aus der
Menge der Tasks, die auf die gemeinsamen Daten oder Ressourcen Zugriff
haben)
- ein Task, der sich nicht im kritischen Abschnitt befindet und anhält, darf dies
nur tun ohne andere Tasks zu beeinflussen
- wartet ein Task auf Eintritt in den kritischen Abschnitt, muss ihm dieser irgend
wann auch gewährt werden
- wenn sich kein Task im kritischen Abschnitt befindet, muss jedem Task der in
den kritischen Abschnitt eintreten möchte, sofort Eintritt gewährt werden
- es dürfen keine Annahmen zur Abarbeitungsgeschwindigkeit von Tasks oder zur
Anzahl Prozessoren gemacht werden
- ein Task bleibt nur für eine endliche Zeit in seinem kritischen Abschnitt

• Reine Softwarelösungen
  • Software-Algorithmen, deren Korrektheit von keinen weiteren Bedingungen abhängt

• Hardwarelösungen
  • Unterstützung durch spezielle Maschineninstruktionen
• Lösungen mit Hilfe des Betriebssystems
  • stellen dem Anwender Funktionen und Datenstrukturen zur Verfügung
  • Semaphore, Mutexes, etc.
• Lösungen zusammen mit Programmiersprache
  • Monitore, z.B. Java

Software Lösung 1

Mittels Busy Wait:

• Task wartet aktiv
• Er konsumiert Rechenzeit, bis Scheduler einen Task-Switch durchführt
• Wird auch Spinnlock genannt

Diskussion:

• Gegenseitiger Ausschluss wird zwar erreicht, aber Tasks können nur abwechselnd den kritischen Abschnitt durchlaufen

Semaphore

Der Semaphor ist eigentlich eine Datenstruktur(integer), die zugriff erlauben und verweigern kann auf eine Ressource in einer Multi-Processing Umgebung.

Operationen auf Semaphore:

• Wait(S) Semaphor schliessen auch P(S), down(S)
• Post(S) Semaphor öffnen auch V(S), Up(S),signal(S)

Vorteile:

• Kein Busy wait
• Wartende Tasks
  • In Queue eingereith
  • Blockieren bis Sperre Frei

Probleme:

• Wait(s) & post(s) ev. Über mehrere Tasks verteilt
  • Schwierig den Überblick zu behalten à fehleranfällig
  • Fehler schwierig zu finden, treten nur unter bestimmten Bedingungen auf
  • Anwendung muss in allen Tasks korrekt sein

Monitore

Ist ein Softwaremodul, die Daten Prozeduren und eine Initialisierungssequenz enthält. Jedes Java Objekt ist ein Monitor. Eingänge in den Monitor sind synchronized Methoden

Funktionsweise:

• Zugriff auf lokale Variable nur über Monitormethoden
• Zutritt in Monitor mit Aufruf einer dieser Methoden
• Nur ein Task kann Code innerhalb des Monitors ausführen
• Andere Tasks: warten auf Eintritt, warten auf Bedingung im Wartebereich