Organização e Recuperação da Informação Memória Secundária

Organização e Recuperação da Informação Memória Secundária

Dr. Ednaldo Pizzolato

ORI - DISCOS

• Memória Secundária– Não Volátil– Lenta– Barata

• Memória Primária– Volátil– Rápida– Cara

ORI - DISCOS

ORI - DISCOS

ORI - DISCOS

• UNIDADE BÁSICA DE MEMÓRIA• O computador só pode identificar a informação

através de sua restrita capacidade de destinguir entre dois estados, por exemplo, algo está imantado num sentido ou está imantado no sentido oposto. A uma dessas opções o computador associa o valor 1, e ao outro estado, o valor 0.

• Os dígitos 0 e 1 são os únicos elementos do sistema de numeração de base 2, sendo então chamados de dígitos binários, ou abreviadamente, bit. Entenda-se por bit a unidade básica de memória, ou seja, a menor unidade de informação que pode ser armazenada num computador.

ORI - DISCOS

A tecnologia de gravação mais usada é a magnética, baseada em materiais que podem ser magnetizados (como o óxido de ferro e outros). Esta tecnologia foi usada inicialmente para a gravação de sons e depois adaptada para a gravação digital que os computadores exigem.

ORI - DISCOS

A superfície do disco, recoberta com uma fina camada de material magnetizável (quanto mais fina, melhor), é tratada como uma matriz de pontos. Cada ponto é considerado como um bit que pode ser definido como o equivalente magnético de 0 ou 1. Como a posição dos pontos não é determinada com precisão, o esquema de gravação envolve algumas marcas de orientação. Estas marcas são um dos motivos pelos quais um disco precisa ser formatado antes de poder ser utilizado.

ORI - DISCOS

Os discos (ao contrário das fitas que têm leitura/gravação linear) proporcionam acesso rápido por dois motivos: rotação e movimentação do cabeçote. Com a rotação, qualquer parte da circunferência do disco passa rapidamente por qualquer ponto determinado. A movimentação do cabeçote no sentido centro-borda aumenta ainda mais sua velocidade de acesso.

ORI - Trilhas

• A superfície dos discos é dividida em círculos concêntricos, as chamadas trilhas. Cada trilha é numerada, começando pelo círculo mais externo que recebe o número 0 (zero). O disquete de 1.44 Mb, por exemplo, possui 80 trilhas; os HDs costumam ter de 500 a mais de 1000 trilhas, dependendo do modelo. É bom lembrar que o perímetro da trilha 0 (a primeira e mais externa) é bem maior que o perímetro da trilha 79 (a última e mais central).

ORI - Trilhas

• A maioria das pessoas imagina que as trilhas cubram toda a superfície do disquete, mas não é bem assim. Basta fazer umas continhas sabendo que o disquete de 1.44 Mb e 3.5 polegadas grava dados na proporção de 135 trilhas por polegada, ou seja, poderia gravar cerca de 470 trilhas (135x3.5=472.5). Como existem 80 trilhas, a superfície que elas ocupam corresponde apenas a cerca de 0.6 polegadas, algo em torno de 1.5 cm dos 8.4 cm de superfície total.

ORI - Setores

• Cada uma das trilhas é dividida em porções menores - os setores. O tipo de disco determina o número de setores por trilha. O disquete de 3.5 polegadas e 1.44 Mb tem 18 setores por trilha e os HDs, novamente, podem ter números diferentes de setores dependendo do modelo além de poderem possuir mais setores nas trilhas mais externas.

ORI - Setores

• Os setores também são numerados. Os setores 0 (zero) de cada trilha estão reservados para identificação ao invés de armazenamento de dados. Eles têm sempre um tamanho fixo, que pode ser de 128 a 1024 bytes. O tamanho mais utilizado é de 512 bytes. Toda leitura e gravação é feita em termos de setores completos, mesmo que os dados ultrapassem setores e ocupem o último parcialmente.

ORI - Lados

• Nada impede a utilização das duas faces de um disco para armazenar dados. Deste modo, os chamados dupla face, possuem o lado 0 e o lado 1. Neles existem dois cabeçotes (por aste). Alguns HDs possuem um "sanduiche" de discos. Neste caso, os lados são numerados sequencialmente: lados 0 e 1 (do disco 1), lados 2 e 3 (do disco 2) e assim sucessivamente.

ORI - Cilindros

• O conjunto de trilhas com a mesma distância do centro em cada face do disco é chamado de cilindro. Imagine um HD com 3 discos de dupla face superpostos. Neste caso, existem 6 lados, numerados de 0 a 5. As trilhas de todas as faces ficam alinhadas na vertical, como se formassem tubos concêntricos. Cada um destes tubos é o chamado cilindro. Em outras palavras, um cilindro inclui uma trilha de cada uma das superfícies. Em um disquete, um cilindro sempre consiste de duas trilhas correspondentes, uma de cada lado.

Calculando capacidades

• Para calcular a capacidade bruta de qualquer disco, basta fazer algumas multiplicações. Tomemos como exemplo um disquete de dupla face com 80 trilhas por lado e 18 setores por trilha. Inicialmente multiplique o número de lados pelo número de trilhas por lado: 80 x 2 = 160. Agora multiplique o resultado pelo número de setores por trilha: 160 x 18 = 2880. Finalmente, multiplique o resultado pelo número de bytes por setor (512 bytes = 0.5 Kb): 2880 x 0.5 = 1440 Kb = 1.44 Mb.

ORI - DISCOS

ORI - DISCOS

ORI - DISCOS

ORI - DISCOS

Evolução dos HDs

ORI - DISCOS

• Conceitos– Tempo de acesso (seek time): é o tempo gasto para a cabeça de

leitura/gravação se posicionar na trilha correta. Varia de 3 ms (para trilhas adjacentes) e até 100 ms (para trilhas que estão nos extremos do disco).

– Tempo de Latência Rotacional (rotational delay): é o tempo gasto para localizar o setor ao qual se quer ter acesso. O tempo total de acesso é a soma destes dois tempos (seek + latência rotacional). A latência rotacional varia de 0 ao tempo de uma rotação completa (a 3600 rpm, a LR é 16,67 ms).

– Tempo de transferência (transfer time): é o tempo gasto para a migração dos dados da memória secundária para a memória principal.

– Tempo de acesso: é a soma dos tempos: seek + latência + transferência.

– Taxa de transferência: é a velocidade com a qual os dados migram da memória secundária para a memória principal. Ex.: 1.200 kbps.

ORI - DISCOS

• O tempo de acesso está relacionado com a velocidade de movimentação das cabeças de leitura e gravação do disco rígido. Podemos entender facilmente que quanto mais veloz for o movimento das cabeças, mais rapidamente o disco poderá acessar qualquer dado nele armazenado. Chamamos de tempo médio de acesso, ou simplesmente tempo de acesso, o tempo necessário para mover o braço desde o primeiro cilindro até o cilindro central.

ORI - DISCOS

• O tempo de acesso de uma memória é dependente do modo como o sistema de memória é construído e da velocidade dos seus circuitos. Ele varia bastante de acordo com o tipo de memória analisado, sendo valores típicos aqueles numa faixa entre 50 e 150 nanossegundos (ns), para a memória principal (ou memória DRAM); de 8 a 15 mili-segundos para discos magnéticos (memória secundária), enquanto fitas magnéticas têm tempo de acesso da ordem de poucos segundos.

ORI - DISCOS

• Ao lado do tempo médio de acesso, a taxa de transferência interna é o mais importante fator que define o desempenho de um disco rígido.

• Enquanto o tempo médio de acesso é decisivo na leitura de arquivos pequenos em grande quantidade, a taxa de transferência interna é o principal fator envolvido na velocidade de leitura e gravação de arquivos grandes.

ORI - DISCOS

• Os discos rígidos possuem uma área interna de memória, para onde são lidos os dados que serão posteriormente transferidos para a placa de CPU.

• Esta área é chamada de cache ou buffer.

ORI - DISCOS

• Quando um disco rígido IDE transfere dados, estão envolvidos dois tipos de transferência:

• 1. Transferência da mídia magnética para a cache interna do disco

• 2. Transferência da cache interna do disco para a placa de CPU

ORI - DISCOS

• A taxa de transferência interna representa a velocidade na qual a primeira transferência é feita. A velocidade na qual a segunda transferência se faz, é chamada de taxa de transferência externa. Para que o disco rígido possa fazer uma transferência completa (mídia - cache - CPU) de forma mais veloz, tanto a transferência interna como a externa precisam ser rápidas.

ORI – DISCOS (BLOCOS)

Bloco

Uma seqüência contígua de setores de uma única trilhaOs dados são trasferidos entre o disco e a memória principal em blocosOs tamanhos variam de 512 bytes até vários kilobytes– Blocos menores: mais transferências do disco– Blocos maiores: mais espaço desperdiçado, devido a blocos

parcialmente cheios– Os tamanhos típicos de blocos hoje variam de 4 a 16 kilobytes

ORI – DISCOS (BLOCOS)

Bloco

Algoritmos de Agendamento do braço do disco

Ordenam os acessos pendentes para as trilhas para minimizar a movimentação do braço do disco.

Algoritmo elevador: move o braço do disco em uma direção (das trilhas externas para as internas e vice-versa), processando a próxima requisição naquela direção, até que não haja mais requisições naquela direção, então reverte a direção e repete.

ORI – DISCOS (blocos)

• Suponha que tenhamos um disco organizado em blocos com capacidade para 20.000 bytes (por trilha) e que para armazenar um bloco o sistema gaste 300 bytes a mais com informações de suporte e espaçamento entre blocos.

• Queremos armazenar um arquivo que tem registros de tamanho igual a 100 bytes. Quantos registros podem ser armazenados em cada trilha com fator de bloco igual a 10?


• Se temos 100 bytes por registro e o fator de bloco é 10, então cada bloco armazena 1000 bytes de dados e mais 300 bytes de informação de controle. Assim, cada bloco utiliza 1300 bytes. Se temos 20.000 bytes em uma trilha, isso implica em 20.000 / 1.300 = 15.38 blocos.

• Como precisamos de um número inteiro, teremos 15 blocos com 10 registros 150 registros por trilha.


• E se o fator de bloco fosse 60?

• Se fosse 60 teríamos 6000 bytes de dados (60 x 100) + 300 bytes de controle.

• Assim, teríamos 20.000 / 6.300 = 3

• Ou sejam, 3 blocos com capacidade de 60 registros = 180 registros por trilha (contra 150 da versão anterior). É mais vantajoso utilizar o fator 60...

ORI – DISCOS (organização)Organização de Arquivos

Otimiza o tempo de acesso aos blocos organizando-os para corresponder à forma como os dados serão acessados. Por exemplo: armazenar informações relacionadas no mesmo cilindro ou em cilindros próximos.

Fragmentação : Os blocos livres no disco ficam espalhados ou os arquivos novos têm seus blocos espalhados pelo disco:– Acesso seqüencial a um arquivo fragmentado resulta em maior

movimentação do braço do disco

Alguns sistemas possuem utilitários para desfragmentar o sistema de arquivos, para tornar mais rápido o acesso aos arquivos

ORI – DISCOS (organização)

Vamos analisar 2 situações diferentes de processamento de arquivo para demonstrar como o acesso à informação pode ser afetado pelo tempo de acesso.

Situação 1 – Tempo para acessar o arquivo em seqüência.

Situação 2 – Tempo para acessar o arquivo aleatoriamente.


O melhor desempenho para transferência de dados ocorre quando os arquivos estão em uma trilha. O arquivo tem 8.704.000 bytes e está dividido em 34.000 registros de 256 bytes cada.Primeiramente, é importante descobrir como o arquivo está distribuído no disco.Um bloco com 4096 bytes comporta 16 registros. O arquivo será armazenado de forma a ter uma seqüência de 2125 blocos que serão distribuídos em 100 trilhas.


Assumiremos que as 100 trilhas estão dispersas aleatoriamente no disco (situação extrema apenas para enfatizar a conclusão).Devemos estimar o tempo que se deve consumir para ler o arquivo em seqüência (setor por setor). O processo envolve os seguintes tempos:

seek time = 8 msecrotational delay = 3 msecleitura de uma trilha = 6 msec

Total para uma trilha = 17 msec

ORI – DISCOS (organização)Como desejamos a leitura de 100 trilhas temos : 100 x 17 msec = 1.7 segundos

A segunda situação assume que os setores podem estar em posições distintas (não seqüencial), e assim, a cabeça de leitura terá que ficar “pulando” de uma posição para outra. Para ler um registro é preciso ler um bloco:

