Quais algoritmos de substituição de página são usados no kernel Linux para cache de arquivos do SO?

Question

O Linux usa as partes não usadas da memória para o armazenamento em cache de arquivos e limpa o espaço quando necessário.

A minha pergunta é sobre como escolhe uma página de vítima para substituição? Existem vários algoritmos (LRU, FIFO, LFU e substituição aleatória)

Eu gostaria de saber  1) Quais algoritmos de substituição de página são usados no kernel Linux para o cache de arquivos do SO?

2) Se possível, gostaria de saber como evoluiu ao longo do tempo no kernel do Linux. Eu suponho que seu algoritmo e implementação podem mudar ao longo do tempo, considerando mudanças "razoáveis" nas tendências. Como posso encontrar esses? Preciso ler códigos fonte do kernel?

    

Answer 1

O gerenciamento de memória do Linux ("MM") parece ser um pouco misterioso e desafiador para rastrear.

A literatura sobre Linux faz uma strong menção de LRU (Least Recently Used), no contexto do gerenciamento de memória. Eu não notei nenhum dos outros termos sendo mencionados.

Eu encontrei uma introdução interessante (primeiros quatro parágrafos) em este artigo no incomparável LWN.net. Explica como a LRU básica pode ser implementada na prática para a memória virtual. Leia.

A substituição True LFU (Least Frequently Used) não é considerada prática para a memória virtual. O kernel não pode contar todas as leituras de uma página, quando mmap() é usado para acessar páginas de cache de arquivos - por exemplo, é assim que a maioria dos programas é carregada na memória. A sobrecarga de desempenho seria muito alta.

Para ir além desse conceito simples, há um esboço de projeto em torno da versão 2.6.28-32 do Linux aqui:

link

Ele sugere que o Clock-PRO é usado para páginas de arquivo. Há um artigo original disponível. Há uma antiga descrição do Clock-PRO no LWN.net, novamente incluindo alguns detalhes práticos de implementação. Aparentemente, o Clock-PRO "tenta ir além da abordagem LRU", uma variante da qual é "usada na maioria dos sistemas". Parece colocar mais peso na frequência.

O Linux-mm tem outro documento de design para implementar o Clock-PRO no Linux. Este não fala sobre isso ser fundido; foi escrito alguns meses antes do artigo da LWN sobre isso. link

descrições mais recentes são de que o Linux simplesmente "usa algumas idéias" de relógio -PRO, e é realmente um "mash de um número de diferente algoritmos com uma série de modificações para capturar casos de canto e várias otimizações ".

A citação acima foi respondida por uma pergunta por Adrian McMenamin . McMenamin passou a completar um MSc projeto em 2011, testando modificações para substituição de página Linux baseada no "modelo de conjunto de trabalho". Inclui uma breve descrição da substituição da página do Linux. A "variante da LRU" é chamada de "abordagem 2Q [fila dupla] para gerenciamento de banco de dados", várias referências são fornecidas e há um diagrama que ilustra o movimento entre as duas filas e outras transições de estado. Ele também descreve o Linux como uma implementação parcial do CLOCK-PRO.

Espero que o conceito de LRU, em oposição às outras possibilidades que você mencionou, tenha sido estabelecido desde o início. E a mudança mais significativa foi a introdução de recursos baseados no Clock-PRO, ou seja, colocando um pouco mais de peso na frequência.

Em 2013, o Linux ganhou "o dimensionamento de cache de arquivos baseado em detecção thrash". Isso provavelmente também é relevante para a questão.