3-Planificadores

PLANIFICADORES

Es un componente funcional muy importante de los sistemas operativos multitarea y multiproceso, y es esencial en los sistemas operativos de tiempo real. Su función consiste en repartir el tiempo disponible de un multiprocesador entre todos los procesos que están disponibles para su ejecución.

Se denomina planificador al software del SO encargado de asignar los recursos de un sistema entre los procesos que los solicitan. Siempre que haya que tomar una decisión, el planificador debe decidir cuál de los procesos que compiten por la posesión de un determinado recurso lo recibirá. En la definición, el procesador se considera como un recurso más del sistema.

La planificación es el conjunto de políticas y mecanismos construidos dentro del sistema operativo que gobiernan la forma de conseguir que los procesos a ejecutar lleguen a ejecutarse.

Es un proceso gradual, por el que se establece el esfuerzo necesario para cumplir con los objetivos de un proyecto en un tiempo u horario que se debe cumplir para que la planificación sea exitosa. En este proceso permite además, refinar los objetivos que dieron origen al proyecto.

Existen diferentes herramientas y técnicas para abordar la planificación de un proyecto, las cuales permiten definir el curso de acción a seguir, que será tomado como base durante la ejecución del mismo.

Si bien la planificación define las acciones a seguir, durante la ejecución puede existir necesidad de cambios respecto de lo definido originalmente, los mismos servirán de punto de partida para un nuevo análisis y una nueva planificación de ser requerido.

PLANIFICAR: es trazar los planos para la ejecución de una obra.

CÓMO FUNCIONAN

Supóngase un ordenador que contiene un único microprocesador. Dicho microprocesador solamente puede ejecutar un programa en cada instante de tiempo. Además, cuando un programa está ejecutándose, nunca dejará de hacerlo por sí mismo. De manera que, en principio, cualquier programa monopoliza el microprocesador impidiendo que otros programas se ejecuten. Por ello, la primera misión de un planificador es expulsar el programa en ejecución cuando decida que es pertinente. Esto se consigue de dos maneras, siempre con ayuda del propio hardware:

• Cuando expira un temporizador, que se activa a intervalos regulares de tiempo. En intervalos muy cortos, generalmente cada 250 milisegundos.

• Cuando el programa solicita una operación de entrada/salida. Dado que el programa no puede continuar hasta que termine dicha operación, es un buen momento para ejecutar otro programa. En ambos casos, el control del microprocesador pasa a manos del planificador gracias a que el hardware genera una interrupción. En este proceso de expulsión, se guarda el estado de ejecución del programa (programa y su estado se denomina proceso). A continuación, el planificador decide cuál será el siguiente proceso en ejecutarse. Naturalmente, solamente se escogen procesos que estén listos para hacerlo. Si un proceso sigue esperando por una operación de entrada/salida no será candidato a ejecutarse hasta que finalice tal operación.

TIEMPO REAL

Un sistema operativo en tiempo real se caracteriza por garantizar que todo programa se ejecutará en un límite máximo de tiempo. El planificador debe comportarse de manera que esto sea cierto para cualquier proceso.

En estos casos, la finalidad del planificador es balancear o equilibrar la carga del procesador, impidiendo que un proceso monopolice el procesador o que sea privado de los recursos de la máquina. En entornos de tiempo real, como los dispositivos para el control automático en la industria (por ejemplo, robots), el planificador también impide que los procesos se paren o interrumpan a otros que esperan que se realicen ciertas acciones. Su labor resulta imprescindible para mantener el sistema estable y funcionando.

TIPOS DE PLANIFICADORES

Los sistemas operativos pueden ofrecer hasta 3 tipos distintos de planificadores: planificador a largo plazo o planificador de trabajos, planificador a mediano plazo y planificador a corto plazo o planificador del procesador. Los nombres sugieren la frecuencia relativa con la cual se realizan estas funciones.

PLANIFICADOR A LARGO PLAZO

El objetivo primordial del planificador a largo plazo es el de dar al planificador de la CPU una mezcla equilibrada de trabajos, tales como los limitados por la CPU (utilizan mucho la CPU) o la E/S. Así, por ejemplo, cuando la utilización de la CPU es baja, el planificador puede admitir más trabajos para aumentar el número de procesos listos y, con ello, la probabilidad de tener algún trabajo útil en espera de que se le asigne la CPU.

El PLP se encarga de seleccionar de ese almacenamiento los trabajos que considera más adecuados llevar a la memoria para su ejecución, de acuerdo con cierta política de gestión. El PLP es el principal responsable de que se cumplan los criterios de gestión establecidos para la utilización global del sistema; para ello debe realizar una mezcla adecuada de trabajos "destinados" al procesador y trabajos "destinados" al sistema de E/S, con el fin de mantener en todo momento un uso adecuado de los recursos.

Lo más usual es definir una función de prioridad y asignarle a cada programa un valor para la misma que se actualiza en instantes determinados por el PLP. Las tareas con mayor prioridad se llevan al estado preparado.

PLANIFICADOR A MEDIANO PLAZO

Determina cuales procesos se van a intercambiar entre la memoria principal y la memoria secundaria.

PLANIFICADOR A CORTO PLAZO

También conocido como distribuidor, se ejecuta cuando ocurre un suceso que interrumpe la ejecución del proceso actual del procesador. Su misión escoger un proceso de la cola de listos y pasarlos al procesador para su ejecución.

RELACIÓN ENTRE LOS PROCESOS

El sistema operativo debe suministrar los servicios que permitan el procesamiento concurrente, es decir simultaneidad de procesos. Estos servicios proporcionan los medios para la ejecución concurrente de los procesos y la sincronización entre estos.

También el S.O debe disponer de algoritmos de planificación y gestión de procesos que se encarguen de decidir qué proceso se ejecutara o tomará el procesador, ver en qué está los procesos y sus prioridades.

Los procesos, dependiendo de la interacción entre ellos se pueden clasificar en:

1. Procesos independientes.

2. Procesos cooperativos

3. Procesos competitivos

Proceso independiente: es aquel que ejecuta sin requerir la ayuda o cooperación de otros procesos. Un ejemplo de procesos independientes son los diferentes shells que se ejecutan de forma simultánea en un sistema.

Procesos cooperativos: son aquellos que están diseñados para trabajar conjuntamente en alguna actividad, para lo que deben ser capaces de comunicarse e interactuar entre ellos.

El sistema operativo es el encargado de armonizar, priorizar y ordenar la ejecución de los diferentes procesos que compiten por los recursos limitados con el objetivo final de permitir procesamiento concurrente de todos ellos.

REQUISITOS PARA UN BUEN ALGORITMO DE PLANIFICACIÓN

1.- Imparcialidad: asegurar que cada proceso tenga la parte que le corresponde de CPU.

2.- Eficiencia: mantener CPU ocupada 100% del tiempo.

3.- Tiempo de respuesta: minimizar el tiempo de respuesta para usuarios interactivos.

4.- Cambio de posición: minimizar el tiempo que los usuarios de un lote deben esperar para obtener la salida.

PRODUCTIVIDAD

La productividad se refiere a la cantidad de trabajo completada por mitad de tiempo. Un modo de expresarla es definiéndola como el número de trabajos de usuario ejecutados por una unidad de tiempo. Cuando mayor sea este número, más trabajo aparentemente está siendo ejecutado por el sistema.

1. La planificación del procesador se clasifica según la escala relativa de tiempo en que es realizada.

2. Se define como el tiempo que transcurre desde el momento en que un Programa es remitido hasta que es totalmente completado por el mismo.

3. Es el tiempo que un proceso o trabajo consume a la espera de la asignación de algún recurso. Es un sistema con Multiprogramación.

