3.4 Administración de memoria virtual

Estrategias de Administración del Almacenamiento
Están dirigidas a la obtención del mejor uso posible del recurso del almacenamiento principal [7, Deitel].
Se dividen en las siguientes categorías:

• Estrategias de búsqueda:
  • Estrategias de búsqueda por demanda.
  • Estrategias de búsqueda anticipada.
• Estrategias de colocación.
• Estrategias de reposición.

Las “estrategias de búsqueda” están relacionadas con el hecho de cuándo obtener el siguiente fragmento de programa o de datos para su inserción en la memoria principal. En la “búsqueda por demanda” el siguiente fragmento de programa o de datos se carga al almacenamiento principal cuando algún programa en ejecución lo referencia.
Se considera que la “búsqueda anticipada” puede producir un mejor rendimiento del sistema.
Las “estrategias de colocación” están relacionadas con la determinación del lugar de la memoria donde se colocará (cargará) un programa nuevo.
Las “estrategias de reposición” están relacionadas con la determinación de qué fragmento de programa o de datos desplazar para dar lugar a los programas nuevos.


Asignación Contigua de Almacenamiento Versus No Contigua
En la “asignación contigua” cada programa ocupa un bloque contiguo y sencillo de localizaciones de almacenamiento.
En la “asignación no contigua” un programa se divide en varios bloques o “segmentos” que pueden almacenarse en direcciones que no tienen que ser necesariamente adyacentes, por lo que es más compleja pero más eficiente que la asignación continua.

Asignación Contigua de Almacenamiento de Un Solo Usuario
Se consideran S. O. que ya poseen desarrollado el “sistema de control de entrada / salida”: IOCS: input / output control system (ver Figura 3.2 [7, Deitel]).

El tamaño de los programas está limitado por la cantidad de memoria principal, pero se puede superar este límite con técnicas de “recubrimientos”, con las siguientes características (ver Figura 3.3 [7, Deitel]):

• Si una sección particular del programa ya no es necesaria, se carga otra sección desde el almacenamiento secundario ocupando las áreas de memoria liberadas por la sección que ya no se necesita.
• La administración manual por programa del recubrimiento es complicada y dificulta el desarrollo y el mantenimiento.

Protección en los sistemas de un solo usuario
El usuario tiene un completo control sobre la totalidad del almacenamiento principal:

• El almacenamiento se divide en porciones que contienen el S. O., el programa del usuario y una porción sin usar.
• El programa del usuario podría destruir áreas del S. O. que podrían:
  • Detener el sistema.
  • Producir salidas erróneas.
• El S. O. debe estar protegido contra el proceso usuario:
  • La protección se instrumenta mediante un “registro de límites” incorporado a la cpu:
    • Contiene la dirección de la instrucción más alta utilizada por el S. O.
    • Si se intenta ingresar al S. O. la instrucción es interceptada y el proceso finaliza.

Procesamiento por lotes de flujo único Los sistemas de un solo usuario se dedican a un trabajo durante más tiempo del que toma su ejecución.
Los trabajos requieren de:

• “tiempo de instalación”: el necesario para preparar el entorno operativo requerido.
• “tiempo de descarga”: el necesario para desmontar el entorno operativo que fue requerido.

Durante la instalación y descarga de los trabajos la cpu no está ejecutando dichos trabajos requeridos, por lo cual:

• Automatizar la “transición de trabajo a trabajo” reduce la cantidad de tiempo perdido entre trabajos.
• Surgieron los sistemas de “procesamiento por lotes”.

En el “procesamiento por lotes de flujo único” los trabajos se agrupan en “lotes” encolándose para su ejecución. El “procesador de flujos de trabajos”:

• Lee las instrucciones del “lenguaje de control de trabajos”.
• Facilita la preparación del trabajo siguiente.
• Emite instrucciones al operador del sistema.
• Automatiza funciones anteriormente manuales.
• Cuando finaliza un trabajo efectúa las “operaciones de mantenimiento” apropiadas para facilitar la transición del siguiente trabajo.

3.3 Organización de memoria virtual

Organización y Administración del Almacenamiento
Organización del Almacenamiento
Históricamente el almacenamiento principal se ha considerado como un recurso costoso, por lo cual su utilización debía optimizarse [7, Deitel].
Por organización del almacenamiento se entiende la manera de considerar este almacenamiento:

