Políticas de Substituição Não-Adaptativas:
LRU (Least-Recently Used): Este método utiliza uma pilha para acompanhar a ordem dos acessos mais recentes ao conjunto de linhas da cache. Quando uma linha é acessada, esta é movida para o topo da pilha. Ao escolher uma linha para ser substituída por uma informação vinda da memória principal a linha que estiver no fundo da pilha (a linha menos recentemente usada - Least-Recently Used) será substituída. Tradicionalmente, a nova linha é colocada no topo da pilha.
LFU (Least-Frequently Used): A política LFU mantém um contador de acesso para cada linha da memória. Ao escolher uma linha para a substituição, a linha com a contagem mais baixa (a linha menos freqüentemente usada - Least-frequently Used) é descartada. Políticas LFU devem implementar um mecanismo de envelhecimento que decrementa automaticamente o valor do contador de acessos de cada linha ao longo do tempo para evitar a poluição da cache com linhas obsoleto.
LFU - (Least Recently Used): Bloco que teve menos acessos pelo processador é escolhido.
Aleatório: Bloco é escolhido aleatoriamente, independente do seu uso pelo processador
FIFO - (First-In, First-Out): Esquema de Fila. Primeiro a chegar é o primeiro a sair. Escolha independe da frequência de uso do bloco pelo processador.
LRU - (Least Frequently Used): Escolhe o bloco que não é usado há mais tempo.
Referência: http://www.ic.uff.br/~boeres/slides_FAC/FAC-Cache-ParteII.pdf
Boa tarde.
Quando pensamos em algoritmos de substituição de paginas de memória devemos entender qual seria o melhor e o pior caso dentre as situações de remoção de paginas.
Devemos entender que o pior caso seria se retirássemos uma pagina que esta sendo referenciada com muita frequência, e no melhor caso uma pagina que não esta sendo referenciada com frequência.
Os algoritmos citados tratam desses quesitos mencionados, qual pagina devo deixar ou retirar.
LFU (Frequentemente usada):
É associado um contador, que toda as vezes que a pagina é referenciada esse contador soma uma a ela.
A pagina removida será a que menos foi referenciada ou seja com o contador mais baixo.
O problema é que pagina que são inseridas recentemente estarão em desvantagem, pois iniciaram com o contador baixo.
LRU(Recentemente usada):
É associado um quantum (tempo) a cada vez que a pagina é referenciada.
A pagina com menos tempo de "uso" será descartada.
O problema é que não podemos prever a necessidade do S.O.
RESPOSTA: *o bloco que está há mais tempo sem ser usado é chamado*
Quando lidamos com o tempo de referencialmente estamos falando do LRU, pois ele associa em um campo a quantidade de tempo que a pagina foi referenciada "mostrando que ele provavelmente será referenciada novamente".