Betriebssysteme:Aufgaben Q
Inhaltsverzeichnis
Q1
a)
M - Ankunftsprozess - M für POISSON-Prozess (exponentialverteilte Zeit)
M - Bedienprozess - M für POISSON-Prozess (exponentialverteilte Zeit)
1 - Anzahl der Bedienungskanäle
∞ - Warteraumkapazität (unbeschränkt)
b)
gegeben: $ \overline{T_a} = 250 ms $, $ \mu = 5 Hz $
gesucht: $ \overline{T_v} $, $ \overline{N_w} $
Lösung:
$ \rho = \frac{\lambda}{\mu} = \frac{1}{\mu * \overline{T_a}} = 0,8 $
$ \overline{T_v} = \overline{T_w} + \overline{T_b} = \frac{\rho}{\mu * (1-\rho)} + \overline{T_b} = (\frac{\rho}{1-\rho} + 1)*\frac{1}{\mu} = \frac{1}{1 - \rho}*\frac{1}{\mu} = 1s $
$ \overline{N_w} = \frac{\rho^2}{1-\rho} = 3,2 $
Q2
a)
siehe Lösungen der Klausurvorbereitung
b)
| Prozessor 1 | A | A | D | D | C | F | F | |
| Prozessor 2 | B | B | B | E | E | E | G |
| Job J | A | B | C | D | E | F | G | |
| Wartezeit $ t_w(J) $ | 0 | 0 | 4 | 2 | 3 | 5 | 6 |
$ \overline{t_v} = \overline{t_w} + \overline{t_b} = \frac{4 + 2 + 3 + 5 + 6}{7}s + \frac{14}{7}s = \frac{34}{7}s $
Durchsatz $ D=\frac{|J|}{t_g}=\frac{7 Jobs}{7 s}=1\frac{Job}{s} $ mit J = {A,B,C,D,E,F,G}
Q3
M/?/n>1/∞
tᵥ = 5s
tₐ = 2s
Q4
a.)
Edit 2: Ich habe noch eine andere Lösung, da ich denke, das nach der obrigen Lösung die Prioritäten falsch gesetzt sind. Sind nicht nach der Definition die mit der höchsten Priorität am nächsten an der X-Achse in der Warteschlange? Und das ist bei CBD nicht gegeben, da D eine höhere Priorität als B hat!
B
BB BBDBBBB
BCCBBBDDEDDFFB
AAAAACCCCCCEEDDFBB
--> da hast du recht
keine Ahnung, wie ihr auf dieses Ergebnis kommen konntet, aber was unten steht wird bearbeitet, darum sollte wohl eher das hier stimmen:
B BB
BBBBBABAABB
BAAAAADADDAABB
AAACCCCCCDEEDFAABB
// ist FALSCH, da prozesse nicht unterbrochen werden können ||edit: Koennen sehr wohl unterbrochen werden!!!! [und loesung stimmt]! //IN DER AUFGABE STEHT PROZESSE SIND nICHT UNTERBRECHBAR. ist also 100% FALSCH
//immer müsst ihr euch Streiten tz tz tz, was haltet ihr hiervon?
p 5 EE 4 3 CCCCCC 2 DDF 1 AAAAA BB
b.)
$ \overline{T_w} = \frac{0+14+2+5+1+2}{6} = \frac{24}{6} = 4 $
$ \overline{T_b} = \frac{5+2+6+2+2+1}{6} = \frac{18}{6} = 3 $
$ \overline{T_v} = \overline{T_w}+\overline{T_b} $
$ \overline{T_v} = 7 $
max.Warteschlangenlänge = 3
durchschnittliche Warteschlangenlänge = $ \frac{26}{21} $
//is doch falsch oder? also ich komm da auf $ \frac{3*1+2*8+1*5+0*7}{21} = \frac{24}{21}= \frac{8}{7} $
//bin auch dafür, dass $ \frac{8}{7} $ rauskommen
d.)
Unterschiedliche Ergebnisse, weil bei den gegebenen Werten die Exopnentialverteilung bei Ankunfts- und Bedienprozess nicht gegeben ist.
Q5
Q6
Shortest Processing Time
- anwendbar wenn R leer ist
- prozesse mit kürzester laufzeit zuerst abarbeiten
- optimal bzgl mittlerer wartezeit $ \overline{t}_w $
// sicherlich nicht allzu wichtig, aber in den Folien steht insbesondere
// optimal bzgl. $ \overline{t}_v $ (mittlere Verweildauer)
//- beide Größen stehen ja auch in engem Zusammenhang.
Edit: SPT ist auch anwendbar, wenn $ R \neq \varnothing $.
-->ja schon... aber meist wird die ordnung dann eh durch R vorgegeben
Q7
a) siehe Q6 (o_O an den Autor)
b) weil SPT kein RTS-verfahren ist. EDF wäre möglich.
Beispiel dazu: ein prozess, der alle 3 ZE auftritt, 2ZE laufzeit, deadline=start+2ZE.
andrer prozess tritt gleichzeitig auf, 1ZE laufzeit, deadline=start+3ZE
Q8
Q9
Q10
Q11
a)
$ \lambda = 75Hz $
$ T_b = 20ms \Rightarrow \mu = \frac{1}{0,02s} = 50Hz $
Kritisch, weil mehr Forderungen eintreffen als bedient werden können.
b)
Wirkungsvoller ist die Erhöhung der Anzahl der Bedienkanäle.
Q12
Q13
a) Die Zuordnung ist nicht optimal in der Klasse der statischen Echtzeitschedulingverfahren, weil es ein anderes Verfahren(z.B RMS(optimal)) gibt, welches ein nicht einplanbares Szenario des einen Verfahrens doch einplanen kann.
b) 3 Jobs, verdrängbar, Echtzeitsystem, p(i)...Periodendauer, t(i)...maximale Bearbeitungszeit
Job1: p(1) = 5s, t(1) = 4s Job2: p(2) = 30s, t(2) = 1s Job3: p(3) = 60s, t(3) = 1s
RMS: Job1 - Job2 -|- Job1 - Job3 -|- Job1 ...
Text: Job2 - Job3 - Job|1 ....> Deadline job1 überschritten
// Für Beweis reichen 2 Jobs aus: T1(3,4) und T2(2,9)
Q14
a) Gesamtauslastung muß größer sein als
$ n* (\sqrt[n]{2} - 1) $, denn es gilt
wenn $ \sum_{i=1}^n \frac {t_i}{p_i} $ kleiner oder gleich diesem Wert ist, ist die Taskmenge mit RMS einplanbar.
(Bedingung hinreichend, nicht notwendig!)
^^ ist schon ganz in ordnung, jedoch gibt es einen wert bei rms, gegen den der wurzelausdruck konvergiert für sehr große n. Demnach könnte man sagen, dass unter bestimmten (sehr großen n) die Gesamtauslastung mindestens 0.68 sein muss (da man sonst ein n finden könnte, für das RMS möglich wäre)
b) sinnlos, da RMS optimal bzgl. statischen Prioritäten ist
Q15
a) Kleinste Auslastung Zuerst, kurz der KZ-Algorithmus ;-)
b) nein, denn RMS ist optimal bzgl. statischen Prioritäten, dies bedeutet insbesondere, daß es keinen Algorithmus mit statischen Prioritäten gibt, der mehr zu leisten im Stande ist als RMS. Da der gegebene Algorithmus feste Prioritäten hat, kann es keine Taskmengen geben, die mit RMS nicht, mit diesem Algorithmus aber schon einplanbar sind.
c) k.A., hat da jemand ne Idee?
Kleiner Tip für den Ansatz: Betrachte zuerst mal ein System, wo alle Tasks gleich lange Perioden haben. Dann eines, wo ein Task eine sehr lange Periode, aber eine geringe Ausführungszeit hat, ein zweiter eine kurze Periode mit verhältnismäßig langer Ausführungszeit. HTH ;-)
Q16
a) M/M/k/0
Der Bezeichner M ist für einen Poisson-Prozess bzw. exponentialverteilt. Prozess zu verwenden, was hier der Fall ist. Die Anzahl k der Kanäle ist noch zu definieren, die Warteschlange ist nicht vorhanden, da ein sog. "Vormerken" nicht mgl. sein soll
b) ETa = 60/(150/s) = 400ms
c) p = (1/(0,4s))/(1/(3s)) = 7,5
Schlussfolgerung: Da keine Warteschlange vorhanden ist, sollte man 8 Kanäle implementieren, um den Anforderungen gerecht zu werden
Q17
a) SPT: $ \overline{t_w} = \frac{1}{5}*(0+0+3+5+9) = \frac{17}{5} $
LPT: $ \overline{t_w} = \frac{1}{5}*(0+0+7+9+13) = \frac{29}{5} $
b) Alle Jobs sind voneinander unabhängig. Somit ist SPT optimal bezüglich der mittleren Warte- und Verweilzeit, wie auch gut aus Beispiel a) ersichtlich ist. LPT hat hingegen eine bessere Prozessorauslastung und bedingt dadurch auch eine kleinere Gesamtzeit (16ZE statt 18ZE bei SPT)
a) SPT: $ \overline{t_w} = \frac{17}{5} $
stimme ich zu, brauch ich wohl mal neue Kontaktlinsen gg
LPT: $ \overline{t_w} = \frac{28}{5} $ wie kommst du auf 28?
nicht korrekter?
LPT sieht bei mir so aus:
PR1: C(9)-B(5)
PR2: A(7)-D(6)-E(3)
mal überlegen...
A(7), B(5), C(9), D(6), E(3)
LPT sieht bei mir so aus
PR_1: CD
PR_2: ABE
darausfolgt:
0+9+0+7+12=28
Is aber leider falsch denn LPT sucht sich immer den Job mit der längsten Bearbeitungszeit aus also: C für PR1 un A für PR2
A ist jetzt nach 7 ZE fertig un der Scheduler sucht sich den nächstlängsten das wäre dann D! und nicht B! wenn C fertig ist, ist D noch am rechnen... der Scheduler sucht sich also wieder den nächsten das wäre dann B usw
danke, hab nicht richtig geschaut
Q18
a)
T1: t1 = 5; p1 = 7 T2: t2 = 6; p2 = 24 => Priorität: T1 vor T2
Task mit der längsten Periode ist T2, sei also T2': t2'= 1; p2'= 4
da die Prioritäten nicht verändert werden sollen, läuft nun zuerst T1 5ZE lang, da aber bereits zum Zeitpunkt 4 die erste Deadline für T2' verstrichen ist, kann die Taskmenge {T1, T2'} nicht mit RMS einplanbar sein.
Somit ist die Behauptung falsch.
b)
Wenn p1=15 sein soll, so müsste t1 bei rund 10s liegen (damit die Auslastung gleich bleibt). Im Intervall [0,24] gäbe es dann aber nur rund 5 freie Zeiteinheiten. T2 benötigt jedoch 6s zur Ausführung. Der Ablaufplan müsste also für eine längere Zeit aufgestellt werden, was unpraktisch ist.
--Mein Beileid, totaler Schwachsinn.--
a) Die kleinste Periode die nicht die Prioritätszuordnung ändert sind 8, das ist ein Drittel von 24, deswegen t2 = 2, dann klappts auch mit dem Nachbarn, also die Sache geht auf
b) Jetzt muss man auch bei b) kein Käse antworten, sondern sieht das p1 größer als die hälfte von p2 ist, also kann man Prozess 2 nicht in kleinere Teile teilen.
84.179.152.25 20:42, 22. Feb 2007 (CET)
Ich stimme meinem Vorposter zu. Hätte er aber bei a) mit 2 gekürzt, also T'_2=(3;12) probiert, hätte er gesehen, dass es nicht mit RMS einplanbar ist. Daher Widerlegung durch Gegenbeispiel.
Q19
a)
Maximum, das mit EDF einplanbar ist:
$ \sum_{i=1}^3 \frac{t_i}{p_i} = 1 $
$ \frac{18+3x}{24} = 1 => x = 2 $
c)
$ \sum_{i=1}^n \frac{t_i}{p_i} \leq n*(\sqrt[n]{2} - 1) $
ist eine hinreichende, aber nicht notwendige Bedingung, damit RMS einplanbar ist. Diese Bedingung ist hier nicht erfüllt. Somit läßt sich auf Anhieb nicht sagen, ob die Menge mit RMS einplanbar ist. Prioritäten wären: T2 vor T1 vor T3
Probiert man es aus, sieht man, daß Task 3 seine Deadline verpaßt, ist somit nicht mit RMS einplanbar