• ¿ se coloca un solo programa de usuario o varios ?.
• Si se encuentran varios programas de usuario:
  • ¿ se concede a cada uno la misma cantidad de espacio o se divide el almacenamiento en porciones o “particiones” de diferente tamaño ?.
  • ¿ se utilizará un esquema rígido de número y tamaño de particiones o un esquema dinámico y adaptable ?.
  • ¿ se requerirá que los trabajos de los usuarios sean diseñados para funcionar en una partición específica o se permitirá que se ejecuten en cualquiera donde quepan ?.
  • ¿ se requerirá o no que cada trabajo sea colocado en un bloque contiguo de memoria ?.

Administración del Almacenamiento
Independientemente del esquema de organización hay que decidir las estrategias que se utilizarán para optimizar el rendimiento.
Las “estrategias de administración” deben considerar:

• ¿ cuándo se consigue un nuevo programa para colocar en la memoria ?:
  • ¿ cuando el sistema lo pide específicamente o se intenta anticiparse a las peticiones ?.
• ¿ dónde se colocará el programa que se ejecutará a continuación ?:
  • ¿ se prioriza el tiempo de carga o la optimización en el uso del almacenamiento ?.
• ¿ con qué criterio se desplazarán programas ?.

3.2 Memoria real

La memoria real o principal es en donde son ejecutados los programas y procesos de una computadora y es el espacio real que existe en memoria para que se ejecuten los procesos. Por lo general esta memoria es de mayor costo que la memoria secundaria, pero el acceso a la información contenida en ella es de más rápido acceso. Solo la memoria cache es más rápida que la principal, pero su costo es a su vez mayor.

1.2.2.- Administración de la memoria con mapas de bits

Este tipo de administración divide la memoria en unidades de asignación, las cuales pueden ser tan pequeñas como unas cuantas palabras o tan grandes como varios kilobytes. A cada unidad de asignación le corresponde un bit en el mapa de bits, el cual toma el valor de 0 si la unidad está libre y 1 si está ocupada (o viceversa). La figura 6 muestra una parte de la memoria y su correspondiente mapa de bits.

Fig. 6. Ejemplo de un mapa de bits para la administración de la memoria.

Un mapa de bits es una forma sencilla para llevar un registro de las palabras de la memoria en una cantidad fija de memoria, puesto que el tamaño del mapa sólo depende del tamaño de la memoria y el tamaño de la unidad de asignación.

1.2.3.- Administración de la memoria con listas ligadas

Otra forma de mantener un registro de la memoria es mediante una lista ligada de los segmentos de memoria asignados o libres, en donde un segmento puede ser un proceso o un hueco entre dos procesos. La memoria de la figura 7(a) está mostrada como una lista ligada de segmentos en la figura 7(b). Cada entrada de la lista especifica un hueco (H) o un proceso (P), la dirección donde comienza, su longitud y un apuntador a la siguiente entrada.

Fig. 7. Ejemplo de listas ligadas.

En este ejemplo, la lista de segmentos está ordenada por direcciones, lo que da la ventaja de que al terminar o intercambiar un proceso, la actualización de la lista es directa.

1.2.4.- Asignación del hueco de intercambio

En algunos sistemas, cuando el proceso se encuentra en la memoria, no hay un hueco en el disco asignado a él. Cuando deba intercambiarse, se deberá asignar un hueco para él en el área de intercambio del disco. Los algoritmos para la administración del hueco de intercambio son los mismos que se utilizan para la administración de la memoria principal.

En otros sistemas, al caerse un proceso, se le asigna un hueco de intercambio en el disco. Cuando el proceso sea intercambiado, siempre pasará al hueco asignado, en vez de ir a otro lugar cada vez. Cuando el proceso concluya, se libera el hueco de intercambio. La única diferencia es que el hueco en disco necesario para un proceso debe representarse como un número entero de bloques del disco. Por ejemplo, un proceso de 13.5 K debe utilizar 14K (usando bloques de 1K).

3.1 Política y filosofía.

Filosofía:

La memoria principal puede ser considerada como un arreglo lineal de localidades de almacenamiento de un byte de tamaño. Cada localidad de almacenamiento tiene asignada una dirección que la identifica.

Una de las funciones básicas que debe implementar un SO es la Administración de la Memoria para tener un control sobre los lugares donde están almacenados los procesos y datos que actualmente se están utilizando.

Sea cual sea es esquema de organización del almacenamiento que se adopte para un sistema específico, es necesario decidir que estrategias se deben utilizar para obtener un rendimiento óptimo .las estrategias de administración del almacenamiento determinan el comportamiento de la administración de memoria cuando se siguen ciertas políticas:

· ¿Cuándo se toma un nuevo programa para colocarlo en memoria?

· ¿Se toma el programa cuando el sistema lo solicita específicamente o se intenta anticiparse alas particiones del sistema?

· ¿En que lugar del almacenamiento principal se coloca el programa por ejecutar?

