Pesquisa em Memória Secundária

Pesquisa em Memria Secundria

ltima alterao: 31 de Agosto de 2010

Transparncias elaboradas por Wagner Meira Jr, Flvia Peligrinelli Ribeiro, Israel Guerra, Nvio Ziviani e Charles OrnelasAlmeida

Projeto de Algoritmos Cap.1 Introduo 1

Contedo do Captulo

6.1 Modelo de Computao para Memria Secundria

6.1.1 Memria Virtual

6.1.2 Implementao de um Sistema de Paginao

6.2 Acesso Sequencial Indexado

6.2.1 Discos pticos de Apenas-Leitura

6.3 rvores de Pesquisa

6.3.1 rvores B

6.3.2 rvores B

6.3.3 Acesso Concorrente em rvores B

6.3.4 Consideraes Prticas

Projeto de Algoritmos Cap.1 Introduo 2

Introduo

Pesquisa em memria secundria: arquivos contm mais registros do quea memria interna pode armazenar.

Custo para acessar um registro algumas ordens de grandeza maior do queo custo de processamento na memria primria.

Medida de complexidade: custo de trasferir dados entre a memria principale secundria (minimizar o nmero de transferncias).

Memrias secundrias: apenas um registro pode ser acessado em um dadomomento (acesso seqencial).

Memrias primrias: acesso a qualquer registro de um arquivo a um custouniforme (acesso direto).

O aspecto sistema de computao importante.

As caractersticas da arquitetura e do sistema operacional da mquinatornam os mtodos de pesquisa dependentes de parmetros que afetamseus desempenhos.

Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.1 3

Modelo de Computao para Memria Secundria -Memria Virtual

Normalmente implementado como uma funo do sistemaoperacional.

Modelo de armazenamento em dois nveis, devido necessidade degrandes quantidades de memria e o alto custo da memria principal.

Uso de uma pequena quantidade de memria principal e uma grandequantidade de memria secundria.

Programador pode enderear grandes quantidades de dados,deixando para o sistema a responsabilidade de trasferir o dado damemria secundria para a principal.

Boa estratgia para algoritmos com pequena localidade de referncia.

Organizao do fluxo entre a memria principal e secundria extremamente importante.

Projeto de Algoritmos Cap.6 Pesquisa em Memria Secundria Seo 6.1.1 4

Memria Virtual

Organizao de fluxo transformar o endereo usado peloprogramador na localizao fsica de memria correspondente.

Espao de Endereamento endereos usados pelo programador.

Espao de Memria localizaes de memria no computador.

O espao de endereamento N e o espao de memria M podem servistos como um mapeamento de endereos do tipo: f : N M .

O mapeamento permite ao programador usar um espao deendereamento que pode ser maior que o espao de memriaprimria disponvel.


Memria Virtual: Sistema de Paginao

O espao de endereamento dividido em pginas de tamanho igual,em geral, mltiplos de 512 Kbytes.

A memria principal dividida em molduras de pginas de tamanhoigual.

As molduras de pginas contm algumas pginas ativas enquanto orestante das pginas esto residentes em memria secundria(pginas inativas).

O mecanismo possui duas funes:

1. Mapeamento de endereos determinar qual pgina umprograma est endereando, encontrar a moldura, se existir, quecontenha a pgina.

2. Transferncia de pginas transferir pginas da memriasecundria para a memria primria e transfer-las de volta para amemria secundria quando no esto mais sendo utilizadas.


Memria Virtual: Sistema de Paginao

Endereamento da pgina uma parte dos bits interpretada comoum nmero de pgina e a outra parte como o nmero do byte dentroda pgina (offset).

Mapeamento de endereos realizado atravs de uma Tabela dePginas.

a p-sima entrada contm a localizao p da Moldura de Pginacontendo a pgina nmero p desde que esteja na memriaprincipal.

O mapeamento de endereos : f(e) = f(p, b) = p + b, onde e oendereo do programa, p o nmero da pgina e b o nmero do byte.


Memria Virtual: Mapeamento de Endereos

p p+ b

Tabela_de_Pginas Pgina p

N dapgina

N dobyte

Endereode

programap b

p = nil pgina nopresente namemria

?

--

?


Memria Virtual: Reposio de Pginas

Se no houver uma moldura de pgina vazia uma pgina deverser removida da memria principal.

Ideal remover a pgina que no ser referenciada pelo perodo detempo mais longo no futuro.

tentamos inferir o futuro a partir do comportamento passado.


Memria Virtual: Polticas de Reposio de Pginas

Menos Recentemente Utilizada (LRU):

um dos algoritmos mais utilizados,

remove a pgina menos recentemente utilizada,

parte do princpio que o comportamento futuro deve seguir opassado recente.

Menos Freqentemente Utilizada (LFU):

remove a pgina menos feqentemente utilizada,

inconveniente: uma pgina recentemente trazida da memriasecundria tem um baixo nmero de acessos e pode ser removida.

Ordem de Chegada (FIFO):

remove a pgina que est residente h mais tempo,

algoritmo mais simples e barato de manter,

desvantagem: ignora o fato de que a pgina mais antiga pode ser amais referenciada.


Memria Virtual: Poltica LRU

Fim -

Incio

Pgina p

?

6

?6

.

.

.

.

Toda vez que uma p-gina utilizada ela removida para o fim dafila.

A pgina que est noincio da fila a pginaLRU.

Quando uma nova p-gina trazida da me-mria secundria eladeve ser colocada namoldura que contm apgina LRU.


Memria Virtual: Estrutura de Dados

const TAMANHODAPAGINA = 512;

ITENSPORPAGINA = 64; { TamanhodaPagina/TamanhodoItem }

type Registro = record

Chave: TipoChave;

{ outros componentes }

end;

TipoEndereco = record

p: integer ;

b: 1 . . ITENSPORPAGINA;

end;

TipoItem = record

Reg: TipoRegistro ;

Esq, Dir : TipoEndereco;

end;

TipoPagina = array [ 1 . . ITENSPORPAGINA ] of TipoItem;


Memria Virtual

Em casos em que precisamos manipular mais de um arquivo aomesmo tempo:

A tabela de pginas para cada arquivo pode ser declaradaseparadamente.

A fila de molduras nica cada moldura deve ter indicado oarquivo a que se refere aquela pgina.

type TipoPagina = record

case byte of

0 : (Pa : TipoPaginaA) ;

1 : (Pb : TipoPaginaB) ;

2 : (Pc : TipoPaginaC) ;

end;


Memria Virtual

Procedimentos para comunicao com o sistema de paginao:

ObtemRegistro torna disponvel um registro.

EscreveRegistro permite criar ou alterar o contedo de umregistro.

DescarregaPaginas varre a fila de molduras para atualizar namemria secundria todas as pginas que tenham sidomodificadas.


Memria Virtual - Transformao do Endereo Virtual paraReal

P2Determinaendereo

real

P4Recupera pgina

da memriasecundria

A1Tabela

depginas

A3Memria

secundria

ProgramaUsurio

A2Filade

molduras

P5Grava pginana memriasecundria

P1Consultatabela depginas

P3Determinamoldura

para pgina

?

6

6?

6

6

--

?

-

p

p

pp

p Pgina

p

p

p

Pgina

pp

p

pp

Pgina

p

Quadrados resulta-dos de processos ou ar-quivos.

Retngulos proces-sos transformadores deinformao.


Acesso Seqencial Indexado

Utiliza o princpio da pesquisa seqencial cada registro lidoseqencialmente at encontrar uma chave maior ou igual a chave depesquisa.

Providncias necessrias para aumentar a eficincia:

o arquivo deve ser mantido ordenado pelo campo chave do registro,

um arquivo de ndices contendo pares de valores < x, p > deve sercriado, onde x representa uma chave e p representa o endereo dapgina na qual o primeiro registro contm a chave x.

Estrutura de um arquivo seqencial indexado para um conjunto de15 registros:

3 14 25 411 2 3 4

3 5 7 111 14 17 20 212 25 29 32 363 41 44 484


Acesso Seqencial Indexado: Disco Magntico

Dividido em crculos concntricos (trilhas).

Cilindro todas as trilhas verticalmente alinhadas e que possuem omesmo dimetro.

Latncia rotacional tempo necessrio para que o incio do blococontendo o registro a ser lido passe pela cabea de leitura/gravao.

Tempo de busca (seek time) tempo necessrio para que omecanismo de acesso desloque de uma trilha para outra (maior partedo custo para acessar dados).

Acesso seqencial indexado = acesso indexado + organizaoseqencial,

Aproveitando caractersticas do disco magntico e procurandominimizar o nmero de deslocamentos do mecanismo de acesso esquema de ndices de cilindros e de pginas.


Acesso Seqencial Indexado: Discos ticos deApenas-Leitura (CD-ROM)

Grande capacidade de armazenamento (600 MB) e baixo custo.

Informao armazenada esttica.

A eficincia na recuperao dos dados afetada pela localizao dos dadosno disco e pela seqncia com que so acessados.

Velocidade linear constante trilhas possuem capacidade varivel e tempode latncia rotacional varia de trilha para trilha.

A trilha tem forma de uma espiral contnua.

Tempo de busca: acesso a trilhas mais distantes demanda mais tempo queno disco magntico. H necessidade de deslocamento do mecanismo deacesso e mudanas na rotao do disco.

Varredura esttica: acessa conjunto de trilhas vizinhas sem deslocarmecanismo de leitura.

Estrutura seqencial implementada mantendo-se um ndice de cilindros namemria principal.


rvores B

rvores n-rias: mais de um registro por nodo.

Em uma rvore B de ordem m:

pgina raiz: 1 e 2m registros.

demais pginas: no mnimo m registros e m+ 1 descendentes e nomximo 2m registros e 2m+ 1 descendentes.

pginas folhas: aparecem todas no mesmo nvel.

Registros em ordem crescente da esquerda para a direita.

Extenso natural da rvore binria de pesquisa.

rvore B de ordem m = 2 com trs nveis:

hhhhhh

30

10 20

````

40 50 ````

3 4 8 9 11 13 17 25 28 33 36 43 45 48 52 55


rvores B - TAD Dicionrio

Estrutura de Dados:

type TipoRegistro = record

Chave: TipoChave;

{outros componentes}

end;

TipoApontador = ^TipoPagina;

TipoPagina = record

n: 0 . .mm;

r : array [ 1 . .mm ] of TipoRegistro ;

p: array [ 0 . .mm ] of TipoApontador

end;

TipoDicionario = TipoApontador;


rvores B - TAD Dicionrio

Operaes:

Inicializa

procedure In ic ial iza (var Dicionario : TipoDicionario ) ;

begin

Dicionario := n i l ;

end; { Inic ial iza }

Pesquisa

Insere

Remove


rvores B - Pesquisa

procedure Pesquisa (var x : TipoRegistro ; Ap: TipoApontador) ;

var i : Integer ;

begin

i f Ap = ni l

then writeln ( Registro nao esta presente na arvore )

else with Ap^ do

begin

i := 1;

while ( i < n) and (x.Chave > r [ i ] .Chave) do i := i + 1;

i f x.Chave = r [ i ] .Chave

then x := r [ i ]

else i f x.Chave < r [ i ] .Chave

then Pesquisa (x , p[ i1])

else Pesquisa (x , p[ i ] )

end;

end; { Pesquisa }


rvores B - Insero

1. Localizar a pgina apropriada aonde o regisro deve ser inserido.

2. Se o registro a ser inserido encontra uma pgina com menos de 2mregistros, o processo de insero fica limitado pgina.

3. Se o registro a ser inserido encontra uma pgina cheia, criada umanova pgina, no caso da pgina pai estar cheia o processo de divisose propaga.

Exemplo: Inserindo o registro com chave 14.

1 10

`````

2 33 4 8 9 16 20 25 29 (a)

1 10 20

`````

2 3 43 4 8 9 14 16 25 29 (b)


rvores B - Insero

Exemplo de insero das chaves: 20, 10, 40, 50, 30, 55, 3, 11, 4, 28, 36,33, 52, 17, 25, 13, 45, 9, 43, 8 e 48

(a) 20

(b) 30

PPP

10 20 40 50

(c) 10 20 30 40

((((((( PPP

hhhhhhh

3 4 11 13 17 25 28 33 36 50 52 55

hhhhhh

(d) 30

10 20

````

40 50 ````

3 4 8 9 11 13 17 25 28 33 36 43 45 48 52 55


rvores B - Primeiro refinamento do algoritmo Insere

procedure Insere (Reg: Registro ; var Ap: Apontador) ;

procedure Ins (Reg: Registro ; Ap: Apontador ; var Cresceu: Boolean;var RegRetorno: Registro ; var ApRetorno: Apontador) ;

var i : integer ;begin

i f Ap = ni lthen begin

Cresceu := true ;Atribui Reg a RegRetorno;Atribui n i l a ApRetorno;end

else with Ap^ dobegini := 1;while ( i < n) and (x.Chave > r [ i ] .Chave) do i := i + 1;i f x.Chave = r [ i ] .Chavethen writeln ( Erro : Registro ja esta presente na arvore )else i f x.Chave < r [ i ] .Chave

then Ins (x , p[ i 1], Cresceu, RegRetorno, ApRetorno)else Ins (x , p[ i ] , Cresceu, RegRetorno, ApRetorno) ;


rvores B - Primeiro refinamento do algoritmo Insere

i f Cresceu then i f (Numero de registros em Ap) < mmthen Insere na pagina Ap e Cresceu := falseelse begin { Overflow : pagina tem que ser dividida }

Cria nova pagina ApTemp;Transfere metade dos registros de Ap para ApTemp;Atribui registro do meio a RegRetorno;Atribui ApTemp a ApRetorno;end;

end;end;

begin { Insere}Ins (Reg, Ap, Cresceu, RegRetorno, ApRetorno) ;i f Cresceu then Cria nova pagina raiz para RegRetorno e ApRetorno;end;


rvores B - Procedimento InsereNaPgina

procedure InsereNaPagina (Ap: TipoApontador ; Reg: TipoRegistro ; ApDir : TipoApontador) ;var NaoAchouPosicao: Boolean;

k : Integer ;beginwith Ap^ do

begink := n;NaoAchouPosicao := k > 0;while NaoAchouPosicao do

i f Reg.Chave < r [k ] .Chavethen begin

r [k+1] := r [k ] ; p[k+1] := p[k ] ;k := k 1;i f k < 1 then NaoAchouPosicao := false ;end

else NaoAchouPosicao := false ;r [k+1] := Reg; p[k+1] := ApDir;n := n + 1;end;

end; { InsereNaPagina }


rvores B - Refinamento final do algoritmo Insereprocedure Insere (Reg: TipoRegistro ; var Ap: TipoApontador) ;var Cresceu: Boolean; RegRetorno: TipoRegistro ;

ApRetorno, ApTemp: TipoApontador;

procedure Ins(Reg:TipoRegistro ; Ap: TipoApontador ; var Cresceu:Boolean;var RegRetorno:TipoRegistro ; var ApRetorno:TipoApontador) ;

var i , j : Integer ; ApTemp: TipoApontador;begin

i f Ap = ni lthen begin Cresceu := true ; RegRetorno := Reg; ApRetorno := n i l ; endelse with Ap^ do

begini := 1;while ( i < n) and (Reg.Chave > r [ i ] .Chave) do i := i + 1;i f Reg.Chave = r [ i ] .Chavethen begin writeln ( Erro : Registro ja esta presente ) ; Cresceu:=false ; endelse begin i f Reg.Chave < r [ i ] .Chave then i := i 1;

Ins (Reg, p[ i ] , Cresceu, RegRetorno, ApRetorno) ;i f Cresceuthen i f n < mm

then begin { Pagina tem espaco }InsereNaPagina (Ap, RegRetorno, ApRetorno) ; Cresceu := false ;end

{ Continua na prxima transparncia }


rvores B - Refinamento final do algoritmo Insereelse begin { Overflow : Pagina tem que ser dividida }

new (ApTemp) ;ApTemp^.n := 0; ApTemp^.p[0 ] := n i l ;i f i < M + 1then begin InsereNaPagina (ApTemp, r [mm] , p[mm ] ) ; n := n 1;

InsereNaPagina (Ap, RegRetorno, ApRetorno)end

else InsereNaPagina (ApTemp, RegRetorno, ApRetorno) ;for j := M + 2 to mm do

InsereNaPagina (ApTemp, r [ j ] , p[ j ] ) ;n := M; ApTemp^.p[0 ] := p[M+1];RegRetorno := r [M+1]; ApRetorno := ApTemp;end;

end;end;

end; { Ins }begin Ins (Reg, Ap, Cresceu, RegRetorno, ApRetorno) ;

i f Cresceu then begin { Arvore cresce na altura pela raiz }new (ApTemp) ; ApTemp^.n := 1;ApTemp^. r [1 ] := RegRetorno;ApTemp^.p[1 ] := ApRetorno;ApTemp^.p[0 ] := Ap; Ap := ApTempend

end; { Insere }


rvores B - Remoo

Pgina com o registro a ser retirado folha:

1. retira-se o registro,

2. se a pgina no possui pelo menos de m registros, a propriedadeda rvore B violada. Pega-se um registro emprestado da pginavizinha. Se no existir registros suficientes na pgina vizinha, asduas pginas devem ser fundidas em uma s.

Pagina com o registro no folha:

1. o registro a ser retirado deve ser primeiramente substitudo por umregistro contendo uma chave adjacente.


rvores B - Remoo

Exemplo: Retirando a chave 3.

j4

6 8

HHH

j2

j1 [email protected]@ j5

j7 j9TT

1 2

j* ,,

j5

j4

j7

6 8

ll

j9TT

1 2

j4,,

j5AA

j6

j7

j8ll

j9AA

(a) Pgina vizinha possui mais do que m registros

j1

j2,,

j3AA

j4

j5

j6ll

j7AA

1 2

j* ,,

j4

j5

j6ll

j7AA

j

4 6

1 2

j5 j7TT

(b) Pgina vizinha possui exatamente m registros


rvores B - Remoo

Remoo das chaves 45 30 28; 50 8 10 4 20 40 55 17 33 11 36; 3 9 52.

(d) 13 25 43 48

(c) 13

PPP

3 9 25 43 48 52

(b) 10 25 40 50

((((((( PPP

hhhhhhh

3 4 8 9 11 13 17 20 33 36 43 48 52 55

hhhhhh

(a) 30

10 20

````

40 50 ````

3 4 8 9 11 13 17 25 28 33 36 43 45 48 52 55


rvores B - Procedimento Retiraprocedure Ret(Ch:TipoChave;var Ap:TipoApontador;var Diminuiu:Boolean) ;

var Ind , j : Integer ;

procedure Reconstitui (ApPag: TipoApontador ; ApPai : TipoApontador;PosPai : Integer ; var Diminuiu : Boolean) ;

var Aux: TipoApontador ; DispAux, j : Integer ;begin

i f PosPai < ApPai^.nthen begin { Aux = Pagina a direita de ApPag }

Aux := ApPai^.p[PosPai+1];DispAux := (Aux^.n M + 1) div 2;ApPag^. r [ApPag^.n+1] := ApPai^. r [PosPai+1];ApPag^.p[ApPag^.n+1] := Aux^.p[0 ] ;ApPag^.n := ApPag^.n + 1;i f DispAux > 0then begin { Existe folga : transfere de Aux para ApPag }

for j := 1 to DispAux 1 doInsereNaPagina (ApPag, Aux^. r [ j ] , Aux^.p[ j ] ) ;ApPai^. r [PosPai+1] := Aux^. r [DispAux] ;Aux^.n := Aux^.n DispAux;for j := 1 to Aux^.n do Aux^. r [ j ]:=Aux^. r [ j+DispAux] ;for j := 0 to Aux^.n do Aux^.p[ j ]:=Aux^.p[ j+DispAux] ;Diminuiu := falseend



rvores B - Procedimento Retiraelse begin { Fusao: intercala Aux em ApPag e libera Aux }

for j := 1 to M doInsereNaPagina (ApPag, Aux^. r [ j ] , Aux^.p[ j ] ) ;

dispose (Aux) ;for j := PosPai + 1 to ApPai^.n 1 do with ApPai^ do

beginr [ j ] := r [ j +1]; p[ j ] := p[ j +1]end;

ApPai^.n := ApPai^.n 1;i f ApPai^.n >= Mthen Diminuiu := false ;end

endelse begin { Aux = Pagina a esquerda de ApPag }

Aux := ApPai^.p[PosPai1];DispAux := (Aux^.n M + 1) div 2;for j := ApPag^.n downto 1 do

ApPag^. r [ j +1] := ApPag^. r [ j ] ;ApPag^. r [1 ] := ApPai^. r [PosPai ] ;for j := ApPag^.n downto 0 do

ApPag^.p[ j +1] := ApPag^.p[ j ] ;ApPag^.n := ApPag^.n + 1;



rvores B - Procedimento Retira

i f DispAux > 0then begin { Existe folga : transfere de Aux para ApPag }

for j := 1 to DispAux 1 do with Aux^ doInsereNaPagina (ApPag, r [Aux^.n+1j ] , p[n+1j ] ) ;

ApPag^.p[0 ] := Aux^.p[Aux^.n+1DispAux] ;ApPai^. r [PosPai] := Aux^. r [Aux^.n+1DispAux] ;Aux^.n := Aux^.n DispAux;Diminuiu := falseend

else begin { Fusao: intercala ApPag em Aux e libera ApPag }for j := 1 to M do

InsereNaPagina (Aux, ApPag^. r [ j ] , ApPag^.p[ j ] ) ;dispose (ApPag) ;ApPai^.n := ApPai^.n 1;i f ApPai^.n >= M then Diminuiu := false ;end;

end;end;

end; { Reconstitui }{ Continua na prxima transparncia }



procedure Antecessor (Ap: TipoApontador ; Ind : Integer ;ApPai : TipoApontador;var Diminuiu : Boolean) ;

beginwith ApPai^ do

begini f p[n] n i lthen begin

Antecessor (Ap, Ind , p[n] , Diminuiu ) ;i f Diminuiu then Reconstitui (p[n] , ApPai, n, Diminuiu ) ;end

else beginAp^. r [ Ind ] := r [n ] ; n := n 1;Diminuiu := n < M;end;

endend; { Antecessor }



rvores B - Procedimento Retirabegin { Ret }

i f Ap = ni lthen begin writeln ( Erro : registro nao esta na arvore ) ; Diminuiu := false ; endelse with Ap^ do

beginInd := 1;while ( Ind < n) and (Ch > r [ Ind ] .Chave) do Ind := Ind + 1;i f Ch = r [ Ind ] .Chavethen i f p[ Ind1] = n i l

then begin { Pagina folha }n := n 1; Diminuiu := n < M;for j := Ind to n do

beginr [ j ] := r [ j +1];p[ j ] := p[ j +1];end;

endelse begin { Pagina nao e folha : trocar com antecessor }

Antecessor (Ap, Ind , p[ Ind1], Diminuiu ) ;i f Diminuiu then Reconstitui (p[ Ind1], Ap, Ind1, Diminuiu ) ;end




else begini f Ch > r [ Ind ] .Chave then Ind := Ind + 1;Ret (Ch, p[ Ind1], Diminuiu ) ;i f Diminuiuthen Reconstitui (p[ Ind1], Ap, Ind1, Diminuiu ) ;end

endend; { Ret }

begin { Retira }Ret (Ch, Ap, Diminuiu ) ;i f Diminuiu and (Ap^.n = 0)then begin { Arvore diminui na altura }

Aux := Ap; Ap := Aux^.p[0 ] ;dispose (Aux) ;end

end; { Retira }


rvores B* - TAD Dicionrio

Estrutura de Dados:

typeTipoRegistro = record

Chave: TipoChave;{ outros componentes }

end;TipoApontador = ^TipoPagina;TipoIntExt = ( Interna , Externa) ;TipoPagina = record

case Pt : TipoIntExt ofInterna : ( ni : 0 . .mm;

r i : array [ 1 . .mm ] of TipoChave;pi : array [ 0 . .mm ] of TipoApontador) ;

Externa : (ne: 0 . .mm2;re : array [ 1 . .mm2 ] of TipoRegistro ) ;

end;TipoDicionario = TipoApontador;


rvores B* - Pesquisa

Semelhante pesquisa em rvore B,

A pesquisa sempre leva a uma pgina folha,

A pesquisa no pra se a chave procurada for encontrada em umapgina ndice. O apontador da direita seguido at que se encontreuma pgina folha.


rvores B* - Procedimento para pesquisar na rvore B

procedure Pesquisa (var x : TipoRegistro ; var Ap: TipoApontador) ;var i : integer ;begin

i f Ap^.Pt = Internathen with Ap^ do

begini := 1;while ( i < ni ) and (x.Chave > r i [ i ] ) do i := i + 1;i f x.Chave < r i [ i ]then Pesquisa(x , pi [ i1])else Pesquisa(x , pi [ i ] )end

else with Ap^ dobegini := 1;while ( i < ne) and (x.Chave > re [ i ] .Chave) do i := i + 1;i f x.Chave = re [ i ] .Chavethen x := re [ i ]else writeln ( Registro nao esta presente na arvore ) ;

end;end;


rvores B* - Insero e Remoo

Insero na rvore B*

Semelhante insero na rvore B,

Diferena: quando uma folha dividida em duas, o algoritmopromove uma cpia da chave que pertence ao registro do meiopara a pgina pai no nvel anterior, retendo o registro do meio napgina folha da direita.

Remoo na rvore B*

Relativamente mais simples que em uma rvore B,

Todos os registros so folhas,

Desde que a folha fique com pelo menos metade dos registros, aspginas dos ndices no precisam ser modificadas, mesmo se umacpia da chave que pertence ao registro a ser retirado esteja nondice.


Acesso Concorrente em rvore B*

Acesso simultneo a banco de dados por mais de um usurio.

Concorrncia aumenta a utilizao e melhora o tempo de resposta dosistema.

O uso de rvores B* nesses sistemas deve permitir o processamentosimultneo de vrias solicitaes diferentes.

Necessidade de criar mecanismos chamados protocolos para garantira integridade tanto dos dados quanto da estrutura.

Pgina segura: no h possibilidade de modificaes na estrutura darvore como conseqncia de insero ou remoo.

insero pgina segura se o nmero de chaves igual a 2m,

remoo pgina segura se o nmero de chaves maior que m.

Os algoritmos para acesso concorrente fazem uso dessa propriedadepara aumentar o nvel de concorrncia.


Acesso Concorrente em rvore B* - Protocolos deTravamentos

Quando uma pgina lida, a operao de recuperao a trava, assim,outros processos, no podem interferir com a pgina.

A pesquisa continua em direo ao nvel seguinte e a trava liberadapara que outros processos possam ler a pgina .

Processo leitor executa uma operao de recuperao

Processo modificador executa uma operao de insero ouretirada.

Dois tipos de travamento:

Travamento para leitura permite um ou mais leitores acessaremos dados, mas no permite insero ou retirada.

Travamento exclusivo nenhum outro processo pode operar napgina e permite qualquer tipo de operao na pgina.


rvore B - Consideraes Prticas

Simples, fcil manuteno, eficiente e verstil.

Permite acesso seqencial eficiente.

Custo para recuperar, inserir e retirar registros do arquivo logaritmico.

Espao utilizado , no mnimo 50% do espao reservado para oarquivo,

Emprego onde o acesso concorrente ao banco de dados necessrio, vivel e relativamente simples de ser implementado.

Insero e retirada de registros sempre deixam a rvore balanceada.

Uma rvore B de ordem m com N registros contm no mximo cercade logm+1N pginas.


rvore B - Consideraes Prticas

Limites para a altura mxima e mnima de uma rvore B de ordem mcom N registros: log2m+1(N + 1) altura 1 + logm+1

(

N+12

)

Custo para processar uma operao de recuperao de um registrocresce com o logaritmo base m do tamanho do arquivo.

Altura esperada: no conhecida analiticamente.

H uma conjectura proposta a partir do clculo analtico do nmeroesperado de pginas para os quatro primeiros nveis (das folha emdireo raiz) de uma rvore 2-3 (rvore B de ordem m = 1).

Conjetura: a altura esperada de uma rvore 2-3 randmica com Nchaves h(N) log7/3(N + 1).


rvores B Randmicas - Medidas de Complexidade

A utilizao de memria cerca de ln 2.

Pginas ocupam 69% da rea reservada aps N inseresrandmicas em uma rvore B inicialmente vazia.

No momento da insero, a operao mais cara a partio da pginaquando ela passa a ter mais do que 2m chaves. Envolve:

Criao de nova pgina, rearranjo das chaves e insero da chavedo meio na pgina pai localizada no nvel acima.

Pr{j parties}: probabilidade de que j parties ocorram durantea N -sima insero randmica.

rvore 2-3: Pr{0 parties} = 47, Pr{1 ou mais parties} = 3

7

rvore B de ordem m: Pr{0 parties} = 1 1(2 ln 2)m

+O(m2),

Pr{1 ou + parties} = 1(2 ln 2)m

+O(m2).

rvore B de ordem m = 70: 99% das vezes nada acontece emtermos de parties durante uma insero.


rvores B Randmicas - Acesso Concorrente

Foi proposta uma tcnica de aplicar um travamento na pgina seguramais profunda (Psmp) no caminho de insero.

Uma pgina segura se ela contm menos do que 2m chaves.

Uma pgina segura a mais profunda se no existir outra pginasegura abaixo dela.

J que o travamento da pgina impede o acesso de outros processos, interessante saber qual a probabilidade de que a pgina seguramais profunda esteja no primeiro nvel.

rvore 2-3: Pr{Psmp esteja no 1 nvel} = 47,

Pr{Psmp esteja acima do 1 nvel} = 37

rvore B de ordem m:Pr{Psmp esteja no 1 nvel} = 1 1

(2 ln 2)m+O(m2),

Pr{Psmp esteja acima do 1 nvel} = 37= 1

(2 ln 2)m+O(m2).


rvores B Randmicas - Acesso Concorrente

Novamente, em rvores B de ordem m = 70: 99% das vezes a Psmpest em uma folha. (Permite alto grau de concorrncia para processosmodificadores.)

Solues muito complicadas para permitir concorrncia de operaesem rvores B no trazem grandes benefcios.

Na maioria das vezes, o travamento ocorrer em pginas folha.(Permite alto grau de concorrncia mesmo para os protocolos maissimples.)


rvore B - Tcnica de Transbordamento (ou Overflow)

Assuma que um registro tenha de ser inserido em uma pgina cheia,com 2m registros.

Em vez de particion-la, olhamos primeiro para a pgina irm direita.

Se a pgina irm possui menos do que 2m registros, um simplesrearranjo de chaves torna a partio desnecessria.

Se a pgina direita tambm estiver cheia ou no existir, olhamospara a pgina irm esquerda.

Se ambas estiverem cheias, ento a partio ter de ser realizada.

Efeito da modificao: produzir uma rvore com melhor utilizao dememria e uma altura esperada menor.

Produz uma utilizao de memria de cerca de 83% para uma rvoreB randmica.


rvore B - Influncia do Sistema de Paginao

O nmero de nveis de uma rvore B muito pequeno (trs ou quatro)se comparado com o nmero de molduras de pginas.

Assim, o sistema de paginao garante que a pgina raiz estejasempre na memria principal (se for adotada a poltica LRU).

O esquema LRU faz com que as pginas a serem particionadas emuma insero estejam disponveis na memria principal.

A escolha do tamanho adequado da ordem m da rvore B geralmente feita levando em conta as caractersticas de cadacomputador.

O tamanho ideal da pgina da rvore corresponde ao tamanho dapgina do sistema, e a transferncia de dados entre as memriassecundria e principal realizada pelo sistema operacional.

Estes tamanhos variam entre 512 bytes e 4.096 bytes, em mltiplos de512 bytes.

Pesquisa em Memória Secundária - dcc.ufmg.br · Pesquisa em Memória ... 6.1 Modelo de Computação para Memória Secundária 6.1.1 Memória Virtual 6.1.2 Implementação de um

Text of Pesquisa em Memória Secundária - dcc.ufmg.br · Pesquisa em Memória ... 6.1 Modelo de...

Curso de NS Rainer R. P. Couto ([email protected])[email protected]

Mapas Conceituais Angelo de Moura Guimarães [email protected] Angelo de Moura Guimarães [email protected]

Apresentação do PowerPoint - walderson.comwalderson.com/site/wp-content/uploads/2014/05/Aula11-Gerencia-da... · memória principal para a memória secundária (Swap out), geralmente

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

Algoritmo e Estrutura de Dados I Aula 9 – Variáveis Compostas Homogêneas Márcia Marra [email protected]

Componentes Básicos e Funcionamento; Memória; E/S. · Memória Cache Interna Memória Secundária HD, FD, ZIP, CD, DVD r it Memória Interna Fita Magnética, MO, WORM Memória de

Arquitetura de ComputadoresArquitetura de Computadores Memória Agenda: 1.Introdução (definição). 2.Função 3.Tipos 1.Primária (registradores, cache, RAM e ROM) 2.Secundária

Pesquisa em Memória Secundária - professor.ufabc.edu.brprofessor.ufabc.edu.br/~leticia.bueno/classes/aed2/materiais/... · • envolve mais registros do que a memória interna pode

Subsistemas de memória Livro Introdução à Organização de Computadores Capítulos: 4 – Memória Principal 5 – Memória Cache 9 – Memoria Secundária

Curso de NS Ferramentas auxiliares Rainer R. P. Couto ([email protected])[email protected]

Programação Usando Threads em C - dcc.ufmg.br · Threads em C. O que são Threads?

Microprocessadores Memórias - dfisica.ubi.ptpinheiro/MP03.pdf · Memória Secundária Memória de massa, normalmente constituída pelo disco, e também por CD’s, "discketes"e outros

Oficina sobre a Plataforma Janeiro/2006 Prof. Angelo de Moura Guimarães [email protected] Prof. Antônio Mendes Ribeiro [email protected]

Mapas Conceituais Angelo de Moura Guimarães [email protected] Angelo de Moura Guimarães [email protected] Comunidade Prática de EAD da UFMG

Sistemas Operativos 2011 / 2012 - Instituto Superior …groups.ist.utl.pt/~leic-so.daemon/2011-2012/teoricas...Concatenar base e deslocamento Trazer página de memória secundária

Contatos · Informática para Concursos ... sistema operacional. c) memória secundária, sistema operacional, ... A unidade central de processamento

ACESSO À MEMÓRIA SECUNDÁRIA - ÁRVORES

ACESSO À MEMÓRIA SECUNDÁRIA - ÁRVORES ORI – Prof. Dr. Ednaldo Pizzolato

Sistemas Operacionais e Introdução à Programaçãomsobral/SOP/slides/aula1.pdf · Memória virtual: memória secundária (disco) usada como se fosse memória principal ... Uso

FUNDAMENTOS DE ARQUITETURAS DE COMPUTADORES …boeres/slides_FAC/FAC-aula3.pdf · Registradores, memória cache, memória principal, ROM, e hoje, até memória secundária Mais caras

Algoritmo e Estrutura de Dados I Aulas 15 – Linguagem C Alocação Dinâmica de Memória Márcia Marra [email protected]

Escrita de Artigos Científicos Mirella M. Moro [email protected]

DIEGO - dcc.ufmg.br

ed2 pesquisa-externa.ppt [Modo de Compatibilidade] · memória secundária um programa está endereçando, e encontrar a moldura de tal página na memória principal, caso exista

Introdução à Organização de Computadoresrossano.pro.br/network/cursos/arqcomp/apostilas/... · 2008-11-06 · Introdução à Organização de Computadores Memória Secundária

Algoritmo e Estrutura de Dados I Aulas 12 – Linguagem C Strings Márcia Marra [email protected]

Algoritmo e Estrutura de Dados I Aulas 13 – Variáveis Compostas Multidimensionais Márcia Marra [email protected]

Algoritmo e Estrutura de Dados I Aula 7 – Estrutura de repetição Márcia Marra [email protected]

Fundamentos da Arquitetura de Computadores Memória Secundária Prof. André Renato 1º Semestre / 2012

Documents

Pesquisa em Memória Secundária - dcc.ufmg.br · Pesquisa em Memória ... 6.1 Modelo de Computação para Memória Secundária 6.1.1 Memória Virtual 6.1.2 Implementação de um

Text of Pesquisa em Memória Secundária - dcc.ufmg.br · Pesquisa em Memória ... 6.1 Modelo de...