Organização e Recuperação da Informação
Memória Secundária
Dr. Ednaldo Pizzolato
ORI - DISCOS
• Memória Secundária • Memória Primária
– Não Volátil
– Lenta
– Barata
– 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 trilha
Os dados são trasferidos entre o disco e a memória
principal em blocos
Os 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 viceversa), 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?
ORI – DISCOS (blocos)
• 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.
ORI – DISCOS (blocos)
• 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.
ORI – DISCOS (organização)
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.
ORI – DISCOS (organização)
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 msec
rotational delay = 3 msec
leitura 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 msec
rotational delay = 3 msec
leitura de um bloco = 1/21.5 x 6) = 0.28 msec
total = 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, podese, 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 CDROM 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 CDROM .
ORI – CD-ROMS
• Para que isso fosse realizado, foi adotada para o CDROM 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
10000100000000
00000010
10010000100000
00000011
10001000100000
00000100
01000100000000
00000101
00000100010000
00000110
00010000100000
00000111
00100100000000
00001000
01001001000000
00001001
10000001000000
00001010
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
1x
2x
3x
4x
6x
8x
10x
12x
16x
20x
Taxa de transferência
150 kB/s
300 kB/s
450 kB/s
600 kB/s
900 kB/s
1,2 MB/s
1,5 MB/s
1,8 MB/s
2,4 MB/s
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 padrões digitais.
ORI - Digitalização
• A onda é representada por um gráfico de
amplitude contra o tempo.
ORI - Digitalização
• Como estamos digitalizando, precisamos
armazenar as amplitudes em períodos regulares
para, depois, reconstruírmos o gráfico referente
à onda.
ORI - Digitalização
ORI - Digitalização
ORI - Digitalização
• 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).
ORI - Digitalização
• 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.
ORI – External Sorting
• 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...)
ORI – External Sorting
• 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.
ORI – External Sorting
• 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).
ORI – External Sorting
arquivo desordenado
arquivo ordenado
ORI – External Sorting
• 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]
ORI – External Sorting
• F1  [50
• F2  [10
F3  [10
95 110]
[40 120 153]
[22 80 140]
36 100]
[60 70 130]
36 ... 110]
[ 40 ... 153]
[22 80 140]
• F1  [vazio]
• F2  [vazio]
F3  [10 36 ... 110]
[ 40 ... 153]
[22 80 140]
ORI – External Sorting
• F1  [10 ... 110]
• F2  [40 ... 153]
F3  [vazio]
• F1  [10 ... 153]
• F2  [22 ... 140]
F3  [10 ... 153]
[22 80 140]
ORI – External Sorting
• 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
ORI – External Sorting
• Merge
Para 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 GB
Seek time de trilha a trilha: 0.78 ms
Seek time médio:
8 ms
Rotational delay (médio):
3 ms
Transfer rate:
14.506 bytes / ms
ORI – External Sorting
• 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.
ORI – External Sorting
• Durante a fase de ordenação é preciso ler
os dados e criar as rodadas. Escrevendoas no disco.
• Durante a fase de merge é preciso ler os
dados de cada rodada e escrever o
resultado de cada rodada no disco.
ORI – External Sorting
• 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
ORI – External Sorting
• Passo 2: Escrita das rodadas
– Processo reverso do anterior
– Outros 61 s
ORI – External Sorting
• 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
ORI – External Sorting
• 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)
ORI – External Sorting
• 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...
ORI – External Sorting
• 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.
ORI – External Sorting
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
ORI – External Sorting
• 8.680 s  2h e 24 m
(aprox. 25 vezes o tempo de um arquivo
de 800 MB)
ORI – External Sorting
• 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);
ORI – External Sorting
• Concluindo...
– A solução atual é O(n2) do ponto de vista de
seeks...
ORI – External Sorting
• Como melhorar?
– Melhoria de hardware;
– Melhoria de software.
ORI – External Sorting
• 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)
ORI – External Sorting
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
ORI – External Sorting
É ó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)