Cache
# Cache

Na área da computação, cache é um dispositivo de acesso rápido, interno a um sistema, que serve de intermediário entre um operador de um processo e o dispositivo de armazenamento ao qual esse operador acede. A principal vantagem na utilização de um cache consiste em evitar o acesso ao dispositivo de armazenamento - que pode ser demorado -, armazenando os dados em meios de acesso mais rápidos.
O uso de memórias cache visa obter uma velocidade de acesso a memória próxima da velocidade de memórias mais rápidas, e ao mesmo tempo disponibilizar no sistema uma memória de grande capacidade, a um custo similar de memórias de semicondutores mais baratas.

## Nos dispositivos de armazenamento

Com os avanços tecnológicos, vários tipos de cache foram desenvolvidos. Atualmente há cache em processadores, discos rígidos, sistemas, servidores, nas placas-mãe, clusters de bancos de dados, entre outros. Qualquer dispositivo que requeira do usuário uma solicitação/requisição a algum outro recurso, seja de rede ou local, interno ou externo a essa rede, pode requerer ou possuir de fábrica o recurso de cache.
Por ser mais caro, não é financeiramente viável que o recurso mais rápido seja usado para armazenar todas as informações. Sendo assim, usa-se o cache para armazenar apenas as informações mais frequentemente usadas. Nas unidades de disco também conhecidas como discos rígidos (HD) também existem chips de cache nas placas eletrônicas que os acompanham. Como exemplo, a unidade Samsung de 160 GB possui 8 MB de cache.
No caso da informática, o cache é útil em vários contextos:
* nos casos dos processadores, em que cache disponibiliza alguns dados já requisitados e outros a processar;
* no caso dos navegadores web, em que as páginas são guardadas localmente para evitar consultas constantes à rede (especialmente úteis quando se navega por páginas estáticas);
* no caso das redes de computadores, o acesso externo, ou à Internet, se dá por meio de um software que compartilha a conexão ou link, software este também chamado de proxy, que tem por função rotear as requisições a IPs externos à rede que se encontra. Os proxys têm capacidade de caching: ao armazenar o conteúdo de páginas web já visitadas pelos usuários da rede na qual faz parte e fornecer esse conteúdo às novas requisições, minimizam o consumo do de largura de banda e agilizam a navegação;
* os servidores web também podem dispor caches configurados pelo administrador, que variam de tamanho conforme o número de page views que o servidor tem.

## Cache de disco

A cache de disco representa uma pequena quantidade de memória incluída na placa lógica do HD. Tem como principal função armazenar as últimas trilhas lidas pelo HD. Esse tipo de cache evita que a cabeça de leitura e gravação passe várias vezes pela mesma trilha, pois como os dados estão no cache, a placa lógica pode processar a verificação de integridade a partir dali, acelerando o desempenho do HD, já que o mesmo só requisita a leitura do próximo setor assim que o último setor lido seja verificado.

## Operação

Uma cache é um bloco de memória para o armazenamento temporário de dados que possuem uma grande probabilidade de serem utilizados novamente.
Uma definição mais simples de cache poderia ser: uma área de armazenamento temporária onde os dados frequentemente acedidos são armazenados para acesso rápido.
Uma cache é feita de uma fila de elementos. Cada elemento tem um dado que é a cópia exata do dado presente em algum outro local (original). Cada elemento tem uma etiqueta que especifica a identidade do dado no local de armazenamento original, que foi copiado.
Quando o cliente do cache (CPU, navegador etc.) deseja aceder a um dado que acredita estar no local de armazenamento, primeiramente ele verifica o cache. Se uma entrada for encontrada com uma etiqueta correspondente ao dado desejado, o elemento do cache é então utilizado ao invés do dado original. Essa situação é conhecida como cache hit (acerto do cache). Como exemplo, um navegador poderia verificar o seu cache local no disco para ver se tem uma cópia local dos conteúdos de uma página Web numa URL particular. Nesse exemplo, a URL é a etiqueta e o conteúdo da página é o dado desejado. A percentagem de acessos que resultam em cache hits é conhecida como a taxa de acerto (hit rate ou hit ratio) do cache.
Uma situação alternativa, que ocorre quando o cache é consultado e não contém um dado com a etiqueta desejada, é conhecida como cache miss (erro do cache). O dado então é copiado do local original de armazenamento e inserido no cache, ficando pronto para o próximo acesso.
Se o cache possuir capacidade de armazenamento limitada (algo comum de acontecer devido ao seu custo), e não houver mais espaço para armazenar o novo dado, algum outro elemento deve ser retirado dela para que liberte espaço para o novo elemento. A forma (heurística) utilizada para selecionar o elemento a ser retirado é conhecida como política de troca (replacement policy). Uma política de troca muito popular é a LRU (least recently used), que significa algo como “elemento recentemente menos usado”.
Quando um dado é escrito na cache, ele deve ser gravado no local de armazenamento em algum momento. O momento da escrita é controlado pela política de escrita (write policy). Existem diferentes políticas. A política de write-through (algo como “escrita através”) funciona da seguinte forma: a cada vez que um elemento é colocado no cache, ele também é gravado no local de armazenamento original. Alternativamente, pode ser utilizada a política de write-back (escrever de volta), onde as escritas não são diretamente espelhadas no armazenamento. Ao invés, o mecanismo de cache identifica quais de seus elementos foram sobrepostos (marcados como sujos) e somente essas posições são colocadas de volta nos locais de armazenamento quando o elemento for retirado do cache. Por essa razão, quando ocorre um cache miss (erro de acesso ao cache pelo fato de um elemento não existir nele) em um cache com a política write-back, são necessários dois acessos à memória: um para recuperar o dado necessário e outro para gravar o dado que foi modificado no cache.
O mecanismo de write-back pode ser accionado por outras políticas também. O cliente pode primeiro realizar diversas mudanças nos dados do cache e depois solicitar ao cache para gravar os dados no dispositivo de uma única vez.
Os dados disponíveis nos locais de armazenamento original podem ser modificados por outras entidades diferentes, além da própria cache. Nesse caso, a cópia existente na cache pode se tornar inválida. Da mesma forma, quando um cliente atualiza os dados no cache, as cópias do dado que estejam presentes em outros caches se tornarão inválidas. Protocolos de comunicação entre gerentes de cache são responsáveis por manter os dados consistentes e são conhecidos por protocolos de coerência.

## Princípio da localidade de referência

É a tendência de o processador ao longo de uma execução referenciar instruções e dados da memória principal localizados em endereços próximos. Tal tendência é justificada devido as estruturas de repetição e as estruturas de dados, vetores e tabelas utilizarem a memória de forma subsequente (um dado após o outro). Assim a aplicabilidade do cache internamente ao processador fazendo o intermédio entre a memória principal e o processador de forma a adiantar as informações da memória principal para o processador.

## Tipos de memória cache

Os tipos de memória cache mais conhecidos são:
* Mapeamento direto: cada bloco da memória principal é mapeado para uma linha do cache;
* Mapeamento associativo: um bloco da memória principal pode ser carregado para qualquer linha do cache;
* Mapeamento associativo por conjunto (N-way): meio termo direto e o associativo.

## Ausência de conteúdo no cache - CACHE MISS

Quando o processador necessita de um dado, e este não está presente no cache, ele terá de realizar a busca diretamente na memória RAM, utilizando wait states e reduzindo o desempenho do computador. Como provavelmente será requisitado novamente (localidade temporal) o dado que foi buscado na RAM é copiado no cache.

## Cache em níveis

Com a evolução na velocidade dos dispositivos, em particular nos processadores, o cache foi dividido em níveis, já que a demanda de velocidade a memória é tão grande que são necessários caches grandes com velocidades altíssimas de transferência e baixas latências. Sendo muito difícil e caro construir memórias caches com essas características, elas são construídas em níveis que se diferem na relação tamanho X desempenho.

### Cache L1

Uma pequena porção de memória estática presente dentro do processador. Em alguns tipos de processador, como o Pentium II, o L1 é dividido em dois níveis: dados e instruções (que "dizem" o que fazer com os dados). O primeiro processador da Intel a ter o cache L1 foi o i486 com 8KB. Geralmente tem entre 16KB e 128KB; hoje já encontramos processadores com até 16MB à 32MB de cache.

### Cache L2

Em função da capacidade reduzida do cache L1, foi desenvolvido o cache L2, com mais memória que o cache L1. Ela é mais um caminho para que a informação requisitada não tenha que ser procurada na lenta memória principal. Alguns processadores colocam esse cache fora do processador, por questões econômicas, pois um cache grande implica num custo grande, mas há exceções, como no Pentium II, por exemplo, cujas caches L1 e L2 estão no mesmo cartucho, que está o processador. A memória cache L2 é, sobretudo, um dos elementos essenciais para um bom rendimento do processador mesmo que tenha um clock baixo. Um exemplo prático é o caso do Intel Itanium 9152M (para servidores) que tem apenas 1.6 GHz de clock interno e supera em desempenho o atual Intel Extreme, pelo fato de possuir uma memória cache de 24MB. Quanto mais alto é o clock do processador, mais este aquece e mais instável se torna. Os processadores Intel Celeron têm um fraco desempenho por possuir menos memória cache L2. Um Pentium M 730 de 1.6 GHz de clock interno, 533 MHz FSB e 2 MB de cache L2, tem rendimento semelhante a um Intel Pentium 4 2.4 GHz, aquece muito menos e torna-se muito mais estável e bem mais rentável do que o Intel Celeron M 440 de 1.86 GHz de clock interno, 533 MHz FSB e 1 MB de cache L2.

### Cache L3

Terceiro nível de cache de memória. Inicialmente utilizado pelo AMD K6-III (por apresentar o cache L2 integrado ao seu núcleo), utilizava o cache externo presente na placa-mãe como uma memória de cache adicional. Ainda é um tipo de cache raro devido a complexidade dos processadores atuais, com suas áreas chegando a milhões de transístores por micrômetros ou nanômetros de área.
É possível a necessidade futura de níveis ainda mais elevados de cache, como L4 e assim por diante.

