Algoritmo del ascensor

El algoritmo del elevador , o SCAN , es un algoritmo de programación de discos para determinar el movimiento del brazo y el cabezal del disco al atender solicitudes de lectura y escritura.

Este algoritmo recibe su nombre a raíz del comportamiento del ascensor de un edificio , donde el ascensor continúa viajando en su dirección actual (arriba o abajo) hasta que se vacía, deteniéndose solo para dejar bajar a personas o para recoger a nuevas personas que se dirigen en la misma dirección.

Desde una perspectiva de implementación, la unidad mantiene un búfer de solicitudes de lectura/escritura pendientes, junto con el número de cilindro asociado a la solicitud, en el que los números de cilindro más bajos generalmente indican que el cilindro está más cerca del husillo y los números más altos indican que el cilindro está más lejos.

Descripción

Cuando llega una nueva solicitud mientras la unidad está inactiva, 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]

Variaciones

Una variación de este método garantiza que todas las solicitudes se atiendan en una sola dirección, es decir, una vez que el cabezal ha llegado al borde exterior del disco, vuelve al principio y atiende las nuevas solicitudes en esta única dirección solamente (o viceversa). Esto se conoce como "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 uniforme para todas las posiciones del cabezal, ya que la distancia esperada desde el cabezal siempre es la mitad de la distancia máxima, a diferencia del algoritmo de elevador estándar, donde los cilindros del medio se atenderán con una frecuencia hasta dos veces mayor que los cilindros más internos o más externos.

Otras variaciones incluyen:

Ejemplo

El siguiente es un ejemplo de cómo calcular los tiempos promedio de búsqueda de disco para los algoritmos SCAN y C-SCAN.

Ejemplo de lista de solicitudes de discos pendientes (ordenadas por número de pista): 100, 50, 10, 20, 75.
El número de pista inicial para los ejemplos será 35.
La lista deberá ordenarse en orden ascendente: 10, 20, 50, 75, 100.

Tanto SCAN como C-SCAN se comportan de la misma manera hasta que llegan a la última pista en cola. Para este ejemplo, supongamos que el algoritmo SCAN está pasando actualmente de un número de pista inferior a un número de pista superior (como lo hace C-SCAN). Para ambos métodos, se toma la diferencia de magnitud (es decir, el valor absoluto) entre la siguiente solicitud de pista y la pista actual.

Busca 1: 50 − 35 = 15
Búsqueda 2: 75 − 50 = 25
Búsqueda 3: 100 − 75 = 25

En este punto, ambos han alcanzado la solicitud de pista más alta (final). SCAN simplemente invertirá la dirección y atenderá la siguiente solicitud de disco más cercana (en este ejemplo, 20) y C-SCAN siempre volverá a la pista 0 y comenzará a buscar solicitudes de pista más altas.

Búsqueda 4 (SCAN): 20 − 100 = 80
Búsqueda 5 (SCAN): 10 − 20 = 10
Total (ESCANEO): 155
Promedio (SCAN): 155 ÷ 5 = 31
Búsqueda 4 (C-SCAN): 0 − 100 = 0 movimiento del cabezal ya que los cilindros se tratan como una lista circular (C-SCAN siempre vuelve a la primera pista)
Búsqueda 5 (C-SCAN): 10 − 0 = 10
Búsqueda 6 (C-SCAN): 20 − 10 = 10
Total (C-SCAN): 85
Promedio (C-SCAN): 85 ÷ 5 = 17

Aunque se realizaron seis búsquedas utilizando el algoritmo C-SCAN, en realidad solo se realizaron cinco E/S.

Análisis

En ambas versiones del algoritmo del ascensor, el movimiento del brazo es menor que el doble del número total de cilindros y produce una variación menor en el tiempo de respuesta. El algoritmo también es relativamente simple.

El algoritmo del elevador no siempre es mejor que el algoritmo de búsqueda más corta primero , que es ligeramente más cercano al óptimo, pero puede generar una gran variación en el tiempo de respuesta e incluso inanición cuando se atienden continuamente nuevas solicitudes antes que las solicitudes existentes. Se pueden aplicar técnicas antiinanición al algoritmo de búsqueda más corta primero para garantizar un tiempo de respuesta máximo.