Algoritmos de criterios de reemplazo - Historial de revisiones

Juarolsal: Cambiado el enlace de Página Principal#Memoria virtual a Memoria Virtual

2013-01-22T22:35:37Z

Cambiado el enlace de Página Principal#Memoria virtual a Memoria Virtual

Alexrdp: Añadir LRU y LFU

2011-06-10T12:28:26Z

Añadir LRU y LFU

Mostrar los cambios

Alexrdp en 16:13 6 jun 2011

2011-06-06T16:13:19Z

Alexrdp: Criterio por orden de carga FIFO

2011-06-06T16:07:31Z

Criterio por orden de carga FIFO

Alexrdp: Añadir algoritmos MRU y estocástico

2011-06-06T16:01:04Z

Añadir algoritmos MRU y estocástico

Alexrdp: /* Criterio de Sustitución por envejecimiento */

2011-06-06T14:25:51Z

‎Criterio de Sustitución por envejecimiento

Alexrdp: /* Criterio de Aproximacion discreta LRU */

2011-06-02T20:26:50Z

‎Criterio de Aproximacion discreta LRU

Alexrdp: Algoritmo aproximacion discreta LRU

2011-06-02T20:19:56Z

Algoritmo aproximacion discreta LRU

Página nueva

== Criterio de Aproximacion discreta LRU ==

<source lang="python">
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)))

</source>

Si ejecutamos el ejemplo visto en clase mostraría:

<source lang="python">
>>> 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
</source>

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.

@@ 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:
+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">

@@ Línea 1: / Línea 1: @@
-Algoritmosen Python para comprobar los ejercicios de [[Criterios de reemplazo|criterios de reemplazo]] del tema de '''Memoria Virtual'''. El contenido mínimo que debe tener el script es el siguiente:
+= Criterios de reemplazo =
 <source lang="python">
@@ Línea 32: / Línea 34: @@
 secuencia = [2,2,3,1,1,3,4,5,1,1,2,3,4]
 </source>
 == Criterio MRU (Most Recently Used) ==
@@ Línea 58: / Línea 61: @@
          return fallo
 </source>
 Código de prueba:
@@ Línea 65: / Línea 69: @@
 >>> ejecuta(m1, secuencia)
 </source>
 == Criterio de selección estocástica ==
@@ Línea 84: / Línea 89: @@
          return fallo
 </source>
 Código de prueba:
@@ Línea 91: / Línea 97: @@
 >>> ejecuta(m2, secuencia)
 </source>
 == Criterio por orden de carga FIFO ==
@@ Línea 116: / Línea 123: @@
          return fallo
 </source>
 Código de prueba:
@@ Línea 124: / Línea 132: @@
 </source>
 == Criterio de Sustitución por envejecimiento ==

@@ Línea 90: / Línea 90: @@
 >>> m2 = MemoriaEstocastica(4)
 >>> ejecuta(m2, secuencia)
 </source>

← Revisión anterior		Revisión del 16:01 6 jun 2011
Línea 1:		Línea 1:
−	~~Scripts en~~ Python para comprobar los ejercicios de criterios de reemplazo	+	Algoritmosen Python para comprobar los ejercicios de [[Criterios de reemplazo\|criterios de reemplazo]] del tema de '''Memoria Virtual'''. El contenido mínimo que debe tener el script es el siguiente:
		+
		+	<source lang="python">
		+	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]
		+	</source>
		+
		+	== Criterio MRU (Most Recently Used) ==
		+
		+	<source lang="python">
		+	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
		+	</source>
		+
		+	Código de prueba:
		+
		+	<source lang="python">
		+	>>> m1 = MemoriaMRU(4)
		+	>>> ejecuta(m1, secuencia)
		+	</source>
		+
		+	== Criterio de selección estocástica ==
		+
		+	<source lang="python">
		+	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
		+	</source>
		+
		+	Código de prueba:
		+
		+	<source lang="python">
		+	>>> m2 = MemoriaEstocastica(4)
		+	>>> ejecuta(m2, secuencia)
		+	</source>
		+
		+	----

	== Criterio de Sustitución por envejecimiento ==		== Criterio de Sustitución por envejecimiento ==

@@ Línea 1: / Línea 1: @@
 Scripts en Python para comprobar los ejercicios de criterios de reemplazo
-== Criterio de Aproximacion discreta LRU ==
+== Criterio de Sustitución por envejecimiento ==
 <source lang="python">

← Revisión anterior		Revisión del 20:26 2 jun 2011
Línea 1:		Línea 1:
		+	Scripts en Python para comprobar los ejercicios de criterios de reemplazo
		+
	== Criterio de Aproximacion discreta LRU ==		== Criterio de Aproximacion discreta LRU ==