0 Daumen
148 Aufrufe

Gegeben sind 4 Prozesse, die nach 0, 1, 2 und 3 Sekunden auf dem System "ankommen". Prozess 1 braucht 10ms Rechenzeit, Prozess 2 braucht 4ms Rechenzeit, Prozess 3 braucht 5ms Rechenzeit und Prozess 4 braucht 3ms Rechenzeit. Das Quantum ist 3ms.

a) Wie teilt der mit Round Robin arbeitende Scheduler die Prozesse der einen CPU zu?

b) Wie groß muss das Quantum sein, damit die Vorgehensweise dem FIFO-Algorithmus gleicht? Je frĂŒher die Prozesse auf dem System ankommen, desto höher ist ihre PrioritĂ€t.

Kann mit jemand helfen? Bitte?

von

Hast du mal unter https://de.wikipedia.org/wiki/Round_Robin_(Informatik) geschaut.

Was ich nicht verstehe:

Prozess 1 kommt ja sofort am System an. Prozess 2 ja aber erst nach einer Sekunde. Dann ist Prozess 1 mit 10 ms doch schon lange abgearbeitet.

Da spielt das Quantum doch ĂŒberhaupt keine Rolle.

Ist die Aufgabe so richtig abgeschrieben?

Dieser Meinung bin ich auch. Ist das eine Fangfrage? So, wie die Aufgabe gestellt ist, wĂŒrde die Queue niemals mehr als einen Prozess enthalten und das Verhalten wĂ€re automatisch wie bei FIFO. Ist das eine Klausuraufgabe? Falls ja: schau mal auf die Anzahl der Punkte, die es dafĂŒr gibt :-)

Da steht 0, 1, 2 und 3 milisekunden. Da habe ich mich verschrieben tut mir leid.

2 Antworten

+2 Daumen
 
Beste Antwort

a) Beim Scheduling via Round Robin werden alle Prozesse zunĂ€chst in eine Queue eingereiht und jedem Prozess ein Quantum zugeteilt (hier allen Prozessen \(3\)ms). GemĂ€ĂŸ der Reihenfolge in der Queue wird den Prozessen die CPU zugewiesen. Wenn ein Prozess nach Ablauf seines Quantums noch im Zustand "running" ist, wird ihm die CPU entzogen und er wechselt seinen State zu "ready". Anschließend wird er ans Ende der Queue verlegt und der erste Prozess in der Warteschlange erhĂ€lt die CPU. Die Wahl des Quantums sollte sinnvoll sein. Das ist genau dann der Fall, wenn das VerhĂ€ltnis zwischen Quantum und der Zeit, die das System fĂŒr einen Context Switch benötigt, vernĂŒnftig ist. Wird das Quantum zu groß gewĂ€hlt, so ist das zwar ein effizienter Ansatz, allerdings muss man ggf. mit langen Verzögerungs- und Wartezeiten rechnen (darauf zielt glaube ich auch die b) ab). Bei einem zu kleinen Quantum hat man wiederum sehr kurze Antwortzeiten, doch aufgrund der hĂ€ufigen Prozessumschaltungen einen großen Overhead. Ich denke, dass \(3\)ms in Ordnung sind. So weit zur Theorie um den Algorithmus. BeschĂ€ftigen wir uns nun mit dem Beispiel. 

Am Anfang enthÀlt die Queue \(P_1\), der eine Rechenzeit von \(10\)ms benötigt. Diesem wird direkt die CPU zugeteilt.
Nach einer Millisekunde kommt \(P_2\) in die Queue. Zu diesem Zeitpunkt hat \(P_1\) bereits eine Millisekunde gerechnet.  Danach kommt \(P_3\) in die Queue und wird hinter \(P_2\) eingereiht. Zu diesem Zeitpunkt hat \(P_1\) bereits \(2\)ms gerechnet. Nun kommt auch der letzte Prozess \(P_4\) hinzu, der hinter \(P_3\) in der Queue positioniert wird:

\(\begin{array}{|c|c|} \hline \text{Prozess} & \text{Rechenzeit [ms]} & \text{verbleibende Rechenzeit [ms]}\\\hline P_1 & 10 & 7\\\hline P_2 & 4 & 4\\\hline P_3 & 5 & 5\\\hline P_4 & 3 & 3\\\hline\end{array}\) 

Da \(P_1\) sein Quantum aufgebraucht hat und noch nicht fertig ist, wird er hinter \(P_4\) eingereiht und \(P_2\) erhĂ€lt die CPU. \(P_2\) rechnet \(3\)ms und wird vom Scheduler anschließend hinter \(P_1\) eingeordnet, da auch \(P_2\) nach Aufbrauchen des Quantums noch nicht fertig ist. Nun wird \(P_3\) die CPU zugeteilt, \(3\)ms gerechnet und \(P_3\) danach hinter \(P_2\) eingereiht. Jetzt erhĂ€lt \(P_2\) die CPU und wird komplett abgearbeitet. \(P_2\) wird also nicht mehr in die Queue geschickt:

