sábado, septiembre 09, 2006
Tarea #2
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 proceso
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:\Como la conmutación se realiza después de cada
instrucción el tiempo entonces si hay n procesos si las instrucciones del
proceso que toma un tiempo T fuera menor que el de los otros n procesos
entonces el tiempo serian T*n pero como no se sabe cuantas instrucciones tienen
los n procesos el calculo se realizaría mientras estuvieran esos n procesos, si
el n cambia entonces se realizaría un nuevo calculo con el nuevo n por lo tanto
la formula seria
Tiempo(T) = T*n
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 un proceso aparece dos veces en la lista de
planificación utilizando Round Robin entonces este estaría utilizando dos
quantum, un quantum más que los demás procesos y este terminaría al la mitad
del tiempo normal.
La razón para permitir esto es si quisiéramos implementar
prioridades de algún proceso entonces un aumento de prioridad consistiría en
aumentar una aparición más del proceso en la lista, por ejemplo si quisiéramos
que el proceso X tuviera una prioridad 2(es mayor) entonces este proceso
estaría 2 veces en la lista y si quisiéramos que fuera de prioridad 3 el
proceso x estaría 3 veces en la lista lo que aria que se ejecutara 1/3 mas
rápido que los demás procesos porque obtendría 3 quantum por ciclo.
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 = ∞
R:\Como cada Proceso toma a lo más un quantum y este es ∞
el proceso se realiza en T por lo que
T = sumatoria de (Ti*Si) desde i = 1 a n
La eficiencia sería
E = T/n
b) Q > T
R:\Como cada Proceso toma a lo más un quantum y este es >
T el proceso se realiza en T por lo que la formula es igual al anterior
T = sumatoria de (Ti*Si) desde i = 1 a n
La eficiencia sería
E = T/n
c) S < Q < T
R:\Como cada Proceso toma a lo más un quantum y este es <
T el proceso se realiza en
C = sumatoria de (Qi*Si) desde i = 1 a n donde C es el
tiempo por ciclo
E = (C*c)/n donde c es el número de ciclos y n el número de
procesos
d) Q = S
R:\Como cada Proceso toma a lo más un quantum y no sabemos
cuantos quantum toma por proceso la formula sería
C = sumatoria de (Qi) desde i = 1 a n donde C es el tiempo
por ciclo
La eficiencia sería
E = (2*C*c)/n donde c es el número de ciclos y n el número
de procesos
e) Q casi 0
R:\Como cada Proceso toma a lo más un quantum y no sabemos
cuantos quantum toma por proceso la formula sería
C = sumatoria de (Qi) desde i = 1 a n donde C es el tiempo
por ciclo
La eficiencia sería
E = (2*C*c)/n donde c es el número de ciclos y n el número
de procesos
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:\Se debe de ordenar de menor a mayor
Por lo que los tiempos conocidos ordenados son
3,5,6,9
Si X < 3 entonces seria
X,3,5,6,9
Si 3 < X < 5 entonces seria
3,X,5,6,9
Si 6 < X < 9 entonces seria
3,5,6,X,9
Si X > 9 entonces seria
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.
R:\
Proceso
Tiempo
Prioridad
P1
10
3
P2
6
5
P3
2
2
P4
4
1
P5
8
4
a) Round Robin.
R:\ Con q = 2.
((0+2+4+6+8) +(10+12+14)+(16)+(18+20)+(22+24+26+28)) / 5 = 42
b) Planificación por prioridad.
R:\ (0+6+14+24+26)/5 = 14
c) Primero que llega, primero que se atiende (ejecutados en el orden 10, 6, 2,
4, 8).
R:\ (0+10+16+18+22)/5 = 13.2
d) El primer trabajo más corto.
R:\ (0+2+6+12+20)/5 = 8
