Page faults in least recently used (LRU)

Paging is a memory management process related to the operating system. It stores or retrieves some process data from secondary data storage into primary data storage or memory by using page segments. The paging process happens when the process encounters any error on the page, where we cannot satisfy the allocation process with a new free page. The LRU process generates specific replacement algorithm requirements. When a process generates a new page, it determines which page needs to be replaced. Let us take an example -

The input is used for this process -

N = 9, C = 4

Present pages for the process = {5, 0, 1, 3, 2, 4, 1, 0, 5}

The output result is: 8

explain -

The allocated memory pages are 5, 0, 1, 3

Faults that occurred during this process = 4

Needs to allocate memory, value is 2, replace LRU 5:

Errors occurred during this process = 4 1 = 5

Need to allocate memory with value 4, replace LRU 0:

Errors occurred during this process = 5 1 = 6

The required memory with value 1 already exists:

Errors occurred during this process = 6 0 = 6

Need to allocate memory with a value of 0 to replace the 3 least recently used memory blocks:

Errors occurred during this process = 6 1 = 7

Need to allocate memory with value 5, this will replace LRU 2:

Errors occurred during this process = 7 1 = 8.

Algorithm Evaluates Page Faults in LRU

The LRU algorithm is a replacement process mentioned in the field of operating systems. Capacity is the number of pages held in memory. Now we will set the current collection of pages in a specific memory. The process always places the least frequently used pages in the process's value.

• Step 1 - Start the process of LRU operation.

• Step 2 - Declare the total to be 0 here.

• Step 3 - Create a vector class.

• Step 4 - Build and declare an array with the desired array size.

• Step 5 - Start the process with the memory capacity.

• Step 6 - Create a map for this method.

• Step 7 - Store the frequency value into the page's map

• Step 8 - Traverse the page elements.

• Step 9 - If; the required element exists in the base storage location, then we

Delete it and push it.

• Step 10 - Step 9 adds frequency to the process.

• Step 11 - Otherwise, the memory is completely full. Remove the first element and reduce the frequency.

• Step 12 - Count incremented.

• Step 13 - Compare frequency results.

• Step 14 - Sort by page frequency and time-based results.

• Step 15 - If we get the same frequency, then the page will arrive first.

• Step 16 - Repeat the process.

• Step 17 - Return results.

• Step 18 - Terminate the process.

