Multi-level page tables, Operating System

Multi-level page tables are tree-like structures to hold page tables. As an example, consider a two- level page table, again on a 32-bit architecture with 212 = 4 kbyte pages. Now, we can divide the virtual address into three parts: say 10 bits for the level-0 index, 10 bits for the level-1 index, and again 12 bits for the offset within a page.

The entries of the level-0 page table are pointers to a level-1 page table, and the entries of the level-1 page table are PTEs as described above in the single-level page table section. Note that on a 32-bit architecture, pointers are 4 bytes (32 bits), and PTEs are typically 4 bytes.

So, if we have one valid page in our process, now our two-level page table only consumes (210

level-0 entries)(22
bytes/entry)+1(210
level-1 entries)(22
bytes/entry) = 2212
bytes = 8 kbytes:

For processes with sparse virtual memory maps, this is clearly a huge savings, made possible by the additional layer of indirection.

Note that for a process which uses its full memory map, that this two-level page table would use slightly more memory than the single-level page table (4k+4M versus 4M). The worst-case memory usage, in terms of ef?ciency, is when all 210 level-1 page tables are required, but each one only has a single valid entry.

In practice, most page tables are 3-level or 4-level tables. The size of the indices for the different levels are optimized empirically by the hardware designers, then these sizes are permanently set in hardware for a given architecture.

Posted Date: 3/12/2013 5:40:03 AM | Location : United States







Related Discussions:- Multi-level page tables, Assignment Help, Ask Question on Multi-level page tables, Get Answer, Expert's Help, Multi-level page tables Discussions

Write discussion on Multi-level page tables
Your posts are moderated
Related Questions
Q. How is the NTFS namespace planned? Explain. Answer: The NTFS namespace is prearranged as a hierarchy of directories where every directory uses a B+ tree data structure to

The producer-consumermodel above has a standard human analogy of an assembly line. Humans have specialized skills, however, whereas threads running the same program do not need to

Making the Transition to Client - Server Programming Making the transition to client - server programming is a significant effort. Client - server applications must be designed

Q. Which of the subsequent instructions should be privileged? a) Read the clock b) Clear memory c) Set value of timer d) Issue a trap instruction e) Turn off interr

Q. Discuss the advantages as well as disadvantages of caching name translations for computers located in remote domains. Answer: There is a performance benefit to caching nam

CONTROL PROGRAMS Control Programs are those programs which control & maintain the operation of computer. They provide basic facilities. Control program are further divided into

What is starvation? A main problem related to deadlock is starvation. Starvation is the circumstances where process waits indefinitely within the semaphore. Indefinite blocking

Define Instance. An instance is an administrative unit in which components of R/3 systems giving one or more services are grouped together.  The services offered by a case are


Do you have writers that can use the software AIMMS version 3.9?