Capítulo 5 Planificaciónarantxa.ii.uam.es/~so1/transpas/05-planificador-2pp.pdf · Diagrama de colas de planificación. Ocurre un suceso . gjhgjh 7 Listo (2) En ejecución ... FCFS

gjhgjh

1

Capítulo 5 Planificación Secciones Stallings:

9.1, 9.2 (hasta pág. 421), 9.3

Planificación •  Propósito •  Tipos de planificación:

– Largo plazo – Medio plazo – Corto plazo – E/S

•  Criterios: – Orientados al usuario – Orientados al sistema

•  Prioridades •  Políticas de planificación

gjhgjh

2

Propósito de la planificación

Propósito de la planificación

•  Asignar procesos al planificador de modo que se consiga: – Mejorar tiempos de respuesta – Aumentar productividad – Optimizar eficiencia del procesador y de

dispositivos de E/S.

gjhgjh

3

Tipos de Planificación •  Planificación a largo plazo

–  Decisión de añadir procesos al conjunto de procesos a ejecutar

•  Planificación a medio plazo –  Decisión de añadir procesos al conjunto de procesos que

se encuentran parcial o completamente en la memoria •  Planificación a corto plazo

–  Decisión sobre qué proceso disponible será ejecutado en el procesador

•  Planificación de E/S –  Decisión sobre qué solicitud de E/S pendiente será

tratada por un dispositivo de E/S disponible (Gestión E/S – Stallings 11)

Planificación

a largo plazo

Planificación

a medio plazo

Planificación

a corto plazo

Nuevo

Listo/ suspendido

Bloqueado

Listo Ejecutando Salida

Bloqueado/ suspendido

Planificación y transiciones de estado de los procesos.

Planificación

a largo plazo

Planificación a largo plazo

gjhgjh

4

Ejecutando

Listo

Bloqueado

Corto plazo

Bloqueado suspendido

Listo suspendido

Medio plazo

Nuevo Salida

Figura 9.2. Niveles de planificación.

Largo plazo


•  Determina cuáles son los programas admitidos en el sistema – Listo: cola de planificador a corto plazo – Listo suspendido: cola de planificador a medio

plazo.

•  Controla el grado de multiprogramación: – Cuantos más procesos se crean,

menor porcentaje de tiempo en el que cada proceso se puede ejecutar.

gjhgjh

5

Planificación a largo plazo •  ¿Cuántos procesos adicionales?

–  Limitar el número para dar buen servicio –  Nuevo: cada vez que termina un proceso o si el

porcentaje de utilización del procesador es bajo

•  ¿Qué procesos incluir? –  Algoritmos de planificación

•  Simples (e.g., FIFO-FCFS) •  Por rendimiento del sistema: prioridades, carga procesador,

carga E/S, recurso E/S a solicitar, ...

•  Sistemas interactivos de tiempo compartido –  Se aceptan procesos interactivos hasta saturación

(ej: máx. nº de procesos, carga procesador, número de usuarios, ...) y después mensaje de intentar más tarde.

Planificación a medio plazo

•  Forma parte de la función de intercambio – Gestión de memoria, Memoria Virtual, Estados

Suspendidos.

•  Se basa en la necesidad de controlar el grado de multiprogramación

(tema de memoria)

gjhgjh

6

Planificación a corto plazo •  Decide qué proceso se ejecutará a continuación

–  Obj.: repartir tiempo del procesador de forma que se optimice el comportamiento de 1 o más elementos del sistema.

•  Planificador a corto plazo = distribuidor (dispatcher)

•  Es el de ejecución más frecuente •  Se ejecuta cuando se interrumpe la ejecución de

un proceso: –  Interrupciones del reloj –  Interrupciones de E/S –  Llamadas al sistema operativo –  Señales


Usuarios interactivos


Planificación a corto plazo


Ocurre un suceso

Trabajos por lotes

Tiempo de guarda

Cola de listos

Cola de listos suspendidos

Cola de bloqueados suspendidos

Cola de bloqueados

Terminación Procesador

Espera de un suceso

Figura 9.3. Diagrama de colas de planificación.

Ocurre un suceso

gjhgjh

7

Listo (2) En ejecución (3)

En espera (bloqueado)

(4)

Creación (1) interrupción

Salida (5)

E/S o evento (wait) E/S o final de espera

Asignación

Planificador Procesos

1. Uso de CPU: 100 - (t2-t1) 2. Rendimiento: 2/100 (pr/ut) 3. Tiempo de retorno (medio): (t11 + (100- t3) )/2 4. Tiempo de espera/respuesta (medio):

[(t6 - t5) + (t9 - t8) + (t4 - t3) + (t7 - t6) + (t11 - t10)]/2

P1

P2

T 0 100

1 1 5 5

t1 t2 t3 t4 t5 t6 t7 t8 t9 t11 t10

Criterios de la planificación

Criterios de la p.a corto plazo

•  Orientados al usuario – Cuantitativos (rendimiento) – Cualitativos

•  Orientados al sistema – Cuantitativos (rendimiento) – Cualitativos

