En un dispositivo sin sistema operativo, el programa que ejecutemos tendrá toda la CPU y memoria para sí mismo. Cuando entran más programas en juego y se ejecutan “simultáneamente”, es necesario encontrar un modo de que todos ellos puedan estar en RAM a la vez sin interferir entre sí.

A partir de esta necesidad surge el concepto de Espacio de direcciones (Address Space).

Espacio de direcciones

#

El espacio de direcciones es una abstracción que se crea de cara a un proceso específico y que representa su visión (punto de vista) de la memoria del sistema. Esto implica que un proceso no necesariamente tiene que poder ver o acceder a todas las direcciones de memoria reales del sistema.

El espacio de direcciones de un proceso normalmente tiene la siguiente forma. Está formado por la zona de código y datos (estáticos, normalmente Read-Only), y la zona de Stack (creciente hacia direcciones bajas, la gestiona el compilador de forma implícita), y de Heap (creciente hacia direcciones altas, la gestiona el programador de forma explícita).

Este es el espacio de direcciones de un proceso, ahora necesitamos tener esto, repetido, para todos los procesos del sistema.

Objetivo

#

El objetivo que tenemos es encontrar un modo de construir, sobre toda la memoria física, un espacio de direcciones privado para cada uno de los procesos del sistema. Los tres puntos a tener en cuenta a la hora de crear esto son:

• Transparencia: El SO debería implementar esta abstracción de forma que sea totalmente transparente hacia el proceso, y que este crea que toda la memoria del sistema le pertenece (Un programador no debería tener que preocuparse sobre cómo afecta la implementación de dicha abstracción a su programa.).
• Eficiencia: El SO debería hacer que dicha abstracción funcionase lo más rápido posible y usase estructuras de datos que tomasen el menor espacio en memoria necesario.
• Protección: El SO debería ser capaz de proteger a los procesos entre sí, uno de otro, y de protegerse a sí mismo frente a los procesos.

API de memoria

#

La forma que tiene el programador de interactuar con esta abstracción del sistema es principalmente a través de dos funciones (no syscalls): malloc() y free(). Estas funciones gestionan únicamente el heap.

• malloc(): Permite solicitar una cantidad específica de bytes contiguos de memoria en el heap. Devuelve la dirección de memoria en la que se ubican esos bytes, o NULL si algo sale mal.
• free(): Una vez hemos usado el espacio que habíamos reservado con malloc(), tenemos que liberarlo. free() toma un puntero del tipo que sea y libera su memoria. El programador no necesita especificar cuántos bytes se deben liberar porque al reservar memoria con malloc() se reservan unos bytes de más y se guardan metadatos.
  • Al terminar un proceso, el SO libera todos sus recursos, así que para un programa corto no es un gran problema olvidarnos de hacer free(), pero si el programa es largo (como un juego), se irá agotando la memoria disponible poco a poco hasta que el rendimiento caiga en picado cuando no quede más.

Traducción de direcciones

#

El mecanismo usado para dicha abstracción se conoce como Address Translation (Traducción de direcciones). Consiste en lo siguiente:

• El hardware dispone de memoria RAM. Las direcciones de la RAM física se conocen como direcciones físicas, y la memoria en sí, como memoria física.
• El SO se encarga de abstraer la RAM física, dando a cada proceso una memoria virtual.
• Con cada acceso a memoria de un proceso, el SO (Y el hardware, en conjunto, mediante un componente denominado MMU o Memory Management Unit) traducen la dirección de memoria virtual a la dirección física (real) en la que el dato o instrucción están almacenados.

Definido el concepto, hay varias métodos para elegir cómo mapeamos la memoria virtual a su correspondiente física.

Mecanismos de traducción

#

Base & Bounds

#

Es el más básico, también se conoce como “dynamic relocation”.

• La CPU debe tener dos registros físicos dedicados, llamados base y bound.
• Cuando se compila y ejecuta un proceso, desde su punto de vista, la primera instrucción está en la dirección (virtual) \(\text{0x0}\).
• Antes de ejecutarlo, el SO ha decidido en qué posición en memoria física almacenar el proceso, p.ej, \(\text{0x12300000}\), entonces mete \(\text{0x12300000}\) en el registro base.

A partir de aquí, cada dirección física se calcula como:

P.ej, si un programa intenta leer el dato en \(\text{0x15}\), el sistema hará el siguiente cálculo:

Y el programa accederá al dato almacenado en la dirección real \(\text{0x12300015}\), pero creyendo haber accedido a la \(\text{0x15}\), ahí el punto de transparencia.