· ¿Se colocan los programas lo más cerca unos de otros en los espacios disponibles de la memoria principal para reducir al mínimo el

desperdicio de espacio, o se colocan los programas lo más rápido posible para reducir al mínimo el tiempo de ejecución?

· Si se necesita colocar un nuevo programa en el almacenamiento principal y éste está lleno, ¿Cuál de los otros programas se desaloja?

Se han realizado sistemas que utilizan cada una de estas estrategias de administración.

Los programas y datos necesitan estar en el almacenamiento principal para ser ejecutados o para poder hacer referencia de ellos. Los que no se necesitan de inmediato pueden guardarse en el almacenamiento secundario.

Unix permite procesos múltiples y en un proceso puede generar otro fácilmente. La planificación del procesador usa un algoritmo basado en prioridades. La administración de memoria es un algoritmo de regiones variables con intercambios. Inicialmente los algoritmos realizados se eligieron por sencillez, no por velocidad ni complejidad. El desarrollo inicial se hizo bajo un espacio muy pequeño de memoria.

Los recursos de memoria totales eran insuficientes para justificar algoritmos complejos, por lo que UNIX intercambiaba el contenido en memoria de los procesos.

POLÍTICAS.

FIFO: Los procesos se despachan de acuerdo a su tiempo de llega a la cola de procesos listos, si un proceso llega al procesador sale hasta que termine. La política FIFO actualmente no se usa como el esquema principal de un sistema, pero si por ejemplo cuando se usa una política de prioridades y hay procesos con la misma prioridad, a estos se les podría aplicar FIFO.

Round Robin: Los procesos se despachan en la forma que lo hace el FIFO, pero se les asigna una cantidad limitada de tiempo (CUANTUM) en el procesador, si no termina en ese lapso se manda al final de la lista de procesos listos.

SJF (Shortest job first - Prioridad del trabajo mas corto): Se ejecuta primero el proceso en espera que tiene el menor tiempo estimado. SJF favorece a los procesos cortos, ya que los largos podrían llegar a rezagarse mucho tiempo e incluso nunca ejecutarse.

SRT (Sortest remaining time scheduling – Tiempo restante más corto): En SJF una vez que un proceso comienza su ejecución continua hasta terminar. En SRT, un proceso en ejecución puede ser desposeído por uno nuevo de menor tiempo de ejecución.

HRN: (highest response ratio next – Prioridad de la tasa de respuesta más alta): Política no apropiativa que corrige el retraso excesivo de procesos grandes que produce el SJF, para así no caer en un favoritismo excesivo por los procesos cortos, lo logra usando una formula basada en el tiempo de espera y el tiempo de servicio, con lo cual la prioridad de cada trabajo no solo esta en función del tiempo de servicio sino también del tiempo que ha esperado para ser atendido.

Unidad 3 Administración de memoria

Administración de la Memoria

La parte del sistema operativo que administra la memoria se llama administrador de la memoria. Para ello existen diferentes esquemas de administración de memoria desde los mas simples hasta los mas elaborados entre los cuales se ubican:

· Administración de la memoria sin intercambio o paginación.

Los sistemas de administración de memoria se pueden clasificar en dos tipos. Los que desplazan los procesos de la memoria principal al disco y viceversa durante la ejecución (intercambio y paginación) y aquellos que no.

· Monopogramación sin intercambio o paginación.

Es en forma secuencial pues solo se tiene un objeto en memoria en cada instante, el usuario carga toda la memoria con un programa, esto implica que cada proceso debe contener controladores de dispositivo para cada uno de los dispositivos E/S que utilice.

· Multiprogramación y uso de la memoria.

La multiprogramación facilita la programación de una aplicación al dividirla en dos o mas procesos. La mayoría de los procesos tardan cierto tiempo en la espera de datos de dispositivos E/S. Un modelo para el uso y aprovechamiento de la CPU es el modelo probabilístico dado por la fórmula : Uso de la CPU = 1 − pn

· Multiprogramación con particiones fijas

El objetivo en todo esto es tener mas de un proceso en memoria a la vez, solución posible sería dividir la memoria en n partes al inicio de una sesión de uso de la máquina, pero aún así se obtiene el desperdicio de particiones grandes con una tarea pequeña, la respuesta puede ser tener particiones pequeñas también. Las tareas que van llegando se forman hasta que una partición adecuada está disponible, en cuyo momento la tarea se carga en esa partición y se ejecuta hasta terminar.

· Intercambio