gjhgjh

8

Criterios de la p.a corto plazo •  Orientados al usuario (cuantitativos, rendimiento):

–  Tiempo de retorno •  Desde el lanzamiento hasta la finalización de un proceso. •  Apropiado para trabajos por lotes

–  Tiempo de respuesta •  Desde que se emite solicitud hasta que la respuesta aparece en

la salida. •  Apropiada para procesos interactivos

–  Plazos •  Si hay plazos, maximizar porcentaje de plazos cumplidos. •  Caminos críticos: a seguir si se quieren cumplir los requisitos.

•  Orientados al usuario (cualitativos): –  Previsibilidad

•  Tiempo y coste independiente de la carga del sistema

•  Orientados al sistema (cuantitativos, rendimiento): –  Productividad

•  Maximizar nº procesos / unidad de tiempo –  Utilización del procesador

•  Importante en sistemas compartidos caros •  Menos importante en monousuario y en tiempo real

•  Orientados al sistema (cualitativos): –  Equidad (si no hay otras directrices) –  No inanición –  Prioridades: si hay, favorecer a procesos con mayor –  Equilibrio de ocupación de recursos

•  Mantener ocupados los recursos •  Favorecer procesos que no usen recursos sobrecargados •  Afecta también a planificación a largo y medio plazo

Criterios de la p. a corto plazo

gjhgjh

9

Uso de prioridades •  Planificador selecciona, según un algoritmo

de planificación, siempre proceso de mayor prioridad antes que menor prioridad

•  Múltiples colas de Listos: una/nivel de prioridad

•  Procesos de prioridad más baja podrían sufrir inanición. Solución: – Permitir que un proceso cambie su prioridad en

función de su edad o su historial de ejecución.

RQ0

RQ1

RQn

• • •

Expedir Terminar

Espera de Suceso

Entrar

Expulsión

Ocurre un Suceso Cola de Bloqueados

Colas de prioridad

gjhgjh

10

Tema 5: Planificación •  Propósito •  Tipos y alcance:

– A largo plazo – A medio plazo – A corto plazo – Algoritmos de planificación

•  Criterios: –  Orientados al usuario –  Orientados al sistema

•  Prioridades •  Políticas de planificación

Políticas de planificación

•  Definiciones: – Función de selección:

•  cómo seleccionar siguiente proceso a ejecutar

– Modo de selección: •  momento en que se aplica la función de selección

gjhgjh

11

Políticas de planificación

•  Función de selección: cómo seleccionar siguiente proceso a ejecutar – Prioridades – Necesidades de recursos – Características de ejecución:

•  tiempo en el sistema, tiempo ejecutado, tiempo total estimado

Modo de decisión

•  No preferente, no expulsivo (política apropiativa):

•  Proceso pasa a Ejecución => ejecuta hasta que: –  Termina –  Se bloquea en espera de E/S –  Solicita servicio de SO

•  Preferente, expulsivo (política no apropiativa):

•  Proceso en ejecución puede ser interrumpido y pasado a Listo por el SO por:

–  Nuevo proceso –  Proceso pasa de bloqueado a listo (interrupción) –  Interrupción de reloj

gjhgjh

12

Modo de decisión: comparación

•  El modo preferente, expulsivo (apropiativa): –  Mejor servicio: impiden a un proceso

monopolizar el procesador. –  Mayor coste: más cambios de contexto.

Tipos de políticas de planif.

•  FCFS (First-come, First-served) •  Turno rotatorio (Round-Robin) •  SPN (Shortest Process Next) •  SRT (Shortest Remaining Time) •  HRRN (Highest Response Ratio Next) •  Realimentación •  Reparto equitativo •  Planificación garantizada

gjhgjh

13

Ejemplo (políticas de planif.)

Proceso Instante de llegada Tiempo de servicio

FCFS (FIFO) •  Cada proceso se incorpora a la cola de listos. •  Cuando el proceso actual cesa su ejecución,se

selecciona el proceso que lleve más t. listo. –  Función de selección: máximo tiempo en la cola

de listos –  Modo de decisión: No preferente

0 5 10 15 20

A

B C D E

Llegada Proceso Servicio

gjhgjh

14

FCFS

P1

P2

T 0 100

1 5 5

80 90 P3

5

P2

P3

P1

1 5 5 5

Es teóricamente justo, pero poco eficiente en tiempo de espera medio. Penaliza los procesos cortos.

FCFS Efecto convoy:

Dominio de procesos con carga de CPU frente a los que hacen uso de E/S. Posible uso ineficiente no solo de CPU sino también de los dispositivos de E/S.

P1

P2

P3

1

P1

P2

P3

1

gjhgjh

15

FCFS

•  Por sí misma, no útil para monoprocesadores

•  Planificación efectiva combinada con colas de prioridades – Planificación realimentada

Proceso Llegada Ráfaga CPU E/S Ráfaga CPU A 0 3 2 2 B 2 6 - - C 4 4 4 4 D 6 5 5 1 E 8 2 2 2

FCFS

A B C D E

5 10 15 20 25 30

En ejecución Listo En espera de E-S

Terminado

Sin Cargar

gjhgjh

16


FCFS

A B C D E

5 10 15 20 25 30


Terminado

Sin Cargar


FCFS

A B C D E

5 10 15 20 25 30


Terminado

Sin Cargar

gjhgjh

17


FCFS

A B C D E

5 10 15 20 25 30


Terminado

Sin Cargar


FCFS

A B C D E

5 10 15 20 25 30


Terminado

Sin Cargar

gjhgjh

18


FCFS

A B C D E

5 10 15 20 25 30


Terminado

Sin Cargar


FCFS

A B C D E

5 10 15 20 25 30


Terminado

Sin Cargar

gjhgjh

19


FCFS

A B C D E

5 10 15 20 25 30


Terminado

Sin Cargar


FCFS

A B C D E

5 10 15 20 25 30


Terminado

Sin Cargar

gjhgjh

20

A B C D E

5 10 15 20 25 30 35 40 45

Proceso llegada Ráfaga CPU E/S ráfaga CPU A 0 3 2 2 B 2 6 - - C 4 4 4 4 D 6 5 5 1 E 8 2 2 2

FCFS


Terminado

Sin Cargar

A B C D E

5 10 15 20 25 30 35 40 45


FCFS

1. Uso de CPU: 29 – 0 = 29/29 2. Rendimiento: 5/29 3. Tiempo de retorno (medio): (15 + 7 + 22 + 23 + 20) / 5 = 82 / 5 = 17.4 4. Tiempo de espera/respuesta (medio): (8 + 1 + 5 + 5 + 9 + 3 + 12 + 2) / 5 = 9

gjhgjh

21

Turno rotatorio (Round Robin)

0 5 10 15 20

A

B C D E

•  Reduce penalización a procesos cortos •  Apropiación dependiente de un reloj •  Se determina un periodo de tiempo (cuanto,

q) de uso del procesador –  Función de selección: constante –  Modo de decisión: preferente (cada q)

Turno rotatorio (Round Robin)


gjhgjh

22

•  Periódicamente, se genera interrupción de reloj – Diseñado específicamente para sistemas de

tiempo compartido – Se asigna un cuanto de tiempo (10-100 ms.) de

igual duración a todos los procesos listos para ser ejecutados

•  Cuando se genera la interrupción: – El proceso en ejecución pasa a la cola de Listos – Se selecciona el siguiente trabajo de la cola

(FCFS)

Round Robin

Round Robin (q=3)

1

0 26 16 1 6 2 3 12 9 15 19 21 23 T

P1

P2 P3

P4

gjhgjh

23

•  Parámetro crítico de diseño: longitud del cuanto –  Si muy pequeño, procesos cortos pasan rápidamente,

pero sobrecarga del procesador (gestión interrupciones de reloj, planificación, expedición)

–  Si muy grande, degenera en FCFS –  Referencia: debe ser algo mayor que el tiempo necesario

para una interacción normal –  Efectivo en sistemas de carácter general, tiempo

compartido, procesos de transacciones –  Favorece procesos con carga de procesador vs. procesos

con carga de E/S (éstos no aprovechan el cuanto).

Round Robin


En ejecución Listo Sin cargar

Round Robin q=1

A B C D E

gjhgjh

24



Round Robin q=1

A B C D E



Round Robin q=1

A

A B C D E

gjhgjh

25



Round Robin q=1

A B

A B C D E


Round Robin q=1

A B C

A B C D E

5


Terminado

Sin Cargar

gjhgjh

26


Round Robin q=1

A B C B

A B C D E

5


Terminado

Sin Cargar


Round Robin q=1

A B C B A D C

A B C D E

5


Terminado

Sin Cargar

gjhgjh

27


Round Robin q=1

A B C B A D C

D C B

A B C D E

5


Terminado

Sin Cargar


Round Robin q=1

A B C B A D C

D C B

C B E A

A B C D E

5


Terminado

Sin Cargar

gjhgjh

28


Round Robin q=1

A B C B A D C

D C B

C B E A

B E A D

A B C D E

5 10


Terminado

Sin Cargar


Round Robin q=1

A B C B A D C

D C B

C B E A

B E A D

E A D C

A B C D E

5 10


Terminado

Sin Cargar

gjhgjh

29


Round Robin q=1

A B C B A D C

D C B

C B E A

B E A D

E A D C

A D C B

D C B E

C B E

B E D

E D C

D C B

C B

A B C D E

5 10 15 20 25 30 35 40 45


Terminado

Sin Cargar

Orden encolar (RR): •  Vuelta de E/S •  Nuevo •  Acaba de ejecutarse (RR)


Round Robin q=1

A B C B A D C

D C B

C B E A

B E A D

E A D C

A D C B

D C B E

C B E

B E D

E D C

D C B

C B

A B C D E

5 10 15 20 25 30 35 40 45


Terminado

Sin Cargar


B D

gjhgjh

30


Round Robin q=1

A B C B A D C

D C B

C B E A

B E A D

E A D C

A D C B

D C B E

C B E

B E D

E D C

D C B

C B

B D

D E

A B C D E

5 10 15 20 25 30 35 40 45


Terminado

Sin Cargar


B

20


Round Robin q=1

A B C B A D C

D C B

C B E A

B E A D

E A D C

A D C B

D C B E

C B E

B E D

E D C

D C B

C B

B D

D E

E

A B C D E

5 10 15 20 25 30 35 40 45


Terminado

Sin Cargar


B

20

gjhgjh

31


Round Robin q=1

A B C B A D C

D C B

C B E A

B E A D

E A D C

A D C B

D C B E

C B E

B E D

E D C

D C B

C B

B D

D E

E D

A B C D E

5 10 15 20 25 30 35 40 45


Terminado

Sin Cargar


B

20


Round Robin q=1

A B C B A D C

D C B

C B E A

B E A D

E A D C

A D C B

D C B E

C B E

B E D

E D C

D C B

C B

B D

D E

E D

A B C D E

5 10 15 20 25 30 35 40 45


Terminado

Sin Cargar


B

20

E

gjhgjh

32


Round Robin q=1

A B C B A D C

D C B

C B E A

B E A D

E A D C

A D C B

D C B E

C B E

B E D

E D C

D C B

C B

B D

D E

E D

A B C D E

5 10 15 20 25 30 35 40 45


Terminado

Sin Cargar


B

20

E C


Round Robin q=1

A B C B A D C

D C B

C B E A

B E A D

E A D C

A D C B

D C B E

C B E

B E D

E D C

D C B

C B

B D

D E

E D E C

A B C D E

5 10 15 20 25 30 35 40 45


Terminado

Sin Cargar


gjhgjh

33


Round Robin q=1

A B C B A D C

D C B

C B E

B E A

E A D

A D C

D C B

C B E

B E D

E D C

D C B

C B

B D

D E

E D E C

A B C D E

5 10 15 20 25 30 35 40 45

1. Uso de CPU: 29 - 0 = 29/29 2. Rendimiento: 5/29 3. Tiempo de retorno (medio): (13 + 18 + 24 + 23 + 16) / 5 = 94 / 5 = 18.8 4. Tiempo de espera/respuesta (medio): (6 + 12 + 12 + 12 + 10) / 5 = 10.4

Virtual Round Robin (VRR)

•  Procesos con carga E/S vs. procesos con carga CPU con Round Robin: –  Procesos con carga E/S tienden a rendimiento pobre

=> desaprovechamiento de recursos E/S

•  VRR: Cola de Listos (FCFS) y una cola Auxiliar (FCFS) con mayor prioridad –  Procesos que dejan de estar bloqueados por E/S

se desplazan a cola Auxiliar –  Procesos de cola Auxiliar se ejecutan q-e

(“apuran el cuanto”) •  e = tiempo de ejecución la última vez (antes de espera E/S)

gjhgjh

34

SPN (1º el proceso más corto) •  Se selecciona el proceso con menor tiempo

esperado de ejecución. •  Un proceso corto salta a la cabeza de la cola,

sobrepasando a trabajos largos. –  Función de selección: mínimo tiempo total de servicio –  Modo de decisión: No expulsivo (no preferente)

0 5 10 15 20

A

B C D E


SPN •  Estimaciones:

– Trabajos por lotes o repetitivos: •  estimación del programador o estadísticas

en función de tiempos de ejecución pasados => miramos suma de ráfagas en la tabla

– Si procesos interactivos •  en lugar de tiempo de trabajo, tiempo de cada ráfaga

(se supone que siguen una distribución uniforme) => calculamos en función de ráfagas pasadas (media o con alfa)

•  Modo de decisión: no expulsivo α tn Sn+1 = + (1- α) Sn 0< α < 1

gjhgjh

35

SPN •  Normalmente se utiliza promedio exponencial:

• S1 : valor pronosticado (no calculado). Puede eliminarse en sucesivos cálculos o sustituirse por T1

•  Si α tiende a 1 se reflejan rápidamente los cambios, pero si son efectos aislados desestabilizan la media más tiempo. •  Conviene dar más peso a los valores más recientes

α tn Sn+1 = +(1- α) Sn 0< α < 1

SPN

Σ ti i=1

n 1 n Sn+1 = = Σ ti i=1

n-1 1 tn n

1 n + = + Σ ti i=1

n-1 1 tn n

1 n-1

n-1 n

Sn = Σ ti i=1

n-1 1 n-1

Sn+1 = +1 tn n

n-1 n Sn

Mismo peso a todos los casos

gjhgjh

36

SPN (1º el proceso más corto) •  Se selecciona el proceso con menor tiempo

esperado de ejecución. •  Un proceso corto salta a la cabeza de la cola,

sobrepasando a trabajos largos. –  Función de selección: mínimo tiempo total de servicio –  Modo de decisión: No expulsivo (no preferente)

0 5 10 15 20

A

B C D E


