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

...