En un sistema por lotes la organización de la memoria en particiones fijas es adecuado pero en un ambiente multiusuario la situación es distinta con el tiempo compartido, ya que existen mas usuarios de los que puede albergar la memoria, por lo que es conveniente albergar el exceso de los procesos en disco., por supuesto para ser ejecutados estos procesos deben ser trasladados a la memoria principal. Al traslado de procesos de disco a memoria y viceversa se le llama intercambio.

· Multiprogramación con particiones variables.

Mediante un algoritmo de administración de memoria las particiones variables varían de forma dinámica durante el uso de la máquina, evitando desperdicio de memoria

Otros métodos de administración de memoria que tenemos son:

la administración de memoria con mapa de bits

la memoria se divide en unidades de asignación, a cada asignación le corresponden un bit en el mapa de bits, un mapa de bits es una forma sencilla para llevar un registro de las palabras de la memoria en una cantidad fija de memoria.

la administración de memoria con listas ligadas

otra forma de mantener un registro en memoria es mediante una lista ligada donde cada entrada de la lista específica un hueco o un proceso.

la administración de memoria con el sistema de los asociados

basado en el sistema binario o utiliza para las direcciones.

· Memoria Virtual

El método diseñado por Fotheringham en 1961 se conoce como Memoria Virtual, la idea es que el tamaño combinado de la pila, programa y datos puede exceder la memoria física disponible para ello. El S.O. mantiene en memoria aquellas partes del programa que se deben permanecer en memoria y el resto lo deja en disco, las partes entre el disco y la memoria se intercambian de modo que se vayan necesitando.

· Paginación

El espacio de direcciones de cada proceso se divide en bloques de tamaño uniforme llamados páginas, los cuales se pueden colocar dentro de cualquier para página marco disponible en memoria. Cuando las tablas de páginas son muy grandes se puede utilizar un esquema de paginación de varios niveles para que las páginas se paginen a sí mismas.

Existen distintos niveles de paginación y a su vez distintos modelos de computadoras han trabajado con ellas.

Paginación de nivel 1: PDP−11

Paginación de 2 niveles: la VAX

Paginación de 3 niveles: la SPARC

Paginación de 4 niveles: la 68030

Memoria asociativa

En los algoritmos de paginación las tablas de páginas se mantienen en la memoria debido a su gran tamaño, en potencia este diseño tiene un efecto enorme en el rendimiento.

· Algoritmos de reemplazo de páginas.

Cuando ocurre un fallo de página el sistema operativo debe elegir una página para retirarla de la memoria y hacer un espacio para la página por recuperar. Si la página por eliminar fue modificada mientras estaba en memoria, debe escribirla en el disco para mantener actualizada la copia del disco, si por el contrario la página no ha sido modificada la copia del disco ya está actualizada por lo que no es necesario volver a escribir, la página por leer sólo escribe encima de la página por retirar.

Aunque es posible elegir una página al azar para el reemplazo relacionado con un fallo de página, el rendimiento del sistema es mucho mejor si se elige una página de poco uso.

· Algoritmo de reemplazo de páginas optimo

Mejor algoritmo posible para reemplazo de páginas pero irrealizable en la práctica.

Al momento de ocurrir un fallo de página cierto conjunto de páginas se encuentran en la memoria, en la siguiente instrucción se hará referencia a una de estas páginas, otras páginas no se utilizaran sino hasta mucho después, cada página puede ejecutarse con el número de instrucciones ejecutadas antes de la primera referencia a esa página, el algoritmo dice que se elimine la página con la mayor etiqueta; si una página no va a utilizase sino hasta mucho después que otra la eliminación de la primera retrasa el fallo de página lo mas posible, el único problema de este algoritmo es que es irrealizable. Al momento del fallo de página el S.O. no tiene forma de saber a qué página se hace referencia.

· Algoritmo de página de uso no muy reciente.

En un fallo de página , el sistema operativo inspecciona todas las páginas y las divide en cuatro categorías según los valores actuales de los bits R y M

Clase 0: No se ha hecho referencia ni ha sido modificada

Clase 1: No se ha hecho referencia pero ha sido modificada

Clase 2: Se ha hecho referencia pero no ha sido modificada

Clase 3: Se ha hecho referencia y ha sido modificada

El algoritmo NRU implica una hipótesis que indica que es mejor eliminar una página modificada sin referencias al menos por lo general un intervalo de reloj, este algoritmo es fácil de comprender, de implantación eficiente y con un rendimiento que, aún sin ser el óptimo si es adecuado en muchos casos.

· Algoritmo de reemplazo “ primero en entrar, primero en salir FIFO”

El sistema operativo tiene una lista de todas las páginas que se encuentran en memoria, siendo la primera página la mas antigua y la última la mas reciente, en un fallo de página, se elimina la primera página y se añade la nueva al final de la lista.

