3.1   Politica y Filosofia.

Filosofia:

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.

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 informacion contenida en ella es de mas rapido acceso.
       
Solo la memoria cache es mas rapida que la principal, pero su costo es a su vez mayor.


Cuando no existe memoria virtual no hay diferenciacion entre el espacio de direcciones y la memoria real; el espacio de direcciones que puede ser usado en los programas tiene identico tamano al espacio de memoria real posible. Si se utiliza memoria virtual, el espacio de direcciones disponibles para los programas es aquel determinado por el tamano de la memoria virtual implementada y no el espacio de direcciones provisto por la memoria real disponible (el espacio de la memoria virtual sera mayor que el de la memoria real).


La organización y administración de la “memoria principal”, “memoria primaria” o “memoria real” de un sistema ha sido y es uno de los factores mas importantes en el diseño de los S. O.
Los términos “memoria” y “almacenamiento” se consideran equivalentes. 


Los programas y datos deben estar en el almacenamiento principal para:

• Poderlos ejecutar.
• Referenciarlos directamente.  

 


 




 3.3   Organizacion de Memoria Virtual


Mediante un esquema se ejecutan programas que no se encuentran totalmente en memoria principal. Por lo tanto, un programa puede tener un tamaño mayor a la memoria fisica disponible.




Los metodos mas comunes para poner en practica el almacenamiento visrual son:

• Paginacion.
• Segmentacion

Conceptos Basicos:

• Las direcciones referidas por un proceso se denominan Direcciones Virtuales o Logicas (L). Por otra parte, las direcciones disponibles en memoria principal se denominan Direcciones Fisicas (F).

• En el momento de ejecucion de los programas, las direcciones logicas deben hacerse corresponder con las direcciones fisicas, mediante una aplicacion m: L ----> F , la cual se denomina Mapeo de Memoria (Mapping).

La memoria virtual ha llegado a ser un componente esencial de la mayoría de los S.O actuales. Y como en un

instante dado, en la memoria solo se tienen unos pocos fragmentos de un proceso dado, se pueden mantener más procesos en la memoria.

La memoria virtual también simplifica la carga del programa para su ejecución llamado reubicación, este procedimiento permite que el mismo programa se ejecute en cualquier posición de la memoria física.

 

Los métodos más comunes de implementación son mediante:

• Técnicas de “paginación”.
• Técnicas de “segmentación”.
• Una combinación de ambas técnicas. 

Paginación

¿Qué es la paginación?

 
El termino memoria virtual se asocia normalmente con sistemas que emplean paginación, aunque también se puede usar memoria virtual basada en la segmentación. El uso de la paginación en la memoria virtual fue presentado por primera vez en el computador Atlas.

Cada proceso tiene su propia tabla de paginas y cuando carga todas sus paginas en la o memoria principal. Puesto que solo algunas de las páginas de un proceso pueden estar en la memoria principal, se necesita un bit en cada entrada de la tabla para indicar si la pagina perteneciente esta presente en la memoria principal o no. Si el bit indica que la pagina esta en la memoria, la entrada incluye también el número de marco para esa pagina.

Otro bit de control necesario en la entrada de la tabla de páginas es el bit de modificación (M), para indicar si el contenido de la página correspondiente se ha alterado desde que la página se cargo en la memoria principal. Si no ha habido cambios, no es necesario escribir la página cuando sea sustituida en el marco que ocupa actualmente.

 

Segmentación

Implicaciones de la memoria virtual


La segmentación permite al programador contemplar la memoria como si constara de varios espacios de direcciones o segmentos. Los segmentos pueden ser de distintos tamaños, incluso de forma dinámica. Las referencias a la memoria constan de una dirección de la forma (numero de segmento, desplazamiento).

