LRU Algorithm

lru.rb

#!/usr/bin/env ruby

# O algoritmo LRU (Least Recently Used) é utilizado em sistemas operacionais como método 
# de substituição de páginas. Considerando que 4 páginas são alocadas na memória principal, 
# após a requisição das páginas 4, 7, 5, 7, 6, 7, 10, 4, 8, 5, 8, 6, 8, 11, 4, 9, 5, 9, 6, 
# 9, 12, 4, 7, 5, 7 o número de falhas de página (page faults) será
# (A) 15  (B) 17  (C) 19  (D) 21  (E) 23



def main
  n = 4
  acessos = '4,7,5,7,6,7,10,4,8,5,8,6,8,11,4,9,5,9,6,9,12,4,7,5,7'.split(',')

  
  acessos.map! {|a| a.to_i}
  puts "Entrada: #{acessos.join(',')}"
  puts "Executando o LRU para #{n} slots de memória"

  fault = 0
  memoria = MemoriaComTemporizador.new

  n.times {memoria << -1}

  acessos.each do |pagina|
    print "[#{memoria.join(',')}]".ljust(20)
    if memoria.include?(pagina)
      print " - hit : #{pagina.to_s.rjust(2)}"
      memoria.refresca pagina
    else
      print " - miss: #{pagina.to_s.rjust(2)}"
      fault += 1
      memoria.adiciona pagina
    end
  
    puts " -> [#{memoria.join(',')}]".rjust(20)
  end

  puts "Total de Faults: #{fault}"
end


class Memoria < Array
  def refresca(pagina)
    old = self.clone
    n = self.size
    n.times {self.pop} #esvazia
    self << pagina
    old.each {|i| self << i unless self.include?(i)}
  end
  
  def adiciona(pagina)
    old = self.clone
    n = self.size
    n.times {self.pop} #esvazia
    self << pagina
    old.each {|i| self << i} 
    self.pop
  end
end


class MemoriaComTemporizador < Array
  def refresca(pagina)
    self.each do |a| 
      a[1] = a[0]==pagina ? 0 : a[1]+1 if a.class == Array
    end
  end
  
  def adiciona(pagina)
    empty_i = self.index(-1)
    final_i = 0
    if empty_i
      final_i = empty_i 
    else
      maior = 0
      self.each_with_index do |a,i|
        atual = a[1]
        if atual > maior
          final_i = i 
          maior = atual
        end
      end
    end
    self[final_i] = [pagina, 0]
    self.refresca pagina
  end
  
  def include?(pagina)
    self.each{|a| return true if a[0]==pagina}
    false
  end
end

main

