Resumen Sistemas Operativos

Silberchatz
Captulo 8: Memoria Principal
Hardware Bsico:
Respecto a la velocidad:
Las nicas reas de almacenamiento en la que el CPU puede
acceder directamente son la memoria principal y los registros
internos del propio procesador. Hay instrucciones de mquina
que toman como argumentos direcciones de memoria, pero no
existe ninguna instruccin que acepte direcciones de disco. Por
eso, todas las instrucciones y los datos utilizados deben estar en
alguno de esos dispositivos de almacenamientos, si los datos no
se encuentran en memoria, debern llevarse hasta all antes de
que la CPU pueda operar con ellos. Debido al costo de tiempo
que lleva acceder a la memoria principal, para obtener las
instrucciones y los datos, se utiliza bfer intermedio llamado
memoria cach.
Respecto a la proteccin:
Debemos asegurar que cada proceso tenga un espacio de
memoria separado, para hacer esto, debemos poder determinar
el rango de direcciones legales, mediante dos registros: base y
lmite, el primero almacena la direccin de memoria fsica legal
ms pequea y el segundo especifica el tamao del rango.
Por ejemplo: si el registro base contiene el valor 300040 y el
registro lmite es 120900. Entonces el programa podr acceder
legalmente a todas las direcciones comprendidas entre 300040
y 420940 (300040 + 120900).
La proteccin del espacio de memoria se consigue haciendo que
el hardware de la CPU (el sistema operativo no puede llevar a
cabo la proteccin) comparte todas las direcciones generadas en
modo usuario con el contenido de esos registros. Cualquier
intento, por parte de un programa que se est ejecutando en
modo usuario, de acceder a la memoria del sistema operativo o
a la memoria de otros usuarios har que se produzca una
interrupcin hacia el sistema operativo.

Los dos registros solo pueden ser cargados por el sistema

operativo, que utiliza una instruccin privilegiada especial (en
modo kernel). Este esquema permite al SO modificar el valor de
los registros, y evita que los programas de usuario cambien el
contenido de esos registros.

Reasignacin de direcciones:
Para que un programa pueda ejecutarse, este deber ser
cargado en memoria y colocado dentro de un proceso.
Los procesos del disco que estn esperando a ser cargados en
memoria para su ejecucin forman lo que se denomina cola de
entrada.
El procedimiento normal consiste en seleccionar uno de los
procesos de la cola de entrada y cargar dicho proceso en
memoria. Una vez que termina su ejecucin, el espacio ser
declarado como disponible.
Las direcciones de los programas pueden representarse de
diferentes formas y puede realizarse en cualquier de estos
pasos:
Tiempo de compilacin:
Si sabemos en el momento de realizar la compilacin, dnde va
a residir el proceso en memoria, podremos generar cdigo
absoluto. Si la ubicacin inicial cambiase en algn instante
posterior, entonces sera necesario recompilar ese cdigo.
Tiempo de carga:
Si no conocemos en tiempo de compilacin dnde va a residir el
proceso en memoria, el compilador deber generar cdigo
reubicable. En este caso, se retarda la reasignacin final hasta
el momento de la carga. Si cambia la direccin inicial, tan slo
es necesario volver a cargar el cdigo de usuario para incorporar
el valor modificado
Tiempo de ejecucin:
Si el proceso puede desplazarse durante su ejecucin desde un
segmento de memoria a otro, entonces es necesario retardar la
reasignacin hasta el instante de la ejecucin. En este caso en
especial, se necesita un hardware especial.

Espacios de direcciones lgico y fsico:

Una direccin generada por la CPU se denomina comnmente

direccin lgica, mientras que una direccin vista por la
unidad de memoria (es decir, la que se carga en el registro de
direcciones de memoria de la memoria) se denomina
comnmente direccin fsica.
Los mtodos de reasignacin en tiempo de compilacin y en
tiempo de carga generan direcciones lgicas y fsicas idnticas.
Sin embargo, el esquema de reasignacin de direcciones en
tiempo de ejecucin hace que las direcciones lgicas y fsicas
difieran. En este caso, usualmente decimos que la direccin
lgica es una direccin virtual.
La correspondencia entre direcciones virtuales y fsicas en
tiempo de ejecucin es establecida por un dispositivo hardware
que se denomina MMU (memory-management unit).
El programa de usuario nunca ve las direcciones fsicas reales.
Este maneja las direcciones lgicas , y el hardware de
conversin (mapeo) de memoria convierte esas direcciones
lgicas en direcciones fsicas.

