Por que o LRU é melhor que o FIFO?
https://stackoverflow.com/questions/2058403
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Por que é Menos usado recentemente melhor que FIFO em relação a arquivos de paginação?
Solução
Se você quer dizer em termos de descarga de páginas de memória para disco - se o seu processo estiver acessa frequentemente uma página, você realmente não deseja que ele seja paginado no disco, mesmo que fosse o primeiro que você acessou. Por outro lado, se você não acessa uma página de memória há vários dias, é improvável que o faça no futuro próximo.
Se não é isso que você quer dizer, edite sua pergunta para dar mais detalhes.
Outras dicas
Não existe um algoritmo de cache único que sempre funcione bem porque requer um conhecimento perfeito do futuro.(E se você souber onde conseguir isso...) O domínio do LRU no design de cache de VM é o resultado de um longo histórico de medição do comportamento do sistema.Dadas cargas de trabalho reais, o LRU funciona muito bem durante uma grande fração do tempo.Entretanto, não é muito difícil construir uma string de referência para a qual o FIFO teria desempenho superior ao LRU.
Considere uma varredura linear através de um grande espaço de endereço, muito maior que a memória real paginável disponível.LRU é baseado na suposição de que "o que você tocou recentemente, provavelmente tocará novamente", mas a varredura linear viola completamente essa suposição.É por isso que alguns sistemas operacionais permitem que programas aconselhem o kernel sobre seu comportamento de referência - um exemplo é a coleta de lixo "marcar e varrer" tipificada pelos intérpretes LISP clássicos.(E um importante impulsionador para o trabalho em GCs mais modernos, como "geracional".)
Outro exemplo é a tabela de símbolos em um determinado macroprocessador antigo (STAGE2).A árvore binária é pesquisada a partir da raiz em busca de cada símbolo, e a avaliação da string é feita em uma pilha.Acontece que reduzindo os quadros de página disponíveis "conectando" a página raiz da árvore de símbolos e a página inferior da pilha fizeram uma grande melhoria na taxa de falhas de página.O cache era minúsculo e agitava-se violentamente, sempre empurrando para fora as duas páginas referenciadas com mais frequência porque o cache era menor do que a distância entre referências para essas páginas.Então um pequeno o cache funcionou melhor, mas SOMENTE porque esses dois quadros de página roubados do cache foram usados com sabedoria.
A conclusão de tudo isso é que LRU é a resposta padrão porque geralmente é muito boa para cargas de trabalho reais em sistemas que não estão terrivelmente sobrecarregados (VM muitas vezes a memória real disponível) e isso é suportado por anos de medições cuidadosas.No entanto, você certamente pode encontrar casos em que o comportamento alternativo será superior.Isso é por que medindo sistemas reais é importante.
Trate a RAM como um cache.Para ser um cache eficaz, ele precisa manter na memória os itens com maior probabilidade de serem solicitados.
LRU mantém na memória os itens que foram usados mais recentemente.FIFO mantém as coisas que foram adicionadas mais recentemente.LRU é, em geral, mais eficiente, porque geralmente há itens de memória que são adicionados uma vez e nunca mais usados, e há itens que são adicionados e usados com frequência.É muito mais provável que o LRU mantenha os itens usados com frequência na memória.
Dependendo dos padrões de acesso, o FIFO às vezes pode vencer a LRU. Um Cache de reposição adaptável é híbrido que adapta sua estratégia com base nos padrões de uso reais.
De acordo com Localidade temporal de referência, a memória que foi acessada recentemente é mais provável de ser acessada novamente em breve.
