Paginación en Memoria Virtual Por: Edgar A. Mendieta I...

Paginación en Memoria Virtual Edgar A. Mendieta

1

Paginación en Memoria Virtual Por:

Edgar A. Mendieta I. Gestión de Memoria. En un sistema con multiprogramación, el sistema operativo debe encargarse de

realizar un reparto transparente, eficiente y seguro de los distintos recursos de la

máquina entre los diversos procesos, de forma que cada uno de ellos crea que

«tiene una máquina para él solo». Esto es, el sistema operativo debe permitir

que los programadores desarrollen sus aplicaciones sin verse afectados por la

posible coexistencia de su programa con otros durante su ejecución.

En el caso de la memoria, el sistema operativo, con el apoyo del hardware de

gestión de memoria del procesador, debe repartir el almacenamiento existente

proporcionando un espacio de memoria independiente para cada proceso y

evitando la posible interferencia voluntaria o involuntaria de cualquier otro

proceso.

Se podría considerar que, en el caso del procesador, se realiza un reparto en el

tiempo, mientras que en el de la memoria, se trata de un reparto en el espacio

La acción combinada de estos dos mecanismos ofrece a los programas una

abstracción de procesador virtual que les independiza del resto de los procesos.

1. Requisitos de la Gestión de Memoria.

Sea cual sea la política de gestión de memoria empleada en un determinado

sistema, se pueden destacar las siguientes características como objetivos

deseables del sistema de gestión de memoria:

• Ofrecer a cada proceso un espacio lógico propio.

• Proporcionar protección entre los procesos.

• Permitir que los procesos compartan memoria.

• Dar soporte a las distintas regiones del proceso.

• Maximizar el rendimiento del sistema.

• Proporcionar a los procesos mapas de memoria muy grandes.

1.1. Reubicación.


2

En un sistema operativo multiprogramado de propósito general no se puede

conocer a priori la posición de memoria que ocupará un programa cuando se

cargue en memoria para proceder a su ejecución, puesto que dependerá del

estado de ocupación de la memoria, pudiendo variar, por tanto, en sucesivas

ejecuciones del mismo.

El código máquina de un programa contenido en un archivo ejecutable incluirá

referencias a memoria, utilizando los diversos modos de direccionamiento del

juego de instrucciones del procesador, tanto para acceder a sus operandos

como para realizar bifurcaciones en la secuencia de ejecución. Estas referencias

típicamente estarán incluidas en un intervalo desde 0 hasta un valor máximo N.

1.2. Protección. En un sistema con monoprogramación es necesario proteger al sistema

operativo de los accesos que realiza el programa en ejecución para evitar que,

voluntaria o involuntariamente, pueda interferir en el correcto funcionamiento del

mismo. Todos los usuarios que han trabajado en un sistema que no cumple este

requisito de protección, como por ejemplo MS-DOS, han experimentado cómo

un error de programación en una aplicación puede causar que todo el sistema se

colapse durante la ejecución de la misma al producirse una alteración imprevista

del código o las estructuras de datos del sistema operativo.

En un sistema con multiprogramación el problema se acentúa ya que no sólo

hay que proteger al sistema operativo sino también a los procesos entre sí. El

mecanismo de protección en este tipo de sistemas necesita del apoyo del

hardware puesto que es necesario validar cada una de las direcciones que

genera un programa en tiempo de ejecución. Este mecanismo está típicamente

integrado en el mecanismo de traducción: la función de traducción debe

asegurar que los espacios lógicos de los procesos sean disjuntos entre sí y con

el del propio sistema operativo.

Observe que en el caso de un sistema que use un procesador con mapa de

memoria y E/S común, el propio mecanismo de protección integrado en el

proceso de traducción permite impedir que los procesos accedan directamente a


3

los dispositivos de E/S, haciendo simplemente que las direcciones de los

dispositivos no formen parte del mapa de ningún proceso.

1.3. Compartición. Para cumplir el requisito de protección, el sistema operativo debe crear espacios

lógicos independientes y disjuntos para los procesos. Sin embargo, en ciertas

situaciones, bajo la supervisión y control del sistema operativo, puede ser

provechoso que los procesos puedan compartir memoria.

Esto es, la posibilidad de que direcciones lógicas de dos o más procesos,

posiblemente distintas entre sí, se correspondan con la misma dirección física.

