¿Por qué es óptimo programar trabajos más cortos primero en un uniprocesador?

7

En un uniprocesador, es aparentemente óptimo programar trabajos que toman menos tiempo asumiendo primero la programación no preventiva: una vez que se ejecuta un trabajo, debe finalizar. ¿Por qué?

Estoy confundido acerca de cómo el pedido cambiaría la latencia general. Dado que un uniprocesador solo puede asumir un solo proceso a la vez, ¿no sería la latencia igual sin importar el orden?

    
pregunta David Faux 17.01.2012 - 04:51

3 respuestas

2

Aunque este algoritmo fue diseñado para proporcionar el máximo rendimiento en todos los escenarios, esto no es correcto para todas las situaciones. ¿Qué pasa si el procesador tiene muchos procesos pequeños? Definitivamente conducirá a la inanición. El tiempo de respuesta de los procesos pequeños será bajo, mientras que el de los procesos grandes será grande en comparación con otros algoritmos de programación.

Wikipedia dice:

  

Dado que el tiempo de respuesta se basa en el tiempo de espera más el tiempo de procesamiento,   Los procesos más largos se ven significativamente afectados por esto. Espera general   el tiempo es más pequeño que el FIFO, sin embargo, dado que ningún proceso tiene que esperar   La terminación del proceso más largo.

Si programa trabajos más grandes primero, muchos procesos pequeños tendrían que esperar a que finalice el proceso (ya que esto no es preventivo). Y dado que el tiempo de respuesta es el tiempo total entre la presentación de un proceso y su finalización, este sería definitivamente bajo. Pero en SJF, muy pocos procesos grandes esperan algunos procesos pequeños, por lo que el tiempo de respuesta de solo esos procesos grandes se vería afectado.

Echa un vistazo a este enlace para una comparación de varias técnicas.

    
respondido por el c0da 17.01.2012 - 05:05
10

La medida de cuán bueno es el programador sería la espera promedio / total.

Suponga que tiene un conjunto de trabajos J , dentro de estos tiene el trabajo x , que es el más largo. Deje que y sea cualquier otro trabajo.

Si coloca x en último lugar, el tiempo total de espera de los trabajos ejecutados anteriormente será total ( J ) -time ( x ), mientras que para cualquier otro será total ( J ) -time ( y ). Así, solo poniendo el último trabajo más largo minimiza el tiempo de espera. Luego, repite eso para el conjunto de trabajos restantes J- {x}, y así sucesivamente, siempre poniendo el más largo al último. El resultado final es que los ha ordenado de más corto a más largo.

    
respondido por el vartec 17.01.2012 - 12:51
3

Si el trabajo corto (A) se ejecuta antes que el trabajo largo (B), A tiene que esperar solo su propia longitud para completarse, mientras que B tiene que esperar su propia longitud + la longitud de A. Si B va primero, tiene que esperar solo su propia longitud, pero A tiene que esperar toda la longitud de B más la suya propia. En otras palabras, tiene un tiempo de espera total de 2B + A en lugar de 2A + B. Como el denominador es 2 en cualquier caso, la solución anterior es mejor. Eso es todo lo que hay en esa regla.

    
respondido por el Kilian Foth 17.01.2012 - 10:53

Lea otras preguntas en las etiquetas