Paginación

De Departamento de Informatica
Saltar a: navegación, buscar

Contenido

Contenidos

¿Qué es y Cómo funciona?

La paginación es uno de los esquemas de manejo de memoria en donde un computador puede almacenar y recuperar datos de un dispositivo de almacenamiento secundario para su uso en la memoria principal. En el esquema de manejo de memoria de paginación, el sistema operativo recupera datos desde un dispositivo de almacenamiento secundario en bloques de un mismo tamaño llamados páginas. La principal ventaja de paginación sobre la segmentación de memoria es que permite al espacio de dirección física de un proceso ser no contiguo. Antes de la paginación, los sistemas debían poner programas en almacenamiento de forma contigua, lo que causaba varios problemas de almacenamiento y fragmentación.

Esquema de Memoria física y lógica.

El método básico para implementar paginación consiste en dividir la memoria física en bloques de tamaño fijo llamados frames (marcos) y dividir la memoria lógica en bloques de mismo tamaño llamados pages (páginas). Cuando un proceso se va a ejecutar, sus páginas son cargadas en cualquier marco de la memoria de almacenamiento secundario. Este esta dividido en bloques de tamaño fijo del mismo tamaño de los marcos en memoria.

Hardware de Paginación

El tamaño de pagina (como el marco de página) es definido por hardware. El tamaño de una pagina es tipicamente una potencia de 2, variando entre 512 B y 16 MB por pagina, dependiendo de la arquitectura del computador. La selección de una potencia de 2 como tamaño de página hace la traducción de una direccion lógica a un número de pagina y offset de página algo fácil. Si el tamaño del espacio de dirección lógica es 2^m y el tamaño de página 2^n unidades de dirección (bytes o palabras), entonces los m-n bits de mayor orden de la dirección logica designan el número de pagina, y los n bits de menor orden designan el offset de página.

Esquema Hardware de paginación.

Cualquier direccion generada por la CPU es divida en dos partes: un número de página (p) y un offset de página (d). El número de pagina es usado como indice en una tabla de página. La tabla de página contiene las direcciones base de cada pagina en la memoria física. Esta dirección base es combinada con el offset de página para definir la dirección de memoria física que es enviada a la unidad de memoria.

Tabla de Página

Bueno, ya hemos revisado el concepto de paginación y como funciona, En esta sección explicaremos como se implementa, y es en este punto en donde debemos mencionar a "la Tabla de Página". La tabla de página es una Estructura de datos usada por el sistema de memoria virtual, en un sistema operativo para almacenar la relación entre una dirección virtual en la memoria y la direcciones físicas. Veamos dicha explicación en una imágen:

Tabla de Página

Ahora bien, debemos comprender con mayor profundidad como funciona una tabla de página y es lo que veremos a continuación.

Estructura de una tabla de Página

La tabla de página se guarda en memoria principal, y para poder acceder a ella, se requieren de 2 estructuras, las cuales son conocidas como:

* PTBR: Page Table Base Register, el cuál apunta a la tabla de página
* PTLR: Page Table Length Register: cuya función es indicar el tamaño de la página.

Ahora bien, cada dirección, ya sea dato o instrucción requiere de 2 accesos a memoria, uno para la tabla de página y otro para la instrucción. También debemos mencionar que la implementación de la tabla de página puede ser resuelta de varias maneras,citemos algunas:

* Se puede implementar como un conjunto de registros(hardware) dedicados de alta velocidad.
* Haciendo uso de la memoria Caché, para el caso de los 2 accesos a memoria, reduciendo el tiempo de acceso.


Esta última también es conocida como TLB, cuya traducción es: tranlation look-aside, y como mencionabamos tiene por objeto el reducir el tiempo de acceso a memoria, veamos un ejemplo:

TLB en acción, haga click para agrandar

Un dato a mencionar, que mas adelante será tratado en profundidad es que algunos TLB tienen identificadores en sus entradas, conocidos por sus siglas como ASID cuya función es identificar a cada proceso y así proteger el espacio de direcciones.


Con respecto al tamaño, ¿que pasa si la tabla de página es muy grande?: una respuesta inmediata es que se perderían aquellos espacios que quizás no son pequeños, pero no son lo suficientemente grandes como para darle cabida a un proceso. Es por ello, que existen técnicas para grandes tablas de páginas, las cuáles son:

  • Paginación Jerárquica: Se caracteriza por dividir el espacio lógico en múltiples tablas de página.
