FCFS: el algoritmo más simple

1. Qué es FCFS

FCFS (First-Come, First-Served) es el algoritmo de planificación que atiende a los procesos en el orden en que llegan al sistema. El primero en llegar es el primero en recibir la CPU, y así sucesivamente. Es una cola FIFO (First-In, First-Out) aplicada a la CPU.

Es el algoritmo más antiguo y el más intuitivo: cualquiera que haya hecho cola en un banco o en un supermercado entiende la regla. No requiere conocer la duración de los procesos, no necesita prioridades ni temporizadores, y es trivial de implementar: basta con una cola.

FCFS fue el primer algoritmo de planificación usado en los sistemas por lotes de los años 60. En aquel entonces los trabajos se enviaban en tarjetas perforadas y se procesaban en el orden de llegada. La simplicidad era una virtud: los ordenadores eran lentos y el planificador debía ser lo más barato posible.

2. La cola FIFO

La estructura de datos de FCFS es una cola FIFO: los procesos entran por el final y salen por el principio. Cuando un proceso llega, se añade al final de la cola de listos. Cuando la CPU queda libre, se toma el proceso del principio de la cola.

La cola FIFO tiene tres operaciones:

• Encolar (enqueue): añadir un proceso al final de la cola. Ocurre cuando un proceso llega o cuando termina su E/S.
• Desencolar (dequeue): tomar el proceso del principio de la cola. Ocurre cuando la CPU queda libre.
• Vacía: si la cola está vacía, la CPU queda ociosa hasta que llegue un proceso.

La cola de listos de FCFS es una sola: no hay prioridades, no hay niveles, no hay turnos. Todos los procesos listos esperan en la misma cola y se atienden en orden de llegada.

3. Cómo funciona paso a paso

El funcionamiento de FCFS se reduce a un bucle con tres eventos:

1. Llega un proceso. Se añade al final de la cola de listos. Si la CPU está ociosa, se le da la CPU inmediatamente. llegada
2. Un proceso termina su ráfaga de CPU. Si tiene más ráfagas de CPU (tras una E/S), se bloquea; si terminó del todo, sale del sistema. La CPU toma el siguiente proceso de la cola. terminación
3. Un proceso termina su E/S. Se añade al final de la cola de listos (no al principio). Esperará su turno. E/S

La regla clave es que un proceso que termina su E/S se encola al final, no se le da la CPU inmediatamente. Esto es lo que diferencia a FCFS de algoritmos más sofisticados y lo que provoca el efecto convoy.

4. Un ejemplo desarrollado

Cuatro procesos con llegadas distintas:

Simulación paso a paso:

1. t = 0: llega P1. La CPU está libre, se le da. Cola: []. llegada
2. t = 1: llega P2. La CPU está ocupada (P1), se encola. Cola: [P2]. encolar
3. t = 2: llega P3. Se encola. Cola: [P2, P3]. encolar
4. t = 4: llega P4. Se encola. Cola: [P2, P3, P4]. P1 sigue ejecutándose. encolar
5. t = 5: P1 termina. La CPU toma P2 de la cola. Cola: [P3, P4]. desencolar
6. t = 8: P2 termina. La CPU toma P3. Cola: [P4]. desencolar
7. t = 12: P3 termina. La CPU toma P4. Cola: []. desencolar
8. t = 14: P4 termina. La CPU queda ociosa. fin

El Gantt resultante es:

Las métricas, calculadas con las fórmulas del tema 7 y 8:

Como FCFS es no apropiativo, cada proceso recibe la CPU una sola vez: respuesta y espera coinciden.

5. La fórmula del tiempo de espera en FCFS

Para FCFS se puede calcular el tiempo de espera sin simular la cola, usando solo las llegadas y las ráfagas. Si los procesos se ordenan por llegada (P₁, P₂, …, P_n), el tiempo de espera del proceso i es:

W_i = (Σ_j=1^i-1 B_j) − A_i + A₁ · (i − 1) … simplificando: W_i = F_i-1 − A_i, donde F_i-1 es la terminación del proceso anterior (o 0 si es el primero).

En la práctica, la forma más sencilla es simular: el inicio de P_i es el máximo entre su llegada y la terminación del anterior. Eso es exactamente lo que hace la función fcfs del tema 9.

Para el caso especial en que todos llegan en 0, la fórmula se simplifica mucho:

Si todos llegan en 0: W_i = B₁ + B₂ + … + B_i-1. Es decir, la espera de cada proceso es la suma de las ráfagas de todos los que van antes.

El tiempo de espera promedio en ese caso es:

W̄ = ( (n−1)B₁ + (n−2)B₂ + … + 1·B_n-1 ) / n.

Esta fórmula muestra que el orden importa: un proceso largo al principio multiplica su ráfaga por (n−1), mientras que al final solo suma 1. Por eso, poner los procesos largos primero dispara el promedio.

6. Propiedades de FCFS

FCFS es el único algoritmo que no necesita conocer las ráfagas de CPU. Eso lo hace aplicable cuando las ráfagas no se pueden predecir (tema 15). En ese sentido, es el algoritmo «por defecto» cuando no hay información.

7. Ventajas

• Trivial de implementar: una cola FIFO y dos operaciones (encolar, desencolar).
• Bajo overhead: no hay temporizador, no hay cambios de contexto adicionales, no hay cálculos de prioridad.
• Sin inanición: todo proceso que llega se ejecuta eventualmente.
• Justo en orden de llegada: respeta el orden cronológico, que es la noción de justicia más intuitiva.
• No necesita conocer las ráfagas: funciona aunque no se sepa cuánto va a durar cada proceso.
• Fácil de analizar: las fórmulas son simples y los resultados son predecibles.

8. Desventajas y el efecto convoy

La principal desventaja de FCFS es el efecto convoy: un proceso con ráfaga larga se ejecuta primero y hace que todos los procesos cortos que llegan después esperen. Es como un camión lento en una carretera de un solo carril: todos los coches rápidos quedan atrapados detrás.

En el ejemplo del tema 1, tres procesos de 4, 2 y 1 unidades daban un tiempo medio de 1,95 s con FCFS (orden A, B, C) y de 1,27 s con SJF (orden C, B, A). La diferencia es el efecto convoy.

Otras desventajas:

• No optimiza ninguna métrica: ni espera, ni retorno, ni respuesta. Solo respeta el orden de llegada.
• Mala respuesta: un proceso corto que llega después de uno largo espera todo el tiempo del largo. El tiempo de respuesta puede ser enorme.
• Sensible al orden de llegada: si los procesos largos llegan primero, el promedio se dispara.
• No distingue entre procesos interactivos y por lotes: un clic del usuario espera lo mismo que una compilación.

9. FCFS es no apropiativo

FCFS es inherentemente no apropiativo: una vez que un proceso recibe la CPU, la conserva hasta que termina su ráfaga de CPU o se bloquea en E/S. El planificador no puede interrumpirlo.

Esto tiene dos consecuencias:

• Un proceso largo no se puede interrumpir: aunque llegue un proceso más corto o más urgente, debe esperar.
• No hay quantum: no hay temporizador que fuerce un cambio de contexto. El cambio solo ocurre cuando el proceso termina o se bloquea.

La no apropiación simplifica la implementación (no hay que manejar interrupciones de temporizador), pero reduce la capacidad de respuesta del sistema. Por eso, FCFS se combina con apropiación en algoritmos más avanzados (Round Robin, SRTF).

10. Cuándo se usa FCFS

FCFS se usa en situaciones donde la simplicidad y la predecibilidad importan más que la optimización:

• Sistemas por lotes (batch): cuando los trabajos se procesan en orden de llegada y no hay interactividad.
• Colas de impresión: los documentos se imprimen en el orden en que se enviaron.
• Procesamiento de mensajes: los mensajes se procesan en orden de llegada (FIFO).
• Como política por defecto: cuando no se conoce la duración de los procesos y no hay prioridades.
• Como componente de algoritmos más complejos: FCFS se usa dentro de colas multinivel (tema 24) para las colas de baja prioridad.

En la práctica, ningún sistema operativo moderno usa FCFS puro para la CPU. Incluso los sistemas por lotes usan variantes con prioridades. Pero FCFS sigue siendo el punto de partida para entender todos los demás algoritmos: es la línea base contra la que se comparan.

11. Simulador interactivo

Este simulador genera una carga de trabajo aleatoria y la ejecuta con FCFS. Cambia los parámetros y observa cómo cambian el Gantt y las métricas:

12. Resumen

• FCFS atiende a los procesos en orden de llegada, usando una cola FIFO.
• Es el algoritmo más simple: no necesita conocer ráfagas ni prioridades.
• Es no apropiativo: un proceso que recibe la CPU la conserva hasta terminar o bloquearse.
• No hay inanición: todo proceso que llega se ejecuta eventualmente.
• El tiempo de espera de P_i es la terminación del anterior menos su llegada.
• Si todos llegan en 0, la espera de P_i es la suma de las ráfagas anteriores.
• El efecto convoy: un proceso largo bloquea a los cortos que llegan después.
• FCFS no minimiza ninguna métrica, pero es la línea base para comparar.
• Se usa en sistemas por lotes, colas de impresión y como componente de algoritmos más complejos.

13. Preguntas de repaso

Intenta responder cada una antes de abrir la respuesta.

Para practicar

1. Calcula a mano las métricas para los procesos P1(0,6), P2(2,4), P3(4,2) en FCFS.
2. Repite el ejercicio anterior con llegadas 0, 0, 0 y ráfagas 6, 4, 2. ¿Cambian los promedios?
3. Demuestra que si todos llegan en 0, poner el proceso más largo primero maximiza el tiempo de espera promedio.
4. Modifica el simulador para mostrar el efecto convoy: genera un proceso largo seguido de varios cortos.
5. Compara FCFS con SJF para la misma carga de trabajo usando el simulador del tema 9.
6. Escribe una función que calcule el tiempo de espera promedio de FCFS sin simular, usando la fórmula del tema.