Esta organización ofrece al programador varias ventajas sobre un espacio de direcciones no segmentado:
1. Simplifica la gestión de estructuras de datos crecientes. Si el programador no conoce a priori cuan larga puede llegar a ser una estructura de datos determinada, es necesario suponerlo a menos que se permitan tamaños de segmentos dinámicos. Con memoria virtual segmentada, a la estructura de datos se le puede asignar a su propio segmento y el S.O expandirá o reducirá el segmento cuando se necesite.
2. Permite modificar y recopilar los programas independientemente, sin que sea necesario recopilar o volver a montar el conjunto de programas por completo.
3. Se presta a la comparición entre procesos. Un programador puede situar un programa de utilidades o una tabla de datos en un segmento que puede ser referenciado por otros procesos.
4. Se presta a la protección. Puesto que un segmento puede ser construido para albergar un conjunto de procedimientos y datos bien definido, el programador o el administrador del sistema podrán asignar los permisos de acceso de la forma adecuada.

Organización

 
En el estudio de la segmentación simple, se llego a la conclusión de que cada proceso tiene su propia tabla de segmento y que, cuando todos los segmentos se encuentran en la memoria principal, la tabla de segmentos del proceso se crea y se carga en la memoria. Cada entrada de la tabla contiene la dirección de comienzo del segmento correspondiente de la memoria principal, así como su longitud. La misma estructura se necesitara al hablar de un esquema de memoria virtual basado en la segmentación donde las entradas de la tabla de segmentos pasan a ser mas complejas.

Puesto que solo algunos de los segmentos de un proceso estarán en la memoria principal, se necesita un bit en cada entrada de la tabla de segmentos para indicar si el segmento correspondiente esta presente en la memoria principal. Si el bit indica que el segmento esta en la memoria, la entrada incluye también la dirección de comienzo y la longitud del segmento.

Otro bit de control necesario en la entrada de la tabla de segmentos es un bit de modificación que indique si el contenido del segmento correspondiente ha sido modificado desde que se cargo por última vez en la memoria principal. Si no ha habido cambios, no será necesario escribir en el disco el segmento cuando llegue el momento de reemplazarlo en el espacio que ocupa actualmente

Sistema de paginación / segmentación

La paginación y la segmentación puras son métodos de manejo de memoria bastante efectivos, aunque la mayoría de los sistemas operativos modernos implantan esquemas combinados, es decir, combinan la paginación y la segmentación.

La idea de combinar estos esquemas se debe a que de esta forma se aprovechan los conceptos de la división lógica de los programas (segmentos) con la granularidad de las páginas. De esta forma, un proceso estará repartido en la memoria real en pequeñas unidades (paginas) cuya liga son los segmentos. También es factible así el compartir segmentos a medida que las partes necesitadas de los mismos se van reverenciando (paginas).

Para comprender este esquema, nuevamente se vera como se traduce una dirección virtual en una localidad de memoria real. Para la paginación y segmentación puras se puede decir que el direccionamiento es `bidimensional' porque se necesitan dos valores para hallar la dirección real.
Para el caso combinado, se puede decir que se tiene un direccionamiento `tridimensional'.

El sistema debe contar con una tabla de procesos (TP) (Ver figura 3.3.4.1). Por cada renglón de esa tabla se tiene un número de proceso y una dirección a una tabla de segmentos. Es decir, cada proceso tiene una tabla de segmentos. Cuando un proceso hace alguna referencia a memoria, se consulta TP para encontrar la tabla de segmentos de ese proceso. En cada tabla de segmentos de proceso (TSP) se tienen los números de los segmentos que componen a ese proceso.

Por cada segmento se tiene una dirección a una tabla de páginas. Cada tabla de páginas tiene las direcciones de las páginas que componen a un solo segmento. Por ejemplo, el segmento `A' puede estar formado por las paginas reales `a','b','c','p' y `x'. El segmento `B' puede estar compuesto de las paginas `f','g','j','w' y `z'. Otro aspecto importante es la estrategia para cargar páginas (o segmentos) a la memoria RAM.

Se usan más comúnmente dos estrategias: cargado de páginas por demanda y cargado de páginas anticipada. La estrategia de cargado por demanda consiste en que las páginas solamente son llevadas a RAM si fueron solicitadas, es decir, si se hizo referencia a una dirección que cae dentro de ellas.

