UNET Logo

Universidad Nacional Experimental Del Táchira
Decanato De Docencia
Dpto. Ingeniería en Informática

Paginación y Segmentación

Código 0435607T

Prof. Miguel Useche - migueluseche@unet.edu.ve - @skatox

Contenido

  • Paginación
  • Tabla de páginas.
  • Memoria asociativa.
  • Páginas compartidas.
  • Páginas multinivel.
  • Segmentación.
  • Segmentación con paginación.

Paginación

  • El sistema operativo divide la memoria en segmentos del mismo tamaño llamados marcos de página.
  • El espacio de direcciones lógicas de un programa es divido en segmentos llamados páginas.
  • Para ejecutar un programa de N tamaño de páginas, es necesario contar con N marcos de páginas disponibles y proceder a cargar el programa en memoria.
  • Se utiliza una tabla de página para transformar las direcciones lógicas a físicas.
  • Desaparece la fragmentación externa gracias al uso de los marcos de página, pero aparece fragmentación interna.

Paginación

Memoria lógica

Página 0
Página 1
Página 2

Tabla de páginas

0 1
1 4
2 3

Memoria física

0
1 página 0
2
3 página 2
4 página 1

Paginación

Dirección lógica

Una dirección de un proceso, consta de dos partes:

  • Número de página ( p ): usado como índice en la tabla de páginas para conocer la dirección base de la página en memoria física.
  • Desplazamiento ( d ): se combina con la dirección base para definir la dirección de memoria física enviada a la unidad de memoria.

Paginación

Dirección lógica

Memoria de 2KB con tamaño de páginas 256B.
Dirección: 0x75B = 11101011011

Página Desplazamiento
111 = 7 01011011 = 91

Paginación

Paginación

Modelo de paginación de la memoria lógica y física

Ejemplo de paginación

Memoria de 32B y página de 4B

Memoria lógica

0 - 3 4 - 7 8 - 11 12 - 15
a b c d e f g h i j k l m n o p

Tabla de páginas

0 1 2 3
5 6 1 2

Memoria física

0 4 8 12 16 20 24 28
          i j k l m n o p                     a b c d e f g h          

Tabla de páginas

tabla de paginas

Vista a tabla de páginas

  Accedido Modificado Presente / Ausente Protección Número Marco de página
  • Accedido: indica si se ha leído información de esa página, útil para algoritmos como LRU (Less Recently Used).
  • Modificado: advierte sobre cambios en los datos de la página desde que fue cargada del disco, para guardarlos al momento de salir de la memoria.
  • Presente / Ausente: permite conocer si la página se encuentra cargada en memoria o en el disco.
  • Protección: muestra el tipo de acceso permitido para el contenido de la página (lectura o escritura).
  • Número del marco: guarda el valor del marco de página donde se encuentra ubicada la información.

Implementación de la tabla de página

  • La tabla de páginas se mantiene en memoria principal.
  • El registro base de la tabla de páginas (PTBR) apunta al inicio de la tabla de páginas.
  • El registro longitud de la tabla de páginas (PRLR) indica el tamaño de la tabla de páginas.
  • En este esquema cada acceso a dato o instrucción requiere dos accesos a memoria. Uno para la tabla de páginas y otro para obtener el dato o instrucción.
  • Este proceso puede agilizarse usando una pequeña memoria asociativa o TLB (translation look-aside buffer).

Memoria asociativa

TLB

TLB

Memoria asociativa

TLB

Si la página esta en un registro asociativo se obtiene el número de marco, de lo contrario, se debe buscar en la tabla de páginas.

Memoria asociativa

  • Tasa de aciertos: 80%.
  • Tiempo accesso a TLB: 20 ns.
  • Tiempo accesso a memoria: 100 ns.

Si encuentra el número de marco en el TLB:
20ns + 100ns = 120 ns

Si no encuentra el número de marco en el TLB:
20ns + 100ns + 100ns = 220 ns

Tiempo efectivo de acceso:
0,8x120 + 0,20x220 = 140ns

Tiempo efectivo de acceso para 90% de aciertos:
0,9x120 + 0,10x220 = 130ns

Tasa de acierto: es el porcentaje de veces que se encuentra un número de página en el TLB.

Memoria asociativa

Tasa de acceso

tasa de acceso

A mayor porcentaje de acierto, menor es el tiempo de acceso a los datos en memoria.

Páginas compartidas

ejemplo de pagina compartida
  • Gracias al uso de tabla de páginas, se puede compartir código común entre procesos.
  • Esto es implementado a través de la compartición de un marco de memoria, para ello, el marco debe estar asociado en la tabla de proceso.
  • El número de página asociado al marco, puede ser diferente en cada proceso.

Páginas multinivel

TP multinivel
  • Si tablas de página ocupa mucho espacio, éstas se someten a una paginación, creando una organización páginada de múltiples niveles. Por ejemplo, la páginacion en dos niveles.
  • Las direcciones lógicas ahora poseen la siguiente estructura:
0x1AA76F = 0110101010011101101111
Página externa Página interna Desplazamiento
01101 01010 111 0110 1111

Segmentación

  • Un programa es una colección de segmentos.
  • Por ello, una dirección lógica consiste en un par de valores:
    número de segmento, desplazamiento
  • Existe una tabla de segmentos donde guarda:
    limite, base
    de cada segmento en memoria.
segmentos

Segmentación

Ejemplo de Segmentación de Memoria

Segmentación con paginación

  • La paginación y la segmentación se pueden combinar en la segmentación con paginación.
  • En este esquema de gestión de memoria los segmentos se paginan.
  • Se apoya la visión de la memoria que tiene el usuario.
  • Se resuelve el problema de la asignación dinámica.
  • Es necesario una tabla de segmentos y una tabla de páginas por cada segmento
  • La traducción de direcciones es más compleja y puede requerir un mayor número de accesos a memoria en el peor caso.

Anexos

Record mundial de
Super Mario World

Observa como rompieron el record de finalizar el juego aprovechando bugs de memoria.

Inyección de código en
Super Mario World

Observa como jugando inyecta código en el juego a través del bug mencionado anteriormente.

Lectura recomendada

What every programmer should know about memory : excelente publicación realizada por RedHat donde explican cómo es el manejo de memoria en Linux.

¿Preguntas?