Espaços de Endereçamento e Tradução de Endereços

Um programa em execução trabalha com um espaço de endereçamento: sua própria visão da memória, com posições de bytes numeradas. O sistema operacional posiciona a memória do programa na máquina e garante que seus endereços alcancem os bytes físicos corretos. A organização que o programa vê e a organização no hardware são coisas diferentes.

Por que vários programas permanecem na memória

Os primeiros sistemas podiam manter um programa ao lado do sistema operacional. Por exemplo, o sistema operacional poderia ocupar os primeiros 64 KB e o programa, a memória restante. A multiprogramação mantinha mais de um processo pronto, para que a CPU pudesse trabalhar enquanto outro processo aguardava entrada ou saída. O compartilhamento de tempo alternava a CPU com frequência suficiente para atender usuários interativos.

Salvar toda a memória de um processo em disco a cada troca tornaria a troca lenta demais. Manter vários processos na memória física evita essa cópia, mas cria um problema de proteção. Um endereço gerado por um processo não deve permitir que ele sobrescreva o sistema operacional ou um processo vizinho.

Os tamanhos de memória aqui seguem a convenção binária usada nesses modelos: 1 KB corresponde a 1.024 bytes, também representado por 1 KiB; 1 MB corresponde a 1.024 KB. Um espaço de endereçamento de 16 KB tem 16.384 posições de bytes, numeradas de 0 a 16.383. O número 16.384 é o limite final, não um endereço de byte válido.

Código, dados, área de alocação dinâmica e pilha

Em uma organização didática clássica de 16 KB, o código usa os endereços baixos, de 0 até o limite de 1 KB. A área de alocação dinâmica começa acima do código e cresce para cima. A pilha começa no limite superior e cresce para baixo. O espaço livre entre elas permite que ambas cresçam. Organizações reais variam; por exemplo, cada thread tem sua própria pilha. As funções das regiões continuam úteis mesmo quando suas posições mudam.

Acompanhe um ponteiro até a memória correta

Um endereço virtual identifica um byte no espaço de endereçamento de um processo. Um endereço físico identifica um byte no hardware de memória da máquina. Quando um código C imprime printf("%p", (void *) &x), ele imprime um endereço virtual. O ponteiro impresso não revela o byte físico que armazena x.

Suponha que dois processos usem o endereço virtual 1.000. Cada endereço é interpretado no espaço de endereçamento do próprio processo, de modo que os acessos podem alcançar bytes físicos diferentes. Da mesma forma, o código no endereço virtual 0 não precisa ocupar o endereço físico 0. O sistema operacional pode colocá-lo em outro lugar e configurar a tradução por hardware para alcançá-lo.

O processador traduz buscas de instrução, leituras e escritas. O sistema operacional escolhe e gerencia os mapeamentos, inclusive alterando as localizações físicas enquanto mantém estáveis os endereços virtuais do programa.

Um sistema de memória deve fazer mais do que traduzir corretamente um número. Ele deve permitir que programas comuns executem sem gerenciar a localização física, manter baixo o custo da tradução e impor os limites que tornam o compartilhamento seguro. Esses requisitos são transparência, eficiência e proteção.

Preserve a visão do programa

Transparência significa que um programa executa como se tivesse memória privada. Ele usa seus próprios endereços para código e dados sem acompanhar quais outros processos estão presentes ou onde seus bytes estão. O sistema operacional e o hardware preservam essa visão nos bastidores. Mover um processo na memória física não deve exigir que ele reescreva seus ponteiros.

A ilusão não exige uma cópia física distinta de cada byte para cada processo. Por exemplo, código protegido somente de leitura pode ser compartilhado. O que importa é que o compartilhamento preserve o comportamento e os direitos de acesso aos quais cada processo tem direito.

Considere os dois tipos de custo

Toda busca de instrução, leitura e escrita precisa de tradução. Executar uma rotina do sistema operacional para cada acesso tornaria a execução comum lenta demais. O hardware realiza as operações frequentes; o código do sistema operacional cuida da configuração, das alterações e das falhas.

A eficiência de espaço também importa. Um mecanismo de tradução pequeno e rápido ainda pode desperdiçar muita memória. Uma única região de base e limite reserva o espaço não usado entre a área de alocação dinâmica e a pilha. A segmentação evita reservar memória física para esse espaço, mas introduz regiões físicas de tamanhos variáveis e lacunas entre elas. Metadados, espaço reservado não usado e lacunas afetam a quantidade de trabalho útil que cabe na memória.

Faça um acesso inválido parar no limite

Sem proteção, um ponteiro incorreto em um editor de texto poderia sobrescrever outro processo ou o núcleo. O dano poderia aparecer muito mais tarde em um código sem relação com o editor. Com limites impostos, o hardware rejeita um acesso fora da região permitida e gera uma exceção. O sistema operacional trata a exceção e geralmente encerra o processo com defeito, informando comumente uma falha de segmentação.

A proteção isola os processos uns dos outros. Ela não torna seguro o uso da memória em C dentro de uma região permitida da área de alocação dinâmica. Uma escrita além de um bloco alocado ainda pode atingir outro bloco pertencente ao mesmo processo. Limites de processos e limites de blocos do alocador são limites diferentes.

Separe a operação da escolha

Um mecanismo é como uma operação é realizada. Somar um registrador base e verificar um registrador limite são mecanismos. Uma política escolhe entre ações possíveis: onde colocar um processo, qual lacuna livre usar ou quando mover um segmento.

