•Esquema de administración de memoria que soporta la visión del usuario de la memoria.
•Un programa es una colección de segmentos. Un segmento es una unidad lógica como por ejemplo:
–Programa principal
–procedimientos
–funciones
–Variables locales, variables globales
–bloques comunes
–pila
–tabla de simbolos, arreglos, etc.
Esquema de traducción usando segmentación

Tabla de correspondencia de segmentos
Dirección virtual=(s,d), los segmentos se intercambian como unidades.

Programa: nucleo principal, rutinas, datos(tablas, pilas, etc)

r= 0 si segmento no esta en real, 1 si esta

Bits de protección: 1-si 0-no

R-acceso lectura,W-escritura,E-ejecución, A-adición

Segmentación con paginacion
•La segmentación con paginación intenta aunar lo mejor de los dos esquemas anteriores.
•La segmentación proporciona soporte directo a las regiones del proceso y la paginación permite un mejor aprovechamiento de la memoria y una base para construir un esquema de memoria virtual.
•Un segmento está formado por un conjunto de páginas y, por tanto, no tiene que estar contiguo en memoria.
•La MMU utiliza una tabla de segmentos, tal que cada entrada de la tabla apunta a una tabla de páginas.
•Requiere un hardware más complejo
•El sistema Multics resolvio la fragmentación externa y los largos tiempos de busqueda paginando los segmentos.
•Ésta solución difiere de la segmentación pura en que la entradas de la tabla de segmentos no contienen la dirección base del segmento, mas bien contienen la dirección base de la tabla de paginas para este segmento.

Páginación multinivel y rendimiento (sin intercambio)L
Establecer el EAT para un procesador con 4 niveles de paginación con tiempo de acceso a memoria de 100ms, tiempo de busqueda es 20ms y una tasa de aciertos en cache de 98%

Para 4 niveles de paginación

Dado que cada nivel es almacenado como una tabla separada en memoria, el convertir una dirección lógica a una física requiere de 4 accesos a memoria, No obstante el tiempo requerido para el acceso a memoria es quintuplicado, el cache permite que el rendimiento permanezca razonable.

•Si t=100ms, e= 20ms,a= 98% da:
Tiempo de acceso efectivo = (t + e) a + ((n+1)t + e)(1 – a)

EAT = (t + e) a + (5t + e)(1 – a)

EAT =(100+20)0.98+((4+1)100+ 20)(1- 0.98)

EAT = 120 * 0.98 + 520 * 0.02 = 128 ms.

Que es solamente un 28% de reducción en tiempo de acceso a memoria.

---

Rendimiento en paginación por demanda con intercambio

•Tasa de fallo de pagina 0 £ p £ 1.0
–si p = 0 no hay fallo de pagina
–Si p = 1,cada referencia es un fallo de pagina
Tiempo de acceso efectivo con intercambio =EATS = (1 – p) * acceso a memoria

• p * (sobrecarga de fallo de pagina

carga

reinicio)

Si asumimos un valor global para el tiempo requerido en fallo de página (f) tendremos:

EATS=(1-p)t + pf

Donde

t :el tiempo de acceso a memoria,

p :la probabilidad de fallo de pagina y

f : el tiempo de fallo de pagina

Las direcciones generadas por la Cpu se dividen en:

Número de página (p)
Utilizado  en la tabla de páginas que contiene las direcciones base de cada página en la memoria física.
El desplazamiento de página (d)
Combinado con la dirección base definen la dirección de memoria física que es enviada a la unidad de memoria.

Traducción: proceso referencia (p,d), se busca en la  tabla de correspondencia de páginas para ver la p’ (p real),
La dirección real es p’+d. Por agilidad tabla de correspondencia en caché.•Si no hay residencia de la página en memoria principal, sucede una falta de página. r= 0 si página no esta en real, 1 si esta.

Traducción de direcciones en paginación

