4.2 Carga de programas y reubicación

Las tablas de páginas o segmentos proporcionan reubicación dinámica a nivel de
página o de segmento. En paginación, el cargador busca marcos de página libres en
memoria, carga las páginas del programa, crea la tabla de páginas con lacorrespondencia y carga su dirección en el PTBR. En segmentación el proceso es
similar, salvo que requiere la asignación de huecos adecuados al tamaño de cada
segmento del programa, así como la colaboración del compilador y el montador para
establecer los tamaños.

4.3 Gestión

La traducción de direcciones, un mecanismo complejo y crítico para el rendimiento,
ha de gestionarse a nivel hardware, genéricamente por una unidad de gestión de
memoria (MMU).
La memoria libre en segmentación se gestiona bajo los criterios de las particiones de
tamaño variable, mientras que en paginación es adecuado un mapa de bits.
La paginación presenta fragmentación interna en las páginas. Esto no ocurre en la
segmentación, si bien ahora aparece fragmentación externa al utilizar unidades de
ubicación de tamaños diferentes. Ya que el tamaño de los segmentos es típicamente
mayor que el de las páginas, el problema de la fragmentación en la segmentación es
más importante.
El mismo mecanismo permite que los programas compartan páginas o, más
propiamente, segmentos. Por ejemplo, una única copia de código puede compartirse
por varios programas simplemente haciendo que las entradas correspondientes alsegmento de código en sus tablas de segmentos (o el conjunto de entradas de sus
tablas de páginas, en paginación) coincidan. Los bits de sólo lectura estarán activados, para evitar que un programa pueda corromper el código.

4.4 Sistemas combinados

Para evitar el problema de la fragmentación externa en segmentación pura, y para
evitar el tener cargada una tabla de páginas demasiado grande en paginación,
aparecen sistemas que combinan paginación y segmentación. Se denominan sistemas
de segmentación paginada (o segmentado-paginados) o de paginación segmentada
(o paginado-segmentados), según se entienda que los segmentos se dividen en
páginas o que la tabla de páginas se segmenta en varias, respectivamente4. La
dirección lógica se divide en tres partes: número de segmento, de página y
desplazamiento dentro de la página. El número de segmento identifica en la tabla de
segmentos la dirección base de una tabla de páginas, que se direcciona mediante el
número de página para obtener el marco de página en memoria, según se ilustra en
la Figura 4.5. El cálculo de la dirección lógica es ahora más complejo y lento,requiriendo dos indirecciones. El soporte hardware para traducción (TLB) es ahora
aún más importante.
Son también habituales los sistemas doblemente paginados (con dos niveles de
paginación), que siguen un esquema parecido. Generalizando, se pueden concebir
sistemas que dividen la dirección virtual en más de tres partes, especificando
diferentes niveles de paginación y/o segmentación5.

5 Enlace dinámico

La necesidad de ejecutar programas de tamaño mayor que la memoria física
disponible ha originado a lo largo de la historia la introducción de sofisticados
mecanismos de gestión de la ubicación de programas en memoria. Un primer
enfoque es el de dividir en programa en varios módulos, denominados overlays o
solapamientos, a partir de su estructura y cargar dinámicamente sólo aquellos que se
necesiten. La carga de un solapamiento la realiza una rutina de enlace, que se
encarga también de seleccionar el(los) solapamiento(s) reemplazado(s), si se requiere
espacio para la carga. Tradicionalmente, el programador determinaba qué rutinas
constituían los solapamientos, construía la rutina de enlace y las tablas de rutinas de
los solapamientos, y elaboraba el programa de forma que las llamadas a las rutinas
de los solapamientos se llamasen a través de la rutina de enlace. También eran suyos
los criterios de reemplazo de los solapamientos.
El enfoque alternativo al problema es la memoria virtual, más general y
completamente transparente al programador, al que dedicaremos la siguiente
Sección.
Sin embargo, una evolución de los overlays ha quedado en los sistemas de hoy en día
para cubrir un objetivo diferente del originalmente asignado a aquellos: las rutinas
de enlace dinámico6.
Una librería de enlace dinámico es un conjunto de rutinas agrupadas en módulos que
se cargan dinámicamente en el momento de la llamada, como ocurría en los overlays,
pero de forma transparente al programa. El sistema operativo proporciona como
soporte una llamada al sistema donde se especifica como parámetro la rutina de
enlace dinámico a ejecutar. Cuando en un programa aparece una llamada a una
rutina de este tipo, el montador, en vez de enlazar estáticamente a la rutina en el
código ejecutable, enlaza a la llamada al sistema. Cuando esta llamada al sistema seejecuta, comprueba si el módulo que contiene la rutina especificada como parámetro
está cargado en memoria. Si no lo está, lo carga y establece la referencia (indirecta)
desde el programa. A esto se le llama montaje dinámico o en tiempo de ejecución.
Se requiere una tabla que especifique el estado de cada módulo de enlace dinámico
(cargado o no) y la dirección de memoria donde se carga. En principio, hay que
destinar un espacio de memoria específico para los módulos de enlace dinámico, y
proporcionar una política de reemplazo, pero cuando se combina con memoria
virtual, que es lo habitual hoy en día, el reemplazo se realiza página a página de
forma integrada en el propio mecanismo de memoria virtual.
Aunque esta técnica se podría utilizar con el mismo objetivo de los overlays,
actualmente, ya que todos los sistemas tienen soporte de memoria virtual, el enlace
dinámico se utiliza por otros motivos:
· Los ficheros ejecutables de los programas almacenados en disco son más
pequeños. Esto tiene cierta importancia si se tiene en cuenta que hoy en día los
programas hacen un amplio uso de rutinas que consumen un gran volumen
de espacio, como por ejemplo las rutinas de tratamiento gráfico.
· Las rutinas de enlace dinámico cargadas en memoria se comparten por varios
programas, lo que permite ahorrar espacio también en memoria.
· El tiempo de carga de los programas, y por lo tanto su latencia, es menor.
· Facilita la actualización de las aplicaciones. La instalación de una nueva
aplicación aporta nuevas versiones de las librerías de enlace dinámico (por
ejemplo, rutinas de tratamiento gráfico más elaborado) que sustituyen a las
versiones antiguas, de lo que se benefician otras aplicaciones que usan dichas
rutinas

