sistoper: 1er PP 2023, duda de SJF, ayuda

Buenas, me surgió una duda a raíz de la solución del ejercicio 2, parte a.

En el problema se usan a nivel de usuario 3 hilos con el criterio SJF. Inicialmente pensé que el SJF asignaba procesos en función del tiempo de ejecución restante del programa (el programa que fuera a terminar primero era el próximo en asignarse), pero a juzgar por la solución, parece ser que el SJF únicamente se fija en el tiempo de ejecución del próximo CPU burst, no del tiempo total de ejecución.

Me fijé en las diapositivas del curso, y parece ser que sí, solamente ordena por CPU burst, no por todo el tiempo de ejecución restante del programa (aunque por cierto, los ejemplos son un poco engañosos porque solamente se muestran procesos con una única instrucción de ejecución, por lo que el tiempo del próximo CPU burst es el mismo que el tiempo total de ejecución, dejando sin resolver la ambigüedad que planteé).

El punto es que, mientras estaba intentando entender cómo funciona el SJF desde esta confusión, me surgió una duda que no me supe responder. Partiendo de la base de que el SJF expropiativo y el SJF no expropiativo solamente diferen en una cosa, y es que el expropiativo es capaz de indicar al Scheduler que reasigne la CPU a un nuevo proceso si detecta que terminará de ejecutar antes, mientras que el no expropiativo una vez que asignó el procesador a un proceso debe esperar a que el proceso termine para poder asignar el recurso procesador a otro proceso, imaginemos que tenemos los siguientes procesos en un sistema multiprogramado monoprocesador con un SJF no expropiativo a nivel Kernel:

(en el ejemplo, asumir que ambos procesos llegan a la vez, en t=0)

Si el SJF se fijara en el tiempo total de ejecución, entonces vería que el proceso 1 tiene un tiempo de ejecución de 1001 ms, mientras que el Proceso 2 tiene un tiempo de ejecución de 3 ms, y le asignaría primero el procesador al proceso 2, y después de que el proceso ya haya terminado, le asignaría el procesador al proceso 1.

Pero, según lo que entendí, el SJF se fija solamente en el tiempo del próximo CPU burst, entonces, siguiendo el ejemplo, vería que el próximo CPU burst demora 1 ms para el Proceso 1, y 2ms para el proceso 2, entonces le asignaría el procesador al Proceso 1, porque es el que tiene el próximo CPU burst más corto. Pero entonces, se procesaría primero el Proceso 1 (de 1001 ms), y después el Proceso 2 (de 3 ms). Esto hace que el tiempo de espera sea subóptimo, porque el Proceso 2 estuvo 1001 ms en la Ready Queue ... y se supone que el SJF es óptimo en tiempo de espera (notar que el una vez asignado el Proceso 1, no puede asignarse el 2 hasta que el 1 termine porque en el ejemplo el SJF es no expropiativo).

Gracias por leer mi duda, tal vez hay algún concepto que estoy entendiendo mal, en cuyo caso agradezco correcciones.

Re: 1er PP 2023, duda de SJF, ayuda

de Joaquín Sande González - domingo, 24 de marzo de 2024, 23:15

Buenas, era para comunicar que hablando con otros estudiantes y repensando algunas cosas descubrí algunos errores conceptuales en mi razonamiento. Igualmente voy a dejar el mensaje en el foro por si algún otro estudiante tenía las mismas dudas que yo. Mis errores fueron:

1) El CPU burst no se calcula como el tiempo de ejecución de la siguiente instrucción del proceso sino como el tiempo de ejecución de la siguiente ráfaga de ejecución (esto es, todas instrucciones del proceso que consuman CPU seguidas. En otras palabras, todas las instrucciones del tipo "Ejecutar X ms" antes de llegar al final del proceso, o a un bloqueo).

2) Cuando un proceso se bloquea, aunque la invocación al scheduler no sea expropiativa, se puede reasignar el recurso procesador a otro proceso distinto. No hace falta que sea expropiativo para hacer eso porque al bloquearse, el proceso libera voluntariamente la CPU.

3) El SJF solamente es óptimo en tiempo de espera cuando es expropiativo, o cuando todos los procesos llegan a la vez después de cada CPU burst. En el ejemplo que di en mi mensaje original;

image%20%281%29.png

Los CPU burst se calcularían contando el tiempo de ejecución de cada ráfaga (1001 ms para el proceso 1, y 3 ms para el proceso 2). Pero si altero el ejemplo original de la siguiente manera;

En ese caso, si entendí bien los nuevos conceptos lo que pasaría sería algo así;

Y el Proceso 2 estaría en la Ready Queue durante 1000 ms, por lo que sería subóptimo en tiempo de espera. Esto sucede porque si bien la primera ráfaga de ejecución de ambos procesos llega a la vez, la segunda ráfaga de ejecución del proceso 1 llega antes que la del proceso 2, entonces el SJF no expropiativo no resulta óptimo. Si fuese expropiativo sería óptimo porque el t = 9 se le expropiaría el procesador al primer proceso, al que le quedan 998 milisegundos de ejecución, y se lo daría al segundo proceso, al que le queda 1ms de ejecución.