Betriebssysteme:Aufgaben Q

• Aufgaben
• Zurück zur Auswahl

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)

Ablaufplan

Prozessor 1		A	A	D	D	C	F	F
Prozessor 2		B	B	B	E	E	E	G

Größen

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.

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

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.

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