Algoritmos de criterios de reemplazo

Scripts en Python para comprobar los ejercicios de criterios de reemplazo

Criterio de Aproximacion discreta LRU

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.