Diferencia entre revisiones de «Algoritmos de criterios de reemplazo»
De Wiki de Sistemas Operativos
(Añadir LRU y LFU) |
m (Cambiado el enlace de Página Principal#Memoria virtual a Memoria Virtual) |
||
| Línea 1: | Línea 1: | ||
= Criterios de reemplazo = | = Criterios de reemplazo = | ||
| − | Algoritmos en Python para comprobar los ejercicios de [[Criterios de reemplazo|criterios de reemplazo]] del tema de [[ | + | Algoritmos en Python para comprobar los ejercicios de [[Criterios de reemplazo|criterios de reemplazo]] del tema de [[Memoria Virtual|memoria virtual]]. El contenido mínimo que debe tener el script es el siguiente: |
<source lang="python"> | <source lang="python"> | ||
Revisión actual del 00:35 23 ene 2013
Contenido
[ocultar]Criterios de reemplazo
Algoritmos en Python para comprobar los ejercicios de criterios de reemplazo del tema de memoria virtual. El contenido mínimo que debe tener el script es el siguiente:
from collections import deque
from random import choice
class Memoria:
def imprime_cabecera(self):
s = ' '
for i in range(len(self.marcos)):
s+= '___%s___ ' % (i+1)
return s
def __repr__(self):
s = '|'
for programa in self.marcos:
if programa:
s+= ' %s ' % programa
else:
s+= ' '
s+= '|'
s += '\n' + len(s)*'-'
return s
def ejecuta(memoria, secuencia):
fallos = 0
res = memoria.imprime_cabecera()
for programa in secuencia:
hay_fallo = memoria.add(programa)
if hay_fallo:
print(res + ' Fallo de %s!'%programa)
fallos += 1
else:
print(res + ' Acceso a %s'%programa)
res = str(memoria)
print(res)
print('\nTasa de fallos = %s/%s\n\n' % (fallos, len(secuencia)))
secuencia = [2,2,3,1,1,3,4,5,1,1,2,3,4]
Criterio MRU (Most Recently Used)
class MemoriaMRU(Memoria):
def __init__(self, i):
self.pila = []
self.marcos = [False] * i
def add(self, programa):
fallo = 0
# Fallo de pagina
if not programa in self.marcos:
fallo = 1
if not False in self.marcos:
# Borramos el de lo alto de la pila
indice = self.marcos.index(self.pila.pop())
self.marcos[indice] = False
self.marcos[self.marcos.index(False)] = programa
# Insertamos el programa en la pila actualizando
if programa in self.pila:
self.pila.remove(programa)
self.pila.append(programa)
return fallo
Código de prueba:
>>> m1 = MemoriaMRU(4)
>>> ejecuta(m1, secuencia)
Criterio de selección estocástica
class MemoriaEstocastica(Memoria):
def __init__(self, i):
self.marcos = [False] * i
def add(self, programa):
fallo = 0
# Fallo de pagina
if not programa in self.marcos:
fallo = 1
if not False in self.marcos:
# Elegimos uno aleatorio
rand = choice(range(len(self.marcos)))
self.marcos[rand] = programa
else:
# Hay un marco vacio
self.marcos[self.marcos.index(False)] = programa
return fallo
Código de prueba:
>>> m2 = MemoriaEstocastica(4)
>>> ejecuta(m2, secuencia)
Criterio por orden de carga FIFO
class MemoriaFIFO(Memoria):
def __init__(self, i):
self.cola = deque([])
self.marcos = [False] * i
def add(self, programa):
fallo = 0
# Fallo de pagina
if not programa in self.marcos:
fallo = 1
if not False in self.marcos:
# Borramos el primero de la cola
indice = self.marcos.index(self.cola.popleft())
self.marcos[indice] = False
self.marcos[self.marcos.index(False)] = programa
# Insertamos el programa en la cola
if not programa in self.cola:
self.cola.append(programa)
return fallo
Código de prueba:
>>> m3 = MemoriaFIFO(4)
>>> ejecuta(m3, secuencia)
Criterio LRU
class MemoriaLRU(Memoria):
def __init__(self, i):
self.cola = deque([])
self.marcos = [False] * i
def add(self, programa):
fallo = 0
# Fallo de pagina
if not programa in self.marcos:
fallo = 1
if not False in self.marcos:
# Borramos el primero de la cola
indice = self.marcos.index(self.cola.popleft())
self.marcos[indice] = False
self.marcos[self.marcos.index(False)] = programa
# Insertamos el programa en la cola actualizando
if programa in self.cola:
self.cola.remove(programa)
self.cola.append(programa)
return fallo
Código de prueba:
>>> m4 = MemoriaLRU(4)
>>> ejecuta(m4, secuencia)
Criterio LFU
class MemoriaLFU(Memoria):
def __init__(self, i):
self.marcos = [False] * i
self.contadores = [0] * i
def add(self, programa):
fallo = 0
if not programa in self.marcos:
# Fallo de pagina
fallo = 1
if False in self.marcos:
# Seleccionamos un marco vacio
indice_false = self.marcos.index(False)
self.contadores[indice_false] = 1
self.marcos[indice_false] = programa
else:
# Seleccionamos el de menor contador
indice = self.contadores.index(min(self.contadores))
self.marcos[indice] = programa
self.contadores[indice] = 1
else:
# Exito, incrementamos contador
indice = self.marcos.index(programa)
self.contadores[indice] += 1
return fallo
def __repr__(self):
s = '|'
i = 0
for programa in self.marcos:
if programa:
s+= ' %s {%s} ' % (programa, self.contadores[i])
else:
s+= ' '
s += '|'
i += 1
s += '\n' + len(s)*'-'
return s
Código de prueba:
>>> m5 = MemoriaLFU(4)
>>> ejecuta(m5, secuencia)
Criterio de Sustitución por envejecimiento
class Marco:
def __init__(self, tam):
self.programa = False
self.tam = tam
self.registro = [0] * tam
def inserta(self, programa):
self.programa = programa
self.registro = [1] + ([0] * (self.tam-1))
def actualiza(self):
self.registro[0] = 1
def desplaza(self):
self.registro = [0] + self.registro[:-1]
def __gt__(self,marco):
for i in range(self.tam):
if self.registro[i] > marco.registro[i]:
return True
return False
def __repr__(self):
if self.programa:
return '%s %s' %(self.programa, self.registro)
else:
return ' ' * (self.tam*3 + 2)
class Tabla:
def __init__(self, cantidad, tam_registros):
self.lista = []
for i in range(cantidad):
self.lista.append(Marco(tam_registros))
def addPrograma(self, programa):
esta = False
indice = 0
for marco in self.lista:
if programa == marco.programa:
esta = True
break
indice += 1
if esta:
self.lista[indice].actualiza()
return 0
else:
print("Fallo!")
indice = self.lista.index(self.minimo())
self.lista[indice].inserta(programa)
return 1
def minimo(self):
res = self.lista[0]
for marco in self.lista[1:]:
if res > marco:
res = marco
return res
def __repr__(self):
s = ''
for marco in self.lista:
s += '| %s ' % marco
s += '|\n' + '-'*(len(s)+1)
return s
class AproximacionDiscretaLRU:
def __init__(self, cantidad, periodo, tam_registros = 3):
self.tabla = Tabla(cantidad, tam_registros)
self.periodo = periodo
def ejecuta(self, lista_programas):
i = 0
fallos = 0
for programa in lista_programas:
if i%self.periodo == 0:
for marco in self.tabla.lista:
marco.desplaza()
i+=1
fallos += self.tabla.addPrograma(programa)
print(self.tabla)
print("\nTasa de fallos: %s/%s" % (fallos, len(lista_programas)))
Si ejecutamos el ejemplo visto en clase mostraría:
>>> alg = AproximacionDiscretaLRU(4, 4)
>>> alg.ejecuta([2,2,3,1,1,3,4,5,1,1,2,3,4])
Fallo!
| 2 [1, 0, 0] | | | |
---------------------------------------------------------
| 2 [1, 0, 0] | | | |
---------------------------------------------------------
Fallo!
| 2 [1, 0, 0] | 3 [1, 0, 0] | | |
---------------------------------------------------------
Fallo!
| 2 [1, 0, 0] | 3 [1, 0, 0] | 1 [1, 0, 0] | |
---------------------------------------------------------
| 2 [0, 1, 0] | 3 [0, 1, 0] | 1 [1, 1, 0] | |
---------------------------------------------------------
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | 4 [1, 0, 0] |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | 5 [1, 0, 0] |
---------------------------------------------------------
| 2 [0, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [0, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [1, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [1, 0, 1] | 3 [1, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [0, 1, 1] | 1 [0, 1, 1] | 4 [1, 0, 0] |
---------------------------------------------------------
Tasa de fallos: 6/13
La diferencia con respecto a la solución de clase es que la resolución en caso de empate es elegir el marco con índice menor.
