Правило 50 процентов

Question

Я пишу программу, которая проверяет динамическое распределение памяти, чтобы увидеть, насколько хорошо выполняется правило 50 процентов.

Программа имеет 10 000 указателей на динамически распределенные блоки памяти.Он также имеет массив для хранения размера каждого блока.Он должен:

1. Использовать malloc() для динамического выделения блока памяти для каждого элемента ptrList.Эти блоки должны иметь размеры, которые выбираются случайным образом в диапазоне от 1 до 10000 байт, а размер блока должен храниться в массиве 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

Помимо 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, вы можете освободить элемент, который учитывает текущий минимальный или максимальный адреса памяти. Одним из способов решения этой проблемы является поддержание приоритетных очередей со значениями min / max и дисциплиной fifo; я думаю, что вам будет проще не отслеживать мин / макс при распределении, а просто создать цикл для нахождения мин / макс прямо перед каждой распечаткой.

Незначительная проблема с вашей программой: максимальный используемый адрес не ptrList[index] для некоторого индекса, но ptrList[index]+sizeList[index].