Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2001-04-24
2004-01-27
Nguyen, T. (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S133000, C711S141000, C711S155000, C711S160000, C711S156000
Reexamination Certificate
active
06684305
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to computer systems, and, more particularly, to multiprocessor systems wherein multiple processors implement virtual memory and access a shared memory.
2. Description of the Related Art
A typical computer system includes a memory hierarchy to obtain a relatively high level of performance at a relatively low cost. Instructions of several different software programs are typically stored on a relatively large but slow non-volatile storage unit (e.g., a disk drive unit). When a user selects one of the programs for execution, the instructions of the selected program are copied into a main memory, and a processor (e.g., a central processing unit or CPU) obtains the instructions of the selected program from the main memory. Well-known virtual memory management techniques allow the processor to access data structures larger in size than that of the main memory by storing only a portion of the data structures within the main memory at any given time. Remainders of the data structures are stored within the relatively large but slow non-volatile storage unit, and are copied into the main memory only when needed.
Virtual memory is typically implemented by dividing an address space of the processor into multiple blocks called page frames or “pages.” Only data corresponding to a portion of the pages is stored within the main memory at any given time. When the processor generates an address within a given page, and a copy of that page is not located within the main memory, the required page of data is copied from the relatively large but slow non-volatile storage unit into the main memory. In the process, another page of data may be copied from the main memory to the non-volatile storage unit to make room for the required page.
Popular processor architectures (e.g., the 80x86 or “x86” processor architecture) typically include specialized hardware elements to support implementation of virtual memory. For example, the x86 processor architecture includes specialized hardware elements to support a protected virtual address mode (i.e., a protected mode). Such processors produce virtual addresses, and implement virtual-to-physical address translation mechanisms to “map” the virtual addresses to physical addresses of memory locations in the main memory. The address translation mechanisms typically include one or more data structures (i.e., “page tables”) arranged to form a hierarchy. The page tables are typically stored in the main memory and are maintained by operating system software (i.e., an operating system). A highest-ordered page table (e.g., the x86 page directory) is always located within the main memory. Any additional page tables may be obtained from the storage unit and stored in the main memory as needed.
A base address of a memory page containing the highest-ordered page table (e.g., the x86 page directory) is typically stored in a register. The highest-ordered page table includes multiple entries. The entries may be base addresses of other page tables, or base addresses of pages including physical addresses corresponding to virtual addresses. Where multiple page tables are used to perform the virtual-to-physical address translation, entries of the highest-ordered page table are base addresses of other page tables. A virtual address produced by the processor is divided into multiple portions, and the portions are used as indexes into the page tables.
A lowest-ordered page table includes an entry storing a base address of the page including the physical address corresponding to the virtual address. The physical address is formed by adding a lowest-ordered or “offset” portion of the virtual address to the base address in the selected entry of the lowest-ordered page table.
The above described virtual-to-physical address translation mechanism requires accessing one or more page tables in main memory (i.e., page table “lookups” or “walks”). Such page table accesses require significant amounts of time, and negatively impact processor performance. Consequently, processors typically include a translation look-aside buffer (TLB) for storing the most recently used page table entries. TLB entries are typically maintained by the operating system. Inclusion of the TLB significantly increases processor performance.
It would be beneficial to extend the benefits of virtual memory to multiprocessor systems including multiple processors. Such multiprocessor systems may advantageously have a main memory shared by all of the processors. The ability of all processors to access instructions and data (i.e., “code”) stored in the shared main memory eliminates the need to copy code from one memory accessed exclusively by one processor to another memory accessed exclusively by another processor. Additionally, a portion of the shared main memory may be used for interprocess communication.
Several problems arise in multiprocessor systems implementing virtual memory and having a shared main memory. One problem is how to create and maintain virtual memory data structures (e.g., page tables), and how to coordinate transfers of pages between the main memory and one or more storage units. Another problem, referred to herein as the “TLB coherence problem,” arises when each of the multiple processors expectedly has its own performance-enhancing TLB. As described above, each page table entry corresponds to a different page in the shared main memory. When one of the processors replaces a page in the shared main memory with a page from the storage unit, TLB entries corresponding to the replaced page in the other processors become invalid. One or more of the other processors may use such invalid page table entries in their TLBs to perform virtual-to-physical address translations, thereby accessing wrong pages in memory, and possibly causing incorrect results to be produced and/or other errors in system operation.
Moreover, to further preclude page table accesses in main memory, write accesses to pages in main memory may be recorded in “dirty” bits stored in the TLBs rather than having to access dirty bits of the corresponding page table entries in the shared main memory. Not having visibility into the TLBs of the other processors, a processor replacing a page in the shared main memory may not know that one of the other processors had previously written to the replaced page, and thus may not write the replaced page back to storage. As a result, data in the replaced page may not be correct, possibly causing incorrect results to be produced and/or other errors in system operation.
The present invention is directed to a system which implements a method that may solve, or at least reduce, some or all of the aforementioned problems.
SUMMARY OF THE INVENTION
A computer system is presented including a first processor, a second processor in communication with the first processor, and a memory coupled to the first and second processors (i.e., a shared memory) and including multiple memory locations, and a storage device coupled to the first processor. The first and second processors implement virtual memory using the memory. The first processor maintains a first set of page tables and a second set of page tables in the memory, and uses the first set of page tables to access the memory locations within the memory. The second processor uses the second set of page tables, maintained by the first processor, to access the memory locations within the memory.
The first and second sets of page tables may include at least one page table. The first processor may use the first set of page tables to translate a virtual address generated within the first processor to a corresponding physical address of a memory location within the memory, and may use the physical address of the memory location to access the memory location. Similarly, the second processor may use the second set of page tables to translate a virtual address generated within the second processor to a corresponding physical address of a memory location within the memory, and may use the physica
Nguyen T.
Williams Morgan & Amerson
LandOfFree
Multiprocessor system implementing virtual memory using a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiprocessor system implementing virtual memory using a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiprocessor system implementing virtual memory using a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3225805