2.6 TECNICAS DE ADMINISTRACION DEL PLANIFICADOR

2.6 TECNICAS DE ADMINISTRACION DEL PLANIFICADOR

La cuestión de la planificación del procesador aborda el problema de decidir a qué proceso de la cola de procesos preparados debe asignársele al procesador. Existen distintos algoritmos de planificación del procesador, a continuación analizaremos algunos de ellos.

Planificación FCFS

Este es el algoritmo más simple de planificación (First Come, First Served; primero en llegar, primero servido). En este esquema se asigna el CPU al primer proceso que lo solicite. La implementación de esta política se gestiona con una cola FIFO (First In, First Out; primero en entrar, primero en salir). Cuando un proceso entra en la cola de procesos preparados, su PCB se coloca al final de la cola. Cuando el procesador queda libre, se le asigna al siguiente proceso de la cola y al pasar a ejecutarse se elimina de la cola.

El tiempo medio de espera con el algoritmo FCFS es normalmente bastante largo. Suponiendo que el siguiente conjunto de procesos llega en el instante 0, estando la ráfaga de CPU especificada en milisegundos:

Si lo procesos llegan en el orden P1, P2, P3 y se sirven según el orden FCFS, obtendremos el resultado mostrado en el siguiente diagrama de Gantt:

El tiempo de espera es de 10 milisegundos para el proceso P1, de 24 milisegundos para el proceso P2 y de 27 milisegundos para P3. Por tanto el tiempo medio de espera es de (0+24+27)/3 = 17 milisegundos. Sin embargo, si los procesos llegan en el orden P2, P3, P1, los resultados se muestran en el siguiente diagrama de Gantt:

Ahora el tiempo de espera es de (6+0+3)/3 = 3 milisegundos. Esta reducción es sustancial. Por tanto, el tiempo medio de espera con una política FCFS no es, generalmente, mínimo y puede variar si la duración de las ráfagas del CPU de los procesos es muy variable.

El algoritmo de planificación FCFS es cooperativo. Una vez que el CPU ha sido asignado a un proceso, dicho proceso conserva el CPU hasta que lo libera, ya sea por que termina su ejecución o por que realiza una petición de E/S. El algoritmo FCFS resulta, especialmente problemático en los sistemas de tiempo compartido, donde es importante que cada usuario obtenga una cuota del CPU a intervalos regulares. Sería desastroso que un proceso mantuviera el CPU durante un periodo largo de tiempo.

Planificación SJF

Shortest-job-First (Trabajo más corto Primero), este algoritmo asocia con cada proceso la duración de la siguiente ráfaga de CPU del proceso. Cuando el CPU esta disponible, se asigna al proceso que tiene la siguiente ráfaga de CPU más corta. Cuando las siguientes ráfagas de CPU de dos procesos son iguales, se usa la planificación FCFS para romper el empate. Un término más apropiado sería el de “algoritmo de la siguiente ráfaga de CPU más corta”, ya que la planificación depende de la duración de la siguiente ráfaga de CPU, en lugar de depender de la duración total.

Como ejemplo de planificación SFJ, tenemos el siguiente conjunto de procesos, estando especificada la duración de la ráfaga de CPU en milisegundos:

Usando la planificación SJF, planificaríamos estos procesos de acuerdo al siguiente diagrama de Gantt:

El tiempo de espera es de 3 milisegundos para el proceso P1, de 16 milisegundos para el proceso P2, de 9 milisegundos para el proceso P3 y de 0 milisegundos para el proceso P4. Por tanto, el tiempo medio de espera es de (3+16+9+0)/4 = 7 milisegundos. Por comparación, si estuviéramos usando el esquema de planificación FCFS, el tiempo de espera seria de 10.25 milisegundos

El algoritmo de planificación SJF es probablemente óptimo, ya que proporciona el tiempo medio de espera mínimo para un conjunto de procesos. Al anteponer un proceso corto a uno largo disminuye el tiempo de espera del proceso corto en mayor medida de lo que incrementa el tiempo de espera del proceso largo. Por esto, el tiempo medio de espera disminuye.

La dificultad del algoritmo SJF es conocer la duración de la siguiente solicitud de CPU. En una planificación a largo plazo en un sistema de procesamiento por lotes, podemos usar una duración el límite del tiempo del proceso que el usuario especifique en el momento de enviar el trabajo. La planificación SJF se usa frecuentemente como mecanismo de planificación a largo plazo.

Aunque el algoritmo SJF es optimo, no se puede implementar en el nivel de planificación del CPU a corto plazo, ya que no hay forma de conocer la duración de la siguiente ráfaga de CPU. Un método consiste en intentar aproximar la planificación SJF: podemos no conocer la duración de la siguiente ráfaga de CPU, pero podemos predecir su valor, por el procedimiento de confiar en que la siguiente ráfaga de CPU sea similar en duración a las anteriores. De esta manera, calculando una aproximación de la duración de la siguiente ráfaga de CPU, podemos tomar el proceso que tenga la ráfaga de CPU predicha más corta.

La siguiente ráfaga de CPU se predice como una media exponencial de las duraciones medias anteriores. Sea tn la duración de la n-ésima ráfaga de CPU y sea τn+1 el valor predicho rapa la siguiente ráfaga de CPU. Entonces, para α, 0≤α≤1, se define: τn+1 = αtn + (1 - α)tn

Esta fórmula define un promedio exponencial. El valor de tn contiene la información más reciente; τn almacena el historial pasado. El parámetro α controla el peso relativo del historial reciente y pasado de nuestra predicción. Si α=0, entonces τn+1 = τn, y el historial reciente no tiene ningún efecto; si α=1, entonces τn+1 = τn y solo la ráfaga de CPU mas reciente importa. Frecuentemente, α=1/2, el historial reciente y pasado tienen el mismo peso. El valor inicial τ0 puede definirse como una constante o como un promedio global para todo el sistema. La siguiente figura muestra el promedio exponencial como α=1/2 y τ0 = 10.

Para entender el comportamiento del promedio exponencial, podemos desarrollar la formula τn+1 sustituyendo el valor de τn y el de los términos sucesivos, obteniendo

τn+1 = αtn + (1 – α) αtn-1 + … + (1 – α)jαtn-j + … + (1 – α) n-1 τ0

Dado que tanto α como 1 - α con menores o iguales a 1, cada término sucesivo tiene menor peso que su predecesor. El algoritmo SJF puede ser cooperativo o apropiativo. La necesidad de eligir surge se da cuando un proceso llega a la cola de procesos preparados mientras que un proceso anterior está todavia en ejecución. La siguiente ráfaga de CPU del proceso que acaba de llegar puede ser más corta que lo que quede del proceso actualmente en ejecución. Un algoritmo SJF apropiativo detendrá el proceso, mientras que un algoritmo sin desalojo permitirá que dicho proceso termine su rafagá de CPU. La planificación SJF apropiativa tambien es conocida como: planificación con selección del proceso con tiempo restante más corto.

Analizaremos el siguiente ejemplo con cuatro procesos donde tenemos especificada la duración de la ráfaga de CPU en milisegundos:

Si los procesos llegan a la cola de procesos preparados en los instantes que se muestran y necesitan los tiempos que se muestran los tiempos de ráfaga indicados, entonces la planificacion SJF apropiativa es la que se muestra en el siguiente diagrama de Gantt:

El proceso P1 se inicia en el instante 0, dado que es el único proceso que hay en la cola. El proceso P2 llega en el instante 1. El tiempo que le da al proceso P1 (7 milisegundos) es mayor que el tiempo requerido por el proceso P2 (4 milisegundos), por lo que el proceso P1 se desaloja y se planifica el proceso P2. El tiempo medio de espera en este ejemplo es de ( (10 - 1) + (1 - 1) + (17 - 2) + (5 - 3) )/4 = 26/4 = 6.5 milisegundos. La planificacion SJF cooperativa proporcionaria un tiempo promedio de espera de 7.75 milisegundos.

Planificación por Prioridades

