Lista II - Estrutura de Dados

Prévia do material em texto

Universidade Federal de Rondônia
Departamento Acadêmico de Ciência da Computação
Estrutura de Dados II 
Lista 2 – Arquivos 
Pode ser feito em duplas
Baseada na lista de exercícios da Profa. Maria Cristina, e livro do Folk.
Dupla: Aden Hercules Pinto de Azevedo, André Luis Mendes Ferreira
1. Explique a diferença entre arquivo lógico e arquivo físico.
Arquivo Físico: conjunto de bytes no disco, geralmente agrupados em setores de dados. Gerenciado pelo sistema operacional.
Arquivo lógico: modo como a linguagem de programação enxerga os dados. Uma seqüência de bytes, eventualmente organizados em registros ou outra estrutura lógica.
2. Descreva as operações fundamentais que podem ser realizadas em um arquivo. Descreva as funções que executam estas operações na linguagem de programação que você usa, e como elas são utilizadas. Por que existem vários modos de abrir um arquivo?
Principais operações: abertura e fechamento de arquivos, leitura de dados, escrita de dados, posicionamento do cursor. 
Abertura de arquivos: FILE * fopen(char *nome, char *modo);
Fechamento de arquivos: fclose(FILE *f);
Leitura de arquivos: 
int fgetc(FILE *f) 
lê um byte, retorna seu valor (0255) como inteiro. Retorna EOF em caso de erro.
char *fgets(char *dest, int limite, FILE *f);
lê uma linha de texto (ou até atingir o limite de bytes lidos) e guarda o texto lido em dest. Retorna dest em caso de sucesso, NULL em caso de erro.
int fscanf(FILE *f, char *formato, ...);
 scanf para arquivos.
int fread(void *dados, int tam_elem, int num_elem, FILE *f);
lê num_elem elementos de tam_elem bytes cada e armazena em dados. Retorna o número de elementos lidos com sucesso.
Escrita de dados: 
int fputc(int c, FILE *f) 
Escreve o byte c. Retorna EOF em caso de erro.
int fputs(char *dest, FILE *f); Escreve a string dest (que deve ter o zero terminador) no arquivo. Retorna EOF em caso de erro.
int fprintf(FILE *f, char *formato, ...); 
printf para arquivos
int fwrite(void *dados, int tam_elem, int num_elem, FILE *f); Escreve num_elem elementos de tam_elem bytes cada, armazenados em dados. Retorna o número de elementos escritos com sucesso.
Posicionamento do cursor: 
	int fseek(FILE *f, long distancia, int origem);
		Move o cursor do arquivo f para a posição distancia relativa a alguma origem.
	long ftell(FILE *f); 
Retorna a posição atual do cursor no arquivo f.
O modo de abertura diz à função fopen() que tipo de uso você vai fazer do arquivo, isto é, todos os modos tem suas funções específicas de acordo com o que você deseja trabalhar.
3. Quais as funções de um gerenciador de arquivos?
4. Explique porque os arquivos abertos devem ser fechados.
Fechar um arquivo faz com que qualquer caracter que tenha permanecido no "buffer" associado ao fluxo de saída seja gravado.
5. Descreva o que acontece quando um arquivo já existente é aberto por um aplicativo (p. ex., um programa) para escrita. E se o mesmo ocorrer com um arquivo não existente?
Com o arquivo existente, o programa abrirá para a escrita normalmente, e seu conteúdo anterior é sobrescrito. Se não existir, o programa cria.
6. Os sistemas de arquivos permitem definir atributos para controlar o acesso a um arquivo. O que acontece quando um programa tenta abrir um arquivo que tem proteção para leitura? E quando o arquivo tem proteção para escrita?
7. Muitos sistemas diferenciam os arquivos binários dos arquivos de texto. Qual a diferença entre eles?
Um arquivo texto, ou 'texto plano', é um arquivo cujos caracteres estão de acordo com a tabela ascii. Por exemplo, um caractere 13 é uma quebra de linha, um 65 é a letra 'A', e assim por diante. Quando você abre um desses textos em um editor comum, você consegue ler o conteúdo facilmente. Os arquivos HTML, por exemplo, são texto plano. Já com um arquivo binário, a coisa não é bem assim. Um executável, por exemplo, é um arquivo binário, e possui, na verdade, instruções para o processador executar. O código 90, ao invés de representar o caractére 'Z', indica a instrução NOP, do assembly.
8. No que consiste a operação de posicionamento (seeking) em um arquivo? Qual a sua utilidade? Exemplifique uma situação em que esta operação precisa ser utilizada.
Ação de mover o ponteiro para uma certa posição no arquivo. A função fseek() nos permite realizar operações de leitura e escrita em arquivos de forma randômica. 
Exemplo:
// posiciona no final do arquivo
fseek(arquivo,  0,  SEEK_END);
// grava endereco
fwrite(&endereco, sizeof(endereco), 1, arquivo);
// posiciona no início do arquivo
fseek(arquivo,  0,  SEEK_SET);
// lê o primeiro registro
fread(&endereco, sizeof(endereco), 1, arquivo);
// posiciona  no segundo registro
fseek(arquivo,  2*sizeof(endereço),  SEEK_SET);
fread(&endereco, sizeof(endereco), 1, arquivo);
// lê o segundo registro
9. Faça um programa que leia os últimos 10 caracteres de um arquivo qualquer e imprima-os na tela.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
int main()
{
	char ch;
	FILE *arq;
	if (!(arq = fopen("novo.txt", "r")))
		exit(1);
	fseek(arq, -10, 2);
	ch = fgetc(arq);
	while(ch != EOF){
		printf("%c\n", ch);
		ch = fgetc(arq);
	}
	fclose(arq);
	return 0;
}
10. Faça um programa que leia o conteúdo de um arquivo e o escreve na tela.
#include <stdio.h>
#include <stdlib.h>
int main()
{
	FILE *arq = fopen ("valores.txt", "r");
	
	char exibe[150];
	
	while(fgets(exibe, 150, arq)){
		puts(exibe);
	}
	fclose(arq);
	getchar();
	getchar();
	return 0;
}
11. Faça um programa para copiar o conteúdo de um arquivo para outro.
#include <stdio.h>
#include <stdlib.h>
int main()
{
	FILE *arq = fopen ("valores.txt", "r");
	FILE *arq2ponto0 = fopen ("novo.txt", "w");
	if (!arq || !arq2ponto0)
		exit(1);
	
	char recebe[10], i;
	while(!feof(arq)){
			fgets(recebe, 10, arq);
			fprintf(arq2ponto0, "%s\n", recebe);
	}
	
	fclose(arq);
	fclose(arq2ponto0);
	getchar();
	return 0;
}
12. Faça um programa que lê um vetor numérico pelo teclado e o escreve em um arquivo.
#include <stdio.h>
#include <stdlib.h>
int main()
{
	FILE *arq = fopen ("valores.txt", "w");
	int vet[10], i;
	printf("Digite 10 números inteiros: \n");
	for (i = 0; i < 10; ++i)
	{
		scanf("%d", &vet[i]);
		fprintf(arq, "%d\n", vet[i]);
	}
	fclose(arq);
	return 0;
}
13. Discuta as diferenças e semelhanças entre a memória principal (RAM) e a memória secundária (os arquivos).
Memória primária também é chamada de memória real, trata-se dos tipos de memória que o processador pode endereçar diretamente, sem as quais o computador não pode funcionar. Estas fornecem geralmente uma ponte para as secundárias, mas a sua função principal é a de conter a informação necessária para o processador num determinado momento; esta informação pode ser, por exemplo, os programas em execução. 
A memória secundária é do tipo que não podem ser endereçada diretamente pela CPU, os dados precisam ser carregados na memória principal antes de eles serem tratados pelo processador. Não são estritamente necessárias para a operação do computador. São geralmente não-voláteis, permitindo guardar os dados permanentemente. Incluem-se, nesta categoria, os discos rígidos, CDs, DVDs e disquetes.
..terminar...
14. Como são organizados fisicamente os discos? De que forma os discos armazenam os arquivos? Por que o tamanho real de um arquivo em disco é sempre maior do que o seu tamanho nominal?
São organizados em trilhas, setores e cilindros. A leitura e gravação são feitas através da manipulação de moléculas produzidas pelos polos da cabeça de leitura e gravação, de maneira que, quando está positiva, atrai um polo negativo e vice-versa. Essa polaridade apresenta uma variação de frequência extremamente alta; através dela são gravados os bits. A leitura de dados acontece de forma mais simples, pois a cabeça de leitura e gravação apenas decodifica o campo magnético gerado pelas moléculas e produz uma corrente elétrica correspondente; o controlador do HD analisa a variação e administra os bits.
Tamanho é o tamanho real do arquivo em bytes. Tamanho no disco é a quantidadereal de espaço ocupada no disco. Eles diferem porque o disco é dividido em faixas e setores e pode alocar blocos de tamanho discreto.
15. Quais parâmetros são considerados para calcular o tempo de leitura de um arquivo mantido em disco?
O tempo de acesso é a combinação do tempo de busca e do tempo de latência, o tempo médio necessário para realizar um acesso a um setor aleatório do HD.
Os fabricantes calculam o tempo de latência dos HDs de formas diferentes, tornando difícil uma comparação direta. O ideal é que você mesmo calcule o tempo de acesso médio com base nas informações anteriores. Para isso, basta somar o tempo de busca médio (Average) e o tempo de latência, calculado com base na velocidade de rotação dos discos. Como é muito difícil encontrar o settle time e o command overhead time nas especificações, você pode adicionar 0.5 ms, que é um valor aproximado.
16. Explique o que é um cilindro, e a razão para a organização de arquivos em cilindros.
Um cilindro nada mais é do que o conjunto de trilhas com o mesmo número nos vários discos. A divisão do disco em trilhas, setores e cilindros é chamada de formatação de baixo nível, ou formatação física. Exemplificando, para acessar um dado contido na trilha 982 da face de disco 3 por exemplo, a controladora do disco ativa a cabeça de leitura responsável pelo disco 3 e a seguir ordena ao braço de leitura que se dirija à trilha correspondente. Não é possível que uma cabeça de leitura esteja na trilha 982, ao mesmo tempo que outra esteja na trilha 5631 por exemplo, justamente por seus movimentos não serem independentes. Já que todas as cabeças de leitura sempre estarão na mesma trilha de seus respectivos discos, deixamos de chamá-las de trilhas e passamos a usar o termo "cilindro".
17. Explique o que é um cluster e o que é um extent.
Cluster é um termo em inglês que significa “aglomerar” ou “aglomeração” e pode ser aplicado em vários contextos. No caso da computação, o termo define uma arquitetura de sistema capaz combinar vários computadores para trabalharem em conjunto ou pode denominar o grupo em si de computadores combinados. Cada estação é denominada “nodo” e, combinadas, formam o cluster. Em alguns casos, é possível ver referências como “supercomputadores” ou “computação em cluster” para o mesmo cenário, representando o hardware usado ou o software especialmente desenvolvido para conseguir combinar esses equipamentos. Extent é uma área contígua de armazenamento reservada para um arquivo em um sistema de arquivos, representado como um intervalo de números de bloco ou trilhas em dispositivos de dados principais de contagem. Um arquivo pode consistir em zero ou mais extents; um fragmento de arquivo requer um extent.
18. O que é a fragmentação de um arquivo no disco? Quais os tipos de fragmentação do arquivo, por que elas ocorrem e quais seus efeitos?
Fragmentação: é a existência de vários pequenos espaços não contínuos não permitindo que um programa seja alocado. Fragmentação é o desperdício de espaço disponível em memória. Existem dois tipos de fragmentação, a fragmentação interna e a fragmentação externa. A fragmentação interna é a perda de espaço dentro de uma área de tamanho fixo. Numa memória secundária, ela ocorre quando um arquivo ou fragmento de arquivo não ocupa completamente o espaço da unidade de alocação destinado a ele, causando desperdício de espaço. A fragmentação externa ocorre no particionamento dinâmico. Este tipo de fragmentação começa a acontecer quando os programas forem terminando e deixando espaços cada vez menores na memória, não permitindo o ingresso de novos programas.
19. Discuta as vantagens e as desvantagens de organizar arquivos em blocos de tamanho definido pelo usuário, ao invés de em setores de tamanho fixo.
20. Por que os discos são considerados o gargalo de um sistema computacional? Explique como este problema pode ser minimizado.
HDs são centenas, e até milhares, de vezes mais lentos que a memória RAM. O acesso à RAM equivale a buscar uma informação no índice de um livro que está em suas mãos. O acesso a disco seria equivalente a mandar buscar a mesma informação em uma biblioteca. Em resumo, acesso a disco é muito caro, isto é, lento! Então, o número de acessos ao disco deve ser minimizado, a quantidade de informações recuperadas em um acesso deve ser maximizada. Estruturas de dados eficientes em memória principal são inviáveis em disco. Seria fácil obter uma estrutura de dados adequada para disco se os arquivos fossem estáveis (não sofressem alterações).
21. Como os arquivos são organizados em uma fita magnética? Por que as fitas organizam os dados em blocos?
São organizadas em posições de um registro e é dada por um deslocamento em bytes(offset) relativo ao início do arquivo. Os frames da fita são agrupados em blocos de dados de tamanhos variados, os quais são separados por intervalos (interblock gaps) sem informações, intervalos são necessários para viabilizar parada/reinício.
22. Quais as vantagens e desvantagens de fitas sobre discos com dispositivos de memória secundária?
Desvantagens: Sofre mais desgaste que discos; não permitem acesso direto/aleatório; acesso sequencial; maior fragilidade.
Vantagens: Compactas, resistentes, fáceis de transportar, mais baratas que disco; grande capacidade de armazenamento; longa expectativa de vida; confiabilidade na retenção dos dados ao longo de sua vida útil.
23. No que consiste um sistema de armazenamento terciário?
O armazenamento terciário é aquele que usa mídia removível, como as unidades de fita, e que usa um robô para buscar os dados.
24. 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.
25. 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?
 É uma região de memória física utilizada para armazenar temporariamente os dados enquanto eles estão sendo movidos de um lugar para outro. Normalmente, os dados são armazenados em um buffer enquanto eles são recuperados de um dispositivo de entrada (como um microfone) ou pouco antes de serem enviados para um dispositivo de saída (como auto-falantes). 
