Algoritmo del ascensor

El algoritmo de ascensor , o SCAN , es un algoritmo de planificación de disco que determina el movimiento del brazo y el cabezal del disco para atender las solicitudes de lectura y escritura.

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

Desde el punto de vista de la 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, donde 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.

El algoritmo está prácticamente obsoleto para el almacenamiento de datos. Con la generación actual de discos magnéticos, no es posible conocer la ubicación de datos específicos en el disco, y los dispositivos de memoria de estado sólido tienen un tiempo de búsqueda constante, independiente de la ubicación. ^{[ 1 ]}

El primer tratamiento publicado del algoritmo se encuentra en el libro clásico de Donald Knuth , *El arte de la programación informática*, volumen 1, donde describe una simulación teórica de un solo ascensor en el edificio de Matemáticas del Instituto Tecnológico de California para analizar las corrutinas y las listas doblemente enlazadas . En la década de 1980, el problema se extendió a n ascensores. Actualmente se considera un problema clásico de la ingeniería de software y de la especificación formal de lenguajes de programación . ^{[ 2 ]}

Cuando llega una nueva solicitud mientras la unidad está inactiva, el movimiento inicial del brazo/cabezal se realizará en la dirección del cilindro donde se almacenan los datos, ya sea hacia adentro o hacia afuera . A medida que llegan solicitudes adicionales, estas se procesan únicamente en la dirección actual del movimiento del brazo hasta que este alcanza el borde del disco. Cuando esto sucede, la dirección del brazo se invierte y se procesan las solicitudes que quedaban en la dirección opuesta, y así sucesivamente. ^{[ 3 ]}

Una variante de este método garantiza que todas las solicitudes se atiendan en una sola dirección; es decir, una vez que el cabezal llega al borde exterior del disco, regresa al inicio y atiende las nuevas solicitudes solo en esa dirección (o viceversa). Esto se conoce como el "Algoritmo del Ascensor Circular" o C-SCAN. Si bien se desperdicia tiempo en la búsqueda de retorno, esto resulta en 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 del ascensor estándar, donde los cilindros centrales se atienden hasta el doble de veces que los cilindros más internos o más externos.

Otras variantes incluyen:

• FSCAN
• MIRAR
  • C-LOOK
• Escaneo de N pasos

A continuación se muestra un ejemplo de cómo calcular los tiempos promedio de búsqueda en disco para los algoritmos SCAN y C-SCAN.

• Ejemplo de lista de solicitudes de disco pendientes (ordenadas por número de pista): 100, 50, 10, 20, 75.
• El número de pista inicial para los ejemplos será el 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 llegar a la última pista en cola. Para este ejemplo, supongamos que el algoritmo SCAN está pasando de una pista menor a una mayor (como lo hace C-SCAN). En ambos métodos, se toma la diferencia (es decir, el valor absoluto) entre la siguiente solicitud de pista y la pista actual.

• Buscar 1: 50 − 35 = 15
• Buscar 2: 75 − 50 = 25
• Busca 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 ir a las solicitudes de pistas más altas.

• Buscar 4 (ESCANEAR): 20 − 100 = 80
• Buscar 5 (ESCANEAR): 10 − 20 = 10
• Total (ESCANEO): 155
• Promedio (ESCANEO): 155 ÷ 5 = 31
• Búsqueda 4 (C-SCAN): 0 − 100 = 0 movimiento de la cabeza ya que los cilindros se tratan como una lista circular (C-SCAN siempre vuelve a la primera pista)
• Buscar 5 (C-SCAN): 10 − 0 = 10
• Buscar 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 operaciones de entrada/salida.

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

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

• FIFO (informática y electrónica)