Syntax for calculating page faults in LRU

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)
  {
    itr = find(q.begin(),q.end(),i);
    if(!(itr != q.end()))
    {
 
      ++page_faults;
      if(q.size() == capacity)
      {
        q.erase(q.begin());
        q.push_back(i);
      }
      else{
        q.push_back(i);
 
      }
    }
    else
    {
      q.erase(itr);
      q.push_back(i);        
    }
 
  }
  cout<<page_faults;
}
{
   int capacity = 4;
   int arr[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};
   ArrayList<Integer> s=new ArrayList<>(capacity);
   int count=0;
   int page_faults=0;
   for(int i:arr)
   {
      if(!s.contains(i))
      {
         if(s.size()==capacity)
         {
            s.remove(0);
            s.add(capacity-1,i);
         }
		 else
            s.add(count,i);
         page_faults++;
         ++count;
       } else {
         s.remove((Object)i);
         s.add(s.size(),i);		
   }
}

In the possible syntax mentioned above, we tried to show the possible ways to implement LRU page fault management in the operating system world. Through this intersectional syntax, we will build some C code to interpret and solve the problem statement in an efficient way.

method

• Method 1 - C program demonstrating the Least Recently Used (LRU) algorithm with accompanying pages for memory management in the operating system.

• Method 2 - Using paging with indexing and hash functions with LRU algorithm to manage memory in the operating system, C program is used to find page faults.

C program demonstrates memory management with the page-related least recently used (LRU) algorithm in the operating system

The LRU (least recently used) algorithm is a strategy in the operating system for handling page faults. Here is the process -

• Start traversing the page.

• Insert data into a collection.

• Request page processing.

• Keep happening at the same time.

• Declare index.

• The increment of page fault has started.

• Find the page in the collection.

• Replace the found page with the current page.

• Add fault.

• Update index

Sample code 1

//C++ program to demonstrate the Least Recently Used (LRU) Algorithm attached with the paging for memory management in Operating System
#include<iostream>
using namespace std;
int main ()
{
  int nopages, nofaults, page[20], i, count = 0;
  cout << "\n\t Enter no of pages for which you want to calculate page faults:>";
  cin >> nopages;
  //it will store the numer of Pages
  cout << "\n\t Enter the Reference String:";
  for (i = 0; i < nopages; i++)

    {
      cout << "\t"; cin >> page[i];
    }
  cout << "\n\t Enter the Number of frames:"; cin >> nofaults;
  int frame[nofaults], fcount[nofaults];
  for (i = 0; i < nofaults; i++)

    {
      frame[i] = -1;
      fcount[i] = 0;
    }
  i = 0;
  while (i < nopages)

    {
      int j = 0, flag = 0;
      while (j < nofaults)

	{
	  if (page[i] == frame[j])
	    {
	      flag = 1;
	      fcount[j] = i + 1;
	    }
	  j++;
	}
      j = 0;
      cout << "\n\t***\n";
      cout << "\t" << page[i] << "-->";
      if (flag == 0)

	{
	  int min = 0, k = 0;
	  while (k < nofaults - 1) { if (fcount[min] > fcount[k + 1])
		min = k + 1;
	      k++;
	    }
	  frame[min] = page[i];
	  fcount[min] = i + 1;
	  count++;
	  while (j < nofaults)

	    {
	      cout << "\t|" << frame[j] << "|";
	      j++;
	    }
	}
      i++;
    }
  cout << "\n\t***\n";
  cout << "\n\t Page Fault:" << count;
  return 0;
}

Output

 Enter no of pages for which you want to calculate page faults:>
	 Enter the Reference String:
	 Enter the Number of frames:
	***

	 Page Fault:0

C program using indexing and paging with LRU algorithm to find page faults by using hash functions for memory management in the operating system

During page tracking, a page fault occurs when code attempts to access a memory page that does not exist in RAM or is not listed. To explain the process, we will follow the steps mentioned below.

• Iterate the process and reference the page.

• Delete current.

• Increase page errors.

• Add the current content to the page.

• Remove the first one from the page.

• Use hashed strings.

• Return the number of page clicks as a number

示例代码2

//C++ program to find page faults by using indexes with LRU algorithm attached with the paging for memory management in Operating System using hashing function
#include<bits/stdc++.h>
using namespace std;
int pageFaults(int pages[], int n, int capacity)
{
	unordered_set<int> s;
	unordered_map<int, int> indexes;
	int page_faults = 0;
	for (int i=0; i<n; i++)
	{
		if (s.size() < capacity)
		{
			if (s.find(pages[i])==s.end())
			{
				s.insert(pages[i]);
				page_faults++;
			}
			indexes[pages[i]] = i;
		}
		else
		{
			if (s.find(pages[i]) == s.end())
			{
				int lru = INT_MAX, val;
				for (auto it=s.begin(); it!=s.end(); it++)
				{
					if (indexes[*it] < lru)
					{
						lru = indexes[*it];
						val = *it;
					}
				}
				s.erase(val);
				s.insert(pages[i]);
				page_faults++;
			}
			indexes[pages[i]] = i;
		}
	}

	return page_faults;
}
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;
}

输出

6

结论

最近最少使用（LRU）替换算法是一种特定的页面算法，我们可以使用它比任何其他算法更长的时间。该过程返回较少的页面错误，并能够完成页面分析。在本文中，我们学习了分页过程及其应用。通过使用上述提到的算法和语法，我们已经创建了一些代码以高效地解决问题陈述。

The above is the detailed content of Page faults in least recently used (LRU). For more information, please follow other related articles on the PHP Chinese website!