Tema 3.
Gestión de Memoria
• INTRODUCCIÓN
• SIN INTERCAMBIO NI MEMORIA VIRTUAL (Estático)
• Monoprogramación
• Multiprogramación con Particiones Fijas
• INTERCAMBIO
• Introducción
• Particiones Variables
• Algoritmos de gestión Libre / Ocupado
– Lista encadenada y Mapa de bits
• MEMORIA VIRTUAL
• Paginación
• Algoritmos de sustitución de páginas
• Cuestiones de diseño
Gestión de Memoria
1
Introducción
Cada vez, más memoria, más barata y ocupa menos:
1982
1985
16KB
1MB
16.000 pts.
500.000 pts.
PseudoPC
Victory (Unix)
PC
1991
1998
2002
2005
8MB
64MB
256MB
512MB
77.500 pts.
17.900 pts.
13.800 pts.
9.500 pts.
128MB
512MB
1GB
Sin embargo, ¡ SIEMPRE AMPLIANDO !
51.900 pts.
29.700 pts.
29.900 pts.
Ley de Parkinson
512K, 640K, 1M, 4M, 8M, 16M, 32M, 64M, 128M
MSDOS
¿Windows XP?
Gestión de Memoria
Win95
WinNT Win00
70MB
120MB 275MB
2
Introducción (objetivos)
Memoria: Recurso escaso y compartido (Multiprogramación)
Poca memoria para los muchos procesos que quieren ejecutarse
P1
P4
Memoria
?
P2
P5
Principal
P6
P3
Gestión eficiente
OBJETIVOS
• Proteger
• Compartir
• Organización eficiente
lineal
Caché
Principal
Secundaria
segmentada
• Reubicación de procesos
Gestión de Memoria
3
Introducción (¿Proceso en memoria?)
Program principal;
var
Vector1: array [0..$FFF] of byte := (23,43,…,53);
Vector2: array [0..$4FF] of byte;
begin
...
if Vector1[0] = Vector2[0]
then Subrutina;
Programa
...
end.
Objeto n
$5000
$5030
$5036
$503A
$503E
$5200
$9000
$A000
…
cmp $9000,$A000
bnz $503E
bsr $5200
…
(codigo de subrutina)
…
(valores de vector1)
…
(valores de vector2)
…
Gestión de Memoria
Programa
Fuente 1
Compilador
Programa
Objeto 2
Programa
Objeto 1
Enlazador
¿
Fichero
Ejecutable
Cargador
Código máquina
?
Memoria
Proceso
4
Introducción (¿Formato de un fichero ejecutable?)
• Fichero ejecutable  UNIX
$0000 Nº mágico
CP inicial
Cabecera --------Tabla secciones
$1000
Código máquina
$5000
Código
Var. Inic.
Var. No Inic.
--------------Tabla Símbolos
Inicio Tamaño
$1000 $4000
$5000 $1000
$500
------------$8000 $2000
Variables
Secciones inicializadas
.....
Otras secciones
$8000 Tabla símbolos
(depurador)
Gestión de Memoria
¡ Algunas secciones no ocupan espacio
en el fichero ejecutable y sí en
memoria !
5
Introducción (¿Imagen de un proceso en memoria?)
• Fichero ejecutable  UNIX
$0000 Nº mágico
CP inicial
--------Tabla secciones
$1000
Código máquina
$5000
• Imagen de un proceso
Código máquina
$4000
Memoria
Variables
inicializadas
$5000 Variables no
“0”
inicializadas
$5500 Memo. Dinámica
.....
Otras secciones
$xxxx Pila
Gestión de Memoria
$0000
S.O.
P1
Variables
inicializadas
$8000 Tabla símbolos
(depurador)
?
$0000
P1
sp
...
...
...
P4
sp
...
...
...
Pn
sp
...
...
...
P2
$yyyy
Pn
P4
CPU
pc
sp
...
...
...
6
Introducción (modelo estático vs dinámico)
M.P.
exec
M.P.
Pi
exec
Pi
¡ Reubicar !
exit
Pi
exit
Pi se ejecuta en la
misma zona de
memoria desde
que se crea hasta
que termina
Gestión de Memoria
M.P.
Pi
Pi
Pi puede ir
cambiando en su
totalidad de zona
de memoria
Pi puede ir
cambiando por
trozos de zona de
memoria
Intercambio
Memoria Virtual
7
Monoprogramación
• Máquina desnuda con monitor
“Primeras máquinas”
“Prácticas de arquitectura”
Programa
“Sistemas empotrados”
de usuario
+ drivers
Cargar y RS232
depurar
Monitor
programas
• Máquina con S.O. (MSDOS)
FFFFF IPL + ROM
drivers
RAM
00000
Power
Word
Excel
Point
S.O.
Gestión de Memoria
?
RAM
?
S.O. +
ROM
drivers
Word
Word
S.O. +
drivers
RAM
8
Multiprogramación ( Particiones Fijas )
Se trocea la M.P. libre para procesos de usuario en particiones fijas,
de diversos tamaños y reconfigurable sólo en arranque
300K
320K 115K
•
•
•
•
300K
200K
100K
?
Estático
“En arranque”
600K
S.O.
250K
50K
S.O.
CUESTIONES DE DISEÑO
¿Cuántas particiones?
• ¿Planificación?
¿De qué tamaño?
• Tabla de particiones
Reubicación
Tamaño y Libre / Ocupada
Protección
• Cola/s de procesos entrantes
Gestión de Memoria
9
Particiones Fijas ( ¿Cuántas particiones? )
Aprovechar UCP  Índice / Nivel de multiprogramación
% de uso 100
de la UCP 80
60
40
20
1
2
3
4
5
6
7
8
9 10
Nivel de
Multiprogramación
¿Caracterización de los procesos?
20% de su tiempo hacen E/S
50% de su tiempo hacen E/S
80% de su tiempo hacen E/S
¡ Ojo ! Aprovechar la
UCP al 100% no es el
único objetivo
Usuarios interactivos
Gestión de Memoria
10
Particiones Fijas ( ¿De qué tamaño? )
Intentar aprovechar la memoria al máximo (ocupada al 100% por Pi)
• GRANDES
Fragmentación
300K
interna
200K 40K 50K
P200K no puede ejecutarse
pese a haber 510K sin usar
300K
S.O.
• PEQUEÑAS
250K
60K
200K 40K 50K
P60K no puede ejecutarse pese
a haber 5 particiones libres
Gestión de Memoria
50K
S.O.
Fragmentación
externa
11
Particiones Fijas ( Planificación )
• COLAS MÚLTIPLES / SEPARADAS
125
150
F
D
200K
 Entra un Proceso
