Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

La Memoria Como Mecanismo De Comunicación

No description
by

Leiby Romero

on 24 November 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of La Memoria Como Mecanismo De Comunicación

La Memoria Como Mecanismo De Comunicación
Intercambio.
La técnica del intercambio (swapping) significó en su momento una manera de permitir que en los sistemas del tiempo compartido existieran más procesos de los que caben en memoria. Se puede considerar que se trata de un mecanismo antecesor de la memoria virtual.
El intercambio se basa en usar un disco o parte de un disco (dispositivo de swap) como respaldo de la memoria principal.
En cuanto al dispositivo de swap, hay dos alternativas en la asignación de espacio:
-
Preasignación
. Al crear el proceso ya se reserva espacio suficiente para albergarlo.
-
Sin preasignación.
Sólo se reserva espacio de swap cuando se expulsa el proceso.
Memoria Virtual.
Es un sistema que está organizado como una jerarquía de niveles de almacenamiento, entre los que se mueve la información dependiendo de la necesidad de la misma en un determinado instante. La técnica de memoria virtual se ocupa de la transferencia de información entre la memoria principal y la secundaria. La memoria secundaria está normalmente soportada en un disco (o partición). La memoria virtual se implementa sobre un esquema de paginación, a este dispositivo se le denomina Dispositivo de Paginación.
El rendimiento del sistema de memoria virtual está basado en que los procesos presentan la propiedad de Proximidad de Referencias. Esta propiedad permite que un proceso genere muy pocos fallos aunque tenga en memoria principal sólo una parte de su imagen de memoria (Conjunto Residente).
Algunos beneficios del uso de memoria virtual son los siguientes:
. Se produce un aumento del grado de multiprogramación al no ser necesario que todo el mapa de memoria de un proceso esté en memoria principal para poder ejecutarlo. Este aumento implica una mejora en el rendimiento del sistema . Sin embargo, si el grado de multiprogramación se hace demasiado alto, el número de fallos de pagina se dispara y el rendimiento del sistema baja drásticamente. A esta situación se le denomina Hiperpaginación.
. Se puede ejecutar programas más grandes que la memoria principal disponible.
Paginación.
Los sistemas de gestiónde memoria basados en asignación contigua presentan numerosas restricciones a la hora de satisfacer los requisitos que debe cumplir el gestor de memoria del sistema operativo. La paginación surge como un intento de paliar estos problemas sofisticando apreciablemente el hardware de gestión de memoria del procesador y aumentando considerablemente la cantidad considerablemente la cantidad de información de traducción que se almacena por cada proceso.
Como su nombre indica, la unidad básica de este tipo de esquema es la página. La página corresponde con una zona de memoria contigua de un determinado tamaño. Por motivos de eficiencia en la traducción, este tamaño debe ser potencia de 2 (un tamaño de página de 4 KB es un valor bastante típico.)
Cada entrada de la tabla de páginas, además del número de marco que corresponde con esa página, contiene información adicional tal como la siguiente:
.
Información De Protección.
Un conjunto de bits que especifican qué tipo de accesos están permitidos.
.
Indicación De Página Válida.
Un bit que especifica si esa página es válida, sea, tiene una traducción asociada.


Con la paginación se le asigna a cada proceso un número entero de marcos de páginas, aunque, en general, su mapa no tendrá un tamaño múltiplo del tamaño del marco. Por tanto, se desperdiciará parte del último marco asignado al proceso, lo que correspondería con las zonas sombreadas a este fenómeno se le denomina Fragmentación Interna e implica por cada proceso se desperdiciará, en término medio, la mitad de una página, lo cual es un valor bastante tolerable.
Glosario.
- DMA: Direct Memory Access en español ADM (Acceso Directo a Memoria).
- MMU: Memory Management Unit en español UGM (Unidad de Gestión de Memoria).
- TLB: Traslation Lookaside Buffer en español BTA (Buffer de Traducción Anticipada).
- MIPS: Microprocessor without Interlocked Pipeline Stages en español (Microprocesador sin etapas de canalización interbloqueadas).
- FIFO: First Input-First Output en español PEPS (Primeras en Entrar- Primeras en Salir).
- LRU: Least Recently Used en español (Menos Recientemente Usada).
- POSIX es el acrónimo de Portable Operating System Interface; la X viene de UNIX como seña de identidad de la API.
- COW: Copy-On-Write en español (Copia En Escritura).
En la entrada de la tabla de páginas puede haber información adicional, tal como la siguiente:
-
Indicación de Página Accedida.
La MMU activaeste bit indicador cuando se aacede a una dirección lógica que pertenece a esa página.
-
Indicación de Página Modificada.
La MMU activa este bit indicador cuando se escribe en una dirección lógica que pertenece a esa página.
-
Desactivación de Cache.
Este bit indica que no debe usarse la cache en la memoria principal para acelerar el acceso a las direcciones de esta página.

