Memória virtual e tradução

O pai e o filho podem usar o endereço virtual 0x1000 para dados privados diferentes. A MMU, unidade de gestão de memória, traduz cada acesso com o mapa do processo e verifica permissões. Seguiremos um endereço desde a separação em página e deslocamento até à moldura física, distinguindo o custo da tradução do custo de trazer dados para RAM.

Hierarquia de memória

Os registos guardam operandos junto da CPU. As caches conservam cópias de dados e instruções para reduzir acessos à RAM. A RAM guarda as páginas residentes; ficheiros e swap podem guardar dados que terão de ser preparados antes do uso. Em geral, os níveis mais próximos da CPU têm menor capacidade e menor latência.

Uma cache de dados e o TLB têm funções diferentes: a primeira guarda conteúdo; o segundo guarda traduções. Um miss numa delas não prova falta na outra. Nos exercícios de tempos, identifica quais destes custos o modelo inclui.

Endereço virtual e físico

O endereço virtual é o que o processo usa. O físico identifica a posição na memória física. Dois processos podem usar o virtual 0x1000 e traduzi-lo para molduras diferentes. Também podem mapear uma página partilhada em endereços virtuais distintos.

A associação pode acontecer em compilação, se o destino estiver fixo; no carregamento, se o código for relocável; ou em execução, com tradução por hardware. A tradução em execução permite mudar a colocação física sem mudar os endereços usados pelo programa.

O tamanho máximo do espaço virtual não mede RAM atribuída. Páginas podem estar ausentes, regiões podem não ter mapeamento e o hardware pode implementar menos bits de endereço do que a largura dos registos. Um registo de 64 bits não garante $2^{64}$ bytes utilizáveis pelo processo.

Base, limite e alocação contígua

Num modelo simples, o virtual $v$ é válido se $0 \leq v < L$, sendo $L$ o limite em bytes. O físico é $b+v$, sendo $b$ a base. Só o núcleo pode mudar estes registos.

Para $b=12000$ e $L=2000$, $v=1500$ traduz para 13500; $v=2000$ é inválido, apesar de a soma 14000 existir. O limite é exclusivo neste modelo.

Na alocação contígua, cada processo ocupa uma região física. Parte de um buraco de 500 KiB para um pedido de 212: ficam 288 livres, mas noutra posição da lista. É esta evolução dos buracos que a tabela regista passo a passo. First-fit escolhe o primeiro suficiente, best-fit o menor suficiente e worst-fit o maior.

Com buracos de 100, 500, 200, 300 e 600 KiB, por esta ordem, uma sequência de pedidos 212, 417 e 112 KiB dá:

Política	Colocação de 212	Colocação de 417	Colocação de 112
First-fit	Buraco 500, sobram 288	Buraco 600, sobram 183	Resto 288, sobram 176
Best-fit	Buraco 300, sobram 88	Buraco 500, sobram 83	Buraco 200, sobram 88
Worst-fit	Buraco 600, sobram 388	Buraco 500, sobram 83	Resto 388, sobram 276

Fragmentação externa significa haver espaço total mas não uma região contígua suficiente. Fragmentação interna é espaço dentro de uma unidade atribuída que não é usado. Compactar aproxima regiões ocupadas para reunir buracos, mas exige relocação adequada e cuidado com I/O em curso.

Segmentação

Um endereço segmentado contém número de segmento e deslocamento. A tabela guarda base, limite e permissões de cada segmento. O segmento pode representar código, dados ou pilha e ter dimensão diferente dos restantes.

Para o segmento 2 com base 8000 e limite 400, o par (2, 350) traduz para 8350. (2, 400) viola o limite. Segmentos de tamanho variável podem sofrer fragmentação externa. Paginação e segmentação também podem ser combinadas: primeiro identificar a região lógica, depois traduzir as suas páginas.

Paginação

O espaço virtual divide-se em páginas de tamanho $P=2^n$ bytes. A RAM divide-se em molduras do mesmo tamanho. Uma tabela de páginas indica que moldura corresponde a cada página virtual e guarda estado e permissões.

Para um endereço virtual $v$:

$$p=\lfloor v/P\rfloor,\quad d=v\bmod P,\quad f=\operatorname{tabela}[p],\quad a=fP+d.$$

$p$ é a página, $d$ o deslocamento, $f$ a moldura e $a$ o físico. O deslocamento passa sem alteração porque indica a posição dentro da página, e as páginas têm todas o mesmo tamanho. Com endereços de $m$ bits, $n$ bits ficam para o deslocamento e $m-n$ para a página.