seek time = 8 msecrotational delay = 3 msecleitura de um bloco = 1/21.5 x 6) = 0.28 msectotal = 11.28 msec

Como temos 34.000 registros, teremos 34.000 x 11.28 ms = 9,25 s

ORI – CD-ROMS

• Desenvolvido inicialmente pela Philips, e em seguida com a colaboração da Sony, os cd-roms têm se tornado muito populares. Seguros, duráveis, fáceis de armazenar e com alta capacidade de armazenamento, eles têm se tornado um grande meio de distribuição de programas.

ORI – CD-ROMS

• O nome cd-rom vem de compact disk read only memory. Como o próprio nome diz, ele é uma memória rom, isto é, memória somente de leitura (não pode ser alterada).

ORI – CD-ROMS

• Um cd é gravado utilizando um laser de alta potência. Com este laser são feitos “furos” (pits) em um disco. As áreas não “furadas” entre os pits são chamadas lands. Com os pits têm uma refletividade diferente dos lands, pode-se, assim, representar uma informação digital (dois estados).

ORI – CD-ROMS

• O processo de leitura é feito através da interpretação de altos e baixos relevos (PITS e LANDS), impressos no CD-ROM durante o processo de fabricação. Os PITS tem 0,12 microns por 0,6 microns de largura, sendo que a distância entre os mesmos corresponde à espiral de 1,6 microns representando uma taxa de 16000 TPI (trilhas por polegadas), muito maior de que hoje temos nos disquetes 5 1/4” 360 kbytes.

ORI – CD-ROMS

• É usado para leitura, um feixe de laser (Light Amplification by Stimulated Emission of Radar), circular de aproximadamente 1 mícron de diâmetro. Para se produzir esse feixe de laser é necessário aumentar a sua intensidade, que irá passar por uma série de lentes de altíssima qualidade, a fim de incidir sobre a face reflexiva do CD-ROM.

ORI – CD-ROMS

• Assim, de um lado temos o disco CD-ROM e do outro um feixe de laser incidindo sobre a espiral (PITS/LANDS), que é refletida pela camada de alumínio que compõe o CD-ROM.

ORI – CD-ROMS

• Quando o feixe incidir sobre uma microcavidade (baixo relevo “LAND”), ela será refletida ordenadamente com a mesma intensidade, voltando através do sistema de lentes e passando por um fotodetector que produzirá uma corrente elétrica de intensidade proporcional ao feixe recebido.

ORI – CD-ROMS

• De outro modo, quando o feixe incidir sobre um PIT (alto relevo) será refletido em diversas direções, dispersando a intensidade de luz refletida e, voltando pelo sistema óptico com uma baixa intensidade, irá gerar uma corrente elétrica de baixa intensidade.

ORI – CD-ROMS

• Quando se armazenam dados, em qualquer meio, eles devem ter uma forma que seja aceitável por esse meio. Em todas essas formas, é utilizado o sistema de representação binário (1/0). Nos CD’s temos os PITS e LANDS (espaço entre pits), que não correspondem a 1s e 0s. O conceito de representação binária dos 1s é através da mudança de estado de PIT para LAND ou, de LAND para PIT, e o tamanho do PIT ou LAND indica o número de 0s.

ORI – CD-ROMS

• Transições adjacentes, (PIT/LAND/PIT), não conseguem ser lidas pelo sistema óptico. Para solucionar este problema foi definido um tamanho mínimo de LAND (2 bits) e um tamanho máximo (11bits) para que durante a leitura dos dados não houvesse perda de sincronismo e que não prejudicasse o sistema de leitura do CD-ROM .

ORI – CD-ROMS

• Para que isso fosse realizado, foi adotada para o CD-ROM uma modulação de dados chamada EFM (Eight Fourteem Modulation), que transforma um byte (8 bits) de dados do usuário em 14 bits, que representam um caractere ou símbolo. A utilização da conversão EFM (8 para 14 bits), faz com que seja possível o tamanho mínimo (land máximo de 11 bits), mas como existe a possibilidade do fim da representação de um caractere (seqüência de 14 bits) terminar com “1” e o próximo caractere também iniciar com “1” para que isso não ocorra, é introduzido uma seqüência de três bits (merge bits) entre os caracteres.

ORI - EFM

• Eight to Fourteen Modulation 00000000 01001000100000

