Ver el código de «Algoritmos de criterios de reemplazo»

= 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">
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 por orden de carga FIFO ==

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


Código de prueba:

<source lang="python">
>>> m3 = MemoriaFIFO(4)
>>> ejecuta(m3, secuencia)
</source>


== Criterio de Sustitución por envejecimiento ==

<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.