CODEWITHSUNDEEP
operating-systemvirtual-memorypage-tables
manissss
manissss

Reputation: 101

How do Multi-Level Page Tables Actually Save Space

I've been trying to do some research on why multi level page tables save space, and I think I'm a little confused on how a page table itself works. I found the following from Cornell:

The page table needs one entry per page. Assuming a 4GB (2^32 byte) virtual and physical address space and a page size of 4kB (2^12 bytes), we see that the the 2^32 byte address space must be split into 2^20 pages.

It is my understanding each process has its own page table. Does this mean that each process has 4GB of virtual address space? What is the point of the virtual address space being so huge? Why not allocate virtual pages as needed? Is it because the OS wants every possible address that can be made in the word size to map to a virtual page? Why not just prevent the program from dereferencing any virtual page number that is not a valid index for the page table?

I have read that one of the advantages of the multi-level page table is that it saves space by not having page table entries for virtual pages that are not in use. See below from Carnegie Mellon:

enter image description here

But why not just have a single level page table that has continuous entries - why would the process need PTE 1, 2, and then skip to 8? Why allow that? Even still, why do all the trailing, unused PTE's exist? Why not cut the page table short?

Upvotes: 0

Views: 4502

Answers (2)

thyu
thyu

Reputation: 1773

This saves memory (the word "space" is not specific enough) because the level 1 page table is much smaller when using two-level page tables instead of one. We can just keep level 1 page table in memory and paged out some level 2 page tables to disk.

Multi-level page tables

You can watch this YouTube video to learn about size of page table and multi-level page tables.

Upvotes: 0

Gabriel Ceron Viveros
Gabriel Ceron Viveros

Reputation: 41

Consider a system with a 32-bit logical address space. If the page size in such a system is 4 KB (2^12), then a page table may consist of over 1 million entries (2^20 = 2^32/2^12). Assuming that each entry consists of 4 bytes, each process may need up to 4 MB of physical address space for the page table alone.

Clearly, we would not want to allocate the page table contiguously in main memory. One simple solution to this problem is to divide the page table into smaller pieces. We can accomplish this division in several ways. One way is to use a two-level paging algorithm, in which the page table itself is also paged. For example, consider again the system with a 32-bit logical address space and a page size of 4 KB. A logical address is divided into a page number consisting of 20 bits and a page offset consisting of 12 bits. Because we page the page table, the page number is further divided into a 10-bit page number and a 10-bit page offset. Two-level paging

--Silberschatz A., Galvin P.B.

So for the case proposed above we would use 2^10 * 4B = 4KB for the outer page (p1) and only N * 2^10 * 4B= N * 4KB of inner page tables where N is the number of the needed pages for a process, which in total is less than the space needed for a non-leveled page table (4MB).

You should also notice that the process only occupies the number of pages and memory needed, and the maximum virtual address space determines the maximum addressable and thus occupiable memory for a process given a system configuration (32/64 bit address space).

Upvotes: 1

Related Questions