El algoritmo SJF es un caso especial del algoritmo de planificación por prioridades general. A cada proceso se le asocia una prioridad y el CPU se le asigna al proceso que tenga la prioridad mas alta. Los procesos con la misma prioridad se planifican con un orden FCFS. Un algoritmo SJF es simplemente un algoritmo por prioridades donde la prioridad (p) es el inverso de la siguiente ráfaga de CPU (predicha). Cuanto mas larga sea la ráfaga del CPU, menor será la prioridad y viceversa.

Se debe observar que al hablar de planificación se piensa en términos de “alta” prioridad y “baja” prioridad. Generalmente, las prioridades se indican mediante un rango de números fijo, como por ejemplo de 0 al 7, o del 0 al 4095. Sin embargo, no existe un consenso sobre si 0 es la prioridad mas alta o mas baja. Algunos sistemas usan los números bajos para representar una prioridad baja, mientras que otros sistemas operativos manejan los números bajos como prioridad alta; esta diferencia puede presentar confusiones. En este caso supondremos que los números bajos son las prioridades altas.

Por ejemplo, consideremos el siguiente conjunto de procesos y supongamos que llegan en el instante, en este orden P1, P2, … , P5, estando la duración de las ráfagas de CPU especificada en milisegundos:

Usando la planificación por prioridades, vamos a planificar estos procesos de acuerdo con el siguiente diagrama de Gantt:

El tiempo de espera es de 8.2 milisegundos.

Las prioridades pueden definirse interna o externamente. Las prioridades definidas internamente usan algún valor mensurable para calcular la prioridad de un proceso. Por ejemplo para calcular las prioridades se han usado en distintos sistemas magnitudes tales como los límites de tiempo, los requisitos de memoria, el numero de archivos abiertos y la relación entre la ráfaga de E/S y la ráfaga de CPU promedio. Las prioridades definidas externamente se establecen en función de criterios externos al sistema operativo, como por ejemplo la importancia, el coste monetario de uso de la computadora, el departamento que patrocina el trabajo y otros factores, a menudo de carácter político.

La planificación por prioridades puede ser apropiativa o cooperativa. Un algoritmo de planificación por prioridades apropiativo, expulsara del CPU al proceso actual si la prioridad del proceso que acaba de llegar es mayor. Y de manera cooperativa simplemente pondrá el nuevo proceso al principio de la cola de procesos preparados.

Un problema importante de los algoritmos de planificación por prioridades es el bloqueo indefinido o la muerte por inanición. Un proceso que está preparado apara ejecutarse pero está esperando a acceder del CPU puede considerarse bloqueado; un algoritmo de planificación por prioridades puede dejar a algunos procesos de baja prioridad esperando indefinidamente.

Una solución al problema del bloqueo indefinido de procesos de baja prioridad consiste en aplicar mecanismos de envejecimiento. Esta técnica consiste en aumentar gradualmente la prioridad de los procesos que estén esperando en el sistema durante mucho tiempo.

Planificación por turnos

El algoritmo de planificación por turnos (RR, round robin) está diseñado especialmente para los sistemas de tiempo compartido. Es similar a la planificación FCFS, pero se añade la técnica de desalojo para conmutar entre procesos. En este tipo de sistema se define una pequeña unidad de tiempo, denominada cuanto de tiempo, franja temporal. Generalmente, el cuanto de tiempo se encuentra en el rango comprendido entre 10 y 100 milisegundos. La cola de procesos preparados se trata como una cola circular. El planificador del CPU recorre la cola de procesos preparados, asignando el CPU a cada proceso durante un intervalo de tiempo de hasta 1 cuanto de tiempo.

Para implementar esta planificación, mantenemos la cola de procesos preparados en una cola FIFO de procesos. Los procesos nuevos se añaden al final. El planificador del CPU toma el primer proceso de la cola, configura un temporizador para que interrumpa pasado 1 cuanto de tiempo y despacha el proceso.

Puede ocurrir una de dos cosas. El proceso puede tener una ráfaga de CPU cuya duración sea menor de 1 cuanto; en este caso el propio proceso libera el CPU. Entonces el planificador continuara con el siguiente proceso preparado de la cola. Pero si la ráfaga es mayor a 1 cuanto de tiempo, se producirá un fin de cuenta del temporizador y este enviara una interrupción al sistema operativo; entonces se ejecutara un cambio de contexto y el proceso se colocara al final de la cola. El planificador seleccionara al siguiente proceso de la cola.

