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.
