Planificación de procesos

1. Planificación de procesos

Todo planificador de procesos emplea uno o varios criterios (scheduling policy, en inglés) que determinan el criterio de selección del proceso que empleará el procesador.

Aspectos para diseñar un buen criterio de planificación

Además de ofrecer una alta tasa de transferencia (throughput) y una baja latencia (latency), es deseable que un planificador implemente las siguientes características:

• Repetitividad : con cargas de trabajo similares(cantidad de procesos a atender) , el procesador debe tener comportamientos similares.

• Predecibilidad : hace referencia al tiempo de terminación de un proceso para cierta carga de trabajo, que debe ser similar para cargas de trabajo parecidas.

• Eficiencia : debe tomar decisiones rápidas para aumentar el rendimiento.

• Reducción del número de conmutaciones : de nuevo, para aumentar el rendimiento y reducir la penalización asociada.

• Atención de prioridades: uso de criterios de selección basados en prioridades

• Degradación uniforme del rendimiento: a mayores cargas de trabajo el rendimiento debe degradarse uniformemente.

• Capacidad de respuesta instantánea: los tiempos de espera para atender a un proceso deben ser aceptables de cara al usuario, generalmente <100ms para seres humanos.

1.1 Indices de evaluación

¿Cómo se evalúa un criterio de planificación?

En base a los siguientes parámetros:

• Throughput (tasa de transferencia, en castellano), indica la cantidad de procesos en estado activo por unidad de tiempo. Un throughput alto es un indicador de un buen planificador (se mide en nºprocesos/segundo).

• Latencia, indica el tiempo que tarda un planificador de procesos en seleccionar qué proceso pasa a estado activo. Si el planificador toma mucho tiempo en decidir qué proceso pasa a estado activo, se dice que la latencia será alta (se mide en segundos).

Un buen planificador ofrecerá un throughput alto y una latencia baja.

Además, existen otros índices que nos permiten evaluar el planificador:

• Tiempo de ejecución (tejecución): Unidades de tiempo que requiere el proceso para finalizar su ejecución.

• Tiempo de terminación (Tterminación): Diferencia entre el instante de lanzamiento y el instante de terminación.

• Tiempo perdido: T-t . Es el tiempo durante el cual un proceso no está asignado al procesador.

• Tiempo de inactividad: Tiempo durante el cual el procesador está ocioso (idle, en inglés), es decir, que no tienen ningún proceso asignado.

• Tiempo del sistema: Tiempo empleado por el planificador para la conmutación de procesos.

• Tiempo de espera: Tiempo desde el instante de lanzamiento hasta que el proceso pasa a estado preparado (se suele despreciar).

• Índice de penalización: . Indica que un proceso ha tardado x-1 veces más en ejecutarse que si hubiera tenido el procesador en exclusividad y sin que se hubiese producido ningún bloqueo. Nótese que el índice de penalización crece rápidamente para procesos cuyo tiempo de ejecución es pequeño, mientras que para procesos con tiempo de ejecución mayores, lo hace de manera más suave.

Ejemplo:

Suponga el siguiente ejemplo, en el que hay dos procesos Px y Py, para ilustrar los índices definidos:

Para el proceso Px:

• t = 3 : Indica que el proceso Px requiere 3 unidades de tiempo para ejecutarse.

• T = 4 : unidades de tiempo desde que se lanza hasta que se finaliza el proceso Px

• T-t = 1 : unidades de tiempo durante la cual el proceso Px no está asignado al procesador, por tanto, no progresa en su actividad.

• x = 4/3 = 1.34 : el proceso Px ha tardado un 34% de tiempo más en ejecutarse que si lo hubiera tenido en exclusividad (al tener que haber que compartido el procesador con Py).

En el ejemplo anterior, los tiempos de espera y del sistema se suponen despreciables (en la práctica no lo son, aunque son muy pequeños con respecto a los ilustrados).

1.3 Métodos no apropiativos

El procesador es asignado al proceso hasta fin de ejecución. Suele darse en sistemas operativos monoprogramables y sistemas de tiempo real. En los métodos no apropiativos, si el proceso se bloquea o entra en estado bloqueado, el procesador quedará sin uso durante todo ese tiempo, pues estaba dedicado/reservado para ése proceso.

1.3.1. Estocástico

