FIFO

Las disciplinas de planificación pueden ser:

• Expropiativas

• No expropiativas

Se denomina planificador al software del sistema operativo encargado de asignar los recursos de un sistema entre los procesos que los solicitan. Siempre que haya tomar una decisión, el planificador debe decidir cuál de los procesos que compiten por la posesión de un determinado recursos lo recibirá.

Los algoritmos (técnicas) tienen distintas propiedades según los criterios en los que se basen para su construcción, lo cual se refleja en qué tipo de procesos se puede ver favorecido frente a otro en la disputa del procesador. Antes de realizar la elección de un algoritmo se debe considerar las propiedades de estos frente al criterio de diseño elegido. Algunos de estos son:

a) Eficacia: Se expresa como un porcentaje del tiempo medio de utilización. Aunque puede parecer lógico intentar mantener este parámetro próximo al 100%, con un valor tan elevado otros aspectos importantes de medida del comportamiento del sistema pueden verse deteriorados, como por ejemplo el tiempo medio de espera.

b) Rendimiento: Es una medida del número de procesos completados por unidad de tiempo. Por ejemplo 10 procesos por segundo.

c) Tiempo de retorno o regreso: Es el intervalo de tiempo que transcurre desde que un proceso se crea o presenta hasta que completa por el sistema.

d) Tiempo de espera: Es el tiempo que el proceso espera hasta que se le concede el procesador. Puede resultar una medida más adecuada de la eficiencia del sistema, ya que se elimina de la media el tiempo que tarda en ejecutarse el mismo.

e) Tiempo de respuesta a un evento: Se denomina así el intervalo de tiempo que transcurre desde que se señala un evento hasta que se ejecuta la primera instrucción de la rutina de servicio de dicho evento. El criterio de selección de un algoritmo se suele basar en la maximización o minimización de una función de los parámetros anteriores.

2.6.1 Fifo

FIFO: First In First Out

Mecanismo de scheduling en el cual los procesos se ordenan en una fila, en la cual se ejecutan cada uno de los procesos hasta su finalización secuencialmente. Es tremendamente ineficiente. Cuando se tiene que elegir a qué proceso asignar la CPU se escoge al que llevara más tiempo listo. El proceso se mantiene en la CPU hasta que se bloquea voluntariamente.

FIFO es el acrónimo inglés de First In, First Out (primero en entrar, primero en salir). Un sinónimo de FIFO es FCFS, acrónimo inglés de First Come First Served ( primero en llegar, primero en ser servido). Es un método utilizado en estructuras de datos, contabilidad de costes y teoría de colas. Guarda analogía con las personas que esperan en una cola y van siendo atendidas en el orden en que llegaron, es decir, que la primera persona que entra es la primera persona que sale.

El sistema debe reservar el tamaño de memoria necesario para acoger todos los datos, sea cual sea el número de elementos usados, lo que en algunas aplicaciones supone un despilfarro de la memoria. Sin embargo, si se usan punteros, el número máximo no está declarado sino que se hace un uso dinámico de la memoria, adaptándose al tamaño necesario en cada momento en función de los elementos que hay en la cola. Uno de los usos de las colas es la exploración “en anchura” de un árbol de búsqueda. Otro uso típico de las colas, es la gestión de descargas de una aplicación p2p. FIFO FULL (LLENO)/EMPTY (VACIO) En el hardware FIFO se usa para propósitos de sincronización.

Comportándose como una cola circular. Tiene dos punteros:

1. Puntero de Lectura/Registro de Dirección de Lectura

2. Puntero de Escritura/Registro de Dirección de Escritura

Miguel Satiner (2004, junio 20).informática sistemas operativos. Recuperado 27 de Octubre de 2008 de http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/SO3.htm

2.6.2 Sjf

Al igual que en el algoritmo FIFO las ráfagas se ejecutan sin interrupción, por tanto, sólo es útil para entornos batch. Su característica es que cuando se activa el planificador, éste elige la ráfaga de menor duración. Es decir, introduce una noción de prioridad entre ráfagas.

Hay que recordar que en los entornos batch se pueden hacer estimaciones del tiempo de ejecución de los procesos. La ventaja que presenta este algoritmo sobre el algoritmo FIFO es que minimiza el tiempo de finalización promedio, como puede verse en el siguiente ejemplo:

Supongamos que en un momento dado existen tres ráfagas listos R1, R2 y R3, sus tiempos de ejecución respectivos son 24, 3 y 3 ms. El proceso al que pertenece la ráfaga R1 es la que lleva más tiempo ejecutable, seguido del proceso al que pertenece R2 y del de R3.

• SJF F = (3 + 6 + 30) / 3 = 13 ms.

2.6.3 Rr

Cada proceso tiene asignado un intervalo de tiempo de ejecución, llamado quantum o cuanto. Si el proceso agota su quantum de tiempo, se elige a otro proceso para ocupar la CPU. Si el proceso se bloquea o termina antes de agotar su quantum también se alterna el uso de la CPU.

El round robín es muy fácil de implementar. Todo lo que necesita el planificador es mantener una lista de los procesos listos.

2.6.4 QuevesMultilevel

Un algoritmo de planificación multinivel particiona la cola de listos en colas separadas. Se asignan en forma permanente los trabajos a una cola, generalmente, basándose en alguna propiedad del mismo (requerimientos de memoria, tipo de trabajo), teniendo cada cola su propio algoritmo. Por ejemplo, la cola interactiva podría planificarse usando RR y la batch FIFO.

Ningún trabajo en una cola de baja prioridad puede ejecutarse si las colas con mayor prioridad no están vacías. Si algún trabajo entra en una cola de mayor prioridad, el trabajo de otras colas es interrumpido.

2.6.5 MultiLevel Feedback Queves

En colas multinivel realimentadas los trabajos pueden moverse dentro de distintas colas. La idea es separar procesos con distintos tipos de interrupciones de la CPU. Si un trabajo consume mucho tiempo de CPU, será movido a una cola con menor prioridad.

En forma similar, si un proceso espera demasiado tiempo en una cola de baja prioridad, lo moveremos a una cola de mayor prioridad.

En general un planificador de este tipo esta definido por los siguientes parámetros:

1. El número de colas.

2. El tipo de algoritmo de planificación de cada cola.

3. Un método de determinación de cuando mover un trabajo a una cola de mayor prioridad.

4. Un método de determinación de

...