Módulo 5
ADMINISTRACIÓN DE
MEMORIA CENTRAL
Funciones y Operaciones
Funciones y Operaciones del Adm. Mem
Consideraciones
• Por cuestiones de diseño, el único espacio de memoria que el procesador
puede utilizar es la Memoria central (MC)
• Uhhhmmmm... y los Caches??
• Son para mejorar la performance y en general replican el contenido de la MC
• Uhhhmmmm (si... otro!) …. y los registros del procesador??
• Sí!!!! Esos sí, pero son muy pequeños y solo los utiliza para realizar sus operaciones
• ...pero los discos....????
• No… no…. esos NO!!. Es almacenamiento secundario. No es accesible directamente por el procesador. Están conectados
al sistema mediante el módulo de I/O. lo vemos mas adelante
• Los programas deben cargarse a la MC antes de ser ejecutados
• …Todo completo???
• Depende.... de como se gestione la memoria (de eso se trata el tema)
• También está relacionado con el HW que disponga el equipo, en especial con el MMU
Funciones y Operaciones del Adm. Mem
Espacio de direccionamiento
• La Memoria Central está estructurada como un arreglo direccionable de BYTES.
• Cada operación de lectura/escritura se hará de a 8 bits (no menos)
• Un procesador que soporta un espacio de direccionamiento de 16 bits puede
referirse directamente a hasta 216 bytes, esto es, hasta 65 536 bytes (64 KB).
• En procesadores de 32 bits, sus registros pueden referenciar hasta 4 294 967
296bytes (4 GB) de RAM
• No obstante, 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 bytes 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 Hexabytes).
• En la práctica, por cuestiones económicas van desde 2 40 a 248 (1 a 256 Terabytes).
Funciones y Operaciones del Adm. Mem
Hardware: el MMU
• ¿Por qué hace falta un Memory Manager Unit (MMU) ?
• Multitarea (multiprogramación) => Múltiples programas en MC => El S.O debe
resolver como ubicar los programas en la memoria física disponible.
• Ir mas allá de la memoria física disponible (Memoria virtual)
• Verificar los límites entre los que un proceso puede acceder al espacio asignado
(ejemplo: Registro base/límite)
• Uhhmmmm … pero no lo hace el SO???
• Es muy costoso delegarlo en el SO
Funciones y Operaciones del Adm. Mem
Hardware: memora Cache
• ¿Por qué un cache?
• La velocidad del procesador >> que la de la MC. Influye directamente en el
rendimiento ya que si no está el dato, el sistema detiene su ejecución (stall)
• ¿Qué es?
• Memoria de alta velocidad que está entre el Procesador y la MC que guarda
copias de las páginas accedidas partiendo del principio de localidad de
referencia:
• Loc. Temporal: probabilidad de reutilizar un recurso recientemente utilizado
• Localidad espacial: La probabilidad de que un recurso aún no requerido sea accedido
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.
• El precio de un sistema varía significativamente dependiendo de los
tamaños de caches de Nivel 2 y Nivel 1 con el que cuenta.
Funciones y Operaciones del Adm. Mem
Espacio de Memoria de un proceso
• Cuando se crea un proceso, la carga se realiza con la
siguiente estructura:
• Sección (o segmento) de texto o código Es la imagen en memoria
de las instrucciones a ser ejecutadas. Usualmente, ocupa las
direcciones más bajas del espacio en memoria.
• Sección de datos Espacio fijo preasignado para las variables
globales y datos inicializados (como las cadena de caracteres por
ejemplo). Se fija en tiempo de compilación, y no puede cambiar
(aunque los datos que cargados allí sí cambian en el tiempo de vida
del proceso).
• Espacio de libres (HEAP) Espacio 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.
• Lenguajes dinámicos (C )-> Free/Malloc
• Lenguajes gestión automática (java)->, garbage collector.
• Pila de llamadas (stack) Espacio de memoria que se usa para
almacenar la secuencia 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.
Funciones y Operaciones del Adm. Mem
Resolución de direcciones
• El compilador reemplaza las variables/funciones
simbólicas por las direcciones de memoria a donde se
ubican.
• Para poder coexistir con otros procesos, esas
direcciones deben ser traducidas a la posición relativa,
con alguna de las siguientes estrategias:
• En tiempo de compilación: Las direcciones son
absolutas/fijas. Ej: [Link]
• En tiempo de carga: El loader calcula las ubicaciones al
momento del inicio del programa (ej: Reg Base + offset)
• En tiempo de ejecución: El programa NUNCA hace
referencia a una ubicación fija (ej: base_frame +offset)
Asignación de memoria
contigua
Asignación de Memoria
contigua
Monoprogramados/por lotes-> El SO casi no necesitaba
gestionar la memoria.
• Por qué???
Asignación de Memoria
contigua
• Particiones fijas : Se parte la memoria en
espacios fijos predeterminados.
• Algunas cuestiones
• ¿¿Cuántos programas puedo ejecutar??
• Si el programa necesita X bytes y tengo Y
bytes...
• Si X > Y??
• Si X = Y ??
• Si X < Y ??
• ¿¿Cuál es el tamaño máximo de los
programas??
• Pueden usar Memoria virtual
• … Y las I/O pendientes??
• Es costoso en tiempo/recursos??
Asignación de Memoria
contigua
• Particiones variables: asignación dinámica de acuerdo al tamaño a
ubicar Compactación
• Algunas cuestiones:
• ¿Qué pasa cuando los procesos terminan y los
bloques se reusan??
• Si tengo varios frames libres de diversos tamaños en
cuál ubico el proceso?
• ¿Cuál es el tamaño máximo de los programas?
• Fragmentación externa -> defragmentación/compactación
(Muy costoso!)
• Tamaño máximo determinado de los programas
• Algoritmos:
• First Fit
• Best Fit
• Worst Fit
• Pueden usar Memoria virtual
Compactación: Para minimizar la fragmentación,
el sistema puede realizar una “compactación”,
que implica reubicar la memoria de los procesos
juntando el espacio libre
Segmentación
Segmentación
• Divide la memoria en "segmentos de tamaño variables"
• Los segmentos se corresponden con las distintas partes de un
programa (código, tabla de símbolos, stack, heap)
• Los segmentos pueden tener distintos tipos de acceso (read only,
write, execution).
• Se pueden compartir segmentos entre distintos procesos.
• Las bibliotecas ligadas dinámicamente (link edited) se representan
en segmentos independientes
• Se puede utilizar memoria virtual
• El espacio libre se gestiona en forma similar a particiones
variables
Segmentación
• Las direcciones están compuestas por Nro de segmento + Desplazamiento (s:d)
• El sistema operativo mantiene una SMT (Segment Memory Table) por proceso
¿Cómo se administra? que tiene el Nro de segmento, el tamaño y la dirección de inicio. El espacio
libre se gestiona con el criterio de particiones variables
• Cuando se requiere una dirección, se recupera el inicio del segmento en la SMT
y se le suma el desplazamiento (Offset) y se obtiene la dirección en la MC
(memoria central)
Cuestiones: ??? • ¿Qué pasa con la fragmentación?
• ¿Se necesita soporte de Hardware?
Paginación
Paginación pura o simple
• El proceso se divide en bloques de tamaño fijo llamados
"páginas" (pages)
• La memoria física se divide en una serie de marcos (frames) del
mismo tamaño que las páginas
• Por lo general, los frames/pages se dividen en porciones de entre
512B (29) y 16MB (224) - Siempre son potencias de 2
• Para el direccionamiento se divide el bus de direcciones
considerando N bits para la página y M bits para el
desplazamiento (Offset)
Paginación pura
o simple
• Las direcciones están compuestas por Nro de Página+ Desplazamiento (p:d)
• El sistema operativo mantiene una MPT (Memory Page Table) por proceso que
¿Cómo se administra? tiene el Nro de página, el tamaño y la dirección de inicio. El espacio
ocupado/libre se administra con una tabla de bits por frame MFT (Memory
Frame Table)
• Cuando se requiere una dirección, se recupera el inicio del frame en la MPT y
se le suma el desplazamiento (Offset) y se obtiene la dirección en la MC
(memoria central)
• ¿Necesita Soporte de HW?
• ¿Qué pasa con la fragmentación?
Cuestiones: ??? •
•
¿Cuál es el tamaño de página óptimo?
¿Cuánto ocupa la tabla de páginas?
• ¿Puedo compartir memoria entre procesos?
Paginación pura o simple
• ¿Necesita Soporte de HW?
• ¡Obvio! Leer/cargar las tablas para calcular las direcciones es sumamente costoso, el overhead es muy grande
• Soluciones: Además del MMU, se pueden implementar TLBs y caches
• ¿Qué pasa con la fragmentación?
• Se reduce mucho respecto de la asignación contigua, solo se fragmentan porciones de páginas.
• No tiene el problema de la segmentación. Cuando un frame se libera, se puede volver a reasignar
• ¿Cuál es el tamaño de página óptimo?
• Uhhhmmm... Páginas grandes -> mucha fragmentación interna, páginas chicas -> tabla de páginas muy grande, PCB
también más grande, transferencias entre MC y Disco más costosas
• ¿Cuánto ocupa la tabla de páginas?
• Ejemplos: Procesador 16 bits y páginas de 13bits (8KB) => 2^3 = 8 entradas. ¡Insignificante!
Procesador 32 bits y páginas de 12bits(4KB) => 2^20 = 1.048.576 entradas . x (20b frame + 20b pág ) ¡Unos
5MB!
¿¿¿Procesador de 64bits ??? ¡Inmanejable!
• Solución: Paginación multinivel
• ¿Puedo compartir memoria entre procesos como en segmentación?
• Si... Por ejemplo, cuando se crea un proceso hijo se copia el espacio de memoria del padre, apuntado a las páginas del
padre, cuando se modifican se reescriben en un frame nuevo, de esta forma, las páginas de solo lectura y/o ejecución
son compartidas por ambos procesos
Direccionamiento con TLB
Translation Lookaside Buffer (TLB)/Buffer de
traducción anticipada: El TLB es una tabla
asociativa (un hash) en memoria de alta
velocidad, una suerte de registros residentes
dentro de la 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
Direccionamiento con
TLB y Cache
Paginación Multinivel
Se definen tablas de directorios, que a su vez
apuntan a tablas de páginas
Ejemplo: Sistema de 32 bits, con 10 para la
tabla externa, 10 para la interna y 12 para el
desplazamiento
Direccionamiento
Memoria compartida
Se pueden compartir solo las
páginas que son de solo
lectura
Copiar al escribir (copy on write, CoW)
(a) Inmediatamente después de la creación del proceso (b) Cuando el proceso hijo modifica información en la primer
hijo por fork() página de su memoria, se
crea como una página nueva.
Memoria Virtual
Paginación sobre demanda
En general, memoria virtual es la utilización de una memoria
secundaria (por ejemplo, parte de un disco). De esta forma, los
procesos trabajan con una “idealización de la memoria”, en el cual
pueden ocupar hasta el 100% de la capacidad de direccionamiento,
independiente de la memoria física con la que cuenta el sistema.
Memoria La memoria virtual es gestionada de forma automática y
transparente por el sistema operativo. No se considera memoria
Virtual
virtual, por ejemplo, si un proceso pide explícitamente intercambiar
determinadas páginas
Swapping : Es el intercambio entre la memoria entre distintos
niveles de memoria
Swapping
Es el intercambio de información entre 2 niveles de memoria
• Swap-in: Es cuando el intercambio se hace desde un dispositivo de menor jerarquía a
uno de mayor jerarquía (ej. De Disco duro a MC)
• Swap-out: Es cuando el intercambio se hace desde un dispositivo de mayor jerarquía a
uno de menor jerarquía (ej. De Cache L1 a MC)
Algunas consideraciones:
• ¿Qué pasa si el proceso a suspender tiene
I/O pendiente?
• Solo se pueden pasar a suspendidos los
procesos que no tengan pendientes
operaciones de I/O, o
• Ejecutar operaciones de I/O sobre
buffers del S.O Políticas de Administración de Memoria Virtual
• ¿Que pasa si el intercambio es excesivo? • Fetch (búsqueda) → Cuando debe llevarse una pagina a MC
• Eso es HIPERPAGINACION O TRASHING! • Placement (colocación) → A donde debe ubicarse en la MC
• ¿Y la performance? • Replacement (reemplazo)→Cual es la página que se va a
• ¿Dónde se guardan las páginas descargadas? reemplazar
Paginación bajo demanda
• En paginación sobre demanda, el sistema emplea
espacio en almacenamiento secundario (típicamente,
disco duro), mediante un esquema de intercambio
(swap) guardando y trayendo páginas enteras.
• Utiliza un cargador (pager) “lazy” (flojo/perezoso). Al
comenzar la ejecución de un proceso, solo se cargan a
memoria las páginas necesarias a medida que se van
requiriendo.
• Si la página requerida no se encuentra en memoria, el
pager deberá cargarla
La técnica opuesta a Lazy es Eager (ansioso/glotón) en
el que se carga todo al momento inicial
Direccionamiento
Fallo de página
1. Verifica en el PCB si esta solicitud corresponde a una página que ya ha sido
asignada a este proceso.
2. En caso de que la referencia sea inválida, se termina (suspende) el proceso.
3. Procede a traer la página del disco a la memoria. El primer paso es buscar
un marco disponible (por ejemplo, por medio de una tabla de asignación
de marcos).
4. Solicita al disco la lectura de la página en cuestión hacia el marco
especificado.
5. Una vez que finaliza la lectura de disco, modifica tanto al PCB como al TLB
para indicar que la página está en memoria.
6. Termina la suspensión del proceso, continuando con la instrucción que
desencadenó al fallo. El proceso puede continuar sin notar que la página
había sido intercambiada.
Rendimiento
te: Tiempo efectivo de acceso a memoria.
p: Probabilidad de fallo de página
ta: Tiempo de acceso a memoria (entre 10 y 200 ns)
tf : Tiempo que toma atender a un fallo de página (aprox 8 ms – posicionado de cabeza + latencia, descartando ta )
Si p = 1/1000 (Un fallo cada 1000 accesos) =>
En promedio el te es 40 veces mayor que sin usar swapping
Reemplazo de páginas
Situación:
Profe: El sistema está comprometido mas allá de la memoria física disponible, y necesita cargar una
página que no está presente!
Alumno: Fácil!!! Reemplazo una de las páginas que está en memoria, y listo!
Profe: Ahhh… ok!!! Cuál?? Porqué??
Alumno: ehhhh… ehhhh…
Elección de la víctima
• La página ya se encuentra en MV (memoria virtual)??
• Fue modificada en MC ?
• Es del mismo proceso o de otro?
• Cuándo se la accedió por última vez?
• Cuándo se modificó?
Considerando esto, se pueden implementar diferentes algoritmos para
la elección de la página víctima.
Reemplazo de páginas
¿Si se le otorgan más frames a un proceso, entonces deberían haber más o menos
fallos??
Anomalía de Belady:
En general, si se le asignan más frames a un proceso, en consecuencia deberían producirse menos fallos
de página, pero en algunos algoritmos, con determinada secuencias de llamadas, se pueden presentar más
fallos de página
Ejemplo: 3 frames y la cadena de referencia: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
Relación ideal entre el número de marcos Comportamiento del algoritmo *fifo* exhibiendo la
y fallos de página. anomalía de Belady al pasar de tres a cuatro marcos.
Reemplazo de páginas . Algoritmos
Primero en entrar, primero en salir - FIFO
Ejemplo: 3 frames y la cadena de referencia: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
• Simple
• Vulnerable a la anomalía de Belady
Reemplazo de páginas . Algoritmos
Reemplazo de páginas óptimo (OPT, MIN)
Ejemplo: 3 frames y la cadena de referencia: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
• Requiere conocer la cadena de referencias a priori (futurismo!!)
• Solo sirve para comparación con respecto a otros algoritmos
Reemplazo de páginas . Algoritmos
Menos recientemente utilizado (LRU)
Ejemplo: 3 frames y la cadena de referencia: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
• Busca acercarse a OPT prediciendo cuándo
será la próxima vez en que se emplee cada
una de las páginas que tiene en memoria
basado en la historia reciente de su
ejecución
• Elige la página que no ha sido empleada
desde hace más tiempo
• Por su complejidad, requiere soporte de
HW
Más frecuentemente utilizada (MFU)/Menos
frecuentemente utilizada (LFU)
• Se implementa como LRU pero en lugar de
registrar tiempo se registran las
invocaciones
• Costoso de implementar
• Bajo rendimiento
Reemplazo de páginas . Algoritmos
Aproximaciones a LRU Segunda oportunidad (o reloj)
• Similar a BIT de referencia.
Bit de referencia • Mantiene un Apagador del BIT de
• La tabla de páginas tiene un bit adicional “referencia de referencia.
acceso” • Ante un fallo, si el bit está apagado, es la
• Cuando inicia la ejecución el bit de “referencia” está víctima, sino, se enciende para darle una
apagado segunda oportunidad
• Cada vez que se referencia el frame, el bit se enciende
• Periódicamente el SO resetea el bit de referencia.
• Ante un fallo, se aplica FIFO entre los que tengan el bit Segunda oportunidad mejorado
de referencia apagado • Similar a 2da oportunidad, pero implementa 2bits (referencia,
modificación)
Columna de referencia
• (0, 0) Candidato ideal para su reemplazo.
• Similar a BIT de referencia, pero usando
• (0,1) No es tan buena opción, porque es necesario
una “columna de bits” (ejemplo 4b)
escribir la página a disco antes de reemplazarla, pero
• Cuando ejecuta el SO el RESET, hace un
puede ser elegida.
right shift del valor a la siguiente posición y
• (1,0) fue empleado recientemente, por lo que
se descarta el bit menos significativo
probablemente se vuelva a requerir pronto.
• Ante un fallo, se aplica FIFO entre los que
• (1,1) sería necesario escribir la página a disco antes de
tengan el valor de la columna mas bajo
reemplazar, hay que evitar reemplazarla.
• Ante un fallo, si el bit está apagado, es la víctima, sino, se
enciende para darle una segunda oportunidad
Asignación de marcos
• ¿cómo se asignan los marcos existentes a los procesos del sistema?
• ¿qué esquemas se pueden definir para que la asignación inicial (y, de ser posible, en el
transcurso de la ejecución) sea adecuada?
• ¿Cuál es el mínimo de frames que puede requerir un proceso?
Mínimo de marcos:
Por ejemplo si una instrucción de CPU permite la suma de 2 operandos directos en
memoria y la asignación del resultado en otro, ➔ se necesitarán un mínimo de 4 frames (1 para el
Código, 2 para los operandos y 1 para el resultado
Ámbitos del algoritmo de reemplazo de páginas
• Reemplazo local: EL objetivo: es mantener tan estable como sea posible el cálculo hecho por el esquema de
asignación empleado. Las únicas páginas que se considerarán para su intercambio serán aquellas
pertenecientes al mismo proceso que el que causó el fallo.
• Reemplazo global: Los algoritmos de asignación determinan el espacio asignado a los procesos al ser
inicializados. Los algoritmos de reemplazo de páginas operan sobre el espacio completo de memoria, y la
asignación física de cada proceso puede variar según el estado del sistema momento a momento.
• Reemplazo global con prioridad: Es un esquema mixto, en el que un proceso puede sobrepasar su límite
siempre que le robe espacio en memoria física exclusivamente a procesos de prioridad inferior a él. Esto es
consistente con el comportamiento de los algoritmos planificadores, que siempre dan preferencia a un
proceso de mayor prioridad por sobre de uno de prioridad más baja.
Hiperpaginación
Sucede cuando la frecuencia de reemplazo de páginas es tan alto que el Sistema no puede avanzar.
Todo (o casi todo) el trabajo realizado es overhead.
• Si la política es de asignación es local, alguno/s proceso/s tiene/n poco/s frames asignado/s
• Si la política es de asignación es global, hay demasiados procesos en ejecución
Síntomas
• la tasa de page faults aumenta considerablemente;
• se incrementa el tiempo de acceso efectivo a memoria;
• la utilización del procesador decae;
• no se realiza ningún trabajo ya que los procesos se
dedican a paginar
Solución posible
• Reducir el grado de multiprogramación (suspender
procesos)
Sistemas mixtos
Segmentación con paginación por demanda
• Combinan las técnicas de Segmentación y de paginación.
• En general los segmentos tienen un tamaño múltiplo de páginas.
• No se necesitan tener cargadas en memoria central todas las Páginas de los segmentos.
• La dirección virtual se organiza en tres partes:
Ventajas:
1. Permite compartir segmentos. Direccionamiento
2. No es necesario cargar la totalidad de los
segmentos en memoria central ni la totalidad de
las
Páginas. Solo lo que se necesite.
3. No se requiere compactación.
Desventajas:
1. Requiere más Hardware para el
direccionamiento.
2. Es más lento en la ejecución (por el mecanismo
de traducción de las direcciones virtuales)
3. El S.O. ocupa más Memoria.
4. Aumenta la fragmentación interna.