Crasht das System mit den folgenden Prozessen?

Question

Ich habe wieder ein system mit unterschiedlichen prozessen

1 Verarbeitungszeit 2ms, Zykluszeit 5ms

2 Verarbeitungszeit 3ms, Zykluszeit 6ms

3 Verarbeitungszeit 1ms, Zykluszeit 10ms

diese starten bei unterschiedlichen Zeiten, nämlich 1 bei 0ms (Startpunkt) , 2 bei 3ms und 3 bei 5ms.

Wie kann ich nachweisen, dass das system nicht crasht, wenn Rate monotonic genutzt wird?

Danke

Answer 1

Rate Monotonic Scheduling ist ein prioritätsbasiertes Scheduling-Verfahren mit statischen Prioritäten. Die Prozesse, die auf diese Weise der CPU zugeteilt werden, müssen unterbrechbar sein. Die Priorität definiert sich über den reziproken Wert der Zykluszeiten. D.h. also, je länger die Zykluszeit, desto geringer ist Priorität des dazugehörigen Tasks. Die Prioritätenverteilung sieht also wie folgt aus:

\(p(P_3)=\frac{1}{10} < p(P_2)=\frac{1}{6} < p(P_1)=\frac{1}{5}\)

Du kannst graphisch nachweisen, ob dieses Scheduling-Verfahren auf dem System mit den beschriebenen Prozessen zu einem Fehler führt. Horizontal sind die Zeitslots eingezeichnet. Darüber liegen die einzelnen Prozesse. Je weiter „unten“ sich ein Prozess befindet, desto höher ist seine Priorität. Wenn in mindestens einer Spalte mehr als eine „Farbe“ auftaucht, dann ist konfliktfreies Scheduling mit diesem Verfahren nicht möglich:

Wie man sieht, ist die Zuteilung von \(P_3\) für einen Zeitslot in seinem zweiten Zyklus nicht möglich. Das System crasht! Über die hinreichende Scheduling-Bedingung kannst Du hier nicht argumentieren!

Comments

Insgesamt liefert Dir diese Ansicht die Rechnerkernbelegung für ein Single-Core-System.

---

Danke was passiert wenn die prozesse alle die gleiche prio haben? Geht das?

---

Befinden sich mindestens zwei Prozesse auf einer Prioritätsebene, nutzt man üblicherweise Round Robin. Hierfür wäre dann die Wahl eines Quantums vonnöten.

---

Lieben dank:))

---

doch mal eine frage. Woher weiß ich wie weit ich die Zeiteinheiten zeichnen muss (also bis wohin)?

---

Woher weiß ich wie weit ich die Zeiteinheiten zeichnen muss

So lange, bis erstmalig ein Konflikt auftritt. Andernfalls (wenn z.B. eine konfliktfreie Einordnung der Prozesse möglich ist) bis sich der Ablauf aller Prozesse auf dem System wiederholt. Diesen Wert berechnest Du durch das kleinste gemeinsame Vielfache der Zykluszeiten (kgV bzw. lcm (least common multiple)). Auf diesen Wert addierst Du den spätesten Startpunkt unter den Prozessen. Für \(P_1, P_2, ..., P_n\) ist demnach von \(0\) bis

$$\mathrm{lcm}(t_c(P_1), t_c(P_2), ..., t_c(P_n))+\max(t_s(P_1), t_s(P_2), ..., t_s(P_n))$$

zu zeichnen. Dabei ist \(t_c(P_i)\) die Zykluszeit von Prozess \(i\) und \(t_s(P_i)\) der Startzeitpunkt von Prozess \(i\).

---

Vielleicht noch ein Tipp: Es schadet nie, vorher die Systemauslastung zu berechnen (das geht ja sehr einfach und schnell). Ggf. sparst Du Dir den Aufwand zum Zeichnen, wenn die hinreichende Scheduling-Bedingung (https://www.informatik.academy/einplanbarkeit-beim-rate-monotonic/#hinreichende-scheduling-bedingung) erfüllt ist. Hier geht es aber (wie bereits oben erwähnt) nicht, da die Auslastung \(>\frac{100}{e}\%\)

---

Ich habe gerade ein kleines Programm geschrieben, mit dem Du alle Aufgaben dieses Typs lösen können solltest. Spezifiziere einfach in der Main Deine Prozesse, erzeuge ein Scheduler-Objekt, übergib die Prozesse dem Scheduler im Ctor und starte die Methode "is_schedulable()".

https://github.com/informatik-academy/Mathelounge/tree/master/Scheduling

Als Output für Dein Beispiel erhält man:

Die hinreichende Scheduling-Bedingung kann nicht als Argument verwendet werden, da die Auslastung 1,000000 beträgt, was nicht <= 0,779763 ist!
Prozess <P3> kann in Zyklus <2> nicht eingeplant werden!
0 - P1
1 - P1
2 - null
3 - P2
4 - P2
5 - P1
6 - P1
7 - P2
8 - P3
9 - P2
10 - P1
11 - P1
12 - P2
13 - P2
14 - null
15 - P1
16 - P1
17 - P2
18 - P2
19 - P2
20 - P1
21 - P1
22 - P2
23 - P2
24 - P2
25 - P1
26 - P1
27 - P2
28 - P2
29 - P2
30 - P1
31 - P1
32 - null
33 - P2
34 - P2

null heißt in diesem Fall, dass innerhalb dieser Zeiteinheit kein Prozess die CPU belegt. Vergleiche die Ergebnisse mit meiner Grafik.

---

Ich bin sprachlos. Aber wie kann ich das programm installieren?

---

Eine klassische „Installation“ ist in diesem Fall nicht nötig.

1. Lade Dir das unter dem Link erreichbare Projekt auf Deinen Rechner.

2. Lade Dir (falls nicht bereits vorhanden) die nötigen Ressourcen zur Verwendung von Java herunter. Eine Anleitung findest Du hier:

https://www.youtube.com/watch?v=r59xYe3Vyks

3. Öffne das Projekt in einer IDE (oder kompiliere es über die Konsole). 

4. Passe die Main-Methode Deiner Aufgabenstellung an.

5. Starte das Programm.

6. Freue Dich über die Lösung :-)

Übrigens: Ich habe das Programm performancetechnisch noch ein klein wenig optimiert. Für den Fall \(\mu>1\) (eine über \(100\%\) liegende Auslastung) führt direkt zu der Rückgabe von false in is_schedulable. Somit spart man sich die Simulation.