Universidad Central de Venezuela Facultad de Ciencias Escuela de Computacin Sistemas Operativos (6004)
Prctica #5
Planificacin (CPU) Objetivos:
Estudiar la planificacin del procesador a fin de comprender su importancia en el soporte de los sistemas operativos multiprogramados. Analizar los distintos algoritmos de planificacin a corto plazo del procesador. Establecer comparaciones entre estos algoritmos que permitan determinar cul es el ms apropiado en un problema de planificacin especfico.
Conocimientos necesarios para desarrollar la prctica:
Concepto de planificacin de procesos: Planificacin a corto plazo. Planificacin a mediano plazo. Planificacin a largo plazo. Medidas de rendimiento en sistemas operativos: Tiempo de retorno. Tiempo de finalizacin. Tiempo de espera. Tiempo de retorno normalizado. Tiempo de servicio. Tipos de planificacin a corto plazo: Apropiativa. No apropiativa. Algoritmos de planificacin a corto plazo: FIFO (First In First Out). SJF (Shortest Job First). RR (Round Robin). SRT (Shortest Remaining Time). Planificacin por prioridades. Planificacin de lotera. Diagramas de Gantt. Esto corresponde con el captulo 5 del libro de Silberschartz (Operating Systems Concepts); captulo 2.4 y 8.1 del libro de Tanenbaum (Modern Operating Systems); y los captulos 9 y 10 del libro de Stallings (Operating Systems: Internals and Design Principles). Para ms informacin consulten el cronograma general de la materia.
Preguntas:
1. Qu es cierto respecto al dispatcher? Explique brevemente. a. Se ejecuta con relativa poca frecuencia. b. Se ejecuta cuando ocurre una interrupcin de reloj.
Semestre I-2012
Universidad Central de Venezuela Facultad de Ciencias Escuela de Computacin Sistemas Operativos (6004)
Prctica #5
c. Su funcin es la misma a la del mdulo activador. d. Tambin es conocido como planificador a medio plazo. e. Ninguna de las anteriores. 2. En un sistema operativo con planificacin por prioridad circular, sea E el tiempo medio de ejecucin de un proceso antes de solicitar una peticin de entrada/salida (E/S) y C es el tiempo invertido en la conmutacin entre procesos, donde E >> C. Analizar el efecto que sobre los procesos y el rendimiento del sistema tienen cada una de las situaciones siguientes, en las que vara el valor del cuanto Q: a. Cuanto arbitrariamente grande. b. Cuanto muy pequeo, ligeramente superior a cero. c. Cuanto muy cercano a E, tal que C< Q< E. d. Cuanto igual a C. 3. La lista de los estados suspendidos no est organizada por prioridades. Exponer algunas razones de por qu no se utiliza la prioridad e indicar bajo qu circunstancias podra resultar til su empleo. 4. Dar una ecuacin que relacione los siguientes periodos de tiempo de trabajo: tiempo de retorno, tiempo de ocupacin del procesador y tiempo de espera. 5. Expresar con frmulas los conceptos de eficiencia y el rendimiento. 6. Considrese un sistema multiproceso con un nivel de multiprogramacin igual a 5 en el que se ejecutan concurrentemente 3 procesos, cuyas trazas de ejecucin tericas en un sistema monoproceso son las siguientes:
a. Proceso A: E/S CPU
Tiempo 0
E/S CPU
9 10 11 12 13 14 15 16 17 18 19
b. Proceso B:
Tiempo 0
9 10 11 12 13 14 15 16 17 18 19
c. Proceso C: E/S CPU
Tiempo 0
9 10 11 12 13 14 15 16 17 18 19
Semestre I-2012
Universidad Central de Venezuela Facultad de Ciencias Escuela de Computacin Sistemas Operativos (6004)
Prctica #5
El planificador del sistema operativo asigna el procesador segn el algoritmo de planificacin Round Robin. Adems, en caso de que varios procesos necesiten ponerse a la vez en la cola de procesos listos, el orden de prioridad de mayor a menor segn el estado de procedencia es: proceso nuevo, proceso en ejecucin y proceso bloqueado. El sistema permite que haya varios procesos bloqueados a la vez. Se pide: i. Representar las trazas de ejecucin de los 3 procesos para cuantos de tiempo de 3, 4 y 5 unidades, determinando la opcin menos ptima. ii. En qu instante de tiempo terminara de ejecutarse el proceso B si el sistema fuera monoproceso. iii. En qu instante de tiempo terminara de ejecutarse el proceso B si el sistema fuera multiprocesador con 3 procesadores.
7. Considrese un sistema con un nico procesador que necesita ejecutar concurrentemente una serie de procesos, cuyos instantes de llegada y tiempos que tardan en ejecutarse se representan en la siguiente tabla: PROCESO A B C D E Instante de llegada 0 1 5 9 16 Tiempo de proceso 3 5 6 4 2
Se pretende seleccionar un algoritmo de planificacin para el sistema operativo que sea ptimo, para lo cual es necesario obtener una serie de trazas de ejecucin de dichos procesos, segn diferentes algoritmos. Se pide: a. Mostrar los resultados que se obtendrn utilizando los siguientes algoritmos de planificacin: i. FIFO. ii. Round Robin con cuanto=2. iii. Round Robin con cuanto=3. iv. SPN. v. SRT. Muestre los tiempos de finalizacin, tiempos de retorno y tasas de penalizacin, as como un promedio de todos stos valores. b. Justificar, en funcin de los resultados anteriores, qu algoritmo de planificacin debe utilizar el sistema operativo si se desea el ms ptimo. 8. Cul de las siguientes transiciones entre los estados de un proceso no se puede producir en un sistema con un algoritmo de planificacin no apropiativo? a. Bloqueado a Listo. b. Ejecutando a Listo.
Semestre I-2012
Universidad Central de Venezuela Facultad de Ciencias Escuela de Computacin Sistemas Operativos (6004)
Prctica #5
c. Ejecutando a Bloqueado. d. Listo a Ejecutando. 9. Cuntos planificadores podramos encontrar en un Sistema Operativo Multi-hilo? a. Dos, si los hilos se implementan a nivel de usuario. b. Dos, si los hilos se implementan a nivel de kernel. c. Uno, si los hilos se implementan a nivel de usuario. Un planificador por cada usuario que est utilizando la biblioteca de hilos en el espacio de usuario. 10. Supngase 5 procesos P1, P2, P3, P4 y P5 cuyos tiempos de ejecucin requeridos son 2, 4, 1, 1 y 1 respectivamente. Adems su llegada se produce en los instantes 0, 0, 3, 3, 3 respectivamente (cuando el planificador puede elegir entre dos procesos en igualdad de circunstancias elegir el de menor identificador). Es cierto que si se utiliza el algoritmo de planificacin El ms corto el primero, el tiempo medio de retorno obtenido es: a. Menor que el obtenido si se utilizase Primero en llegar primero en servir. b. Mayor que el obtenido si se utilizase Primero en llegar primero en servir. c. Igual que el obtenido si se utilizase Primero en llegar primero en servir. 11. Qu ventaja tiene el uso de diferentes tamaos de cuanto de tiempo en diferentes niveles en un sistema que trabaja con colas multinivel? Razone su respuesta. a. En un sistema con planificacin por Round-Robin donde se estn ejecutando 4 procesos durante 10 segundos, es cierto que: b. Cada proceso se ejecutar durante 2,5 segundos. c. En cualquier circunstancia, cada proceso recibir siempre el mismo nmero de rodajas de tiempo. d. Con rodajas de 10 milisegundos, los procesos se aprovecharn de ms tiempo de CPU que si las rodajas son de 100 milisegundos. e. Ninguna de las anteriores. 12. En un sistema con planificacin por Round-Robin donde se estn ejecutando 4 procesos durante 10 segundos, es cierto que: a. Cada proceso se ejecutar durante 2,5 segundos. b. En cualquier circunstancia, cada proceso recibir siempre el mismo nmero de rodajas de tiempo. c. Con rodajas de 10 milisegundos, los procesos se aprovecharn de ms tiempo de CPU que si las rodajas son de 100 milisegundos. d. Ninguna de las anteriores. GDSO
Semestre I-2012
