50％规则

Question

我正在编写一个程序来测试动态内存分配，以了解 50% 规则的适用情况。

该程序有 10,000 个指向动态分配的内存块的指针。它还有一个数组来存储每个块的大小。它应该：

1. 使用 malloc() 为 ptrList 的每个元素动态分配一块内存。这些块的大小应在 1 到 10,000 字节的范围内随机选择，并且块大小应存储在 sizeList 数组中。
2. 初始块分配后，程序应重复释放块并分配新块。这应该循环 100,000 次迭代。在每次迭代中，ptrList 中的索引被随机选择，该块被释放，然后替换为具有随机大小的新的动态分配的块。
3. 每 100 次迭代后，它应该打印出一行，显示迭代计数、近似堆大小（由任何块中包含的最高和最低内存地址之间的差异确定）以及指向的所有块的总大小通过ptrList。

我的程序编码如下：

#include <stdio.h>
#include <pthread.h>   /* for pthreads */
#include <stdlib.h>    /* for exit */

/** Number of memory blocks to allocate/deallocate. */
#define BLOCK_COUNT 10000

/** Number of free/malloc operations to perform */
#define TEST_LENGTH 100000

/** Maximum size of an allocated block. */
#define SIZE_LIMIT 10000

int main( int argc, char *argv[] ) {
  // Array of pointers to all blocks that have been allocated.
  char *ptrList[ BLOCK_COUNT ];

  // Array of sizes for each block, so we can know how much memory we're using.
  int sizeList[ BLOCK_COUNT ];

  // Insert your code here
  for (int j = 0; j < 1000; j++) {

      int minimum = 0;
      int maximum = 0;
      int total = 0, remainder = 0;

      for (int i = 0; i < BLOCK_COUNT; i++) {
          int size = (rand() % SIZE_LIMIT) + 1;
          ptrList[i] = malloc (size);
          sizeList[i] = size;
          total += size;
          int heapsize = (int)ptrList[i];

          if (i == 0) {
              maximum = heapsize;
              minimum = heapsize;
          }
          else {
              if (heapsize > maximum) {
                  maximum = heapsize;
              }
              if (heapsize < minimum) {
                  minimum = heapsize;
              }
          }
      }

      for (int i = 0; i < TEST_LENGTH; i++) {
          int index = rand() % BLOCK_COUNT;
          int size = (rand() % SIZE_LIMIT) + 1;
          free(ptrList[index]);
          total -= sizeList[index];
          ptrList[index] = malloc (size);
          sizeList[index] = size;
          total += sizeList[index];
          int heapsize = (int)ptrList[index];

          if (heapsize > maximum) {
              maximum = heapsize;
          }
          if (heapsize < minimum) {
              minimum = heapsize;
          }
      }

      if (j > 0) {
          remainder = j % 100;
      }

      if (remainder == 0 ) {
          //printf("%d", example);
          printf("%d %d %d\n", j, maximum - minimum, total);
      }

      for (int i = 0; i < BLOCK_COUNT; i++) {
          free(ptrList[i]);
      }

  }

  return 0;
}

我是否以正确的方式处理内存的分配/释放？在我使用 int j 实现 for 循环之前，我的程序已编译并运行（无输出）。它在我实现后挂起，所以也许有人可以帮助我解决那里的问题。

编辑： 50% 规则是所有块的总大小除以堆大小的近似值，通常约为 50%。

Answer 1

除了繁琐的代码（极其不必要的代码）之外，您还遇到了变量和循环的一些问题：您的 for (int i = 0; i < TEST_LENGTH; i++)... 循环，它实现了步骤 2规范是一个循环，在该循环中，每 100 步您应该打印当前统计信息。拥有外部 for (int j = 0; j < 1000; j++) 循环并测试 j%100 余数是无意义的。

要调试此类问题，请将 BLOCK_COUNT、TEST_LENGTH、SIZE_LIMIT 中的每个大数字去掉两个或三个零，将 j 循环限制更改为 10，然后添加 printf("j= ..." ...) 在 for (int j ...) { 之后，这样您就可以知道发生了什么。通过这些更改，您将看到：

  j=0 0 0
  0 556736 507760
  j=1 0 0
  j=2 0 0
  j=3 0 0
  ...

然后可以得出结论，您的程序似乎挂起，因为它正在慢慢地将 j 计数到 100，以达到 j%100 == 0。

现在我将提到两个需要删除的小问题，然后将提到您的程序的一个主要问题。

而不是

  int minimum = 0;
  int maximum = 0;
  ...
     if (i == 0) {
        maximum = heapsize;
        minimum = heapsize;
     }
     else {
       if (heapsize > maximum) {
          maximum = heapsize;
     }
     if (heapsize < minimum) {
          minimum = heapsize;
     }

写

  int minimum = MAX_INT;
  int maximum = 0;
  ...
     if (heapsize > maximum)
        maximum = heapsize;
     if (heapsize < minimum)
        minimum = heapsize;

（或者可能是 MAX_INT 的变体）和（如果您需要 j 和/或 remainder，但您不需要）而不是

  if (j > 0) {
      remainder = j % 100;
  }

  if (remainder == 0 ) {
     ...

写

  if (j>0 && j%100 == 0 ) {
     ...

一个主要问题对于您的程序：当您在第 2 部分中说 free(ptrList[index]); 时，您可能会释放占用当前最小或最大内存地址的项目。解决这个问题的一种方法是维护具有最小/最大值和先进先出规则的优先级队列；我认为你会发现更简单的是在分配时不跟踪最小值/最大值，而是在每次打印输出之前有一个循环来查找最小值/最大值。

您的程序存在一个小问题：对于某些索引，使用的最大地址不是 ptrList[index]，而是 ptrList[index]+sizeList[index]。