1.4. Soporte de las regiones del proceso. Como se analizará con más detalle en secciones posteriores, el mapa de un

proceso no es homogéneo sino que está formado por distintos tipos de regiones

con diferentes características y propiedades.

Dado que el sistema operativo conoce qué regiones incluye el mapa de memoria

de cada proceso, el gestor de memoria con el apoyo del hardware debería dar

soporte a las características específicas de cada región.

Así, por ejemplo, el contenido de la región que contiene el código del programa

no debe poder modificarse. Se debería detectar cualquier intento de escritura

sobre una dirección incluida en dicha región y tratarlo adecuadamente (p. ej.:

mandando una señal al proceso).

Otro aspecto a resaltar es que el mapa del proceso no es estático. Durante la

ejecución de un programa puede variar el tamaño de una región o, incluso,

pueden crearse nuevas regiones o eliminarse regiones existentes. El sistema de

memoria debe controlar qué regiones están presentes en el mapa de memoria y

cuál es el tamaño actual de cada una.

1.5. Maximizar el rendimiento. El gestor de memoria debe, por tanto, realizar un reparto de la memoria entre los

procesos intentando que quepa el mayor número de ellos en memoria y

minimizando el desperdicio inherente al reparto. Para ello, debe establecerse


4

una política de asignación adecuada. La política de asignación determina qué

direcciones de memoria se asignan para satisfacer una determinada petición.

Hay que resaltar que la propia gestión de la memoria requiere un gasto en

espacio de almacenamiento para que el sistema operativo almacene las

estructuras de datos implicadas en dicha gestión. Así, será necesario guardar la

tabla de regiones y la función de traducción asociada a cada proceso

(normalmente implementadas como tablas), así como una estructura que refleje

qué partes de la memoria permanecen libres y cuáles están ocupadas. Dado que

el almacenamiento de estas estructuras resta espacio de memoria para los

procesos, es importante asegurar que su consumo se mantiene en unos

términos razonables.

II. Memoria Virtual. 1. Estructura de Control y Hardware.

Si se comparan la paginación y segmentación simple con la partición estática y

dinámica, se pueden ver los avances fundamentales en la gestión de memoria.

Las claves de estos avances son las siguientes características.

• Los procesos pueden ser descargados y cargados a memoria principal de

memoria principal en cualquier instante a lo largo de la ejecución. Ya que

las referencias a memoria de un proceso son lógicas; las cuales son

traducidas a direcciones físicas, dinámicamente durante la ejecución del

proceso.

• Gracias a la combinación de la traducción dinámica de direcciones de

memoria y el uso de tablas de páginas o de segmentos los procesos

pueden dividirse en varias partes sin que sea necesario que dichas partes

estén contiguas en memoria principal.

Si las características mencionadas anteriormente están presentes no será

necesario que todas las páginas de o todos los segmentos de un proceso estén

en la memoria principal durante la ejecución. Bastara con la parte que contiene

los datos a acceder.


5

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.

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.

Al momento de querer traer un proceso a memoria en un instante dado. El

sistema operativo comienza trayendo solo unos fragmentos, incluyendo el que

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

Como los procesos se ejecutan sólo en memoria principal, a esta memoria se le

llama memoria real. Un programado o usuario puede ver la ejecución de dicho


6

proceso en espacios de memoria mayores a la memoria real; esta memoria será

espacios disco que tomara dicho proceso para ejecutarse. Está memoria

residente o que hace uso de espacio en disco es denominada memoria virtual.

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


7

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

Lo dicho anteriormente lo podemos resumir en la siguiente expresión:

Memoria Virtual = Memoria Física + Área de Swapping en Disco


8

3. Paginación.

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.


9

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.

3.1 Tabla de Páginas. Cada página tiene un número que se utiliza como índice en la tabla de páginas,

lo que da por resultado el número del marco correspondiente a esa página

virtual. Si el bit presente / ausente es 0, se provoca un señalamiento (trap) hacia

el sistema operativo. Si el bit es 1, el número de marco que aparece en la tabla

de páginas se copia en los bits de mayor orden del registro de salida, junto con

el ajuste (offset) de 12 bits, el cual se copia sin modificaciones de la dirección

virtual de entrada. Juntos forman una dirección física de 15 bits. El registro de

salida se coloca entonces en el bus de la memoria como la dirección en la

memoria física.


10

En teoría, la asociación de las direcciones virtuales con las físicas se efectúa

