4.6 Segmentación

Hasta ahora la memoria que hemos vista es una memoria unidimensional por que las direcciones virtuales van desde 0 hasta una dirección máxima. Una solución consiste en proveer a la maquina muchos espacios de direcciones independientes, llamados segmentos.

Cada segmento consiste en una secuencia lineal de direcciones, desde 0 hasta el máximo. Cada longitud de segmento puede cambiar durante la ejecución. Los segmentos pueden crecer y encogerse de forma independiente, sin afectarse entre sí. La segmentación facilita compartir procedimientos o datos entre varios procesos.

Implementación de la segmentación pura

La segmentación es diferente a la paginación: el tamaño de pagina es fijo mientras el de los segmentos no. Después del cierto tiempo de ejecución del sistema, la memoria estará divida en trozos, unos con segmentos y otros con agujeros. Este fenómeno se llama cuadriculación o fragmentación externa, desperdicia memoria en los agujeros.

Segmentación con paginación: MULTICS

Cada programa MULTICS tiene una tabla de segmentos, con un descriptor por segmento. Un descriptor de segmento contiene una indicación de si el segmento está en la memoria principal o no.

Una dirección en MULTICS consta de dos partes: el segmento y la dirección dentro del segmento. La dirección dentro del segmento se subdivide en un numero de pagina y una palabra dentro de la pagina.

Segmentación con paginación: El Pentium de Intel

El corazón de la memoria virtual Pentium consiste en dos tablas, la LDT (tabla de descriptor local) y la GDT (tabla de descriptor global). Cada programa tiene su propia LDT, pero solo hay una GDT para todos los programas de la computadora.

4.5 Aspectos de diseño de los sistemas con paginación

El modelo del conjunto del trabajo

En la forma más pura de paginación, los procesos se inician con ninguna de sus páginas en la memoria. El proceso tiene la mayor parte de las páginas que necesita y se dedica a ejecutarse con relativamente pocas fallas de página. Este método se denomina paginación por demanda por que las paginas se cargan solo cuando se piden, no por si solas.

El conjunto de páginas que el proceso está usando actualmente es un conjunto de trabajo. Si todo el conjunto de trabajo esta en la memoria, el proceso se ejecutara sin causar muchas fallas hasta que pase a otra fase de ejecución.

La carga de las páginas antes de dejar que los procesos se ejecuten se denomina prepaginación.

Políticas de asignación Local vs. Global

Los algoritmos locales corresponden a asignar a cada proceso una fracción fija de la memoria. Los algoritmos globales reparten dinámicamente marcos de página entre los procesos ejecutables.

Los algoritmos globales funcionan mejor, cuando el tamaño del conjunto de trabajo puede variar durante la vida de un proceso. Si se emplea un algoritmo local y el conjunto de trabajo crece, habrá thrashing.

Tamaño de página

El tamaño de pagina es un parámetro que el SO puede escoger. Un tamaño de página grande hará que haya mayor proporción de programa que no se utiliza en la memoria que si usan las páginas pequeñas. El empleo de páginas pequeñas implica que los programas, y la tabla de páginas será grande.

En algunos ordenadores, la tabla de páginas debe cargarse en registros de hardware que cada CPU conmuta de un proceso a otro.

Interfaz de memoria virtual

Hasta este punto hemos notado que la memoria virtual es transparente para los procesos y los programadores. Una estrategia para los programadores para controlar su mapa de memoria es permitir que dos o más procesos compartan la misma memoria. Cuando dos o más procesos comparten las páginas, hace posible la compartición de ancho de banda: un proceso escribe en la memoria compartida y el otro la lee.

Otra estrategia de administración avanzada de memoria es la memoria compartida distribuida, es decir, que múltiples procesos en una red compartan un conjunto de páginas, como un solo espacio de direcciones lineal compartido.

4.4 Algoritmos de sustitución de páginas

Cuando ocurre una falla de pagina, el SO tiene que escoger la pagina que está fallando para sacarla de la memoria y así puede entrar la nueva página. La nueva página solo sobreescribe la que está siendo desalojada.

El algoritmo de sustitución de páginas óptimo

Se debe eliminar la pagina que contenga el rotulo más alto. Si una página no se va a si no hasta después de 8 millones de instrucciones y otra pagina no se usara si no hasta de 6 millones de instrucciones, el desalojo de la primera postergara la falla de pagina que la traerá de nuevo a la memoria lo más lejos hacia el futuro que es posible.

El algoritmo de sustitución de páginas no usadas recientemente

Los bits R y M pueden servir para construir un algoritmo de paginación sencillo.

Cuando se inicia un proceso, el SO pone en 0 los bits de todas sus pagina. Periódicamente (ej. en cada interrupción de reloj), se apaga el bit R, a fin de distinguir las paginas a las que no se ha hecho referencia recientemente de las que si se han leído.

Cuando ocurre una falla de página, el SO examina todas las páginas y las divide en cuatro categorías con base a los valores actuales de sus bits R y M:

Clase 0: no referida, no modificada

Clase 1: no referida, modificada

Clase 2: referida, no modificada

Clase 3: referida, modificada

El algoritmo de sustitución de páginas de primera que entra, primera que sale (FIFO)

El SO mantiene una lista de todas las paginas que están en la memoria, siendo la pagina que está a la cabeza de la lista más vieja, y la del final, las mas reciente.

Cuando hay una falla de página, se elimina la página que está a la cabeza de la lista, y se agrega la nueva página al final.

El algoritmo de sustitución de páginas de segunda oportunidad

Lo que realiza el algoritmo de segunda oportunidad es buscar una página vieja a la que no se haya hecho referencia en el intervalo de reloj anterior. Si se ha hecho referencia todas las páginas, este algoritmo pasa a ser FIFO puro.

El algoritmo de sustitución de páginas por reloj

Cuando ocurre una falla de página, se analiza la página a la que apunta la manecilla. Si un bit R es 0, se desaloja la página, y se inserta la nueva página en el reloj en su lugar, y la manecilla avanza una posición. Pero si R es 1, se pone en 0 y la manecilla se avanza a la siguiente pagina. Este proceso se repita hasta encontrar una página con R = 0.

El algoritmo de sustitución de páginas menos recientemente usadas (LRU)

Este algoritmo sugiere: cuando ocurra una falla de página, se desalojara la pagina que haya estado más tiempo sin usarse.

Simulación de LRU en software

El algoritmo NFU (no utiliza frecuentemente), el cual requiere un contador de software asociado a cada página y que inicialmente vale 0. NFU puede simular LRU de forma satisfactoria. Esta modificación tiene dos partes: primera todos los contadores se desplazan a la derecha un bit antes de sumarles el bit R, segunda, el bit R se suma de la extrema izquierda a la extrema derecha.