5

KAPITE L

CPU
Terminplanung

Übungsaufgaben

5.1ADer CPU-Planungsalgorithmus bestimmt eine Reihenfolge für die Ausführung seiner

geplante Prozesse. Gegebene Prozesse, die auf einem Prozess geplant werden sollen.
Tut mir leid, wie viele verschiedene Zeitpläne sind möglich? Geben Sie eine Formel in Bezug auf
ofn.
Antwort:
n!(n-Fakultät = n× n– 1× n– 2× ... × 2× 1).
5.2 Erklären Sie den Unterschied zwischen präemptiver und nicht präemptiver Planung.
Ing.
Antwort:
Präemptives Scheduling ermöglicht es, einen Prozess mitten in
seine Ausführung, indem die CPU entzogen und einem anderen Prozess zugewiesen wird.
Die nicht präemptive Planung stellt sicher, dass ein Prozess die Kontrolle abgibt
der CPU nur, wenn sie mit ihrem aktuellen CPU-Burst fertig ist.
5.3 Angenommen, dass die folgenden Prozesse zu den Zeiten zur Ausführung ankommen
angegeben. Jeder Prozess wird für die angegebene Zeit laufen. In Antwort-
Bei den Fragen verwenden Sie nicht präemptive Planung und basieren alle Entscheidungen darauf.
auf der Grundlage der Informationen, die zum Zeitpunkt der Entscheidungsfindung vorliegen.

Prozess Ankunftszeit Burst-Zeit

P1 0.0 8
P2 0,4 4
P3 1.0 1

a. Wie lange dauert es durchschnittlich, diese Prozesse abzuschließen?

FCFS-Scheduling-Algorithmus?

b. Was ist die durchschnittliche Bearbeitungszeit für diese Prozesse mit dem
SJFscheduling-Algorithmus?
c. Der SJF-Algorithmus soll die Leistung verbessern, aber beachten Sie
dass wir uns entschieden haben, processP auszuführen1zu Zeitpunkt 0, weil wir es nicht wussten

115
116 Kapitel 5 CPU-Planung

dass zwei kürzere Prozesse bald eintreffen würden. Berechne, was das
Die durchschnittliche Bearbeitungszeit wird sein, wenn die CPU für die erste Zeit untätig bleibt.
1 Einheit und dann wird die SJFScheduling verwendet. Denken Sie daran, dass Prozesse
P1undP2warten während dieser Untätigkeit, so ist ihre Wartezeit
könnte zunehmen. Dieser Algorithmus könnte als Zukunftswissen bekannt sein.
Terminplanung.

Antwort:
a. 10.53
b. 9.53
c. 6,86
Denken Sie daran, dass die Bearbeitungszeit die Endzeit minus Ankunftszeit ist, also
Sie müssen die Ankunftszeiten subtrahieren, um die Wendepunkte zu berechnen.
FCFS ist 11, wenn Sie vergessen, die Ankunftszeit abzuziehen.

5.4 Betrachten Sie die folgende Menge von Prozessen, mit der Länge des CPU-Burst
Zeit in Millisekunden

Prozess Burst-Zeit Priorität

P1 2 2
P2 1 1
P3 8 4
P4 4 2
P5 5 3

Es wird angenommen, dass die Prozesse in der Reihenfolge P angekommen sind.1 ,P2 ,P3 ,P4 ,P5 ,
alles zur Zeit 0.
a. Zeichnen Sie vier Gantt-Diagramme, die die Ausführung dieser Pro-
Prozesse unter Verwendung der folgenden Scheduling-Algorithmen: FCFS, SJF, non-
präventive Priorität (eine größere Prioritätsnummer impliziert eine höhere
Priorität), und RR(Quantum = 2).
b. Wie lange dauert jeder Prozess jeweils für jede der
Scheduling-Algorithmen in Teil a?
c. Wie lange ist die Wartezeit jedes Prozesses für jede dieser Planungen?
Ing-Algorithmen?
d. Welcher der Algorithmen führt zu der minimalen durchschnittlichen Wartezeit?
Zeit (über alle Prozesse)?

Antwort:
a. Die vier Gantt-Diagramme:

P1 P2 2 P3 3 P4 4 P5 5
0 2 3 2 3 11 11 15 15 20
 Übungsaufgaben 117

P2 P1 P4 P5 P3
0 1 3 7 12 20

P3 P5 P1 P4 P2
0 8 13 15 19 20

P1 P2 P3 P4 P5 P3 P4 P5 P3 P5 P3
0 2 3 5 7 9 11 13 15 17 18 20

Durchlaufzeit:

FCFS SJF Priorität RR

P1 2 3 15 2
P2 3 1 20 3
P3 11 20 8 20
P4 15 7 19 13
P5 20 12 13 18
[Link] (Durchlaufzeit minus Burstzeit):

FCFS SJF Priorität RR

P1 0 1 13 0
P2 2 0 19 2
P3 3 12 0 12
P4 11 3 15 9
P5 15 7 8 13
d. SJF hat die kürzeste Wartezeit.

5.5 Die folgenden Prozesse werden mit einem präemptiven, runden Scheduling geplant.
Round-Robin-Scheduling-Algorithmus.

Prozess Priorität Platzen Ankunft

P1 40 20 0
P2 30 25 25
P3 30 25 30
P4 35 15 60
P5 5 10 100
P6 10 10 105

Jeder Prozess erhält eine numerische Priorität, wobei eine höhere Zahl anzeigt
eine höherwertige relative Priorität. Neben den oben aufgeführten Prozessen,
Das System hat auch eine Leerlaufaufgabe (die keine CPU-Ressourcen verbraucht und
118 Kapitel 5 CPU-Zuteilung

wird alsP identifiziertuntätig). Diese Aufgabe hat Priorität 0 und ist geplant, wenn-
immer das System keine anderen verfügbaren Prozesse zum Ausführen hat. Die Länge von einem
Die Zeitscheibe beträgt 10 Einheiten. Wenn ein Prozess von einem höherpriorisierten Prozess unterbrochen wird.
Im Prozess wird der unterbrochene Prozess ans Ende der Warteschlange gesetzt.

