Algoritmos de trocas de páginas - Implementação

Quando não há espaço disponível para armazenar a nova página o sistema operacional deverá escolher, entre as páginas que estão na memória principal, uma para remover e permitir que a nova página seja trazida para a memória. Se esta página a ser removida foi modificada enquanto estava na memória, ela deverá ser salva no disco antes de poder trazer a nova página. Caso uma página que é frequentemente acessada seja removida da memória, muito provavelmente ela deverá ser trazida de volta a memória em um curto período, causando um gasto de tempo evitável.Para gerenciar a memória, são utilizados algoritmos de troca de página.

Critérios para substituição de página:

• Idade da página: páginas muito antigas talvez sejam pouco usadas.
• Frequência de acessos: páginas muito acessadas possivelmente ainda o serão.
• Data do último acesso: páginas sem acesso a muito tempo não o serão mais. 
• Prioridade: processos de alta prioridade, ou de tempo-real, podem precisar de suas páginas de memória rapidamente.
• Conteúdo da página: páginas com  código executável exigem menos esforço enquanto páginas de dados que tenham sido alteradas precisam ser salvas.
• Páginas especiais: páginas contendo buffers de operações de E/S causam problemas.

Para o estudo de algoritmos de substituição utiliza-se uma string de referência, que indica a sequência de páginas acessadas por um processo durante sua execução.
Exemplo: 0, 2, 1, 3, 5, 4, 6, 3, 7, 4, 7, 3, 3, 5, 5, 3, 1, 1, 1, 7, 1, 3, 4, 1 
Onde cada um dos valores é referência para uma página. Dizemos que ocorre uma falta, sempre que há substituição de uma página na memória.

Algoritmo FIFO
Baseado na idade das páginas na memória, ou seja, páginas mais antigas podem ser removidas.

Algoritmo Ótimo
“A melhor página a remover  em um dado instante é aquela que ficará mais tempo sem ser usada”, ou seja, não é implementável pois seria necessário prever o futuro da cadeia de referência.

Algoritmo LRU
O LRU (Least Recently Used, menos utilizado recentemente) escolhe preferencialmente páginas antigas e menos usadas para remoção.

Algoritmo da Segunda Chance
Implementação do FIFO que analisa o bit de referência de cada página candidata, para saber se ela foi acessada recentemente. Caso essa página tenha sido acessada recentemente (bit=1), ela recebe um "segunda chance" e volta para o fim da fila com o bit ajustado para 0.
Pode ser visualizado como uma lista circular, ou relógio.

Implementação em Java
Código em Java que simula os algoritmos de substituição de páginas FIFO, LRU e Segunda Chance. A entrada da cadeia de referências segue o formato: 1,0;1,1;2,0;1,1;2,1;3,0;1,3;0,0; que corresponde a sequência de referências à página 0 do processo 1, seguido da página 1 do processo 1, etc.

import java.util.LinkedList;
import java.util.Scanner;

public class Test {
 public static void main(String[] args) {
  Scanner scanner = new Scanner(System.in);
  String referencia = scanner.nextLine();
  String[] stringReferencia = referencia.split(";");

  // FIFO
  AlgoritmoDeSubstituicao fifo = new AlgoritmoFifo(3);

  for (int i = 0; i < (stringReferencia.length - 1); i++) {
   fifo.inserir(stringReferencia[i]);

  }
  System.out.println("Page Faults: " + fifo.getPageFaultCount());

  // LRU
  AlgoritmoDeSubstituicao lru = new AlgoritmoLRU(3);

  for (int i = 0; i < (stringReferencia.length - 1); i++) {
   lru.inserir(stringReferencia[i]);

  }
  System.out.println("Page Faults: " + lru.getPageFaultCount());

  // SEGUNDA CHANCE
  AlgoritmoDeSubstituicao sc = new AlgoritmoSegundaChance(3);

  for (int i = 0; i < (stringReferencia.length - 1); i++) {
   sc.inserir(stringReferencia[i]);
   // sc.imprimirQuadros();

  }
  System.out.println("Page Faults: " + sc.getPageFaultCount());

 }
}

abstract class AlgoritmoDeSubstituicao {
 protected int numeroDeFalhas;
 protected int numeroDeQuadros;
 LinkedList quadros;

