0 Daumen
499 Aufrufe

Gegeben ist ein System, dass ein prioritätsbasiertes Schedulingverfahren  verwendet und auf dem eine bestimmte anzahl an Prozessen läuft, die alle unterbrochen werden können. Diese Prozesse lasten das System zu 65% aus. Wie kommt man darauf, dass alle Prozesse rechtzeitig eingeplant werden? Wie geht man hier vor?

Avatar von

1 Antwort

+3 Daumen
 
Beste Antwort

Mit den vorliegenden Informationen ist diese Aufgabe nicht eindeutig lösbar. Sollte Rate Monotonic Scheduling, das prioritätsbasiert und statisch ist, gemeint sein, könntest Du über die hinreichende Scheduling-Bedingung argumentieren. Wenn $$\sum_{k=1}^{n}{\dfrac{C_k}{T_k}}\leq n\cdot \left(\sqrt[n]{2}-1\right)$$

erfüllt ist, dann sind die Jobs (Prozesse) garantiert einplanbar. Dabei ist \(C_k\) die Ausführungszeit von Prozess \(k\), \(T_k\) die Periodenlänge von Prozess \(k\) und \(\sum\limits_{k=1}^{n}{\dfrac{C_k}{T_k}}\) die Systemauslastung. Da die Anzahl der Prozesse nicht gegeben ist, gehen wir von dem Worst-Case \(n\longrightarrow \infty\) aus und berechnen:

$$\lim_{n\longrightarrow\infty}{n\cdot\left(\sqrt[n]{2}-1\right)}$$

$$=\lim_{n\longrightarrow\infty}{\dfrac{\sqrt[n]{2}-1}{\frac{1}{n}}}\text{ }\mid \text{l'Hospital}$$

$$=\lim_{n\longrightarrow\infty}{\dfrac{-\frac{\sqrt[n]{2}\cdot \ln(2)}{n^2}}{-\frac{1}{n^2}}}$$

$$=\lim_{n\longrightarrow\infty}{\sqrt[n]{2}\cdot \ln(2)}$$

$$=\ln(2)$$

Die Worst-Case-Untersuchung bezogen auf die Anzahl der Prozesse zeigt, dass diese bei einer Auslastung \(\leq ln(2)\) (\(\approx 69.315\%\)) sicher einplanbar sind. Da \(65\%\lt 69.315\%\) ist, können (sofern Rate Monotonic Scheduling verwendet wird) die Prozesse sicher eingeplant werden.

Beachte, dass es sich hierbei um eine hinreichende Bedingung handelt. Wenn die Auslastung größer als die Auslastungsschranke \(\ln(2)\) ist, könnte es dennoch einen Weg für die sichere Einplanbarkeit aller Prozesse geben.

Sollten \(n,C_k\) und \(T_k\) gegeben sein, solltest Du über einen Echtzeitnachweis nachdenken.

Avatar von

Ah dankeschön. Ja dieses verfahren war gemeint. Wie macht man einen echtzeitnachweis oder was meinst du damit?

Einen Echtzeitnachweis führst Du durch Prüfung der beiden Echtzeitbedingungen. Diese sind:

1. Auslastung

Die Gesamtauslastung eines Systems darf maximal \(100\%\) betragen, d.h. $$\sum\limits_{k=1}^{n}{\dfrac{C_k}{T_k}}\leq 1$$Dies liefert Dir auch gleichzeitig die Berechnungsmethodik.


2. Pünktlichkeit

Um Aufgaben rechtzeitig erledigen zu können, muss die Reaktionszeit zwischen der minimal und maximal zulässigen Reaktionszeit liegen. Dies kannst Du mathematisch (sehr aufwendig) oder graphisch für die einzelnen Jobs nachweisen.
Stelle am besten eine Aufgabe dazu, wenn Du eine hast.

Kannst Du mir auch hier helfen? https://www.mathelounge.de/497282/echtzeitnachweis-wie-berechnen Das wäre sehr lieb!

Hier noch einmal die ausführliche Variante: https://www.informatik.academy/einplanbarkeit-beim-rate-monotonic/

Diese Frage passt super in unser Informatikforum!

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community