· Algoritmo de reemplazo de páginas de la segunda oportunidad

Una modificación simple del FIFO que evita deshacerse de una página de uso frecuente inspecciona el bit R de la página mas antigua, busca una página antigua sin referencias durante el anterior intervalo de tiempo.

· Algoritmo de reemplazo de páginas del reloj

Aunque el anterior algoritmo es razonable un mejor enfoque es mantener las páginas en una lista circular con la forma de un reloj, una manecilla apunta hacia la mas antigua. Al ocurrir un fallo de página se inspecciona la página a la que apunta la manecilla si su bit R=0 se retira de la memoria, se inserta la nueva página en su lugar en el reloj y la manecilla avanza una posición, si R=1 la manecilla avanza una posición y el bit se limpia, esto continua hasta encontrar una página con R=0.

· Segmentación

Una memoria segmentada tiene otras ventajas como hacer mas sencilla la administración de las estructuras de datos que crecen o se reducen, si cada procedimiento ocupa un segmento independiente con la posición inicial cero el ligado independiente de los procesos compilados es mucho mas sencillo.

Bit que se activa si se hace referencia a la página en cuestión

Bit que se activa si se modifica la página.

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 [23, Tanenbaum]:

• 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:

1. Se carga en la memoria principal cierto subconjunto de los procesos ejecutables.
2. El planificador se restringe a ellos durante cierto tiempo.
3. Periódicamente se llama a un planificador de nivel superior para efectuar las siguientes tareas:
   1. Eliminar de la memoria los procesos que hayan permanecido en ella el tiempo suficiente.
   2. Cargar a memoria los procesos que hayan estado en disco demasiado tiempo.
4. El planificador de nivel inferior se restringe de nuevo a los procesos ejecutables que se encuentren en la memoria.
5. 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.

[23] A. S. Tanenbaum. Sistemas Operativos Modernos. Prentice Hall Hispanoamericana, S.A., México, 1993. 

Tipos de Planificación

Planificación a Plazo Fijo
 

Ciertos trabajos se planifican para ser terminados en un tiempo específico o plazo fijo. Es una planificación compleja debido a los siguientes factores:

• El usuario debe suministrar anticipadamente una lista precisa de recursos necesarios para el proceso, pero generalmente no se dispone de dicha información.
• La ejecución del trabajo de plazo fijo no debe producir una grave degradación del servicio a otros usuarios.
• El sistema debe planificar cuidadosamente sus necesidades de recursos hasta el plazo fijo, lo que se puede complicar con las demandas de recursos de nuevos procesos que ingresen al sistema.
• La concurrencia de varios procesos de plazo fijo (activos a la vez) puede requerir métodos sofisticados de optimización.
• La administración intensiva de recursos puede generar una considerable sobrecarga adicional. 

Planificación Garantizada
 
Se establecen compromisos de desempeño con el proceso del usuario, por ejemplo, si existen “n” procesos en el sistema, el proceso del usuario recibirá cerca del “1 / n” de la potencia de la cpu.
El sistema debe tener un registro del tiempo de cpu que cada proceso ha tenido desde su entrada al sistema y del tiempo transcurrido desde esa entrada.
Con los datos anteriores y el registro de procesos en curso de ejecución, el sistema calcula y determina qué procesos están más alejados por defecto de la relación “1 / n” prometida y prioriza los procesos que han recibido menos cpu de la prometida.



Planificación del Primero en Entrar Primero en Salir (FIFO)

Es muy simple, los procesos se despachan de acuerdo con su tiempo de llegada a la cola de listos.
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”.

Planificación de Asignación en Rueda (RR: Round Robin)
 
Los procesos se despachan en “FIFO” y disponen de una cantidad limitada de tiempo de cpu, llamada “división de tiempo” o “cuanto”.
Si un proceso no termina antes de expirar su tiempo de cpu ocurren las siguientes acciones:

1. La cpu es apropiada.
2. La cpu es otorgada al siguiente proceso en espera.
3. El proceso apropiado es situado al final de la lista de listos.

Es efectiva en ambientes de tiempo compartido. La sobrecarga de la apropiación se mantiene baja mediante mecanismos eficientes de intercambio de contexto y con suficiente memoria principal para los procesos.



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 [7, Deitel].
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).




Planificación del Trabajo Más Corto Primero (SJF)
 
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.


Planificación del Tiempo Restante Más Corto (SRT)
 
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_r es la “prioridad”, t_e es el “tiempo de espera” y t_s es el “tiempo de servicio”:

 

Planificación por Prioridad
 
