SO Sistemas operativos

Objetivos

1.- Introducir los conceptos y los problemas básicos de la gestión de

memoria:
Gestión de la memoria – Memoria lógica vs. memoria física
– Asignación de memoria a procesos
2.- Estudiar las técnicas básicas de asignación dispersa:
– Paginación.
– Segmentación.
– Combinación de técnicas
Equipo “Sistemas Operativos DISCA/DSIC” „ Segmentación Paginada
Universidad Politécnica de Valencia „ Paginación multinivel.
3.- Entender la gestión de memoria virtual: problemas a resolver,
implementación y efectos sobre el rendimiento del sistema.

TEMA 3.- Gestión de la memoria 2

Indice y bibliografía Contenidos

„ Índice
1.-
1.- Conceptos básicos
– 1. Conceptos básicos
„ Memoria física vs. Memoria lógica
– 2. Gestión de memoria „ La Unidad de Manejo de Memoria (MMU)
– 3. Asignación contigua 2.- Gestión de memoria
– 4. Asignación dispersa
3.- Asignación contigua
– 5. Memoria virtual
4.- Asignación dispersa
„ Bibliografía 5.- Memoria virtual
– A. Silberschatz, P.B. Galvin
– Sistemas Operativos. Conceptos Fundamentales. 5ª ed.
„ Capítulo 8: Apartados 8.1 (excepto 8.1.4), 8.2, 8.3, 8.4 (excepto 8.4.1),
8.5 (excepto 8.5.5), 8.6 y 8.7 (excepto 8.7.1 y 8.7.2)
„ Capítulo 9: Apartados 9.1, 9.2, 9.3, 9.4, 9.5 (excepto [Link]), 9.6
(excepto 9.6.1) y 9.7 .
TEMA 3.- Gestión de la memoria 3 TEMA 3.- Gestión de la memoria 4
 Memoria física vs. memoria lógica La Unidad de Manejo de Memoria (MMU)

„ Memoria lógica de un proceso (8.2)

Dirección CPU
P1 lógica
Memoria
0000 física
Mapa de
código memoria del
MMU
proceso en
ejecución
datos
Dirección
física
Bus
pila

1.- Conceptos básicos 5 1.- Conceptos básicos 6

Contenidos El problema de gestión de la memoria

1.- Conceptos básicos „ Todo sistema operativo debe ofrecer alguna solución para estos
problemas:
2.-
2.- Gestión de memoria Memoria
„ El problema de gestión de la memoria
– Reubicación física
P1
„ El problema de la reubicación – Escasez
P1
„ El problema de la escasez de memoria – Protección 0000
Memoria
„ El problema de la asignación – Asignación
P2
lógica
P2
3.- Asignación contigua
0000
4.- Asignación dispersa Memoria
P1
lógica
5.- Memoria virtual Pn
Pn
0000
Memoria
lógica

7 8
El problema de la reubicación El problema de escasez de la memoria

„ Reubicación en tiempo de ejecución: la MMU (8.1.1) „ ¿Por qué? (9.1)

– Programa reubicable es aquel que puede ejecutarse en cualquier segmento – Los procesos tienen una necesidad mayor de memoria.
de memoria física.
– Aumentar el grado de multiprogramación
– Para permitir la reubicación en tiempo de ejecución es necesario un
Hardware específico ÆMMU
– Ejemplo: MMU con registro base. „ Técnicas para solucionarlo:
– Intercambios (Swapping)
MMU MEMORIA – Memoria virtual
CPU
r
– Bibliotecas dinámicas
do dirección dirección 7000
es
a
lógica 2000 + física 7000
mov R1, R2
r oc
P

5000
Registro
base
9 10

El problema de escasez de la memoria El problema de escasez de la memoria

Disco
„ El método de intercambios (swapping) (8.3) „ La técnica de memoria virtual (9.1) memoria
secundaria

Memoria física
Memoria virtual memoria primaria
DISCO memoria lógica
MEMORIA
Proceso 1 swap out P2
Proceso 1

Proceso 2 Intercambio
swap in Proceso 2
con disco

Falta de
espacio

11 12
El problema de escasez de la memoria El problema de escasez de la memoria

„ Bibliotecas dinámicas (8.1.3) „ Bibliotecas dinámicas (8.1.3)

Memoria Memoria
P1 T. func. bib.
Memoria física física
printf
lógica P1
0000 P1 (3)
P1

libX11 Rutina cargador

[Link] (2)
[Link]
P2 Memoria
lógica
(1) call printf
0000
P2
Sistema
Stub printf
libX11
operativo
13 14

El problema de escasez de la memoria El problema de escasez de la memoria

„ Bibliotecas dinámicas (8.1.3) „ Bibliotecas dinámicas (8.1.3)

T. func. bib. Memoria T. func. bib. Memoria

printf física printf física
P1 P1
(3)
P1 (6) P1

Rutina cargador Rutina cargador

(2) (4)
(5)
[Link] [Link]

(1) call printf call printf

Sistema Sistema
Stub printf [Link] Stub printf
operativo operativo
15 16
 Asignación de la memoria Asignación de la memoria
„ Asignación contigua y asignación dispersa
„ Métodos de asignación
Memoria Memoria
física física – Asignación contigua (8.4) :
P1 memoria P1 memoria
lógica lógica
P1 „ Particiones fijas (8.4.2).
0000 0000
P1
„ Particiones variables (8.4.2)
P2
– Asignación dispersa:

P2 P2 „ Paginación (8.5).
memoria memoria P1
lógica P2 lógica
„ Segmentación (8.6).
0000 0000

P2

17 18

Contenidos Método de múltiples particiones fijas

1.- Conceptos básicos „ Memoria dividida en particiones de diferente tamaño

2.- Gestión de memoria „ Cola única / múltiples colas
3.-
3.- Asignación contigua „ Problema: Fragmentación interna sistema
„ Método de múltiples particiones fijas COLA DE operativo
„ Método de múltiples particiones variables PROCESOS
100 K
4.- Asignación dispersa P1 100 K
5.- Memoria virtual P4 necesita un hueco que ha sido P2 100 K
ocupado por un proceso que P3 100 K 400 K
desperdicia gran parte de su espacio.
P4 500 K
P5 400 K

600 K

TEMA 3.- Gestión de la memoria 19 20

 Método de múltiples particiones variables Método de múltiples particiones variables

„ Algoritmos de asignación de huecos

P1 P1 P1 – El primer ajuste
COLA DE
PROCESOS – El mejor ajuste
– El peor ajuste
P1 600 K
P2 P4 P4
„ Problema: Fragmentación externa
P2 1000 K P1
– Solución: Compactación coste: 1900
P3 300 K P1
P3 P3 P3 P3 P4
P4 700 K P1 600 K
P5 700 K P2 1000 K P1 P3
P3 300 K P4
Asignación Asignación P3
P2 acaba P1 acaba P3
P1, P2,P3 P4
P4 coste: 300

21 22

Contenidos La paginación

1.- Conceptos básicos „ Concepto básico (8.5)

Dividir el espacio de direcciones en memoria
2.- Gestión de memoria física
fragmentos de longitud FIJA.
3.- Asignación contigua „ Páginas. memoria
P2 lógica
4.-
4.- Asignación dispersa „ Marcos.
„ Paginación (8.5)
„ Segmentación (8.6)
„ Técnicas combinadas
– Segmentación paginada (8.7)
– Paginación multinivel (8.5.3)

5.- Memoria virtual páginas

marcos
TEMA 3.- Gestión de la memoria 23 24
La paginación La paginación
memoria
lógica
„ Estructura de una dirección lógica „ La tabla de páginas
– Descriptor de página :
0 „ Número de marco físico
„ Bit de validez
„ Bits de protección (rwx)
1
„ Bit de modificado

num. de página desplazamiento d p Tabla de páginas

p d
Descriptor de página
m-1 k-1 0
número de bit bits bit otros
m bits ... marco validez protección modificado ...
m-k bits k bits

N=2k 2m-k-1

25 26

La paginación La paginación memoria

física

„ Traducción de direcciones „ Un ejemplo 0