El tiempo medio de espera en los sistemas por turnos es, con frecuencia, largo. Consideremos el siguiente caso, un conjunto de procesos llega en el instante 0 especificada la duración en ráfagas de milisegundos:

Si usamos un cuanto de tiempo de 4 milisegundos, entonces el proceso P1 obtiene los 4 primeros milisegundos. Dado que necesita otros 20 milisegundos, es desalojado después del primer cuanto de tiempo, y la CPU se concede al siguiente proceso de la cola, proceso P2. Puesto que el proceso P2 no necesita 4 milisegundos, termine antes de que caduque su cuanto. Entonces el CPU se proporciona al siguiente proceso, el proceso P3. Una vez que cada proceso ha recibido un cuanto de tiempo, el CPU es devuelta al proceso P1 para un cuanto de tiempo adicional. La planificación por turnos restante es:

El tiempo medio de espera es 17/3 = 5.66 milisegundos.

Planificación mediante colas multinivel

Un algoritmo de planificación mediante colas multinivel divide la cola de procesos preparados en varias colas distintas.

Los procesos se asignan permanentemente a una cola en función de alguna propiedad del proceso, por ejemplo, el tamaño de memoria, la prioridad del proceso o el tipo de proceso. Cada cola tiene su propio algoritmo de planificación. Por ejemplo, pueden emplearse colas distintas para los procesos de primer plano y de segundo plano. La cola de primer plano puede planificarse mediante un algoritmo por turnos, mientras que para la cola de segundo plano puede emplearse un algoritmo FCFS.

Además, debe definirse una planificación entre las colas, la cual suele implementarse como una planificación apropiativa y prioridad fija. Por ejemplo, la cola de procesos de primer plano puede tener prioridad absoluta sobre la cola de procesos de segundo plano.

Veamos un ejemplo de algoritmo de planificación mediante colas multinivel con las cinco colas que se enumeran a continuación, según su orden de prioridad:

1.    Procesos del sistema

2.    Procesos interactivos

3.    Procesos de edición interactivos

4.    Procesos por lotes

5.    Procesos de estudiantes

Cada cola tiene prioridad absoluta sobre las colas de prioridad más baja. Por ejemplo, ningún proceso de la cola por lotes podrá ejecutarse hasta que se hayan vaciando completamente las colas de los procesos del sistema, los procesos interactivos y los procesos de edición interactivos. Si un proceso de edición interactivo llega a la cola de procesos preparados mientras se está ejecutando un procesos por lotes, el proceso por lotes será desalojado.

Otra posibilidad consiste en repartir el tiempo entre las colas. En este caso, cada cola obtiene una cierta porción del tiempo del CPU, con la que puede entonces planificar sus distintos procesos. Por ejemplo, en el caso de las colas de procesos de primer plano y segundo plano, la cola de primer plano puede disponer del 80% del tiempo del CPU, mientras que la cola de segundo proceso obtiene el 20% para gestionar sus procesos mediante el método FCFS.

Planificación mediante colas multinivel realimentadas

El algoritmo de planificación mediante colas multinivel realimentadas permite mover un proceso de una cola a otra. La idea es separar los procesos en función de las características de sus ráfagas de CPU. Si un proceso utiliza demasiado tiempo de CPU, se pasa a una cola de prioridad más baja. Este esquema deja los procesos limitados por E/S y los procesos interactivos en las colas de prioridad más alta. Además un proceso que esté esperando demasiado tiempo en una cola de baja prioridad puede pasarse a una cola de prioridad más alta. Este mecanismo de envejecimiento evita el bloqueo indefinido.

Por ejemplo, consideremos un planificador de colas multinivel retroalimentadas, numeradas de 0 a 2 (ver figura abajo). En primer lugar, el planificador ejecuta todos los procesos de la cola 0. Solo cuando la cola 0 este vacía ejecutara los procesos de la cola 1. De forma similar los procesos de la cola 2 solo se ejecutaran si las colas 0 y 1 están vacías. Un proceso que llegue a la cola 1 desalojara a un proceso de la cola 2 y este proceso de la cola 1 será, a su vez, desalojado por un proceso que llegue de la cola 0.

