. Swapping
Esse documento representa parte dos meus estudos acerca do Livro - Operational Systems Three Easy Pieces, de dominio publico.
Ate o momento, tratamos de address spaces de tamanho pequeno que cabiam na memoria inteiramente. Agora, falaremos de alguns maiores.
Swapping
Utilizamos uma regiao de memoria secundaria (HDDs e SSDs) como um stash de memoria nao frequentemente utilizada. Uma especie de cache invertido. A presenca do swap space permite ao OS que gere uma ilusao de uma memoria virtual maor para melhor gerir concorrencia de processos.
Swap Space
Eh a regiao na memoria secundaria reservada para a troca de paginas com a memoria principal.
Present Bit
Precisamos de mecanismos para permitir esse tipo de troca de maneira eficiente. Lembremos:
acesso a memoria fisica (sem page table multinivel ou segmentacao):
- acesso ao endereco virtual eh requisitado pelo processo corrente.
- usamos n bits mais significativos do virtual address como VPN (virtual page number), o resto como offset
- olhamos o TLB (translation look-aside buffer) e verificamos se o endereco fisico esta nele. Se estiver, o endereco eh traduzido e podemos acessar a memoria fisica.
- Se nao estiver, teremos que olhar na memoria principal pelo page-table.
- Para isso, usamos o Page Table Base Register e procura pelo PTE (page table entry) usando o VPN como indice.
- Se a pagina retornada for valida e existir na memoria, extraimos o PFN (Page Frame number) do PTE, o guardamos no TLB e fazemos o acesso novamente.
Podemos, agora, utilizar de um bit identificador no PTE que indica se a pagina esta ou nao na memoria principal: o Present Bit.
Page Fault
Quando ha uma tentativa de acesso um endereco de pagina pelo TLB, ha a chance obvia de um TLB miss. Quando isso ocorre, o fluxo de erro tem q ser tratado por um componente do SO chamado de page-fault handler. Esse sistema, naturalmente, pode conferir se a pagina foi enviada para o disco buscando por uma PTE (Page Table Entry), utilizando o VPN como indice na tabela e, a partir dai, verificando o Present Bit. Se for positivo, o buscamos na memoria, se nao, atribui-se uma operacao de I/O com o endereco fisico obtido na PTE (caso haja um). Quando a operacao de I/O eh finalizada, o SO atualiza a PTE com o Present Bit, atualiza o PFN para guardar o endereco que foi pego do disco e faz novamente a instrucao de busca.
Note que enquanto estiver ocorrendo a operacao de I/O, o processo estara no estado blocked.
Page Fault Control Flow
Caso a operacao de I/O que buscou a pagina em swap retorne uma pagina, o que sera feito caso a memoria principal esteja lotada? Precisamos de alguns algoritmos para decidir quem devemos trocar da memoria principal para o swap, ou seja, a page-replacement policy.
Esse eh o flow do hardware com qualquer traducao de endereco:
VPN = (virtualAddr & VPN_MASK) >> SHIFT;
(Success, TlbEntry) = TLB_Lookup(VPN);
if (Success == true){ // TLB hit
if (CanAccess(TlbEntry.ProtectBits) == true) {
Offset = virtualAddr & OFFSET_MASK;
PhysAddr = (TlbEntry.PFN << SHIFT) | Offset;
Register = AccessMemory(PhysAddr);
}
else
raiseException(PROTECTION_FAULT);
}
else { // TLB miss
PTEAddr = PTBR + (VPN * sizeof(PTE));
PTE = AccessMemory(PTEAddr);
if (PTE.Valid == false)
raiseException(SEG_FAULT);
else { // no seg fault
if (CanAccess(PTE.ProtectBits) == false )
raiseException(PROTECTION_FAULT);
else if (PTE.Present == true) {
// if valid and present in mem
//
// assuming hardware-managed TLB
TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits);
RetryInstruction();
}
else if (PTE.Present == false) {
raiseException(PAGE_FAULT)
}
}
}Esse eh o flow do SO:
PFN = FindFreePhysicalPage();
if (PFN == -1) // no free page found
PFN = EvictPage(); // run replacement algorithm
DiskRead(PTE.DiskAddr, PFN); // sleep (waiting for I/O) -> blocked state
PTE.present = true; // update the page table with present
PTE.PFN = PFN; // bit and translation (PFN -> page frame number)
RetryInstruction(); // retry the instruction
Tratando replacement corretamente
Para sermos mais realistas, temos que falar exatamente o momento em que deviamos utilizar a politica de replacement. Apenas atualizar isso com a memoria cheia nao faz sentido, pois qualquer novo processo aberto simplesmente vai criar um overhead absurdo quando executado, vamos precisar trocar dezenas de paginas de uma vez de uma vez.
Manter uma quantidade de memoria livre urge como necessidade nesse sentido, para facilitar o gerenciamento de outros processos. A maioria dos sistemas operacionanis tem um High watermark (HW) e Low watermark (LW), que funcionam mais ou menos assim:
- tem uma thread rodando que verifica se a quantidade de memoria esta em LW. (chamada de Swap Deamon ou Page Deamon).
- se chegar a LW Paginas livres, essa thread vai trocando as paginas de acordo com a politica de replacement ate chegar em HW paginas livres.