Как полностью неиспользуемая память может быть фрагментирована?

Question

Следующий пример кода C (взяты из http://bugs.python.org/issue19246) выполнен на Windows 7 64-битной, в то время как скомпилирован в 32-битном режиме

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

Выходы:

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

Результат может быть интерпретирован как: после того, как весь выделение памяти, а затем ее освобождение, память процесса фрагментирована настолько плохо, что нет фрагмента с длиной 1 МБ. Однако процедуру стресса можно повторять непрерывно без ошибок памяти.

Вопросов:

1. Как память может быть фрагментирован, если она полностью не используется?
2. Как фрагментация памяти может быть исправлена ​​для этого процесса?

Answer 1

# 1

Это своего рода забавный вопрос, потому что мы никогда не говорим о фрагментированной памяти в использовании (давайте игнорировать кэш местности на данный момент). Фрагментация памяти становится проблемой, когда память доступна для распространения снова, но предыдущие распределения памяти, разделяющие пул памяти на более мелкие куски, требуют объединения блоков.

Я думаю, причина, по которой вы задаете этот вопрос, состоит в том, что вы привыкли к примеру наихудшего случая, где такой непрерывный блок памяти не существует, не перемещая ничего. Но даже в не худших случаях это может быть очень сложная проблема, обнаруживающая потенциальную операцию де-фрагментации, в результате чего распределитель задыхается от экземпляров проблемы, когда человек может легко увидеть решение.

Но чтобы ответить на ваш вопрос, рассмотреть этот выделенный фрагмент памяти:

aaaabbbbcccc 

Теперь a и c получить освободившуюся:

....bbbb.... 

И теперь b получает освобожденный:

....____.... 

Теперь у нас есть три непрерывных seperat e кусков памяти в пуле памяти - для этого требуется специальный код, и, по-видимому, распределитель дросселирует на этом.

# 2

Ответ на этот вопрос прост: дефрагментировать пул памяти. Насколько легко/сложно решить эту проблему, зависит от того, какой распределитель используется и сколько он делает.