Trabalhando com dados em memoria secundaria
Published: 2021-06-01 14:45:23

Em um programa, por vezes é necessário manipular um grande conjunto de dados, que nem sempre caberá na memória principal (RAM). Quando isto acontece é necessário utilizar a memória secundaria (Disco rígido) para trabalhar com os mesmos. O principal desafio é que o acesso à memória secundaria é muito custosa.

Para isto, existem algumas abordagens ao acesso à memória, dentre elas:

## Acesso sequencial

Em que cada item é trazido da memória secundária individualmente. Esta é uma maneira menos eficiente pois, o acesso ao disco é em ordem de grandeza mais lento que o acesso a RAM.

## Acesso em blocos (Sistema de paginação)

O acesso em blocos consiste em subdividir o conjunto de dados em subconjuntos (páginas) que cabem na memória principal.

No sistema de paginação, chamamos de páginas ativas as páginas que foram levadas para a memória principal e páginas inativas as que ainda estão em memória secundaria.

O sistema de paginação possui duas funções:

- Mapeamento de endereços

    Determina qual página da memória secundaria está sendo endereçada.

- Transferência de páginas

    Transferir da memória secundaria para a primaria e vice-versa

O endereçamento é determinado por uma sequência de bytes, onde uma parte é utilizada para representar o número da página e a outra o número do item dentro da página.

Na figura abaixo a primeira parte - em preto - corresponde ao endereço do bloco, e a segunda parte - em vermelho - corresponde ao endereço do item.

![Passo-a-passo de como funciona o endereçamento](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fun6egxgpc07pnn9td7v.gif)

O mapeamento é feito por meio de uma tabela de páginas, onde cada posição representa uma das páginas do arquivo. Ela é utilizada, de forma que os dados, uma vez trazidos da memória secundaria são adicionados na tabela, para acessá-lo durante a execução do programa. Quando o item não existir, sua página correspondente, será buscada na memória secundaria.

![Algoritmo de busca](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/atrbqta43jujckorp4gf.gif)

Uma vez que a tabela fique cheia, deve-se retirar uma página da memória principal para adicionar outra. Para isso, existem algumas estratégias, o ideal é remover uma página, que não será utilizada em um futuro próximo.

Dentre as políticas de remoção temos:

- LRU (Menos recentemente utilizada)

    Pode-se criar uma fila com as referências das páginas em que toda vez que uma página for utilizada, sua referência será colocada ao final da fila. 

- Menos frequentemente utilizada (LFU)

    Pode-se criar um contador para cada página e a que tiver menor frequência quando a memória primaria encher, dará lugar para a nova página. Deve-se atentar ao fato que ao adicionar a página o contador não pode ser 1 pois ela poderia ser removida logo após ser adicionada. Dessa forma, é necessário iniciar o contador com um valor maior, uma solução é inicializá-lo com a média dos contadores atuais.

![Esquema de páginas] (https://dev-to-uploads.s3.amazonaws.com/uploads/articles/n5fhw8d6xn3l4vcf7y3d.png)

- Ordem de Chegada (FIFO)

    Remove a página que está há mais tempo na memória principal.

É possível combinar estratégias de remoção para alcançar o objetivo de maneira mais eficiente.

# Métodos de pesquisa em memória secundaria

## Acesso Sequencial Indexado

É uma forma de pesquisa para encontrar itens dentro da memória secundaria em que é criado um índice de páginas que armazena a primeira chave do item de cada página e o endereço da página no disco. **Este método só pode ser utilizado se as chaves estiverem ordenadas. **

![Imagem animada mostrando o passo-a-passo](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gi6a80ah6b8znr8e4xia.gif)

 Para localizar um item, deve-se:

- Localizar, no índice de páginas, a página que pode conter o item desejado, de acordo com sua chave de pesquisa.
- Trazer a página para a memória principal.
- Realizar uma pesquisa sequencial (ou binaria) na página localizada.

Após encontrar a página, em que o item se encontra, pode-se optar em trazer a página toda ou trazer apenas o item.  A primeira forma pode ser mais vantajosa, pois é necessário apenas um acesso a memória secundaria, enquanto a segunda, deve-se fazer acessos a cada item buscado, tornando-o mais lento.

Este artigo foi produzido em conjunto com a Michele Andrade.