Algoritmo Adaptativo de Substituição de Páginas
LRU-WAR: Exploração do Modelo LRU
com Detecção de Acessos Seqüenciais
Hugo Henrique Cassettari
Edson Toshimi Midorikawa
EPUSP - Escola Politécnica da Universidade de São Paulo
PCS - Departamento de Engenharia de Computação e Sistemas Digitais
Objetivo
Apresentar o LRU-WAR:
Um algoritmo adaptativo de substituição de páginas que
visa minimizar as falhas detectadas no algoritmo LRU sem
perder a sua simplicidade computacional.
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Apresentação
• Algoritmos de substituição de páginas
- Memória virtual paginada
- Algoritmo LRU
• Algoritmos adaptativos
- Principais propostas e contribuições
• Algoritmo LRU-WAR
- Motivação e idéia geral
- Descrição operacional detalhada
- Avaliação de desempenho
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Memória Virtual com Paginação
Página
4 KB
Área de Swap
(Disco)
Memória
Principal
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Memória Virtual com Paginação
Problema da
Substituição:
Qual página
deve ser retirada
da memória?
LRU
FIFO
MRU
LFU
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Algoritmo LRU (Least Recently Used)
ordem decrescente de recência dos acessos
Fila LRU
(memória)
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Algoritmo LRU (Least Recently Used)
• Benefícios
- Critério de substituição eficiente na maioria dos casos
- Conceitualmente muito simples
- Baixo overhead (via aproximações)
• Deficiências
- Acessos seqüenciais em um grande número de páginas distintas
- Acessos dentro de grandes loops
- Freqüência irregular de acessos a uma mesma página
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Propriedade da Localidade nos Programas
• Localidade de referências
- Concentração dos acessos realizados à memória em determinadas
regiões do espaço de endereçamento utilizado pelo programa
- Temporal e/ou espacial
• Working set
- Conjunto das páginas requeridas para o processamento de um
programa num certo intervalo de tempo
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Algoritmos Adaptativos de Substituição
• Adaptam seu comportamento em uma execução
• Atuam de acordo com as características de acesso à
memória detectadas
• Podem:
- Modificar o tamanho da memória utilizada
- Modificar o critério de substituição de páginas
- Modificar os parâmetros associados ao critério vigente
- Modificar as suas próprias regras adaptativas
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Propostas Adaptativas
• SEQ e EELRU
- Modelo LRU
- Identificação de acessos seqüenciais
• LIRS
- Previsão de acessos baseada na última reutilização de cada página
• ARC e CAR
- Estratégia do algoritmo 2Q: duas filas para gerenciar a memória
- Recência e freqüência dos acessos analisadas em conjunto
• DEAR, AFC e UBM
- Reconhecimento dinâmico de padrões de acesso à memória
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Proposta LRU-WAR (Working Area Restriction)
• Como o SEQ e o EELRU, procura detectar padrões de
acesso seqüenciais
• Utiliza LRU ou MRU-n
• Princípio: Analisar a proporção de faltas de página em
relação ao número máximo de páginas referenciadas
(hits) entre cada falta
- O algoritmo verifica a reutilização das páginas carregadas no
modelo LRU e compara com o número de faltas de página
recentes
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Área de Trabalho (Working Area)
• Porção inicial da fila LRU em que todas as páginas
referenciadas entre duas faltas consecutivas se
encontravam no momento do respectivo acesso
Posições onde páginas foram acessadas desde a última falta de página
Área de Trabalho (Working Area )
Página MRU
Página LRU
...
W
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
Fila LRU representando a memória principal
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Regiões da Fila LRU
• Parâmetro L=MIN[50,M/2]: delimita a região seqüencial
• Parâmetro C=5: delimita a região protegida
Região Protegida
L
Região Seqüencial
Região LRU
C
1
2
3
Fila LRU
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
M = 20
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Tendência Seqüencial
• Área de trabalho pequena o suficiente para indicar baixa
reutilização de páginas
Região Protegida
L
Região Seqüencial
Região LRU
C
1
2
3
Fila LRU
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
M = 20
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Operação Seqüencial
• Área de trabalho pequena o suficiente para indicar baixa
reutilização de páginas
• Número de faltas de página – desde o início da tendência
seqüencial – maior que o tamanho da área de trabalho
Região Protegida
L
Região Seqüencial
Região LRU
C
1
2
3
Fila LRU
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
M = 20
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Estados de Execução Previstos
Estado de execução
Tendência Original (LRU)
Tendência Seqüencial
Operação Seqüencial
ALGORITMO LRU-WAR
Tamanho da Área de
Critério de
Trabalho
Substituição
LRU
Maior que L
LRU
Menor ou igual a L
MRU-n
Menor ou igual a L e estável
Ponto de Substituição
(Posição na Fila LRU)
M
M
W+1
Região Protegida
L
Região Seqüencial
Região LRU
C
1
2
3
Fila LRU
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
M = 20
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Pontos de Substituição do LRU-WAR
Exemplo de falta de página
em operação seqüencial
L
Área de Trabalho
Ponto de Substituição
W +1
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
Fila LRU
M = 20
Exemplo de falta de página
em tendência original (LRU)
L
Área de Trabalho
Ponto de Substituição
W
1
2
3
Fila LRU
4
5
6
7
8
9
LRU
10 11 12 13 14 15 16 17 18 19 20
M = 20
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Exemplo de Simulação
• Identificação e atualização dinâmica da área de trabalho:
A
U
V
X
B
C
E
D
U
E
W
A
U
E
V
1
2
3
4
5
Fila LRU
W
D
A
C
F
G
D
A
F
G
H
D
F
G
H
FI
G
H
JI
K
H
JI
K
L
JI
M
K
L
J
M
N
K
L
M
O
N
L
M
O
N
P
Q
O
N
P
Q
O
R
P
Q
R
S
P
Q
R
S
T
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
FALTA 4
1
2
3
M = 20
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Mecanismo para Detecção de Erros
• Tempo de carência antes do início de uma operação
seqüencial
Área de Trabalho
Páginas não substituídas pela
L
Ponto de Substituição
op. seqüencial devido ao
tempo de carência
W +1 +2 +3 +4 +5 +6
1
2
3
Fila LRU
4
5
6
7
8
9
10 11 12 13 14 15 16 17 18 19 20
M = 20
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Versões do Algoritmo LRU-WAR
• Offline
- Completa, mas teórica
- Atualiza a fila LRU após cada acesso à memória
• Online
- Aproximada, mas factível
- Atualiza a fila LRU somente após uma falta de página
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Metodologia para Avaliação de Desempenho
Programa
executável
resultados
Gerador
de traces
Simulador
arquivo de traces
desempenho
dos algoritmos
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Simulações Realizadas
• 527 simulações com 7 programas, representados por
traces que compõem o pacote VMTrace
VMTrace
Simulações Realizadas
Arquivos
de Trace
Espresso
GCC
Gnuplot
Grobner
GS
Lindsay
P2C
Páginas
Interv. entre Número de
Tamanhos de Memória Simulados
Distintas
Tamanhos Simulações
77
10, 11, 12, ..., 73, 74, 75
1
66
458
10, 15, 20, ..., 445, 450, 455
5
90
7718 100, 200, 300, ..., 7500, 7600, 7700
100
77
67
10, 11, 12, ..., 63, 64, 65
1
56
558
10, 15, 20, ..., 545, 550, 555
5
110
521
10, 15, 20, ..., 510, 515, 520
5
103
132
10, 15, 20, ..., 120, 125, 130
5
25
Total de Simulações
527
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Gráficos de Desempenho
Diferenças
Percentuais
de Desempenho
- GCC.VMTrace
Curvas
de Desempenho
- GCC.VMTrace
2,00%
30000
Número de
faltas de
Diferença
% (faltas
de página
página)
0,00%
25000
Ótimo
LRU
LRU
LRU-WAR
LRU-WAR
-2,00%
20000
-4,00%
15000
10000
-6,00%
-8,00%
5000
10
10 0
110
11 5
135
13 0
140
14 5
5
16
16 0
0
1
1775
5
19
19 0
0
2
2005
5
2
2220
0
23
23 5
5
25
25 0
0
26
26 5
5
28
28 0
0
22995
5
33110
0
33 2
255
33 4
400
33555
5
33770
0
33 8
855
40
0
41
5
43
0
44
5
0
-10,00%
Tamanho
Tamanhoda
damemória
memória
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Gráficos de Desempenho
Diferenças
Percentuais
de Desempenho
- GNUPLOT.VMTrace
Curvas
de Desempenho
- GNUPLOT.VMTrace
10,00%
Ótimo
Diferença
Número de
% (faltas
faltas de
de página
página)
0,00%
27000
LRU
LRULRU-WAR
-10,00%
LRU-WAR
22000
-20,00%
-30,00%
17000
-40,00%
-50,00%
12000
-60,00%
10
10
30
30 0
0
70
70 0
1 0
11100
00
15
15 00
00
19
19 00
00
23
23 00
00
27
27 0
000
3
3110
000
35
35 0
000
33990
000
44330
000
44770
000
55110
000
55 5
5000
0
55 9
9000
0
63
00
67
00
71
00
75
00
7000
-70,00%
Tamanho
Tamanhoda
damemória
memória
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Gráficos de Desempenho
Diferenças
Curvas
Percentuais
de Desempenho
de Desempenho
- GS.VMTrace
- GS.VMTrace
5000
6%
LRU
Diferença
Número de
% (faltas
faltas de
de página
página)
4500
Ótimo
LRU-WAR
LRU
4000
3%
LRU-WAR
3500
3000
0%
2500
2000
-3%
1500
1000
114
455
116
605
17
185
195
0
220
055
222
205
23
245
255
0
226
655
228
805
29
305
315
0
32
5
34
340
5
35
365
375
0
38
5
40
400
5
41
5
42
435
0
44
5
46
460
5
47
5
48
495
0
50
5
52
0
-6%
500
Tamanho
Tamanho da
da memória
memória
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Resultados Obtidos
ALGORITMO LRU-WAR: Diferença percentual no número de faltas de
página em relação ao algoritmo LRU
Melhor Caso
Pior Caso
Arquivos de
Média
Trace
Diferença % (Mem.) Diferença % (Mem.)
Espresso
-7,94%
(12)
0,02%
(27)
-0,28%
GCC
-9,66%
(185)
0,18%
(245)
-1,24%
Gnuplot
-66,22%
(7700)
-0,53%
(100)
-33,38%
Grobner
-11,75%
(28)
1,02%
(13)
-3,78%
GS
-5,61%
(155)
5,09%
(300)
1,34%
Lindsay
-17,38%
(. . .)
1,74%
(130)
-8,60%
P2C
-0,72%
(50)
0,04%
(75)
-0,14%
Pacote VMTrace
-66,22%
5,09%
-6,58%
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Conclusão
• Algoritmo LRU-WAR
- Proposta simples e inédita
- Cumpre sua meta: é eficiente se acessos seqüenciais predominam
- Mostra-se confiável: seu pior desempenho constatado é aceitável
- Overhead discutível
• Trabalhos futuros
- Adaptação para viabilizá-lo em ambientes com multiprogramação
- Desenvolvimento e implementação prática da nova estratégia
- Sistema de gerenciamento de memória completo
• Agradecimentos
- Scott F. Kaplan (Amherst College)
- Yannis Smaragdakis (Georgia Institute of Technology)
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP
Contato
• Hugo Henrique Cassettari:
[email protected]
• Edson Toshimi Midorikawa: [email protected]
• ESCOLA POLITÉCNICA DA USP
Departamento de Engenharia de Computação e Sistemas Digitais
Laboratório de Arquitetura e Software Básico
Av. Prof. Luciano Gualberto, travessa 3, 158, Cidade Universitária
CEP: 05508-900, São Paulo-SP
www.lasb.pcs.poli.usp.br
I WSO / 2004 – Algoritmo Adaptativo de Substituição de Páginas LRU-WAR: Exploração do Modelo LRU com Detecção de Acessos Seqüenciais - EPUSP