Requisito previo: algoritmo de reemplazo de página de uso menos reciente (LRU) El algoritmo
de reemplazo de página de uso menos reciente reemplaza la página que no se usó recientemente.
Implementación:
en este artículo, LRU se implementa usando contadores, se usa una variable ctime (es decir, contador) para representar la hora actual, se incrementa para cada página de la array de referencia. Se utiliza un vector de par para representar los marcos de página, la primera variable del par es el número de página y la segunda variable es la hora actual. Cuando se va a insertar una nueva página y los marcos están llenos, se elimina la página con el tiempo de ctime mínimo (ya que es la página utilizada menos recientemente). Si se vuelve a acceder a la página, se actualiza el valor de ctime.
Nota:
El valor de ctime mínimo (contador/tiempo actual) representa la página utilizada menos recientemente.
Ejemplos:
Reference array is : 0, 0, 0, 2, 3, 0, 5, 7, 1, 2, 0, 8 Output : When the number of frames is : 3 The number of page faults are : 9 Reference array is : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 0, 0 Output : When the number of frames is : 3 The number of page faults are : 15
Código:
#include <bits/stdc++.h>
using namespace std;
// To calculate the number of page faults
void pageFaults(int frame_size, int* ref, int len, int ctime)
{
// Count variable to count the
// number of page faults
int cnt = 0;
// Arr to simulate frames
vector<pair<int, int> > arr;
// To initialise the array
for (int i = 0; i < frame_size; i++) {
arr.push_back(make_pair(-1, ctime));
}
int page;
for (int i = 0; i < len; i++) {
page = ref[i];
auto it = arr.begin();
for (it = arr.begin(); it != arr.end(); it++) {
if (it->first == page) {
break;
}
}
// If page is found
if (it != arr.end()) {
// update the value of
// current time
it->second = ctime;
}
// If page is not found
else {
// Find the page with min value of ctime,
// as it will be the least recently used
vector<pair<int, int> >::iterator pos;
pos = arr.begin();
int min = pos->second;
for (auto itr = arr.begin(); itr != arr.end(); itr++) {
if (itr->second < min) {
pos = itr;
min = pos->second;
}
}
// Erase this page from the frame vector
arr.erase(pos);
// Insert the new page
arr.push_back(make_pair(page, ctime));
cnt++;
}
ctime++;
}
cout << "The number of page faults is : " << cnt << endl;
}
int main()
{
// This is the reference array
int ref[] = { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 };
int len = sizeof(ref) / sizeof(ref[0]);
int frame_size = 3;
// Ctime represents current time,
// it is incremented for every page
int ctime = 0;
pageFaults(frame_size, ref, len, ctime);
}
The number of page faults is : 10
Publicación traducida automáticamente
Artículo escrito por DeveshRattan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA