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; 
} 

很接近我的內存分配/釋放的正確方法？在我執行for循環之前，我的程序編譯並運行（沒有輸出），其中int j。它在我實現它之後掛起，所以也許有人可以幫我把問題固定在那裏。

編輯： 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 
    ... 

，然後可以斷定你的程序似乎掛起，因爲它是慢慢數Ĵ高達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]);時，可能會釋放佔當前最小或最大內存地址的項目。解決這個問題的一種方法是維護具有最小/最大值和fifo規則的優先級隊列;我認爲，你會發現更簡單的是，在分配時不跟蹤最小/最大值，而是在每次打印之前找到最小/最大值的循環。

程序的一個小問題：某些索引使用的最大地址不是ptrList[index]，而是ptrList[index]+sizeList[index]。