Algoritmo de programación FCFS: qué es, programa de ejemplo
Natalia Brooks
¿Qué es el método por orden de llegada?
Primero en llegar, primero en servir (FCFS) es un algoritmo de programación del sistema operativo que ejecuta automáticamente las solicitudes y procesos en cola en el orden de llegada. Es el algoritmo de programación de CPU más sencillo y fácil. En este tipo de algoritmo, los procesos que solicitan la CPU primero obtienen la asignación de CPU primero. Esto se gestiona con una cola FIFO. La forma completa de FCFS es "First Come First Serve".
Cuando el proceso ingresa a la cola lista, su PCB (Bloque de control de proceso) se vincula con la cola de la cola y, cuando la CPU queda libre, debe asignarse al proceso al comienzo de la cola.
Características del método FCFS
- Admite algoritmos de programación preventivos y no preventivos.
- Los trabajos siempre se ejecutan por orden de llegada.
- Es fácil de implementar y utilizar.
- Este método tiene un rendimiento deficiente y el tiempo de espera general es bastante alto.
Ejemplo de programación FCFS
Un ejemplo real del método FCFS es comprar una entrada de cine en la taquilla. En este algoritmo de programación, se atiende a una persona según la forma de cola. La persona que llega primero a la cola compra primero el billete y luego el siguiente. Esto continuará hasta que la última persona en la cola compre el boleto. Usando este algoritmo, el proceso de la CPU funciona de manera similar.
¿Cómo funciona FCFS? Calcular el tiempo de espera promedio
A continuación se muestra un ejemplo de cinco procesos que llegan en diferentes momentos. Cada proceso tiene un tiempo de ráfaga diferente.
| Proceso | Tiempo quemado | Hora de llegada |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Utilizando el algoritmo de programación FCFS, estos procesos se manejan de la siguiente manera.
Paso 1) El proceso comienza con P4 que tiene hora de llegada 0
Paso 2) En el momento = 1, llega P3. P4 todavía se está ejecutando. Por lo tanto, P3 se mantiene en cola.
| Proceso | Tiempo quemado | Hora de llegada |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Paso 3) En el tiempo = 2, llega P1 que se mantiene en la cola.
| Proceso | Tiempo quemado | Hora de llegada |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Paso 4) En el momento = 3, el proceso P4 completa su ejecución.
Paso 5) En el momento = 4, P3, que es el primero en la cola, inicia la ejecución.
| Proceso | Tiempo quemado | Hora de llegada |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Paso 6) En el momento = 5, llega P2 y se mantiene en cola.
| Proceso | Tiempo quemado | Hora de llegada |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Paso 7) En el momento 11, P3 completa su ejecución.
Paso 8) En el momento = 11, P1 inicia la ejecución. Tiene un tiempo de ráfaga de 6. Completa la ejecución en el intervalo de tiempo 17.
Paso 9) En el momento = 17, P5 inicia la ejecución. Tiene un tiempo de ráfaga de 4. Completa la ejecución en el tiempo=21.
Paso 10) En el momento = 21, P2 inicia la ejecución. Tiene un tiempo de ráfaga de 2. Completa la ejecución en el intervalo de tiempo 23.
Paso 11) Calculemos el tiempo de espera promedio para el ejemplo anterior.
Waiting time = Start time - Arrival time
P4 = 0-0 = 0
P3 = 3-1 = 2
IP = 11-2 = 9
P5= 17-4 = 13
P2= 21-5= 16
Tiempo medio de espera
= 40 / 5 = 8
Ventajas de FCFS
A continuación, se detallan las ventajas y beneficios de utilizar el algoritmo de programación FCFS:
- La forma más simple de un Algoritmo de programación de CPU
- Fácil de programar
- Primero llegado, primero servido
Desventajas de FCFS
A continuación se detallan las desventajas/desventajas de utilizar el algoritmo de programación FCFS:
- Es un algoritmo de programación de CPU no preventivo, por lo que una vez que el proceso se ha asignado a la CPU, nunca liberará la CPU hasta que termine de ejecutarse.
- El tiempo medio de espera es elevado.
- Los procesos cortos que están al final de la cola tienen que esperar a que finalice el proceso largo al frente.
- No es una técnica ideal para sistemas de tiempo compartido.
- Debido a su simplicidad, FCFS no es muy eficiente.
Resumen
- Definición: FCFS es un algoritmo de programación del sistema operativo que ejecuta automáticamente las solicitudes y procesos en cola según el orden de llegada.
- Admite programación preventiva y no preventiva
- algoritmo.
- FCFS significa "por orden de llegada"
- Un ejemplo real del método FCFS es comprar una entrada de cine en la taquilla.
- Es la forma más simple de algoritmo de programación de CPU.
- Es un algoritmo de programación de CPU no preventivo, por lo que una vez que el proceso se ha asignado a la CPU, nunca liberará la CPU hasta que termine de ejecutarse.
