El algoritmo del elevador (también SCAN ) es un algoritmo de programación de disco para determinar el movimiento del brazo y la cabeza del disco al atender las solicitudes de lectura y escritura.
Este algoritmo lleva el nombre del comportamiento de un ascensor de edificio , donde el ascensor continúa viajando en su dirección actual (hacia arriba o hacia abajo) hasta que se vacía, y se detiene solo para dejar que las personas bajen o para recoger nuevas personas que se dirigen en la misma dirección.
Desde una perspectiva de implementación, el variador mantiene un búfer de solicitudes de lectura / escritura pendientes, junto con el número de cilindro asociado de la solicitud. (Los números de cilindro más bajos generalmente indican que el cilindro está más cerca del eje, y los números más altos indican que el cilindro está más lejos).
Cuando llega una nueva solicitud mientras el variador está inactivo, el movimiento inicial del brazo / cabezal será en la dirección del cilindro donde se almacenan los datos, ya sea hacia adentro o hacia afuera . A medida que llegan solicitudes adicionales, las solicitudes se atienden solo en la dirección actual del movimiento del brazo hasta que el brazo alcanza el borde del disco. Cuando esto sucede, la dirección del brazo se invierte y se atienden las solicitudes que quedaban en la dirección opuesta, y así sucesivamente. [1]
Una variación de este método garantiza que todas las solicitudes se atiendan en una sola dirección, es decir, una vez que la cabeza ha llegado al borde exterior del disco, regresa al principio y atiende las nuevas solicitudes solo en esta dirección (o viceversa). ). Esto se conoce como el "algoritmo de elevador circular" o C-SCAN. Aunque se desperdicia el tiempo de la búsqueda de retorno, esto da como resultado un rendimiento más equitativo para todas las posiciones de la cabeza, ya que la distancia esperada desde la cabeza es siempre la mitad de la distancia máxima, a diferencia del algoritmo de elevador estándar donde los cilindros en el medio serán atendidos como hasta dos veces más a menudo que los cilindros más internos o más externos.
El siguiente es un ejemplo de cómo calcular los tiempos de búsqueda de disco promedio para los algoritmos SCAN y C-SCAN.