Como fazer com que o kernel compacte memória fragmentada

Estou executando Fedora 26.

Isto é para uma tarefa muito estranha dada pelo meu professor de algoritmos. A tarefa diz:

Fragmentação de memória em C:
projete, implemente e execute um programa C que faça o seguinte: Aloca memória para uma sequência de 3mmatrizes com tamanho de 800.000 elementos cada; em seguida, desaloca explicitamente todas as matrizes de números pares e aloca uma sequência de mmatrizes de tamanho 900.000 elementos cada. Meça a quantidade de tempo que seu programa requer para a alocação da primeira sequência e da segunda sequência. Escolha mesgotar quase toda a memória principal disponível para o seu programa ".

O objetivo geral disso é fragmentar a memória e solicitar um pouco mais do que o que está disponível como um bloco contíguo, forçando o sistema operacional a compactar ou desfragmentar a memória.

Na aula, perguntei como deveríamos fazer isso, já que a memória é visualizada e não é realmente contígua, à qual ele respondeu: "Bem, você terá que desativar a [memória virtual]". Alguns outros alunos perguntaram na sala de aula como deveríamos saber quando atingimos essa "coleta de lixo" e ele disse que: "O tempo para a segunda alocação deve ser maior que o primeiro por causa do tempo gasto na coleta de lixo".

Depois de pesquisar um pouco, a coisa mais próxima que pude encontrar para desabilitar a memória virtual foi desabilitar a troca de memória swapoff -a. Desativei meu ambiente de área de trabalho, compilei e executei meu programa a partir do terminal nativo (para evitar possíveis interferências de outros processos, especialmente um pesado como o Ambiente de Área de Trabalho). Fiz isso e executei meu programa aumentando maté chegar a um ponto em que o tempo para a segunda alocação era maior que o primeiro.

Executei o programa com aumento me, finalmente, encontrei um ponto em que o tempo para a segunda alocação era maior que o tempo para a primeira alocação. Ao longo do caminho, porém, cheguei a um ponto em que o processo foi encerrado antes da segunda alocação. Eu verifiquei dmesge vi que foi morto por oom-killer. Eu encontrei e li vários artigos sobre o oom-killer e descobri que era possível desativar a alocação de memória excessiva pelo kernel.

Fiz isso e executei meu programa novamente, só que desta vez não consegui encontrar um mtal que o tempo do segundo fosse maior que o primeiro. Eventualmente, com m cada vez maior (embora muito menor do que quando a alocação geral estava ativada), o malloc falharia e meu programa seria encerrado.

Eu tenho três perguntas, a primeira das quais não é realmente tão importante:

1. Coleta de lixo é o termo correto para isso? Meu professor é muito inflexível ao dizer que isso é coleta de lixo, mas eu assumi que a coleta de lixo era algo feito pelas linguagens de programação e que isso seria considerado mais desfragmentado.

2. A compactação como ele deseja é possível em um sistema Linux?

3. Por que consegui chegar a um ponto em que o tempo para a segunda alocação era maior que o primeiro quando desabilitei a troca, mas ainda tinha a alocação geral de memória ativada? A compactação realmente ocorreu? Se sim, por que não consegui chegar a um ponto em que a compactação ocorreu depois que desabilitei a localização geral da memória?

Parabéns pela sua pesquisa até agora, este é realmente um conjunto interessante de perguntas.

Geralmente, há um aspecto importante a ser considerado: a alocação de memória é parcialmente da responsabilidade do sistema operacional e parcialmente de cada processo em execução (ignorando os sistemas antigos sem proteção de memória e espaços de endereço virtual). O sistema operacional cuida de fornecer a cada processo seu próprio espaço de endereço e alocar memória física aos processos quando necessário. Cada processo cuida de dividir seu espaço de endereço (até certo ponto) e garantir que ele seja usado adequadamente. Observe que a responsabilidade de um processo será em grande parte invisível para os programadores, pois o ambiente de tempo de execução cuida da maioria das coisas.

Agora, para responder suas perguntas ...

1. Na minha opinião, a coleta de lixo está a um passo do que você está fazendo aqui. Eu imagino que você está escrevendo em C, usando malloc()e free(). A coleta de lixo , quando suportada pela linguagem de programação e pelo ambiente de tempo de execução, cuida da última parte: identifica blocos de memória que foram alocados anteriormente, mas não estão mais em uso (e, o mais importante, nunca podem ser usados ​​novamente) e os retornam para o alocador. A questão ligada em JdeBP ‘s comentário fornece algumas informações, mas acho que é principalmente interessante porque demonstra que pessoas diferentes têm opiniões muito diferentes sobre a coleta de lixo, e até mesmo o que constitui a coleta de lixo.

   No contexto em que estamos interessados, eu usaria "compactação de memória" para falar sobre o processo em discussão.

2. Do ponto de vista da programação do espaço do usuário, o que seu professor está pedindo não é possível, em C, no Linux, por um simples motivo: o que nos preocupa aqui não é a fragmentação da memória física, é a fragmentação do espaço de endereço. Quando você aloca seus muitos blocos de 800.000 bytes, você acaba com o mesmo número de ponteiros para cada bloco. No Linux, neste momento, o sistema operacional em si não fez muito e você não precisa necessariamente de memória física para cada alocação (além disso, com alocações menores, o sistema operacional não estaria envolvido, apenas sua Alocador da biblioteca C; mas as alocações aqui são grandes o suficiente para que a biblioteca C usemmap, que é tratado pelo kernel). Quando você libera os blocos de números ímpares, recupera esses blocos de espaço de endereço, mas não pode alterar os ponteiros que possui para os outros blocos. Se você imprimir os ponteiros à medida que avança, verá que a diferença entre eles não é muito mais do que a solicitação de alocação (802.816 bytes no meu sistema); não há espaço entre dois ponteiros para um bloco de 900.000 bytes. Como seu programa possui ponteiros reais para cada bloco, em vez de um valor mais abstrato (em outros contextos, um identificador), o ambiente de tempo de execução não pode fazer nada sobre isso e, portanto, não pode compactar sua memória para unir blocos livres.

   Se você usar uma linguagem de programação em que ponteiros não sejam um conceito visível para programadores, a compactação de memória será possível no Linux. Outra possibilidade seria usar uma API de alocação de memória em que os valores retornados não sejam ponteiros; veja, por exemplo, as funções de alocação de heap baseada em identificador no Windows (onde os ponteiros são válidos apenas quando um identificador está bloqueado).

3. O exercício do seu professor está efetivamente medindo o desempenho de mmap, que inclui seu algoritmo de caminhada em bloco livre. Primeiro você aloca blocos de 3 × m , libera metade deles e começa a alocar m blocos novamente; liberar todos esses blocos despeja uma enorme carga de blocos livres no alocador do kernel, que ele precisa acompanhar (e o tempo gasto pelas freechamadas mostra que não há otimização sendo feita neste momento). Se você acompanhar os tempos de alocação de cada bloco individual, verá que a primeira alocação de 900k leva muito, muitomais longo que os outros (três ordens de grandeza no meu sistema), o segundo é muito mais rápido, mas ainda leva muito mais tempo (duas ordens de grandeza), e a terceira alocação volta aos níveis típicos de desempenho. Portanto, há algo acontecendo, mas os ponteiros retornados mostram que não era compactação de memória, pelo menos não compactação de bloco alocada (o que, como explicado acima, é impossível) - presumivelmente o tempo corresponde ao tempo de processamento das estruturas de dados que o kernel usa para acompanhe o espaço de endereço disponível no processo (estou verificando isso e atualizarei mais tarde). Essas alocações demoradas podem aumentar para diminuir as seqüências gerais de alocação que você está medindo, ou seja, quando as alocações de 900k acabam demorando mais do que as alocações de 800k.

   A razão pela qual a confirmação excessiva altera o comportamento que você vê é que ele altera o exercício de manipular o espaço de endereço puramente para realmente alocar memória e, portanto, reduz o tamanho do seu playground. Quando você pode confirmar demais, o kernel é limitado apenas pelo espaço de endereço do seu processo, para que você possa alocar muito mais blocos e colocar muito mais pressão no alocador. Quando você desabilita a confirmação excessiva, o kernel é limitado pela memória disponível, o que reduz o valor que você pode ter para mníveis em que o alocador não está estressado o suficiente para que os tempos de alocação aumentem.