O comando ativa o S.O (file manager), que supervisiona a operação:
1- Verifica se o arquivo existe; se tem permissão de escrita, etc.
2- Obtém a localização do arquivo físico (drive, cilindro, cluster ou extent) correspondente ao arquivo lógico 
3 - Determina em que setor escrever o byte. Verifica se esse setor já está no buffer de E/S (se não estiver, carrega-o...)
26. 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.
27. Explique as diferentes estratégias que podem ser utilizadas para separar um registro de outro. Discuta as vantagens e desvantagens de cada uma delas.
28. Explique o que é fragmentação de campos e registros. Quando e por que ela ocorre?
29. 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.
30. 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.
31. 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?
32. Como um registro é identificado para acesso aleatório? Qual operação permite localizar um registro no arquivo em C?
Ele identifica através de suposição de arquivos com indicação do número de bytes antes de cada registro, e depois usa marcação do registro eliminados via um marcado especial. É necessária uma busca sequencial na LD para encontrar uma posição com espaço suficiente.
33.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.
Desvantagens:
Perda de espaço útil; O espaço alocado (e não usado) aumenta desnecessariamente o tamanho do arquivo
(desperdício). Solução inapropriada quando se tem uma grande quantidade de dados com tamanho variável. Razoável apenas se o comprimento dos campos é realmente fixo ou apresenta pouca variação.
34. 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?
São necessárias, em média, O(n) leituras para encontrar um registro em um arquivo com n registros usando a busca sequencial. Para identificar que um registro não está no arquivo também são necessárias O(n) leituras.
35. Quais as vantagens e as desvantagens de utilizar arquivos organizados em registros de tamanho fixo?
36. O que é RRN? Como é possível fazer acessos aleatórios em arquivos a registros de tamanho variável?
Relative Record Number, ou byte offset, que fornece a posição relativa do registro dentro do arquivo. Para utilizar o RRN, é necessário trabalhar com registros de tamanho fixo. Nesse caso, a posição de início do registro é calculada facilmente a partir do seu RRN.
37. É 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?
Sim, é vantajoso , pois mantém acesso direto. 
Vantagens: 
Cada campo ocupa no arquivo um tamanho fixo, pré-determinado;
O fato de o tamanho ser conhecido garante que é possível recuperar cada campo;
Desvantagem: 
O espaço alocado (e não usado) aumenta desnecessariamente o tamanho do arquivo (desperdício);
Solução inapropriada quando se tem uma grande quantidade de dados com tamanho variável;
Razoável apenas se o comprimento dos campos é realmente fixo ou apresenta pouca variação;
38. Como um registro pode ser eliminado de um arquivo?
1 - remove do arquivo de dados, usando algum dos mecanismos de remoção. 
2 - remove também do índice. A remoção do registro do índice pode exigir a sua reorganização, ou pode-se simplesmente marcar os registros como removidos.
39. O que são modelos abstratos de dados, para que são utilizados e quais as suas vantagens?
Focar no conteúdo da informação, ao invés de no seu formato físico. As informações atuais tratadas pelos computadores (som, imagens, documentos, etc.) não se ajustam bem à metáfora de dados armazenados como sequências de registros separados em campos. É mais fácil pensar em dados deste tipo como objetos que representam som, imagens, etc. e que têm a sua própria maneira de serem manipulados. O termo modelo abstrato de dados captura a noção de que o dado não precisa ser visto da forma como está armazenado - ou seja, permite uma visão dos dados orientada à aplicação, e não ao meio no qual eles estão armazenados.
Porque são utilizados:
A abstração de informações através do TAD permitiu a melhor compreensão dos algoritmos e maior facilidade de programação, e por consequência aumentou a complexidade dos programas, tornando-se fundamental em qualquer projeto de software a modelagem prévia de seus dados. A separação entre a definição conceitual – par (v, o) – e a implementação (ED específica). O programa só acessa o TAD por meio de suas operações, a ED nunca é acessada diretamente, há "ocultamento de informação". Programador tem acesso a uma descrição dos valores e operações admitidos pelo TAD. O programador não tem acesso à implementação. Idealmente, a implementação é ´invisível´ e inacessível.
Vantagens:
Reuso: uma vez definido, implementado e testado, o TAD pode ser acessado por diferentes programas. Manutenção: mudanças na implementação do TAD não afetam o código fonte dos programas que o utilizam (decorrência do ocultamento de informação), módulos do TAD são compilados separadamente, uma alteração força somente a recompilação do arquivo envolvido e uma nova link-edição do programa que acessa o TAD. O programa mesmo não precisa ser recompilado! Correção: TAD foi testado e funciona corretamente
40. Por que é interessante utilizar cabeçalhos nos arquivos?
Em geral, é interessante manter algumas informações sobre o arquivo para uso futuro. Essas informações podem ser mantidas em um cabeçalho no início do arquivo. A existência de um registro cabeçalho torna um arquivo um objeto auto-descrito. O software pode acessar arquivos de forma mais flexível.
41. 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?
O torna possível por que ele ordena o arquivo através da estratégia de alocação de espaço, first-fit(pega-se o primeiro que servir) e depois coloca o espaço que sobrou na lista LD, é uma boa estratégia, independente da forma que se escolhe o espaço e é possível fazer busca binaria pois o arquivo se encontra ordenado. 
FALTA SEGUNDA PARTE.
42. 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?
Porque pode haver vários CDs com o mesmo título.
Tratar maiúsculo e minúsculo como a mesma coisa.
43. 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?
44. 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.
Alterou uma chave secundária: o índice secundário para esta chave precisa ser reordenado. 
Alterou a chave primária: atualizar (reordenar) o índice primário e corrigir os campos de referência índices secundários. Vantagem: atualização dos índices secundários não requer reorganização! Alterou outros campos: não afeta nenhum dos índices.
45. 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
46. 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.
O que é:
Lista invertida ou índice invertido é um estrutura de dados que permite mapear um conjunto de palavras e símbolos dentro de um arquivo. Desta maneira, facilita a busca de informações em uma estrutura de dados. É usada principalmente na busca de informações em WEB como por exemplo a busca no Google.
Aplicação:
Listas invertidas são um elemento central de sistemas de busca, pois estes visam trazer resultados de forma rápida e eficiente. Buscas por termos em uma lista tradicional exigiram percorrer cada documento e cada palavra dentro destes em busca do termo, enquanto que, com o uso de um índice reverso, pode-se saltar diretamente para o termo buscado. Logo, o uso deste recurso permite que os resultados sejam obtidos de forma consideravelmente mais rápida (a diferença de desempenho tende a ser cada vez mais significativaconforme aumenta a quantidade de documentos). O uso de listas invertidas tem o potencial de deixar as buscas mais eficientes, dado que estas permitem que sejam armazenadas informações adicionais que, acompanhadas de algoritmos adequados, tornam fácil a classificação e ordenação dos resultados.
Referências às chaves primárias associadas a cada chave secundária podem ser mantidas em um arquivo sequencial separado, organizado segundo a entrada dos registros.
Esquema:
	ANG3795
	DG139201
	DG18807
	RCA2626
	BEETHOVEN
	COREA
	DVORAK
	PROKOFIEV
	WAR23699
	COL31809
	LON2312
47. Como são alteradas as estruturas mostradas na figura 6.11 pela inclusão do registro abaixo?
LON 1259 Fidelio Beethoven Maazel
48. 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;
b. Liste todas as gravações de Perleman de peças de Mozart ou Joplin.
49. 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 sobre os pacientes pelas chaves Nome do paciente, Código do paciente, Localização, Medicação, Médico ou Médicos, e Doença.
50. 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?
6 minutos aproximadamente
b. Quanto tempo durará a ordenação do arquivo usando o algoritmo key sort?
O(800.000)
c. Por que o algoritmo key sort não funcionará se houver 1MB de RAM disponível para a fase de ordenação?
51. Quantos posicionamentos (seeks) são necessários para uma intercalação em um único passo, se um posicionamento toma 50ms, em média, e o tamanho do buffer interno disponível é 500k? E se for 100k?
52. 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?
b. Quanto tempo os passos 1, 2 e 3 levam?
c. Qual é o impacto de um aumento no tamanho do arquivo por um fator 10 terá no tempo total do merge sort?
53. 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.
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.