Requisito previo: algoritmos de reemplazo de página
Además de las políticas de reemplazo de página LRU, OPT y FIFO, también tenemos la política de reemplazo de página de segunda oportunidad/reloj. En la política de reemplazo de páginas de segunda oportunidad, las páginas candidatas para la eliminación se consideran en un asunto de turno rotativo, y no se reemplazará una página a la que se haya accedido entre consideraciones consecutivas. La página reemplazada es aquella que, al ser considerada en un asunto de turno rotativo, no ha sido accedida desde su última consideración.
Se puede implementar agregando un bit de «segunda oportunidad» a cada cuadro de memoria: cada vez que se considera el cuadro (debido a una referencia hecha a la página que contiene), este bit se establece en 1, lo que le da a la página una segunda oportunidad. , ya que cuando consideramos la página candidata para el reemplazo, reemplazamos la primera con este bit establecido en 0 (mientras ponemos a cero los bits de las otras páginas que vemos en el proceso). Por lo tanto, una página con el bit de «segunda oportunidad» establecido en 1 nunca se reemplaza durante la primera consideración y solo se reemplazará si todas las demás páginas también merecen una segunda oportunidad.
Ejemplo:
digamos que la string de referencia es 0 4 1 4 2 4 3 4 2 4 0 4 1 4 2 4 3 4 y tenemos 3 marcos. Veamos cómo procede el algoritmo rastreando el bit de segunda oportunidad y el puntero.
- Inicialmente, todos los marcos están vacíos, por lo que después de los primeros 3 pases se llenarán con {0, 4, 1} y la array de segunda oportunidad será {0, 0, 0} ya que todavía no se ha hecho referencia a ninguno. Además, el puntero volverá a 0.
- Pass-4: Frame={0, 4, 1}, second_chance = {0, 1, 0} [4 tendrán una segunda oportunidad], pointer = 0 (No es necesario actualizar la página, por lo que el candidato todavía está en la página del marco 0), pf = 3 (Sin aumento en el número de fallos de página).
- Pass-5: Frame={2, 4, 1}, second_chance= {0, 1, 0} [0 reemplazado; su bit de segunda oportunidad era 0, por lo que no tuvo una segunda oportunidad], puntero=1 (actualizado), pf=4
- Pass-6: Frame={2, 4, 1}, second_chance={0, 1, 0}, pointer=1, pf=4 (Sin cambios)
- Pass-7: Frame={2, 4, 3}, second_chance= {0, 0, 0} [4 sobrevivió pero su bit de segunda oportunidad se convirtió en 0], pointer=0 (ya que el elemento en el índice 2 finalmente fue reemplazado), pf =5
- Pass-8: Frame={2, 4, 3}, second_chance= {0, 1, 0} [4 referenciados nuevamente], pointer=0, pf=5
- Pass-9: Frame={2, 4, 3}, second_chance= {1, 1, 0} [2 referenciados nuevamente], pointer=0, pf=5
- Pass-10: Frame={2, 4, 3}, second_chance= {1, 1, 0}, pointer=0, pf=5 (sin cambios)
- Pass-11: Frame={2, 4, 0}, second_chance= {0, 0, 0}, pointer=0, pf=6 (2 y 4 tienen segundas oportunidades)
- Pass-12: Frame={2, 4, 0}, second_chance= {0, 1, 0}, pointer=0, pf=6 (4 volverán a tener una segunda oportunidad)
- Pass-13: Frame={1, 4, 0}, second_chance= {0, 1, 0}, puntero=1, pf=7 (puntero actualizado, pf actualizado)
- Página-14: Cuadro={1, 4, 0}, segunda_oportunidad= {0, 1, 0}, puntero=1, pf=7 (Sin cambios)
- Página-15: Frame={1, 4, 2}, second_chance= {0, 0, 0}, pointer=0, pf=8 (¡4 sobrevivieron nuevamente debido a la segunda oportunidad!)
- Página-16: Cuadro = {1, 4, 2}, segunda oportunidad = {0, 1, 0}, puntero = 0, pf = 8 (Se actualizó la segunda oportunidad)
- Página-17: Cuadro={3, 4, 2}, segunda_oportunidad= {0, 1, 0}, puntero=1, pf=9 (puntero, pf actualizado)
- Página-18: Cuadro={3, 4, 2}, segunda_oportunidad= {0, 1, 0}, puntero=1, pf=9 (Sin cambios)
En este ejemplo, el algoritmo de segunda oportunidad funciona tan bien como el método LRU, que es mucho más costoso de implementar en hardware.
Más ejemplos –
Input: 2 5 10 1 2 2 6 9 1 2 10 2 6 1 2 1 6 9 5 1 3 Output: 14 Input: 2 5 10 1 2 2 6 9 1 2 10 2 6 1 2 1 6 9 5 1 4 Output: 11
Algoritmo:
cree una array de marcos para rastrear las páginas actualmente en la memoria y otra array booleana second_chance para rastrear si se ha accedido a esa página desde su último reemplazo (es decir, si merece una segunda oportunidad o no) y un puntero variable para rastrear el objetivo para reemplazar.
- Comience a recorrer la array arr . Si la página ya existe, simplemente establezca su elemento correspondiente en second_chance en verdadero y regrese.
- Si la página no existe, verifique si el espacio al que apunta el puntero está vacío (lo que indica que el caché aún no está lleno); si es así, colocaremos el elemento allí y regresaremos; de lo contrario, recorreremos la array de uno en uno . one (utilizando cíclicamente el valor de pointer ), marcando todos los elementos second_chance correspondientes como falsos, hasta que encontremos uno que ya sea falso. Esa es la página más adecuada para el reemplazo, así que lo hacemos y regresamos.
- Finalmente, informamos el recuento de fallas de la página.
C++
// CPP program to find largest in an array
// without conditional/bitwise/ternary/ operators
// and without library functions.
#include<iostream>
#include<cstring>
#include<sstream>
using namespace std;
// If page found, updates the second chance bit to true
static bool findAndUpdate(int x,int arr[],
bool second_chance[],int frames)
{
int i;
for(i = 0; i < frames; i++)
{
if(arr[i] == x)
{
// Mark that the page deserves a second chance
second_chance[i] = true;
// Return 'true', that is there was a hit
// and so there's no need to replace any page
return true;
}
}
// Return 'false' so that a page for replacement is selected
// as he reuested page doesn't exist in memory
return false;
}
// Updates the page in memory and returns the pointer
static int replaceAndUpdate(int x,int arr[],
bool second_chance[],int frames,int pointer)
{
while(true)
{
// We found the page to replace
if(!second_chance[pointer])
{
// Replace with new page
arr[pointer] = x;
// Return updated pointer
return (pointer + 1) % frames;
}
// Mark it 'false' as it got one chance
// and will be replaced next time unless accessed again
second_chance[pointer] = false;
//Pointer is updated in round robin manner
pointer = (pointer + 1) % frames;
}
}
static void printHitsAndFaults(string reference_string,
int frames)
{
int pointer, i, l=0, x, pf;
//initially we consider frame 0 is to be replaced
pointer = 0;
//number of page faults
pf = 0;
// Create a array to hold page numbers
int arr[frames];
// No pages initially in frame,
// which is indicated by -1
memset(arr, -1, sizeof(arr));
// Create second chance array.
// Can also be a byte array for optimizing memory
bool second_chance[frames];
// Split the string into tokens,
// that is page numbers, based on space
string str[100];
string word = "";
for (auto x : reference_string)
{
if (x == ' ')
{
str[l]=word;
word = "";
l++;
}
else
{
word = word + x;
}
}
str[l] = word;
l++;
// l=the length of array
for(i = 0; i < l; i++)
{
x = stoi(str[i]);
// Finds if there exists a need to replace
// any page at all
if(!findAndUpdate(x,arr,second_chance,frames))
{
// Selects and updates a victim page
pointer = replaceAndUpdate(x,arr,
second_chance,frames,pointer);
// Update page faults
pf++;
}
}
cout << "Total page faults were " << pf << "\n";
}
// Driver code
int main()
{
string reference_string = "";
int frames = 0;
// Test 1:
reference_string = "0 4 1 4 2 4 3 4 2 4 0 4 1 4 2 4 3 4";
frames = 3;
// Output is 9
printHitsAndFaults(reference_string,frames);
// Test 2:
reference_string = "2 5 10 1 2 2 6 9 1 2 10 2 6 1 2 1 6 9 5 1";
frames = 4;
// Output is 11
printHitsAndFaults(reference_string,frames);
return 0;
}
// This code is contributed by NikhilRathor
Java
// Java program to find largest in an array
// without conditional/bitwise/ternary/ operators
// and without library functions.
import java.util.*;
import java.io.*;
class secondChance
{
public static void main(String args[])throws IOException
{
String reference_string = "";
int frames = 0;
//Test 1:
reference_string = "0 4 1 4 2 4 3 4 2 4 0 4 1 4 2 4 3 4";
frames = 3;
//Output is 9
printHitsAndFaults(reference_string,frames);
//Test 2:
reference_string = "2 5 10 1 2 2 6 9 1 2 10 2 6 1 2 1 6 9 5 1";
frames = 4;
//Output is 11
printHitsAndFaults(reference_string,frames);
}
//If page found, updates the second chance bit to true
static boolean findAndUpdate(int x,int arr[],
boolean second_chance[],int frames)
{
int i;
for(i = 0; i < frames; i++)
{
if(arr[i] == x)
{
//Mark that the page deserves a second chance
second_chance[i] = true;
//Return 'true', that is there was a hit
//and so there's no need to replace any page
return true;
}
}
//Return 'false' so that a page for replacement is selected
//as he reuested page doesn't exist in memory
return false;
}
//Updates the page in memory and returns the pointer
static int replaceAndUpdate(int x,int arr[],
boolean second_chance[],int frames,int pointer)
{
while(true)
{
//We found the page to replace
if(!second_chance[pointer])
{
//Replace with new page
arr[pointer] = x;
//Return updated pointer
return (pointer+1)%frames;
}
//Mark it 'false' as it got one chance
// and will be replaced next time unless accessed again
second_chance[pointer] = false;
//Pointer is updated in round robin manner
pointer = (pointer+1)%frames;
}
}
static void printHitsAndFaults(String reference_string,
int frames)
{
int pointer,i,l,x,pf;
//initially we consider frame 0 is to be replaced
pointer = 0;
//number of page faults
pf = 0;
//Create a array to hold page numbers
int arr[] = new int[frames];
//No pages initially in frame,
//which is indicated by -1
Arrays.fill(arr,-1);
//Create second chance array.
//Can also be a byte array for optimizing memory
boolean second_chance[] = new boolean[frames];
//Split the string into tokens,
//that is page numbers, based on space
String str[] = reference_string.split(" ");
//get the length of array
l = str.length;
for(i = 0; i<l; i++)
{
x = Integer.parseInt(str[i]);
//Finds if there exists a need to replace
//any page at all
if(!findAndUpdate(x,arr,second_chance,frames))
{
//Selects and updates a victim page
pointer = replaceAndUpdate(x,arr,
second_chance,frames,pointer);
//Update page faults
pf++;
}
}
System.out.println("Total page faults were "+pf);
}
}
Python3
# Python3 program to find largest in an array
# without conditional/bitwise/ternary/ operators
# and without library functions.
# If page found, updates the second chance bit to true
def findAndUpdate(x, arr, second_chance, frames):
for i in range(frames):
if arr[i] == x:
# Mark that the page deserves a second chance
second_chance[i] = True
# Return 'true', that is there was a hit
#and so there's no need to replace any page
return True
# Return 'false' so that a page
# for replacement is selected
# as he reuested page doesn't
# exist in memory
return False
# Updates the page in memory
# and returns the pointer
def replaceAndUpdate(x, arr, second_chance, frames, pointer):
while(True):
# We found the page to replace
if not second_chance[pointer]:
# Replace with new page
arr[pointer] = x
#Return updated pointer
return (pointer+1)%frames
# Mark it 'false' as it got one chance
# and will be replaced next time unless accessed again
second_chance[pointer] = False
# Pointer is updated in round robin manner
pointer = (pointer + 1) % frames
def printHitsAndFaults(reference_string, frames):
# initially we consider
# frame 0 is to be replaced
pointer = 0
# number of page faults
pf = 0
# Create a array to hold page numbers
arr = [0]*frames
# No pages initially in frame,
# which is indicated by -1
for s in range(frames):
arr[s] = -1
# Create second chance array.
# Can also be a byte array for optimizing memory
second_chance = [False]*frames
# Split the string into tokens,
# that is page numbers, based on space
Str = reference_string.split(' ')
# get the length of array
l = len(Str)
for i in range(l):
x = Str[i]
# Finds if there exists a need to replace
# any page at all
if not findAndUpdate(x,arr,second_chance,frames):
# Selects and updates a victim page
pointer = replaceAndUpdate(x,arr,second_chance,frames,pointer)
# Update page faults
pf += 1
print("Total page faults were", pf)
reference_string = ""
frames = 0
# Test 1:
reference_string = "0 4 1 4 2 4 3 4 2 4 0 4 1 4 2 4 3 4"
frames = 3
# Output is 9
printHitsAndFaults(reference_string,frames)
# Test 2:
reference_string = "2 5 10 1 2 2 6 9 1 2 10 2 6 1 2 1 6 9 5 1"
frames = 4
# Output is 11
printHitsAndFaults(reference_string,frames)
# This code is contributed by mukesh07.
C#
// C# program to find largest in an array
// without conditional/bitwise/ternary/ operators
// and without library functions.
using System;
public class secondChance
{
public static void Main()
{
String reference_string = "";
int frames = 0;
// Test 1:
reference_string = "0 4 1 4 2 4 3 4 2 4 0 4 1 4 2 4 3 4";
frames = 3;
// Output is 9
printHitsAndFaults(reference_string,frames);
// Test 2:
reference_string = "2 5 10 1 2 2 6 9 1 2 10 2 6 1 2 1 6 9 5 1";
frames = 4;
// Output is 11
printHitsAndFaults(reference_string,frames);
}
// If page found, updates the second chance bit to true
static bool findAndUpdate(int x,int []arr,
bool []second_chance,int frames)
{
int i;
for(i = 0; i < frames; i++)
{
if(arr[i] == x)
{
//Mark that the page deserves a second chance
second_chance[i] = true;
//Return 'true', that is there was a hit
//and so there's no need to replace any page
return true;
}
}
// Return 'false' so that a page
// for replacement is selected
// as he reuested page doesn't
// exist in memory
return false;
}
// Updates the page in memory
// and returns the pointer
static int replaceAndUpdate(int x,int []arr,
bool []second_chance,int frames,int pointer)
{
while(true)
{
//We found the page to replace
if(!second_chance[pointer])
{
//Replace with new page
arr[pointer] = x;
//Return updated pointer
return (pointer+1)%frames;
}
//Mark it 'false' as it got one chance
// and will be replaced next time unless accessed again
second_chance[pointer] = false;
//Pointer is updated in round robin manner
pointer = (pointer + 1) % frames;
}
}
static void printHitsAndFaults(String reference_string,
int frames)
{
int pointer, i, l, x, pf;
// initially we consider
// frame 0 is to be replaced
pointer = 0;
// number of page faults
pf = 0;
// Create a array to hold page numbers
int []arr = new int[frames];
// No pages initially in frame,
// which is indicated by -1
for(int s = 0;s<frames;s++)
arr[s]=-1;
//Create second chance array.
//Can also be a byte array for optimizing memory
bool []second_chance = new bool[frames];
//Split the string into tokens,
//that is page numbers, based on space
String []str = reference_string.Split();
//get the length of array
l = str.Length;
for(i = 0; i < l; i++)
{
x = int.Parse(str[i]);
//Finds if there exists a need to replace
//any page at all
if(!findAndUpdate(x,arr,second_chance,frames))
{
//Selects and updates a victim page
pointer = replaceAndUpdate(x,arr,
second_chance,frames,pointer);
//Update page faults
pf++;
}
}
Console.WriteLine("Total page faults were "+pf);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find largest in an array
// without conditional/bitwise/ternary/ operators
// and without library functions.
// If page found, updates the second chance bit to true
function findAndUpdate(x, arr, second_chance, frames)
{
let i;
for(i = 0; i < frames; i++)
{
if(arr[i] == x)
{
//Mark that the page deserves a second chance
second_chance[i] = true;
//Return 'true', that is there was a hit
//and so there's no need to replace any page
return true;
}
}
// Return 'false' so that a page
// for replacement is selected
// as he reuested page doesn't
// exist in memory
return false;
}
// Updates the page in memory
// and returns the pointer
function replaceAndUpdate(x, arr, second_chance, frames, pointer)
{
while(true)
{
//We found the page to replace
if(!second_chance[pointer])
{
//Replace with new page
arr[pointer] = x;
//Return updated pointer
return (pointer+1)%frames;
}
//Mark it 'false' as it got one chance
// and will be replaced next time unless accessed again
second_chance[pointer] = false;
//Pointer is updated in round robin manner
pointer = (pointer + 1) % frames;
}
}
function printHitsAndFaults(reference_string, frames)
{
let pointer, i, l, x, pf;
// initially we consider
// frame 0 is to be replaced
pointer = 0;
// number of page faults
pf = 0;
// Create a array to hold page numbers
let arr = new Array(frames);
arr.fill(0);
// No pages initially in frame,
// which is indicated by -1
for(let s = 0;s<frames;s++)
arr[s]=-1;
//Create second chance array.
//Can also be a byte array for optimizing memory
let second_chance = new Array(frames);
second_chance.fill(false);
//Split the string into tokens,
//that is page numbers, based on space
let str = reference_string.split(' ');
//get the length of array
l = str.length;
for(i = 0; i < l; i++)
{
x = str[i];
//Finds if there exists a need to replace
//any page at all
if(!findAndUpdate(x,arr,second_chance,frames))
{
//Selects and updates a victim page
pointer = replaceAndUpdate(x,arr,
second_chance,frames,pointer);
//Update page faults
pf++;
}
}
document.write("Total page faults were " + pf + "</br>");
}
let reference_string = "";
let frames = 0;
// Test 1:
reference_string = "0 4 1 4 2 4 3 4 2 4 0 4 1 4 2 4 3 4";
frames = 3;
// Output is 9
printHitsAndFaults(reference_string,frames);
// Test 2:
reference_string = "2 5 10 1 2 2 6 9 1 2 10 2 6 1 2 1 6 9 5 1";
frames = 4;
// Output is 11
printHitsAndFaults(reference_string,frames);
// This code is contributed by divyesh072019.
</script>
Producción:
Total page faults were 9 Total page faults were 11
Nota:
- Las arrays arr y second_chance se pueden reemplazar y combinar a través de un hashmap (con elemento como clave, verdadero/falso como valor) para acelerar la búsqueda.
- La complejidad temporal de este método es O(Número_de_fotogramas*longitud_de_la_string_de_referencia) u O(mn) pero dado que el número de fotogramas será una constante en un Sistema Operativo (ya que el tamaño de la memoria principal es fijo), es simplemente O(n) [Igual que hashmap enfoque, pero eso tendrá constantes más bajas]
- El algoritmo de segunda oportunidad puede sufrir la Anomalía de Belady .