Manter os dois separados permite que o sistema operacional altere sua estratégia de alocação mantendo a mesma tradução por hardware. A virtualização de memória começa com essa visão privada e protegida; ela não é definida pelo uso do disco como memória adicional.

Uma variável ponteiro e a memória para a qual ela aponta são objetos separados. Entender seus tempos de vida é o ponto de partida para a API de memória de C. Variáveis locais comuns geralmente usam armazenamento automático na pilha, blocos da área de alocação dinâmica duram até serem liberados, e variáveis globais e locais static têm armazenamento durante toda a execução do programa.

Acompanhe a alocação, não apenas o ponteiro

void f(void) {
    int x;
    int *p = malloc(sizeof(int));
}

Na organização usual da pilha, x e p pertencem a essa chamada de f. O inteiro requisitado pertence à área de alocação dinâmica. O retorno remove a variável ponteiro local; ele não libera o bloco da área de alocação dinâmica. Se nenhuma cópia do endereço permanecer, o programa terá perdido acesso a uma alocação ativa: um vazamento de memória.

malloc(size) requisita pelo menos essa quantidade de bytes e retorna um ponteiro, ou NULL quando não consegue atender à requisição. Seus bytes não são inicializados para o programa. Para 10 inteiros, use malloc(10 * sizeof(int)); onde um inteiro tem 4 bytes, isso requisita 40 bytes. Para uma string, reserve espaço para seus caracteres mais um byte para o caractere nulo de término: malloc(strlen(s) + 1).

sizeof(a) mede o objeto chamado a. Se a for um ponteiro, ele fornece o tamanho do ponteiro, não o tamanho da alocação. Um ponteiro de 8 bytes pode se referir a um bloco de 40 bytes.

Saiba o que cada operação da biblioteca faz

free recebe o ponteiro retornado, sem um argumento de tamanho. O alocador mantém metadados de tamanho, geralmente em um cabeçalho antes do bloco. Passe o ponteiro retornado de um bloco atualmente alocado; um ponteiro para o interior do bloco não é um substituto válido. free(NULL) é válido e não faz nada. Essas funções são rotinas da biblioteca C, não chamadas de sistema.

Reconheça o erro pelo tempo de vida ou pelo limite

Um ponteiro sem uma alocação válida não pode ser usado como se já apontasse para uma área de armazenamento. Ler bytes recém-alocados antes de inicializá-los é uma leitura de memória não inicializada. Escrever além do fim da área alocada é um estouro de buffer; omitir o byte de término de uma string pode causar esse erro.

Após free, os ponteiros antigos para o bloco ficam pendentes. Acessar a memória por meio de um deles é um uso após liberação. Liberar o bloco novamente é uma dupla liberação. Liberar um endereço que o alocador não retornou para um bloco ativo é uma liberação inválida. Vazamento de um bloco é diferente: o bloco continua alocado, mas o programa deixa de liberá-lo quando deveria.

Entenda o que o hardware pode verificar

A compilação pode ser bem-sucedida apesar de todos esses erros. O hardware normalmente verifica regiões e permissões do processo, não cada alocação da biblioteca. Ultrapassar o limite de um bloco enquanto se permanece dentro da área de alocação dinâmica permitida do processo pode causar comportamento indefinido sem uma falha imediata. O programa pode corromper dados, falhar mais tarde, ler valores sem sentido ou parecer funcionar. Valgrind e AddressSanitizer podem detectar muitos desses erros durante a execução.

A biblioteca C e o sistema operacional gerenciam a memória em escalas diferentes. O sistema operacional estabelece regiões no espaço de endereçamento de um processo e fornece a memória que as sustenta. O alocador divide a memória disponível da área de alocação dinâmica em blocos, registra os blocos livres e os reutiliza entre chamadas.

Mova o limite da área de alocação dinâmica

O limite da área de alocação dinâmica é o endereço imediatamente após o fim da área tradicional de alocação dinâmica. brk define esse limite em um endereço escolhido. sbrk(n) o move por um incremento em bytes e, em caso de sucesso, retorna o limite anterior. sbrk(0) informa o limite atual sem movê-lo.

Suponha que o limite seja 40.960 e que o alocador chame sbrk(8192) com sucesso. O valor retornado é 40.960. O novo limite é:

Os bytes adicionados ocupam os endereços virtuais de 40.960 a 49.151. O novo limite, 49.152, fica imediatamente após a região adicionada. Confundir o valor retornado com o novo limite desloca todos os cálculos posteriores de alocação.

As aplicações usam a biblioteca de alocação em vez de mover o limite diretamente. A biblioteca controla quais partes de sua região pertencem a ela. Alterações independentes nesse limite podem invalidar seus registros.

Obtenha um mapeamento separado

mmap pode criar uma região anônima: memória não vinculada a um arquivo, inicialmente preenchida com bytes de valor zero. munmap remove um mapeamento. Um alocador pode usar mapeamentos separados para alocações grandes e devolvê-los ao sistema operacional quando forem liberados.

Na glibc, o limiar inicial padrão para essa abordagem é 128 KB, ou 131.072 bytes, e pode ser aumentado. Uma alocação suficientemente grande geralmente é mapeada separadamente se não puder ser atendida pelo espaço livre existente. Essa é uma política da biblioteca, não uma linha divisória universal na linguagem C.

Libere no nível da biblioteca ou do sistema operacional

