Post on 30-Jan-2020
transcript
Tema 4: Organización y gestión de memoria 1
Conceptos generales Esquemas de memoria basados en la
asignación contigua Recubrimientos (overlay) Intercambio (swapping) Organización de la Memoria Virtual Gestión de la Memoria Virtual
Tema 4. Organización y Gestión de Memoria
Tema 4: Organización y gestión de memoria 2
Objetivos Distinguir entre dirección relativa o lógica y dirección física o
real y entre espacio de direcciones lógico y físico Entender qué es la reubicación y sus diferentes tipos (estática
y dinámica) Conocer las distintas formas en las que el sistema operativo
puede organizar y gestionar la memoria física Saber en qué consiste y para qué se utiliza el mecanismo de
recubrimientos (overlays) y el intercambio (swapping) Entender qué es la Memoria Virtual y por qué se utiliza Conocer los mecanismos de paginación, segmentación y
segmentación paginada y cómo se llevan a cabo en un sistema con memoria virtual
Comprender qué es la propiedad de localidad y su relación con el comportamiento de un programa en ejecución
Conocer la teoría del conjunto de trabajo y el problema de la hiperpaginación
Tema 4: Organización y gestión de memoria 3
1. Conceptos Generales
Jerarquía de Memoria Objetivos generales Espacio de direcciones lógico y
espacio de direcciones físico Carga absoluta y reubicación
Tema 4: Organización y gestión de memoria 4
1.1 Jerarquía de Memoria
Dos principios sobre memoria: Menor cantidad, acceso más rápido Mayor cantidad, menor coste por byteAsí, los elementos frecuentemente accedidos se ponen en memoria rápida, cara y pequeña; el resto, en memoria lenta, grande y barata.
CPU
RegistrosCaché
HardwareMemoriaPrincipal
MemoriaAuxiliar
Bus de memoria Bus de E/S
Tema 4: Organización y gestión de memoria 5
Conceptos sobre Cachés
Caché - copia que puede ser accedida más rápidamente que el original
Idea: hacer los casos frecuentes eficientes, los caminos infrecuentes no importan tanto
Acierto de caché: item en la caché Fallo de caché: item no en caché; hay que realizar la
operación completa Tiempo de Acceso Efectivo (TAE) =
Probabilidad_acierto * coste_acierto + Probabilidad_fallo * coste_fallo
Funciona porque los programas no son aleatorios, explotan la localidad principio de localidad
Tema 4: Organización y gestión de memoria 6
1.2 Objetivos generales
Organización: ¿cómo está dividida la memoria?
Gestión: Dado un esquema de organización, ¿qué estrategias se deben seguir para obtener un rendimiento óptimo? » Estrategias de asignación » Estrategias de sustitución» Estrategias de búsqueda
Protección » El SO de los procesos de usuario» Los procesos de usuario entre ellos
Tema 4: Organización y gestión de memoria 7
1.3 Espacio de direcciones lógico y espacio de direcciones físico
Espacio de direcciones lógico: conjunto de direcciones lógicas o virtuales generadas por un programa
Espacio de direcciones físico: conjunto de direcciones físicas correspondientes a las direcciones lógicas en un instante dado
L O A D R 1 , # 1 0 0 0L O A D R 2 , # 2 0 0 0L O A D R 3 , / 1 5 0 0L O A D R 4 , [ R 1 ]S T O R E R 4 , [ R 2 ]I N C R 1I N C R 2D E C R 3J N Z / 1 2. . . . . . . . . . . . . . . . .
C a b e c e r a
F i c h e r o E j e c u t a b l e
04. . . .9 61 0 01 0 41 0 81 1 21 1 61 2 01 2 41 2 81 3 21 3 6
Carretero, p.165
Tema 4: Organización y gestión de memoria 8
Mapa de memoria de un proceso
C a b e c e r a
F i c h e r o E j e c u t a b l eN ú m e r o m á g i c o
C o n t a d o r d e p r o g r a m a i n i c i a l
T a b l a d e s e c c i o n e s
C ó d i g o
D a t o s c o n v a l o r i n i c i a l
T a b l a d e s í m b o l o s
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
0
1 0 0 0
5 0 0 0
8 0 0 0
S e c c i o n e s
M a p a d e m e m o r i a
C ó d i g o
D a t o s c o n v a l o r i n i c i a l
0
4 0 0 0
5 0 0 0D a t o s s i n v a l o r i n i c i a l
P i l aA r g u m e n t o s d e l p r o g r a m a
“ 0 ”
Imagen de proceso =mapa + PCB
Figura (Carretero, p.179)
Tema 4: Organización y gestión de memoria 9
1.4 Carga absoluta y Reubicación
Carga absoluta“Asignar direcciones físicas al programa en tiempo de compilación”
Reubicación“Capacidad de cargar y ejecutar un programa en un lugar arbitrario de la memoria”
Programa Fuente
Compilador(y Encuadernador)
S.O.Memoria Principal
X
N
ProgramaEjecutable
X
Ndirecciones absolutas
ProgramaEjecutable
0
Mdirecciones lógicas o relativas
? es necesario
reubicarlo
Cargador
Cargador
Tema 4: Organización y gestión de memoria 10
Reubicación estática
• Decisión de dónde ubicar el programa en tiempo de carga
• El compilador genera direcciones lógicas (relativas)
dirección física = dirección de comienzo + dirección lógica
MOVE A, 100
0
M
Programa ejecutable con direcciones lógicas
Memoria Principal
1000
1000 + M
MOVE A, 1100
Tema 4: Organización y gestión de memoria 11
Reubicación dinámica
• El compilador genera direcciones lógicas (relativas)
• La traducción de direcciones lógicas a físicas se hace en tiempo de ejecución
dirección física = registro base + dirección lógica Memoria Principal
b
b + M
MOVE A, 100
CPU
DirecciónLógica
+DirecciónFísica
Hardware
R.Base
b
Tema 4: Organización y gestión de memoria 12
Asignación contigua y no contigua Sistemas monoprogramados Sistemas multiprogramados con
particiones: - Particiones fijas
- Particiones variables
- Protección en sistemas multiprogramados
2. Esquemas de memoria basados en la asignación contigua
Tema 4: Organización y gestión de memoria 13
2.1 Asignación contigua y no contigua
Podemos clasificar las organizaciones de memoria como:
Contiguas - La asignación de almacenamiento para un programa se hace en un único bloque de posiciones continuas de memoria Particiones fijas y Particiones variales
No contiguas - Permiten dividir el programa en bloques o segmentos que se pueden colocar en zonas no necesariamente continuas de memoria principal Paginación, Segmentación y Segmentación paginada
Tema 4: Organización y gestión de memoria 14
2.2 Sistemas monoprogramados
Memoria principal dividida en dos partes:» S.O. residente» Proceso de usuario
La asignación contigua en sistemas monousuario implementa protección a través del registro de relocalización (o límite)
SO
Procesode
usuario
No usada
CPU
a
registro límite
0
a
Tema 4: Organización y gestión de memoria 15
2.3 Sistemas multiprogramados con particiones
Existen varios procesos en memoria. El tamaño máximo de cada proceso es el tamaño de la
memoria física disponible. El esquema más sencillo es dividir la memoria en
regiones o particiones cada una de las cuales puede ser ocupada por un proceso. Existen dos formas de dividir la memoria en particiones » Particiones fijas o estáticas» Particiones variables o dinámicas
La protección se obtiene a través de los registros base y límite (sus valores para un proceso se guardan en su PCB)
Tema 4: Organización y gestión de memoria 16
Particiones fijas
El número y tamaño de cada partición viene establecido por el sistema y es constante
Tamaño de las particiones:» Particiones de igual tamaño» Particiones de distinto tamaño
Estrategias de asignación: proceso – partición» Cola única» Varias colas (particiones de distinto tamaño)
Tema 4: Organización y gestión de memoria 17
Problema de las particiones fijas
Uso de la memoria principal ineficiente. Cualquier proceso, sin importar lo pequeño que sea, ocupará una partición completa
Fragmentación: incapacidad del sistema operativo para asignar posiciones de memoria principal no utilizadas. Dos tipos: interna y externa
Problema de fragmentación en particiones fijas: Fragmentación interna
Tema 4: Organización y gestión de memoria 18
Particiones variables
Las particiones son variables en número y tamaño
Cuando llega un proceso a memoria se le asigna la memoria que necesita: se crea una partición
El SO mantiene información sobre las zonas de memoria asignadas (tabla de particiones) y las libres (huecos)
Es necesario tener una estrategia de asignación de espacio y gestión de espacio libre
Tema 4: Organización y gestión de memoria 19
Problema particiones variables
Fragmentación externa - existe el espacio necesario para satisfacer una petición pero no es contiguo
Compactación - técnica utilizada para reducir la fragmentación externa. Consiste en arrastrar los contenidos de memoria a un lugar para reunir toda la memoria libre en un bloque. Problemas:» Requiere reubicación dinámica» Consume recursos del sistema» El sistema se detiene mientras se realiza no se
puede hacer demasiado frecuentemente
Tema 4: Organización y gestión de memoria 20
Ejemplo fragmentación externa
SO 148 k
896 k
SO 148 k
576 k
Proceso 1320 k
SO 148 k
352 k
Proceso 1320 k
Proceso 2 224 k
SO 128 k
268 k
Proceso 1320 k
Proceso 2 224 k
Proceso 3
84 k
SO 148 k
268 k
Proceso 1320 k
224 k
Proceso 3
64 k
SO 148 k
268 k
Proceso 1320 k
Proceso 4 128 k
Proceso 3
64 k
96 k
SO 148 k
268 k
320 k
Proceso 4 128 k
Proceso 3
64 k
96 k
SO 148 k
268 k
230 k
Proceso 4 128 k
Proceso 3
64 k
96 k
Proceso 590 k
Tema 4: Organización y gestión de memoria 21
Particiones variables: Estrategias de asignación de espacio
¿Cómo satisfacer una petición de tamaño n desde una lista de huecos? Estrategias:» Primer ajuste – asigna el primer hueco lo
suficientemente grande para satisfacer la petición» Mejor ajuste – asigna el hueco más pequeño que
mejor se ajuste al espacio necesitado. Se debe buscar en la lista entera, si no esta ordenada por tamaños. Produce el hueco sobrante menor.
» Peor ajuste - asigna el hueco mayor. Debemos buscar en toda la lista. Produce el hueco sobrante mayor
Tema 4: Organización y gestión de memoria 22
Ejemplo: Primer Ajuste
Sistema Operativo
Hueco de 16K
Hueco de 14K
Hueco de 5K
Hueco de 30K
0ab
cd
e
f
g
Direc.inicial
Lon-gitud
aceg
16K14K 5K30K
Lista espacio libre(orden por direcc.)
Solicitudes
13 K
Produce un hueco de 3K
Tema 4: Organización y gestión de memoria 23
Ejemplo: El Mejor Ajuste
Sistema Operativo
Hueco de 16K
Hueco de 14K
Hueco de 5K
Hueco de 30K
0ab
cd
e
f
g
Direc.inicial
Lon-gitud
ecag
5k14k16k30k
Lista espacio libre(orden ascendentetamaño de hueco)
Solicitudes
13 K
Produce un hueco de 1K
Tema 4: Organización y gestión de memoria 24
Ejemplo: El Peor Ajuste
Sistema Operativo
Hueco de 16K
Hueco de 14K
Hueco de 5K
Hueco de 30K
0ab
cd
e
f
g
Direc.inicial
Lon-gitud
gace
30K16K14K5K
Solicitudes
13 K
Lista espacio libre(orden descendentetamaño de hueco)
Produce un hueco de 17K
Tema 4: Organización y gestión de memoria 25
Gestión de espacio libre
Estado actual de la M.P.
MAPA DE BITS :
Divide la memoria principal en unidades de asignación y se utiliza un bit por cada una de ellas que indica si está libre (0) u ocupada (1)
1 1 1 1 1 0 0 0 1
1 1 1 1 1 1 1 1 1
0 0 1 1 1 0 0 ….
D
C
B
A5
10
15
20
25
LISTA ENCADENADA (O ENLAZADA) :
P (Partición)H (Hueco)
Direcciónde comienzo
Tamaño
P 0 5 H 6 3 P 8 6 P 14 4
H 18 2 P 20 3 H 24 3
Tema 4: Organización y gestión de memoria 26
Protección en sistemas multiprogramados
Reubicación estática
Reubicación dinámica
CPU
c
d
Memoria Principal
S.O.
Partición 1
Partición 2
Partición 3
Partición 4
Partición 5
0
ab
c
d
e
R.Base
R.Límite
Tema 4: Organización y gestión de memoria 27
3. Recubrimientos (overlays)
Era un mecanismo para ejecutar programas más grandes que la memoria. En memoria sólo se tenían las instrucciones y datos que se necesitan en un momento dado
El SO no da soporte. Es responsabilidad del programador diseñar y programar la estructura de overlays
Memoria
Programa
SO
Código ydatos
residentes
Inicializar
Procesar
Salir
Area derecubri-miento
1º
2º
3º
Tema 4: Organización y gestión de memoria 28
4. Intercambio (Swapping)
Intercambiar procesos entre memoria y un almacenamiento auxiliar
El almacenamiento auxiliar debe ser un disco rápido con espacio para albergar las imágenes de memoria de los procesos de usuario
El factor principal en el tiempo de intercambio es el tiempo de transferencia
El intercambiador tiene las siguientes responsabilidades:» Seleccionar procesos para retirarlos de MP» Seleccionar procesos para incorporarlos a MP» Gestionar y asignar el espacio de intercambio
Tema 4: Organización y gestión de memoria 29
Localización del espacio de intercambio
Intercambio Dinámico:» Un archivo de intercambio global del sistema
cubre las necesidades de intercambio de todos los procesos
» Problema: elección de su tamaño Intercambio Estático:
» Existe un archivo de intercambio dedicado por cada proceso intercambiable del sistema
» Elimina el problema del tamaño» No impone límites al número de procesos
intercambiados» Problema: Necesita más espacio en disco, los
accesos son más lentos y los direccionamientos son más complicados
Tema 4: Organización y gestión de memoria 30
5. Organización de la Memoria Virtual
Concepto de memoria virtual
Paginación
Segmentación
Segmentación paginada
Tema 4: Organización y gestión de memoria 31
5.1 Concepto de memoria virtual
Memoria Virtual» El tamaño del programa, los datos y la pila
puede exceder la cantidad de memoria física disponible para él.
» Se usa un almacenamiento a dos niveles:–Memoria Principal partes del proceso
necesarias en un momento dado–Memoria Secundaria espacio de
direcciones completo del proceso
Tema 4: Organización y gestión de memoria 32
Concepto de memoria virtual (y II)
» Es necesario:–saber qué se encuentra en memoria
principal–una política de movimiento entre MP y MS
Además, la memoria virtual» resuelve el problema del crecimiento
dinámico de los procesos» puede aumentar el grado de
multiprogramación
Tema 4: Organización y gestión de memoria 33
Unidad de Gestión de Memoria
La MMU (Memory Management Unit) es un dispositivo hardware que traduce direcciones virtuales a direcciones físicas ¡Este dispositivo está gestionado por el SO!
En el esquema MMU más simple, el valor del registro base se añade a cada dirección generada por el proceso de usuario al mismo tiempo que es enviado a memoria
El programa de usuario trata sólo con direcciones lógicas; éste nunca ve direcciones reales
Tema 4: Organización y gestión de memoria 34
Unidad de Gestión de Memoria (y II)
Además de la traducción, el MMU deberá:- detectar si la dirección aludida se encuentra o no en MP- generar una interrupción si se encuentra en MS
Tarjeta del procesador
Memoria
CPU
MMU
direcciónvirtual
direcciónfísica
Controladorde disco
BUS
Tema 4: Organización y gestión de memoria 35
Ejemplo de MMU: El MIPS R2000/3000
MMU
MMU
RegistrosALU
CPUCP0Registros ges-tión excepcion
DirecciónVirtual
Dirección Física
Búfer de TraducciónAdelantada (TLB)
Indice
Aleatorio
Tema 4: Organización y gestión de memoria 36
5.2 Paginación
El espacio de direcciones físicas de un proceso puede ser no contiguo
La memoria física se divide en bloques de tamaño fijo, denominados marcos de página. El tamaño es potencia de dos, de 0.5 a 8 Kb
El espacio lógico de un proceso se divide en bloques del mismo tamaño, denominados páginas
Los marcos de páginas contendrán páginas de los procesos
Tema 4: Organización y gestión de memoria 37
Paginación (y II)
Las direcciones lógicas, que son las que genera la CPU se dividen en número de página (p) y desplazamiento dentro de la página (d)
Las direcciones físicas se dividen en número de marco (m, dirección base del marco donde está almacenada la página) y desplazamiento (d)
dp
dm
Tema 4: Organización y gestión de memoria 38
Paginación (y III)
Cuando la CPU genere una dirección lógica será necesario traducirla a la dirección física correspondiente, la tabla de páginas mantiene información necesaria para realizar dicha traducción. Existe una tabla de páginas por proceso
Tabla de ubicación en disco (una por proceso) ubicación de cada página en el almacenamiento secundario
Tabla de marcos de página, usada por el S.O. y contiene información sobre cada marco de página
Tema 4: Organización y gestión de memoria 39
Contenido de la tabla de páginas
Una entrada por cada página del proceso: Número de marco (dirección base del marco) en
el que está almacenada la página si está en MP Bit de presencia o bit válido Bit de modificación Modo de acceso autorizado a la página (bits de
protección)
nº marco presencia modificación protección
46 1 0 01
Nº de página
Tema 4: Organización y gestión de memoria 40
Ejemplo: contenido de la tabla de páginas
Memoria T.P.secundaria
Memoria Física
Pag12
Pag1
Pag7Pag10
Pag4Pag3
pag12
Pag11
Pag10
Pag9
Pag8
Pag7
Pag6
Pag5
Pag4
Pag3
Pag2
Pag1
3
5
-
-
-
10
6
-
2
1
-
8 1
2
3
4
5
6
7
8
9
10
Num. Marco
1
2
3
4
5
6
7
8
9
10
11
12Num. Pagina
0
1
-
0
0
1
1
0
1
1
0
1
Nº de Marco
Bit de presencia
...
...
...
...
...
...
...
...
...
...
...
...
Tema 4: Organización y gestión de memoria 41
Esquema de traducción
m DESPLAZAMIENTO
Dirección real
DESPLAZAMIENTON. pagina
Dirección virtual
RBTP
m 1
N. de marco presencia modificación pro.
TABLA DE PAGINAS
FALTA DE PAGINA
si
noPresencia
= 1
si
no¿Acceso autorizado?
excepción
violación de privilegios
¿Actualizar bit de modificación?
(si/no)
Dir. TUD
Tabla de Ubicación en Disco
Tema 4: Organización y gestión de memoria 42
Falta de página
1. Bloquear proceso2. Encontrar la ubicación en disco de la página solicitada (tabla de ubicación en disco)3. Encontrar un marco libre. Si no hubiera, se puede optar por desplazar una página de MP4. Cargar la página desde disco al marco de MP5. Actualizar tablas (bit presencia=1, nº marco, ...)6. Desbloquear proceso7. Reiniciar la instrucción que originó la falta de página
Tema 4: Organización y gestión de memoria 43
Implementación de la Tabla de Páginas
La tabla de páginas se mantiene en memoria principal
El registro base de la tabla de páginas (RBTP) apunta a la tabla de páginas (suele almacenarse en el PCB del proceso)
En este este esquema: » cada acceso a una instrucción o dato
requiere dos accesos a memoria: uno a la tabla de páginas y otro a memoria
» un problema adicional viene determinado por el tamaño de la tabla de páginas
Tema 4: Organización y gestión de memoria 44
Búfer de Traducción Adelantada (TLB)
El problema de los dos accesos a memoria se resuelve con una caché hardware de consulta rápida denominada búfer de traducción adelantada o TLB (Translation Look-aside Buffer)
El TLB se implementa como un conjunto de registros asociativos que permiten una búsqueda en paralelo
De esta forma, para traducir una dirección:1 Si existe ya en el registro asociativo, obtenemos el
marco2 Si no, la buscamos en la tabla de páginas y se actualiza
el TLB con esta nueva entrada
Tema 4: Organización y gestión de memoria 45
Traducción con TLB
CPU
MemoriaFísica
Tabla de páginas
m
p d m d
TLB
Nº página Nº marco
Acierto TLB
FalloTLB
Tema 4: Organización y gestión de memoria 46
Tamaño de la Tabla de Páginas
Ejemplo:» Dirección virtual: 32 bits.» Tamaño de página = 4 Kbytes (212 bytes).
tamaño del campo desplazamiento = 12 bits tamaño número de página virtual = 20 bits Nº de páginas virtuales = 220 = ¡1,048,576!
Solución para reducir el tamaño de la TP:» Paginación multinivel
Tema 4: Organización y gestión de memoria 47
Paginación multinivel
Esta solución opta por “paginar las tablas de páginas”
La partición de la tabla de páginas permite al SO dejar particiones no usadas sin cargar hasta que el proceso las necesita. Aquellas porciones del espacio de direcciones que no se usan no necesitan tener tabla de página
Tema 4: Organización y gestión de memoria 48
Paginación a dos niveles
Lo que hacemos es paginar la tabla de páginas.
La dirección lógica se divide en:» número de página (n bits):
– un número de página p1 (=k)– desplazamiento de página p2 (=n-k)
» desplazamiento de página d (m bits) Así una dirección lógica es de la forma:
p1 p2 d
Tema 4: Organización y gestión de memoria 49
Esquema de paginación a dos niveles
. . .
. . .
. . .
. . .
. . .. . .
p1 p2 d
Tabla de páginasde primer nivel Tablas de páginas
de segundo nivel
Memoria física
Tema 4: Organización y gestión de memoria 50
Ejemplo: Esquema de paginación a dos niveles
Memoria secundaria
MemoriaFísica
Pag12
Pag1Pag3_TPPag7Pag10
Pag1_TPPag4Pag3
pag12
Pag11
Pag10
Pag9
Pag8
Pag7
Pag6
Pag5
Pag4
Pag3
Pag2
Pag1
2
1
-
8 1
2
3
4
5
6
7
8
9
10
Num. Marco
1
2
3 7
--
3
Tabla de pag.1º Nivel
-
6
-
-
10
-
5
-
Tablas de pag.2º Nivel
Pag 1 de la TP
Pag 2 de la TP
Pag 3 de la TPNum. de pag de la TP
1
2
3
4
1
2
3
4
1
2
3
4
Tema 4: Organización y gestión de memoria 51
Páginas compartidas
Una copia de código de solo lectura (reentrante) compartido entre varios procesos.Ej. editores, compiladores, sistemas de ventanas
ed 1
ed 2
ed 3
data 1
ed 1
ed 2
ed 3
data 2
ed 1
ed 2
ed 3
data 3
3 4 6 1
3 4 6 7
3 4 6 2
data 1data 3 ed 1 ed 2
ed 3data 2
0123456789
Proceso P1
Proceso P2
Proceso P3
Tabla de páginaspara P1
Tabla de páginaspara P2
Tabla de páginaspara P3
Memoria
Tema 4: Organización y gestión de memoria 52
5.3 Segmentación
Esquema de organización de memoria que soporta mejor la visión de memoria del usuario: un programa es una colección de unidades lógicas -segmentos-, p. ej. procedimientos, funciones, pila, tabla de símbolos, matrices, etc.
S1
S2
S3
S4
S1S4
S3
S1
Espacio deusuario
Memoriafísica
Tema 4: Organización y gestión de memoria 53
Tabla de Segmentos
Una dirección lógica es una tupla:<número_de_segmento, desplazamiento>
La Tabla de Segmentos aplica direcciones bidimensionales definidas por el usuario en direcciones físicas de una dimensión. Cada entrada de la tabla tiene los siguientes elementos (aparte de presencia, modificación y protección):» base - dirección física donde reside el inicio
del segmento en memoria.» tamaño - longitud del segmento.
Tema 4: Organización y gestión de memoria 54
Implementación de la Tabla de Segmentos
La tabla de segmentos se mantiene en memoria principal
El Registro Base de la Tabla de Segmentos (RBTS) apunta a la tabla de segmentos (suele almacenarse en el PCB del proceso)
El Registro Longitud de la Tabla de Segmentos (STLR) indica el número de segmentos del proceso; el nº de segmento s, generado en una dirección lógica, es legal si s < STLR (suele almacenarse en el PCB del proceso)
Tema 4: Organización y gestión de memoria 55
Esquema de traducción
S’ + dDirección real
dN. Segmento
Dirección virtual
FALTA DE SEGMENTO
si
no¿Acceso autorizado?
Excepción
violación de privilegios
¿Actualizar bit de modificación?
(si/no)
S’ t
D. base tamaño presencia modif. pro.
TABLA DE SEGMENTOS
1
si
noPresencia
= 1si
nod > t
Excepción acceso indebido
RBTS
Dir. TUD
Tabla de Ubicación en Disco
Tema 4: Organización y gestión de memoria 56
5.4 Segmentación Paginada
La variabilidad del tamaño de los segmentos y el requisito de memoria contigua dentro de un segmento, complica la gestión de MP y MS
Por otro lado, la paginación simplifica la gestión pero complica más los temas de compartición y protección
Algunos sistemas combinan ambos enfoques, obteniendo la mayoría de las ventajas de la segmentación y eliminando los problemas de una gestión de memoria compleja
Tema 4: Organización y gestión de memoria 57
Esquema de traducción
+
RBTS
s p d’
d m
Tabla de Páginasdel segmento s
s’ : dirección base de la Tabla de Páginas del segmento s
+
si
s’ t
d<t
Tabla de Segmentos
direcciónvirtual
¿presente?
m d’
si
direcciónfísica
Tema 4: Organización y gestión de memoria 58
6. Gestión de la Memoria Virtual
Introducción
Algoritmos de sustitución
Comportamiento de los programas
Hiperpaginación (Thrashing)
Algoritmos de asignación y sustitución
Tema 4: Organización y gestión de memoria 59
6.1 Introducción
Gestión de Memoria Virtual con paginación Criterios de clasificación respecto a:
» Políticas de asignación: –Fija–Variable
» Políticas de búsqueda: –Paginación por demanda–Paginación anticipada (≠ prepaginación)
» Políticas de sustitución: –Sustitución local–Sustitución global
Tema 4: Organización y gestión de memoria 60
Introducción (y II)
Independientemente de la política de sustitución utilizada, existen ciertos criterios que siempre deben cumplirse:» Páginas “limpias” frente a “sucias”
– se pretende minimizar el coste de transferencia
» Páginas compartidas– se pretende reducir el nº de faltas de página
» Páginas especiales– algunos marcos pueden estar bloqueados
(ejemplo: buferes de E/S mientras se realiza una transferencia)
Tema 4: Organización y gestión de memoria 61
Asignación fija
Asignación por igual» Se asignan el
mismo número de marcos a todos los procesos
» Si hay m marcos, y n procesos. A cada proceso se se asignan m/n marcos
Asignación propor-cional por tamaño» Asigna según ta-
maño del proceso» si=tamaño de pi
» S = Σ si
» m = número total de marcos
» la asignación, ai, para pi es:ai = (si / S)*m
Tema 4: Organización y gestión de memoria 62
Paginación por demanda frente a anticipada
Las ventajas de la paginación por demanda son:» Se garantiza que en MP solo están las
páginas necesarias en cada momento» La sobrecarga de decidir qué páginas llevar a
MP es mínima Las ventajas de la paginación anticipada son:
» Se puede optimizar el tiempo de respuesta para un proceso pero los algoritmos son más complejos y se consumen más recursos
Tema 4: Organización y gestión de memoria 63
Rendimiento de la paginación por demanda
Sea p la tasa de falta de página; p=0 no hay faltas de páginas, ó p=1, toda referencia es una falta. Por tanto, 0 ≤ p ≤ 1
TAE = (1 - p) * acceso_a_memoria+ p * (sobrecarga_falta_de_página+ [sacar_fuera_la_página]+ traer_la_página+ sobrecarga_de_rearranque)
Tema 4: Organización y gestión de memoria 64
Influencia del tamaño de página
Cuanto más pequeñas» Aumento del tamaño de las tablas de
páginas» Aumento del nº de transferencia MPDisco» Reducen la fragmentación interna
Cuanto más grandes» Grandes cantidades de información que no
serán usadas están ocupando MP» Aumenta la fragmentación interna
Búsqueda de un equilibrio
Tema 4: Organización y gestión de memoria 65
6.2 Algoritmos de sustitución
Podemos tener las siguientes combinaciones» asignación fija y sustitución local» asignación variable y sustitución local» asignación variable y sustitución global
Veremos distintos algoritmos de sustitución y nos basaremos (por simplicidad) en que se utiliza una política de asignación fija y sustitución local
Cadena de referencia, ω = r1,r2,r3,...,ri, ..., : secuencia de números de páginas referenciadas por un proceso durante su ejecución
Tema 4: Organización y gestión de memoria 66
Algoritmo Optimo
Se sustituye la página que no será objeto de ninguna referencia posterior o que se referencie más tarde
» 4 marcos de página» Problema: debemos tener un “conocimiento perfecto” de la cadena de referencia» Se utiliza para medir cómo de bien se comportan otros algoritmos» Faltas de páginas: 6
1,2,3,4,1,2,5,1,2,3,4,5
1 1 1 1 1 1 1 1 1 1 4 4
2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3 3
4 4 4 5 5 5 5 5 5
* * * * * *
Tema 4: Organización y gestión de memoria 67
Algoritmo FIFO
Se sustituye la página por orden cronológico de llegada a MP (la página más antigua)
» 4 marcos de página» Faltas de página: 10» Sufre de la Anomalía de Belady: “más marcos no implican menos faltas de páginas”
1,2,3,4,1,2,5,1,2,3,4,5
1 1 1 1 1 1 5 5 5 5 4 4
2 2 2 2 2 2 1 1 1 1 5
3 3 3 3 3 3 2 2 2 2
4 4 4 4 4 4 3 3 3
* * * * * * * * * *
Tema 4: Organización y gestión de memoria 68
Algoritmo LRU
Se sustituye la página que fue objeto de la referencia más antigua (Least Recently Used)
» 4 marcos de página» Faltas de página: 8» Implementación del algoritmo:
– con contadores– con pila
» Mayor coste
1,2,3,4,1,2,5,1,2,3,4,5
1 1 1 1 1 1 1 1 1 1 1 5
2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 5 5 5 5 4 4
4 4 4 4 4 4 3 3 3
* * * * * * * *
Tema 4: Organización y gestión de memoria 69
Implementaciones de LRU
LRU con contador
» Cada entrada de la tabla de páginas tiene un contador. Cada vez que se referencia la página, se copia el tiempo del reloj en el contador
» Cuando necesitamos cambiar una página, se miran todos los contadores y se elige la que tiene el menor tiempo
LRU con pila
» Los números de páginas se mantienen en una pila (lista doblemente enlazada). Cuando se referencia una página se mueve a la cima de la pila (cambio de seis punteros como máximo)
» No hay que hacer búsqueda para la sustitución de una página, se sustituye la del fondo de la pila
Tema 4: Organización y gestión de memoria 70
Algoritmo del reloj
Cada página tiene asociado un bit de referencia R (lo pone a 1 el hardware)
Los marcos de página se representan por una lista circular y un puntero a la página
visitada hace más tiempo
Selección de una página:1. Consultar marco actual2. ¿Es R=0?
– No: R=0; ir al siguiente marco y volver al paso 1– Si: seleccionar parasustituir e incrementar posición
página 1ref.=1
página 3ref.=1
página 2ref.=1
3
página 4ref.=1
0
1
2
Tema 4: Organización y gestión de memoria 71
Comparación
Conclusión:» Influye más la cantidad de MP disponible
que el algoritmo de sustitución usado
nº faltasde pág.
nº marcos asignados
FIFO
RELOJ
LRU
OPTIMO
Tema 4: Organización y gestión de memoria 72
6.3 Comportamiento de los programas
Viene definido por la secuencia de referencias a página que realiza el proceso
Importante para maximizar el rendimiento del sistema de memoria virtual (TLB, alg. sustitución, ...)
Pá
gin
asre
fere
nci
adas
Tiempo
Tema 4: Organización y gestión de memoria 73
Propiedad de localidad
Distintos tipos» Temporal: Una posición de memoria
referenciada recientemente tiene una probabilidad alta de ser referenciada en un futuro próximo (ciclos, rutinas, variables globales, ...)
» Espacial: Si cierta posición de memoria ha sido referenciada es altamente probable que las adyacentes también lo sean (array, ejecución secuencial, ...)
Tema 4: Organización y gestión de memoria 74
Conjunto de Trabajo
Observaciones:» Mientras el conjunto de páginas necesarias puedan
residir en MP, el nº de faltas de página no crece mucho
» Si eliminamos de MP páginas de ese conjunto, la activación de paginación crece mucho
Conjunto de trabajo (Working Set) de un proceso es el conjunto de páginas que son referenciadas frecuentemente en un determinado intervalo de tiempo
WS(t,∆) = páginas referenciadas en el intervalo
de tiempo t - ∆ y t
Tema 4: Organización y gestión de memoria 75
Conjunto de Trabajo: propiedades
Propiedades» Los conjuntos de trabajo son transitorios» No se puede predecir el tamaño futuro de un
conjunto de trabajo» Difieren unos de otros sustancialmente
nºpág.
tiempo
ws1 ws2 ws3
Tema 4: Organización y gestión de memoria 76
Teoría del Conjunto de Trabajo
Un proceso sólo puede ejecutarse si su conjunto de trabajo está en memoria principal
Una página no puede retirarse de memoria principal si está dentro del conjunto de trabajo del proceso en ejecución
Tema 4: Organización y gestión de memoria 77
6.4 Hiperpaginación
Si un proceso no tiene “suficientes” páginas, la tasa de faltas es alta » bajo uso de la CPU » el SO incrementa el grado
de multiprogramación» más faltas de páginas
Hiperpaginación = el sistema operativo está ocupado en resolver faltas de página Grado de
multiprogramaciónP
rodu
ctiv
idad
Conductareal
Conductaesperada
Tema 4: Organización y gestión de memoria 78
Hiperpaginación (y II)
Formas de evitar la hiperpaginación:» Asegurar que cada proceso existente
tenga asignado un espacio en relación a su comportamiento Algoritmos de asignación variables
» Actuar directamente sobre el grado de multiprogramación Algoritmos de regulación de carga
Tema 4: Organización y gestión de memoria 79
6.5 Algoritmos de asignación y sustitución: Algoritmo Optimo
En cada referencia, busca qué página (en memoria real) no es referenciada en el intervalo de tiempo: [t, t + ∆ ] y ésta es la desplazada. ∆: Tamaño de la ventana para cada proceso
Requiere un conocimiento “a priori” de la cadena de páginas referenciadas (irrealizable)
– En la figura se representan las páginas del proceso que están en MP– Proceso de 5 páginas– ∆ = 4– En t=0 sólo la página D reside en MP
C, C, D, B, C,E,C, E,A,D
- - - - - - - - - A -
- - - - B - - - - - -
- C C C C C C C - - -
D D D D - - - - - - D
- - - - - - E E E - -
* * * * *
Tema 4: Organización y gestión de memoria 80
Algoritmo basado en el modelo del WS
En cada referencia, determina el conjunto de trabajo: páginas referenciadas en el intervalo (t - ∆, t] y sólo esas páginas son mantenidas en MP
– En la figura se representan las páginas del proceso que están en MP– Proceso de 5 páginas– ∆ = 4– En t=0 WS = {A, D, E}, A se referenció en t=0, D en t=-1 y E en t=-2
A A A A - - - - - A A
- - - - B B B B - - -
- C C C C C C C C C C
D D D D D D D - - - D
E E - - - - E E E E E
* * * * *
C, C, D, B, C,E, C,E,A,D
Tema 4: Organización y gestión de memoria 81
Algoritmo FFP (Frecuencia de Falta de Página)
Idea: para ajustar el conjunto de páginas de un proceso, usa los intervalos de tiempo entre dos faltas de página consecutivas:» Si intervalo de tiempo grande, mayor que λ, todas las páginas no
referenciadas en dicho intervalo son retiradas de MP» En otro caso, la nueva página es simplemente incluida en el
conjunto de páginas residentes
Formalmente: tc = instante de tº de la actual falta de página tc-1= instante de tº de la anterior falta de página Z = conjunto de páginas referenciadas en un intervalo de tº R = conjunto de páginas residentes en MP
Z(tc-1 ,tc) si tc - tc-1 > λ R(tc,λ) =
R(tc-1 ,λ) + Z(tc) en otro caso
Tema 4: Organización y gestión de memoria 82
Ejemplo del algoritmo FFP
Se garantiza que el conjunto de páginas residentes crece cuando las faltas de página son frecuentes y decrece cuando no lo son
– En la figura se representan las páginas del proceso que están en MP– Proceso de 5 páginas– λ = 2– La página A se referenció en t=-1 y E en t=-2– D se referencia en t=0
A A A A - - - - - A A
- - - - B B B B B - -
- C C C C C C C C C C
D D D D D D D D D - D
E E E E - - E E E E E* * * * * *
D,C, C,D,B,C,E, C,E, A,D