00000001 1000010000000000000010 1001000010000000000011 1000100010000000000100 0100010000000000000101 0000010001000000000110 0001000010000000000111 0010010000000000001000 0100100100000000001001 1000000100000000001010 10010001000000

ORI – CD-ROMS

• A divisão lógica dos CD´s é totalmente diferente de um disquete ou disco rígido. Os dados não são gravados em trilhas e setores, mas numa espiral contínua, em blocos de dados. Um CD de 553 Mb, por exemplo, tem 270.000 blocos de dados.

ORI – CD-ROMS

• Os primeiros drives de CD-ROM operavam com a taxa de transferência de 150 kB/s, a mesma utilizada pelos CD Players para áudio. Surgiram os drives de velocidade dupla (2x), com taxa de 300 kB/s. Os drives mais antigos passaram a ser chamados de drives de velocidade simples, ou 1x. Seguiram-se os drives de velocidade tripla (3x), quádrupla (4x), e assim por diante.

ORI – CD-ROMS

• Tipo Taxa de transferência• 1x 150 kB/s• 2x 300 kB/s• 3x 450 kB/s• 4x 600 kB/s• 6x 900 kB/s• 8x 1,2 MB/s• 10x 1,5 MB/s• 12x 1,8 MB/s• 16x 2,4 MB/s• 20x 3,0 MB/s

ORI – CD-ROMS

Nos bons tempos, para comparar o desempenho de um drive, bastava saber sua velocidade, a velocidade média de acesso, a velocidade média de procura, e o tempo médio entre falhas (MTBF).

ORI – CAV

Para compreender a lógica por trás da tecnologia CAV (Constant Angular Velocity, ou Velocidade Angular Constante), é importante observar como os dados são gravados.

Discos rígidos, por exemplo, usam velocidade angular constante ou CAV para ter acesso a informações, o que significa que em qualquer área do disco passa por um ponto especificado, o cabeçote do disco, a uma taxa constante.

ORI – CAV

Os setores num disco rígido são semelhantes aos raios de uma roda de bicicleta. No centro do disco, os dados estão mais compactados. Já na borda externa, as informações são gravadas de forma mais espalhada.

Devido a essa variação de densidade de dados, o disco pode girar a uma velocidade constante e ler os dados a uma velocidade constante, estando no centro do disco ou em sua borda externa.

ORI – CLV

Ao contrário dos discos rígidos, a tecnologia de CD foi desenvolvida usando o padrão CLV (Constant Linear Velocity, ou Velocidade Linear Constante), pois os criadores de CDs de Áudio desejavam colocar o máximo de música possível no CD.

ORI – CLV

Para tanto, as especificações determinavam que cada setor num CD deveria ocupar o mesmo comprimento ao longo da trilha espiral, ao invés de espalhar os dados ao aproximar-se da borda do disco.

ORI – CLV

Para ler estes setores eqüidistantes no centro do disco à mesma velocidade que os da borda externa, era necessário acelerar o motor nas trilhas internas e reduzir sua rotação nas trilhas externas.

ORI – CLV

Diversos fatores forçaram os fabricantes de drives de CD-ROM a migrar da tecnologia CLV native do CD-ROM para a tecnologia CAV. O principal fator de limitação para a velocidade de drives de CD-ROM está nos próprios discos. Num drive de CD-ROM 12X CLV, a velocidade de rotação varia de 2.400 rpm a 6.360 rpm. A 6.360 rpm o disco está girando o mais rápido possível antes que pequenas imperfeições com o disco e a legenda impressa nele desequilibrem o disco em relação ao seu eixo de rotação, provocando vibrações e reduzida confiabilidade na leitura de dados.

ORI – CLV

Por outro lado, um drive usando tecnologia CAV não precisa girar tão rápido para atingir velocidades de leitura maiores, tendo portanto menos torque no motor e vibração reduzida.

ORI – CLV x CAV

ORI – CD-R

• A sigla CD-R significa cd recordable. Um cd deste tipo pode ser gravado somente uma vez. Representa uma evolução dos Cd-roms comuns justamente pela capacidade de serem graváveis pelo usuário comum.

ORI – Discos Ópticos Apagáveis

• A terceira fase da evolução dos discos óticos é o cd óptico apagável. Com este tipo de mídia, podem ser realizadas várias gravações.

• Como? • R: Utilizando-se ligas metálicas exóticas, que

