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
Normal 0 false false false EN-US X-NONE X-NONE MicrosoftInternetExplorer4

Explain the various types of computer systems. Mainframe systems Large Number of CPU with Greatest Processing Power:  Huge Memory Capacity:  Increased Performance by s

There is a very small amount of networking background required for Project 2. In Project 2, we want our computer (or our "host") to request information over the Internet from a rem

Examining the write/cycles as shown below We can see that the bus is designed for asynchronous read/write cycles. The operation of the write cycle is simple in that the add

What is a general graph? A tree structure where links can go from one branch to a node earlier in the similar branch or other branch, allowing cycles.

What are the disadvantages of swapping technique used in pre-3BSD UNIX systems? If there is excessively much memory contention, processes are swapped out until sufficient

Many early operating systems regarded processes as different timesharing users. The process abstraction is a popular way to organize concurrent programs, but it is not the only cho

Q. Segmentation is alike to paging but uses variable-sized "pages". Describe two segment-replacement algorithms based on FIFO and LRU page replacement schemes. Remember that since

DIFFERENT MULTITHREADING MODELS Multithreading Models the majority multithreading models fall into one of the following categories of threading implementation: 1.      M

linked allocation using i node