CPU Marco 0
num. de página desplazamiento Dirección lógica – Espacio de direcciones físicas: 32 bytes
4
p d – Espacio de direcciones lógicas: 16 bytes
Marco 1
m bits – Tamaño de página: 4 bytes
memoria memoria 8 e
f
física lógica Marco 2
Tabla de páginas g
h
0 a 12
p 0 b Marco 3
c Tabla de
d.f. = f*N + d 4
d
e páginas 16
f f Marco 4
P2 g 5
h 20 a
8 m 2 b
n Marco 5 c
. 6 d
m
num. de marco desplazamiento Dirección física . 24
d f 12
- Marco 6
n
f d .
.
28
n bits Marco 7
N=2k
27 28
La paginación La paginación
memoria
física
„ Protección ([Link]) 0000 „ Análisis
– Un ejemplo Marco 0
– Ventajas
Marco 1 „ No aparece fragmentación externa .
memoria
Tabla de páginas „ Facilita la reubicación.
lógica Marco 2 Página 0
0000 „ Proporciona protección.
Página 0 Marco bits acc. bit val Marco 3 Página 1 – Inconvenientes
2 r v
Página 1 Marco 4 Página 2 „ Fragmentación interna.
3 r v
Página 2 Marco 5
P1 4 r v – Tamaños de página
Página 3 7 r v Marco 6
„ Grandes Æ mucha fragmentación interna.
Página 4 8 w v Marco 7 Página 3 „ Pequeños Æ tablas de página muy grandes.
Página 5 9 w v Marco 8
6143 Página 4
- r i
Marco 9 Página 5
- r i
10239
29 30

La paginación La paginación

„ Implementación de la tabla de páginas (8.5.2) „ Tabla de páginas en memoria Memoria

física
– Registros de la MMU
– Memoria Dirección lógica
num. de página desplazamiento
– TLB CPU p d

– Tabla de páginas invertida (8.5.4)

PTLR > ¿ PTLR > p ? Marco bits bit
NO acc. val
SI
PTBR + f r v
... ... …

f r v

MMU marco de página desplazamiento

f d

31 32
La paginación La paginación
Memoria
„ Tabla de páginas en registros asociativos: (8.5.2) „ Tabla de páginas con TLB
física
TLB: Translation Look-aside Buffers
„ Los registros contienen: Dirección lógica
– clave. num. de página desplazamiento
CPU p d
– contenido.
„ La búsqueda se realiza por la clave en paralelo para todo el conjunto de
registros asociativos Marco bits bit
clave contenido acc. val

NO
f r v
... ... …

SI
MMU marco de página desplazamiento
f d

33 34

La paginación Contenidos

„ Tabla de páginas invertida 1.- Conceptos básicos

– sólo una tabla de páginas en el sistema, con tantas entradas como
2.- Gestión de memoria
marcos se tengan Dirección lógica
num. de página desplazamiento
3.- Asignación contigua
PID p d
4.-
4.- Asignación dispersa
„ Paginación (8.5)
„ Segmentación (8.6)
f „ Técnicas combinadas
– Segmentación paginada (8.7)
PID p (num. página) – Paginación multinivel (8.5.3)
marco de página desplazamiento
f d 5.- Memoria virtual
Dirección física

Tabla de páginas invertida

35 TEMA 3.- Gestión de la memoria 36
La segmentación La segmentación
„ Concepto de segmentación (8.6) „ Estructura de una dirección lógica
–Definición Memoria lógica
Memoria física num. de segmento desplazamiento
Dividir el espacio de direcciones en Datos SEGMENT
fragmentos de longitud VARIABLE. : s d
– Tipos de Segmento datox dw xx
datoy dw yy Codigo m bits
„ Código
:
„ Datos Datos ENDS
„ Pila
Tabla de segmentos

–Propiedades de los segmentos Datos

Codigo SEGMENT
:
Codigo ENDS

Pila
Pila SEGMENT Dirección física
dw 500
Pila ENDS n bits
37 38