Paginación Jerárquica
  • Utilización de Hash: Por lo general el espacio de direcciones comunes es mayor a 32bits. El número de la página virtual se usa como llave de una tabla de página hash. Esta tabla de página contiene una lista con los elementos asociados al mismo registro, por lo que se compara el número de página virtual en la lista buscando una coincidencia, si se encuentra, el marco de página se extrae,(en este punto es recomendable revisar el material de ARI).

Veamos como esto actúa:

Paginación con método Hash
  • Utilización de Tabla de páginas invertidas: La especial particularidad de este método, es que disminuye el desperdicio de memoria, pero aumenta el tiempo de búsqueda y para lidiar con esto, utiliza la tabla hash. Veamos el ejemplo:
Tabla de Página invertida

Memoria Asociativa

Se llama memoria asociativa si permite recuperar información a partir de conocimiento parcial del contenido en algún dispositivo de almacenamiento, sin saber su localización de almacenamiento.

Estas pueden almacenar información y recuperarla cuando sea necesario, es como una red retroalimentada ya que la salida se utiliza repetidamente como una nueva entrada hasta que el proceso converge. Puede recuperar dicha información basándose en el conocimiento de parte de ésta (una clave). El patrón clave puede ser una versión con ruido de un patrón memorizado, es decir, que difiere de él en pocas componentes. La memoria humana recuerda a una persona aunque vaya vestida de forma diferente o lleve gafas.

Las memorias asociativas son una de las redes neuronales artificiales más importantes con un amplio rango de aplicaciones en áreas tales como: Memorias de acceso por contenido, identificación de patrones y control inteligente.

Existen dos tipos de memorias asociativas:

- Memorias heteroasociativas: establecen una correspondencia de x (vector de entrada) en y (vector de salida), de distinta dimensión. Dichos patrones se llaman memorias principales o de referencia.

- Memorias autoasociativas: establece la misma correspondencia que la memoria heteroasociativa pero siendo los patrones de entrada y de salida los mismos.

TAE: Tiempo de Acceso Efectivo

Como sabemos la paginacion pede tener una demanda significativa de rendimientos en el sistema, por lo que cuando usamos cache, debemos saber cuanto tiempo nos cuesta acceder a la memoria, para determinar este tiempo ocupamos el TAE, que nos da el tiempo medio de acceso a una celda de memoria. Este tiempo se calcula con la siguiente formula:


TAE : p*ta + (1-p)*tf

Donde:

- p: probabilidad de acierto

- ta: tiempo de acceso si hay acierto

- tf: tiempo de acceso si hay fallo

- 1-p: probabilidad de fallo

Protección de Memoria

Es un método esencial que utilizan los sistemas operativos para el control del uso de memoria de un computador. Su finalidad es evitar que un proceso en un sistema operativo acceda a la memoria que no le ha sido asignada. Así pueden evitarse problemas durante la ejecución del software, y también se evita que software maligno acceda a los recursos del sistema.

La protección se implementa por un conjunto de bits que son asociados a cada frame. Un bit puede definir si una página es read-only o read-write y cada vez que se hace una operación sobre un page frame se verifica sobre estos bits.

- Multilevel Paging: Aca se busca minimizar el tiempo de búsqueda en la tabla de páginas utilizando un sistema de paginación de 2 niveles. Una dirección es de la forma: (P1,P2,d), donde ( numero pagina, numero pagina, desplazamiento).

- Inverted Page Table: Se lleva una tabla de páginas para todos los procesos. Cada entrada de página contiene la siguiente información: <process-id, nro. Pagina, desplazamiento>.

- Paginas Compartidas: Es posible que los procesos compartan código común. El código común no sera protegido mediante los bits de protección, ya que no puede ser modificado.

- Segmentación: En un esquema de segmentación un espacio de direcciones lógicas es un conjunto de segmentos. Cada segmento tendrá un nombre y un largo. Las direcciones van a hacer referencia tanto al nombre como al desplazamiento dentro del segmento. <nro.segmento, desplazamiento>.

- Mecanismo de traducción de direcciones: Se lleva un tabla de segmento por cada proceso, cada entrada a la tabla de segmento lleva la siguiente información: segment base (dirección base del segmento) segment limit (largo del segmento)


La mayoría de los sistemas operativos tienen protección de memoria. Algunos de los sistemas operativos que disponen de protección de memoria incluyen:

- La familia Microsoft Windows

- La mayoría de sistemas tipo Unix incluyendo:

- Solaris

- Linux

- BSD

- Mac OS X (el anterior Mac OSes tenía una protección de memoria limitada)

Referencias

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas