FCFS y SSTF

1. Qué decide el planificador

El tema 41 separó búsqueda, rotación, transferencia y espera en cola. Ahora supondremos que hay varias solicitudes disponibles y que podemos elegir cuál despachar. La posición final de una operación será la posición inicial de la siguiente.

Política de planificación de disco: regla que selecciona una petición entre las pendientes. FCFS significa First Come, First Served: primero en llegar, primero en atenderse. SSTF significa Shortest Seek Time First: priorizar la búsqueda estimada más corta.

Para SSTF usaremos la distancia entre cilindros como aproximación del coste de búsqueda. Es un modelo didáctico de HDD: una dirección LBA real no revela por sí sola el cilindro físico, y en un SSD no hay un cabezal que recorrer.

2. Contrato del modelo de cilindros

• Una sola operación se atiende a la vez y se completa antes de seleccionar otra.
• En las trazas estáticas todas las solicitudes están pendientes al inicio; la lista conserva su orden de llegada.
• Cada solicitud tiene identidad propia, aunque comparta cilindro con otra.
• La distancia de h a c es |c − h| y se mide en cilindros.
• No agregamos un regreso al origen ni viajes a los extremos del disco.
• Un empate de SSTF se resuelve por orden de llegada; si la llegada coincide, por el identificador asignado al ingresar.
• No modelamos rotación, tamaño de transferencia, fusión, caché ni reordenamiento del firmware.

El ejemplo manual usa cilindros de 0 a 199. El programa general admite coordenadas de 0 a 1000000 para ensayar otros casos; no consulta una geometría real. El simulador permite fijar el mayor cilindro válido.

Si dos peticiones se fusionaran, cambiarían el número de operaciones y su identidad. Aquí se conservan separadas para comparar políticas sobre la misma carga. Los resultados describen únicamente este contrato.

3. Recorrido, espera y respuesta

h0 = posición inicial
h1, h2, ..., hn = cilindros en orden de atención

di = |hi − h(i−1)|
D = d1 + d2 + ... + dn
Recorrido medio por petición = D / n

Se cuenta el primer desplazamiento desde h0. Si una petición está en la posición actual, aporta cero distancia, pero sigue siendo una operación. D/n es distancia media por operación, no latencia media.

Para hablar de tiempo necesitamos otro contrato. Si un ejercicio establece servicio = a × distancia + b, con a en ms/cilindro y b en ms/operación, podemos obtener inicio y final de cada servicio. La espera es inicio − llegada y la respuesta es final − llegada.

Con ese modelo lineal, una cola estática de n operaciones cuesta aD + nb hasta completar la última. Si a = 0,05 y b = 1, FCFS con D=640 tarda 40 ms y SSTF con D=236 tarda 19,8 ms. Son tiempos calculados a partir de una regla inventada; no se miden ni se deducen del nombre del algoritmo.

4. FCFS: respetar el orden de llegada

FCFS, también llamado FIFO, toma la solicitud más antigua de la cola. Una petición posterior no adelanta a otra que continúa pendiente. El planificador no necesita buscar el cilindro más próximo.

mientras haya solicitudes pendientes:
    retirar la primera de la cola
    sumar distancia desde el cabezal actual
    atenderla por completo
    actualizar el cabezal al cilindro atendido

Es simple y permite razonar sobre el orden. Si una solicitud tiene un número finito de predecesoras y cada servicio termina en tiempo finito, las llegadas posteriores no impiden que sea atendida. Esto no constituye una cota de tiempo independiente de la carga: una petición puede encontrar una cola muy larga o una operación previa lenta.

Su desventaja espacial es que alternar solicitudes lejanas obliga a cruzar repetidamente el disco. Además, una solicitud corta puede esperar detrás de trabajo costoso. Respetar llegada no garantiza el menor recorrido ni iguales tiempos de respuesta.

5. Traza completa de FCFS

Partimos del cilindro 53. La cola, en orden de llegada, es 98, 183, 37, 122, 14, 124, 65, 67. Asignamos R1 a 98, R2 a 183 y así sucesivamente. Todas están disponibles antes de comenzar.

Orden: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67
Recorrido total: 640 cilindros
Recorrido medio: 640 / 8 = 80 cilindros por petición

El hecho de pasar por un cilindro solicitado no atiende automáticamente esa petición. Al viajar de 98 a 183 pasamos por la coordenada 122, pero R4 conserva su lugar en la cola. Atenderla en ese momento cambiaría la política.

6. SSTF: elegir desde la posición actual

SSTF examina las solicitudes pendientes y elige la de menor distancia al cabezal actual. Tras completar una operación, se actualiza la posición y se vuelven a calcular las distancias. La decisión anterior modifica el problema siguiente.

mientras haya solicitudes pendientes:
    mejor = ninguna
    recorrer pendientes en orden de llegada:
        si no hay mejor o distancia(actual, candidata) < distancia(actual, mejor):
            mejor = candidata
    retirar y atender mejor
    actualizar actual = cilindro de mejor

La comparación usa <, no ≤: una candidata igual de cercana no reemplaza a la más antigua. Si cambiamos el desempate, el recorrido posterior puede cambiar. El empate es parte de la especificación.

Ordenar una sola vez por distancia a la posición inicial no implementa SSTF. Tampoco equivale a ordenar de menor a mayor cilindro. En cada paso importa dónde quedó el cabezal.

En este modelo, «búsqueda más corta» se aproxima por distancia. Si se incluyeran posición angular y transferencia, seleccionar el menor tiempo de acceso requeriría información adicional. El capítulo Hard Disk Drives de OSTEP desarrolla la diferencia entre SSTF y políticas que consideran también rotación.

7. Traza completa de SSTF

En 53, R7=65 está a 12 cilindros y R3=37 a 16: elegimos R7. Desde 65, R8=67 queda a 2. Después de R8 se recalculan las distancias desde 67: R3=37 queda a 30 y R1=98 a 31. Esa diferencia de un cilindro decide el siguiente paso.

Orden: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183
Recorrido total: 236 cilindros
Recorrido medio: 236 / 8 = 29,5 cilindros por petición
Reducción respecto de FCFS: (640 − 236) / 640 × 100 = 63,125 %

La reducción corresponde a esta carga y este inicio. R2 pasa del segundo al último lugar. El recorrido agregado mejora, pero una petición concreta puede esperar más decisiones que con FCFS.

8. Empates, duplicados y posición inicial

Con cabezal en 50 y cola 60, 40, ambas solicitudes están a 10. Elegimos R1=60 por ser la más antigua; después atendemos R2=40. El total es 10 + 20 = 30. Si la lista es 40, 60, el primer destino cambia.

Con cola 50, 50, 60 e inicio 50, las dos primeras operaciones aportan cero distancia y la tercera aporta 10. Hay tres solicitudes atendidas. Un conjunto que elimine duplicados estaría cambiando la carga.

La posición inicial también forma parte de la entrada. No se deduce del primer elemento ni se omite su primer desplazamiento. Para un único destino c el recorrido es |c − h0|, y para una cola vacía es cero, aunque nuestro ejecutable exige al menos una solicitud para evitar un promedio sin denominador.

Al comparar políticas se reinicia el cabezal en la misma posición y se restaura la cola completa. Usar la posición final de FCFS como inicio de SSTF invalida la comparación.

9. Comparar resultados sin prometer un óptimo

SSTF es una regla voraz: elige el mejor paso inmediato según su criterio. Eso no garantiza el menor recorrido de toda la cola ni que siempre gane a un orden FCFS concreto.

Contraejemplo: inicio 50 y cola 40, 0, 100, 60. FCFS recorre 10 + 40 + 100 + 40 = 190. SSTF elige 40, luego 60, después 100 y finalmente 0: 10 + 20 + 40 + 100 = 170. Aunque mejora FCFS, existe otra ruta: 40 → 0 → 60 → 100, con 10 + 40 + 60 + 40 = 150. La elección local no encontró el mínimo.

Incluso puede perder contra FCFS: inicio 50 y cola 0, 40, 60, 100. FCFS sigue 0 → 40 → 60 → 100 y recorre 150. SSTF empieza por 40 debido al empate con 60 y termina con la ruta de 170. Una comparación correcta calcula el caso; no aplica una desigualdad universal.

10. Nuevas llegadas y decisiones no apropiativas

En una carga dinámica cada solicitud tiene instante de llegada. Solo pueden competir las que ya llegaron y siguen pendientes. Una solicitud futura no se adelanta porque su cilindro resulte conveniente.

Usaremos decisiones no apropiativas: una vez despachada una operación, se la deja terminar. Una nueva llegada se incorpora a la próxima selección. Si la cola está vacía, el reloj avanza a la siguiente llegada o el simulador registra un intervalo ocioso.

1. Completar la operación anterior, si corresponde.
2. Incorporar todas las llegadas con instante ≤ t.
3. Elegir una petición disponible usando FCFS o SSTF.
4. Atenderla hasta su finalización; no cambiarla a mitad de servicio.

El experimento siguiente usa ranuras de una unidad: cada servicio dura una ranura, cualquiera que sea la distancia. Las llegadas ocurren al inicio de cada ranura. Este reloj ayuda a estudiar el orden y la espera; no representa milisegundos ni la mecánica de un HDD.

11. Cómo aparece la inanición

Inanición significa que una solicitud permanece pendiente indefinidamente mientras otras siguen atendidas. Una espera larga observada durante un experimento finito no demuestra por sí sola una espera infinita.

Construimos un caso: cabezal en 50, solicitud lejana F al cilindro 199 desde t=0 y una solicitud cercana Nt en cada ranura t, alternando cilindros 50 y 51. F entra antes que N0. Todos los servicios duran una ranura.

• FCFS elige F en t=0: es la más antigua. Finaliza en t=1.
• SSTF elige N0=50, a distancia cero. En t=1 prefiere N1=51, a distancia uno.
• Mientras siga llegando una cercana, el cabezal permanece entre 50 y 51: la siguiente cercana está a lo sumo a uno y F está al menos a 148.
• Si ese flujo continúa para siempre, F nunca resulta elegida por SSTF.

Si detenemos las cercanas tras K llegadas, SSTF atiende esas K solicitudes y después F, que comienza en t=K y termina en K+1. La cola finita se vacía: el caso ilustra cómo crece la espera y permite razonar sobre la prolongación infinita.

Para incorporar equidad se pueden considerar antigüedad, plazos o restricciones al adelantamiento. Cambiar la prioridad de esa manera crea otra política y exige describir sus reglas. En el tema 43 estudiaremos recorridos direccionales.

12. Programa en C: ejecutar ambas políticas

Guarda planificar-disco.c. Recibe fcfs|sstf, posición inicial y de 1 a 100 solicitudes. Solo acepta enteros decimales entre 0 y 1000000, sin signo. El índice de entrada identifica a cada solicitud y determina los desempates. Devuelve 2 ante uso incorrecto y 0 al producir la traza.

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <string.h>

#define MAX_PETICIONES 100
#define MAX_CILINDRO UINT32_C(1000000)

struct peticion {
    uint32_t cilindro;
    int atendida;
};

static int decimal(const char *s, uint32_t *valor)
{
    uint32_t n = 0;
    if (!*s) return -1;
    for (; *s; ++s) {
        if (*s < '0' || *s > '9') return -1;
        uint32_t d = (uint32_t)(*s - '0');
        if (n > (MAX_CILINDRO - d) / 10) return -1;
        n = n * 10 + d;
    }
    *valor = n;
    return 0;
}
static uint32_t distancia(uint32_t a, uint32_t b)
{
    return a >= b ? a - b : b - a;
}
int main(int argc, char **argv)
{
    struct peticion cola[MAX_PETICIONES] = {0};
    uint32_t actual;
    if (argc < 4 || argc > MAX_PETICIONES + 3 ||
        (strcmp(argv[1], "fcfs") && strcmp(argv[1], "sstf")) ||
        decimal(argv[2], &actual)) {
        fprintf(stderr, "Uso: %s fcfs|sstf inicial c1 [c2 ... c100]\n", argv[0]);
        return 2;
    }
    int n = argc - 3, sstf = !strcmp(argv[1], "sstf");
    for (int i = 0; i < n; ++i) {
        if (decimal(argv[i + 3], &cola[i].cilindro)) {
            fprintf(stderr, "Cilindro invalido en R%d\n", i + 1);
            return 2;
        }
    }
    uint64_t total = 0;
    puts("paso,id,desde,hasta,distancia,acumulado");
    for (int paso = 0; paso < n; ++paso) {
        int mejor = paso;
        if (sstf) {
            mejor = -1;
            for (int i = 0; i < n; ++i) {
                if (cola[i].atendida) continue;
                if (mejor == -1 || distancia(actual, cola[i].cilindro) <
                    distancia(actual, cola[mejor].cilindro)) mejor = i;
            }
        }
        uint32_t destino = cola[mejor].cilindro;
        uint32_t tramo = distancia(actual, destino);
        total += tramo;
        printf("%d,%d,%" PRIu32 ",%" PRIu32 ",%" PRIu32 ",%" PRIu64 "\n",
               paso + 1, mejor + 1, actual, destino, tramo, total);
        cola[mejor].atendida = 1;
        actual = destino;
    }
    printf("TOTAL=%" PRIu64 "\nMEDIA=%.6f\n", total, (double)total / n);
    return 0;
}

La distancia se calcula restando el menor del mayor para evitar el subdesbordamiento de una resta sin signo. No usamos abs sobre una resta que ya pudo desbordar. El total usa uint64_t y cada coordenada se valida antes del cálculo. En el contrato, 100 tramos de a lo sumo 1000000 mantienen el total acotado.

El analizador comprueba el límite antes de multiplicar por diez. Se validan todas las entradas antes de imprimir la cabecera, para no mezclar una traza parcial con un error de entrada. Los formatos PRIu32 y PRIu64 corresponden a los tipos impresos.

FCFS usa el índice del paso como siguiente posición de la cola, por lo que procesa toda la carga en O(n). SSTF explora las pendientes en cada selección y necesita O(n²) con esta implementación. El arreglo de marcas conserva duplicados y no modifica sus coordenadas.

13. Experimento en Python: observar una solicitud lejana

Guarda llegadas-disco.py. Recibe la política, cantidad K de cercanas y horizonte H en ranuras. Admite K de 0 a 1000 y H de 1 a 1001. F llega primero en t=0; Nt llega en t para 0 ≤ t < K. El desempate usa el identificador de ingreso.

import argparse

def simular(politica, cercanas, horizonte):
    pendientes = [{'id': 0, 'nombre': 'F', 'cilindro': 199, 'llegada': 0}]
    actual = 50
    final_f = None
    filas = []
    for t in range(horizonte):
        if t < cercanas:
            pendientes.append({'id': t + 1, 'nombre': f'N{t}',
                               'cilindro': 50 + t % 2, 'llegada': t})
        if not pendientes:
            filas.append((t, '-', actual, actual, 0, 0))
            continue
        if politica == 'fcfs':
            elegida = min(pendientes, key=lambda r: (r['llegada'], r['id']))
        else:
            elegida = min(pendientes, key=lambda r:
                          (abs(r['cilindro'] - actual), r['llegada'], r['id']))
        pendientes.remove(elegida)
        espera = t - elegida['llegada']
        respuesta = t + 1 - elegida['llegada']
        filas.append((t, elegida['nombre'], actual, elegida['cilindro'],
                      espera, respuesta))
        actual = elegida['cilindro']
        if elegida['id'] == 0:
            final_f = t + 1
    return filas, final_f, pendientes

def main():
    parser = argparse.ArgumentParser(description='FCFS/SSTF en ranuras abstractas')
    parser.add_argument('politica', choices=('fcfs', 'sstf'))
    parser.add_argument('cercanas', type=int)
    parser.add_argument('horizonte', type=int)
    a = parser.parse_args()
    if not 0 <= a.cercanas <= 1000 or not 1 <= a.horizonte <= 1001:
        parser.error('K debe estar entre 0 y 1000; H entre 1 y 1001')
    filas, final_f, pendientes = simular(a.politica, a.cercanas, a.horizonte)
    print('t,id,desde,hasta,espera,respuesta')
    for fila in filas:
        print(','.join(map(str, fila)))
    print('FINAL_F=' + ('pendiente' if final_f is None else str(final_f)))
    print('PENDIENTES=' + str(len(pendientes)))

if __name__ == '__main__':
    main()

Una fila ociosa usa id «-» y ceros en espera y respuesta como marcadores; no corresponde a una solicitud terminada. PENDIENTES cuenta las que ya llegaron y siguen en cola al terminar H, no las cercanas futuras. Para analizar una solicitud inacabada, se informa cuánto lleva esperando y su estado; no se inventa su respuesta final.

14. Laboratorio con casos contrastantes

