Shortest Job First?

vip*r

Hi Leute!

Ich hab hier ein Beispiel zu einem Shortest Job First (non-preemptive)

Process   Arrival Time     Burst Time
P1:        0.0                7
P2:        2.0                4
P3:        4.0                1
P4:        5.0                4

Ich möchte hier nun die average waiting time ausrechnen. Wir haben das als Beispiel gemacht und auf folgende Rechnung gekommen:

time = (0+6+3+7)/4 = 4

Ich hab mir dazu auch schon eine Grafik gemacht, die die 3 Prozesse zeigt. P1 beginnt bei 0 und geht bis zu P3 bei 7 dann kommt P2 bis 12 und dann noch P4 bis 16. Wie komm ich von diesem Graph nun auf die obige Rechnung? Das verstehe ich nicht. Vielleicht könnt ihr mir helfen?

cooky451

Ich habe zwar keine Ahnung davon, aber ich versuche es mal:

Zu Beginn gibt's nur P1, P1 muss nicht warten (0) und dauert 7. Während 7 kommen P2, P3, P4. Nach 7 wird P3 ausgeführt, da kürzeste Dauer. P3 kam bei 4, musste also (7 - 4 = 3) warten. Danach wird P2 ausgeführt, P2 kam bei 2, musste also (7 + 1 - 2 = 6) warten. Danach wird P4 ausgeführt, P4 kam bei 5, musste also (7 + 1 + 4 - 5 = 7) warten. Dann noch den Durchschnitt berechnen und man kommt auf das gleiche Ergebnis.

Auf Vorrechnen habe ich jetzt keine Lust. Aber du kannst wie folgt vorgehen:
markiere für jede der Tasks den Zeitpunkt zu dem sie Laufbereit werden (arrival time). Dann zählst du für jede Tasks wie viele Zeiteinheiten sie warten müssen bis sie ausgeführt werden. Die erhaltenen Zahlen summierst du und teilst sie durch die Anzahl der Tasks.

Ich gehe mal davon aus, dass dein Gantt-Chart richtig gezeichnet ist. Sonst prüfe den bitte noch einmal. Da du keine Preemption hast musst du immer wenn ein Job fertig wird unter allen Laufbereiten den auswählen mit der kürzesten Rechenzeit. Wenn du dir zuerst auf dem Chart markierst wo jeder Laufbereit wird, ist es auch leicht zu sehen wo und wann du zwischen welchen auswählen musst.