Prozessor Scheduling Algorithmen

In diesem Beitrag geht es um die verschiedenen Scheduling Algorithmen der Prozessor Rechenzeit. Anknüpfend an meinen Beitrag „Prozesse und Threads“ (http://marvins-blog.de/blog/2014/12/18/prozesse-und-threads-betriebssysteme/)


Wir betrachten folgende 4 Prozesse in allen gängigen Scheduling Algorithmen.

Prozess Ankunftszeitpunkt Bedienzeit
P1 0 1000
P2 100 500
P3 400 200
P4 500 100

 

First-Come First-Served (FCFS)

Zeitpunkt Laufender Prozess Bereite Prozesse
0 P1
1000 P2 P3, P4
1500 P3 P4
1700 P4 /

Laufzeit: P1 = 1000, P2 = 1400, P3 = 1300, P4 = 1300, Durchschnitt: 1250

Shortest Job First (SJF)

Ohne Abbruch. (Nicht präemptiv)

Zeitpunkt Laufender Prozess Bereite Prozesse
0 P1
1000 P4 P2, P3, P4
1100 P3 P2, P3
1300-1800 P2

Laufzeit: P1 = 1000, P2 = 1700, P3 = 900, P4 = 600, Durchschnitt: 1050

Shortest Remaining Time Next (SRTN)

Zeitpunkt Laufender Prozess Bereite Prozesse
0 P1(1000)
100 P2(500) P1(900)
400 P2(200) P1(900), P3(200)
500 P2(100) P1(900), P3(200), P4(100)
600 P4(100) P1(900), P3(200)
700 P3(200) P1(900)
900-1800 P1(900)

Laufzeit: P1 = 1800, P2 = 500, P3 = 500, P4 = 200, Durchschnitt: 750

Round-Robin (RR) mit einer Zeitscheibengröße von 100

Zeitpunkt Laufender Prozess
0 P1
100 P2
200 P1
300 P2
400 P1
500 P3
600 P2
700 P4
800 P1
900 P3
1000 P2
1100 P1
1200 P2
1300 P1

Laufzeit: P1 = 1800, P2 = 1200, P3 = 500, P4 = 100, Durchschnitt: 900

Zu beachten ist, das der Prozess schon da ist, wenn der andere schon läuft, heißt, wenn ein neuer Prozess hinzu kommt, wird dieser der Schlange angehangen. Der Prozess der davor beendet bzw pausiert wurde, wird ganz hinten angehangen, der neue Prozess kommt vor den beendeten. Also => Neue Prozesse hängen sich zuerst an, beendete Prozesse kommen danach.

 

Rate Monotonic Scheduling (RMS)

Hierfür verwenden wir folgendes Beispiel:

Prozess Bedienzeit Periode
P1 10 100
P2 100 200
P3 20 300

Bedienzeit zwischen den Perioden berechnen (Bedienzeit / Peiode):
10/100 + 100/200 + 20/300 = 2/3% ~ 66%

Damit sind die Voraussetzungen gegeben, da der Wert unter den 69,3% liegt.

Scheduling Plan nach RMS

Zeitpunkt Laufender Prozess Bereite Prozesse
0 P1 P2(100), P3(20)
10 P2 P3(20)
100 P1(10) P3(20), P2(10)
110 P2 P3(20)
120 P3
200 P1 P2(100)
210 P2

In den übrigen Rechenzeiten (Hier bei 600 Einheiten, 200) kann man andere Prozesse mit z.B. RR Rechnen lassen, die nichts mit Echtzeit zu tun haben.

Marvin Sengera

Hey! Ich bin Marvin Sengera, Inhaber der Internetagentur "Binärfabrik" aus Paderborn. Ich habe mein Bachelorstudium Informatik mit Schwerpunkt Industriespionage an der Hochschule Hamm Lippstadt abgeschlossen und absolviere derzeit meinen Master in Fachrichtung "Technical Entrepreneurship and Innovation". Ich beschäftige mich rund um die Themen Informatik, Innovation & Unternehmensgründung.

Das könnte dich auch interessieren …

Schreibe einen Kommentar