Actividad 3: Criterios de Planificación del CPU

Introducción

Planificación: Gestión del procesador realizada por los sistemas operativos a través de distintas políticas y mecanismos. Su objetivo principal es el de dar un buen servicio a todos los procesos que existan en un momento dado en el sistema [Lancharro, 1992].

La planificación del procesador es la base de los sistemas operativos multiprogramados. Al conmutar el procesador entre los procesos, el sistema operativo puede hacer más productiva la computadora [Silberschatz, 1999].

Niveles de planificación

Niveles de planificación [Lancharro, 1992]:

Planificación a largo plazo (planificador de trabajos).

Decide cuál será el próximo trabajo que se va a ejecutar. Sólo existe en los sistemas de proceso por lotes, donde la decisión se basa en las necesidades de recursos y su disponibilidad. En los sistemas de tiempo compartido tiene como única misión cargar los programas que se desean ejecutar en memoria. Es el encargado de crear procesos.

Planificación a mediano plazo (planificador de swapping).

Decide si un proceso que está en ejecución en estado bloqueado o suspendido debe ser extraído de la memoria temporalmente. Posteriormente, cuando el sistema se encuentre más descargado, devolverá dicho proceso a la memoria y al estado de ejecución. Está técnica se conoce con el nombre de swapping. Sólo existe en sistemas de tiempo compartido y en aquellos que tienen gestión de memoria virtual. Gestiona los procesos suspendidos en espera de algún recurso no disponible en el momento de la suspensión.

Planificación a corto plazo (planificador de procesador).

Es el encargado de decidir cómo y cuándo tendrá acceso al procesador a un proceso que está preparado para utilizarlo. Por ello, lleva a cabo las funciones de la multiprogramación, estando siempre residente en memoria y ejecutándose con mucha frecuencia; por ello, debe ser de ejecución muy rápida. En este nivel, es donde se debe dar buen servicio a los procesos interactivos para que el usuario no perciba, o lo haga en pequeño grado, que está compitiendo por el procesador junto con otros usuarios.

Objetivos

Las políticas de planificación intentan cubrir los siguientes objetivos [Lancharro, 1992]:

Justicia. La política debe ser lo más justa posible con todo tipo de procesos, sin favorecer a unos perjudicar a otros.

Máxima capacidad de ejecución. Debe dar un servicio aceptable para que todos los trabajos se realicen lo más rápidamente posible. Esto se logra disminuyendo el número de cambios de proceso.

Máximo número de usuarios interactivos. En los sistemas de tiempo compartido se tratará de que puedan estar trabajando el mayor número de usuarios simultáneamente.

Predecibilidad. La política de planificación debe concebirse de tal forma que en todo momento pueda saberse cómo será su ejecución.

Minimización de la sobrecarga. La computadora debe tener poca sobrecarga ya que ésta incide directamente sobre el rendimiento final del sistema: a menor sobrecarga, mayor velocidad de proceso. Por ello, los cambios de contexto deben disminuirse.

Equilibrio en el uso de recursos. Para obtener un buen rendimiento en el uso de los recursos y que éstos estén ocupados equitativamente el mayor tiempo posible.

Seguridad de las prioridades. Si un proceso tiene mayor prioridad que otro, éste debe ejecutarse más rápidamente.

Criterios

Criterios a considerar a la hora de elegir o diseñar un buen algoritmo de planificación [Tanenbaum, 1993], [Lancharro, 1992], [Silberschatz, 1999]:

1- Equidad.

Garantizar que cada proceso obtiene su proporción justa de la CPU.

2- Eficacia, eficiencia, utilización de la CPU.

Mantener ocupada la CPU el 100% del tiempo.

3- Tiempo de respuesta.

Velocidad con que el ordenador da respuesta a una petición. Depende mucho de la velocidad de los dispositivos de entrada/salida.

4- Tiempo de regreso o de servicio.

Es el tiempo que tarda en ejecutarse un proceso, donde se incluye el tiempo de carga del programa en memoria, el tiempo de espera en la cola de procesos preparados, el tiempo de ejecución en el procesador y el tiempo consumido en operaciones de entrada/salida.

5- Tiempo de ejecución.

Es idéntico al tiempo de servicio menos el tiempo de espera en la cola de procesos preparados; es decir, es el tiempo teórico que necesitaría el proceso para ser ejecutado si fuera el único presente en el sistema.

6- Tiempo de procesador.

Es el tiempo que un proceso está utilizando el procesador sin contar el tiempo que se encuentra bloqueado por operaciones de entrada/salida.

7- Tiempo de espera.

Es el tiempo en que los procesos están activos pero sin ser ejecutados, es decir, los tiempos de espera en las distintas colas.

8- Rendimiento.

Es el número de trabajos o procesos realizados por unidad de tiempo, que debe ser lo mayor posible.

Medidas

Para estudiar el comportamiento de las distintas políticas de planificación, definiremos dos medidas relacionadas entre si que nos indiquen cómo estamos tratando un proceso concreto.

- Tiempo de servicio (T):           T = t_f - t_i

siendo   t_i : el instante en que el usuario da la orden de ejecución del proceso.

            t_f : el instante en que el proceso termina su ejecución.

      

- Tiempo de espera (E):            E = T - t

siendo   t : el tiempo que un proceso P necesita estar en ejecución para llevar a cabo su trabajo.

Podemos establecer una relación que nos permite evaluar la actuación de la política establecida en lo que se denomina índice de servicio (I).

                                               I = t / T

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

En caso de que sólo exista un proceso ejecutándose en el sistema, podemos decir que:

- Cuando I sea próximo a la unidad, el proceso está limitado por proceso.

- Si I tiene un valor bajo próximo a 0, el proceso estará limitado por entrada/salida.

En caso de que exista más de un proceso en el sistema, debemos establecer los valores medios obtenidos al considerar el conjunto de procesos presentes. Las medidas serán:

· Tiempo medio de servicio.

· Tiempo medio de espera.

·         Eficiencia (índice medio de servicio).

Existen otras dos medidas que suelen emplearse:

· Tiempo del núcleo.

Es el tiempo consumido por el núcleo del sistema operativo para tomar decisiones de planificación del procesador, donde se incluyen los tiempos de cambio de contexto y de proceso.

· Tiempo de inactividad (Idle).

Es el tiempo consumido cuando la cola de procesos preparados está vacía y por tanto no puede realizarse ningún trabajo productivo.

Algoritmos

El planificador del procesador tiene como misión la asignación del mismo a los procesos que están en la cola de procesos preparados. Esta cola es alimentada desde dos puntos distintos:

· Cada vez que un usuario inicie la ejecución de un programa, el planificador a largo plazo recibe la orden de ejecución, crea el proceso y lo pasa al planificador a corto plazo, colocándose en la cola de procesos preparados.

· Cuando un proceso deja de estar en estado de ejecución y no existen causas para su bloqueo, o deja de estar bloqueado, pasa nuevamente a la cola de procesos preparados.

Cuando un proceso termina su ejecución, deja de existir para el planificador.

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

· Políticas apropiativas.

Son las que producen un cambio de proceso con cada cambio de contexto; es decir, el proceso que está haciendo uso del procesador puede ser temporalmente suspendido y permitir que otro proceso se apropie del procesador. Se utilizan en sistemas operativos con tiempo compartido y tiempo real.

· Políticas no apropiativas.

Son aquellas en las que un proceso no abandona nunca el procesador desde su comienzo hasta su fin. Se utilizan en sistemas de proceso por lotes.

Los diferentes algoritmos que existen son:

