Trabalhando com dados em memoria secundaria

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.

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.

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.

• 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. *

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.