Round Robin

[m_stoica]

Es sollen bis zu vier Programme unterstützt werden. Übergeben
Sie die Dateinamen der MIPS* Programme als Kommandozeileargumente. Die Zeitscheibe
verfügt über insgesamt 16 Zeitslots, die gleichmäßig(soweit möglich) auf die Programme
aufgeteilt werden sollen.

Was hat es mit diesen 16 Zeitslots aufsich? Ist damit der "Zeitschlitz" aus wikipedia gemeint (http://de.wikipedia.org/wiki/Round_Robi ... ormatik%29) ? Dann wäre es aber komisch das es nur 16 sind.

[Daniel Mäurer]

In "echt" wären das natürlich zu wenig, da haben Sie recht.

[heXagon]

Ich sehe noch nicht so recht den Sinn der 16 Zeitslots, außer dass wir vermutlich den Umgang mit Pointern lernen sollen in diesem Praktikum. Ist dem so? Weil 4 Programme auf 16 Slots zu verteilen ist leicht overengineered imho.

Gruß

[Mergian]

Nehm mal das Beispiel, dass du nur 3 aktive Programme hättest. Dann wäre das so verteilt:

1. P1
2. P2
3. P3
4. P1

Wenn du nur 4 Slots nehmen würdest. Also kommt P1 doppelt so oft dran wie P2 und P3.

Bei 16. Slots wäre, dass jedes Programm 5 mal dran kommt und nur eins 6 mal.

Geht also um den fairness Aspekt.

[glowhand]

Also, so wie ich das bisher verstanden habe, ist ein Zeitslot ein Platz in der Warteschlange. Dann würde es aber egal sein, ob es zum Beispiel 16 Zeitslots oder nur 4 gibt, die Reihenfolge, wie die Programme ausgeführt werden, bleibt ja die selbe.
Und ich versteh auch nicht, wie lange ein Zeitschlitz sein soll. Sollen wir da Millisekunden messen?
Angenommen, die Zeitslots sind nicht die Elemente der Warteschlange, sondern die Zeitschlitze... für was genau steht die 16 dann überhaupt?
Ich bin mir sicher, dass das Praktikum gut machbar ist, aber die Aufgabenstellung leuchtet mir so einfach nicht ein.

[Daniel Mäurer]

Die Zeitscheibe soll16 Zeiteinheiten groß sein, das bedeutet 16 ausgeführte MIPS* Befehle. Der Begriff "Slot" war etwas mißverständlich an dieser Stelle.

[martin-t]

Guten Abend, bezüglich des Schedulings ergeben sich auch bei mir noch ein paar Fragen :

Frage 1: Wie sollen Swapping und Scheduling kombiniert werden?

Scheduling: Jeder Prozess wird 16 Befehle "lang" ausgeführt, danach wird zum nächsten wartenden Prozess gewechselt.
Swapping: Jeder Prozess wird 100 Befehle "lang" ausgeführt, danach wird zum nächsten ausgelagerten Prozess gewechselt.

Soll ein Prozess innerhalb seines 16 Befehle Zeitslots beendet und durch seinen ausgelagerten Nachfolger ersetzt werden? Das ist unsinnig, aber nach Aufgabenstellung die einzig korrekte Lösung. Sinnvoller erscheint es mir, nach Ende eines jeweiligen Zeitslots über das Swapping zu entscheiden.

Frage 2: Wie soll mit Eingabe/Ausgabe-Operationen verfahren werden?

Wird ein lesender/schreibender Prozess durch Scheduling von einem zweiten Prozess unterbrochen, der ebenfalls eine Lese-/Schreiboperation durchführen will, gibt es einen Ressourcenkonflikt.
- Sollen E/A-Operationen nur innerhalb des E/A-Prozesses blockierend sein?
- Oder soll eine E/A-Operation ALLE anderen Prozesse blockieren?

Die erste Variante erfordert die Implementierung eines eigenen Eingabe- und Ausgabebuffers für jeden E/A-Prozess. Die Frage ist also, ob Syscalls innerhalb der 16 Befehle eines Zeitslots wie einfache MIPS*-Befehle gezählt werden sollen.

Frage 3: Zählen Jump/Branch-Befehle zur Berechnung der 16 Scheduling-Befehle?

"Jumps and branches can change the control flow of a program. The MIPS ISA has a single architected
branch delay slot, so the instruction following a jump or branch is always executed (except for annulling
branch likely instructions when the branch is not taken)."

[AlexPi11]

Zu 1:
In der Aufgabe steht, dass nach 100 ausgeführten Codezeilen oder nach Beenden eines Programms geswappt werden soll. Was der Scheduler mit diesen max. 100 Zeilen macht ist dem Swapper egal.

Zu 2: EDIT(ging an der Frage vorbei):
Konflikte sollte es eigentlich nicht geben, da jeder Prozess seinen eigenen Stack hat.

Zu 3:
Da davon nichts in der Aufgabe steht, würde ich mir das Leben nicht unnötig schwer machen und einfach behaupten 1 Zeile = 1 Slot - komme was da wolle.

[jonas]

Scheduling: Ich habs so verstanden das es 16 "Plätze" gibt.
Die werden (soweit möglich) gleichmäßig auf die Programme aufgeteilt. Also 1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4 wenn es 4 Programme gibt.
Wenn es nur drei sind wäre es dann 1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1

Ist der letzte Slot erreicht wird wieder mit dem ersten begonnen. Jeder Slot besteht aus der Ausführung eines(!) Befehls des jeweiligen Programms.

Ist ein Programm zu Ende - oder es sind 100 Code-Zeilen ausgeführt worden - wird das swapping aktiv und danach werden die Zeitslots neu verteilt.

[m_stoica]

ich hatte es so verstanden:
4+Programme: 1111222233334444
3 Programme: 1111122222333331
2 Programme: 1111111122222222

[xmanu]

ich hatte es so verstanden:
4+Programme: 1111222233334444
3 Programme: 1111122222333331
2 Programme: 1111111122222222

So hab ich das auch verstanden und implementiert.

Allerdings gibt es da glaub ich Spielraum, da q (also die Anzahl Instruktionen, nach denen gewechselt wird) selbst gewählt werden kann.

[heXagon]

Scheduling war glaube so gemeint, dass jedes Programm 16 Zeiteinheiten hat, d.h. 16 Instruktionen, bevor der Scheduler dem nächsten Programm CPU-Zeit gestattet.

[swordfish]

Scheduling war glaube so gemeint, dass jedes Programm 16 Zeiteinheiten hat, d.h. 16 Instruktionen, bevor der Scheduler dem nächsten Programm CPU-Zeit gestattet.

Das würde ich so nicht sehen, da die Sprache von "Die Zeitschabe verfügt über insgesamt 16 Zeitslots" die Rede ist, die soweit möglich gleichmäßig aufgeteilt werden sollen.

Auch ich stelle mir die Frage: Warum Warteschlange, wenn man doch einfach immer abwechselnd diese 4 Programme aufrufen kann?

Aber angenommen, die Zeitschiebe sähe wirklich so aus: 1-2-3-4|1-2-3-4|1-2-3-4|1-2-3-4 (so wäre zumindest ein normales Scheduling)... was passiert dann, wenn Programm 3 nach den zweiten vier Zeitslots fertig ist? Wird dann direkt das nächste Programm geladen und erhält die Plätze von Programm 3, oder wie sieht das aus? Und was passiert, wenn nach Beenden von Programm 3, nur noch 3 Programme vorhanden sind? Rücken die anderen dann auf und schließen somit die Zeitslots (also: 1-2-4-1|2-4-1-2|...), oder werden die Zeitslots neugefüllt mit den übrigen drei (1-2-1-4|1-2-2-4)?

Fragen über Fragen.... Und irgendwie bin ich auch zu blöd momentan Google richtig zu benutzen, da ich kaum etwas zum Thema Round Robin beim Scheduling mit dem Zeitscheibenverfahren finde, was mich irgendwie weiterbringen würde.

Mein eigentliches Problem ist, dass wir hier mit ganzen Programmen arbeiten und jeder Zeitslot exakt einen Befehl verarbeiten kann. Würden wir Prozesse der Längen 53ms, 16ms und 23ms haben, dann wäre es ein einfaches, Scheduling darauf auszuführen, egal für wieviele Zeislots. Aber dank der Sprungbefehle können wir kaum vorhersehen, wie lange jedes Programm nun noch aktiv sein wird..... Vielleicht kann irgendwer meinen verknoteten Gehirn mal auf die Sprünge helfen.

Schönes Wochenende noch und schon einmal vielen Dank.

[heXagon]

Siehe http://d120.de/forum/viewtopic.php?f=18 ... 07#p109602.

Dort wird gesagt, dass es mißverständlich formuliert war, also dass ein Zeitslot 16 MIPS*-Befehle enthält.

Gruß

[jonas]

Prozesse erhalten CPU jeweils für ein festgelegtes Zeitquantum (Zeitscheibe) q

Die Zeitscheibe soll16 Zeiteinheiten groß sein, das bedeutet 16 ausgeführte MIPS* Befehle. Der Begriff "Slot" war etwas mißverständlich an dieser Stelle.

Daraus schließe ich:

jedes Programm bekommt 16 Befehle Zeit zu rechnen. Danach darf das nächste für 16 Befehle rechnen und das erste reiht sich wieder hinten in der Warteschlange ein.
Die Warteschlange hat 3 Platze - zusammen mit dem aktuell rechnendem Programm macht das die geforderten 4 aktiven Programme.

Sind 100 Befehle bearbeitet worden - oder ein Programm ist fertig - wird dieser Platz in der Warteschlange an ein anderes Programm vergeben was vorher ausgelagert war.