Betriebssysteme

Welche Arten von Scheduling gibt es?

Zunächst mal Preemptive und Non-Preemptive.

Non-Preemptive heißt: Scheduling-Entscheidungen finden nur statt, wenn ein Process von Running nach Waiting schaltet oder wenn er terminiert. Non-Preemptive nennt man auch Cooperating.

Nun zu den davon unabhängigen Scheduling-Varianten:

  1. First Come, First Served - mit FIFO-Schlange implementiert. Hier ist die Wartezeit nicht gerade minimal! Hängt eben ganz davon ab, ob ein langer Job zuerst kommt, order nicht. Beim Preemtive Scheduling wird zusätzlich auch dann geschaltet, wenn er von Running nach Ready schaltet (z.B. bei einem Interrupt) und wenn er von waiting nach Ready schaltet (z.B. wenn I/O fertig).
  2. Shortest Job First - Der Prozess, der den kleinsten nächsten CPU-Burst hat, kriegt die CPU als nächstes. Wenn zwei gleich sind, kommt eben wieder FCFS zum Tragen. SJF ist die Strategie mit der minimalen Wartezeit! Das ist beweisbar - und zwar supersimpel, klar. Aaaber: Weil wir die Länge des nächsten Bursts nicht einschätzen können, können wir das auch nicht für Short Term Scheduling implementieren. Wir könnten das höchstens schätzen. SJF können wir auch NON-Preemptive machen.
  3. Shortest Remaining Time First: Entspricht Preemptiven SJF. Da darf man nämlich auch mal nen Prozess unterbrechen.
  4. Priority Scheduling: Prozesse mit gleicher Priorität werden untereinander FCFS behandelt. In hoch ausgelasteten Systemen kommen Prozesse mit niedriger Priorität aber vielleicht nicht dran. Idee: Aging! Je länger einer wartet, desto höher wird seine Priorität. Kann man auch Non-Preemptive machen.
  5. Round Robin: Ähnlich wie FCFS, aber Preemption wird hinzugefügt. Wenn man die Zeitdauer, die Round Robin immer vergibt, extrem klein macht, ist das schon mit Processor Sharing zu vergleichen. Aber: Dann haben wir sooo viele Context Switches, dass das wieder sehr unperformant wird. Wenn wir aber ein sehr großes Zeitquantum verwenden, dann wird RR zu FCFS.
  6. Dann gibt es noch Multilevel Queue Scheduling, also zum Beispiel eine Aufteilung in Vorder- und Hintergrundprozesse, wobei beide unterschiedliche Scheduling-Verfahren verwenden.
  7. Und dann noch Multilevel Feedback-Queue Scheduling - da dürfen die Prozesse auch mal die Queue wechseln, wenn man merkt, dass sie in einer anderen besser aufgehoben sind.

Stichworte

Kommentare (0)