为什么这个程序分配了8页，但只能容纳2048个8字节的节点？

Question

节点定义如下：

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

通过使用 sizeof(struct node) 我了解到一个节点是 8 个字节（在 xv6 中）。所以我使用 malloc 分配一些内存 space 来存储一些节点。 xv6中单个页面是4096字节，如果我有8个页面，我可以存储4096个这样的节点。然而，这不是正在发生的事情，在我 malloc 2048 个这样的节点之后，如果我 malloc 另一个，为当前进程分配更多页面，这是为什么？

    // 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

这就是我很困惑的地方，前8页不应该还有很多space吗？既然单个节点的大小只有8字节，为什么分配给进程的页数更多？

Answer 1

问题已经在评论中回答了：malloc()需要一些space来存储，Memory是如何使用的。

内存处理程序将堆视为单个大字节数组（因为 RAM 在大多数内存模型中都是一个大数组）。（还有其他内存模型或者内存管理器可能会在额外的页面中存储一些数据，但为了简单起见，我们忽略这种情况）

例如，我们可以考虑系统，其中前 4 个字节用作指针 (p0)，下一个有效块从此处开始，接下来的 4 个字节用于变量 (size_t, s0) 这个块使用了多少字节（我们需要 2 个变量来检测 2 个块之间的块何时被释放）。下一个块也有一个指向下一个（下一个的下一个）块的指针（p1）和一个块大小的变量（s1）

在此header之后是您可以使用的数据，malloc() return指向此header之后第一个字节的指针。变量 s0 将存储您请求的字节数。一个新的malloc()之后，第一个block之后会创建一个新的header，p0会指向这个header:

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

这里是你alloc 2块后的情况，p1和s1是第二个块的header的变量。您只能使用变量 next 和 value。 malloc() returned 的指针是 0x18 和 0x28.

为了避免将 space 的一半用于内存处理程序，您可以一步分配一个更大的数组。您可以像这样使用 struct：

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

那么你将需要 4*4 = 16 字节的总开销（包括内存处理程序的开销，并假设内存处理程序每个块需要 8 字节 header 和 int，指针和 size_t 是 4 个字节）。但是当你在其他值之间删除或添加一个值时，你需要额外的复制或移动开销。

为什么这个程序分配了8页，但只能容纳2048个8字节的节点？

Why does this program allocate 8 pages but can only fit in 2048 nodes whose size is 8 bytes?

c

operating-system

system

xv6