2.6.-Tecnicas de administrcion del planificador

FIFO

 

Algoritmo de planificacion de FIFO                    Tal vez la disciplina mas simple de planificacion sea la de primeras entradas ? primeras salidas (PEPS). Los procesos se despachan de acuerdo con su tiempo de llegada a la cola de procesos listos. Cuando un proceso tiene la CPU, se ejecuta hasta terminar. Es junto en el sentido formal, pero algo injusta en cuanto a que los trabajos largos hacen esperar a los cortos y los trabajos sin importancia hacen esperar a los importantes. FIFO ofrece variaciones relativamente pequenas en los tiempos de respuesta y por lo tanto es mas predecible que los otros esquemas. No es util en la planificacion para los usuarios interactivos porque no puede garantizar buenos tiempos de respuesta. El esquema FIFO rara vez se usa como esquema principal en los sistemas actuales, pero a menudo esta incorporado en otros sistemas. Por ejemplo, muchos esquemas de planificacion despachan los procesos de acuerdo con la prioridad, pero los procesos con la misma prioridad se despachan de acuerdo con el esquema FIFO. Este es un algoritmo que no usa apropiacion, y que consiste en atender a los procesos por estricto orden de llegada a la lista de procesos listos. Cada proceso se ejecuta hasta que termina, o hasta que hace una llamada bloqueante (de E/S). Se trata de una politica muy simple y sencilla de llevar a la practica, pero muy pobre en cuanto a su comportamiento. Las caracteristicas principales de este algoritmo son las siguientes: No es apropiativa. Es justa, aunque los procesos largos hacen esperar mucho a los cortos. Es una politica predecible. El tiempo promedio de servicio es muy variable ya que esta en funcion del numero de procesos y la duracion promedio que tenga.
SJR

 

Otro metodo de planificacion de la CPU es el algoritmo de planificacion con seleccion del trabajo mas corto (SJF, shortest job-first). Este algoritmo asocia con cada proceso la duracion de la siguiente rafaga de CPU del proceso. Cuando la CPU esta disponible, se asigna al proceso que tiene la siguiente rafaga de CPU mas corta. Si las siguientes rafagas de CPU de dos procesos son iguales, se usa la planificacion FCFS para romper el empate. Observe que un termino mas apropiado para este metodo de planificacion seria el de algoritmo de la siguiente rafaga de CPU mas corta, ya que la planificacion depende de la duracion de la siguiente rafaga de CPU de un proceso, en lugar de depender de su duracion total. Usamos el termino SJF porque casi todo el mundo y gran parte de los libros de texto emplean este termino para referirse a este tipo de planificacion. Planificacion de Asignacion en Rueda (RR-Round Robin)   Es un sistema apropiativo. Cada proceso recibe una fraccion de tiempo de procesamiento o quanto para su ejecucion, de manera que cuando se esta ejecutando y excede el tiempo que se le ha concedido, se genera una interrupcion de reloj, mediante la cual la ejecucion del proceso se detiene y se coloca al proceso al final de la cola de procesos ‘listos’ para su posterior ejecucion, seleccionandose a continuacion un nuevo proceso de la cola para su ejecucion. Si un proceso finaliza su ejecucion antes de que termine el tiempo que se le ha asignado, este cede el control, seleccionandose un nuevo proceso de la cola para su ejecucion. Con el Round Robind, cuando un proceso inicia una operacion de E/S, este es penalizado respecto de los procesos que no realizan E/S. Los procesos se despachan en “FIFO” y disponen de una cantidad limitada de tiempo de cpu, llamada “division de tiempo” o “cuanto”. Si un proceso no termina antes de expirar su tiempo de cpu ocurren las siguientes acciones: La cpu es apropiada. La cpu es otorgada al siguiente proceso en espera. El proceso apropiado es situado al final de la lista de listos. Es efectiva en ambientes de tiempo compartido. La sobrecarga de la apropiacion se mantiene baja mediante mecanismos eficientes de intercambio de contexto y con suficiente memoria principal para los procesos. Tamano del Cuanto o Quantum   La determinacion del tamano del cuanto es decisiva para la operacion efectiva de un sistema computacional. Los interrogantes son: ?cuanto pequeno 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 terminacion, por lo cual la asignacion en rueda (“RR”) degenera en “FIFO”. Si el cuanto se hace muy pequeno, 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 mayoria de las peticiones interactivas requieran de menos tiempo que la duracion del cuanto, es decir que el tiempo transcurrido desde el otorgamiento de la cpu a un proceso hasta que genera una peticion de Entrada / Salida debe ser menor que el cuanto establecido, de esta forma, ocurrida la peticion la cpu pasa a otro proceso y como el cuanto es mayor que el tiempo transcurrido hasta la peticion de Entrada / Salida, los procesos trabajan al maximo de velocidad, se minimiza la sobrecarga de apropiacion y se maximiza la utilizacion de la Entrada / Salida. El cuanto optimo varia de un sistema a otro y con la carga, siendo un valor de referencia 100 mseg (cien milisegundos). Caracteristicas de RR Baja sobrecarga si el cambio entre un proceso y otro es eficiente y los procesos siempre estan en la memoria principal El tamano optimo del quantum depende de: El tipo de sistema. Las cargas que vaya a soportar el sistema. El numero de procesos en el sistema y su tipo. Es la politica mas usada para tiempo compartido. Ofrece un servicio igual para todos los procesos. Es una politica apropiativa. Mantiene mas equilibradas las colas de procesos listos y bloqueados. Virtual Round Robind (vrr)   Este sistema va a permitir solucionar el problema del RoundRobind en relacion al favorecimiento que este realiza con los procesos orientados a la CPU frente a los procesos orientados a las operaciones de E/S. El vrr utiliza una cola auxiliar de espera que incluye aquellos procesos que no hayan consumido completamente el quanto que tenian asignados al verse detenidos por una operacion de E/S. Esta cola tiene prioridad respecto a la principal y a los procesos almacenados en ella se les asigna temporalmente (hasta que se ejecuten de nuevo) un nuevo quanto, que es el tiempo del quanto principal que no llegaron a consumir antes de ser bloqueados (el 2o quanto es el quanto principal menos el tiempo del mismo que ya haya sido consumido por el proceso).   Queues Multinivel   Otra clase de algoritmos de planificacion es la que se ha desarrollado para aquellas situaciones en las que los procesos pueden clasificarse facilmente en grupos diferentes. Por ejemplo, una clasificacion habitual consiste en diferenciar entre procesos de primer plano (interactivos) y procesos de segundo plano (por lotes). Estos dos tipos de procesos tienen requisitos diferentes de tiempo de respuesta y, por tanto, pueden tener distintas necesidades de planificacion. Ademas, los procesos de primer plano pueden tener prioridad (definida externamente) sobre los procesos de segundo plano. Un algoritmo de planificacion mediante colas multinivel divide la cola de procesos prepados en varias colas distintas (Figura 5.6). Los procesos se asignan permanentemente a una cola, generalmente en funcion de alguna propiedad del proceso, como por ejemplo el tamano memoria, la prioridad del proceso o el tipo de proceso. Cada cola tiene su propio algoritmo de planificacion. Por ejemplo, pueden emplearse colas distintas para los procesos de primer plano y de segundo plano. La cola de primer plano puede planificarse mediante un algoritmo por turnos, mientras que para la cola de segundo plano puede emplearse un algoritmo FCFS. Ademas , debe definirse una planificaciion entre las colas, la cual suele implementarse como una planificacion apropiada y prioridad fija. po ejemplo, la cola de procesos de primer plano puede tener velocidad absoluta sobre la cola de procesos de segundo plano. Veamos un ejemplo de algoritmo de planificacion mediante colas multinivel con las cinco colas que se enumeran a continuacion, segun su orden de prioridad: 1. Procesos del sistema. 2. Procesos interactivos. 3. Procesos de edicion interactivos. 4. Procesos por lotes. 5. Procesos de estudiantes. Cada cola tiene prioridad absoluta sobre las colas de prioridad mas baja. Por ejemplo, ningun proceso de la cola por lotes podra ejecutarse hasta que se hayan vaciado completamente las colas de los procesos del sistema, los procesos interactivos y los procesos de edicion interactivos. Si un proceso de edicion interactivo llega a la cola de procesos preparados mientras se esta ejecutando un proceso por lotes, el proceso por lotes sera desalojado. Otra posibilidad consiste en repartir el tiempo entre las colas. En este caso, cada cola obtiene una cierta porcion del tiempo de CPU, con la que puede entonces planificar sus distintos procesos Por ejemplo, en el caso de la colas de procesos de primer plano y segundo plano, la cola de primer plano puede disponer del 80 por ciento del tiempo de CPU para planificar por turnos sus procesos, mientras que la cola de procesos de segundo plano recibe el 20 por ciento del tiempo de CPU para gestionar sus procesos mediante el metodo FCFS.                             Multi-Level FreedBack Queues     Normalmente, cuando se usa el algoritmo de planificacion mediante colas multinivel, los procesos se asignan de forma permanente a una cola cuando entran en el sistema. Por ejemplo, si hay colas diferentes para los procesos de primer y segundo plano, los procesos no se mueven de una cola a otra, dado que no pueden cambiar su naturaleza de proceso de primer o segundo plano. Esta configuracion presenta la ventaja de una baja carga de trabajo de planificacion, pero resulta poco flexible. Por el contrario, el algoritmo de planificacion mediante colas multinivel realimentadas permite mover un proceso de una cola a otra. La idea es separar los procesos en funcion de las caracteristicas de sus rafagas de CPU. Si un proceso utiliza demasiado tiempo de CPU, se pasa a una a de prioridad mas baja. Este esquema deja los procesos limitados por E/S y los procesos interactivos en las colas de prioridad mas alta. Ademas, un proceso que este esperando demasiado tiempo en una cola de baja prioridad puede pasarse a una cola de prioridad mas alta. Este mecanismo de envejecimiento evita el bloqueo indefinido. Por ejemplo, considere un planificador de colas multinivel realimentadas con tres colas, numeradas de 0 a 2 (Figura 5.7). En primer lugar, el planificador ejecuta todos los procesos de la cola 0. Solo cuando la cola 0 este vacia ejecutara procesos de la cola 1. De forma similar, los procesos de la cola 2 solo se ejecutaran si las colas 0 y 1 estan vacias. Un proceso que llegue a la cola 1 desalojara a un proceso de la cola 2 y ese proceso de la cola 1 sera, a su vez, desalojado por un proceso que llegue a la cola 0. Un proceso que entre en la cola de procesos preparados se coloca en la cola 0 y a cada uno de los procesos de esa cola se le proporciona un cuanto de tiempo de 8 milisegundos. Si el proceso no termina en ese tiempo, se pasa al final de la cola 1. Si la cola 0 esta vacia, al proceso que se encuentra al principio de la cola 1 se le asigna un cuanto de 16 milisegundos. Si no se completa en ese tiempo, se lo desaloja y se lo incluye en la cola 2. Los procesos de la cola 2 se ejecutan basandose en una planificacion FCFS, pero solo cuando las colas 0 y 1 estan vacias. Este algoritmo de planificacion proporciona la prioridad mas alta a todo proceso que tenga una rafaga de CPU de 8 milisegundos o menos. Tales procesos acceden rapidamente a la CPU, concluyen su rafaga de CPU y pasan a su siguiente rafaga de E/S. Los procesos que necesitan mas de 8 milisegundos y menos de 24 milisegundos tambien son servidor rapidamente, aunque con una prioridad mas baja que los procesos mas cortos. Los procesos largos terminan yendo automaticamente a la cola 2 y se sirven, siguiendo el orden FCFS, con los ciclos de CPU no utilizados por las colas 0 y 1. En general, un planificador mediante colas multinivel realimentadas se define mediante los parametros siguientes: ??????? El numero de colas. ?????????? El algoritmo de planificacion de cada cola. ?????????? El metodo usado para determinar cuando pasar un proceso a una cola de prioridad mas alta. ?????????? El metodo usado para determinar cuando pasar un proceso a una cola de prioridad mas baja. ?????????? El metodo usado para determinar en que cola se introducira un proceso cuando haya que darle servicio. La definicion del planificador mediante colas multinivel realimentadas le convierte en el algoritmo de planificacion de la CPU mas general. Puede configurarse este algoritmo para adaptarlo a cualquier sistema especifico que se quiera disenar. Lamentablemente, tambien es el algoritmo mas complejo, puesto que definir el mejor planificador requiere disponer de algun mecanismo para seleccionar los valores de todos los parametros.