Por otro lado, respecto a la seguridad, se usa el registro bound. Este registro simplemente sirve para asegurarse de que todo acceso a memoria debe estar en el rango virtual \([\text{0}, \text{Bound})\). Si un programa intenta acceder a memoria fuera de ese rango virtual, se producirá una excepción (SegFault, más adelante se verá el origen del nombre) y posiblemente el SO mate el proceso.

Además, cada vez que se hace un context switch a otro proceso, será necesario que el SO guarde los registros base y bound del proceso anterior, y restaure los del siguiente.

Problemas

#

Al compilar un programa, su tamaño es conocido, sabemos cuánto ocupan en total datos e instrucciones, pero no sabemos cuánta memoria el Stack o Heap van a necesitar. Esto significa que no podemos saber con exactitud cuánto espacio total reservar para el programa cuando lo cargamos a memoria, conocemos un mínimo (Datos+Instrucciones), pero solamente podemos estimar lo que ocupa el programa en total (Datos+Instrucciones+Stack+Heap).

Esto significa que tenemos que reservar memoria a ciegas, lo que puede llevar a dos situaciones:

• Se reserva de más: Esto hace que el “espacio vacío” entre stack y heap mostrado en la primera imagen sea demasiado grande, desperdiciando memoria porque ningún otro proceso puede usarla, lo que se conoce como fragmentación interna.
• Se reserva de menos: Si el SO determina que debe hacer más grande el espacio de un proceso, puede aumentar el registro bounds. El problema es que teniendo en cuenta que bajo este modelo toda la memoria de un proceso debe ser contigua, si justo tras la memoria física del proceso a agrandar hay memoria reservada de otro proceso distinto, el sistema no podrá agrandar el registro bounds porque entraría en la memoria del otro. Esto obligaría al sistema a mover todo el bloque de memoria del primer proceso a un lugar con más espacio, lo que resultaría extremadamente lento.

En un intento de solucionar algunos de estos problemas, se desarrolla el mecanismo de Segmentación, una generalización de Base & Bounds.

Segmentación

#

En lugar de tener un par de registros base y bound por proceso, por qué no tenerlos por segmento en memoria? Aquí asumimos que un segmento es una sección contigua de memoria de una longitud dada.

En el espacio de direcciones de un proceso había 3 segmentos: datos globales y código, heap y stack. Si dividimos dicho espacio en 3 partes, tendríamos 3 trozos pequeños y podríamos meterlos en más sitios, evitando además el gran espacio desperdiciado que se formaba entre heap y stack. Para poder soportar esto es necesario contar con una estructura de datos por proceso que guarde registros base y bounds de código, stack y heap.

Cuando un proceso intente acceder a memoria que no entre dentro de ninguno de los 3 rangos reservados, se producirá una excepción llamada Segmentation Fault (o error de segmentación), y el SO muy posiblemente matará el proceso. Este nombre (Segfault) sigue usándose a día de hoy en sistemas modernos para definir un acceso a memoria no permitido (fuera de rango) incluso aunque ahora ya no se use la segmentación.

Por ejemplo, este código producirá un segfault (aunque, de nuevo, los sistemas ya no usan segmentación, pero el nombre se ha quedado por motivos históricos):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

$ cat cosa.c      
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void){
    char* string1 = "patata"; // string1 = Origen: puntero a char, string "patata"

    // Intentamos copiar datos en una zona prohibida (0x0). (El área de código no siempre empieza en 0x0)
    strcpy(NULL, string1); // Se intenta copiar string1 a la dirección 0x0.

    // Si hay segfault, esto no se ejecutará.
    printf("El programa ha funcionado bien!\n");
    return 0;
}

$ gcc cosa.c -o cosa
$ ./cosa 
[1]    87372 segmentation fault (core dumped)  ./cosa

Qué segmento usar?

#

Ahora que tenemos 3 segmentos por proceso, cómo sabe el SO si queremos acceder a datos, heap o stack? Para determinarlo hay varias formas:

• Forma explícita: De los bits usados para representar la dirección de memoria, se toman los (p.ej, 2) superiores, y según la combinación de dichos bits se determina si son datos (p.ej 00), heap (01) o stack (10). El resto de bits será el offset.
• Forma implícita: El SO lo determina en función del contexto. Si la dirección efectiva parte del PC, entonces serán datos/código (Un fetch); si está formada a partir del Stack Pointer, entonces será stack, y por descarte, si no será heap.

Stack, Crecimiento negativo

#

Hay un pequeño problema con el modelo creado hasta ahora: el stack crece hacia abajo (direcciones menores). Esto significa que no podemos calcular sus direcciones igual que con el heap o código.

Para solucionar esto, necesitamos añadir otro dato más a nuestra estructura de datos que, para cada segmento, almacene si este crece hacia arriba o crece hacia abajo.

En este caso hay que tener en cuenta lo siguiente:

• El registro base apunta a la base del stack (dirección más alta).
• El registro bound contiene el tamaño del segmento del stack.
• El offset virtual es un número positivo que empieza a contar desde la dirección más baja del segmento.

Cuando un segmento crezca hacia abajo, como el stack, el sistema hará lo siguiente para calcular la dirección efectiva:

• Calcula el offset negativo: \(\text{Offset Negativo = Offset Virtual − Tamaño Máximo Segmento}\)
• Calcula la dirección física: \(\text{Dir. Física = Base + Offset Negativo}\)
• Para que el acceso sea válido, debe cumplirse que \(|\text{Offset Negativo}|\le\text{Bound}\), si no, da Segfault.

Bits de protección

#

Una de las formas de optimizar el uso de memoria es que varios procesos compartan código (o al menos ciertos segmentos). Para evitar que dichos procesos interfieran entre sí, es necesario determinar qué puede hacer un proceso sobre cada segmento específico: Puede modificar sus datos, o sólo puede leerlos? Esto no solo interesa al compartir código, sino que también es interesante para evitar que un programa modifique por error (o intencionadamente) su propio código mientras se ejecuta.

Para esto puede definirse, por ejemplo, un protection bit, que determine los permisos de los procesos sobre un segmento, diferenciando, p.ej, entre Read-Execute (instrucciones) o Read-Write (datos).

A la hora de comprobar un acceso a memoria, el SO aquí también tendría que comprobar los permisos sobre el segmento al que se accede.

Problemas

#

Con la segmentación se ha solucionado el problema de fragmentación interna que tenía Base & Bounds, pero se mantiene el otro problema, y ahora triplicado: Tenemos 3 trozos de memoria, dispersos por ahí, y de tamaño variable. Esto llevará a que en algún punto el sistema necesite un chunk de memoria de un tamaño determinado pero no pueda encontrarlo porque todo lo que haya sean pequeños trozos en memoria sueltos. Este problema de que haya huecos libres entre los segmentos de memoria reservada para procesos se conoce como fragmentación externa.

A esto se proponen soluciones como la Compactación: Cada cierto tiempo, el SO toma todos los segmentos de memoria de todos los procesos y los va copiando de tal forma que queden todos contiguos para dejar un único hueco grande sobrante al final. Aunque soluciona el problema, es bastante ineficiente (requiere copiar la memoria de muchos de los procesos)

Gestión de memoria libre

#

Como la segmentación va dejando huecos en memoria, hay que ver qué hacemos o cómo gestionamos dichos huecos. La forma estándar es unificar el mecanismo de Splitting & Coalescing junto con una de las políticas para reservar espacio.

• Splitting y Coalescing: Cuando un programa solicita memoria con malloc(), la función se encarga de buscar un espacio libre que tenga al menos el tamaño solicitado, y una vez la devuelve, divide ese espacio en 2: Los bytes que solicitamos, y el espacio restante (De ahí el Splitting). Cuando hacemos free() para liberarla, si el espacio recién liberado está al lado (encima o debajo) de otro espacio vacío de memoria, la función también se encarga de unir esos dos espacios de memoria en su Free-List para formar uno único más grande, esto es el Coalescing.

• Políticas: Son el algoritmo que usamos para determinar qué hueco coger de entre todos los disponibles (que tienen tamaño igual o mayor al pedido). Algunos son:

  • Best Fit: De entre todos los huecos posibles, se elige el más pequeño.
  • Worst Fit: De entre todos los huecos posibles, se elige el más grande.
  • First Fit: Se elige el primer hueco que se encuentra.
  • Next Fit: Como First Fit pero cada vez se parte desde el elemento que se estaba mirando la última vez, con el fin de no sobrecargar la zona inicial de la lista.
  • Buddy Allocation: Cuando se solicita una cantidad específica de memoria, esta se redondea a la siguiente potencia de 2. Si tenemos 64kB de memoria y necesitamos 7kB, primero buscaremos 64kB, luego 32kB, 16kB, y finalmente 8kB libres, que serán los que reservaremos. La gracia de este sistema es que cuando se liberan esos 8kB, el algoritmo comprueba si su pareja (con la que suma 16kB) está libre, y si es así, se unen (Coalescing), luego se hace lo mismo con esos 16kB que acaban de unirse, luego con 32kB, y así hasta que una pareja no esté libre. Problema: Vuelve la fragmentación interna (perdemos 1kB) a cambio de poder hacer un coalescing muy rápido.

Para intentar solucionar todos los problemas que tiene la segmentación, se propone un modelo diferente, la paginación.