Administración de Memoria   3.4.1 Estrategias de Administración

Estrategias de Obtención

Determinan cuando se debe de transferir una página o un segmento de almacenamiento secundario al primario. Las estrategias de obtención por demanda esperan a que un proceso en ejecución haga referencia a una página o un segmento antes de traer la página o el segmento de almacenamiento primario. Los esquemas de obtención anticipada intentan determinar por adelantado a cuales páginas o segmentos hará referencia un proceso.

Estrategias de Colocación

Determinan en que lugar del almacenamiento primario se debe colocar una página o un segmento entrante. Una página entrante se puede colocar en cualquier marco de página disponible.

Estrategias de Reemplazo

Sirven para decidir cual pagina o segmento se debe desplazar para dar espacio a una pagina o segmento entrante cuando esta completamente ocupado el almacenamiento primario.

Técnicas de reemplazo de pagina

Las rutinas de administración de almacenamiento del Sistema operativo deben decidir que pagina del almacenamiento primario se debe desplazar para dejar espacio a una pagina entrante.

Principio de Optimalizad

Para obtener un rendimiento optimo, la pagina que se debe reemplazar es aquella que tardara mas tiempo en ser utilizada. Esta estrategia óptima de reemplazo se denomina OPT o MIN.

Reemplazo de Páginas aleatorio

Es una técnica sencilla. Todas las páginas que se encuentran en el almacenamiento principal tienen la misma probabilidad de ser elegidas para el reemplazo. Esta estrategia podría seleccionar cualquier página para ser reemplazada, incluyendo la siguiente página la que se hará referencia. Las decisiones de reemplazo aleatorio se de paginas se pueden tomar rápidamente y con un numero significativo de marcos de pagina. Es un esquema que casi no se utiliza por su enfoque aleatorio de acertar o errar.

Reemplazo de páginas de primeras entradas-primeras salidas (PEPS)

Cada pagina se registra en el instante que entro en el almacenamiento primario. Cuando se necesita reemplazar una pagina, se escoge la que ha permanecido en el almacenamiento durante el mayor tiempo.

Anomalías PEPS

Belady, Nelson y Shelder descubrieron que al utilizar el reemplazo de paginas PEPS, ciertos patrones de referencia a pagina originan mas fallas de paginas cuando aumenta el numero de marcos de pagina asignados a un proceso. Este fenómeno se denomina Anomalía PEPS o anomalía Belady. La columna de la izquierda indica el patrón de referencias a páginas de un proceso. La primera tabla muestra como dicho patrón a referencia de páginas hace que las páginas se carguen a memoria y se reemplacen en secuencia PEPS cuando se asignan tres marcos de páginas a proceso.
La segunda tabla muestra como se comporta este proceso en las mismas circunstancias, pero con cuatro marcos de paginas asignados, a la izquierda de cada tabla se indica si la nueva referencia a una pagina ocasiona o no una falla de pagina. Cuando el proceso se ejecuta en cuatro páginas, experimenta una falla de página más que cuando se ejecuta con tres.

Reemplazo de páginas de la menos reciente utilizada

Se selecciona para su reemplazo, a aquella pagina que no se ha sido utilizada durante mayor tiempo. La estrategia se basa en que la heurística de localidad según en el cual el pasado reciente es un buen indicador del futuro cercano, de modo que LRU exige que se marque cada pagina con el instante en que .se hace referencia a ella. Por el trabajo adicional que requiere no se usa a menudo en los sistemas actuales; lo que se hace es utilizar estrategias que ese aproximen a la LRU y que no ocasionen grandes costos.

Reemplazo de páginas de la menos frecuentemente utilizada (LFU)

La pagina por remplazar es aquella que ha sido utilizada menos frecuentemente o a la que se ha hecho referencia con menos frecuencia.
Al parecer estos esquemas de reemplazo de páginas corren cierto riesgo de tomar decisiones equivocadas. Esto sucede por el simple hecho de que no se puede predecir con precisión el futuro.

