c - 50%规则

Question

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

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

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

我的程序是这样编码的:

#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% 规则是所有 block 的总大小除以堆大小的近似值通常约为 50%。

Answer 1

除了 cruft(极其不必要的代码)之外，您还遇到了变量和循环的一些问题:您的 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 ) {
     ...

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

你程序的一个小问题:使用的最大地址不是ptrList[index]对于某些索引，但是 ptrList[index]+sizeList[index] .