Aufzugsalgorithmus - Elevator algorithm

Der Aufzug - Algorithmus (auch SCAN ) ist eine Scheibe - Scheduling - Algorithmus , um die Bewegung der Scheibe Arm und Kopf in der Wartung Lese- und Schreibanforderungen zu bestimmen.

Dieser Algorithmus wird nach dem Verhalten eines Gebäudes namens Aufzug , wo der Aufzug in seiner aktuellen Richtung ( nach oben oder nach unten) Reise fortgesetzt , bis leer, nur stoppen Individuen abzulassen oder neue Personen in der gleichen Richtung zu holen.

Aus Implementierungssicht verwaltet das Laufwerk einen Puffer mit anstehenden Lese-/Schreibanforderungen zusammen mit der zugehörigen Zylindernummer der Anforderung. (Niedrige Zylindernummern bedeuten im Allgemeinen, dass sich der Zylinder näher an der Spindel befindet, und höhere Zahlen bedeuten, dass der Zylinder weiter entfernt ist.)

Beschreibung

Wenn eine neue Anforderung eintrifft , während der Antrieb im Leerlauf ist, wird die anfängliche Arm / Kopfbewegung in Richtung des Zylinders, wo die Daten gespeichert ist, entweder in oder aus . Wenn zusätzliche Anforderungen ankommen, werden Anforderungen nur in der aktuellen Richtung der Armbewegung bedient, bis der Arm den Rand der Platte erreicht. In diesem Fall wird die Richtung des Arms umgekehrt, und die Anfragen, die in der entgegengesetzten Richtung verbleiben, werden bedient usw.

Variationen

Eine Variante dieser Methode stellt sicher, dass alle Anfragen nur in eine Richtung bedient werden, d. h. sobald der Kopf am äußeren Rand der Platte angekommen ist, kehrt er zum Anfang zurück und bedient die neuen Anfragen nur in diese eine Richtung (oder umgekehrt) ). Dies ist als "Circular Elevator Algorithm" oder C-SCAN bekannt. Obwohl die Zeit für die Rückkehrsuche verschwendet wird, führt dies zu einer gleichmäßigeren Leistung für alle Kopfpositionen, da der erwartete Abstand zum Kopf immer die Hälfte der maximalen Entfernung beträgt, im Gegensatz zum Standard-Aufzugsalgorithmus, bei dem Zylinder in der Mitte als doppelt so oft wie die innersten oder äußersten Zylinder.

Andere Variationen sind:

• FSCAN
• LOOK (und C-LOOK )
• N-Schritt-SCAN

Beispiel

Im Folgenden finden Sie ein Beispiel für die Berechnung der durchschnittlichen Festplattensuchzeiten für den SCAN- und den C-SCAN-Algorithmus.

• Beispielliste der ausstehenden Festplattenanforderungen (aufgelistet nach Titelnummer): 100, 50, 10, 20, 75.
• Die Startgleisnummer für die Beispiele ist 35.
• Die Liste muss in aufsteigender Reihenfolge sortiert werden: 10, 20, 50, 75, 100.

Sowohl SCAN als auch C-SCAN verhalten sich gleich, bis sie den letzten in der Warteschlange befindlichen Titel erreichen. Nehmen wir für dieses Beispiel an, dass der SCAN-Algorithmus derzeit von einer niedrigeren Spurnummer zu einer höheren Spurnummer geht (wie es der C-SCAN tut). Bei beiden Verfahren nimmt man den Betragsunterschied (dh den absoluten Wert) zwischen dem nächsten Track-Request und dem aktuellen Track.

• Suche 1: 50 − 35 = 15
• Suche 2: 75 − 50 = 25
• Suche 3: 100 − 75 = 25

An diesem Punkt haben beide die höchste (End-)Track-Anfrage erreicht. SCAN kehrt einfach die Richtung um und bedient die nächstgelegene Plattenanforderung (in diesem Beispiel 20) und C-SCAN geht immer zurück zu Spur 0 und beginnt, zu höheren Spuranforderungen zu gehen.

• Suche 4 (SCAN): 20 − 100 = 80
• Suche 5 (SCAN): 10 − 20 = 10
• Gesamt (SCAN): 155
• Durchschnitt (SCAN): 155 ÷ 5 = 31
• Seek 4 (C-SCAN): 0 − 100 = 0 Kopfbewegung, da Zylinder als kreisförmige Liste behandelt werden (C-SCAN geht immer zum ersten Track zurück)
• Suche 5 (C-SCAN): 10 − 0 = 10
• Suche 6 (C-SCAN): 20 − 10 = 10
• Gesamt (C-SCAN): 85
• Durchschnitt (C-SCAN): 85 ÷ 5 = 17

Obwohl sechs Suchvorgänge mit dem C-SCAN-Algorithmus durchgeführt wurden, wurden tatsächlich nur fünf I/Os durchgeführt.

Analyse

Die Armbewegung ist somit für beide Versionen des Aufzugsalgorithmus immer kleiner als die doppelte Anzahl der Gesamtzylinder. Die Variation hat den Vorteil, dass sie eine geringere Varianz in der Reaktionszeit hat. Der Algorithmus ist auch relativ einfach.

Der Aufzugsalgorithmus ist jedoch nicht immer besser als der kürzeste Suchlauf zuerst , der etwas näher am Optimum liegt, kann jedoch zu einer hohen Varianz in der Antwortzeit und sogar zu einem Mangel führen, wenn neue Anforderungen kontinuierlich vor bestehenden Anforderungen bedient werden.

Anti-Starvation-Techniken können auf den Algorithmus mit der kürzesten Suchzeit angewendet werden, um eine optimale Reaktionszeit zu garantieren.

Siehe auch

• FCFS
• Kürzeste Suchzeit zuerst

Verweise