4. Se define como tiempo que transcurre desde el momento en que se introduce el último carácter de una orden que desencadena la ejecución de un programa. A menudo un proceso puede comenzar a producir alguna salida al usuario mientras continuo procesando la respuesta. Entonces, esta es una mejor medida desde el punto de vista del usuario.

5. Determina qué nuevos programas son aceptados para ser procesados por el sistema, o sea determina el grado de multiprogramación. Una vez admitidos, se convierten en procesos que son agregados a la cola de Planificación a Corto Plazo. En algunos sistemas, son agregados a la cola de Planificación a Mediano Plazo, ya que los procesos creados recientemente comienzan en una condición de suspendidos. Relativamente, se ejecuta en forma poco frecuente.

La utilización de recursos al nivel deseado. Es importante conseguir una administración equilibrada para saber cómo conjugar procesos interactivos que tienen retardos especiales con procesos por lotes que son una simple de cola de cálculo. Por ejemplo, cuando la utilización del microprocesador puede admitir más trabajos, el planificador puede dar entrada al sistema a nuevos procesos y aumentar con ello la probabilidad de asignación de alguno de estos procesos al procesador.

ESQUEMAS DE PLANIFICACIÓN

Los sistemas de planificación son útiles según el ambiente donde sean aplicados:

Sistemas Operativos con planificadores no expropiadores, son los que asignan el recurso procesador a un proceso y hasta que este no lo libere ya sea porque finalice su ejecución o se bloquea, no se vuelve a ejecutar el planificador.

Sistemas operativos con planificadores expropiativos: son los que pueden expropiar el recurso procesador a un proceso cuando otro proceso entra en estado pronto (ya sea porque es nuevo o porque se bloquea) o porque se le impone una limitante de tiempo para ejecutar.

Sistemas por lotes: Como no existe interacción con usuarios los planificadores no expropiadores son ideales.

Sistemas interactivos: Debido a que existen procesos de usuarios ejecutando a la vez los planificadores expropiadores son ideales para mantener un buen tiempo de respuesta para los usuarios.

Sistemas de tiempo real: No es necesario planificadores expropiadores ya que los procesos pueden que no se ejecuten por un buen tiempo, pero cuando lo hacen es por un periodo muy corto.

SISTEMAS MULTIPROCESADORES

En un sistema simétrico, cualquier procesador podrá ejecutar procesos de usuario.

Una posibilidad es asignar una cola de procesos listos para cada procesador y de esa forma mantenerlos procesos asignados a un procesador (afinidad de procesador).

Esto es conveniente para aprovechar los datos que están frescos en la memoria cache del procesador, ya que al ejecutar un procesador se nutre su cache con datos del proceso.

De esta forma, se logra mantener un mayor índice de cachehity, por lo tanto, un mayor rendimiento en el sistema.

Un problema que puede surgir es un desbalance en la cantidad de trabajo por procesador. En estos casos se migrarán procesos de cola para lograr balancear nuevamente la carga.

DESPACHADOR

Una vez que el planificador ejecuta y elige el proceso a asignar al procesador, se invoca al despachador (dispatcher) que es el encargado de asignar el proceso al procesador.

La tarea que realiza es:

Cambiar el contexto: Salvar registros del procesador en PCB del proceso saliente. Cargar los registros con los datos del PCB del proceso entrante.

Cambiar el bit de modo a usuario.

Saltar a la instrucción adecuada que había quedado el proceso que se asigno a la CPU (registro program counter).

POLITICAS DE PLANIFICACIÓN

A continuación se enumeran diversas políticas de planificación. Lo habitual es utilizar políticas mixtas. Generalmente, el planificador a corto plazo utiliza round-robin, mientras que el planificador a largo plazo utiliza varias colas FIFO. Cada una de estas colas corresponde a una prioridad diferente.

· Round-Robín

Round Robín es un método para seleccionar todos los elementos en un grupo de manera equitativa y en un orden racional, normalmente comenzando por el primer elemento de la lista hasta llegar al último y empezando de nuevo desde el primer elemento.