Modificaciones de PEPS; reemplazo de paginas por reloj y reemplazo de paginas con segunda oportunidad

La estrategia PEPS puede decidir reemplazar una pagina muy utilizada que ha permanecido en memoria durante mucho tiempo. Esta posibilidad se puede evitar reemplazando solo aquellas paginas cuyos bits de referencia valgan O.
La variante de PEPS denominada "con segunde oportunidad" examina el bit de referencia de la pagina mas antigua; si este bit vale O, se selecciona de inmediato la pagina para ser reemplazada. Si el bit de referencia vale 1, se le asigna el valor O y la pagina se pasa al final de la lista y se considera en esencia como una pagina nueva; gradualmente dicha pagina se desplaza hacia el principio de la lista, donde será seleccionada para reemplazo solo si su bit de referencia sigue valiendo O. En esencia, esto da a la página una segunda oportunidad de permanecer en el almacenamiento principal si su bit de referencia cambia a 1 antes de que la pagina llegue al principio de la lista. La variación 'z' del reloj" del algoritmo de la segunda oportunidad dispone las paginas en una lista circular, en lugar de en una lista lineal.

Un apuntador a la lista se desplaza alrededor de la lista circular en la misma forma que gira la manecilla de un reloj. Cuando el bit de referencia de una página toma el valor O, el apuntador se mueve al siguiente elemento de la lista (simulando el movirl1iento de esta pagina al final de la lista PEPS).

Unidad III. Memorias

Memoria...

Los circuitos que permiten almacenar y recuperar la información. En un sentido más amplio, puede referirse también a sistemas externos de almacenamiento, como las unidades de disco o de cinta. Por lo general se refiere sólo al semiconductor rápido de almacenaje (RAM) conectado directamente al procesador.

Memoria de Computadora

Como el microprocesador no es capaz por sí solo de albergar la gran cantidad de memoria necesaria para almacenar instrucciones y datos de programa (por ejemplo, el texto de un programa de tratamiento de texto), pueden emplearse transistores como elementos de memoria en combinación con el microprocesador. Para proporcionar la memoria necesaria se emplean otros circuitos integrados llamados chips de memoria de acceso aleatorio (RAM, siglas en inglés), que contienen grandes cantidades de transistores. Existen diversos tipos de memoria de acceso aleatorio. La RAM estática (SRAM) conserva la información mientras esté conectada la tensión de alimentación, y suele emplearse como memoria cache porque funciona a gran velocidad. Otro tipo de memoria, la RAM dinámica (DRAM), es más lenta que la SRAM y debe recibir electricidad periódicamente para no borrarse.
La DRAM resulta más económica que la SRAM y se emplea como elemento principal de memoria en la mayoría de las computadoras.  

Memoria de Acceso Aleatório o RAM 
En informática, memoria basada en semiconductores que puede ser leída y escrita por el microprocesador u otros dispositivos de hardware. Es un acrónimo del inglés Random Access Memory. Se puede acceder a las posiciones de almacenamiento en cualquier orden. 

Caché de Disco 

En informática, una parte de la memoria de acceso aleatorio de un ordenador o computadora que se reserva para contener, de manera temporal, información leída o escrita recientemente en el disco. La memoria caché de disco realiza distintas funciones: en unos casos, almacena direcciones concretas de sectores; en otros, almacena una copia del directorio y en otros, almacena porciones o extensiones del programa o programas en ejecución. 

Memoria Programable o Borrable o de Sólo Lectura o EPROM

En informática, tipo de memoria, también denominada reprogramable de sólo lectura (RPROM, acrónimo inglés de Reprogrammable Read Only Memory). Las EPROM (acrónimo inglés de Erasable Programmable Read Only Memory) son chips de memoria que se programan después de su fabricación. Son un buen método para que los fabricantes de hardware inserten códigos variables o que cambian constantemente en un prototipo, en aquellos casos en los que producir gran cantidad de chips PROM resultaría prohibitivo. Los chips EPROM se diferencian de los PROM por el hecho de que pueden borrarse por lo general, retirando una cubierta protectora de la parte superior del chip y exponiendo el material semiconductor a radiación ultravioleta, después de lo cual pueden reprogramarse. 