Proceso llegada Ráfaga CPU E/S Ráfaga CPU A 0 3 2 2 B 2 6 - - C 4 4 4 4 D 6 5 5 1 E 8 2 2 2


SPN (Primero el proceso más corto)

A B C D E

(proceso por lotes)

Suma = 5 Suma = 6 Suma = 8 Suma = 6 Suma = 4

gjhgjh

37




A B C D E

(proceso por lotes)

Suma = 5 Suma = 6 Suma = 8 Suma = 6 Suma = 4



A B C D E

5


Terminado

Sin Cargar

(proceso por lotes)

Suma A = 5 Suma B = 6 Suma C = 8 Suma D = 6 Suma E = 4

gjhgjh

38



A B C D E

5 10


Terminado

Sin Cargar

(proceso por lotes)




A B C D E

5 10


Terminado

Sin Cargar

(proceso por lotes) E tmb. pasa a cola de listos


gjhgjh

39



A B C D E

5 10 15


Terminado

Sin Cargar

(proceso por lotes)




A B C D E

5 10 15 20


Terminado

Sin Cargar

(proceso por lotes)


gjhgjh

40



A B C D E

5 10 15 20


Terminado

Sin Cargar

(proceso por lotes)




A B C D E

5 10 15 20 25


Terminado

Sin Cargar

(proceso por lotes)


gjhgjh

41



A B C D E

5 10 15 20 25


Terminado

Sin Cargar

(proceso por lotes)




A B C D E

5 10 15 20 25 30 35 40 45


Terminado

Sin Cargar

(proceso por lotes)


gjhgjh

42



1. Uso de CPU: 32 - 3 => 29/32 2. Rendimiento: 5/32 3. Tiempo de retorno (medio): (13 + 7 + 28 + 20 + 7) / 5 = 75 / 5 = 15 4. Tiempo de espera/respuesta (medio): (6 + 1 + 16 + 9 + 1) / 5 = 33 / 5 = 6.6

A B C D E

5 10 15 20 25 30 35 40 45

(proceso por lotes)



A B C D E

5 10 15 20 25 30 35 40 45

SPN(Primero el proceso más corto)

(proceso interactivo)

Varias formas para estimar tiempo inicial de proceso nuevo: -  No sabemos nada sobre las ráfagas: S1 = 0 (los procesos nuevos son preferentes) -  Tomando S1= T1 (problema: hay que saber el T1) -  Tomando S1 = CTE (ej: media de las ráfagas de procesos interactivos anteriores en el sistema)

gjhgjh

43


A B C D E

5 10 15 20 25 30 35 40 45


(proceso interactivo) S1 = 0

Est. A = 3 Est. B = 0 Est. C = 0 Est. D = 0 Est. E = 0


A B C D E

5 10 15 20 25 30 35 40 45




gjhgjh

44


A B C D E

5 10 15 20 25 30 35 40 45





A B C D E

5 10 15 20 25 30 35 40 45




gjhgjh

45


A B C D E

5 10 15 20 25 30 35 40 45





A B C D E

5 10 15 20 25 30 35 40 45




gjhgjh

46


A B C D E

5 10 15 20 25 30 35 40 45





A B C D E

5 10 15 20 25 30 35 40 45


1. Uso de CPU: 29 => 29/29 2. Rendimiento: 5/29 3. Tiempo de retorno (medio): (22 + 7 + 24 + 24 + 12) / 5 = 89 / 5 = 17.8 4. Tiempo de espera/respuesta (medio): (15+ 1 + 12 + 12 + 10) / 5 = 50 / 5 = 10.0


Est.ini A = 0 Est.ini B = 0 Est.ini C = 0 Est.ini D = 0 Est.ini E = 0

gjhgjh

47


•  Mejora rendimiento global: t. de retorno y t. de espera/respuesta

•  Posibilidad de inanición para los procesos largos

•  No conveniente para tiempo compartido o procesamiento de transacciones (por la ausencia de apropiación)

•  Se reduce la previsibilidad de los procesos largos (puede variar mucho de una vez a otra)

SRT (Menor tiempo restante) •  Versión preferente de SPN: elige el proceso que le

queda menos tiempo esperado de ejecución •  Cada vez que llega un proceso nuevo a la cola de

listos se ejecuta el planificador. –  Función de selección: mínimo tiempo restante

de ejecución (t. total – t. consumido) –  Modo de decisión: Preferente en llegada a listos

0 5 10 15 20

A

B C D E


gjhgjh

48

SRT (Menor tiempo restante)

•  Problema: ¿Cómo saber el tiempo esperado? •  Estimar igual que en SPN




A B C D E

(proceso por lotes)

Trestante= 3 Trestante= 6

Sin Cargar Sin Cargar

Sin Cargar

gjhgjh

49



A B C D E


Terminado

Sin Cargar

(proceso por lotes)


Trestante= 8 Sin Cargar

Sin Cargar



A B C D E

5


Terminado

Sin Cargar

(proceso por lotes)


Trestante= 8 Sin Cargar

Sin Cargar

