Requisito previo: Anomalía de
Belady La Anomalía de Belady se produce cuando el número de errores de página aumenta incluso después de aumentar el número de fotogramas.
En este artículo, demostramos la anomalía de Belady usando el algoritmo de reemplazo de página FIFO.
Ejemplos:
Reference array is: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 Output : When number of frames is 3, page fault : 9 When number of frames is 4, page fault : 10 Reference array is: 0, 1, 5, 3, 0, 1, 4, 0, 1, 5, 3, 4 Output : When number of frames is 3, page fault : 9 When number of frames is 4, page fault : 10
Implementación:
el algoritmo de reemplazo de página FIFO se utiliza para mostrar la anomalía de Belady. En primer lugar, se utiliza una array de tamaño igual al número de marcos, esta array simula los marcos de la página, las operaciones en esta array se realizan de forma circular. Se usa una variable de conteo para calcular la falla de página, esta variable se incrementa cada vez que se inserta/reescribe un elemento en la array de marcos de página.
En este código:
se prueban dos tamaños de marco 3 y 4 respectivamente, con un aumento en el número de marcos, las fallas de página deberían haber disminuido, pero se observa una anomalía ya que 3 marcos dan como resultado 9 fallas de página, mientras que 4 marcos dan como resultado 10 fallas de página. Esta es la anomalía de Belady, se observa en casos especiales de array de referencia y tamaño de marco.
C++
#include <bits/stdc++.h>
using namespace std;
void pageFault(int frame_size, int* ref, int len)
{
// To dynamically allocate an array,
// it represents the page frames.
int* arr = new int[frame_size];
// To initialize the array
for (int i = 0; i < frame_size; i++) {
arr[i] = -1;
}
// To count page faults
int cnt = 0;
int start = 0;
int flag;
int elm;
for (int i = 0; i < len; i++) {
elm = ref[i];
// Linear search to find if the page exists
flag = 0;
for (int j = 0; j < frame_size; j++) {
if (elm == arr[j]) {
flag = 1;
break;
}
}
// If the page doesn't exist it is inserted,
// count is incremented
if (flag == 0) {
if (start < frame_size) {
arr[start] = elm;
start++;
}
else if (start == frame_size) {
arr[0] = elm;
start = 1;
}
cnt++;
}
}
cout << "When the number of frames are: " << frame_size << ", ";
cout << "the number of page faults is : " << cnt << endl;
}
int main()
{
// Reference array
int ref[] = { 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 };
int len = sizeof(ref) / sizeof(ref[0]);
// The frame size
int frame_size = 3;
pageFault(frame_size, ref, len);
// Increase value of frame size
frame_size = 4;
// The page fault increases
// even after increasing the
// the number of frames.
// This is Belady's Anomaly
pageFault(frame_size, ref, len);
}
Java
// Java Implementation of the above approach
class GFG
{
static void pageFault(int frame_size,
int []ref, int len)
{
// To dynamically allocate an array,
// it represents the page frames.
int []arr = new int[frame_size];
// To initialize the array
for (int i = 0; i < frame_size; i++)
{
arr[i] = -1;
}
// To count page faults
int cnt = 0;
int start = 0;
int flag;
int elm;
for (int i = 0; i < len; i++)
{
elm = ref[i];
// Linear search to find
// if the page exists
flag = 0;
for (int j = 0; j < frame_size; j++)
{
if (elm == arr[j])
{
flag = 1;
break;
}
}
// If the page doesn't exist it is inserted,
// count is incremented
if (flag == 0)
{
if (start < frame_size)
{
arr[start] = elm;
start++;
}
else if (start == frame_size)
{
arr[0] = elm;
start = 1;
}
cnt++;
}
}
System.out.print("When the number of frames are: " +
frame_size + ", ");
System.out.println("the number of page faults is : " + cnt);
}
// Driver Code
public static void main (String[] args)
{
// Reference array
int ref[] = { 1, 2, 3, 4, 1, 2,
5, 1, 2, 3, 4, 5 };
int len = ref.length;
// The frame size
int frame_size = 3;
pageFault(frame_size, ref, len);
// Increase value of frame size
frame_size = 4;
// The page fault increases
// even after increasing the
// the number of frames.
// This is Belady's Anomaly
pageFault(frame_size, ref, len);
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 Implementation of the above approach
def pageFault(frame_size, ref, len):
# To dynamically allocate an array,
# it represents the page frames.
arr = [0] * frame_size;
# To initialize the array
for i in range(frame_size):
arr[i] = -1;
# To count page faults
cnt = 0;
start = 0;
for i in range(len):
elm = ref[i];
# Linear search to find if the page exists
flag = 0;
for j in range(frame_size):
if (elm == arr[j]):
flag = 1;
break;
# If the page doesn't exist it is inserted,
# count is incremented
if (flag == 0):
if (start < frame_size):
arr[start] = elm;
start += 1;
elif (start == frame_size):
arr[0] = elm;
start = 1;
cnt += 1;
print("When the number of frames are: ",
frame_size, end = ", ");
print("the number of page faults is : ", cnt);
# Driver Code
# Reference array
ref = [1, 2, 3, 4, 1, 2,
5, 1, 2, 3, 4, 5 ];
len = len(ref);
# The frame size
frame_size = 3;
pageFault(frame_size, ref, len);
# Increase value of frame size
frame_size = 4;
# The page fault increases
# even after increasing the
# the number of frames.
# This is Belady's Anomaly
pageFault(frame_size, ref, len);
# This code is contributed by 29AjayKumar
C#
// C# Implementation of the above approach
using System;
class GFG
{
static void pageFault(int frame_size,
int []refer, int len)
{
// To dynamically allocate an array,
// it represents the page frames.
int []arr = new int[frame_size];
// To initialize the array
for (int i = 0; i < frame_size; i++)
{
arr[i] = -1;
}
// To count page faults
int cnt = 0;
int start = 0;
int flag;
int elm;
for (int i = 0; i < len; i++)
{
elm = refer[i];
// Linear search to find
// if the page exists
flag = 0;
for (int j = 0; j < frame_size; j++)
{
if (elm == arr[j])
{
flag = 1;
break;
}
}
// If the page doesn't exist it is inserted,
// count is incremented
if (flag == 0)
{
if (start < frame_size)
{
arr[start] = elm;
start++;
}
else if (start == frame_size)
{
arr[0] = elm;
start = 1;
}
cnt++;
}
}
Console.Write("When the number of frames are: " +
frame_size + ", ");
Console.WriteLine("the number of page " +
"faults is : " + cnt);
}
// Driver Code
public static void Main()
{
// Reference array
int []refer = { 1, 2, 3, 4, 1, 2,
5, 1, 2, 3, 4, 5 };
int len = refer.Length;
// The frame size
int frame_size = 3;
pageFault(frame_size, refer, len);
// Increase value of frame size
frame_size = 4;
// The page fault increases
// even after increasing the
// the number of frames.
// This is Belady's Anomaly
pageFault(frame_size, refer, len);
}
}
// This code is contributed by kanugargng
Javascript
<script>
// JavaScript Implementation of the above approach
function pageFault(frame_size, refer, len)
{
// To dynamically allocate an array,
// it represents the page frames.
let arr = new Array(frame_size);
// To initialize the array
for (let i = 0; i < frame_size; i++)
{
arr[i] = -1;
}
// To count page faults
let cnt = 0;
let start = 0;
let flag;
let elm;
for (let i = 0; i < len; i++)
{
elm = refer[i];
// Linear search to find
// if the page exists
flag = 0;
for (let j = 0; j < frame_size; j++)
{
if (elm == arr[j])
{
flag = 1;
break;
}
}
// If the page doesn't exist it is inserted,
// count is incremented
if (flag == 0)
{
if (start < frame_size)
{
arr[start] = elm;
start++;
}
else if (start == frame_size)
{
arr[0] = elm;
start = 1;
}
cnt++;
}
}
document.write("When the number of frames are: " +
frame_size + ", ");
document.write("the number of page " +
"faults is : " + cnt + "</br>");
}
// Reference array
let refer = [ 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 ];
let len = refer.length;
// The frame size
let frame_size = 3;
pageFault(frame_size, refer, len);
// Increase value of frame size
frame_size = 4;
// The page fault increases
// even after increasing the
// the number of frames.
// This is Belady's Anomaly
pageFault(frame_size, refer, len);
</script>
Producción:
When the number of frames are: 3, the number of page faults is : 9 When the number of frames are: 4, 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