Funciones y operaciones del administrador de
memoria
El único
espacio de almacenamiento que el procesador puede utilizar directamente, más
allá de los registros (que si bien le son internos y sumamente rápidos, pero de
capacidad muy escasa) es la memoria física. Todas las arquitecturas de
procesador tienen instrucciones para interactuar con la memoria, pero ninguna
lo tiene para hacerlo con medios persistentes
de almacenamiento, como las unidades de disco1. Cabe mencionar que cuando veamos en un
texto referencia al almacenamiento
primario siempre se referirá a la memoria, mientras que el almacenamiento secundario se refiere
a los discos u otros medios de almacenamiento persistente.
Todos los
programas que deseemos ejecutar deben cargarse a la memoria del sistema antes
de ser utilizados. En esta unidad veremos cómo administra el sistema operativo
a la memoria para permitir que varios procesos la compartan — Esta tarea debe
preverse desde el proceso de compilación de nuestros programas (en particular,
la fase de ligado). Hoy en día,
además, casi todos los sistemas operativos emplean implementaciones que
requieren de hardware especializado — La Unidad
de Manejo de Memoria (MMU). Hablaremos de cómo se manejaban los sistemas
multitarea antes de la universalización de los MMU, y qué rol juegan hoy en
día.
En esta primera
sección, veremos algunos conceptos base que iremos hilando y empleando en las
secciones subsecuentes.
Espacio de direccionamiento
La
memoria está estructurada como un arreglo direccionable de bytes. Esto es, al
solicitar los contenidos de una dirección específica de memoria, el hardware
nos entregará un byte (8 bits), y no menos. Si queremos hacer una operación
sobre bits específicos, tenemos
que solicitar y almacenar bytes enteros. En algunas arquitecturas, el tamaño de palabra es mayor — Por
ejemplo, los procesadores Alpha incurrían en fallas de alineación si se solicitaba una dirección de memoria
no alineada a 64 bits, y toda llamada a direcciones mal alineadas tenía que ser atrapada por el sistema operativo, re-alineada, y entregada.
Un procesador que soporta un espacio de direccionamiento de 16 bits puede referirse directamente a hasta $2^{16}$ bytes, esto es, a hasta 65,536 bytes (64K). Estos procesadores fueron comunes en las décadas de 1970 y 1980 — Los más conocidos incluyen al Intel 8080 y 8085, Zilog Z80, MOS 6502 y 6510, y Motorola 6800. Hay que recalcar que estos procesadores son reconocidos como procesadores de 8 bits, pero con espacio de direccionamiento de 16 bits. El procesador empleado en las primeras PC, el Intel 8086, manejaba un direccionamiento de 20 bits (hasta 1024KB), pero al ser una arquitectura real de 16 bits requería del empleo de segmentación para alcanzar toda su memoria.
Hoy en
día, los procesadores dominantes son de 32 o 64 bits. Un procesador de 32 bits
puede direccionar hasta 4,294,967,296 bytes (4GB), que está ya dentro de los
parámetros de lo esperable hoy en día; una arquitectura de 32 bits sin extensiones
adicionales no puede emplear más de 4GB RAM; a través de un mecanismo llamado PAE (Extensión de Direcciones
Físicas, Physical Address Extension)
permite extender esto a rangos de hasta $2^{52}$ a cambio de un nivel más de indirección.
Un
procesador de 64 bits podría direccionar hasta 18,446,744,073,709,551,616 bytes
(16 Exabytes). Los procesadores comercialmente hoy en día no ofrecen esta
capacidad de direccionamiento principalmente por un criterio económico: Al
resultar tan poco probable que exista un sistema con estas capacidades, los
chips actuales están limitados a entre$2^{40}$ y$2^{48}$ bits — 1 y 256 terabytes. Esta restricción
debe seguir teniendo sentido económico por muchos años aún.
Hardware: de la unidad de manejo de memoria (MMU)
A lo largo
de la historia de las computadoras ha sido necesario emplear más memoria de la
que está directamente disponible — Por un lado, ofrecer a los procesos más
espacio de lo que puede direccionar la
arquitectura (hardware) que empleamos, por otro lado la abstracción de
un espacio virtualmente ilimitado para realizar sus operaciones incluso cuando
la memoria real es mucho menor
a la solicitada, y por último, la ilusión de tener un bloque contiguo e
ininterrumpido de memoria, cuando en realidad puede haber alta fragmentación.
Veremos
cómo es que el MMU cubre estas necesidades, qué mecanismos emplea para lograrlo
— Y qué debemos cuidar, incluso como programadores de aplicaciones de alto
nivel, para aprovechar de la mejor manera estas funciones (y evitar, por el
contrario, que nuestros programas se vuelvan lentos por no saber manejar la
memoria) correctamente.
El MMU es
también el encargado de verificar que un proceso no tenga acceso a leer o
modificar los datos de otro — Si el sistema operativo tuviera que verificar que
ninguna de las instrucciones ejecutadas por un programa resulta en una
violación de seguridad, la penalización en velocidad sería demasiado severa2.
Una
primer aproximación a la protección de acceso es a través de un registro base y un registro límite: Si la arquitectura
ofrece dos registros del procesador que sólo pueden ser modificados por el
sistema operativo (Esto es, el hardware define la modificación de dichos
registros como una operación privilegiada que requiere estar ejecutando en modo supervisor), el MMU puede
comparar cada acceso a memoria
para verificar que esté en el rango permitido.
Por
ejemplo, si a un proceso le fue asignado un espacio de memoria de 64K (65535
bytes) a partir de la dirección 504214 (492K), el registro base contendría 504214, y el registro límite 65535. Si hubiera una instrucción por parte de
dicho proceso que solicitara una dirección menor a 504214 o mayor a 569749
(556K), el MMU lanzaría una excepción o trampa
interrumpiendo el procesamiento, e indicando al sistema operativo que ocurrió
una violación de segmento (segmentation fault)3.
El sistema operativo entonces procedería terminando la ejecución del proceso,
reclamando todos los recursos que tuviera asignados y notificando a su usuario.
La memoria caché
Hay otro
proceso que hoy en día asumimos como un hecho: La memoria caché. Si bien su manejo es (casi)
transparente para el sistema operativo, es muy importante mantenerlo en mente.
Conforme
el procesador va avanzando sobre las instrucciones de un programa (avanzando el
registro de conteo de instrucción), se van produciendo accesos a memoria. Por
un lado, tiene que buscar en memoria la siguiente instrucción a ejecutar. Por
otro lado, estas instrucciones pueden requerirle uno o más operadores
adicionales que deben ser traídos de la memoria. Por último, la instrucción
puede requerir guardar su resultado en cierta dirección de memoria.
Hace años
esto no era un problema — La velocidad del procesador estaba básicamente
sincronizada con la del manejador de memoria, y el flujo podía mantenerse
básicamente estable. Pero conforme los procesadores se fueron haciendo más
rápido, y conforme se ha popularizado el procesamiento en paralelo, la memoria
no ha podido acelerarse a la misma velocidad. La memoria de alta velocidad es
demasiado cara, e incluso las distancias de unos pocos centímetros se van
volviendo obstáculos insalvables por la velocidad máxima de los electrones
viajando por pistas conductoras.
Cuando el
procesador solicitó el contenido de una dirección de memoria y esta no está aún
disponible, tiene que detener su
ejecución (stall) hasta
que los datos estén disponibles. El CPU no puede, a diferencia del sistema
operativo, "congelar" todo y guardar el estado para atender a otro proceso:
Para el procesador, la lista de instrucciones a ejecutar es estrictamente
secuencial, y todo tiempo que requiere esperar a una transferencia de datos es
tiempo perdido.
La
respuesta para reducir esa espera es la memoria
caché. Esta es memoria de alta velocidad, situada entre la memoria principal y el
procesador propiamente, que guarda copias de las páginas que van siendo accesadas, partiendo del principio de la localidad de referencia:
Localidad temporal
Es probable que
un recurso que fue empleado recientemente vuelva a ser empleado en un futuro
cercano.
Localidad espacial
La probabilidad de que un recurso aún no requerido sea accesado es mucho mayor si fue requerido algún recurso cercano.
Localidad secuencial
Un recurso, y
muy particularmente la memoria, tiende a ser requerido de forma secuencial.
Patrones de acceso a memoria, demostrando la
localidad espacial / temporal (Silberschatz, p.350)
Basándonos
en estos conceptos, vemos que cuando el procesador solicita al hardware
determinada dirección de memoria, el hardware no sólo transfiere a la memoria
caché el byte o palabra solicitado, sino que un bloque o página completo.
El espacio en memoria de un proceso
Cuando un
sistema operativo inicia un proceso, no se limita a volcar el archivo
ejecutable a memoria, sino que tiene que proveer la estructura para que éste
vaya guardando la información de estado relativa a su ejecución.
Sección de texto
Es el nombre que recibe la imagen
en memoria de las instrucciones a ser ejecutadas. Típicamente, la sección de
texto ocupa las direcciones más bajas
del espacio en memoria.
Sección de datos
Espacio fijo pre asignado para
las variables globales. Este espacio es fijado en tiempo de compilación, y no
puede cambiar (aunque los datos que carga sí cambian en el tiempo de vida del
proceso)
Espacio de libres
(Heap) Espacio de memoria que se emplea para la asignación
dinámica de memoria durante la
ejecución del proceso. Este espacio se ubica por encima de la sección de
datos, y crece hacia arriba.
Cuando el programa es escrito en lenguajes que
requieren manejo manual de la memoria
(como C), esta área es la que se maneja a través de las llamadas de la familia
de malloc y free; en lenguajes con gestión automática, esta área es
monitoreada por los recolectores de
basura (volveremos a estos conceptos más adelante).
Pila de llamadas
(Stack) Estructuras representando a la serie de funciones que han
sido llamadas dentro del proceso, con sus parámetros, direcciones de retorno, variables locales, etc. La
pila ocupa la parte más alta
del espacio en memoria, y crece hacia
abajo.
Resolución de direcciones
Un
programa compilado no emplea nombres simbólicos para las variables o funciones
que llama4; el compilador, al convertir el programa a lenguaje máquina,
las substituye por la dirección en memoria donde se encuentra.
Ahora
bien, en los sistemas actuales, los procesos requieren coexistir con otros,
para lo cual las direcciones indicadas en el texto del programa pueden requerir ser traducidas al lugar relativo al sitio de inicio del proceso en
memoria — Esto es, resueltas.
Podemos hablar de las siguientes tres estrategias de resolución:
En tiempo de compilación
El texto del programa tiene la
dirección absoluta de los datos
y funciones. Esto era muy común en las computadoras previas al
multiprocesamiento; en la arquitectura compatible con PC, el formato ejecutable
.COM es un volcado de memoria directo
de un archivo objeto con las direcciones indicadas de forma absoluta. Esto lo
podemos ver hoy principalmente en sistemas embebidos o de función específica.
En tiempo de carga
Al cargarse a memoria el programa
y antes de iniciar su ejecución, el cargador
(componente del sistema operativo) actualiza las referncias a memoria dentro
del texto para que apunten al lugar correcto — Claro está, esto depende de que
el compilador indique dónde están todas las referencias a variables y
funciones.
En tiempo de ejecución
El programa nunca hace referencia
a una ubicación absoluta de memoria, sino que lo hace siempre relativo a una base y un desplazamiento (offset). Esto permite que el proceso sea incluso
reubicado en la memoria mientras está siendo ejecutado sin tener que sufrir
cambios, pero requiere de hardware específico (como un MMU).
Esto es,
los nombres simbólicos (por ejemplo, la variable llamada contador) para ser traducidos ya sea a ubicaciones en la
memoria, pueden resolverse en tiempo de compilación (y quedar plasmada en el
programa en disco con una ubicación explícita y definitiva: 510200), en tiempo
de carga (sería guardada en el programa en disco como inicio + 5986 bytes, y el proceso de carga incluiría
substituirla por la dirección resuelta a la suma del registro base, 504214, y
el desplazamiento, 5986, esto
es, 510200).
Por
último, para emplear la resolución en tiempo de ejecución, se mantiene en las
instrucciones a ser ejecutadas por el proceso la etiqueta relativa al módulo
actual, inicio + 5986 bytes, y
es resuelta cada vez que sea requerido.
Proceso
de compilación y carga de un programa, indicando el tipo de resolución de
direcciones (Silberschatz, p.281)
Asignación de memoria contigua
En los
sistemas de ejecución en lotes, así como en las primeras computadoras
personales, sólo un programa se ejecutaba a la vez, por lo que, más allá de la
carga del programa y la satisfacción de alguna eventual llamada al sistema
solicitando recursos, el sistema operativo no tenía que ocuparse de la
asignación de memoria.
Al nacer
los primeros sistemas operativos multitarea, se hizo necesario resolver cómo
asignar el espacio en memoria a diferentes procesos.
Partición de la memoria
La primera
respuesta, claro está, es la más sencilla: Asignar a cada programa a ser
ejecutado un bloque contiguo de
memoria de un tamaño fijo. En tanto los programas permitieran la resolución de
direcciones en tiempo de carga o de ejecución, podrían emplear este esquema.
El
sistema operativo emplearía una región específica de la memoria del sistema
(típicamente la región baja —
Desde la dirección en memoria 0x00000000 hacia arriba), y una vez terminado el
espacio necesario para el núcleo y sus estructuras, el sistema asigna espacio a
cada uno de los procesos. Si la arquitectura en cuestión permite limitar los
segmentos disponibles a cada uno de los procesos (por ejemplo, con los
registros base y límite discutidos anteriormente),
esto sería suficiente para alojar en memoria a varios procesos y evitar que
interfieran entre sí.
Desde la
perspectiva del sistema operativo, cada uno de los espacios asignados a un
proceso es una partición.
Cuando el sistema operativo inicia, toda la memoria disponible es vista como un
sólo bloque, y conforme se van lanzando procesos, este bloque va siendo
subdividido para satisfacer sus requisitos. Cada proceso debe indicar al
sistema operativo cuánta memoria va a requerir a lo largo de su vida prevista.
2.1.1 Fragmentación
La fragmentación comienza a aparecer
cuando más procesos van siendo lanzados y van terminando: Al terminar la
ejecución de un proceso, ya no tenemos sólo un bloque de espacio libre, sino
dos. Potencialmente, cada programa que vaya terminando, irá devolviendo al
sistema operativo un bloque de distinto tamaño, que quede entre dos procesos
activos.
Si la
computadora no tiene hardware específico que permita que los procesos resuelvan
sus direcciones en tiempo de ejecución, el sistema operativo no puede reasignar
los bloques existentes, y aunque pudiera hacerlo, mover un proceso entero en
memoria puede resultar una operación cara en tiempo de procesamiento.
Al
lanzarse un nuevo programa, el sistema operativo tiene tres estrategias según
las cuales podría asignarle uno de los bloques disponibles:
Primer ajuste
Asigna al nuevo proceso el primer
bloque que encuentre donde éste quepa. Este mecanismo es el más simple de
implementar y el de más rápida ejecución.
Mejor ajuste
El sistema busca entre todos los
bloques disponibles cuál es el que mejor se ajusta al tamaño requerido por el
nuevo proceso. Esto requiere la revisión completa de la lista de bloques; lleva
a que los bloques remanentes, una vez que se ubicó al nuevo proceso, sean tan
pequeños como sea posible (esto es, que haya menor desperdicio).
Peor ajuste
El sistema busca cuál es el
bloque más grande disponible, y se lo asigna al nuevo proceso. Empleando una estructura
de datos como un montículo,
esta operación puede ser incluso más rápida que la de primer espacio. Con este
mecanismo se busca que los bloques que queden después de otorgarlos a un
proceso sean tan grandes como sea posible, de cierto modo balanceando su
tamaño.
La fragmentación externa se produce
cuando hay muchos bloques libres entre bloques asignados a procesos; la fragmentación interna se refiere a la
cantidad de memoria perdida por asuntos administrativos — Por ejemplo, si el
sistema operativo maneja bloques
de 512 bytes y un proceso requiere 768 bytes para su ejecución, el sistema le
entregará dos bloques (1024 bytes), con lo cual desperdicia 256. En el peor de
los casos, con un bloque de $n$ bytes, un proceso podría solicitar $kn+1$ bytes
de memoria, desperdiciando por fragmentación interna $n-1$ bytes.
Según
análisis estadísticos (Silberschatz, p.289), por cada N bloques asignados, se perderán del orden de 0.5N bloques por fragmentación
interna y externa.
Compactación
Un
problema importante que va surgiendo como resultado de esta fragmentación es
que el espacio total libre de memoria puede ser mucho mayor que lo que requiere
un nuevo proceso, pero al estar fragmentada
en muchos bloques, éste no encontrará una partición donde ser cargado.
Si los procesos emplean resolución de direcciones en tiempo de ejecución, cuando el sistema operativo comience a detectar un alto índice de fragmentación, puede lanzar una operación de compresión o compactación: Mover los contenidos en memoria de los procesos en ejecución para que ocupen espacios contiguos, permitiendo unificar varios bloques libres en uno solo.
Compactación
de la memoria de procesos en ejecución
La
compactación tiene un costo alto — Involucra mover prácticamente la totalidad
de la memoria (probablemente más de una vez por bloque).
Siguiendo
de cierto modo la lógica requerida por la compactación encontramos los sistemas
que utilizan intercambio (swap) entre la memoria primaria y
secundaria. En estos sistemas, el sistema operativo puede comprometer más espacio de memoria
del que tiene físicamente disponible. Cuando hay más procesos de los que caben
en memoria, el sistema suspende a uno de ellos y almacena una copia de su
imagen en memoria en almacenamiento secundario.
Hay
algunas restricciones a observar previo a suspender un proceso. Un proceso que
tiene abierto alguna operación de entrada/salida en curso. Una estrategia ante
esto podría ser que todas las operaciones se realicen únicamente a buffers en el espacio del sistema
operativo y éste las transfiera al espacio del proceso interesado.
Esta
técnica se popularizó en los sistemas de escritorio hacia fines de los 1980 y
principios de los 1990, en que las computadoras personales tenían típicamente
entre 1 y 8MB de memoria.
Recordemos que las unidades de disco son del orden de decenas de miles de veces más lentas que la memoria, por lo que este proceso resulta muy caro — Por ejemplo, si la imagen en memoria de un proceso es de 100MB, bastante conservador hoy en día, y la tasa de transferencia sostenida al disco de 50MB/s, intercambiar un proceso al disco toma dos segundos. Cargarlo de vuelta a memoria toma otros dos segundos — Y a esto debe sumarse el tiempo de posicionamiento de la cabeza de lectura/escritura, especialmente si el espacio a emplear no es secuencial y contiguo. Resulta obvio por qué esta técnica ha caído en desuso conforme aumenta el tamaño de los procesos.
Segmentación
Al desarrollar un programa, el
programador no ve a la memoria como un sólo arreglo plano, en el que todas las
direcciones son iguales (si bien está consciente de que la realidad es así). El
uso que damos a la memoria sigue una lógica de distintos segmentos: En vez de dar una
dirección lineal, damos al
procesador una dirección de segmento
y un desplazamiento dentro de
dicho segmento. Podemos tener segmentos de distintos tamaños presentes en
memoria, y la resolución de direcciones de cada uno de ellos se realizará por mecanismos
análogos al descrito en el apartado anterior (registro base y desplazamiento).
Claro está, esto debe también hacerse con apoyo del MMU.
Ejemplo
de segmentación
Una de
las implementaciones más obvias y directas de un espacio de memoria segmentado
es asignar un segmento distinto a cada una de las secciones mencionadas en la
sección espacio en memoria de un proceso.
La
segmentación también ayuda a incrementar la modularidad de un programa: Es muy común que las bibliotecas ligadas dinámicamente estén
representadas en segmentos independientes.
Permisos
Una de
las principales ventajas del uso de segmentación es que nos permite pedir al
MMU que cada uno de los segmentos tenga un distinto juego de permisos para el proceso en cuestión: El sistema
operativo puede indicar, por ejemplo, que el segmento de texto (el código del programa) sea de lectura y
ejecución, mientras que la sesión de datos es de lectura y escritura. De este
modo podemos evitar que un error en la programación resulte en que datos
proporcionados por el usuario o por el entorno modifiquen el código que está
siendo ejecutado.5 Es más, Incluso, dado que el acceso de ejecución está limitado a sólo los
segmentos cargados del disco por el sistema operativo, el atacante no podrá
introducir código ejecutable tan fácilmente — Tendría que cargarlo como un
segmento adicional con los permisos correspondientes.
Intercambio parcial
Un uso
muy común de la segmentación, particularmente en los sistemas de los 1980s, era
el de permitir que sólo ciertas
regiones de un programa sean intercambiadas al disco: Si un programa
está compuesto por porciones de código que nunca se ejecutarán aproximadamente
al mismo tiempo en sucesión, puede separar su texto (e incluso los datos
correspondientes) en diferentes segmentos.
A lo
largo de la ejecución del programa, algunos de sus segmentos pueden no
emplearse por largos periodos de tiempo. Estas páginas pueden ser enviadas al espacio de intercambio (swap) ya sea a solicitud del proceso
o por iniciativa del sistema operativo.
Rendimiento
En la
sección donde presentamos el concepto de intercambio mencionamos que
intercambiar un proceso completo resultaba demasiado caro. Cuando hablamos de
un espacio de memoria segmentado, y muy particularmente cuando hablamos de
bibliotecas de carga dinámica, la sobrecarga es mucho menor:
En primer
término, podemos hablar de la cantidad de información que intercambiaremos: En
un sistema que sólo maneja regiones contiguas de memoria, intercambiar un
proceso significa mover toda su información al disco; cuando hablamos de
intercambio en un sistema con segmentación, puede enviarse a disco cada uno de
los segmentos por separado, según el sistema operativo lo juzgue necesario. Podría
sacar de memoria a alguno de
los segmentos, eligiendo no necesariamente al que más estorbe (esto es, el más grande), sino el que más probablemente
no esté siendo utilizado: Emplear el principio de localidad de referencia para
intercambiar al segmento menos
recientemente utilizado (LRU,
Leas Recental Usted).
Además de
esto, si hablamos de un segmento de texto (sea el código programa base o alguna
de las bibliotecas) y su acceso es de sólo lectura, una vez que éste fue
copiado una vez al disco, ya no hace falta volver a hacerlo: Tenemos la certeza
de que no será modificado por el proceso en ejecución, por lo que basta
marcarlo como no presente en
las tablas de segmentos en memoria para que cualquier acceso ocasione que el
sistema operativo lo traiga de disco.
Por otro
lado, si la biblioteca en cuestión reside en disco (antes de ser cargada) como
una imagen directa de su representación en memoria, al sistema operativo le
bastará identificar el archivo en cuestión al cargar el proceso; no hace falta
siquiera cargarlo en la memoria principal y guardarlo al área de intercambio,
puede quedar referido directamente al espacio en disco en que reside el
archivo.
Claro
está, el acceso a disco sigue siendo una fuerte penalización cada vez que un
segmento tiene que ser cargado del disco (sea del sistema de archivos o del
espacio de intercambio), pero este mecanismo reduce dicha penalización,
haciendo más atractiva la flexibilidad del intercambio por segmentos.
Ejemplificando
A modo de
ejemplo (Finque, p.79), y conjuntando los conceptos presentados en esta
sección, si un proceso tuviera la siguiente tabla de segmentos:
Segmento
|
Inicio
|
Tamaño
|
Permisos
|
Presente
|
0
|
13426
|
26
|
RWX
|
sí
|
1
|
2309
|
00
|
R
|
sí
|
2
|
1000
|
23
|
WX
|
sí
|
3
|
-
|
95
|
W
|
no
|
4
|
10000
|
100
|
RWX
|
sí
|
En la
columna de permisos, R se
refiere a lectura, W a
escritura y X a ejecución.
Un
segmento que ha sido enviado al espacio de intercambio (en este caso, el 3),
deja de estar presente en memoria y, por tanto, no tiene ya dirección de inicio
registrada.
Veamos el
resultado de entregar al MMU las siguientes direcciones y tipos de acceso:
Dirección
|
Tipo
de
|
Dirección
|
virtual
|
acceso
|
física
|
0-0
|
R
|
13426
|
2-17
|
W
|
1017
|
2-17
|
R
|
Atrapada:
Violación de seguridad
|
2-32
|
R
|
Atrapada:
Desplazamiento fuera de rango
|
3-72
|
W
|
Atrapada:
Segmento faltante
|
3-94
|
R
|
Atrapada:
Segmento faltante;
|
violación
de seguridad
|
||
4-99
|
X
|
10099
|
7-25
|
X
|
Atrapada:
Segmento invalido
|
Cuando se
atrapa una situación de excepción, el sistema operativo debe intervenir. Por
ejemplo, la solicitud de un segmento inválido, de un desplazamiento mayor al
tamaño del segmento, o de un tipo de acceso que no esté autorizado, típicamente
llevan a la terminación del proceso, en tanto que una de segmento faltante
(indicando un segmento que está en el espacio de intercambio) llevaría a la
suspensión del proceso, lectura del segmento de disco a memoria, y una vez que
éste estuviera listo, se permitiría continuación de la ejecución.
En caso
de haber más de una excepción, como podemos verlo en la solicitud de lectura de
la dirección 3-94, el sistema debe reaccionar primero a la más severa: Si como resultado de esa
solicitud iniciara el proceso de carga del segmento, sólo para abortar la
ejecución del proceso al detectarse la violación de tipo de acceso, sería un
desperdicio injustificado de recursos.
Paginación
La
fragmentación externa y, por tanto, la necesidad de compactación pueden
evitarse por completo empleando la paginación.
Esta consiste en que cada proceso esté compuesto por una serie de páginas, dejando de requerir que la
asignación sea de un área contigua
de memoria. Claro está, esto requiere de mayor especialización por parte del
hardware, y mayor información relacionada a cada uno de los procesos: No nos
basta ya con indicar dónde inicia y dónde termina el área de memoria de cada
proceso, sino que debemos hacer un mapeo
entre la ubicación real (física)
y la presentada a cada uno de los procesos (lógica). La memoria se presentará a cada proceso como si fuera
de su uso exclusivo.
La
memoria física se divide en una serie de marcos
(frames), todos ellos del mismo
tamaño, y el espacio cada proceso se divide en una serie de páginas (pages), del mismo tamaño que los
marcos. El MMU se se encarga del mapeo entre páginas y marcos a través de tablas de páginas. Las direcciones
que maneja el CPU ya no son presentadas de forma absoluta, sino que como la
combinación de un identificador de página y un desplazamiento — De forma
similar a lo que presentamos al hablar de resolución de instrucciones en tiempo
de ejecución.
El tamaño
de los marcos (y, por tanto, las páginas) debe ser una potencia de 2, de modo que el MMU pueda discernir fácilmente la
porción de una dirección de memoria que se refiere a la página del desplazamiento.
El rango varía, según el hardware, entre los 512 bytes ($2^9$) y 16MB
($2^{24}$); al ser una potencia de 2, el MMU puede separar la dirección en
memoria entre los primeros $m$ bits (referentes a la página) y los últimos $n$
bits (referentes al desplazamiento).
Página y
desplazamiento, en un esquema de direccionamiento de 16 bits y páginas de 512
bytes
Para
poder realizar este mapeo, el MMU requiere de una tabla de páginas (page
table), que resuelve la
relación entre páginas y marcos, convirtiendo la dirección lógica (aquella que conoce el proceso) en la dirección física (la ubicación en que
realmente se encuentra en la
memoria del sistema).
Esquema
del proceso de paginación, ilustrando el rol del MMU
Podemos
tomar como ejemplo para explicar este mecanismo el esquema presentado en el
libro de Silberschatz, Galvin y Gagné. Este nos presenta un esquema minúsculo:
Un espacio de direccionamiento
de 32 bytes (5 bits), organizado en 8 páginas de 4 bytes cada una (esto es, la
página es representada con los 3 bits más
significativos de la dirección, y el desplazamiento con los 2 bits menos significativos).
Ejemplo
(minúsculo) de paginación, con un espacio de direccionamiento de 32 bytes y
páginas de 4 bytes
El
proceso que se nos presenta tiene una visión de la memoria como la columna del
lado izquierdo: Le parece que existen 4 páginas, y tiene sus datos distribuidos
en orden desde la dirección 00000 (0) hasta la 01111 (15), aunque en realidad
en el sistema éstas se encuentren desordenadas y desperdigadas.
Cuando el
proceso quiere referirse a la letra f,
lo hace indicando la dirección 00101 (5). De esta dirección, los tres bits más
significativos (001, 1 — Y recordemos que para la computadora, lo natural es comenzar a contar por el
0) se refieren a la página número 1, y los dos bits menos significativos (01,
1) indican al desplazamiento
dentro de ésta.
El MMU
verifica en la tabla de páginas, y encuentra que la página 1 corresponde al
marco número 6 (110), por lo que traduce la dirección lógica 00101 (5) a la
física 11001 (26).
Podemos
ver que la paginación resulta en una suerte de resolución de direcciones en
tiempo de ejecución, pero con una base
distinta para cada una de las páginas.
Tamaño de la página
Ahora, si
bien la fragmentación externa se resuelve al emplear paginación, seguiremos
enfrentándonos con la fragmentación interna: Al dividirse la memoria en bloques
de longitud preestablecida de $2^n $bytes, un proceso en promedio
desperdiciará$\frac{2^n}{2}$ (y, en el peor de los casos, hasta $2^n-1$).
Multiplicando esto por el número de procesos que están en ejecución en todo
momento en el sistema, para evitar que una proporción sensible de la memoria se
pierda en fragmentación interna, podríamos vernos tentados a emplear un tamaño
de página tan pequeño como fuera posible.
Sin
embargo, la sobrecarga administrativa en que incurriríamos por gestionar
demasiadas páginas pequeñas se vuelve una limitante en sentido opuesto:
- Las transferencias entre
unidades de disco y memoria son mucho más eficientes si pueden mantenerse
como trechos continuos. El controlador de disco puede responder a
solicitudes de acceso directo a memoria (DMA) siempre que tanto los
fragmentos en disco como en memoria sean continuos; fragmentar la memoria
demasiado jugaría en contra de la eficiencia de estas solicitudes.
- El bloque de control de
proceso (PCB) incluye la información de memoria. Entre más páginas tenga
un proceso (aunque estas fueran muy pequeñas), más grande es su PCB, y más
información requerirá intercambiar en un cambio de contexto.
Estas
consideraciones opuestas apuntan a que debemos mantener el tamaño de página más
grande, y se regulan con las primeras expuestas en esta sección.
Hoy en
día, el tamaño habitual de las páginas es de 4KB u 8KB ($2^{12}$ o $2^{13}$
bytes). Hay algunos sistemas operativos que soportan múltiples tamaños de
página — Por ejemplo, Solaris puede emplear páginas de 8KB y 4MB ($2^{13}$ o
$2^{22}$ bytes), dependiendo del tipo de información que se declare que
almacenarán.
Almacenamiento de la tabla de páginas
Algunos
de los primeros equipos en manejar memoria paginada empleaban un conjunto
especial de registros para representar la tabla de páginas. Esto era posible
dado que eran sistemas de 16 bits, con páginas de 8KB ($213). Esto
significa que en el sistema había únicamente 8 páginas posibles ($2^3$), por lo
que resultaba sensato dedicar un registro a cada una.
En los
equipos actuales, mantener la tabla de páginas en registros resultaría
claramente imposible: Teniendo un procesaador de 32 bits, e incluso si
manejáramos un tamaño de página muy
grande (digamos, 4MB), tendríamos 1024 páginas posibles6; con un tamaño de páginas mucho más común
(4KB, $2^{12}$ bytes), la tabla de páginas llega a ocupar 5MB.7 Los registros son muy rápidos, sin
embargo, son correspondientemente muy caros. El manejo de páginas más pequeñas
(que es lo normal), y muy especialmente el uso de espacios de direccionamiento
de 64 bits, harían prohibitivo este enfoque. Además, nuevamente, cada proceso
tiene una tabla de páginas distinta — Se haría necesario hacer una
transferencia de información muy grande en cada cambio de contexto.
Otra
estrategia para enfrentar esta situación es almacenar la propia tabla de
páginas en memoria, y apuntar al inicio de la tabla con un juego de registros
especiales: el registro de base de la
tabla de páginas (PTBR, Page Table Base Register) y el registro de longitud de la tabla de páginas
(PTLR, Page Table Length Register),8 De esta manera, en el cambio de contexto
sólo hay que cambiar dos registros, y además tenemos un espacio muy amplio para
poder guardar las tablas de páginas que necesitemos. El problema con este
mecanismo es la velocidad: Estaríamos penalizando a cada acceso a memoria con un acceso de memoria adicional — Si
para resolver una dirección lógica a su correspondiente dirección física hace
fala consultar la tabla de páginas en memoria, el tiempo efectivo de acceso a
memoria se duplica.
La salida
obvia a este dilema es el uso de un caché. Sin embargo, más que un caché
genérico, el MMU utiliza un caché especializado en el tipo de información que
maneja: El buffer de traducción
adelantada o anticipada
(Translation Lookaside Buffer, TLB). El TLB es una tabla asociativa
(un hash) en memoria de alta
velocidad, una suerte de registros residentes dentro del MMU, donde las llaves son las páginas y los valores son los marcos
correspondientes. De este modo, las búsquedas se efectúan en tiempo constante.
El TLB
típicamente tiene entre 64 y 1024 entradas. Cuando el procesador efectúa un
acceso a memoria, si la página solicitada está en el TLB, el MMU tiene la
dirección física de inmediato.9 En caso de no encontrarse la página en el
TLB, el MMU lanza un fallo de página
(page fault), con lo cual
consulta de la memoria principal cuál es el marco correspondiente. Esta nueva
entrada es agregada al TLB; por las propiedades de localidad de referencia que vimos anteriormente, la probabilidad
de que las regiones más empleadas de la memoria durante un área específica de
ejecución del programa sean cubiertas por relativamente pocas entradas del TLB
son muy altas.
Como sea,
dado que el TLB es limitado, es necesario explicitar un mecanismo que indique
dónde guardar las nuevas entradas una vez que el TLB está lleno y se produce un
fallo de página. Uno de los esquemas más comunes es emplear la entrada menos recientemente utilizada (LRU, Least Recently Used), nuevamente apelando a la localidad de
referencia; esto tiene como consecuencia necesaria que debe haber un mecanismo
que contabilice los accesos dentro del TLB (lo cual agrega tanto latencia como
costo); otro mecanismo (con obvias desventajas) es el reemplazar una página al
azar. Veremos con mayor detalle más adelante algunos de los mecanismos más
empleados para este fin, comparando sus puntos a favor y en contra.
4.2.2 Subdividiendo la tabla de páginas
Incluso
empleando TLBs, el espacio empleado por las páginas sigue siendo demasiado
grande. Consideremos un escenario más frecuente que el propuesto anteriormente:
Empleando un procesador con espacio de direccionamiento de 32 bits, y un tamaño
de página estándar (4KB, $212), hablamos ya de 1,048,576 ($2^{20}$)
páginas. Si cada entrada de la página ocupa 40 bits10 (esto es, 5 bytes), cada proceso
requeriría de 5MB (5 bytes por cada una de las páginas) solamente para
representar su mapeo de memoria. Esto, especialmente en procesos pequeños,
resultaría más gravoso para el sistema que los beneficios obtenidos de la
paginación.
Aprovechando
que la mayor parte del espacio de direccionamiento de un proceso está
típicamente vacío, se puede subdividir el identificador de página en dos (o
más) niveles, por ejemplo, separando una dirección de 32 bits en una tabla externa de 10 bits, una tabla interna de 10 bits, y el desplazamiento de 12 bits.
Paginación
en dos niveles: Una tabla externa de 10 bits, tablas intermedias de 10 bits, y marcos
de 12 bits
(esquema común para procesadores de 32 bits)
Este
esquema funciona adecuadamente para equipos con direccionamiento de hasta 32
bits. Sin embargo, recordemos que cada nivel de páginas conlleva un acceso
adicional a memoria en caso de fallo de página — Emplear paginación jerárquica
con un nivel externo y uno interno implica que un fallo de página triplica (y no duplica, como sería
con un esquema de paginación directo) el tiempo de acceso a memoria. Para
obtener una tabla de páginas manejable bajo los parámetros aquí descritos en un
sistema de 64 bits, tendríamos que septuplicar
el tiempo de acceso (cinco accesos en
cascada para fragmentos de 10 bits, y un tamaño de página de 14 bits, más
el acceso a la página destino).
Otra
alternativa es el emplear funciones
digestoras (hash functions)11 para mapear cada una de las páginas a un espacio muestral mucho más pequeño.
Cada página es mapeada a una lista de correspondencias simples12.
Un
esquema basado en funciones digestoras nos brinda características muy
deseables: El tamaño de la tabla de páginas puede variar según crece el uso de
memoria de un proceso (aunque esto requiera recalcular la tabla con diferentes
parámetros) y el número de accesos a memoria en espacios tan grandes como el de
un procesador de 64 bits se mantiene mucho más tratable. Sin embargo, por la
alta frecuencia de accesos a esta tabla, debe elegirse un algoritmo digestor
muy ágil para evitar que el tiempo que tome calcular la posición en la tabla
resulte significativo frente a las alternativas
Memoria compartida
Hay
muchos escenarios en que diferentes procesos pueden beneficiarse de compartir
áreas de su memoria. Uno de ellos es como mecanismo de comunicación entre
procesos (IPC, Inter Process Communication), en que
dos o más procesos pueden intercambiar estructuras de datos complejas sin
incurrir en el costo de copiado que implicaría copiarlas a través del sistema
operativo. Otro caso, mucho más frecuente, es el de compartir código.
Si un
mismo programa es ejecutado varias veces, y dicho programa no emplea mecanismos
de código auto-modificable, no
tiene sentido que las páginas en que se representa cada una de dichas
instancias ocupe un marco independiente — El sistema operativo puede asignar a
páginas de diversos procesos el mismo
conjunto de marcos, con lo cual puede aumentar la capacidad percibida de
memoria.
Y si bien
es muy común compartir los segmentos
de texto de los diversos programas que están en un momento dado en
ejecución en la computadora, este mecanismo es todavía más útil cuando hablamos
de bibliotecas del sistema: Hay
bibliotecas que son empleadas por una gran cantidad de programas13.
Uso de
memoria compartida: Tres procesos comparten la memoria ocupada por el texto del
programa (azul), difieren sólo en los datos.
Claro
está, para ofrecer este modelo, el sistema operativo debe poder garantizar que
las páginas correspondientes a las secciones
de texto (el código del programa) sean de sólo lectura.
Un
programa que está programado y compilado de forma que permita que todo su
código sea de sólo lectura es reentrante,
dado que posibilita que diversos procesos entren a su espacio en memoria sin
tener que sincronizarse con otros procesos que lo estén empleando.
Copiar al escribir (Copy on Write, CoW)
En los
sistemas Unix, el mecanismo más frecuentemente utilizado para crear un nuevo
proceso es el empleo de la llamada al sistema fork(). Cuando es invocado por un proceso, el sistema
operativo crea a un nuevo proceso idéntico
al que lo llamó, diferenciándose únicamente en el valor entregado por la llamada a fork(). Si ocurre algún error, el sistema entrega un
número negativo (indicando la causa del error). En caso de ser exitoso, El
proceso nuevo (o proceso hijo)
recibe el valor 0, mientras que el proceso
preexistente (o proceso padre) recibe el PID (número identificador de proceso)
del hijo. Esto es, es frecuente que veamos:
/* (...) */
int pid;
/* (...) */
pid = fork();
if (pid == 0) {
/* Soy el proceso hijo
*/
/* (...) */
} else if (pid < 0) {
/* Ocurrio un error, no
se creo un proceso hijo */
} else {
/* Soy el proceso padre
*/
/* La variable 'pid'
tiene el PID del proceso hijo */
/* (...) */
}
Este
método es incluso utilizado normalmente para crear nuevos procesos,
transfiriendo el ambiente
(variables, por ejemplo, que incluyen cuál es la entrada y salida
estándar de un proceso, esto es, a qué terminal están conectados, indispensable
en un sistema multiusuario). Frecuentemente, la primer instrucción que ejecuta
un proceso hijo es execve(), que carga a un nuevo programa
sobre del actual y transfiere la ejecución a su primer instrucción.
Cuesta
trabajo comprender el por qué de esta lógica si no es por el empleo de la
memoria compartida: El costo de fork() en un
sistema Unix es muy bajo, se limita a crear las estructuras necesarias en la
memoria del núcleo. Tanto el proceso padre como el proceso hijo comparten todas sus páginas de memoria — Sin
embargo, siendo dos procesos independientes, no deben poder modificarse más que
por los canales explícitos de comunicación entre procesos.
Memoria
de dos procesos inmediatamente después de la creación del proceso hijo por fork()
Esto
ocurre así gracias a un mecanismo llamado Copiar al escribir (Copy
on Write o CoW). Las
páginas de memoria de ambos procesos son las mismas mientras sean sólo leídas. Sin embargo, si uno de los procesos
modifica a cualquier dato en una de estas páginas, ésta se copia a un nuevo
marco, y deja de ser una página compartida. El resto de las páginas seguirá
siendo compartido.
Cuando el
proceso hijo modifica información en la primer página de su memoria, se crea
como una página nueva.
Incluso
cuando se ejecutan nuevos programas a través de execve(), es posible que una buena parte de la memoria se
mantenga compartida, por ejemplo, al referirse a copias de bibliotecas de
sistema.
Memoria virtual
Varios de
los aspectos mencionados en la sección de paginación van conformando a lo que conocemos como memoria virtual: Vimos ya que en un sistema que emplea
paginación, un proceso no conoce su dirección en memoria relativa a otros
procesos, sino que trabajan con una idealización
de la memoria, en la cual ocupan el espacio completo de direccionamiento, desde
el cero hasta el límite lógico de la arquitectura, independientemente del
tamaño físico de la memoria disponible.
Y si bien
el modelo mencionado de paginación nos llevó a que los diferentes procesos
pueden compartir regiones de
memoria y direccionar más
memoria de la físicamente disponible, no abordamos qué estrategia se emplearía
cuando el total de páginas solicitadas por todos los procesos activos en el
sistema superara el total de espacio físico. Es ahí donde entra en juego la memoria virtual: Para ofrecer a los
procesos mayor espacio en memoria del que existe físicamente, el sistema emplea
espacio en almacenamiento secundario
(típicamente, disco duro), a través de un esquema de intercambio (swap).
Esquema
general de la memoria, incorporando espacio en almacenamiento secundario,
representando la memoria virtual
Es
importante apuntar que la memoria virtual es gestionada de forma automática y transparente por el sistema operativo. No
hablaríamos de memoria virtual, por ejemplo, si un proceso pide explícitamente
intercambiar determinadas páginas.
Puesto de
otra manera: Del mismo modo que la segmentación permitió
hacer mucho más cómodo y útil al intercambio a través del intercambio parcial, permitiendo que continuara la ejecución del proceso incluso con
ciertos segmentos intercambiados
(swappeados) a disco, la
memoria virtual lo hace aún más conveniente al aumentar la granularidad del intercambio: Ahora
ya no sólo se enviarán a disco secciones lógicas completas del proceso
(segmentos), sino que podrá hacerse página por página, aumentando muy
fuertemente el rendimiento resultante. Veremos que, empleando memoria virtual,
de cierto modo la memoria física se vuelve sólo una proyección parcial de la memoria lógica, potencialmente mucho
mayor a ésta.
Técnicamente,
cuando hablamos de memoria virtual, no nos referimos ya a un intercambiador (swapper), sino que al paginador.
No hay comentarios:
Publicar un comentario