Uma chamada a free geralmente devolve um bloco pequeno à reserva da biblioteca. Por isso, o processo pode apresentar o mesmo uso de memória posteriormente. A memória fica disponível para reutilização sem outra requisição ao sistema operacional.

O encerramento do processo recupera até as alocações que o programa deixou vazar. Durante a vida de um servidor de longa duração, porém, vazamentos repetidos continuam consumindo a memória disponível. A recuperação no encerramento não evita essa pressão enquanto ele executa.

Relacione o crescimento da área de alocação dinâmica à tradução

No modelo de segmentação, a área de alocação dinâmica é um segmento físico contíguo. Ampliá-la exige bytes físicos livres imediatamente acima dela. Se esses bytes estiverem ocupados, o sistema operacional pode mover o segmento para uma lacuna maior e atualizar seu estado de tradução. Se não houver uma região adequada disponível, a ampliação falhará. Se o alocador não conseguir obter espaço suficiente, malloc retornará NULL.

A relocação dinâmica traduz endereços enquanto um programa executa. No modelo de base e limite, um processo ocupa uma região física contígua. Comece com espaços de endereçamento de mesmo tamanho que caibam na memória física; um par de registradores descreve então a região do processo em execução no momento.

Verifique primeiro o endereço virtual

O registrador base contém o endereço físico do primeiro byte da região. O registrador de limites, ou registrador limite, contém o tamanho da região em bytes. Para um endereço virtual não negativo, a regra é:

Se a verificação for bem-sucedida:

Caso contrário, o hardware gera uma exceção. Um tamanho é uma contagem, portanto o endereço igual ao limite já está fora da região. Endereços virtuais negativos também são inválidos.

Examine os limites dos bytes

Considere um espaço de endereçamento de 8 KB com base 20.480 e limite 8.192. Seus bytes virtuais vão de 0 a 8.191. O endereço virtual 1.000 passa na verificação e alcança o byte físico 21.480. O último byte virtual permitido, 8.191, alcança 28.671. O endereço 9.000 falha porque é pelo menos 8.192; o hardware deve rejeitá-lo antes de realizar o acesso físico.

As buscas de instrução usam a mesma tradução que os dados. Se uma instrução no endereço virtual 128 lê do endereço virtual 3.000, a busca alcança o endereço físico 20.608 e a leitura alcança 23.480. São dois acessos à memória com dois endereços traduzidos, não uma única tradução compartilhada por toda a instrução.

Diferencie as convenções de limite

A mesma região de 8 KB tem limite físico final 28.672. As duas convenções permitem exatamente os bytes de 20.480 a 28.671. Comparar o endereço físico 21.480 com o tamanho 8.192 mistura as duas convenções e rejeita incorretamente um acesso permitido.

Mova a memória sem alterar os ponteiros

A MMU, ou unidade de gerenciamento de memória, realiza as verificações e a soma. O sistema operacional pode pausar um processo, copiar sua região para outro lugar e alterar a base. O processo continua usando os mesmos endereços virtuais, por isso a relocação é dinâmica.

Na relocação estática, um carregador reescreve os endereços incorporados ao carregar o código. Reescrever uma referência de 1.000 para 21.480 registra uma localização física no programa. Movê-lo depois exige novas alterações, e a reescrita por si só não impede que um programa construa um endereço fora de sua região.

Some a base apenas a um endereço virtual. Somá-la a um endereço físico já traduzido desloca a localização uma segunda vez e destrói o mapeamento.

O hardware mantém registradores de tradução para o processo em execução em uma CPU. O sistema operacional mantém o estado salvo dos processos em espera. A proteção depende de conceder apenas ao código privilegiado do sistema operacional o poder de alterar esse estado.

Forneça as operações de hardware

A CPU precisa dos modos usuário e núcleo, de um par de registradores base e limite em sua MMU e de circuitos para a verificação e a soma. Ela também precisa de operações privilegiadas para alterar o par e instalar tratadores de exceções. Endereços inválidos e tentativas de executar instruções privilegiadas em modo usuário devem gerar exceções.

Se um programa de usuário pudesse alterar sua base, poderia redirecionar seus endereços para o núcleo ou outro processo. As verificações de limite protegeriam então a região errada. Restringir alterações é, portanto, parte do mecanismo de proteção, não apenas uma conveniência administrativa.

Crie e execute um processo

Na inicialização, o sistema operacional instala seus tratadores de armadilhas e exceções, inicia o temporizador de interrupção e prepara seus registros de memória livre. Quando um processo começa, o sistema operacional encontra uma posição física para seu espaço de endereçamento. Com posições de mesmo tamanho, uma lista de blocos livres pode simplesmente registrar quais posições não estão em uso.

O sistema operacional marca a posição escolhida como ocupada, registra a base e o limite do processo, carrega os registradores e entra no modo usuário. O processo executa então diretamente na CPU. O hardware traduz os acessos comuns sem chamar o sistema operacional para cada byte.

Restaure o par correto em uma troca de contexto

Uma interrupção do temporizador transfere o controle ao sistema operacional. Ele salva os registradores do processo anterior, incluindo base e limite, em seu bloco de controle de processo e restaura os valores do próximo processo antes de retornar ao modo usuário.

Suponha que a base de A seja 20.480 e a de B seja 40.960, ambas com limite 8.192. O endereço virtual 1.000 de A alcança 21.480. Após a troca para B, o mesmo número virtual alcança 41.960. Restaurar os registradores da CPU sem restaurar o estado de tradução faria B acessar a região de A usando os ponteiros de B.

A CPU mantém o par ativo; cada processo tem seu próprio par salvo. Não imagine um único par permanente para toda a máquina nem suponha que o par de cada processo esteja ativo simultaneamente em uma CPU.

Mova, trate falhas e encerre

Para mover A para o endereço físico 49.152, o sistema operacional retira A da CPU, copia sua região de 8 KB e atualiza a base salva de A. Quando A retoma com essa base instalada, o endereço virtual 1.000 alcança 50.152. Seus valores de ponteiro virtual não precisam ser alterados.

Em um acesso inválido, o hardware gera uma exceção e transfere a execução para o modo núcleo no tratador registrado. O sistema operacional geralmente encerra o processo responsável. No encerramento, ele devolve a posição à lista de blocos livres e libera os registros do processo.

Base e limite atende a dois objetivos com baixo custo: a tradução é transparente, e cada endereço é verificado em relação à região alocada. Seu principal ponto fraco é a relação entre essa região e os bytes que o processo realmente usa.

Reserve toda a extensão

O hardware precisa apenas de uma soma e uma comparação no caminho executado com frequência. Um alocador de posições de tamanho fixo também pode escolher rapidamente uma posição livre. Nenhuma dessas vantagens significa que a posição esteja cheia de dados úteis.

Na organização clássica, o código e a área de alocação dinâmica ficam perto de uma extremidade, e a pilha, perto da outra. Um único par de registradores base e limite traduz todo o intervalo. O espaço não usado entre a área de alocação dinâmica e a pilha ocupa memória física assim como as partes úteis.

Para um espaço de endereçamento de 16 KB que usa 1 KB de código, 2 KB de área de alocação dinâmica e 1 KB de pilha:

O desperdício é fragmentação interna: bytes não usados dentro de uma região já alocada a um processo. Ele não resulta de uma escolha ruim de bloco pelo alocador da área de alocação dinâmica. Mesmo uma área de 2 KB perfeitamente ocupada deixa o grande espaço intermediário reservado.

Separe três questões de tamanho

A extensão do espaço de endereçamento, os bytes usados no momento e a memória física disponível são grandezas diferentes. Um espaço de 32 bits endereçado por byte abrange $2^{32}$ bytes, ou 4 GB. Reservá-lo como um único bloco físico exige os 4 GB inteiros, mesmo que o processo use apenas alguns megabytes no momento.

Tornar as posições de tamanho variável elimina a restrição de tamanho igual, mas não elimina a necessidade de uma lacuna contígua. Isso também cria um problema de alocação: o sistema operacional deve escolher entre lacunas livres de tamanhos diferentes. Reduzir uma posição não pode preservar tanto os endereços baixos do código quanto um endereço alto e distante da pilha se toda a extensão tiver de permanecer válida no mesmo mapeamento simples.

Realocar as regiões separadamente

Código, área de alocação dinâmica e pilha não precisam ser vizinhos na memória física para preservar a visão do programa. Dar a cada um sua própria base e seu próprio limite permite que o sistema operacional aloque apenas suas extensões usadas e deixe o espaço virtual sem memória física associada. Isso é segmentação, a generalização de um par de relocação para várias regiões lógicas.

Na organização de 16 KB acima, as três regiões usadas precisam de apenas 4 KB no total antes de sua própria sobrecarga de gerenciamento. A economia de espaço vem da mudança do que é realocado como uma unidade, não de tornar mais rápida a soma do registrador base.

Um segmento é uma região contígua de um espaço de endereçamento com uma finalidade. No modelo clássico, código, área de alocação dinâmica e pilha recebem, cada um, um par de base e tamanho. Suas regiões físicas podem ser posicionadas independentemente, embora o processo mantenha sua organização virtual habitual.

Mapeie apenas as extensões usadas

Use um espaço de endereçamento de 16 KB com as seguintes posições. Os tamanhos usam KB binário, ou KiB.

O código e a área de alocação dinâmica crescem em direção aos endereços mais altos; a tradução da pilha usa seu limite superior e um deslocamento negativo. As três regiões físicas usam apenas 7 KB no total. As lacunas virtuais entre elas não precisam de armazenamento físico. Um segmento continua contíguo; o que deixa de exigir posições adjacentes é a relação entre segmentos.

Traduza um segmento que cresce para cima

Primeiro identifique o segmento. Depois calcule o deslocamento a partir de seu início virtual. Verifique se o deslocamento é não negativo e menor que o tamanho atual e, então, some-o à base física:

Para o endereço virtual 500, o deslocamento no código é 500. Ele é menor que 2.048, então o acesso alcança o endereço físico 41.460.

Para o endereço virtual 5.000, o deslocamento na área de alocação dinâmica é:

A verificação de tamanho é bem-sucedida porque 904 é menor que 3.072. O resultado é:

Somar o endereço virtual inteiro à base da área de alocação dinâmica produziria 31.624. Isso inclui incorretamente a posição inicial virtual da área em um cálculo que precisa apenas da distância dentro do segmento.

Verifique o segmento, não apenas a extensão do espaço de endereçamento

O endereço virtual 7.500 ainda cabe em 14 bits, mas isso não o torna permitido. Seu deslocamento na área de alocação dinâmica é 3.404, além da extensão atual de 3.072 bytes. O hardware gera uma exceção. Um endereço pode, portanto, estar dentro da extensão total do espaço de endereçamento e ainda assim fora de todas as regiões válidas.

O termo falha de segmentação surgiu para acessos inválidos em sistemas segmentados e continua em uso para acessos inválidos em sistemas com outros esquemas de tradução. O nome do erro, por si só, não identifica o mecanismo de tradução da máquina.

Antes que o hardware possa usar a base e o tamanho de um segmento, ele deve decidir a qual segmento um acesso se refere. Uma arquitetura explícita coloca essa escolha em bits do endereço. Uma arquitetura implícita a determina pela forma como a CPU gerou o endereço.

Divida um endereço de 14 bits

Reserve os dois bits mais altos para o número do segmento e os doze bits mais baixos para o deslocamento. O campo de dois bits tem quatro valores possíveis. Use 00 para código, 01 para área de alocação dinâmica e 11 para pilha; deixe 10 sem uso.

O campo de deslocamento pode representar 4.096 valores diferentes, de 0 a 4.095. Portanto, a janela virtual máxima de cada segmento é de 4 KB, mesmo quando a extensão válida atual do segmento é menor. Capacidade máxima e tamanho atual são limites diferentes.

Para o endereço virtual 5.000, a representação em 14 bits é:

01 0011 1000 1000

Os bits iniciais 01 selecionam a área de alocação dinâmica. Os bits restantes, 0011 1000 1000, correspondem a 904 em decimal. Com tamanho 3.072 e base física 26.624 para a área de alocação dinâmica, o deslocamento passa na verificação de tamanho e alcança o endereço físico 27.528.

Use uma máscara e um deslocamento de bits

A mesma divisão pode ser expressa em código:

segment = (va & 0x3000) >> 12;
offset = va & 0x0FFF;

A máscara 0x3000 mantém os dois bits de seleção; deslocá-los doze posições move-os para as posições mais baixas, fornecendo o número do segmento. A máscara 0x0FFF zera esses bits de seleção e mantém o deslocamento. Para va = 0x1388, os resultados são segmento 1 e deslocamento 0x388, ou 904.

Não some 0x1388 diretamente à base da área de alocação dinâmica. Esse valor inclui tanto o seletor de segmento quanto o deslocamento. O seletor escolhe os registradores; apenas o deslocamento participa da tradução dentro do segmento. O endereço físico resultante não precisa manter o padrão de bits do seletor.

Reconheça o custo da divisão

Um seletor de dois bits cria quatro janelas. Deixar 10 sem uso torna indisponível um quarto da extensão virtual de 16 KB. Nenhum segmento pode crescer além de sua janela de 4 KB apenas porque mais memória física ficou livre. Outras arquiteturas podem usar uma divisão diferente; combinar código e área de alocação dinâmica em um segmento permite que um único bit seletor o diferencie da pilha.

Deixe o tipo de acesso escolher

Em uma arquitetura implícita, as buscas de instrução usam o segmento de código porque seu endereço vem do contador de programa. Referências baseadas no ponteiro de pilha ou no ponteiro de quadro usam o segmento de pilha. Outros acessos usam o segmento da área de alocação dinâmica nesse modelo simplificado.

A pilha cresce em direção aos endereços mais baixos. Sua tradução precisa de um bit de direção, além de uma base e um tamanho. Neste modelo, 1 indica crescimento para cima e 0 indica crescimento para baixo. As permissões de acesso acrescentam outra verificação independente: um byte pode estar dentro dos limites e ainda assim não permitir a operação solicitada.

Trate a base da pilha como um limite superior

Para um segmento que cresce para cima, a base identifica seu primeiro byte físico. Para um segmento que cresce para baixo, a base identifica o limite imediatamente acima de seu byte físico mais alto. Na organização usada no exemplo, a base 53.248 e o tamanho 2.048 da pilha abrangem os bytes físicos de 51.200 a 53.247.

Para a janela de pilha de 4 KB selecionada por 11, converta o campo de deslocamento de doze bits em um deslocamento negativo:

O campo varia de 0 a 4.095, portanto esse deslocamento é sempre negativo. Ele é válido quando seu módulo não excede o tamanho atual da pilha. Em seguida, some o deslocamento com sinal à base.

Examine um acesso permitido à pilha

O endereço virtual 15.500 seleciona a pilha. Sua janela começa no endereço virtual 12.288, portanto seu campo de deslocamento é 3.212. Converta o campo:

A profundidade 884 está dentro do tamanho 2.048. A tradução resulta em:

Somar o valor positivo 3.212 à base apontaria para cima da pilha. O campo ainda não é o deslocamento necessário para um segmento que cresce para baixo.

O endereço virtual 13.000, por sua vez, fornece o campo 712 e o deslocamento −3.384. Sua profundidade excede 2.048, então o hardware gera uma falha. Se o sistema operacional ampliar a pilha com sucesso, o aumento de seu tamanho poderá tornar válidos mais endereços baixos.

Inclua o extremo inferior

Um deslocamento de −2.048 alcança o byte mais baixo da pilha, 51.200, e é permitido. Um deslocamento de −2.049 está fora dela. Portanto, a verificação para crescimento descendente inclui o módulo igual ao tamanho. Isso corresponde à contagem de bytes da regra para crescimento ascendente, embora essa regra exclua um deslocamento igual ao tamanho: a base ascendente é um byte, enquanto a base descendente é um limite final.

Verifique a operação solicitada

