Substituição de páginas: FIFO, LRU e a política ótima

A memória dispõe de algumas molduras, cada uma com espaço para uma página. O programa pede as páginas pela ordem da sequência de referências. Se a página já estiver numa moldura, há um acerto. Caso contrário, há uma falha de página. Quando todas as molduras estão ocupadas, é preciso retirar uma página: FIFO retira a que foi carregada há mais tempo, LRU a que não é usada há mais tempo e OPT a que só voltará a ser necessária mais tarde.

Exemplo resolvido — Substituição de páginas: FIFO, LRU e a política ótima

Referências	12
LRU falhas com 3 molduras: referências − acertos	10
OPT falhas com 3 molduras: referências − acertos	7

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — Substituição de páginas: FIFO, LRU e a política ótima

A memória divide-se em molduras de igual tamanho, e os dados de um programa em páginas desse mesmo tamanho. Assim, qualquer página cabe em qualquer moldura. A sequência de referências regista, por ordem, as páginas a que o programa acede. Um acesso a uma página ausente da memória causa uma falha de página: a página é carregada e, se não houver nenhuma moldura livre, uma política de substituição escolhe a página a retirar. Uma política apresenta a anomalia de Bélády numa sequência quando produz mais falhas com F + 1 molduras do que com F.

O que significa cada símbolo

F: número de molduras
n: número de páginas de um ciclo (exercício resolvido)
r: número de repetições do ciclo

Pressupõe: Paginação a pedido: uma página só é carregada quando o programa a pede. A memória começa vazia, pelo que a primeira referência a cada página causa uma falha em qualquer política. Quando várias páginas deixam de ser necessárias, esta implementação de OPT retira a de menor número. Cada referência corresponde a uma página; não se distingue entre leituras e escritas, e retirar uma página não tem qualquer custo. Para implementar LRU de forma exata, seria preciso registar o momento de cada acesso à memória. Esse registo é demasiado dispendioso, por isso os núcleos dos sistemas operativos usam aproximações baseadas num bit de referência por página. A mais conhecida é o algoritmo do relógio.

Mais uma moldura, mais uma falha 🖖

Prima FIFO, 3 molduras e depois FIFO, 4 molduras. A sequência é 1 2 3 4 1 2 5 1 2 3 4 5, e a memória maior sofre mais falhas: 10 contra 9. Avance em ambos os casos até ao passo 7, quando chega a página 5. Com três molduras, as páginas 1 e 2 já tinham sido retiradas e carregadas de novo. São, por isso, as mais recentes, e FIFO retira a página 4. Com quatro molduras, 1 e 2 nunca saíram da memória. A página 1 é a que foi carregada há mais tempo, e FIFO retira-a um passo antes de o programa a pedir. Bélády, Nelson e Shedler descreveram este efeito em 1969. É raro: testámos FIFO em todas as sequências com menos de doze referências, para qualquer número de páginas, e nenhuma apresentou a anomalia. Das 4.213.597 sequências com exatamente doze referências, contando como uma só as que diferem apenas nos nomes das páginas, oito apresentam-na. Todas começam por 1 2 3 4 1 2 5 1 e todas produzem uma única falha adicional ao passar de três molduras para quatro. Esta é a única das oito que usa cinco páginas.

Em LRU e OPT, mais memória nunca aumenta o número de falhas 🖖

Prima LRU, 4 molduras: a mesma sequência produz 8 falhas, contra 10 com três molduras. Com F molduras, LRU mantém as F páginas usadas mais recentemente; com F + 1, mantém essas páginas e mais uma. Em cada passo, portanto, todas as páginas da memória menor também estão na maior. Uma referência que dá um acerto com três molduras também dá um acerto com quatro. FIFO mantém as páginas carregadas mais recentemente, e mudar o número de molduras altera o histórico de carregamentos: após o passo 7, três molduras contêm 1, 2 e 5, enquanto quatro contêm 2, 3, 4 e 5. OPT tem a mesma propriedade de inclusão que LRU. As políticas com esta propriedade chamam-se algoritmos de pilha. Para elas, o número de falhas na tabela abaixo dos resultados nunca aumenta com o número de molduras. Em FIFO, pode aumentar; a célula correspondente fica assinalada.

Um ciclo com uma página a mais do que cabe na memória faz LRU falhar em todos os acessos 🖖

Prima Ciclo, LRU: cinco páginas são lidas por ordem, três vezes, com quatro molduras. Todas as 15 referências causam falhas, porque a página que não é usada há mais tempo é sempre a próxima que o ciclo pede. FIFO faz exatamente o mesmo. Prima Ciclo, OPT e o total desce para 7. OPT retira a página cujo próximo acesso está mais distante; nos passos 5 e 9, é a página que acabou de ler. Só consegue identificá-la porque lê a sequência até ao fim antes de escolher. Nenhum sistema operativo pode fazer isso. OPT serve como referência: dá o menor número de falhas que qualquer política poderia conseguir nesta sequência. Acrescente uma quinta moldura e as três políticas produzem 5 falhas, uma por página.

Problema resolvido na íntegra

Quando LRU falha em todas as referências 5 passos
Prima Ciclo, OPT e identifique os passos em que ocorrem as suas 7 falhas. Considere depois um programa que soma os elementos de um vetor de 100 páginas, repetindo a operação 1.000 vezes, com 99 molduras. Quantas falhas produz LRU? E OPT? Quantas haverá com uma 100.ª moldura?

Abrir este problema na ferramenta
1. Na demonstração, as primeiras cinco referências causam falhas: quatro preenchem as molduras vazias e a quinta substitui uma página. As falhas seguintes ocorrem nos passos 9 e 13, com um intervalo de quatro referências: 5 + 2 = 7.
  
  $5 + 2 = 7 faults: steps 1 - 5, 9, 13$
2. O intervalo de quatro referências resulta da escolha de OPT. Com n − 1 molduras e um ciclo de n páginas, há exatamente uma página do ciclo fora da memória. Quando ocorre uma falha, a página cujo próximo acesso está mais distante é a que foi lida imediatamente antes: só voltará a ser pedida daí a n − 1 referências. Na última passagem, algumas páginas já não serão necessárias, e OPT pode retirar uma dessas. Ao retirar aquela página, as próximas n − 2 referências encontram as suas páginas na memória. A falha seguinte ocorre, por isso, n − 1 referências depois.
  
  $n - 1 frames : one fault every n - 1 references$
3. LRU com 99 molduras: quando o acesso à página p causa uma falha, as molduras contêm todas as outras páginas. A que não é usada há mais tempo é p + 1, precisamente a próxima que o ciclo pede. Todas as 100 × 1.000 = 100.000 referências causam falhas, tal como as 15 da demonstração. FIFO retira as mesmas páginas.
  
  $LRU : 100 \times 1000 = 100000$
4. OPT: as primeiras 99 referências preenchem as molduras. A partir da 100.ª, há uma falha a cada 99 referências, nas referências 100, 199, 298, …: são 1 + ⌊(100.000 − 100) / 99⌋ = 1 + 1.009 = 1.010 falhas. O total é 99 + 1.010 = 1.109, dado pela expressão n + ⌊n(r − 1)/(n − 1)⌋ com n = 100 e r = 1.000.
  
  $OPT : 99 + (1 + ⌊ \frac{100 000 - 100}{99} ⌋) = 99 + 1010 = 1109 = n + ⌊ \frac{n ( r - 1 )}{n - 1} ⌋$
5. Com uma 100.ª moldura, o vetor inteiro cabe na memória: qualquer uma das três políticas produz 100 falhas, uma por página, e nenhuma após a primeira passagem.
  
  $F = 100 : 100 faults$
Resposta

LRU: 100.000; OPT: 1.109; com mais uma moldura: 100. Um ciclo com uma página a mais do que cabe na memória é o pior caso para LRU. A moldura que falta reduz o número de falhas para um milésimo.

$LRU 100000, OPT 1109, 100 with one frame more$

Percurso de aprendizagem

O que custa pouco numa estrutura de dados

Referências (1)

The first insight's date and attribution: the anomaly, and its formal treatment for FIFO: L. A. Belady, R. A. Nelson and G. S. Shedler, "An anomaly in space-time characteristics of certain programs running in a paging machine," Communications of the ACM 12(6), 349–353, June 1969.

Pela equipa 42Math · Verificado com fontes publicadas. Correções bem-vindas.