Algoritmos de criterios de reemplazo

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.