Os bits de proteção registram as permissões de leitura, escrita e execução. O código normalmente permite leitura e execução; a área de alocação dinâmica e a pilha normalmente permitem leitura e escrita. Uma escrita em código com permissão de leitura e execução causa uma falha mesmo quando seu deslocamento é válido. Executar dados também causa uma falha quando não há permissão de execução.

Código somente de leitura pode ser compartilhado. O sistema operacional pode apontar os segmentos de código de dois processos para a mesma região física e negar escritas em ambos. Os bytes de instrução ocupam uma única cópia física, enquanto cada processo mantém uma área de alocação dinâmica e uma pilha separadas.

A segmentação substitui uma região grande por várias menores. Isso evita associar memória física a lacunas virtuais vazias, mas agora o sistema operacional deve posicionar e ampliar regiões de tamanhos diferentes enquanto preserva o estado de tradução de cada processo.

Salve todas as partes do mapeamento

Em uma troca de contexto, apenas a base e o tamanho já não são suficientes. O sistema operacional salva e restaura a base, o tamanho, a direção de crescimento e as permissões de cada segmento. Restaurar uma pilha com a direção errada ou código com as permissões erradas mudaria o significado de endereços que, de outro modo, seriam idênticos.

Quando um alocador precisa de mais espaço na área de alocação dinâmica, o sistema operacional deve ampliar seu segmento físico. Bytes livres imediatamente acima dele permitem o crescimento direto. Caso contrário, o sistema operacional pode movê-lo para uma lacuna maior adequada e atualizar sua base. Se não conseguir obter uma região adequada, a ampliação falhará.

Escolha a granularidade

O Multics usava segmentação de granularidade fina. Mais segmentos permitem unidades menores de controle, mas exigem mais metadados de tradução e gerenciamento.

Encontre uma lacuna suficientemente grande

Segmentos físicos de tamanhos variáveis deixam lacunas livres de tamanhos variáveis à medida que processos começam, crescem e terminam. A fragmentação externa ocorre quando há bytes livres suficientes no total, mas nenhuma lacuna individual pode conter o segmento solicitado.

Suponha que as lacunas livres tenham 8 KB, 6 KB e 10 KB. Seu total é 24 KB. Um segmento de área de alocação dinâmica de 12 KB ainda não cabe: a maior lacuna disponível tem apenas 10 KB. Juntar as lacunas no papel não torna seus endereços físicos adjacentes.

A compactação pode corrigir essa organização. O sistema operacional pausa os processos, copia os segmentos para ficarem lado a lado e atualiza suas bases. Os endereços virtuais continuam funcionando porque a tradução oculta as movimentações físicas. O resultado é uma grande região livre contígua, mas a cópia é custosa e novas alocações podem fragmentar a memória novamente.

Políticas de alocação como primeiro ajuste e melhor ajuste procuram limitar sobras inadequadas sem copiar. Nenhuma política de alocação de tamanhos variáveis elimina a fragmentação externa para toda sequência de requisições. Um único segmento grande também pode desperdiçar espaço dentro de sua própria extensão quando apenas partes dispersas são usadas.

Reconheça o modelo nos sistemas modernos

A paginação divide a memória em partes de tamanho fixo e evita exigir que cada região lógica ocupe uma única lacuna física. O modelo de segmentação continua útil para entender regiões, proteção e compartilhamento. No modo de 64 bits do x86-64, as bases comuns dos segmentos de código, dados e pilha funcionam como zero e seus limites não são verificados; FS e GS mantêm bases úteis para dados específicos de cada thread ou CPU. Uma mensagem de acesso inválido chamada falha de segmentação não significa que o modelo clássico de três segmentos esteja ativo.

O gerenciamento de espaço livre registra a memória disponível e escolhe onde cada requisição será colocada. Requisições de mesmo tamanho podem usar uma lista de blocos intercambiáveis. Tamanhos variáveis são mais difíceis: tanto um alocador da área de alocação dinâmica quanto um sistema operacional que posiciona segmentos devem encontrar um bloco contíguo grande o suficiente para a próxima requisição.

Localize a fragmentação externa

Considere uma região de 60 bytes com os bytes de 0 a 19 livres, um bloco alocado de 20 a 39 e os bytes de 40 a 59 livres. Há quarenta bytes livres, mas nenhuma das lacunas livres pode conter uma requisição de 25 bytes. O bloco ativo do meio impede que essas lacunas sejam tratadas como uma única região.

Isso é fragmentação externa: há capacidade livre fora dos blocos alocados, mas sua disposição a torna inutilizável para uma determinada requisição contígua. Os bytes livres não desapareceram. Eles ainda podem atender a requisições menores ou se tornar úteis quando os blocos intermediários forem liberados.

Localize a fragmentação interna

Um alocador que arredonda requisições para múltiplos de 16 fornece um bloco de 32 bytes para uma requisição de 20 bytes. Os 12 bytes adicionais ficam dentro de uma alocação já fornecida. Esse desperdício é fragmentação interna.

O espaço não usado entre a área de alocação dinâmica e a pilha em uma posição de base e limite é outro exemplo. A alocação de blocos parceiros introduz o mesmo tipo de desperdício quando arredonda para potências de dois. O nível de gerenciamento é diferente, mas a localização do espaço não usado é a característica decisiva.

Um alocador pode sofrer os dois tipos. Arredondar uma requisição pode desperdiçar bytes dentro de seu bloco enquanto outros blocos livres permanecem separados em outro lugar.