Primero en llegar, primero en ser servido (First Come, First Served - FCFS) Primero en entrar, primero en salir (First Input, First Output - FIFO) Servicio por orden de llegada.
Descripción	El procesador ejecuta cada proceso hasta que termina, en el orden que llegan.
Manejo de cola de procesos preparados	Los procesos permanecerán encolados en el orden en que lleguen hasta que les toque su ejecución. Se alimenta sólo por la creación de los procesos.
Política	No apropiativa.
Ventajas	Muy simple y sencilla. Justa aunque los procesos largos hacen esperar mucho a los cortos. Es predecible.
Desventajas	Pobre en cuanto a su comportamiento. Tiempo medio de servicio muy variable dependiendo del número de procesos y su duración. Tiempo de espera promedio suele ser muy largo. No sirve para sistemas de tiempo compartido.
Observaciones	I mejora cuanto más largos son los procesos. E depende del número de procesos que se encuentren en cola y del tiempo que requieran el procesador y es independiente de las necesidades de ejecución del propio proceso.

Round Robin (RR) Asignación cíclica Planificación en rueda Planificación por turno circular
Descripción	Concede a cada proceso en ejecución un tiempo q (quantum o cuanto de tiempo o porción de tiempo). Forma un rueda de procesos que serán ejecutados cíclicamente hasta que terminen.
Manejo de cola de procesos preparados	Transcurrido q, si el proceso no ha terminado, el temporizador genera una interrupción para el sistema operativo, se le devuelve al final de la cola. Gestión de cola: FIFO o por prioridad. Cuando se crea un proceso se coloca al final de la lista. Si un proceso se crea en el momento en que un q finaliza, se supondrá que este llegó antes a la cola.
Política	Apropiativa.
Ventajas	El tiempo de espera crece de acuerdo al tiempo de ejecución de cada proceso. Es la más usada para tiempo compartido. Ofrece índice de servicio uniforme Sencillo, justo y de uso amplio.
Desventajas	Determinar el q óptimo, ya que depende de: -     El tipo de sistema. -     Las cargas. -     El número de procesos y su tipo. El tiempo de espera promedio suele ser muy grande.
Observaciones	Si el proceso se bloquea o termina antes de consumir q, se alterna el uso de la CPU. Si q es mayor que el tiempo de ejecución del proceso más largo se convertirá en una política FCFS. Si se aproxima a 0, la mayor parte del tiempo se consumirá en cambios de contexto. 10 ms. < q < 100 ms. Se recomienda q mayor al 80 % de los tiempos de respuesta de los procesos.

El siguiente proceso, el más corto (Shortest Job Next - SJN) Primero el trabajo más corto (Shortest Job First – SJF)
Descripción	Toma el proceso que necesite menos tiempo de ejecución. Debe conocer el tiempo que necesita cada proceso.
Manejo de cola de procesos preparados	Ubicar los procesos en cola en orden por el tiempo de ejecución.
Política	No apropiativa
Ventajas	El tiempo de espera aumenta con la longitud de los procesos, pero el tiempo medio de espera es óptimo. Buen tiempo de servicio. Algoritmo apropiado para las tareas por lotes.
Desventajas	Determinar el tiempo necesario para cada proceso. Métodos: -          Información del usuario. -          Por el propio programa. -          Basado en la historia (heurística) Poco predecible. No es justa para procesos largos.
Observaciones	Si hay dos procesos que necesitan igual tiempo de ejecución se usa FCFS para romper el empate. El tiempo de espera del proceso corto disminuirá más de lo  que aumenta el tiempo de espera del proceso largo. Entonces el tiempo de espera promedio disminuye.

Próximo proceso, el de tiempo restante más corto (Shortest Remaining Time - SRT)
Descripción	Variante de SJN. Cambia el proceso en ejecución cuando se ejecuta un proceso con un tiempo de ejecución total menor que el que se está ejecutando.
Manejo de cola de procesos preparados
Política	Apropiativa
Ventajas	El tiempo de respuesta medio de los procesos largos mejora. Excelente I y E es bastante corto para todos los procesos. Logra que la cola sea lo más corta posible. Es muy eficiente.
Desventajas	Mayor sobrecarga. Injusta, pues un proceso corto puede echar a uno largo que este haciendo uso del procesador y que además esté terminando.
Observaciones

Prioridad
Descripción	A cada proceso se le asocia una prioridad y el procesador se asigna al de mayor prioridad. Se pueden asignar en forma estática o dinámica.
Manejo de cola de procesos preparados
Política	Apropiativa o no apropiativa.
Ventajas
Desventajas	Bloqueo o postergación indefinida o inanición. Utilizar envejecimiento de las prioridades, que aumenta gradualmente las prioridades de los procesos que están en espera.
Observaciones	Las prioridades son definidas: -          Internamente: el SO se basa en información medible (tiempo necesitado de procesador, necesidad de memoria, número de archivos abiertos). -          Externamente: se fijan según criterios como la importancia del proceso, el tipo, el departamento que lo patrocina, a menudo factores políticos. UNIX provee el comando nice que permite a un usuario reducir en forma voluntaria. Nadie la ha utilizado.

Próximo el de más alto índice de respuesta (High Response Next - HRN)
Descripción	Hace variable la prioridad de un proceso. P = (w + t) / t P: prioridad w: tiempo de espera en cola t: tiempo de ejecución del proceso.
Manejo de cola de procesos preparados
Política	No apropiativa.
Ventajas	Corrige las injusticias de SJN con procesos largos y las de FCFS con procesos cortos. Es justa.
Desventajas	Si aparece un proceso corto inmediatamente después de que un proceso largo comienza a ejecutarse deberá sufrir una larga espera. Muy costosa y produce gran sobrecarga por los cálculos.
Observaciones	P inicialmente valdrá 1. P aumentará a medida que el proceso permanezca en cola (w favorece a procesos largos). P disminuirá cuando más tiempo este en ejecución (t favorece a procesos cortos).

Colas múltiples
Descripción	Divide la cola de procesos preparados en varias colas separadas. Los procesos se asignan a una determinada cola según sus necesidades, tamaño de memoria, prioridades y tipo. Existe un algoritmo de planificación entre las colas. Normalmente apropiativo de prioridad fija. Otra posibilidad: dividir el tiempo entre colas. Cada cola tiene un tiempo de CPU.
Manejo de cola de procesos preparados	Cada cola puede tener una planificación distinta.
Política	Apropiativa.
Ventajas
Desventajas
Observaciones

Colas múltiples con retroalimentación (Feedback Multiple Queues - FB)
Descripción	Divide los procesos en varias colas numeradas siendo la de numeración más baja la de mayor prioridad. Un planificador de colas multinivel con retroalimentación esta definido por: -          el número de colas. -          El algoritmo de planificación para cada cola. -          El método empleado para determinar cuando se debe promover un proceso a una cola de mayor prioridad. -          El método empleado para determinar cuando se debe promover un proceso a una cola de menor prioridad. -          El método empleado para determinar en cual cola ingresará un proceso cuando necesite servicio.
Manejo de cola de procesos preparados	Cuando el proceso finaliza su q, se selecciona el proceso del principio de la cola del nivel más bajo que tenga algún proceso. Luego de un número determinado de consumos de q, sin haber finalizado, se lo coloca al final del nivel inmediatamente superior. Cada cola puede tener una planificación distinta.
Política	Apropiativa.
Ventajas	Soporta bien la sobrecarga. Adaptable a las necesidades del sistema. Algoritmo más general.
Desventajas
Observaciones	Procesos limitados por procesador irán a colas de menor prioridad (nivel alto). Procesos muy interactivos irán en colas de alta prioridad (nivel bajo).