La segmentación La segmentación
„ Traducción de direcciones (8.6.2)
„ La tabla de segmentos Dirección lógica CPU
– Contiene un descriptor por cada segmento. num. de segmento desplazamiento
s d
– Cada descriptor de segmento contiene, al menos:
„ Base del segmento: Memoria física
„ Límite: Tabla de segmentos
„ Otros, ... s
Codigo
base límite
Tabla de segmentos

base límite etc. Descriptor de segmento Datos

SI
base límite otras + <
NO
Pila
Dirección física
39 40
La segmentación La segmentación
Memoria
Memoria
física
física
„ Ejemplo de segmentación „ Compartición de segmentos
0 0
Proceso P1 Segmento
Memoria
Memoria pila 6300
1400
pila virtual
virtual Segmento 0 Límite Base Datos P1
subrutina Segmento 6700
Segmento 3 2400 S ... ... datos
D 400 6300 Segmento
Segmento 0 código
Tabla de segmentos 3200 C 21000 28400 12300
tabla emacs Datos P2
base límite Segmento 3
sqrt de
símbolos 0 1400 1000 4300 22300
Proceso P2 Segmento
Segmento 1 Segmento 4 1 6300 400 Segmento 2 pila
2 4300 400 4700 Límite Base
Segmento
programa 3 3200 1100 Segmento 4 S ... ... datos
principal 4 4700 1000 5700 D 10000 12300 Segmento 28400
C 21000 código emacs
Segmento 2 6300 28400
Segmento 1
emacs
6700 49400
41 42

La segmentación La segmentación
„ Facilidad para protección (8.6.4)
„ Análisis
Proceso P1 – Ventajas
„ No aparece fragmentación interna.
Límite Base Permisos
Dirección virtual „ Facilita la reubicación.
S ... ... RW C 1200
CPU Proporciona protección.
D 400 6300 RW „

C 21000 28400 RO – Inconvenientes

WR „ Fragmentación externa.
Segmento
pila INTR – Tamaños de segmento

Segmento
MMU „ Muy Grandes Æ aproximación a particiones variables.
datos „ Muy Pequeños Æ eliminaría la fragmentación externa, pero aumentaría el
Segmento Error tamaño destinado a registros
WR código
„ Tamaño Fijo ÆPaginación
emacs
43 44
La segmentación Contenidos

„ Implementación de la tabla de segmentos (8.6.3) 1.- Conceptos básicos

– Registros de la MMU 2.- Gestión de memoria
– Memoria 3.- Asignación contigua
– TLB
4.-
4.- Asignación dispersa
„ Paginación (8.5)
„ Segmentación (8.6)
„ Técnicas combinadas
– Segmentación paginada (8.7)
– Paginación multinivel (8.5.3)

5.- Memoria virtual

45 TEMA 3.- Gestión de la memoria 46

La segmentación paginada La segmentación paginada

(8.7) „ Traducción de direcciones

„ Motivación Dirección lógica CPU
Cuando los segmentos crecen: num. de segmento desplazamiento
„ Aumenta la fragmentación externa.
s d
„ Aumenta el problema de encontrar un Límite Base Otras
hueco libre en memoria para ubicarlo.
segmento Tabla páginas protec, .. p d’
„ Problema de asignación dinámica de STBR >
memoria debido a la diferencia de
tamaño de los segmentos.
„ Solución: + Tabla de segmentos Tabla páginas
p
– Paginar los segmentos Æ segmentación s
paginada Longitud Base tabla páginas + f

„ La tabla de segmentos
– Base de la tabla de páginas.
num. de marco desplazamiento
– Tamaño del segmento f d’
47 48
La segmentación paginada Contenidos

„ Análisis 1.- Conceptos básicos

– Ventajas 2.- Gestión de memoria
„ Ventajas de Segmentación 3.- Asignación contigua
„ Ventajas de Paginación 4.-
4.- Asignación dispersa
„ Proporciona protección. „ Paginación (8.5)
– Inconvenientes „ Segmentación (8.6)
„ Fragmentación interna. „ Técnicas combinadas
– Segmentación paginada (8.7)
– Paginación multinivel (8.5.3)

5.- Memoria virtual

49 TEMA 3.- Gestión de la memoria 50

La paginación multinivel La paginación multinivel Memoria