rodrigo@rodrigo-macbook:~/Documents/Provas Petrobras$ ./lru.rb
Entrada: 4,7,5,7,6,7,10,4,8,5,8,6,8,11,4,9,5,9,6,9,12,4,7,5,7
Executando o LRU para 4 slots de memória
[-1,-1,-1,-1]        - miss:  4   -> [4,0,-1,-1,-1]
[4,0,-1,-1,-1]       - miss:  7  -> [4,1,7,0,-1,-1]
[4,1,7,0,-1,-1]      - miss:  5 -> [4,2,7,1,5,0,-1]
[4,2,7,1,5,0,-1]     - hit :  7 -> [4,3,7,0,5,1,-1]
[4,3,7,0,5,1,-1]     - miss:  6 -> [4,4,7,1,5,2,6,0]
[4,4,7,1,5,2,6,0]    - hit :  7 -> [4,5,7,0,5,3,6,1]
[4,5,7,0,5,3,6,1]    - miss: 10 -> [10,0,7,1,5,4,6,2]
[10,0,7,1,5,4,6,2]   - miss:  4 -> [10,1,7,2,4,0,6,3]
[10,1,7,2,4,0,6,3]   - miss:  8 -> [10,2,7,3,4,1,8,0]
[10,2,7,3,4,1,8,0]   - miss:  5 -> [10,3,5,0,4,2,8,1]
[10,3,5,0,4,2,8,1]   - hit :  8 -> [10,4,5,1,4,3,8,0]
[10,4,5,1,4,3,8,0]   - miss:  6 -> [6,0,5,2,4,4,8,1]
[6,0,5,2,4,4,8,1]    - hit :  8 -> [6,1,5,3,4,5,8,0]
[6,1,5,3,4,5,8,0]    - miss: 11 -> [6,2,5,4,11,0,8,1]
[6,2,5,4,11,0,8,1]   - miss:  4 -> [6,3,4,0,11,1,8,2]
[6,3,4,0,11,1,8,2]   - miss:  9 -> [9,0,4,1,11,2,8,3]
[9,0,4,1,11,2,8,3]   - miss:  5 -> [9,1,4,2,11,3,5,0]
[9,1,4,2,11,3,5,0]   - hit :  9 -> [9,0,4,3,11,4,5,1]
[9,0,4,3,11,4,5,1]   - miss:  6 -> [9,1,4,4,6,0,5,2]
[9,1,4,4,6,0,5,2]    - hit :  9 -> [9,0,4,5,6,1,5,3]
[9,0,4,5,6,1,5,3]    - miss: 12 -> [9,1,12,0,6,2,5,4]
[9,1,12,0,6,2,5,4]   - miss:  4 -> [9,2,12,1,6,3,4,0]
[9,2,12,1,6,3,4,0]   - miss:  7 -> [9,3,12,2,7,0,4,1]
[9,3,12,2,7,0,4,1]   - miss:  5 -> [5,0,12,3,7,1,4,2]
[5,0,12,3,7,1,4,2]   - hit :  7 -> [5,1,12,4,7,0,4,3]
*Total de Faults: 18*


rodrigo@rodrigo-macbook:~/Documents/Provas Petrobras$ ./lru.rb
Entrada: 4,7,5,7,6,7,10,4,8,5,8,6,8,11,4,9,5,9,6,9,12,4,7,5,7
Executando o LRU para 4 slots de memória
[-1,-1,-1,-1]        - miss:  4     -> [4,-1,-1,-1]
[4,-1,-1,-1]         - miss:  7      -> [7,4,-1,-1]
[7,4,-1,-1]          - miss:  5       -> [5,7,4,-1]
[5,7,4,-1]           - hit :  7       -> [7,5,4,-1]
[7,5,4,-1]           - miss:  6        -> [6,7,5,4]
[6,7,5,4]            - hit :  7        -> [7,6,5,4]
[7,6,5,4]            - miss: 10       -> [10,7,6,5]
[10,7,6,5]           - miss:  4       -> [4,10,7,6]
[4,10,7,6]           - miss:  8       -> [8,4,10,7]
[8,4,10,7]           - miss:  5       -> [5,8,4,10]
[5,8,4,10]           - hit :  8       -> [8,5,4,10]
[8,5,4,10]           - miss:  6        -> [6,8,5,4]
[6,8,5,4]            - hit :  8        -> [8,6,5,4]
[8,6,5,4]            - miss: 11       -> [11,8,6,5]
[11,8,6,5]           - miss:  4       -> [4,11,8,6]
[4,11,8,6]           - miss:  9       -> [9,4,11,8]
[9,4,11,8]           - miss:  5       -> [5,9,4,11]
[5,9,4,11]           - hit :  9       -> [9,5,4,11]
[9,5,4,11]           - miss:  6        -> [6,9,5,4]
[6,9,5,4]            - hit :  9        -> [9,6,5,4]
[9,6,5,4]            - miss: 12       -> [12,9,6,5]
[12,9,6,5]           - miss:  4       -> [4,12,9,6]
[4,12,9,6]           - miss:  7       -> [7,4,12,9]
[7,4,12,9]           - miss:  5       -> [5,7,4,12]
[5,7,4,12]           - hit :  7       -> [7,5,4,12]
*Total de Faults: 18*