Algoritmo de ascensor

El algoritmo de ascensoro SCAN, es un algoritmo de programación de disco para determinar el movimiento del brazo y la cabeza del disco en el mantenimiento de solicitudes de lectura y escritura.

Este algoritmo lleva el nombre del comportamiento del ascensor de un edificio, donde el ascensor 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 las personas o para recoger 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 de 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 el cilindro está más lejos.

Descripción

Cuando llega una nueva solicitud mientras la unidad está inactiva, el movimiento inicial del brazo/cabeza será en la dirección del cilindro donde se almacenan los datos, ya sea dentro o fuera. 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.

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, regresa al principio y atiende las nuevas solicitudes en esta única dirección (o viceversa). Esto se conoce como el "algoritmo del ascensor circular" o C-SCAN. Aunque se desperdicia el tiempo de búsqueda de retorno, esto da como resultado un rendimiento más equitativo para todas las posiciones del cabezal, ya que la distancia esperada desde el cabezal es siempre la mitad de la distancia máxima, a diferencia del algoritmo de ascensor estándar donde los cilindros en el medio serán atendidos como con el doble de frecuencia que los cilindros más internos o más externos.

Otras variaciones incluyen:

• FSCAN
• Mira.
  • C-LOOK
• N-Step-SCAN

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 solicitudes de disco pendientes (listas por número de pista): 100, 50, 10, 20, 75.
• El número de pista inicial de los ejemplos será 35.
• La lista tendrá que ser clasificada 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. Por el bien de este ejemplo, supongamos que el algoritmo SCAN está pasando actualmente de un número de pista más bajo a un número de pista más alto (como lo hace el C-SCAN). Para ambos métodos, se toma la diferencia en magnitud (es decir, valor absoluto) entre la siguiente solicitud de seguimiento y el seguimiento actual.

• Buscad 1: 50 - 35 = 15
• Buscad. 75 - 50 = 25
• Busquen 3: 100 − 75 = 25

En este punto, ambos han alcanzado la solicitud de seguimiento 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 solicitudes de pistas superiores.

• Buscar 4 (SCAN): 20 − 100 = 80
• Buscar 5 (SCAN): 10 − 20 = 10
• Total (SCAN): 155
• Promedio (SCAN): 155 ÷ 5 = 31
• Buscar 4 (C-SCAN): 0 − 100 = 0 movimiento de cabeza como 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: 85
• Promedio (C-SCAN): 85 ÷ 5 = 17

A pesar de que se realizaron seis búsquedas usando el algoritmo C-SCAN, sólo se hicieron cinco I/O.

Análisis

Para ambas versiones del algoritmo del ascensor, el movimiento del brazo es menos del 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 la búsqueda más corta primero, que está ligeramente más cerca de lo óptimo, pero puede generar una gran variación en el tiempo de respuesta e incluso una escasez cuando las nuevas solicitudes reciben servicio continuamente antes que las solicitudes existentes. Se pueden aplicar técnicas anti-hambruna al algoritmo de tiempo de búsqueda más corto para garantizar un tiempo de respuesta máximo.