Armazenamento e Acesso a Arquivos

Prévia do material em texto

Utilização de arquivos: 
- Acesso a memória não-volátil; 
- Acesso a memória em grande quantidade e baixo custo; 
 
Arquivo Físico: sequência de bytes armazenada no disco em blocos distribuídos em 
trilhas/setores. 
Arquivo Lógico: arquivo como visto pelo aplicativo que o acessa – sequência contínua de 
registros ou bytes. 
 
FILE *arq 
if ((arq = fopen(“arquivo.dat”, “r”)) == NULL) 
 printf(“Erro na abertura do arquivo \n”); 
else 
 
Leitura sequencial: ponteiro de leitura avança byte a byte (ou por blocos), a partir de uma 
posição inicial. 
Acesso aleatório (direto): posicionamento em um byte ou registro arbitrário. 
 
Capacidade do setor: nº bytes (Ex. 512 bytes). 
Capacidade da trilha: nº de setores/trilha * capacidade do setor. 
Capacidade do cilindro: nº de trilhas/cilindro * capacidade da trilha. 
Capacidade do disco: nº de cilindros x capacidade do cilindro. 
 
Queremos armazenar 20.000 registros de tamanho fixo num disco de 300 Mbytes que contém: 
512 bytes/setor 
40 setores/trilha 
11 trilhas/cilindro 
1331 cilindros 
 
Quantos cilindros são necessários, se cada registro tem 256 bytes ? 
2 registros/setor = 10.000 setores. Se em cada cilindro há 40 x 11 = 440 setores, então o 
número de cilindros é aproximadamente 10.000/440 = 22.7 cilindros. 
 
Fragmentação é a perda de espaço útil decorrente da organização em setores de tamanho fixo. 
Fragmentação interna consiste em espaço não utilizado nos cluster/blocos de um arquivo. 
Fragmentação externa consiste em espaços vazios entre cluster/blocos de arquivos. A medida 
que o sistema vai evoluindo e registros/arquivos vão sendo criados ou removidos. 
 
O custo de acesso ao disco é uma combinação de 3 fatores: 
- Tempo de busca (seek): tempo para posicionar o braço de acesso no cilindro correto; 
- Delay de rotação: tempo para o disco rodar de forma que a cabeça de L/E esteja posicionada 
sobre o setor desejado; 
- Tempo de transferência: tempo para transferir os bytes. 
O tempo de acesso real também é afetado pela distribuição do arquivo no disco e o modo de 
acesso (seqüencial x aleatório). 
 
Tempo de Busca (Seek) 
Depende de quanto o braço precisa se movimentar. 
Mais caro em ambiente multi-usuário. 
 
Escrever um byte: 
- Verifica se o arquivo existe, se tem permissão de escrita, etc. 
- Obtém a localização do arquivo físico (drive, cilindro, cluster ou extent) correspondente ao 
arquivo lógico. 
- Determina em que setor escrever o byte. Verifica se esse setor já está no buffer de E/S (se 
não estiver, carrega-o). 
- Instrui o processador de E/S (que libera a CPU de cuidar do processo de transferência) sobre 
a posição do byte na RAM, e onde ele deve ser colocado no disco. 
 
A transferência de dados entre a área de dados do programa e a memória secundária requer o 
uso de buffers* de memória. 
Buffering: permite trabalhar com grandes quantidades de dados em RAM, de modo a reduzir o 
nº de acessos que precisam ser feitos ao dispositivo de armazenamento secundário (buffers de 
E/S (buffers do sistema, não dos programas)). 
Os sistemas precisam de, no mínimo, 2 buffers: 1 p/ leitura e 1 p/ escrita. 
 
Campo: menor unidade lógica de informação em um arquivo; 
 
Campos com tamanho fixo 
Cada campo ocupa no arquivo um tamanho fixo pré-determinado. 
Porém o espaço alocado e não usado aumenta o tamanho do arquivo e gera desperdício. 
Inapropriado quando tem uma grande quantidade de dados com tamanho variável. 
 
Campos com indicador de comprimento 
O tamanho do campo é armazenado antes do dado. 
 
Campos separados por delimitadores 
Caracteres especiais são inseridos ao final de cada campo. 
 
Uso de keyword 
O campo fornece a informação sobre ele mesmo ajudando a identificar o conteúdo do arquivo. 
Porém pode ocupar uma porção significativa do arquivo. 
 
Métodos para organização de registros 
- Tamanho fixo 
- Número fixo de campos 
- Indicador de tamanho 
- Uso de índice 
- Uso de delimitadores 
 
Considerando que os arquivos estão organizados por registros, deve-se recuperar um registro 
específico ao invés de ler todo o arquivo. Uma chave associada a cada registro identificando-o 
é uma boa solução. 
Uma chave primária é utilizada para identificar unicamente um registro, enquanto uma chave 
secundária não identifica unicamente um registro, podendo ser utilizada para buscas 
simultâneas por várias chaves. 
 
Encontrar registros associados a chaves: 
- Busca Seqüencial; 
Lê o arquivo, registro a registro, em busca de um registro contendo um certo valor de chave. 
Na busca em RAM, considera-se o numero de comparações efetuadas. O acesso a disco é a 
operação mais cara, pois cada chamada READ lê um registro e requer um SEEK. 
Vantagens: fácil de programar e requer estruturas de arquivos simples. 
Pode ser usada em arquivos com poucos registros ou pouco pesquisados em busca de chaves 
que se repetem e que se espera muitas ocorrências. 
 
- Busca Binária; 
Compara a chave procurada com a chave do registro mediano. Se a chave procurada for 
menor que a chave do registro mediano, procura-se somente na metade inferior do arquivo. Se 
for maior, procura-se na metade superior do arquivo e se for igual, então é o fim da busca. 
Esse método requer que o arquivo esteja ordenado, encontra a chave com poucas 
comparações, mas requer muitas operações de SEEK e requer registros de tamanho fixo ou 
estrutura auxiliar de índice. 
 
- Acesso Direto; 
Realiza seeking direto para o início do registro desejado e lê o registro imediatamente. 
Um único acesso traz o registro independentemente do tamanho do arquivo. 
Para saber a posição do início do registro no arquivo, pode-se utilizar um arquivo índice 
separado ou um RRN que fornece a posição relativa do registro dentro do arquivo (byte offset). 
 
A compressão de dados envolve codificação da informação para que o arquivo ocupe menos 
espaço afim de uma transmissão mais rápida e processamento seqüencial mais rápido. 
Há técnicas como: 
- Redução de redundância; 
- Omissão de sequências repetidas; 
- Códigos de tamanho variável; 
 
Um marcador no campo do registro é usado para reconhecer que o registro foi eliminado. 
Compactação consiste na busca por regiões do arquivo que não contém dados e na 
recuperação desses espaços não utilizados. 
Em registros de tamanho fixo: RRN 
Em registros de tamanho variável: offset 
 
Fragmentação interna é o espaço não utilizado dentro dos registros. 
Exemplo: um registro de 55 bytes é inserido no espaço de 72 bytes, sobram 17 bytes. 
Registros de tamanho variável são usados para diminuir a fragmentação interna. 
Pode-se colocar o espaço não utilizado na lista de disponíveis. 
Porém o registro pode não ocupar exatamente o espaço que resta, ocasionando a 
fragmentação externa, quando espaços vazios são utilizáveis, mas muito pequenos para serem 
realmente úteis. 
A fragmentação interna é decorrente dos espaços perdidos DENTRO dos registros, enquanto a 
externa é decorrente dos espaços perdidos FORA dos registros. 
A fragmentação externa pode ser evitada com estratégias de posicionamento: 
- First-fit = a lista de disponíveis não tem ordem. 
- Best-fit = a lista de disponíveis está em ordem crescente de espaço. A vaga alocada é a 
primeira que possuir tamanho suficiente, que é a menor vaga na qual o registro cabe e aquela 
que será perdido menos espaço. Porém, aumenta a fragmentação externa. 
- Worst-fit = a lista de disponíveis está em ordem decrescente. A vaga alocada é a primeira que 
possua tamanho suficiente e é a maior vaga resultando na sobra de espaço. Esse espaço deve 
ser devolvido a Dispo. 
 
Busca 
Sequencial: funciona para qualquer organização do arquivo. 
Binária: requer que o arquivo esteja ordenado. 
 
Se o arquivo é pequeno, pode-se carregá-lo em memória principal, ordená-lo e gravá-lo. 
Acessa-se o arquivo 2 vezes, para leitura antes de ordenar e para escrita depois de ordenado. 
 
Em keysorting,o importante é ordenar as chaves somente e o arquivo não precisa ser 
carregado totalmente em memória. Somente as chaves são carregadas em memória e 
ordenadas. 
Ao invés de escrever o arquivo ordenado no disco, é interessante gerar um arquivo com as 
chaves ordenadas atuando como índice para o arquivo original. 
 
Índices são utilizados para facilitar a localização de informações principalmente quando 
precisamos organizar um arquivo para ser pesquisado por chaves. 
As vantagens são: 
- Melhora o tempo de busca por um registro. 
- Permitir colocar ordem no arquivo sem rearranjar o arquivo; 
- Possibilitar múltiplas visões dos registros em um arquivo de dados; 
- Fornecer acesso rápido a arquivos com registros de tamanho variável. 
- Se os registros dos índices são menores que os do arquivo de dados, ordenar e manter 
índices pode ser menos caro do que ordenar e manter o arquivo de dados. 
- Permite combinar chaves associadas e fazer buscas que combinam visões particulares. 
Um campo contém a chave e o outro informa a posição inicial do registro no arquivo de dados. 
O índice está ordenado apesar do arquivo de dados não estar. 
O arquivo índice é mais fácil de trabalhar, pois usa registros de tamanho fixo e pode ser 
pesquisado com busca binária (em memória principal), além de ser muito menor que o arquivo 
de dados. 
Dados a chave e o offset, um único seek é necessário para recuperar o registro 
correspondente. 
O acesso a registros é feito por chaves secundárias, pra isso cria-se um índice que relaciona 
uma chave secundária à chave primária. 
A lista invertida é usada para evitar a repetição das chaves secundárias, onde associa-se cada 
chave secundária a uma lista encadeada das chaves primárias referenciadas. 
 
Compressão: reduz a quantidade de bits para representar um dado. 
- Elimina redundância 
- Economizar espaço em dispositivos de armazenamento. 
- Ganhar desempenho em transmissões 
 
Com perdas x Sem perdas 
Sem perdas: os dados obtidos após a descompressão são idênticos aos dados que se tinha 
antes da compressão. 
Com perdas: Não são idênticos após a descompressão. 
 
Simétricos x Assimétricos 
Simétricos: quando a compressão e descompressão são realizadas executando métodos 
idênticos ou bem semelhantes. 
Assimétricos: quando o método de compressão é mais complexo que o de descompressão ou 
vice-versa (mais raro). 
 
Adaptativos x Não adaptativos 
Não adaptativos: regras não variam de acordo com os dados, nem a medida que os dados são 
lidos. 
Adaptativos: se adaptam aos dados à medida que os dados são processados. 
 
Compactação: união de dados que não estejam unidos (compressão sem perdas). 
 
O Código de Huffman é usado em algoritmos de compressão de arquivos, principalmente do 
tipo texto e atribui códigos menores para símbolos freqüentes e códigos maiores para os 
menos frequentes