algoritmo de Bélády
o algoritmo de cache mais eficiente seria sempre descartar a informação que não será necessária por mais tempo no futuro. Este resultado ideal é referido como o algoritmo ideal de Bélády/simplesmente a Política de substituição ideal ou o algoritmo clarividente. Uma vez que, de um modo geral, é impossível prever até que ponto serão necessárias informações no futuro, tal não é, de um modo geral, exequível na prática. O mínimo prático pode ser calculado apenas após a experimentação, e pode-se comparar a eficácia do algoritmo de cache realmente escolhido.
no momento em que uma falha de página ocorre, algum conjunto de páginas está na memória. No exemplo, a sequência de ‘5’, ‘0’, ‘1’ é acessado pelo Frame 1, Frame 2, Frame 3, respectivamente. Então, quando ” 2 “é acessado, ele substitui o valor “5”, que está no quadro 1, uma vez que prevê que o valor ” 5 ” não vai ser acessado em um futuro próximo. Como um sistema operacional de propósito geral da vida real não pode realmente prever quando ‘5’ será acessado, o algoritmo de Bélády não pode ser implementado em tal sistema.
primeiro na primeira edição (FIFO)editar
Usando este algoritmo, a cache comporta-se da mesma forma que uma fila FIFO. O cache evoca os blocos na ordem em que foram adicionados, sem qualquer consideração a quantas vezes ou quantas vezes eles foram acessados antes.
Last in first out (LIFO) or First in last out (FILO)Edit
Using this algorithm the cache behaves in the same way as a stack and exact opposite way as a FIFO queue. O cache retrata o bloco adicionado mais recentemente primeiro, sem qualquer consideração a quantas vezes ou quantas vezes ele foi acessado antes.
Least recently used (LRU)Edit
Discards the least recently used items first. Este algoritmo requer manter o controle do que foi usado quando, o que é caro se alguém quiser ter certeza de que o algoritmo sempre descarta o item menos usado recentemente. Implementações gerais desta técnica requerem a manutenção de ” bits de idade “para linhas de cache e rastrear a linha de cache” menos usada recentemente ” baseada em bits de idade. Em tal implementação, cada vez que uma linha de cache é usada, a idade de todas as outras linhas de cache muda. LRU é na verdade uma família de algoritmos de caching com membros incluindo 2Q por Theodore Johnson e Dennis Shasha, e LRU/K por Pat O’Neil, Betty O’Neil e Gerhard Weikum.
a sequência de Acesso para o exemplo abaixo é um B C D E D F.
no exemplo acima, uma vez que um B C D é instalado nos blocos com números de sequência (incremento 1 para cada novo acesso) e quando E é acessado, é uma falha e precisa ser instalado em um dos blocos. De acordo com o algoritmo LRU, uma vez que A tem a classificação mais baixa(a(0)), E irá substituir A.
no segundo último passo D é acessado e, portanto, o número de sequência é atualizado.
LRU, como muitas outras políticas de substituição, pode ser caracterizada usando um campo de transição de estado em um espaço vetorial, que decide que o estado de cache dinâmico muda semelhante a como um campo eletromagnético determina o movimento de uma partícula carregada colocada nele.
Time aware least recently used (TLRU)Edit
The Time aware Least Recently Used (TLRU) is a variant of LRU designed for the situation where the stored contents in cache have a valid life time. O algoritmo é adequado em aplicações de cache de rede, tais como redes centradas na informação (ICN), redes de entrega de conteúdo (CDNs) e redes distribuídas em geral. TLRU introduz um novo termo: TTU (tempo de Uso). TTU é um carimbo de tempo de um conteúdo / página que estipula o tempo de usabilidade para o conteúdo com base na localidade do conteúdo e o anúncio do editor de conteúdo. Devido a este horário baseado na localidade, TTU fornece mais controle para o administrador local para regular no armazenamento de rede.No algoritmo TLRU, quando um pedaço de conteúdo chega, um nó de cache calcula o valor TTU local baseado no valor TTU atribuído pelo editor de conteúdo. O valor TTU local é calculado usando uma função definida localmente. Uma vez que o valor TTU local é calculado a substituição do conteúdo é realizada em um subconjunto do conteúdo total armazenado no nó de cache. O TLRU garante que o conteúdo menos popular e de vida pequena deve ser substituído pelo conteúdo de entrada.
mais recentemente usado (MRU)editar
devoluções, em contraste com a LRU, os itens usados mais recentemente primeiro. Em descobertas apresentadas na 11ª Conferência VLDB, Chou e DeWitt observaram que ” quando um arquivo está sendo digitalizado repetidamente em um padrão de referência, MRU é o melhor algoritmo de substituição. Posteriormente, outros pesquisadores que apresentaram na 22ª Conferência VLDB observaram que para padrões de acesso Aleatório e varreduras repetidas em grandes conjuntos de dados (às vezes conhecidos como padrões de acesso Cíclico) algoritmos de cache de MRU têm mais acessos do que a LRU devido à sua tendência para reter dados mais antigos. Os algoritmos MRU são mais úteis em situações em que quanto mais antigo um item é, mais provável é que ele seja acessado.
A sequência de Acesso para o exemplo abaixo é um B C D E C D B.
aqui, um B C D são colocados no cache como ainda há espaço disponível. No quinto acesso e, vemos que o bloco que segurava D é agora substituído por E como este bloco foi usado mais recentemente. Outro acesso a C e no próximo acesso a D, C é substituído como era o bloco acessado pouco antes de D e assim por diante.
Pseudo-EFP (PLRU)editar
para caches de CPU com grande associatividade (geralmente>4 maneiras), o custo de implementação da LRU torna-se proibitivo. Em muitos caches de CPU, um esquema que quase sempre descarta um dos itens menos usados recentemente é suficiente, então muitos designers de CPU escolhem um algoritmo PLRU que só precisa de um bit por item de cache para funcionar.A PLRU normalmente tem uma taxa de falhas ligeiramente pior, tem uma latência ligeiramente melhor, usa um pouco menos de potência do que a LRU e custos gerais mais baixos em comparação com a LRU.
o exemplo seguinte mostra como os Bits funcionam como uma árvore binária de ponteiros de 1-bit que apontam para a sub-árvore menos usada recentemente. Seguindo a cadeia de ponteiros para o nó folha identifica o candidato substituto. On an access all pointers in the chain from the accessed way’s leaf node to the root node are set to point to subtree that does not contain the accessed way.
A sequência de acesso é uma B C D E.
O princípio aqui é simples de entender se olharmos apenas para os ponteiros da seta. Quando há um acesso a um valor, diga “A”, e não podemos encontrá-lo no cache, em seguida, carregá-lo a partir da memória e colocá-lo no bloco onde as setas estão apontando atualmente, indo de cima para baixo. Depois de colocarmos aquele bloco, viramos as mesmas flechas para que apontem para o lado oposto. No exemplo acima vemos como ” a “foi colocado, seguido de “B”, ” C ” E “D”. Depois, à medida que o cache se tornava completo, ” e “substituía” A “porque era onde as setas apontavam naquela altura, e as setas que levavam a” A ” eram viradas para apontar na direcção oposta. As setas então levaram a ‘B’, que será o bloco substituído na próxima falha de cache.
edição de substituição aleatória (RR)
selecciona aleatoriamente um item candidato e rejeita-o para criar espaço quando necessário. Este algoritmo não requer a manutenção de qualquer informação sobre o histórico de acesso. Por sua simplicidade, tem sido usado em processadores ARM. Admite simulação estocástica eficiente.
a sequência de Acesso para o exemplo abaixo é uma cache B C D E B D F
CLU segmentada (SLRU)Edit
SLRU é dividida em dois segmentos, um segmento experimental e um segmento protegido. As linhas em cada segmento são ordenadas do mais ao menos acessado recentemente. Os dados de falhas são adicionados ao cache no final mais recentemente acessado do segmento probatório. Os acessos são removidos de onde quer que residam atualmente e adicionados ao final mais recentemente acessado do segmento protegido. As linhas no segmento protegido foram assim acessadas pelo menos duas vezes. O segmento protegido é finito, de modo que a migração de uma linha do segmento experimental para o segmento protegido pode forçar a migração da linha LRU no segmento protegido para o mais recentemente utilizado (MRU) fim do segmento experimental, dando a esta linha outra chance de ser acessado antes de ser substituído. O limite de tamanho do segmento protegido é um parâmetro SLRU que varia de acordo com os padrões de carga de Trabalho I / O. Sempre que os dados devem ser descartados do cache, as linhas são obtidas a partir do fim da EFP do segmento probatório.
menos frequentemente usado (LFU)editar
conta com a frequência com que um item é necessário. Aqueles que são usados com menos frequência são descartados primeiro. Isso funciona muito semelhante à LRU, exceto que em vez de armazenar o valor de como recentemente um bloco foi acessado, nós armazenamos o valor de quantas vezes ele foi acessado. Então, é claro, enquanto executamos uma sequência de acesso, vamos substituir um bloco que foi usado menos vezes do nosso cache. Por exemplo, se A foi usado (acessado) 5 vezes e B foi usado 3 vezes e outros C E D foram usados 10 vezes cada, Nós substituiremos B.
menos frequente recentemente usado (LFRU)editar
o menos frequente recentemente usado (LFRU) esquema de substituição de cache combina os benefícios dos esquemas LFU e LRU. O LFRU é adequado para aplicações de cache “em rede”, tais como redes centradas na informação (ICN), redes de entrega de conteúdo (CDNs) e redes distribuídas em geral. Em LFRU, o cache é dividido em duas partições chamadas de partições privilegiadas e não privilegiadas. A partição privilegiada pode ser definida como uma partição protegida. Se o conteúdo é altamente popular, ele é empurrado para a partição privilegiada. A substituição da partição privilegiada é feita da seguinte forma: o LFRU evoca o conteúdo da partição não protegida, empurra o conteúdo da partição privilegiada para a partição não protegida, e finalmente insere um novo conteúdo na partição privilegiada. No procedimento acima o LRU é usado para a partição privilegiada e um esquema aproximado de LFU (ALFU) é usado para a partição não protegida, daí a abreviatura LFRU.
a ideia básica é filtrar o conteúdo localmente popular com o esquema ALFU e empurrar o conteúdo popular para uma das partições privilegiadas.
LFU with dynamic aging (LFUDA)Edit
uma variante chamada LFU with Dynamic Aging (LFUDA) que usa o envelhecimento dinâmico para acomodar mudanças no conjunto de objetos populares. Ele adiciona um fator de idade de cache para a contagem de referência quando um novo objeto é adicionado ao cache ou quando um objeto existente é re-referenciado. O LFUDA aumenta a idade da cache ao despejar blocos, ajustando-a para o valor-chave do objeto despejado. Assim, a idade do cache é sempre menor ou igual ao valor-chave mínimo no cache. Suponha que quando um objeto foi freqüentemente acessado no passado e agora se torna impopular, ele permanecerá no cache por um longo tempo, impedindo assim os objetos recém-populares de substituí-lo. Assim, este envelhecimento dinâmico é introduzido para reduzir a contagem de tais objetos, tornando-os assim elegíveis para substituição. A vantagem do LFUDA é que reduz a poluição do cache causada pelo LFU quando os tamanhos do cache são muito pequenos. Quando os tamanhos do Cache são grandes poucas decisões de substituição são suficientes e a poluição do cache não será um problema.
Low inter-reference recency set (LIRS)Edit
LIRS is a page replacement algorithm with an improved performance over LRU and many other newer replacement algorithms. Isso é conseguido usando a distância de reutilização como uma métrica para classificação dinâmica de páginas acessadas para tomar uma decisão de substituição. O LIRS aborda efetivamente os limites da EFP utilizando a recência para avaliar a Recência Inter-referência (IRR) para tomar uma decisão de substituição.
na figura acima, ” x ” representa que um bloco é acessado no tempo T. Suponha que se o bloco A1 é acessado no tempo 1, Então a Recência se tornará 0, uma vez que este é o primeiro bloco acessado e IRR será 1, uma vez que prevê que A1 será acessado novamente no tempo 3. No tempo 2 desde que A4 é acessado, a recência se tornará 0 para A4 e 1 para A1, porque A4 é o objeto acessado mais recentemente e IRR se tornará 4 e ele vai continuar. No tempo 10, o algoritmo LIR terá dois conjuntos Lir set = {A1, A2} e hir set = {A3, A4, A5}. Agora, no momento 10, Se houver acesso ao A4, falha ocorre. O algoritmo LIRS agora despejará A5 em vez de A2 por causa de sua maior recência.
CLOCK-ProEdit
LRU algoritmo não pode ser implementado diretamente na trajetória crítica de sistemas informáticos, tais como sistemas operacionais, devido à sua alta sobrecarga. Uma aproximação de LRU, chamado relógio é comumente usado para a implementação. Da mesma forma, CLOCK-Pro é uma aproximação de LIRS para uma implementação de baixo custo em sistemas. CLOCK-Pro está sob o framework básico CLOCK, mas tem três grandes méritos distintos. Primeiro, O CLOCK-Pro tem três ” mãos de clock “em contraste com uma estrutura simples de CLOCK onde apenas uma” mão ” é usada. Com as três mãos, CLOCK-Pro é capaz de medir a distância de reutilização dos acessos de dados de uma forma aproximada. Em segundo lugar, todos os méritos de LIRS são mantidos, como rapidamente despejando itens de dados de acesso único e/ou baixa localidade. Em terceiro lugar, a complexidade do CLOCK-Pro é igual à do CLOCK, assim é fácil de implementar a um custo baixo. A implementação de substituição de cache buffer na versão atual do Linux é uma combinação de LRU e CLOCK-Pro.
cache de substituição adaptável (ARC)editar
equilibra constantemente entre a EFP e a EFF, para melhorar o resultado combinado. ARC melhora no SLRU usando informações sobre itens de cache despejados recentemente para ajustar dinamicamente o tamanho do segmento protegido e do segmento probatório para fazer o melhor uso do espaço de cache disponível. Algoritmo de substituição adaptativo é explicado com o exemplo.
Adapttiveclimb (AC)Edit
usa hit/miss recente para ajustar o salto onde em Subida qualquer hit muda a posição de um slot para o topo, e em LRU hit switches a posição do hit para o topo. Assim, beneficiando-se da otimalidade da escalada quando o programa está em um escopo fixo, e a rápida adaptação a um novo escopo, como faz a LRU. Também suporta o compartilhamento de cache entre núcleos, liberando extras quando as referências são para a parte superior do cache.
Clock with adaptive replacement (CAR)Edit
combina as vantagens de Cache de substituição adaptativa (ARC) e CLOCK. O carro tem desempenho comparável ao da ARC, e supera substancialmente tanto a EFP quanto o relógio. Como o ARC, o carro é auto-tuning e não requer parâmetros mágicos especificados pelo Usuário. Ele usa 4 listas duplamente ligadas: dois relógios T1 e T2 e duas listas LRU simples B1 e B2. O T1 clock armazena páginas baseadas em” recency “ou” short term utility”, enquanto o T2 armazena páginas com” frequency “ou”long term utility”. T1 e T2 contêm as páginas que estão na cache, enquanto B1 e B2 contêm páginas que foram despejadas recentemente de T1 e T2, respectivamente. O algoritmo tenta manter o tamanho dessas listas B1≈T2 e B2≈T1. São inseridas novas páginas em T1 ou T2. Se houver um acerto no tamanho B1 de T1 é aumentado e similarmente se houver um acerto no tamanho B2 de T1 é diminuído. A regra de adaptação utilizada tem o mesmo princípio que no ARC, investir mais em listas que dará mais hits quando mais páginas são adicionadas a ele.
multi queue (MQ)Edit
the multi queue algorithm or MQ was developed to improve the performance of second level buffer cache for e.g. a server buffer cache. É introduzido em um artigo por Zhou, Philbin e Li. o cache MQ contém um número m de filas LRU: Q0, Q1,…, Qm-1. Aqui, o valor de m representa uma hierarquia baseada no tempo de vida de todos os blocos nessa fila particular. Por exemplo, se j>i, blocos em Qj terão uma vida útil mais longa do que aqueles em Qi. Além disso, há um outro buffer de histórico Qout, uma fila que mantém uma lista de todos os identificadores de bloco, juntamente com suas freqüências de acesso. Quando o Quout estiver completo, o identificador mais antigo é despejado. Os blocos permanecem nas filas da LRU para uma determinada vida útil, que é definida dinamicamente pelo algoritmo MQ para ser a distância temporal máxima entre dois acessos ao mesmo arquivo ou o número de blocos de cache, o que for maior. Se um bloco não foi referenciado durante sua vida útil, ele é rebaixado de Qi para Qi-1 ou despejado do cache se estiver em Q0. Cada fila também tem uma contagem máxima de acesso; se um bloco na fila Qi é acessado mais de 2i vezes, este bloco é promovido a Qi+1 até que seja acessado mais de 2i+1 vezes ou sua vida útil expira. Dentro de uma determinada fila, os blocos são classificados pela recência do access, de acordo com a LRU.podemos ver a partir da Fig. como as filas m LRU são colocadas no cache. Ver também da Fig. como o Quout armazena os identificadores de bloco e suas correspondentes frequências de acesso. a foi colocado em Q0 como foi acessado apenas uma vez recentemente e podemos verificar em Qout como b E c foram colocados em Q1 e Q2, respectivamente, como suas freqüências de acesso são 2 e 4. A fila em que um bloco é colocado depende da frequência de acesso(f) como log2(f). Quando o cache estiver cheio, o primeiro bloco a ser removido será o cabeça de Q0, neste caso, um. Se um é acessada mais uma vez ele vai passar para Q1 abaixo b.
Pannier: Recipiente baseado no algoritmo de cache para o composto objectsEdit
Pannier é um recipiente baseado em flash mecanismo de cache que identifica divergentes (heterogêneo) recipientes onde blocos realizada nele altamente variados padrões de acesso. Pannier usa uma estrutura de Fila de sobrevivência baseada em prioridade para classificar os contêineres com base em seu tempo de sobrevivência, o que é proporcional aos dados ao vivo no contêiner. O Pannier é construído com base em LRU segmentada (S2LRU), que segrega dados quentes e frios. Pannier também usa um controlador de feedback multi-passo para throttle flash writes para garantir a vida útil do flash.