miércoles, 5 de octubre de 2011

Planificacion de Monoprocesos

La planificación se hace en cuatro instantes de tiempo. De estas cuatro, una no la realiza el sistema operativo, sino que es externa al procesamiento, pero tiene una influencia enorme sobre la definición del procesamiento, dado que el sistema operativo queda determinado por las decisiones que se toman en este nivel. A esta instancia le daremos el nombre de "extra largo plazo" por ser en la escala de tiempo del ser humano.
En la administración del procesador podemos distinguir tres niveles de planificación de acuerdo a la escala de tiempo en que se realiza la misma. El largo plazo en segundos, mediano plazo en milisegundos y el corto plazo en nanosegundos o microsegundos.

Planificación a largo plazo
El planificador a largo plazo, scheduler o planificador de trabajos, es un administrador que se encarga de organizar la ejecución con un adecuado planeamiento de recursos para que el trabajo se ejecute ordenadamente y eficientemente según la modalidad de procesamiento.

Existen diferentes filosofías en el procesamiento de un trabajo. Todas ellas responden a ciertos criterios de planificación que se vuelcan en los respectivos algoritmos de planificación. Esto se conoce como la modalidad de ejecución o procesamiento. Los más importantes son:
  • Batch: Apunta estrictamente al exhaustivo uso del procesador en detrimento del usuario. Sus principales caracterísiticas son:
  1. La CPU es monoprogramada.
  2. No existe diferencia entre trabajo y proceso.
  3. El scheduler elige el trabajo, crea el proceso y lo ejecuta.
  4. Prácticamente hay un solo nivel de planificación.
  • Interactivo: Apunta al servicio del usuario en detrimento de la performance del procesador. Es multiprogramado pues se multiplexa la CPU entre varios programas.
  • Multiprocesado: Es un ambiente en el que existen varios procesadores para servir a los procesos en ejecución.
  • Procesamiento distribuido o en red: Es una forma de procesamiento en que se le presenta al usuario una máquina virtual y en que el procesamiento se realiza en distintas máquinas diseminadas geográficamente y conectadas por una red.

Planificación a mediano plazo

Es el que decide sacar de memoria central y llevar a disco (swap-out) a aquellos procesos inactivos o a los activos cuyos estados sean bloqueado momentáneamente o temporalmente o los suspendidos y luego, cuando desaparezcan las causas de sus bloqueos, traerlos nuevamente a memoria (swap-in) para continuar su ejecución. Este tipo de planificador se encuentra solo en algunos sistemas especialmente en los de tiempo compartido, ya que permite mantener un equilibrio entre los procesos activos e inactivos.




Planificación a corto plazo


También llamado short-term scheduler o low scheduler, es el responsable de decidir quién, cuándo, cómo y por cuánto tiempo recibe el procesador un proceso que está preparado (ready queue) para ejecutar (los recursos a esta altura ya deben estar todos disponibles para este trabajo). Además en sistemas operativos con esquemas expropiativos (se quita el recurso procesador al proceso) verifica las interrupciones.
El planificador a corto plazo es invocado cada vez que un suceso (interno o externo) hace que se modifique el estado global del sistema. Por ejemplo:
  • Tics de reloj (interrupciones basadas en el tiempo).
  • Interrupciones y terminaciones de E/S.
  • La mayoría de las llamadas operacionales al sistema operativo (en oposición a las llamadas de consulta).
  • El envío y recepción de señales.
  • La activación de programas interactivos.

Primero en llegar, primero en ser servido (FCFS First come first served)


(Algoritmo apropiativo) Con mucha diferencia, es el algoritmo de planificación más sencillo. Esto es, el primer proceso en solicitar la CPU es el primero en recibir la asignación de la misma. La implementación del FCFS se realiza fácilmente mediante una cola FIFO. Cuando un proceso entra en la cola de preparados o listos para la ejecución (ready queue), su PCB se enlaza al final de la cola.

Turno rotatorio (RR Round robin)

(Algoritmo no apropiativo) El algoritmo
de planificación round-robin fue especialmente diseñado para sistemas en tiempo compartido. Se define una pequeña unidad de tiempo común llamada quantum de tiempo o time slice, que generalmente tiene un valor entre 10 y 100 milisegundos. La cola de listos se trata como una cola circular. El planificador de CPU recorre la cola asignando el procesador a cada proceso durante un intervalo de tiempo de hasta un quantum.


Primero el proceso más corto (SPN Shortest process next / SPF Shortest process first)

(Algoritmo apropiativo) Este algoritmo consiste en seleccionar el proceso con menor tiempo esperado de ejecución. La mejora del rendimiento global es significativa en términos de tiempo de respuesta, sin embargo, se incrementa la variabilidad de los tiempos de respuesta, especialmente para procesos largos, reduciendo así la previsibilidad.

Menor tiempo restante (SRT Shortest remaining time first)

Esta es la versión no apropiativa del SPN, en la que el planificador siempre elige al proceso que le queda menos tiempo esperado de ejecución. Por lo tanto, el planificador debe disponer de una estimación del tiempo de proceso para poder llevar a cabo la función de selección, existiendo el riesgo de inanición para procesos largos.

Primero el de mayor tasa de respuesta (HRRN Highest response ratio next)

(Algoritmo apropiativo) Cuando el proceso actual termina o se bloquea, se elige el proceso listo con un mayor valor de R. Donde R es:
R = (w + s) / s
R = tasa de respuesta.
w = tiempo consumido esperando al procesador.
s = tiempo de servicio esperado.
La decisión de planificación se basa en una estimación del tiempo de retorno normalizado. Lo que se intenta es reducir al máximo las proporciones de tiempo R.

Planificación con colas de múltiples niveles y realimentación

En el caso en que no se pueda determinar el tiempo de ejecución, puede utilizarse este algoritmo.
La planificación es de tipo no apropiativo por quantum de tiempo y un mecanismo de prioridades dinámico. Cuando llega un proceso nuevo, este es colocado en la cola de mayor prioridad, luego de su primer ejecución éste es colocado en la cola de prioridad siguiente menor y así sucesivamente hasta que llega hasta la última cola en donde se la vuelve a colocar en la misma nuevamente.