1 Introducción (1) Idealmente, los programadores quieren
memoria mucha, rápida, no volátil, barata Historia
1980’s: MDS (64k), monousuario, CP/M, overlays
1980’s: VAX (4Mb), multiusuario (docenas) 2000’s:
Windows, 64Mb (normal 512 Mb) Jerarquía de memorias
Caché: poca, rápida, cara RAM: Mb, velocidad y
precio medios Disco: Gb, lenta y barata Es un problema de
costes
2 Introducción (2) Trabajos del gestor de memoria
Qué memoria está libre/ocupada
Asignación/liberación de memoria a procesos
Intercambio RAM-disco Clases de gestores de memoria Con
intercambio Swapping y paginación Sin intercambio
3 Solo un programa en memoria (junto con el SO) Se carga y se
queda ahí hasta que acaba (CP/M) MSDOS BIOS (Basic Input
Ouput System) palmTop, empotrados minis Gestión
básica de memoria (1)Monoprogramación sin
intercambio ni paginación
4 Gestión básica de memoria
(2)Multiprogramación con particiones fijas
5 Planificación: queda libre una partición,
¿qué trabajo cargar? El primero en la cola que
quepa Fragmentación interna El más grande de la
cola que quepa Se perjudica a los pequeños (y debe ser al
revés) Disponer de una partición pequeña No
retrasar un trabajo más de k veces OS/360, MFT
(Multiprogramming with a Fixed number of Task) Gestión
básica de memoria (3)Multiprogramación con
particiones fijas
6 La utilización de CPU es función del nº. de
procesos en memoria Grado de multiprogramación
Gestión básica de memoria (4)Modelo de
multiprogramación
7 Los procesos son independientes n: grado de
multiprogramación p: fracción de tiempo que un
proceso está esperando una I/O Utilización de la
CPU = 1 – pn Los procesos no son independientes: 1 sola
CPU-> los otros en preparados (esperando). Aproximación
válida. Ejemplo: 32Mb memoria, el SO ocupa 16Mb cada
proceso de usuario 4Mb => n = 4; si p=0.8, CPU = 60% Si
compramos 16Mb => n = 8; si p=0.8, CPU = 83%; ganancia: 38% Si
compramos otros 16Mb CPU=93%; ganancia: 12% Gestión
básica de memoria (5)Modelo de multiprogramación
(La sección 4.1.4 no entra para el examen)
8 Reubicación: ¿dónde reside un programa?
estática, dinámica Las direcciones de un programa
suelen ser relativas a su dirección de comienzo. PERO …
al montar un programa no se sabe dónde se va a ejecutar.
SOLUCIONES ? Modificación de direcciones durante la carga
(estático) ? Registro de Reubicación (o registro
base) (permite reubicación dinámica) Dir.Virtual
Registro deReubicación DirecciónReal (Gp:) + 6000
5166 4418 4200 2854 512 0 A B C A B C 1345 0 747 0 2341 0 Espacio
Virtual Espacio Real Ra = 2854Rb = 4418Rc = 512 Gestión
básica de memoria (6)Reubicación y
protección
9 Protección: acceso indiscriminado a cualquier
área de memoria RegistroLímite RegistroBase
DirecciónVirtual (Gp:) + (Gp:) <
ERROR de direccionamiento ¡ ! RAM tamaño del
programa dirección comienzo partición
Gestión básica de memoria (7)Reubicación y
protección
10 Intercambio (swapping) (1) Dos aproximaciones: Intercambio
(entre RAM y disco) Memoria virtual (solo una parte del programa
en RAM) Batch TiempoCompartido Se aceptan tantos trabajos como
quepan en memoria Suele haber más procesos de usuario de
los que caben en memoria¡ y hay que atenderlos a
todos!
11 Intercambio (swapping) (2) PARTICIONES DE TAMAÑO
VARIABLE(el nº, tamaño y dirección
varía con el tiempo) (Gp:) ¡ Fragmentación
Externa ! COMPACTACIÓN
12 P.ejem: 4 bytes: 40ns. 256Mb: 2,7 s. T4.4 (1ed) Ciertos
sistemas con intercambio eliminan la fragmentación externa
mediante compactación. Suponga que una computadora con 1Mb
de memoria para usuario hace una compactación cada
segundo. Si tarda 0,5 microseg en copiar un byte y el
tamaño medio de los huecos es de 0,4 el tamaño
medio de los segmentos ¿Cuál es la fracción
del tiempo total de CPU que se utiliza para la
compactación? Intercambio (swapping) (3)
13 Intercambio (swapping) (4) ¿Puede crecer
dinámicamente la memoria de un proceso? A S. O. B
Paracrecimiento En uso Paracrecimiento En uso S. O. Datos de B
Código de B Pila de B Datos de A Código de A Pila
de A Paracrecimiento Paracrecimiento (a) (b)
14 Intercambio (swapping) (5)Gestión de memoria con mapa
de bits (Gp:) Se debe llevar la cuenta de la memoria utilizada y
de los huecos libres (Gp:) Mapa de Bits Lista de Bloques Libres
Sistema Buddy Mapa de Bits 0 8 16 24 32 A B C D E
1111100011111111110011111111100000111111 ¿Tamaño de
la Unidad de Asignación? Pequeño ? Mapa
GrandeGrande ? Mapa Pequeño? Fragmentación Interna
Es caro buscar una zona libre de tamaño K.
15 Intercambio (swapping) (6)Gestión de memoria con listas
enlazadas
16 Intercambio (swapping) (7) Gestión de memoria con
listas enlazadas T4.4 Se trata de comparar la memoria necesaria
para mantener la pista de los bloques de memoria libre utilizando
un mapa de bits o una lista enlazada. La memoria es de 128 Mb y
la unidad de asignación es de n bytes. Para El caso de la
lista enlazada, suponer que la memoria consiste de una secuencia
alternada de segmentos y huecos, cada uno de 64kb. También
suponer que cada nodo en la lista necesita una dirección
de memoria de 32 bits, una longitud de 16 bits y un campo
(siguiente nodo) de 16 bits. ¿Cuántos bytes se
necesitan para mantener el mapa de bits y cuántos para
mantener la lista enlazada? ¿Qué método es
el mejor?
17 Intercambio (swapping) (8) Gestión de memoria con
listas enlazadas Lista de Bloques Libres (ordenados por
dirección: liberación)
18 Intercambio (swapping) (9) Gestión de memoria con
listas enlazadas Lista de Bloques Libres (ordenados por
dirección: asignación) El primero que sirva siempre
se comienza en la cabecera se generan muchos huecos
pequeños al principio Siguiente que sirva lista circular;
la cabecera se desplaza fragmentación externa:
distribución uniforme El que mejor se adapte recorrer toda
la lista: lento desperdicia más memoria El que peor se
adapte no es buena idea
19 Intercambio (swapping) (10) Gestión de memoria con
listas enlazadas Lista de Bloques Libres (ordenados por
tamaño: asignación) Orden creciente de
tamaños el primero que sirva = el que mejor se adapte
siguiente que sirva no tiene sentido sobrecarga: mantener la
lista ordenada en: asignación y liberación
(¿compactar con vecinos?) Algoritmo Quick Fit lista
separadas por tamaño (2k, 4k, …) asignación
rápida; liberación: compactación Cada nodo
de la lista puede ser el propio bloque
20 Intercambio (swapping) (11) T4.5 Considerar un sistema de
intercambio en el que la memoria consiste de Los siguientes
huecos (en tamaño) en el siguiente orden en memoria: 10kb,
4kb, 20kb, 18kb, 7kb, 9kb, 12kb y 15kb ¿Qué hueco
se elegirá para Satisfacer la próxima
petición de memoria: 12kb 10kb 9kb Para los algoritmos: El
primero que sirva El que mejor se adapte El que peor se adapte El
siguiente que sirva 20, 10, 18 12, 10, 9 20, 18, 15 20, 18,
9
21 Memoria Virtual (1) Se ocupa de tener la memoria de un proceso
partida en trozos, e ir cargando en memoria principal el trozo
que es necesario para poder continuar su ejecución. No es
necesario tener todo el programa en memoria RAM Se podrían
ejecutar programas mayores que la RAM Se podrían tener
más procesos en memoria principal Menos E/S por
intercambio: más velocidad Trozos Iguales Trozos de
tamaño variable PAGINACIÓN
SEGMENTACIÓN
22 Memoria Virtual (2). Paginación Posición y
función de la MMU
23 La memoria virtual se divide en páginas La memoria
física en marcos de página tamaño
página = tamaño marco Conversión: MOV REG, 0
– Dirección 0 está en página 0 –
Página 0 está en marco 2 – Dirección
física es 8192 MOV REG, 8192 – Dirección 8192
está en página 2 – Página 2 está en
marco 6 – Dirección física es 24576 ¿ MOV
REG, 32780 ? Memoria Virtual (3). Paginación
24 Memoria Virtual (4). Paginación 32780 está en la
página 8 (32768) La página tiene X La MMU genera un
TRAP FALTA de PÁGINA: Elegir víctima Escribir a
disco (si hace falta) Cargar la nueva página. Reiniciar
MOV REG, 32780 P.ejem: Víctima la del marco 1.
¿escribir? Indicar que página 1: X Cargar
página 8 en marco 1. Indicar que página 8 en marco
1 Reiniciar MOV REG, 32780 Dirección física:
4108
25 Memoria Virtual (5). Paginación
26 Memoria Virtual (6). Tabla de páginas Tabla de
páginas: marco = TP (página) Tamaño de la
tabla Velocidad de traducción C P U Pag . 0 Pag . 1 Pag .
2 Pag . 3 . . . . . . . . . . . . . . . . . . . . . Pag . n
Espacio de Direcciones Virtuales Marco 0 Marco 1 Marco 2 . . . .
. . . . . . . . Marco m dir . virtual dir . física Memoria
Principal Tabla de Páginas
27 Tamaño de la tabla: Direcciones virtuales = 32 bits
(232 = 4Gb) Si tamaño página = 4Kb (212)
Número de páginas = 232/212 = 220 = 1Mg = nº
de entradas TP Dirección virtual = 64 bits (264) Si
tamaño de página = 4Kb (212) Número de
páginas = 264/212 = 252=222*230=222 G = 4,5 Peta entradas
= 4,5 * 1015 entradas Cada proceso tiene su propia tabla de
páginas. El nº de entrada * tamaño (bytes) de
cada entrada. Memoria Virtual (7). Tabla de páginas
28 Memoria Virtual (8). Tabla de páginas Tablas de
página multinivel: – Evita mantener todas las tablas de
página en memoria 4 Mb (210*212=22*220) Texto Datos Stack
Gap
29 (Gp:) 3 2 1 0 (Gp:) 1023 (Gp:) 4Mb (4194304)) (Gp:) 12288
Memoria Virtual (9). Tabla de páginas dirección
virtual: 0x00403004 (4206596, 0000 0000 0100 0000 0011 0000 0000
0100) PT1 = 0000 0000 01 (4M-8M) PT2 = 00 0000 0011 nº marco
(Gp:) + dir. física Offset = 0000 0000 0100 Solo cargadas
4 TP
30 Estructura de una entrada: Número de marco en el que
reside Presente/ausente: 1 está; 0 no está.
Protección: 0 RW; 1 R o RWX Modificada (bit de ensuciado):
1 sucia; 0 limpia Referenciada: 0 cuando se carga; 1 cuando RW.
Para sustitución Caching disabled: máquinas con E/S
mapeada en memoria. No usar una copia vieja de la caché
(de la página que contiene la memoria E/S) 32 bits aprox.
Memoria Virtual (10). Tabla de páginas
31 Memoria Virtual (11). Tabla de páginas T4.13 Una
computadora con direcciones de 32 bits utiliza una tabla de
páginas de dos niveles. Las direcciones virtuales se
dividen en un campo de 9 bits para la tabla de nivel superior y
un campo de 11 bits para la tabla de nivel secundario; el resto
es para el desplazamiento dentro de una página.
¿Cuál es el tamaño de la página?
¿Cuántas páginas existen en el espacio
virtual de direccionamiento?
32 Memoria Virtual (12). TLB Tabla de páginas: Velocidad
de traducción Una instrucción: 1, 2 o más
referencias a memoria Cada referencia a memoria: consulta a la TP
Soluciones: Todas las entradas en registros Muy caro (hw) Mucho
tiempo en cambio contexto Toda la tabla en memoria (de todos los
procesos) Registro RBTP (Registro Base de la Tabla de
Páginas) Dir. Entrada = [RBTP] + (nº.pag *
tamaño de la entrada) Cambio de contexto: recargar RBTP
Mantener en memoria sólo la TP del proceso
ejecutándose ¿Otras soluciones?
33 Localidad referencial TLB (Translation Lookaside Buffers)
(memoria asociativa) dentro de la MMU Memoria Virtual (13). TLB
(La sección “Software TLB Management” no entra
para el examen)
34 Memoria Virtual (14) T4.17 En un ordenador los procesos tienen
un espacio de direccionamiento de 1024 páginas y mantienen
en memoria su tabla de páginas. La sobrecarga por lectura
de una palabra desde la tabla de páginas es de 5 ns. Para
reducir esta sobrecarga, el ordenador tiene una TLB con 32
entradas (página virtual, num. marco) que tarda 1 ns en
realizar una consulta. ¿Cuál debe ser la tasa de
aciertos en dicha memoria asociativa para reducir la sobrecarga a
2 ns.?
35 Memoria Virtual (15)Tabla invertida de páginas Tabla de
páginas: Velocidad de traducción (Proceso,
página virtual)
36 Memoria Virtual (16). T4.21 Un ordenador con páginas de
8kB, memoria principal de 256MB y un espacio de direccionamiento
virtual de 64GB, utiliza una tabla invertida de páginas
para implementar su memoria virtual. ¿Cómo de
grande debería ser la tabla hash para asegurar que por
término medio la cadena hash tiene una longitud menor que
1? Suponga que el tamaño de la tabla hash es potencia de
2.
37 Memoria Virtual (17) T4.12 Una máquina tiene un espacio
de direcciones de 32 bits y una página de 8k. la tabla de
páginas está en hardware, con una palabra de 32
bits por cada entrada. Al iniciar un proceso, la tabla de
páginas se copia al hardware desde la memoria, con una
palabra cada 100ns. Si cada proceso se ejecuta durante 100ms
(incluyendo el tiempo de carga de la tabla de páginas),
¿cuál es la fracción del tiempo de CPU que
se dedica a la carga de las tablas de páginas?
38 Algoritmos de sustitución de páginas (1) Se
produce una falta de página y no hay memoria libre: Elegir
victima Llevar victima a disco (si sucia) En TP: victima no
presente Traer nueva página al marco donde estaba la
víctima Actualizar TP: nueva está presente y marco
y demás info ¿Cómo elegir la víctima?
Algoritmos de sustitución de página Problemas
similares: Memoria caché Caché de un servidor
web
39 Objetivo de todos los algoritmos de sustitución: Elegir
páginas que generen el menor número de faltas de
página. En todos los algoritmos hay una constante: el
nº de marcos existentes Algoritmo Óptimo de
sustitución de páginas Quitar la página que
tardará más tiempo en ser referenciada Imposible
implementar Algoritmos de sustitución de páginas
(2)
ESTA PRESENTACIÓN CONTIENE MAS DIAPOSITIVAS DISPONIBLES EN
LA VERSIÓN DE DESCARGA