Explain the mapping scheme of virtual address to physical address?

Question

Also describe the page replacement and page allocation scheme in LINUX.

Answer 1

1. Virtual Addressing

Linux sees a virtual address as consisting of four fields: The directory- middle- page- and offset-field. Each process has a list called "global directory" which maps the directory-field to a "page middle directory". The directory-field indexes the entry in this directory, which in turn maps to another list called "page table", which when indexed by the value of the page-field, finally maps to a page in the physical memory. The offset field addresses the desired memory cell relative to the page location.

Why all the effort with triple indirection?, you may ask. The reason is, that the "page middle directories" and "page tables" are themselves memory pages, that need not to be kept in memory, unless they are actually needed.

2. Page Allocation

When a process requests memory, Linux allocates it the following way: It splits the total memory in halves, and splits one half again and one of that quarters again, and so on, until the chunk is just big enough to hold the amount the process requested. If a process relinquishes it's memory chunk, these may be rejoined with another chunk, if they were split before. This is called the "buddy algorithm."

3. Page Replacement

The Page Replacement Algorithm in Linux is a variant of the Clock Algorithm, e. g. it iterates repeatedly over the memory pages, like a clock hand iterating over the numbers on its face. In Linux, each memory page as an age variable which gets incremented when the page is used. When a page suitable for replacement is searched, the iteration starts, and decrements the age variables of the pages one after another, until it encounters one with age zero. This page is then replaced.