ÍNDICE

Los métodos de administración de la memoria principal, que no utilizan Memoria Virtual y esquemas de Paginación y Segmentación, es decir que llevan a las direcciones directamente al bus de la memoria, tienen un inconveniente: producen lo que se denomina fragmentación.

La fragmentación, que son huecos en la memoria que no pueden usarse debido a lo pequeño de su espacio, provoca un desperdicio de memoria principal.

Una posible solución para la fragmentación externa es permitir que espacio de direcciones lógicas lleve a cabo un proceso en direcciones no contiguas, así permitiendo al proceso ubicarse en cualquier espacio de memoria física que esté disponible, aunque esté dividida. Una forma de implementar esta solución es a través del uso de un esquema de paginación. La paginación evita el considerable problema de ajustar los pedazos de memoria de tamaños variables que han sufrido los esquemas de manejo de memoria anteriores. Dado a sus ventajas sobre los métodos previos, la paginación, en sus diversas formas, es usada en muchos sistemas operativos.

Al utilizar la memoria virtual, las direcciones no pasan en forma directa al bus de memoria, sino que van a una unidad administradora de la memoria (MMU –Memory Management Unit). Estas direcciones generadas por los programas se llaman direcciones virtuales y conforman el hueco de direcciones virtuales. Este hueco se divide en unidades llamadas páginas. Las unidades correspondientes en la memoria física se llaman marcos para página o frames. Las páginas y los marcos tienen siempre el mismo tamaño.

Comparando la paginación y segmentación simple por un lado, con la partición estática y dinámica por el otro, se establecen las bases para un avance fundamental en la gestión de memoria, y es que:

· Se puede cargar y descargar un proceso de la memoria principal de tal forma que ocupe regiones diferentes de la memoria principal en momentos distintos a lo largo de su ejecución.

· Un proceso puede dividirse en varias partes (páginas o segmentos) y no es necesario que estas partes se encuentren contiguas en la memoria principal.

Si estas dos características están presentes, no será necesario que todas las páginas o todos los segmentos de un proceso estén en la memoria durante la ejecución.

El término fragmento hace referencia tanto a páginas como a segmentos, dependiendo de si se emplea paginación o segmentación. Supóngase que se trae un proceso a la memoria en un momento dado, el S.O comienza trayendo sólo unos pocos fragmentos, incluido el fragmento que contiene el comienzo del programa.

Se llamará conjunto residente del proceso a la parte que está realmente en la memoria principal.

Si el procesador encuentra una dirección lógica que no está en la memoria principal, genera una interrupción que indica un fallo de acceso a la memoria. El S.O pone al proceso interrumpido en estado Bloqueado y toma el control. Para que la ejecución de este proceso siga más tarde, el S.O necesita traer a la memoria principal el fragmento del proceso que contiene la dirección. Para ello se emite una solicitud de Lectura de E/S al disco; luego se expide otro proceso para que se ejecute mientras se realiza la operación.

Una vez que el fragmento deseado se ha traído a la memoria principal y se ha emitido la interrupción de E/S, se devuelve el control al S.O, que coloca el proceso afectado en el estado de Listo.

MEMORIA VIRTUAL

La memoria virtual es una técnica para proporcionar la simulación de un espacio de memoria mucho mayor que la memoria física de una máquina. Esta "ilusión" permite que los programas se hagan sin tener en cuenta el tamaño exacto de la memoria física.

La ilusión de la memoria virtual está soportada por el mecanismo de traducción de memoria, junto con una gran cantidad de almacenamiento rápido en disco duro. Así en cualquier momento el espacio de direcciones virtual hace un seguimiento de tal forma que una pequeña parte de él, está en memoria real y el resto almacenado en el disco, y puede ser referenciado fácilmente.

Debido a que sólo la parte de memoria virtual que está almacenada en la memoria principal, es accesible a la CPU, según un programa va ejecutándose, la proximidad de referencias a memoria cambia, necesitando que algunas partes de la memoria virtual se traigan a la memoria principal desde el disco, mientras que otras ya ejecutadas, se pueden volver a depositar en el disco (archivos de paginación).

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 sólo se tienen unos pocos fragmentos de un proceso dado, se pueden mantener más procesos en la memoria. Es más, se ahorra tiempo, porque los fragmentos que no se usan no se cargan ni se descargan de la memoria. Sin embargo, el S.O debe saber cómo gestionar este esquema.

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.

En un estado estable, prácticamente toda la memoria principal estará ocupada con fragmentos de procesos, por lo que el procesador y el S.O tendrán acceso directo a la mayor cantidad de procesos posibles, y cuando el S.O traiga a la memoria un fragmento, deberá expulsar otro. Si expulsa un fragmento justo antes de ser usado, tendrá que traer de nuevo el fragmento de manera casi inmediata. Demasiados intercambios de fragmentos conducen a lo que se conoce como hiperpaginación: donde el procesador consume más tiempo intercambiando fragmentos que ejecutando instrucciones de usuario. Para evitarlo el S.O intenta adivinar, en función de la historia reciente, qué fragmentos se usarán con menor probabilidad en un futuro próximo.

Los argumentos anteriores se basan en el principio de cercanía o principio de localidad que afirma que las referencias a los datos y el programa dentro de un proceso tienden a agruparse. Por lo tanto, es válida la suposición de que, durante cortos períodos de tiempo, se necesitarán sólo unos pocos fragmentos de un proceso.

Una manera de confirmar el principio de cercanía es considerar el rendimiento de un proceso en un entorno de memoria virtual.

El principio de cercanía sugiere que los esquemas de memoria virtual pueden funcionar. Para que la memoria virtual sea práctica y efectiva, se necesitan dos ingredientes. Primero, tiene que existir un soporte de hardware y, en segundo lugar, el S.O debe incluir un software para gestionar el movimiento de páginas o segmentos entre memoria secundaria y memoria principal.

Justo después de obtener la dirección física y antes de consultar el dato en memoria principal se busca en memoria-cache, si esta entre los datos recientemente usados la búsqueda tendrá éxito, pero si falla, la memoria virtual consulta memoria principal , ó, en el peor de los casos se consulta de disco (swapping).

Memoria Virtual = Memoria Física + Area de Swapping en Disco

PAGINACION

El término 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 páginas y cuando carga todas sus páginas en la memoria principal, se crea y carga en la memoria principal una tabla de páginas. Cada entrada de la tabla de páginas contiene el número de marco de la página correspondiente en la memoria principal. Puesto que sólo 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 página correspondiente está presente (P) en la memoria principal o no. Si el bit indica que la página está en la memoria, la entrada incluye también el número de marco para esa página.

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

Estructura de la tabla de páginas

El mecanismo básico de lectura de una palabra de la memoria supone la traducción por medio de la tabla de páginas de una dirección virtual o lógica, formada por un número de página y un desplazamiento, a una dirección física que está formada por un número de marco y un desplazamiento.

Con la memoria virtual, la CPU produce direcciones virtuales que son traducidas por una combinación de hardware y software a direcciones físicas, pues pueden ser utilizadas para acceder a memoria principal. Este proceso se denomina correspondencia de memoria o traducción de direcciones. Actualmente los dos niveles de la jerarquía de memoria controlados por la memoria virtual son las DRAM y los Discos magnéticos.

Puesto que la tabla de páginas es de longitud variable, en función del tamaño del proceso, no es posible suponer que quepa en los registros.

Traducción de direcciones en un sistema de paginación

La figura anterior sugiere una implementación en hardware de este esquema. Cuando se está ejecutando un proceso en particular, la dirección de comienzo de la tabla de páginas para este proceso se mantiene en un registro. El número de página de la dirección virtual se emplea como índice en esta tabla para buscar el número de marco correspondiente. Este se combina con la parte de desplazamiento de la dirección virtual para generar la dirección real deseada.

La mayoría de los esquemas de memoria virtual almacenan las tablas de páginas en la memoria virtual en vez de en la memoria real. Esto significa que estas tablas de páginas están también sujetas a paginación, de la misma forma que las otras páginas.

Cuando un proceso se está ejecutando, al menos una parte de su tabla de páginas debe estar en la memoria principal, incluyendo la entrada de la tabla de páginas para la página actualmente en ejecución. Algunos procesadores usan un esquema de dos niveles para organizar grandes tablas de páginas, donde hay un directorio de páginas en el que cada entrada señala a una tabla de páginas. Así pues, si la longitud del directorio de páginas es X, y la longitud máxima de una tabla de páginas es Y, un proceso puede estar formado por hasta X x Y páginas. Normalmente, la longitud máxima de una tabla de páginas está limitada a una página. Por ejemplo, el procesador Pentium utiliza este método.

Un enfoque alternativo al uso de tablas de páginas de uno o dos niveles es el uso de una estructura de tabla de páginas invertida. Con este método, la parte del número de página de una dirección virtual se traduce a una tabla de dispersión por medio de una función de dispersión simple. La tabla de dispersión contiene un puntero a la tabla de páginas invertida, que contiene a su vez las entradas de la tabla de páginas.

Con esta estructura, hay una entrada en la tabla de dispersión y en la tabla de páginas invertida por cada página de memoria real en lugar de una por cada página virtual. Así pues, se necesita una parte fija de la memoria real para las tablas, sin reparar en el número de procesos o de páginas virtuales soportados. La técnica de dispersión genera normalmente cadenas cortas, de dos a tres entradas cada una.

Buffer de traducción adelantada

Cada referencia a la memoria virtual puede generar dos accesos a la memoria: uno para obtener la entrada de la tabla de páginas correspondientes y otro para obtener el dato deseado.

Un esquema sencillo de memoria virtual podría tener el efecto de doblar el tiempo de acceso a la memoria. Para solucionar este problema, la mayoría de los esquemas de memoria virtual hacen uso de una cache especial para las entradas de la tabla de páginas, llamada generalmente buffer de traducción adelantada (TLB,Translation Lookaside Buffer) que contiene aquellas entradas de la tabla de páginas usadas hace menos tiempo.

La organización de hardware de paginación resultante se muestra en la figura siguiente.

Dada una dirección virtual, el procesador examinará primero la TLB. Si la entrada de la tabla de páginas buscada está presente se obtiene el número de marco y se forma la dirección real. Si no se encuentra, el procesador emplea el número de página como índice para buscar en la tabla de páginas del proceso y examinar la entrada correspondiente de la tabla de páginas. Si no se encuentra activo el bit de presencia, es que la página está en la memoria principal y el procesador puede obtener el número de marco de la entrada de la tabla de páginas para formar la dirección real. El procesador, además, actualiza la TLB para incluir esta nueva entrada de la tabla de páginas. Si el bit de presencia no está activo, es que la página buscada no está en la memoria principal y se produce un fallo en el acceso a la memoria, llamado fallo de página.

Existe una serie de detalles adicionales sobre la organización real de la TLB. Puesto que la TLB contiene sólo algunas de las entradas de la tabla de páginas completa, no se puede indexar simplemente la TLB por el número de páginas. Cada entrada debe incluir el número de página, además de la entrada completa a la tabla de páginas. El procesador estará equipado con un hardware que permita consultar simultáneamente varias entradas de la TLB para determinar si hay coincidencia en el número de página. Esta técnica se denomina correspondencia asociativa y contrasta con la correspondencia directa, que se emplea para buscar en la tabla de páginas de la figura de Búsqueda directa y asociativa. El diseñador de la TLB también debe considerar la forma en que se organiza las entradas en la TLB y que entrada reemplazar cuando se introduce una nueva.