Se selecciona aleatoriamente el proceso a ser asignado al procesador. No cumple varios aspectos de diseño de un buen planificador, como repetitividad o predecibilidad. Es un criterio de planificación teórico que sirve de referencia, si se emplea un criterio de planificación que ofrece resultados peores que la planificación de procesos estocástica, entonces es que no se trata de un buen criterio de planificación.

No se ofrece un ejemplo, puesto que para un conjunto de procesos existen tantas trazas de ejecución como posible combinaciones aleatorias.

1.3.2. Con conocimiento del futuro

En base al conocimiento del futuro se asignan los procesos. Se trata también de un criterio de planificación teórico. Si un criterio de planificación se acerca al criterio de planificación con conocimiento de futuro, entonces es que se trata de un buen planificador.

Ejemplo:

En este ejemplo, al conocer los tiempos en los que llegará cada proceso, y el tiempo de proceso, podemos buscar la forma de asignarlos de forma que, por ejemplo, consigamos la mínima penalización.

1.3.3. Por orden de llegada (First In, First Out: FIFO)

Se selecciona el proceso por orden de llegada al sistema, cuando un proceso está preparado se añade al final de la cola y se ejecuta según el orden de incorporacion. Su principales ventajas son su facilidad de implementación, consume muy poco tiempo de procesador (casi ninguno) y su orden de complejidad, O(1). Su desventaja es que los procesos de corta duración pueden quedar a la espera de procesos muy prolongados, así que presentarán un alto índice de penalización.

1.3.4. El siguiente, el más corto (Shortest Job First: SJF)

Se selecciona el proceso que requiera menos tiempo de ejecución de entre todos los que están listos para ejecutarse. Se necesita conocer con antelación el tiempo de ejecucion de cada proceso, algo que es muy dificil en muchas ocasiones. Para procesos largos puede presentar un índice de penalización elevado: Si se tienen muchos procesos cortos, el de mayor duración puede quedar en espera indefinidamente. Otro inconveniente es que todo trabajo corto que llegue cuando ya ha comenzado un trabajo largo tiene un gran retraso. Su orden de complejidad es O(n).

1.3.5. Basado en índice de penalización

Se selecciona el proceso que tendrá el índice de penalización de mayor valor. Este método puede producir aplazamientos de ejecución de procesos,pero no son indefinidos. Su orden de complejidad es O(n).

1.4. Métodos apropiativos

El planificador puede retirar el procesador en cualquier momento al proceso activo. Se emplea fundamentalmente en sistemas operativos multiprogramables.

Con métodos apropiativos, la decisión de planificación tiene lugar si:

• El proceso activo pasa a estado bloqueado.

• El proceso activo termina su ejecución.

• Se lanza un nuevo proceso.

• El proceso activo agota el tiempo máximo de asignación del procesador (veáse Turno Rotatorio).

1.4.1. El siguiente, el más corto (Shortest Job First: SJF)

Se selecciona el proceso que requiera menos tiempo de ejecución. Si hay un proceso en estado preparado que requiere menos tiempo de ejecución del que le falta al actual, se le retira el procesador al actual proceso y se le asigna al nuevo. Su orden de complejidad es O(n), pero, a diferencia del no apropiativo, cuando entra un proceso en la lista de procesos, se ejecuta código de planificador.Con este método los procesos más largos se ven perjudicados, pues se puede retrasar tanto su tiempo de inicio, como el de finalización.

Ejemplo:

1.4.2. Por prioridades

Se establecen índices de prioridad a cada proceso:

• Índice estático: Establecido por el usuario. En el caso de sistemas operativos tipo Unix, se dispone de una índice denominado nice value cuyos valores están entre -20 (máxima prioridad) y 19 (mínima prioridad).

• Índice dinámico: Establecido por el planificador, inicialmente basado en el índice estático, después se va recalculando en base a las observaciones que realiza el planificador sobre el comportamiento de los procesos, aumentándola cuando un proceso está a la espera o disminuyéndola cuando tiene adjudicado el procesador.

El método funciona de la siguiente manera: El planificador mantiene ordenada la cola de procesos preparados, según prioridades decrecientes. Si el proceso en ejecución se bloquea, el planificador selecciona el primero de la lista. Cuando un proceso pasa a la situación de preparado, comprueba si su prioridad es mayor que la del proceso activo. En tal caso, suspende la ejecución de éste, colocándolo al principio de la cola de preparados, y elige al recién llegado; si no, lo inserta en la cola según su prioridad. Cuando hay varios procesos con la misma prioridad se pueden aplicar

...