Lsta_04_ED2

Prévia do material em texto

Fundação Universidade Federal de Rondônia
Departamento Acadêmico de Ciências da Computação
Estrutura de Dados II – Lista de exercícios – Arquivos - parte 2
Giullia de Souza Santos
Thauan Costa da Silva
1. Quais os parâmetros são considerados para calcular o tempo de leitura de um arquivo em
fita? Procure estas informações para um dispositivo de fita comercial e calcule quanto
tempo tal dispositivo levaria para ler um arquivo de 1MB.
R: Para calcular o tempo de leitura de um arquivo em fita é necessário levar em
consideração a densidade da fita (bytes por inches), a velocidade (inches por segundo), o
tamanho do interblock (inches) e até o tempo de rebobinamento.
Taxa nominal de transmissão = densidade * velocidade;
2. O que são buffers de E/S (ou I/O)? Quais os passos executados para ler um byte do disco
de forma que ele possa ser utilizado por um programa?
R: É uma região de memória que armazena temporariamente dados enquanto são
transferidos de um dispositivo E/S para a memória principal.
O sistema operacional solicita a leitura e verifica se o byte já está no buffer para que seja
realizada a leitura do bloco a partir do buffer do controlador, caso o byte não esteja no
buffer, é posicionado a cabeça de leitura na posição especificada do disco, o bloco é lido
e transferido para o buffer do controlador em seguido os dados são transferidos para a
memória principal para que possa ser utilizado por um programa.
3. As aplicações usualmente armazenam as informações em arquivos organizando-as em
campos e registros. Explique as diferentes maneiras pelas quais um campo pode ser
armazenado em um arquivo para posterior recuperação.
R: As maneiras que um campo pode ser armazenado e recuperado dependem do método
utilizado em sua organização, por exemplo cada campo possui um tamanho fixo
definido que pode ser utilizado para calcular o deslocamento para acesso, contudo esse
método pode apresentar desperdício de espaço caso os dados armazenados não ocupem
todo o tamanho pré estabelecido, uma outra maneira de dá pelo uso de indicadores de
comprimento em que cada campo é precedido de um número que indica seu tamanho,
assim esse valor é lido primeiro e então é determinado a quantidade de bytes a serem
lidos desse campo. Existe também a utilização de delimitadores específicos (exemplo /,
tab, # etc) em que os campos são separados por um delimitador que indica o seu final.
Por fim, também há o uso de tags (etiquetas) em que o campo fornece informação
semântica sobre si próprio.
4. Explique as diferentes estratégias que podem ser utilizadas para separar um registro de
outro. Discuta as vantagens e desvantagens de cada uma delas.
R: Cada registro possui um tamanho fixo definido, o que permite calcular o
deslocamento para acesso de forma direta e eficiente. Analogamente, quando para cada
registro se tem um número fixo de campos, em que os tamanhos dos campos podem
variar ou não. Contudo, embora facilite a leitura e estruturação dos dados, pode haver
desperdício de espaço.
Também há a possibilidade do uso de indicadores de tamanho, no qual cada registro
é precedido por um valor indicando seu tamanho. Assim, esse valor é lido primeiro para
determinar quantos bytes compõem o registro. Esse método oferece flexibilidade para
tamanhos variáveis de registros, mas adiciona complexidade na leitura e pode tornar o
acesso a registros específicos mais lento.
Outra opção é utilizar um índice para indicar o deslocamento de cada registro relativo
ao início do arquivo. Isso permite um acesso rápido e direto a registros específicos sem a
necessidade de percorrer o arquivo inteiro. No entanto, essa abordagem requer espaço
adicional para armazenar o índice e sua manutenção.
Por fim, pode ser utilizado delimitadores específicos, como caracteres especiais, para
delimitar o fim de cada registro. É uma forma flexível de separar registros e de fácil
interpretação, mas pode tornar o acesso a registros específicos mais lento e apresentar
problemas se os dados contiverem os próprios delimitadores.
5. Explique o que é fragmentação de campos e registros. Quando e por que ela ocorre?
R: A fragmentação ocorre quando há uma constante criação e eliminação de arquivos
que ao decorrer do tempo desencadeiam o surgimento de espaços vagos no disco que não
comportam tamanhos suficientes para novos arquivos. Assim, surgindo “espaços
fragmentados” que impossibilitam o armazenamento de dados (campos e registros) de
maneira sequencial/contígua.
6. Se a separação entre registros e campos é feita por delimitadores, quais as restrições para
a escolha desses delimitadores? Descreva uma situação que exemplifique sua resposta.
R: A escolha do delimitador deve ser específico e único de forma que não haja
ambiguidade com os dados reais, além disso, os delimitadores para campos e registros
devem ser diferentes um do outro. Por exemplo, os campos podem ser separados por “|”
e os registros por quebras de linha “\n”.
7. Crie um programa para escrever registros de tamanho variável em um arquivo e outro
capaz de recuperá-los. Faça o mesmo para registros de tamanho fixo. Os registros devem
ter pelo menos 3 campos.
R: Em anexo.
8. O que é gravado no arquivo quando uma struct do C é escrita em um arquivo? Como são
armazenados campos que não são strings?
R: Gera um arquivo binário. São armazenadas em ponteiro com valor inteiro.
9. Como um registro é identificado para acesso aleatório? Qual operação permite localizar
um registro no arquivo em C?
R: O acesso dependerá de cada estratégia utilizada para a organização do registro. Em
registros de tamanho fixo a posição para acessar pode ser calculada diretamente. Para
localizar a posição exata do início do registro no arquivo, pode-se utilizar um arquivo de
índice separado ou se pode ter um RRN (relative record number) (ou byte offset) que
fornece a posição relativa do registro dentro do arquivo. Geralmente, em C pode ser
utilizado a função fseek para acessar de forma aleatória um registro.
10. Explique como é possível melhorar o desempenho de um acesso sequencial a todo o
conteúdo de um arquivo. Tal solução também garante um melhor desempenho de uma
sequência arbitrária de acessos aleatórios? Discuta.
R: Para melhorar o acesso sequencial podem ser utilizadas técnicas como bufferização
lendo um bloco de registros por vez, e então processar este bloco em RAM. Estratégia
como leitura antecipada (Read-Ahead) em que o sistema carrega dados da memória
antecipadamente a solicitação, uso de caches eficientes bem como uma manutenção
frequente de arquivos desfragmentados.
11. Quantas leituras são necessárias, em média, para encontrar um registro em um arquivo
com N registros usando a busca sequencial? Quantas leituras são necessárias para
identificar que um registro não está no arquivo?
R: São necessárias O(n) leituras, igualmente para um registro que não está no arquivo.
12. Quais as vantagens e as desvantagens de utilizar arquivos organizados em registros de
tamanho fixo?
R: Pode oferecer como maior vantagem o acesso direto ao registro, visto que qualquer
posição no arquivo pode ser calculada multiplicando pelo tamanho fixo. Assim como
possibilita um melhor gerenciamento do espaço de memória alocado, pois cada registro
ocupa necessariamente um tamanho definido. Contudo, pode ser desvantajoso quando é
levado em consideração que pode acabar gerando um desperdício de espaço quando os
dados armazenados não ocupam devidamente o tamanho definido. Bem como torna-se
ineficiente caso seja necessário adicionar ou aumentar os campos já informados no
arquivo.
13. O que é RRN? Como é possível fazer acessos aleatórios em arquivos a registros de
tamanho variável?
R: Em registros de tamanho fixo, RRN (Relative Record Number) é um identificador
numérico que fornece a posição relativa de cada registro dentro de um arquivo, podendo
ser calculado o deslocamento multiplicando o seu RRN pelo tamanho fixo (Byte offset =
RRN * Tamanho do registro). Já para acessar registros de tamanho variável, existem
estratégias como a implementação de índicesde byte offsets para delimitar o início de
cada registro, ou seja, cada índice armazena o byte (deslocamento) para cada registro do
arquivo, permitindo um acesso direto a qualquer registro.
14. É vantajoso manter um arquivo separado para armazenar apenas as chaves e os byte
offsets, ou RRNs, dos registros no arquivo de dados? Como isto afeta a inserção de um
novo registro?
R: Oferece como principal vantagem o acesso direto aos registros e o melhor
desempenho em buscas e ordenações. Contudo, a cada nova inserção é necessário a
atualização dos índices de byte offsets ou RRNs no caso de registros de tamanho fixo.
15. Como um registro pode ser eliminado de um arquivo?
R: Um registro pode ser eliminado ao ser marcado como excluído. Dessa maneira o
registro não é eliminado, mas é configurado como inválido, posteriormente, em
processos de reorganização e compactação, esses registros inválidos são removidos.
16. O que são modelos abstratos de dados, para que são utilizados e quais as suas vantagens?
R: No contexto de arquivos, podem ser entendidos como representações conceituais de
dados que não se adequam a forma de organização de dados armazenados
sequencialmente em campos e registros. Dados como imagens e sons dependem de
meios de implementação de uma aplicação para que seus dados sejam interpretados e
apresentados de maneira que o usuário possa visualizá-los. Conceitualmente, o tipo
abstrato de dados (TAD) descreve dados e operações que podem ser realizadas sobre
eles, sem se preocupar com os detalhes de implementação.
17. Por que é interessante utilizar cabeçalhos nos arquivos?
R: A existência de um cabeçalho torna o arquivo um objeto auto-descrito, o que por sua
vez facilita na organização e gerenciamento para usos futuros.
18. Comprima a cadeia de caracteres a seguir usando código de Huffman:
DCCACADEACCCCCBCEBBBD. Apresente a árvore e os códigos gerados.
Considerando que, inicialmente, cada letra era escrita usando 3 bits cada, houve
compressão? De quanto?
De 63 bits para 45 bits, compressão de 63-45 = 18 bits.
19. Em princípio, não é possível fazer busca binária em um arquivo de dados com registros
de tamanho variável. Por que a indexação do arquivo torna a busca binária possível?
Com um arquivo com registros de tamanho fixo é possível fazer busca binária. Isto
significa que indexação não é necessária para arquivos de registros de tamanho fixo?
R: Em arquivos com registros de tamanho variável não há como realizar a busca binária
devido a imprevisibilidade de tamanhos, sendo assim se torna impraticável o cálculo de
acesso direto (método de cálculo utilizado na busca binária). Contudo, por meio da
indexação é possível gerenciar para que cada início de registro haja um índice marcando
sua posição. Logo, a busca binária pode ser aplicada nos índices, que podem ser
ordenados.
A busca binária é aplicável em registros de tamanho fixo devido ao fato de todos os
registros possuírem o mesmo tamanho, tornando viável o cálculo para o acesso direto.
Porém, o uso da indexação pode ser vantajoso mesmo em registros de tamanho fixo,
visto que oferece uma forma de busca mais flexível ao pensar que o índice é um “id”
conhecido de um registro.
20. Considerando um cadastro de CDs, por que título não é usado como chave primária no
arquivo de dados? Se título fosse usado como chave secundária, que problemas deveriam
ser considerados na escolha de uma forma canônica para os títulos?
R: Considerando que títulos de CDs são strings que podem possuir tamanhos variáveis,
conter caracteres especiais e ter a probabilidade de aparecimento de homônimos, faz com
que seja ineficaz em ser usada como chave primária (visto que a chave primária deve ser
única). É mais praticável pensar no título como chave secundária, mas em vista dos
problemas citados, seria necessário aplicar métodos como Case Sensitivity para tratar as
diferenças de maiusculo e minúsculo, espaços e outros caracteres especiais. Além disso,
faz sentido que a chave secundária esteja relacionada por meio de índices à chave
primária para uma busca de maior eficiência.
21. Qual o propósito em deixar um indicador de desatualizado no cabeçalho de um índice?
Em um ambiente de multiprogramação, este indicador poderia ser encontrado “setado”
por um programa porque outro programa está em processo de reindexação. Como o
primeiro programa deveria responder a esta situação?
R: Deixar como desatualizado sinaliza que o índice em questão deve ser tratado com
cautela ao ser gerenciado, pois estar sinalizado como desatualizado indica que possa
haver inconsistências no registro. Desse modo, garante que não seja utilizado enquanto
não houver sua atualização, por exemplo em casos de reindexação.
22. Quando um registro é atualizado num arquivo, as chaves primárias e secundárias do
índice podem ser alteradas ou não, dependendo do arquivo ter registros de tamanho fixo
ou variável e dependendo do tipo de alteração que foi feita no registro de dados. Faça
uma lista das situações diferentes que podem ocorrer devido a atualizações e explique
como cada uma pode afetar os índices.
R: Ao atualizar um registro, podem haver 3 tipos de situações:
1 - Alteração de chave secundária: O índice secundário para esta chave precisa ser
reordenado.
2 - Alteração de chave primária: Necessário atualizar (reordenar) o índice primário e
corrigir os os campos de referência dos índices secundários.
vantagem: atualização dos índices secundários não requer reorganização.
3 - Alteração de outros campos: não afeta nenhum dos índices, desde que o tamanho
do registro não mude.
23. Discuta o problema que ocorre quando você inclui o registro abaixo em seu arquivo,
assumindo que o índice por compositor usado é o mostrado na Figura 6.9. Como você
poderia resolver o problema sem grandes alterações na estrutura do índice de chave
secundária?
LON 1259 Fidelio Beethoven Maazel
R: Implementar uma lista de referências encadeada (lista invertida) em que cada chave
secundária estará ligada, por meio de ponteiros, a uma lista de chaves primárias.
24. O que é uma lista invertida? Quando ela é útil? Como ela é mantida em memória
secundária? Esquematize o conteúdo de um índice secundário organizado como lista
invertida para um arquivo de dados hipotético.
R: É uma estrutura de dados que permite mapear valores de campos em posições
específicas de um arquivo (exemplo do esquema acima, na questão anterior), como
exemplo onde uma chave secundária é linkada a uma lista de chaves primárias, por isso o
nome “invertido”. São armazenadas em arquivos em memória secundária, organizadas
por um aestrutura de índices que apontam para uma lista de referências.
25. Como são alteradas as estruturas mostradas na figura 6.11 pela inclusão do registro
abaixo?
LON 1259 Fidelio Beethoven Maazel
R: Os registros estão organizados em uma estrutura de lista invertida encadeada, além de
ter sido linkado mais um id a chave secundária “PROKOFIEV”.
26. Suponha que você tenha um arquivo de dados de CD’s, muito grande, com um índice
pela chave primária e índices pelas chaves secundárias organizados por compositor,
artista e título. Suponha que uma lista invertida é usada para as chaves secundárias.
Explique, passo a passo, como um programa poderia responder às seguintes solicitações:
a) Liste todas as gravações de Bach ou Beethoven;
R:
1. Na lista invertida, localizar Bach e Beethoven associados a chave compositor.
2. Recuperar os registros dos CDs
3. Exibir resultados
b) Liste todas as gravações de Perleman de peças de Mozart ou Joplin.
R:
1. Localizar Perelman nos índices de artista
2. Localizar Mozart e Joplin nos índices de compositores
3. Interseção das listas de CDs
4. Recuperar detalhes dos CDs
5. Exibir resultados
27. O método e temporização do binding afeta dois importantes atributos de um sistema de
arquivos: velocidade e flexibilidade. Discuta a relevância desses atributos, e o efeito do
binding sobre o tempo em cada um dos atributos acima, para um sistema de informação
de um hospital projetado para prover informação sobreos pacientes pelas chaves Nome
do paciente, Código do paciente, Localização, Medicação, Médico ou Médicos, e
Doença.
R:
28. Suponha que você tenha 8MB de memória RAM para ordenar um arquivo de 800.000
registros.
a) Quanto tempo durará a ordenação do arquivo usando o algoritmo merge sort?
R: Etapas a serem consideradas
1. Leitura dos registros do disco para a memória para criar as corridas.
2. Escrita das corridas ordenadas para o disco.
3. Leitura das corridas para intercalação.
4. Escrita do arquivo final em disco
Tempo total, aproximadamente 7 minutos
b) Quanto tempo durará a ordenação do arquivo usando o algoritmo key sort?
R: Etapas a serem consideradas
1. Leitura das chaves do disco para a memória.
2. Ordenação das chaves na memória.
3. Leitura dos registros conforme a ordenação das chaves.
4. Escrita dos registros ordenados no disco.
Tempo total, aproximadamente 5 horas.
c) Por que o algoritmo key sort não funcionará se houver 1MB de RAM disponível
para a fase de ordenação?
R:Insuficiência de memória para processar eficientemente os registros resultando em
um aumento significativo das operações de E/S e tempo de ordenação muito maior.
29. Em nossos cálculos envolvendo merge, assumimos que só uma busca e um atraso
rotacional são necessários para um único acesso sequencial. Se isso não ocorrer, mais
tempo será necessário para a realização de I/O. Por exemplo, o arquivo de 80 MB usado
no exemplo em sala, para a fase de leitura do processo de geração de corridas, a leitura
de cada corrida pode requerer muitos acessos. Assuma que o tamanho do extent para
nosso drive hipotético é de 20.000 bytes (aproximadamente uma trilha), e que todos
arquivos armazenados em blocos do tamanho da trilha devem ser acessados
separadamente (uma procura e um atraso rotacional por bloco).
a) Quantas buscas o passo 1 requer agora?
R: Em média, 2040 buscas.
b) Quanto tempo os passos 1, 2 e 3 levam?
R: Em média 254.5 segundos.
c) Qual é o impacto de um aumento no tamanho do arquivo por um fator 10 terá no
tempo total do merge sort?
R: O aumento do tamanho do arquivo por um fator 10 resulta em um aumento de
aproximadamente 15 vezes, seriam 3821.8 segundos.
30. Suponha que um arquivo de dados com 6.000 registros, mantido em disco, deve ser
ordenado em um computador cuja memória interna acomoda no máximo 600 registros
por vez, usando o procedimento de intercalação. Considere que serão geradas 10 corridas
de 600 registros cada, e que será realizada uma intercalação em 10 vias. Essa mesma área
de memória interna é usada como buffer de entrada para leitura de dados do disco, e o
sistema conta com um buffer de saída adicional que acomoda 200 registros.
a) Durante a intercalação, quantos registros serão lidos de cada corrida cada vez que ela
é acessada? Justifique.
R: n° de corridas: = 10 corridas6000
600
n° de registos: = 60 registros.600
10
b) Quantos seeks serão realizados para ler dados durante o processo de intercalação
(excluindo a fase de geração de corridas)? Quantos serão realizados para escrever
dados? Justifique.
R: Respectivamente: 10² = 100 seeks e = 30 seeks.6000
200