Sistemas Operativos II

Hugo Carrer

2020
Planificación

I Una de las principales tareas del sistema operativo es

repartir los recursos del sistema entre los diferentes
procesos que compiten por el acceso a los mismos
I Uno de estos recursos es el tiempo del procesador
I Este recurso en particular se distribuye por medio de un
plan o cronograma definido por el planificador
I El objetivo de la planificación es repartir el tiempo del
procesador entre los diferentes procesos de una manera
que cumpla con los requerimientos del sistema, tales
como, tiempo de respuesta, productividad, o eficiencia en
el uso del procesador, etc.
Planificación
La función de planificación debería,
I Repartir el tiempo del procesador de manera justa entre
los procesos
I Prevenir la inanición de los procesos
I Usar el procesador de manera eficiente
I Tener poco overhead
I Proveer la opción de priorizar algún proceso cuando sea
necesario
Diagrama de Estados y Planificación
Diagrama de Colas y Planificación
Planificación de Largo Plazo

I La planificación de largo plazo controla la creación de

procesos, es decir que controla el grado de
multiprogramación
I Una vez aceptado y dependiendo del sistema, el proceso
puede ser incluído en la cola de procesos listos o bien
puede ser iniciado en estado suspendido
I En un sistema de trabajos por lotes el trabajo es agregado
al grupo del próximo lote y mantenido en el disco hasta
que el planificador de largo plazo decida crear un proceso
nuevo para este trabajo
I Vemos que el planificador debe tomar 2 decisiones,
I Cuándo el SO puede crear nuevos procesos
I Cuál de los trabajos a realizar se convertirá en el próximo
proceso
Planificación de Largo Plazo

I La primera decisión depende del grado deseado de

multiprogramación
I Suponiendo que no hay problemas de memoria la cantidad
de procesos incide en el tiempo de procesador que le toca
a cada proceso
I La segunda decisión dijimos que involucra cual de los
programas disponibles será convertido en un proceso
I FIFO?
I Prioridades?
I Tiempo esperado de ejecución?
I etc.
Planificación de Mediano Plazo

I Afecta las decisiones de suspensión de procesos

I Las decisiones de suspender o llevar procesos a memoria
principal se toman en función de la necesidad de controlar
también el grado de multiprogramación
Planificación de Corto Plazo

I Este planificador se conoce usualmente como el scheduler

propiamente dicho
I Se ejecuta cada vez que ocurre algun evento, por ejemplo
I Interrupciones de reloj
I Interrupciones de E/S
I Llamadas al sistema operativo
I Señales, como semáforos por ejemplo
Planificación de Corto Plazo

I El objetivo principal es distribuir el uso del procesador para

poder optimizar algun aspecto particular del sistema
I La primera división con respecto al criterio puede ser entre
requerimientos de usuario y requerimientos del sistema
I Un ejemplo de requerimiento desde el pto de vista del
usuario es el tiempo de respuesta, se puede definir el
objetivo de maximizar la cantidad de usuarios que
experimentan un tiempo de respuesta menor a x segundos
I Un ejemplo de requerimiento desde el pto de vista del
sistema es el nro. de procesos completados por unidad de
tiempo. Este es un criterio interesante para el
administrador o dueño del sistema pero no
necesariamemnte para un usuario particular
I Veamos algunos ejemplos de criterios válidos
Criterios de Planificación de Corto Plazo
Orientados a usuario, desempeño
I Tiempo de retorno, es el tiempo transcurrido entre la
generación de un proceso y su finalización. Incluye todas
las esperas
I Tiempo de respuesta, para un proceso interactivo es el
tiempo entre que el usuario genera un pedido y comienza
a recibir la respuesta
I Límites, en los casos en los que se puede definir un límite
de tiempo el planificador debe maximizar el porcentaje de
procesos que cumplen con los límites

Orientados al usuario, otros

I Consistencia, un mismo proceso debería volver a correr en
aproximadamente la misma cantidad de tiempo
independientemente de la carga del sistema
Criterios de Planificación de Corto Plazo
Orientados al sistema, desempeño
I Productividad, la política de planificación debe tratar de
maximizar la cantidad de trabajos completados por unidad
de tiempo
I Utilización, en algunos casos en los que el costo es
significativo entonces la carga del procesador es un
parámetro importante. Mantener el procesador ocupado

Orientados al sistema, otros

I Equitatividad, siendo todas las condiciones iguales todos
los procesos deberían ser tratados por igual y ningún
proceso debe sufrir inanición
I Prioridades, en caso de existir el planificador debe
respetar las prioridades
I Recursos, en general el planificador debe mantener
ocupados todos los recursos del sistema sin saturarlos
Ejemplo de Prioridades

I En un sistema con prioridades para los procesos el

planificador debe elegir para la ejecución el proceso que
tenga mayor prioridad
I Hay que verificar que no pueda ocurrir la inanición de los
procesos de menor prioridad
Ejemplo de Prioridades
Políticas de Planificación
Políticas de Planificación

I w representa el tiempo que el proceso ha estado en el

sistema hasta el momento, esperando
I e representa el tiempo que el proceso ha estado
ejecutándose hasta el momento
I s representa el tiempo total de servicio requerido por el
proceso
I El modo de decisión puede ser no preferente o preferente
I Preferente El proceso actualmente en ejecución puede ser
interrumpido y llevado nuevamente al estado de listo
I No preferente, en este caso una vez que un proceso se
está ejecutando solo se detiene si termina o si se bloquea
Políticas de Planificación

Veamos algunos ejemplos para comprender mejor las

diferentes políticas
Primero en Llegar Primero en Servir

I Sistema de cola puro

I No preferente
I Favorece procesos intensivos en el uso del CPU. Un
proceso corto debe esperar mucho en relación con su
tiempo de ejecución
Round Robin

I Preferente basado en un reloj que interrumpe la ejecución

I El proceso interrumpido es puesto de vuelta en la cola de
listos y se ejecuta el próximo proceso en la cola
Efecto del Tiempo entre Interrupciones
Efecto del Tiempo entre Interrupciones
Round Robin Virtual
Primero el Proceso más Corto

I No preferente
I Se elige para ejecutar el proceso con el tiempo de
procesamiento esperado mas corto
I Puede haber inanición de los procesos mas largos
I Hay que estimar la duración de cada proceso
Primero Menor Tiempo Restante

I Versión preferente del anterior

I Hay que estimar el tiempo restante de ejecución de cada
proceso
Primero el de Mayor Tasa de Respuesta

I Elige el proceso con mayor R,

w+s
R= s
Realimentado
Realimentado

I Penaliza gradualmente aquellos procesos que hace más

tiempo que se están ejecutando
I Con la llegada de nuevos procesos puede producirse
inanición de procesos antiguos
Planificación Justa
I Las aplicaciones de los usuarios son un conjunto de
procesos o threads
I El usuario está interesado en la performance del conjunto
I Resulta interesante tomar decisiones de planificación en
función de esto
I Lo mismo aplica a grupos de usuarios con diferentes
intereses
I El tiempo se divide equitativamente entre grupos
considerando su prioridad relativa
I Un usuario afecta la prioridad de su grupo y no la del
conjunto de todos los usuarios
CPUj (i − 1)
CPUj (i) = (1)
2
GCPUk (i − 1)
GCPUk (i) = (2)
2
CPUj (i) GCPUk (i)
Pj (i) = Basej + + (3)
2 4Wk
Planificación Justa
Planificación Tradicional en UNIX
I Es el planificador usado en los sistemas SVR3 y BSD4.3
I El objetivo principal es el funcionamiento de tiempo
compartido interactivo
I Si bien ha sido reemplazado en los sistemas modernos es
interesante estudiarlo como un ejemplo de un sistema real
I Es un sistema realimentado multinivel con turno rotatorio
para cada cola de prioridad
I Es un sistema preferente con tiempo límite de 1 segundo
CPUj (i − 1)
CPUj (i) = (4)
2
CPUj (i)
Pj (i) = Basej + + nicej (5)
2

I La prioridad base divide los procesos en bandas de

prioridad
I Los valores de CPU y nice tienen restricciones para evitar
cambios de banda
Planificación Tradicional en UNIX

I Las bandas de prioridad están definidas por el valor del

parametro Base
I Se utilizan para optimizar el acceso a dispositivos de
bloque como el almacenamiento secundario y permitir que
el SO responda rápidamente a llamadas de sistema
I En orden decreciente de prioridad las bandas son,
I Intercambio
I Control de dispositivos E/S por bloques
I Manejo de archivos
I Control de dispositivos E/S de caracteres
I Procesos de usuarios
Planificación Tradicional en UNIX
Tiempo de Respuesta
I Es el tiempo que tarda el sistema en reaccionar ante una
entrada
I El que un valor del tiempo de respuesta sea aceptable o
no depende de la aplicación
I Por supuesto lo ideal es que el tiempo de respuesta sea
despreciable en todos los casos
I Lograr esto tiene un costo inversamente proporcional al
tiempo de respuesta deseado
I El origen de estos costos puede ser
I Potencia de cálculo, mientras mas rápido el procesador
mayor el costo
I Requerimientos contrapuestos, para otorgarle una
respuesta rápida a algún proceso se penaliza algún otro
I Un tiempo de respuesta bajo es clave para las
aplicaciones interactivas
Tiempo de Respuesta

I En los sistemas interactivos podemos dividir el tiempo de

trabajo en dos componentes
Tiempo de respuesta del usuario: El tiempo que
transcurre entre que el usuario recibe una respuesta y
genera una nueva orden

Tiempo de respuesta del sistema: El tiempo que

transcurre entre que el usuario ingresa una orden y
recibe una respuesta completa