Sistemas Operativos - Apuntes de Clases 11 Paginación y Segmentación

Sistemas Operativos
Paginación y Segmentación

Clase 11
Matías Alejo García

Atención: Estos apuntes deben ser usados como referencia de los temas vistos en clase. No son, ni intentan ser un texto de estudio. El contenido de estos apuntes no alcanza para la aprobación de la materia, ya que sólo enumeran los temas vistos.
Para estudiar la materia, por favor referirse a la bibliografía del curso.

11.1 Paginación

Es una forma de disminuir la fragmentación externa.
Además, hasta ahora el swapping debía hacerse con los procesos completos. Con paginación, un proceso puede ser llevado parcialmente al disco. Regla del 90/10: Un proceso ocupa el 90% del tiempo accediendo a 10% de su memoria.
Es usada por casi todas las arquitecturas de hardware y por los SO.
Las direcciones lógicas no se disponen continuamente en la memoria física.
Consiste en dividir la memoria física en secciones de memoria, llamadas marcos, y dividir la memoria lógica en secciones del mismo tamaño, llamadas páginas.
El tamaño es fijo, y determinado por el hardware (4kb, 2Mb y 4Mb en i386)
Cuando se crea un proceso, se le asigna el número de páginas y frames necesarios.
Las direcciones lógicas del proceso son un rango continuo de números, pero estas se mapean de forma (probablemente) discontinua en memoria física.
Cualquier marco puede ser asignado a cualquier página.
Se elimina la fragmentación externa.
Se acota la fragmentación interna (~1/2 página por proceso). Ejemplos extremos.
Grafico de páginas y marcos: Asignaciones no continuas.

11.2 Hardware de Paginación

Cómo hacemos para mapear un continuo de direcciones lógicas a la memoria física?

Los procesos usan direcciones continuas de memoria: direcciones virtuales ó lógicas. Van de 0 al tamaño del proceso.
Esta dirección virtual definirá una página y el offset en la página.
El SO pedirá al hardware que asigne un marco a las páginas usadas.
Una tabla en la MMU asocia las páginas con los marcos.
Gráfico de traducción dirección lógica -> Tabla -> dirección física. Sección de offset no traducida. Tamaño de la sección de offset, por qué? 2^N
Es una forma (compleja) de relocación dinámica.
Es transparente al proceso.
El SO es responsable de mantener la Tabla de Páginas.
Tamaño típicos de página: entre 512 y 8192 bytes. (Definida por el hardware). Siempre 2^N. (Ejemplo)

11.3 Ejemplos de Paginación

Datos: RAM: 256bytes. Tamaño página: 16bytes.Direccionamiento por byte.

La dirección física tiene 8 bits (suficientes para mapear 256bytes planos).

16 marcos de 16 bytes.

4 bits de offset para direcciones 16 bytes dentro de cada página
4 bits para seleccionar la página: entre 16 páginas.
4+4 = 8 bits de dirección lógica.

dado un proceso de 64bytes -> 4 páginas -> la tabla tiene 4 entradas.
p: los '4' más significativos. 'd' los menos.
dada un dirección: 0x18 (24) -> 0x1 es la página, y 0x8 es el offset.
dada un dirección: 0x2A (42) -> 0x2 es la página, y 0xA es el offset.

Datos: RAM: 512bytes. Tamaño página: 16bytes.Direccionamiento por word (2 bytes).

dirección física: 9 bytes.
32 marcos de 16 bytes.
5bits para seleccionar la página
3 bits para el offset. (porque son 16bytes = 8 words por página)
5+3 = 8 bits de dirección lógica.
'p': los 5 más significativos, 'n' los 3 menos.
dada una dirección: 0xD (13d 1101b)-> p=1b-> 1d , n=101b-> 5d

Cada cambio de contexto es necesario guardar la Tabla de Página en el PCB y cargar la del nuevo proceso. La página puede estar guardada de dos formas: Registros o Memoria. En el primer caso, es necesario guardar toda la tabla desde los registros a la memoria en el PCB para cambiar de proceso y restaurar los registros desde el PCB del nuevo proceso. En el segundo caso, basta con tener todas las tablas en memoria y guardar un puntero al comienzo de cada tabla en cada PCB.
Dónde se guarda la tabla de páginas. Dos opciones:

