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
What is meant by file management systems? File Management systems are as well referred to as simply a file system .File system is the system that an OS operating system or prog

Q. Researchers have recommended that instead of having an access list associated with each file (specifying which users can access the file and how) we should have a user control

Define UFD and MFD. In the two-level directory structure, every user has her own user file directory (UFD). Every UFD has a similar structure, but lists only the files of a one

How the Nested Macro calls are expanded LIFO (Last in First out)

Explain DosCreateThread Functions Used in the OS/2  DosCreateThread(&threadID,MyThreadFunction,arg,flags,stackSize) DosCreateThread creates a thread within the context of th

Q. Give an instance of an application in which data in a file should be accessed in the following order: a. Sequentially b. Randomly Answer: a. Print the content of

Define race condition. When various process access and manipulate similar data concurrently, then the outcome of the execution depends on certain order in which the access take

Processes have valid and invalid entries on their page tables. The valid entries all point to some where "real" (e.g. a physical page, or some portion of disk in case of non-reside

What is busy waiting? The repeated implementation of a loop of code while waiting for an event to happen is known as busy-waiting. The CPU is not engaged in any actual producti

How can the deadlock be prevented? To evade deadlocks first we will have to obtain the information about how resources are to be requested. And as well we should make sure that