Si no está familiarizado con el Algoritmo usado menos recientemente, marque Algoritmo usado menos recientemente (Reemplazo de página)
Este algoritmo es una combinación del uso de una cola, similar a FIFO ( FIFO (reemplazo de página) ) junto con el uso de una array para realizar un seguimiento de los bits utilizados para dar a la página en cola una «segunda oportunidad».
Cómo funciona el algoritmo:
- Establezca todos los valores de bitref como False (que sea el tamaño de la capacidad máxima de la cola).
- Establezca una cola vacía para tener una capacidad máxima.
- Compruebe si la cola no está llena:
- Si el elemento está en la cola, establezca su correspondiente bitref = 1.
- Si el elemento no está en la cola, introdúzcalo en la cola.
- Si la cola está llena:
- Encuentre el primer elemento de la cola que tiene su bitref = 0 y si algún elemento en el frente tiene bitref = 1, configúrelo en 0. Gire la cola hasta que encuentre un elemento con bitref = 0.
- Elimina ese elemento de la cola.
- Empuje el elemento actual de la array de entrada a la cola.
Explicación:
Los bits se establecen como de costumbre en este caso a uno para los índices en el bitref hasta que la cola esté llena.
Una vez que la cola se llena, de acuerdo con el Algoritmo de reemplazo de página FIFO, debemos deshacernos del frente de la cola (si el elemento es un error/falta). Pero aquí no hacemos eso.
En su lugar, primero verificamos su bit de referencia (también conocido como bitref) si es 0 o 1 (Falso o Verdadero). Si es 0 (falso), lo sacamos de la cola y empujamos el elemento en espera a la cola. Pero si es 1 (verdadero), establecemos su bit de referencia (bitref) en 0 y lo movemos al final de la cola. Seguimos haciendo esto hasta que nos encontramos con el frente de la cola para tener el bit de referencia de su valor frontal (bitref) como 0 (falso).
Luego seguimos lo habitual al eliminarlo de la cola y empujar el elemento de espera a la cola.
¿Qué pasa si el elemento en espera ya está en la cola? Simplemente establecemos su bit de referencia (bitref) en 1 (verdadero).
We now move all the values like 2, 4, 1 to the back until we encounter 3, whose bitref is 0. While moving 2, 4, 1 to the back, we set their bitref values to 0.
Entonces, ahora, la pregunta es cómo es esto una aproximación de LRU , cuando claramente implementa FIFO en lugar de LRU . Bueno, esto funciona dando una segunda oportunidad al principio de la cola (que en el caso de FIFO habría sido eliminado y reemplazado). Aquí, la segunda oportunidad se basa en el hecho de que si el elemento se ve «recientemente», su bit de referencia (bitref) se establece en 1 (verdadero). Si no se hubiera visto recientemente, no habríamos establecido su bit de referencia (bitref) en 1 (verdadero) y, por lo tanto, lo habríamos eliminado. Por lo tanto, es por eso que es una aproximación y no LRU ni FIFO .
A continuación se muestra la implementación del enfoque anterior:
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find an element in the queue as
// std::find does not work for a queue
bool findQueue(queue<int> q, int x)
{
while (!q.empty()) {
if (x == q.front())
return true;
q.pop();
}
// Element not found
return false;
}
// Function to implement LRU Approximation
void LRU_Approximation(vector<int> t, int capacity)
{
int n = t.size();
queue<int> q;
// Capacity is the size of the queue
// hits is number of times page was
// found in cache and faults is the number
// of times the page was not found in the cache
int hits = 0, faults = 0;
// Array to keep track of bits set when a
// certain value is already in the queue
// Set bit --> 1, if its a hit
// find the index and set bitref[index] = 1
// Set bit --> 0, if its a fault, and the front
// of the queue has bitref[front] = 1, send front
// to back and set bitref[front] = 0
bool bitref[capacity] = { false };
// To find the first element that does not
// have the bitref set to true
int ptr = 0;
// To check if the queue is filled up or not
int count = 0;
for (int i = 0; i < t.size(); i++) {
if (!findQueue(q, t[i])) {
// Queue is not filled up to capacity
if (count < capacity) {
q.push(t[i]);
count++;
}
// Queue is filled up to capacity
else {
ptr = 0;
// Find the first value that has its
// bit set to 0
while (!q.empty()) {
// If the value has bit set to 1
// Set it to 0
if (bitref[ptr % capacity])
bitref[ptr % capacity] = !bitref[ptr % capacity];
// Found the bit value 0
else
break;
ptr++;
}
// If the queue was empty
if (q.empty()) {
q.pop();
q.push(t[i]);
}
// If queue was not empty
else {
int j = 0;
// Rotate the queue and set the front's
// bit value to 0 until the value where
// the bitref = 0
while (j < (ptr % capacity)) {
int t1 = q.front();
q.pop();
q.push(t1);
bool temp = bitref[0];
// Rotate the bitref array
for (int counter = 0; counter < capacity - 1; counter++)
bitref[counter] = bitref[counter + 1];
bitref[capacity - 1] = temp;
j++;
}
// Remove front element
// (the element with the bitref = 0)
q.pop();
// Push the element from the
// page array (next input)
q.push(t[i]);
}
}
faults++;
}
// If the input for the iteration was a hit
else {
queue<int> temp = q;
int counter = 0;
while (!q.empty()) {
if (q.front() == t[i])
bitref[counter] = true;
counter++;
q.pop();
}
q = temp;
hits++;
}
}
cout << "Hits: " << hits << "\nFaults: " << faults << '\n';
}
// Driver code
int main()
{
vector<int> t = { 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 };
int capacity = 4;
LRU_Approximation(t, capacity);
return 0;
}
Hits: 6 Faults: 6