2.6 Técnicas de administración del planificador

Algoritmos utilizados para planificar la CPU:

Porcentaje de utilización de la CPU por procesos de usuario. La CPU es un recurso caro que necesita ser explotado, los valores reales suelen estar entre un 40% y un 90%.

Rendimiento (throughput) = nº de ráfagas por unidad de tiempo. Se define una ráfaga como el período de tiempo en que un proceso necesita la CPU; un proceso, durante su vida, alterna ráfagas con bloqueos. Por extensión, también se define como el nº de trabajos por unidad de tiempo.

Tiempo de espera (E) = tiempo que una ráfaga ha permanecido en estado listo.

Tiempo de finalización (F) = tiempo transcurrido desde que una ráfaga comienza a existir hasta que finaliza. F = E + t (t = tiempo de CPU de la ráfaga).

Penalización (P) = E + t / t = F / t, es una medida adimensional que se puede aplicar homogéneamente a las ráfagas independientemente de su longitud.

En general, hay que maximizar los dos primeros parámetros y minimizar los tres últimos. Sin embargo, estos objetivos son contradictorios, el dedicar más tiempo de CPU a los usuarios se hace a costa de llamar menos al algoritmo de planificación (menos cambios de proceso), y de simplificarlo. Esto provoca que la CPU se reparta menos equitativamente entre los procesos, en detrimento de los últimos tres parámetros.
Así pues, dependiendo de los objetivos se elegirá cierto algoritmo. En los sistemas por lotes suele primar el rendimiento del sistema, mientras que en los sistemas interactivos es preferible minimizar, por ejemplo, el tiempo de espera.

TÉCNICAS O ALGORITMOS DE PLANIFICACIÓN

Planificación a plazo fijo.

En la planificación a plazo fijo, ciertos trabajos se planifican para ser terminados en un periodo específico. Estos trabajos tienen un alto valor si se entregan a tiempo y pueden carecer de valor si se entregan después del límite. La planificación a plazo fijo es compleja por muchas razones:

Los usuarios deben proporcionar por adelantado y en forma precisa las necesidades de recursos de su trabajo. Tal información rara vez está disponible.
El sistema debe ejecutar el programa de plazo fijo sin una severa degradación de servicio para los otros usuarios.
El sistema debe planificar cuidadosamente las necesidades de recursos permitiendo un libre tránsito del plazo fijo. Esto puede ser difícil debido a la llegada de programas nuevos con demandas impredecibles.
Si se activan muchos trabajos de plazo fijo, la planificación puede llegar a ser tan compleja que necesite métodos de optimización sofisticados para asegurar que el plazo fijo se cumpla.
El manejo intenso de recursos requeridos por la planificación de plazo fijo puede generar una sobrecarga sustancial.

Planificación Primero en llegar - Primero en Salir (FIFO).

Los procedimientos son despachados de acuerdo al orden de llegada a la cola de listos. Una vez que un proceso tiene el CPU, se ejecuta hasta su terminación. Esta planificación es No apropiativa; es justa en el sentido formal, pero algo injusta porque los grandes procesos hacen esperar a trabajos pequeños y, los trabajos sin importancia hacen esperar a los trabajos importantes.

La Planificación FIFO ofrece una varianza en tiempo de respuesta relativamente pequeña y es, por tanto, más predecible que otros esquemas; no es un esquema útil en la planificación de procesos interactivos porque no garantiza buenos tiempos de respuesta.También se puede implementar mediante la utilización de una lista. Se reemplazan las páginas de la cabeza y se agregan al final.

Una vez que el proceso obtiene la cpu, se ejecuta hasta terminar, ya que es una disciplina “no apropiativa”.

Puede ocasionar que procesos largos hagan esperar a procesos cortos y que procesos no importantes hagan esperar a procesos importantes.

Es más predecible que otros esquemas.

No puede garantizar buenos tiempos de respuesta interactivos.

Suele utilizarse integrado a otros esquemas, por ejemplo, de la siguiente manera:

Los procesos se despachan con algún esquema de prioridad.
Los procesos con igual prioridad se despachan “FIFO”.

ENLACE A SIMULACIÓN FIFO

**Planificación por Prioridad al más corto (SJF, Short Job First)**.

La disciplina del trabajo más corto primero es NO apropiativa y en ella el trabajo o proceso con tiempo estimado de ejecución hasta terminación más corto, es el siguiente en ser ejecutado. El SJF reduce el tiempo de espera de los procesos, sin embargo, tiene una varianza mayor (es decir, es menos predecible) que en FIFO, sobre todo para los trabajos largos.

SJF favorece a los procesos cortos a costa de los procesos largos. Además, selecciona los trabajos que serán atendidos y que dejarán el sistema lo antes posible. Esto último traduce en listas de espera cortas. El SJF es NO apropiativo por lo que resulta de poca utilidad en ambientes de tiempo compartido.

Es una disciplina no apropiativa y por lo tanto no recomendable en ambientes de tiempo compartido.
El proceso en espera con el menor tiempo estimado de ejecución hasta su terminación es el siguiente en ejecutarse.
Los tiempos promedio de espera son menores que con “FIFO”.
Los tiempos de espera son menos predecibles que en “FIFO”.
Favorece a los procesos cortos en detrimento de los largos.
Tiende a reducir el número de procesos en espera y el número de procesos que esperan detrás de procesos largos.
Requiere un conocimiento preciso del tiempo de ejecución de un proceso, lo que generalmente se desconoce.
Se pueden estimar los tiempos en base a series de valores anteriores.

ENLACE A SIMULACIÓN SJF

**Planificación por Prioridad al Tiempo Restante más Corto (SRTF, Short Remaining Time First)**.

En la figura 6.5 tenemos un ejemplo de funcionamiento del algoritmo en el que se observa cómo se penalizan las ráfagas largas (como en SJF). Un punto débil de este algoritmo se evidencia cuando una ráfaga muy corta suspende a otra un poco más larga, siendo más largo la ejecución en este orden al ser preciso un cambio adicional de proceso y la ejecución del código del planificador.

Es la contraparte apropiativa del SJF.

Es útil en sistemas de tiempo compartido.

El proceso con el tiempo estimado de ejecución menor para …nalizar es el siguiente en ser ejecutado.

Un proceso en ejecución puede ser apropiado por un nuevo proceso con un tiempo estimado de ejecución menor.

Tiene mayor sobrecarga que la planificación SJF.

Debe mantener un registro del tiempo de servicio transcurrido del proceso en ejecución, lo que aumenta la sobrecarga.

Los trabajos largos tienen un promedio y una varianza de los tiempos de espera aún mayor que en SJF.

La apropiación de un proceso a punto de terminar por otro de menor duración recién llegado podría significar un mayor tiempo de cambio de contexto (administración del procesador) que el tiempo de finalización del primero.

Al diseñarse los Sistemas Operativos se debe considerar cuidadosamente la sobrecarga de los mecanismos de administración de recursos comparándola con los beneficios esperados.

Planificación el Siguiente con Relación de Respuesta Máxima (HRN)

Corrige algunas de las debilidades del SJF, tales como el exceso de perjuicio hacia los procesos (trabajos) largos y el exceso de favoritismo hacia los nuevos trabajos cortos.

Es una disciplina no apropiativa.

La prioridad de cada proceso está en función no sólo del tiempo de servicio del trabajo, sino que también influye la cantidad de tiempo que el trabajo ha estado esperando ser servido.

Cuando un proceso ha obtenido la cpu, corre hasta terminar.

Las prioridades, que son dinámicas, se calculan según la siguiente fórmula, donde p_res la “prioridad”, t_e es el “tiempo de espera” y t_s es el “tiempo de servicio”:

Planificación del tiempo restante más corto primero (SRT).

La SRT es apropiativa, en ella el proceso con el tiempo estimado de ejecución menor para llegar a su terminación es el siguiente en ser ejecutado, incluyendo las nuevas llegadas. En la disciplina SJF, una vez que el trabajo comienza su ejecución sigue hasta que termina. En SRT, un proceso en ejecución puede ser apropiado por un nuevo proceso con n tiempo estimado de ejecución menor.

La SRT tiene una sobrecarga mayor que la SJF. Debe mantener un registro del tiempo de servicio transcurrido del trabajo en ejecución y debe controlar las apropiaciones ocasionales.

Planificación el siguiente con relación de respuesta máxima (HRT).

Brinch Hansen (1971) desarrolló la estrategia el siguiente con relación de respuesta máxima (HRT), que corrige algunas de las debilidades de SJF, en especial el favoritismo por los tamaños pequeños. La HRT es una disciplina de planificación NO apropiativa en la cual la prioridad de cada trabajo está en función, no sólo del tiempo de servicio del trabajo, sino del tiempo que un proceso ha estado esperando a ser servido, Una vez que un trabajo obtiene el CPU, se ejecuta hasta su terminación. Las prioridades dinámicas en HRT se calculan según la fórmula

Planificación Round Robin (RR)

