Diferencia entre revisiones de «Algoritmos de criterios de reemplazo»
De Wiki de Sistemas Operativos
(Añadir LRU y LFU) |
|||
| Línea 11: | Línea 11: | ||
s = ' ' | s = ' ' | ||
for i in range(len(self.marcos)): | for i in range(len(self.marcos)): | ||
| − | s+= ' | + | s+= '___%s___ ' % (i+1) |
| − | + | return s | |
def __repr__(self): | def __repr__(self): | ||
s = '|' | s = '|' | ||
for programa in self.marcos: | for programa in self.marcos: | ||
if programa: | if programa: | ||
| − | s+= ' | + | s+= ' %s ' % programa |
else: | else: | ||
| − | s+= ' | + | s+= ' ' |
s+= '|' | s+= '|' | ||
s += '\n' + len(s)*'-' | s += '\n' + len(s)*'-' | ||
| Línea 26: | Línea 26: | ||
def ejecuta(memoria, secuencia): | def ejecuta(memoria, secuencia): | ||
fallos = 0 | fallos = 0 | ||
| − | memoria.imprime_cabecera() | + | res = memoria.imprime_cabecera() |
for programa in secuencia: | for programa in secuencia: | ||
| − | + | hay_fallo = memoria.add(programa) | |
| − | print(memoria) | + | 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))) | print('\nTasa de fallos = %s/%s\n\n' % (fallos, len(secuencia))) | ||
| Línea 49: | Línea 55: | ||
fallo = 1 | fallo = 1 | ||
if not False in self.marcos: | if not False in self.marcos: | ||
| + | # Borramos el de lo alto de la pila | ||
indice = self.marcos.index(self.pila.pop()) | indice = self.marcos.index(self.pila.pop()) | ||
self.marcos[indice] = False | self.marcos[indice] = False | ||
| − | |||
self.marcos[self.marcos.index(False)] = programa | self.marcos[self.marcos.index(False)] = programa | ||
| − | + | # Insertamos el programa en la pila actualizando | |
| − | # Insertamos el programa en la pila | ||
if programa in self.pila: | if programa in self.pila: | ||
self.pila.remove(programa) | self.pila.remove(programa) | ||
| Línea 83: | Línea 88: | ||
fallo = 1 | fallo = 1 | ||
if not False in self.marcos: | if not False in self.marcos: | ||
| + | # Elegimos uno aleatorio | ||
rand = choice(range(len(self.marcos))) | rand = choice(range(len(self.marcos))) | ||
self.marcos[rand] = programa | self.marcos[rand] = programa | ||
| − | else: | + | else: |
| + | # Hay un marco vacio | ||
self.marcos[self.marcos.index(False)] = programa | self.marcos[self.marcos.index(False)] = programa | ||
return fallo | return fallo | ||
| Línea 112: | Línea 119: | ||
fallo = 1 | fallo = 1 | ||
if not False in self.marcos: | if not False in self.marcos: | ||
| + | # Borramos el primero de la cola | ||
indice = self.marcos.index(self.cola.popleft()) | indice = self.marcos.index(self.cola.popleft()) | ||
self.marcos[indice] = False | self.marcos[indice] = False | ||
| Línea 130: | Línea 138: | ||
>>> m3 = MemoriaFIFO(4) | >>> m3 = MemoriaFIFO(4) | ||
>>> ejecuta(m3, secuencia) | >>> ejecuta(m3, secuencia) | ||
| + | </source> | ||
| + | |||
| + | |||
| + | == Criterio LRU == | ||
| + | |||
| + | <source lang="python"> | ||
| + | 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 | ||
| + | </source> | ||
| + | |||
| + | |||
| + | Código de prueba: | ||
| + | |||
| + | <source lang="python"> | ||
| + | >>> m4 = MemoriaLRU(4) | ||
| + | >>> ejecuta(m4, secuencia) | ||
| + | </source> | ||
| + | |||
| + | |||
| + | == Criterio LFU == | ||
| + | |||
| + | <source lang="python"> | ||
| + | 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 | ||
| + | </source> | ||
| + | |||
| + | |||
| + | Código de prueba: | ||
| + | |||
| + | <source lang="python"> | ||
| + | >>> m5 = MemoriaLFU(4) | ||
| + | >>> ejecuta(m5, secuencia) | ||
</source> | </source> | ||
Revisión del 14:28 10 jun 2011
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.