mudam suas propriedades de acordo com a temperatura. Na temperatura ambiente, suas propriedades não são alteradas, mas, a altas temperaturas, estas ligas (térbio, gadolínio), ficam sensíveis a campos magnéticos.

ORI - Digitalização

Quando queremos armazenar som,precisamos converter a onda em pa-drões digitais.


• A onda é representada por um gráfico de amplitude contra o tempo.


• Como estamos digitalizando, precisamos armazenar as amplitudes em períodos regulares para, depois, reconstruírmos o gráfico referente à onda.




• O CD de áudio utiliza 16 bits para armazenar cada amplitude. Isso significa que a amplitude pode ter 65536 graus de diferença. Existem restrições para o armazenamento adequado do som: é preciso armazenar as amplitudes um uma taxa no mínimo duas vezes maior que a mais alta freqüência que queremos capturar. Normalmente o “sampling” rate é de 44.1 KHz (ou 44.100 vezes por segundo) que permitem capturar freqüências de até 20 KHz (o limite da audição humana).


• Assim, 16 bits (2 bytes) a uma taxa de 44.100 vezes por segundo 88.200 bytes por segundo. Se for som estéreo, precisamos dobrar 176.400 bytes por segundo.

ORI – Sistemas de Detecção de Erros

• Pesquisar os sistemas de detecção de erros (CRC...)

ORI – External Sorting

• Em várias aplicações pode-se ter a necessidade de se organizar os dados em uma determinada ordem.

• Entretanto, em muitos casos, os arquivos podem ser muito grandes de forma que seus dados não possam estar todos em memória ao mesmo tempo.


• Para ilustrar, vamos supor, nesta aula, que tenhamos um arquivo com 8 milhões de registros, cada um de 100 bytes. O espaço em disco necessário para armazenar estes dados é de 800 megabytes.

• O espaço disponível em memória para trabalho é de 10 megabytes (espaço livre após contar-se o utilizado pelo SO, buffers...)


• Podemos utilizar um algoritmo como o quicksort – por exemplo – ou uma árvore binária para ordenar um subconjunto dos dados, de tal forma que possam ocupar quase todo o espaço disponível do sistema.

• Após isso, devemos escrever os dados (ordenados) de volta no arquivo e proceder com o restante. A este subconjunto damos o nome de rodada.


• Em nosso exemplo, uma rodada seria:– 10.000 bytes / 100 bytes (registro) = 100.000 registros

Após a primeira rodada, deve-se ler um segundo subconjunto de dados do arquivo e criar uma nova rodada...

E, após 80 rodadas, pode-se combinar os resultados para se gerar um único arquivo (ordenado).


arquivo desordenado

arquivo ordenado


• Two-way Sort / Merge• 50 110 95 10 100 36 153 40 120 60 70 130 22 140 80

• O número máximo de elementos que podem ocupar o espaço de memória de trabalho é 3. Assim, nossas rodadas podem ter no máximo tamanho 3:

• F1 [50 95 110] [40 120 153] [22 80 140] • F2 [10 36 100] [60 70 130]


• F1 [50 95 110] [40 120 153] [22 80 140] • F2 [10 36 100] [60 70 130]

F3 [10 36 ... 110] [ 40 ... 153] [22 80 140]

• F1 [vazio] • F2 [vazio]

F3 [10 36 ... 110] [ 40 ... 153] [22 80 140]


• F1 [10 ... 110] [22 80 140] • F2 [40 ... 153]

F3 [vazio]

• F1 [10 ... 153] • F2 [22 ... 140]

F3 [10 ... 153]


• Características– Ordena arquivos de qualquer tamanho– Leitura seqüêncial mais rápida

• Podem ser utilizadas fitas...

– Ordenação interna com método rápido


• MergePara analisar o processo de ordenação externa –

e mais especificamente o merge – vamos considerar um disco rígido de alguns anos atrás (1997) da marca Seagate:Capacidade : 9 GBSeek time de trilha a trilha: 0.78 msSeek time médio: 8 msRotational delay (médio): 3 msTransfer rate: 14.506 bytes / ms


• Suposições:– Arquivos são sempre armazenados em áreas

contíguas no disco. Assim, somente um seek é preciso para uma leitura seqüêncial;

– Se a quantidade de dados a ser lida for maior que o espaço de uma trilha, assume-se 1 rotational delay.


