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. What are the three main activities of an operating system in regard to secondary-storage management? Answer: 1) Free-space management 2) Storage allocation 3) Disk

Give a brief introduction about the operation of your program and show that you understand the idea behind threads and mutual exclusion variable. Why do we need to use mutual exclu

Q. The RC 4000 system as well as other systems have defined a tree of processes (called a process tree) such that all the descendants of a process are given resources (objects) as

Evicting the most-recently used (MRU) page does very well on LRU's worst case. In general, however, MRU is a bad idea, since many programs exhibit temporal locality in their memory


why some companies do not pay sufficient attention to staff induction

1. Draw a schematic diagram of a CMOS inverter and explain its operation. 2. Draw schematic diagrams of CMOS NAND and NOR gates, and explain their operation. 3. Explain what

Page Fault Handling conditions like, where the copy on write bit of a page is set and that page is send by more than one process, the Kernel assign new page and copies the conten

Question 1 Explain (a) tightly coupled systems                               (b) Loosely coupled system Question 2 Describe the RPC model Question 3 Write a note o

SEGMENTATION HARDWARE An execution to map two-dimensional user-defined addresses into one-dimensional physical addresses. This mapping is affected by means of segment table. Ev