a. Zeigen Sie die Terminierungsreihenfolge der Prozesse mithilfe eines Gantt-Diagramms.

b. Wie lange dauert es für jeden Prozess?

c. Wie lange dauert es, bis jeder Prozess wartet?
d. Wie hoch ist die CPU-Auslastungsrate?

Antwort:
a. Das Gantt-Diagramm:

P1 untätig P2 P3 P2 P3 P4 P2 P3 ruhen P5 P6 P5

0 20 25 35 45 55 60 75 80 90 100 115

20-0 - 20
120-100 = 20, P6: 115-105 = 10
c. P1: 0, p2: 40, P3: 35, P4: 0, P5: 10, P6: 0
d. 105/120 = 87,5 Prozent.
5.6 Welchen Vorteil gibt es, unterschiedliche Zeitscheibenlängen zu haben?
verschiedene Ebenen eines mehrstufigen Warteschlangensystems?

Antwort:
Prozesse, die häufigere Wartung benötigen - beispielsweise interaktiv
Prozesse wie Editoren können sich in einer Warteschlange mit einem kleinen Zeitquantum befinden.
Prozesse, die keinen häufigen Service benötigen, können in einer Warteschlange sein mit
ein größeres Quantum, das weniger Kontextwechsel benötigt, um abzuschließen
Verarbeitung und damit eine effizientere Nutzung des Computers.
5.7 Viele CPU-Planungsalgorithmen sind parametrisiert. Zum Beispiel, das
Der RR-Algorithmus benötigt einen Parameter, um das Zeitintervall anzuzeigen. Multilevel
Feedback-Warteschlangen erfordern Parameter, um die Anzahl der Warteschlangen zu definieren.
die Planungsalgorithmen für jede Warteschlange, die Kriterien, die verwendet werden, um zu verschieben
Prozesse zwischen Warteschlangen und so weiter.
Diese Algorithmen sind also wirklich Mengen von Algorithmen (zum Beispiel die Menge
vonRRalgorithmen für alle Zeitabschnitte usw.). Ein Satz von Algorithmen kann
Include einen weiteren (zum Beispiel, der FCFS-Algorithmus ist der RR-Algorithmus
mit einem unendlichen Zeitquantum). Welche (wenn überhaupt) Beziehung besteht zwischen
die folgenden Paare von Algorithmus-Sets?

a. Priorität und SJF

b. Mehrstufige Rückmeldeschlangen und FCFS
c. Priorität und FCFS
[Link]
 Übungsaufgaben 119

Antwort
Der kürzeste Job hat die höchste Priorität.
b. Die niedrigste Stufe von MLFQ ist FCFS.

[Link] gewährt der Aufgabe, die am längsten besteht, die höchste Priorität.
der längste.
d. Keine.
5.8 Angenommen, ein CPU-Planungsalgorithmus bevorzugt jene Prozesse, die
haben in der letzten Zeit die wenigste Prozessorezeit verwendet. Warum wird dies
Algorithmus begünstigt I/O-gebundene Programme und sorgt dennoch dafür, dass sie nicht dauerhaft verhungern
CPU-gebundene Programme?
Antwort:
Es wird die I/O-gebundenen Programme begünstigen, aufgrund der relativ kurzen
CPU-Perioden, die von ihnen angefordert wurden; jedoch werden die CPU-gebundenen Programme

nicht verhungern, weil die I/O-gebundenen Programme die CPU freigeben werden
relativ häufig ihre Ein- und Ausgaben durchzuführen.

5.9Unterscheiden Sie zwischenPCSundSCSPlanung.

Antwort:
Die PCScheduling ist lokal zum Prozess. Es ist, wie die Thread-Bibliothek plant.
Threads auf verfügbare LWPs planen. SCS-Planung wird verwendet, wenn der Betrieb -
Das Betriebssystem plant Kernel-Threads. Auf Systemen, die entweder das nutzen ...
viele-zu-eins oder das viele-zu-viele Modell, die beiden Planungsmodelle
sind grundsätzlich unterschiedlich. In Systemen, die das Eins-zu-eins-Modell verwenden,
PCSandSCS sind gleich.

5.10 Der traditionelle UNIX-Scheduler erzwingt eine umgekehrte Beziehung zwischen

Prioritätszahlen und Prioritäten: Je höher die Zahl, desto niedriger die
Die Priorität. Der Scheduler berechnet die Prozessprioritäten einmal pro Sekunde neu.
unter Verwendung der folgenden Funktion:

Priorität = (aktuelleCPU-Nutzung / 2) + Basis

wo Basis = 60 aktuelleCPU-Auslastung bezieht sich auf einen Wert, der angibt, wie
Häufig hat ein Prozess die CPU genutzt, seit die Prioritäten zuletzt neu berechnet wurden.
Angenommen, dass die aktuelle CPU-Nutzung für Prozess P1ist 40, für processP2ist 18,
und für processP3Was werden die neuen Prioritäten für diese drei sein?
Prozesse, wenn Prioritäten neu berechnet werden? Basierend auf diesen Informationen,
Senkt oder erhöht der traditionelle UNIX-Scheduler die relative Priorität?
eines CPU-intensiven Prozesses?

Antwort:
Die den Prozessen zugewiesenen Prioritäten werden 80, 69 und 65 sein, respektiv.
Der Scheduler senkt die relative Priorität von CPU-gebundenen Prozessen.
Prozesse.