registros

mas rápidos
si mucha RAM -> la tabla tendrá muchas entradas y no se puede ponerla en registos
cada cambio de contexto hay que modificar el valor de todos los registros

memoria

un registro (CR3 en i386) apunta a la tabla de páginas
acceso mas lento que registeos: dos accesos a memoria por cada acceso real.
pero: no hay problemas de espacios
y para cambiar de contexto solo es necesario cambiar un registro, el que apunta a la tabla. Todas las tablas, de todos los procesos, de guardan al mismo tiempo en memoria, y sólo se cambia el registro puntero.

Otros datos en la tabla:

Presente?: Si esta en la RAM o en swap.
User/Kernel. Si se puede acceder a modo usuario.
Ejecutable/Data. Si es ejecutable o no la info que contiene.
Espacio libres para el SO: Contadores de referencias, Accesos, etc.

Estos campos están definidos por el hardware.

Recordar: El CPU trabaja entonces con direcciones lógicas, no físicas.
El caché de memoria esta implementado a nivel lógico, con direcciones lógicas.
La MMU posee un TLB para acelerar el proceso de traducción de direcciones.

11.4 TBL: Translation Look Aside Buffer

Para disminir el tiempo de acceso a memoria en sistemas que usan paginación y guardan las tablas en memoria.
Memoria asociativa (cache) que guarda las N últimas traducciones de dirección lógica a física.
Típicamente tiene de 2 a 2048 entradas.
Antes de acceder a la Tabla de páginas, el hardware se fija en el TBL, si la dir lógica está allí, también esta guardada la dir física a la que corresponde y se accede directamente. Si no esta allí, el hardware se fija en la Tabla de Páginas y luego en la memoria y luego se guarda el acceso en el TBL.
Como un cache, el probable que las memorias accedidas frecuentemente estén en el TBL y por lo tanto se accedan mas rápido.
Ver gráfico de implementación del TBL en el libro.
El tiempo de acceso es aprox: (ma +TBL) *p + (2*ma)*(1-p)

donde ma es el tiempo de acceso a una posición de memoria
TBL el tiempo de acceso de una entrada en el TBL (TBL en gral es << que ma).
p es la posibilidad que la dirección en cuestión esté en el TBL
examinar lo límites p->0 y p->1.

El TBL es válido para cada proceso. Las entradas en el TBL de un proceso no sirven a otro proceso...por qué?
Algunos SOs guardan el TBL en el PCB al hacer un cambio de contexto, y restauran el TBL del PCB del proceso nuevo.
Otros, simplemente invalidan el TBL, y empieza vacio al cambiar de contexto.

11.5 Compartir Memoria

Usar paginación nos permite compartir memoria entre procesos.
Podemos apuntar al mismo marco físico desde las Tablas de Páginas de diferentes procesos.
Asi por ejemplo:

La página número 2 del Proceso 1 puede apuntar al marco 10
y La página número 10 del Proceso 2 puede apuntar al marco 10.

En gral, se comparte el texto (código) de las librerías. Se marca esas páginas como sólo lectura.
Mejora la utilización de memoria, y también la velocidad con la que arrancan los programas.

11.6 Segmentación

Desde el punto de vista del usuario y los compiladores, un proceso esta 'naturalmente' dividido en secciones: texto, data, stack, heap.
Dando a cada una de estas secciones espacios de direccionamientos distintos, simplificamos la tarea del compilador, y mantenemos la división natural.
Es más fácil:

permitir al stack y al heap crecer dinámicamente.
compartir info entre programas.
proteger programas

11.7 Implementación de Segmentación

El hardware tiene que soportar protección de memoria por registros base/limite.
Las direcciones lógicas determinan el segmento y el offset dentro del segmento y al igual que en paginación, se divide la dirección en dos: una parte define el segmento y otra el offset.
El SO mantiene una tabla de segmentos: La tabla es propia de cada programa. Se guardan las direcciones base y límite del segmento y otra información como 'tipo de acceso'.
En paginación, los compiladores no tienen que saber si el sistema esta usando paginación o no, ya que siempre crean un continuo de direcciones lógicas. En segmentación, en cambio, los compiladores deben saber si tienen que generar direcciones utilizando segmentos diferentes, tienen que saber por ejemplo que parte de la dirección lógica define el segmento.
Al igual que en paginación, también se puede guardar la tabla de segmentos en registos o en memoria. Si es en memoria, existe un registro especial que indica dónde comienza la tabla de segmentos (STBR: Segment Table Base Register).
Si el SO esta diseñado para usar muchos segmentos (extraño), se debe proveer algún sistema similar a TBL para optimizar el acceso a la tabla de segmentos.
En segmentación, la división lógica de la memoria permite definir segmentos RO de texto y compartirlos entre diferentes programas. En paginación pura es mas complicado, ya que una misma página podría tener parte de texto y parte de data...
Lo mismo para con la protección. Es simple proteger segmentos, ya que tienen la dimensión exacta de lo que queremos proteger.
A diferencia de paginación:

Cada segmento ocupa un espació físico contiguo en memoria -> puede habar fragmentación externa.
Los segmentos son de longitud variable.

11.8 Segmentación con Paginación

Segmentación y paginación tiene tienen cada uno sus ventajas. Podemos combinarlas y obtener un sistema mejor.
Dos ejemplos: Multics e OS/2
Multics

18bit segmentos + 16bit offset. Alineación en words.
Si se usar segmenación pura: Segmentos de 16bits -> 64k x 2bytes -> Segmentos de 128kb -> habría mucha segmentación.
kw=kwords= 1024 words = 2048 bytes.
Se dividen los segmentos en páginas de 1K words.

-> 64kw/1kw -> 64 páginas por segmento -> 6 bits para identificar una página en un segmento.
El offset de una página es de 10 bits, porque 2^10=1024 -> suficiente para identificar cada word dentro de la página
Entonces, el offset del segmento de 16bits esta dividido en 6bits para la página y 10 bits para el offset dentro de la página.
La tabla de segmentos tiene una dirección base para la tabla de páginas, y una dirección base simplemente.
Tiene además un campo que indica el tamaño del segmento, y este se compara directamente con el offset de la dirección original. (Notar como se definen las páginas dentro de los segmentos).
Hay un registro general, que indica dónde comienza la tabla de segmentos.
ver figura 11.1

multics

Figura 11.1: Segmentación Paginada en Multics (ver referencias)

Finalmente, como podría haber 2^18 segmentos y la tabla sería muy grande, se pagina también la tabla de segmentos en 8bits+10 bits. (páginas de 1K)
Hay una TBL de 16 entradas.

Intel 386 y OS/2

Cada proceso puede tener 16K segmentos, 8K propios y 8K compartidos.
Cada segmentos tiene hasta 4Gb
Están paginados en marcos de 4Kb.
Hay dos tablas de segmentos, una global y compartidas por todos los procesos (GDT) y otra privada sólo para el proceso.
Las direcciones lógicas tiene 48 bits: 16 para el selector de segmento y 32 para el offset (4Gb por segmento).
El selector tiene 13 bits para definir el segmento (8k segmentos), 1 bits para definir si esta en la tabla pública o privada, y 2 bits para protección.
Hay 6 selectores, para usar en los programas.
El offset esta paginado en dos niveles: 10+10+12 bits.
Los marcos pueden estar en RAM o en la memoria Swap.
Ver figura 11.2.

i386

Figura 11.2: Segmentación Paginada en i386 (ver referencias)

Referencias

Esta clase está basada en "Operating Systems Concepts", 5ta Edición. Silberschatz & Galvin, ( Capitulos 8 y 9).
Apuntes de Clases del Prof. Andrew Faggs.

2003 (C)Matías Alejo García, os@matiu.com.ar, http://os.matiu.com.ar