Programa para Algoritmos de Reemplazo de Páginas | Conjunto 2 (PEPS)

Requisito previo: Algoritmos de reemplazo de página En los sistemas operativos que usan paginación para la administración de la memoria, se necesita un algoritmo de reemplazo de página para decidir qué página debe reemplazarse cuando ingresa una nueva página. 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. 

Algoritmo de reemplazo de página First In First Out (FIFO) – 

// C++ implementation of FIFO page replacement
// in Operating Systems.
#include<bits/stdc++.h>
using namespace std;
 
// Function to find page faults using FIFO
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 the pages in FIFO manner
    queue<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())
            {
                // Insert the current page into the set
                s.insert(pages[i]);
 
                // increment page fault
                page_faults++;
 
                // Push the current page into the queue
                indexes.push(pages[i]);
            }
        }
 
        // If the set is full then need to perform FIFO
        // i.e. remove the first page of the queue from
        // set and queue both and insert the current page
        else
        {
            // Check if current page is not already
            // present in the set
            if (s.find(pages[i]) == s.end())
            {
                // Store the first page in the
                // queue to be used to find and
                // erase the page from the set
                int val = indexes.front();
                 
                // Pop the first page from the queue
                indexes.pop();
 
                // Remove the indexes page from the set
                s.erase(val);
 
                // insert the current page in the set
                s.insert(pages[i]);
 
                // push the current page into
                // the queue
                indexes.push(pages[i]);
 
                // Increment page faults
                page_faults++;
            }
        }
    }
 
    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 implementation of FIFO page replacement
// in Operating Systems.
 
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
 
 
class Test
{
    // Method to find page faults using FIFO
    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 the pages in FIFO manner
        Queue<Integer> indexes = new LinkedList<>() ;
      
        // 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++;
      
                    // Push the current page into the queue
                    indexes.add(pages[i]);
                }
            }
      
            // If the set is full then need to perform FIFO
            // i.e. remove the first page of the queue from
            // set and queue both and insert the current page
            else
            {
                // Check if current page is not already
                // present in the set
                if (!s.contains(pages[i]))
                {
                    //Pop the first page from the queue
                    int val = indexes.peek();
      
                    indexes.poll();
      
                    // Remove the indexes page
                    s.remove(val);
      
                    // insert the current page
                    s.add(pages[i]);
      
                    // push the current page into
                    // the queue
                    indexes.add(pages[i]);
      
                    // Increment page faults
                    page_faults++;
                }
            }
        }
      
        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

# Python3 implementation of FIFO page
# replacement in Operating Systems.
from queue import Queue
 
# Function to find page faults using FIFO
def 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
    s = set()
 
    # To store the pages in FIFO manner
    indexes = Queue()
 
    # Start from initial page
    page_faults = 0
    for i in range(n):
         
        # Check if the set can hold
        # more pages
        if (len(s) < capacity):
             
            # Insert it into set if not present
            # already which represents page fault
            if (pages[i] not in s):
                s.add(pages[i])
 
                # increment page fault
                page_faults += 1
 
                # Push the current page into
                # the queue
                indexes.put(pages[i])
 
        # If the set is full then need to perform FIFO
        # i.e. remove the first page of the queue from
        # set and queue both and insert the current page
        else:
             
            # Check if current page is not
            # already present in the set
            if (pages[i] not in s):
                 
                # Pop the first page from the queue
                val = indexes.queue[0]
 
                indexes.get()
 
                # Remove the indexes page
                s.remove(val)
 
                # insert the current page
                s.add(pages[i])
 
                # push the current page into
                # the queue
                indexes.put(pages[i])
 
                # Increment page faults
                page_faults += 1
 
    return page_faults
 
# Driver code
if __name__ == '__main__':
    pages = [7, 0, 1, 2, 0, 3, 0,
                4, 2, 3, 0, 3, 2]
    n = len(pages)
    capacity = 4
    print(pageFaults(pages, n, capacity))
 
# This code is contributed by PranchalK

// C# implementation of FIFO page replacement
// in Operating Systems.
using System;
using System.Collections;
using System.Collections.Generic;
 
class Test
{
    // Method to find page faults using FIFO
    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 the pages in FIFO manner
        Queue indexes = new Queue() ;
     
        // 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++;
     
                    // Push the current page into the queue
                    indexes.Enqueue(pages[i]);
                }
            }
     
            // If the set is full then need to perform FIFO
            // i.e. Remove the first page of the queue from
            // set and queue both and insert the current page
            else
            {
                // Check if current page is not already
                // present in the set
                if (!s.Contains(pages[i]))
                {
                    //Pop the first page from the queue
                    int val = (int)indexes.Peek();
     
                    indexes.Dequeue();
     
                    // Remove the indexes page
                    s.Remove(val);
     
                    // insert the current page
                    s.Add(pages[i]);
     
                    // push the current page into
                    // the queue
                    indexes.Enqueue(pages[i]);
     
                    // Increment page faults
                    page_faults++;
                }
            }
        }
     
        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;
        Console.Write(pageFaults(pages, pages.Length, capacity));
    }
}
 
// This code is contributed by Arnab Kundu