Cola de la partición
“Mejor Ajuste”
400K
350K
80K
250
90
80
70
E
C
B
110
5
15
 Sale un Proceso P100K
¿Quién entra?
A
300K
100K
S.O.
• FIFO
• Más grande
• Más corto
B
E
C
Tiempos
Se libera P400K  Partición grande libre y 6 procesos bloqueados
¿Particiones de igual tamaño?  Equilibrar la carga
Gestión de Memoria
12
Particiones Fijas ( Planificación )
• COLA ÚNICA
90
125
150
F
E
D
4
80
110
25
70
250
C
B
A
5
15
3
200K
 Entra un Proceso
 Partición para él o
Se encola
400K
 Sale un Proceso P200K
¿Quién entra?
300K
Tiempos
100K
S.O.
• FIFO
• Más grande
• Más corto
B
D
F
• Más complejo y lento
• Mejor aprovechamiento de UCP y memoria
• Puede que injusticia: grandes vs pequeños
Gestión de Memoria
13
Particiones Fijas ( Reubicación )
128K
IF A >= 0
THEN
A := A-1
ELSE
A := A+1
512K
250
A
256K
TST
JMI
SUB
JMP
ELSE ADD
NEXT
R0
ELSE
#1,R0
NEXT
#1,R0
100K
00000
S.O.
Programa  Partición
¡No siempre la misma!
¿Direcciones Absolutas?
Gestión de Memoria
?
Problemas
00050
00052
00058
0005A
00060
00062
TST
JMI
SUB
JMP
ADD
R0
00060
#1,R0
00062
#1,R0
14
Particiones Fijas ( Reubicación )
?
20000
20050
20052
20058
2005A
20060
20062
TST
JMI
SUB
JMP
ADD
R0
00060
20060
#1,R0
20062
00062
#1,R0
SOLUCIONES
a) Reubicar al cargar (reubicación estática)
+20000 Direcciones Absolutas
Dirección de carga
b) Reubicación dinámica
20000
dv
 Registro de Reubicación
00060
+
dr
20060
c) Código reubicable
S.O.
Gestión de Memoria
JMI 8(PC)
15
Particiones Fijas ( Protección )
• Controlar accesos de Pi fuera de su zona
20000
20000
20050
20052
20058
2005A
20060
20062
...........
5FC00
TST
JMI
SUB
JMP
ADD
R0
00060
#1,R0
00062
#1,R0
No
direccionable?
dv
00060
Registro de Reubicación
(Registro Base)
+
dr
20060
dr>RL
5FC00
SI
Excepción
S.O.
Gestión de Memoria
16
Intercambio ( Introducción )
Dos grandes problemas de las particiones fijas sin intercambio:
A Muchos procesos interactivos y poca memoria para ellos
B ¿Cómo gestionar la memoria dinámica de los procesos?
?
P19
P1
P2
Máximo 16
procesos
try
4
S.O.
later
20 usuarios desean 16 particiones
de 1MB
usar editor 1MB
¿Una solución?
Gestión de Memoria
P16
S.O.
P1
P17
P18
P19
P20
¡ Eficiente si no hay trasiego !
Ampliar la M.P. con más
particiones en disco
17
Intercambio ( Introducción )
Algunas cuestiones:
P19
P2
P16
S.O.
?
• ¿ Cuándo intercambiar ?
P1
P17
P18
P20
• ¿ Quién por quién ?
• ¿ Coste del intercambio ?
Word  Excel
¡ 111..297 mseg !
Gestión de Memoria
18
Intercambio ( Introducción )
Dos grandes problemas de las particiones fijas sin intercambio:
A Muchos procesos interactivos y poca memoria para ellos
B ¿Cómo gestionar la memoria dinámica de los procesos?
300K
K
200K
300
250
200
150
100
300
P1
100K
S.O.
¿Por qué P1 pide 300K?
ti
Particiones Fijas
¿ Intercambio ?
tf
Partición de 300K
P100K P200K
P300K
P100K
¿Qué estructura tiene la memoria dinámica de un Pi?
Gestión de Memoria
19
Intercambio ( Introducción )
Componentes de MP de un Pi
$FFFFF
Fijo
Varía (bsr y rts)
Varía (new y dispose)
Necesita 325K y le doy 400K (crecer)
200K (C) + 75K (D) + 50K (P)
Pila
300K
• Código
• Pila
• Datos
Datos
Código
?
Dos zonas no contiguas
50K
Pila
400K
$00000
25K
Pila
Pila
200K
50K
Datos
Código
Datos
Código
S.O.
?
Gestión de Memoria
Datos
Fragmentación
Protección
Código
200K
20
Particiones Variables
• Asignar a cada proceso sólo la memoria que necesita
200
400
500
200
800
100
300
200
C
B
A
224 S.O.
A300K C200K
B100K
Gestión de Memoria
200
100
200
C
B
100
C
B
200
D
B 150
C
C
D
E
D
S.O.
S.O.
250
150
300
A
200
200
150
S.O.
S.O.
D150K
¿ Solución
E225K
Fragmentación externa
E esperando
?
21
Particiones Variables (Compactación)
• Siempre un único hueco con toda la memoria libre
200
400
500
200
800
100
C
B
300
A
224 S.O.
200
500
200
100
200
300
100
A
125
350
C
B
C
B
150
200
100
S.O.
Compactar
A300K C200K
D150K
¿ Siempre ?
B100K
Gestión de Memoria
Costoso en tiempo
225
D
C
B
150
200
100
S.O.
225
E
D
C
B
E
D
C
S.O.
S.O.
B
Compactar
E225K
¿ Cuándo ?
¿ De vez en
cuando ?
Gestión de huecos 22
Algoritmos de gestión trozos (Lista Encadenada)
• Lista encadenada: distribuida vs centralizada
Ordenada por direcciones y de cada trozo saber (al menos):
Tipo (Libre/Ocupado); Tamaño
S.O.
P1
Ocupado
5MB
P2
P3
Libre
6MB
P4
P5
Libre
4MB
P1
Gestión de Memoria
23
Algoritmos de gestión trozos (Lista Encadenada)
• Lista encadenada: distribuida vs centralizada
64MB 20
5
S.O.
6
P1
P1
dirTrozo $0140 0000
Tipo
Ocupado
Tamaño $0050 0000
Sig
4
13
P3
Gestión de Memoria
4
P5
• ¿Lista dinámica? => Array estático => ¿Tamaño?
• La memoria se da a trozos (sean de 4KB)
01400
P
00500
01900
H
00600
01F00
P
00400
P3
$0190 0000
Libre
$0060 0000
12
$01F0 0000
Ocupado
$0040 0000
02300
H
00D00
03000
P
00C00
03C00
H
00400
P5
$0230 0000
Libre
$00D0 0000
$0300 0000
Ocupado
$00C0 0000
$03C0 0000
Libre
$0040 0000
24
Algoritmos de gestión trozos (Liberación de Memoria)
• Lista encadenada:
Supongamos que termina un proceso (sea P2)
• Hay que tener en cuenta cuatro situaciones:
P1
P2
P1
P2
P2
P3
P1
P3
P1
P3
P3
P2
• ¡ Fusionar !  Ventaja de tener la lista ordenada (contigüidad)
• Conveniencia de tener la lista doblemente enlazada
Gestión de Memoria
25
Algoritmos de gestión trozos (Asignación de Memoria)
• Lista encadenada: Asignación de memoria
1. First Fit
“Primero en donde quepa”
2. Next Fit
“Siguiente donde quepa”
3. Best Fit
“Donde quepa mejor”
Muchos huecos inútiles
(demasiado pequeños)
¡ Recorrer
toda la lista !
4. Worst Fit “Donde quepa peor”
Liberación
¿ Cómo acelerar la asignación ?
ineficiente
5. Lista de procesos por un lado y de huecos por otro
Ya lo tenemos
[descriptores de procesos]
Ordenados por
tamaño
First = Best
¿Next?
6. Quick Fit “Donde quepa antes”
Gestión de Memoria
26
Algoritmos de gestión trozos (First Fit)
• FIRST FIT “Primero en donde quepa”
P
P
P
P
P
P
P
P
P P’
P
P
P’
P
Muchos huecos pequeños al principio y uno grande al final:
Ejemplo: [Fork(P20K)]8 + [Exit(P20K) + Fork(P18K)]8 + Fork(P15K)
P P P P P P P P
P P P P P P P P P’
P’
Gestión de Memoria
¡ Siempre recorriendo el principio !
27
Algoritmos de gestión trozos (Next Fit)
• NEXT FIT “Siguiente donde quepa”
Ejemplo: [Fork(P20K)]8 + [Exit(P20K) + Fork(P18K)]8 + Fork(P15K)
Inicio de búsqueda del siguiente hueco
P
P P P P P P P P
P P P P P P P P P
Fragmentación externa
¿Pi grande?
P P P P P P P P P P P P P P
Gestión de Memoria
! Huecos dispersos de tamaño moderado !
28
Algoritmos de gestión trozos (Quick Fit)
• QUICK FIT
“Donde quepa antes”
Idea: Varias listas que agrupan bloques de tamaño similar
P310
P220
P500
P900
64K
128K
256K
512K
1M
2M
4M
Enormes
16
65
32
112
40
52
280
800
300
360
360
3
32
3,5
3,8
400
¡ Todavía puede mejorarse tanto la asignación como la liberación !
Sistema Buddy (Compañeros)
Gestión de Memoria
29
Algoritmos de gestión trozos (Mapa de Bits)
• ¡Doy memoria a trozos! Asignación a golpe de 4K (granularidad)
libre
64MB ocupado
000....00 0
1 0
1 0
1 1 1 1 1 1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 1 1 0
1 0
1 0
1 1 1
S.O.
Pi
00000000
-------11111111
00011111
11111111
00000000
11111111
11000111
-------Pi pide 10K
Se le dan 12K (3 trozos)
Fragmentación
Interna
Gestión de Memoria
Pj
• ¿Tamaño del Mapa de Bits?
64MB/4KB = 16Kbits => 2KB
Pk
?
Lista
Encadenada
• ¿Liberación de memoria?
• ¿Asignación de memoria?
First, Next, Best, Worst => Viables
Quick, Buddy => Inviables
¡ No hay información explícita de tamaños !
30
Paginación
• PROBLEMÁTICA DEL INTERCAMBIO
• ARQUITECTURA SUBYACENTE
• TRADUCCIÓN DE DIRECCIONES
• UBICACIÓN DE LA TABLA DE PÁGINAS
• UNO O VARIOS ESPACIOS DE D.V.
• TRATAMIENTO DE FALTA DE PÁGINA
Gestión de Memoria
31
Paginación ( Problemática del Intercambio )
¿Su gran restricción?
Exigir que un Pi esté entero en
M.P. para poder ejecutarse
A Un Pi más grande que la M.P. no podrá ejecutarse
B Si {Procesos preparados} aumenta, no cabe en M.P.  Trasiego
C El intercambio Disco  M.P. es mucho (dos procesos enteros)
Trocear
M.P.
?
Gestión de Memoria
Overlays (solapamientos)
Compilador: 1 Análisis léxico
2 Análisis sintáctico
3 Análisis semántico
¿Solución general? 4 Generación de código
32
Paginación ( Problemática del Intercambio )
Solución  Darle al usuario la sensación de tener una M.P. enorme
• El Pentium 4 (32 bits de direcciones)
 4GB
8 veces
menos
• Un PC medio dispone tan sólo de
 512MB
M.P.
Espacio
de dir.
Espacio de Direcciones Reales del PC
• Teóricamente podemos escribir programas
pensando en el Pentium 4 y 4GB
• Tendremos una Memoria Virtual de 4GB y
mis programas se ejecutan aunque tenga
menos Memoria Principal (512MB)
siempre que quepan en la memoria virtual.
del P 4
M.P.
M.V.
M.P.
¿ Cómo funciona todo esto ?
Arquitectura subyacente
Gestión de Memoria
33
Paginación ( Arquitectura Subyacente )
M.V.
M.P.
¡ No caben !
MEMORIA VIRTUAL
• Principio de localidad:
Meto en M.P. los trozos
que hagan falta para
ejecutar Pr y Pv
dv
La Memoria Virtual reside
Bus Datos
físicamente en memoria secundaria
CPU
Gestión de Memoria
34
Paginación ( Arquitectura Subyacente )
M.V.
M.P.
0
0
1
2
3
Traducir
dvdr
8
6
dr
¿Cachés?
2
9
S.O.
MMU
fallo
Bus Datos
Gestión de Memoria
dv
CPU
?
5
6
7
8
9
• La M.V. se divide en páginas (1000B?)
• La M.P. se divide en marcos
35
Paginación ( Arquitectura Subyacente )
Resumiendo:
• M.V. en disco y gestionado como un sistema de particiones
variables (los trozos “granularidad” de M.V. son páginas)
• Las páginas de M.V. necesarias para que se ejecute un Pi están
en la M.P. en uno cualquiera de sus marcos
¡ Principio de localidad espacial y temporal !
• Función de traducción (dv  dr) implementada en Hw
¡ MMU interna vs externa !
• Las páginas se intercambian MV  MP (Falta de Página)
gracias a la intervención del S.O.
¿ Cómo hacer la traducción dv  dr ?
Gestión de Memoria
36
Paginación ( Traducción de direcciones )
M.P.
M.V.
F.T.
0
8
6
2
9
¿ Qué páginas
están cargadas
y dónde ?
Gestión de Memoria
?
0
1
2
3
5
6
7
8
9
37
Paginación ( Traducción de direcciones “decimal” )
M.V. de 16MB
M.P. de 1MB
M.P.
M.V.
0
0
1
4095
4096
2
8191
8192
Página 2
en Marco 1 (4096)
12287
11285
255
Gestión de Memoria
¿ # páginas ?  4096
¿ # marcos ?  256
Páginas de 4KB
4096
4096
8191
7189
MMU
8192
12287
11285
0
0
1
4095
4096
2
8191
8192
12287
2 1 4096
3093 +
7189
4095
38
Paginación ( Traducción de direcciones “binario” )
M.V. de 16MB
M.P. de 1MB
M.P.
0
Páginas de 4KB
12 bits
0000 0000 0000 0000 0000
¿ # bits dv ?
¿ # bits dr ?
M.V.
0
 24
 20
