Pourquoi ce programme alloue 8 pages mais ne peut contenir que 2048 nœuds dont la taille est de 8 octets?

Question

Un nœud est défini comme suit:

struct node{ 
     int value; 
     struct node *next; 
    }; 

En utilisant sizeof(struct node) j'apprendre qu'un noeud est de 8 octets (en xv6). Donc, j'utilise malloc pour allouer de l'espace mémoire pour stocker certains nœuds. Une seule page en xv6 est 4096 octets, si j'ai 8 pages, je peux stocker 4096 tels nœuds. Cependant, ce n'est pas ce qui se passe, après que je malloc 2048 de tels nœuds, si un autre malloc, plus de pages sont allouées pour le processus en cours, pourquoi est-ce?

// Now display how many pages are allocated to the process 
    // Suppose there is a system call named memcount(), it is given by 
    // my professor, I wouldn't think there's any problem with that 
    // 
    memcount(); // which prints 3, meaning that initially, without 
       // allocaing anything, 3 pages = 12288 bytes of memory allocated 

    for(i = 0; i < 2048; ++i){ 
     struct node *nd = (struct node *)malloc(sizeof(struct node)); 
    } 

    memcount(); // which prints 11, so 8 more pages are allocated 

    // If we allocated 1 more node 
    struct node *nd = (struct node *)malloc(sizeof(struct node)); 
    memcount(); // which prints 19, another 8 pages are allocated 

C'est là où je suis si confus, ne devrait pas être là beaucoup d'espace laissé dans les 8 premières pages? Puisque la taille d'un seul nœud est de seulement 8 octets, pourquoi y a-t-il plus de pages allouées au processus?

Answer 1

La question a déjà répondu dans le commentaire: malloc() besoin d'espace pour stocker, comment la mémoire est utilisée. Le gestionnaire de mémoire voit le tas comme un seul grand tableau d'octets (car la RAM est un grand tableau dans la plupart des modèles de mémoire). (Il existe également d'autres modèles de mémoire ou le gestionnaire de mémoire peut stocker des données dans des pages supplémentaires, mais pour simplifier, nous ignorons ces cas)

À titre d'exemple, nous pourrions penser au système, où les 4 premiers octets utilisés comme pointeur (p0), où les prochains blocs valides commencent et les 4 octets suivants pour une variable (size_t, s0) combien d'octets sont utilisés pour ce bloc (nous avons besoin de 2 variables pour détecter quand un bloc entre 2 blocs est libéré). Le bloc suivant ont également un pointeur (p1) à côté (suivant du suivant) bloc et une variable de la taille du bloc (s1)

Après cet en-tête sont les données que vous pouvez utiliser, malloc() retour d'un pointeur sur le premier octet après cet en-tête. La variable s0 va stocker combien d'octets vous avez demandé. Après une nouvelle malloc(), un nouvel en-tête sera créé après le premier bloc et le p0 pointera vers cet en-tête:

Address: 0x10 0x14 0x18 0x1B 0x20 0x24 0x28 ... 
Name:  p0  s0  value next p1  s1  value... 
Value:  0x20 8  ??  0x28 0  8  ?? 

Voici la situation après que vous alloc 2 blocs, p1 et s1 sont variables pour l'en-tête du deuxième bloc. Vous pouvez uniquement utiliser la variable next et value. Le pointeur malloc() renvoyé est 0x18 et 0x28. Pour éviter d'utiliser la moitié de l'espace pour le gestionnaire de mémoire, vous pouvez affecter un plus grand tableau en une seule étape. Vous pouvez utiliser un struct comme ceci:

struct Node_T 
    { 
    int values[512]; 
    size_t usedValues; 
    struct Node_T *next; 
    } 

Ensuite, vous devez 4 * 4 = 16 octets total des coûts indirects (y compris les frais généraux de l'memoryhandler, et a assumé les memoryhandler ont besoin de 8 octets en-tête par bloc et int, pointeurs et size_t sont 4 octets). Mais vous avez besoin d'une copie supplémentaire ou d'un déplacement supplémentaire lorsque vous supprimez ou ajoutez une valeur entre d'autres valeurs. Malloc (X) utilise plus de X octets de mémoire.