Sistemas operativos modernos

minutos; el de fi, 12 minutos; el de C, 16 minutos, y el de D, 20 minutos, para un promedio de 14 minutos. 6 4 4 4 4 4 4 8 A B C D B C D A (a) (b) Figura 2-39. Ejemplo de calendarización tipo trabajo más corto primero, a) Ejecu­ ción de cuatro trabajos en el orden original, b) Ejecución en orden de trabajo más corto primero. Ahora consideremos la ejecución de estos cuatro trabajos bajo la política del trabajo más corto primero, como se muestra en la figura 2-39b. Ahora los tiempos de retorno son 4, 8 , 12 y 20 minutos, para un promedio de 11 minutos. Puede demostrarse que esta política es ópüma. Consideremos el caso de cuatro trabajos, con tiempos de ejecución a , b , c y d, respectivamen­ te. El primer trabajo termina en un tiempo a, el segundo, en un tiempo a + b, etc. El tiempo de retomo medio es (4a + 3/? + 2c + d)!A. Es evidente que a contribuye más al promedio que los demás tiempos, así que debería ser el trabajo más corto, seguido de b, luego c y al último d co­ mo trabajo más largo, que sólo afecta su propio tiempo de retomo. Ei mismo argumento es vá­ lido para cualquier cantidad de trabajos. Vale la pena señalar que la estrategia de trabajo más corto primero sólo es óptima si todos los trabajos están disponibles en forma simultánea. Como contraejemplo, consideremos cinco trabajos, -4 a £ , con fiempos de ejecución de 2,4, l, 1 y l, respectivamente. Sus tiempos de lle­ gada son O, O, 3, 3 y 3. Al principio sólo es posible escoger entre A y B, porque los otros tres trabajos todavía no han llegado. Ejecutando primero el trabajo más corto, el orden será A, B, C, D, E, para una espera promedio de 4.6. En cambio, si se les ejecuta en el orden B, C, D, E, A, la espera promedio será de 4.4. Tiempo restante más corto a continuación Una versión expropiativa de la estrategia anterior es la de tiempo restante más corto a conti­ nuación. En este algoritmo, el calendarizador siempre escoge el proceso con base en el tiem­ po que falla para que termine de ejecutarse. En este caso también es preciso conocer con antelación los tiempos de ejecución. Cuando llega un trabajo nuevo, su tiempo total se compa­ ra con el tiempo que resta para que el proceso actual termine de ejecutarse. Si es menor, el pro­ ceso actual se suspende y se pone en marcha el trabajo recién llegado. Este esquema permite que trabajos cortos nuevos obtengan buen servicio. Calendarización de tres niveles Desde cierto punto de vista, los sistemas por lotes permiten calendarizar en tres niveles, como se ilustra en la figura 2-40. A medida que llegan trabajos al sistema, se les coloca en una cola de en