Diferencia entre revisiones de «Algoritmos de criterios de reemplazo»
De Wiki de Sistemas Operativos
m (Cambiado el enlace de Página Principal#Memoria virtual a Memoria Virtual) |
|||
| (No se muestra una edición intermedia de otro usuario) | |||
| 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"> | ||
| 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 actual del 23:35 22 ene 2013
Contenido
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.