gjhgjh

50



A B C D E

5


Terminado

Sin Cargar

(proceso por lotes)


Trestante= 8

Trestante= 6

Sin Cargar



A B C D E

5 10 15 20 25 30 35 40 45


Terminado

Sin Cargar

Terminó Trestante= 4

Trestante= 8

Trestante= 6

Sin Cargar

(proceso por lotes)

gjhgjh

51


SRT(Menor tiempo restante)

A B C D E

5


Terminado

Sin Cargar

(proceso por lotes)


Trestante= 8

Trestante= 6

Trestante= 4



A B C D E

5 10


Terminado

Sin Cargar

(proceso por lotes)


Trestante= 8

Trestante= 6

Trestante= 4

gjhgjh

52



A B C D E

5 10


Terminado

Sin Cargar

(proceso por lotes)

Terminó Terminó

Trestante= 8

Trestante= 6

Trestante= 4



A B C D E

5 10


Terminado

Sin Cargar

(proceso por lotes)

Terminó Terminó

Trestante= 8

Trestante= 6

Trestante= 2

gjhgjh

53



A B C D E

5 10 15


Terminado

Sin Cargar

(proceso por lotes)

Terminó Terminó

Trestante= 8

Trestante= 4

Trestante= 2



A B C D E

5 10 15


Terminado

Sin Cargar

(proceso por lotes)

Terminó Terminó

Trestante= 8

Trestante= 4

Terminó

gjhgjh

54



A B C D E

5 10 15 20


Terminado

Sin Cargar

(proceso por lotes)

Terminó Terminó

Trestante= 8

Trestante= 1

Terminó



A B C D E

5 10 15 20 25 30 35 40 45


Terminado

Sin Cargar

(proceso por lotes)

gjhgjh

55



A B C D E

5 10 15 20 25 30 35 40 45

(proceso por lotes) 1. Uso de CPU: 32 - 3 = 29/32 2. Rendimiento: 5/32 3. Tiempo de retorno (medio): (7 + 9 + 28 + 20 + 9) / 5 = 73 / 5 = 14.6 4. Tiempo de espera (medio): (0 + 3 + 16 + 9 + 3) / 5 = 31 / 5 = 6.2


Procesos interactivos:

S1 debe ser estimado por ejemplo, podemos tomar como estimación para la primera ráfaga la media “histórica” de ráfagas de procesos interactivos en el sistema. Supongamos S1 = 3

SRT (Menor Tiempo Restante)

gjhgjh

56


A B C D E

5 10 15 20 25 30 35 40 45

S1= 3, r = 1 S1= 3, r = 3 Sin Cargar Sin Cargar Sin Cargar

(proceso interactivo S1 = 3)


Terminado

Sin Cargar



A B C D E

5 10 15 20 25 30 35 40 45

S1 = 3, S2 = ? S1 = 3, r = 3 Sin Cargar

Sin Cargar Sin Cargar


Terminado

Sin Cargar



gjhgjh

57


A B C D E

5 10 15 20 25 30 35 40 45

S1 = 3 , S2 = ? S1 = 3, r = 2 S1 = 3, r = 3 Sin Cargar Sin Cargar


Terminado

Sin Cargar




A B C D E

5 10 15 20 25 30 35 40 45

S2 = 3, r = 3 S1 = 3, r = 1 S1 = 3, r = 3 Sin Cargar Sin Cargar


Terminado

Sin Cargar



gjhgjh

58


A B C D E

5 10 15 20 25 30 35 40 45

S2 = 3, r = 3 S1 = 3, r = 0 S1 = 3, r = 3 S1 = 3, r = 3 Sin Cargar


Terminado

Sin Cargar


(proceso interactivo S1 = 3) u=7 ?


A B C D E

5 10 15 20 25 30 35 40 45

S2 = 3, r = 3 S1 = 3, r = -2 S1 = 3, r = 3 S1 = 3, r = 3 S1 = 3, r = 3


Terminado

Sin Cargar



gjhgjh

59


A B C D E

5 10 15 20 25 30 35 40 45

S2 = 3, r = 3 Terminado S1 = 3, r = 3 S1 = 3, r = 3 S1 = 3, r = 3


Terminado

Sin Cargar




A B C D E

5 10 15 20 25 30 35 40 45


Terminado

Sin Cargar



S2 = 3, r = 3 Terminado S1 = 3, S2 = ? S1 = 3, r = 3 S1 = 3, r = 3

gjhgjh

60


A B C D E

5 10 15 20 25 30 35 40 45


Terminado

Sin Cargar



Terminado Terminado S1 = 3, S2 = ? S1 = 3, r = 3 S1 = 3, r = 3


Terminado Terminado S2 = 3.8, r = 3.8 S1 = 3, r = 1 S1 = 3, r = 3


Terminado

Sin Cargar



A B C D E

5 10 15 20 25 30 35 40 45

gjhgjh

61


Terminado Terminado S2 = 3.8, r = 3.8 S1 = 3, S2 = ? S1 = 3, r = 3


Terminado

