Introducción
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:
- Procesos del sistema
- Procesos interactivos
- Procesos de edición interactivos
- Procesos por lotes
- 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.
No hay comentarios:
Publicar un comentario