Memória e armazenamento

A mesa de trabalho e o arquivo

Imagine que você está estudando: os livros que estão na sua mesa (RAM) você acessa em segundos. Os que estão no armário (SSD) levam um minuto para pegar. Os que estão em depósito (fita magnética) levam horas. Por isso você mantém na mesa só o que está usando agora.

A CPU é ainda mais extrema: ela prefere dados que estão a 0,3 ns de distância (registrador) e sofre esperando 100 ns pela RAM — que para nós parece instantâneo, mas para uma CPU é uma eternidade de 300 ciclos de clock em espera.

Leia e escreva na memória

Clique em uma célula para "lê-la" (azul). Use o formulário para escrever um valor num endereço (verde). Observe a hierarquia de velocidades abaixo da grade.

A hierarquia completa

• Registradores: dentro da CPU, < 1 ns, poucos bytes. Onde a ALU opera diretamente.
• Cache L1/L2/L3: 1–20 ns, KB–MB. Gerenciado automaticamente pelo hardware.
• RAM: 60–100 ns, GB. O sistema operacional gerencia o que fica aqui.
• SSD NVMe: ~0,1 ms, TB. Persistente, não perde com a energia.
• HDD: ~10 ms, TB. Mais barato por GB, mas mecânico (prato girando + cabeça de leitura).

Por que o cache faz tanta diferença

# Sem cache: toda leitura vai à RAM (100 ns)
para i em 0..999:
    soma += array[i]   # 1000 × 100 ns = 100 µs

# Com cache: após a primeira leitura, os dados ficam no L1 (1 ns)
para i em 0..999:
    soma += array[i]   # ~1 ns após o cache warm-up = 1 µs (100× mais rápido!)

Política de substituição: LRU

Quando o cache enche e um novo dado precisa entrar, qual dado expulsar? A política LRU (Least Recently Used) expulsa o que foi acessado há mais tempo:

# Cache LRU simples (capacidade = 3)
cache = []  # mais recente na frente

função acessar(página):
    se página em cache:
        cache.mover_para_frente(página)   # hit!
    senão:
        se len(cache) == capacidade:
            cache.remover_último()         # miss: evict LRU
        cache.inserir_frente(página)

Implemente uma cache LRU

Mini projeto: implemente a política LRU com um dicionário e uma fila (deque em Python). A função get(chave) retorna o valor ou None se não estiver no cache. A função put(chave, valor) insere e evicta o LRU se necessário.

Projeto principal: instrumente sua implementação para medir a taxa de acertos (hit rate) com diferentes tamanhos de cache e sequências de acesso. Compare LRU com FIFO (expulsa o mais antigo inserido).

Desafio extra: implemente LRU com complexidade O(1) para ambas as operações usando um hash map + lista duplamente encadeada (a solução canônica da entrevista técnica).

Teste sua intuição

Onde você encontra isso