Algoritmos de itineración

De Departamento de Informatica
Saltar a: navegación, buscar

La itineración tiene que ser lo más rápida posible, esto significa que los algoritmos usados para la itineración deben estar optimizados de alguna forma. Los distintos algoritmos tienen distintos “fuertes” o enfoques que se pueden clasificar en criterios de optimización. De esta forma, dependiendo del criterio al que pertenezca el algoritmo usado, la itineración será mejor en ciertos aspectos que en otros.

Criterios de optimización:

  • Máximo uso de la CPU.
  • Máxima productividad (procesos por unidad de tiempo o throughput).
  • Mínimo turnaround time.
  • Mínimo tiempo de espera de los procesos en la cola ready.
  • Mínimo tiempo de respuesta.

El principal problema de la itineración consiste en decidir cuál proceso de la cola ready asignarle a la CPU . Para realizar esta tarea existen distintos algoritmos, a continuación se presentan los que se usan más frecuentemente.

Contenido

First­ Come, First ­Served (FCFS)

Conocido también como FIFO (First in , first out) o más vulgarmente como el "algoritmo del banquero". Al igual que una fila de personas en un banco, donde la primera persona en llegar será la primera en ser atendida, el primer proceso en llegar será el primero en usar la CPU y los restantes la usarán conforme aparecen.

En este algoritmo, la itineración ocurre cuando el proceso deja de usar la CPU, además, no realiza ningún tipo de ordenamiento de la cola de procesos. Esta es la razón de que su scheduling overhead sea muy bajo, ya que, por su forma de actuar, lo que tiene que “procesar” es mínimo.

El rendimiento de este algoritmo es bajo, ya que puede ocurrir que un proceso largo ocupe la CPU durante mucho tiempo mientras que otros procesos, quizás, mucho más cortos no pueden ser ejecutados. Esto produce que los tiempos de espera y el de respuesta promedio sean altos.Otro de sus problemas de rendimiento es que puede que un proceso no se termine y por ende no se pase al siguiente.

Ejemplo

Consideremos tres comerciantes (comerciante A, comerciante B y comerciante C) que necesitan dinero para financiar sus negocios. El banco ya les ha entregado un préstamo, pero cada uno necesita aún más dinero para seguir su negocio.

El banco dispone de un total de 24 millones de pesos. El préstamo inicial y los requerimientos de cada comerciante se resume en la siguiente tabla

A B C
Necesita 8 13 10
Tiene 6 8 7
Le faltan 2 5 3

Es decir, se ha dado un total de 21 millones de pesos a los tres comerciantes, por lo que el banco ahora dispone de sólo 3 millones de pesos a repartir. La fila de 'Le faltan' se refiere a la diferencia entre lo que cada comerciante tiene actualmente y lo que necesita para concretar su negocio.

El banco ahora debe repartir los 3 millones que tiene de tal forma que al prestarle el dinero a uno de los comerciantes este pueda completar su negocio y así devolverle el total de lo que se le ha prestado. De esta forma ahora el banco dispondrá de más fondos con los que podrá financiar al siguiente comerciante, hasta que todos terminen. Los comerciantes no pueden devolver el dinero a menos que hayan logrado terminar su negocio.

El comerciante B no se le puede prestar, porque necesita 5 millones, pero el banco sólo dispone de 3. Si se le presta el dinero, B no podrá terminar su negocio, y el banco no tendrá más dinero para prestar a los demás comerciantes, por lo que el sistema se encontrará en un deadlock.

Se disponen de dos opciones: se le prestan 2 millones a A, o 3 millones a C. Ambas opciones son válidas ya que se dispone de los fondos y los comerciantes podrán terminar su negocio. Optando por la primera opción, se llega a la tabla

A B C
Necesita 8 13 10
Tiene 8 8 7
Le faltan 0 5 3

Y el banco se queda con 1 millón. Pero como A puede terminar su negocio, le devuelve todo lo que se le ha prestado, y el banco ahora tiene 8+1=9 millones. Con este dinero ahora puede prestarle a B, obteniendo el estado siguiente

A B C
Necesita - 13 10
Tiene - 13 7
Le faltan - 0 3

Ahora el banco tiene 9-5=4 millones disponibles. Pero B puede terminar, así que el banco ahora tiene 4+13=17 millones. Finalmente, se le puede dar el préstamo a C, con lo que queda

A B C
Necesita - - 10
Tiene - - 10
Le faltan - - 0