6 Memoria virtual

La memoria virtual es el mecanismo más general para la ejecución de programas no 

enteros en memoria. Se basa en un sistema de paginación (o combinado) en el que 

sólo un subconjunto de las páginas del programa están cargadas en memoria. El 

resto reside en un dispositivo de almacenamiento secundario, análogamente al de 

swap7

. La memoria virtual presenta, adicionalmente a su  capacidad para ejecutar 

programas mayores que la memoria física disponible, un conjunto de interesantes 

ventajas con respecto a la paginación con programas enteros: 

• Reduce la latencia en la ejecución de los programas, al no tener éstos que 

cargarse completamente para comenzar a ejecutarse. 

• Permite gestionar más eficientemente la memoria física. Cualquier espacio 

libre, incluso una única página, puede ser aprovechado para cargar un nuevo 

programa y comenzar a ejecutarlo. Por otra parte, si una página de un 

programa no se referencia durante la ejecución, no habrá que cargarla. 

• Al aumentar el grado de multiprogramación a costa de reducir el número de 

páginas cargadas de cada programa, permite incrementar la eficiencia de la 

CPU en sistemas multiprogramados

8

. 

• Ahora la independencia de los programas con respecto a la máquina es 

completa. Además del direccionamiento virtual que aporta la paginación, la 

cantidad de memoria física disponible para ejecutar el programa sólo es 

relevante para la velocidad de ejecución del programa.  

6.1 Soporte hardware

Además del soporte hardware para la traducción de direcciones de los sistemas
paginados, la memoria virtual requiere mecanismos hardware adicionales:
• Espacio para paginación en un dispositivo de almacenamiento secundario
(disco).
• Bit de validez, V. Para cada entrada de la tabla de páginas es necesario un bit
que indique si la página correspondiente está cargada en memoria o no.
• Trap de fallo de página. Cuando la página referenciada no está cargada en
memoria, el mecanismo de interrupciones produce el  salto a la  rutina de
tratamiento del fallo de página (que promoverá la carga de la página en
memoria). A diferencia de una interrupción normal, el fallo de página puede
ocurrir en cualquier referencia a memoria durante la ejecución de la
instrucción, por lo que la arquitectura debe proporcionar los mecanismos
adecuados para establecer un estado del procesador consistente antes de saltar
a la rutina de tratamiento.
• Información adicional para la gestión del fallo de  página (bit de página
modificada, referenciada, …). Se verá más adelante.

6.2 Carga de programas y reubicación

El cargador carga la tabla de páginas del programa  y una o más páginas,
estableciendo las direcciones de las páginas cargadas en las entradas de la tabla de
páginas y los valores de los bits de validez. Almacena también las direcciones de
disco donde se encuentran las páginas no cargadas en memoria. Como en
paginación, la reubicación se hace independientemente para cada página, cuando
éstas se cargan tras un fallo de página.
Básicamente, hay dos estrategias para cargar las páginas de un programa:
(a) Cargar sólo la primera página de código y dejar que el resto se cargue por fallo
de página (paginación por demanda).
(b) Cargar un cierto número de páginas o todas, dependiendo de la memoria
disponible y del tamaño del programa (prepaginación).

6.3 Gestión

El proceso de direccionamiento en un sistema de memoria virtual combina el
mecanismo hardware de traducción de direcciones siguiendo el mecanismo habitual
de paginación pura o combinada, con la intervención del sistema operativo cuanto se
produce un fallo de página. En la referencia a memoria se comprueba el estado del
bit de validez. Si está activado, la página está cargada y el proceso de traducción
hardware acaba proporcionando la dirección física; en caso contrario, el trap de fallo
de página aborta la ejecución de la instrucción en curso9
 y provoca el salto a la rutina
de tratamiento del fallo de página, que ejecuta los siguientes pasos:
 (1) Si la dirección generada por el programa no es correcta10
, se aborta la ejecución
del programa. Si se trata de una dirección correcta, se busca un marco de
página libre en memoria donde cargar la página referenciada. Si no hay
marcos libres, se consigue uno expulsando una página de memoria. La
elección de ésta (página víctima) se realiza mediante un  algoritmo de
reemplazo. El reemplazo de una página, que se estudiará más  adelante,
implica escribir en disco la página víctima si ésta hubiera sido modificada.
(2) Se programa la lectura de la página referenciada en el dispositivo de
paginación. En los sistemas multiprogramados se produce un cambio de contexto: el proceso que ha provocado el fallo de página pasa a estado
bloqueado y se planifica otro proceso.
(3) Mientras el programa está bloqueado, se lee por DMA en el dispositivo de
paginación la página buscada y se carga en el marco libre seleccionado.
(4) Finalizada la carga, se actualiza la entrada de la tabla de páginas y el bit de
validez asociado. El proceso bloqueado por fallo de página pasa a preparado
para ejecución. Dependiendo de la política de planificación de procesos, el
proceso puede tener la oportunidad de entrar a ejecución.

6.4 Evaluación del rendimiento

Como podemos deducir del apartado anterior, el tratamiento de un fallo de página es
muy costoso en tiempo comparado con un acceso a memoria paginada. Hay que
tener en cuenta que en la actualidad un tiempo de acceso a memoria paginada típico
(tm) es del orden de 10-7
 segundos o menos, mientras que el tiempo de tratamiento de
un fallo de página (t
f
) es del orden de la decena de milisegundos (básicamente el
tiempo de acceso a disco), es decir cinco órdenes de magnitud superior.
Si la probabilidad de fallo de página es  pf
, el tiempo medio de acceso a memoria
virtual (tv) se calcula como:
tv = tm + pf
 t
f
Para hacernos una idea de en qué órdenes debe moverse la probabilidad de fallo de
página para que el rendimiento del sistema no se resienta demasiado, vamos a partir
de la relación de tiempos tv/tm. Obsérvese que tv/tm – 1 expresa una medida de la
pérdida de rendimiento relativa a tm resultante de introducir en un sistema paginado
memoria virtual, en tanto por 1. Despejando pf
 en la expresión de arriba, podemos
expresarla en función de esta relación:
pf
 = (tv/tm –1) (tm/t
f
)
Por ejemplo, si se pretende que la pérdida de rendimiento en el acceso a memoria
con memoria virtual no supere el 10% con respecto al tiempo de acceso en el mismo
sistema sin memoria virtual, la probabilidad de fallo de página debería ser:
pf
 < 0,1 (tm / t
f
)
que para la relación típica tm/t
f
 de 5 órdenes de magnitud razonada más arriba, da
una probabilidad del orden de 10
−6
.
Afortunadamente, hay algunos factores que permiten matizar estos resultados:

• Si el sistema no fuese de memoria virtual, debería cargar inicialmente todo el
programa, lo que supone un tiempo equivalente al de tratar tantos fallos de
página como páginas tiene el programa.
• La localidad espacial de los programas y el tamaño de las páginas (típicamente
de varios Kb en la actualidad) aseguran que, cargadas las primeras páginas,
habrá gran cantidad de referencias a ellas antes de producir un fallo.
• En sistemas multiprogramados, la CPU puede ejecutar otros procesos
mientras se atiende un fallo de página.
• Con relación a otros niveles de la jerarquía de memoria (por ejemplo la
memoria cache), en memoria virtual el espacio destinado en disco para área de
paginación ha de configurarse de forma que no sea mucho mayor que el
espacio la memoria física disponible
11
.
Una política de reemplazo de páginas adecuada explotará ventajosamente la
localidad temporal de los programas, haciendo posible un rendimiento razonable.

6.5 Reemplazo de páginas

Como hemos visto, cuando se produce un fallo de página y no hay marcos libres es
necesario liberar uno de los marcos de página ocupados para poder cargar la página
referenciada. Los pasos a seguir son los siguientes:
(1) Se selecciona la página víctima mediante un  algoritmo de reemplazo que
ejecute una política de reemplazo determinada.
(2) Si la página víctima había sido modificada durante su estancia en memoria,
hay que escribirla en el dispositivo de paginación  (page-out). Si no, esta
operación no es necesaria. Para la gestión de páginas modificadas se asocia un
bit de página modificada para cada marco de página, que se activa cada vez
que se accede a memoria para escritura.
(3) Se pone a cero el bit de validez correspondiente a la página víctima en su tabla
de páginas.
A continuación se sigue con el tratamiento del fallo de página como se describió
anteriormente, leyendo del dispositivo de paginación la página que provocó el fallo y
cargándola en el marco libre (page-in).

6.6 Políticas de reemplazo de páginas

Los criterios a seguir para implementar un algoritmo de reemplazo de páginas son
fundamentalmente dos:
• Minimizar el número de fallos de página, como se ha razonado en el apartado
anterior. Explotar la localidad temporal de los programas será fundamental.
• Sencillez de implementación. Un algoritmo complejo, como veremos, puede
requerir intervención adicional en los accesos a memoria, lo que implicará o
pérdida de rendimiento, o un hardware costoso, lo que a su vez redundará
probablemente en pérdida de rendimiento12
.
A continuación se describen las políticas de reemplazo de páginas. Para probar los
algoritmos de reemplazo y así poder evaluar su rendimiento comparativo se utiliza
una  secuencia de referencias a páginas (finita y determinista
13
), que permite
determinar la tasa de fallos de página para cada algoritmo. Para simplificar, se
considera que las referencias son producidas por un único programa. El Ejercicio 7
incluye una secuencia de referencias que permitirá probar el comportamiento de los
algoritmos. Como se verá más adelante, en multiprogramación es necesario
considerar que un conjunto de secuencias de referencias se intercalan en el tiempo.

6.6.1 Política óptima

En un algoritmo de reemplazo óptimo en cuanto al número de fallos de páginas, la
página víctima a seleccionar será aquélla que más tiempo va a tardar en ser
referenciada. Desafortunadamente, determinar las referencias a memoria futuras es
irresoluble en la práctica, por lo que los algoritmos de reemplazo reales se basan
habitualmente en el comportamiento pasado de las referencias a memoria, confiando
en la propiedad de localidad temporal de los programas.

6.6.2 Política FIFO

Se elige como página víctima la que más tiempo lleva cargada.
La implementación puede hacerse mediante una cola FIFO de marcos de página, que
se actualiza cada vez que se carga una página. Una  alternativa es elegir la víctima
sobre la base de un registro que almacena el tick en que se produjo la carga, lo que
proporciona una aproximación a FIFO.
Al no basarse en criterios de localidad, FIFO no obtiene buenos resultados en cuanto
a probabilidad de fallo. Además, presenta un problema conocido como anomalía de
Belady, un fenómeno de pérdida de rendimiento (mayor número de fallos de
página), que presentan algunos algoritmos de reemplazo con determinadas
secuencias de referencias cuando se incrementa el número de marcos de página en
memoria. Esto ocurre, por ejemplo, con la siguiente secuencia:
1  2  3  4  1  2  5  1  2  3  4  5
En concreto, con esta secuencia se producen más fallos de página con cuatro marcos
que con tres.

