Electrical computers and digital processing systems: memory – Address formation – Combining two or more values to create address
Reexamination Certificate
1999-10-31
2002-05-21
Nguyen, Hiep T. (Department: 2185)
Electrical computers and digital processing systems: memory
Address formation
Combining two or more values to create address
C711S203000, C711S216000, C711S206000, C711S221000, C711S202000
Reexamination Certificate
active
06393544
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to memory organization in computer systems. More specifically, the present invention relates to virtual memory systems having page tables that are accessed via a hash function.
DESCRIPTION OF THE RELATED ART
Conventional computer systems use a technique called virtual memory that simulates more logical memory than actually exists and allows the computer to run several programs concurrently regardless of their size. Concurrent user programs access main memory addresses via virtual addresses assigned by the operating system. The mapping of the virtual addresses to the physical addresses of the main memory is a process known as virtual address translation. Virtual address translation can be accomplished by any number of techniques, thereby allowing the processor to access the desired information in main memory.
The virtual address and physical address spaces are typically divided into equal size blocks of memory called pages, and a page table provides the translation between virtual addresses and physical addresses. Each page table entry typically contains the virtual address and/or the physical address, and protection and status information concerning the page. Status typically includes information about the type of accesses the page has undergone. For example, a dirty bit indicates there has been a modification to data in the page. Because the page tables are usually large, they are stored in memory. Therefore each regular memory access can actually require at least two accesses, one to obtain the translation and a second to access the physical memory location.
Many computer systems that support virtual address translation use a translation lookaside buffer (TLB). The TLB is typically a small, fast, associative memory which is usually situated on or in close proximity to the processor unit and stores recently used pairs of virtual and physical addresses. The TLB contains a subset of the translations in the page table and can be accessed much more quickly. When the processing unit needs information from main memory, it sends the virtual address to the TLB. The TLB accepts the virtual address page number and returns a physical page number. The physical page number is combined with low order address information to access the desired byte or word in main memory.
In most cases, the TLB cannot contain the entire page table, so procedures need to be implemented to update the TLB. When a virtual page is accessed, the translation for which is not in the TLB, the page table is accessed to determine the translation of this virtual page number to a physical page number, and this information is entered in the TLB. Access to the page table can take twenty times longer than access to the TLB, and therefore program execution speed is optimized by keeping the translations being utilized in the TLB.
Most computer systems today use some sort of mass storage, typically a disk, to augment the physical random access (RAM) memory in the computer. This augmentation of main memory enables larger programs to be implemented than if only main memory were available. In addition, disk memory is considerably less expensive than RAM, but is also orders of magnitude slower. Depending on the length of a program and the competition with other programs for main memory, part of a program may reside in main memory and part may reside on disk at any particular point in time. The parts of a program that need to be accessed immediately are brought into main memory while the parts not currently used are left on the disk.
For example, consider a single program that is two megabytes long and is executed on a computer having one megabyte of main memory. The program will require two megabytes of virtual address space. Since the main memory can only hold one megabyte, at most half of the program can reside in main memory at any given time and the remainder of the virtual address space is stored on the disk. Access to the information in main memory occurs normally. That is, the TLB is looked to first to see if it has the translation, and if not in the TLB, the TLB is updated using information from the page table and then the TLB is again referenced to get the desired translation information.
If access to the information that is not in the main memory occurs, then the TLB is accessed first for the translation, which will not be there. Then the page table is referenced to get the translation information to update the TLB. However the page table only has the translations for information in main memory, and therefore will not have the required translation information. This condition is called a page fault. In response to a page fault, a page fault handler finds a free physical page, loads the physical page with the required virtual page stored on the disk, and inserts the translation into a page table. If all physical pages have already been associated with other virtual pages, then the page fault handler needs to select which virtual pages currently stored in physical memory to swap out to the disk. There are many algorithms for performing this task, such as the first-in-first-out and least-recently-used algorithms. The page fault handler is typically implemented in software, while the TLB update process can be handled either by hardware or software, as is well known in the art.
FIG. 1
illustrates the process described above. In step
112
a virtual address is
1
presented to the TLB. If the translation for that virtual address is in the TLB (a TLB hit), then the associated physical address is derived from the TLB and is utilized to access physical memory (step
114
). If the translation for that virtual address is not in the TLB (a TLB miss), then the page table is accessed for the translation (step
116
). If the translation is in the page table, then this information is inserted in the TLB (step
118
) and the virtual address is again presented (step
112
). This time there will be a TLB hit so that the resulting physical address is used to access physical memory.
If the virtual address is in a page of virtual addresses for which no page of physical addresses is associated, then there will be no entry for this page in the page table and a page fault will occur. In this situation, a software page fault handler (step
120
) will assign a physical page to the virtual page, copy the page from disk to the physical page, and update the page table. Then the virtual address is again presented to the TLB. Since the TLB does not yet have the translation, there will be another TLB miss and the TLB will be updated from the page table. Thereafter, the virtual address is again presented to the TLB, and this time a TLB hit is assured and the resulting physical address is used to access physical memory.
FIG. 2
illustrates a simplified method of accessing an entry in a translation lookaside buffer (TLB) in response to the presentation of a virtual address. To simplify the example, the illustrated TLB has only one entry, whereas a TLB would normally have many more entries. The virtual address is loaded into a register
201
. This virtual address is composed of two parts a virtual page number
203
and a physical offset
205
. The physical offset corresponds to the page size. For a computer system having a page size of 4 kilobytes, the physical offset
205
is the lower 12 bits (bits
11
-
0
) of the address and specifies a particular byte within a page. The remaining bits in the register indicate the virtual page number. The term “page offset” is a term often used in the industry and is synonymous with the term “physical offset”. The virtual address may include other bits that are used in uniquely specifying a translation to a physical page number, such as “address space identifier” bits or “region identifier” bits.
For the example illustrated, the virtual page number becomes the virtual tag, which supplies one input for the TLB comparator
207
. A TLB
209
has two linked parts, a TLB tag
211
and an associated physical page number
213
. The TLB tag
211
supplies the second input to
Bryg William R.
Burger Stephen G.
Hammond Gary N.
Hays James O.
Huck Jerome C.
Institute for the Development of Emerging Architectures L.L.C.
Kim Hong
Nguyen Hiep T.
Plettue David A.
LandOfFree
Method and apparatus for calculating a page table index from... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for calculating a page table index from..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for calculating a page table index from... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2908528