OSDI Capitulo 2, Problemas del 19 al 23

19. Las computadoras CDC 6600 podían manejar hasta 10 procesos de E/S simultáneamente usando una forma interesante de planificación round robin llamada compartición de procesador. Ocurría una conmutación de proceso después de cada instrucción, de modo que la instrucción 1 provenía del proce­so 2, la instrucción 2 provenía del proceso 2, etc. La conmutación de procesos se efectuaba mediante un hardware especial, y el gasto extra era cero. Si un proceso necesitaba T segundos para llegar a su fin en la ausencia de competidores, ¿cuánto tiempo necesitaría si se usara compartición de procesador con n procesos?

R// El tiempo total que tardaría el proceso seria igual al tiempo que se tardaría dicho proceso (o la sumatoria de sus cuantums) mas la suma de los cuantums de los n procesos demás que han sido ejecutados hasta el momento de la finalización de dicho proceso. Ósea:

T(total) = Ti + ∑Qj

donde la sumatoria de Qj va desde j = 1 hasta n, con j ≠ i, me indica el numero de cuantums de los procesos distintos de i que se han ejecutado.

20. Los planificadores round robin normalmente mantienen una lista de todos los procesos ejecutables, y cada proceso aparece una y sólo una vez en la lista. ¿Qué sucedería si un proceso ocurriera dos veces en la lista? ¿Puede usted pensar en alguna razón para permitir esto?

R// Si el proceso aparece dos veces en la lista ocuparía un mayor tiempo de CPU, lo que contribuiría a que este terminará su trabajo de manera mas rápida. Esto no ocurriría normalmente, como se menciona en el enunciado del ejercicio, pero si ocurre depende la implementación de planificación de procesos que se que se haya escogido.

21. Mediciones realizadas en cierto sistema indican que, en promedio, un proceso se ejecuta durante un tiempo T antes de bloquearse en espera de E/S. Una conmutación de procesos requiere un tiempo S, que efectivamente se desperdicia (gasto extra). Para planificación round robin con cuanto Q, deduzca una fórmula para la eficiencia de la CPU en cada uno de los siguientes casos:

(a) Q =­ ∞

(b) Q > T

(c) S <>

(d) Q = S

(e) Q casi 0

22. Cinco trabajos están esperando para ejecutarse. Sus tiempos de ejecución esperados son 9, 6, 3, 5 y X. ¿En qué orden deben ejecutarse si se desea minimizar el tiempo medio de respuesta? (Su respuesta dependerá de X.)

R// Deben ejecutarse, dependiendo el valor de X, según el trabajo más corto de las siguientes formas:

1) X<3

X, 3, 5, 6, 9

2) 3<5

3, X, 5, 6, 9

3) 5<6

3, 5, X, 6, 9

4) 6<9

3, 5, 6, X, 9

5) X>9

3, 5, 6, 9, X

23. Cinco trabajos por lotes, A a E, llegan a un centro de cómputo casi al mismo tiempo, y tienen tiempos de ejecución estimados de 10, 6, 2, 4 y 8 minutos. Sus prioridades (determinadas externamente) son 3, 5, 2, 1 y 4, respectivamente, siendo 5 la prioridad más alta. Para cada uno de los siguientes algoritmos de planificación, determine el tiempo de retorno medio de los procesos. Ignore el gasto extra por conmutación de procesos.

(a) Round robin.

(b) Planificación por prioridad.

(c) Primero que llega, primero que se atiende (ejecutados en el orden 10, 6, 2, 4, 8).

(d) El primer trabajo más corto.

Para (a), suponga que el sistema está multiprogramado, y que cada trabajo recibe una parte equitativa del tiempo de CPU. Para (b) a (d), suponga que sólo se ejecuta un trabajo a la vez, hasta terminar. Todos los trabajos están limitados únicamente por CPU.

Desarrollo:

a) Con cuantum 2:

((2+4+6+8) +(10+12+14)+(16)+(18+20)+(22+24+26+28)) / 5 = 42

b) (5*6+4*8+3*10+2*2+1*4)/5 = 20

c) (5*10+4*6+3*2+2*4+1*8)/5 = 19.20

d) (5*2+4*4+3*6+2*8+1*10)/5 = 14