6.6.3 Política LRU

De acuerdo al principio de localidad temporal en las referencias (es más probable la
referencia a una página cuanto más recientemente se haya referenciado), se
selecciona como página víctima la  menos recientemente referenciada. Nótese que ello
implica modificar en cada referencia la información acerca de las páginas cargadas, a
diferencia del algoritmo FIFO, que sólo requiere hacerlo en la carga de cada página.
Esta característica hace de LRU un  algoritmo de pila. Los algoritmos de pila
presentan la propiedad de que, dada una secuencia de referencias, una memoria con
más marcos de página, tras un número determinado de referencias, mantiene el
conjunto de páginas que contendría con un tamaño menor en la misma referencia. En
otras palabras, la tasa de fallos nunca aumenta si  se incrementa el tamaño de
memoria. Los algoritmos de pila evitan la anomalía de Belady.
La implementación hardware de la política LRU es compleja. Hay dos mecanismos:
(a) Mantener una lista encadenada de páginas ordenadas por el tiempo de su
última referencia.
(b) Mantener un contador de referencias y un registro (de al menos 64 bits)
asociado a cada marco de página, que se actualiza en una referencia con el
valor del contador.
En ambos casos la implementación es muy costosa, por lo que, como alternativa al
algoritmo LRU puro se utilizan aproximaciones. Un mecanismo de aproximación
consiste en almacenar el tick de reloj en el que se produce la referencia en vez de la
propia referencia, para lo que se requiere un bit de referencia asociado a cada marco
en base al cual la rutina de atención al reloj puede determinar si la página ha sido referenciada desde el tick anterior y actualizar el registro de ticks de última


referencia a la página, que puede implementarse por software. Con esta
aproximación se pierde precisión, al convertir la relación de orden total entre las
referencias en una relación de orden parcial (las referencias dentro de un mismo tick
no están ordenadas).
Algunos de los siguientes algoritmos también son aproximaciones a LRU.

6.6.4 Segunda Oportunidad

Se distingue entre páginas que han sido referenciadas y páginas que no lo han sido.
Si, siguiendo un orden determinado, una página debería ser seleccionada como
víctima y ha sido referenciada, se deja en memoria, pero se marca como no
referenciada. Será candidata a página víctima en el próximo fallo si no vuelve a ser
referenciada antes.
Se requiere un bit de referencia, R, por marco de página, que se activa cuando se
referencia la página. La política de la segunda oportunidad se puede implementar
mediante el algoritmo del reloj. Los marcos se organizan en orden circular con un
puntero a uno de ellos. Cuando ocurre un fallo, si el bit R correspondiente está a cero
se elige esa página como víctima. Si no, R se pone a cero y se apunta al siguiente.

6.6.5 NRU

Se elige como página víctima una no usada recientemente.
Se mantienen dos bits por página:
R referenciada/no referenciada
M modificada/no modificada
Cuando una página se carga, sus bits R y M se ponen a cero. El bit R de una página se
activa cuando ésta se referencia. El bit M se activa si la referencia es para escritura.
Periódicamente (por ejemplo, con cada tick de reloj), todos los bits R se ponen a cero.
De acuerdo a estos bits, se pueden establecer cuatro categorías de páginas, según su
grado de candidatura para ser elegidas páginas víctimas:
(1) no referenciadas y no modificadas
(2) no referenciadas y modificadas
(3) referenciadas y no modificadas
(4) referenciadas y modificadas


Entre páginas de una misma categoría puede aplicarse cualquier criterio de elección.
Presenta el problema de que en los momentos inmediatamente posteriores a la
puesta a cero del bit R incluso páginas que están siendo actualmente referenciadas
son susceptibles de ser elegidas como víctimas.

6.6.6 NFU

En el algoritmo NFU (página  no referenciada frecuentemente), se establece si en un
intervalo de tiempo (por ejemplo, un tick de reloj) una página ha sido o no
referenciada. Se lleva la cuenta del número de intervalos que cada página ha sido
referenciada, eligiendo como víctima la de cuenta más baja.
Para cada página se requiere, además del bit R que se activa en cada referencia, un
contador. En cada tick de reloj, para cada página, el bit R se acumula en el contador.
Comparado con LRU puro, en NFU los contadores se incrementan con mucha menor
frecuencia, por lo que es implementable en software.
NFU, al recordar todas las referencias, no prima la localidad temporal de los
programas, por lo que páginas que se han usado mucho en un pasado lejano
permanecen en memoria por delante de páginas que están comenzando a usarse
intensamente en el momento del fallo.

6.6.7 Envejecimiento

Como una mejora de NFU, se puede introducir un parámetro de olvido (o
envejecimiento) sobre las referencias pasadas.
Un mecanismo para implementar el envejecimiento consiste en desplazar los
contadores un bit a la derecha en cada tick de reloj, introduciendo el bit R por la
izquierda. De esta forma, una página referenciada durante el último tick
permanecerá en memoria sobre cualquiera que no lo haya sido.

6.7 Memoria virtual y multiprogramación

Hasta aquí hemos descrito la paginación en sistemas de memoria virtual de manera
simplificada. Se ha supuesto que la gestión de páginas se hace de acuerdo a una
secuencia de referencias única, como si fuese obtenida por un único programa. Esto
es perfectamente válido en monoprogramación. Como veremos, en sistemas
multiprogramados es muy interesante considerar qué  programa genera cada
referencia, lo que equivale a tener una secuencia de referencias para cada programa.
Para una secuencia de referencias única, la elección de la página víctima sólo tiene
sentido entre todas las páginas de memoria. En cambio, en sistemas multiprogramados, donde cada programa genera su propia secuencia de referencias,

la localidad se mantiene entre las páginas de un mismo programa, pero no
globalmente. Por lo tanto, parece una alternativa razonable considerar de manera
independiente la secuencia de referencias de cada programa para seleccionar la
página víctima. El subconjunto de páginas al que se aplica el algoritmo de reemplazo
determina lo que se conoce como rango de asignación.
En sistemas multiprogramados, el rango de asignación y otros criterios de la gestión
de la memoria virtual determinan en cierta medida el grado de multiprogramación
del sistema, y por lo tanto influyen decisivamente en la planificación de procesos. En
los siguientes apartados estudiaremos los aspectos relacionados con la asignación de
páginas en sistemas operativos multiprogramados.

6.7.1 Rango de asignación

La gestión de la memoria virtual para un sistema operativo multiprogramado debe
determinar entre qué páginas se aplica el algoritmo de reemplazo. Hay dos políticas
alternativas:
(a)  Asignación global. Las referencias generadas por todos los programas se
consideran como una secuencia de referencias única, de forma que un fallo de
página producido por un programa puede provocar que salga de memoria
una página de otro programa (esta será la elección más probable para la mayor
parte de los algoritmos de reemplazo, ya que las páginas del proceso en
ejecución son precisamente las más recientemente referenciadas).
 (b)  Asignación local. El algoritmo de reemplazo se aplica exclusivamente entre
las páginas del proceso. Hay que establecer los criterios para el reparto de los
marcos de página entre los procesos. Fundamentalmente hay dos
posibilidades:
(b1) Igual número de marcos para cada proceso. Si hay M marcos de página
y N programas, cada programa dispone de M/N marcos de página. Este
criterio penaliza excesivamente a los programas de gran tamaño.
(b2) Asignación proporcional. Si un proceso i ocupa si
 páginas, definiendo
S=Σsi
  como la suma del tamaño de los N procesos (S>M), la asignación
de páginas para el proceso i, ai
, será:
ai = (si
/S ) M
 Este criterio se puede combinar con la prioridad del proceso.

Las alternativas descritas son extremos entre los que caben soluciones intermedias.
Por ejemplo, la asignación global se puede suavizar introduciendo límites (máximos
y mínimos) en el número de marcos de página que tiene asignado cada proceso.

http://www.sc.ehu.es/acwlaroa/SO2/Apuntes/Cap4.pdf

6.7.2 Sobrepaginación

Debido a que la memoria virtual permite la existencia de programas no enteros en 

memoria, la capacidad de la memoria física deja de ser un factor limitante del grado 

de multiprogramación. De hecho, en principio, el grado de multiprogramación tiene 

como límite el número de marcos de página que caben en memoria.

Figura 4.6. Realimentación que conduce a la sobrepaginación 

En principio, un grado de multiprogramación alto incrementa la eficiencia de la CPU. 

Sin embargo, en sistemas con una fuerte carga, un número excesivo de programas en 

memoria conduce a tener muy pocas páginas de cada proceso y, por tanto, una 

probabilidad muy alta de fallo de página. Como el proceso que comete el fallo de 

página deja libre la CPU y pasa a estado bloqueado, se produce un cambio de 

contexto que pronto provocará un nuevo fallo de página al cambiar la localidad de 

las referencias. Esta situación se realimenta (Figura 4.6) hasta que la mayoría de los 

procesos estarán bloqueados por fallo de página, y  la CPU tendrá una utilización 

muy baja. Esta caída drástica de la eficiencia (Figura 4.7) es lo que se conoce como 

sobrepaginación o thrashing.

Figura 4.7. Caída del rendimiento por sobrepaginación

7.3 Modelo de working-set

Se puede intentar evitar la sobrepaginación explotando hasta el límite la propiedad
de localidad de los programas. Para un programa y en un instante de tiempo dado,
es posible definir con bastante precisión un subconjunto de sus páginas que va a
recibir la práctica totalidad de las referencias que genera el programa (working-set o
conjunto de trabajo del programa, WS). Esto nos garantiza que dicho programa va a
provocar muy pocos fallos de página. Si mantenemos  en memoria únicamente
conjuntos de trabajo completos, aseguraremos tasas de fallo de página bajas.
Implícitamente, la utilización de conjuntos de trabajo establece una nueva política de
asignación que limita el grado de multiprogramación del sistema,  N, ya que debe
cumplirse:
tamaño WS M
N
i
∑ i ≤
=1
( )
Para definir conjuntos de trabajo (sobre la base de la propiedad de localidad
temporal) es necesario llevar una traza de las últimas referencias de cada programa.
Dicha traza puede verse como una ventana de tamaño  ∆ sobre la secuencia de
referencias del programa, desde la referencia actual hacia atrás. El conjunto de
páginas referenciadas en ∆ es el WS del programa.
La elección de un ∆ adecuado es muy importante. Una ventana demasiado pequeña
no asumiría bien la localidad del programa. Una ventana demasiado grande
abarcaría localidades de instantes de tiempo anteriores. Se ha mostrado
experimentalmente que un valor razonable de ∆ es del orden de 10.000 referencias.
La implementación de la ventana del WS sobre la base de una cuenta de referencias
es costosa. Una aproximación razonable es utilizar el concepto de envejecimiento con
la implementación que se vio en la sección dedicada a los algoritmos de reemplazo.
En el caso más simple puede usarse únicamente el bit R y un ∆ de un tick de reloj.
En el modelo de conjuntos de trabajo la asignación  de marcos de página es local.
Usualmente se definen tamaños máximos de WS.
Si para la carga del conjunto de trabajo de un programa se usa paginación por
demanda, existirá un periodo transitorio hasta que  se cargue el WS del proceso
durante el cual el número de fallos de página puede ser muy elevado, lo que
conduciría a sobrepaginación. Esto se evita cargando todo el conjunto de trabajo
antes de planificar el proceso  (prepaginación). De esta forma, el transitorio sólo se
produce cuando se crea el proceso, cuando todavía no tiene establecido su WS.

