Planungsalgorithmen für Betriebssysteme

Ein Prozessplaner plant verschiedene Prozesse, die der CPU basierend auf bestimmten Planungsalgorithmen zugewiesen werden sollen. Es gibt sechs gängige Prozessplanungsalgorithmen, die wir in diesem Kapitel behandeln werden -

FCFS-Planung (First-Come, First-Served)
SJN-Planung (Shortest-Job-Next)
Prioritätsplanung
Kürzeste verbleibende Zeit
Round Robin (RR) -Planung
Planung von Warteschlangen auf mehreren Ebenen

Diese Algorithmen sind entweder non-preemptive or preemptive. Nicht präemptive Algorithmen sind so konzipiert, dass ein Prozess, sobald er in den laufenden Zustand übergeht, erst nach Ablauf seiner zugewiesenen Zeit vorbelegt werden kann, während die präemptive Planung auf der Priorität basiert, bei der ein Scheduler einen laufenden Prozess mit niedriger Priorität jederzeit mit hoher Priorität verhindern kann Prozess tritt in einen Bereitschaftszustand ein.

Wer zuerst kommt, mahlt zuerst (FCFS)

Jobs werden nach dem Prinzip "Wer zuerst kommt, mahlt zuerst" ausgeführt.
Es ist ein nicht präventiver, präventiver Planungsalgorithmus.
Einfach zu verstehen und umzusetzen.
Die Implementierung basiert auf der FIFO-Warteschlange.
Schlechte Leistung, da die durchschnittliche Wartezeit hoch ist.

Wait time von jedem Prozess ist wie folgt -

Prozess	Wartezeit: Servicezeit - Ankunftszeit
P0	0 - 0 = 0
P1	5 - 1 = 4
P2	8 - 2 = 6
P3	16 - 3 = 13

Durchschnittliche Wartezeit: (0 + 4 + 6 + 13) / 4 = 5,75

Kürzester Job als nächstes (SJN)

Dies ist auch bekannt als shortest job firstoder SJF
Dies ist ein nicht präemptiver, präventiver Planungsalgorithmus.
Bester Ansatz zur Minimierung der Wartezeit.
Einfache Implementierung in Batch-Systemen, bei denen die erforderliche CPU-Zeit im Voraus bekannt ist.
In interaktiven Systemen, in denen die erforderliche CPU-Zeit nicht bekannt ist, ist keine Implementierung möglich.
Der Verarbeiter sollte im Voraus wissen, wie viel Zeit der Vorgang in Anspruch nehmen wird.

Gegeben: Tabelle der Prozesse und deren Ankunftszeit, Ausführungszeit

Prozess	Ankunftszeit	Ausführungszeit	Servicezeit
P0	0	5	0
P1	1	3	5
P2	2	8	14
P3	3	6	8

Waiting time von jedem Prozess ist wie folgt -

Prozess	Wartezeit
P0	0 - 0 = 0
P1	5 - 1 = 4
P2	14 - 2 = 12
P3	8 - 3 = 5

Durchschnittliche Wartezeit: (0 + 4 + 12 + 5) / 4 = 21/4 = 5,25

Prioritätsbasierte Planung

Die Prioritätsplanung ist ein nicht präemptiver Algorithmus und einer der häufigsten Planungsalgorithmen in Batch-Systemen.
Jedem Prozess wird eine Priorität zugewiesen. Der Prozess mit der höchsten Priorität muss zuerst ausgeführt werden und so weiter.
Prozesse mit derselben Priorität werden nach dem Prinzip "Wer zuerst kommt, mahlt zuerst" ausgeführt.
Die Priorität kann basierend auf Speicheranforderungen, Zeitanforderungen oder anderen Ressourcenanforderungen festgelegt werden.

Gegeben: Tabelle der Prozesse und deren Ankunftszeit, Ausführungszeit und Priorität. Hier betrachten wir 1 als die niedrigste Priorität.

Prozess	Ankunftszeit	Ausführungszeit	Priorität	Servicezeit
P0	0	5	1	0
P1	1	3	2	11
P2	2	8	1	14
P3	3	6	3	5

Waiting time von jedem Prozess ist wie folgt -

Prozess	Wartezeit
P0	0 - 0 = 0
P1	11-1 = 10
P2	14 - 2 = 12
P3	5 - 3 = 2

Durchschnittliche Wartezeit: (0 + 10 + 12 + 2) / 4 = 24/4 = 6

Kürzeste verbleibende Zeit

Die kürzeste verbleibende Zeit (SRT) ist die präemptive Version des SJN-Algorithmus.
Der Prozessor wird dem Auftrag zugewiesen, der der Fertigstellung am nächsten kommt. Er kann jedoch durch einen neueren Bereitschaftsjob mit kürzerer Zeit bis zur Fertigstellung verhindert werden.
In interaktiven Systemen, in denen die erforderliche CPU-Zeit nicht bekannt ist, ist keine Implementierung möglich.
Es wird häufig in Batch-Umgebungen verwendet, in denen kurze Jobs bevorzugt werden müssen.

Round Robin Scheduling

Round Robin ist der präventive Prozessplanungsalgorithmus.
Jedem Prozess wird eine feste Ausführungszeit zur Verfügung gestellt, die als a bezeichnet wird quantum.
Sobald ein Prozess für einen bestimmten Zeitraum ausgeführt wurde, wird er vorab ausgeführt und ein anderer Prozess wird für einen bestimmten Zeitraum ausgeführt.
Die Kontextumschaltung wird verwendet, um Zustände von vorab freigegebenen Prozessen zu speichern.

Wait time von jedem Prozess ist wie folgt -

Prozess	Wartezeit: Servicezeit - Ankunftszeit
P0	(0 - 0) + (12 - 3) = 9
P1	(3 - 1) = 2
P2	(6 - 2) + (14 - 9) + (20 - 17) = 12
P3	(9 - 3) + (17 - 12) = 11

Durchschnittliche Wartezeit: (9 + 2 + 12 + 11) / 4 = 8,5

Planung von Warteschlangen auf mehreren Ebenen

Warteschlangen mit mehreren Ebenen sind kein unabhängiger Planungsalgorithmus. Sie verwenden andere vorhandene Algorithmen, um Jobs mit gemeinsamen Merkmalen zu gruppieren und zu planen.

Für Prozesse mit gemeinsamen Merkmalen werden mehrere Warteschlangen verwaltet.
Jede Warteschlange kann ihre eigenen Planungsalgorithmen haben.
Jeder Warteschlange werden Prioritäten zugewiesen.

Beispielsweise können CPU-gebundene Jobs in einer Warteschlange und alle E / A-gebundenen Jobs in einer anderen Warteschlange geplant werden. Der Prozessplaner wählt dann abwechselnd Jobs aus jeder Warteschlange aus und weist sie der CPU basierend auf dem der Warteschlange zugewiesenen Algorithmus zu.