ESQUEMA DE CORRESPONDENCIA DIRECTA

Dirección virtual

37          502

                37

.

.

.

.

.

.

.

.

.

nª pág.      Desplazam.

nº marco Desplaza-

miento

Dirección real

Tabla de páginas

5 502

ESQUEMA DE CORRESPONDENCIA ASOCIATIVA

Dirección virtual

37 502

nª pág. Desplazam.

nº pág. Entrada a PTE

nº marco Desplaza-

miento

Dirección real

Buffer de traducción adelantada

Por último, el mecanismo de la memoria virtual debe interactuar con el sistema de cache de la memoria principal. La de traducción con buffer ilustra esta interacción. Una dirección virtual estará formada por el número de página más el desplazamiento. Una vez que se ha generado la dirección real, que está en forma de etiqueta(formada por los bits más significativos de la dirección real) y un resto, se consulta la cache para ver si está presente el bloque que contiene dicha palabra. Si lo está, es devuelto a la CPU. Si no, se toma la palabra de la memoria principal.

Tamaño de Página

Hay varios factores que considerar. Uno es la fragmentación interna. Sin duda, cuanto menor sea el tamaño de página, menor será la cantidad de fragmentación interna. Para optimizar el uso de la memoria principal, es positivo reducir la fragmentación interna. Por otro lado, cuanto menor sea la página, mayor será el número de páginas que se necesitan por proceso. Un número mayor de páginas por proceso significa que las tablas de páginas que se necesitan por proceso serán mayores. Así pues, pueden suceder dos fallos de página para una única referencia a la memoria: primero, para traer la parte necesaria de la tabla de páginas y, segundo, para traer la página del proceso.

Se puede considerar el efecto que tiene el tamaño de página en el porcentaje de fallos de página y se basa en el principio de cercanía. Si el tamaño de página es muy pequeño, normalmente estarán disponibles en la memoria principal un gran número de páginas para cada proceso. Después de un tiempo, todas las páginas de la memoria contendrán parte de las referencias más recientes del proceso y la tasa de fallos de página será menor. Cuando de incrementa el tamaño de la página, cada página individual contendrá posiciones cada vez más distantes de cualquier referencia reciente; se atenúa el efecto de principio de cercanía y comienza a aumentar la tasa de fallos de página, que comenzará a bajar cuando, finalmente, el tamaño de página se aproxime al tamaño de todo el proceso. Cuando una sola página abarca todo el proceso, no hay fallos de página.

Una dificultad más es que la tasa de fallos de página viene determinada también por el número de marcos asignados a un proceso. Por último el diseño del tamaño de página está relacionado con el tamaño de la memoria física principal. Al mismo tiempo que la memoria principal se hace mayor, el espacio de direcciones que emplean las aplicaciones también crece. Esta tendencia es más evidente en las computadoras personales y estaciones de trabajo, donde las aplicaciones se hacen cada vez más complejas.