Dos niveles
Descripción	Si no se dispone de suficiente memoria principal será necesario mantener algunos procesos ejecutables en disco. Primero se trabaja con un subconjunto cargado en memoria y en forma periódica se llama al planificador de nivel superior para realizar el cambio.
Manejo de cola de procesos preparados
Política
Ventajas
Desventajas
Observaciones	Criterios para elegir que procesos ejecutables están en memoria o en disco: -          Tiempo que ha transcurrido desde el último intercambio del proceso. -          Tiempo de CPU que ha utilizado recientemente el proceso. -          Tamaño del proceso. -          Prioridad del proceso.

Planificación de múltiples procesadores

El problema de planificación se vuelve más complejo. Se han ensayado muchas posibilidades, tales como:

· Tener una cola aparte para cada procesador; sin embargo, un procesador podría estar ocioso, con su cola vacía, mientras otro está muy ocupado.

· Tener una cola común para los procesos listos. Los procesos ingresan en una cola y se les asigna cualquier procesador que esté disponible. Existen 2 estrategias para este caso:

- Cada procesador se auto - planifica. El procesador examina la cola común de procesos listos y escoge el proceso que ejecutará. Como varios procesadores tratan de acceder a una estructura de datos común y actualizarla es preciso programar cada procesador con mucho cuidado.

- Para evitar los problemas de la estrategia anterior se nombra a un procesador como planificador para los demás  procesadores, lo que da lugar a una estructura maestro - esclavo. Una variante es que el procesador maestro tome todas las decisiones de planificación y se encargue del procesamiento de E/S y otras actividades del sistema. Los demás procesadores ejecutan código de usuario. Este se conoce como multiprocesamiento asimétrico, porque sólo un procesador accede a las estructuras de datos del sistema y reduce la necesidad de compartir recursos.

Planificación en tiempo real.

Evaluación de algoritmos.

El siguiente paso es evaluar los diversos algoritmos que se estén considerando. Hay varios métodos de evaluación distintos, entre ellos:

· Modelado determinista.

Es un tipo de evaluación analítica que toma una carga de trabajo predeterminada específica y define el desempeño del algoritmo para esa carga de trabajo.

· Modelos de colas.

Consiste en determinar las distribuciones características del sistema, tales como: la distribución de las ráfagas de CPU y E/S (comúnmente exponencial) y la distribución de los tiempos en que los procesos llegan al sistema. A partir de estas distribuciones es posible calcular el rendimiento promedio, el aprovechamiento, el tiempo de espera, etc. para la mayor parte de los algoritmos. Los modelos consisten asociar a cada recurso colas de procesos en espera. Conociendo frecuencias de llegada y rapidez de servicio es posible calcular el aprovechamiento, la longitud de colas, el tiempo de espera promedio, etc.

·Simulaciones.

Implica programar un modelo del sistema de computación. El simulador tiene una variable que representa un reloj; cuando se incrementa el valor de esta variable, el simulador modifica el estado del sistema de modo que refleje las actividades de los dispositivos, los procesos y el planificador. Conforme se ejecuta la simulación, se recopilan e imprimen los datos estadísticos que indican el desempeño del algoritmo.

Los datos que se alimentan a la simulación se pueden generar de varias maneras. El método más común emplea un generador de números aleatorios. Otra forma es a través de cintas de rastreo que se crean vigilando el sistema real y registrando la secuencia de sucesos reales.

· Implementaciones.

La única forma exacta de evaluar un algoritmo de planificación es codificarlo, colocarlo en el SO y ver como funciona. El principal inconveniente es el costo. Es necesario codificar el algoritmo y modificar el SO para que lo apoye, crear las estructuras de datos que requiere y ver la reacción de los usuarios ante un SO que cambie constantemente. Otro inconveniente de cualquier evaluación de algoritmos es que el entorno en el que se usa el algoritmo cambiará no sólo cuando se escriben nuevos programas y los tipos de problemas cambian sino también por el desempeño del planificador.

Existen algoritmos de planificación más flexibles que permiten  los administradores o usuarios alterarlos o modificar las variables que utilizan.