0 Daumen
1,3k 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?

Avatar 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).

Avatar von

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 Daumen

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.

Avatar 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 einfach und kostenlos

x
Made by a lovely community