+1 Daumen
550 Aufrufe

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

von

1 Antwort

+4 Daumen
 
Beste Antwort

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:
sdjhfsdguzfgsaduzfgdsuzfg.png
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!

von

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:

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community