NRU-page replacement algorithm

Question

I am trying to implement a NRU page replacement algorithm. The algorithm itself is as follows: Break all pages that are in physical memory into 4 classes:

класс 0: R-Bit = 0, M-Bit = 0 класс 1: R-Bit = 0, M-Bit = 1 класс 2: R-Bit = 1, M-Bit = 0 класс 3: R-Bit = 1, M-Bit = 1

After that you need to select the page RANDOM page from the lowest non-empty class. This is a snatch of my code. It works and replaces the pages with one drawback - it searches for the page of the minimum class (that is, the banal search for the minimum) and returns this page as a candidate for replacement. The problem is that this is not a random page.

 if ((processTable[pid].valid) && (processTable[pid].pageTable != NULL)) for (page = 0; page < processTable[pid].size; page++) { if (!isPagePresent(pid, page)) { continue; } else if (getPageClass(pid, page) <= minPageClass) { minPageClass = getPageClass(pid, page); pageToRemove = page; frame = processTable[pid].pageTable[page].frame; } }

My other idea was to create 4 data structures for each class (for example, an array) and a travel page for each class to add to the data structure, and then extract it from the data structure using random data. But it comes out too complicated code and it seems to me that there is a simpler way, how can I find a random page without resorting to using 4 data structures .... Ie. essentially there are:

 СТРАНИЦА КЛАСС 1 2 2 1 3 3 4 0 5 1 6 0

And of all these, only pages 4 and 6 are minimal and you need to return the random of these two.

I do not pretend to be true, but IMHO “random” in this context can be understood as “the first one that came across, but not the same every time.”
This is not a cryptography, where everything just keeps on it ... So you can just start a new search from the next page after what you found the previous time, or actually start from a random page.
If there are pages in memory with classes like {7, 0} (page 7, class 0) and {5, 0} (page 5, class 0).
Suppose the first page found will be unloaded from memory and a new one comes in its place.
This will work if the new page has a class higher than the previous one (for example, the following situation appears {1, 2} {7.0}).
Then at the next pass of the algorithm the page {1, 0} will be returned again.
I had a similar idea from the very beginning (which is essentially a search for a minimum).
in this example, the second will be superseded {7.0} since in the next search it will be the first.

Answer 1 · 2017-12-18T15:33:06

I do not pretend to be true, but IMHO “random” in this context can be understood as “the first one that came across, but not the same every time.” So you can just start a new search from the next page after it was found the previous time.

Pseudocode:

 int page = processTable[pid].last_swap_page + 1; int size = processTable[pid].size; int minPageClass = 9000 + 1; int stop_page = page ? page -1 : size - 1; for (page; page != stop_page && minPageClass != 0; page=(page+1)% size) { if (!isPagePresent(pid, page)) { continue; } else if (getPageClass(pid, page) < minPageClass) { // строгий поиск minPageClass = getPageClass(pid, page); pageToRemove = page; frame = processTable[pid].pageTable[page].frame; } } processTable[pid].last_swap_page = pageToRemove;

The diagram of the algorithm (5 physical / 8 real pages):

 Адрес/страницы &0| {1,2} {1,2} {1,2} {1,0} {1,2} {1,2} {1,2} &1| {2,0} 1 {6,2} 2 {6,2} 3 {6,0} 4 {6,0} 5 {2,2} 6 {2,2} &2| {3,3} ⇒ {3,3} ⇒ {3,3} ⇒ {3,1} ⇒ {3,1} ⇒ {3,1} ⇒ {9,2} &3| {4,2} {4,2} {7,2} {7,0} {7,3} {7,3} {7,3} &4| {5,3} {5,3} {5,3} {5,1} {5,3} {5,3} {5,3} 1) Надо загрузить {6}* | очевидно выбирается &1, запоминаем i=1 2) Надо загрузить {7} | начинаем поиск минимума с i:=i+1 == 2 выбираем &3 ({7,2}), запоминаем i=3 3) Сработал таймер | Сброс битов R 4) Чтение {1;5;7};запись {7} | 5) Загрузка 2 | начинаем поиск с i:=i+1 == 4, выбираем i=1 ({6,0}), запоминаем i=1 6) Загрузка 8 | начинаем поиск с i:=i+1 == 2, выбираем i=1 ({6,0}), запоминаем i=2

The new page is guaranteed to have the R flag set (not by its whim, the memory manager decided to load it), at least until the next reset.

for (int page; page != last_page && minPageClass != 0; page=(page+1)% size) instead of the last_page variable we mean the variable stop_page , right?
The value of 9000 + 1 is only a starting value for comparison and can be any, right?
of course;), a less cheerful value would be max_page_class + 1
1) if we start with a non-zero page, then we end with page -1 , and if with a zero, then the last one, size - 1 ;
2) Once the page has exceeded the size of the page pool, start counting from scratch.
For optimization, you can remove the modulo division by breaking into two cycles: from (page — size-1) and (0 — stop_page)

NRU-page replacement algorithm

1 answer 1

More articles: