03 - Gerenciamento de Buffer V-0'761

Prévia do material em texto

BANCO DE DADOS II 
Gerenciamento de Buffer 
 
Versão dos Slides: 0.761 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
 
 
 
DCC-UFLA, Lavras 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Introdução 
 Operações do Gerenciador de Buffer 
 String de Referência 
 Localidade de Referência 
 Algoritmo para Estratégia de Alocação 
 Algoritmos para Substituição de Páginas 
2 
3 
armazenamento externo 
serviços de arquivos 
controle de propagação 
estruturas de 
armazenamento 
caminhos de 
acessos lógicos 
estruturas de 
dados lógicas C5 
C4 
C3 
C2 
C1 
Camada 2: Controle de Propagação 
4 
Arquitetura de 5 Níveis 
(Härder e Reuter) 
armazenamento externo 
serviços de arquivos 
controle de propagação 
estruturas de 
armazenamento 
caminhos de 
acessos lógicos 
estruturas de 
dados lógicas 
interface do buffer do BD 
fix/unfix de páginas 
unidades de endereçamento: 
páginas, segmentos 
estruturas auxiliares: 
tabelas de páginas, tabelas de blocos 
unidades de endereçamento: 
blocos, arquivos 
C5 
C4 
C3 
C2 
C1 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Controle de Propagação: 
Visão Geral 
5 
TA1 TA2 TAn TA3 ... 
Gerenciador de Transações e Operadores Físicos 
Referências Lógicas de Páginas 
Gerenciador de Buffer 
Gerenciador de Armazenamento 
Referências Físicas de Páginas 
SGBD 
(Simplificado) 
SELECT Nome 
FROM Empregado 
WHERE ID = 1111 
FIX Pi 
UNFIX Pi 
READ Bi 
WRITE Pi 
Canais 
de Acesso 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Blocos vs. Páginas 
 Camada C1: BD logicamente dividido em 
blocos de mesmo tamanho 
• Bloco: objeto de dados administrado em C1 
cujo conteúdo está armazenado no disco 
 Camada C2: BD logicamente dividido em 
páginas de mesmo tamanho 
• Página: objeto de dados administrado em 
C2 cujo contéudo pode ou não estar em 
memória 
6 
Blocos vs. Páginas 
 Aqui, iremos assumir uma relação 1-1 
(mapeamento) entre blocos e páginas 
• Tamanho de blocos = Tamanho de páginas 
• Identificador de Blocos = Identificador de páginas 
 Para cada página 𝑃𝑖, teremos um bloco 𝐵𝑖 
correspondente 
• O subscrito 𝑖 é o identificador da página ou bloco 
 O conteúdo de uma página já existente é sempre 
obtido inicialmente do bloco correspondente no disco 
 Entretanto, o conteúdo de uma página em memória 
pode divergir do contéudo do bloco correspodente no 
disco caso a mesma tenha sido modifica em memória e 
ainda não tenha sido propagada no disco 
 
7 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Blocos vs. Páginas 
 Finalmente, notem que essa relação 1-1 entre 
blocos e páginas, apesar de amplamente 
usada na prática, não é uma restrição 
conceitual 
 Por exemplo, estratégias em que uma página 
pode ser armazenada em blocos diferentes ao 
longo do “tempo de vida” do BD já foram 
propostas 
 
8 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Propagação 
 Propagação: termo geral para denotar a transferência 
de dados entre o disco e a memória 
• Ação controlada por C2 usando serviços de C1 
 Página suja: página cujo contéudo foi modificado em 
memória mas ainda não foi escrito no bloco 
correspondente no disco 
 Atualizações: 
• Novas páginas criadas devido à inserção ou 
remanejamento de dados do BD resulta na criação de 
novos blocos 
• Similarmente, deleção de páginas resulta na deleção de 
blocos no disco 
9 
Propagação: Exemplos 
1) Bloco 𝐵1 é propagado para a página 𝑃1 
2) Página suja 𝑃2′ é propagada para o bloco 𝐵2 
3) Nova página 𝑃3 é propagada para o novo bloco 𝐵3 
4) Página deletada 𝑃4 causa a deleção do bloco 𝐵4 
 
10 
C1 
C2 
𝐵1 
𝐵1 
Disco 
𝐵2 
𝑃2′ 𝑃1 
𝐵2 𝐵3 
𝐵3 𝐵4 
𝑃4 𝑃3 
𝐵4 
1) 2) 3) 4) X 
X 
Intermediação 
da propagação 
em C1 
Buffer do SGBD 
 Um buffer de um SGBD é dividido em quadros de 
páginas (page frame) de mesmo tamanho em um espaço 
de endereçamento de memória linear 
 Tipicamente, um quadro de página armazena o conteúdo 
de uma única página 
 Notem que uma página pode ser armazenada em 
diferentes quadros de páginas cada vez que seu 
contéudo é lido de um bloco 
 Quando não for relevante para a discussão, não faremos 
distinção entre página (objeto) e quadro de página (local 
de armazenamento no buffer) 
• Por exemplo, podemos usar endereço de memória da página 
𝑃 no lugar endereço de memória do quadro de página que 
armazena a página 𝑃 
 
 
11 
Buffer do SGBD 
 Dados do BD requisitados por camadas superiores 
são sempre armazenados primeiramente no buffer 
• Cache de dados: Requisições subsequentes podem ser 
atendidas sem a necessidade de novo acesso ao disco 
• Exceção: Objetos volumosos como vídeos e fotos não 
são normalmente armazenados no buffer 
 SGBDs podem manter mais de um buffer para 
armazenar diferentes tipos de dados 
• Por exemplo, um buffer para tabelas regulares, outro 
para tabelas temporárias, e um terceiro para índices 
 Manuais frequentemente usam o termo buffer pool 
para se referir à memória usada para armazenar 
dados do BD 
• Aqui, usaremos apenas buffer 
 
12 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Gerenciador de Buffer 
 O buffer é controlado por um mecanismo de 
gerenciamento de buffer, ou, simplesmente, 
gerenciador de buffer 
 O principal objetivo do gerenciador de buffer é 
minimizar a quantidade de IO para um dado 
tamanho de buffer 
• Proporção de 1:1000 entre buffer e o BD é comum 
• Mesmo com esta proporção, um gerenciador de 
buffer bem ajustado pode evitar 95% (até mais) dos 
acessos ao disco 
 
13 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Referências de Página 
 Referências de páginas podem ser lógicas ou físicas 
 Referências lógicas: realizada por operações em C3 
invocando serviços em C2 
 Referências físicas: realizada por operações em C2 
invocando serviços em C1 
• Ocorre quando a página requisitada na referência lógica 
não se encontra em memória e seu conteúdo precisa ser 
buscado no bloco correspodente 
• Resulta em acesso ao disco a não ser que os serviços do 
sistema de arquivos do SO estejam sendo usados por C1 e 
os dados do bloco correspondente se encontrem no cache 
• O último caso resulta em uma situação de double 
buffering, onde dados estão duplicados no buffer do SGBD 
e no cache do sistema de arquivos, como discutido 
anteriormente 
14 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Por Que Não Usar o Mecanismo 
de Cache do SO? 
 Performance: 
• SO gerencia cache de arquivos no espaço do kernel: 
necessidade de chamadas ao sistema 
• Gerenciamento de buffer no espaço de usuário pode 
ser realizado com um número bem menor de 
instruções 
 Diferentes padrões de acesso: 
• O algoritmo de substituição de página LRU (Least 
Recently Used), que é popularmente usado em SOs 
pode não é o mais adequado para certos tipos de 
acesso. Por exemplo: scan de tabelas 
 
15 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Por Que Não Usar o Mecanismo 
de Cache do SO? 
 Prefetching: Sequência lógica de blocos, que é 
invisível para o SO, normalmente não 
corresponde à sequência física 
 Escritas Forçadas de Páginas no Disco: o SGBD 
precisa ter o controle sobre o momento em 
que certas páginas são escritas no disco. Por 
exemplo, para gerenciar mecanismos de 
logging (a ser visto mais adiante no curso) 
 
16 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Introdução 
 Operações do Gerenciador de Buffer 
 String de Referência 
 Localidade de Referência 
 Algoritmo para Estratégia de Alocação 
 Algoritmos para Substituição de Páginas17 
Serviços do Gerenciador de Buffer 
 O principal serviço do gerenciador é retornar endereços 
de páginas solicitadas por operações em C3* (referências 
lógicas) 
 Solicitantes em C3 enviam requições usando 
identificadores de páginas 
• O particionamento do BD em páginas e a respectiva 
identificação é vísivel em C3 por razões de performance 
 O gerenciador retorna o endereço de mémoria da página 
 Este serviço é acionado pela interface FIX/UNFIX 
exportada por C2 
 
 
18 
* No restante da discussão, focaremos em requisiçoes para acesso de 
leitura ou escrita de páginas. Requisições para criação ou remoção de 
páginas são tratadas de maneira similar. 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Interface FIX/UNFIX 
 Método FIX: possui uma página 𝑃𝑖 como parâmetro, 
opcionalmente com um flag sinalizando intenção de 
atualização na página 
• 𝑃𝑖 é localizada, armazenada em um quadro de página, e 
“fixada“ no buffer para evitar que a mesma seja removida 
do buffer enquanto estiver sendo usada 
• O endereço de memória de 𝑃𝑖 é passado para o invocador 
(em C3) do método FIX 
• O invocador pode usar e modificar os elementos de dados 
contidos em 𝑃𝑖 
 Método UNFIX: Após o término das operações em 𝑃𝑖 , 
o método UNFIX é invocado para deixar 𝑃𝑖 disponível 
para seleção pelo algoritimo de substituição de páginas 
(mais adiante) 
19 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Interface FIX/UNFIX:Exemplo 
20 
C3 
C2 
FIX(𝑃33, escrita) 
Retorno FIX 
Endereço de 𝑃33 
0xF13A42BC 
Interface de C2 
Operação em C3 
UNFIX(𝑃33) 
Gerenciador de Buffer 
Operações do Gerenciador de Buffer 
 O gerenciador de buffer realiza três operações básicas 
para atender as invocações dos métodos FIX e UNFIX 
21 
Busca de Páginas no Buffer 
Estratégia de Alocação 
Substituição de Páginas 
G
er
en
ci
ad
o
r 
d
e 
B
u
ff
er
 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Busca de Páginas no Buffer 
22 
 Verifica se um página requisitada se encontra no buffer 
 Diversas estratégias possíveis: 
• Busca sequencial 
• Uso de estruturas auxiliares (uma entrada para cada 
quadro de página): tabelas, tabelas ordenadas, árvores 
 Winner: Tabela hash com overflow chain 
• Mapeia identificadores de página para o endereço de 
memória correspodente 
• Páginas sem entrada na tabela hash não estão em 
mémoria 
• Número de entrada acessadas para cada referência lógica 
varia no intervalo 1,1.2 
• Esta tabela recebe o nome de tabela de tradução 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Estratégia de Alocação 
 Estratégia de alocação é usada para distribuir 
quadros de páginas entre transações 
concorrentes 
 Alocação dinâmica: 
• Quantidade de quadros de páginas associados a uma 
transação pode aumentar ou diminuir durante a 
execução da mesma 
 A estratégia de alocação também determina as 
páginas a serem consideradas pelo algoritmo de 
substituição de páginas, como veremos a seguir 
 
23 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Substituição de Páginas 
 Se o buffer está cheio e uma página que não se 
encontra em memória é referenciada, então é 
necessário escolher uma “vítima” para ser substituída 
no buffer pela nova página referenciada 
 A estratégia de alocação de páginas determina o 
conjunto de páginas elegíveis para substituição 
 Um algoritmo de substituição de páginas é então 
usado para determinar qual página do conjunto de 
páginas elegíveis será escolhida para ceder lugar no 
buffer para a nova página 
• Caso a página escolhida tenha sido modificada (página 
suja), então a mesma tem que ser escrita no disco antes 
que seu conteúdo seja substituído no buffer 
24 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Estratégia de Alocação 
e Substituição de Páginas 
 Os algoritmos para implementar a estratégia 
de alocação e o mecanismo de substituição de 
páginas são bastante relacionados 
• Um mesmo arcabouço algorítmico pode ser usado 
para as duas operações 
• Entretanto, o problema de alocação de quadros e 
o de substituição de páginas são logicamente 
diferentes 
 Algoritmos para estas duas operações serão 
apresentados mais adiante 
 
25 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
 A seguir são apresentados os passos de 
processamento do gerenciador de buffer após 
a realização de uma referência lógica à página 
através da invocação do método FIX em C2 
1. O gerenciador de buffer realiza uma busca pela 
página no buffer 
2. Caso a página já estiver no buffer, a mesma é 
“fixada” (isto é, a mesma não será considerada 
pelo algoritmo de substituição de páginas) e seu 
endereço é retornado para o invocador em C3 
 
 
Putting It All Together 
26 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Putting It All Together (2) 
3. Se a página não estiver no buffer, mas existir 
quadros de páginas livres, então é realizada uma 
referencia física, isto é, uma invocação do 
serviço de C1 (ex.: 𝑅𝐸𝐴𝐷(𝐵)), para acessar o 
conteúdo do bloco correspondente 
4. Se a página não estiver no buffer e não existir 
quadros de páginas livres, então o algoritmo de 
substituição de páginas é executado para 
escolher uma “vítima” do conjunto de páginas 
elegíveis para substituição 
27 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Putting It All Together (3) 
3. Caso a vítima for uma página suja, então é realizada 
uma referencia física, isto é, uma invocação do serviço 
de C1 (ex.: 𝑊𝑅𝐼𝑇𝐸(𝑃)), para escrever o conteúdo da 
página no bloco correspondente 
5. Uma referência física é realizada para acessar o bloco 
correspondente à página solicitada e seu conteúdo é 
armazenado no quadro de página ocupado 
anteriormente pela vítima 
7. Assim como no passo 2, a página referenciada é 
“fixada” antes de seu endereço ser retornado para o 
invocador em C3 
 
28 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Putting It All Together 
1) Referência lógica para página 
X 
2) Página suja Y é escolhida 
como vítima e uma 
referência físíca é realizada 
para escrevê-la no disco 
3) Outra referência física é 
realizada para ler o conteúdo 
do bloco X e armazená-lo no 
quadro de página ocupado 
anteriormente por X 
4) O endereço do quadro de 
página Y é retornado para C3 
29 
Buffer 
Disco 
Y 
X Y 
referência física 
referência lógica 
FIX (X) 
2 
3 
1 4 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Introdução 
 Operações do Gerenciador de Buffer 
 String de Referência 
 Localidade de Referência 
 Algoritmo para Estratégia de Alocação 
 Algoritmos para Substituição de Páginas 
30 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
String de Referências 
Lógicas de Página 
 A sequência de referências lógicas em ordem 
temporal é chamada de string de referências 
lógicas de página (ou, abreviadamente, string de 
referência, quando o contexto for claro) 
• Exemplo: 𝑃1, 𝑃4, 𝑃13, 𝑃1, 𝑃13, 𝑃13, 𝑃13, 𝑃1, 𝑃4 
• Descrevem o padrão de referências lógicas do SGBD 
 Fatores que influenciam este padrão: 
• O tipo das transações consituindo a “carga” do SGBD 
(atualização, leitura, acesso sequencial, etc) 
• O mix de transações em paralelo 
• Estruturas de acesso (índices) e o modelo de dados 
31 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Referências Lógicas 
 Referêcias lógicas emitidas por uma única 
transação independem do tamanho do buffer 
 Referêcias lógicas emitidas pelo conjunto global 
de transações dependem indiretamente do 
tamanho do buffer 
• Sequência global de transações é afetada pelo 
escalonamento de processamento de transações 
• Escalonamento de transações é determinado, em 
grande parte,por transações gerando referências 
físicas 
• Referências físicas é uma função do tamanho do 
buffer 
32 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Padrão de Referências Lógicas 
 Localidade no padrão de referência não é 
causado necessariamente por apenas uma 
transação, mas pode emergir da sequência de 
referências global do conjunto de relações 
• O uso concorrente de uma página por transações é 
frequente 
 Padrão de referência em BDs pode ser previsível 
devido a existência de caminhos de acesso 
(índices). Ex.: A raiz de árvores possui alta 
probabilidade de acesso 
33 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
String de Referências Físicas 
 Toda referência física é precedida por uma 
referência lógica 
• Entretanto, nem toda referência lógica resulta em 
uma referência física 
 Diretamente influenciada pelo tamanho do buffer 
e pelo algoritmo de substituição de páginas 
 A mesma string de referências lógicas pode gerar 
strings de referências físicas bastante diferentes 
para diferentes algoritmos de substituição de 
páginas 
34 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Introdução 
 Operações do Gerenciador de Buffer 
 String de Referência 
 Localidade de Referência 
 Algoritmo para Estratégia de Alocação 
 Algoritmos para Substituição de Páginas 
35 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Localidade de Referência 
 A propriedade mais importante da string de 
referência lógica a ser explorada algoritmos de 
alocação de buffer e substituição de páginas 
 Dado uma string de referência lógica, como 
caracterizar e medir a localidade? 
36 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Distribuição da Profundidade 
da Pilha LRU 
 Pilha LRU: páginas referenciadas são colocadas 
em uma pilha; página usada mais recentemente 
sempre encontra-se no topo 
 Se uma página referenciada encontra-se também 
em posições mais baixas da pilha, ela é deletada 
 Realizando uma contagem do quantidade de 
vezes que páginas encontram-se em determinada 
profundidade da pilha é possível estabelecer uma 
distribuição da profundidade da pilha LRU 
37 
38 
Distribuição da Profundidade 
da Pilha LRU 
A 
B 
C 
D 
E 
1 
2 
3 
4 
5 
String de referência: ABACAAADDE 
A 
B 
C 
D 
E 
B 
A 
C 
D 
E 
A 
B 
C 
D 
E 
C 
A 
B 
D 
E 
A 
C 
B 
D 
E 
A 
C 
B 
D 
E 
A 
C 
B 
D 
E 
D 
A 
C 
B 
E 
D 
A 
C 
B 
E 
E 
D 
A 
C 
B 
Pilhas LRU 
1 2 3 4 5 
Distribuição de 
profundidade 
da pilha LRU 
profundidade da pilha 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Distribuição de Profundidade: 
Aplicação sobre SO 
39 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Distribuição de Profundidade: 
SGBD 
40 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Por que a Distribuição 
do SGBD é Diferente? 
 A página “mais jovem“ já encontra-se fixa no 
buffer; acesso subsequentes a essa página não 
geram outras referências 
 Referências em posições 6-40 são causadas por 
transações bloqueadas por um certo período de 
tempo porque outras transações concorrentes 
estão mantendo acesso exclusivo a recursos 
requisitados por estas transações 
 Distribuição não é monotonicamente decrescente 
41 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Introdução 
 Operações do Gerenciador de Buffer 
 String de Referência 
 Localidade de Referência 
 Algoritmo para Estratégia de Alocação 
 Algoritmos para Substituição de Páginas 
42 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Algoritmo para 
Estratégia de Alocação 
 O algoritmo a ser apresentado aloca quadros 
de página para cada transação baseando-se na 
respectiva string de referência lógica 
• A string de referência lógica para cada transação é 
analisada em separado 
 Propriedade de localidade é medida usando o 
conceito de working-set 
43 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Modelo Working-Set 
 O working-set de uma transação, denotado por 𝑊 𝑡, 𝜏 
, é definido como o conjunto de páginas distintas entre 
as 𝜏 últimas páginas referenciadas até o tempo 𝑡 
 𝜏 é chamado de tamanho da janela 
 𝑤 𝑡, 𝜏 = 𝑊 𝑡, 𝜏 = tamanho do working set no 
tempo 𝑡 
• Isto é, quantidade de páginas distintas referenciadas para 
uma janela 𝜏 no tempo 𝑡 
 A média do tamanho do working-set durante 
diferentes valores de 𝑡, denotado por 𝑤 𝜏 , pode ser 
usado como uma medida da localidade 
44 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Modelo Working-Set: Exemplo 
45 
A B A C A B A B C D E F G H 
𝑡1 
𝑡2 
𝜏 = 8 
𝜏 = 8 𝑤 𝑡1 , 𝜏 = 8 = 3 
𝑤 𝑡2 , 𝜏 = 8 = 8 
𝑤 𝜏 = 8 =
8 + 3
2
= 5.5 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Estratégia de Alocação Dinâmica 
usando Working-Sets 
 Quatro princípios básicos: 
1. Em fases de alta localidade de uma transação, a 
quantidade de quadros de páginas alocados para esta 
transação diminui (working-set pequeno) 
2. Em fases de baixa localidade de uma transação, a 
quantidade de quadros de páginas alocados para esta 
transação aumenta (working-set grande) 
3. Páginas que pertençam ao working-set de uma ou mais 
transações são mantidas no buffer 
4. Páginas que não pertençam ao working-set de qualquer 
transação são elegíveis para substuição 
 Generalização: uso de janelas 𝜏 de tamanhos 
diferentes para diferentes tipos de transações: 
sistema de prioridade 
 
 
46 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Agenda 
 Introdução 
 Operações do Gerenciador de Buffer 
 String de Referência 
 Localidade de Referência 
 Algoritmo para Estratégia de Alocação 
 Algoritmos para Substituição de Páginas 
47 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Algoritmos de 
Substituição de Páginas 
 Recebem com entrada o conjunto de páginas 
elegíveis para substituição determinado pela 
estratégia de alocação 
 Objetivo básico: escolher como “vítima” a 
página com menor probabilidade de 
referência futura 
48 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
LRU (Least Recently Used) 
 Substitui a página que foi referenciada pela 
última vez há mais tempo 
 Intuição: páginas que não tem sido usadas por 
um bom tempo possuem menos 
probabilidade de serem acessadas novamente 
 O gerenciador de buffer precisa manter uma 
tabela indicando a última vez que cada página 
foi acessada 
49 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
FIFO (First-In-First-Out) 
 Seleciona a página que foi carregada do disco 
para a memória há mais tempo 
 O gerenciador precisa apenas saber o momento 
que o bloco do disco foi escrito no buffer 
 Como a estratégia FIFO desconsidera referências, 
páginas altamente referenciadas e que estejam 
no buffer há mais tempo podem ser selecionadas 
como vítima. Ex.: o nó raiz de uma árvore B 
 FIFO é apropriado para padrões de acesso 
sequencial. Ex.: scan de uma tabela 
50 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Algoritmo Clock (Segunda Chance) 
 Implementado seguindo metáfora dos movimentos de um 
relógio: páginas são organizadas logicamente como um círculo 
 Cada página possui um bit associado 
 Quando uma página é carregada no buffer ou referenciada, o 
valor bit é feito igual a 1 
 Quando o gerenciador de buffer precisa selecionar uma página 
como vítima, ele percorre o conjunto de páginas em sentido 
horário 
• Se o bit de uma página encontrada for 1, então ele é modificado 
para 0 
• Seo bit de uma página for 0, então esta página é selecionada como 
vítima 
 Uma página só é selecionada como vítimase a mesma não 
tiver nenhum acesso após segunda passagem do “ponteiro do 
relógio” 
51 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Algoritmo Clock (Segunda Chance) 
52 
0 
1 
1 
1 
0 
1 
1 
1 
0 
1 
1 
0 
0 
0 
0 
0 
1 
1 
1 
1 
1 
0 
0 
0 
0 
0 
0 
0 
1 
0 
0 
0 
Tempo 1 Tempo 2 
vítima 
Tempo 3 
páginas 
referenciadas 
vítima 
Tempo 4 
página lida do disco 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Algoritmo Clock: Generalização 
 No lugar de bits, contadores podem usados 
• Diferentes valores podem definir um sistema de 
prioridades 
• Ex.: O nó raiz de uma árvore B recebe um valor 
mais alto 
 Implementação do mecanismo FIX/UNFIX 
• FIX: muda o valor do contador para infinito 
• UNFIX: muda o valor do contador para 0 
53 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Referências Adicionais 
 Stonebraker, M: Operating System Support for 
Database Management. Commun. ACM 24(7): 
412-418 (1981) 
 Effelsberg, W., Härder, T.: Principles of 
Database Buffer Management. ACM 
Transactions on Database Systems, 9(4), pp. 
560-595 (1984) 
54