Gerenciamento de Memória: Fragmentação, Paginação e Swap

Fragmentação interna

Fragmentação interna é quando sobra espaço dentro de uma partição de memória que não consigo utilizar.

Solução — alocar dinamicamente a memória para que não haja desperdício.

Fragmentação externa

Fragmentação externa é quando sobra espaço entre dois espaços alocados que não consigo utilizar.

Solução — utilizar mecanismos que alocam espaço de forma que não sobre espaço livre fragmentado.

Aglutinação e Compactação

Aglutinação — pegar os espaços vazios vizinhos e juntar em um só.

Compactação — deslocar processos para outro espaço de modo que a fragmentação diminua.

Cálculo da fragmentação interna

Calcular a fragmentação interna: alocar os processos nas partições e ver quanto sobra de cada partição.

Algoritmos de alocação

• Best-fit — na hora de alocar procura o menor buraco onde o processo cabe.
• Worst-fit — aloca no maior buraco disponível.
• First-fit — aloca no primeiro local encontrado onde o processo caiba.
• Next-fit — pega o próximo local livre a partir do último local alocado.

Swap

Swap é um mecanismo do sistema operacional (S.O.) para mover processos para o disco a fim de liberar espaço na memória. É usado quando a memória estiver cheia e for necessário liberar espaço.

Unidades e potências de 2

Relação entre potências de 2, unidades em KB/MB e bytes:

2^10 = 1 KB = 1 024 bytes
2^11 = 2 KB = 2 048 bytes
2^12 = 4 KB = 4 096 bytes
2^13 = 8 KB = 8 192 bytes
2^14 = 16 KB = 16 384 bytes
2^15 = 32 KB = 32 768 bytes
2^16 = 64 KB = 65 536 bytes
2^17 = 128 KB = 131 072 bytes
2^18 = 256 KB = 262 144 bytes
2^19 = 512 KB = 524 288 bytes
2^20 = 1 MB = 1 048 576 bytes
2^21 = 2 MB = 2 097 152 bytes
2^22 = 4 MB = 4 194 304 bytes
2^23 = 8 MB = 8 388 608 bytes
2^24 = 16 MB = 16 777 216 bytes
2^25 = 32 MB = 33 554 432 bytes
2^26 = 64 MB = 67 108 864 bytes
2^27 = 128 MB = 134 217 728 bytes
2^28 = 256 MB = 268 435 456 bytes

Exercício: definir esquema de endereçamento por paginação

Defina um esquema de endereçamento usando paginação que permita endereçar uma memória de 128 MB, usando páginas de 4 KB.

Endereço lógico = 27 bits, porque 2^27 = 128 MB.

Deslocamento = 12 bits, porque 2^12 = 4 KB.

Bits para endereçar páginas = 27 − 12 = 15 bits.

Número de páginas = 2^15.

Páginas grandes

Vantagens — a tabela de páginas é menor.

Desvantagens — maior fragmentação interna.

Cálculos de probabilidade e utilização

N = 4 programas
P = 0,5 é a probabilidade de estar fazendo entrada/saída
Desperdício = p^n

Exemplo de potências de 0,5: 0,5^1 = 0,5; 0,5^2 = 0,25; 0,5^3 = 0,125; 0,5^4 = 0,0625; 0,5^5 = 0,03125; 0,5^6 = 0,015625; 0,5^7 = 0,0078125; 0,5^8 = 0,00390625; 0,5^9 = 0,001953125; 0,5^10 = 0,000976563; 0,5^11 = 0,000488281.

Aumento na taxa de utilização (exemplo)

N = 3 programas
P = 0,6

Fu = 1 − p^n = utilização atual

Adicionando 1 MB cabe mais 2 processos de 512 KB (supondo que processos rodem a 512 KB).

Fu = 1 − p^n (posterior)

Posterior − atual = aumento na utilização.

Memória virtual

• Memória virtual permite carregar partes do programa para ser executado sem precisar ter todo o programa em memória.
• Carga inicial do programa é mais rápida.
• Permite que mais programas sejam carregados em memória.
• Partes inúteis do programa não são carregadas.

Paginação versus segmentação

Na paginação o processo é quebrado em pedaços de tamanho fixo. Na segmentação o processo é dividido em segmentos de tamanhos variados.

Page fault

Page fault é quando uma página não está carregada na memória (ocorre em memória virtual).

Ocorre quando tento acessar uma página que ainda não está carregada na memória. A MMU gera uma interrupção, o S.O. carrega a página do disco para a memória e o programa retoma a execução.

Quando isso ocorre, o programa fica parado aguardando a finalização do S.O.

Fragmentação interna e tradução de endereços

Fragmentação interna ocorre, possivelmente, na última página.

Tradução do endereço lógico para endereço físico:

endereço lógico / tamanho da página = número do bloco (página); o restante é o deslocamento dentro da página.

Política de substituição de páginas

Quando a memória fica cheia e é necessário carregar uma nova página, alguma página que está na memória terá que ser removida — essa é a política de substituição de páginas.

Bit de modificação — indica que houve uma operação de escrita naquela página (também chamado de bit M).

Acesso à memória e locality

Programas estruturados acessam a memória em regiões subsequentes (localidade espacial/temporal). Programas não estruturados tendem a acessar a memória em partes diversas, o que pode gerar mais page faults.

Algoritmos de substituição (resumo)

• NRU — não recentemente usada (usa bits R e M).
• LRU — menos recentemente usada (última referência).
• Segunda chance — similar ao FIFO, mas verifica o bit R; se R = 1, zera R e dá uma segunda chance à página, passando para a próxima.