Sistemas
Operativos
UNIDAD 3
PLANIFICACIÓN DE PROCESOS
SISTEMAS OPERATIVOS - PLANIFICACIÓN DE PROCESOS
Multiprogamación y Planificación
Sistema multiprogramado: varios procesos
La clave de la multiprogramación es la planificación de CPU para mejorar:
◦ Tiempo de respuesta.
◦ Productividad.
◦ Eficiencia del procesador.
Elementos del núcleo del S.O. relacionados
◦ CPU Scheduler: Planificador
◦ Dispatcher: Despachador
◦ Interrupt Handler: Manejador de Interrupciones
-
Frecuencia de ejecución
+
Estados y planificadores
Grafo transiciones entre estados y
niveles de planificación:
El planificador a medio plazo es parte de la
función de intercambio (swapping function)
SISTEMAS OPERATIVOS - PLANIFICACIÓN DE PROCESOS
Modelo de colas de planificación
SISTEMAS OPERATIVOS - PLANIFICACIÓN DE PROCESOS
Planificador a Largo Plazo
Objetivos de la planificación a largo plazo:
◦ Controlar el grado de multiprogramación mediante la admisión de nuevos programas en:
◦ Listo (cola de corto plazo) Memoria
◦ Listo Suspendido (cola de medio plazo) Zona de Intercambio
Sistemas de proceso por Lotes (o parte Lotes Sistema Generalista)
◦ Los procesos se incorporan a la cola de procesos por lotes en disco.
◦ De la cola de proceso por lotes a Listo. Decisiones: • Si se admiten muchos trabajos se reduce
◦ Si el SO puede acoger a más procesos en Listo el tiempo de servicio y los procesos
compiten por el tiempo
◦ Control del Grado de Multiprogramación
• Si el procesador está mucho tiempo
◦ Decidir cual será el elegido de la cola de lotes. ocioso se llama al planificador a largo
◦ Por un algoritmo de planificación plazo.
◦ Por una herramienta de rendimiento
◦ Por planificación de E/S
Sistemas Interactivos
◦ Cuando un usuario intenta conectarse se crea una solicitud al planificador a largo plazo.
◦ Se aceptan todas hasta un límite. Se informa de sistema saturado.
SISTEMAS OPERATIVOS - PLANIFICACIÓN DE PROCESOS
Planificadores medio y corto plazo
La Planificación a medio plazo
◦ Forma parte de la función de intercambio.
Planificación a Corto Plazo.
◦ Objetivos:
◦ Justicia: todos los procesos sean tratados por igual
◦ Optimizar el uso de recursos: Uso del procesador y operaciones E/S
◦ Evitar la sobrecarga del sistema
◦ Evitar inanición de procesos
◦ Evitar la degradación paulatina
◦ Se ejecuta siempre que un proceso abandona la CPU, por:
◦ Interrupción de reloj.
◦ Interrupción de E/S
◦ Llamadas al Sistema Operativo
◦ Señales
SISTEMAS OPERATIVOS - PLANIFICACIÓN DE PROCESOS
Criterios de planificación a corto plazo
Orientados al Usuario Orientados al Sistema
Prestaciones Otros Prestaciones Otros
Tiempo de estancia Previsibilidad Rendimiento Equidad
Desde que se lanza hasta Un proceso debería tardar Numero de procesos Los procesos deben de ser
que finaliza. aprox. siempre lo mismo y completados por unidad de tratados de igual forma,
Trabajos por lotes. con el mismo coste, tiempo. Mide el trabajo que ninguno de be sufrir de
independientemente de la esta siendo realizado. inanición
Tiempo de respuesta carga del sistema.
Desde que se lanza la Utilización del procesador Imposición de Prioridades
petición hasta que se Porcentaje de tiempo que el Si se determinan prioridades
obtienen resultados. procesador está ocupado el planificador debe
Sistemas Interactivos. favorecer a los procesos en
función de su prioridad
Fecha Tope
Si se especifica hay que Equilibrado de recursos
maximizar el porcentaje de Se debe mantener ocupados
deadlines conseguidos los recursos del sistema.
Favorecer procesos con
poca carga de recursos
cuando estos están muy
ocupados.
SISTEMAS OPERATIVOS - PLANIFICACIÓN DE PROCESOS
Criterios de planificación a corto plazo
Criterios de planificación (corto plazo):
◦ Utilización de CPU Ver:
Planificación de procesos: Evaluación del rendimiento
◦ % de tiempo que la CPU está ocupada
◦ Maximizar
Algunos objetivos son incompatibles entre si, por lo
◦ Productividad (throughput) que nos centraremos en optimizar el que más nos
◦ Nº procesos terminados por unidad de tiempo interese dependiendo del tipo de sistema:
◦ Maximizar • Sistemas interactivos: tiempo de respuesta
• Sistemas por lotes (batch): tiempo de retorno
◦ Tiempo de retorno
◦ Intervalo entre el lanzamiento de un proceso y su
finalización Los Algoritmos se pueden clasificar por grupos en
función de la forma de abandonar la CPU:
◦ Suma del tiempo de ejecución real + tiempo consumido en • Sin reciclaje de procesos (no preemtiva).
espera por recursos (inc. Procesador) Abandono no forzoso.
◦ Minimizar • Con reciclaje de procesos (preemtiva).
Abandono forzoso
◦ Tiempo de respuesta
◦ Intervalo de tiempo transcurrido desde que se emite una
solicitud hasta que se comienza a recibir respuesta
◦ Minimizar
◦ Tiempo de espera
◦ Total del tiempo que el proceso está esperando por algún
recurso incluido el procesador
◦ Minimizar
◦ Para comparar los distintos algoritmos:
◦ media
◦ varianza
SISTEMAS OPERATIVOS - PLANIFICACIÓN DE PROCESOS
Algoritmos de Planificación de Procesos
La decisión de planificación puede ocurrir:
a) Cuando un proceso pasa de ejecución a espera
b) Cuando un proceso termina
c) Cuando un proceso pasa de ejecución a listo
d) Cuando un proceso pasa de espera a listo
e) Cuando llega una interrupción
f) Periódicamente
Los Algoritmos se pueden clasificar por grupos en función de la forma de abandonar la CPU:
SISTEMAS OPERATIVOS - PLANIFICACIÓN DE PROCESOS
Algoritmos de Planificación de Procesos
SISTEMAS OPERATIVOS - PLANIFICACIÓN DE PROCESOS
Planificación de procesos - Algoritmos
1. FCFS (First Come, First Served):
◦ Política no preemtiva
◦ La cola de preparados es FIFO
◦ Abandona la CPU cuando:
◦ Realiza una llamada al sistema (operación de E/S, ..)
◦ Termina
◦ Cuando el proceso actual cesa su ejecución, se selecciona el proceso más antiguo
de la cola.
Ventajas:
◦ No hay posposiciones indefinidas (inanición)
Inconvenientes:
◦ Favorece a los procesos largos: puede que un proceso corto tenga que esperar mucho
tiempo
◦ Favorece a los procesos con carga de CPU: los procesos con carga de E/S tienen que
esperar a que se completen los procesos con carga de CPU.
◦ No son válidos para sistemas de tiempo compartido
(multiusuario)
SISTEMAS OPERATIVOS - TEMA 2 11
Planificación de procesos - Algoritmos
1. FCFS: Proceso Instante de llegada Tiempo de servicio
1
2
3
4
Preparado 5
0 5 10 15 20
1
2
3
4
5
SISTEMAS OPERATIVOS - TEMA 2 12
Planificación de procesos - Algoritmos
Desv. Est.
2,05
12,08
12,08
SISTEMAS OPERATIVOS - TEMA 2 13
Planificación de procesos - Algoritmos
Desv. Est.
11,81
2,05
2,05
SISTEMAS OPERATIVOS - TEMA 2 14
Planificación de procesos - Algoritmos
2. SPN (Shortest Process Next):
◦ Política no preemtiva
◦ Abandona la CPU cuando:
◦ Realiza una llamada al sistema (operación de E/S, ..)
◦ Termina
◦ Se selecciona el proceso con menor tiempo esperado de ejecución.
◦ Un proceso corto saltará a la cabeza de la cola, sobrepasando a trabajos largos.
Ventajas:
◦ Siempre obtendremos el mínimo tiempo medio de respuesta
Inconvenientes:
◦ Los procesos largos se penalizan (inanición)
◦ Casi nunca es posible conocer de antemano el tiempo de ejecución de
cada proceso, por lo que se recurre a estimaciones de ese tiempo.
SISTEMAS OPERATIVOS - TEMA 2 15
Planificación de procesos - Algoritmos
2. SPN: Proceso Instante de llegada Tiempo de servicio
1
2
3
4
Preparado 5
0 5 10 15 20
1
2
3
4
5
SISTEMAS OPERATIVOS - TEMA 2 16
Planificación de procesos - Algoritmos
Desv. Est.
12,08
2,05
2,05
SISTEMAS OPERATIVOS - TEMA 2 17
Planificación de procesos - Algoritmos
3. Uso de prioridades:
◦ Política no preemtiva
◦ Tiene múltiples colas de “preparados” para representar cada nivel de prioridad
◦ Un proceso no se ejecutará mientras haya procesos de mayor prioridad esperando
◦ Abandona la CPU cuando:
◦ Realiza una llamada al sistema (operación de E/S, ..)
◦ Termina
◦ Los procesos de prioridad más baja pueden sufrir inanición:
◦ Permite que un proceso cambie su prioridad en función de su edad o su historial de ejecución.
SISTEMAS OPERATIVOS - TEMA 2 18
Planificación de procesos - Algoritmos
4. RR (Round Robin) o turno rotatorio:
◦ Política apropiativa (preeemtiva)
◦ Asignación de intervalo de tiempo: quantum
◦ Es el más sencillo y justo
◦ La cola de preparados se gestiona como si fuera una cola FIFO circular.
◦ Habiendo n procesos, un proceso no esperará mas de (n-1)q unidades de tiempo, siendo
q la duración del quantum.
◦ Abandona la CPU cuando:
◦ Realiza una llamada al sistema (operación de E/S, ..)
◦ Termina
◦ Agotamiento de quantum
◦ El quantum puede ser fijo o variable durante la vida de un proceso.
◦ Hay que buscar el equilibrio en la duración del quantum
Ventajas:
◦ No hay posposiciones indefinidas (inanición)
◦ Especialmente diseñado para sistemas de tiempo compartido (multiusuario)
Inconvenientes:
◦ Rendimiento pobre de los procesos que realizan muchas operaciones de E/S, con el consiguiente desaprovechamiento de los dispositivos de E/S.
¡ El valor del quantum es muy importante !
SISTEMAS OPERATIVOS - TEMA 2 19
Planificación de procesos - Algoritmos
RR (q=1): Proceso Instante de llegada Tiempo de servicio
1
2
3
4
Preparado 5
0 5 10 15 20
1
2
3
4
5
SISTEMAS OPERATIVOS - TEMA 2 20
Planificación de procesos - Algoritmos
RR (q=4): Proceso Instante de llegada Tiempo de servicio
1
2
3
4
5
0 5 10 15 20
1
2
3
4
5
SISTEMAS OPERATIVOS - TEMA 2 21
Planificación de procesos - Algoritmos
EJERCICIO
SISTEMAS OPERATIVOS - TEMA 2 22
Planificación de procesos - Algoritmos
5. SRTN (Shortest Remaining Time Next):
◦ Es una versión apropiativa de la política de SPN (primero el proceso más corto).
◦ Debe estimar el tiempo de proceso.
◦ Abandona la CPU cuando:
◦ Realiza una llamada al sistema (operación de E/S, ..)
◦ Termina
◦ Al ser apropiativo, si llega un proceso más corto que el que actualmente está en ejecución se selecciona.
SISTEMAS OPERATIVOS - TEMA 2 23
Planificación de procesos - Algoritmos
SRTN: Proceso Instante de llegada Tiempo de servicio
1
2
3
4
Preparado 5
0 5 10 15 20
1
2
3
4
5
SISTEMAS OPERATIVOS - TEMA 2 24
Planificación de procesos - Algoritmos
6. Uso de prioridades:
◦ Prioridades apropiativo
◦ Abandona la CPU cuando:
◦ Realiza una llamada al sistema (operación de E/S, ..)
◦ Termina
◦ Al ser apropiativo, si llega un proceso con mayor prioridad que el que actualmente está en ejecución. Se asignaría el
procesador directamente al nuevo proceso, en vez de esperar el primero en la cola de preparados, tal y como haría el
algoritmo por prioridades no apropiativo.
SISTEMAS OPERATIVOS - TEMA 2 26
Planificación de procesos - Algoritmos
7. MLQ (Multiple Level Queues):
◦ Política apropiativa (preemtiva)
◦ Apropiado cuando los diferentes procesos son fácilmente clasificables en diferentes grupos:
Foreground (interactivos) / Background (por lotes)
◦ Tendremos distintas colas de preparado, con una prioridad distinta y algoritmo de
planificación común o diferente.
◦ No se podrá ejecutar ningún proceso de una cola mientras queden procesos en colas de
mayor prioridad.
MLQ Inconvenientes:
◦ Puede haber inanición para los procesos de menor prioridad si continuamente están llegando
procesos de mayor prioridad.
SISTEMAS OPERATIVOS - TEMA 2 27
Planificación de procesos - Algoritmos
Colas de prioridad
SISTEMAS OPERATIVOS - TEMA 2 28
Planificación de procesos - Algoritmos
8. MLQ con realimentación:
◦ Política apropiativa (preemtiva)
◦ Soluciona el problema de inanición del algoritmo anterior.
◦ Penaliza a los trabajos que han estado ejecutándose durante más tiempo (cambiando a colas
de menor prioridad)
◦ No se conoce el tiempo de ejecución restante del proceso.
Inconvenientes:
◦ Este algoritmo es el más complejo de todos
Ventajas:
◦ Es el más general, ya que estableciendo los parámetros correctos podremos simular
cualquier otro algoritmo:
◦ Número de colas
◦ Algoritmo de planificación de cada cola
◦ Métodos para mover los procesos de cola (a mayor o a menor prioridad)
SISTEMAS OPERATIVOS - TEMA 2 29
Planificación de procesos - Algoritmos
SISTEMAS OPERATIVOS - TEMA 2 30
Planificación de procesos - Algoritmos
MLQ (q=2i): Proceso Instante de llegada Tiempo de servicio
1
2
3
4
Preparado 5
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1
2
3
4
5
SISTEMAS OPERATIVOS - TEMA 2 32
Planificación de procesos - Algoritmos
Proceso Tiempo de llegada Duración de ráfaga de CPU
P0 0 8
P1 1 4
P2 3 2
Ejercicio: P3 5 3
◦ Diagrama de gant
◦ Tiempo medio de retorno
◦ Tiempo medio de espera
◦ Eficiencia media
◦ Con:
◦ FIFO
◦ SRTF (expulsivo)
◦ SJF (no expulsivo)
◦ SJF (expulsivo)
◦ RR q=2, q=4
◦ MLQ con realimentación q=2^n
SISTEMAS OPERATIVOS - TEMA 2 33
Planificación de procesos - Algoritmos
Ejercicio:
◦ Diagrama de Gant
◦ Tiempo medio de retorno
◦ Tiempo medio de espera
◦ Eficiencia media (los trabajos llegan en el orden de la tabla. Prioridad max=1)
◦ Con:
◦ FIFO Trabajos - LLegada Unidades tiempo Prioridad
◦ SRTF (expulsivo) 1–2 8 2
◦ SJF (no expulsivo) 2–0 5 4
◦ SJF (expulsivo) 3–8 7 2
◦ Prioridades (no expulsiva) 4–3 2 3
◦ Prioridades (expulsiva)
◦ RR q=4, q=2
◦ MLQ con realimentación q=2^n
SISTEMAS OPERATIVOS - TEMA 2 34
Planificación de procesos - Algoritmos
Ejercicio:
• Uso CPU
(Ttotal-Tociosa)/Ttotal
• Uso efectivo CPU
Tcputareas/Ttotal
• Sobrecarga SO
Tcambio/Ttotal
SISTEMAS OPERATIVOS - TEMA 2 35
Planificación de procesos - Algoritmos
Ejercicio:
◦ Sea un sistema que usa un algoritmo de planificación Round-Robin con
quantum=100ms.
◦ El sistema ejecuta 2 procesos
◦ El primer proceso P1 no utiliza E/S
◦ El segundo proceso P2 solicita E/S cada 50ms.
◦ ¿Cuál es el porcentaje de utilización de la CPU?
◦ Representa el cronograma de ejecución.
SISTEMAS OPERATIVOS - TEMA 2 36
Fin
UNIDAD 3
PLANIFICACIÓN DE PROCESOS
SISTEMAS OPERATIVOS - PLANIFICACIÓN DE PROCESOS