Y el banco queda con 17-3=14 millones. Ahora C puede terminar y el banco logra tener los 24 millones iniciales, y los tres comerciantes pudieron lograr terminar sus negocios.

En este ejemplo se hace una analogía donde el banco representa a la CPU, los millones de pesos los recursos disponibles (por ejemplo, memoria), y los comerciantes son procesos que requieren de los recursos para trabajar.

Shortest remaining time (SJF)

Es el algoritmo más óptimo en cuanto al tiempo de espera para un conjunto de procesos, ya que se basa en el ciclo de vida de los procesos. Para cada proceso en la cola ready, se calcula o estima el tiempo que usara la CPU. Usando esto, el itinerador, asigna CPU al proceso más corto en la lista. La dificultad de este algoritmo, está en conocer el tiempo que tomará el próximo ciclo de CPU. Este algoritmo puede funcionar de dos formas:

  • Con desalojo: Cuando se añade a la lista un nuevo proceso y este tiene menor ciclo de CPU que el proceso que se esta ejecutando, se interrumpe el proceso en ejecución y se le asigna la CPU al proceso en la lista que tiene menor ciclo.
  • Sin desalojo: Cuando un proceso toma la CPU, ningún otro proceso podrá apropiarse de ella hasta que que el proceso que la posee termine de ejecutarse.

La estimación del tiempo en el que ocupará la CPU un proceso se calcula utilizando como datos los tiempos de uso de la CPU utilizados previamente. EL calculo corresponde a un promedio exponencial de los tiempos de CPU, definido de la siguiente forma.

τn + 1 = αtn + (1 − α)τn

Donde 0\leq \alpha\leq 1, tn contiene el ultimo ciclo de CPU y τn almacena los ciclos más antiguos. Expandiendo el término τn, o dicho de otra forma, reemplazandolo por los términos sucesivos de tni (ciclos CPU antiguos), se ve de mejor forma el comportamiento del promedio exponencial.

\tau_{n+1} = \alpha t_n + (1-\alpha )\alpha t_{n-1} + \cdots+(1-\alpha )^j\alpha t_{n-j}+ \cdots+(1-\alpha )^{n+1}\tau_{0}

Se puede ver que 0 < (1 − α) < 1 por lo que cada término (1 − α)jαtnj es menor a su predecesor.

Manipulando el valor del parámetro α, se puede dar más énfasis al último dato o al conjunto de datos. Para α = 1 el único valor utilizado para estimar el tiempo es el último obtenido, la ecuación entonces es τn + 1 = tn. Para α = 0, en cambio, la importancia la tienen los valores anteriores al ultimo, es decir, τn + 1 = τn. Si se escoge α = 1 / 2 se le da el mismo "peso" tanto al último dato como a los anteriores.

El SJF se considera como un algoritmo óptimo, porque da el mínimo tiempo de espera promedio para un conjunto de procesos, así como las estimaciones de CPU. Su dificultad radica en que materialmente es un algoritmo imposible de implementar .

Itineración por prioridad

Este algoritmo consiste en asignar la CPU en el orden que de acuerdo a la prioridad se tenga. El algoritmo SJF es un caso especial de este algoritmo donde la prioridad corresponde al inverso del tiempo estimado que usará la CPU, es decir, los proceso más cortos tienen una mayor prioridad.

La prioridad corresponde a un número entero asociado a cada proceso. El cómo se interpreta ese número, es decir, el valor de la prioridad, varía dependiendo del sistema. En algunos sistemas un valor bajo representa una prioridad alta en la planificación del uso de la CPU, en otros sistemas, en cambio, un valor alto es el que representa una alta prioridad en la planificación.Esta itineración o planificación puede ser expropiativos(pre-preemptive) o no expropiativos(nonemptive). La diferencia en esto es que si llega a la cola ready un proceso con prioridad menor al proceso que está actualmente en ejecución, la itineración expropiativa detendra la ejecución del proceso y le asignará la CPU al proceso de la prioridad menor, mientras que la itineración no expropiativa esperará a que el proceso termine para asignar la CPU al proceso que tiene menor prioridad.

La prioridad se puede clasificar entre prioridades internas o externas. Las prioridades internas son calculadas en base a datos como el tiempo de uso de la CPU, la cantidad de archivos abiertos, relación entre tiempos en CPU y tiempos en I/O, etc. La prioridad externa, se obtiene a partir de otros criterios ajenos al sistema operativo, como por ejemplo, importancia del proceso, el costo monetario que implica su ejecución, etc. Es decir, la prioridad externa está más relacionada con factores politicos que con factores técnicos.

