3

一个节点定义如下:

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

通过使用sizeof(struct node),我了解到一个节点是 8 个字节(在 xv6 中)。所以我使用malloc分配一些内存空间来存储一些节点。xv6 中单页是 4096 字节,如果我有 8 页,我可以存储 4096 个这样的节点。但是,这不是发生的事情,在我malloc2048 个这样的节点之后,如果我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页不应该有很多空间吗?既然单个节点的大小只有8个字节,为什么还要给进程分配更多的页呢?

4

1 回答 1

1

评论中已经回答了这个问题:malloc()需要一些空间来存储,如何使用内存。

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

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

在此标头之后是您可以使用的数据,malloc()返回指向此标头后第一个字节的指针。该变量s0将存储您请求的字节数。在一个 new 之后malloc(),会在第一个块之后创建一个新的头,并且 p0 将指向这个头:

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

这是分配 2 个块后的情况,p1并且s1是第二个块的标题的变量。您只能使用变量nextand valuemalloc()返回的指针是0x18and 0x28

为了避免为内存处理程序使用一半的空间,您可以一步分配一个更大的数组。你可以使用struct这样的:

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

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

于 2017-04-09T11:18:27.300 回答