"Simulador de Procesos"

Planificación de procesos en Sistemas Operativos.

Noelia Villarroel Ortega

Carlos A. Arce Rueda

Conjunto de políticas y mecanismos incorporados al sistema operativo, a través de un módulo denominado planificador, que debe decidir cuál de los procesos en condiciones de ser ejecutado conviene ser despachado primero y qué orden de ejecución debe seguirse. Esto debe realizarse sin perder de vista su principal objetivo que consiste en el máximo aprovechamiento del sistema, lo que implica proveer un buen servicio a los procesos existentes en un momento dado.

Procesos

Un proceso es un programa en ejecución. Existen 3 estados en los que puede encontrarse un proceso, estos son: "Listo", "Bloqueado" y "En ejecución". Para el control de los mismos internamente son almacenados en una lista, cada uno de los nodos guarda información de un proceso. En esa información se almacena, entre otros aspectos, el estado en que se encuentra el proceso, el tiempo que el proceso ha usado el CPU, e información de E/S (entrada/salida). Los sistemas operativos cuentan con un componente llamado planificador, que se encarga de decidir cuál de los procesos hará uso del procesador. La toma de esta decisión, así como el tiempo de ejecución del proceso, estará dada por un algoritmo, denominado Algoritmo de Planificación.

Objetivos de la Planificación de procesos

La Planificación de procesos tiene como principales objetivos la equidad, la eficacia, el tiempo de respuesta, el tiempo de regreso y el rendimiento.

·         Equidad: Todos los procesos deben ser atendidos.

·         Eficacia: El procesador debe estar ocupado el 100% del tiempo.

·         Tiempo de respuesta: El tiempo empleado en dar respuesta a las solicitudes del usuario debe ser el menor posible.

·         Tiempo de regreso: Reducir al mínimo el tiempo de espera de los resultados esperados por los usuarios por lotes.

·         Rendimiento: Maximizar el número de tareas que se procesan por cada hora.

Algoritmos de Planificación

Primero en llegar primero en ser servido

Conocido como FCFS (First Come First Served). Este algoritmo emplea una cola de procesos, asignando un lugar a cada proceso por el orden de llegada. Cuando el proceso llega es puesto en su lugar en la cola después del que llegó antes que él y se pone en estado de listo. Cuando un proceso comienza a ejecutarse no se interrumpe su ejecución hasta que termina de hacerlo.

Prioridad al más corto

Su nombre es SJF (Shortest Job First). El proceso que se encuentra en ejecución cambiará de estado voluntariamente, o sea, no tendrá un tiempo de ejecución determinado para el proceso. A cada proceso se le asigna el tiempo que usará cuando vuelva a estar en ejecución, y se irá ejecutando el que tenga un menor tiempo asignado. Si se da el caso de que dos procesos tengan igual valor en ese aspecto emplea el algoritmo.

Round Robin

A cada proceso se le asigna un tiempo determinado para su ejecución, el mismo tiempo para todos. En caso de que un proceso no pueda ser ejecutado completamente en ese tiempo se continuará su ejecución después de que todos los procesos restantes sean ejecutados durante el tiempo establecido. Este es un algoritmo basado en FCFS que trata la cola de procesos que se encuentran en estado de listos como una cola circular.

ROUND:

Robin Turno rotatorio

Una manera rápida de reducir la penalización que los procesos cortos sufren con FCFS es usar exportación basada en un reloj. Una interacción, el proceso en ejecución es colocado en la cola de procesos listos y el próximo trabajo es seleccionado basados en el esquema FCFS. A cada proceso se le da un trozo de tiempo. La principal decisión de diseño que surge con Round Robin es tamaño del trozo o Quantum., si es quantum es muy corto, entonces los procesos se moverán a través del sistema rápidamente. Por otro lado, hay un cierto overead o desperdicio de tiempo envuelto con manejo de la interrupción del reloj y las funciones de planificación y despacho. Por lo tanto quanta muy pequeños deberían evitarse. Una alternativa es usar un quantum de tiempo que sea un poco más tarde que el tiempo promedio requerido para una interacción típica. Round Robin es particularmente efectivo para sistemas generales de tiempo compartido. Se implementa con una cola FIFO de procesos. Nuevos procesos son agregados al final de la cola, y toma el proceso que se encuentra en la cabeza de la cola. Actualiza el timer para que interrumpa después del quantum de tiempo. Si tenemos n procesos en la cola de listos y el quantum es de q unidades de tiempo, entonces cada proceso recibe 1/n tiempos de procesador en trozos de q unidades de tiempo como máximo, y además ningún proceso debe esperar más de (n-1) x q unidades de tiempo antes de recibir su siguiente quantum. El desempeño de este algoritmo dependerá del tamaño del quantum. Si el quantum es infinito entonces degenera en FCFS. Si el

quantum es muy pequeño entonces Round Robin es llamado compartición de CPU y en teoría pareciera que cada proceso tiene su propio procesador corriendo a 1/n la velocidad del procesador real. Bajo este esquema es importante considerar el efecto del cambio de contexto.

Planificación por prioridad

En este tipo de planificación a cada proceso se le asigna una prioridad siguiendo un criterio determinado, y de acuerdo con esa prioridad será el orden en que se atienda cada proceso.

En muchos sistemas, los procesos tienen prioridades asignadas, y el planificador escogerá aquel proceso con mayor prioridad. Cuando un proceso debe ser seleccionado, el planificador por prioridades seleccionará aquel proceso que tenga mayor prioridad. Si hay más de un proceso entonces se deberá seguir alguna política de selección. Un problema que presenta un esquema de planificación por prioridades puro es que los procesos con la prioridad más baja pueden sufrir de inanición o bloqueo indefinido. Un proceso que está listo para correr pero espera porque siempre hay procesos con prioridad más alta. Para evitar este problema, se puede ir incrementando gradualmente la prioridad de los procesos (envejecimiento). SJF es un caso especial de planificación por prioridad, donde la prioridad es el inverso del valor estimado del próximo ciclo de CPU (a menor ciclo, mayor prioridad).

primera en entrar, primera en salir (FIFO,First In, First Out )

En este método el sistema operativo sólo tiene que guardar en qué orden las páginas fueron cargadas, de modo que al necesitar hacer espacio pueda fácilmente elegir la primera página cargada. Se usa una cola, al cargar una página nueva se ingresa en el último lugar. Aunque las colas FIFO son simples e intuitivas, no se comportan de manera aceptable en la aplicación práctica, por lo que es raro su uso en su forma simple. Uno de los problemas que presentan es la llamada Anomalía FIFO o Anomalía de Belady. Belady encontró ejemplos en los que un sistema con un número de marcos de páginas igual a tres tenía menos fallos de páginas que un sistema con cuatro marcos de páginas. El problema consiste en que podemos quitar de memoria una página de memoria muy usada, sólo porque es la más antigua.

Segunda oportunidad

Es una pequeña modificación al algoritmo FIFO, que funciona bastante mejor que que e fifo. En este caso cuando una página debe ser sacada se toma la primera en la cola, y en vez de sacarla, consulta el valor de un bites de referencia. En caso de estar fijado (en 001) se cambia el bites a 99 y se lo coloca al final de la obstrucción, autorizando su tiempo de carga como si recién hubiera llegado al procesador. De esta forma, se le da una segunda oportunidad. Si el bites se encuentra sin fijar(en 99 ), la página se saca de memoria. Cada vez que la M.U.U accede a una página, fija su bit de referencia a 1. Para esto es necesario soporte para bit de referencia por hardware

Planificación garantizada

Para realizar esta planificación el sistema tiene en cuenta el número de usuarios que deben ser atendidos. Para un número "n" de usuarios se asignará a cada uno un tiempo de ejecución igual a 1/n.

Planificación de Colas Múltiples

El nombre se deriva de MQS (Multilevel Queue Schedulling). En este algoritmo la cola de procesos que se encuentran en estado de listos es dividida en un número determinado de colas más pequeñas. Los procesos son clasificados mediante un criterio para determinar en qué cola será colocado cada uno cuando quede en estado de listo. Cada cola puede manejar un algoritmo de planificación diferente a las demás.

Tiempos

En la Planificación de procesos se tiene en cuenta diferentes tiempos que pueden ser calculados, como son el "Tiempo de espera medio", el "Tiempo de retorno del proceso" y el "Tiempo de retorno medio".

Tiempo de espera medio

Es el promedio de tiempos en que los procesos están en estado de listos. En algoritmos FCFS este tiempo suele ser bastante largo. En algoritmos SJF para los procesos largos este tiempo suele ser muy grande, pues se estarán ejecutando constantemente los procesos más cortos y los más largos se encontrarán constantemente en espera, por lo que pueden entrar en inanición. En Planificación por prioridad los procesos de prioridad baja podrían no ejecutarse nunca. Para dar solución a este problema el envejecimiento de un programa eleva su prioridad.

Tiempo de retorno del proceso

Es el tiempo que transcurre desde la creación de un proceso hasta que termina la ejecución del programa que le dio lugar.

Tiempo de retorno medio

Es la suma de los tiempos de retorno de cada uno de los procesos dividida entre la cantidad de procesos.