SEGMENTACION

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 (número 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 cuán 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 compartició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á asignar los permisos de acceso de la forma adecuada.

Organización

En el estudio de la segmentación simple, se llegó 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 necesitará al hablar de un esquema de memoria virtual basado en la segmentación donde las entradas de la tabla de segmentos pasan a ser más complejas. Puesto que sólo 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 está presente en la memoria principal. Si el bit indica que el segmento está 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 cargó 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.

Traducción de direcciones en un sistema con segmentación

PAGINACION Y SEGMENTACION COMBINADAS

Tanto la paginación como la segmentación tienen sus ventajas. La paginación elimina la fragmentación externa y de este modo, aprovecha la memoria principal de forma eficiente. Además, puesto que los fragmentos que se cargan y descargan de la memoria principal son de tamaño fijo e iguales, es posible construir algoritmos se gestión de memoria sofisticados que aprovechen mejor el comportamiento de los programas. La segmentación tiene las ventajas antes citadas, incluida la capacitación de gestionar estructuras de datos que puedan crecer, la modularidad y el soporte de la compartición y la protección. Para combinar las ventajas de ambas, algunos sistemas están equipados con hardware del procesador y software del S.O.

En un sistema con paginación y segmentación combinadas, el espacio de direcciones de un usuario se divide en varios segmentos según el criterio del programador. Cada segmento se vuelve a dividir en varias páginas de tamaño fijo, que tienen la misma longitud que un marco de memoria principal. Si el segmento tiene menor longitud que la página, el segmento ocupará sólo una página. Desde el punto de vista del programador, una dirección lógica todavía está formada por un número de segmento y un desplazamiento en el segmento. Desde el punto de vista de sistema, el desplazamiento del segmento se ve como un número de página dentro del segmento y un desplazamiento dentro de la página.

La entrada de la tabla de segmentos contiene la longitud del segmento. Los bits de presencia y modificación no son necesarios, puesto que estos elementos se gestionan en la página. Pueden usarse otros bits de control para comparición y protección. La entrada de la tabla de páginas es, la misma que se usa en un sistema de paginación pura. Cada número de página se convierte en el número de marco correspondiente si la página está presente en la memoria. El bit de modificación indica si se necesita escribir la página en el disco cuando se asigna el marco a otra página.

Marco

de

página

Dirección virtual

Programa Mecanismo de Mecanismo de Memoria Principal

segmentación paginación

-Traducción de direcciones en un sistema con segmentación y paginación-

PROTECCION Y COMPARTIMIENTO

Un proceso de usuario sólo puede acceder memoria localizada en su espacio de direccionamiento virtual y un espacio de memoria compartido para sus procesos-hijo.

    Habilidad de separar completamente las tareas, al poder dar a cada tarea un espacio de direcciones virtuales diferentes. Esto se hace dando un mapa de traducción de direcciones virtuales diferente a cada tarea.
    Los otros mecanismos funcionan dentro de una tarea: para proteger al propio sistema operativo de la intrusión por parte de esa tarea, y al uso de registros especiales del procesador e instrucciones reservadas únicamente al sistema operativo.
    Sólo un proceso kernel puede controlar y acceder cualquier espacio de direccionamiento.

Además la segmentación se presta a la implementación de políticas de protección, puesto que cada entrada de la tabla de segmentos incluye la longitud, además de la dirección base, un programa no podrá acceder por descuido a una posición de la memoria principal más allá de los límites de un segmento.

Para conseguir la compartición, es posible que un segmento se referencia desde las tablas de segmentos de más de un proceso. Este mismo mecanismo es válido en un sistema de paginación.

Se pueden ofrecer también mecanismos más sofisticados. Un esquema habitual consiste en usar una estructura de anillo de protección donde los anillos interiores gozan de mayores privilegios que los anillos externos. Normalmente, el anillo 0 está reservado para las funciones del núcleo del S.O y las aplicaciones están situadas a un nivel más alto. Algunos servicios del S.O pueden ocupar un anillo intermedio. Los principios básicos del sistema de anillos son los siguientes:

1. Un programa puede acceder sólo a datos que estén en el mismo anillo o en un anillo de menor privilegio.

2. Un programa puede hacer llamadas a servicios que residan en el mismo anillo o en anillos más privilegiados.

SOFTWARE DEL SISTEMA OPERATIVO

El diseño del gestor de memoria en un sistema operativo depende de tres áreas fundamentales de decisión:

v Si se emplean o no técnicas de memoria virtual.

v El uso de paginación, segmentación o ambas.

v Los algoritmos empleados para los problemas de la gestión de memoria.

Las decisiones tomadas en las dos primeras áreas dependen de la plataforma de hardware disponible. Las decisiones del tercer punto (los algoritmos) son del dominio del software del S.O.. En las políticas, elementos claves de diseño, que luego se desarrollarán, el punto clave es el rendimiento: se busca minimizar el porcentaje de fallos de página. Los fallos de página originan una considerable sobrecarga en el software. Como mínimo, la sobrecarga incluye la decisión que el S.O. debe tomar sobre las páginas residentes o páginas que se deben reemplazar y la E/S de intercambiar páginas. Además, el S.O. debe planificar la ejecución de otro proceso durante el intercambio de página, dando lugar a un cambio de proceso.

Los elementos clave del diseño son los desarrollados a continuación:

POLÍTICAS DE LECTURA (FETCH)

Es la que está relacionada con la decisión de cuándo se debe cargar una página en la memoria principal. Las dos alternativas más comunes son:

Ø Paginación por demanda: Se trae una página a la memoria principal sólo cuando se hace referencia a una posición en dicha página.

Ø Paginación previa: Se cargan otras páginas distintas a las demandadas debido a un fallo de página.

Esta política no es efectiva si la mayoría de las páginas extra que se traen no se referencian.

La utilidad no ha sido demostrada.

POLÍTICAS DE UBICACIÓN

Tiene que ver con determinar dónde va ha residir una parte de un proceso en la memoria principal. Es un aspecto importante del diseño en un sistema puro de segmentación.

Como posibles alternativas se tiene:

Ø Políticas del mejor ajuste.

Ø Políticas del primer ajuste

Ø Y otras.

Sin embargo, para un sistema que usa tanto paginación pura como paginación combinada con segmentación, la ubicación carece de importancia puesto que el hardware de traducción de direcciones y el hardware de acceso a la memoria principal pueden desarrollar sus funciones en cualquier combinación de marco de página con idéntica eficiencia.

POLÍTICAS DE REEMPLAZO

Trata de la selección de la página a reemplazar en la memoria principal cuando se debe cargar una nueva página. Esto resulta difícil de explicar por lo que se debe tener en cuenta algunos conceptos interrelacionados como ser:

Ø El numero de marcos de página a asignar a cada proceso activo.

Ø Si el conjunto de páginas a considerar para el reemplazo debe limitarse a las del proceso que provocó el fallo de página o abarcar todos los marcos de página situados en la memoria principal.

Ø De entre el conjunto de páginas consideradas, cuál es la página específica que debe elegirse para el reemplazo.

MEMORIA PRINCIPAL

MEMORIA SECUNDARIA

- X6 FUE EL MARCO ELEGIDO PARA REALIZAR EL REEMPLAZO DE PÁGINAS. SE ELIMINA LA PÁGINA QUE NO SE ESTA USANDO Y SE TRAE A MEMORIA PRINCIPAL LA PÁGINA QUE EL SISTEMA OPERATIVO NECESITA.

La Política de Reemplazo se encarga de seleccionar la página a reemplazar de entre las que están actualmente en la memoria, cuando todos los marcos de memoria principal están ocupados y es necesario traer una nueva página para atender a un fallo de página.

Todas las políticas tienen como objetivo que la página a reemplazar sea la que tenga una menor posibilidad de ser referenciada en un futuro cercano. Debido al principio de cercanía, hay una alta correlación entre la historia de referencias recientes y las pautas de futuras referencias.

Es necesario tener en cuenta una restricción de la política de reemplazo: algunos de los marcos de la memoria principal pueden estar bloqueados; si es así, la página cargada actualmente en ese marco no puede ser reemplazada. En los marcos bloqueados se albergan: la mayoría del núcleo del S.O. y las estructuras clave de control. El bloqueo se consigue asignando un bit de bloqueo a cada marco, este bit puede guardarse en una tabla de marcos o estar en la tabla de página actual.

Algoritmos básicos

Los algoritmos que se emplean para seleccionar una página a reemplazar son las siguientes:

§ Óptima: selecciona para reemplazar la página que tiene que esperar más tiempo hasta que se produzca la referencia siguiente. Esta política genera el menor número de fallos de página. Este algoritmo resulta imposible de implementar ya que requiere que el S. O. Tenga un conocimiento exacto de los sucesos futuros.

· Algoritmo de reemplazo de páginas según el uso no tan reciente:

Este algoritmo hace uso de los dos bits de estado que están asociados a cada página. Estos bits son: R, el cual se activa cuando se hace referencia (lectura / escritura) a la página asociada; y M, que se activa cuando la página asociada es modificada (escritura). Estos bits deben de ser actualizado cada vez que se haga referencia a la memoria, por esto es de suma importancia que sean activados por el hardware. Una vez activado el bit, permanece en ese estado hasta que el sistema operativo, mediante software, modifica su estado.

Estos bits pueden ser utilizados para desarrollar un algoritmo de reemplazo que cuando inicie el proceso, el sistema operativo asigne un valor de 0 a ambos bits en todas las páginas. En cada interrupción de reloj, limpie el bit R para distinguir cuáles páginas tuvieron referencia y cuáles no.

Cuando ocurre un fallo de página, el sistema operativo revisa ambos bits en todas las páginas y las clasifica de la siguiente manera:

- Clase 0: La página no ha sido referenciada, ni modificada.

- Clase 1: La página no ha sido referenciada, pero ha sido modificada.

- Clase 2: La página ha sido referenciada, pero no ha sido modificada.

- Clase 3: La página ha sido referenciada y también modificada.

Estrategia: Sustituir primero celdas tipo 0 (mejor opción), ó tipo 1 (lento) pero grabando celda de salida, ó tipo 2 (posible hiperpaginación), ó tipo 3 (peor) pero grabando celda de salida.

Una vez obtenida la clasificación, elimina una página de manera aleatoria de la primera clase no vacía con el número más pequeño. Esto porque para el algoritmo es mejor eliminar una página modificada sin referencias en al menos un intervalo de reloj, que una página en blanco de uso frecuente.

A pesar de que este algoritmo no es el óptimo, es fácil de implementar y de comprender y con mucha frecuencia es el más adecuado.

§ Usada menos recientemente (LRU, Last Recently Used): reemplaza la página de memoria que no ha sido referenciada desde hace más tiempo. Debido al principio de cercanía esta debería ser la página con menor probabilidad de ser referenciada en un futuro cercano. El problema de este método es su dificultad de implementación. Una solución sería etiquetar cada página con el momento de su última referencia; tanto para instrucciones como datos. Este esquema produce sobrecarga.

§ Primera en entrar, primera en salir (FIFO, First In First Out): trata los marcos asignados a un proceso como un buffer circular y las páginas se suprimen de la memoria según la técnica de Round-Robin. Lo que se necesita es un puntero que circule a través de los marcos del proceso. Esta es una de las políticas de reemplazo más sencillas de implementar. Se reemplaza la página que a estado más tiempo en la memoria, teniendo como desventaja que habrá regiones del programa o de datos que son muy usadas a lo largo de la vida de un programa por lo cual estas páginas se cargarán y expulsarán repetidas veces.

§ Reloj (Clock): requiere asociar un bit adicional a cada marco, denominado ‘bit de uso’. Cuando se carga una página por primera vez el bit de uso se pone a cero. Cuando se hace referencia a la página posteriormente, el bit de uso se pone a uno. Para el algoritmo de reemplazo de páginas, el conjunto de marcos candidatos a ser reemplazados se considera como un buffer circular con un puntero asociado. Al reemplazar una página, se hace que el puntero señale a la primer puntero del buffer. Cuando llega el momento de reemplazar una página, el S.O. recorre el buffer buscando un marco con el bit de uso a cero. Cada vez que se encuentra un marco con el bit de uso a uno, lo pone a cero. Si algún marco del buffer tiene el bit de uso a cero, al comienzo de la búsqueda, se elige para reemplazar el primero que se haya encontrado. Si todo los marcos tienen el bit de uso a uno, el puntero dará una vuelta completa al buffer, poniendo todos los bits a cero y se detendrá en la posición inicial, reemplazando la página de dicho marco.

Almacenamiento intermedio de páginas

El coste de reemplazar una página que ha sido modificada es mayor que el de una que no lo ha sido, porque las páginas modificadas deben volver a escribirse en la memoria secundaria.

Una solución representativa es la del VAX/VMS. El algoritmo de reemplazo es simplemente un FIFO. Para mejorar el rendimiento, no se pierde la pista de la página reemplazada, sino que se asigna a una de las dos listas siguientes:

- la lista de páginas libres (si no ha sido modificada), o,

- la lista de páginas modificadas (si lo ha sido).

Pero la página no se mueve físicamente de la memoria principal, sino que se suprime su entrada en la tabla de páginas y se pone en la lista de páginas libres o modificadas.

Así, si la página que fue agregada a una de las listas (permanente en la memoria) y si el proceso hace referencia a dicha página, simplemente se devuelve al conjunto residente del proceso con un coste pequeño.

Estas listas de páginas libres y modificadas actúan como una caché de páginas.

La lista de páginas modificadas tiene otra función provechosa: las páginas modificadas son reescritas por bloques, en vez de una a una; esto reduce significativamente el número de operaciones se E/S y por tanto, la cantidad de tiempo de acceso al disco.

Políticas de reemplazo y tamaño de caché

Por ser el tamaño de la memoria cada vez más grande, y la cercanía en las aplicaciones cada vez menor; se busca compensar haciendo más grande el tamaño de las caches.

Con una caché grande, el reemplazo de páginas de memoria virtual puede tener un gran impacto en el rendimiento. Si el marco seleccionado para reemplazar se encuentra en la caché, entonces se pierde el bloque de caché, así como la página que contiene.

Una estrategia cuidadosa de reemplazo de páginas puede dar como resultado de un 10 a un 20% menos de fallos de caché que la ubicación arbitraria, utilizando una política de ubicación de páginas en el buffer de páginas.

GESTION DEL CONJUNTO RESIDENTE

Tamaño del conjunto residente

Con memoria virtual paginada no es necesario y, puede no ser posible, traer todas las páginas de un proceso a la memoria principal para preparar su ejecución. El sistema operativo debe decidir cuantas paginas traer, es decir, cuanta memoria principal asignar a un proceso. Aquí entran en juego varios factores:

· Cuanto menor es la cantidad de memoria asignada a un proceso, mayor es el número de procesos que pueden estar en la memoria principal. Esto aumenta la probabilidad de que el sistema operativo encuentre al menos un proceso Listo y, por lo tanto, reduzca el tiempo perdido en el intercambio.

· Si en la memoria principal hay un número relativamente pequeño de paginas de un proceso entonces a pesar del principio de cercanía, el porcentaje de fallos de pagina será algo mayor.

· La asignación de memoria adicional a un proceso en particular no tendrá efectos notables en el porcentaje de fallos de pagina para ese proceso debido al principio de cercanía.

Con estos factores en los sistemas operativos actuales se pueden encontrar con dos tipos de políticas. La política de asignación fija otorga a cada proceso un número fijo de paginas en las que ejecutar. Con una política de asignación fija, cada vez que se produce un fallo de pagina en la ejecución de un proceso, se debe reemplazar una de las paginas de dicho procesador la pagina que se necesite.

La política de asignación variable permite que el núcleo de marcos asignados a un proceso cambie a lo largo de su vida.

La política de asignación variable parece ser la mas potente. La dificultad de este método esta en que requiere que el sistema operativo evalué el compartimiento de los procesos activos.

Alcance del reemplazo

El alcance de una estrategia de reemplazo puede clasificarse en global o local. Un fallo de pagina, producido cuándo no hay marcos libres, es le activador de ambos tipos de políticas. Para seleccionar la pagina a reemplazar, una política de reemplazo local escoge únicamente de entre las paginas residentes del proceso que originó el fallo de pagina. Una política de reemplazo global considera todas las páginas de la memoria como candidatas para reemplazar, independientemente del proceso particular a que pertenezcan.

Reemplazo local

Reemplazo global

Asignación fija

· El número de marcos asignados a un proceso es fijo.

· La pagina a reemplazar se elige de entre los marcos asignados al proceso.

· No es posible.

Asignación variable

· El número de marcos asignados a un proceso puede cambiar de un momento a otro para mantener su conjunto de trabajo.

· La pagina a reemplazar se elige de entre las paginas asignadas al proceso.

· La pagina a reemplazar se elige de entre todos los marcos disponible en la memoria principal; esto hace que cambie el tamaño del conjunto residente de los procesos.

Asignación fija y alcance local

En este caso, se tiene un proceso que se ejecuta en la memoria principal con un número fijo de paginas. Cuando se produce un fallo de pagina, el sistema operativo debe elegir la pagina a reemplazar entre las de dicho proceso que están actualmente en la memoria.

Con una política de asignación fija, es necesario decidir por anticipado la cantidad de memoria asignada a un proceso.

Asignación variable y alcance global

Esta combinación es sencilla de implementar y ha sido adoptada por un buen número de sistemas operativos. En un instante en la memoria principal habrá varios procesos, cada uno de ellos con un cierto número de marcos asignados. El sistema operativo también mantiene una lista de marcos libres. Cuando se produce un fallo de página, se añade un marco libre al conjunto residente del proceso y se carga la pagina.

La dificultad de este método es la elección del reemplazó. Cuando no hay marcos libres, el sistema operativo debe elegir una pagina que este en la memoria para reemplazar. La selección se realiza entre todos los marcos de la memoria excepto los marcos bloqueados.

Asignación variable y alcance local

Es otro método de agnación variable, que intenta superar los problemas de alcance global. La estrategia de asignación variable y alcance local puede resumirse como sigue:

1. cuando se carga un nuevo proceso en la memoria, se le asigna cierto número de marcos en función del tipo de aplicación, las necesidades del programa u otros criterios. La asignación puede cubrirse tanto con paginación previa como con paginación por demanda.

2. cuando se produce un fallo de pagina, se selecciona la pagina a reemplazar de entre las del conjunto residente del proceso que sufre el fallo.

3. de vez en cuando, se vuelve a evaluar la asignación otorgada al proceso y se aumenta o disminuye para mejorar el rendimiento global.

El conjunto de trabajo ha tenido un gran impacto en el diseño de la gestión de la memoria virtual. El conjunto de trabajo de un proceso en un instante virtual t y con parámetro *, denotado por W(t,*), es el conjunto de paginas a las que el proceso ha hecho referencia en las ultimas * unidades de tiempo virtual. Se usa el termino tiempo virtual par indicar el tiempo que transcurre mientras que el proceso está en ejecución.

La variable * es una ventana de tiempo para la observación del proceso. El tamaño del conjunto de trabajo será una función no decreciente del tamaño de la ventana. Los puntos indican unidades de tiempo en las que no cambia el conjunto de trabajo, cuando mayor es el conjunto de trabajo, menos frecuentes son los fallos de página.

Este concepto de conjunto de trabajo puede modificar la siguiente estrategia para el tamaño del conjunto residente:

1. Supervisar el conjunto de trabajo de cada proceso.

2. Eliminar periódicamente del conjunto residente de un proceso aquellas paginas que no pertenezcan a su conjunto de trabajo.

3. Un proceso puede ejecutar si su conjunto de trabajo es en la memoria principal (es decir, si su conjunto residente incluye a su conjunto de trabajo).

Esta estrategia resulta atractiva porque toma un principio reconocido, el principio de cercanía y lo aprovecha para obtener la estrategia de gestión de memoria que permita minimizar los fallos de página. Por desgracia, la estrategia del conjunto de trabajo presenta una serie de problemas.

1. El pasado no siempre predice el futuro. Tanto el tamaño como el contenido del conjunto de trabajo cambiarán con el tiempo.

2. Es impracticable una medida real del conjunto de trabajo para cada proceso. Sería necesario marcar cada referencia de pagina de cada proceso con su tiempo virtual y mantener una cola ordenada entorno de las páginas de cada proceso.

3. El valor óptimo de D es desconocido y, en cualquier caso, puede variar.

El algoritmo de frecuencia de fallo de página (PFF. Page Fault Frequency) sigue esta estrategia. El algoritmo exige que se asocie un bit de uso a cada pagina de la memoria. El bit se pone cuando se accede a la página. Cuando produce un fallo de pagina el sistema operativo anota el tiempo virtual transcurrido desde el ultimo fallo de pagina para ese proceso. Se define un umbral F. Si el tiempo transcurrido desde el ultimo fallo de página es menor que F, entonces una página se añade al conjunto residente del proceso. En otro caso, descartan todas las páginas con bit de uso a 0 y, en consecuencia, se reduce el conjunto residente. Al mismo tiempo, se restauran a 0 el valor del bit de uso en las paginas restantes.

Un método que intenta solucionar el fenómeno de las transiciones entre ubicaciones con una pequeña sobrecarga, es la política de conjunto de trabajo con muestreos en intervalo variables (VSWS, Variable Interval Sampled Working Set). La política VSWS evalúa el conjunto de trabajo de un proceso tomando muestras en función del tiempo virtual transcurrido. Al comienzo de un intervalo de muestreo, se restauran los bit de uso de todas las páginas residentes del proceso durante el intervalo siguiente, descartándose el resto. Así pues, el tamaño del conjunto residente puede disminuir sólo al final de un intervalo.

La política del VSWS está gobernada por los siguientes parámetros:

M: Duración mínima del intervalo de muestreo.

L: Duración máxima del intervalo de muestreo.

Q: Número de fallos de página permitidos entre cada par de muestras.

La política VSWS es la siguiente:

1. Si el tiempo virtual transcurrido desde la última muestra alcanza L, suspende el proceso y explora los bits de uso.

2. Si, antes de que transcurra un tiempo virtual L, se producen Q fallos de página:

a) Si el tiempo virtual desde la última muestra es menor que M, espera hasta que el tiempo virtual transcurrido alcance M para suspender el proceso y explorar los bit de uso.

b) Si el tiempo virtual desde la última muestra es mayor o igual que M, suspende el proceso y explora los bits de uso.

POLÍTICA DE VACIADO

Una política de vaciado es la contraria a una política de lectura: se preocupa de determinar el momento en que hay que escribir en la memoria secundaria una página modificada. Las dos alternativas son el vaciado por demanda y el vaciado previo. Con vaciado por demanda, una pagina se escribirá en la memoria secundaria sólo cuando haya sido elegida para reemplazarse. Una política de vaciado previo escribe las páginas modificadas antes de que se necesiten sus marcos, de forma que las páginas pueden escribirse por lotes.

Existe un peligro si se sigue estrictamente cualquiera de las dos políticas. Con el vaciado previo, una pagina se escribe pero permanece en la memoria principal hasta que el algoritmo de reemplazo de pagina diga que se suprime. El vaciado previo permite escribir las paginas por lotes, pero tiene poco sentido escribir miles de páginas para encontrarse que la mayoría de ellas han sido modificadas antes de ser reemplazadas. La capacidad de transferencia de la memoria secundaria es limitada y no debe malgastarse con operaciones de vaciado innecesarias.

Por otro lado, en el vaciado por demanda, la escritura de una página modificada es anterior a la lectura de una nueva página. Esta técnica puede minimizar las escrituras de paginas, pero hace que un proceso que sufra un fallo de pagina pueda tener que esperar dos transferencias de pagina antes de desbloquearse.

