EJERCICIO Algoritmos de planificacion

[pic 1][pic 2][pic 3]

EJERCICIOS GESTIÓN DE PROCESOS

1. Sea la siguiente carga de procesos: (2,5ptos)

Realiza el diagrama de ejecución de procesos para los siguientes algoritmos:

1. FCFS
2. SJF
3. SRT
4. RR quantum=2

Calcula además, para cada uno de los algoritmos tiempo medio de espera y tiempo medio de retorno.

• Según el tiempo medio de espera, cual es el algoritmo más eficiente?
• Con qué algoritmo es menor el tiempo de retorno?

En la tabla anterior aparecen identificados los procesos, el instante de llegada al sistema y la carga de cpu correspondiente para cada uno de ellos.

Tiempo total de ejecución de procesos: 6 + 3 + 4 + 5 + 3 = 21 ut (unidades temporales)

Es importante recordar que nos encontramos en un entorno Monoprocesador.

1. FCFS (First Come, First Served)  

Se trata de un algoritmo No Apropiativo. Esto implica que, una vez se asigna un proceso al procesador, este lleva a cabo todas sus instrucciones hasta su finalización. Para la representación gráfica de los procesos, emplearemos una tabla como la que sigue. En el eje Y, colocamos los procesos y el eje X representa los ciclos de cpu (tiempo de ejecución).

Para calcular el tiempo medio de ejecución, sumamos todos los ciclos de cpu que consuman los procesos y dividimos por el número de procesos:

(6 + 3 + 4 + 5 + 3)/5=21/5=4,2u.t

El tiempo de respuesta, es el número de ciclos de cpu que el proceso está esperando en la lista de procesos en estado listo, hasta que puede recibir la cpu por primera vez. (Aparece marcado con color gris en la gráfica anterior).

Proceso A: no espera, ya que, llega en el instante 0 y ya recibe la cpu.

Proceso B: espera 4 ut hasta que le conceden la cpu.

Proceso C: espera 6 ut.

Proceso D: espera 8 ut.

Proceso E: espera 12 ut

Tiempo medio de respuesta = ( 0 + 4 + 6 + 8 + 12 ) / 5= 6 ut

El tiempo de espera, es el número de ciclos de cpu que el proceso espera en total. En el caso del algoritmo FCFS (o FIFO), este tiempo de espera coincide con el tiempo de respuesta, ya que el proceso no se detiene una vez se le asigna el procesador.

Tiempo medio espera = 6ut.

El tiempo de retorno es el número de ciclos que transcurren desde que el proceso llega al sistema hasta que finaliza su ejecución. Mide el tiempo total de permanencia del proceso en el sistema (incluye tiempos de ejecución y tiempos de espera).

Proceso A: 6 ut

Proceso B: 7 ut.

Proceso C:  10 ut

Proceso D: 13 ut.

Proceso E: 15 ut

Tiempo medio retorno = ( 6 + 7 + 10 + 13 + 15 ) / 5= 10,2 ut

1. SJF (Shortest Job First)

Este algoritmo asigna el proceso que tenga un menor tiempo de cpu al procesador. Al igual que en el caso anterior (FCFS) se trata de un algoritmo no apropiativo. Esto quiere decir que una vez que el proceso ha tomado el procesador, no puede retirársele hasta que éste haya finalizado. La representación de la carga de procesos sería la siguiente:

Aparecen marcados en color gris los tiempos (ciclos) que los procesos pasan esperando en la lista de procesos en estado listo.

Para realizar la gráfica hay que tener en cuenta los instantes de llegada y los tiempos de cpu de cada uno de los procesos. Observamos que C, al tener menos tiempo de CPU, se ejecutará antes que B (aunque este haya llegado antes). En el caso de los procesos D y E, ocurre exactamente lo mismo. E recibe la cpu antes al ser un proceso más corto.

Tiempo medio de ejecución, es la suma todos los tiempos de ejecución de los procesos divididos por el número de procesos:

(6 + 3 + 4 + 5 + 3)/5=21/5=4,2u.t

Tiempo medio de respuesta

Proceso A: no espera, ya que, llega en el instante 0 y ya recibe la cpu. Recordemos que es un algoritmo no apropiativo, y una vez concedida la cpu a un proceso no se le puede retirar. Mientras A está en el procesador, otros procesos van llegando al sistema y se añaden a la lista de procesos en estado listo o preparado, donde estarán hasta que se les conceda la cpu.

Proceso B: espera 4 ut hasta que le conceden la cpu.

Proceso C: 9 ut

Proceso D: 11 ut.

Proceso E: espera 3 ut. El proceso E se ejecutará antes que el proceso D porque su tiempo de cpu son 3 ut

Tiempo medio de respuesta = ( 0 + 4 + 9 + 11 + 3 )/5 = 5,4 u.t.

Tiempo medio de espera

Coincide con el tiempo medio de respuesta.

Tiempo medio de retorno

Proceso A:  6 ut

Proceso B: 7 ut.

Proceso C: 13 ut

Proceso D: 16 ut.

Proceso E: 6 ut

Tiempo medio de retorno = (6 + 7 + 13 + 16 + 6 ) / 5= 9,6 ut

1. SRT (Shortest Remaining Time)

El algoritmo SRT asigna el procesador a aquel trabajo que le quede menos tiempo de ejecución para ser completado. Se trata de un algoritmo apropiativo. Veamos la gráfica para nuestra carga de procesos:

...