En Bash, crea un directorio nuevo y guarda allí los dos fuentes. Se requieren un compilador C, Python 3 y ninguna imagen ni dispositivo. Los bloques siguientes se copian sin prefijos de terminal.

mkdir laboratorio42
cd laboratorio42
# Guardar aqui planificar-disco.c y llegadas-disco.py.
cc -std=c11 -O2 -Wall -Wextra -Wpedantic planificar-disco.c -o planificar-disco
./planificar-disco fcfs 53 98 183 37 122 14 124 65 67
./planificar-disco sstf 53 98 183 37 122 14 124 65 67
./planificar-disco sstf 50 60 40
./planificar-disco sstf 50 50 50 60
./planificar-disco fcfs 50 0 40 60 100
./planificar-disco sstf 50 0 40 60 100

Para la carga principal, las últimas líneas deben ser TOTAL=640 y MEDIA=80.000000 con FCFS; TOTAL=236 y MEDIA=29.500000 con SSTF. En el empate 60/40, R1 debe aparecer primero. En el caso con duplicados deben aparecer las tres identidades, incluso las dos distancias cero.

python3 llegadas-disco.py fcfs 12 12
python3 llegadas-disco.py sstf 12 12
python3 llegadas-disco.py sstf 12 13
python3 llegadas-disco.py sstf 100 100
python3 llegadas-disco.py sstf 100 101

Con FCFS, F termina en 1. Con SSTF y K=12, H=12, sigue pendiente: se completaron N0 a N11. Si extendemos H a 13 sin agregar cercanas, F termina en 13. Con K=100 la misma construcción posterga su final hasta 101. El horizonte limita la observación; K controla cuándo se detiene el flujo.

No se ejecutan lecturas físicas. Medir cuánto tarda el programa en calcular su traza sería medir el simulador y su salida, no el movimiento de un cabezal real. La comparación usa los datos calculados por el modelo.

15. Verificador reproducible de trazas

Desde laboratorio42 ejecuta este bloque con Python 3. Comprueba la selección en cada paso, conserva identidades y duplicados, recalcula distancias y suma, contrasta casos conocidos y valida rechazos. Las entradas aleatorias usan una semilla fija.

python3 - <<'PY'
import csv
import io
import math
import random
import runpy
import subprocess

def ejecutar(args, estado=0):
    r = subprocess.run(args, capture_output=True, text=True)
    assert r.returncode == estado, (args, r.returncode, r.stderr)
    return r.stdout

def comprobar(politica, inicio, cola):
    texto = ejecutar(['./planificar-disco', politica, str(inicio), *map(str, cola)])
    lineas = texto.splitlines()
    filas = list(csv.DictReader(io.StringIO('\n'.join(lineas[:-2]))))
    assert len(filas) == len(cola)
    pendientes = set(range(len(cola)))
    actual, total = inicio, 0
    for paso, fila in enumerate(filas, 1):
        i = int(fila['id']) - 1
        assert i in pendientes
        esperado = min(pendientes) if politica == 'fcfs' else min(
            pendientes, key=lambda j: (abs(cola[j] - actual), j))
        assert i == esperado, (politica, paso, i, esperado)
        distancia = abs(cola[i] - actual)
        total += distancia
        assert [int(fila[k]) for k in ('paso', 'desde', 'hasta', 'distancia', 'acumulado')] == [
            paso, actual, cola[i], distancia, total]
        actual = cola[i]
        pendientes.remove(i)
    assert not pendientes
    assert lineas[-2] == f'TOTAL={total}'
    assert math.isclose(float(lineas[-1].split('=')[1]), total / len(cola), abs_tol=0.000001)
    return total

principal = [98, 183, 37, 122, 14, 124, 65, 67]
assert comprobar('fcfs', 53, principal) == 640
assert comprobar('sstf', 53, principal) == 236
assert comprobar('sstf', 50, [60, 40]) == 30
assert comprobar('sstf', 50, [50, 50, 60]) == 10
assert comprobar('fcfs', 50, [0, 40, 60, 100]) == 150
assert comprobar('sstf', 50, [0, 40, 60, 100]) == 170
rng = random.Random(42)
for n in (1, 2, 8, 30, 100):
    for _ in range(10):
        cola = [rng.randrange(1000001) for _ in range(n)]
        inicio = rng.randrange(1000001)
        for politica in ('fcfs', 'sstf'):
            comprobar(politica, inicio, cola)