Hay que tener en cuenta que la determinación del tamaño óptimo es un compromiso entre diversos factores:
- Un tamaño reduce la fragmentación y cuando se usa para implementar memoria virtual, permite ajustarse mejor l conjunto de trabajo del proceso.
-Un tamaño grande implica tablas más pequenas y cuando se usa para implementar memoria virtual, un mejor remdimiento en los accesos a disco.
Gestión del Sistema Operatvo.
El Sistema Operativo mantendrá una tabla de páginas para cada proceso y se encargará de notificar al hardware en cada cambio de proceso que la tabla tiene que usar dependiendo del proceso que esté ejecuntando, utilizando para ello el registro base de la tabla de páginas o el registro identificador del espacio de direccionamiento (RIED).

El Sistema operativo mantiene una única tabla de páginas para si mismo. De esta forma, todos los procesos comparten el Sistema Operativo. Cuando el Sistema Operativo está ejecutndo una llamad al sistema invocada por un proceso, puede acceder directamente a su propio mapa y al del proceso.
Valoración de la Paginación.
Una vez realizada esta presentación de los fundamentos de los esquemas de paginación, se puede analizar cómo cumplen los requisitos:
- Espacios lógicos independientes. Cada proceso tiene una tabla de páginas que crea un espacio lógico independiente para el mismo.
- Protección. La tabla de páginas de un proceso restringe qué parte de la memoria puede ser accedida por el mismo, permitiendo asegurr que los procesos usan espacios disjuntos.
- Compartir memoria. Bajo la supervisión del sistema operativo, que es el único que puede manipular las tablas de páginas.
- Soporte de ls regiones del proceso. La información de protección presente en cada entrada de la tabla de págins permite controlar que los accesos a la región son del tipo que ésta requiere.
- Maximizar el rendimiento. En primer lugar, la paginación, a pesar de la fragmentación interna, obtiene un buen aprovechamiento de la memoria, ya que elimin la necesidad de que el mapa de memoria de un proceso se almacene de forma contigua en memoria principal.
- Mapas de memoria grandes para los procesos. Gracias a que los huecos no consumen espacio de almacenamiento, el sistema operativo puede crear un mapa de memoria para el proceso que ocupe todo su espacio lógico direccionable.

Implementación de la tabla de páginas.
El esquema básico de paginación aunque funciona de manera correcta, presenta serios problemas a la hora de implementarlo directamente. Estos problemas surgen debido a la necesidad de mantener las tablas páginas en memoria principal. Esto conlleva problemas de’ eficiencia y de consumo de espacio.
Por lo que se refiere a los problemas de eficiencia, dado que para acceder a la posición de memoria solicitada, la MMU debe consultar la entrada correspondiente de la tabla de páginas, se producirán dos accesos a memoria por cada acceso real solicitado por el programa. Esta sobrecarga es intolerable, ya que reduciría a la mitad el rendimiento del sistema. Para solventar este problema, la MMU incluye internamente una especie de cache de traducciones llamada TLB (Translation Lookaside Buffer).
Por otro lado, existe un problema de gasto de memoria. Las tablas de páginas son muy grandes y hay una por cada proceso activo. La paginación permite construir mapas de memoria muy grandes para los procesos, ya que los huecos no consumen espacio. Sin embargo, si se usa todo el espacio de direccionamiento, como es deseable para conseguir que los procesos no tengan problemas de memoria durante su ejecución, la tabla de páginas debe tener tantas entradas como páginas hay en el espacio lógico, aunque muchas de ellas estén marcadas como inválidas al corresponder con huecos.
Translation Lookaside Buffer (TLB).
Para hacer que un sistema de paginación sea aplicable en la práctica es necesario que la mayoría de los accesos a memoria no impliquen una consulta a la tabla de páginas, sino que únicamente requieran el acceso a la posición solicitada. De esta forma, el rendimiento será similar al de un sistema sin paginación. Se trata de una pequeña memoria asociativa interna a la MMU que mantiene información sobre las últimas páginas accedidas. Cada entrada en la TLB es similar a la de la tabla de páginas (número de marco, protección, bit de referencia, etc.), pero incluye también el número de la página para permitir realizar una búsqueda asociativa. Existen dos alternativas en el diseño de una TLB dependiendo de si se almacenan identificadores de proceso o no.
- TLB sin identificadores de proceso. La MMU accede a la TLB sólo con el número de página. Por tanto, cada vez que hay un cambio de proceso el sistema operativo debe invalidar la TLB ya que cada proceso tiene su propio mapa.
- TLB con identificadores de proceso. La MMU accede a la TLB con el número de página y un identificador de proceso. En cada entrada de la TLB, por tanto, se almacena también este identificador. La MMU obtiene el identificador de un registro del procesador. El sistema operativo debe encargarse de asignarle un identificador a cada proceso y de rellenar este registro en cada cambio de proceso.
Algunos procesadores modernos (como, por ejemplo, MIPS o Alpha) tienen un diseño alternativo en el que se traspasa parte de la gestión de la TLB al sistema operativo. A este esquema se le denomina TLB gestionada por software. La MMU se encarga de buscar la traducción en la TLB, pero si no la encuentra produce una excepción que activa al sistema operativo.
Tabla de páginas multinivel.
Una manera de afrontar el problema del gasto de memoria de las tablas de páginas es utilizar tablas de página multinivel. Con este esquema, en vez de tener una única tabla de páginas por proceso, hay una jerarquía de tablas. Existe una única tabla de páginas de primer nivel. Cada entrada de esta tabla apunta a tablas de páginas de segundo nivel. A su vez, las tablas de página de segundo nivel apuntan a tablas de página de tercer nivel. Así, sucesivamente, por cada nivel de la jerarquía. Las tablas de páginas del último nivel apuntan directamente a marcos de página. En la práctica, esta jerarquía se limita a dos o tres niveles. A la hora de traducir una dirección lógica, el número de página contenido en la misma se considera dividido en tantas partes como niveles existan.


