Skip to content

Instantly share code, notes, and snippets.

@rodvlopes rodvlopes/lru.rb
Created Jul 11, 2011

Embed
What would you like to do?
LRU Algorithm
#!/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
@rodvlopes

This comment has been minimized.

Copy link
Owner Author

commented Jul 12, 2011

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*
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.