FACTOID # 8: Bookworms: Vermont has the highest number of high school teachers per capita and third highest number of librarians per capita.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Page table
Relationship between pages addressed by virtual addresses and the frames in physical memory, within a simple address space scheme. Physical memory can contain pages belonging to many processes. Pages can be swapped to disk if used infrequently, or if physical memory is full. Not all pages are in physical memory, here.
Relationship between pages addressed by virtual addresses and the frames in physical memory, within a simple address space scheme. Physical memory can contain pages belonging to many processes. Pages can be swapped to disk if used infrequently, or if physical memory is full. Not all pages are in physical memory, here.

A page table is the data structure used by a virtual memory system in a computer operating system to store the mapping between virtual addresses and physical addresses. Virtual addresses are those unique to the accessing process. Physical addresses are those unique to the CPU, i.e., RAM. Image File history File links This is a lossless scalable vector image. ... Image File history File links This is a lossless scalable vector image. ... Virtual memory is an addressing scheme implemented in hardware and software that allows non-contiguous memory to be addressed as if it is contiguous. ... A BlueGene supercomputer cabinet. ... An operating system (OS) is a set of computer programs that manage the hardware and software resources of a computer. ... Virtual address In computer terminology a virtual address is an address not identifying a logical interface or device, but to a virtual (not physical) entity. ... In computer science, a physical address is the address presented to a computers main memory in a virtual memory system, in contrast to the virtual address which is the address generated by the CPU. Virtual addresses are translated into physical addresses by a memory management unit (abbreviated MMU). ... In computing, a process is an instance of a computer program that is being executed. ... Die of an Intel 80486DX2 microprocessor (actual size: 12×6. ... Random access memory (usually known by its acronym, RAM) is a type of magnetic storage data storage used in computers. ...

Contents

Role of memory in computer systems

A running program, be it a web browser on a PC or a Turing machine in an academic paper, is a process for transferring data between the physical world and a computer's memory, and then transforming the data in that memory. (In computer science, a program is a set of instructions, and a process is the process of a computer following those instructions.) The memory can be physically organized in many ways, e.g. a long paper tape, magnetic domains on a disk platter, or arrays of tiny capacitors on a microchip. During the 1950s, as computers became more complex, they were connected to many kinds of memory. Managing which memories were storing which bits of data became complicated, especially when multiple processes were running on the same machine at the same time. An example of a web browser (Internet Explorer), displaying the English Wikipedia main page. ... An artistic representation of a Turing Machine . ...


One useful simplification was the development of virtual memory. One program, the operating system, keeps track of the physical location of each piece of data, and moves data between physical locations to improve performance or ensure reliability. For each "user-level" program, the operating system fabricates a single, simplified virtual memory space. Processes running inside virtual memory do not have to move data between physical devices, and do not have to allocate and reallocate portions of the fixed amount of primary memory between them. They are free to use as much of their virtual memory as necessary without reference to other processes.


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 maps the program's text and data into the virtual address space, 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). GUI can refer to the following: GUI is short for graphical user interface, a term used to describe a type of interface in computing. ... The term Von Neumann machine has two seperate meanings. ... In computer science, a subroutine (function, method, procedure, or subprogram) is a portion of code within a larger program, which performs a specific task and is relatively independent of the remaining code. ... In computer science, a call stack is a special stack which stores information about the active subroutines of a computer program. ... A binary tree, a simple type of branching linked data structure. ...


Not all information is 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. In computing, a system call is the mechanism used by an application program to request service from the operating system. ... The title given to this article is incorrect due to technical limitations. ...


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. This article is about a unit of data measurement. ... In mathematics and computer science, hexadecimal, base-16, or simply hex, is a numeral system with a radix, or base, of 16, usually written using the symbols 0–9 and A–F, or a–f. ...


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 (232 − 1), giving us 4G (gigabytes) of memory to work with. This fact will become important later. A gigabyte (derived from the SI prefix giga-) is a unit of information or computer storage equal to one billion (short scale, meaning a thousand million) bytes. ...


Why virtual addressing

When a program is running, it needs to make use of some form of memory in order to store information. A program may store information such as a numerical variable used in a computation, or data such as customer information in an accounting application. 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), but relatively fast, such as RAM
  • secondary memory, which is non-volatile, but relatively slow; such as a hard disk.

Virtual addressing provides a separation between the physical memory and the addresses that a program accesses to load or store data. One of the common uses of this separation is to facilitate paging to disk, which allows an operating system to make efficient use of primary memory, by moving unused instructions and data into secondary memory and then re-allocating the physical memory to another process. When the original process references the virtual address where it expects its instructions or data to be, the operating system re-allocates physical primary memory (possibly having to move some additional primary memory to secondary memory), then moves these instructions and data back to this primary memory. If the operating system gets into a situation where it is constantly moving primary memory to secondary memory (and back) in order to support the set of applications, the system will perform poorly. This is known as thrashing. Look up RAM, Ram, ram in Wiktionary, the free dictionary. ... Typical hard drives of the mid-1990s. ... In computer operating systems, paging memory allocation, paging refers to the process of managing program access to virtual memory pages that do not currently reside in RAM. It is implemented as a task that resides in the kernel of the operating system and gains control when a page fault takes... An operating system (OS) is a set of computer programs that manage the hardware and software resources of a computer. ... Virtual address In computer terminology a virtual address is an address not identifying a logical interface or device, but to a virtual (not physical) entity. ... An operating system (OS) is a set of computer programs that manage the hardware and software resources of a computer. ... An operating system (OS) is a set of computer programs that manage the hardware and software resources of a computer. ... This page is a candidate to be moved to Wiktionary. ...


Virtual addressing provides many other benefits. One of the most important benefits of virtual addressing is that each process can write only to the physical memory for which the operating system has created page table entries. This prevents one process from overwriting another process's data. Other important benefits include providing the operating system the ability to detect references to invalid addresses (e.g. addresses with no underlying physical memory, writes on addresses that are mapped to read-only memory, etc.). To meet Wikipedias quality standards, this article or section may require cleanup. ... In computing, a process is an instance of a computer program that is being executed. ... It has been suggested that this article or section be merged with Primary storage. ... An operating system (OS) is a set of computer programs that manage the hardware and software resources of a computer. ... Rom is also the name of a toy and comic book character Rom (Spaceknight). ...


The combination of virtual addressing and two forms of backing storage (as described above) is often referred to as virtual memory, although this is somewhat of a misnomer. To meet Wikipedias quality standards, this article or section may require cleanup. ... Virtual memory is an addressing scheme implemented in hardware and software that allows non-contiguous memory to be addressed as if it is contiguous. ...


Virtual addressing

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 4GB. These addresses form what is called as the virtual address space. These addresses have no physical meaning - if we only have 16MB of memory, all addresses above 0x01000000 would be invalid. However, as mentioned, almost all programs do not use all 4GB 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. Virtual address space (abbreviated VAS) is a memory mapping mechanism available in modern operating systems such as OpenVMS, Unix, Linux, and Windows NT. Overview When you run an application on a 32-bit operating system (OS), the OS creates a new process for it. ... A megabyte is a unit of information or computer storage equal to exactly one million bytes. ...


The chunks as mentioned above are called special names. This 4GB 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, virtual address to page-frame mapping is cached in the TLB, which gains us a performance increase. A Translation Lookaside Buffer (TLB) is a cache in a CPU that is used to improve the speed of virtual address translation. ...


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.

In computer operating systems, paging memory allocation, paging refers to the process of managing program access to virtual memory pages that do not currently reside in RAM. It is implemented as a task that resides in the kernel of the operating system and gains control when a page fault takes...

Role of the page table

Actions taken upon a virtual to physical address translation. Each translation is restarted if a TLB miss occurs, so that the lookup can occur correctly through hardware.

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. Typical actions taken upon a virtual-physical address translation. ... Typical actions taken upon a virtual-physical address translation. ...


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 within the TLB (a TLB hit), the physical frame number is retrieved, the offset 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.


When the hardware is unable to find a physical frame for a virtual page, it will generate a processor interrupt called a page fault. Hardware architectures offer the chance for an interrupt handler to be installed by the operating system to deal with such page faults. 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. In computer storage technology, a page fault is an interrupt (or exception) to the software raised by the hardware, when a program accesses a page that is not mapped in physical memory. ...


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 evicted to secondary memory).

In the first case, the memory access is invalid, and the operating system must take some action to deal with the problem. On modern operating systems, it will send a segmentation fault to the offending program. 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. It has been suggested that Access violation be merged into this article or section. ...


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. In a computer operating system which utilises paging for virtual memory memory management, page replacement algorithms decide what pages to page out (swap out) when a page needs to be allocated. ...



Computer security: Although not intended by design, page tables may be manipulated by a rootkit in order to hide memory and/or software code on a computer. Such modifications are difficult to detect and allow a program to hide itself or remain undetected.

A root kit is a set of tools frequently used by an intruder after cracking a computer system. ...


Page table data

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


The frame table, 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. This might not be accurate information since anyone can make changes to it. 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 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 page number (VPN), the physical page number (not the physical address), some 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 optimized 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 for each entry in the table the VPN is provided to check if it is the searched entry or a collision. In computer science, a hash table is a data structure that speeds up searching for information by a particular aspect of that information, called a key. ...


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 in between . 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

Dr. Andrew Stuart Andy Tanenbaum (born 1944) is a professor of Computer Science at Vrije Universiteit, Amsterdam in the Netherlands. ...

See also

Virtual memory is an addressing scheme implemented in hardware and software that allows non-contiguous memory to be addressed as if it is contiguous. ... In computer operating systems, paging memory allocation, paging refers to the process of managing program access to virtual memory pages that do not currently reside in RAM. It is implemented as a task that resides in the kernel of the operating system and gains control when a page fault takes... In computer storage technology, a page fault is an interrupt (or exception) to the software raised by the hardware, when a program accesses a page that is not mapped in physical memory. ... Memory management is the act of managing computer memory. ... It has been suggested that Software pointer be merged into this article or section. ... This 68451 MMU could be used with the Motorola 68010 MMU, short for memory management unit or sometimes called paged memory management unit as PMMU, is a class of computer hardware components responsible for handling memory accesses requested by the CPU. Among the functions of such devices are the translation... In computer security, PaX is a patch for the Linux kernel that implements least privilege protections for memory pages. ... W^X (pronounced W xor X[1]) is the name of a security feature present in the OpenBSD operating system. ... Özalp Babaoğlu, son of former Turkish foreign officer Nazif Babaoğlu and his wife Şükran Babaoğlu, born in Ankara, Turkey, is a Turkish computer scientist. ...

External link


  Results from FactBites:
 
Page table - MediaWiki (429 words)
Then, page_latest is used to search the revision table for rev_id, and rev_text_id is obtained in the process.
Note: If you want to completely delete a page manually from the database, be sure to delete the entry for the page in the page table, and for all the page's revisions in the revision table, and all of the text rows corresponding only to the page in the text table.
This timestamp is updated whenever the page changes in a way requiring it to be re-rendered, invalidating caches.
Page table - Wikipedia, the free encyclopedia (2567 words)
A page table is the data structure used by a virtual memory system in a computer operating system to store the mapping between virtual addresses and physical addresses.
The page table is used for this purpose.
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).
  More results at FactBites »

 
 

COMMENTARY     

There are 1 more (non-authoritative) comments on this page

Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m