Sistemas Paginados

Desventajas de la paginación:

• Fragmentación interna (espacio desperdiciado al final de la última página física, cosa grave si el tamaño de página es grande).
• Fragmentación de la tabla (espacio de memoria física desperdiciado en almacenar las tablas de páginas, cosa grave si el tamaño de página es pequeño).

El tamaño de página práctico se sitúa entre 128 y 1024 palabras (entre 512 y 8192 bytes), siendo la ubicación totalmente asociativa.

Algoritmo de Carga

¿Cuándo debe transferirse una página virtual desde la memoria secundaria a la primaria?

Soluciones:

1. Carga por demanda: la página virtual se carga en la memoria principal cuando es referenciada y produce un fallo de página. Método simple y no sobrecarga el canal de paginación. Usual en microprocesadores de 16 y 32 bits.
2. Precarga: como consecuencia de un fallo de página, se carga en memoria principal la página fallada junto con otras adicionales. Es un método predictivo, se precargan aquellas páginas que producirían fallos en el futuro. El número de páginas precargadas depende de la organización de la información en la memoria secundaria, del tipo de interfaz entre la memoria principal y la secundaria, y del tamaño de la memoria principal asignada y si es de tamaño constante. Normalmente se carga una sola página.

Algoritmo de Reemplazo

Controlado por el Sistema Operativo. (Aproximaciones teóricas: FIFO, LRU… . Aproximaciones prácticas: LFU, NUR…).

Inconvenientes de la Paginación

Las páginas son de tamaño fijo y arbitrario: no tienen relación con la estructura lógica del programa. Puede haber datos en una página no relacionados con los demás. Ineficiencia por el principio de localidad.

Sistemas Segmentados

Sistema de memoria virtual que considera bloques de tamaño desigual, definidos en función de la estructura lógica del código y datos del programa (procedimientos, funciones, arrays, matrices). Cada bloque se denomina segmento.

La mayoría de las características (conceptos) de los sistemas segmentados son similares a las de los sistemas paginados.

Traducción de Direcciones

• Direcciones virtuales: (s_i,d_j) s_i número de segmento; d_j desplazamiento.
• Tabla de segmentos: contiene información para traducir el número de segmento a una dirección física de comienzo del segmento. Sus entradas contienen información similar a la contenida en las entradas de las tablas de página, junto con la longitud del segmento.
• Fallo de segmento: referencia a un segmento no residente en la memoria principal.
• Tipos de traducción: los mismos que en los sistemas paginados (directa, asociativa o híbrida) con la diferencia de que el desplazamiento se SUMA (no se concatena).

Fallos de Segmento

Es necesario determinar si hay espacio de memoria principal para ubicar el segmento virtual fallado (este problema no existe en los sistemas paginados).

Solución: estructurar la memoria principal definiendo dos listas encadenadas similares (lista de segmentos reservados, lista de segmentos libres (LAVS) normalmente en orden ascendente de su posición).

Espacio Virtual vs Paginado

• Un sistema segmentado es un espacio bidimensional: los segmentos son bloques de direcciones virtuales contiguas, pero los segmentos no son contiguos entre sí.
• Se produce una excepción al intentar acceder a una posición fuera del segmento.

Comparticion de los Segmentos

Posibilidad de compartición de segmentos:

1. Un segmento compartido es referenciado por 2 procesos mediante el mismo número.
2. Un segmento compartido es referenciado por 2 procesos mediante números diferentes: esquema más versátil, implementado permitiendo una tabla de segmentos privada a cada proceso y puede necesitarse que el segmento compartido genere números de segmento dependientes del contexto.

Algoritmos de Carga y Ubicación

El proceso de carga es similar a los sistemas paginados, siendo el proceso de ubicación más complejo.

Los algoritmos de ubicación están todos basados en la lista de LAVS (list of available segments):

1. FIRST-FIT: hace uso de la lista LAVS. El segmento solicitado no residente se coloca en el primer segmento libre de la memoria principal donde quepa (búsqueda en orden ascendente de direcciones físicas). Si el procesador solicita el segmento S no residente de tamaño L se realizan las siguientes acciones:
   1- Sea Q <– FIRST (puntero inicial de LAVS).
   2- Si TAMAÑO(Q) > L, S se coloca a partir de la dirección física Q+TAMAÑO(Q)-L. Se actualiza TAMAÑO(Q) a TAMAÑO(Q)-L.
   3- Si TAMAÑO(Q)=L, S se coloca a partir de la dirección física Q. Se borra el segmento libre de LAVS.
   4- Si TAMAÑO(Q)<L, se asigna Q<–SIGUIENTE(Q) y se va a 2.
   Para evitar la formación de segmentos libres demasiado pequeños, se cambian:
   2- Si TAMAÑO(Q)>L+C…
   3- Si L<=TAMAÑO(Q)<=L+C.
2. BEST-FIT: hace uso de la lista LAVS. El segmento solicitado no residente se coloca en el segmento libre de la memoria principal más pequeño donde quepa. El procedimiento de ubicación es el mismo que el del algoritmo first-fit, pero previamente, se ordena la lista LAVS según el orden creciente de los tamaños de los segmentos libres. Necesidad de ordenación.
3. WORST-FIT: hace uso de la lista LAVS. El segmento solicitado no residente en memoria se coloca en el mayor de los segmentos libres de la memoria principal. El procedimiento de ubicación es similar al del algoritmo Best-fit salvo que la lista LAVS se ordena en orden decreciente de los tamaños de los segmentos libres.
4. BINARY-BUDDY: tamaño de segmento y LAVS potencia entera de 2. Hace uso de la lista LAVS. Procedimiento de ubicación –> se divide la lista LAVS en n listas (2ⁿ es el tamaño máximo de los segmentos), la i-ésima lista encadena los segmentos libres de tamaño 2ⁱ (buddies), las n listas pueden restructurarse de 2 formas [a) un segmento libre de la lista (i+1)-ésima se divide en 2 segmentos iguales y se encadenan a la lista i-ésima; b) proceso inverso al a)]. Desarrollo de un algoritmo de ubicación basado en las n listas anteriores y sus dos mecanismos de reestructuración.

Comparación de los Algoritmos de Ubicación

• Best-Fit: minimiza el tamaño del segmento libre sobrante tras la ubicación. Es la peor de las elecciones, genera muchos espacios libres pequeños que no serán de utilidad.
• Worst-Fit: basado en la idea de que tras la ubicación, el segmento libre sobrante es suficientemente grande como para ser útil.
• MÁS EFICIENTES: First-Fit y Binary Buddy.
• Inconvenientes asociados a la ubicación: fragmentación externa –> pérdida de espacio de memoria física debido a la producción de segmentos libres sobrantes de tamaño muy pequeños (inútiles).

Compactación o Reemplazo

Cuando se solicita un segmento no residente, pueden darse 2 situaciones: que se encuentre un segmento libre de tamaño suficiente (ubicación) o que no se encuentre tal segmento libre (compactación o reemplazo).

• Compactación (garbage collection): se redisponen los segmentos libres de forma contigua en una zona de la memoria física (se crea un único segmento libre de gran tamaño) con los problemas de que hay un gran consumo de tiempo y que tiene asociada una actualización de las tablas de segmentos.
• Reemplazo: similar al reemplazo de los sistemas paginados. Única diferencia –> debe tenerse en cuenta el tamaño de segmento solicitado. Problemas –> uso poco eficiente de la memoria física y el segmento reemplazado puede necesitarse en un futuro.
• La relación entre compactación y reemplazo no es simple: depende de cada situación particular.
• Tamaño de los segmentos: los segmentos pueden ser desmesuradamente grandes –> Solución: limitar el tamaño de los segmentos o paginar los segmentos (segmentación con paginación).

Sistemas Segmentados con Paginación

Hoy en día, pocos sistemas usan segmentación pura debido a los problemas para efectuar los reemplazos. Enfoque híbrido: segmentos paginados –> simplifica el reemplazo (no se precisa que la memoria de un segmento sea contigua y no es preciso cargar los segmentos enteros en memoria).

• Los segmentos se dividen en un número entero de páginas –> segmentación lineal (domina paginación) o segmentación nominal (domina segmentación).
• Dirección virtual: (s_i, p_j, d_k) espacio tridimensional –> s_i es el número de segmento virtual, p_j es el número de página virtual, d_k es el desplazamiento dentro de la página.
• PTS apunta a la tabla de segmentos del proceso en curso. Límite es el campo que indica el tamaño de cada segmento. Los bits de protección están a nivel de páginas (no es necesario en segmentación nominal). Flag indica la residencia en memoria principal asignada de cada página.
• DOS traducciones: elevado coste temporal –> Soluciones: uso de TLB o uso de registros rápidos.
• El fallo de página se resuelve de la misma forma que en los sistemas puramente paginados –> Problema: fallo en el acceso a la tabla de páginas –> lentifica –> 2 fallos.

Paginación vs Segmentación

**En los algoritmos de ubicación en los ejemplos, los datos entre paréntesis, el 1º es la dirección que empieza el segmento libre y el 2º es su tamaño**