• Durante a fase de ordenação é preciso ler os dados e criar as rodadas. Escrevendo-as no disco.

• Durante a fase de merge é preciso ler os dados de cada rodada e escrever o resultado de cada rodada no disco.


• Passo 1: Lendo registros– Os dados são lidos de 10 em 10 MB (80

vezes). O tempo para ler cada rodada inclui o tempo de acesso a cada bloco (seek time + rotational delay) + tempo de transferência. Assim, para nosso disco exemplo, temos:

• 8 + 3 = 11 ms

– Como vamos fazer 80 acessos, o tempo total será de 1 s

– O tempo de transferência será de 60 s


• Passo 2: Escrita das rodadas– Processo reverso do anterior – Outros 61 s


• Passo 3: Lendo rodadas p/ o merge– Temos que ler 1/80 de cada rodada para

realizar o merge. Assim, temos que ler cada rodada 80 vezes. E temos 80 delas para serem lidas...

– 80 x 80 = 6.400 seeks– Assim 6.400 x 11 ms = 70 s– Tempo de transferência dos dados = 60 s– Total 130 s


• Passo 4: Escrita no disco– Depende do tamanho do buffer de saída.

Para simplificar, vamos assumir um buffer de 200.000 bytes:

• 800.000.000 / 200.000 = 4.000 seeks

– 4.000 x 11 ms = 44 s– Tempo de transferência = 60 s– Total geral = 61 + 61 + 130 + 104 = 356 s

(ou 5 minutos e 56 segundos)


• E o que aconteceria se aumentássemos a magnitude do problema ?

• Analisando o problema verificamos que a leitura e a escrita são majoritariamente seqüêncial e, portanto, muito difícil de ter o desempenho melhorado.

• A fase de merge, entretanto, pode ser melhorada...


• Se aumentarmos o tamanho do arquivo em um fator de 10, sem aumentarmos o tamanho da área de trabalho, precisaremos criar mais rodadas... Se antes tínhamos 80, agora teremos 800... Isso significa que vamos ter um merge de 800 arquivos que devem ser acessados 800 vezes 800 x 800 = 640.000 seeks.


Fase Seeks Transfer

(mb)

Seek+ Rot. Transfer

(seg)

Total

(seg)

leitura 640.000 8000 7040 600 7640

escrita 40.000 8000 440 600 1040

total 680.000 16000 7480 1200 8680


• 8.680 s 2h e 24 m

(aprox. 25 vezes o tempo de um arquivo de 800 MB)


• Analisando...– A grande diferença entre os problemas foi

relativa ao seek time e o rotational delay. No primeiro caso tínhamos 6.400 seeks contra 640.000 no segundo (100 x 102 x);

– Tínhamos 4.000 seeks de escrita e temos 40.000 agora (10 x);


• Concluindo...– A solução atual é O(n2) do ponto de vista de

seeks...


• Como melhorar?– Melhoria de hardware;– Melhoria de software.


• Melhorando o algoritmo:• Ao invés de combinarmos as 800 rodadas de

uma só vez, vamos criar um novo passo: vamos fazer 25 conjuntos de 32 rodadas cada (25 x 32 = 800)

• Cada um dos buffers iniciais terá 1/32 da rodada o que perfaz 32 x 32 = 1024 seeks.

• Com 25 conjuntos tem-se 25 x 1024 = 25.600 seeks.

• Cada rodada resultante será de 320 MB (3.200.000 regs x 100.000 regs anteriormente)


Na segunda fase, teremos 25 rodadas finais. Cada buffer deverá conter 1/25 do espaço alocado (ou 1/800 de uma rodada). Assim, teremos 800 seeks por rodada:

25 x 800 seeks = 20.000 seeks

Total das duas fases: 25.600 + 20.000 = 45.600


É óbvio que teremos também que contabilizar os tempos extras de escrita e transmissão. Temos que transmitir os dados 3 vezes (no lugar de 2). Assim, o tempo de transmissão aumenta em 1.200 s.

Além disso, escrevemos os registros 2 vezes (no lugar de 1), o que implica em mais 40.000 seeks (de escrita). O total geral será de 3.782 s (ou 1 h e 3 m – contra as 2h e 25 m)

Documents

Organização e Recuperação da Informação Memória Secundária