Ejercicios Políticas - Resueltos [PDF]

Zitiervorschau

Sistemas Operativos

Ejercicios planificadores 1. Cinco procesos llegan a un computador casi al mismo tiempo. Sus datos de tiempo de CPU y prioridad aparecen en la tabla anexa. Para cada uno de los siguientes algoritmos de planificación, determine el tiempo medio de retorno y el tiempo medio de espera de los procesos. (Ignorar el tiempo de conmutación entre procesos). Los diagramas de Gantt (diagramas de ejecución) le ayudarán a resolver el problema. a) Prioridad estricta b) FCFS (First Come, First Served) c) SJF (Shortest Job First) d) Round Robin con q = 1 Priorida Proceso T. CPU d A

10

2

B

6

0 (superior)

C

2

3

D

4

4 (inferior)

E

8

1

2. Considere n procesos que comparten la CPU en modo Round Robin. Suponiendo que cada conmutación de proceso tarda s segundos y que la CPU garantiza que cada proceso obtendrá su turno al menos cada t segundos, ¿cuál es el valor del cuanto q? (el valor será una función de las otras variables, no un valor numérico).

3. Considere la siguiente variación del algoritmo “Round Robin”: un proceso que ha consumido su cuanto de tiempo es devuelto al final de la cola de listos, un proceso que ha utilizado la mitad de su cuanto pasa a mitad de la cola, y otro que ha usado la cuarta parte se coloca en un lugar a una cuarta parte de distancia del principio de la cola. (a) ¿Cuál es el objetivo de esta política de planificación? (b) Analice las ventajas y desventajas de su implementación. SOI

1

Sistemas Operativos

4. Tenemos dos computadores: Venus y Júpiter: Venus se usa para predicción meteorológica. Los meteorólogos ejecutan en Venus sus procesos de cálculo meteorológico. Dichos procesos leen un fichero con una imagen del satélite Meteosat, efectúan cálculos durante 5 horas, y generan otro fichero con el mapa del tiempo. Júpiter se usa como servidor de 50 terminales en un palacio de congresos. Cada uno de los 50 terminales conectados a Júpiter se usa para navegar por el web y los 50 navegadores de web se ejecutan en Júpiter 24 horas al día, 7 días a la semana. Los navegadores web, cada vez que un usuario hace clic en un enlace, se conectan a un servidor de web, leen una página web, y la muestran. Conteste razonadamente: a) ¿Qué algoritmo de planificación CP será más adecuado para Venus: RR, o FCFS? ¿Y para Júpiter? b) Si le obligan a usar RR en ambos sistemas, ¿qué cuanto de procesador emplearía para Venus? ¿5ms ó 5s? ¿Y para Júpiter? 5. Se tiene un sistema operativo con tres procesos críticos (tienen que terminar antes de que se cumpla un tiempo máximo llamado plazo final). Dados los tiempos de plazo final y de ejecución total que se indican en la tabla: a) Planifique el orden de ejecución de los procesos, teniendo en cuenta que el sistema favorece a los procesos más críticos. b) Calcule el tiempo de retorno de cada proceso según la planificación a) y después compáralo con el tiempo de retorno que se obtendría si se aplicase la planificación Round Robin. Proceso

T. ejecución

Plazo final

Proc_1

85ms

210ms

t de cambio de contexto = 0.5ms

Proc_2

45ms.

100ms

Cuanto = 25ms

Proc_3

118ms

270ms

6. Kleinrock ha descrito una estrategia de planificación con prioridad y expropiación basada en prioridades modificadas dinámicamente. Se conoce como SRR (Selfish Round Robin, Round Robin egoísta). Cuanto mayor es el valor del número asignado, mayor es la prioridad. Cuando un proceso está esperando a la CPU (en la cola de listos) su prioridad se modifica a razón de a; cuando está ejecutándose su prioridad se modifica a razón de b. Todos los procesos tienen prioridad 0 cuando entran por primera vez a la cola de listos. Los parámetros a y b pueden fijarse para obtener muchos algoritmos de planificación diferentes. a) Si b > a > 0, ¿qué procesos se verán beneficiados? ¿Qué algoritmo resulta? b) Si 0 > b > a, ¿qué procesos se verán beneficiados? ¿Qué algoritmo resulta? SOI

2

Sistemas Operativos

7. Dado un sistema que implementa el algoritmo de planificación a corto plazo Round Robin con cuanto de duración q y tiempo de intercambio i, una serie de n procesos con tiempos de ejecución p1 a pn entran al sistema en distintos instantes de tiempo, t1 , t2 , ... tn . ¿Qué condición debe cumplirse para que todos los procesos cumplan un plazo de ejecución P? Justifique debidamente su respuesta en función de los datos proporcionados en el enunciado.

SOI

3

Sistemas Operativos

Soluciones – Hoja 1 – Sistemas Operativos S1.

a)  Prioridad estricta. Como los procesos llegaron a la máquina prácticamente a la vez, el planificador los ordena por prioridad y los lanza a ejecutarse en ese orden. El diagrama de Gantt sería el siguiente:

B

E

0

A

6

C

1 4

2 4

D 2 6

2 9

Proces T. Retorno T. Espera R(x) (24 + 6 + 26 + 30 + 14) / 5 = 100 / 5 = 20 o A B C D E

24 6 26 30 14

14 0 24 26 6

E(x) = (14 + 24 + 26 + 6) / 5 = 70 / 5 = 14

b)  FCFS  (First Come, First Served): primero en llegar, primero en ser atendido. Como todos llegan casi al tiempo, supondremos que el orden es el que aparece en la tabla: A, B, C, D, E.

A

B 1 0

0

C 1 6

D 1 8

E 2 2

3 0

Proces T. Retorno T. Espera R(x) = (10 + 16 + 18 + 22 + 30) / 5 = 96 / 5 = 19,2 o A B

10 16

0 10

C

18

16

D E

22 30

18 22

E(x) = (10 + 16 + 18 + 22) / 5 = 66 / 5 = 13,2

SOI

4

Sistemas Operativos

c) SJN (Shortest Job Next). De Nuevo, como los procesos han llegado prácticamente a la vez al sistema, son ordenados de menor a mayor tiempo de CPU, y lanzados a ejecutarse en ese orden.

C 0

D 2

B

E 1 2

6

A 2 0

3 0

Proces T. Retorno T. Espera R(x) = (30 + 12 + 2 + 6 + 20) / 5 = 70 / 5 = 14 o A B C D E

30 12 2 6 20

20 6 0 2 12

E(x) = (20 + 6 + 2 + 12) / 5 = 40 / 5 = 8

d) Round Robin (cuanto = 1). Como no se tienen en cuenta los tiempos de intercambio de procesos, la ejecución será la siguiente (mostraremos el contenido de la cola de procesos a cada momento que cambie):

ABCDEABCDE A B D E A B D E A B E A B E A E A E A A 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 Cola de procesos: su ordenación inicial será la dada en la tabla. t = 0: B, C, D, E t = 1: C, D, E, A A ha consumido una unidad de tiempo de CPU y se pone a la cola. t = 2: D, E, A, B B ha consumido una unidad de tiempo de CPU y se pone a la cola. La cola evoluciona así hasta el instante t = 7. Ahí C termina su ejecución y sale del sistema. t = 7: D, E, A, B t = 8: E, A, B C ha terminado, entra D a ejecutarse. t = 9: A, B, D Y el sistema evoluciona así hasta que todos los procesos terminan.

SOI

5

Sistemas Operativos

Proces T. Retorno o

S2.

T. Espera

A B

30 23

20 17

C

8

6

D E

17 28

13 20

R(x) = (30 + 23 + 8 + 17 + 28) / 5 = 106 / 5 = 21.2

E(x) = (20 + 17 + 6 + 13 + 20) / 5 = 76 / 5 = 15.2

Si sabemos que la CPU dará el turno a cada proceso al menos cada  t  segundos, podemos afirmar que ese tiempo será el que tarden los  n­1  procesos restantes en ejecutarse, que es igual a:

t  ( n  1) (q  s ) Despejando q queda:

q

t s (n  1)

Ejemplo: t = 1 s,  n = 10 procesos,  s = 5 ms, el cuanto vale q = 106 ms

SOI

6

Sistemas Operativos

S3.

El objetivo de esta variante de “Round Robin” es darle cierta prioridad a los procesos que  necesitan de algún recurso para poder seguir ejecutándose. Si un proceso no puede continuar  antes de consumir su cuanto, será porque “le falta algo”. De este modo, los procesos que estén a la espera de algún recurso entrarán en ejecución con más frecuencia. Ventajas: los procesos que necesiten de algún recurso bloqueante podrán incorporarse en   una   posición   “adelantada”   de   la   cola   de  listos  cuando   salgan   de   la   cola   de bloqueados. Desventajas:   podría   producirse   inanición   de   algún   proceso   que   no   necesitase   de recursos y estuviese atrás en la cola de  listos. Se pierde equitatividad y, del mismo modo, el tiempo medio de espera aumenta.

SOI

7

Sistemas Operativos

S4.

Selección de algoritmos de planificación: a) Para Venus elegiría el algoritmo de planificación FIFO, ya que los procesos que se ejecutan en Venus no son interactivos y Round­Robin llevaría a una pérdida innecesaria de tiempo de procesador en cambios de contexto. Para Júpiter elegiría el algoritmo de planificación Round­Robin,  ya   que  tenemos   50   procesos   interactivos  a  los  que   hay   que  dar   buenos tiempos de respuesta. Con la política FIFO no se pueden garantizar tiempos de respuesta cortos. b) Para Venus elegiría un cuanto de procesador de 5s., para así reducir el número de cambios de contexto realizados. Para Júpiter elegiría un cuanto de procesador de 5ms., para que el tiempo de respuesta observado por los usuarios interactivos sea pequeño. Un cuanto de 5s llevaría a tiempos de respuesta inaceptablemente largos.

SOI

8

Sistemas Operativos

c)

S5.

a

El orden de ejecución deberá ser por plazo final, en orden no decreciente: Proc_2, Proc_1, Proc_3.

a) Siguiendo el orden determinado en el apartado a), y utilizando una planificación FIFO, el resultado sería el siguiente: Proc_2

Proc_1

0

Proc_3

45,5

131

249,5

Todos los procesos cumplen el requisito de plazo final (en gris aparecen los intervalos de cambio de contexto). Planificación por turnos (Round Robin), suponiendo la ordenación de partida: Proc_1, Proc_2, Proc_3: P1 0

P2 25,5

P3 51

P2*

P1 76,5

102

P3

P3

P1**

173,5

199

P1

122,5

148

P3 209,5

P3*** 235

253

* P2 sólo ejecuta 20 unidades de tiempo, terminando su ejecución. ** P1 sólo ejecuta las 10 unidades de tiempo que le restan. *** P3 ejecuta las 18 unidades de tiempo finales. Con RR, no se cumple el requisito de los plazos de espera para ninguno. Cálculo de los tiempos de retorno para ambas alternativas: T. de Retorno “FIFO” Round Robin

Proc_1

Proc_2

Proc_3

130,5

45

249,5

214

122

258

a)

SOI

9

Sistemas Operativos

S6 .

b > a > 0: los procesos que entren a ejecutarse tendrán más prioridad que los que “aguantan” en la cola, de modo que parecerá un FIFO. b) 0 >  b  >  a:  ambos incrementos son negativos, de manera que quien entra a ejecutarse sufrirá   una   disminución   menor   en   su   prioridad,   y   seguirá   el   primero   de   la   cola.   Sin embargo,   un   proceso   nuevo   en   el   sistema,   aun   teniendo   prioridad   0,   podría   colocarse   el primero. El algoritmo parecerá un LIFO, gestionado como FIFO en caso de “empate”.

SOI 10

Sistemas Operativos

S7

Condiciones para cumplir un plazo de ejecución P: a)

b)

La   suma   de   los   tiempos   de   ejecución   de   los   procesos   más   los   correspondientes intercambios en el caso peor, es decir, cuando coexisten en el sistema los n procesos, debe ser menor o igual a P: Además,   como   los   procesos   pueden   entrar   en   el   sistema   en   cualquier   instante   de tiempo,   hay   que   vigilar   que   desde   que   entra   el   último   proceso   (instante  tn,   siempre menor que P) hasta P haya tiempo de terminar de ejecutar los procesos que quedan en el sistema.

(Intentar expresar las dos condiciones anteriores  con notación matemática: sumatorios…)

SOI 11