Algoritmos

Algoritmo del ascensor para acceso a disco

Al algoritmo del ascensor es una técnica de optimización de los accesos que consiste en reducir en lo posible los movimientos de cambio de pista. Para ello la cabeza se va moviendo a lo largo de las pistas con un movimiento de vaivén, como un ascensor que va atendiendo las peticiones a medida que va pasando por los pisos con movimiento de subida y bajada.

Las peticiones de los distintos programas se van atendiendo en el orden de las pistas y no en el orden en que se solicitan. Además se entrelazarán las accesos a sectores de distintas peticiones, si es conveniente.

Tras leer o grabar un sector, el controlador seleccionará como siguiente operación elemental la que corresponda a la misma pista o a la pista más próxima en el sentido de movimiento actual. Si no hay ninguna petición pendiente en esas condiciones, invertirá el sentido de movimiento.

Al solicitar una operación sobre varios sectores seguidos (módulo DISCO), el orden en el que se deberán solicitar los accesos elementales vendrá marcado por la situación de la cabeza en el momento de la solicitud. Si la cabeza está en una pista igual o anterior a la del primer sector (a), los sectores se solicitarán en orden creciente. Si la cabeza está en una pista igual o posterior a la del último sector (b), los sectores se solicitarán en orden inverso. Si la cabeza está en una pista intermedia (c), se solicitarán primero los que estén en el sentido del movimiento actual, en el orden correspondiente a dicho sentido, y luego el resto en el orden contrario.

FCFS (First come, first served) served) algorithm algorithm.

El acceso que permite el algoritmo es justo.

No proporciona el servicio más rápido.

Imaginemos que se requiere acceder a los siguientes bloques dentro de un disco (bloque de inicio 60):

100, 190, 30, 180, 10, 130, 50, 70

SSTF (shortest-seek-time-first) algorithm.

De lo anterior, es razonable acomodar las solicitudes de manera que los bloques a los cuales hay que acceder, estén de manera continua… Esta es la base del algoritmo SSTF.

La idea es seleccionar la solicitud que tenga la búsqueda más rápida a partir de la posición del bloque en la que se está.

Retomando nuestro ejemplo:

100, 190, 30, 180, 10, 130, 50, 70

El algoritmo SSTF acomodaría las solicitudes de la siguiente manera:

Aun cuando se observa una mejoría con respecto al FCFS, el algoritmo no es óptimo.

Scan algorithm.

El algoritmo funciona de la siguiente manera: el apuntador inicia en el primer bloque y recorre todos los bloques hasta llegar al último y luego de regreso, durante su camino va atendiendo a las solicitudes que se le presenten en el recorrido.

Este algoritmo no es justo, debido a que si una solicitud llega, y el recorrido del apuntador es tal que puede ser atendida de inmediato, el algoritmo lo permitirá.

Una vez que el apuntador llega a un extremo, y va de regreso, algunas de las solicitudes ya fueron atendidas, por lo que en principio es obvio pensar que el regreso no tendrá solicitudes que atender. Más aun, las solitudes que lleguen después del apuntador tendrán que esperar un largo tiempo.

C-Scan (circular Scan) algorithm.

Este algoritmo es una variante del algoritmo SCAN, la idea es proporcionar un tiempo de espera un poco más uniforme.

El funcionamiento es igual al algoritmo SCAN, pero tiene la variante de que cuando llega uno de los extremos, inmediatamente regresa al otro, sin atender ninguna solicitud.

Look.

El algoritmo look, el cual funciona de manera semejante al algoritmo SCAN, pero con la diferencia de que no regresa hasta el otro extremo, sino hasta donde sea necesario.

OCX

...