Page table

A page table is an integral part of a virtual memory system in a computer operating system. One role of the virtual memory system is to translate part virtual addresses, which assume that much more memory is available than is actually present, and physical addresses which matches a computer's main memory (ie., RAM). The virtual memory system must translate virtual addresses to physical addresses by storing these mappings in a page table.

Role of memory in computer systems

A program when it is running needs to make use of some form of memory in order to store information for several reasons, such as using information in computations, or storing necessary data such as customer information in an accounting application, and so on. Many computer architectures structure memory in the following manner:

• primary memory, which is volatile (meaning that the information is lost when the computer is turned off), and very fast, such as RAM
• secondary memory, which is non-volatile, however, is slower in comparison to primary memory, such as a hard disk.

If all memory accesses were to be through secondary memory, when a program would access memory, every access would slow down the running of the program (and fast response times are desirable in general purpose operating systems, since it is the program that manages key operation of a computer). If all memory accesses were to go through primary memory, everything would be faster, but all data would be lost when the computer is switched off, which is not desirable. Both forms of memory are used together (and in a virtual memory system, the link between primary and secondary memory is brought even tighter).

Primary memory usage

A program consists of two things (simplistically):

• "text", that is, the instructions a program uses to run
• data, for "hard-wired" information that a program needs, such as string constants, for example, the strings that are in a menu in a GUI program would be stored as string constants, and for other information that can be created and destroyed as a program runs.

When a program runs, the operating system loads the program's text and data into primary memory, and then executes the program's instruction in memory (see Von Neumann machine). However, when the program runs, it may need to store temporary data, or more importantly, when it calls another function (a basic block of functionality), it will need to save the state of the current function. For many purposes, this data is stored on a stack, since when a function finishes executing, the temporary data stored in that function is no longer needed - so naturally, the best form of data structure to use is a stack, since we merely "pop" off this temporary data. However, this means that the stack grows dynamically over a program's running. The operating system often splits up the text, data, and stack sections into separate regions, called segments, for security and reliability (so if the stack grows too large, attempting to overwrite the text or data segments, this can be more reliably detected).

Yet, all information is not stored on the stack. Say for example we have a word processor program. At the beginning, the block of memory that may be allocated to contain the text of the document may be small, but as the user enters more text, this block needs to grow. Using the stack for this purpose doesn't work, since the stack can only accommodate fixed-size blocks of memory. What is done is that the data segment of the program is made larger (see for example, the sbrk system call), so that the block of memory for your document can fit, and that as the need for more memory arises, the segment and the block grows (see for example, realloc). So the data segment grows and shrinks dynamically also.

Primary memory, however, is finite. This means that there are only a finite number of memory locations we can use to store data. In many modern computer architectures, these locations are indexed in a linear fashion, that is, there is some sense of position 0 at the beginning of the block of memory, with each following position increasing linearly to the end of memory. We call a "position" an address. So, if we have 16M (megabytes) of primary memory, we are able to access addresses 0 through to 16777215. In talking in a technical fashion about memory, we often use hexadecimal, that is, base-16 numbers to describe the address, so (using the C-style notation of prefixing with 0x to denote a hexadecimal address) in the previous example, we would have addresses 0x0 through to 0xFFFFFF.

Computer architectures are often described as "32-bit", "64-bit", and so on. This means that the largest number a 32-bit computer architecture can work with is 32-bits in size, etc. This number is the word size. This means, however, that the amount of physical memory a computer can work with is limited by the word size. So that means in a 32-bit computer the range of addressable address starts from 0 to 4294967295 (<math>2^{32}-1<math>), giving us 4G (gigabytes) of memory to work with. This fact will become important later.

Why virtual memory

As was mentioned above, primary memory is finite. So, in most modern operating systems, we want to multitask applications, that is, be able to run two or more programs at the same time. If we have say one program, with its text, data, and stack segments taking up 15M of physical memory, we won't be able to run a program that together takes up 2M of physical memory, since it won't fit into physical memory, and if the first program grows in size by 1M, there won't be any physical memory altogether.

This poses a problem. The method of virtual memory allows us to split up physical memory into chunks, and for the operating system (often with special computer hardware also) to manage these chunks as they are needed. Recall the example of the word processor. If the user is extensively working on the end of the document, the beginning of the document becomes somehow less important - we need a way of storing the memory comprising the beginning of the document somewhere else, and fetching it back later if need be. If the block of memory comprising the document is split into chunks, we could then take the first hundred or so chunks and put them into secondary memory, and then fetch them back if need be later.

However, this "swapping" capability is not enough, since there needs to be a way of managing these chunks with some structure, as having a random scattering of these chunks in physical memory becomes unworkable. What is done is that a program is fooled into thinking that it can use the entire 4G of memory that is possible to use (whether the computer actually has 4G of memory or not!). Whilst this may sound immediately impossible, the fact remains that a program is very unlikely to use the whole 4G of memory over its usage. So instead of just splitting up large parts of memory so they can be swapped around, all the memory is split up into chunks, so swapping can occur for any part of memory. This allows a greater amount of flexibility.

Virtual memory

Say we have a computer architecture where the word size is 32 bits. This means we are able to form addresses from 0x00000000 to 0xffffffff - spanning 4G. These addresses form what is called as the virtual address space'. These addresses have no physical meaning - if we only have 16M of memory, all addresses above 0x01000000 would be invalid. However, as mentioned, almost all programs do not use all 4G of memory when a program runs, but only parts of it at a time. For example, the text, data, and stack segments may only be used and together only take 1 megabyte in total over the time where it runs.

The chunks as mentioned above are called special names. This 4G virtual address space is split up into chunks, commonly 4K in size, called pages. The physical memory is also split up into chunks, also commonly 4K in size, called frames*. A program's text segment might start at the virtual address 0x00000004 - page number 0x0, and offset 0x4, but in reality, this may correspond to the physical address 0xff0e0004 - frame number 0xff0e, and offset 0x4. What the virtual memory system does is convert virtual addresses into physical addresses, essentially, mappings between pages and frames. The page table is used for this purpose.

Many architectures also have direct hardware support for virtual memory, providing what is known as a translation lookaside buffer (TLB), which is filled with page-frame mappings initially, and instead of having the virtual memory system entirely in software, when the hardware looks up a memory address and does the page-frame translation, which gains us a performance increase.

However, the TLB can only hold a fixed number of page-frame mappings. It is the job of the virtual memory system to extend this into software, and to hold extra page-frame mappings. The virtual memory system does so by means of a page table.

• Usage note: Some texts do not make a distinction between a "chunk" that is in physical or in virtual memory, using the term page for both, or the terms are page frame for a physical frame or a page for a virtual page. Other texts may use different terms.

Role of the page table

Say a program is running and it tries to access memory in the virtual address 0xd09fbabe. The virtual address is broken up into two: 0xd09f is the page number and 0xbabe is the offset, within the page 0xd09f.

With hardware support for virtual memory, the address is looked up within the TLB. The TLB is specifically designed to perform this lookup in parallel, so this process is extremely fast. If there is a match for page 0xd09f is found within the TLB (a TLB hit), the physical frame number is retrieved and the offset is replaced and the memory access can continue. However, if there is no match (called a TLB miss), the second port-of-call is the page table.

Hardware architectures can offer the chance for an interrupt handler to be installed so the TLB miss can be handled. The handler can look up the address mapping in the page table, and can see whether a mapping exists in the page table. If one exists, it is written back to the TLB, as the hardware accesses memory through the TLB in a virtual memory system, and the faulting instruction is restarted, with the consequence that the hardware will look in the TLB again, find the mapping, and the translation will succeed.

However, the page table lookup may not be successful for two reasons:

• there is no translation available for that address - the memory access to that virtual address is thus bad or invalid, or
• the page is not resident in physical memory (it is full).

In the first case, the memory access is invalid and the program is stopped and an error may be triggered (other operating systems may behave differently). In the second case, the page is normally stored elsewhere, such as on a disk. To handle this case, the page needs to be taken from disk and put into physical memory. When physical memory is not full, this is quite simple, one simply needs to write the page into physical memory, modify the entry in the page table to say that it is present in physical memory (see the next section), write the mapping into the TLB and restart the instruction.

However, when physical memory is full, and there are no free frames available, pages in physical memory may need to be swapped with the page that needs to be written to physical memory. The page table needs to be updated to mark that the pages that were previously in physical memory are no longer so, and to mark that the page that was on disk is no longer so also (and to of course write the mapping into the TLB and restart the instruction). This process of swapping pages between physical memory and disk is known sometimes as, obviously, swapping (though the term is sometimes used to describe swapping entire processes). This process however is extremely slow in comparison to memory access via the TLB or even the page table, which lies in physical memory. Which page to swap is the subject of page replacement algorithms.

Page table data

The simplest page table systems often maintain a frame table and a page table.

The frame table, which in the most basic system, holds information about which frames are mapped. In more advanced systems, the frame table can also hold information to which address space a page belongs, or statistics information, or other background information.

The page table holds the mapping between a virtual address of a page and the address of a physical frame. There is also auxiliary information about the page such as a present bit, a dirty or modified bit, address space or process ID information, amongst others.

Secondary storage, such as a hard disk, can be used to augment physical memory. Pages can be swapped in and out of physical memory and the disk. The present bit can indicate what pages are currently present in physical memory or are in disk, and can indicate how to treat these different pages, ie., whether to load a page from disk and swap another page in physical memory out, etc.

The dirty bit allows us a performance optimization. Say we have a page on disk that we swap in to physical memory. We can either write to this page, or we can just read from it. If we just read from it, and we need to replace this page with another, we don't need to write this page back to disk since the page hasn't changed (if we want to reload the page, we can just do so from disk again). However, if we did write to the page, we would raise the dirty flag, and this would mean we would need to write the page back so if we reload the page, we get the correct information back.

Address space or process ID information is necessary so the virtual memory management system knows what pages to associate to what process. Since the virtual memory map is the same for each process, between two processes, two identical virtual addresses could be used for different purposes, so the addresses must be somehow distinguished by identifying it with the process in the page table. This can be done by using a unique address space identifier, or by using process IDs.

Page table types

There are several different types of page table, that are best suited for different requirements. Essentially, a bare-bones page table must store the virtual address, the physical address that is "under" this virtual address, and possibly some address space information.

Inverted page table

The inverted page table (IPT) combines a page table and a frame table into the one data structure. At its core is a fixed-size table with the number of rows associating to each frame in memory. If there were 4000 free frames, the inverted page table has 4000 rows. For each row there is an entry for the virtual address, other data, and a means for creating a collision chain, as we will see later.

To search through all entries of the core IPT structure is tedious, so we use a hash table mapping virtual addresses (and address space/PID information if need be) to an index in the IPT - this is where the collision chain is used. This hash table is known as a hash anchor table. The hashing function is not generally optimised for coverage - raw speed is more desirable. Of course, hash tables experience collisions. Due to this chosen hashing function, we may experience a lot of collisions in usage, so a field is set up in the IPT to resolve collisions.

In searching for a mapping, the hash anchor table is used, and if no entry exists, a page fault occurs, otherwise, the entry is found and, depending on the architecture, is placed in the TLB again and the memory reference is restarted, or the collision chain is followed until it has been exhausted and a page fault occurs.

A virtual address in this schema could be split into two, the first half being a virtual page number and the second half being the offset in that page.

Multilevel page table

The inverted page table keeps a listing of mappings installed for all frames in physical memory. However, we could create a page table structure that contained mappings for virtual pages. However, this could be quite wasteful. What is done is to keep several page tables that cover a certain block of virtual memory, for example, smaller 1024-entry 4K pages covering 4M of virtual memory.

This is useful since often the top-most parts and bottom-most parts of virtual memory are used in running a process - the top is often used for text and data segments whilst the bottom for stack, with free memory inbetween . The multilevel page table may keep a few of the smaller page tables to cover just the top and bottom parts of memory and create new ones when only strictly necessary.

Now, each of these smaller page tables are linked together by a master page table, effectively creating a tree data structure. There need not only be two levels, but possibly multiple ones.

A virtual address in this schema could be split into three, the index in the root page table, the index in the sub-page table, and the offset in that page.

Virtualized page table

It was mentioned that creating a page table structure that contained mappings for every virtual page in the virtual address space could end up being wasteful. But, we can get around the excessive space concerns by putting the page table in virtual memory, and letting the virtual memory system manage the memory for the page table.

However, part of this linear page table structure must always stay resident in physical memory, in order to prevent against circular page faults, that look for a key part of the page table that is not present in the page table, which is not present in the page table, etc.

References

• Andrew S. Tanenbaum, Modern Operating Systems, ISBN 0130313580
• CNE Virtual Memory Tutorial, Center for the New Engineer George Mason University, Page Tables, http://cne.gmu.edu/modules/vm/purple/ptable.html
• Art of Assembler, 6.6 Virtual Memory, Protection, and Paging, http://webster.cs.ucr.edu/AoA/Windows/HTML/MemoryArchitecturea3.html

See also

• Virtual memory
• Paging
• Page fault
• Memory management

External link

• The Memory Management Reference (http://www.memorymanagement.org)
• Virtual memory lecture notes (http://www.cs.wisc.edu/~david/courses/cs354/cs354/karen.notes/vm.html)