El esquema de tablas de página multinivel proporciona dos ventajas adicionales:
• Permite compartir tablas de páginas intermedias. Así, por ejemplo, en el caso de un sistema con dos niveles, si dos procesos comparten una región que se corresponde con una tabla de segundo nivel, pueden compartir directamente dicha tabla, O sea, cada proceso tendrá una entrada en su tabla de primer nivel que apunte a la tabla de segundo nivel compartida. De esta forma, se ahorra espacio en almacenar entradas repetidas. Observe que esto requiere que la región que se comparte se corresponda con un número entero de tablas de segundo nivel.
• Sólo es preciso que esté residente en memoria la tabla de páginas de primer nivel. Las restantes podrían almacenarse en el disco y traerlas bajo demanda.

Tabla de páginas invertida.
Otra alternativa para reducir el gasto en tablas de páginas es usar una tabla invertida. Una tabla de páginas invertida contiene una entrada por cada marco de página. Cada entrada identifica qué página está almacenada en ese marco y cuáles son sus características. Para ello, contiene el número de página y un identificador del proceso al que pertenece la página. Con este esquema hay una única tabla de páginas cuyo tamaño es proporcional al tamaño de la memoria principal. La MMU usa una TLB convencional, pero cuando no encuentra en ella la traducción debe acceder a la tabla invertida para encontrarla. Dado que la tabla está organizada por marcos, no se puede hacer una búsqueda directa. En principio, se deberían acceder a todas las entradas buscando la página solicitada. Para agilizar esta búsqueda, generalmente la tabla de páginas se organiza como una tabla hash. En esta exposición no se entrará en más detalles sobre esta organización (p. ej.: explicar cómo se resuelven las colisiones de la función hash).
Hay básicamente dos alternativas:
- Procesadores (p. ej.: PA4?.JSC) que acceden a la cache usando la dirección virtual (o parte de ella). Esto permite realizar la búsqueda en la TLB y en la cache en paralelo, pero obliga a que el sistema operativo tenga que invalidar la cache en cada cambio de proceso para evitar incoherencias.
- Procesadores (p. ej.: Alpha) que acceden a la cache usando la dirección física (o parte de ella). Con este esquema el sistema operativo no tiene que invalidar la cache, pero no permite que el acceso a la TLB y a la cache se hagan en paralelo (aunque si el tamaño de la cache es igual al de la página, sí se podría hacer en paralelo).

Segmentación.
Con la paginación, la MMU no sabe nada sobre las distintas regiones de los procesos. Sólo entiende de páginas. El sistema operativo debe guardar para cada proceso una tabla de regiones que especifique qué páginas pertenecen a cada región. Esto tiene dos desventajas:
- Para crear una región hay que rellenar las entradas de las páginas pertenecientes a la región con las mismas características. Así, por ejemplo, si se trata de una región de código que ocupa diez páginas, habrá que rellenar diez entradas especificando una protección que no permita modificarlas.
- Para compartir una región, hay que hacer que las entradas correspondientes de dos procesos apunten a los mismos marcos.
La segmentación es una técnica hardware que intenta dar soporte directo a las regiones. Para ello, considera el mapa de memoria de un proceso compuesto de múltiples segmentos. Cada región se almacenará en un segmento.Se puede considerar que esta técnica es una generalización del uso de los registros valla, pero utilizando una pareja de registro base y registro límite por cada segmento. La MMU maneja una tabla de segmentos. Cada entrada de esta tabla mantiene, además de información de protección, el registro base y límite correspondientes a esa región. Una dirección lógica está formada por un número de segmento y una dirección dentro del segmento.
Valoración de la segmentación.
La segmentación debe cumplir los requisitos :
• Espacios lógicos independientes. Cada proceso tiene una tabla de segmentos que crea un espacio lógico independiente para el mismo.
• Protección. La tabla de segmentos de un proceso restringe qué parte de la memoria puede ser accedida por el mismo, permitiendo asegurar que los procesos usan espacios disjuntos.
• Compartir memoria. Bajo la supervisión del sistema operativo, que es el único que puede manipular las tablas de segmentos, dos o más procesos pueden tener un segmento asociado a la misma zona de memoria.
• Soporte de las regiones del proceso. Este es precisamente el punto fuerte de este sistema.
• Maximizar el rendimiento. Esta es una de sus deficiencias. Por un lado, presenta fragmentación externa, por lo que no se obtiene un buen aprovechamiento de la memoria. Por otro lado, y más importante todavía, esta técnica no facilita la implementación de esquemas de memoria virtual debido al tamaño variable de los segmentos.
• Mapas de memoria grandes para los procesos. No contempla adecuadamente esta característica al no permitir implementar eficientemente un sistema de memoria virtual.