prozessssssss.png

\(\begin{array}{|c|c|} \hline \text{Prozess} & \text{Rechenzeit [ms]} & \text{verbleibende Rechenzeit [ms]}\\\hline P_1 & 10 & 7\\\hline P_2 & 4 & 1\\\hline P_3 & 5 & 2\\\hline P_4 & 3 & 0\\\hline\end{array}\)

Jetzt startet \(P_1\) und arbeitet wieder \(3\)ms. Nach der Abarbeitung wird \(P_1\) hinter \(P_3\) positioniert. Den Prozessen \(P_2\) und \(P_3\) wird nun nacheinander die CPU zugeteilt. Beide werden komplett fertig (und benötigen dafĂŒr nicht einmal ihr gesamtes Quantum).

prozessssssss.png

\(\begin{array}{|c|c|} \hline \text{Prozess} & \text{Rechenzeit [ms]} & \text{verbleibende Rechenzeit [ms]}\\\hline P_1 & 10 & 4\\\hline P_2 & 4 & 0\\\hline P_3 & 5 & 0\\\hline P_4 & 3 & 0\\\hline\end{array}\)

Nun wird \(P_1\) abgearbeitet:

prozessssssss.png
\(\begin{array}{|c|c|} \hline \text{Prozess} & \text{Rechenzeit [ms]} & \text{verbleibende Rechenzeit [ms]}\\\hline P_1 & 10 & 1\\\hline P_2 & 4 & 0\\\hline P_3 & 5 & 0\\\hline P_4 & 3 & 0\\\hline\end{array}\)

\(\begin{array}{|c|c|} \hline \text{Prozess} & \text{Rechenzeit [ms]} & \text{verbleibende Rechenzeit [ms]}\\\hline P_1 & 10 & 0\\\hline P_2 & 4 & 0\\\hline P_3 & 5 & 0\\\hline P_4 & 3 & 0\\\hline\end{array}\)

b) Bei FIFO (bzw. FCFS, "First come, first served") erhÀlt ein ankommender Prozess so lange die CPU, bis er abgearbeitet wurde. Wenn wir uns also das Maximum der angegebenen Rechenzeiten heraussuchen und das als Quantum wÀhlen, können alle Prozesse komplett abgearbeitet werden. Deswegen sollte bei einem Quantum von \(10\)ms das Verhalten dem von FIFO Àhneln. Auf diese Weise wird Prozess \(P_1\) nicht unterbrochen (die anderen haben ohnehin eine geringere Rechenzeit).

von 8,4 k

Dankeschön. Was bedeutet der Pfeil nach unten in der Grafiken?

Du meist hier

"Jetzt erhÀlt P2 die CPU und wird komplett abgearbeitet. P2 wird also nicht mehr in die Queue geschickt: "

Vermutlich P4 oder?

@infomatiker

Damit signalisiere ich die Reihenfolge, in der die Warteschlange zu verstehen ist. Oben befindet sich der Prozess, der als nĂ€chstes die CPU erhĂ€lt. 

@EmNero

Ich danke Dir fĂŒr den Hinweis! Ja, gemeint ist natĂŒrlich, wie man der Grafik entnehmen kann, \(P_4\). :-)

+1 Punkt

a)

Prozess A kommt an und wird einen Slot lang abgearbeitet

A(10)

WĂ€hrend der Zeit Treffen auch Prosesse A, B und C ein. Wenn der Slot zu ende ist wird A hinten eingereiht

B(4) C(5) D(3) A(7)

Jetzt wird B einen Slot lang abgearbeitet und stellt sich hinten an

C(5) D(3) A(7) B(1)

Jetzt wird C einen Slot lang abgearbeitet und stellt sich hinten an

D(3) A(7) B(1) C(2)

Jetzt wird D abgearbeitet und ist fertig

A(7) B(1) C(2)

Jetzt wird A einen Slot lang abgearbeitet und stellt sich hinten an

B(1) C(2) A(4)

Jetzt wird B abgearbeitet und ist fertig

C(2) A(4)

Jetzt wird C abgearbeitet und ist fertig

A(4)

Jetzt wird A einen Slot lang abgearbeitet und stellt sich hinten an

A(1)

Jetzt wird A abgearbeitet und ist fertig

b)

Damit A nicht unterbrochen wird mĂŒsste das Quantum mind. 10 ms betragen.

von

Hoppla, Du warst wohl schneller :-)

DafĂŒr habe ich das auch nicht ganz so ausfĂŒhrlich notiert.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...