Nótese que la gestión de la memoria mediante conjuntos de trabajo es una forma de
combinar memoria virtual y swapping.

6.8 Otros aspectos de la memoria virtual

6.8.1 Fijación de páginas en memoria

Considérense los siguientes casos en un sistema con asignación global:
Caso A:
(1) Un proceso P1 se bloquea para leer de disco en un buffer de memoria.
(2)  Entra a ejecución otro proceso, P2.
(3) P2 comete fallo de página.
(4) La página de P1 que contiene el buffer de E/S es elegida como víctima.
Caso B:
(1) Un proceso P1 se bloquea por fallo de página.
(2) Entra a ejecución otro proceso, P2.
(3) La página pedida por P1 se carga en memoria y P1 a preparado para
ejecución.
(4) P2 comete fallo de página.
(5) La página recién cargada de P1 es elegida como víctima.
El Caso A se introdujo con el swapping de procesos, y se vio entonces que una de las
alternativas es definir los buffers de E/S en el espacio del sistema operativo. El Caso B
es una nueva consecuencia de la memoria virtual. Una solución general aplicable a
ambas situaciones es evitar que dichas páginas salgan de memoria mediante un bit
de fijación de la página en memoria que la hace no elegible como víctima.

6.8.2 Páginas iniciadas a cero

Las páginas iniciadas a cero en tiempo de compilación (por ejemplo, arrays de gran
tamaño) no se almacenan en el fichero ejecutable. El montador crea un segmento
específico y las entradas correspondientes de la tabla de páginas se marcan como
inválidas y se señalan como páginas iniciadas a cero mediante un bit específico. Al
ser referenciada una de estas páginas, la rutina de fallo de páginas asigna un marco y
lo inicia a ceros.

6.8.3 Páginas copy-on-reference

Este bit permite la gestión de páginas compartidas  modificables, de utilidad en
sistemas donde los procesos hijos heredan las características de padre, como es el
caso de UNIX (llamada al sistema fork). Las páginas del nuevo proceso, en vez de
copiarse en la creación del proceso, se comparten y marcan con un bit de  copy-on-reference, para duplicarse bajo demanda sólo si fuese necesario. Cuando un proceso
referencie para escritura una página de este tipo, se le proporciona una copia privada
de la página, desactivándose entonces el bit.

7 Ejemplos

7.1 VAX/VMS

El sistema operativo VMS, desarrollado para la familia VAX-11 de Digital,
introducida a finales de los 70, proporciona un entorno unificado para hardware con
diferentes niveles de rendimiento. La gestión de memoria se encontraba muchas
veces con un soporte hardware muy limitado. Aunque prácticamente en desuso, su
estudio tiene interés por razones históricas, como veremos.
El VAX-11 proporcionaba un espacio de direccionamiento virtual de 32 bits,
repartidos entre usuario y sistema. Las direcciones eran paginadas, con un tamaño de
página de 512 bytes. Un programa de usuario disponía de tres regiones (segmentos),
cada uno con una tabla de páginas con registros de base y de longitud asociados.
Como soporte para memoria virtual, cada entrada de las tablas de páginas contaba,
al menos, con un bit de validez y un conjunto de bits para protección de acceso.
Las principales características de la gestión de la memoria virtual en VMS son las
siguientes:
Asignación de páginas local. Existe un límite máximo en el número de páginas residentes
por proceso (su  working-set, en terminología VAX/VMS). Los procesos pueden ser
expulsados de memoria para evitar la sobrepaginación. Cuando un proceso vuelve a
memoria lo hace con el mismo conjunto de páginas residentes con que fue expulsado.
Paginación con reemplazo FIFO y buffer de marcos global. El paginador mantiene un
número adicional de marcos de página que no están asignados a los conjuntos
residentes de cada proceso. Este buffer de marcos se compone de dos listas: lista de
marcos modificados y lista de marcos libres. Un marco elegido como víctima se
añade a una de estas listas dependiendo de si la página ha sido o no modificada.
Cuando un proceso hace referencia a una página que  no está en su conjunto
residente, la rutina de fallo de página busca primero en estas listas; si lo encuentra, lo
añade a su conjunto residente sin necesidad de acceder a memoria secundaria. Sólo
cuando el número de marcos libres alcanza un límite mínimo se produce realmente

una expulsión de página al eliminarse elementos de la lista con disciplina FIFO
. En el caso de la lista de marcos modificados, éstos se escriben conjuntamente en disco.
Agrupamiento de páginas. El pequeño tamaño de la página del VAX causaría un
rendimiento muy pobre si éstas se transfirieran individualmente entre memoria y
disco. Para evitarlo, las páginas de un proceso se  agrupan para transferirse
conjuntamente. En el caso de lectura, por ejemplo,  se transfieren las páginas del
conjunto residente de un proceso. En el caso de escritura, se transfieren las de la lista
de modificadas. Swapping. En determinadas circunstancias, la única forma de recuperar marcos libres
es sacando de memoria el working-set completo de uno o más procesos, para lo que
se tiene en cuenta la prioridad y un quantum de memoria de los procesos.

7.2 UNIX

UNIX es un sistema operativo diseñado para ser instalado sobre una gran variedad 

de máquinas. Ya que la gestión de la memoria es muy dependiente del soporte 

hardware disponible, nos encontraremos con que existen diferentes formas de 

gestión de memoria en UNIX. Así, las primeras implementaciones de UNIX, sobre 

máquinas PDP-11, no trabajaban con memoria virtual. Las implementaciones 

posteriores proporcionan memoria virtual con paginación por demanda combinado 

con swapping de procesos. A continuación describiremos la gestión de la memoria en 

