Disk Scheduling

Norbert Bartos

Plattenspeicher sind bekannterweise Massenspeicher mit relativ großer Zugriffszeit. Um so eher muss dafür gesorgt werden, dass ihre Kooperation mit dem Halbleiterspeicher auf dem Prozessorplatine möglichst effizient abläuft. Der nachstehende Text ist aus folgendem Buch übernommen:

Das Buch ist ein ausgesprochen umfassendes Werk und kann durchaus als ein Standardwerk angesehen werden. Es werden alle Aspekte moderner Betriebssysteme behandelt. Am Ende jedes Kapitels befinden sich viele Fragen zur Wiederholung und Vertiefung des Inhaltes. Referenzen auf reale Betriebssysteme halten das Buch praxisnahe. Es ist besonders empfehlenswert für Personen, welche an Tiefenwissen im Bereich der Betriebssysteme interessiert sind.

Eine wichtige Aufgabe von Betriebssystemen ist, die Hardware effizient zu nutzen. Im Falle von Disk-Drives bedeutet das eine geringe Zugriffszeit und eine hohe Bandbreite für die Übertragung. Die Zugriffszeit besteht im Wesentlichen aus zwei Komponenten. Die erste ist die Seek-Time, welche notwendig ist, den Arm mit den Lese-Schreib-Köpfen auf demjenigen Zylinder zu positionieren, der den gewünschten Sektor enthält. Die zweite Zeit ist die Rotational-Latency, welche vergeht, bis der gewünschte Sektor unter den Kopf gelangt. Die Bandbreite der Disk ist die gesamte Anzahl der übertragenen Bytes, dividiert durch die gesamte Zeit vom ersten I/O-Request bis zur Komplettierung des Datentransfers. Man kann nun die Zugriffszeit und die Bandbreite durch eine geeignete Wahl der Abarbeitungsreihenfolge der anstehenden Service-Requests beeinflussen. Im realen Betrieb ist immer eine bestimmte Anzahl dieser Requests in einer Queue anstehend. Der Scheduler kann nun versuchen, die Reihenfolge für die Ausführung zu optimieren.

a) FCFS-Scheduling

Die einfachste Form ist die First-Come-First-Served-Strategie (FCFS, auch FIFO bzw. First-In-First-Out-Strategie genannt). Der Algorithmus ist fair, aber liefert kein zeitoptimales Scheduling. Als Beispiel sei die Reihenfolge der einlangenden Requests für Datenblöcke durch die Zylindernummern 98, 183, 37, 122, 14, 124, 65, 67 definiert (die zulässigen Zylindernummern sind von 0 bis 199 gewählt). Falls sich der Kopf auf Position 53 befindet, so ist die Bewegungsfolge dann 53, 98, 183, 37, 122, 14, 124, 65, 67. Der Kopf bewegt sich somit über insgesamt 640 Zylinder.

b) SSTF-Scheduling

Eine weitere Möglichkeit ist das Shortest-Seek-Time-First-Verfahren (SSTF). Dabei wird als nächstes derjenige Zylinder aus der Requestliste als Ziel selektiert, welcher der momentanen Position am nächsten ist. In unserem Beispiel ergibt sich dann die Folge 53, 65, 67, 37, 14, 98, 122, 124, 183. Dabei werden nur 236 Zylinder überstrichen.

c) SCAN-Scheduling

Dieses Verfahren wird auch Fahrstuhlverfahren genannt, da zunächst einmal alle Requests in aufsteigender Folge erfüllt werden und nach der Umkehr der Kopfbewegungsrichtung  diejenigen in absteigender Folge und so weiter. Im bereits bekannten Beispiel und einer momentanen Kopfbewegung in Richtung von Zylinder 0 würde sich die Folge 53, 37, 14, 0, 65, 67, 98, 122, 124, 183 ergeben. Damit überstreicht man ebenfalls 236 Zylinder. Eine Variante ist das C-SCAN-Scheduling, bei dem während der Rückkehr in Richtung von Zylinder 0 keine Requests angenommen werden. Die Requestliste wird somit als zirkuläre Liste aufgefasst. Damit ergibt sich die Folge 53, 65, 67, 98, 122, 124, 183, 199, 0, 14, 37. Somit überstreicht man jetzt (ohne den schnellen Rücklauf) nur mehr 183 Zylinder.

d) LOOK-Scheduling

Sowohl SCAN als auch C-SCAN bewegen den Kopf jeweils bis zum ersten (0.) bzw. letzten (199.) Sektor. Das ist eigentlich nicht notwendig, d.h. die tatsächlich implementierten Verfahren besuchen nur den am weitesten entfernten Zylinder. Die entsprechenden Verfahren heißen dann LOOK und C-LOOK. Bei LOOK-Verfahren erhalten wir die Folge 53, 37, 14, 65, 67, 98, 122, 124, 183 und überstreichen damit 208 Zylinder. Beim C-LOOK-Verfahren jedoch 53, 65, 67, 98, 122, 124, 183, 14, 37 und somit werden 153 Zylinder überstrichen.

e) Auswahl des geeignetsten Algorithmus

SSTF ist aus dem Bereich des Multiprocessings allgemein bekannt und wird gerne verwendet, SCAN/C-SCAN sind gut für starke I/O-Belastung geeignet. Außer den oben erwähnten Algorithmen existieren noch weitere Verfahren, welche eher von geringerer Bedeutung für die Praxis sind. Natürlich kann für jede Requestliste ein optimales Scheduling durchgeführt werden, aber der Gewinn bei der Zugriffszeit, wird u.U. durch den Aufwand bei der Berechnung wieder zunichte gemacht. Bei neueren Disk-Systemen ist aber auch die Rotational-Latency zu berücksichtigen, da sie in der selben Größenordnung wie die Seek-Time liegt. Das macht aber zusätzliche Probleme, da die physikalische Anordnung der Sektoren eine andere ist, als die logische Anordnung. Damit müsste der Scheduling-Algorithmus auf der Controllerkarte beheimatet sein, was einzelne Kartenhersteller auch schon realisiert haben. Zusammenfassend kann gesagt werden, dass die für ein System optimale Strategie am besten durch Experimente zu ermitteln ist. Jeder Versuch eines absoluten Vergleichs ist von bestimmten Randbedingungen abhängig und damit nicht zu verallgemeinern.