En este tipo de algoritmo se puede dar el caso de que procesos en la cola ready pero que tienen una prioridad muy baja no se les sea asignado tiempo en la CPU y queden en la cola indefinidamente, a esto se le denomina como bloqueo indefinido o muerte por inamición. Una forma de evitar esto es ir aumentando la prioridad de los procesos en espera conforme pasa el tiempo y no son ejecutados, a este tipo de mecanismos se les denomina mecanismos de envejecimiento.

Round-robin (RR)

O algoritmo de planificación por turnos. En este algoritmo se define una unidad de tiempo que definirá el tiempo máximo que se puede usar la CPU por proceso, llamada cuanto de tiempo (time quantum), esta unidad representa un intervalo de tiempo que se encuentra generalmente entre 10 ms y 100 ms.

La cola de procesos en estado ready se trata como una lista circular.

El planificador asigna a un proceso un tiempo de ejecucion en la CPU no mayor a un cuanto, este proceso obtiene el control de la CPU hasta que se ha completado el tiempo asignado, entonces se hace un cambio de contexto y se ejecuta el siguiente proceso hasta que cumpla su cuota de tiempo. El proceso que está siendo ejecutado puede, o bien requerir más tiempo del asignado, o terminar antes de cumplir un cuanto de tiempo. En el primer caso, el proceso es interrumpido cuando se cumple un cuanto de tiempo en ejecución y es mandado de vuelta a la cola de procesos ready en espera a que le sea asignado nuevamente tiempo en la CPU. En el segundo caso, el proceso libera por cuenta propia la CPU y el planificador le asigna la CPU al siguiente proceso durante un cuanto de tiempo.

El problema en este algoritmo es la magnitud del cuanto de tiempo. Al calcular el cuanto de tiempo es necesario tener en cuenta el tiempo que demora hacer el cambio de contexto, pues esto aumenta el tiempo promedio de espera de los procesos. Además, se debe considerar el tiempo que necesitan los procesos, ya que si hay procesos que requieren de mucho tiempo para ser ejecutados, estos procesos serán interrumpidos muchas veces y por lo que deberan esperar que se cumpla un ciclo para ser ejecutados nuevamente varias veces.

Para que el tiempo que demora un cambio de contexto no tenga una mayor influencia negativa en el tiempo promedio de espera, el cuanto de tiempo debe ser considerablemente mayor a lo que demora un cambio de contexto. Ademas, es recomendable, en general, que el cuanto de tiempo sea mayor al 80% del tiempo que necesitan los procesos para ser ejecutado . Hay que considerar, en el tamaño del cuanto de tiempo, que si este es muy grande la itineración será similar al de FCFS, en cambio, de ser muy corto, el comportamiento será como si los procesos se estubieran ejecutando en forma paralela en varios procesadores lentos.

Colas Multi nivel

Consiste en dividir la cola ready en varias colas, cada una con procesos que cumplen con alguna condición. Los factores a considerar para separar los procesos en distintas listas pueden ser el tamaño de memoria que necesita el proceso, tipo de proceso, etc. Una vez que un proceso es asignado a una lista no se puede cambiar a otra. Si bien esto es poco flexible, el que los procesos no puedan cambiar de lista una vez que son asignados, hace que este algoritmo no necesite una gran cantidad de tiempo para planificar.

Cada lista puede tener un algoritmo distinto de itineración. Cada lista tiene prioridad distinta con respecto a las otras listas. La planificación entre las colas es generalmente apropiativa y con prioridad fija.

Colas Multi nivel con Retroalimentación

Este algoritmo, al contrario del de colas multinivel, permite que un proceso cambie de una cola a otra. En este algoritmo se dividen los procesos en colas de acuerdo al tiempo de uso de CPU que requieren. Las colas, a su vez, tienen prioridad sobre las demás de acuerdo al cuantum de tiempo que se asigna a los procesos de cada cola. Es decir, la cola con mayor prioridad tendrá un cuantum de tiempo inferior a las otras de menor prioridad. Así, mientras baja la prioridad aumenta el tiempo en el que los procesos pueden usar la CPU.

La ejecución de los procesos parte por los de la cola con prioridad más alta, una vez que esta cola está vacia, se procede a ejecutar los procesos en la siguiente cola en prioridad. Si un proceso entra a una cola con mayor prioridad al del proceso que se está ejecutando, este proceso es interrumpido y se pasa el control al proceso recien llegado.

Links Externos

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas