Was versteht man unter Scheduling?  =Verteilung

Unter Scheduling versteht man das Koordinieren von kongruierenden Prozessen, das eine Maximierung der Auslastung und eine Minimierung der Antwortzeiten zum Ziele hat.

Scheduling wird notwendig, wenn die Anzahl der gleichzeitig laufenden Prozesse die Anzahl der physikalischen Prozessoren übersteigt. Die Verwaltung kann dezentral (Prozesse selbst) oder zentral erfolgen. Es gibt zwei grundlegende Modelle für zentrale Scheduling-Verwaltung:

FIFO wie bei Supermarktkasse äquivalent in durchschnittlicher Wartezeit, Antwortzeit und Durchsatz
LIFO wie beim Stack
RANDOM  
FEP klassisches Verfahren
jeder Prozess erhält eine Priorität.
nächster abzuarbeitender Prozess wird nach Priorität ausgewählt
Abarbeitung wird nicht unterbrochen
Prozesse mit gleicher Priorität werden gemäß FIFO zugeteilt

Warum ist Prozessorzuteilung wichtig?

NProzessoren << NProzesse

Welche Strategien der Prozessorzuteilung werden unterschieden?

Es ist nicht möglich CPU-Auslastung und Durchsatz zu maximieren und gleichzeitig Warte- und Antwortzeit zu minimieren. Deshalb müssen alle Scheduling Algorithmen Kompromisse eingehen.

Nach welchen Kriterium richtet sich das Scheduling Verfahren?

Dies hängt in erster Linie vom Einsatzgebiet des Systems ab:

Was ist das deterministische Modell?

Bei diesem Modell werden die Schedules vor der Ausführung berechnet. Dies funktioniert natürlich nicht in interaktiven offenen Systemen, sondern nur in geschlossenen Systemen mit fester Prozessanzahl und vordefinierter Betriebsmittelnutzung mit statischen Ablauf. In Dialogsystemen wird deshalb das offene probabilistische System verwendet, da hier Anzahl der Prozesse und Betriebsmittelnutzung dynamisch erfolgen...

Deterministisches Scheduling

1. P1, P2, … Pn lassen sich in Teilprozessfolgen zerlegen, z.B. pi = {pi1, pi2, … pin} zerlegen

2. Die Abarbeitungszeit jedes Prozesses ist bekannt.

3. Alle zeitlichen Abhängigkeiten zwischen den Prozessen sind bekannt.

4. Es existieren keine weiteren Restriktionen.

 

Was ist das probabilistisches Modell?

Die Entscheidung welcher Prozess den Prozessor bekommt, wird dynamisch wärend der Prozessabarbeitung gefällt. Hierbei gibt es einige wichtige Größen, welche als stochastische Variablen zur Berechnung herangezogen werden können. Die Warteschlangentheorie ist wichtiges Mittel für Untersuchungen. (Alle Prozesse welche den Prozessor fordern werden in eine Warteschlange eingereiht).

Ein System besteht aus drei Prozessen P1, P2 und P3.

P1: {P11(3), P12(2), P13(2), P14(5) } P2: {P21(5), P22(7) },  P3: {P31(5), P32(2) }

Weiterhin existieren folgende zeitliche Abhängigkeiten:

P21 vor P12, P12 vor P22, P13 vor P31, P14 vor P32, P22 vor P32

Zeichne den Präzedenzgraphen und das Gantt - Diagramm für eine ausführende Maschine mit einem Prozessor.

Das Gantt-Diagramm ist ein Ablaufplan für die Prozessorzuteilung. Die Abszisse entspricht der Prozessorzeit in äquidistanten Zeitquanten. Die Ordinate entspricht den einzelnen Prozessoren. Typische Auswahlkriterien der nächsten Prozesse sind:

1) LPT (longest processing time) -->  maximaler Systemdurchsatz

2) SPT (shortest processing time) -->  minimale Antwortzeit

Erstes Diagramm ohne Entzug

Zweites Diagramm mit Entzug plus Migration

Gegeben sei ein System mit 5 rechenbereiten Prozessen, die folgende Bedienzeitanforderungen t(e) (execution time) und Prioritäten besitzen. (höhere Zahlen bedeuten höhere Prioritäten):

Prozess t (e) Priorität
A 5 2
B 2 3
C 7 5
D 4 3
E 1 1

Gib die Abarbeitungsreihenfolge und die durchschnittliche Verweildauer für die Strategien FIFO, LIFO, FEP, SJN und Round Robin an.

FIFO First in Forst Out Prozesse werden streng in ihrer Reihenfolge abgearbeitet
LIFO Last in First Out Prozess, der als letzter in Warteschlange tritt, wird abgearbeitet
FEP Fixed Extrenal Priorities Prozess mit höchster Priorität wird abgearbeitet
SJN Shortest Job Next nach kürzester Bedienzeit
Round Robin Alle Prozesse im System erhalten reihum den Prozessor für eine bestimmte Zeiteinheit zugeteilt.

 Lösung:

    Verweildauer
FIFO A(5) - B(2) - C(7)- D(4) - E (1) [5+(5+2)+(7+7)+(14+4)+(18+1)]/5 = 12,6 
LIFO E(1) - D(4) - C(7) - B(2) - A(5) [1+(1+4)+(5+7)+(12+2)+(14+5)]/5 = 10,2
FEP C(7) - B(2) - D(4) - A(5) - E(1) [7+(7+2)+(9+4)+(13+5)+(18+1)]/5 = 13,2
R.Robin ABCDE ABCD ACD ACD AC CC  ???
SJN E(1) - B(2) - D(4) - A(5) - C(7) [1+(1+2)+(3+4)+(7+5)+(12+7)]/5 =  8,4

In einem System befinden sich 5 Prozesse, die nach Round Robin zugeteilt werden. Jeder Kontextwechsel dauert 1 ms. Genau einer der 5 Prozesse ist für die Entgegennahme und Verarbeitung der Benutzereingabe zuständig. Wie groß ist die mittlere Reaktionszeit des Systems, wenn die Zeitscheibenlänge a) 1 Sekunde bzw. b) 10 Millisekunden beträgt? Wie groß ist der Anteil an Prozessorzeit, den die Prozesse erhalten bei einer Zeitscheibenlänge von a) 1 Sekunde bzw. b) 10 Millisekunden?

???

 

Was ist das Single-Server-Modell?

Eine Warteschlange nimmt Prozesse in einem bestimmten Abstand (A) auf. Der Scheduler entnimmt nach einer gewissen Wartezeit (W) im Pool einen Prozess und führt diesen in einer bestimmten Zeit (B) aus .

GRUNDLAGEN

Präemptiv (= mit Entzug), ohne Prioritäten Prozesse werden zyklisch für kurze Zeit ausgeführt, entweder sind alle Prozesse gleichberechtigt oder sie erhalten Prioritäten

Kontextwechsel

1) Umgebung des unterbrochenen Prozesses sichern

2) Scheduler bestimmt den „nächsten“ Prozess

3) Umgebung des „nächsten“ Prozesses restaurieren

4) Rücksprung aus dem BS zum „nächsten“ Prozess

tC („context switch time“) wird beim context switch verbraten

Präemptiv (= mit Entzug), mit Prioritäten

shortest elapsed time (SET)

aufwändigste Schedulstrategie; zyklische Neuberechnung der Prioritäten; die meisten Desktopsysteme benutzen modifizierte Varianten

c geeignet gewählte Rechenzeit

te dem Prozess bisher gewährte Prozessorzeit („elapsed time“)

steigt te, dann sinkt PSET (um so seltener erhält er den Prozessor); lange Prozesse schreiten immer langsamer voran

Verfahren „bevorteilt“ kurze Prozesse

Gegeben sei ein System mit Prozessen, die bestimmte Bedienzeitanforderungen stellen. Zu t=0 treten die Prozesse A, B, C und E ins System in dieser Reihenfolge ein. Bei t=4 kommt D hinzu. Die Tabelle stellt dies dar.

Prozess t(v) t(r) Priorität
A 7 0 2
B 3 0 1
C 1 0 3
D 4 4 1
E 2 0 2

tv repräsentiert die jeweilige Bedienzeitanforderung in Zeiteinheiten. Die Priorität ist umgekehrt proportional zum Zahlenwert. tr ist die Eintrittszeit ins System („release time“)

Zeichne die GANTT-Diagramme für die Zuteilungsverfahren

a) FIFO („first in, first out“)

b) FEP („fixed external priorities“) ohne Entzug

c) SJN („shortest job next“)

d) RR („round robin“)

e) SRTF („shortest remaining time first“) mit Prioritäten gemäß Prior = 100/ t(rem)

Bestimme auch die Verweildauer, vernachlässige dabei tc.

FIFO A(7) - B(3) - C(1) - D(4) - E(2)
FEP B(3) - A(7) - D(4) -E(2) - C(1)
SJN C(1) - E(2) - B(3) - D(4) - A(7)
RR ABCE ABDE ABD AD AD AA (andere Lösung als Baumgärtel)
SRTF ????