física
0
„ La tabla de páginas paginada 1
„ Motivación (8.5.3)
– Para espacios de direcciones muy grandes, la tabla de páginas puede Tabla de
Tabla de páginas páginas
ser excesivamente grande.
de 1er nivel 100
1
„ Solución: ...
500 500
– Paginar la propia tabla de páginas
100
... ... 708
708

...
900
929
Página de la ...
929
tabla de páginas 900
51 52
La paginación multinivel La paginación multinivel
„ Traducción de direcciones
„ Ejemplos reales de sistemas con paginación multinivel
num. de página desplazamiento – La arquitectura SPARC, con 32 bits de dirección soporta un esquema
p d
con 3 niveles de paginación.
– La arquitectura del Motorola 68030, con 32 bits de dirección soporta
p1 p2 d Dirección lógica un esquema con 4 niveles de paginación.
– El Pentium de Intel, con 32 bits de dirección, soporta un esquema con
2 niveles de paginación.

p1
p2
„ Inconveniente:
Cada nivel de paginación requiere incrementar en uno el número de
accesos a memoria para acceder a una dirección física.
Tabla de páginas
de 1er nivel d
Página de
tabla de páginas de Dato al que se accede
2º nivel
53 54

La paginación multinivel Contenidos

„ Solución: 1.- Conceptos básicos

– Utilizar un TLB 2.- Gestión de memoria
„ i386 de Intel, tiene un TLB con 32 entradas y consigue una tasa de
aciertos del 98% 3.- Asignación contigua
„ Motorola 68030 tiene un TLB de 22 entradas. 4.- Asignación dispersa
Pentium de Intel tiene dos TLBs:
„
5.-
5.- Memoria virtual
– el primero gestiona las páginas estándar de 4Kbytes y tiene una capacidad de
64 entradas. „ Paginación por demanda
– el segundo para implementar páginas de 4Mb y tiene una capacidad de 8 „ Algoritmos de reemplazo
entradas. „ Asignación de marcos
– Utilizar memoria caché para almacenar tablas de páginas. Con esto el „ Hiperpaginación
sistema se ralentizará, pero únicamente entre un 20% y un 40%.

55 TEMA 3.- Gestión de la memoria 56

 Memoria virtual Memoria virtual
„ Concepto de memoria virtual (9.1) „ Intercambios
– Paginación por demanda.
Memoria Virtual
– Segmentación por demanda. A (lógica)
Memoria Secundaria
„ Ventajas
0000
– Aumentar el grado de multiprogramación A0 A0 Memoria Principal
– Aumentar el tamaño de los programas (física)
A1
– Ahorro de memoria. A1
A0 A0 A0 B0
B1
„ Inconvenientes B A1 B1
– Reducir el rendimiento del sistema si no se diseña y sintoniza B0
A1
0000
adecuadamente.
B0
B1
– Mayor complejidad.
B1

57 58

Contenidos Paginación por demanda

1.- Conceptos básicos „ Concepto de paginación por demanda (9.2)

2.- Gestión de memoria – Paginación + Intercambios entre memoria principal y secundaria
(swapping).
3.- Asignación contigua
4.- Asignación dispersa
„ Descriptores de página
5.-
5.- Memoria virtual – Bit de validez
„ Paginación por demanda
– Bit de referencia
„ Algoritmos de reemplazo
„ Asignación de marcos – Bit de modificación
„ Hiperpaginación „ Problema con las páginas compartidas.

TEMA 3.- Gestión de la memoria 59 60

Paginación por demanda Paginación por demanda
„ Fallo de página: caso de página en disco (9.2)
„ Fallos de página 3: buscar página en el área de swap

– Definición: Sistema 2: excepción

Memoria
„ Se produce cuando referenciamos una página que tiene su bit de validez primaria
operativo
igual a 0 Memoria
Tabla de páginas
– Manejo de fallos de página secundaria
„ Página en disco. A Memoria Marco Validez Página 2
– Se carga la página en un marco lógica 4 1
Error de acceso. 0000 6- 0
1
„
Página 0 A0 A2
– Se aborta el proceso 1 1
Página 1 Página 0 A1 A3
„ El proceso “crece” y reclama nuevas páginas. 5 1
– Si el SO lo permite, se le asigna una nueva página al proceso, se valida y se le Página 2 0 0 Página 3
asigna un marco. Página 3 0 0 Página 1
0 0 4. Cargar página
(page in)
6: reiniciar
1: referencia
CPU instrucción
5: Actualizar tabla de páginas
61 62

Paginación por demanda Paginación por demanda

„ Algoritmo de fallo de página: caso de página en disco (9.2) „ Reemplazo de páginas (9.4)
– Encontrar la página demandada en disco. – Si la memoria principal está completamente ocupada y se produce un
– Encontrar un marco libre: fallo de página:
„ Si existe un marco libre, utilizarlo. „ Una página ubicada en memoria principal, denominada víctima, debe
dejar su marco a la página demandada.
„ Si no, utilizar un algoritmo de reemplazo de páginas.
– Si el bit de modificación es 1 hay que salvar la víctima a disco (page out)
„ Si el bit de modificación es 1, escribir la víctima en disco (page out).
– Leer la página demandada sobre el marco de la víctima (page in)
„ Actualizar la tabla de páginas, invalidando la víctima, y la tabla de marcos.
– Leer la página demandada del disco (page in) y ubicarla en el marco
– Existen diversos algoritmos para seleccionar la víctima.
libre, actualizando la tabla de páginas y la tabla de marcos libres.
– Transferir control al proceso de usuario, reejecutando la instrucción
que provocó el fallo de página.

63 64
 Contenidos Algoritmos de reemplazo de páginas

1.- Conceptos básicos

„ Serie de referencias (9.5)
2.- Gestión de memoria
3.- Asignación contigua „ Algoritmos de sustitución de páginas
4.- Asignación dispersa
– Algoritmo FIFO
5.-
5.- Memoria virtual
„ Paginación por demanda – Algoritmo óptimo
„ Algoritmos de reemplazo
„ Asignación de marcos – Algoritmo LRU
„ Hiperpaginación
– Algoritmo de aproximación al LRU
„ Segunda oportunidad

TEMA 3.- Gestión de la memoria 65 66

Algoritmos de reemplazo de páginas Algoritmos de reemplazo de páginas

„ Algoritmo FIFO (9.5.1)

„ Algoritmo FIFO
3 marcos de página: 9 fallos de página (6 reempl.)
– Filosofía
1 2 3 4 1 2 5 1 2 3 4 5 „ La víctima será aquella página que hace mas tiempo que ha sido
1 1 1 4 4 4 5 5 5 5 5 5 CARGADA en memoria.

2 2 2 1 1 1 1 1 3 3 3 – Ventajas
„ Muy simple.
3 3 3 2 2 2 2 2 4 4
– Inconvenientes
4 marcos de página: 10 fallos de página (6 reempl.) „ Presenta la anomalía de Belady

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

67 68
Algoritmos de reemplazo de páginas Algoritmos de reemplazo de páginas

„ Algoritmo óptimo (9.5.2)

„ Algoritmo óptimo
3 marcos de página: 7 fallos de página (4 reempl.)
– Filosofía
1 2 3 4 1 2 5 1 2 3 4 5 „ La víctima es aquella página que se tardará más en utilizar.
1 1 1 1 1 1 1 1 1 3 4 4 – Ventajas
2 2 2 2 2 2 2 2 2 2 2 „ Ofrece un número de fallos mínimo.

3 4 4 4 5 5 5 5 5 5 – Inconvenientes
„ Implementación imposible.
4 marcos de página: 6 fallos de página (2 reempl.)

1 1 1 1 1 1 1 1 1 1 4 4
2 2 2 2 2 2 2 2 2 1 1
3 3 3 3 3 3 3 3 2 2
4 4 4 5 5 5 5 5 5

69 70

Algoritmos de reemplazo de páginas Algoritmos de reemplazo de páginas

„ Algoritmos de pila
„ Algoritmos de pila (9.5.1)
– FIFO no es un algoritmo de pila
– Definición
„ Garantiza que un conjunto de páginas mantenido con N marcos es un 3 marcos de página: 9 fallos de página (6 reempl.)
subconjunto del que se mantiene con N+1 marcos 1 2 3 4 1 2 5 1 2 3 4 5
– Propiedad 1 1 1 4 4 4 5 5 5 5 5 5
„ Si un algoritmo es de pila NUNCA presenta la anomalía de Belady 2 2 2 1 1 1 1 1 3 3 3
3 3 3 2 2 2 2 2 4 4
4 marcos de página: 10 fallos de página (6 reempl.)
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
71 72
Algoritmos de reemplazo de páginas Algoritmos de reemplazo de páginas

„ Ejemplo algoritmo LRU

„ Algoritmo LRU (9.5.3)
3 marcos de página: 10 fallos de página (7 reempl.)
– Filosofía:
„ La víctima será aquella página que hace más tiempo que ha sido 1 2 3 4 1 2 5 1 2 3 4 5
REFERENCIADA. 1 1 1 4 4 4 5 5 5 3 3 3
– Propiedades: 2 2 2 1 1 1 1 1 1 4 4
„ Es un algoritmo de pila.
3 3 3 2 2 2 2 2 2 5

4 marcos de página: 8 fallos de página (4 reempl.)

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

73 74

Algoritmos de reemplazo de páginas Algoritmos de reemplazo de páginas

„ Alg. segunda oportunidad

„ Implementaciones del algoritmo LRU (9.5.3)
– Contadores 1
0
– Cola
„ Ventajas 1
0
– Buena aproximación al óptimo
„ Inconvenientes siguiente 0 víctima
víctima
– Difícil de implementar
1
– Solución:
„ Utilizar aproximaciones al algoritmo.

1
Bit de páginas
referencia
75 76
 Contenidos Asignación de marcos

1.- Conceptos básicos „ Problema de asignación de marcos

– Lista de marcos libres
2.- Gestión de memoria
– Reparto de marcos entre los procesos y el SO
3.- Asignación contigua
„ Algoritmos de asignación de marcos
4.- Asignación dispersa
– Asignación equitativa
5.-
5.- Memoria virtual – Asignación proporcional
„ Paginación por demanda
– Asignación prioritaria
„ Algoritmos de reemplazo
„ Asignación de marcos
„ Ambito de las políticas de reemplazo
„ Hiperpaginación – Reemplazo local
– Reemplazo global

TEMA 3.- Gestión de la memoria 77 78

Contenidos Hiperpaginación (thrashing)

1.- Conceptos básicos „ El problema de la hiperpaginación (9.7)

2.- Gestión de memoria – Causa de la hiperpaginación
3.- Asignación contigua
4.- Asignación dispersa Hiperpaginación
5.-
5.- Memoria virtual Utilización
„ Paginación por demanda de la CPU
„ Algoritmos de reemplazo
„ Asignación de marcos
„ Hiperpaginación

Grado de multiprogramación

TEMA 3.- Gestión de la memoria 79 80

Hiperpaginación (thrashing) Hiperpaginación (thrashing)

„ Principio de localidad de referencia (9.7.1) „ Modelo del área activa (9.7.2)

– Localidad: – Asume el principio de localidad de referencia.
Conjunto de páginas que un proceso utiliza conjuntamente. – Determinar el número de páginas que un proceso que deben tener en
– Principio de localidad de referencia. memoria para obtener un buen rendimiento y evitar la
hiperpaginación.
– Hiperpaginación ≡ Σ(tamaños de localidad) > (tamaño memoria total) – Área activa: conjunto de páginas accedidas en las últimas ∆
referencias.
– Ventana de área activa ∆ Es un número fijo de referencias.

81 82

Hiperpaginación (thrashing) Hiperpaginación (thrashing)

„ Modelo del área activa „ Control de la tasa de fallos de página (9.7.3)

... 5 3 5 2 3 5 2 3 5 4 5 4 5 9 8 9 4 6 9 2 3 9 2 Límite superior --> Asignar marcos

Tasa
de
fallos
de
página

∆ ∆

t1 t2
Límite inferior --> Eliminar marcos

AA(t1) = {2,3,5} AA(t2) = {4,5,6,8,9} Número de marcos

83 84