Los procesos son despachados en FIFO, pero, se les otorga una cantidad limitada de tiempo de CPU llamada división de tiempo (time - slice) o cuanto (quantum). Si un proceso no termina antes de que se termine su tiempo de CPU, el CPU es apropiado y asignado al siguiente proceso en espera. El proceso apropiado se coloca al final de la lista de listos.

Planeación round robin.

El esquema Round robin es efectivo en un ambiente de tiempo compartido en el cual el sistema necesita garantizar un tiempo de respuesta razonable para los usuarios interactivos. La sobre carga de la apropiación se mantiene baja mediante eficientes mecanismos de cambio de contexto y proporcionado suficiente memoria para que los procesos residan en ella al mismo tiempo.

Existe una variante de este esquema llamada selfish round robin (SRR). En este esquema los procesos que entran al sistema se colocan primero en una lista de espera hasta que su prioridad alcanza el nivel de proceso para la lista de activos. Mientras un proceso está en la lista de espera, su prioridad aumenta en una relación a; cuando un proceso entra a la lista de activos su prioridad se incrementa en una relación b.

Tamaño del cuanto.

La determinación del tamaño del cuanto es decisiva para la operación efectiva de un sistema computacional. ¿Debe ser pequeño o grande el cuanto? ¿Debe ser fijo o variable? ¿Debe ser el mismo para todos los usuarios, o debe ser diferente para cada grupo de usuarios?.

Cuando se tiene un cuanto grande cada proceso pude recibir todo el tiempo que necesita para su terminación, de manera que el esquema round robin se convierte en un FIFO. Cuando el cuanto es pequeño, la sobrecarga por el intercambio de contexto se convierte en un factor dominante y el rendimiento del sistema se degrada.

¿Cuál es el cuanto óptimo ? Es claro que cambia de un sistema a otro y que varia de acuerdo a la carga del sistema.

ENLACE A LA SIMULACIÓN DE COLAS RR

Tamaño del Cuanto o Quantum

La determinación del tamaño del cuanto es decisiva para la operación efectiva de un sistema computacional

Los interrogantes son: ¿cuanto pequeño o grande?, ¿cuanto fijo o variable? y ¿cuanto igual para todos los procesos de usuarios o determinado por separado para cada uno de ellos?.

Si el cuanto se hace muy grande, cada proceso recibe todo el tiempo necesario para llegar a su terminación, por lo cual la asignación en rueda (“RR”) degenera en “FIFO”.

Si el cuanto se hace muy pequeño, la sobrecarga del intercambio de contexto se convierte en un factor dominante y el rendimiento del sistema se degrada, puesto que la mayor parte del tiempo de cpu se invierte en el intercambio del procesador (cambio de contexto) y los procesos de usuario disponen de muy poco tiempo de cpu.

El cuanto debe ser lo suficientemente grande como para permitir que la gran mayoría de las peticiones interactivas requieran de menos tiempo que la duración del cuanto, es decir que el tiempo transcurrido desde el otorgamiento de la cpu a un proceso hasta que genera una petición de Entrada / Salida debe ser menor que el cuanto establecido, de esta forma, ocurrida la petición la cpu pasa a otro proceso y como el cuanto es mayor que el tiempo transcurrido hasta la petición de Entrada / Salida, los procesos trabajan al máximo de velocidad, se minimiza la sobrecarga de apropiación y se maximiza la utilización de la

Entrada / Salida.

El cuanto óptimo varía de un sistema a otro y con la carga, siendo un valor de referencia 100 mseg (cien milisegundos)

Queves multi-level

Planificación de Dos Niveles

Los esquemas analizados hasta ahora suponen que todos los procesos ejecutables están en la memoria principal.

Si la memoria principal es insuficiente, ocurrirá lo siguiente

Habrá procesos ejecutables que se mantengan en disco.

Habrá importantes implicaciones para la planificación, tales como las siguientes:

El tiempo de alternancia entre procesos para traer y procesar un proceso del disco es considerablemente mayor que el tiempo para un proceso que ya está en la memoria principal.
Es más eficiente el intercambio de los procesos con un planificador de dos niveles.

El esquema operativo de un planificador de dos niveles es como sigue:

Se carga en la memoria principal cierto subconjunto de los procesos ejecutables.
El planificador se restringe a ellos durante cierto tiempo.
Periódicamente se llama a un planificador de nivel superior para efectuar las siguientes tareas:

Eliminar de la memoria los procesos que hayan permanecido en ella el tiempo suficiente.
Cargar a memoria los procesos que hayan estado en disco demasiado tiempo.

El planificador de nivel inferior se restringe de nuevo a los procesos ejecutables que se encuentren en la memoria.
El planificador de nivel superior se encarga de desplazar los procesos de memoria a disco y viceversa.

Los criterios que podría utilizar el planificador de nivel superior para tomar sus decisiones son los que se indican a continuación:

¿Cuánto tiempo ha transcurrido desde el último intercambio del proceso?.
¿Cuánto tiempo de cpu ha utilizado recientemente el proceso?.
¿Qué tan grande es el proceso? (generalmente los procesos pequeños no causan tantos problemas en este sentido).
¿Qué tan alta es la prioridad del proceso?.

El planificador de nivel superior podría utilizar cualquiera de los métodos de planificación analizados.

Multi-level feedback queves.

Colas de Retroalimentación de Niveles Múltiples

Cuando un proceso obtiene la CPU, sobre todo cuando todavía no ha tenido oportunidad de establecer un patrón de comportamiento, el planificador no tiene idea de la cantidad de tiempo de CPU que necesitará el proceso. Los procesos limitados por la E/S normalmente usan la CPU sólo un momento antes de generar una solicitud de E/S; los procesos limitados por la CPU pueden usar el procesador durante horas si está disponible en forma no apropiativa.
Un mecanismo de planificación debe:

Favorecer a los trabajos cortos.

Favorecer a los trabajos limitados por la E/S para lograr un mejor aprovechamiento de los dispositivos de E/S.

Determinar la naturaleza de un trabajo lo más pronto posible y planificarlo de acuerdo con su naturaleza.

Las colas de retroalimentación de niveles múltiples (figura 6.6) ofrecen una estructura que cumple con estos objetivos. Un proceso nuevo entra en la red de colas al final de la primera cola. Se desplaza en esa cola mediante Round Robin hasta que obtiene la CPU. Si el trabajo termina o cede la CPU para esperar la terminación de una operación de E/S o de algún evento, el trabajo abandona la red de colas. Si el cuanto expira antes de que el proceso ceda voluntariamente la CPU, el proceso se colocará al final de la cola del siguiente nivel. El proceso será atendido otra vez cuando llegue a la cabeza de esa cola si está vacía la primera. Mientras el proceso utilice todo el cuanto proporcionado en cada nivel, continuará desplazándose al final de la siguiente cola inferior. Por lo general, existe una cola en el nivel más bajo en la cual el proceso circula por turno rotatorio hasta que termina.

En muchos esquemas de retroalimentación de múltiples niveles, el cuanto asignado a un proceso cuando pasa a una cola de nivel inferior alcanza un valor mayor. De esta forma, cuanto más tiempo se encuentre un proceso en la red de colas más grande será el cuanto asignado cada vez que obtenga la CPU, pero tal vez no obtenga la CPU muy a menudo, porque los procesos de las colas de nivel superior tienen mayor prioridad. Un proceso situado en una cola no puede ejecutarse a menos que estén vacías las colas de nivel superior. Un proceso en ejecución será desposeído por un proceso que llegue a una cola superior.

Considérese ahora cómo responde un mecanismo de este tipo a diferentes tipos de procesos. El mecanismo debe favorecer a los procesos limitados por la E/S para lograr un buen aprovechamiento de los dispositivos y una respuesta buena para los usuarios interactivos; y de hecho lo hace porque los procesos limitados por la E/S entrarán en la red con prioridad alta y se les asignará rápidamente la CPU. El tamaño del cuanto de la primera cola se elegirá lo suficientemente grande para que la gran mayoría de los trabajos limitados por la E/S generen una petición de E/S antes de que expire el primer cuanto. Cuando el proceso solicita E/S, abandona la red y ha obtenido un tratamiento favorable, tal como se deseaba.

Ahora considérese una tarea limitada por la CPU que necesita mucho tiempo de procesador. Esa tarea entra en la cola más alta de la red con prioridad alta. Recibe rápidamente su primera asignación de la CPU, pero su cuanto expira y el proceso se coloca en la cola del siguiente nivel inferior. En ese momento, el proceso tiene una prioridad menor que la de los procesos que llegan al sistema, en particular los trabajos limitados por la E/S, que obtienen primero la CPU. El proceso limitado por la CPU acaba recibiendo ésta, obtiene un cuanto mayor que en la cola más alta y vuelve a utilizar la totalidad de su cuanto. Luego es situado al final de la siguiente cola inferior. El proceso sigue desplazándose a colas inferiores, espera más entre divisiones de tiempo y utiliza todo su cuanto cada vez que obtiene la CPU ( a menos que sea arrebatada por un proceso entrante). En algún momento, el proceso limitado por la CPU llega a la cola de nivel inferior, en donde entrará en una planificación por turno hasta terminar.

Las colas de retroalimentación de niveles múltiples son ideales para separar procesos en categorías basadas en su necesidad de la CPU. En un sistema de tiempo compartido, cada vez que un proceso abandona la red de colas puede "marcarse" con la identidad de la última cola en donde estuvo, y cuando el proceso entra de nuevo en la red de colas, puede enviarse directamente a la cola en la cual terminó su operación por última vez. En este caso, el planificador está usando un razonamiento heurístico, según el cual el comportamiento anterior del proceso es un buen indicador de su comportamiento en un futuro inmediato. De esta forma, un proceso limitado por la CPU que regresa a la red de colas no se coloca en las colas de nivel alto donde interferiría con el servicio a los procesos cortos de prioridad alta o con los limitados por la E/S.

Si los procesos se colocan siempre dentro de la red en la cola que ocuparon la última vez, será imposible que el sistema responda a cambios de un proceso, por ejemplo, de estar limitado por la CPU, a estar limitado por la E/S. El problema puede resolverse marcando al proceso también con su duración dentro de la red la última vez que estuvo en ella. Así, cuando el proceso entra de nuevo en la red puede colocarse en la cola correcta. Entonces, si el proceso entra en una fase nueva en la cual deja de estar limitado por la CPU y empieza a estar limitado por la E/S, el proceso experimentará en principio un tratamiento lento mientras el sistema determina que la naturaleza del proceso está cambiando. Pero el mecanismo de planificación responderá con rapidez a este cambio. Otra forma de hacer que el sistema responda a los cambios de comportamiento de los procesos es permitir que un proceso ascienda un nivel en la red de colas cada vez que abandona voluntariamente la CPU antes de que expire su cuanto.

El mecanismo de colas de retroalimentación de niveles múltiples es un buen ejemplo de mecanismo adaptativo, que responde a los cambios en el comportamiento del sistema que controla. Los mecanismos adaptativos implican, en general, una carga extra mayor que los no adaptativos, pero la sensibilidad ante los cambios en el sistema da como resultado una mejor capacidad de respuesta, y justifica el aumento en el gasto extra.

Una variante común del mecanismo de colas de retroalimentación de múltiples niveles consiste en hacer que un proceso circule por turno varias veces en cada cola antes de pasar a la siguiente cola inferior. El número de ciclos en cada cola crece por lo regular cuando el proceso pasa a la siguiente cola inferior.

ENLACE A LA SIMULACIÓN COLAS MULTINIVEL

Planificación a la Tasa de Respuesta mas Alta

Brinch Hansen desarrolló la estrategia de prioridad a la tasa de respueta más alta (HRN, highest-response-ratio-next) que corrige algunas deficiencias de SJF, particularmente el retraso excesivo de trabajos largos y el favoritismo excesivo para los trabajos cortos. HRN es un disciplina de planificación no apropiativa en la cual la prioridad de cada proceso no sólo se calcula en función del tiempo de servicio, sino también del tiempo que ha esperado para ser atendido. Cuando un trabajo obtiene el procesador, se ejecuta hasta terminar. Las priori
dades dinámicas en HRN se calculan de acuerdo con la siguiente expresión:

prioridad = (tiempo de espera + tiempo de servicio) / tiempo de servicio

Como el tiempo de servicio aparece en el denominador, los procesos cortos tendrán preferencia. Pero como el tiempo de espera aparece en el numerador, los procesos largos que han esperado también tendrán un trato favorable. Obsérvese que la suma tiempo de espera + tiempo de servicio es el tiempo de respuesta del sistema para el proceso si éste se inicia de inmediato.

Planificación por el Comportamiento

Con este tipo de planificación se pretende garantizar al usuario cierta prestación del sistema y tratar de cumplirla. Si en un sistema tenemos 'n' usuarios lo normal será garantizar a cada uno de ellos al menos 1/n de la potencia del procesador. Para ello necesitamos del tiempo consumido por el procesador y el tiempo que lleva el proceso en el sistema. La cantidad de procesador que tiene derecho a consumir el proceso será el cociente entre el tiempo que lleva en el sistema entre el número de procesos que hay en el sistema. A esa cantidad se le puede asociar una prioridad que vendrá dada como el cociente entre tiempo de procesador que ha consumido y el tiempo que se le prometió (el tiempo que tiene derecho a consumir). De tal modo que si esa proporción es de 0'5 significa que tan sólo ha consumido la mitad del tiempo prometido pero si es de 2 quiere decir que ha consumido más de lo debido, justamente el doble.

Buscar este blog

Sistemas Operativos