Una blocos livres vizinhos sem mover dados ativos

A coalescência une blocos livres fisicamente adjacentes. Se o bloco do meio na região de 60 bytes for liberado, as três partes poderão formar uma única lacuna de 60 bytes. Se o bloco do meio continuar alocado, a coalescência não poderá atravessá-lo. A união reduz a fragmentação externa, mas não garante uma lacuna suficientemente grande para toda requisição.

Adicionar mais memória a uma área de alocação dinâmica pode aliviar a pressão, mas não muda os endereços dos blocos ativos existentes. Sua disposição ainda pode deixar pequenas lacunas inutilizáveis.

Explique por que o sistema operacional pode compactar segmentos

O sistema operacional pode copiar segmentos físicos e atualizar suas bases. Os programas mantêm endereços virtuais, portanto o mapeamento pode ocultar essas movimentações. Um alocador geral de C para a área de alocação dinâmica não tem uma camada de tradução entre os ponteiros retornados e as localizações dentro da área. Um programa pode ter copiado um ponteiro para muitos objetos, e o alocador não consegue descobrir e reescrever cada cópia.

Mover um bloco ativo da área de alocação dinâmica por conta própria deixaria esses ponteiros apontando para sua localização antiga. Consequentemente, o gerenciamento comum com malloc mantém blocos ativos nos endereços retornados até que sejam liberados. Ele deve controlar a fragmentação por meio de alocação, reutilização, divisão e união do espaço livre.

Uma lista de blocos livres registra blocos livres por endereço e tamanho. A alocação divide um bloco ou o remove da lista; a liberação devolve um bloco e pode uni-lo aos vizinhos. A convenção de tamanho importa: um tamanho registrado pode significar a área útil utilizável ou o bloco inteiro, incluindo metadados.

Divida e una intervalos simples

Primeiro ignore os cabeçalhos. Em uma região de 60 bytes com entradas livres (0, 20) e (40, 20), uma requisição de 8 bytes colocada no início retorna o endereço 0. As entradas restantes são (8, 12) e (40, 20).

Partindo novamente da organização original, libere os bytes alocados do meio, de 20 a 39. Sem união, três entradas de 20 bytes ainda não podem atender individualmente a uma requisição de 30 bytes. A coalescência de intervalos adjacentes produz (0, 60), que pode atendê-la. A ordem de endereço ajuda o alocador a reconhecer vizinhos; a proximidade na lista, por si só, não basta se seus intervalos físicos não forem contíguos.

Recupere o cabeçalho a partir do ponteiro do usuário

free(ptr) não recebe um tamanho. Um alocador simples armazena um cabeçalho de tamanho imediatamente antes da área útil, às vezes com um valor de verificação ou número mágico. Subtrair o comprimento do cabeçalho permite encontrar os metadados.

Com um cabeçalho de 16 bytes, uma requisição de 96 bytes ocupa 112 bytes no total. O programa recebe um ponteiro 16 bytes após o início do bloco. Liberá-lo devolve toda a extensão de 112 bytes, incluindo o cabeçalho, para gerenciamento futuro. O alinhamento pode acrescentar arredondamento; os tamanhos deste exemplo já atendem ao alinhamento de 16 bytes.

Acompanhe uma lista de blocos livres embutida

Suponha que uma área de alocação dinâmica de 4.096 bytes comece em 32.768. Um nó livre usa 16 bytes e registra os bytes utilizáveis após o nó. Inicialmente, ele registra 4.080 bytes utilizáveis.

Três requisições de 96 bytes consomem 112 bytes cada:

O nó livre restante começa em 33.104. Seu tamanho utilizável é de 3.744 bytes. A contabilização é:

Liberar o ponteiro 32.896 leva ao cabeçalho 32.880. Esse bloco se torna um nó livre com 96 bytes utilizáveis. Ele não pode se unir ao nó final em 33.104 porque a terceira alocação está entre eles. Quando as três alocações são liberadas e unidas por coalescência, um único nó volta a descrever 4.080 bytes utilizáveis. A incorporação dos antigos cabeçalhos internos torna seus bytes disponíveis dentro da extensão resultante da união.

Mantenha os registros dentro da região gerenciada

Nós de lista embutidos ficam na própria memória livre, portanto gerenciar a lista não exige uma alocação separada para cada entrada. O nó contém um tamanho e uma ligação para o próximo bloco livre. Se nenhum bloco couber, o alocador pode requisitar mais memória com sbrk ou mmap; se não conseguir obter memória suficiente, o resultado será NULL.

Um estouro pode sobrescrever um cabeçalho ou nó vizinho. Isso explica por que a falha visível pode ocorrer durante uma chamada posterior a malloc ou free, depois da escrita que danificou a lista.

Uma política de alocação escolhe entre blocos suficientemente grandes para uma requisição. Escolhas diferentes deixam lacunas diferentes para requisições futuras. O tempo de busca importa junto com a fragmentação, e nenhuma política vence para toda carga de trabalho.

Compare as regras de busca

Para melhor e pior ajuste, uma lista simples não ordenada exige uma busca completa. Outras estruturas podem encontrar tamanhos adequados mais rapidamente. Primeiro ajuste significa o primeiro na ordem escolhida para a lista, o que não precisa ser o menor endereço, a menos que a lista esteja ordenada por endereço.

Acompanhe a primeira requisição