Elementos de la tabla de páginas
•Otras informaciones
–Copia en escritura
–Edad
–No pagina (fija en memoria física)
–Rellenar a ceros
Buffer de traducción anticipada (TLB)
•La tabla de páginas se mantiene en memoria principal.
•El registro base de la tabla de páginas (PTBR) señala la tabla de páginas.
•El registro de longitud de tabla de páginas (PRLR) indica el tamaño de la tabla de páginas.
•Toda memoria virtual puede causar dos accesos a memoria física
–Uno para buscar en la tabla de página apropiada
–Uno para buscar los datos solicitados
•Para solventar este problema, la mayoría de esquemas de memoria virtual utilizan una cache especial de alta velocidad para las entradas de la tabla de página
–Se le denomina buffer de traducción anticipada [Translation Lookaside Buffer (TLB)], también llamado registros asociativos.
•Contiene aquellas entradas de la tabla de páginas que han sido usadas de forma más reciente
•Dada una dirección virtual, el procesador primero examina la TLB
•Si la entrada de la tabla de páginas solicitada está presente (acierto en TLB), entonces se recupera el número de marco y se construye la dirección real
•Si la entrada de la tabla de páginas solicitada no se encuentra (fallo en la TLB), el procesador utiliza el número de página para indexar la tabla de páginas del proceso
•Primero comprueba si la página solicitada está todavía en la memoria principal
–Si no se encuentra en la memoria principal, se produce un fallo en la memoria, llamado fallo de página
•La TLB se actualiza para incluir esta nueva entrada de tabla de páginas

• Utiliza paginación por demanda con clustering. El agrupamiento trae las páginas alrededor de la página fallada.
• A los procesos se les asigna un working set minimum y un working set maximum.
• El conjunto de trabajo mínimo es el número de páginas que se le garantiza a un proceso tener en memoria.
• A un proceso se le pueden asignar tantas páginas hasta alcanzar su conjunto de trabajo máximo.
• Cuando la cantidad de memoria en el sistema cae por debajo de un umbral, se realiza un recorte automático del conjunto de trabajo para recuperar memoria disponible.
• Este recorte remueve las páginas de exceso de los procesos que están sobre su conjunto de trabajo mínimo.

Espacio de direcciones 32 bit windows

Se toma el algoritmo del reloj pero con los 2 bit, el de referencia y el de modificación:

0,0 No referenciadas, no modificadas.
0,1 No referencidas, modificadas.
1,0 Referenciadas, no modificadas.
1,1 Referenciadas, modificadas.
Se reemplaza el de la clase más baja (Macintosh).

Otros algoritmos de reemplazo de páginas

• Aleatorio (Random): Reemplaza las páginas de forma aleatoria, se trabaja en el OS/360 cuando se degenera el LRU, también se utilizó en extinto i860 de intel (risc).
• No frecuentemente usada (NFU): Cada página tiene un contador, en cada intervalo de reloj se incrementa en 1 el contador de las páginas referenciadas, así cuando se requiere intercambio se saca la de menor contador.
• Envejecimiento (Aging): Similar al anterior pero tiene en cuenta el tiempo, primero se desplaza a la derecha antes de incrementar. Con lo cual se compensan las páginas más recientemente usadas.
• La menos usada frecuentemente (LFU): Reemplaza la página que menos intensivamente ha sido referenciada, se basa en la heurística de que una página no referenciada con frecuencia es probable que no sea referenciada en el futuro.
• Reemplazo de página más lejana FPR (Far Page Replacement): Crea un grafo de acceso que caracteriza los patrones de referencia de un proceso. Reemplaza la página no referenciada que esté más lejana de cualquier página referenciada en el grafo de acceso. Es compleja de manejar sin soporte en hardware, no ha sido implementada en sistemas comerciales.