según lo descrito. El número de página virtual se divide en un número de página

virtual (los bits superiores)y un ajuste (los bits inferiores). El número de página

virtual se utiliza como un índice en la tabla de páginas para encontrar la entrada

de esa página virtual. El número de marco (si existe) se determina a partir de la

tabla de páginas. El número de marco se asocia al extremo superior del ajuste y

reemplaza al número de página virtual para formar una dirección física que se

puede enviar a la memoria.

La finalidad de la tabla de páginas es asociar las páginas virtuales con los

marcos. En términos matemáticos, la tabla de páginas es una función, cuyo

argumento es el número de página virtual y como resultado el número del marco

físico. Mediante el resultado de esta función, se puede reemplazar el campo de

la página virtual de una dirección virtual por un campo de marco, lo que produce

una dirección en la memoria física. Sin embargo hay que enfrentar dos aspectos

fundamentales:

• La tabla de páginas puede ser demasiado grande.

• La asociación debe ser rápida.

El primer punto proviene del hecho de que las computadoras modernas utilizan

direcciones virtuales de al menos 32 bits. Por ejemplo, si el tamaño de página es

de 4K, un hueco de direcciones de 32 bits tiene un millón de páginas; en el caso

de un hueco de direcciones de 64 bits, se tendría más información de la que uno

quisiera contemplar.

El segundo punto es consecuencia del hecho de que la asociación virtual – física

debe hacerse en cada referencia a la memoria. Una instrucción común tiene una

palabra de instrucción y también un operando de memoria. Entonces es

necesario hacer una, dos o más referencias a la tabla de páginas por cada

instrucción.

Muchos sistemas como los AS/400 de IBM y las estaciones de trabajo RISC

Sistemas/600 de IBM son usados tablas de paginas invertidas. Con este metodo

la parte del número de página virtual se contrasta en una tabla de dispersión por

medio de una función de dispersión simple. La tabla de dispersión contiene un


11

puntero a la tabla de páginas invertidas, que contienen a su vez las entradas de

la tabla de páginas.

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


12

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


13

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.

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


14

dicha palabra. Si lo está, es devuelto a la CPU. Si no, se toma la palabra de la

memoria principal.

3.3 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


15

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.

3.4 Ventajas y Desventajas de la Paginación. Ventajas:

• mejor utilización de la memoria física (programas implantados por

fragmentos, en páginas no consecutivas).

• Posibilidad de cargar páginas solamente cuando éstas son referenciadas

(cargado bajo demanda).

• Independencia del espacio virtual y de la memoria física (memoria virtual

generalmente más grande).

• Posibilidad de llevar al disco solamente páginas modificadas.

• Posibilidad de cobertura dinámica (emparejamiento).

Desventajas:

• Fragmentación interna (todas las páginas no son llenadas).

• Imposibilidad de relacionar dos (o varios) procesos relacionados a las

mismas direcciones en el espacio virtual.

4. Algoritmos de Reemplazo de Paginas.

Con el uso del método de paginación se puede llegar a saturar la memoria si se

incrementa demasiado el nivel de multiprogramación. Por ejemplo, si se corren


16

seis procesos, cada uno con un tamaño de diez páginas de las cuales en

realidad sólo utiliza cinco, se tiene un mayor uso del CPU y con marcos de

sobra. Pero pudiera suceder que cada uno de esos procesos quiera usar las diez

páginas resultando en una necesidad de 60 marcos, cuando solo hay 40

disponibles.

Esto provoca sobre-asignación y mientras un proceso de usuario se está

ejecutando, ocurre un fallo de página. El hardware se bloquea con el sistema

operativo, el cual checa en sus tablas internas y se da cuenta que es un fallo de

página y no un acceso ilegal de memoria. El sistema operativo determina si la

página está residiendo en disco, pero también determina que no hay marcos de

memoria disponibles en la lista de marcos libres.

Al ocurrir el fallo de página, el sistema operativo debe elegir una página para

retirarla de la memoria y usar el espacio para la página que se necesita para

desbloquear el sistema y que el hardware pueda seguir trabajando. Si la página

por eliminar de la memoria fue modificada, se debe volver a escribir al disco para

mantener la información actualizada; de lo contrario, si la página no fue

modificada no es necesario rescribir la información a disco y la página que se

carga simplemente se escribe sobre la página a borrar en memoria.


17

4.1. Algoritmo aleatorio Este algoritmo consiste simplemente en reemplazar aleatoriamente

cualquier página de la memoria principal, sin hacer ningún esfuerzo de

predicción.

Es el algoritmo más sencillo dado que no requiere tener ninguna

información, sin embargo, por no hacer uso de dicha información sobre el

comportamiento del proceso, no puede lograr un buen desempeño.

4.2. Algoritmo de reemplazo de páginas óptimo Este algoritmo debe de tener el menor índice de fallos de página de todos los

algoritmos. En teoría, este algoritmo debe de reemplazar la página que no va a

ser usada por el periodo más largo de tiempo.

Desafortunadamente, el algoritmo de reemplazo óptimo es fácil en teoría, pero

prácticamente imposible de implementar, dado que requiere conocer a futuro las

necesidades del sistema.

Tal algoritmo existe y ha sido llamado OPT o MIN, pero se usa únicamente para

estudios de comparaciones. Por ejemplo, puede resultar muy útil saber que

aunque algún nuevo algoritmo no sea óptimo, está entre el 12.3% del óptimo y

entre el 4.7% en promedio.

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


18

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.

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.

4.4. Algoritmo de reemplazo “Primero en entrar, primero en salir” (FIFO)

El algoritmo más sencillo para remplazo de páginas es el FIFO (First In – First

Out). Este algoritmo asocia a cada página el momento en que ésta fue traída a

memoria. Cuando una página debe ser reemplazada se selecciona a la más

antigua.

No es estrictamente necesario registrar el momento de entrada de la página a

memoria, sino que se puede crear una cola en la que se van agregando las

páginas conforme van llegando a la memoria. Cuando se debe eliminar una

página, se selecciona la que está al frente de la lista (o sea, la más antigua de la

lista). Cuando llega una página nueva, se inserta en la parte trasera de la cola.

Al igual que el algoritmo aleatorio, este algoritmo es fácil de comprender y de

programar. Sin embargo, su desempeño no siempre es del todo bueno. La

página reemplazada puede ser un módulo de inicialización que fue usado hace

mucho tiempo y ya no se tiene necesidad de él. Por otro lado, puede contener


19

una variable de uso muy frecuente que fue inicializada de manera temprana y

está en uso constante.

4.5. Algoritmo de reemplazo de páginas de la segunda oportunidad

Este algoritmo es una modificación del FIFO. El algoritmo hace uso del bit de

referencia de la página. Cuando una página ha sido seleccionada para

reemplazo, se revisa el bit de referencia. Si tiene valor de 0, se procede a

reemplazar la página. Si por el contrario, el bit de referencia es 1 se le da a la

página una segunda oportunidad.

Cuando esto sucede, se le cambia el bit de referencia a 0 y se actualiza su

tiempo de llegada al tiempo actual para que la página se colocada al final de la

cola. De esta manera, la página espera todo un ciclo completo de páginas para

ser entonces reemplazada.

Si la página tiene un uso muy frecuente, el bit de referencia se mantendría

constantemente en 1 y la página no sería reemplazada. En la figura 10 se puede

apreciar el funcionamiento del algoritmo.

4.6. Algoritmo de reemplazo de páginas del reloj Modificando el algoritmo de la segunda oportunidad (que a su vez es una

modificación de FIFO) obtenemos el algoritmo aumentado de la segunda

oportunidad o algoritmo del reloj. Usamos la misma clasificación vista en el

algoritmo de uso no tan reciente.

Este algoritmo organiza las páginas en una lista circular; se usa un apuntador (o

manecilla) que señala a la página más antigua.


20

4.7 Algoritmo de reemplazo de páginas “la de menor uso reciente” (LRU)

Este algoritmo es una buena aproximación al óptimo y se basa en al observación

de que las páginas de uso frecuente en las últimas instrucciones se utilizan con

cierta probabilidad en las siguientes. De la misma manera, es probable que las

páginas que no hayan sido utilizadas durante mucho tiempo permanezcan sin

uso por bastante tiempo. Implementando el algoritmo con esta base, al ocurrir un

fallo de página, se elimina la página que no haya sido utilizada durante el tiempo

más grande. De ahí su denominación: menor uso reciente (LRU - Least Recent

Use).

A diferencia de los algoritmos anteriores, el LRU tiene un mejor rendimiento en

cuanto al tiempo de aprovechamiento del CPU y del uso de la memoria. Sin

