C语言 50-Percent Rule

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 %dn", j, maximum - minimum, total);
      }
      for (int i = 0; i < BLOCK_COUNT; i++) {
          free(ptrList[i]);
      }
  }
  return 0;
}

我是否以正确的方式接近内存的分配/释放?在我用int j实现for循环之前，我的程序编译并运行(没有输出)。它挂起后，我实现它，所以也许有人可以帮助我把问题，以及。

Edit: 50%规则是所有块的总大小除以堆大小的近似值，通常在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这些大数中去掉两个或三个0，将j循环限制更改为10，并在for (int j ...) {之后添加printf("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。

现在我将提到要删除的两个次要的cruft项，然后再提到您的程序中的一个主要问题。

代替

  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]);时，您可能正在释放占用当前最小或最大内存地址的项。解决这个问题的一种方法是维护具有最小/最大值和fifo原则的优先级队列;我认为，你会发现更简单的方法是，在分配时不跟踪min/max，而是在每次打印输出之前循环查找min/max。

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