el System V. 

Para cada entrada de la tabla de páginas se considera la dirección física del marco de 

página, bits de protección (r, w, x), bit de validez, bit de referencia, bit de página 

modificada, y un contador de antigüedad de la página. Estrictamente, sólo la 

dirección física y el bit de validez deben estar obligatoriamente soportados por 

hardware. El resto de la información puede simularse en software (como ocurría en 

                                                

15

 Esta estrategia equivale a una implementación software de un algoritmo de reemplazo  NRU. Al no 

poder contar siempre con un bit de referencia hardware, es el bit de validez el que hace su papel; la 

rutina de atención al fallo de página representa implícitamente las páginas no referenciadas 

recientemente dentro de las listas de marcos libres y  modificados. 

16

 El paginador organiza la ubicación de las páginas  en disco de manera que se almacenen en lo 

posible en bloques contiguos. 

17

  El quantum de memoria se refiere a la cantidad de tiempo que un proceso puede estar residente en 

memoria, y no coincide con el concepto de quantum que habitualmente se usa para describir modelos 

Round-Robin, referido al tiempo que un proceso puede estar consecutivamente en la CPU. Al contrario, 

en el VAX/VMS se utiliza el término quantum para referirse al tiempo  acumulado de CPU  de un 

proceso en memoria.

el VAX-11). Además, para cada entrada de la tabla de páginas se almacena la 

información para acceder a la página en memoria secundaria (descriptor de bloque 

del disco). 

Otra estructura de información que se mantiene es una lista de marcos de página,  que 

guarda información acerca del estado de la página (asignada, en fichero ejecutable, 

libre, cargándose por DMA), el número de procesos que referencian el marco (para 

compartición), y el dispositivo que contiene una copia de la página y el número de 

bloque.  

Algunas características de la gestión de la memoria virtual en el Sistema V son los 

siguientes: 

Asignación global y working-set. UNIX define el working-set de un proceso como el 

conjunto de páginas asignadas a un proceso. Los marcos no asignados a ningún 

proceso son marcos libres asignables a cualquier proceso. El sistema define el número 

mínimo de marcos libres, que comprueba periódicamente. Si en un instante de 

tiempo no se alcanza dicho límite, un proceso paginador (page-stealer) entra para 

envejecer las páginas. Toda referencia a una página pone a cero la edad de la página. 

Si la edad alcanza un valor n, establecido por la instalación, la página pasa a estado 

libre. El diagrama de transición de estados que ilustra este mecanismo se muestra en 

la Figura 4.8. La página de un marco libre puede ser rescatada en una referencia si el 

marco no hubiera sido asignado antes. Este mecanismo se ha implementado en los 

Sistemas V hasta la versión 3, y es utilizado también por Linux. El SVR4 ha 

simplificado el reemplazo de páginas prescindiendo  del contador de edad. El 

paginador se limita a poner a cero el bit de referencia (lo que equivale a envejecer 

hasta n=1) y a liberar las páginas con R=0 siguiendo el algoritmo del reloj. 

Escritura de páginas en disco por grupos. Si el paginador decide liberar una página y la 

página se ha modificado o no existe una copia en disco (por ejemplo, página iniciada 

a ceros), el paginador pone la página en una lista de páginas a escribir. Si el número 

de elementos de esta lista alcanza un cierto límite, las páginas se escriben físicamente 

en el disco. 

Swapping. En situaciones de mucha demanda de memoria por parte de los procesos, 

el paginador puede no ser capaz de conseguir marcos libres a la velocidad necesaria. 

Cuando la rutina de fallo de página no es capaz de mantener el nivel mínimo de 

marcos libres, entra el proceso swapper para sacar algún proceso de memoria. Los 

criterios de elección dependen de la versión de UNIX, pero fundamentalmente se 

basan en el estado del proceso y su prioridad. 

Figura 4.8. Transición de estados y envejecimiento de una página en UNIX.

7.3 Windows

Windows NT, como sistema operativo moderno, presupone un potente soporte
hardware para la gestión de memoria, como es el caso de los procesadores actuales.
Los procesos manejan espacios de direcciones de 32 bits. El tamaño de página es de 4
Kbytes, aunque en algunas máquinas se puede configurar. Utiliza memoria virtual
con paginación a dos niveles y proporciona los mecanismos de protección y
compartición habituales.
En lo referente a la política de gestión de la memoria virtual, básicamente copia la
filosofía de VMS. Las capacidades de la gestión de  memoria las proporciona un
módulo del núcleo denominado  VM manager. Cabe destacar las siguientes
características.
Paginación por demanda con clustering. A partir de un fallo de página no sólo se carga
la página que ha producido el fallo sino también un conjunto de páginas adyacentes.
Asignación de páginas local. Aplica una política FIFO entre las páginas cargadas del
proceso (su working-set).
Tamaño de working-set ajustable dinámicamente. El VM manager ajusta el tamaño de los
working-sets de los procesos en función de sus comportamientos, sus cuotas de
memoria y de las necesidades globales de memoria. Cuando necesita memoria, el
VM manager recupera marcos de los working-sets de los procesos, respetándoles un
tamaño mínimo. Un proceso puede aumentar su working-set a medida que comete
fallos de página si hay marcos libres.

8 Bibliografía

Los textos clásicos de sistemas operativos vuelven a ser útiles en este tema. Al ser la
gestión de memoria un tema muy asentado académicamente, todos ellos siguen un
enfoque similar y son prácticamente equivalentes como texto de referencia. El orden
en que se relacionan a continuación es meramente alfabético: [SIL08], [STA05],
[TAN08].
[BAH86] (capítulo 9) describe la implementación de la gestión de memoria en UNIX
System V, mientras que [VAH96] (capítulos 13, 14 y 15) lo hace para los SVR4 y BSD
(éste último no tratado en estos apuntes). [CUS93,  SOL98, SOL00] describen la
gestión en Windows.

