Created
July 11, 2011 04:54
-
-
Save rodvlopes/1075328 to your computer and use it in GitHub Desktop.
LRU Algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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 |
Author
rodvlopes
commented
Jul 12, 2011
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment