Übungsblatt - Betriebssysteme und verteilte Systeme

Theorie
und Praxis
für Karrieren
von morgen
UNIVERSITÄT SIEGEN
Prof. Dr. Roland Wismüller • Fachgruppe Betriebssysteme und verteilte Systeme • Fachbereich 12 • Hölderlinstr. 3 • 57068 Siegen
Dr.-Ing. Adrian Kacso
Ab jetzt finden die Übungen NICHT mehr im Rechnerpool statt sondern im
Raum H-F 114 -- Di. 10:15.,
Raum H-C 7324 -- Mi. und Do.
Übungsaufgaben zur Vorlesung Betriebssysteme I
Wintersemester 2015/2016
Übungsblatt 10 , 8.01.
Aufgabe 1
(Übung ab 12.01.)
(Schedulingalgorithmen) [TÜ]
Fünf Prozesse treffen zu gegebenen Zeitpunkten in der Bereitliste ein. Es ist bekannt, wie viel Bedienzeit
(Rechnenzeit) sie benötigen. Jeder Prozess hat eine Priorität ( 0 stellt die höchste Priorität dar).
Die folgende Tabelle gibt die Ankunftszeiten, Bedienzeiten und Prioritäten der einzelnen Prozesse wieder.
Prozess
Ankunftszeit
Bedienzeit
Priorität
A
0
8
4
B
3
28
1
C
7
12
0
D
9
3
2
E
15
4
3
Wartezeit
Durchlaufzeit
Mittelwerte:
Betrachten Sie die Ausführung der Prozesse unter verschiedenen Scheduler-Strategien.
Nicht-präemptiv (ohne Verdrängung) d.h. nach der Zuteilung der CPU arbeitet ein Prozess, bis er von selbst
den Prozessor abgibt (oder blockiert).
a) First Come First Served (FCFS)
b) Prioritätsbasiertes Scheduling ( Highest Priority First = HPF)
c) Shortest Job First ( SJF)
Prämptiv ( mit Verdrängung) d.h. der Scheduler kann die CPU entziehen wenn anderer Prozess rechenbereit
geworden ist oder nach Ablauf einer bestimmten Zeit.
d) Round Robin (RR) mit dem Zeitscheibenwert (Zeitquantum) 5
e) HPF
f) Shortest Remaining Time First. Dies ist die prämptive Variante von SJF, die die CPU an den
Prozess mit der kürzesten Restzeit zuweist.
Zeichen Sie die Gantt-Diagramme und berechnen Sie für a)-f) jeweils für jeden Prozess die Wartezeit und
die Durchlaufzeit (Spalte 5/6 in der Tabelle). Berechnen Sie für die fünf Prozesse die mittlere Wartezeit und
die mittlere Durchlaufzeit.
Aufgabe 2
(Scheduling) [TU]
Für die folgenden Teilaufgaben sei folgende Situation gegeben: vier Prozesse treffen zu den angegebenen
Zeiten in der Bereitliste eines Schedulers ein. Von jedem Prozess ist die Bedienzeit (= benötigte Rechenzeit)
und seine Priorität (0 = höchste Priorität) bekannt:
Prozess
Ankunftszeit
Bedienzeit
Priorität
A
0
8
1
B
3
5
0
C
5
4
1
D
7
3
0
Die Prozesse geben die CPU nie freiwillig ab und werden auch nie durch E/A oder sonstige Gründe
blockiert. Der Scheduler entscheidet online, d.h. nur aufgrund der zum Scheduling-Zeitpunkt bereits
vorliegenden Prozesse.
a) Mit einem bestimmten Scheduling-Verfahren ergibt sich für die oben beschriebene Situation der folgende
(unvollständige) Zeitablauf als Gantt-Diagramm (die Pfeile markieren, wann die einzelnen Prozesse im
System eintreffen):
Welche Scheduling-Verfahren können hier zum Einsatz gekommen sein (richtige Antwort(en) ankreuzen)?
FCFS (First Come First Served)
nicht-präemptives SJF (Shortest Job First)
präemptives SJF (Shortest Job First)
präemptives prioritätenbasiertes Scheduling (HPF)
RR (Round-Robin) mit einer Zeitscheibenlänge (Quantum) von 4.
b) Geben Sie den zeitlichen Ablauf für die Ausführung der oben beschriebenen Prozesse als GanttDiagramm an, wenn präemptives prioritätenbasiertes Multilevel-Scheduling mit zwei Prioritätsklassen
verwendet wird. Innerhalb der beiden Klassen wird jeweils Round Robin (RR) verwendet, wobei die
Zeitscheibenlänge (Quantum) unterschiedlich ist:
•
die Prioritätsklasse 0 hat die Zeitscheibenlänge 3,
•
die Prioritätsklasse 1 hat die Zeitscheibenlänge 4.
Geben Sie zusätzlich zu den markierten Zeiten den Inhalt der beiden RR-Prozeßwarteschlangen an.
Geben Sie für Prozess A die Wartezeit und die Durchlaufzeit an.

Download Report