Manual del estudiante de Ingeniería en Sistemas de UTN/Diseño e Implementación de Sistemas Operativos/El sistema compañero de alocación de memoria

La técnica de alocación de memoria conocida como sistema compañero divide la memoria en mitades, para intentar dar el mejor ajuste.

Implementación y consecuencias editar

Comparado con las técnicas de alocación, tales como la paginación, que utilizan los sistemas operativos actuales, el sistema compañero es simple de implementar, y no requiere una unidad administradora de memoria en hardware (MMU), por lo cual puede ser implementado por ejemplo en computadoras Intel 80286 y anteriores.

Además, comparada con otras técnicas simples tales como la alocación dinámica, el sistema compañero presenta poca fragmentación externa, y no requiere compactación de la memoria.

En contraste, presenta una cantidad moderada de fragmentación interna, ya que sólo se pueden asignar bloques de un tamaño de la forma  , siendo t la cantidad total de memoria administrada, y n un número natural.

Funcionamiento editar

El sistema compañero aloca memoria en potencias de 2, es decir, 2x, donde x es un entero. Por lo tanto, el programador deberá decidir, o escribir el código que obtenga el límite superior de x en función de la memoria física con la que cuente el sistema.

Una vez decidido el límite superior (que llamaremos u), el programador deberá decidir el límite inferior (que llamaremos l), es decir, el bloque de memoria más pequeño que pueda ser alocado. Este límite es necesario para minimizar el almacenamiento de los datos sobre la ocupación de cada bloque. Típicamente, este número es moderado (por ejemplo 2, de manera que la memoria sea alocada en 22 = 4K bloques), lo suficientemente pequeño para minimizar la fragmentación interna, pero lo suficientemente pequeño como para evitar espacio extra excesivo.

Ejemplo
en un sistema donde l = 6, lo cual resulta en bloques de 26 = 64K, y u = 10, lo cual resulta en un bloque de tamaño máximo de 210 = 1024K. A continuación se muestra un posible estado del sistema luego de varias solicitudes de memoria.
64K64K64K64K64K64K64K64K64K64K64K64K64K64K64K64K
t=01024K
t=1A-64K64K128K256K512K
t=2A-64K64KB-128K256K512K
t=3A-64KC-64KB-128K256K512K
t=4A-64KC-64KB-128KD-128K128K512K
t=5A-64K64KB-128KD-128K128K512K
t=6128KB-128KD-128K128K512K
t=7256KD-128K128K512K
t=81024K

Esta alocación pudo haber ocurrido de la siguiente forma:

  1. Programa A solicita 34K..64K
  2. Programa B solicita 66K..128K
  3. Programa C solicita 35K..64K
  4. Programa D solicita 67K..128K
  5. Programa C libera la memoria
  6. Programa A libera la memoria
  7. Programa B libera la memoria
  8. Programa D libera la memoria

Esto es lo que ocurre cuando se realiza una solicitud de memoria:

  • Si se solicita memoria
  1. Buscar una ranura de memoria de tamaño adecuado (el mínimo bloque 2k que es más grande que la memoria solicitada)
    1. Si se encuentra, se aloca para el programa
    2. Si no, se intenta crear una ranura adecuada de la siguiente manera:
      1. Dividir a la mitad una ranura libre de tamaño mayor que el solicitado
      2. Si se alcanzó el límite inferior, alocar esa cantidad de memoria
      3. Volver al paso 1 (buscar una ranura de memoria de tamaño adecuado)
      4. Si no, repetir el proceso hasta obtener una ranura del tamaño adecuado
  • Si se libera memoria
  1. Liberar el bloque de memoria
  2. Consultar si el vecino está libre
  3. Si lo está, combinar los dos y volver al paso 2. Repetir hasta alcanzar el límite superior (toda la memoria está libre) o hasta que se encuentre un vecino ocupado

Este método de liberación de memoria es bastante eficiente, dado que la compactación es realizada relativamente rápido, con el máximo número de compactaciones requeridas igual a  

Tipicamente, el sistema compañero es implementado mediante el uso de un árbol binario para representar los bloques ocupados o libres.

De todas formas, queda todavía el problema de la fragmentación interna. Como el sistema compañero se usa para la memoria del kernel, es esencial disminuir la fragmentación interna, para lo cual se utiliza el algoritmo slab allocation.

Algorithm editar

One possible version of the buddy allocation algorithm was described in detail by Donald Knuth in The Art of Computer Programming. This is a complicated process.