Diferencia entre revisiones de «Algoritmos de criterios de reemplazo»
De Wiki de Sistemas Operativos
(Criterio por orden de carga FIFO) |
|||
| Línea 1: | Línea 1: | ||
| − | + | = Criterios de reemplazo = | |
| + | |||
| + | Algoritmos en Python para comprobar los ejercicios de [[Criterios de reemplazo|criterios de reemplazo]] del tema de [[Página Principal#Memoria virtual|memoria virtual]]. El contenido mínimo que debe tener el script es el siguiente: | ||
<source lang="python"> | <source lang="python"> | ||
| Línea 32: | Línea 34: | ||
secuencia = [2,2,3,1,1,3,4,5,1,1,2,3,4] | secuencia = [2,2,3,1,1,3,4,5,1,1,2,3,4] | ||
</source> | </source> | ||
| + | |||
== Criterio MRU (Most Recently Used) == | == Criterio MRU (Most Recently Used) == | ||
| Línea 58: | Línea 61: | ||
return fallo | return fallo | ||
</source> | </source> | ||
| + | |||
Código de prueba: | Código de prueba: | ||
| Línea 65: | Línea 69: | ||
>>> ejecuta(m1, secuencia) | >>> ejecuta(m1, secuencia) | ||
</source> | </source> | ||
| + | |||
== Criterio de selección estocástica == | == Criterio de selección estocástica == | ||
| Línea 84: | Línea 89: | ||
return fallo | return fallo | ||
</source> | </source> | ||
| + | |||
Código de prueba: | Código de prueba: | ||
| Línea 91: | Línea 97: | ||
>>> ejecuta(m2, secuencia) | >>> ejecuta(m2, secuencia) | ||
</source> | </source> | ||
| + | |||
== Criterio por orden de carga FIFO == | == Criterio por orden de carga FIFO == | ||
| Línea 116: | Línea 123: | ||
return fallo | return fallo | ||
</source> | </source> | ||
| + | |||
Código de prueba: | Código de prueba: | ||
| Línea 124: | Línea 132: | ||
</source> | </source> | ||
| − | |||
== Criterio de Sustitución por envejecimiento == | == Criterio de Sustitución por envejecimiento == | ||
Revisión del 18:13 6 jun 2011
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)
print(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
memoria.imprime_cabecera()
for programa in secuencia:
fallos += memoria.add(programa)
print(memoria)
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:
indice = self.marcos.index(self.pila.pop())
self.marcos[indice] = False
self.marcos[self.marcos.index(False)] = programa
# Insertamos el programa en la pila
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:
rand = choice(range(len(self.marcos)))
self.marcos[rand] = programa
else:
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:
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 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.