Memoria Programable de Sólo Lectura o PROM

En informática, tipo de memoria de sólo lectura (ROM) que permite ser grabada con datos mediante un hardware llamado programador de PROM. Una vez que la PROM ha sido programada, los datos permanecen fijos y no pueden reprogramarse. Dado que las ROM son rentables sólo cuando se producen en grandes cantidades, se utilizan memorias programables de sólo lectura durante las fases de creación del prototipo de los diseños. Nuevas PROM pueden grabarse y desecharse durante el proceso de perfeccionamiento del diseño. 

Memoria de Sólo Lectura o ROM

En informática, memoria basada en semiconductores que contiene instrucciones o datos que se pueden leer pero no modificar. Para crear un chip ROM, el diseñador facilita a un fabricante de semiconductores la información o las instrucciones que se van a almacenar. El fabricante produce entonces uno o más chips que contienen esas instrucciones o datos. Como crear chips ROM implica un proceso de fabricación, esta creación es viable económicamente sólo si se producen grandes cantidades de chips. Los diseños experimentales o los pequeños volúmenes son más asequibles usando PROM o EPROM. El término ROM se suele referir a cualquier dispositivo de sólo lectura, incluyendo PROM y EPROM. 

Memoria Expandida

En informática, en los PC de IBM y en los compatibles, organización lógica de memoria, de hasta 8 megabytes (MB) que puede utilizarse en las máquinas que ejecutan MS-DOS en modo real (emulación de 8086). El uso de la memoria expandida está definido en la EMS (Especificación de Memoria Expandida). Como representa la memoria a la que normalmente no acceden los programas que ejecutan MS-DOS, la memoria expandida requiere una interfaz denominada EMM (Gestor de Memoria Expandida), que asigna páginas (bloques) de bytes de la memoria expandida según se necesiten. Sólo el software compatible con EMS puede utilizar la memoria expandida. 

Memoria Extendida

En informática, la parte de memoria del sistema que supera 1 megabyte (MB) en las computadoras basadas en procesadores Intel 80286/386/486. Sólo se puede tener acceso a esta memoria cuando el procesador trabaja en modo protegido o en modo virtual real en los equipos 386/486. Normalmente MS-DOS no puede utilizar la memoria extendida. Puede permitirse el acceso a esta memoria mediante la utilización de un determinado software que hace que el microprocesador quede en modo protegido, o mediante el uso de las posibilidades que los procesadores 386 y 486 tienen para asignar determinadas porciones de la memoria expandida como memoria convencional. Para ello se utilizan las convenciones EMS. 

Buffer de Memoria Intermedia 

En informática, depósito de datos intermedio, es decir, una parte reservada de la memoria en la que los datos son mantenidos temporalmente hasta tener una oportunidad de completar su transferencia hacia o desde un dispositivo de almacenamiento u otra ubicación en la memoria. Algunos dispositivos, como las impresoras o como los adaptadores que las soportan, suelen tener sus propios buffers. 

Memoria Caché L2 (Segundo Nivel) 

Almacena los datos transferidos más recientemente entre la memoria RAM y el microprocesador.
Así, si el microprocesador necesita algo de esta información accede directamente a la caché sin acudir a la RAM. De esta forma acelera la ejecución de las instrucciones del microprocesador ya que la caché trabaja más rápido que la RAM.

 

Tipos de Planificacion de Procesos

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 
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.

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.

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

Criterios de Planificacion

Para realizar los objetivos de la planificación, un mecanismo de planificación debe considerar lo siguiente

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

Objetivos de la Planificación

Los objetivos de la planificación del procesador son los siguientes e involucran a los conceptos detallados seguidamente: 

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