Purposely waste all of main memory to learn fragmentation

Question

In my class we have an assignment and one of the questions states:

Memory fragmentation in C: Design, implement, and run a C-program that does the following: it allocated memory for a sequence of of 3m arrays of size 500000 elements each; then it deallocates all even-numbered arrays and allocates a sequence of m arrays of size 700000 elements each. Measure the amounts of time your program requires for the allocations of the first sequence and for the second sequence. Choose m so that you exhaust all of the main memory available to your program. Explain your timings

My implementation of this is as follows:

#include <iostream>
#include <time.h>
#include <algorithm>

void main(){
    clock_t begin1, stop1, begin2, stop2;
    double tdif = 0, tdif2 = 0;
    for(int k=0;k<1000;k++){
    double dif, dif2;
    const int m = 50000;
    begin1 = clock();
    printf("Step One\n");
    int *container[3*m];
    for(int i=0;i<(3*m);i++)
    {
        int *tmpAry = (int *)malloc(500000*sizeof(int));
        container[i] = tmpAry;
    }
    stop1 = clock();
    printf("Step Two\n");
    for(int i=0;i<(3*m);i+=2)
    {
    free(container[i]);
    }
    begin2 = clock();
    printf("Step Three\n");
    int *container2[m];
    for(int i=0;i<m;i++)
    {
    int *tmpAry = (int *)malloc(700000*sizeof(int));
    container2[i] = tmpAry;
    }
    stop2 = clock();
    dif = (stop1 - begin1)/1000.00;
    dif2 = (stop2 - begin2)/1000.00;
    tdif+=dif;
    tdif/=2;
    tdif2+=dif2;
    tdif2/=2;
}
printf("To Allocate the first array it took: %.5f\n",tdif);
printf("To Allocate the second array it took: %.5f\n",tdif2);
system("pause");
};

I have changed this up a few different ways, but the consistencies I see are that when I initially allocate the memory for 3*m*500000 element arrays it uses up all of the available main memory. But then when I tell it to free them the memory is not released back to the OS so then when it goes to allocate the m*700000 element arrays it does it in the page file (swap memory) so it does not actually display memory fragmentation.

The above code runs this 1000 times and averages it, it takes quite some time. The first sequence average took 2.06913 seconds and the second sequence took 0.67594 seconds. To me the second sequence is supposed to take longer to show how fragmentation works, but because of the swap being used this does not occur. Is there a way around this or am I wrong in my assumption?

I will ask the professor about what I have on monday but until then any help would be appreciated.

Answer 1

Many libc implementations (I think glibc included) don't release memory back to the OS when you call free(), but keep it so you can use it on the next allocation without a syscall. Also, because of the complexity of modern paging and virtual memory stratagies, you can never be sure where anything is in physical memory, which makes it almost imposible to intentionally fragment it (even if it comes fragmented). You have to remember, all virtual memory, and all physical memory are different beasts.

(The following is written for Linux, but probably applicable to Windows and OSX)

When your program makes the first allocations, let's say there is enough physical memory for the OS to squeeze all of the pages in. They aren't all next to each-other in physical memory -- they are scattered wherever they can be. Then the OS modifies the page table to make a set of continuous virtual addresses, that refer to the scattered pages around in memory. But here's the thing -- because you don't really use the first memory you allocate, it becomes a really good candidate for swapping out. So, when you come along to do the next allocations, the OS, running out of memory, will probably swap out some of those pages to make room for the new ones. Because of this, you are actually measuring disk speeds, and the efficiency of the operations systems paging mechanism -- not fragmentation.

Remember, an set of continuous virtual addresses is almost never physically continuous in practice (or even in memory).