How does kernel know, which pages in the virtual address space correspond to a swapped out physical page frame? -

August 15, 2012

consider following situation: kernel has exhausted physical ram , needs swap out page. picks least used page frame , wants swap contents out disk , allocate frame process.

what bothers me page frame mapped to, speaking, several (identical) pages of several processes. kernel has somehow find of processes , mark page swapped out. how carry out?

thank you.

edit: illustrations question:

before swapping processes 1 , 2 had shared page 1, resided in physical memory frame 1:

enter image description here

now, memory in system exhausted , kernel allocates memory process 3 swapping out page 1 frame 1 , replacing page 2. in order that, has

1) find processes, referring page 1 (process 1 , process 2 in our case)

2) modify page table entries, setting "present" bit 0 , setting page 1 location in swap

enter image description here

so, don't get, how step 1 carried out. kernel couldn't iteratively looking every process's page tables in order find page table entry, pointing frame 1. there should kind of reverse mapping page frames page table entries.

the answer is:

"the significant , important change page table management introduction of reverse mapping (rmap). referring “rmap” deliberate common usage of “acronym” , should not confused -rmap tree developed rik van riel has many more alterations stock vm reverse mapping.

in single sentence, rmap grants ability locate ptes map particular page given struct page. in 2.4, way find ptes map shared page, such memory mapped shared library, linearaly search page tables belonging processes. far expensive , linux tries avoid problem using swap cache (see section 11.4). means many shared pages, linux may have swap out entire processes regardless of page age , usage patterns. 2.6 instead has pte chain associated every struct page may traversed remove page page tables reference it. way, pages in lru can swapped out in intelligent manner without resorting swapping entire processes."

from understanding linux memory management, "what's new in linux2.6"

linux:

when swap file used page table entry gets updated 1 marked invalid , holding information saved in swap file. is: index swap_info array , offset within swap_map.

example (an bit old) page table entry type (pte_t) on x86. of bits used flags:

bit         function _page_present   page resident in memory , not swapped out _page_protnone  page resident not accessable _page_rw        set if page may written _page_user      set if page accessible user space _page_dirty     set if page written _page_accessed  set if page accessed

^{table 3.1: page table entry protection , status bits}

in simple terms: process points page, page updated. processes are, in effect, updated. when physical page requested swapped in , processes well. point being page table entry not removed when memory swapped out.

you might find of useful: