Planificación

Se necesita realizar una planificación para determinar cuáles serán los programas admitidos en el sistema

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 / hilo disponible será ejecutado en el procesador

Planificación a largo plazo

Determina cuáles son los programas admitidos en el sistema. Debe tomar dos decisiones:

• Cuándo puede crear un nuevo proceso
• Cuál va a ser el siguiente proceso a admitir. Combinar procesos con mayor carga de procesador y procesos con mayor carga de E/S

Controla el grado de multiprogramación. Cuantos más procesos se crean, menor es el porcentaje de tiempo en el que cada proceso se puede ejecutar

Planificación a medio plazo

Forma parte de la función de intercambio

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

Si no se emplea memoria virtual, deberá tener en cuenta las necesidades de memoria del proceso

Planificación a corto plazo

Planificación del uso de la CPU: Gestionar la compartición de la CPU entre los procesos / hilos listos para ejecutarse

El objetivo del planificador (scheduler) es repartir el tiempo del procesador entre los procesos / hilos que pueden ejecutar

Debe tener en cuenta factores como:

• Equidad: repartir el uso de la CPU
• Eficiencia: evitar tiempos ociosos de la CPU
• Rendimiento: maximizar el número de peticiones

Mecanismos de planificación

El planificador está compuesto por tres componentes lógicos:

• Encolador: Cuando un proceso cambia al estado Listos, el encolador lo coloca en una estructura de datos de tipo cola
• Conmutador de contexto: Cuando un proceso va a ser desalojado de la CPU, el conmutador de contexto guarda el contenido de los registros de la CPU en el BCP del proceso
• Distribuidor: El distribuidor selecciona uno de los procesos de la cola de Listos y le asigna la CPU

Criterios de la planificación

Criterios para comparar el rendimiento de los diversos algoritmos de planificación:

• Tiempo de servicio (T_s) Tiempo estimado de ejecución
• Tiempo de retorno (T_r) Tiempo transcurrido desde que llega al sistema hasta que termina
• Tiempo de espera (T_w) Suma de tiempos que el proceso está en no ejecución
• Tiempo de retorno normalizado (\frac{T_r}{T_s}) Tiempo de retorno dividido por el tiempo de servicio

Uso de prioridades

El planificador seleccionará siempre a un proceso de mayor prioridad antes que a los de menor prioridad

Utiliza múltiples colas de Listos para representar cada nivel de prioridad

Los procesos de prioridad más baja pueden sufrir inanición (no son elegidos núnca)

Una solución ante la inanición consiste en permitir que un proceso cambie su prioridad en función de su antigüedad o su historial de ejecución

Políticas de planificación

Se basan en una función de selección para determinar qué proceso, de entre los Listos, se elige para ejecutar

La función puede estar basada en prioridades, necesidades de recursos o en las características de ejecución de los procesos

Hay dos clases de algoritmos según el modo de decisión (instante en que se aplica la función de selección):

• Sin expulsión (no apropiativos o no preferentes): Una vez que el proceso pasa al estado de Ejecución, continúa ejecutando hasta que termina o se bloquea en espera de una E/S (ráfaga)
• Con expulsión (apropiativos o preferentes): El proceso que se está ejecutando actualmente puede ser interrumpido y pasado al estado de Listos por el sistema operativo. Permiten dar un mejor servicio ya que evitan que un proceso pueda monopolizar el procesador durante mucho tiempo

Algoritmos de planificación

Algoritmos sin expulsión:

• FIFO (First-come First-served): Primero en llegar, primero en ser servido
  • Se selecciona para ejecutar el proceso más antiguo de la cola de Listos
  • Sencillo de implementar
  • Tiempo medio de espera muy alto
  • Penaliza a los procesos cortos sobre los procesos largos
  • Favorece a los procesos con carga de CPU sobre los procesos con carga de E/S
  • Suele utilizarse combinado con prioridades
• SPN (Shortest Process Next): Primero el proceso más corto
  • Se selecciona el proceso con menor tiempo de servicio
  • Dificultad en estimar el tiempo esperado de ejecución para cada proceso
  • Minimiza el tiempo medio de espera
  • Penaliza a los procesos largo sobre los procesos cortos
  • Posibilidad de inanición para los procesos largos

Algoritmos con expulsión:

• Turno rotatorio (RR, Round Robin)
  • Utiliza un cuanto de tiempo que es una fracción de tiempo que permite a cada proceso utilizar la CPU
  • Se expulsa el proceso que ha consumido su cuanto de tiempo y pasa a ocupar el último lugar de la cola de Listos
  • Hay dificultades para elegir el tamaño del cuanto (inferior al 80% de las ráfagas de CPU)
  • Favorece a los procesos con carga de CPU sobre los procesos con carga de E/S
  • El tiempo de espera grande, pero garantiza un reparto de la CPU con buenos tiempos de respuesta
• FB (Feedback): Realimentación multinivel
  • Divide la cola de Listos en una jerarquía de colas: RQ_0, \cdots, RQ_n, cada una con un nivel de prioridad
  • Utiliza un cuanto de tiempo y un mecanismo dinámico de prioridades
  • Los procesos entran por RQ_0 y en cada ráfaga de ejecución descienden a la siguiente cola
  • En cada cola se utiliza FIFO, excepto en la de menor prioridad que se trata con turno rotatorio
  • Favorece a los procesos cortos frente a los procesos más viejos y largos
    • Los procesos cortos terminarán rápidamente, sin descender demasiado en la jerarquía de colas
    • Los procesos largos serán gradualmente llevados hacia abajo
  • Existe un gran número de variaciones de este esquema
  • Para evitar la inanición de los procesos largos se puede variar el cuanto en función de cada cola

  Planificación en POSIX

  Cada política de planificación lleva asociada un rango de, al menos, 32 niveles de prioridad

  El planificador seleccionará el proceso con la prioridad más alta

  Cuando un proceso es expulsado por otro de mayor prioridad, el proceso pasa a ser el primero de la cola asociada a su prioridad

  En el planificador conviven tres políticas de planificación:

  • SCHED_FIFO: Es una política de planificación expulsora basada en prioridades estáticas, en la que los procesos con la misma prioridad se atienden en el orden de llegada (cola FIFO). Esta política tendrá al menos 32 niveles de prioridad
  • SCHED_RR: Esta política es muy similar a SCHED_FIFO, pero emplea un método round-robin para planificar procesos de la misma prioridad. También tiene 32 niveles de prioridad como mínimo
  • SCHED_OTHER: Es una política de planificación definida por la implementación

  Servicios POSIX para la planificación de procesos

  Las tres políticas de planificación están definidas en el archivo de cabecera

  <sched.h>

  Modificar los parámetros de planificación de un proceso:

  int sched_setparam(pid_t pid, const struct sched_param *param);
  int sched_scheduler(pid_t pid, int policy, const struct sched_param *param);

  Obtener los parámetros de planificación de un proceso:

  int sched_getparam(pid_t pid, const struct sched_param *param);
  int sched_getscheduler(pid_t pid);
  int sched_get_priority_min(int policy);
  int sched_get_priority_max(int policy);