## Caches inclusivos e exclusivos

Caches Multi-level introduzem novos aspectos na sua implementação. Por exemplo, em alguns processadores, todos os dados no cache L1 devem também estar em algum lugar no cache L2. Estes caches são estritamente chamados de inclusivos. Outros processadores (como o AMD Athlon) têm caches exclusivos - os dados podem estar no cache L1 ou L2, nunca em ambos. Ainda outros processadores (como o Pentium II, III, e 4 de Intel), não requerem que os dados no cache L1 residam também no cache L2, embora possam frequentemente fazê-lo. Não há nenhum nome universal aceitado para esta política intermediária, embora o termo inclusivo seja usado.
A vantagem de caches exclusivos é que são capazes de armazenarem mais dados. Esta vantagem é maior quando o cache L1 exclusivo é de tamanho próximo ao cache L2, e diminui se o cache L2 for bastante acoplado ao núcleo, as vezes maior do que o cache L1. Quando o L1 falha e o L2 acerta acesso, a linha correta do cache L2 é trocada com uma linha no L1. Esta troca é um problema, uma vez que a quantidade de tempo para tal troca ser realizada é relativamente alta.
Uma das vantagens de caches estritamente inclusivos é que quando os dispositivos externos ou outros processadores em um sistema multiprocessado desejam remover uma linha do cache do processador, necessitam somente mandar o processador verificar o cache L2. Nas hierarquias de cache exclusiva, o cache L1 deve ser verificado também.
Uma outra vantagem de caches inclusivos é que um cache maior pode usar linhas maiores do cache, que reduz o tamanho das Tags do cache L2. (Os caches exclusivos requerem ambos os caches teres linhas do mesmo tamanho, de modo que as linhas do cache possam ser trocadas em uma falha no L1 e um acerto no L2).

### Tamanho do cache

Quando é feita a implementação da memória cache, alguns aspectos são analisados em relação a seu tamanho:
* a relação acerto/falha;
* tempo de acesso a memória principal será mais lenta;
* o custo médio, por bit, da memória principal, do cache L1
* o tempo de acesso do cache L1 ou L2;
* a natureza do programa a ser executado no momento é inferior.

## Técnicas de escrita de dados do cache
### Técnicas de "Write Hit"
#### Write-Back Cache

Usando esta técnica a CPU escreve dados diretamente no cache, cabendo ao sistema a escrita posterior da informação na memória principal. Como resultado, o CPU fica livre mais rapidamente para executar outras operações. Em contrapartida, a latência do controlador pode induzir problemas de consistência de dados na memória principal, em sistemas multiprocessados com memória compartilhada. Esses problemas são tratados por protocolos de consistência do cache.
Exemplo:
A escrita de um endereço é feita inicialmente numa linha do cache, e somente no cache. Quando mais tarde algum novo endereço precisar desta linha do cache, estando esta já ocupada, então o endereço inicial é guardado na memoria e o novo endereço ocupa-lhe o lugar na respectiva linha do cache.
Para reduzir a frequência de escrita de blocos de endereços na memória aquando da substituição é usado um "dirty bit", este é um bit de estado, ou seja, quando o endereço é instanciado inicialmente numa linha do cache, estando essa linha vazia, o valor inicial é implicitamente '0', quando o bloco do endereço é modificado(quando ocorre uma substituição) o valor inicial passa a '1' e diz-se que o bloco do endereço está "dirty".

##### Vantagens

* a escrita ocorre à velocidade do cache;
* escritas múltiplas de um endereço requerem apenas uma escrita na memória;
* consome menos largura de banda.

##### Desvantagens

* difícil de implementar;
* nem sempre existe consistência entre os dados existentes no cache e na memória;
* leituras de blocos de endereços no cache podem resultar em escritas de blocos de endereços "dirty" na memoria.

#### Write-Through Cache

Quando o sistema escreve para uma zona de memória, que está contida no cache, escreve a informação, tanto na linha específica do cache como na zona de memória ao mesmo tempo. Este tipo de caching providencia pior desempenho do que Write-Back Cache, mas é mais simples de implementar e tem a vantagem da consistência interna, porque o cache nunca está dessincronizada com a memória como acontece com a técnica Write-Back Cache.

##### Vantagens

* fácil de implementar;
* um "cache-miss" nunca resulta em escritas na memória;
* a memória tem sempre a informação mais recente.

##### Desvantagens

* a escrita é lenta;
* cada escrita necessita de um acesso à memória;
* consequentemente usa mais largura de banda da memória.

### Técnicas de "Write Miss"
#### Write Allocate

O bloco de endereço é carregado na ocorrência seguindo-se uma ação de "write hit". O "Write Allocate" é usado com frequência em caches de "Write Back".

#### No Write Allocate

O bloco de endereço é diretamente modificado na memória, não é carregado no cache. O "No Write Allocate" é usado frequentemente em caches de "Write Through".