1. Ingeniería

Contenido
• Soporte de Hardware
Paginación
– Traducción de direcciones en un sistema de
paginación
– Tabla de páginas implementada como:
• Conjunto de registros
• En memoria principal
• Registros Asociativos
M. B. Ibáñez
M. B. Ibáñez
Características de la Paginación y
la Segmentación
¿Cómo se ejecuta un programa?
• Las referencias a memoria son traducidas
dinámicamente a direcciones físicas en tiempo de
corrida
– Un proceso puede ser llevado y traido de memoria
principal de tal forma que ocupe diferentes regiones
• Un proceso puede ser partido en piezas que no
tienen que estar contiguas en memoria principal
– Todas las partes de un proceso no necesitan estar en
memoria principal durante la ejecución
From Operating Systems. Internals and Design Principles. W. Stalli ng. Prentice Hall.
• El Sistema de Operación lleva a memoria
principal algunas piezas del programa
• Conjunto residente - parte del proceso que está
en memoria principal
• Se genera una interrupción cuando una dirección
que se necesita no está en memoria principal
• El Sistema de Operación coloca el proceso en
estado blocked
From Operating Systems. Internals and Design Principles. W. Stalling. Prentice Hall.
M. B. Ibáñez
M. B. Ibáñez
¿Cómo se ejecuta un programa?
Ventajas de particionar los
procesos
• La parte del proceso que contiene la dirección
lógica es traida a memoria principal
• Más procesos pueden estar en memoria
principal
– operating system issues a disk I/O Read request
– El Sistema de Operación solicita una lectura al disco
– Otro proceso es despachado (se ejecuta) mientras el
disco realiza la lectura
– Se lleva a cabo una interrupción cuando el disco
termina la lectura.
– El Sistema de Operación coloca el proceso afectado en
estado ready.
From Operating Systems. Internals and Design
Principles. W. Stalli ng. Prentice Hall.
M. B. Ibáñez
– Solo cargar algunas piezas de cada proceso
• Con tantos procesos en memoria principal,
es más probable que alguno de ellos esté en
estado ready
• Es factible que un proceso sea más grande
que la memoria principal
From Operating Systems. Internals and Design Principles. W. Stalling. Prentice Hall.
M. B. Ibáñez
1
Ventajas de particionar los
procesos
Tipos de Memoria
• El proceso puede ser tan grande como lo
permita el tamaño del disco duro
• Sería un desperdicio llevar a memoria todas
las piezas de un programa cuando solo una
parte de ellas serán usadas
• Se ahorra tiempo pues las piezas no
utilizadas no son llevadas a memoria
• Memoria real
From Operating Systems. Internals and Design Principles. W. Stalli ng. Prentice Hall.
From Operating Systems. Internals and Design Principles. W. Stalling. Prentice Hall.
– Memoria principal
• Memoria virtual
– Memoria en disco
M. B. Ibáñez
M. B. Ibáñez
Principio de Localidad
Soporte necesario para la
memoria virtual
• Las referencias a los datos de un programa tienden
a estar cerca las unas de las otras
• Solo unas piezas de un proceso serán necesarias
durante un periodo de tiempo corto
• Es posible predecir con cierta confiabilidad qué
piezas serán necesarias en el futuro
• Esto sugiere que la memoria virtual puede trabajar
eficientemente
• El hardware debe soportar la paginación y
la segmentación
• El Sistema de Operación debe ser capaz de
manejar el movimiento de páginas y
segmentos desde memoria principal a
memoria secundaria y viceversa
From Operating Systems. Internals and Design Principles. W. Stalli ng. Prentice Hall.
From Operating Systems. Internals and Design Principles. W. Stalling. Prentice Hall.
M. B. Ibáñez
M. B. Ibáñez
Paginación
Paginación
• Cada proceso tiene su propia tabla
• Cada entrada de la tabla contiene el número
de frame de la página correspondiente en
memoria principal
• Se necesita un bit para indicar si la página
está o no en memoria principal
Virtual Address
Page Number
Offset
Page Table Entry
P
M
Other Control Bits
Frame Number
From Operating Systems. Internals and Design Principles. W. Stalli ng. Prentice Hall.
From Operating Systems. Internals and Design Principles. W. Stalling. Prentice Hall.
M. B. Ibáñez
M. B. Ibáñez
2
Traducción de direcciones
en un
Sistema de Paginación
Ejercicio
Virtual Address
Page #
Offset
Frame #
Un sistema implementa un espacio de direcciones de páginas
virtuales utilizando una tabla de páginas de un nivel
La tabla de páginas para el proceso que corre incluye las
siguientes entradas:
Offset
R egister
Page Table Ptr
Page Table
Offset
+
Page
Frame
P#
Página
Program
Paging
Número de Frame
0
1
2
3
4
Frame #
Main Memory
4
8
16
17
9
From Operating Systems. Internals and Design Principles. W. Stalling. Prentice Hall.
M. B. Ibáñez
M. B. Ibáñez
El tamaño máximo del espacio de
direcciones es de 16 megabytes
El tamaño de la página es de 1024 bytes,
y el tamaño máximo de la memoria física de la
máquina es de 2 megabytes
16Mbytes = 2
24
bytes
Virtual Address
2
24
21
11
/ 2 10 = 2
frames
2
Memory
21
bytes
M. B. Ibáñez
M. B. Ibáñez
¿Cuántos bits se necesitan para
cada entrada de la tabla?
¿Cuál es el número máximo en
entradas en la tabla de páginas?
Virtual Address
11 + α
Memory
2
11
24
frames
p
...
offset
10
14
Page table
Page size = 2
M. B. Ibáñez
10
bytes
M. B. Ibáñez
3
¿Cuál es el número máximo en
entradas en la tabla de páginas?
11 + α
Memory
2
14
2
11
frames
...
¿Cuál el la dirección física de la
dirección virtual 1524?
Page
0
1
2
3
4
Frame
4
8
16
17
9
Page table
La dirección virtual 1524
está en la página 1
La página 1 está en el
frame 8
mod(1524, 1024) = 500
1524 corresponde a la
dirección física :
8 x 1024 + 500 = 8692
M. B. Ibáñez
M. B. Ibáñez
Tabla de Páginas
Tabla de páginas
Implementada como un conjunto de Registros
En Memoria Principal
• La rapidez de acceso a estos registros
permite una traducción eficiente de las
direcciones lógicas
• La DEC-PDP-11 es un ejemplo de esa
arquitectura. Las direcciones consisten de
16 bits, y el tamaño de la página es de 8K.
La tabla de páginas tiene ocho entradas
M. B. Ibáñez
Tabla de páginas
• La tabla de páginas puede ocupar mucho
espacio en memoria principal
• La tabla de páginas también es almacenada
en memoria virtual
• Cuando un proceso corre, parte de su tabla
de páginas está en memoria pincipal
From Operating Systems. Internals and Design Principles. W. Stalli ng. Prentice Hall.
• Dos elementos:
– Tabla de páginas en memoria principal
– page-table base register (PTBR) apunta a la tabla de
páginas
• Problema: access(location i):
– Indexar la tabla de páginas usando el PTBR, obtener el
número del frame
– actual address = frame-number + page-offset
• El acceso a memoria se ha demorado en un
factor de 2
M. B. Ibáñez
Translation Look-aside Buffer
(Registros Asociativos)
• Cada referencia a memoria virtual puede
ocasionar dos solicitudes de memoria
– Obtención de la dirección de la tabla de páginas
– Obtención de los datos
• Para resolver este problema se asigna un
cache especial para colocar las entradas de
página
– Se llama TLB - Translation Look-aside Buffer
M. B. Ibáñez
From Operating Systems. Internals and Design Principles. W. Stalling. Prentice Hall.
M. B. Ibáñez
4
Translation Look-aside Buffer
Translation Look-aside Buffer
• Contiene las entradas de la tabla de páginas
que han sido usadas más recientemente
• Trabaja de manera similar al cache de
memoria principal
• Dada una dirección virtual, el procesador
examina el TLB
• Si la entrada de la tabla de página está
presente (un hit), el número del frame es
recuperado y se forma la dirección real.
• Si la entrada de la tabla no está presente (un
miss), el número de la página es utilizado
para indexar la tabla de páginas del proceso.
From Operating Systems. Internals and Design Principles. W. Stalli ng. Prentice Hall.
From Operating Systems. Internals and Design Principles. W. Stalling. Prentice Hall.
M. B. Ibáñez
M. B. Ibáñez
Translation Look-aside Buffer
Translation Look-aside Buffer
• Primero investiga si la página está en
memoria principal
– Si no está en memoria principal, se produce un
fallo de página
• El TLB es actualizado para incluir la nueva
entrada de página
•
From Operating Systems. Internals and Design Principles. W. Stalli ng. Prentice Hall.
• Cada registro consiste de dos partes:
– Una clave
– Un valor
• Cuando los registros asociativos son
presentados con un item,
– El item es compardo con todas las claves
simultáneamente
– Si el item es hallado, el correspondiente valor
del campo es la salida
M. B. Ibáñez
M. B. Ibáñez
Uso del Translation Look-aside Buffer
Uso del Translation Look-aside Buffer
Main Memory
Virtual Address
Page # Offset
Main Memory
Virtual Address
Page # Offset
Translation
Lookaside Buffer
Translation
Lookaside Buffer
TLB hit
Offset
Offset
Page Table
TLB miss
Frame # Offset
R eal Address
M. B. Ibáñez
Frame # Offset
R eal Address
M. B. Ibáñez
5
Uso del Translation Look-aside Buffer
Secondary
Memory
Main Memory
Virtual Address
Page # Offset
Uso del Translation Look-aside Buffer
Translation
Lookaside Buffer
Translation
Lookaside Buffer
TLB hit
Offset
Load
page
Page Table
Offset
Load
page
Page Table
TLB miss
TLB miss
Frame # Offset
R eal Address
Frame # Offset
R eal Address
Page fault
Page fault
M. B. Ibáñez
From Operating Systems. Internals and Design Principles. W. Stalling. Prentice Hall.
M. B. Ibáñez
START
Operation of TLB
CPU checks
the TLB
Page
table entry in
TLB?
Hit Ratio
• Es el porcentaje de veces que un número de
página es hallado en los registros
asociativos
• Un 80% hit ratio significa que hallamos el
número de página deseado en los registros
asociativos un 80% del tiempo
Yes
No
Access page
table
No
Page fault
hand lin g routin g
Secondary
Memory
Main Memory
Virtual Address
Page # Offset
Page in m ain
memory?
Yes
B. Ibáñez
UpdateM.
TLB
CPU generates
Physical
Addr ess
Ejemplo
• Toma 20 nanoseconds buscar en los
registros asociativos
• Toma 100 nanoseconds accesar la memoria
principal
• Entonces, llegar a una posición de memoria
toma 120 nanoseconds cuando el número de
página está en los registros asociativos
M. B. Ibáñez
M. B. Ibáñez
Ejemplo
• Si fallamos en hallar el número de página
en los registros asociativos (20 nanoseconds )
– Debemos accesar memoria para obtener el
número del frame en la tabla de páginas (100
nanoseconds)
– Accesar la palabra necesaria en memoria (100
nanoseconds)
20 + 100 + 100 = 220 nanoseconds
M. B. Ibáñez
6
Ejemplo
• Supongamos tener un 80% hit ratio
• Calcular el effective memory access time:
EMAT
EMAT = 0.80 x 120 + 0.20 x 220 = 140 nanoseconds
M. B. Ibáñez
7