Where is page table located?

Question

I've been studying about paging and page tables. I don't see to understand where page tables are located. In one of the answers from stack exchange(https://unix.stackexchange.com/questions/487052/where-is-page-table-stored-in-linux), it is said that page tables are in kernel address space, which is in virtual memory(from what I understood). However in lecture slides from University of Illinois(https://courses.engr.illinois.edu/cs241/sp2014/lecture/09-VirtualMemory_II_sol.pdf), page tables seem to be in RAM, which is physical memory. Can anyone tell me clearly where the page tables are stored?

Thank you in advance.

Corrective

Answer 1

The answer to this question is too broad, and I think it belongs to super-user stack exchange.

In x86 systems, page tables are structures used by the CPU, but they are too large to be hold in registers, so they are kept in RAM.

Any process has a memory map in which there is two big zones: user space and kernel space. Kernel space is the same space for all process. User space is private to that process. On 32 bit X86 based Linux systems, any logical address equal or greater than 0xC0000000 belongs to kernel. Below that address, it's user space.

The page table of the process is held in the kernel space. The kernel may have several page tables in RAM, but only one is the active page table. In x86 CPUs, it's the page table pointed by register CR3.

There is a more detailed explanation of how it works here: https://mcmap.net/q/823281/-is-kernel-space-mapped-into-user-space-on-linux-x86

Kantor

Thanks for the recommendation about asking it on super-user stack exchange. I still don't understand how the answer can be broad. If something is in physical memory, shoudln't it not be in virtual memory and vise versa? Do you mean that the only active page table is "held in the kernel space" and rest "are kept in memory"? – Corrective

The answer can be broad because each CPU and each OS deal with this in its own particular way. Therefore I have had to narrow my answer to the OS and CPU I know: Linux and x86. A different CPU may keep its page tables in a CPU located internal structure, for instance. – Kantor

Oh I get it now. Thank you. – Corrective

So CPU need to acces PCB at RAM on EVERY context switch?? If it is the case - it's must be super slow and counter intuitive. – Heppman

Answer 2

i think you have a problem about understanding the virtual and physical memory. as the name suggest the virtual memory is not real. the reason of the idea of virtual memory was that the process sees all the storage in a computer as the available memory. for example in a 64 bit system, a process might see 2^64 as the memory available to it and another process may see the same thing. so using the virtual memory every process would see a continuous memory available to it which might be so much bigger than the available memory on the system. all the addresses in the virtual memory then should be translated to the equivalent physical memory using something called page tables. pages are blocks of cells(addresses), for example lets say that the available memory(physical) in a system is 2 GB, and the pages or blocks of cells has been chosen as 4 KB, in this case in a 4 KB block or page 4096 different cells or addresses are available which we could address using 12 bits , since we have:

2^12 = 4096

if the overall memory is 2 GB, then it means we could have:

2GB/4KB = 524288

which means we could have 524288 different pages in the physical memory, now some of these pages are only assigned to the operating system code, which means only the os could have access to it, these are the codes and instructions of the operating system program which could help the execution of every other program. other pages are available for other processes.

now lets say we have an address like this in the virtual memory:

0x000075fe

first of all we said that we need 12 bits to tell the position of every address in the page itself since the page is 4 KB, this position is 5fe, what operating system or every other memory management tool does! is that it won't translate this OFFSET, the position of every address in the virtual page would be the same thing in the physical page, i think this is one of the main features which makes translation beneficial , now the rest of the address should be translated to the related page in the physical which is :

0x00007

for this , the page table should be looked, which as we said is just a table in the kernel memory, which is not accessible in the user space, for example is something like this:

---

0x00001 0x00004

0x00002 disk ----> means every these addresses are in the disk

0x00007 0x004fe

so the 0x00007 page should be translated to the 0x004fe and therefore the address of:

0x000075fe in the virtual memory would be translated to:

0x004fe5fe in the physical memory , which means this is an address in the page number 0x004fe and the position of 5feth - 1.(since we know the starting point is zero).

Cuttlebone