embargo, el problema con este algoritmo es que su implementación es muy

cara, ya que requiere de una asistencia considerable de hardware. Otro

problema es el de determinar un orden para los marcos definido por el tiempo de

menor uso. Para éste último hay dos posibles implementaciones:

Contadores: En el caso más sencillo, se asocia cada entrada tabla-página un

campo de tiempo-de-uso y se le agrega al CPU un reloj lógico o contador. Este

reloj es incrementado en cada referencia de memoria. Siempre que se hace

referencia a una página, el contenido del registro del reloj es copiado al campo

de tiempo-de-uso en la tabla de páginas para esa página. De esta forma,

siempre se dispone del “tiempo” de la última referencia a cada página. La página

que se reemplaza es la del menor valor de tiempo. Este esquema requiere de

una búsqueda en toda la tabla de páginas para encontrar la página LRU, y una

escritura en memoria al campo de tiempo-de-uso en la tabla de páginas por cada

acceso a memoria. Los tiempos también se deben de mantener cuando las


21

tablas de páginas son alteradas (debido a organización del CPU). Se debe

considerar la posibilidad de sobrecarga en el reloj.

Pilas: Otra aproximación para implementar el reemplazo LRU es la de tener una

pila con los números de páginas. Siempre que se hace referencia a una página,

se quita de la pila y se pone en la parte superior. De esta manera, la parte

superior de la pila es la página de uso más reciente y la de abajo es la LRU.

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

1. SISTEMA DE PAGINACIÓN


22

1.1 Estructuras de datos Para la memoria virtual paginada, UNIX, hace uso de una serie de estructuras

de datos que son independientes de la maquina:

Tabla de páginas: posee una tabla por proceso, con una entrada para cada

página de la memoria virtual en proceso.

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.

Tabla de marcos de página: describe cada marco de la memoria real y está

indexada por el número de marco.

Tabla de uso de intercambios: existe una tabla por cada dispositivo de

intercambio.

1.2 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 páginas 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:

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.

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

IV. GESTION DE MEMORIA EN LINUX


23

Linux comparte algunas características de UNIX, pero su esquema de gestión

de memoria es bastante complejo.

1. MEMORIA VIRTUAL DE LINUX

1.1 Direccionamiento de memoria virtual Linux hace uso de una estructura de tabla de páginas con tres niveles:

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

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

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

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

1.3 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


24

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.

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

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

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

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

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

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


25

Conclusión

Así como la memoria es una de las partes más importantes de un sistema

informático, su administración tendrá la misma importancia; aunque los sistemas

de computación modernos contengan gran cantidad de memoria real, será

necesario expandir la misma o ocupar más espacio el cual será asignado en

disco. Los Sistemas Operativos actuales están diseñados para manejar cada

día más procesos que necesitaran gran cantidad de memoria para su ejecución,

luego entonces, es necesario asignar o reservar este espacio virtual de memoria

en lugares como el disco duro.

Gracias a los estudios realizados se puede entender de forma detallada que el

uso de la memoria virtual a ayudado y seguirá ayudando a los programadores de

Sistemas Operativos y de cualquier tipo de aplicación para que los mismos

tengan un mejor desempeño a la hora de ejecutarse.

Desde que surgieron los primeros Sistemas Operativos se buscó la forma de

ayudar al desempeño de los procesos en ejecución, es de esta forma que para

nuestro tiempo podemos contar con la memoria virtual y su técnica de

paginación, que mas que todo ayudara a la multiprogramación, multiproceso y

sobre todo nos dará un mejor soporte a aplicaciones sobre sistemas que

trabajen en redes.


26

Bibliografía

1. Stallings, William (1998) Sistemas Operativos. España: Prentices Hall.

Segunda Edición. 707 páginas.

2. Magister David Luis la Red Martinez (2001). “Paginación de Memoria

Virtual con Sistemas Expertos”. Universidad Nacional del Nordeste de

Argentina.

http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/SO0.h

tm#IG. Consulta 10/2004.

3. Magister David Luis la Red Martinez (2001). “Memoria Virtual”.

Universidad Nacional del Nordeste de Argentina.

http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativos/Mono

gSO/MEMVIR02.htm . 14/2004.

Paginación en Memoria Virtual Por: Edgar A. Mendieta I...

Documents

Transcript of Paginación en Memoria Virtual Por: Edgar A. Mendieta I...