Conceitos de Mem�ria Virtual
Vantagens:
- Executar programas maiores que o tamanho da mem�ria.
- Executar programas carregados parcialmente.
- Permitir mais do que um programa ao mesmo tempo.
- Permitir c�digo independente de posi��o.
- Libertar programadores da aloca��o de mem�ria.
- Permitir partilha
VM em Unix
- Originalmente segmentos de 64KB(+64KB):
- programadores faziam "software overlay";
- Swapping usado para libertar espa�o;
- Pagina��o sobre demanda: 3BSD no VAX 11 (1978);
- Nova vers�o em SunOS 4 influenciou o desenvolvimento de pagina��o para SVR4 e Solaris;
- Paginador para Mach foi eventualmente adaptado para BSD4.4.
Requerimentos
Precisamos de:
- Gest�o do espa�o do endere�os do processo;
- Tradu��o de endere�os (via MMU e PF);
- Gest�o optimizada da mem�ria f�sica;
- Prote��o de mem�ria:
- processos n�o podem ler p�ginas do kernel ou de outros processos;
- Partilha de Mem�ria:
- partilha de parte do espa�o de endera�amento;
- partilha de frames (eg, depois de fork()).
- Reagir bem a cargas elevadas.
�rea de Swap
Precisamos de
- swap-map para descrever a posi��o de p�ginas swapped;
- N�o � preciso guardar p�ginas de texto.
Mapas de Tradu��o
Precisamos de v�rios mapas:
- Tradu��es de endere�os em HW: podem ser TLBs e/ou tabelas de p�ginas, depende do HW mas gerido por SO;
- Mapa de espa�os de endere�os: usado num PF para verificar se a p�gina � v�lida e carregar uma tradu��o de HW;
- Mapa da mem�ria f�sica: eg, para remover p�ginas;
- Mapa da �rea de backup, que pode ser o arquivo ou swap.
Substitui��o de P�ginas
V�rias t�cnicas s�o poss�veis:
- Ideal: p�gina morta, que nunca mais ser� usada, eg, de processo terminado;
- Local: cada processo tem um n�m de p�ginas;
- Global: olhar para sistema;
- Working Set: p�ginas que v�o ser precisas no futuro pr�ximo;
- Localidade de Refer�ncias: conj. de p�g. mais importantes muda devagar;
- LRU: libertar a p�gina acedida � mais tempo.
Suporte de HW
Unidade de Gest�o de Mem�ria (MMU):
- Tradu��o de endere�os virtuais;
- Tabelas de p�ginas:
- Uma para endere�os de kernel;
- Uma ou mais para cada processo;
- Entrada (PTE) com 32 bits e incluem n�m. de frame, info. de protec��o, se v�lida, se modificada, se referida;
- MMU usa apenas as tabelas activas;
- Erros de tradu��o geram "Page Fault" (PF):
- Endere�o fora de limites;
- P�gina inv�lida;
- Erro de Protec��o
- Problema do tamanho: 512 mil entradas para 2GB e p�g. de 4KB:
- Segmenta��o;
- Pagina��o
- Context Switch.
TLB
Cada acesso a mem�ria obrigaria a acedar PT:
- Adicionar uma cache r�pida procurada antes da PT (L0):
- Endere�o f�sico;
- Endere�o virtual (HP).
- Cache associativa com as tradu��es mais recentes, TLB:
- controlada pela MMU;
- SO tem que manter coer�ncia se mudar PT;
- Altera��es podem ser explicitas ou side-effect de instru��es;
- Alguns sistemas s� usam TLB.
Hardware x86
- Suporte para pagina��o e segmenta��o;
- 32 bits: 4GB de endere�os;
- Pagina��o pode ser desabilitada usando CR0;
- At� 8K segmentos: segment descriptor descreve o segmento que � visto pela LDT do processo mais GDT global;
- Unix s� usa segmenta��o para prote��o de mem�ria, entrada no kernel, e mudan�a de contexto:
- Todos segmentos do usu�rio t�m base 0 e tamanho grande;
- seg. especiais: call gate para entrada no kernel e task state segment para contexto.
Hardware x86: Pagina��o
- Dois n�veis de p�ginas;
- Direct�rio de p�ginas: cont�m PTEs que mapeiam as pr�prias p�ginas (1024 de 4B);
- CR3 ou PDBR armazena endere�o f�sico de dir;
- Cada PTE cont�m p�g f�sica, RW, e se v�lido, referido e modificado;
- Escrita em CR3 faz reset da TLB;
- 4 n�veis de privil�gio.
Hardware: RS/6000
- RS/6000 usa tabela de p�ginas invertida:
- Entrada por frame;
- Hash � usada para encontrar p�gina virtual;
- Compacto, mas lento;
- RS/6000 usa espa�o de endere�os de 52-bits;
- Processo tem 16 segmentos:
- kernel text;
- user text;
- dados privados;
- dados partilhados (7);
- dados de VM (2);
- texto partilhado;
- dados do kernel;
- I/0.
- 4 bits de cima s�o convertidos em 24 bits de selec��o.
VM em 4.3BSD
Baseado no 3BSD:
- Originalmente para VAX-11: emula��o da arquitectura do VAX em sofware;
- Estruturas:
- core map descreve mem�ria f�sica;
- page tables descrevem mem�ria virtual;
- disk maps descrevem �reas de swap;
- proc e u-area.
Mem�ria F�sica
Tr�s �reas:
- Nonpaged pool: c�digo do kernel e mem�ria do kernel alocada est�ticamente;
- Error buffer: mensagens de erro em crash;
- P�ginas de processos e p�ginas de mem�ria din�mica do kernel (nonpageable).
- Nome processo dono, tipo, e VPN:
- dono de p�g de texto � uma estrutura texto;
- Lista de P�ginas Livres
- Cache de P�ginas de Texto
- Sincroniza��o
Espa�o de Endere�amento
Emula VAX-11:
- 4 �reas iguais, P0: texto e dados do processo; P1: pilha de kernel e usu�rio, u-area; S0: texto e dados do kernel; S1: n�o � usada.
- PTs com formato baseado no VAX:
- 1 de sistema para S0;
- cd processo tem mapa P0 e P1;
- Cont�guas em mem�ria virtual e alocadas por mapa em Userptmap de S0;
- Mapa de recursos <base,size> descreve �rea que est�o usadas (first-fit);
- Swapper � usado para libertar entradas em Userptmap
- Partilha em P0 � poss�vel em regi�es alinhadas com 64KB, mas complicada: partilha explicita.
Vida de P�gina
3 Estados:
Residente: em mem�ria f�sica;bits v�lido e fill-on-demand a 0, e PFN a 0.
Espa�o de Swap
Parti��es cruas, sem filesystem
- V�rias parti��es: usa interleaving para melhorar performance;
- Aloca��o de swap apenas para p�ginas que v�o ser enviadas: reduz swap
- pode levar a memory overcommit;
- BSD � conservador: kernel aloca espa�o necess�rio � partida.
- P�ginas de texto n�o precisam de swap, d� problema:
- inicialmente bloco est� na PTE;
- Reescrito com PFN quando p�gina trazido;
- P�ginas s�o guardadas em swap.
- Aloca��o usa estrutura dmap:
- array de tamanho fixo com chunks no swap;
- u-area guarda mapas para dados e swap;
- texto em text structure.
fork() em BSD
Gest�o de Mem�ria:
- Aloca��o de swap para dados e pilha;
- aloca��o de PTEs em Userptmap, sen�o swapping de outro processo;
- �rea-u � inicializada e colocada no map Forkmap;
- Regi�o de texto: filho � adicionado aos processos usando esta estrutura;
- Dados e texto s�o copiados p�g a p�g.
- Copy-on-write: obriga a contadores de refer�ncia por p�gina;
- vfork() apenas cria u-area e proc, muito r�pido.
PF em BSD
Numa PF o sistema guarda informa��o de estado e chama rotina de PF:
- Se viola��o de limites, SIGSEGV ou aumenta pilha, sen�o chama pagein();
- Se simula��o de referenced, coloca valid a 1;
- Se PF residente mas na free lista, valid a 1 e entrada cmap fora de free list;
- Se p�g de texto e
outro processo est� a ler: locked e in-transit; usa wanted e sleep()
- segundo processo pode ter perdido a p�g.
- Procurar tabela de hash para p�ginas de texto que n�o na PTE;
- Ler do swap se em swap;
- Alocar e colocar a 0s para zero-fill;
- Ler de execut�vel para fill-from-text: primeiro na buffer-cache, se l� flush, ler de disco.
Lista de P�ginas Livres
Se mem�ria cheia, qual a melhor p�g para remover?
- P�g de processo terminados;
- Sen�o usar LRU:
- LRU completo � imposs�vel;
- NRU: rel�gio com 2 m�os, uma desactiva bit referido e outra verifica o bit.
- kernel mant�m p�ginas livres entre minfree e maxfree com pagedaemon:
- mapeia p�ginas no seu espa�o de endere�amento;
- escreve directamente no swap;
- usa write ass�ncronos;
- em completion coloca na lista limpa donde s�o retornados para lista de mem�ria livre.
Swapping
Sistema geralmente funciona bem, mas
- Carga pesada pode entrar em thrashing: n�o conseguimos manter todos os working sets em mem�ria;
- Solu��o: desactivar processos com swapper:
- se Userptmap est� muito fragmentado libertar um processo corrente;
- Se freemem abaixo de limites desej�veis por muito tempo;
- Se processo inactivo por muito tempo.
- Candidatos:
- processo que dorme h� mais de 20 segundos;
- dos 4 maiores, o que est� em mem. h� mais tempo.
BSD: Conclus�es
Boa funcionalidade e poucas exig�ncias sobre HW, mas:
- N�o h� acesso a arquivos remotos;
- N�o h� partilha de mem�ria;
- vfork() limitado;
- Cada processo com PT para texto partilhado: gasto extra e sincroniza��o;
- Arquivos mapeados em mem�ria e librarias partilhadas?
- Breakpoints do debugger causam confus�o.
- Aloca��o de swap muito conservadora;
- Swap remoto;
- Influ�ncia do VAX;
- C�digo n�o � modular.
VM em SVR4/Solaris
Ideias:
- Mapeamento de Arquivos (privados e partilhados):
- Util para usu�rios;
- mas n�o substitui read e write;
- Fundamental no kernel.
- Unifica��o de Acesso a ficheiros e de mem�ria virtual: evitar chamadas excessivas a SO.
- Permitir swapping din�mico em ficheiros.
- Partilha de Mem�ria entre processos: read-only e read-write.
- Estrutura orientada para objectos.
Desenho de VM em Solaris
- O espa�o de endere�amento � constituido por um conjunto de mapeamentos para diferentes
objectos.
O objecto mapeado n�o sabe do mapeamento.
- Cada objecto de mem�ria � uma sub-classe de uma classe base.
- Cada mapeamento � uma inst�ncia da sua sub-classe.
- Objectos de mem�ria podem ser associados a um n�-v (muitos para um).
- Objectos n�o associados a n�s-v s�o representados por anon, o objecto an�nimo.
- Mem�ria � baseada em p�ginas.
- P�ginas f�sicas servem como cache para objectos pageados.
- Arquitectura
de VM � independente de Unix,
componentes dependentes de HW no HAT.
- Kernel usa copy-on-write quando poss�vel.
Abstra��es Fundamentais de VM
O sistema usa
- page, p�gina;
- as, espa�o de endere�amento;
- seg, segmento;
- hat, tradu��o de endere�os em hardware;
- anon, p�ginas an�nimas:
P�gina F�sica
Mem�ria � dividida em regi�es paginadas e n�o paginadas:
- Cada page descreve p�gina l�gica (grupo de p�g f�sicas);
- p�g tem inf sobre <no-v,offset>, e est� na lista do n�-v: permite nome �nico mesmo se partilhada;
- p�g em hash-chain baseada no <no-v,offset>;
- n�-v mant�m listas de p�ginas;
- p�g pode estar na free list.
- Ref. count e flags de sincroniza��o, mais c�pias dos bits modifed e referenced;
- informa��o do HAT usada para obter todas as tradu��es da p�gina.
Espa�o de Endere�amento
proc aponta para as:
- Lista de mapeamentos do processo, seg;
- Inclui o hat;
- hint sobre o �ltimo seg. com PF;
- Flags;
- Opera��es sobre as:
- as_alloc() d� novo as;
- as_free() liberta as;
- as_dup() duplica.
- Opera��es sobre grupos de p�ginas:
- as_map() e as_unmap() coloca objectos no as;
- as_setprot() e as_checkprot();
- as_fault(), come�a PF;
- as_faulta() faz fault ahead.
Mapeamentos
Existem v�rios tipos de segmentos:- Campos p�blicos s�o base, tamanho, as;
- Fun��es virtuais em seg_ops:
- dup() duplica mapeamento;
- fault() e faulta();
- setprot() e checkprot();
- unmap() termina;
- swapout() do swapper;
- sync() sincroniza.
- Existe ainda create() que � chamado da fun��o gen�rica para alocar o segmento.
- Outras fun��es gen�ricas: libertar, attach e unmap.
P�ginas An�nimas
Criada quando processo modifica p�gina MAP_PRIVATE:- Modifica��es n�o afectam o objecto original;
- P�ginas inicializadas tornam-se an�nimas quando s�o modificadas;
- Armazenadas em swap;
- Objecto an�nimo:
- �nico no sistema;
- representa��o: v-n� NULL;
- usa swap para backup storage;
- refs a p�ginas s�o contadas;
- anon exporta dup, free, private (c�pia privada), zero e getpage.
O HAT
Opera��es dependentes do HW s�o isoladas no HAT. � acedido por uma interface:
- HAT: aloca��o, dealoca��o, dup, swapin e swapout.
- conjunto de p�ginas: hat_chgprt(), hat_unload(), hat_memload() e hat_devload() (�ltimos para uma �nica p�gina).
- todas as tradu��es de uma p�gina: hat_pageunload(), hat_pagesync().
Informa��o no HAT � redundante e altamente dependente do HW:
- Tradu��es para p�gina mantidas em lista (hat_unload());
- Ref. x86;
- Tradu��o � chamada de chunk.
Drivers de Segmentos
Existem diferentes tipos de segmentos:
- seg_vn: endere�os para ficheiros regulares ou an�nimo;
- seg_map: permite fazer acessos do tipo read e write;
- seg_dev mapeia devices como frame buffers, mem�ria.
- seg_kmem mapeia regi�es do kernel em mem�ria alocada n�o din�micamente.
seg_vn
Mapeia:
- n�-v, ou,
- an�nimos: NULL, /dev/zero
seg_vn em detalhe
Dados incluem:
- prote��es correntes e m�ximas;
- tipo de mapeamento (partilhado ou privado);
- ptr para n�-v;
- offset do segmento no arquivo;
- ptr para mapa an�nimo;
- ptr para um array de protec��es por p�gina, se pags com protec��es diferentes.
Swapping
Responsabilidade do anon layer:
- Rotina swap_xlate mapeia estruturas tipo anon e p�ginas outswapped.
- Dispositivos de swapping
podem ser colocados e removidos din�micamente do sistema por swapctl(). Cada um deles tem uma estrutura tipo swapinfo.
- Segmentos alocam todas as p�ginas de swap que v�o precisar antes de come�ar.
Mapeamento Novo
- Regi�es novas s�o mapeadas por exec ou por mmap.
- Opera��o inclui localizar o n�-v para o ficheiro, chamar VOP_MAP() , verificar se n�o h� sobreposi��o de mapeamentos, chamar as_map() que aloca um seg e chama o create() apropriado.
- Permiss�es n�o podem exceder aquelas com que o ficheiro foi o aberto.
- exec estabele mapas privados para texto, dados e pilha. Pode tamb�m incluir mapeamentos para bibliotecas partilhadas.
Gest�o de P�ginas An�nimas
- P�ginas an�nimas s�o criadas quando util. escreve para
ficheiro com MAP_PRIVATE, ou em acesso a p�ginas partilhadas.
- anon array inclui n�m de refer�ncias. P�g. s�o removidas quando n�m. de ref. desce a zero.
- As estruturas de dados s�o criadas na primeira escrita a p�g. privada.
Novo Processo
- fork() chama as_dup() para duplicar o espa�o do pai;
- as_dup() primeiro chama as_alloc() e chama o dup() de cada segmento;
- Duplica��o aloca um novo struct seg, campos s�o copiados do pai:
- mapeamntos para texto, pilha e dados s�o colocados a MAP_PRIVATE no pai e filho. MAP_SHARED continuam.
- hat_chgprot() protege contra escrita todas as p�gs an�nimas;
- anon_dup() duplica anon_map: copia todos os ptrs no array e incrementa ref counts;
- hat_dup() duplica hat e informa��o de tradu��o.
- hat_dup() pode alocar novas PTs.
Copy On Write
Uso de swap device reference array permite que partilha seja por p�gina:
Depois de PF:
Gest�o de P�ginas Livres
pagedaemon implementa rel�gio:
- m�o da frente usa hat_pagesync() para remover refer�ncia e alterar hat;
- p�ginas sujas s�o enviadas para disco por VOP_PUTPAGE(), que implementa clustering;
- hat_pageunload() invalida p�ginas que saem para lista livre
- Bit de refer�ncia pode ter que ser simulado.
Swapping
Processo swapper tem PID 0 e � chamado cada segundo:
- se mem�ria livre < t_gpgslo, envia processo para fora usando CL_SWAPOUT();
- chama as_swapout() para enviar um processo:
- chama swapout() por segmento;
- maioria dos segmentos usa segvn_swapout().
- No fim faz swap de u_area;
- Swapin: basta trazer u_area.
VM e Sistema de Arquivos
Rela��o simbi�tica:
- VOP_GETPAGE() � chamada para obter p�ginas;
- VOP_PUTPAGE() � chamada para enviar p�ginas sujas;
Vantagens
- Desenho muito modular, OO;
- Isolar HW no hat;
- suporta COW, MAP_SHARED, arquivos.
- suporta mmap();
- suporta bibliotecas partilhadas;
- beneficia do n�-v;
- Unifica buffer-cache com VM cache;
- breakpoints funcionam pq texto � MAP_PRIVATE.
Desvantagens
- Mais informa��o (40B por p�g vs. 16B);
- P�ginas de arquivos n�o s�o guardadas em swap: procura mais lenta;
- alg. mais complexos e mais lentos;
- n�o computa endere�o no disco durante exec(): procura mais lenta;
- Tuning � mais dificil por ser OO;
- COW pode ser mais lento que c�pia puura;
- Swap � alocado por p�gina, perde clustering.
Melhoramentos
Tipos de modifica��es:
- V�lido para inv�lido: propaga��o imediata;
- Inv�lida para v�lida: 2 processadores partilham a p�g,
- pregui�oso: segundo processo n�o v� transi��o;
- vs. propaga��o imediata.
- Resulta em muitos PFs, e mais lento com OO;
- COW pode ser caro: 1 em 4 p�gs t�m que ser copiadas;
N�mero de PF grande na vers�o inicial.
Optimiza��es
Alguns melhoramentos:
- Inicializar mapas de tradu��o em fork():
- filho executa sempre algum c�digo
- Inicializar parte do smapas de tradu��o depois de exec():
- para cada n�-v, inicializar as entradas para p�ginas do n�-v em mem�ria;
- � estimar o conjunto de trabalho como o conjunto de p�g em mem�ria
- Estudar o comportamento de sh e amigos para copiar algumas p�ginas imediatamente.
VM no Linux
- P�ginas s�o inicialmente COW ou zero-fill;
- vm_area descreve um segmento;
- Linux assume tabela de tr�s n�veis:
- Tabela de p�g descreve vm_obj;
- fork() copia PTEs,
- p�ginas swapped out s�o representadas na PTE,
- N�o pode fazer swap out de PTs,
- Toda a mem�ria f�sica � colocada em KVM:
- evita indirec��es,
- problemas com configura��es grandes;
- em x86 tabela do meio tem 1 entrada!
PFNs no Linux
- mem_map_t descreve p�gina f�sica:
- count � o n�mero de usu�rios;
- age � a idade;
- map_nr � o PFN.
- Aloca��o a partir de free_area
LRU no Linux
- lru_page aponta para a cabe�a da fila;
- quando p�g � libertada � colocada no fim da fila;
- shrink_mmap() tenta libertar p�ginas;
- Usa um bit de refer�ncia para manter idade:
- Idade inicial � 3;
- Quanto p�g � tocada pelo MM idade aumenta de 3;
- Envelhecimento por swap decrementa de 1
Swapping em Linux
kswapd mant�m mem�ria livre:
- Geralmente na fila kswapd_wait;
- Acordado pelo alocador quando mem�ria livre desce abaixo de certo valor:
- Tenta libertar p�ginas livres;
- Tenta diminuir dentry;
- Tenta diminuir inode;
- Tenta colocar mem�ria partilhada fora;
- Tenta libertar p�ginas sujas.
- Gestor de VM tenta n�o escrever muitas p�g no swap ao mesmo tempo;
- Aloca��o de swap � linear.