Considera factores externos al proceso [23, Tanenbaum].
Las ideas centrales son que cada proceso tiene asociada una prioridad y que el proceso ejecutable con máxima prioridad es el que tiene el permiso de ejecución.
Los procesos de alta prioridad podrían ejecutar indefinidamente, ya que el planificador del sistema puede disminuir la prioridad del proceso en ejecución en cada interrupción del reloj.
Las prioridades también pueden ser asignadas dinámicamente por el sistema para lograr ciertas metas relacionadas con el procesador o la Entrada / Salida.
Los procesos limitados por la Entrada / Salida (requerimientos intensivos de Entrada / Salida) ocupan mucho de su tiempo en espera de operaciones de Entrada / Salida, por lo tanto:

• Deben tener prioridad para usar la cpu y efectuar la siguiente petición de Entrada / Salida, ya que se ejecutará (la operación de Entrada / Salida) en paralelo con otro proceso que utilice la cpu.
• Si deben esperar mucho tiempo a la cpu estarán ocupando memoria por un tiempo innecesario.

Un algoritmo sencillo consiste en establecer que la prioridad sea “1 / f”, donde “f” es la fracción del último cuanto utilizado por el proceso. Un proceso que utilice 2 mseg (dos milisegundos) de su cuanto de 100 mseg (cien milisegundos) tendrá prioridad 50 (cincuenta).
Un proceso que se ejecutó 50 mseg antes del bloqueo tendrá prioridad 2.
Un proceso que utilizó todo el cuanto tendrá prioridad 1.
Frecuentemente los procesos se agrupan en “Clases de Prioridad”, en cuyo caso se utiliza la Planificación con Prioridades entre las clases y con Round Robin (RR) dentro de cada clase. Si las prioridades no se reajustan en algún momento, los procesos de las clases de prioridad mínima podrían demorarse indefinidamente.



Colas de Retroalimentación de Niveles Múltiples
 
Proporcionan una estructura para lograr los siguientes objetivos:

• Favorecer trabajos cortos.
• Favorecer trabajos limitados por la Entrada / Salida para optimizar el uso de los dispositivos de Entrada / Salida.
• Determinar la naturaleza de un trabajo lo más rápido posible y planificar el trabajo (proceso) en consecuencia.

Un nuevo proceso entra en la red de línea de espera al final de la cola superior. Se mueve por esta cola “FIFO” hasta obtener la cpu.
Si el trabajo termina o abandona la cpu para esperar por la terminación de una operación de Entrada / Salida o la terminación de algún otro suceso, el trabajo abandona la red de línea de espera.
Si su cuanto expira antes de abandonar la cpu voluntariamente, el proceso se coloca en la parte trasera de la cola del siguiente nivel inferior.
El trabajo recibe servicio al llegar a la cabeza de esta cola si la primera está vacía.
Mientras el proceso continúe consumiendo totalmente su cuanto en cada nivel, continuará moviéndose hacia el final de las colas inferiores.
Generalmente hay una cola en la parte más profunda a través de la cual el proceso circula en asignación de rueda hasta que termina.
Existen esquemas en los que el cuanto otorgado al proceso aumenta a medida que el proceso se mueve hacia las colas de los niveles inferiores, en tal caso, cuanto más tiempo haya estado el proceso en la red de línea de espera, mayor será su cuanto cada vez que obtiene la cpu y no podrá obtener la cpu muy a menudo debido a la mayor prioridad de los procesos de las colas superiores.
Un proceso situado en una cola dada no podrá ser ejecutado hasta que las colas de los niveles superiores estén vacías.
Un proceso en ejecución es apropiado por un proceso que llegue a una cola superior.
Es un mecanismo adaptable, es decir que se adapta a cargas variables.
A los efectos de una revisión gráfica de lo enunciado precedentemente, ver la figura 2.5 [7, Deitel].


Política Versus Mecanismo de Planificación
 
Puede ocurrir que haya procesos con muchos procesos hijos ejecutándose bajo su control, por ejemplo, un proceso en un DBMS con procesos hijos atendiendo funciones específicas, tales como, análisis de interrogantes, acceso a discos, etc.
Es posible que el proceso principal (padre) pueda identificar la importancia (o criticidad) de sus procesos hijos, pero los planificadores analizados no aceptan datos de los procesos de usuario relativos a decisiones de planificación.
La solución es separar el mecanismo de planificación de la política de planificación, para ello se parametriza el algoritmo de planificación y los parámetros pueden ser determinados por medio de procesos del usuario; así el mecanismo está en el núcleo del Sistema Operativo pero la política queda establecida por un proceso del usuario.

[7] H. M. Deitel. Introducción a los Sistemas Operativos. Addison-Wesley Iberoamericana, México, 1987.

