Kesilapan halaman sekurang-kurangnya digunakan baru-baru ini (LRU)

Paging ialah proses pengurusan memori yang berkaitan dengan sistem pengendalian. Ia menyimpan atau mendapatkan semula beberapa data proses daripada storan data sekunder ke dalam storan atau ingatan data primer dengan menggunakan segmen halaman. Proses paging berlaku apabila proses menghadapi sebarang ralat pada halaman, di mana kami tidak dapat memenuhi proses peruntukan dengan halaman percuma baharu. Proses LRU menjana keperluan algoritma penggantian khusus. Apabila proses menjana halaman baharu, ia menentukan halaman mana yang perlu diganti. Mari kita ambil contoh -

Apa yang anda masukkan digunakan dalam proses ini -

N = 9, C = 4

Bentangkan halaman untuk proses = {5, 0, 1, 3, 2, 4, 1, 0, 5}

Hasil keluaran ialah: 8

Penjelasan -

Halaman ingatan yang diperuntukkan ialah 5, 0, 1, 3

Ralat berlaku semasa proses ini = 4

Memerlukan peruntukan memori, nilai ialah 2, gantikan LRU 5:

Ralat berlaku semasa proses ini = 4+1 = 5

Perlu memperuntukkan memori dengan nilai 4, gantikan LRU 0:

Ralat berlaku semasa proses ini = 5 + 1 = 6

Memori yang diperlukan dengan nilai 1 sudah wujud:

Ralat berlaku semasa proses ini = 6 + 0 = 6

Memori dengan nilai 0 perlu diperuntukkan untuk menggantikan 3 blok memori yang paling kurang digunakan baru-baru ini:

Ralat berlaku semasa proses ini = 6 + 1 = 7

Perlu memperuntukkan memori dengan nilai 5, yang akan menggantikan LRU 2:

Ralat berlaku semasa proses ini = 7 + 1 = 8.

Algoritma menilai kerosakan halaman dalam LRU

Algoritma LRU ialah proses penggantian yang disebut dalam bidang sistem pengendalian. Kapasiti ialah bilangan halaman yang disimpan dalam ingatan. Sekarang kita akan menetapkan koleksi halaman semasa dalam memori tertentu. Proses sentiasa meletakkan halaman paling kerap digunakan dalam nilai proses.

• Langkah 1 - Mulakan proses operasi LRU.

• Langkah 2 - Isytiharkan jumlah 0 di sini.

• Langkah 3 - Buat kelas vektor.

• Langkah 4 - Bina dan isytiharkan tatasusunan dengan saiz tatasusunan yang dikehendaki.

• Langkah 5 - Mulakan proses dengan kapasiti memori.

• Langkah 6 - Buat peta untuk kaedah ini.

• Langkah 7 - Simpan nilai kekerapan ke dalam peta halaman

• Langkah 8 - Lintas elemen halaman.

• Langkah 9 - Jika; elemen yang diperlukan wujud di lokasi penyimpanan asas, maka kita

Padamkannya dan tolaknya.

• Langkah 10 - Langkah 9 menambah proses kekerapan.

• Langkah 11 - Jika tidak, ingatan benar-benar penuh. Keluarkan elemen pertama dan kurangkan kekerapan.

• Langkah 12 - Kiraan bertambah.

• Langkah 13 - Bandingkan hasil kekerapan.

• Langkah 14 - Isih mengikut kekerapan halaman dan hasil berdasarkan masa.

• Langkah 15 - Jika kita mendapat kekerapan yang sama, maka halaman akan sampai dahulu.

• Langkah 16 - Ulangi proses.

• Langkah 17 - Kembalikan hasil.

• Langkah 18 - Matikan proses.

Sintaks untuk mengira kerosakan halaman dalam 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);		
   }
}

Dalam kemungkinan sintaks yang dinyatakan di atas, kami telah cuba menunjukkan cara yang mungkin untuk melaksanakan pengurusan kesalahan halaman LRU dalam dunia sistem pengendalian. Melalui sintaks persilangan ini, kami akan membina beberapa kod C++ untuk mentafsir dan menyelesaikan penyataan masalah dengan cara yang cekap.

Kaedah

• Kaedah 1 - Program C++ menunjukkan algoritma Paling Kurang Digunakan Baru-baru ini (LRU) dengan halaman yang disertakan untuk pengurusan memori dalam sistem pengendalian.

• Kaedah 2 - Menggunakan paging dengan algoritma LRU untuk fungsi pengindeksan dan cincang untuk mengurus memori dalam sistem pengendalian, program C++ digunakan untuk mencari kerosakan halaman.

Program C++ menunjukkan pengurusan memori dengan algoritma yang paling kurang digunakan (LRU) berkaitan halaman dalam sistem pengendalian

Algoritma LRU (Least Recently Used) ialah strategi dalam sistem pengendalian untuk menangani kerosakan halaman. Inilah prosesnya -

• Mula melayari halaman.

• Masukkan data ke dalam koleksi.

• Minta pemprosesan halaman.

• Teruskan berlaku pada masa yang sama.

• Indeks pengisytiharan.

• Peningkatan ralat halaman telah bermula.

• Cari halaman dalam koleksi.

• Ganti halaman yang ditemui dengan halaman semasa.

• Menambah gangguan.

• Kemas kini indeks

Contoh kod 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

Program C++ menggunakan pengindeksan dan halaman dengan algoritma LRU untuk mencari kesalahan halaman dengan menggunakan fungsi cincang untuk pengurusan memori dalam sistem pengendalian

Semasa penjejakan halaman, ralat halaman berlaku apabila kod cuba mengakses halaman memori yang tidak wujud dalam RAM atau tidak disenaraikan. Untuk menerangkan proses tersebut, kami akan mengikuti langkah-langkah yang dinyatakan di bawah.

• Ulang proses dan rujuk halaman.

• Padam semasa.

• Menambah ralat halaman.

• Tambah kandungan semasa pada halaman.

• Alih keluar yang pertama daripada halaman.

• Gunakan rentetan cincang.

• Mengembalikan bilangan klik halaman sebagai nombor

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

Atas ialah kandungan terperinci Kesilapan halaman sekurang-kurangnya digunakan baru-baru ini (LRU). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!