PLANIFICACIÓN 'FCFS'

DEFINICIÓN

El algoritmo de planificación de la CPU (Central Processing Unit) más sencillo es el de servicio por orden de llegada (FCFS, First Come, First Served), también llamado Primero en Llegar, Primero en Salir.

DEFINIICIÓN

Este algoritmo de planificación es en realidad una secuencia de procesos basados en una cola simple (FIFO) sin discriminación en espera de ser ejecutados.

¿QUÉ ES FIFO?

También llamada primero en entrar/primero en salir (FIFO, First-in, First-out).

FUNCIONAMIENTO

● Con este esquema, el proceso que primero solicita la CPU la recibe primero.

● La implementación de la política FCFS es fácil con una cola FIFO.

FUNCIONAMIENTO

● Cuando un proceso ingresa en la cola de procesos listos, su PCB se enlaza al final de la cola.

● Cuando la CPU queda libre, se asigna al proceso que está a la cabeza de la cola. Acto seguido, el proceso en ejecución se saca de la cola.

Sin embargo...

El tiempo de espera promedio cuando se adopta la política FCFS suele ser muy largo.

Consideremos el siguiente conjunto de procesos que llegan en el tiempo 0 (la duración de la ráfaga de CPU se da en milisegundos):

PROCESO TIEMPO DE RÁFAGA

P1

P2

P3

24

3

3

Si los procesos llegan en el orden P1, P2, P3, y se atienden en orden FCFS, obtenemos el resultado que se muestra en el siguiente diagrama de Gantt:

El tiempo de espera es de 0 milisegundos para el proceso P1, 24 milisegundos para el proceso P2, y 27 milisegundos para el proceso P3.

Entonces, el tiempo de espera promedio es (0+24+27)/3=17 milisegundos.

En cambio, si los procesos llegan en el orden P2, P3, P1, los resultados son los que se muestran en este diagrama de Gantt:

El tiempo de espera promedio ahora es (6+0+3)/3=3 milisegundos.

Esta reducción es sustancial. Así, el tiempo de espera promedio cuando se instituye una política FCFS casi nunca es mínimo, y podría variar sustancialmente si los tiempos de ráfaga de CPU del proceso varían mucho.

Consideremos también el desempeño de la planificación FCFS en una situación dinámica.

Supongamos que tenemos un proceso limitado por CPU y muchos procesos limitados por E/S.

A medida que los procesos circulan por el sistema, podría presentarse la siguiente situación:

● El proceso limitado por CPU recibe la CPU y la conserva.

● Durante este tiempo, todos los demás procesos terminan su E/S e ingresan en la cola de procesos listos para esperar la CPU.

● Mientras los procesos esperan en esa cola, los dispositivos de E/S estarán de ociosos.

● Finalmente, el proceso limitado por CPU terminará su ráfaga de CPU y requerirá un dispositivo.

● Todos los procesos limitados por E/S que tienen ráfagas de CPU muy cortas, se ejecutarán rápidamente y pasarán otra vez a las colas de E/S.

● En este momento, la CPU estará ociosa. A continuación el proceso limitado por CPU volverá a la cola de procesos listos y se le asignará la CPU.

● Una vez más, todos los procesos limitados por E/S acabarán en la cola de procesos listos, esperando que termine el proceso limitado por CPU.

● Se presentará un efecto convoy, ya que todos los demás procesos esperarán que un solo proceso grande desocupe la CPU.

¿Y luego?

● Este efecto tiene como resultado un aprovechamiento de la CPU y de los dispositivos, menor que el que se lograría si se cediera el paso a los procesos más cortos.

VENTAJAS

● La principal ventaja de FCFS es que es fácil de entender y escribir y no hay inanición es decir, cada ráfaga de CPU consigue ser servida, si se espera el tiempo suficiente.

VENTAJAS

● No hay discriminación de procesos.

● Su implementación es fácil y solo requiere de una cola FIFO.

DESVENTAJAS

● Si un proceso entra en un bucle infinito, se ejecutará siempre, excluidos todos los demás. Incluso si asumimos que los procesos no tienen bucles infinitos debemos tomar precauciones especiales para capturar tales procesos, FCFS tiende a favorecer excesivamente largas ráfagas.

DESVENTAJAS

● Un proceso puede monopolizar la CPU, así que el tiempo medio de espera es muy larga.

● Tasa de productividad baja.

DESVENTAJAS

● Tiempos de espera muy largos en relación con procesos largos con afectación a los procesos cortos.

● Tiempos de retorno demasiado variables.

DESVENTAJAS

● Tiende a favoreces a los procesos con carga de CPU frente a los que tienen carga de E/S.

● Uso de procesador ineficiente.

EJERCICIOS

PROBLEMA

● Supóngase que se tienen que realizar cinco trabajos cuyas características se muestran en la Tabla.

SOLUCION

a) El algoritmo FCFS (primero en llegar, primero en ser servido) (First-Come-First-Served) corresponde a la disciplina de planificación en la que los procesos en estado preparado acceden al procesador en el orden en que llegan a dicho estado, sin expropiaciones.

● La implementación del planificador FCFS es bastante directa, y su ejecución da lugar a pocos recargos. Los procesos largos hacen esperar a los cortos. El diagrama de Gantt queda:

●

b) El tiempo de retorno corresponde al tiempo transcurrido desde el lanzamiento de un proceso hasta su finalización. La tabla 2 muestra el tiempo de retorno de cada proceso para el algoritmo FCFS, como se puede observar en el diagrama de Gantt anterior.

d) El tiempo de espera corresponde al tiempo que un proceso consume esperando la asignación de recursos debido a ala competencia con otros en un sistema con multiprogramación.

Matemáticamente se puede expresar como el tiempo de retorno menos el tiempo de ejecución. En la tabla 4 se recogen los cálculos realizados.

e) El tiempo de respuesta a un evento corresponde al intervalo de tiempo que transcurre desde que se señala un evento hasta que se ejecuta la primera instrucción de la rutina de servicio de dicho evento.

En definitiva es el tiempo que esta esperando en el estado de preparado o loqueado para empezar a ejecutarse. Así, a partir de estos resultados se puede calcular el tiempo de respuesta como queda recogido en la Tabla 5.

● f) Del análisis de las tablas anteriores se puede concluir que los mejores resultados se obtendrán con otro algoritmo de planificación que no sea FCFS.

¿PREGUNTAS Y/O COMENTARIOS?