for args in ([], ['otro', '50', '60'], ['sstf', '-1', '60'],
             ['fcfs', '50'], ['sstf', '50', '1000001'],
             ['sstf', '50', '1.5'], ['sstf', '50', ''],
             ['sstf', '50', '999999999999999999999999'],
             ['fcfs', '50', *(['0'] * 101)]):
    ejecutar(['./planificar-disco', *args], 2)

simular = runpy.run_path('llegadas-disco.py')['simular']
for k in (0, 1, 12, 100, 1000):
    filas, final, pendientes = simular('fcfs', k, 1)
    assert final == 1 and filas[0][1] == 'F'
    if k:
        filas, final, pendientes = simular('sstf', k, k)
        assert final is None and [r['nombre'] for r in pendientes] == ['F']
        assert [f[1] for f in filas] == [f'N{t}' for t in range(k)]
    filas, final, pendientes = simular('sstf', k, k + 1)
    assert final == k + 1 and not pendientes
ejecutar(['python3', 'llegadas-disco.py', 'sstf', '-1', '10'], 2)
print('OK: trazas, desempates, duplicados, limites y espera con nuevas llegadas')
PY

El verificador usa una referencia basada en el mínimo de claves para comprobar cada elección. No exige que SSTF gane siempre: incluye un caso donde pierde. La prueba dinámica verifica horizontes finitos; la posibilidad de inanición infinita se justifica con la construcción de la sección 11.

16. Simuladores de recorrido y llegadas

Comparar la misma cola con ambas políticas

Introduce hasta 100 cilindros separados por comas, sin elementos vacíos. R1, R2 y los demás identifican la posición original. Cada fila contiene las decisiones de ambas políticas para ese número de paso. En los gráficos, el eje horizontal representa cilindros y el vertical representa orden de atención; no es una escala de tiempo.

Ver cuándo termina una solicitud lejana

Se reproduce el modelo de ranuras del programa Python. F llega en t=0 al cilindro 199; las cercanas alternan 50 y 51. Cada operación dura una ranura. K limita las nuevas llegadas y H limita la observación. Para ver a F terminar con SSTF, prueba K=12 y H=13.

17. Diagnóstico y resumen

• FCFS conserva el orden de llegada y SSTF busca la menor distancia desde la posición actual.
• Posición inicial, identidades y desempates forman parte de la entrada y del contrato.
• El recorrido suma valores absolutos de todos los tramos, incluido el primero.
• Distancia, tiempo de espera y tiempo de respuesta son métricas distintas.
• La elección local de SSTF no garantiza un recorrido global mínimo ni ganar a toda cola FCFS.
• Una cola estática finita de servicios que terminan no demuestra inanición.
• Las llegadas cercanas continuas pueden impedir indefinidamente el servicio de una petición lejana con SSTF.
• Los simuladores comparan políticas abstractas; no miden ni configuran el planificador real del sistema.

18. Preguntas de repaso y práctica

Para practicar

1. Reproduce las dos trazas principales sin mirar los acumulados y contrasta sus totales.
2. Con inicio 100 y cola 10,190,20,180, compara FCFS y SSTF y documenta los empates.
3. Invierte el orden de llegada de 60 y 40 desde 50 y observa qué cambia.
4. Agrega solicitudes duplicadas en la posición inicial y explica el efecto sobre D y D/n.
5. Comprueba el contraejemplo en el que FCFS recorre 150 y SSTF 170.
6. Usa el modelo temporal a=0,05 ms/cilindro y b=1 ms/operación para calcular espera y respuesta de cada solicitud principal, suponiendo llegada cero.
7. Explica por qué terminar antes toda la cola no implica que cada solicitud termine antes.
8. Compila el programa C y ejecuta el verificador, incluidos los límites y los rechazos.
9. Prueba K=0, K=1 y K=100 y elige horizontes que permitan observar a F terminar.
10. Describe qué información falta para transformar SSTF por distancia en una política que considere rotación.
11. Modifica una copia del algoritmo para desempatar por menor cilindro y encuentra un caso donde cambie el total.
12. Propón una regla que considere antigüedad y especifica cuándo una lejana podría adelantar a las cercanas.

En el tema 43 estudiaremos SCAN, C-SCAN y LOOK: recorridos direccionales que permiten comparar distancia y organización del servicio con otras reglas.