Diferencia entre revisiones de «Algoritmos de criterios de reemplazo»

De Wiki de Sistemas Operativos
Saltar a: navegación, buscar
(Añadir algoritmos MRU y estocástico)
m (Cambiado el enlace de Página Principal#Memoria virtual a Memoria Virtual)
 
(No se muestran 3 ediciones intermedias de otro usuario)
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 =
 +
 
 +
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">
 
<source lang="python">
Línea 9: Línea 11:
 
         s = ' '
 
         s = ' '
 
         for i in range(len(self.marcos)):
 
         for i in range(len(self.marcos)):
−
             s+= '__%s__ ' % (i+1)
+
             s+= '___%s___ ' % (i+1)
−
         print(s)
+
         return s
 
     def __repr__(self):
 
     def __repr__(self):
 
         s = '|'
 
         s = '|'
 
         for programa in self.marcos:
 
         for programa in self.marcos:
 
             if programa:
 
             if programa:
−
                 s+= ' %s ' % programa
+
                 s+= '   %s   ' % programa
 
             else:
 
             else:
−
                 s+= '     '
+
                 s+= '       '
 
             s+= '|'
 
             s+= '|'
 
         s += '\n' + len(s)*'-'
 
         s += '\n' + len(s)*'-'
Línea 24: Línea 26:
 
def ejecuta(memoria, secuencia):
 
def ejecuta(memoria, secuencia):
 
     fallos = 0
 
     fallos = 0
−
     memoria.imprime_cabecera()
+
     res = memoria.imprime_cabecera()
 
     for programa in secuencia:
 
     for programa in secuencia:
−
         fallos += memoria.add(programa)
+
         hay_fallo = memoria.add(programa)
−
         print(memoria)
+
         if hay_fallo:
 +
            print(res + '  Fallo de %s!'%programa)
 +
            fallos += 1
 +
        else:
 +
            print(res + '  Acceso a %s'%programa)
 +
        res = str(memoria)
 +
    print(res)
 
     print('\nTasa de fallos = %s/%s\n\n' % (fallos, len(secuencia)))
 
     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]
 
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 46: Línea 55:
 
             fallo = 1
 
             fallo = 1
 
             if not False in self.marcos:
 
             if not False in self.marcos:
 +
                # Borramos el de lo alto de la pila
 
                 indice = self.marcos.index(self.pila.pop())
 
                 indice = self.marcos.index(self.pila.pop())
 
                 self.marcos[indice] = False
 
                 self.marcos[indice] = False
−
               
 
 
             self.marcos[self.marcos.index(False)] = programa
 
             self.marcos[self.marcos.index(False)] = programa
−
 
+
         # Insertamos el programa en la pila actualizando
−
         # Insertamos el programa en la pila
 
 
         if programa in self.pila:
 
         if programa in self.pila:
 
             self.pila.remove(programa)
 
             self.pila.remove(programa)
Línea 58: Línea 66:
 
         return fallo
 
         return fallo
 
</source>
 
</source>
 +
  
 
Código de prueba:
 
Código de prueba:
Línea 65: Línea 74:
 
>>> ejecuta(m1, secuencia)
 
>>> ejecuta(m1, secuencia)
 
</source>
 
</source>
 +
  
 
== Criterio de selección estocástica ==
 
== Criterio de selección estocástica ==
Línea 78: Línea 88:
 
             fallo = 1
 
             fallo = 1
 
             if not False in self.marcos:
 
             if not False in self.marcos:
 +
                # Elegimos uno aleatorio
 
                 rand = choice(range(len(self.marcos)))
 
                 rand = choice(range(len(self.marcos)))
 
                 self.marcos[rand] = programa
 
                 self.marcos[rand] = programa
−
             else:  
+
             else:
 +
                # Hay un marco vacio
 
                 self.marcos[self.marcos.index(False)] = programa
 
                 self.marcos[self.marcos.index(False)] = programa
 
         return fallo  
 
         return fallo  
 
</source>
 
</source>
 +
  
 
Código de prueba:
 
Código de prueba:
Línea 92: Línea 105:
 
</source>
 
</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:
 +
                # Borramos el primero de la cola
 +
                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 LRU ==
 +
 
 +
<source lang="python">
 +
class MemoriaLRU(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:
 +
                # Borramos el primero de la cola
 +
                indice = self.marcos.index(self.cola.popleft())
 +
                self.marcos[indice] = False
 +
               
 +
            self.marcos[self.marcos.index(False)] = programa
 +
 
 +
        # Insertamos el programa en la cola actualizando
 +
        if programa in self.cola:
 +
            self.cola.remove(programa)
 +
        self.cola.append(programa)
 +
       
 +
        return fallo
 +
</source>
 +
 
 +
 
 +
Código de prueba:
 +
 
 +
<source lang="python">
 +
>>> m4 = MemoriaLRU(4)
 +
>>> ejecuta(m4, secuencia)
 +
</source>
 +
 
 +
 
 +
== Criterio LFU ==
 +
 
 +
<source lang="python">
 +
class MemoriaLFU(Memoria):
 +
    def __init__(self, i):
 +
            self.marcos = [False] * i
 +
            self.contadores = [0] * i
 +
           
 +
    def add(self, programa):
 +
        fallo = 0
 +
        if not programa in self.marcos:
 +
            # Fallo de pagina
 +
            fallo = 1
 +
            if False in self.marcos:
 +
                # Seleccionamos un marco vacio
 +
                indice_false = self.marcos.index(False)
 +
                self.contadores[indice_false] = 1
 +
                self.marcos[indice_false] = programa
 +
            else:
 +
                # Seleccionamos el de menor contador
 +
                indice = self.contadores.index(min(self.contadores))
 +
                self.marcos[indice] = programa
 +
                self.contadores[indice] = 1
 +
        else:
 +
            # Exito, incrementamos contador
 +
            indice = self.marcos.index(programa)
 +
            self.contadores[indice] += 1
 +
        return fallo
 +
 
 +
    def __repr__(self):
 +
        s = '|'
 +
        i = 0
 +
        for programa in self.marcos:
 +
            if programa:
 +
                s+= ' %s {%s} ' % (programa, self.contadores[i])
 +
            else:
 +
                s+= '      '
 +
            s += '|'
 +
            i += 1
 +
        s += '\n' + len(s)*'-'
 +
        return s
 +
</source>
 +
 
 +
 
 +
Código de prueba:
 +
 
 +
<source lang="python">
 +
>>> m5 = MemoriaLFU(4)
 +
>>> ejecuta(m5, secuencia)
 +
</source>
 +
 
  
 
== Criterio de Sustitución por envejecimiento ==
 
== Criterio de Sustitución por envejecimiento ==

Revisión actual del 23:35 22 ene 2013

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)
        return 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
    res = memoria.imprime_cabecera()
    for programa in secuencia:
        hay_fallo = memoria.add(programa)
        if hay_fallo:
            print(res + '  Fallo de %s!'%programa)
            fallos += 1
        else:
            print(res + '  Acceso a %s'%programa)
        res = str(memoria)
    print(res)
    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:
                # Borramos el de lo alto de la pila
                indice = self.marcos.index(self.pila.pop())
                self.marcos[indice] = False
            self.marcos[self.marcos.index(False)] = programa
        # Insertamos el programa en la pila actualizando
        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:
                # Elegimos uno aleatorio
                rand = choice(range(len(self.marcos)))
                self.marcos[rand] = programa
            else:
                # Hay un marco vacio
                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:
                # Borramos el primero de la cola
                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 LRU

class MemoriaLRU(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:
                # Borramos el primero de la cola
                indice = self.marcos.index(self.cola.popleft())
                self.marcos[indice] = False
                
            self.marcos[self.marcos.index(False)] = programa

        # Insertamos el programa en la cola actualizando
        if programa in self.cola:
            self.cola.remove(programa)
        self.cola.append(programa)
        
        return fallo


Código de prueba: 

>>> m4 = MemoriaLRU(4)
>>> ejecuta(m4, secuencia)


Criterio LFU

class MemoriaLFU(Memoria):
    def __init__(self, i):
            self.marcos = [False] * i
            self.contadores = [0] * i
            
    def add(self, programa):
        fallo = 0
        if not programa in self.marcos:
            # Fallo de pagina
            fallo = 1
            if False in self.marcos:
                # Seleccionamos un marco vacio
                indice_false = self.marcos.index(False)
                self.contadores[indice_false] = 1
                self.marcos[indice_false] = programa
            else:
                # Seleccionamos el de menor contador
                indice = self.contadores.index(min(self.contadores))
                self.marcos[indice] = programa
                self.contadores[indice] = 1
        else:
            # Exito, incrementamos contador
            indice = self.marcos.index(programa)
            self.contadores[indice] += 1
        return fallo

    def __repr__(self):
        s = '|'
        i = 0
        for programa in self.marcos:
            if programa:
                s+= ' %s {%s} ' % (programa, self.contadores[i])
            else:
                s+= '       '
            s += '|'
            i += 1
        s += '\n' + len(s)*'-'
        return s


Código de prueba: 

>>> m5 = MemoriaLFU(4)
>>> ejecuta(m5, 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.

Obtenido de «https://1984.lsi.us.es/wiki-ssoo/index.php?title=Algoritmos_de_criterios_de_reemplazo&oldid=2769»