• Asume que las páginas recientemente usadas serán usadas de nuevo, elimina las páginas que no han sido usadas por mucho tiempo.
• Reemplaza la página que no se haya referenciado desde hace más tiempo.
• Por el principio de proximidad referenciada, esta página sería la que tiene menos probabilidad de volver a tener referencias en un futuro próximo.
• Debe conservar una lista de páginas enlazadas
  • Las páginas usadas recientemente de primeras y las menos usadas de últimas.
  • Actualiza estos enlaces en cada referencia de memoria.
• De forma alternativa puede llevar un contador en cada entrada de la tabla de páginas, seleccionando la página con el menor valor.
  • Cada página podría etiquetarse con el instante de tiempo de su última referencia. Esto podría suponer una gran sobrecarga.

Algoritmo del conjunto de trabajo

• Conserva una lista encadenada de todas las páginas en el orden en que llegaron a memoria.
  • Trata los marcos de página ocupados como si se tratase de un buffer circular.
  • Las páginas se reemplazan mediante una estrategia cíclica de tipo round-robin.
  • Es una de las políticas de reemplazo más sencillas de implementar.
  • Se reemplaza la página que lleva en memoria más tiempo.
  • Estas páginas podrían necesitarse de nuevo muy pronto.
• Se reemplazan las páginas al principio de la lista.
• Desventaja
  • Las páginas que más estén en la memoria no necesariamente son las más usadas.

FIFO y anomalía de Belady M

Algoritmo del RELOJ, SEGUNDA OPORTUNIDAD

• Determina cuándo una página se debería traer a la memoria principal.
• Con paginación bajo demanda, una página se trae a memoria sólo cuando se hace referencia a una posición en dicha página.
  • Se producen muchos fallos cuando un proceso se arranca inicialmente
• Con paginacion adelantada, se traen a memoria mas paginas de las que se necesitan
  • Esta política es mas eficiente si se traen las paginas que se encuentran almacenadas en el disco de forma contigua

Algoritmos de reemplazo de páginas

• Las faltas de página forzan al cambio
  • Qué página debe ser removida.
  • Establecer espacio para la página que entra.
• Las páginas modificadas deben ser guardadas las otras pueden sobreescribirse
  • Es aconsejable no reemplazar una página usada con frecuencia, seguramente la necesitaremos.

Algoritmo óptimo de reemplazo de página

• Reemplaza la página que se requerirá en el punto más lejano.
  • Optimo pero no lograble.
• La estimación se basa en el registro de uso de las corridas anteriores de los procesos.
• Sigue siendo poco práctico.

Algoritmo de página no recientemente usada (NRU)

• Cada página tiene un bit de referencia, un bit de modificación.
• Las páginas se clasifican
  1. No referenciadas, no modificadas.
  2. No referenciadas, modificadas.
  3. Referenciadas, no modificadas.
  4. Referenciadas, modificadas.
• NRU remueve las páginas aleatoriamente desde el número más bajo en clases no vacías.

• Mantiene una lista de páginas libres para asignarle a los procesos con faltas de página.
• Lotsfree: parámetro umbral (cantidad de memoria) para empezar a paginar.
• Desfree: parámetro umbral para incrementar la paginación.
• Minfree: parámetro umbral para empezar el intercambio.
• La paginación es realizada por el proceso pageout.
• Pageout busca las páginas utilizando el algoritmo del reloj modificado.
• Scanrate es la velocidad con la cual las páginas son buscadas. Varía de slowscan a fastscan.
• Pageout se utiliza con más frecuencia de acuerdo a la cantidad de memoria libre disponible.

Buscador de páginas en Solaris 2

• Linux utiliza una variante del algoritmo del reloj para aproximarse a la estrategia de reemplazo de páginas LRU.
• El administrador de memoria utiliza dos listas enlazadas
  • La lista activa
    • Contiene las páginas activas.
    • Las páginas más recientemente usadas están cerca de la cabeza de la lista de activas.
  • La lista de inactivas
    • Contiene las páginas inactivas.
    • Las páginas menos recientemente usadas están cerca de la cola de la lista de páginas inactivas.
  • Solo se reemplazan las páginas en la lista de inactivas.