Download Segmentación

Memory Management
M.C. Juan Carlos Olivares Rojas
Operating Systems
[email protected]
April, 2009
Outline
Política y filosofía de A.M.
Mecanismos de asignación
Estrategias de Asignación
El concepto de memoria virtual
Mecanismos de localización
Outline
Implantación de mecanismos de memoria virtual
Base limite
Segmentación
Paginación
Segmentación paginada
Mapa de Memoria
Memoria expandida
Memoria extendida
Objective
• The student will know and apply the basis of
memory management
Política y filosofía de A.M.
• Una de las principales características de una
computadora es la capacidad que tienen
para almacenar datos e información.
• El primero en tener la idea de almacenar un
programa en una computadora fue Jonh Von
Neumman (participante en la ENIAC).
• El utilizó la memoria para almacenar datos y
programas.
Memoria
• En otro modelo de arquitectura de
computadoras conocida como Arquitectura
Harvard, existe una memoria especial para
datos y otra memoria para programas. Esto
hace que los circuitos sean más eficientes pero
más costosos a la vez.
• La gran mayoría de la computadoras
(incluyendo las PC) utilizan la arquitectura Von
Neumman.
Concepto de memoria
• La memoria principal puede ser considerada
como un arreglo lineal de localidades de
almacenamiento de un byte de tamaño. Cada
localidad de almacenamiento tiene asignada
una dirección que la identifica.
• La memoria principal es el lugar donde el CPU
lee las instrucciones a ejecutar, así como
algunos datos a emplear.
Memoria
Memoria
• ¿Por qué es importante la memoria?
• Programas = Algoritmos + Estructuras de Datos
• Estructuras de Datos (pilas, listas, colas, etc.)
son memoria.
Conceptos de memoria
• Existen dos tipos de memoria primaria: volátil (RAM) y
no volátil (ROM).
• La memoria volátil es parecida a un pizarrón. Puede
perder los datos.
• El administrador de memoria se va a encargar de
gestionar la memoria RAM. La memoria ROM sólo la
utiliza para funciones específicas.
Memoria
Memoria
• La memoria se puede ver como un casillero en
el cual se almacena información.
• La memoria puede ser estática o dinámica
dependiendo de cómo se gestione.
• La memoria está divida en secciones de
código, datos estáticos, Pila y el Heap
(monton).
Memoria
Memoria
Conceptos de memoria
• Todo sistema operativo tiene un mapa de
memoria que indica como están administrada la
memoria y que partes se pueden ocupar.
• La filosofía del administrador de memoria
consiste en optimizar el uso de este recurso, ya
que la memoria es uno de los componentes
críticos de todo sistema de cómputo.
Mapa de Memoria
Mapa de Memoria
• Mapa de Memoria de Windows
Volcado de memoria
• Vista del estado de la memoria a través del
comando debug.
Memoria
• La principal problemática de la memoria
principal es que no es persistente. Por este
motivo se tienen que implementar estrategias
de almacenamiento y recuperación de
información.
• Las operaciones básicas que se realizan sobre
una memoria son dos: lectura (r) y escritura
(w).
Memoria
• Las operaciones anteriores son a nivel usuario.
A nivel sistema se tienen llamadas al sistema
como malloc, free, allocate, etc. También debe
proporcionar
opciones
de
bloqueo
y
desbloqueo (protección).
• La ley de Parkinson dice: “los programas se
expanden hasta llenar la memoria disponible
para contenerlos”.
Memoria
• No por tener el doble de memoria instalada en
un sistema legado, este será el doble de
rápido.
• La memoria física es utilizado por muchos
procesos en lugar de la memoria virtual.
• Todo proceso necesita memoria física para
poderse ejecutar.
Administrador de memoria
• Sirve para tener un control sobre los lugares
donde están almacenados los procesos y datos
que actualmente se están utilizando.
• Las políticas de administración de memoria
generalmente son duras, es decir no
modificables, pero se pueden configurar
algunos parámetros para su mejor uso.
Administrador de Disponibilidad
• Tanto el administrador de memoria y el de
archivos son ejemplos claros de un
administrador de disponibilidad sobre recursos.
• La memoria basa sus políticas y mecanismos
en base a jerarquía. Por ejemplo se tienen los
registros en el microprocesador, la memoria
caché y la RAM
Administrador de Disponibilidad
Políticas de asignación
• La memoria caché es una memoria de acceso
rápido. Es finita, se utiliza en muchos niveles
como por ejemplo en microprocesadores,
servicios como la Web, etc.
• Otro ejemplo de memoria son los buffer o
memorias temporales de E/S
Políticas de asignación
• Pueden ser locales o globales. Es más difícil
obtener una buena administración local.
• Las políticas en general son globales mientras
los mecanismos son locales
Ejemplos de memoria
• Las tendencias actuales sobre el manejo de
memoria indican el uso en diversas
aplicaciones:
• Portapapeles: permite guardar
transferirlo a otros programas.
datos
y
• Uso de base de datos en memoria. Algunas
versiones de MySQL Lite permiten hacerlo.
Ejemplos de memoria
• Las computadoras actuales permiten guardar
los datos al apagar una computadora, para
tener un mejor desempeño (hibernación,
suspensión).
• Los punteros permiten desplazarnos por las
localidades de memoria. Una variable es una
localidad de memoria.
Mecanismos de asignación
• Un mecanismo de asignación determina la
cantidad de bloques (particiones) que serán
administrados en la memoria.
• El esquema básico de asignación consiste
en particionar (dividir) la memoria en
diferentes partes.
• Existen 3 mecanismos de Asignación:
Mecanismos de asignación de memoria
• Asignación de una partición. En la memoria se
considera la existencia de una sola partición,
esto es, se tiene la capacidad de ejecutar un
proceso.
• La partición es toda la memoria, cuya
administración corre por cuenta del usuario, o
sea, no hay un sistema operativo. Por ejemplo
las consolas de videojuegos de 8bits al
introducir un cartucho “ROM” se apodera de
toda la máquina.
Mecanismos de Asignación de
Memoria
Mecanismos de asignación de memoria
• Asignación de dos particiones. La memoria se
divide en 2 bloques. En una partición se carga
el Sistema Operativo y en la otra el programa
del usuario.
• Es el concepto de Sistema Operativo
Monousuario. Existen direcciones que un
programa no puede acceder.
Mecanismos de Asignación de
Memoria
Mecanismos de asignación de memoria
• Asignación de múltiples particiones.
La
memoria es dividida en varias particiones una
para el Sistema Operativo y las demás para los
procesos de usuarios u otras funciones
especiales del Sistema Operativo.
• Este es el concepto teórico de asignación de
memoria en los Sistemas Operativos de
Multiparticiones y de Multitarea.
Mecanismos de Asignación de
Memoria
Estrategias de asignación de memoria
• Una estrategia de asignación de memoria determina
el lugar donde será cargado un nuevo proceso en
base a un criterio. Las estrategias de asignación son:
• Primer ajuste. El Sistema Operativo asigna el primer
bloque de memoria libre con espacio suficiente para
satisfacer la información. La búsqueda de este bloque
es de manera secuencial.
Estrategias de asignación de memoria
• Mejor ajuste. El sistema operativo busca el
bloque de memoria que represente el menor
desperdicio según el requerimiento.
• Peor ajuste. El sistema operativo asigna el
bloque mas grande que encuentre.
Estrategias de asignación
• Existen otras estrategias de asignación poco
implementadas como:
• Siguiente ajuste: en este esquema se accede a
la siguiente partición de memoria disponible, es
semejante al primer ajuste. Es útil para
garantizar espacios extras.
Estrategias de Asignación
• Sea el siguiente mapa de memoria en donde se
cuentan con particiones fijas del tamaño
indicado y tres procesos ya cargados en
memoria.
• Llegan los procesos p4, p5 y p6 de tamaño
100, 75 y 120. ¿cómo queda el mapa de
memoria si se aplican las estrategias de mejor,
primer, segundo y peor ajuste?
Estrategias de Asignación
Estrategias de Asignación
Estrategias de asignación
• Listas variables: en este esquema, se propone
un forma de mejorar el acceso a las unidades
de asignación (partición) disponibles.
• Este método mantiene varias listas con
diferentes tamaños de particiones. La
desventaja radica en actualizar la lista de
control de dichas particiones.
Estrategias de Asignación
Complejidad de los mecanismos y
estrategias de asignación
• Cualquier método para manejar la disponibilidad de la
memoria presenta inconvenientes como:
•
•
•
•
Fragmentación
Overhead
Relocalización de programas
Trashing (sacar un programa inmediatamente
después de haber sido asignado memoria)
Concepto de Memoria virtual
• Es un método mediante el cual, un sistema operativo
simula tener mas memoria principal que la que existe
físicamente. Para implementar la memoria virtual se
utiliza un medio de almacenamiento secundario de
alta velocidad de acceso, generalmente en disco duro
de la maquina.
• Se utiliza la paginación como método de
administración de memoria básica y algún mecanismo
de intercambio.
Memoria virtual
• En las tablas de paginas se agrega un campo mas a
cada entrada: el bit valido/invalido (p).
• En los procesadores 80386 y posteriores, que indica
si la página a la que se está haciendo referencia en
un momento dado se encuentra en la memoria
principal (válido) o en el disco duro (inválido). Cuando
el sistema operativo haga referencia a una página
inválida, deberá ir al disco duro y cargarla a memoria
principal para continuar el procesamiento.
Virtual Memory
• Espacio de Direcciones de
32-bit (4 GB)
– 2 GB espacio de usuarios
– 2 GB sistema operativo
• Espacio de Direcciones de
64-bit
– 7192 GB espacio de usuario
(Itanium)
– 8192 GB espacione de
usuario (x64)
– ~6000 GB sistema operativo
Espacio de Direcciones
De 32-bit
Único por proceso
2 GB
Espacio de
Procesos
de Usuario
Systemwide
2 GB Sistema
Kernel/HAL
drivers
Sistema
de cache
Mecanismos de localización
• Los mecanismos de localización hacen referencia a la
forma en como se puede ubicar un programa en
memoria.
• Los programas se localizan en base a un mecanismo
y estrategia de asignación.
• La relocalización de un programa es más complicado
ya que implica volver asignar un nuevo programa en
memoria cuidando los demás espacios.
Implantación de mecanismos de
memoria virtual
• Existen 2 métodos para cargar programas en
memoria:
• Demanda de página: consiste en iniciar la
ejecución de los procesos sin páginas cargadas,
estas se irán cargando conforme el proceso las
demande.
• Prepaginación: consiste en que el sistema
operativo predice cuales páginas se ocuparán
durante la ejecución de un proceso.
Algoritmos de descarga (Reemplazo)
• Se utiliza para determinar cuales páginas serán
descargadas hacia el disco duro cuando se
quiera cargar nuevas paginas y no haya
memoria libre. Existen 3 algoritmos básicos:
• MIN: Consiste en descargar la o las páginas
que no se necesitarán en el periodo de tiempo
más largo en el futuro. Esta implementación es
imposible.
Algoritmos de descarga (Reemplazo)
• FIFO: Consiste en tener un contador de tiempo
para cada pagina para descargar las mas
viejas.
• LRU (Least Recently Used): Consiste en
descargar las últimas páginas usadas (se usa
el pasado para predecir el futuro). Lo utiliza
Windows.
Algoritmos de Descarga
(Reemplazo)
Algoritmos de Descarga
(Reemplazo)
• Sea el siguiente mapa de memorias con tres
procesos activos y tres procesos nuevos, p4,
p5 y p6 de tamaño 100, 75 y 120.
• Como no existe memoria disponible se necesita
sacar procesos de la memoria. Se asume que
el primer proceso p1 es el más antiguo y que
se tiene una tabla de utilización de las
particiones de memoria.
Algoritmos de Descarga
(Reemplazo)
Actividad
• Realizar un simulador de memoria virtual. El
cual deberá permitir crear procesos de un
tamaño indicado planificados.
• Lo primero que se realiza es la configuración
del administrador de memoria. Tamaño de la
memoria y tamaño de los segmentos. Se
deberá realizar una carga de procesos
estáticos para obtener un mapa de memoria.
Actividad
• Se deberá indicar el tipo de estrategia de
asignación de memoria, si se utiliza memoria
virtual o no (se utilizará FIFO como algoritmo
de descarga de páginas).
• El usuario deberá introducir los procesos que
quieren que se ejecuten y el sistema devolverá
la asignación de los bloques de memoria
respectivos.
Base límite
• El registro base y el registro límite pueden
servir para localizar direcciones de memoria.
• El registro base sirve como referencia para
ubicar una dirección en particular y el registro
límite
ayuda
a
determinar
si
el
desplazamiento de una dirección está por
encima del área asignada. Este mecanismo
sirve de protección para la memoria.
Segmentación
• Un método de asignación de memoria es la manera
mediante la cual el Sistema Operativo lleva el control
de la memoria tratando de que sea lo más eficiente
posible. Los métodos de asignación más comunes
son:
• Segmentación: Este método consiste en la asignación
de bloques de memoria de tamaño variable, llamados
segmentos. El tamaño de cada segmento será el
requerido según la petición, por ejemplo el tamaño del
proceso a cargar.
Métodos de asignación de memoria
• El tamaño máximo para un segmento estará
determinado por la capacidad de direccionamiento del
hardware de la computadora, esto es, de cuantos bits
se dispone para almacenar una dirección.
• El acceso a cada elemento individual en la memoria
se hace mediante una dirección de memoria que se
integra por dos elementos: una dirección de segmento
y una de desplazamiento.
Segmentación
• La combinación (suma) de la dirección de
segmento y la de desplazamiento generan la
dirección de memoria absoluta a acceder.
• Dado que en cada proceso se manejan
direcciones lógicas, el sistema operativo debe
obtener una dirección lógica. El sistema
operativo debe también asegurarse de que
cada dirección lógica esté dentro del rango de
direcciones empleado por el proceso.
Direccionamiento DOS
• MS-DOS (Segmentación)
• 8086 (16 Bits) 220=1,048,576 = 1MB.
• 80286 (16 Bits) Puede funcionar de alguno
de los 2 modos:
• Modo real = 8086
• Modo protegido:
– Para cada programa se implementa una tabla de
descriptores.
Direccionamiento DOS
• Modo protegido
– Capacidad de direccionamiento. 224 = 16,777,216 =
16MB
• Windows (Segmentación o Paginación)
• 80386 (32 Bits), 486, Pentium
– Capacidad
de
direccionamiento.
4,294,967,296 = 4GB
232
=
Segmentación en DOS
• Si un programa trata de asignar un bloque de
memoria de cierto tamaño, DOS busca un
bloque apropiado, si lo encuentra, se modifica
para que pertenezca al proceso solicitado.
• Si el bloque es demasiado grande, DOS divide
en un bloque asignado y un nuevo bloque libre.
Segmentación DOS
• Cuando un programa libera un bloque de
memoria, MS-DOS lo modifica para indicar que
está disponible.
• Cuando un programa reduce la cantidad de
memoria que necesita, MS-DOS crea un nuevo
bloque de control de memoria para la memoria
liberada.
Tipos de segmentos
• Segmentos de datos: sólo se puede leer y escribir,
pero no se puede ejecutar código de programa.
• Segmento de código: se puede ejecutar código pero
no puede leer ni escribir.
• Segmento del sistema: describe diferentes tipos de
segmentos que todos ellos sirven para la gestión del
modo protegido.
Paginación
• Consiste en considerar el espacio de
direcciones lógicas de cada proceso como un
conjunto de bloques de tamaño consistente
llamados paginas. Cada dirección lógica
manejada para un proceso estará conformada
por un par de valores [pagina: desplazamiento].
Implementación de mecanismos de
paginación
• La tabla de paginas se implementa completamente en
hardware (ventaja: se obtiene una alta velocidad de
acceso a memoria. Desventaja: resulta problemática
cuando la tabla de páginas debe ser grande).
• Implementar la tabla de páginas en la memoria
principal (ventaja: la tabla de paginas puede crecer
según se requiera. Desventaja: la velocidad de
acceder a memoria es relativamente baja, dado que
cada referencia a memoria involucra 2 accesos.
Swap
• El swap es la forma en como se intercambia
una partición de memoria por otra.
Generalmente se utiliza en técnicas basadas
en paginación.
• Se ocupa de una administración adecuada del
sistema de archivos para permitir paginación.
Swap
• Un ejemplo claro de intercambio es la famosa
función de intercambio
int swap(int a, int b) {
int aux = a;
a = b;
b = aux;
}
Esquema de paginación Windows
• Windows '95 implementa memoria virtual
mediante un esquema paginado, tomando
como base la arquitectura de direccionamiento
del procesador Intel 80386 y posteriores.
• El algoritmo de carga/descarga de páginas
empleado es el LRU (Least Recently Used)
mediante el cual se descargan a disco las
páginas menos recientemente usadas.
Esquema de paginación Windows
• En el disco se genera un archivo de
intercambio que contendrá las paginas que se
vayan descargando.
• Cada página correspondiente a una aplicación
tiene asignado un manejador (Handler) a un
descriptor/paginador (PD) almacenado en ella.
Esquema de paginación Windows
• Un PD contiene las direcciones de las rutinas
utilizadas para la transferencia de páginas
entre la memoria física y el disco.
• Cuando se requiera cargar o descargar una
página, el paginador hará una llamada a la
función apropiada dependiendo del estado que
la página tenga en ese momento. Los posibles
estados de una página son los siguientes.
Esquema de paginación de Windows
• Virgen: significa que el contenido de la página
no se ha modificado durante su tiempo de vida.
Por ejemplo, las paginas de código EXE por lo
general permanecen vírgenes.
• Corruptas: significa que el contenido de la
página se ha modificado al menos una vez
desde que se creó. Por ejemplo las páginas de
datos.
Esquema de paginación de Windows
• Limpia: significa que el contenido de la página
corrupta no fue modificado desde la última vez
que se cargó.
• Sucia: el contenido de una página corrupta fue
modificado desde la última vez que se cargó
(por lo que será necesario "guardarlo"
nuevamente en el archivo de intercambio).
Esquema de paginación de Windows
• Los nombres y tarea que realizará cada una de
las funciones PD son:
•
•
•
•
•
•
Pd_virgin: cargar pagina virgen.
Pd_taintedin: cargar pagina corrupta.
Pd_cleanout: descargar pagina limpia.
Pd_dirtyout: descargar pagina sucia.
Pd_virginfree: liberar pagina virgen.
Pd_taintedfree: liberar pagina corrupta.
Segmentación Paginada
• Algunos sistemas operativos como Multics y la Serie
370 de IBM combinan las técnicas de segmentación y
paginación para una mejora de los procesos.
• El proceso es el siguiente:
• Se hace la solicitud de acceso por medio de una
dirección "V" la cual contiene los campos Segmento,
Página y Desplazamiento.
Segmentación/Paginación
• Con el campo Segmento, lo que se trata es de
acceder a una Tabla de segmentos, cada
campo de dicha tabla apunta directamente a la
tabla de páginas asignada para ese segmento
conteniendo una dirección que será sumada a
una dirección en la Tabla Asociativa para por
fin formar una dirección real con el
desplazamiento de "V".
Administración de Memoria en SO
Móviles
• Symbian y algunos otros sistemas operativos
empotrados manejan el concepto de “executein-place” para indicar que los programas no
tienen que ser relocalizados ya que se pueden
ejecutar de donde se encuentren, ¿cómo es
posible esto?
Administración de Memoria en SO
Móviles
• Los sistemas operativos móviles en muchas
ocasiones tienen limitación en cuanto al
tamaño de los procesos.
• Generalmente los sistemas operativos en
dispositivos móviles son multitarea (aunque
sólo hay un proceso a la vez) y de tiempo real
(deben responder a eventos de manera
inmediata, por ejemplo: recibir una llamada).
Administración de Memoria en SO
Móviles
• La mayoría de la memoria generalmente se
encuentra en áreas de memoria no persistente,
pero poco a poco esta tendencia está
cambiando.
• La gran mayoría de los kernels son del tipo
nanokernel, en donde en el espacio del usuario
corren diversos microkernels encargados de
diversas funciones.
Administración de Memoria en SO
Móviles
• Los sistemas operativos para móviles
generalmente no cuentan con memoria virtual
por los altos costos de implementarla.
• Generalmente los microprocesadores no tienen
MMU (Memory Managment Unit) pero si la
tienen, los sistemas operativos tratarán de
utilizarla. Por lo que SO como Symbian y
Windows CE pueden utilizar paginación.
Administración de Memoria en SO
Móviles
• La mayoría de los SO móviles permiten el uso
de DMA (Direct Memory Acces, Acceso Directo
a Memoria).
• El sistema de memoria secundaria (Sistema de
Archivos) está muy ligado al de memoria
principal llegándose a confundir.
Mapa de Memoria
• El mapa de memoria es la forma en como
está distribuida las particiones de memoria
de un sistema operativo.
• El mapa de memoria ubica áreas de
asignación a semejanza de un plano en
donde se tienen países, estados, etc.
Mapa de memoria
• El mapa de memoria va a depender del sistema
operativo y de la arquitectura de hardware del
sistema de cómputo.
• El mapa de memoria puede ser totalmente
independiente entre diferentes sistemas
operativos que corren sobre la misma
arquitectura.
Memoria expandida
• Es un tipo especial de memoria paginada en
la cual se puede obtener acceso a más
memoria que la que el podía direccionar (640
KB), por lo que se accedería el rango de 640
KB a 1 MB que está orientado a drivers de
controladores en memoria ROM.
• Desde el 80386 los micros pueden utilizar
memoria expandida sin ningún problema.
Memoria extendida
• La memoria extendida es aquella que sobre
pasa 1 MB de memoria RAM y que es
accesible en procesadores 80286 y superiores.
• Este tipo de memoria DOS no la maneja de
manera nativa. Windows la maneja sin
necesidad de algún controlador especial.
Mapa de Memoria DOS/Win 16
Tipos de Datos en Windows
• BOOL (objeto de 32 bits para almacenar un solo valor lógico)
• HANDLE
• DWORD (entero no señalado de 32 bits)
• LPSECURITY_ATTRIBUTE
• LPTSTR (definido como TCHAR *)
• LPCTSTR (definido como const TCHAR *)
(Unicode: TCHAR puede ser char de 1 byte ó 2-bytes wchar_t)
Tipos de Datos en Unix
• Los tipos de datos son dependientes de la
arquitectura de hardware.
• En general esos tamaños dependen de la
longitud
de
palabra
de
los
microprocesadores. Para micros IA64, se
tendría como longitud 8 bytes para el entero,
un long es el doble del entero, un short es la
mitad de un entero. Generalmente los
flotantes se manejan utilizando el formato de
la IEEE, hay de 32 y 64 bits.
Memory
Memory
Memory
Memory
Memory
Memory Utilization
Paging
Paging Algorithm
Paging
Paging
Paging
Paging vs Segmentation
Memory Partitions
Memory Hierarchy
Computer Memory Space
OS Memory Space
Memory
Referencias
• Tutorial de Sistemas Operativos 2. Instituto
Tecnológico
de
la
Paz.
http://sistemas.itlp.edu.mx/tutoriales/sistemasop
erativos2/ [agosto 2007]
• Tanebaum, A., Woodhull, A. (1997) Sistemas
Operativos. Diseño e Implementación. México,
Prentice Hall. ISBN: 970-17-0165-8.
Referencias
• Windows Operating System Internals - by David
A. Solomon and Mark E. Russinovich with
Andreas Polze
Questions?