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
Planificación a 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
Planificación a largo plazo
Usuarios interactivos
Planificación a medio plazo
Planificación a corto plazo
Planificación a medio 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
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
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
17
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
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
18
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
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
19
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
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
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
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)
Llegada Proceso Servicio
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
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
En ejecución Listo Sin cargar
Round Robin q=1
A B C D E
gjhgjh
24
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
En ejecución Listo Sin cargar
Round Robin q=1
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
En ejecución Listo Sin cargar
Round Robin q=1
A
A B C D E
gjhgjh
25
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
En ejecución Listo Sin cargar
Round Robin q=1
A B
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
Round Robin q=1
A B C
A B C D E
5
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
gjhgjh
26
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
Round Robin q=1
A B C B
A B C D E
5
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
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
Round Robin q=1
A B C B A D C
A B C D E
5
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
gjhgjh
27
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
Round Robin q=1
A B C B A D C
D C B
A B C D E
5
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
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
Round Robin q=1
A B C B A D C
D C B
C B E A
A B C D E
5
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
gjhgjh
28
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
gjhgjh
29
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
Orden encolar (RR): • Vuelta de E/S • Nuevo • Acaba de ejecutarse (RR)
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
Orden encolar (RR): • Vuelta de E/S • Nuevo • Acaba de ejecutarse (RR)
B D
gjhgjh
30
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
Orden encolar (RR): • Vuelta de E/S • Nuevo • Acaba de ejecutarse (RR)
B
20
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
Orden encolar (RR): • Vuelta de E/S • Nuevo • Acaba de ejecutarse (RR)
B
20
gjhgjh
31
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
Orden encolar (RR): • Vuelta de E/S • Nuevo • Acaba de ejecutarse (RR)
B
20
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
Orden encolar (RR): • Vuelta de E/S • Nuevo • Acaba de ejecutarse (RR)
B
20
E
gjhgjh
32
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
Orden encolar (RR): • Vuelta de E/S • Nuevo • Acaba de ejecutarse (RR)
B
20
E C
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
Orden encolar (RR): • Vuelta de E/S • Nuevo • Acaba de ejecutarse (RR)
gjhgjh
33
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
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
Llegada Proceso Servicio
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
Llegada Proceso Servicio
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
En ejecución Listo Sin cargar
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
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
En ejecución Listo Sin cargar
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
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
5
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
(proceso por lotes)
Suma A = 5 Suma B = 6 Suma C = 8 Suma D = 6 Suma E = 4
gjhgjh
38
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
5 10
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
(proceso por lotes)
Suma A = 5 Suma B = 6 Suma C = 8 Suma D = 6 Suma E = 4
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
5 10
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
(proceso por lotes) E tmb. pasa a cola de listos
Suma A = 5 Suma B = 6 Suma C = 8 Suma D = 6 Suma E = 4
gjhgjh
39
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
5 10 15
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
(proceso por lotes)
Suma A = 5 Suma B = 6 Suma C = 8 Suma D = 6 Suma E = 4
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
5 10 15 20
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
(proceso por lotes)
Suma A = 5 Suma B = 6 Suma C = 8 Suma D = 6 Suma E = 4
gjhgjh
40
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
5 10 15 20
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
(proceso por lotes)
Suma A = 5 Suma B = 6 Suma C = 8 Suma D = 6 Suma E = 4
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
5 10 15 20 25
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
(proceso por lotes)
Suma A = 5 Suma B = 6 Suma C = 8 Suma D = 6 Suma E = 4
gjhgjh
41
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
5 10 15 20 25
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
(proceso por lotes)
Suma A = 5 Suma B = 6 Suma C = 8 Suma D = 6 Suma E = 4
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
5 10 15 20 25 30 35 40 45
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
(proceso por lotes)
Suma A = 5 Suma B = 6 Suma C = 8 Suma D = 6 Suma E = 4
gjhgjh
42
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)
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)
Suma A = 5 Suma B = 6 Suma C = 8 Suma D = 6 Suma E = 4
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
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
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
A B C D E
5 10 15 20 25 30 35 40 45
SPN(Primero el proceso más corto)
(proceso interactivo) S1 = 0
Est. A = 3 Est. B = 0 Est. C = 0 Est. D = 0 Est. E = 0
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
A B C D E
5 10 15 20 25 30 35 40 45
SPN(Primero el proceso más corto)
(proceso interactivo) S1 = 0
Est. A = 3 Est. B = 6 Est. C = 4 Est. D = 0 Est. E = 0
gjhgjh
44
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
A B C D E
5 10 15 20 25 30 35 40 45
SPN(Primero el proceso más corto)
(proceso interactivo) S1 = 0
Est. A = 3 Est. B = 6 Est. C = 4 Est. D = 5 Est. E = 0
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
A B C D E
5 10 15 20 25 30 35 40 45
SPN(Primero el proceso más corto)
(proceso interactivo) S1 = 0
Est. A = 3 Est. B = 6 Est. C = 4 Est. D = 5 Est. E = 2
gjhgjh
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
A B C D E
5 10 15 20 25 30 35 40 45
SPN(Primero el proceso más corto)
(proceso interactivo) S1 = 0
Est. A = 3 Est. B = 6 Est. C = 4 Est. D = 5 Est. E = 2
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
A B C D E
5 10 15 20 25 30 35 40 45
SPN(Primero el proceso más corto)
(proceso interactivo) S1 = 0
Est. A = 3 Est. B = 6 Est. C = 4 Est. D = 5 Est. E = 2
gjhgjh
46
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
A B C D E
5 10 15 20 25 30 35 40 45
SPN(Primero el proceso más corto)
(proceso interactivo) S1 = 0
Est. A = 3 Est. B = 6 Est. C = 4 Est. D = 5 Est. E = 2
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
A B C D E
5 10 15 20 25 30 35 40 45
SPN(Primero el proceso más corto)
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
(proceso interactivo) S1 = 0
Est.ini A = 0 Est.ini B = 0 Est.ini C = 0 Est.ini D = 0 Est.ini E = 0
gjhgjh
47
SPN (Primero el proceso más corto)
• 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
Llegada Proceso Servicio
gjhgjh
48
SRT (Menor tiempo restante)
• Problema: ¿Cómo saber el tiempo esperado? • Estimar igual que en SPN
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
En ejecución Listo Sin cargar
SRT (Menor tiempo restante)
A B C D E
(proceso por lotes)
Trestante= 3 Trestante= 6
Sin Cargar Sin Cargar
Sin Cargar
gjhgjh
49
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
SRT (Menor tiempo restante)
A B C D E
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
(proceso por lotes)
Trestante= 2 Trestante= 5
Trestante= 8 Sin Cargar
Sin Cargar
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
SRT (Menor tiempo restante)
A B C D E
5
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
(proceso por lotes)
Trestante= 2 Trestante= 4
Trestante= 8 Sin Cargar
Sin Cargar
gjhgjh
50
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
SRT (Menor tiempo restante)
A B C D E
5
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
(proceso por lotes)
Trestante= 1 Trestante= 4
Trestante= 8
Trestante= 6
Sin Cargar
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
SRT (Menor tiempo restante)
A B C D E
5 10 15 20 25 30 35 40 45
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
Terminó Trestante= 4
Trestante= 8
Trestante= 6
Sin Cargar
(proceso por lotes)
gjhgjh
51
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
SRT(Menor tiempo restante)
A B C D E
5
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
(proceso por lotes)
Terminó Trestante= 3
Trestante= 8
Trestante= 6
Trestante= 4
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
SRT(Menor tiempo restante)
A B C D E
5 10
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
(proceso por lotes)
Terminó Trestante= 2
Trestante= 8
Trestante= 6
Trestante= 4
gjhgjh
52
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
SRT(Menor tiempo restante)
A B C D E
5 10
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
(proceso por lotes)
Terminó Terminó
Trestante= 8
Trestante= 6
Trestante= 4
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
SRT (Menor tiempo restante)
A B C D E
5 10
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
(proceso por lotes)
Terminó Terminó
Trestante= 8
Trestante= 6
Trestante= 2
gjhgjh
53
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
SRT (Menor tiempo restante)
A B C D E
5 10 15
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
(proceso por lotes)
Terminó Terminó
Trestante= 8
Trestante= 4
Trestante= 2
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
SRT (Menor tiempo restante)
A B C D E
5 10 15
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
(proceso por lotes)
Terminó Terminó
Trestante= 8
Trestante= 4
Terminó
gjhgjh
54
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
SRT (Menor tiempo restante)
A B C D E
5 10 15 20
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
(proceso por lotes)
Terminó Terminó
Trestante= 8
Trestante= 1
Terminó
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
SRT (Menor tiempo restante)
A B C D E
5 10 15 20 25 30 35 40 45
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
(proceso por lotes)
gjhgjh
55
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
SRT (Menor tiempo restante)
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
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
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
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
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)
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
SRT (Menor Tiempo Restante)
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
SRT (Menor Tiempo Restante)
(proceso interactivo S1 = 3)
gjhgjh
57
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
SRT (Menor Tiempo Restante)
(proceso interactivo S1 = 3)
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
SRT (Menor Tiempo Restante)
(proceso interactivo S1 = 3)
gjhgjh
58
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
SRT (Menor Tiempo Restante)
(proceso interactivo S1 = 3) u=7 ?
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
SRT (Menor Tiempo Restante)
(proceso interactivo S1 = 3)
gjhgjh
59
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
SRT (Menor Tiempo Restante)
(proceso interactivo S1 = 3)
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
A B C D E
5 10 15 20 25 30 35 40 45
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
SRT (Menor Tiempo Restante)
(proceso interactivo S1 = 3)
S2 = 3, r = 3 Terminado S1 = 3, S2 = ? S1 = 3, r = 3 S1 = 3, r = 3
gjhgjh
60
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
A B C D E
5 10 15 20 25 30 35 40 45
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
SRT (Menor Tiempo Restante)
(proceso interactivo S1 = 3)
Terminado Terminado S1 = 3, S2 = ? S1 = 3, r = 3 S1 = 3, r = 3
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
Terminado Terminado S2 = 3.8, r = 3.8 S1 = 3, r = 1 S1 = 3, r = 3
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
SRT (Menor Tiempo Restante)
(proceso interactivo S1 = 3)
A B C D E
5 10 15 20 25 30 35 40 45
gjhgjh
61
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
Terminado Terminado S2 = 3.8, r = 3.8 S1 = 3, S2 = ? S1 = 3, r = 3
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
SRT (Menor Tiempo Restante)
(proceso interactivo S1 = 3)
A B C D E
5 10 15 20 25 30 35 40 45 50
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
SRT (Menor Tiempo Restante)
(proceso interactivo S1 = 3)
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
SRT (Menor Tiempo Restante)
(proceso interactivo S1 = 3)
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
SRT (Menor Tiempo Restante)
(proceso interactivo S1 = 3)
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
SRT (Menor Tiempo Restante)
(proceso interactivo S1 = 3)
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
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
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
SRT (Menor Tiempo Restante)
(proceso interactivo S1 = 3)
A B C D E
5 10 15 20 25 30 35 40 45
gjhgjh
64
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
SRT (Menor Tiempo Restante)
(proceso interactivo S1 = 3)
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
SRT (Menor tiempo restante)
• 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
Llegada Proceso Servicio
t. esperando + t.esperado t. esperado
gjhgjh
66
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
A B C D E
5 10 15 20 25 30 35 40 45
HRRN (Mayor tasa de respuesta)
En ejecución Listo En espera de E-S
Terminado
Sin Cargar
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
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
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
Realimentación multinivel (q=1)
En ejecución Listo En espera de E-S
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
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
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
1. Uso de CPU: 34 - 5 = 29/34 2. Rendimiento: 5/34 3. Tiempo de retorno (medio): (7 + 17 + 19 + 28 + 8) / 5 = 79 / 5 = 15.8 4. Tiempo de espera/respuesta (medio): (0 + 11 + 7 + 17 + 2) / 5 = 37 / 5 = 7.4
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
1. Uso de CPU: 30 - 1 = 29/30 2. Rendimiento: 5/30 3. Tiempo de retorno (medio): (21 + 23 + 24 + 18 + 11) / 5 = 97 / 5 = 19.4 4. Tiempo de espera/respuesta (medio): (14 + 17 + 12 + 13 + 6) / 5 = 62 / 5 = 12.4
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