Considere blocos livres de 30, 12, 50 e 20 bytes em ordem de endereço. Ignore os cabeçalhos e suponha que a divisão possa preservar cada sobra. Uma requisição de 18 bytes altera a lista da seguinte forma:

• O melhor ajuste usa 20 e deixa 30, 12, 50, 2.
• O pior ajuste usa 50 e deixa 30, 12, 32, 20.
• O primeiro ajuste usa 30 e deixa 12, 12, 50, 20.
• O próximo ajuste, começando no quarto bloco, usa 20 e deixa 30, 12, 50, 2.

O próximo ajuste precisa de uma posição inicial para determinar sua escolha. O nome, por si só, não implica a primeira entrada da lista. Um acompanhamento deve manter esse estado de busca entre requisições.

Veja por que a próxima requisição muda a avaliação

Uma requisição seguinte pede 45 bytes. O melhor ajuste e o primeiro ajuste preservaram o bloco de 50 bytes, então ambos atendem à requisição. O maior bloco restante do pior ajuste tem 32 bytes, então ele falha apesar dos 94 bytes livres no total:

Essa falha é fragmentação externa. A decisão anterior dividiu a única lacuna suficientemente grande. Por outro lado, o melhor ajuste deixou uma pequena sobra de 2 bytes que pode ser pequena demais para requisições futuras úteis. Uma sobra imediata pequena não prova que uma política usará bem o espaço ao longo de toda a sequência de requisições.

Equilibre política e estrutura de dados

Percorrer milhares de entradas pode ser custoso mesmo quando cada escolha de alocação é boa. Alocadores práticos agrupam blocos por tamanho ou usam estruturas de busca, como árvores balanceadas. Uma lista ordenada por endereço também favorece a coalescência ao facilitar a localização de vizinhos físicos.

O mecanismo de alocação: encontrar, dividir e atualizar metadados, pode permanecer o mesmo enquanto a política muda. Para comparar políticas de forma justa, acompanhe as mesmas requisições e liberações, mantenha fixas as regras de sobrecarga e considere tanto as lacunas resultantes quanto a quantidade de busca.

A busca geral em listas de blocos livres é flexível, mas pode ser custosa. Alocadores especializados tornam as requisições comuns previsíveis ao agrupar tamanhos, manter objetos reutilizáveis ou restringir tamanhos de blocos a potências de dois.

Reutilize tamanhos frequentes e objetos inicializados

Listas segregadas mantêm listas de blocos livres separadas para tamanhos frequentes, com um alocador geral para outras requisições. Uma requisição de tamanho comum pode ser atendida diretamente por um bloco de sua lista. Blocos de mesmo tamanho não criam fragmentação externa entre si, mas a divisão da capacidade entre listas é uma escolha de política: blocos disponíveis de um tamanho podem não atender a outro tamanho.

Um alocador slab mantém um cache de objetos para um tipo de objeto do núcleo usado repetidamente, como um nó-i, uma trava ou um descritor de processo. Um slab é dividido em objetos desse tipo. O cache obtém mais slabs quando necessário e pode devolver um slab totalmente livre a um alocador geral. Jeff Bonwick projetou essa abordagem para o Solaris.

O cache mantém os objetos liberados em estado inicializado, evitando preparação e destruição repetidas. Isso economiza tempo além do gasto na própria busca.

Divida uma região de blocos parceiros

Um alocador binário de blocos parceiros começa com uma região cujo tamanho é uma potência de dois e arredonda cada requisição para um tamanho de bloco que seja potência de dois. Ele divide repetidamente um bloco livre em metades iguais até que uma metade tenha o tamanho mínimo adequado. As duas metades de uma divisão são blocos parceiros.

Para uma requisição de 5 KB em uma região de 64 KB, arredonde 5 KB para 8 KB. Divida 64 em dois blocos de 32 KB, depois os 32 escolhidos em dois blocos de 16 KB e, então, os 16 escolhidos em dois blocos de 8 KB. Retornar o primeiro bloco de 8 KB deixa blocos parceiros livres nos deslocamentos 8 KB, 16 KB e 32 KB, com tamanhos de 8 KB, 16 KB e 32 KB, respectivamente.

A alocação desperdiça 3 KB dentro de seu bloco de 8 KB. Isso é fragmentação interna, aceita em troca de divisão e união regulares.

Encontre o único parceiro permitido para união

Usando deslocamentos medidos a partir do início da região gerenciada:

O ou exclusivo inverte o bit correspondente ao tamanho do bloco. Para um bloco de 8 KB no deslocamento 0, seu parceiro está no deslocamento 8.192. Para um bloco de 16 KB no deslocamento 16.384, seu parceiro está em 0.

Quando o primeiro bloco de 8 KB é liberado, ele se une a seu parceiro livre de 8 KB. O bloco de 16 KB resultante pode se unir a seu parceiro livre e, depois, o bloco de 32 KB resultante pode se unir novamente. A união para se o parceiro necessário de mesmo tamanho estiver em uso. Estar adjacentes e livres não é suficiente quando dois blocos não são parceiros da mesma divisão.

Uma requisição de 20 KB recebe 32 KB, desperdiçando 12 KB, ou 37,5% do bloco. O Linux combina a alocação de blocos parceiros para memória física com caches de objetos do tipo slab. Alocadores para múltiplas threads também usam caches locais ou múltiplas arenas para reduzir a espera por uma única trava de alocação compartilhada; glibc, jemalloc e tcmalloc usam versões dessas ideias.