Esse documento representa parte dos meus estudos acerca do Livro - Operational Systems Three Easy Pieces, de dominio publico.

Cache Management

Considerando que a memoria principal carrega parcialmente paginas que compoem a memoria virtual completa do sistema, podemos assumir a memoria entao como um cache. Nosso objetivo, entao, sera diminuir a quantidade de cache missess, ou seja, minimizar a quantidade de acesso a discos, que sempre eh o maior gargalo de um sistema computacional de Von Neumann.

Vamos calcular uma metrica entao, o tempo medio de acesso a memoria (AMAT - avarage mem access time):

$$AMAT = T_m + (P_{miss} \times T_d)$$

$T_m =$ Tempo de acessa a memoria $T_d =$ Tempo de acessa ao disco $P_{miss} =$ Probabilidade de ter um cache miss.

Politicas de replacement

[!hint] Os 3 C’seja

cold-start/compulsory miss -> erros de cache esperados no inicio do processo, ja que o TLB ou Cache (memoria principal) ainda nao carregaram as paginas.

capacity miss -> quando nao ha espaco no cache.

conflict miss -> nao entendi

FIFO (first-in first-out)

Primeira pagina ou batch de paginas a entrar sao as primeiras que saem. Aprox Hit Rate -> $36.4%$. ($57.1%$ tirando os misses compulsorios)

Random

Nao tem um numero preciso de miss ou hit, eh aleatorio (como o nome diz). Nem sempre eh a pior a escolha, mas eh algo pouco certo e nao faz sentido implementar num SO multiprogramacao e multiusuario.

[!warning] Problemas com algs simples

Esses Algoritmos simples geram um problema obvio. Eles simplesmente n fazem uma escolha baseada na realidade, simplesmente sequer fazer uma escolha. Assim, eles sao mais sucetiveis a tirar paginas importantes em momentos inconvenientes.

LRU (Least Recently Used) e LFU (Least Frequently Used)

Baseada no principio da localidade. Se refere ao fato da maior probalidade de uma pagina que necessita de outra estar fisicamente proxima uma da outra, seja temporalmente ou espacialmente.

Clock Algorithm (LRU)

Podemos usar o clock algorithm, que cria um bit de uso para aproximar o algoritmo LRU (Least Recently Used). Nele, as páginas da memória são organizadas em uma lista circular, e um ponteiro (mão do relógio) aponta para uma página inicial qualquer. Quando é necessário substituir uma página, o sistema verifica se o bit de uso da página atual é 1 ou 0.

  • Se for 1, significa que a página foi usada recentemente e não é um bom candidato para substituição. O bit é então zerado, e o ponteiro avança para a próxima página.

  • Se for 0, significa que a página não foi usada recentemente e pode ser substituída.

O processo continua até encontrar uma página com bit 0 ou, no pior caso, percorrer todas as páginas e zerar todos os bits antes de encontrar um candidato para substituição.

Dirty Pages

Podemos adicionar um bit para considerar se a pagina esta ou nao alterada em memoria principal e precisa de reescrita no disco. Se sim, quer dizer que eh mais custoso fazer o swap dela. Isso melhora bastante o desempenho do Clock Algorithm, ja que evita trocar pagina custosas para o SO.

Thrashing

Thrashing é uma condição em que o sistema operacional passa a maior parte do tempo fazendo swap em vez de executar processos de forma eficiente. Isso acontece quando há pouca memória RAM disponível e muitos processos precisam ser carregados simultaneamente, resultando em um número excessivo de page faults.

Bibliografia

https://pages.cs.wisc.edu/~remzi/OSTEP/vm-beyondphys-policy.pdf