Una solución es incorporar almacenamiento intermedio de paginas, que permite la adopción de la siguiente política: vaciar solo las paginas que es posible reemplazar, pero desconectar las operaciones de vaciado y reemplazo. Con almacenamiento intermedio de páginas reemplazadas pueden situarse en dos listas: modificadas y no modificadas

GESTION DE MEMORIA EN UNIX Y SOLARIS

Las primeras versiones de Unix sólo utilizaban particiones variables sin ningún esquema de memoria virtual., pero en las implementaciones actuales, incluidas SVR4 y Solaris 2.x, utilizan memoria virtual paginada.

En SVR4 y Solaris, tienen dos esquemas de memoria separados. El sistema de paginación ofrece una memoria virtual que asigna marcos de pagina en la memoria principal a los procesos y también asigna marcos de pagina a las memorias intermedias de los bloques de disco.

Un esquema de memoria virtual paginado se adapta peor a la gestión de la asignación de memoria para el núcleo, por lo que se utiliza un asignador de memoria del núcleo.

SISTEMA DE PAGINACIÓN

Estructuras de datos

Para la memoria virtual paginada, UNIX, hace uso de una serie de estructuras de datos que son independientes de la maquina:

v Tabla de páginas: posee una tabla por proceso, con una entrada para cada página de la memoria virtual en proceso.

v Descriptor de bloques de disco: asociado a cada página del proceso hay una entrada en la tabla que describe la copia en el disco de la página virtual.

v Tabla de marcos de página: describe cada marco de la memoria real y está indexada por el número de marco.

v Tabla de uso de intercambios: existe una tabla por cada dispositivo de intercambio.

Reemplazo de páginas

La tabla de marcos de página se utiliza en el reemplazo de páginas, utilizando varios punteros para crear listas dentro de esta tabla.

El algoritmo de reemplazo de paginas utilizado en SVR4 es conocido como algoritmo del reloj de dos agujas, ya que utiliza un bit de referencia para cada pagina de la memoria que reúne los requisitos (no bloqueada) para ser expulsada. Este bit se pone a 0 cuando la página entra por primera vez y a 1 cuando se hace referencia a la pagina para una lectura o escritura. La aguja frontal recorre la lista y pone el bit de referencia a 0, así en algún tiempo la aguja trasera recorre la misma lista y comprueba el bit de referencia. Si el bit está a 1, entonces la página se ha referenciado y se ignora el marco, en cambio, si el bit está todavía 0, entonces la página no se ha referenciado en el intervalo y se pone a estas páginas en una lista para ser reemplazadas.

Dos parámetros determinan la operación del algoritmo:

v Velocidad de recorrido: la velocidad con la que las agujas se mueven a través de la lista de páginas, en páginas por segundo.

v Alcance entre agujas: el espacio entre la aguja frontal y la trasera.

GESTION DE MEMORIA EN LINUX

Linux comparte algunas características de UNIX, pero su esquema de gestión de memoria es bastante complejo (DUBE98).

MEMORIA VIRTUAL DE LINUX

Direccionamiento de memoria virtual

Linux hace uso de una estructura de tabla de páginas con tres niveles:

v Directorio de páginas: un proceso activo tiene sólo un directorio de páginas, donde cada entrada en el mismo, señala a una página del directorio intermedio de páginas. Para un proceso activo, el directorio debe estar en la memoria principal.

v Directorio intermedio de páginas: es el que puede ocupar varias páginas y donde cada entrada al directorio señala a una página de la tabla de páginas.

v Tabla de páginas: ésta también puede ocupar varias páginas y en cada entrada se hace referencia a una página virtual del proceso.

Para utilizar esta estructura de la tabla de páginas a tres niveles, una dirección virtual en Linux se ve como un conjunto de cuatro campos. El campo más a la izquierda (el más significativo) se utiliza como índice en el directorio de páginas; el siguiente se utiliza como índice en el directorio intermedio de páginas; el tercero como índice en la tabla de páginas y el cuarto campo indica el desplazamiento dentro de la página seleccionada de la memoria.

Asignación de páginas

Desde la memoria principal, Linux define un mecanismo para tratar bloques de páginas contiguos correspondientes a bloques de marcos de páginas contiguos, para ello, se utiliza el sistema de colegas donde el núcleo mantiene una lista de grupos de marcos de página contiguos de tamaño fijo.

Algoritmo de reemplazo de páginas

El algoritmo de reemplazo de páginas de Linux se basa en el algoritmo del reloj, que, en caso de ser el sencillo, se asocia un bit de uso y un bit de modificación a cada página de la memoria principal. En Linux utiliza una variable edad que, cada vez que se accede a la página, se incrementa la variable y recorre periódicamente la reserva de paginas globales y disminuye la variable de edad de cada página cuando rota por todas las páginas de la memoria principal. Una página con un envejecimiento 0 es una página “vieja” que no se ha referenciado en bastante tiempo y es la mejor candidata para el reemplazo, y cuanto mayor valor de edad, más frecuentemente se ha usado la página recientemente y menos elegible es para el reemplazo.

GESTION DE MEMORIA EN WINDOWS 2000

El gestor de memoria virtual de Windows 2000 (W2K) controla como se asigna la memoria y como se realiza la paginación.

Mapa de Direcciones Virtuales de W2K

Cada proceso de usuario de W2K dispone de un espacio de direcciones separado de 32 bits, lo que permite 4 Gbytes de memoria por proceso. Por lo que, una parte de esta memoria esta reservada para el sistema operativo y cada usuario tiene 2 Gbytes de espacio de direcciones virtual disponible.

Paginación en W2K

Cuando se crea un proceso en principio puede hacer uso de todo el espacio de usuario de 2 Gbytes. Este espacio se divide en paginas de tamaño fijo, y cualquiera puede cargarse en la memoria principal. En la práctica una página puede estar en uno de estos tres estados:

v Disponible: las páginas no usadas actualmente por este proceso.

v Reservada: un conjunto de paginas contiguas que el gestor de la memoria virtual separa para un proceso pero no cuentan para la cuota de memoria del proceso hasta que se usan.

v Confirmada: paginas para las cuales el gestor de memoria virtual mantiene un conjunto de espacio separado en su archivo de paginación.

La distinción entre memoria confirmada y reservada es que la primera permite a procesos o hilos declarar una cantidad de memoria que puede asignarse rápidamente cuando sea necesaria; y la otra, minimiza la cantidad de espacio en el disco separada para un proceso particular dejando ese espacio en disco para otros procesos.

CONCLUSIÓN

La memoria virtual ha llegado a ser un componente esencial de los S.O, convirtiéndose en una herramienta útil de gestión de memoria.

Desde su aparición se ha comprobado que se agilizó la labor del programador, ya que desarrollando un programa no debe restringir su tamaño, no teniendo necesidad de conocer la capacidad de memoria principal disponible.

Oculta también la complejidad de los algoritmos utilizados para el intercambio de los “trozos” de los procesos.

Por dichas razones, se busca implementarla en la mayoría de los S.O. actuales, dejado como optativa, la no utilización de la misma.