50 percent rule

Question

I am writing a program that tests dynamic memory allocation to see how well the 50 percent rule is followed.

The program has 10,000 pointers to dynamically allocated memory blocks. It also has an array to store the size of each block. He must:

• Use malloc() to dynamically allocate a block of memory for each ptrList element. These blocks must have sizes that are randomly selected in the range from 1 to 10,000 bytes, and the block size must be stored in the sizeList array.
• After the initial block allocation, the program should re-release the blocks and allocate new ones. This should take 100,000 iterations. At each iteration, the index in ptrList is randomly selected, the block is freed, and then replaced with a new dynamically allocated block with a random size.
• After every 100 iterations, it should print a line that shows the number of iterations, the approximate heap size (determined by the difference between the highest and lowest memory addresses contained in any of the blocks), and the total size of all blocks pointed to by ptrList .

My program is encoded like this:

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

Am I coming to the right way to allocate / free memory? My program compiles and runs (no output) before I execute a for loop with int j . It freezes after I implemented it, so maybe someone can help me relate the problem there too.

Edit: A 50 percent rule is the total size of all blocks divided by an approximation of the heap size, usually around 50 percent.

Answer 1

Besides the cool (mostly unnecessary code), you have some problems with variables and loops: your for (int i = 0; i < TEST_LENGTH; i++)... loop for (int i = 0; i < TEST_LENGTH; i++)... , which implements specification step 2, is a loop in which every 100 steps you should print the current statistics, the presence of an external for (int j = 0; j < 1000; j++) loop for (int j = 0; j < 1000; j++) and testing j%100 residues is nonsense.

To debug such a problem, drop two or three zeros from each of the large numbers BLOCK_COUNT, TEST_LENGTH, SIZE_LIMIT, change the j loop limit to 10 and add printf("j=..." ...) after for (int j ...) { so you can tell what is happening. With such changes you will see:

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

and then you can conclude that your program seemed to freeze because it slowly counted j to 100 to get to j%100 == 0 .

Now I will talk about two minor elements that need to be removed, and after that the main problem with your program will be mentioned.

Instead

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

records

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

(or perhaps the MAX_INT option) and (if you need j and / or remainder , what you don't) instead

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

you write

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

The main problem with your program: if you say free(ptrList[index]); in part 2, you can free an element on which the current minimum or maximum memory addresses have been indicated. One way to solve this problem is to maintain priority queues with minimum / maximum values ​​and fifo discipline; which, in my opinion, is the easiest way to keep track of min / max during distribution, and instead just have a loop to find min / max immediately before each printout.

A small problem with your program: The maximum address used is not ptrList[index] for some index, but ptrList[index]+sizeList[index] .