How did you select a page for paging(pageout)?

[nicesj]

Hello,

I found various algorithms for selecting a victim page. but I can't understand how they find it..from where?

1) I only have the page directory, page table. and each entry has not enough field to implement such algorithms..
then do I have to make extra data structure for each page frame?
for every page frames?

2) CLOCK algorithm says that the hardware will set an access bit, so it can find a page using that bit.
it means, CLOCK should to search every page in the page directory/page table whether it accessed or not,.
then, when it start to search that page frame??
in the page-fault ISR? or separated thread(maybe this is not possible..)?

3) LRU algorithm uses the linked list (am I right?) for every page frame..
and modify its linkage.
ok, here is same question..
does it make any extra data structure for every page frame and link each other? after linking them, everytime check the
access bit in a page descriptor? and modify the linkage of page list? "EVERYTIME SEARCH ALL PAGE?"


thank you..

[tantrikwizard]

Pages normally need to be swapped out within a page fault handler, not the timer handler. You can normally discard pages that haven't been accessed and aren't dirty. In most cases you can just drop these pages entirely. Dirty pages normally need to be swapped to disk. You got 3 available bits in both structures that can be used for whatever you want. There's not enough resolution in 3 bits to do a very good LRU algorithm but it can set a bit in the available field indicating that more information about the page is in another place.

[kop99]

1) I only have the page directory, page table. and each entry has not enough field to implement such algorithms..
then do I have to make extra data structure for each page frame?
for every page frames?

Yes, you do, for example linux kernel has struct "page" in 32 bytes.

3) LRU algorithm uses the linked list (am I right?) for every page frame..
and modify its linkage.
ok, here is same question..
does it make any extra data structure for every page frame and link each other? after linking them, everytime check the
access bit in a page descriptor? and modify the linkage of page list? "EVERYTIME SEARCH ALL PAGE?"

Hmm... As i said, if you wanna write good mmanager, you have to use page descriptor for every physical page frame. And that page descriptor maybe include lru field.

And the book "Understanding the Linux Kernel 3d edition" would ask for your three questions.