Sin Cargar



A B C D E

5 10 15 20 25 30 35 40 45 50



Terminado

Sin Cargar



Terminado Terminado S2 = 3.8, r = 3.8 S1 = 3, S2 = ? S1 = 3, S2 = ?

A B C D E

5 10 15 20 25 30 35 40 45

gjhgjh

62



Terminado

Sin Cargar



Terminado Terminado S2 = 3.8, r = 1.8 S1 = 3, S2 = ? S2 = 2.2, r = 2.2

A B C D E

5 10 15 20 25 30 35 40 45



Terminado

Sin Cargar



A B C D E

5 10 15 20 25 30 35 40 45

Terminado Terminado S2 = 3.8, r = 0.8 S2 = 4.6, r = 4.6 S2 = 2.2, r = 2.2

gjhgjh

63



Terminado

Sin Cargar



Terminado Terminado Terminado S2 = 4.6, r = 4.6 S2 = 2.2, r = 2.2

A B C D E

5 10 15 20 25 30 35 40 45



Terminado

Sin Cargar



A B C D E

5 10 15 20 25 30 35 40 45

gjhgjh

64




1. Uso de CPU: 29 => 29/29 2. Rendimiento: 5/29 3. Tiempo de retorno (medio): (15 + 7 + 22+ 22 + 20) / 5 = 86 / 5 = 17.2 4. Tiempo de espera (medio): (8 + 1 + 10 + 12 + 14) / 5 = 45 / 5 = 9.0

A B C D E

5 10 15 20 25 30 35 40 45


•  Favorece a los procesos cortos •  Ventaja: no genera interrupciones

adicionales (vs. Round Robin) •  Desventaja: debe contabilizar los tiempos

de servicio transcurridos => sobrecarga

gjhgjh

65

HRRN (1º el de mayor tasa de respuesta)

•  Elige el proceso con la tasa de respuesta (tiempo “instantáneo” de retorno normalizado) más alta. – Función de selección: máxima tasa de respuesta – Modo de decisión: NO preferente

Tasa de Respuesta =

Tiempo consumido esperando al procesador

+ Tiempo de

servicio esperado

Tiempo de servicio esperado

HRRN •  Procesos cortos => denominador pequeño

=> tasa de respuesta alta •  Envejecimiento sin servicio

=> nominador grande => tasa de respuesta alta => procesos largos compiten con los cortos

A

B C D E

0 5 10 15 20


t. esperando + t.esperado t. esperado

gjhgjh

66


A B C D E

5 10 15 20 25 30 35 40 45

HRRN (Mayor tasa de respuesta)


Terminado

Sin Cargar


A B C D E

5 10 15 20 25 30 35 40 45

HRRN (Mayor tasa de respuesta)

1. Uso de CPU: 29 - 0 = 29/29 2. Rendimiento: 5/29 3. Tiempo de retorno (medio): (11 + 7 + 24 + 23 + 16) / 5 = 81 / 5 = 16.2 4. Tiempo de espera/respuesta (medio): (4 + 1 + 12 + 12 + 10) / 5 = 39 / 5 = 7.8

gjhgjh

67

Realimentación multinivel •  No se dispone de información del tiempo de

ejecución del proceso (SPN, SRT, HRRN). •  Para dar preferencia a trabajos cortos, se penaliza

a los que han estado ejecutándose más tiempo. –  Función de selección: FIFO con reducción de prioridad

tras cada ejecución (RR en la última cola) –  Modo de decisión: preferente (cada q)

(q=1, 2 colas)

0 5 10 15 20

A

B C D E

Realimentación multinivel

A

B C D E (q=1, 5 colas)

0 5 10 15 20

gjhgjh

68

RQ0

RQ1

RQn

Expedir Terminar Entrar

• • •

• • • Terminar

Terminar

Planificación con realimentación


Realimentación multinivel (q=1)


Terminado Sin Cargar

B

A

C

D

A B C D E

5 10 15 20 25 30 35 40 45

q = 1

# colas prioridad= 5

gjhgjh

69


Realimentación multinivel (q=1)

1. Uso de CPU: 29 => 29/29 2. Rendimiento: 5/29 3. Tiempo de retorno (medio): (22 + 22 + 24 + 23 + 12) / 5 = 103 / 5 = 20.6 4. Tiempo de espera (medio): (15 + 16 + 12 + 12 + 6) / 5 = 61 / 5 = 12.2

A B C D E

5 10 15 20 25 30 35 40 45

q = 1

# colas prioridad= 5

Realimentación multinivel •  Procesos cortos: terminan rápido, sin descender

demasiado en la jerarquía de colas. •  Procesos largos: llevados gradualmente hacia abajo.

Problema: pueden sufrir inanición en colas de prioridad baja si llegan muchos procesos cortos continuamente

•  Soluciones: –  Cuanta menor es la prioridad se pueden asignar más

cuantos de tiempo de ejecución –  Tras cierto tiempo de espera en cola, se le cambia a una

cola de prioridad mayor.

gjhgjh

70

Realimentación multinivel

•  Múltiples variantes: – Apropiación en intervalos periódicos (como

Round Robin) – Otras: SRT en cada cola, etc.

Combinación de políticas

•  Ejemplos: – FIFO con prioridades realimentadas: FIFO y

cada vez que un proceso deja la CPU se decrementa su prioridad

– Cualquier política + prioridades: se sigue la política concreta (q. puede ser apropiativa o no apropiativa), pero si llega proceso con mayor prioridad, entra directamente.

gjhgjh

71

A B C D E

5 10 15 20 25 30 35 40 45 50

A B C D E

5 10 15 20 25 30 35 40 45 50

A B C D E

5 10 15 20 25 30 35 40 45 50

A B C D E

5 10 15 20 25 30 35 40 45 50

A B C D E

5 10 15 20 25 30 35 40 45 50

A B C D E

5 10 15 20 25 30 35 40 45 50

FCFS

RR (q=1)

SPN

SRT

HRRN

Reali-mentación (q=1)

1. Uso de CPU: 30 – (1) = 29/30 2. Rendimiento: 5/30 3. Tiempo de retorno (medio): (11 + 7 + 20 + 21 + 23) / 5 = 82 / 5 = 16.4 4. Tiempo de espera/respuesta (medio): (4 + 1 + 7 + 1 + 9 + 1 + 16) / 5 = 7.8

1. Uso de CPU: 29 - 0 = 29/29 2. Rendimiento: 5/29 3. Tiempo de retorno (medio): (13 + 18 + 24 + 23 + 16) / 5 = 94 / 5 = 18.8 4. Tiempo de espera/respuesta (medio): (6 + 12 + 12 + 12 + 10) / 5 = 10.4

1. Uso de CPU: 30 - 1 = 29/30 2. Rendimiento: 5/30 3. Tiempo de retorno (medio): (13 + 7 + 24 + 24 + 7) / 5 = 75 / 5 = 15 4. Tiempo de espera/respuesta (medio): (6 + 1 + 12 + 13 + 1) / 5 = 33 / 5 = 6.6




FCFS

RR (q=1)

SPN

SRT

HRRN

Realimentación (q=1)

gjhgjh

72

Planificación clásica en UNIX •  Diseñada para satisfacer las necesidades de usuarios

interactivos, tiempo compartido, propósito general –  Usa realimentación multinivel ,

turno rotatorio (q=0.1 seg.) en cada cola de prioridad –  La prioridad de cada proceso se calcula:

•  Cada segundo con preferencia => si un proceso no se bloquea o termina en ese segundo, es expulsado

•  En función de tipo de proceso e historial de ejecución –  Prioridad base: divide procesos en bandas fijas de

prioridad –  Usa factor de ajuste (nice) para impedir que proceso

salga de la banda asignada.

Bandas

•  En orden decreciente de prioridad: –  Intercambio –  Control de dispositivos de E/S de bloques (ej: disco) –  Gestión de archivos –  Control de dispositivos de E/S de caracteres

(ej: terminales, impresoras) –  Procesos de usuario

•  para –  Garantizar uso eficiente de E/S –  Penalizar a procesos con carga CPU

gjhgjh

73

Planificación clásica en UNIX

CPUj(i)= CPUj(i-1)

2

Pj(i) = Basej+ CPUj(i)

2 + nicej

Media ponderada del proceso j en el intervalo i

Prioridad del proceso j al principio del intervalo i

Figura 9.17. Ejemplo de planificación clásica en UNIX.

(Libro mal coloreado)

Base = 60, ajuste ignorado

gjhgjh

74

Planificación •  Hilos a nivel de usuario:

–  El SO no conoce la existencia de hilos => planifica a nivel de proceso

–  Dentro de un proceso, planificador a nivel de usuario se encarga de los hilos

•  Hilos a nivel de núcleo: –  El SO conoce y maneja hilos

=> planificación a nivel de hilos –  Pero el SO puede decidir asignar tiempos en función de

lo que hayan ejecutado otros hilos del mismo proceso (sabe a qué proceso pertenece cada hilo)

Procesos en tiempo real

•  Proceso debe cumplir plazo límite •  Ejemplos:

–  Sistemas militares de mando y control –  Control del tráfico aéreo –  Control de procesos en plantas industriales –  …

•  Pueden ser periódicos o no •  Planificador debe tener en cuenta plazos

=> debe poder ejecutar lo que corresponda dentro del plazo límite

gjhgjh

75

En cada interrupción…

•  Tratamiento de la interrupción (ejecución de rutina de atención a la interrupción, ej: E/S, llamada al sistema)

•  Comprobar si algún proceso pasa de bloqueado a listo

•  Comprobar si hay procesos nuevos

•  Ejecutar la función de planificación según la política correspondiente

Documents

Capítulo 5 Planificaciónarantxa.ii.uam.es/~so1/transpas/05-planificador-2pp.pdf · Diagrama de colas de planificación. Ocurre un suceso . gjhgjh 7 Listo (2) En ejecución ... FCFS