Carga dinmica:
Como un programa necesita cargarse en la memoria fsica para
poder ejecutarse, este puede depender del tamao del
dispositivo de almacenamiento, por lo que podemos utilizar un
mecanismo denominado carga dinmica.
Este mecanismo se enfoca en cargar solamente las rutinas que
van a ser invocadas (todas se ubican en disco en un formato de
carga reubicable). Cuando una rutina necesita llamar a otra
rutina, la rutina que realiza la invocacin comprueba primero si
la otra ya ha sido cargada, si no es as, se invoca el cargado de
montaje reubicable para que se cargue en memoria la rutina
deseada y para que actualice las tablas de direcciones del
programa con el fin de reflejar este cambio. Despus, se pasa el
control a la rutina recin cargada.

Ventajas:
La ventaja de este mecanismo es que una rutina no
utilizada no se cargar nunca en memoria.
No se requiere ningn soporte especial por parte del
sistema operativo. Es responsabilidad de los usuarios
disear sus programas para poder aprovechar dicho
mtodo.

Montaje dinmico y bibliotecas compartidas:

Algunos sistemas operativos slo permiten el montaje esttico,

mediante el cual las bibliotecas de lenguaje del sistema se
tratan como cualquier otro mdulo objeto y son integradas por
el cargador de lenguaje del sistema dentro de la imagen binaria
del programa.
En el montaje dinmico, se utiliza un stub (pequeo fragmento
de cdigo que indica cmo localizar la rutina adecuada de
biblioteca residente o cmo cargar la biblioteca si la rutina no
est todava presente). Cuando se ejecuta el stub:
ste comprueba si la rutina necesaria ya se encuentra en
memoria.
si no est, el programa carga en memoria la rutina.
En cualquiera de estos dos casos, el stub se sustituye as mismo
por la direccin de la rutina y la ejecuta. As, la siguiente vez
que se ejecute ese segmento de cdigo concreto, se ejecutar
directamente la rutina de biblioteca, sin tener que realizar
nuevamente el montaje dinmico.
Con este mecanismo, se puede modificar una biblioteca por una
nueva versin y todos los programas que hagan referencia a la
biblioteca emplearn automticamente la versin ms reciente,
este mecanismo se conoce como bibliotecas compartidas.
A diferencia de la carga dinmica, el montaje dinmico suele
requerir algo de ayuda por parte del sistema operativo.

Intercambio:
Un proceso en ejecucin puede ser intercambiado
temporalmente para obtener ms memoria, sacndolo de ella y
almacenndolo en un almacn de respaldo (por ej: disco), para
luego volver a cargarlos en memoria y as continuar con su
ejecucin.
Normalmente un proceso descargado se volver a cargar en el
mismo espacio de memoria que ocupaba anteriormente. Esta
restriccin est dictada por el mtodo de reasignacin de las
direcciones. Si la reasignacin se realiza en tiempo de
ensamblado o en tiempo de carga, entonces no resulta sencillo
mover el proceso a una ubicacin diferente. En cambio, en una
reasignacin en tiempo de ejecucin no habra problemas
porque las direcciones fsicas se calculan en tiempo de
ejecucin.

El intercambio est restringido por varios factores:

El tiempo que se tarda en intercambiar los procesos
Dependiendo si el proceso debe operaciones de E/S: se
puede realizar dos acciones, una es no descargar nunca un
proceso que deba E/S o ejecutar nicamente operaciones
con bferes del SO

Asignacin de memoria contigua

La memoria principal debe albergar tanto el sistema operativo
como los diversos procesos de usuario, por lo que est
usualmente dividida en dos particiones: una para el SO
residente (en la zona baja o alta de la memoria, el principal
factor que afecta esta decisin es la ubicacin del vector de
interrupciones) y otra para los procesos de usuario.

Mapeo de memoria y proteccin:

Podemos proporcionar estas caractersticas utilizando:
Un registro de reubicacin: contiene el valor de la direccin
fsica ms pequea.
Un registro lmite: contiene el rango de las direcciones
lgicas.
La MMU convertir la direccin lgica dinmicamente sumndole
el valor contenido en el registro de reubicacin (direccin fsica
= registro lmite + registro de reubicacin).
Es esquema basado en un registro de reubicacin constituye
una forma efectiva de permitid que el tamao del sistema
operativo cambie dinmicamente.

Asignacin de memoria:
Uno de los mtodos ms simples para asignar memoria consiste
en dividirla en particiones de tamao fijo, donde en cada una
entra un proceso. El sistema operativo mantiene una tabla que
indica qu partes de la memoria estn disponibles y cules
estn ocupadas. Inicialmente, toda la memoria est disponible
para los procesos de usuario y se considera como un nico
bloque de gran tamao de memoria disponible, al que se
denomina agujero. Cuando llega un proceso y necesita
memoria, buscamos un agujero lo suficientemente grande como
para albergar este proceso. Incluimos ese proceso en el bloque
de memoria y declaramos la restante como disponible.
El sistema operativo debe considerar a cul proceso elegir, de la
cola de entrada, para asignarlo a la memoria. Este buscar en el
conjunto de agujeros dispersos en toda la memoria para
verificar si el tamao puede satisfacer al proceso, en el caso que
no encuentre un bloque, puede esperar a que se desocupe uno.
Adems, puede reordenar la cola de entrada mediante algn
algoritmo de planificacin.
Si un proceso libera un bloque de memoria, y este ltimo es
adyacente a otro bloque de memoria libre, ambas particiones se
unen formando una sola. En este punto, el sistema debe puede
tener que comprobar si hay procesos esperando a que se les
asigne memoria y si esta nueva memoria liberada y
recombinada permite satisfacer las demandas de algunos de los
procesos en espera.
Este procedimiento constituye un caso concreto del problema
general de asignacin dinmica de espacio de
almacenamiento, que se ocupa de cmo satisfacer una
solicitud de tamao n a partir de una lista de agujeros libres.

Soluciones a este problema, mediante algoritmos de ubicacin:

Primer Ajuste (First-fit): se asigna el primer agujero que
sea lo suficientemente grande. La exploracin puede
comenzar desde el principio o en el punto en que hubiera
terminado la exploracin anterior.
Mejor Ajuste (Best-fit): Se asigna el agujero ms pequeo
que tenga el tamao suficiente. Debemos explorar la lista
completa (a menos que este ordenada segn su tamao).

 Peor Ajuste (Worst-fit): Se asigna el agujero de mayor

tamao. De nuevo, debemos explorar la lista completa, a
menos que sta est ordenada por tamaos.
Siguiente ajuste (Next-fit): se asigna el agujero ms
prximo que se encontr (el puntero arranca a partir de la
ltima asignacin).
Tanto las estrategias del primer ajuste, como la de mejor ajuste
son mejores que la de peor ajuste en trminos del tiempo
necesario y de la utilizacin del espacio de almacenamiento. En
general, la del primer ajuste es ms rpida de implementar.
Fragmentacin:
Tanto la estrategia del primer ajuste (First-fit) como la de mejor
ajuste (Best-fit) para la asignacin de memoria sufren del
problema denominado fragmentacin externa, esto aparece
cuando hay un espacio de memoria total suficiente como para
satisfacer una solicitud, pero esos espacios disponibles no son
contiguos; el espacio est fragmentado en un gran nmero de
pequeos agujeros.
La fragmentacin tambin puede ser interna, se lo denomina al
espacio desperdiciado que se encuentra en una particin, a la
que le asignamos anteriormente un proceso que no ocupe todo
el bloque de memoria. Por ejemplo: Tenemos bloque de memoria
de 18464 Bytes, y un proceso que demanda 18462 Bytes. Si
asignamos ese proceso al espacio de memoria, sobrarn 2
Bytes, a este desperdicio se lo considera como fragmentacin
interna.
Una solucin al problema de la fragmentacin externa
consiste en la compactacin. El objetivo es mover el contenido
de la memoria con el fin de situar toda la memoria libre de
manera contigua, para formar un nico bloque de gran tamao.
Si la reubicacin es esttica y se lleva a cabo en tiempo de
ensamblado o en tiempo de carga, no se puede utilizar el
mecanismo de compactacin.
Si la reubicacin es dinmica y se lleva a cabo en tiempo
de ejecucin, s se puede realizar este mecanismo. Ya
que slo requerir mover el programa y los datos y luego
cambiar el registro base para reflejar la nueva direccin
base utilizada.

El algoritmo de compactacin ms simple es la de mover todos

los procesos hacia uno de los extremos de la memoria,
produciendo de esta manera un nico agujero en el otro
extremo.
Otra posible solucin a la fragmentacin externa es la de
permitir que el espacio de direcciones lgicas de los procesos no
sea contiguo, lo que hace que podamos asignar memoria fsica a
un proceso con independencia de dnde est situada dicha
memoria. Hay dos tcnicas complementarias que permiten
implementar esta solucin:

Paginacin: es un esquema de gestin de memoria que

permite que el espacio de direcciones fsicas de un proceso
no sea contiguo. La paginacin evita el considerable
problema de encajar fragmentos de memoria de tamao
variable en el almacn de respaldo (el almacn tambin
sufre el problema de la fragmentacin, pero con la
salvedad de que el acceso es mucho ms lento, lo que
hace que la compactacin sea imposible).

o Mtodo bsico
El mtodo bsico para implementar la paginacin consiste en
descomponer la memoria fsica en una serie de bloques de
tamao fijo denominados marcos (frames). Cuando hay que
ejecutar un proceso, sus pginas se cargan desde el almacn
de respaldo en los marcos de memoria disponibles. El
almacn de respaldo est divido en bloques de tamao fijo
que tienen el mismo tamao que los marcos de memoria.
Toda direccin generada por la CPU est dividida en dos
partes: en un nmero de pgina (p) y en un nmero de
desplazamiento (Offset). El nmero de pgina se utiliza
como ndice para una tabla de pginas.
La tabla de pginas contiene la direccin base de cada pgina
en memoria fsica, est direccin base se combina con la de
desplazamiento de pgina para definir la direccin de
memoria fsica que se enva a la unidad de memoria.

Puesto que el sistema operativo gestiona la memoria fsica,

debe ser consciente de los detalles relativos a la asignacin de
la memoria fsica: qu marcos han sido asignados, qu marcos
estn disponibles, cul es el nmero total de marcos, etc. Esta

informacin se suele mantener en una estructura de datos

denominada tabla de marcos. Adems el sistema operativo
mantiene una copia de las tablas de pginas, del contador de
instrucciones y de los contenidos de los registros de cada
proceso (todo esto sirve para poder traducir las direcciones
lgicas a fsicas)
o Soporte hardware:
La implementacin hardware de la tabla de pginas puede
hacerse de varias maneras, la ms simple es la de
implementar la tabla de pginas como un conjunto de
registros dedicados. El uso de registros para la tabla de
pginas resulta satisfactorio si esta tabla es
razonablemente pequea (ej, 256 entradas), como las
computadoras actuales tienen casi 1 milln de entradas,
no resulta factible utilizar este mtodo. En lugar de ello, la
tabla de pginas se mantiene en memoria principal,
utilizndose un registro base de la tabla de pginas
para apuntar a la tabla de pginas.
El problema de esta tcnica es el tiempo requerido para
acceder a una ubicacin de memoria del usuario (una
solucin posible es la de introducir una pequea cach
hardware especial, denominada bfer de consulta de
traduccin- TLB).
El bfer TLB se utiliza con las tablas de pginas de la forma
siguiente: el bfer TLB contiene slo unas cuantas
entradas de la tabla de pginas; cuando la CPU genera
una direccin lgica, se presenta el nmero de pgina al
TLB y si se encuentra ese nmero en la pgina, su nmero
de marco correspondiente estar inmediatamente
disponible y se utilizar para acceder a la memoria.
Si el nmero de pgina no se encuentra en el bfer TLB (se
conoce como fallo de TLB), es necesario realizar una
referencia a memoria para consultar la tabla de pginas,
para obtener el marco.
Adems, podemos aadir el nmero de pgina y el nmero
de marco a la TLB, para poder obtener los datos
rpidamente en la prxima referencia.
Si la TLB est llena, el sistema operativo deber
seleccionar una de las entradas para sustituirla (puede ser
aleatoriamente, o con un algoritmo).
Algunos bferes TLB almacenan identificadores del
espacio de direcciones (ASID) que identifican