Com páginas de 4 KiB, $P=4096=2^{12}$. O virtual 0x1A3F5 divide-se em página 0x1A e deslocamento 0x3F5. Se a página está na moldura 0x07, obtemos 0x073F5. Em decimal, $7\times4096+1013=29685$.

Na demo, o espaço virtual tem 64 bytes e a tabela associa as páginas às molduras 3, 0, 5, 1, 7, 2, 6 e 4. Para cada tamanho, só usamos as primeiras $64/P$ entradas da tabela. Todas as páginas do espaço têm permissão de leitura. Muda o tamanho da página e observa que o mesmo endereço passa a ter outra decomposição. Desmarcar presença representa uma página válida que ainda precisa de ser preparada, não um endereço proibido.

Com página de 16 bytes e virtual 45, $p=2$, $d=13$, $f=5$ e físico 93. Este modelo não simula caches nem o custo de uma falta de página.

Fragmentação e tamanho das tabelas

Um objeto de 10000 bytes, assumindo uma região alinhada ao início de página, precisa de $\lceil10000/4096\rceil=3$ páginas. São 12288 bytes de capacidade, com 2288 não usados no fim. A paginação evita exigir contiguidade entre as molduras atribuídas ao processo, mas conserva fragmentação interna.

Uma tabela linear para 32 bits e páginas de 4 KiB tem $2^{20}$ entradas. Com 4 bytes por entrada, ocupa 4 MiB. Páginas maiores reduzem o número de entradas e podem melhorar o alcance do TLB, mas podem aumentar desperdício interno.

Uma tabela multinível reparte o índice. Com 32 bits, páginas de 4 KiB e entradas de 4 bytes, um bloco de tabela guarda $4096/4=1024$ entradas, selecionadas por 10 bits. Dividimos os 20 bits de página em dois campos de 10; os 12 restantes continuam a ser o deslocamento.

O endereço 0x00403F5D decompõe-se assim:

Campo	Cálculo	Valor
Índice exterior	$\lfloor v/2^{22}\rfloor$	1
Índice interior	$\lfloor v/2^{12}\rfloor \bmod 1024$	3
Deslocamento	$v \bmod 4096$	0xF5D = 3933

A entrada exterior 1 aponta para uma tabela interior. Se a entrada 3 dessa tabela indicar a moldura 7, o físico é $7\times4096+3933=32605$, ou 0x7F5D. Os índices escolhem onde procurar a tradução; não se somam à moldura.

Se só esta região de 4 MiB estiver mapeada com páginas normais, basta uma tabela exterior e uma interior: 8 KiB de tabelas, em vez dos 4 MiB da tabela linear completa. As outras entradas exteriores podem indicar regiões sem tabela. O percurso pode exigir duas leituras de tabela antes do dado quando não há TLB nem caches de percurso.

Uma tabela hashed pesquisa por número de página virtual e identifica a tradução nas colisões. Uma tabela invertida guarda uma entrada por moldura física, incluindo a identidade do processo e da página. Poupa espaço para espaços virtuais enormes, mas muda o custo de pesquisa e exige representar partilhas.

TLB e tempo efetivo

O TLB é uma cache de traduções. Um miss obriga a obter a tradução; não significa que o dado esteja fora da RAM. Uma falta de página é outra situação. Identificadores de espaço, como ASID, podem distinguir entradas de processos; sem isso pode ser necessário invalidá-las ao mudar de contexto.

Suponhamos uma tabela de um nível, acesso ao TLB de $t=5$ ns, memória de $M=80$ ns, taxa de acerto $h=0,95$, sem caches adicionais nem faltas de página. Um acerto custa $t+M=85$ ns; um miss custa $t+2M=165$ ns:

$$EAT=h(t+M)+(1-h)(t+2M)=89\text{ ns}.$$

Não apliques esta fórmula sem verificar o modelo. Se a consulta ao TLB estiver incluída no tempo de acesso, não a somes outra vez. Tabelas multinível ou caches de percursos mudam o custo do miss.

O alcance do TLB é aproximadamente número de entradas vezes tamanho de página. 64 entradas de 4 KiB cobrem 256 KiB de páginas distintas. Ultrapassar esse alcance pode aumentar misses do TLB sem aumentar faltas de página.

Presença, permissões e partilha

Uma página pode estar mapeada mas ausente da RAM, presente mas só para leitura, ou não pertencer ao espaço válido. As designações valid e present variam entre modelos; lê a definição do bit no enunciado. Não uses um único bit para concluir que toda a ausência é acesso ilegal.

Código imutável de bibliotecas pode partilhar molduras entre processos com proteção contra escrita. Dados privados depois de fork podem partilhar molduras apenas até uma escrita provocar copy-on-write. A próxima página explica o que acontece quando faltam molduras e é preciso substituir páginas.