9 Ejercicios

1  En un sistema con memoria física de 64 Mbytes gestionada por segmentación,
comparar las alternativas de gestión del espacio libre (mapa de bits y lista de huecos
libres) en cuanto a eficiencia espacial. ¿Qué cambiaría si el sistema fuera segmentadopaginado, con páginas de 4 Kbytes?
2  Un sistema de memoria paginada tiene un espacio de direccionamiento lógico
de 1 Gbyte y páginas de 4 Kbytes. Para una memoria física de 64 Mbytes, calcular el
tamaño de la tabla de páginas, teniendo en cuenta que la memoria es direccionable a
nivel de byte.
3 El siguiente código forma parte de un sistema de gestión de memoria
paginado como el del Ejercicio 2. Se define una función ubicar(), que será llamada
desde ejecutar_programa, que reserva espacio en memoria para el proceso creado:
 int tablas_pag[NUM_PROCS][MAX_ENT_TP];
 int marcos_libres;
 int ubicar(int num_paginas, int num_proc)
 {
  int i, marco;
  entrar_SC(MUTEX_MEM);
  if (num_paginas > marcos_libres) { /*no hay espacio*/
   dejar_SC(MUTEX_MEM);
   return(-1);
  }
  marcos_libres= marcos_libres - num_paginas;
  dejar_SC(MUTEX_MEM);
  for (i=0; i<num_paginas; i++) {
   entrar_SC(MUTEX_MEM);
   marco= buscar_en_mapa_bits();
   poner_a_1_mapa_bits(marco);
   dejar_SC(MUTEX_MEM);
   tablas_pag[num_proc][i]= marco;

}
  for (i=num_paginas; i<MAX_ENT_TP; i++)
   tablas_pag[num_proc][i]= -1; /*páginas no usadas*/
  return(0);
 }
 (a) Definir MAX_ENT_TP. Si el sistema dedica 4 Mbytes de memoria para ubicar
las tablas de páginas, ¿cuál debe ser el valor de NUM_PROCS?
 (b) Programar la rutina liberar(num_proc), que libera los bloques ocupados por el
proceso num_proc. Utilizar funciones para acceso al mapa de bits.
4  Se pretende segmentar el sistema de memoria del Ejercicio 2 para que las
tablas de páginas no ocupen más de un marco de página.
(a) Dibujar el esquema de la traducción de direcciones, mostrando la estructura
de las direcciones virtual y física.
(b) ¿Cuántas entradas tendrá la tabla de segmentos? Calcular el tamaño mínimo de
cada entrada, teniendo en cuenta que las tablas de  páginas pueden estar
ubicadas en cualquier dirección.
(c) Tenemos cargados 100 procesos que ocupan toda la memoria, y cada proceso
tiene como media 3 segmentos. Calcular (c1) la fragmentación interna media por
proceso, (c2) la fragmentación externa total en el  sistema, y (c3) la pérdida de
eficiencia espacial en el sistema por fragmentación interna y externa.
(d) Si la gestión de marcos libres se hace por mapa de bits, ¿cuántos bytes ocupará
el mapa?
(e) ¿Qué parámetros se modificarían si se ampliase la memoria a 128 Mbytes?
5 El sistema del ejercicio anterior se gestiona con memoria virtual. A partir de
las siguientes definiciones,
struct ent_seg {
   int longitud;
   int *ptabla_pag;
 } tablas_seg[NUM_PROCS][NUM_SEG];
(a) Introducir las definiciones necesarias y/o modificar las existentes.
(b) Programar una función ubicar(num_proc) con prepaginación, que rellena
las tablas de páginas a partir de las entradas de longitud de la tabla de
segmentos correspondiente, que se supone que ya ha sido cargada. Nótese que
ubicar() no carga las páginas en memoria.

(c) Programar una nueva versión de ubicar(num_proc) que establece la carga
de páginas por demanda.
6  Se quiere introducir memoria virtual en un sistema paginado donde el tiempo
de acceso a memoria paginada es de 0,1 µs. El tiempo medio para tratar un fallo de
página en el nuevo sistema con memoria virtual se estima que será de 5 ms. Calcular
la probabilidad máxima de fallo de página para que  el tiempo medio de acceso a
memoria en el sistema de memoria virtual no se incremente en más de 20% con
respecto al del sistema paginado original.
7  En un sistema paginado de memoria virtual con 3 marcos de memoria física,
considerar la siguiente secuencia de referencias a páginas:
1  2  3  4  2  3  2  3  1  5  1  2  6  2  5  1  5  2  5  5  1  6  3  5  6
Indicar la sucesión de fallos de página y las páginas víctimas elegidas según se siga
un algoritmo de reemplazo óptimo, FIFO, LRU o Segunda Oportunidad.
8 A partir de las siguientes definiciones:
 struct ent_tab_pag {
  char bit_V;  /* bit de validez */
  int marco;
 } tab_pag[NUM_PROC][NUM_PAG];
 struct ent_marco {
  char bits;  /* MASK_R:referencia, MASK_M:modificado */
  int tick_carga;
  int proceso;
 } marco[NUM_MARCOS];
escribir una rutina int pag_victima(p) que devuelva el número de marco de la página
elegida como víctima para el proceso p (asignación local) siguiendo las políticas (a)
de la segunda oportunidad, (b) FIFO. Modificar (con ambos algoritmos) la rutina
pag_victima() para que la asignación de páginas sea global.
9  Según se ha observado en un sistema como el del Ejercicio 5 (basado en el del
Ejercicio 2), aparece thrashing cuando el grado de multiprogramación supera los 100
procesos. Calcular el tamaño mínimo del working set para evitar esta situación.