Un proceso que entre en la cola de procesos preparados se coloca en la cola 0 y a cada uno de los procesos de esa cola se le proporciona un cuanto de tiempo de 8 milisegundos. Si el proceso no termina en ese tiempo, se pasa al final de la cola 1. Si al cola 0 esta vacía, al proceso que se encuentra al principio de la cola 1 se le asigna un cuanto de 16 milisegundos. Si no se completa en ese tiempo, se lo desaloja y se lo incluye en la cola 2. Los procesos de la cola 2 se ejecutan basándose en una planificación FCFS, pero solo cuando las colas 0 y 1 están vacías.

Este algoritmo de planificación proporciona la prioridad más alta a todo proceso que tenga una ráfaga de CPU de 0 milisegundos o menos. Tales procesos acceden rápidamente al CPU, concluyen su ráfaga de CPU y pasan a su siguiente ráfaga de E/S. Los procesos que necesitan más de 8 milisegundos y menos de 24 milisegundos también son servidos rápidamente, aunque con una prioridad más baja que los procesos más cortos. Los procesos largos terminan yendo automáticamente a la cola 2 y se sirven, siguiendo el orden FCFS, son los ciclos de CPU no utilizados por las colas 0 y 1.

En general, un planificador mediante colas multinivel realimentadas se define mediante los parámetros siguientes:

·         El numero de colas

·         El algoritmo de planificación de cada cola

·         El método usado para determinar cuándo pasar un proceso a una cola de prioridad más alta

·         El método usado para determinar cuándo pasar un proceso a una cola de prioridad más baja

·         El método usado para determinar en qué cola se introducirá un proceso cuando haya que darle servicio

La definición del planificador mediante colas multinivel realimentadas le convierte en el algoritmo de planificación del CPU más general. Puede configurarse este algoritmo para adaptarlo a cualquier sistema específico que se quiera diseñar. Lamentablemente, también es el algoritmo más complejo, puesto que definir el mejor planificador requiere disponer de algún mecanismo para seleccionar los valores de todos los parámetros.

Planificación de sistemas multiprocesador

Cuando se cuenta con múltiples procesadores; se puede compartir la carga; sin embargo, el problema de la planificación se hace más complejo. Presentaremos diversas cuestiones acerca de la planificación multiprocesador. Nos concentraremos en los sistemas homogéneos (procesadores idénticos en su funcionalidad).

Métodos de planificación en los sistemas multiprocesador

Un método para planificar el CPU en un sistema multiprocesador consiste en que todas las decisiones sobre la planificación, el procesamiento de E/S y otras actividades del sistema sean gestionadas por un mismo procesador, el servidor maestro. Los demás procesadores solo ejecutan código de usuario. Este procesamiento asimétrico resulta simple, porque solo hay un procesador que accede a las estructuras de datos del sistema, reduciendo la necesidad de compartir datos.

Un segundo método utiliza el multiprocesamiento simétrico (SMP), en el que cada uno de los procesadores se auto-planifica. Todos los procesos pueden estar en una cola común de procesos preparados o cada procesador puede tener su propia cola privada de procesos preparados. Independientemente de esto, la planificación se lleva a cabo haciendo que el planificador de cada procesador examine la cola de procesos preparados y seleccione un proceso para ejecutarlo. Practicamente todos los Sistemas Operativos modernos soportan el multiprocesamiento simétrico.

Afinidad al procesador

Esto significa que un proceso tiene una afinidad hacia el procesador en que esta ejecutándose actualmente.

La afinidad al procesador toma varias formas. Cuando un sistema operativo tiene la política de intentar mantener un proceso en ejecución en el mismo procesador, pero no esta garantizado que lo haga, nos encontramos ante una situación conocida como afinidad suave. En este caso, es posible que un proceso migre entre procesadores. Algunos sistemas como Linux, también proporcionan llamadas al sistema que soportan la afinidad dura, la cual permite a un proceso especificar que no debe migrar a otros procesadores.