Requisito previo: Algoritmos de reemplazo de página
En los sistemas operativos que usan paginación para la administración de la memoria, se necesitan algoritmos de reemplazo de página para decidir qué página debe reemplazarse cuando ingresa una nueva. El sistema operativo reemplaza una de las páginas existentes con una página recién necesaria. Diferentes algoritmos de reemplazo de página sugieren diferentes formas de decidir qué página reemplazar. El objetivo de todos los algoritmos es reducir el número de errores de página.
El algoritmo L ort R ecently U sed (LRU) es un algoritmo Greedy en el que la página que se va a reemplazar se usa menos recientemente. La idea se basa en la localidad de referencia, no es probable que la página utilizada menos recientemente
Digamos la string de referencia de la página 7 0 1 2 0 3 0 4 2 3 0 3 2 . Inicialmente tenemos 4 espacios para páginas vacíos.
Inicialmente, todos los espacios están vacíos, por lo que cuando se asignan 7 0 1 2 a los espacios vacíos —> 4 errores de página,
0 ya es su error de página, entonces —> 0 error de página.
cuando llegó 3, ocupará el lugar de 7 porque es el que se usó menos recientemente —> 1 Error de página
0 ya está en la memoria, así que —> 0 Error de página .
4 tendrá lugar de 1 —> 1 Fallo de página
Ahora para la siguiente string de referencia de página —> 0 Fallo de página porque ya están disponibles en la memoria.
Dada la capacidad de la memoria (como la cantidad de páginas que puede contener) y una string que representa las páginas a las que se debe hacer referencia, escriba una función para encontrar la cantidad de fallas de página.
Let capacity be the number of pages that
memory can hold. Let set be the current
set of pages in memory.
1- Start traversing the pages.
i) If set holds less pages than capacity.
a) Insert page into the set one by one until
the size of set reaches capacity or all
page requests are processed.
b) Simultaneously maintain the recent occurred
index of each page in a map called indexes.
c) Increment page fault
ii) Else
If current page is present in set, do nothing.
Else
a) Find the page in the set that was least
recently used. We find it using index array.
We basically need to replace the page with
minimum index.
b) Replace the found page with current page.
c) Increment page faults.
d) Update index of current page.
2. Return page faults.
A continuación se muestra la implementación de los pasos anteriores.
C++
//C++ implementation of above algorithm
#include<bits/stdc++.h>
using namespace std;
// Function to find page faults using indexes
int pageFaults(int pages[], int n, int capacity)
{
// To represent set of current pages. We use
// an unordered_set so that we quickly check
// if a page is present in set or not
unordered_set<int> s;
// To store least recently used indexes
// of pages.
unordered_map<int, int> indexes;
// Start from initial page
int page_faults = 0;
for (int i=0; i<n; i++)
{
// Check if the set can hold more pages
if (s.size() < capacity)
{
// Insert it into set if not present
// already which represents page fault
if (s.find(pages[i])==s.end())
{
s.insert(pages[i]);
// increment page fault
page_faults++;
}
// Store the recently used index of
// each page
indexes[pages[i]] = i;
}
// If the set is full then need to perform lru
// i.e. remove the least recently used page
// and insert the current page
else
{
// Check if current page is not already
// present in the set
if (s.find(pages[i]) == s.end())
{
// Find the least recently used pages
// that is present in the set
int lru = INT_MAX, val;
for (auto it=s.begin(); it!=s.end(); it++)
{
if (indexes[*it] < lru)
{
lru = indexes[*it];
val = *it;
}
}
// Remove the indexes page
s.erase(val);
// insert the current page
s.insert(pages[i]);
// Increment page faults
page_faults++;
}
// Update the current page index
indexes[pages[i]] = i;
}
}
return page_faults;
}
// Driver code
int main()
{
int pages[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};
int n = sizeof(pages)/sizeof(pages[0]);
int capacity = 4;
cout << pageFaults(pages, n, capacity);
return 0;
}
Java
// Java implementation of above algorithm
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
class Test
{
// Method to find page faults using indexes
static int pageFaults(int pages[], int n, int capacity)
{
// To represent set of current pages. We use
// an unordered_set so that we quickly check
// if a page is present in set or not
HashSet<Integer> s = new HashSet<>(capacity);
// To store least recently used indexes
// of pages.
HashMap<Integer, Integer> indexes = new HashMap<>();
// Start from initial page
int page_faults = 0;
for (int i=0; i<n; i++)
{
// Check if the set can hold more pages
if (s.size() < capacity)
{
// Insert it into set if not present
// already which represents page fault
if (!s.contains(pages[i]))
{
s.add(pages[i]);
// increment page fault
page_faults++;
}
// Store the recently used index of
// each page
indexes.put(pages[i], i);
}
// If the set is full then need to perform lru
// i.e. remove the least recently used page
// and insert the current page
else
{
// Check if current page is not already
// present in the set
if (!s.contains(pages[i]))
{
// Find the least recently used pages
// that is present in the set
int lru = Integer.MAX_VALUE, val=Integer.MIN_VALUE;
Iterator<Integer> itr = s.iterator();
while (itr.hasNext()) {
int temp = itr.next();
if (indexes.get(temp) < lru)
{
lru = indexes.get(temp);
val = temp;
}
}
// Remove the indexes page
s.remove(val);
//remove lru from hashmap
indexes.remove(val);
// insert the current page
s.add(pages[i]);
// Increment page faults
page_faults++;
}
// Update the current page index
indexes.put(pages[i], i);
}
}
return page_faults;
}
// Driver method
public static void main(String args[])
{
int pages[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};
int capacity = 4;
System.out.println(pageFaults(pages, pages.length, capacity));
}
}
// This code is contributed by Gaurav Miglani
C#
// C# implementation of above algorithm
using System;
using System.Collections.Generic;
class GFG
{
// Method to find page faults
// using indexes
static int pageFaults(int []pages,
int n, int capacity)
{
// To represent set of current pages.
// We use an unordered_set so that
// we quickly check if a page is
// present in set or not
HashSet<int> s = new HashSet<int>(capacity);
// To store least recently used indexes
// of pages.
Dictionary<int,
int> indexes = new Dictionary<int,
int>();
// Start from initial page
int page_faults = 0;
for (int i = 0; i < n; i++)
{
// Check if the set can hold more pages
if (s.Count < capacity)
{
// Insert it into set if not present
// already which represents page fault
if (!s.Contains(pages[i]))
{
s.Add(pages[i]);
// increment page fault
page_faults++;
}
// Store the recently used index of
// each page
if(indexes.ContainsKey(pages[i]))
indexes[pages[i]] = i;
else
indexes.Add(pages[i], i);
}
// If the set is full then need to
// perform lru i.e. remove the least
// recently used page and insert
// the current page
else
{
// Check if current page is not
// already present in the set
if (!s.Contains(pages[i]))
{
// Find the least recently used pages
// that is present in the set
int lru = int.MaxValue, val = int.MinValue;
foreach (int itr in s)
{
int temp = itr;
if (indexes[temp] < lru)
{
lru = indexes[temp];
val = temp;
}
}
// Remove the indexes page
s.Remove(val);
//remove lru from hashmap
indexes.Remove(val);
// insert the current page
s.Add(pages[i]);
// Increment page faults
page_faults++;
}
// Update the current page index
if(indexes.ContainsKey(pages[i]))
indexes[pages[i]] = i;
else
indexes.Add(pages[i], i);
}
}
return page_faults;
}
// Driver Code
public static void Main(String []args)
{
int []pages = {7, 0, 1, 2, 0, 3,
0, 4, 2, 3, 0, 3, 2};
int capacity = 4;
Console.WriteLine(pageFaults(pages,
pages.Length, capacity));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of above algorithm
// Method to find page faults using indexes
function pageFaults(pages,n,capacity)
{
// To represent set of current pages. We use
// an unordered_set so that we quickly check
// if a page is present in set or not
let s = new Set();
// To store least recently used indexes
// of pages.
let indexes = new Map();
// Start from initial page
let page_faults = 0;
for (let i=0; i<n; i++)
{
// Check if the set can hold more pages
if (s.size < capacity)
{
// Insert it into set if not present
// already which represents page fault
if (!s.has(pages[i]))
{
s.add(pages[i]);
// increment page fault
page_faults++;
}
// Store the recently used index of
// each page
indexes.set(pages[i], i);
}
// If the set is full then need to perform lru
// i.e. remove the least recently used page
// and insert the current page
else
{
// Check if current page is not already
// present in the set
if (!s.has(pages[i]))
{
// Find the least recently used pages
// that is present in the set
let lru = Number.MAX_VALUE, val=Number.MIN_VALUE;
for(let itr of s.values()) {
let temp = itr;
if (indexes.get(temp) < lru)
{
lru = indexes.get(temp);
val = temp;
}
}
// Remove the indexes page
s.delete(val);
//remove lru from hashmap
indexes.delete(val);
// insert the current page
s.add(pages[i]);
// Increment page faults
page_faults++;
}
// Update the current page index
indexes.set(pages[i], i);
}
}
return page_faults;
}
// Driver method
let pages=[7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2];
let capacity = 4;
document.write(pageFaults(pages, pages.length, capacity));
// This code is contributed by rag2127
</script>
Producción:
6
Otro enfoque: (sin usar HashMap)
C++
// C++ program for page replacement algorithms
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
int capacity = 4;
int arr[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};
deque<int> q(capacity);
int count=0;
int page_faults=0;
deque<int>::iterator itr;
q.clear();
for(int i:arr)
{
// Insert it into set if not present
// already which represents page fault
itr = find(q.begin(),q.end(),i);
if(!(itr != q.end()))
{
++page_faults;
// Check if the set can hold equal pages
if(q.size() == capacity)
{
q.erase(q.begin());
q.push_back(i);
}
else{
q.push_back(i);
}
}
else
{
// Remove the indexes page
q.erase(itr);
// insert the current page
q.push_back(i);
}
}
cout<<page_faults;
}
// This code is contributed by Akshit Saxena
Java
// Java program for page replacement algorithms
import java.util.ArrayList;
public class LRU {
// Driver method
public static void main(String[] args) {
int capacity = 4;
int arr[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};
// To represent set of current pages.We use
// an Arraylist
ArrayList<Integer> s=new ArrayList<>(capacity);
int count=0;
int page_faults=0;
for(int i:arr)
{
// Insert it into set if not present
// already which represents page fault
if(!s.contains(i))
{
// Check if the set can hold equal pages
if(s.size()==capacity)
{
s.remove(0);
s.add(capacity-1,i);
}
else
s.add(count,i);
// Increment page faults
page_faults++;
++count;
}
else
{
// Remove the indexes page
s.remove((Object)i);
// insert the current page
s.add(s.size(),i);
}
}
System.out.println(page_faults);
}
}
Python3
# Python3 program for page replacement algorithm
# Driver code
capacity = 4
processList = [ 7, 0, 1, 2, 0, 3, 0,
4, 2, 3, 0, 3, 2]
# List of current pages in Main Memory
s = []
pageFaults = 0
# pageHits = 0
for i in processList:
# If i is not present in currentPages list
if i not in s:
# Check if the list can hold equal pages
if(len(s) == capacity):
s.remove(s[0])
s.append(i)
else:
s.append(i)
# Increment Page faults
pageFaults +=1
# If page is already there in
# currentPages i.e in Main
else:
# Remove previous index of current page
s.remove(i)
# Now append it, at last index
s.append(i)
print("{}".format(pageFaults))
# This code is contributed by mahi_07
C#
// C# program for page replacement algorithms
using System;
using System.Collections.Generic;
class LRU
{
// Driver method
public static void Main(String[] args)
{
int capacity = 4;
int []arr = {7, 0, 1, 2, 0, 3, 0,
4, 2, 3, 0, 3, 2};
// To represent set of current pages.
// We use an Arraylist
List<int> s = new List<int>(capacity);
int count = 0;
int page_faults = 0;
foreach(int i in arr)
{
// Insert it into set if not present
// already which represents page fault
if(!s.Contains(i))
{
// Check if the set can hold equal pages
if(s.Count == capacity)
{
s.RemoveAt(0);
s.Insert(capacity - 1, i);
}
else
s.Insert(count, i);
// Increment page faults
page_faults++;
++count;
}
else
{
// Remove the indexes page
s.Remove(i);
// insert the current page
s.Insert(s.Count, i);
}
}
Console.WriteLine(page_faults);
}
}
// This code is contributed by Rajput-Ji
Producción:
6
Nota: También podemos encontrar el número de visitas a la página. Solo hay que mantener un conteo separado.
Si la página actual ya está en la memoria, debe contarse como página visitada.
Discutiremos otros algoritmos de reemplazo de página en conjuntos posteriores.
Este artículo es una contribución de Sahil Chhabra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA