1.4.2.1. Paginación

El espacio virtual de direcciones se divide en páginas del mismo tamaño. La memoria principal se divide en páginas físicas del mismo tamaño. Estas páginas físicas son compartidas entre los distintos procesos que haya en el sistema. Un proceso tendrá unas cuantas páginas residentes en la memoria principal (activas) y el resto en la memoria secundaria (inactivas). El mecanismo de paginado cumple dos funciones:

1. Llevar a cabo la tarea de transformación de direcciones, o sea, fijar la página a la que corresponde una determinada dirección de una página, así como de la página física, si la hay, que ocupa esta página.
2. Transferir páginas de la memoria secundaria a la memoria principal cuando haga falta, y de la memoria principal a la memoria secundaria cuando ya no sean necesarias.

1.4.2.2. Segmentación

Consiste en dividir el espacio de direcciones en segmentos, cada uno de los cuales corresponderá a una rutina, un programa o un conjunto de datos. Ello se puede conseguir añadiendo varios pares de registros límite y de base a cada procesador de forma que el espacio de direcciones pueda dividirse en varias áreas diferentes. El conjunto de registros base y límite formará una tabla llamada tabla de segmentos.

Inconveniente: el número de segmentos, por razones económicas, es necesariamente pequeño. Hace falta un convenio que permita establecer qué segmentos se utilizarán para cada fin.

1.5. Estrategias de Gestión de Memoria

Las políticas para la gestión de la memoria pueden agruparse en tres grupos:

• Políticas de sustitución
• Políticas de carga
• Políticas de ubicación

1.5.1. Políticas de Sustitución

Son las que determinan qué información hay que sacar de la memoria principal, o sea, son las responsables de la creación de zonas de memoria libres.

Políticas de sustitución para sistemas paginados

Los bloques de información a sustituir son páginas. Tres algoritmos habituales de sustitución son:

1. Algoritmo del utilizado menos recientemente (LRU). Sustituir la página que haga más tiempo que no ha sido utilizada.
2. Algoritmo del utilizado menos frecuentemente (LFU). Sustituir la página que se haya utilizado menos en el transcurso de un determinado intervalo de tiempo inmediatamente anterior.
3. Algoritmo del primero en entrar, el primero en salir (First-in First-out). Sustituir la página que haya estado residente más tiempo.

Políticas de sustitución para sistemas no paginados

Los bloques de información a sustituir son segmentos (entendiéndose éstos como el espacio de dirección de un proceso). Existe la salvedad de que no todos los segmentos ocupan la misma cantidad de memoria, con lo que la consideración del segmento a relegar a la memoria secundaria vendrá influida por el tamaño del segmento a cargar.

El algoritmo más sencillo consiste en sustituir el segmento (si es que existe) que junto con los espacios libres que tenga adyacentes, libere suficiente memoria para el nuevo segmento. Si hay varios segmentos de estas características, interviene alguno de los criterios anteriores (tal como LRU) para elegir uno de ellos. Si no hay ningún segmento, habrá que sustituir varios.

1.5.2. Políticas de Carga

Son las que determinan cuándo hay que cargar información en la memoria principal. Se dividen en dos grandes categorías:

• Las de demanda: La falta de un bloque provoca una petición de carga, con lo que los algoritmos de ubicación y/o sustitución harán sitio en la memoria para el nuevo bloque.
• Las anticipatorias: Cargan los bloques por adelantado, por lo que deben basarse en predicciones del comportamiento futuro del programa. Estas predicciones pueden realizarse en base a 2 criterios:
  1. La naturaleza de la construcción del programa, refiriéndose esto al principio de localidad.
  2. La inferencia basada en el comportamiento pasado.

1.5.3. Políticas de Ubicación

Son las que determinan en qué lugar de la memoria principal hay que colocar la información leída, o sea, deben elegir una parte de la zona de memoria libre.

Políticas de ubicación para sistemas paginados

Para colocar k páginas solo hay que recurrir al algoritmo de sustitución, con el fin de liberar k páginas físicas.

Políticas de ubicación para sistemas no paginados

Se tendrá una lista de agujeros (espacios libres de memoria). Su tarea consiste en decidir qué agujero utilizar y en actualizar la lista de agujeros después de cada inserción. Si el bloque a cargar es menor que el agujero, este se colocará en la parte izquierda o extremo inferior del agujero. Esta técnica minimiza la fragmentación de este agujero.

Si es mayor, el algoritmo de ubicación trasladará los bloques que están en memoria para crear un agujero lo suficientemente grande.

Principales algoritmos

Sea x1, x2, x3,…, xn la lista de agujeros.

1. Algoritmo del mejor ajuste. Se ordenan los agujeros por tamaños crecientes. Si s es el tamaño del bloque a colocar, hay que determinar la menor i tal que s ? xi
2. Algoritmo del peor ajuste. Se ordenan los agujeros por tamaños decrecientes. Se coloca el bloque en el primer agujero, y el resto del agujero se incorpora en la posición correspondiente de la lista.
3. Algoritmo del primer ajuste. Se ordenan los agujeros por dirección de base crecientes. Si s es el tamaño del bloque a colocar, hay que determinar la menor i tal que s ? xi
4. Algoritmo recursivo. Los tamaños de los bloques deben ser potencias de 2, s = 2i, i ? k. Los agujeros agrupados en listas por tamaños: 21, 22,…, 2k Puede sacarse un agujero que esté en la lista (i+1) partiéndolo por la mitad, dando lugar a dos agujero de tamaño 2i en la lista i. Y al contrario, compactar agujeros.