Sistemas Operativos:

Planificación
Planificación de procesos en un procesador con núcleo único
Planificación: Repaso de Procesos

▪ Son programas en ejecución administrados por el SO

▪ “Viven” en memoria y se les va asignando el procesador (de a uno) para que
ejecuten sus instrucciones
▪ Pueden liberar (o deben liberar) el procesador cuando:
– Son expulsados (El SO pone límite al tiempo de ejecución –Temporización o Time Out)
– Liberan el procesador voluntariamente
▪ El Sistema Operativo los conoce y los administra
▪ Transitan diferentes Estados (Nuevo, Listo, Bloqueado, Suspendido, etc.)
▪ Overhead: Son las acciones administrativas realizadas por el SO para gestionar
procesos
▪ Desde hoy, vamos a decir también que los procesos son unidades de planificación
Planificación: Objetivos

Recordemos... ¿qué hace un SO? El planificador (o scheduler) tiene

Entre otras cosas, gestiona los como objetivo asignar procesos para
recursos y busca optimizarlos. ser ejecutados en la CPU
(administrando diferentes colas: Listos
¿Qué recursos? - Bloqueado) de forma que cumplan
Entre otros: sus objetivos bajo el control del SO.
- El o los procesadores
- Los dispositivos de E/S

¿Qué se quiere priorizar?

Eficiencia del CPU Rendimiento

Planificación: Criterios de Corto Plazo

Criterios de
Planificación a
Corto Plazo

Orientados al Sistema

Orientados al Usuario

Tiempo de Retorno Tiempo de Respuesta

(Turnaround Time) (Response Time) Equidad
Rendimiento

Prioridades
Fecha Tope (Deadlines) Previsibilidad Utilización del
Procesador

Equilibrio / Balance
Planificación: Criterio orientados al
usuario

▪ Tiempo de Retorno(Turnaround Time): Criterio a minimizar. Es el tiempo

transcurrido desde que se lanza un proceso hasta que finaliza (incluyendo
tiempos de ejecución y espera)
▪ Tiempo de Respuesta (Response Time): Criterio a minimizar. Para un
proceso inactivo, es el tiempo que transcurre desde que se lanza una
petición hasta que comienza a recibir la respuesta.
▪ Previsibilidad: Criterio a minimizar. El tiempo y trabajo de un proceso
debería tomar siempre el mismo tiempo en ser finalizado. Una gran variación
en el tiempo de respuesta o en el tiempo de retorno es malo desde el punto
de vista del usuario. (Afectado por la sobrecarga del sistema)
Planificación: Criterio orientados al
sistema

▪ Rendimiento: Criterio a maximizar. Se busca utilizar el procesador para completar

la mayor cantidad de procesos por unidad de tiempo (Ej.: 20 procesos en 1 min)
▪ Utilización del Procesador: Criterio a maximizar. Es el porcentaje de tiempo que el
procesador está ocupado.
▪ Equidad: Criterio a maximizar. Se espera que el sistema operativo planifique los
procesos en forma justa sin provocar inanición.
▪ Imposición de Prioridades: Criterio a maximizar. Si se asignan prioridades al los
procesos, la política del planificador debería favorecer a los procesos con
prioridades más altas.
▪ Equilibrado de Recursos: Criterio a maximizar. Ocupar los recursos lo máximo
posible, favoreciendo su uso por procesos que los requieran poco cuando tengan
mayor ocupación (Implica planificación de mediano y largo plazo también)
Planificación: Índices y Fórmulas de cálculo

Índice ID ¿Qué representa? Fórmula

Tiempo Inicial Ti Tiempo en que un proceso es admitido --
Tiempo Final Tf Tiempo en que el proceso finaliza --
Tiempo de Retorno Tt Tiempo que un proceso permanece en el sistema Tt = Tf - Ti
Tiempo de Servicio Ts Tiempo dedicado a tareas productivas (CPU, E/S) Ts = Tcpu + TE/S
Tiempo de Espera Te Tiempo que un proceso pasa en colas de espera Te = Tt – Ts
Tiempo transcurrido entre la primera solicitud de
Tiempo de Respuesta Tr --
un proceso y la respuesta del SO
Tiempo de Retorno
Tn Indica el retardo experimentado Tn = Tt / Ts
Normalizado
Planificación: Planificadores según el plazo

▪ Planificador a Corto Plazo (Dispatcher): Toma

la decisión sobre cuál será el siguiente proceso a
ejecutar, como también cuál se debe expulsar Ejecutando

▪ Planificador a Mediano Plazo: Decide qué Listo

imágenes de procesos traerá o quitará de la
memoria principal. Utiliza el intercambio
Bloqueado
(Swapping) para ejecutar su rol.
▪ Planificador de Largo Plazo: Decide qué Bloqueado/
Suspendido

procesos serán Admitidos en el sistema. Listo/

Controla el Grado de Multiprogramación del Suspendido

sistema.
Nuevo Salida
Planificación: Planificador de Largo Plazo

Nuevo

Admisión Admisión

Listo /
Suspendido
Listo Ejecutando Salida Saliente

Bloqueado /
Suspendido
Bloqueado
Planificación: Planificador de Largo Plazo
● Debe tomar la decisión de si se agregará un Proceso finaliza -> disminuye grado multiprogramación
nuevo proceso al conjunto de procesos que
están Admitidos
Monitoreo uso CPU -> cierto tiempo CPU IDLE
● Se ejecuta cuando un nuevo proceso es creado.
o Decide en qué momento se puede cargar
un nuevo proceso Trabajo de Alta Prioridad
○ Decide qué trabajo será aceptado y
convertido en proceso (o procesos)
CPU
Según prioridad de Trabajo BOUND

Buena mezcla de procesos

IO BOUND

Optimizar performance
Planificación: Planificador de Largo Plazo

● Controla el grado de multiprogramación del sistema

Grado de multiprogramación bajo ● CPU ociosa

● CPU no ociosa
Grado de multiprogramación alto ● Menor % CPU para
cada proceso

Brindar un servicio satisfactorio a los procesos

LISTOS
Planificación: Planificador de Mediano Plazo

Nuevo

Suspensión
Reactivación
Listo /
Suspendido
Listo Ejecutando Saliente

Suspensión
Sucede
Evento

Reactivación

Bloqueado /
Suspendido
Bloqueado

Suspensión
Planificación: Planificador de Mediano Plazo

● Debe realizar operaciones de swapping (intercambio) -> IN/OUT

● Debe tomar la decisión de si es necesario suspender un proceso ->
almacenamiento secundario.
● Modifica el grado de multiprogramación -> tratando de lograr una buena
mezcla de procesos CPU/IO BOUND
○ SWAP IN -> aumento
○ SWAP OUT -> disminución
P1 P2
P1

P2
NOTA: El almacenamiento secundario
NO es memoria principal, es en disco. RAM SWAP
Se ve en la unidad de Memoria Virtual
con más detalle.
Planificación: Planificador de Mediano Plazo
Ejemplos:

Muchos procesos Todos bloqueados -> Suspender procesos + cargar

IO BOUND CPU IDLE procesos CPU BOUND desde swap

Suspender procesos + cargar

Muchos procesos
Mal uso dispositivos procesos IO BOUND desde
CPU BOUND
swap

Proceso mayor Suspender un proceso y

prioridad + sin RAM cargar al de > prioridad

Proceso suspendido se está por Cargar proceso en RAM para acelerar

desbloquear + RAM libre su vuelta en ejecución
Planificación: Planificador de Corto Plazo

Nuevo

Listo /
Suspendido
Listo Activación Ejecutando Saliente

Temporización
Sucede
Evento

Espera
Bloqueado /
Bloqueado por evento
Suspendido
(Bloqueo)
Planificación: Planificador de Corto Plazo

● Se ejecuta con mayor frecuencia que el resto -> debe tomar buenas
decisiones + el overhead debe ser mínimo

Eventos a tener en cuenta

Siempre a tener en cuenta:

➔ Proceso finaliza ( Ejecutando -> Saliente) CPU
➔ Proceso se bloquea (Ejecutando -> Bloqueado) LIBERADA
➔ Proceso cede voluntariamente CPU ( Ejecutando -> Listo)

Pueden ser considerados

➔ Proceso recibe evento esperado (Bloqueado -> Listo) Puede convenir
➔ Proceso nuevo (Syscall : Nuevo -> Listo) elegir otro proceso
➔ Interrupción por timer
Planificación: Consecuencias cuando es mala

“Cualquier similitud
con la realidad, es pura
coincidencia.”
Planificación: ¿Preguntas?

El profe de explicando
Planificación y vos
tipo…
Políticas de Planificación
Detalle de las políticas de Planificación a corto plazo y sus diferencias
Planificación: Tipos de Planificadores

Dependiendo de qué eventos tenga en cuenta un algoritmo de planificación de

corto plazo se clasificará en :

Los planificadores que no permiten la expulsión del proceso que se encuentra

actualmente usando el CPU son llamados Sin desalojo / Apropiativos / Non-
preemptive ya que esperan a que el proceso le devuelva el control al SO para elegir
otro proceso a ejecutar.

Los planificadores permiten la expulsión del proceso que se encuentra actualmente

usando el CPU son llamados Con desalojo / No-Apropiativo / Preemptive ya que
pueden interrumpir la ejecución de un proceso (desalojarlo de CPU -> vuelta a Listos)
para ejecutar otro más prioritario, o el siguiente en la cola de Listos
Planificación: Políticas de Planificación

1. Primero en llegar primero en ser servido (FCFS)/(FIFO)

2. Turno rotativo (Round Robin o RR)
3. Turno rotativo virtual (Virtual Round Robin o VRR)
4. Primero el proceso más corto (SJF sin desalojo o SPN)
5. Menor tiempo restante (SJF con desalojo o SRT)
6. Mayor tasa de respuesta (HRRN)
7. Realimentación (Feedback)
8. Prioridades (con y sin desalojo)

SJF: Shortest Job First | SPN: Shortest Process Next | SRT: Shortest Remaining Time
Planificación: Ejemplo de Ejercicio
¿Cómo encarar los ejercicios? Se brindará una tabla como la siguiente:

Proceso T. Llegada T. CPU

• Se representa en una línea las ejecuciones de tu proceso X.
A 0 3
• Se asume un único CPU a menos que el enunciado lo afirme.
B 2 6
• Se van ejecutando los procesos según la duración de la
C 4 4
tabla, la llegada del mismo, y el algoritmo utilizado.
D 6 5
E 8 2
Tus procesos:

IMPORTANTE:
Prioridad ante una simultaneidad de
eventos en ej. de planificación:
1. Interrupción por temporización. Uso de CPU en el Tiempo
2. Interrupción por E/S.
3. Excepciones tipo (Trap)
(Salvo que el ejercicio indique otro orden)
1) Política FCFS: First Come First Served
Atención por orden de llegada (FIFO)

Proceso T. Llegada T. CPU • Política sin desalojo

A 0 3 • Todos los proceso entran a la cola de listos.
B 2 6 • Cuando el proceso actual deja de correr, el siguiente
C 4 4 proceso en la cola de listos es seleccionado.
D 6 5 • Un pequeño grupo de procesos puede esperar largos
E 8 2 periodos de tiempo antes de ser ejecutados.
• Favorece los proceso con carga del procesador en lugar
los que tienen carga de E/S.

(tiempos de llegada de los procesos)

2) Política RR: Round Robin o Turno
Rotatorio

Proceso T. Llegada T. CPU • Prevención del uso basada en un reloj.

A 0 3 • Cada quantum de tiempo un proceso usa la CPU
B 2 6 • Las interrupciones de reloj se generan en intervalos fijos
C 4 4 • Cuando ocurre una interrupción, el proceso en ejecución es
D 6 5 colocado en la cola de listos y el siguiente proceso es
E 8 2 seleccionado.
Quantum = Q = 1
3) Política VRR: Virtual Round Robin o Turno
Rotatorio Virtual

• Planifica similar a Round Robin,

pero la cola de bloqueados tiene
prioridad sobre la cola de listos.
• Se implementa a través de una cola
auxiliar.
• Si hay procesos en la Cola Auxiliar,
se ejecutarán antes de volver a
tomar procesos de la Cola de Listos
4) Política SPN: Shotest Process Next
(Equivale a SJF Sin desalojo)

Proceso T. Llegada T. CPU • Política sin desalojo

A 0 3 • Proceso con tiempo esperado más corto es seleccionado.
B 2 6 • Los procesos pequeños saltan delante de los grandes.
C 4 4 • La predictibilidad de los procesos grandes es reducida
D 6 5 (Predictability)
E 8 2 • Si el tiempo estimado es incorrecto, el SO puede
abortarlo
• Posibilidad de inanición de los procesos grandes.
5) Política SRT: Shortest Remaining Time
(Equivale a SJF Con desalojo)

Proceso T. Llegada T. CPU • Política con desalojo

A 0 3 • Versión preventiva de la política el siguiente proceso
B 2 6 más corto
C 4 4 • Elige proceso que le queda menos tiempo esperado de
D 6 5 ejecución
E 8 2 • Existe riesgo de inanición para procesos largos
6) Política HRRN: Highest Ratio Response
Next (Mayor tasa de respuesta)

Proceso T. Llegada T. CPU • Es una adaptación del SJF que permite romper la inanición.
A 0 3 • Se prioriza a los procesos con mayor tasa de respuesta
B 2 6 (Response Ratio): R.R. = (S + W) / S
C 4 4 • S = Tiempo de servicio (próxima ráfaga)
D 6 5 • W = Espera
E 8 2 • Cuanto mayor sea la espera, respecto al tamaño de su
ráfaga, mayor será su prioridad para ejecutar
7) Política Feedback: Retroalimentación de
nivel múltiple

▪ Penaliza los trabajos que han

corrido más tiempo (Q). Nuevo

▪ Si no se conoce el tiempo de
ejecución restante, entonces es Nivel 0: RR Pn Pn-1 P1 CPU
mejor utilizar el tiempo de ejecución
consumido hasta el momento

▪ Mecanismo dinámico de Nivel 1: RR

prioridades: varias colas de listos de Pn Pn-1 P1 CPU
acuerdo a prioridad
Saliente
▪ Entra 1ra vez cola RQ0 Nivel 2: RR
Pn Pn-1 P1 CPU
▪ Luego de la ejecución i a cola
prioridad i – 1
Nivel 0:
▪ Favorece procesos cortos y nuevos FCFS
frente a los mas viejos y largos Pn Pn-1 P1 CPU
8) Política por Prioridades

● Se asocia con cada proceso una prioridad (número entero)

● La CPU se asigna al proceso con la prioridad más alta (consideramos número pequeño ≡
prioridad alta)
● Tenemos dos posibilidades:
● Expropiativo
● No expropiativo
● SJF se puede ver como un algoritmo de planificación por prioridad en el que la prioridad es
la duración predicha para la siguiente ráfaga de CPU
● Problema: Inanición (starvation) – los procesos de más baja prioridad podrían no ejecutarse
nunca
● Solución: Envejecimiento (aging) – conforme el tiempo pasa aumentar la prioridad de los
procesos que esperan mucho en el sistema
Planificación: Resumen de Políticas

# Algoritmo Justicia / Equidad Overhead ¿Con desalojo? Inanición

1 FCFS (FIFO) Poca Poco No No
Depende del
2 Round Robin Alta Sí No
quantum
Depende del
3 Virtual Round Robin Alta Sí No
quantum y E/S
4 Shortest Process Next (SPN) Media Medio No Sí
5 Shortest Remaining Time (SRT) Media / Alta Medio Sí Sí
6 Highest Ratio Response Next (HRRN) Casi RR Medio No No
7 Feedback* -- Medio -- --
8 Prioridades (con desalojo) Poca Medio Si Si
9 Prioridades (sin desalojo) Poca Bajo No Si

* La política de Feedback puede tener distintos planificadores por cada cola. La Justicia/Equidad, el desalojo y la inanición
dependerán de las mismas.
Planificación: Ejemplo complejo
Construir el diagrama de Gannt
de la siguiente secuencia de
Procesos, planificados con RR
Q=2

Pr Admisión CPU Disco CPU Red CPU

A 0 3 2 1 1 1
B 1 1 3 2 2 1
C 2 2 1 3 3 1
Planificación: ¿Preguntas?