El algoritmo de ascensor (también SCAN ) es un disco - programación algoritmo para determinar el movimiento del brazo y la cabeza del disco en el servicio a 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).
Descripción
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]
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 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 ascensor 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.
Otras variaciones incluyen:
- FSCAN
- LOOK (y C-LOOK )
- N-Step-SCAN
Ejemplo
El siguiente es un ejemplo de cómo calcular los tiempos de búsqueda de disco promedio para los algoritmos SCAN y C-SCAN.
- Lista de ejemplo de solicitudes de disco pendientes (enumeradas 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. 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 está haciendo el C-SCAN). Para ambos métodos, se toma la diferencia de magnitud (es decir, valor absoluto) entre la siguiente solicitud de pista y la pista actual.
- Buscar 1:50 - 35 = 15
- Buscar 2: 75 - 50 = 25
- Buscar 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 solicitudes de pista más altas.
- Búsqueda 4 (ESCANEADO): 20 - 100 = 80
- Buscar 5 (ESCANEAR): 10 - 20 = 10
- Total (ESCANEADO): 155
- Promedio (ESCANEADO): 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
Por lo tanto, el movimiento del brazo es siempre menos del doble del número total de cilindros entonces, para ambas versiones del algoritmo del elevador. La variación tiene la ventaja de tener una variación menor en el tiempo de respuesta. El algoritmo también es relativamente simple.
Sin embargo, el algoritmo del elevador no siempre es mejor que la búsqueda más corta primero , que está un poco más cerca del óptimo, pero puede resultar en una gran variación en el tiempo de respuesta e incluso en inanición cuando las nuevas solicitudes se atienden continuamente antes de las solicitudes existentes.
Las técnicas anti-hambre se pueden aplicar al algoritmo de primer tiempo de búsqueda más corto para garantizar un tiempo de respuesta óptimo.
Ver también
Referencias
- ^ "Programación de disco" . Archivado desde el original el 6 de junio de 2008 . Consultado el 21 de enero de 2008 .