En Sistemas Operativos, la planificación Round Robin da un tiempo máximo de uso de CPU a cada proceso, pasado el cual es desalojado y retornado al estado de listo, la lista de procesos se planifica por FCFS, primero llegado, primero atendido.

FCFS "First Come, First Served". Primero en llegar, primero en ser servido.

Es un algoritmo de planificación no apropiativo que maneja los trabajos de acuerdo con su tiempo de arribo: conforme entran son servidos. Es un algoritmo muy simple de implementar, porque utiliza un tipo de cola FIFO. En este tipo de estructura de datos los procesos son ejecutados en el orden que llegan a la cola de procesos listos. La implementación puede efectuarse con ayuda de arrays o vectores, o bien mediante el uso de punteros y asignación dinámica de memoria.

LIFO “Last In First Out”. Ultimo en entrar, primero en salir.

El término LIFO se utiliza en estructura de datos y teoría de colas. LIFO es el algoritmo utilizado para implementar pilas. Una estructura de datos pila permite que se agreguen y eliminen nodos tan sólo de la parte superior de la misma.

SJF “Shortest Job First”.

Este algoritmo es óptimo para el tiempo de espera, pero requiere que todos los procesos participantes estén al comienzo. Su funcionamiento depende de conocer los tiempos de ejecución, que en la mayoría de los casos no se conoce. Si dos trabajos tienen el mismo tiempo se seleccionan según la estrategia FCFS. Esta estrategia es óptima desde el punto de vista de minimizar el tiempo de espera de los trabajos pendientes de ejecución.

SRT- “Shortest Remaining Time”

El algoritmo SRT corresponde a la versión no apropiativo del método SJF: es el método en el que se elige a continuación aquel proceso al que le queda menos tiempo para terminar su ejecución, incluyendo a los nuevos que lleguen. De esta forma aunque un proceso requiera mucho tiempo de ejecución, a medida que se va ejecutando iría avanzando en la lista de procesos en estado listo hasta llegar a ser el primero.

Algoritmo apropiativo, consiste en elegir de la cola de listos el proceso con menos necesidad de tiempo restante de CPU para cada instante de tiempo.

CRITERIOS PARA LA PLANIFICACIÓN

Los algoritmos de planificación tendrán distintas propiedades y favorecerán cierta clase de procesos. Es necesario definir criterios para poder evaluar los algoritmos de planificación. Algunos de estos son:

A) Eficacia. Se expresa como un porcentaje del tiempo medio de utilización. Aunque puede parecer lógico intentar mantener este parámetro próximo al 100%, con un valor tan elevado otros aspectos importantes de medida del comportamiento del sistema pueden verse deteriorados, como por ejemplo el tiempo medio de espera.

B) Rendimiento (throughput). Es una medida del número de procesos completados por unidad de tiempo. Por ejemplo, 10 procesos por segundo.

C) Tiempo de retorno o regreso (turnarounds). Es el intervalo de tiempo que transcurre desde que un proceso se crea o presenta hasta que se completa por el sistema.

D) Tiempo de espera. Es el tiempo que el proceso espera hasta que se le concede el procesador. Puede resultar una medida más adecuada de la eficiencia del sistema, ya que se elimina de la medida el tiempo que tarda en ejecutarse el mismo.

E) Tiempo de respuesta a un evento. Se denomina así al intervalo de tiempo que transcurre desde que se señala un evento hasta que se ejecuta la primera instrucción de la rutina de servicio de dicho evento. El criterio de selección de un algoritmo se suele basar en la maximización o minimización de una función de los parámetros anteriores. Por ejemplo, maximizar la eficacia y el rendimiento, y minimizar el tiempo de espera, o bien, minimizar la varianza del tiempo de respuesta.

F) Utilización de CPU (CPU utilization): Es el porcentaje de uso (en cuanto a ejecución de tareas de usuario o del sistema que son consideradas útiles) que tiene un procesador.