0

Following C code example (taken from http://bugs.python.org/issue19246) executed on Windows 7 64-bit, while compiled in 32-bit mode

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


int create_huge_linked_list(void **last_item) {
    int i;
    void *prev_item = NULL;

    for(i = sizeof(void *); i < 1000000; i++) {
        void *new_item = malloc(i);
        if(new_item == NULL) {
            break;
        }
        *(void **)new_item = prev_item;
        prev_item = new_item;
    }
    *last_item = prev_item;
    return i;
}

void free_linked_list(void *last_item) {
    while(last_item != NULL) {
        void *prev_item = *(void **)last_item;
        free(last_item);
        last_item = prev_item;
    }
}

int stress_heap() {
    void *last_item;
    int amount = create_huge_linked_list(&last_item);
    free_linked_list(last_item);
    return amount;
}

void stress_twice(void) {
    int first = stress_heap();
    int second = stress_heap();
    printf("%i %i %f%%\n", first, second, 100.0 * second / first);
}

void stress_and_alloc_1_mb() {
    void *ptr;

    ptr = malloc(1000000);
    if(ptr != NULL) {
        printf("Successfully allocated 1 MB before stress\n");
        free(ptr);

        stress_heap();

        ptr = malloc(1000000);
        if(ptr != NULL) {
            printf("Successfully allocated 1 MB after stress\n");
            free(ptr);
        } else {
            printf("Failed to allocate 1 MB after stress\n");
        }
    } else {
        printf("Failed to allocate 1 MB before stress\n");
    }
}

int main() {
    stress_and_alloc_1_mb();
    stress_twice();
    return 0;
}

Outputs:

Successfully allocated 1 MB before stress
Failed to allocate 1 MB after stress
64855 64857 100.003084%

Result may be interpreted as: after whole memory allocation and then freeing it, memory of the process is fragmented so bad, that there is no chunk with length of 1 MB. However, the stress procedure can be repeated continuously without memory errors.

The questions are:

  1. How memory can be fragmented if it is completely unused?
  2. How memory fragmentation can be fixed for that process?
4

1 回答 1

3

#1

这是一个有趣的问题，因为我们从来没有真正谈论过碎片化的正在使用的内存（现在让我们忽略缓存局部性）。当所述内存可以再次分配时，内存碎片成为一个问题，但是之前的内存分配将内存池分成更小的块需要将块连接在一起。

我认为你问这个问题的原因是因为你已经习惯了最坏情况的例子，在这种情况下不存在这样的连续内存块而不移动任何东西。但即使在非最坏的情况下，检测潜在的碎片整理操作也可能是一个非常困难的问题，导致分配器在人类很容易看到解决方案的问题实例上窒息。

但要回答您的问题，请考虑这个分配的内存块：

aaaabbbbcccc

现在a并c获得自由：

....bbbb....

现在b被释放：

....____....

现在我们在内存池中有三个连续的独立内存块——它需要特殊的代码来检测这一点，显然分配器对此感到窒息。

#2

答案很简单：对内存池进行碎片整理。这个问题的难易程度取决于使用了什么样的分配器以及它做了多少记账。

于 2013-10-15T05:55:00.350 回答