Lista De Exercícios 1 - AEDS II

Prévia do material em texto

1) Diferencie memória principal e memória secundária. Dê exemplos.
Resposta: 
A memória principal é uma memória de acesso rápido que armazena dados/informações, 
custando mais por bit e normalmente com menor capacidade, volátil. Já a secundária é 
caracterizada pelo acesso mais lento, grande capacidade de armazenamento e menor custo.
Exemplos: 
Memória principal: Dynamic Randon Access Memory – DRAM
Memória secundária: HD, SSD
2) Explique o funcionamento e estrutura do HD e apresente as diferenças em relação ao 
SSD.
Funcionamento e estrutura: as informações gravadas em um disco são armazenadas na 
superfície de um ou mais platters (discos magnéticos), sendo armazenadas em sucessivos tracks 
(trilhas). Cada track é dividido em um número de sectors (setores).
O SSD(solid-state drive) é um tipo de memória flash que utiliza dois transistores (gates) ao
invés da estrutura do disco. O primeiro transistore ativa a célula e faz a leitura dos dados e no 
segundo são armazenados os dados, ficando entre duas camadas de óxido de silício, as camadas 
de óxido de silício armazenam cargas negativas, impedindo a saída da carga armazenada no 
segundo gate, mantendo os dados sem que seja necessário energia elétrica. 
3) Explique como são calculadas a capacidade e o desempenho de um HD.
Capacidade do HD: um cilindro consiste em grupos de trilhas, uma trilha consiste em 
grupos de setores e um setor consiste em grupos de bytes. Logo podemos computar:
• Capacidade da trilha: número de setores por trilha x bytes por setor;
• Capacidade do cilindro: número de trilhas por cilindro x capacidade da trilha;
• Capacidade do disco: números de cilindros x capacidade do cilindro.
Desempenho HD:
Largura de banda: Velocidade mais rápida na qual o disco pode enviar e receber dados 
pelo cabo (ou barramento) a partir do buffer do disco.
Acessar dado é localizar e posicionar na superfície, trilha e setor:
• Tempo de busca (seek time): tempo para mover o braço até a trilha (Full Stroke, Track-
to-track, Average; a média costuma ser abaixo de 10ms);
• Tempo de latência rotacional: tempo para atingir o início do setor a ser lido/escrito;
• Tempo de transferência: tempo efetivo para escrita/leitura dos dados.
4) Considere os seguintes dados técnicos:
•T_seek= 3ms.
•15000rpm (15000/60 = 250rps).
•512 Bytes/setor.
•500 setores/trilha.
•Leitura de um arquivo de 5000 setores.
Considere que os setores deste arquivo estão distribuídos aleatoriamente pelo disco, encontre o 
tempo de acesso de todo o arquivo.
Resposta:
T_seek = 3 ms
tr = 1/(2r) = 1/(2*250) = 0,002 * 1000 = 2 ms
b = 1*512
N = 512*500
T = b/(rN) = (1×512)/(250×500×512) = 0,000008 * 1000 = 0.008 ms
Tempo de acesso de um setor: 3+2+0,008 = 5,008 ms
Tempo de acesso total: 5000 * 5,008 = 25,04 ms
5) Relacione os modos de abertura de arquivos:
r:Abre um arquivo texto para leitura (se não existir retorna NULL)
w:Abre um arquivo texto para escrita (se existir o conteúdo é apagado, se não, será criado)
a:Abre (se existir) ou cria um arquivo texto para escrita, preservando o conteúdo existente
r+:
Abre um arquivo texto para leitura e escrita (atualização) (se arquivo não existe, retorna 
NULL)
w+:
Cria e abre um arquivo texto para leitura e escrita (se arquivo já existe, conteúdo é 
apagado)
a+:
Abre (se já existir) ou cria um arquivo texto para leitura e escrita – cursor é posicionado 
no final do arquivo
b:Deve ser acrescentado quando o arquivo for binário
6) Explique a finalidade das seguintes funções:
Resposta:
fprintf(): é para um arquivo o que printf() é para o console (grava o campo no arquivo)
fscanf(): é para um arquivo o que scanf() é para o console (captura o campo do arquivo)
fread(): Lê um fluxo de bytes no arquivo binário
fwrite(): Escreve um fluxo de bytes no arquivo binário
fseek(): Altera a posição de leitura/escrita no arquivo binário
ftell(): Retorna a posição atual do cursor no arquivo binário
7) Como saber o endereço de um determinado registro?
Resposta:
Endereço é definido sempre como um deslocamento em relação a um ponto de partida 
(normalmente se usa o início do arquivo como referência) onde tamanhoReg é o tamanho dos 
registros do arquivo, em bytes: 
EndereçoReg(i) = (i – 1) * tamanhoReg
8) Como pode ser feita a organização de registros em arquivo?
Resposta:
• Tamanho Fixo:
◦ Campos de tamanho fixo;
◦ Campos de tamanho variável.
• Tamanho Variável:
◦ Número fixo de campos;
◦ Indicador de tamanho;
◦ Delimitadores;
◦ Índices.
9) Explique como é possível fazer o gerenciamento de espaço em registros de tamanho fixo 
e de tamanho variável em relação aos métodos de exclusão e inserção.
Operações básicas com registros em arquivos
• Exclusão de registros: gera espaços vazios no arquivo.
◦ Reconhecer áreas que foram apagadas. Geralmente, áreas apagadas são 
marcadas com um marcador especial: * |
◦ Lista encadeada de registros excluídos no próprio arquivo.
▪ Registros de tamanho fixo: pilha de RRNs (relative record number) vagos. 
Topo da pilha está no cabeçalho do arquivo. Cada registro excluído contém 
o RRN do próximo removido.
▪ Exclusão de registros de tamanho variável com indicador de tamanho: cada
registro removido é marcado com um caracter específico no primeiro 
campo (*) seguido por um delimitador (|) e por um campo de byte offset 
apontando para o próximo registro removido na lista.
• Inserção de registros: operação simples, final do arquivo.
◦ Recuperar e utilizar os registros vazios:
▪ Em tamanhos variáveis, para reusar um registro, ele deve ser “grande o 
suficiente” para armazenar o novo registro inserido. A inserção de registros 
excluídos na lista de vagos pode ser feita na frente (como pilha) mas a 
remoção para reuso poderá ser feita em qualquer posição da lista. É 
necessário uma busca sequencial na lista para encontrar uma posição com 
espaço suficiente. Se atingir o final da lista e não encontrar registro 
reusável, o novo registro vai para o final do arquivo.
▪ Em registro de tamanho fixo, pode ser inserido no primeiro espaço 
disponível.
10) Por qual motivo é interessante utilizar Pilha de RRNs vagos de registros de tamanho 
fixo?
Resposta:
Como todos os registros têm o mesmo tamanho, não há razão para preferir um registro 
ao outro. Não há motivo para manter a lista de vagos em uma ordem específica. Pilha é a forma 
mais simples de manipular a lista. Pilha resulta em um mínimo de operações para reorganizar a 
lista quando se empilha e desempilha.
11) Diferencie os algoritmos InsertionSort e Busca binária para ordenação externa de 
arquivos.
Resposta:
A busca binária por um dado registro ou campo poderá ocorrer se o arquivo estiver 
ordenado, na busca binária lê-se o registro do meio e compara a chave buscada com a chave do 
registro lido e repete procedimento na metade do arquivo correspondente (se chave menor, na 
metade de cima, se chave maior, na metade de baixo). Para podermos efetuar a busca binária, 
podemos utilizar o algoritmo InsertionSort para ordenar o arquivo. Outros algoritmos de 
ordenação também podem ser utilizados. O InsertionSort assume que o primeiro valor já está 
ordenado, pega o próximo valor, compara com os anteriores até descobrir em que posição ele 
deveria estar.
12)Descreva a finalidade do código a baixo:
int left = 0, right = tam-1;
while(left <= right){
 int middle = (left+right)/2;
 fseek(arq, middle*tamanho_registro(), SEEK_SET);
 TFunc* func = le(arq);
 if(cod == func->cod) {
 return func;
 }
 else if(func->cod < cod) {
 left = middle+1;
 }
 else {
 right = middle-1;
 }
}
Resposta:
Realiza a busca binária em arquivos binários.
13) Explique o processo de interpolação.
Resposta:
Divide os arquivos em pequenas frações que são ordenadas e intercaladas em duas 
etapas: classificação e intercalação.
14) Explique e diferencie os métodos de geração de partições:
•Classificação interna:
• Leitura de M registros para a memória;
• Classificação desses registros por qualquer processode classificação interna 
(bubble sort, shaker sort, quick sort, heap sort, shell sort, merg sort…);
• Gravação desses registros classificados em uma partição.
•Seleção com substituição:
• Aproveita a possível ordenação parcial do arquivo de entrada;
• A desvantagem é que no final da partição grande parte do espaço em memória 
principal está ocupado com registros congelados.
•Seleção natural:
• Reserva-se um espaço de memória secundária (o reservatório) para abrigar os 
registros congelados num processo de substituição.
• A formação de uma partição se encerra quando o reservatório estiver cheio ou 
quando terminarem os registros de entrada.
15) Como funciona o algoritmo básico para fazer a intercalação das partições.
Intercalação: algoritmo básico
• Considere cada arquivos a ser intercalado como uma pilha de registros salvos em
memória.
• A cada iteração do algoritmo, o topo da pilha com menor chave é gravado no
arquivo de saída e é substituído pelo seu sucessor. O algoritmo termina quando todos os topos 
da pilha tiverem high value.
• A cada iteração, encontra-se a menor chave (O(n)), n é o número de arquivos a 
intercalar
• Número de iterações = número total de registros a serem ordenados
16) Explique com suas palavras as estratégias de distribuição e intercalação:
•intercalação balanceada de N caminhos:
• arquivos disponíveis são distribuídos em dois conjuntos. Partições iniciais são 
distribuídas, tão equilibradamente quanto possível, nos arquivos de um dos 
conjuntos. Durante cada fase da intercalação são lidos registros dos arquivos no 
conjunto que recebeu as partições iniciais (conjunto de entrada) e o resultado das 
intercalações é gravado nos arquivos do conjunto de saída, ciclicamente.
•intercalação ótima:
• durante cada fase do algoritmo, F-1 partições são intercaladas e gravadas no 
arquivo de saída. Do conjunto inicial de partições removem-se as partições 
intercaladas e a ele agrega-se a partição gerada na intercalação. Algoritmo termina
quando este conjunto tiver apenas uma partição.
•intercalação polifásica:
• para eliminar as cópias de partições sem que elas sejam intercaladas pode-se fazer
sempre intercalações de ordem F-1. A Intercalação polifásica opera exigindo que a 
fase de classificação interna distribua as partições, entre os F-1 arquivos 
disponíveis para entrada, de maneira especialmente determinada para otimização 
do algoritmo. Em cada fase do algoritmo intercalam-se F- 1 arquivos até chegar ao 
final de qualquer uma delas. Nesse ponto, interrompe-se a fase deixando o 
restante dos arquivos para a fase seguinte.
17) Sobre fragmentação externa, explique as estratégias de alocação de espaço.
First-fit: seleciona o primeiro registro que servir, independente se o registro vago é muito 
maior ou justo para o novo registro.
Best-fit: seleciona o menor registro que servir.
1. Organiza-se a lista de vagos em ordem crescente de tamanho, buscando o 
primeiro registro que couber.
2. Percorrer a lista tanto para inserir registros vagos quanto para reusar registros, ou 
seja, remover da lista.
3. O espaço que sobra pode ser tão pequeno que não dá para reutilizar, resultando 
em fragmentação externa.
4. Com o tempo aumenta o tempo de busca pelo menor registro pra reuso pois os 
menores e que provavelmente não serão usados estarão no início da lista.
Worst-fit: seleciona o maior que servir, diminui a fragmentação externa.
1. Cria lista de excluídos em ordem decrescente de tamanho.
2. O processamento pode ser mais simples pois se o primeiro registro da lista de 
disponíveis não é grande o suficiente para armazenar o novo registro, nenhum 
outro da lista será. Busca é O(1).
3. A porção que sobra ao inserir um novo registro no maior espaço disponível é tão 
grande quanto possível, diminuindo a probabilidade de fragmentação externa.