unvocamente cada proceso y se utiliza para proporcionar

mecanismos de proteccin del espacio de direcciones
correspondiente a ese proceso. Cuando el TLB trata de
resolver los nmeros de pginas virtuales, verifica que el
identificador ASID del proceso que actualmente se est
ejecutando se corresponda con el identificador ASID
asociado con la pgina virtual. Si ambos identificadores no
coinciden, el intento se trata como un fallo de TLB.
Adems de proporcionar proteccin del espacio de
direcciones correspondiente a ese proceso, los ASID
permiten al TLB contener entradas simultneamente para
varios procesos distintos. (Si no lo soportara, cada vez que
se seleccione una nueva tabla de pginas por ej en cada
cambio de contexto- seria necesario borrar el TLB para
garantizar que el siguiente procesos
que se ejecute no utilice una informacin incorrecta de
traduccin de direcciones).
o Proteccin:
Se consigue mediante una serie de bits de proteccin
asociados con cada marco. Normalmente, estos bits se
mantienen en la tabla de pginas. Uno de los bits puede
definir una pgina como lectura-escritura o de slo
lectura. Al mismo tiempo que se calcula la direccin
fsica, pueden comprobarse los bits de proteccin para
verificar que no se est haciendo ninguna escritura en
una pgina de slo lectura. Todo intento de escribir una
pgina de slo lectura provocar una interrupcin
hardware al sistema operativo.
Generalmente, se suele asociar un bit adicional con
cada entrada de la tabla de pginas: un vlidoinvlido. Cuando se configura este bit como:
"Vlido: la pgina asociada se encontrar el
espacio de direcciones lgicas del proceso y
ser, por tanto, una pgina legal.
"Invlido": la pgina no se encuentra en el
espacio de direcciones lgicas del proceso.
El principal problema que genera este esquema es el de la
fragmentacin interna. Ya que no se aprovechara todo el
rango de direcciones que ofrece la pgina (debido a que
hay un determinado rango que se clasifica como invlido y
por lo tanto, este no ser utilizado).

Para este tipo de problemas algunos sistemas proporcionan

mecanismos hardware especiales, en la forma de un
registro de longitud de la tabla de pginas (PTLR,
page-table length register), para indicar el tamao de la
tabla de pginas. Este valor se compara con cada direccin
lgica para verificar que esa direccin se encuentre dentro
del rango de direcciones vlidas definidas para el proceso.
Si esta comprobacin fallara, se producira una interrupcin
de error dirigida al sistema operativo.
o Pginas compartidas:
Una ventaja de la paginacin es la posibilidad de
compartir cdigo comn. Pueden compartirse
programas que se utilicen a menudo, como por ejemplo
compiladores, sistemas de ventanas, editores de texto,
bibliotecas de tiempo de ejecucin, sistemas de base de
datos, etc. Para poder compartirlo, el cdigo debe ser
reentrante (es cdigo que no se auto-modifica; nunca
cambia durante la ejecucin). El carcter de slo-lectura
del cdigo compartido no debe dejarse a expensas de la
correccin de ese cdigo, sino que el propio sistema
operativo debe imponer esta propiedad.
De esta forma cada usuario tendr:
Una copia del programa que se
encuentra en la memoria fsica
(es una sola para todos los
procesos)
Una copia del espacio de datos
(una por cada usuario)

Estructura de la tabla de pginas:

Algunas de las tcnicas para estructurar las tablas de pginas
son:
1. Paginacin Jerrquica
La mayora de los sistemas informticos modernos soportan
un gran espacio de direcciones lgicas. En este tipo de
entorno, la propia tabla de pginas llega a ser excesivamente
grande. Una solucin simple a este problema consiste en
dividir la tabla de pginas en fragmentos ms pequeos y
podemos llevar a cabo esta divisin de varias formas

distintas. Una de esas formas consiste en utilizar un algoritmo

de paginacin de dos niveles, en el que la propia tabla de
pginas est tambin paginada, este esquema tambin se
conoce con el nombre de tabla de pginas con
correspondencia (mapeo) directa.
2. Tablas de pginas Hash
Una tcnica comn para gestionar los espacios de direcciones superiores a 32
bits consiste en utilizar una tabla hash de pginas, donde el valor hash es el
nmero de pgina virtual. . Cada entrada de la tabla hash contiene una lista
enlazada de elementos que tienen como valor hash una misma ubicacin (con
el fin de tratar las colisiones). Cada elemento est compuesto de tres campos:
el nmero de pgina virtual,
(2) el valor del marco de pgina mapeado
(3) un punto del siguiente elemento de la lista enlazada.
El algoritmo funciona de la forma siguiente: al nmero de pgina virtual de la
direccin virtual se le aplica una funcin hash para obtener un valor que se
utiliza como ndice para la tabla hash. El nmero de pgina virtual se
compara con el campo 1 del primer elemento de la lista enlazada. Si hay una
correspondencia, se utiliza el marco de pgina correspondiente (campo 2)
para formar la direccin fsica deseada. Si no se produce una
correspondencia, se exploran las subsiguientes entradas de la lista enlazada
hasta encontrar el correspondiente nmero de pgina virtual.
3. Tablas de pginas invertidas
Usualmente, cada proceso tiene una tabla de pginas
asociada. La tabla de pginas incluye una entrada por cada
pgina que el proceso est utilizando (o un elemento por
cada direccin virtual, independientemente de la validez de
sta). Esta representacin de la tabla resulta natural, ya que
los procesos hacen referencia a las pginas mediante las
direcciones virtuales de stas. El sistema operativo debe
entonces traducir cada referencia a una direccin fsica de
memoria. Puesto que la tabla est ordenada segn la
direccin virtual, el sistema operativo podr calcular dnde se
encuentra en la tabla la entrada de direccin fsica asociada y
podr utilizar dicho valor directamente. Pero una de las
desventajas de este mtodo es que cada tabla de pgina
puede estar compuesta por millones de entradas. Estas
tablas pueden ocupar una gran cantidad de memoria fsica,

simplemente para controlar el modo en que se estn

utilizando otras partes de la memoria fsica. Para resolver
este problema, podemos utilizar una tabla de pginas
invertida. Las tablas de pginas invertidas tienen una
entrada por cada marco de la memoria. Cada entrada est
compuesta de la direccin virtual de la pgina almacenada en
dicha ubicacin de memoria real, e incluye informacin
acerca del proceso que posee dicha pgina. Por tanto, en el
sistema slo habr una nica tabla de pginas y esa tabla
slo tendr una entrada por cada pgina de memoria fsica.
Desventajas:
Aunque este esquema permite reducir la cantidad de
memoria necesaria para almacenar cada tabla de pginas,
incrementa la cantidad de tiempo necesaria para explorar
la tabla cuando se produce una referencia a una pgina
Los sistemas que utilizan tablas de pginas invertidas
tienen dificultades para implementar el concepto de
memoria compartida.

Segmentacin:
La segmentacin es un esquema de gestin de memoria que
interpreta a esta como un conjunto de segmentos de tamao
variable y sin ninguna ordenacin especfica.
Un espacio lgico de direcciones es una coleccin de segmentos
y cada segmento tiene un nombre y una longitud.
Las direcciones especifican tanto el nombre del segmento como
el desplazamiento dentro de ese segmento. El usuario
especifica, por tanto, cada direccin proporcionando dos valores:
un nombre de segmento y un desplazamiento (en la paginacin,
el usuario especificaba una nica direccin, que el hardware
particionaba en un nmero de pginas y en un desplazamiento
de forma invisible para el programador).
Hardware:
Aunque el usuario puede ahora hacer referencia a los objetos
del programa utilizando una direccin bidimensional, la memoria

fsica real contina siendo, por supuesto, una secuencia

unidmensional de bytes. Por tanto, deberemos definir una
implementacin para mapear 1 direcciones bidimensionales
definidas por el usuario sobre las direcciones fsicas
unidimensionales. Este mapeo se lleva a cabo mediante una
tabla segmentos. Cada entrada de la tabla de segmentos
tiene una direccin base del segmento y un lmite del segmento.
La direccin base del segmento contiene la direccin fsica
inicial del lugar donde el segmento reside dentro de la memoria,
mientras que el lmite del segmento especifica la longitud de
ste.