Asignación de memoria del kernel (sistema de compañeros y sistema de losa)

Requisito previo: sistema de amigos 

Dos estrategias para administrar la memoria libre asignada a los procesos del kernel:

1. Sistema de amigos –

El sistema de asignación de amigos es un algoritmo en el que un bloque de memoria más grande se divide en partes pequeñas para satisfacer la solicitud. Este algoritmo se utiliza para dar el mejor ajuste. Las dos partes más pequeñas del bloque son del mismo tamaño y se llaman amigos. De la misma manera, uno de los dos amigos se dividirá en partes más pequeñas hasta que se cumpla la solicitud. El beneficio de esta técnica es que los dos amigos pueden combinarse para formar un bloque de mayor tamaño según la solicitud de memoria. 

Ejemplo: si se realiza la solicitud de 25 Kb, se asigna un bloque de 32 Kb de tamaño. 

Cuatro tipos de sistema de amigos: 

1. Sistema de compañeros binarios
2. Sistema de amigos de Fibonacci
3. Sistema de compañero ponderado
4. Sistema de compañeros terciario

¿Por qué sistema de amigos?  
Si el tamaño de la partición y el tamaño del proceso son diferentes, se produce una coincidencia deficiente y es posible que se use el espacio de manera ineficiente. 
Es fácil de implementar y eficiente entonces la asignación dinámica. 

Sistema de amigos binarios: 
el sistema de amigos mantiene una lista de bloques libres de cada tamaño (llamada lista libre), de modo que es fácil encontrar un bloque del tamaño deseado, si hay uno disponible. Si no hay disponible ningún bloque del tamaño solicitado, Allocate busca la primera lista no vacía de bloques de al menos el tamaño solicitado. En cualquier caso, se elimina un bloque de la lista libre. 

Ejemplo: suponga que el tamaño del segmento de memoria es inicialmente de 256 kb y el kernel solicita 25 kb de memoria. El segmento se divide inicialmente en dos amigos. Llamemos a A1 y A2 cada uno de 128kb de tamaño. Uno de estos amigos se divide en dos amigos de 64 kb, digamos B1 y B2. Pero la siguiente potencia más alta de 25 kb es 32 kb, por lo que B1 o B2 se dividen en dos amigos de 32 kb (C1 y C2) y, finalmente, uno de estos amigos se usa para satisfacer la solicitud de 25 kb. Un bloque dividido solo se puede fusionar con su bloque compañero único, que luego reforma el bloque más grande del que se separaron. 

Sistema de amigos de Fibonacci: 
este es el sistema en el que los bloques se dividen en tamaños que son números de Fibonacci. Satisface la siguiente relación: 

  Zi = Z(i-1)+Z(i-2)

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 144, 233, 377, 610. El cálculo de direcciones para los sistemas de compañeros binarios y ponderados es sencillo, pero el procedimiento original para el El sistema de amigos de Fibonacci estaba limitado a un número pequeño y fijo de tamaños de bloque o a un cálculo que requería mucho tiempo. 

ventajas – 

• En comparación con otras técnicas más simples, como la asignación dinámica, el sistema de memoria de compañeros tiene poca fragmentación externa.
• El sistema de asignación de memoria de compañeros se implementa con el uso de un árbol binario para representar bloques de memoria dividida utilizados o no utilizados.
• El sistema de compañeros es muy rápido para asignar o desasignar memoria.
• En los sistemas de compañeros, el costo de asignar y liberar un bloque de memoria es bajo en comparación con los algoritmos de mejor ajuste o primer ajuste.
• Otra ventaja es la fusión.
• El cálculo de direcciones es fácil.

¿Qué es coalescer?  
Se define como la rapidez con la que los amigos adyacentes se pueden combinar para formar segmentos más grandes, lo que se conoce como fusión. 
Por ejemplo, cuando el núcleo libera la unidad C1 que se le asignó, el sistema puede fusionar C1 y C2 en un segmento de 64 kb. Este segmento B1, a su vez, puede fusionarse con su compañero B2 para formar un segmento de 128 kb. En última instancia, podemos terminar con el segmento original de 256 kb. 

Inconveniente: 
el principal inconveniente del sistema de amigos es la fragmentación interna, ya que se adquiere un bloque de memoria más grande del que se requiere. Por ejemplo, si se realiza una solicitud de 36 kb, solo se puede satisfacer con un segmento de 64 kb y se desperdicia la memoria restante. 

2. Asignación de losa –

Una segunda estrategia para asignar memoria del kernel se conoce como asignación de slab. Elimina la fragmentación causada por asignaciones y desasignaciones. Este método se utiliza para retener la memoria asignada que contiene un objeto de datos de un determinado tipo para su reutilización en asignaciones posteriores de objetos del mismo tipo. En la asignación de losa, se preasignan fragmentos de memoria adecuados para adaptarse a objetos de datos de cierto tipo o tamaño. El caché no libera el espacio inmediatamente después del uso, aunque realiza un seguimiento de los datos que se requieren con frecuencia para que cada vez que se realice una solicitud, los datos lleguen muy rápido. Dos términos requeridos son:  

• Losa: una losa se compone de una o más páginas físicamente contiguas. La losa es el contenedor real de datos asociados con objetos del tipo específico del caché contenedor.
• Caché: la caché representa una pequeña cantidad de memoria muy rápida. Un caché consta de una o más losas. Hay un solo caché para cada estructura de datos de kernel única.

Ejemplo –  

• Un caché separado para una estructura de datos que representa descriptores de procesos
• Caché separada para objetos de archivo
• Caché separado para semáforos, etc.

Cada caché se llena con objetos que son instancias de la estructura de datos del kernel que representa el caché. Por ejemplo, la memoria caché que representa los semáforos almacena instancias de objetos de semáforo, la memoria caché que representa los descriptores de procesos almacena instancias de objetos de descriptores de procesos. 

Implementación: 
el algoritmo de asignación de losas utiliza cachés para almacenar objetos del núcleo. Cuando se crea una memoria caché, se asignan a la memoria caché una serie de objetos que inicialmente se marcan como libres. El número de objetos en el caché depende del tamaño de la losa asociada. 
Ejemplo: una losa de 12 kb (compuesta por tres páginas contiguas de 4 kb) podría almacenar seis objetos de 2 kb. Inicialmente, todos los objetos en el caché se marcan como libres. Cuando se necesita un nuevo objeto para una estructura de datos del núcleo, el asignador puede asignar cualquier objeto libre del caché para satisfacer la solicitud. El objeto asignado desde la memoria caché se marca como utilizado. 

En Linux, una losa puede estar en uno de tres estados posibles:  

1. Completo: todos los objetos en la losa se marcan como usados .
2. Vacío: todos los objetos en la losa se marcan como libres.
3. Parcial: la losa consta de ambos

El asignador de losas primero intenta satisfacer la solicitud con un objeto libre en una losa parcial. Si no existe, se asigna un objeto libre de una losa vacía. Si no hay bloques vacíos disponibles, se asigna un nuevo bloque de páginas físicas contiguas y se asigna a una memoria caché. 

Beneficios del asignador de losas: 

• No se desperdicia memoria debido a la fragmentación porque cada estructura de datos de kernel única tiene un caché asociado.
• La solicitud de memoria se puede satisfacer rápidamente.
• El esquema de asignación de losas es particularmente efectivo para administrar cuando los objetos se asignan o desasignan con frecuencia. El acto de asignar y liberar memoria puede ser un proceso lento. Sin embargo, los objetos se crean de antemano y, por lo tanto, se pueden asignar rápidamente desde la memoria caché. Cuando el kernel ha terminado con un objeto y lo libera, se marca como libre y regresa a su caché, lo que lo hace disponible de inmediato para una solicitud posterior del kernel.