0000 0000 0000 0000 0000 0000
4095
4096
0000 0000 1111 1111 1111
0000 0001 0000 0000 0000
4095
4096
0000 0000 0000 1111 1111 1111
0000 0000 0001 0000 0000 0000
8191
8192
0000 0001 1111 1111 1111
0000 0000 0001 1111 1111 1111
0000 0010 0000 0000 0000
8191
8192
12287
0000 0010 1111 1111 1111
12287
0000 0000 0010 1111 1111 1111
dr 
8
12
Marco
Offset
Gestión de Memoria
dv 
0000 0000 0010 0000 0000 0000
12
12
Página
Offset
39
Paginación ( Traducción de direcciones “hexadecimal” )
MAR
HH
00
00
OFF
HHH
000
FFF 0
Tabla de
páginas
M.P.
02 000
02 FFF
8
6
2
FF 000
FF FFF
0
1
2
3
4
5
6
7
8
9
A
M.V.
Presente
Marco
P 02
9
008 51A
FFF
02 51A
Gestión de Memoria
0
1
2
3
PAG
HHH
000
000
OFF
HHH
000
FFF
5
6
7
008 000
8 008 FFF
9
FFF 000
FFF FFF
40
Paginación ( Ubicación de la Tabla de Páginas )
• Toda la T.P. en M.P.
M.P.
• Toda la T.P. en la M.M.U.
Se lee el
descriptor
M.P.
MMU
T.P.
Tabla de
Páginas
dato
MMU
dr
dv
CPU
Se lee el dato
(Caché | M.P.)
¡ Intolerable por lento !
Gestión de Memoria
dr
dato
dv
CPU
• PDP11 8 páginas de 8K
• ¿Viable en el 80486? 1M páginas 4K
¡ Intolerable por caro !
41
Paginación ( Tabla de Páginas “M.P. + caché” )
• Toda la T.P. en M.P. + una caché de la T.P. en la MMU
Cachés de
8..2046
entradas
¡ Tasas de
acierto del
98% !
dv 008 51A
MMU
RBTP
caché
009 FF
006 63
000 40
Tabla de
Páginas
1M
entradas
dato
008 52
002 A3
Página
Gestión de Memoria
M.P.
Marco
dr 52 51A
¿ Fallo de
Caché ?
42
Paginación ( Tabla de Páginas “Fallo caché” )
M.P.
003 A28 dv
T.P.
0
1
2
3
4
10
10
10
10
10
13
13
13
4095 13
000
004
008
00C P 84
010
MMU
10000
¿ Caché
llena ?
FF0
FF4
FF8
FFC
!Algunos P
por Software!
¿ Página no
presente ?
TLB 030
15F
A32
573
FFE
B00
004
003
F.P.
Gestión de Memoria
 10000+(003*4)
07
42
54
15
01
AB
C2
84
84 A28 dr
43
Paginación ( Tabla de Páginas “multinivel” )
Ejercicio
2 – 12.12.2001
Stack
Gap
Datos
4 Mb (210*212=22*220)
Texto
Evita mantener todas las tablas de páginas en memoria
Gestión de Memoria
44
Paginación ( Tabla de Páginas “invertida” )
M.P.
0
Bastaría con una
caché con tantas
entradas como
marcos
M.V.
F.T.
0
1
2
3
8
6
2
5
6
7
8
9
¿ Seguro ?
9
• Descriptor de página  P Marco
caché
??
Sigue siendo necesaria una T.P. completa (MP / MV)
Gestión de Memoria
45
Paginación ( Tabla de Páginas “descriptor” )
• Aspecto de un descriptor de página
P B R MC
PRESENTE
BLOQUEADA
REFERENCIADA
MODIFICADA
CACHE (Si/No)
LEJ
MARCO
Permisos: LECTURA
ESCRITURA
EJECUCIÓN
¿ Dirección en disco ?
innecesario
• Un disco entero, o varios, o una parte de uno, para la M.V.
• Un fichero especial “pagefile.sys”
Gestión de Memoria
46
Paginación ( Uno o varios espacios de dv )
• Un único espacio de direcciones virtuales para todos los procesos
M.V.
FT
M.P.
P0
M0
• Una única T.P.
P1
M1
P1
Global
P2
M2
P3
M3
• Reubicación:
P4
M4
Carga
P5
M5
P6
M6
Registro
P2
P7
M7
Reubicación
P8
P9
• ¿ Cómo crece un Pi ?
P10
Muy problemático
P3
P11
P12
• Se adapta bien a tener un
P13
disco con n*sector = página
P14
P15
Eficiencia
Ver ejercicio 3 20/6/00 47
Gestión de Memoria
Paginación ( Uno o varios espacios de dv )
• Un espacio de direcciones virtuales para cada proceso
M.V.(P1)
FT(P1)
M.P.
P0
M0
• Una T.P. por
P1
M1
P1
proceso
P2
M2
P3
M3
• Reubicación
M4
innecesaria
M5
P0
M6
P1
• ¿ Fácil crecer ?
M7
P2
P2
P3
P4
• Se adapta bien a tener un
P5
fichero por Pi (ineficiente)
P3
P0
P1
P2
Gestión de Memoria
• En la MMU, las dv se prefijan
por un identificador de proceso
(complejidad)
48
Paginación ( Tratamiento de Falta de Página )
• ¿Cuántas Faltas de Página puede generar una instrucción?
M.V.
M.P.
CPU
PC
$002FFA
$003000
?
clr
move
$0003FA
D0,$0045FB
1. Extraer instrucción  Leer dv $003000  F.P. Una instrucción,
2. Decodificarla
0, 1, 2 o más
F.P.
3. Ejecutarla  Escribir dv $0045FB  F.P.
Gestión de Memoria
49
Paginación ( Tratamiento de Falta de Página )
• El tratamiento de F.P. recae en el S.O.
(I) Hay marco libre
(II) No hay marco libre
M.P.
M.V.
0
8
6
2
9
Política de ubicación
simple: uno cualquiera
Gestión de Memoria
?
M.P.
0
0
1
2
3
5
?
5
6
7
8
9
?
8
6
3
2
1
9
Política de sustitución
no tan simple
50
Paginación ( Tratamiento de Falta de Página “II” )
2
S.O.
01 1
10 0
0
1
2
3
10
1
Gestión de Memoria
8
6
M.P.
M.V.
5
5
5
9
P M Marco
¿Víctima  2 ?
3
5
6
7
8
mov C,D 9
0
0
3
0FA3
0000
4
mov C,D
7
1
2
8
6 3
5 4
C,D 9 5
0FA3
2mov
7 6
7
1
354  Seleccionar
víctima,
Salvando
Fin
E/S. Página
(DMA)
2 página
salvada.
tocar
TP
ylibre.
arrancar
¿ Quién
actualiza
la cachéE/S
?
sucia
Marco
en5 disco
¡ Sólo si sucia !
51
Paginación ( Tratamiento de Falta de Página “II” )
Resumiendo:
1
2
3
Referencia a página no cargada en M.P.
Excepción BERR y se bloquea al proceso
Seleccionar víctima, tocar TP y arrancar E/S
¡ Sólo si sucia !
4
5
6
7
Salvando (DMA) página sucia en disco
Fin E/S. Página 2 salvada. Marco 5 libre.
Arrancar E/S para cargar Página 9 en Marco 5.
Transferencia DMA discoMP. CPU para otro Pi
8  Fin E/S. Página 9 cargada en Marco 5. P  Preparado
9  Actualizar TP
10  Rearrancar “Mov C,D” cuando preparado  UCP
Gestión de Memoria
¿O continuar?
52
Paginación ( Algoritmos de sustitución de páginas )
OBJETIVO: Minimizar el número de Faltas de Página (F.P.)
Accesos:{ ........ $001000, $0043FA, $001002, $006400,
$001006, $006402, $006406, $006408, $001008,
$00640A, $00100A, $00100E, $00640E, $001012 ..}
Serie de
Referencia
{ .. 1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1, ..}
Sean dos marcos
?
Un solo
marco F.P. 11
¿Cuantos más
marcos mejor?
3 o más
?
marcos F.P.
Gestión de Memoria
3
M0
M1
1 1 1
M0
M1
1 1 6 6
M0
M1
4 6
4 4 1
1 1 6 1 6 1 6 1 6 1
4 4 4 4 4 4 4 4 4
F.P.
3
Margen
para la
mejora
4
Algoritmos
10
53
Paginación ( Algoritmos de sustitución de páginas )
ALGORITMOS
IDEAL
Más tiempo tarde en volver a ser referenciada
NRU
No utilizada recientemente
FIFO
Más tiempo lleva en Memoria Principal
LRU
Menos recientemente usada
2nd Chance
Segunda oportunidad
RELOJ
FIFO + LRU
Serie de
Referencia
Gestión de Memoria
¡ El mismo !
{7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1}
54
Paginación ( Algoritmos de sustitución de páginas )
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 FP
7
2
7
0
4
0
IDEAL
9
1
3
1
7
2
0
FIFO
4
3
1
7
0
2
0
2
4
7
Gestión de Memoria
0
2
0
3
2
2
3
12
7
3
0
1
2
1
1
0
4
0
15
1
3
1
RELOJ
1
3
0
LRU
7
0
7
2
14
1
55
Paginación (Cuestiones de diseño: conjunto de trabajo)
• ¿Qué hacer cuando un proceso pasa a ejecución?
Carga por Demanda
Prealimentación
• Se van cargando las páginas que
el proceso vaya necesitando
Muchas F.P. evitables
• Se arranca la carga del
conjunto de trabajo del
proceso.
“Páginas usadas más
recientemente”
2,6,1,5,7,7,7,7,5,1,6,2,3,4,1,2,3,4,4,4,4,3,4,3,4,4,4,1,3,2,3,4,4,1,3
t1
CT(t1, 10) = {1,2,5,6,7}
Gestión de Memoria
t2
CT(t2, 10) = {3,4}
56
Paginación ( Cuestiones de diseño: trasiego )
MV
¿Más Procesos? =>  CT mayor que MP => Trasiego
MV
MP
MP
Cabe en
MP
No cabe
en MP
Páginas = 20 CT = 7
¿Tamaño de página?
 Páginas = 26 CT = 11
2n => 512B .. 4/8KB y aumentando ¡Superpáginas!
Más Fragmentación Interna Mejor ajuste de localidad
¿Grandes?
Mejor rendimiento E/S
Gestión de Memoria
Más ineficiencia de E/S
¿Pequeñas?
57
Paginación ( Cuestiones de diseño: otras )
• Asignación local frente a global
PFF
Pi
Pj
• Control de carga
FIN
Gestión de Memoria
58
Descargar

Sistemas Operativos I