[23] A. S. Tanenbaum. Sistemas Operativos Modernos. Prentice Hall Hispanoamericana, S.A., México, 1993.

Criterios de Planificación

Para realizar los objetivos de la planificación, un mecanismo de planificación debe considerar lo siguiente [7, Deitel]:

• La limitación de un proceso a las operaciones de Entrada / Salida: cuando un proceso consigue la cpu, ¿la utiliza solo brevemente antes de generar una petición de Entrada / Salida?.
• La limitación de un proceso a la cpu: cuando un proceso obtiene la cpu, ¿tiende a usarla hasta que expira su tiempo?.
• Si un proceso es por lote (batch) o interactivo: los usuarios interactivos deben recibir inmediato servicio para garantizar buenos tiempos de respuesta.
• ¿Qué urgencia tiene una respuesta rápida?: por ejemplo, un proceso de tiempo real de un sistema de control que supervise una refinería de combustible requiere una respuesta rápida, más rápida que la respuesta requerida por un proceso en lotes (batch) que deberá entregarse al día siguiente.
• La prioridad de un proceso: a mayor prioridad mejor tratamiento.
• Frecuentemente un proceso genera fallos (carencias) de página:
  • Probablemente los procesos que generan pocos fallos de página hayan acumulado sus “conjuntos de trabajo” en el almacenamiento principal.
  • Los procesos que experimentan gran cantidad de fallos de página aún no han establecido sus conjuntos de trabajo.
  • Un criterio indica favorecer a los procesos que han establecido sus conjuntos de trabajo.
  • Otro criterio indica favorecer a los procesos con una tasa alta de fallos de página ya que rápidamente generarán una petición de Entrada / Salida.
• Frecuentemente un proceso ha sido apropiado por otro de más alta prioridad, lo cual significa lo siguiente:
  • A menudo los procesos apropiados deben recibir un tratamiento menos favorable.
  • Cada vez que el Sistema Operativo asume la sobrecarga para hacer ejecutar este proceso, el corto tiempo de ejecución antes de la apropiación no justifica la sobrecarga de hacer ejecutar al proceso en primer lugar.
• ¿Cuánto tiempo de ejecución real ha recibido el proceso?: un criterio considera que debe ser favorecido un proceso que ha recibido muy poco tiempo de cpu.
• ¿Cuánto tiempo adicional va a necesitar el proceso para terminar?: los tiempos promedio de espera pueden reducirse priorizando los procesos que requieren de un tiempo de ejecución mínimo para su terminación, pero pocas veces es posible conocer la cantidad de tiempo adicional que cada proceso necesita para terminar. 

[7] H. M. Deitel. Introducción a los Sistemas Operativos. Addison-Wesley Iberoamericana, México, 1987. 

Objetivos de la Planificación

Los objetivos de la planificación del procesador son los siguientes e involucran a los conceptos detallados seguidamente [7, Deitel]:

• Ser justa:
  • Todos los procesos son tratados de igual manera.
  • Ningún proceso es postergado indefinidamente.
• Maximizar la capacidad de ejecución:
  • Maximizar el número de procesos servidos por unidad de tiempo.
• Maximizar el número de usuarios interactivos que reciban unos tiempos de respuesta aceptables:
  • En un máximo de unos segundos.
• Ser predecible:
  • Un trabajo dado debe ejecutarse aproximadamente en la misma cantidad de tiempo independientemente de la carga del sistema.
• Minimizar la sobrecarga:
  • No suele considerarse un objetivo muy importante.
• Equilibrar el uso de recursos:
  • Favorecer a los procesos que utilizarán recursos infrautilizados.
• Equilibrar respuesta y utilización:
  • La mejor manera de garantizar buenos tiempos de respuesta es disponer de los recursos suficientes cuando se necesitan, pero la utilización total de recursos podrá ser pobre.
• Evitar la postergación indefinida:
  • Se utiliza la estrategia del “envejecimiento” .
  • Mientras un proceso espera por un recurso su prioridad debe aumentar, así la prioridad llegará a ser tan alta que el proceso recibirá el recurso esperado.
• Asegurar la prioridad:
  • Los mecanismos de planificación deben favorecer a los procesos con prioridades más altas.
• Dar preferencia a los procesos que mantienen recursos claves:
  • Un proceso de baja prioridad podría mantener un recurso clave, que puede ser requerido por un proceso de más alta prioridad.
  • Si el recurso es no apropiativo, el mecanismo de planificación debe otorgar al proceso un tratamiento mejor del que le correspondería normalmente, puesto que es necesario liberar rápidamente el recurso clave.
• Dar mejor tratamiento a los procesos que muestren un “comportamiento deseable”:
  • Un ejemplo de comportamiento deseable es una tasa baja de paginación.
• Degradarse suavemente con cargas pesadas:
  • Un mecanismo de planificación no debe colapsar con el peso de una exigente carga del sistema.
  • Se debe evitar una carga excesiva mediante las siguientes acciones:
    • No permitiendo que se creen nuevos procesos cuando la carga ya es pesada.
    • Dando servicio a la carga más pesada al proporcionar un nivel moderadamente reducido de servicio a todos los procesos.

Muchas de estas metas se encuentran en conflicto entre sí, por lo que la planificación se convierte en un problema complejo.

[7] H. M. Deitel. Introducción a los Sistemas Operativos. Addison-Wesley Iberoamericana, México, 1987. 

Niveles de Planificación del Procesador

Se consideran tres niveles importantes de planificación, los que se detallan a continuación (ver Figura 2.4 [7, Deitel]):

• Planificación de alto nivel:
  • También se denomina Planificación de trabajos.
  • Determina a qué trabajos se les va a permitir competir activamente por los recursos del sistema, lo cual se denomina Planificación de admisión.
• Planificación de nivel intermedio:
  • Determina a qué procesos se les puede permitir competir por la cpu.
  • Responde a fluctuaciones a corto plazo en la carga del sistema y efectúa “suspensiones” y “activaciones” (“reanudaciones”) de procesos.
  • Debe ayudar a alcanzar ciertas metas en el rendimiento total del sistema.
• Planificación de bajo nivel:
  • Determina a qué proceso listo se le asigna la cpu cuando esta queda disponible y asigna la cpu al mismo, es decir que “despacha” la cpu al proceso.
  • La efectúa el Despachador del Sistema Operativo, el que opera muchas veces por segundo y reside siempre en el almacenamiento primario. 
  
    Los distintos Sistemas Operativos utilizan varias Políticas de Planificación, que se instrumentan mediante Mecanismos de Planificación.
  
  [7] H. M. Deitel. Introducción a los Sistemas Operativos. Addison-Wesley Iberoamericana, México, 1987.

Planificación de Procesos

Cuando más de un proceso es ejecutable desde el punto de vista lógico, el Sistema Operativo debe decidir cuál de ellos debe ejecutarse en primer término.
El Planificador es la porción del Sistema Operativo que decide y el Algoritmo de Planificación es el utilizado.
Los principales “criterios” respecto de un buen algoritmo de planificación [23, Tanenbaum] son la equidad, la eficacia, el tiempo de respuesta, el tiempo de regreso y el rendimiento (ver Tabla 2.2 [23, Tanenbaum]).

Tabla 2.2: Criterios de un buen algoritmo de planificación.

Criterio	Descripción
Equidad	Garantizar que cada proceso obtiene su proporción justa de la cpu
Eficacia	Mantener ocupada la cpu el ciento por ciento del tiempo
Tiempo de respuesta	Minimizar el tiempo de respuesta para los usuarios interactivos
Tiempo de regreso	Minimizar el tiempo que deben esperar los usuarios por lotes (batch) para obtener sus resultados
Rendimiento	Maximizar el número de tareas procesadas por hora

Algunas de estas metas son contradictorias, por ejemplo, minimizar el tiempo de respuesta para los usuarios interactivos significaría no ejecutar las tareas batch.

Cada proceso es único e impredecible, es decir que pueden requerir intensivamente operaciones de Entrada / Salida o intensivamente cpu; el planificador del Sistema Operativo no tiene la certeza de cuánto tiempo transcurrirá hasta que un proceso se bloquee, ya sea por una operación de Entrada / Salida o por otra razón .
Para evitar que un proceso se apropie de la cpu un tiempo excesivo, los equipos poseen un dispositivo que provoca una interrupción en forma periódica, por ejemplo 60 hz, o sea sesenta veces por segundo.
En cada interrupción del reloj el Sistema Operativo decide si el proceso que se está ejecutando continúa o si el proceso agotó su tiempo de cpu y debe suspenderse y ceder la cpu a otro proceso.
Los principales conceptos relacionados con Planificación del Procesador son los siguiente:

• Planificación apropiativa: es la estrategia de permitir que procesos ejecutables (desde el punto de vista lógico) sean suspendidos temporalmente.
• Planificación no apropiativa: es la estrategia de permitir la ejecución de un proceso hasta terminar.
• Planificación del procesador: determinar cuándo deben asignarse los procesadores y a qué procesos, lo cual es responsabilidad del Sistema Operativo.

[23] A. S. Tanenbaum. Sistemas Operativos Modernos. Prentice Hall Hispanoamericana, S.A., México, 1993.