Planificación del procesador: niveles, objetivos, criterios y algoritmos

Introducción a la Planificación del Procesador

El conjunto de políticas que gestionan el procesador se conoce como Planificación del procesador. El objetivo principal de dichas políticas es dar un buen servicio a todos los procesos que existan en un momento dado en el sistema.

En general, se distinguen varios niveles de planificación dentro del Sistema Operativo (SO).

Niveles de Planificación

• Planificación a largo plazo (Planificador de trabajos): Decide cuál será el próximo trabajo que se va a ejecutar (solo existe en los sistemas por lotes).
• Planificación a medio plazo (Planificación de swapping): Decide si un proceso que está en ejecución en estado bloqueado o suspendido debe ser extraído de la memoria temporalmente y llevado a la memoria externa (disco duro).
• Planificación a corto plazo (Planificación de procesador): Es el encargado de decidir cómo y cuándo tendrá acceso el procesador a un proceso que está preparado para utilizarlo. Lleva las funciones de la multiprogramación y está siempre residente en memoria.

Objetivos de las Políticas de Planificación

Toda política de planificación intenta alcanzar unos objetivos, algunos de los cuales son:

• Justicia: Ser justos con todos los procesos y tratarlos igual.
• Máxima capacidad de ejecución: Todos los trabajos deben ejecutarse lo más rápidamente posible.
• Predecibilidad: Debe saberse en todo momento cuál será el siguiente proceso que se ejecutará.
• Minimización de la sobrecarga.
• Equilibrio en el uso de recursos: Intentar mantenerlos ocupados el mayor tiempo posible.
• Seguridad en las prioridades.

Criterios de Planificación

• Tiempo de respuesta: Velocidad con que el ordenador responde a una petición.
• Tiempo de servicio: Tiempo que tarda en ejecutarse un proceso.
• Tiempo de ejecución: Tiempo de servicio menos tiempo de espera de los procesos en la cola de preparados.
• Tiempo de procesador: Tiempo que un proceso está usando el procesador menos tiempo de espera en la cola de bloqueados en espera de una operación de E/S.
• Tiempo de espera: Los tiempos que los procesos están en las distintas colas.
• Eficiencia: Utilización del recurso más caro del sistema: el procesador.
• Rendimiento: Número de trabajos por unidad de tiempo.

Medidas de Rendimiento

• t: Tiempo que un proceso necesita estar en ejecución para concluir su trabajo.
• ti: Instante en que el usuario da la orden de trabajo.
• tf: Instante en que el proceso termina su ejecución.
• Tiempo de servicio (T) = tf – ti
• Tiempo de espera (E) = T – t

A partir de los valores se define el índice de servicio (I) = t / T

Este indicador representa, en tanto por uno, el tiempo que el proceso está en ejecución respecto al tiempo de vida del mismo en el sistema.

• Cuando I sea próximo a uno: Proceso limitado por proceso.
• Cuando I sea bajo o próximo a 0: Proceso limitado por E/S.

En los casos más usuales, hay que tomar las medidas con los valores medios, lo que proporciona el verdadero comportamiento del sistema:

• Tiempo medio de servicio.
• Tiempo medio de espera.
• Eficiencia media (índice medio de servicio).

También se suelen usar como medidas:

• Tiempo de núcleo.
• Tiempo de inactividad (Idle).

Algoritmos de Planificación

La cola de procesos preparados se nutre de dos puntos distintos:

• Cada vez que un usuario inicia la ejecución de un proceso.
• Cuando un proceso deja de estar en estado de ejecución y ya no existen causas para que continúe bloqueado.

Las políticas de planificación se agrupan en:

• Apropiativas: Permiten que un proceso que está haciendo uso del procesador sea temporalmente suspendido para que otro proceso ocupe su lugar en el procesador.
• No apropiativas: El proceso solamente abandona el procesador cuando ha acabado su trabajo.

Primero en Llegar Primero en ser Servido (FCFS)

• Muy simple y sencilla de implementar.
• Pobre en comportamiento.

Características de FCFS

• No es apropiativa.
• Es justa, aunque los procesos largos hacen esperar a los cortos.
• Es predecible.
• El tiempo medio de servicio es muy variable, en función del número de procesos y su duración.

Round Robin (RR)

Consiste en conceder a cada proceso en ejecución un determinado periodo de tiempo (quantum), transcurrido el cual, si el proceso no ha terminado, se le devuelve al final de la cola de preparados. Los valores del quantum oscilan entre 10 y 100 milisegundos, siendo recomendable que el valor del quantum supere el 80% de los tiempos de respuesta de los procesos.

Características de RR

• Baja sobrecarga, si los cambios de contexto son eficientes y los procesos siempre están en memoria principal.
• El tamaño óptimo del quantum depende de:
  • El tipo de sistema.
  • Las cargas que vaya a soportar el sistema.
  • El número de procesos en el sistema y su tipo.
• Es la política más usada en los sistemas de tiempo compartido.
• Ofrece un índice de servicio uniforme para todos los procesos.
• Es apropiativa.
• Es predecible.

El Siguiente Proceso, el Más Corto (SJN)

Esta política toma de la cola de preparados el proceso que necesite menos tiempo para la ejecución de su trabajo. El procesador debe saber o estimar de antemano el tiempo que le hará falta a cada proceso para su finalización.