Algoritmos de planificación.

noviembre 17, 2008 at 8:47 pm (informática)

Bien he tenido que hacer un trabajito para la facultad explicando en que consiste los algoritmos de planificación así que dejo por aquí parte del trabajo «Faltan los ejercicios y diagramas que no subo porque no estoy seguro de que estén bien : P»

Espero que os valga a más de uno.

• El algoritmo de planificación FIFO «First In First Out» trabaja de una forma no apropiativa en el sentido formal de la palabra, a pesar de esto trata de forma poco equitativa a los procesos “cortos” frente a los “largos” ya que si se disponen diversos procesos largos antes en la cola el trabajo de un proceso que necesite poco tiempo de estancia puede alargarse de forma indefinida.

  Debido a que el algoritmo anteriormente hace que pueda demorarse de forma excesiva los procesos cortos suele utilizarse como esquema secundario.

• El algoritmo SPN «Shortest Process Next» trabaja con la política de el primero el proceso con tiempo de procesamiento más corto. De esta forma se consigue que los procesos más cortos se situen por delante de los largos. Esto ofrece un beneficio frente al algoritmo FIFO puesto que da un tiempo de procesamiento más óptimo, no obstante este metodo puede dar ciertos problemas ya que puede ocurrir que estén entrando constantemente procesos cortos haciendo así que los procesos más largos no lleguen nunca a procesarse.

  Además ha de conocerse una estimación sobre el tiempo de procesamiento pora cada proceso

• El algoritmo Round-Robin o turno giratorio trabaja mediante expulsiones basandose en el reloj. Realiza una interrupción cada cierto tiempo, esta división de tiempo es llamada quantum.

  Los quantum deben ser ligeramente mayores al tiempo requerido para una iteración o función típica del proceso ya que si es menor se necesitarán almenos dos quantums de tiempo. Además si los quantums o cuantos se toman de gran tamaño la perdida de eficiencia será considerable degenerando este algoritmo finalmente en uno de tipo FIFO.

  Este algoritmo es efectivo en sistemas de tiempo compartido y de proposito general. Una desventaja es que trata de forma desigual a los procesos limitados por el procesador y a los procesos limitados por E/S ya que estos últimos tienen normalmente ráfagas de procesador más cortas que los procesos limitados por procesador acarreando así un rendimiento ineficiente por parte de los procesos limitados por E/S.

• El algoritmo SRT «Shortest Remaining Time» es una versión expulsiva de SPN. La idea que sigue dicho algoritmo es que el planificador escoge los procesos de menor tiempo de proceso restante llegando al punto de que si un nuevo proceso creado se une a la cola y tiene un tiempo restante al proceso en ejecución este último es expulsado para ejecutar el nuevo proceso. Al igual que SPN este algoritmo necesita una estimación de tiempo de proceso para realizar la función mencionada.

  El SRT penaliza entonces a los procesos largos pudiendo llegar a crear problemas de inanición puesto que puede darse el caso en que estén entrando procesos a la cola de listos de un tiempo de procesamiento menor a los procesos largos, así pues estos no llegarían a procesarse.

---

• El algoritmo HRRN «Highest Response Ratio Next» corrige algunas deficiencias de SPN, 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.

  Con este algoritmo los procesos cortos tendrán preferencia no obstante los procesos con tiempo de procesamiento más largo no se desatenderán haciendo así que no puedan darse problemas de inanición.

• Cuando no se puede averiguar el tiempo estimado de servicio de varios procesos no puede utilizarse los algoritmos SPN, SRT y HRRN así pues se puede utilizar otra forma para establecer ciertas prioridades para los trabajos más cortos es penalizar a los trabajos que han estado más tiempo ejecutandose.

  La forma en que trabaja este algoritmo es mediante expulsión y se utiliza un mecanismo de prioridades dinámico. Se crean varias colas de prioridades, de esta forma un proceso que acabe de entrar al sistema se colocará en la cola de más prioridad, después de su primera expulsión pasará a la una segunda cola de listos con una prioridad menor que la primera. De esta forma cada vez que un proceso sea expulsado pasará a estar en una cola de listos de una prioridad menor hasta que llegue a una cola de mínima prioridad siguiendo esta última una poĺitica de turno rotatorio pues no puede descender más.

  Uno de los grandes problemas de este algoritmo es que puede ser ineficiente e incluso ocurrir inanición para procesos largos si no paran de entrar nuevos procesos en el sistema, una forma de solucionar dicho problema es variar los tiempos de expulsión en cada cola.

  Por ejemplo la primera cola tendría una unidad de tiempo mientras que la segunda tendría dos unidades de tiempo y así hasta la cola n.

  A pesar de la solución mencionada puede darse el caso de inanición para procesos grandes, para evitar esto puede moverse a los procesos a colas de mayor prioridad después de permanecer cierto tiempo en su cola actual.

La mayoría de los algoritmos de planificación apropiativos emplean el uso de prioridades de acuerdo con algún criterio. Cada proceso tiene una prioridad asignada y el planificador seleccionará siempre un proceso de mayor prioridad antes que otro de menor prioridad.