 public AlgoritmoDeSubstituicao(int numeroDeQuadros) {
  if (numeroDeQuadros < 0)
   throw new IllegalArgumentException();
  this.numeroDeQuadros = numeroDeQuadros;
  numeroDeFalhas = 0;
 }

 public int getPageFaultCount() {
  return numeroDeFalhas;
 }

 public abstract void inserir(String pageNumber);

 public void imprimirQuadros() {
  System.out.print("Quadros:  ");
  for (int i = 0; i < quadros.size(); i++) {
   System.out.print(quadros.get(i) + " ");
  }
  System.out.println();
 }
}

class AlgoritmoSegundaChance extends AlgoritmoDeSubstituicao {
 LinkedList bits;
 private static int PONTEIRO = 0;

 public AlgoritmoSegundaChance(int numeroDeQuadros) {
  super(numeroDeQuadros);
  this.quadros = new LinkedList();
  this.bits = new LinkedList();

 }

 @Override
 public void inserir(String pageNumber) {
  int tmp = quadros.indexOf(pageNumber);

  // caso a pagina ainda nao esteja na memoria
  if (tmp == -1) {
   if (quadros.size() < numeroDeQuadros) {
    quadros.add(pageNumber);
    bits.add(0);
   } else {
    while (bits.get(PONTEIRO) == 1) {
     bits.set(PONTEIRO, 0);
     PONTEIRO++;
     // ponteiro voltando ao inicio
     if (PONTEIRO == numeroDeQuadros) {
      PONTEIRO = 0;
     }
    }
    // substituicao
    quadros.remove(PONTEIRO);
    bits.remove(PONTEIRO);
    quadros.add(PONTEIRO, pageNumber);
    bits.add(PONTEIRO, 0);

    PONTEIRO++;
    // ponteiro voltando ao inicio
    if (PONTEIRO == numeroDeQuadros) {
     PONTEIRO = 0;
    }
   }
   numeroDeFalhas++;
  } else { // se a pagina ja esta na memoria
   bits.set(tmp, 1);

  }
 }

 @Override
 public void imprimirQuadros() {
  System.out.print("Quadros:  ");
  for (int i = 0; i < quadros.size(); i++) {
   System.out.print(quadros.get(i) + " bit: " + bits.get(i) + " ");
  }
  System.out.println();
 }
}

class AlgoritmoFifo extends AlgoritmoDeSubstituicao {
 private static int INSERCAO = 0;

 public AlgoritmoFifo(int numeroDeQuadros) {

  super(numeroDeQuadros);
  this.quadros = new LinkedList();
 }

 @Override
 public void inserir(String pageNumber) {
  // antes de inserir, checar se a pagina ja esta na lista
  if (!quadros.contains(pageNumber)) {

   // se a quantidade de paginas na memoria for menor que o numero de
   // quadros
   // ou seja, ainda ha espaco
   if (quadros.size() < numeroDeQuadros) {
    quadros.add(pageNumber);
   } else {
    quadros.remove(INSERCAO);
    quadros.add(INSERCAO, pageNumber);
    INSERCAO++;
    if (INSERCAO == numeroDeQuadros) {
     INSERCAO = 0;
    }
   }
   numeroDeFalhas++;

  }
 }
}

class AlgoritmoLRU extends AlgoritmoDeSubstituicao {

 public AlgoritmoLRU(int numeroDeQuadros) {
  super(numeroDeQuadros);
  // TODO Auto-generated constructor stub
  this.quadros = new LinkedList();

 }

 @Override
 public void inserir(String pageNumber) {
  // TODO Auto-generated method stub
  int tmp = quadros.indexOf(pageNumber);
  if (tmp == -1) {

   if (quadros.size() < numeroDeQuadros) {
    quadros.add(pageNumber);
   } else {

    quadros.remove(0);
    quadros.add(pageNumber);
   }
   numeroDeFalhas++;

  } else {
   quadros.remove(tmp);
   quadros.add(pageNumber);
  }
 }

}

Referências:
Sistemas Operacionais: Conceitos e Mecanismos – Carlos Maziero disponível em:
http://wiki.inf.ufpr.br/maziero/doku.php?id=so:livro_de_sistemas_operacionais