Segmentación paginada.
Como su nombre indica, la segmentación paginada intenta aunar lo mejor de los dos esquemas anteriores. La segmentación proporciona soporte directo a las regiones del proceso y la paginación permite un mejor aprovechamiento de la memoria y una base para construir un esquema de memoria virtual.
Con esta técnica, un segmento está formado por un conjunto de páginas y, por tanto, no tiene que estar contiguo en memoria. La MMU utiliza una tabla de segmentos, tal que cada entrada de la tabla apunta a una tabla de páginas.

Valoración de la segmentación paginada.
La valoración de esta técnica se corresponde con la unión de los aspectos positivos de los dos esquemas anteriores:
• Espacios lógicos independientes. Cada proceso tiene una tabla de segmentos que crea un espacio lógico independiente para el mismo.
• Protección. La tabla de segmentos de un proceso restringe qué parte de la memoria puede ser accedida por el mismo, permitiendo asegurar que los procesos usan espacios disjuntos.
• Compartir memoria. Bajo la supervisión del sistema operativo, que es el único que puede manipular las tablas de segmentos, dos o más procesos pueden tener un segmento asociado a la misma zona de memoria.
• Soporte de las regiones del proceso, gracias a la segmentación.
• Maximizar el rendimiento. La paginación proporciona un buen aprovechamiento de la memoria y puede servir como base para construir un esquema de memoria virtual.
• Mapas de memoria grandes para los procesos. La paginación permite implementar un esquema de memoria virtual.

Paginación por demanda.
la memoria virtual se construye generalmente sobre un esquema de paginación, ya sea paginación pura o segmentación paginada. Por tanto, las unidades de información que se transfieren entre la memoria principal y la secundaria son páginas.
Las transferencias desde la memoria secundaria hacia la principal se realizan normalmente bajo demanda (paginación por demanda). Cuando un proceso necesita acceder a una página que no está en memoria principal (a lo que se denomina fallo de página), el sistema operativo se encarga de transferirla desde la memoria secundaria. Si al intentar traer la página desde memoria secundaria se detecta que no hay espacio en la memoria principal (no hay marcos libres), será necesario expulsar una página de la memoria principal y transferirla a la secundaria. Por tanto, las transferencias desde la memoria principal hacia la secundaria se realizan normalmente por expulsión. El algoritmo para elegir qué página debe ser expulsada se denomina algoritmo de reemplazo.

Tratamiento del fallo de página.
La paginación por demanda está dirigida por la ocurrencia de excepciones de fallo de página que indican al sistema operativo que debe traer una página de memoria secundaria a primaria puesto que un proceso la requiere. A continuación, se especifican los pasos típicos en el tratamiento de un fallo de página:
• La MMU produce una excepción y típicamente deja en un registro especial la dirección quç causó el fallo.
• Se activa el sistema operativo que comprueba si se trata de una dirección correspondiente a una página realmente inválida o se corresponde con una página ausente de memoria. Si la página es inválida, se aborta el proceso o se le manda una señal. En caso contrario, se realizan los pasos que se describen a continuación.
• Se consulta la tabla de marcos para buscar uno libre.
• Si no hay un marco libre, se aplica el algoritmo de reemplazo para seleccionar una página para expulsar. El marco seleccionado se desconectará de la página a la que esté asociado poniendo como inválida la entrada correspondiente. Si la página está modificada, previamente hay que escribir su contenido a la memoria secundaria.
• Una vez que se obtiene el mareo libre, ya sea directamente o después de una expulsión, se inicia la lectura de la nueva página sobre el marco y, al terminar la operación, se rellena la entrada correspondiente a la página para que esté marcada como válida y apunte al marco utilizado.

Políticas de administración de la memoria virtual.
En un sistema de memoria virtual basado en paginación hay básicamente dos políticas que definen el funcionamiento del sistema de memoria:
• Política de reemplazo. Determina qué página debe ser desplazada de la memoria principal4 para dejar sitio a la página entrante.
• Política de asignación de espacio a los procesos. Decide cómo se reparte la memoria física entre los procesos existentes en un determinado instante.
Estos dos aspectos están muy relacionados entre sí y son determinantes en el rendimiento del sistema de memoria virtual. En las dos próximas secciones se analizarán estas dos políticas.

Políticas de reemplazo.
Las estrategias de reemplazo se pueden clasificar en dos categorías: reemplazo global y reemplazo local. Con una estrategia de reemplazo global, se puede seleccionar, para satisfacer el fallo de página de un proceso, un marco que actualmente tenga asociada una página de otro proceso. Esto es, un proceso puede quitarle un marco de página a otro. La estrategia de reemplazo local requiere que, para servir el fallo de página de un proceso, sólo puedan usarse marcos de páginas libres o marcos ya asociados al proceso.Existen numerosos trabajos, tanto teóricos como experimentales, sobre algoritmos de reemplazo de páginas. En esta sección se describirán los algoritmos de reemplazo más típicos. Para profundizar en aspectos teóricos avanzados se recomienda [Maekawa, 1987].
Todos estos algoritmos pueden utilizarse tanto para estrategias globales como locales. Cuando se aplica un algoritmo determinado utilizando una estrategia global, el criterio de evaluación del algoritmo se aplicará a todas las páginas en memoria principal. En el caso de una estrategia local, el criterio de evaluación del algoritmo se aplica sólo a las páginas en memoria principal que pertenecen al proceso que causó el fallo de página. La descripción de los algoritmos, por tanto, se realizará sin distinguir entre los dos tipos de estrategias.

Algoritmo de reemplazo óptimo.
Un algoritmo óptimo debe generar el mínimo número de fallos de página. Por ello, la página que se debe reemplazar es aquella que tardará más tiempo en volverse a usar.
Evidentemente, este algoritmo es irrealizable, ya que no se puede predecir cuáles serán las siguientes páginas accedidas. El interés de este algoritmo es que sirve para comparar el rendimiento de otros algoritmos realizables.

Algoritmo FIFO (First Input-First Output, primera en entrar-primera en salir).
Una estrategia sencilla e intuitivamente razonable es seleccionar para la sustitución la página que lleva más tiempo en memoria. La implementación de este algoritmo es simple. Además, no necesita ningún apoyo hardware especial. El sistema operativo debe mantener una lista de las páginas que están en memoria, ordenada por el tiempo que llevan residentes. En el caso de una estrategia local, se utiliza una lista por cada proceso. Cada vez que se trae una nueva página a memoria, se pone al final de la lista. Cuando se necesita reemplazar, se usa la página que está al principio de la lista.
Sin embargo, el rendimiento del algoritmo no es siempre bueno. La página que lleva más tiempo residente en memoria puede contener instrucciones o datos que se acceden con frecuencia. Además, en determinadas ocasiones, este algoritmo presenta un comportamiento sorprendente conocido como la anomalía de Belady [Belady, 19691. Intuitivamente parece que cuantos más marcos de página haya en el sistema, menos fallos de página se producirán. Sin embargo, ciertos patrones de referencias causan que este algoritmo tenga un comportamiento opuesto. El descubrimiento de’ esta anomalía resultó al principio sorprendente y llevó al desarrollo de modelos teóricos para analizar los sistemas de paginación. En la práctica, esta anomalía es más bien una curiosidad que demuestra que los sistemas pueden tener a veces comportamientos inesperados.

Algoritmo de la segunda oportunidad o algoritmo del reloj.
El algoritmo de reemplazo con segunda oportunidad es una modificación sencilla del FIFO que evita el problema de que una página muy utilizada sea eliminada por llevar mucho tiempo residente.
En este algoritmo, cuando se necesita reemplazar una página, se examina el bit de referencia de la página más antigua (la primera de la lista). Si no está activo, se usa esta página para el reemplazo. En caso contrario, se le da una segunda oportunidad a la página poniéndola al final de la lista y desactivando su bit de referencia. Por tanto, se la considera como si acabara de llegar a memoria. La búsqueda continuará hasta que se encuentre una página con su bit de referencia desactivado. Observe que si todas las páginas tienen activado su bit de referencia, el algoritmo degenera en un FIFO puro.
Para implementar este algoritmo, se puede usar una lista circular de las páginas residentes en memoria, en vez de una lineal (en el caso de una estrategia local, se utiliza una lista circular por cada proceso). Existe un puntero que señala en cada instante al principio de la lista. Cuando llega a memoria una página, se coloca en el lugar donde señala el puntero y, a continuación, se avanza el puntero al siguiente elemento de la lista. Cuando se busca una página para reemplazar, se examina el bit de referencia de la página a la que señala el puntero. Si está activo, se desactiva y se avanza el puntero al siguiente elemento. El puntero avanzará hasta que se encuentre una página con el bit de referencia desactivado. Esta forma de trabajo imita al comportamiento de un reloj donde el puntero que recorre la lista se comporta como la aguja del reloj. Debido a ello, a esta estrategia también se le denomina algoritmo del reloj.

Algoritmo LRU (Least Recently Used, menos recientemente usada).
El algoritmo LRU está basado en el principio de proximidad temporal de referencias: si es probable’ que se vuelvan a referenciar las páginas accedidas recientemente, la página que se debe reemplazar es la que no se ha referenciado desde hace más tiempo. El algoritmo LRU no sufre la anomalía de Belady. Pertenece a una clase de algoritmos denominados algoritmos de pila. La propiedad de estos algoritmos es que las páginas residentes en memoria para un sistema con n marcos de página son siempre un subconjunto de las que habría en un sistema con n + 1 marcos. Esta propiedad asegura que un algoritmo de este tipo nunca sufrirá la anomalía de Belady.
Hay un aspecto sutil en este algoritmo cuando se considera su versión global. A la hora de seleccionar una página, no habría que tener en cuenta el tiempo de acceso real, sino el tiempo lógico de cada proceso. O sea, habría que seleccionar la página que haya sido menos recientemente usada teniendo en cuenta el tiempo lógico de cada proceso.
A pesar de que el algoritmo LRU es realizable y proporciona un rendimiento bastante bueno, su implementación eficiente es difícil y requiere un considerable apoyo hardware. Una implementación del algoritmo podría basarse en utilizar un contador que se incremente por cada referencia a memoria. Cada posición de la tabla de páginas ha de tener un campo de tamaño suficiente para que quepa el contador. Cuando se referencia a una página, el valor actual del contador se copia por hardware a la posición de la tabla correspondiente a esa página. Cuando se produce un fallo de página, el sistema operativo examina los contadores de todas las páginas residentes en memoria y selecciona como víctima aquella que tiene el valor menor. Esta implementación’ es factible aunque requiere un hardware complejo y muy específico.

Buffering de páginas.
Una situación que intentan evitar la mayoría de los sistemas es la que se produce cuando la página seleccionada para reemplazar está modificada. En este caso, el tratamiento del fallo de página implica dos operaciones al disco, aumentando considerablemente el tiempo de servicio del fallo.
Una solución utilizada con cierta frecuencia es el buffering de páginas. Esta estrategia consiste en mantener un conjunto de marcos de página libres. Cuando se produce un fallo de página, se usa un marco de página libre, pero no se aplica el algoritmo de reemplazo. Esto es, se consume un marco de página pero no se libera otro. Cuando el sistema operativo detecta que el número de marcos de página disminuye por debajo de un cierto umbral, aplica repetidamente el algoritmo de reemplazo hasta que el número de marcos libres sea suficiente. Las páginas liberadas que no están modificadas pasan a la lista de marcos libres. Las páginas que han sido modificadas pasan a la lista de modificadas.

Retención de páginas en memoria.
Para acabar esta sección en la que se han presentado diversos algoritmos de reemplazo, hay que resaltar que no todas las páginas residentes en memoria son candidatas al reemplazo. Se puede considerar que algunas páginas están «atornilladas» a la memoria principal. En primer lugar, están las páginas del propio sistema operativo. Por simplicidad, la mayoría de los sistemas operativos tienen su mapa de memoria fijo en memoria principal.
Además, si se permite que los dispositivos de entrada/salida que usan DMA realicen transferencias directas a la memoria de un proceso, será necesario marcar las páginas implicadas como no reemplazables hasta que termine la operación.

Política de asignación de marcos de página.
En un sistema con multiprogramación existen varios procesos activos simultáneamente que comparten la memoria del sistema. Es necesario, por tanto, determinar cuántos marcos de página se asignan a cada proceso. Existen dos tipos de estrategias de asignación: asignación fija o asignación dinámica.
Asignación fija.
Se asigna a cada proceso un número fijo de marcos de página. Normalmente, este tipo de asignación lleva asociada una estrategia de reemplazo local. El número de marcos asignados no varía ya que un proceso sólo usa para reemplazo los marcos que tiene asignados. La principal desventaja de esta alternativa es que no se adapta a las diferentes necesidades de memoria de un proceso a lo largo de su ejecución. Una característica positiva es que el comportamiento del proceso es relativamente predecible.
Existen diferentes criterios para repartir los marcos de las páginas entre los procesos existentes. Puede depender de múltiples factores tales como el tamaño del proceso o su prioridad. Por otra parte, cuando se usa una estrategia de asignación fija, el sistema operativo determina cuál es el número máximo de marcos asignados al proceso. Sin embargo, la arquitectura de la máquina establece el número mínimo de marcos que deben asignarse a un proceso.
Por ejemplo, si la ejecución de una instrucción puede generar seis fallos de página y el sistema operativo asigna cinco marcos de página a un proceso que incluya esta instrucción, el proceso podría no terminar de ejecutar esta instrucción. Por tanto, el número mínimo de marcos de página para una determinada arquitectura quedará fijado por la instrucción que pueda generar el máximo número de fallos de página.

Asignación dinámica.
El número de marcos asignados a un proceso varía según las necesidades que tenga el proceso (y posiblemente el resto de procesos del sistema) en diferentes instantes de tiempo. Con este tipo de asignación se pueden usar tanto estrategias de reemplazo locales como globales.
• Con reemplazo local, el proceso va aumentando o disminuyendo su conjunto residente dependiendo de sus necesidades en las distintas fases de ejecución del programa.
• Con reemplazo global, los procesos compiten en el uso de la memoria quitándose entre sí las páginas.
La estrategia de reemplazo global hace que el comportamiento del proceso en ejecución sea difícilmente predecible. El principal problema de este tipo asignación es que la tasa de fallos de página de un programa puede depender de las características de los otros procesos que estén activos en el sistema.

Hiperpaginación.
Si el número de marcos de página asignados a un proceso no es suficiente para almacenar las páginas referenciadas activamente por el mismo, se producirá un número elevado de fallos de página. A esta situación se le denomina hiperpaginación (thrashing). Cuando se produce la hiperpaginación, el proceso pasa más tiempo en la cola de servicio del dispositivo de paginación que ejecutando. Dependiendo del tipo de asignación utilizado, este problema puede afectar a procesos individuales o a todo el sistema.
En un sistema operativo que utiliza una estrategia de asignación fija, si el número de marcos asignados al proceso no es suficiente para albergar su conjunto de trabajo en una determinada fase de su ejecución, se producirá hiperpaginación en ese proceso. Esto traerá consigo un aumento considerable de su tiempo de ejecución, pero, sin embargo, el resto de los procesos del sistema no se ven afectados directamente.
Con una estrategia de asignación dinámica, el número de marcos asignados a un proceso se va adaptando a sus necesidades, por lo que, en principio, no debería presentarse este problema. Sin embargo, si el número de marcos de página existentes en el sistema no son suficientes para almacenar los conjuntos de trabajo de todos los procesos, se producirán fallos de página frecuentes y, por tanto, el sistema sufrirá hiperpaginación. La utilización del procesador disminuirá, puesto que aumenta el tiempo que dedica al tratamiento de fallos de página.
Estrategia del conjunto de trabajo.
Como se comentó previamente, cuando un proceso tiene residente en memoria su conjunto de trabajo, se produce una baja tasa de fallos de página. Una posible estrategia consiste en determinar los conjuntos de trabajo de todos los procesos activos para intentar mantenerlos residentes en memoria principal.
Para poder determinar el conjunto de trabajo de un proceso es necesario dar una definición más formal de este término. El conjunto de trabajo de un proceso es el conjunto de páginas accedidas por un proceso en las últimas n referencias. El número n se denomina la ventana del conjunto de trabajo. El valor de n es un factor crítico para el funcionamiento efectivo de esta estrategia. Si es demasiado grande, la ventana podría englobar varias fases de ejecución del proceso llevando a una estimación excesiva de las necesidades del proceso. Si es demasiado pequeño, la ventana podría no englobar la situación actual del proceso con lo que se generarían demasiados fallos de página.
Suponiendo que el sistema operativo es capaz de detectar cuál es el conjunto de trabajo de cada proceso, se puede especificar una estrategia de asignación dinámica con reemplazo local y control de carga.
• Si el conjunto de trabajo de un proceso decrece, se liberan los marcos asociados a las páginas que ya no están en el conjunto de trabajo.
• Si el conjunto de trabajo de un proceso crece, se asignan marcos para que puedan contener las nuevas páginas que han entrado a formar parte del conjunto de trabajo. Si no hay marcos libres, hay que realizar un control de carga suspendiendo uno o más procesos y liberando sus páginas.
El problema de esta estrategia es cómo poder detectar cuál es el conjunto de trabajo de cada proceso. Al igual que ocurre con el algoritmo LRU, se necesitaría una MMU específica que fuera controlando las páginas accedidas por cada proceso durante las últimas n referencias.

Estrategia de administración basada en la frecuencia de fallos de página.
Esta estrategia busca una solución más directa al problema de la hiperpaginación. Se basa en controlar la frecuencia de fallos de página de cada proceso. se establecen una cuota superior y otra inferior de la frecuencia de fallos de página de un proceso. Basándose en esa idea, a continuación se describe una estrategia de asignación dinámica con reemplazo local y control de carga.

• Si la frecuencia de fallos de un proceso supera el límite superior, se asignan marcos de página adicionales al proceso. Si la tasa de fallos crece por encima del límite y no hay marcos libres, se suspende algún proceso liberando sus páginas.
• Cuando el valor de la tasa de fallos es menor que el límite inferior, se liberan marcos asignados al proceso seleccionándolos mediante un algoritmo de reemplazo.

Estrategia de control de carga para algoritmos de reemplazo globales.
Los algoritmos de reemplazo globales no controlan la hiperpaginación. Necesitan trabajar conjuntamente con un algoritmo de control de carga. A continuación, como ejemplo, se describe la gestión de memoria en el sistema operativo UNIX BSD. El sistema usa la técnica del buffering de páginas, manteniéndose un conjunto de marcos de página libres. Existe un proceso (page daemon) que se despierta periódicamente y comprueba si hay suficientes marcos de página libres. Si no es así, aplica el algoritmo de reemplazo y libera el número necesario de marcos de página.
La estrategia de reemplazo es global y utiliza una modificación del algoritmo de reloj denominada reloj con dos manecillas, puesto que utiliza dos punteros en vez de uno. Cuando se ejecuta el algoritmo de reemplazo, se desactiva el bit de referencia de la página a la que apunta el primer puntero y se comprueba el bit de referencia de la página a la que señala el segundo. Si está desactivado se libera esa página, escribiéndola previamente al disco si está modificada. El algoritmo avanza ambos punteros y repite el proceso hasta que se liberan suficientes marcos. Las páginas que están en la lista de páginas libres pueden recuperarse si se referencian antes de ser reutilizadas.
Cuando la tasa de paginación en el sistema es demasiado alta y el número de marcos libres está frecuentemente por debajo del mínimo, otro proceso especial (swapper) selecciona uno o más procesos para suspenderlos y liberar sus marcos de página. El swapper comprueba periódicamente si alguno de los procesos expulsados debe reactivarse. La reactivación de los procesos seleccionados sólo se llevará a cabo si hay suficientes marcos de página libres.

Gestión del espacio de swap.
El sistema operativo debe gestionar el espacio de swap reservando y liberando zonas del mismo según evolucione el sistema. Existen básicamente dos alternativas a la hora de asignar espacio de swap durante la creación de una nueva región:
• Preasignación de swap. Cuando se crea la nueva región, se reserva espacio de swap para la misma. Con esta estrategia, cuando se expulsa una página ya tiene reservado espacio en swap para almacenar su contenido.
• Sin preasignación de swap. Cuando se crea una región, no se hace ninguna reserva en el swap. Las páginas de la región se irán trayendo a memoria principal por demanda desde el soporte de la región. Sólo se reserva espacio en el swap para una página cuando es expulsada por primera vez.
La tendencia actual es utilizar la segunda estrategia, dado que la primera conlleva un peor aprovechamiento de la memoria secundaria, puesto que toda página debe tener reservado espacio en ella. Sin embargo, la preasignación presenta la ventaja de que con ella se detecta anticipadamente cuándo no hay espacio en swap. Si al crear un proceso no hay espacio en swap, éste no se crea. Con un esquema sin preasignación, esta situación se detecta cuando se va a expulsar una página y no hay sitio para ella. En ese momento, habría que abortar el proceso, aunque ya había realizado parte de su labor.

Operaciones sobre las regiones de un proceso.
A continuación se analiza cómo se realizan las diversas operaciones sobre las regiones en un sistema con memoria virtual.
Creación de una región.
Cuando se crea una región, no se le asigna memoria principal puesto que se cargará por demanda Todas las páginas de la región se marcan como no residentes, o sea, inválidas pero válidas para el sistema operativo. De esta forma, el primer acceso causará un fallo de página. El sistema operativo actualiza la tabla de regiones para reflejar la existencia de la nueva región y guarda la información de las características de las páginas de la región rellenando las entradas de la tabla de páginas de acuerdo a las mismas. Algunas de estas características son relevantes a la MMU, como por ejemplo la protección. Sin embargo, otras sólo le conciernen al sistema operativo, como por ejemplo si las páginas de la región son privadas o compartidas.
Las páginas de una región con soporte en un archivo (p. ej.: las de código o as correspondientes a la región de datos con valor inicial) se marcan para indicar esta situación (bit de cargar de archivo), almacenándose también la dirección del bloque correspondiente del archivo. Las páginas sin soporte (p. ej.: las páginas correspondientes a la región de datos sin valor inicial) se marcan con un valor especial que indica que hay que rellenarlas a cero (bit de rellenar con ceros). Observe que un fallo sobre una página de este tipo no provocaría una operación de entrada/salida al disco. Si en el sistema hay preasignación de swap y se trata de una región privada, hay que reservar en el momento de la creación la zona correspondiente del swap.

Una vez creada una región, el tratamiento que se le da a la página cuando se expulsa y está modificada va a depender de si es privada o compartida:
• Si la región es privada, se escribe en el swap. En el caso de un sistema sin preasignación, será necesario reservar espacio en swap cuando se expulsa por primera vez.
• Si la región es compartida, se escribe directamente en el soporte para que todos los procesos puedan ver las modificaciones.

Liberación de una región.
Cuando se libera una región, se debe actualizar la tabla de regiones para reflejar este cambio. Las páginas asociadas a la región hay que marcarlas como inválidas tanto para la MMU como para el sistema operativo. Además, si se trata de una región privada, se libera el espacio de swap asociada a la misma.
La liberación puede deberse a una solicitud explícita (como ocurre cuando se desproyecta un archivo) o a la finalización del proceso que conlleva la liberación de todas sus regiones. Observe que en POSIX, el servicio exec también produce una liberación del mapa de un proceso.

Cambio del tamaño de una región.

Con respecto a una disminución de tamaño en una región, esta operación implica una serie de acciones similares a la liberación, pero que sólo afectan a la zona liberada. Por lo que se refiere a un aumento de tamaño, hay que comprobar que la región no se solapa con otra región y establecer las nuevas páginas como no residentes y con las mismas características que el resto de las páginas de la región.
En el caso de una expansión del heap, se marcan las nuevas páginas como de lectura y escritura, de carácter privado y a rellenar con ceros.
El tratamiento de la expansión de la pila es algo más complejo, ya que no proviene de una solicitud del proceso, sino de la propia evolución de la pila. Observe que, cuando se produce una expansión de pila, se genera un fallo de página asociado a una dirección que se corresponde con un hueco. El sistema operativo podría pensar, en principio, que se trata de un acceso erróneo. Para diferenciarlo, debe comparar la dirección que causó el fallo con el puntero de pila. Si la dirección es mayor, está dentro de la pila. Se trata de una expansión de la pila, que implica marcar adecuadamente las páginas involucradas en la expansión. En caso contrario, se trata de un acceso erróneo.

Duplicado de una región.
Esta operación está asociada al servicio fork de POSIX y no se requiere en sistemas operativos que tengan un modelo de creación de procesos más convencional.
Cuando se produce una llamada a este servicio, se debe crear un nuevo proceso que sea un duplicado del proceso que la invoca. Ambos procesos compartirán las regiones de carácter compartid@ que hay en el mapa del proceso original (como, por ejemplo, las regiones de código, los archivos proyectados o las zonas de memoria compartida). Sin embargo, las regiones de carácter privado (como, por ejemplo, las regiones de datos con valor inicial, de datos sin valor inicial, la región de heap y la pila) deben ser un duplicado de las regiones originales. Esta operación de duplicado es costosa, ya que implica crear una nueva región y copiar su contenido desde la región original.
Dado que este servicio se usa muy frecuentemente en los sistema UNIX y que, en la mayoría de los casos, el nuevo mapa apenas se utiliza ya que el proceso hijo realiza una llamada exec que lo destruye, la mayoría de las versiones de UNIX han optimizado esta operación de duplicado usando la técnica del copy-on-write (COW).

Gracias Por Su Atención Prestada.
Full transcript