Virtual memory system and methods

Details Virtual memory system and methods Virtual memory system and methods

1998-07-14

2004-07-06

Lao, Sue (Department: 2126)

Electrical computers and digital processing systems: virtual mac

Task management or control

Process scheduling

Reexamination Certificate

active

06760909

ABSTRACT:

TECHNICAL FIELD
This invention relates to operating systems and to virtual memory management techniques within operating systems.
BACKGROUND OF THE INVENTION
Many modern computer systems run multiple concurrent tasks or processes, each with its own address space. It would be expensive to dedicate a full complement of memory to each task, especially since many tasks use only a small part of their address spaces. Rather, virtual memory is used to give each process the appearance of a full address space. This allows a program to run on what appears to be a large, contiguous, physical-memory address space, dedicated entirely to the program. In reality, however, the available physical memory in a virtual memory system is shared between multiple programs or processes. The memory that appears to be large and contiguous is actually smaller and fragmented between multiple programs. Each program accesses memory through virtual addresses, which are translated by special hardware or software to physical addresses.
Rather than attempting to maintain a mapping for each possible virtual address, virtual memory systems divide virtual and physical memory into blocks. In many systems, these blocks are fixed in size and referred to as pages. The addresses within an individual page all have identical upper-most bits. Thus, a memory address is the concatenation of a page number, corresponding to the upper bits of the address, and a page offset, corresponding to the lower bits of the address.
A data structure is typically maintained in physical memory to translate from virtual page numbers to physical page frames. This data structure usually takes the form of a page table. A page table is indexed by virtual page number, and it generally has a number of entries equal to the number of pages in the virtual address space.
Virtual-to-physical address translation can consume significant overhead, since every data access requires first accessing the page table to obtain a physical address and then accessing the data itself. To reduce address translation time, computers use a specialized hardware cache dedicated to translations. The cache is referred to as a translation lookaside buffer (TLB). A TLB typically has a small, fixed number of entries. It can be direct-mapped, set associative, or fully associative.
FIG. 1
shows a prior art example of a virtual memory system using a TLB and a page table. A process generates a virtual address
12
comprising a virtual page number and a page offset. The page number portion of the virtual address is used to index a TLB
14
Assuming that the TLB contains an entry corresponding to the virtual page number (a situation referred to as a TLB “hit”), the TLB produces a physical page number. The page offset portion of virtual address
12
is concatenated with the physical page number from the TLB, resulting in a full physical address for accessing physical memory
16
. If the correct entry is not present in TLB
14
(a situation referred to as a TLB “miss”), an initial reference is made to page table
18
to update TLB
14
.
A TLB miss thus initiates its own memory reference that could in many cases be the source of another TLB miss, creating the potential for an endless loop. To prevent this, the page table is typically stored in an “unmapped” portion of physical memory that is addressed directly by its physical addresses rather than by virtual addresses.
One disadvantage of this approach is that the page tables can consume large amounts of physical memory. Typically, each program requires its own page table, and each table has entries for every possible virtual page number. The page tables cannot typically be paged to secondary storage.
The requirement of locating the page tables in unmapped memory is a further disadvantage in virtual memory systems such as those described above. It is typically quite difficult or at least very inefficient to deal with dynamically allocated data structures in unmapped memory.
FIG. 2
shows an alternative prior art architecture that is described in Rashid,
Machine
-
Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures
, Proceedings of the Second International Conference on Architectural Support for Programming Languages and Operating Systems, Oct. 5-8, 1987, at 31. This architecture, identified in the article as the Mach architecture, has a microprocessor with a hardware TLB
20
similar or identical to the one described above. A virtual page address
22
is formed by the combination of a virtual page number and a page offset. The virtual page number is translated by TLB
20
into a physical page number and combined with the page offset to address physical memory
24
.
The Mach system does not have page tables as they are commonly known. Rather, TLB misses are resolved by a combination of a “pmap” data structure
26
and a plurality of address maps
28
. All of these data structures are located in the system's physical memory. Pmap
26
is located in unmapped portions of the physical memory. Address maps
28
are located in mapped portions of physical memory, and are therefore addressed by virtual addresses.
Pmap
26
is somewhat similar to a single page table. In contrast to a typical page table, however, the pmap does not keep track of all valid virtual-to-physical address mappings. Rather, many entries in pmap
26
can be replaced or flushed to make room for newer entries. Accordingly, the pmap can be much smaller than a page table.
Because the pmap does not keep track of all valid virtual-to-physical address mappings, it may not have a specified desired virtual-to-physical translation. If it does not, reference must be made to an appropriate one of the address maps
28
. Generally, each process or task has its own address map, which contains a complete description of that task's virtual address space. The Rashid article notes that an address map is a “doubly linked list of address map entries, each of which maps a contiguous range of virtual addresses onto a contiguous area of a memory object.”
A system such as shown in
FIG. 2
tends to use memory more efficiently than a system such as shown in FIG.
1
. One reason for this is that address maps
28
can be structured much more compactly than page tables. While page tables are referenced very often, in response to every TLB miss, address maps
28
are referenced much less frequently, only in response to misses in pmap
26
. Therefore, the structure of address maps
28
can sacrifice searching efficiency for compactness. Another advantage of the Mach system is that address maps
28
can be located in mapped memory which is easier to manage and allocate than unmapped memory. In contrast, conventional page tables must usually be located in unmapped memory.
However, some of these advantages are negated by measures that are taken in the Mach system to avoid recursion and deadlock. The possibility of recursion is illustrated in the flow chart of FIG.
3
. In response to a TLB miss, reference is made to the pmap in unmapped memory. In the case of a hit, the corresponding physical address is loaded into the TLB from pmap
26
, and the miss is resolved without any further activity. In the case of a miss, however, reference is made to an appropriate address map. These steps are illustrated by blocks
30
and
32
of FIG.
3
. The search through the address map is performed by kernel routines that are generally located in unmapped memory. However, the address maps are located in mapped memory and accessing them with virtual memory addresses could generate a new TLB miss. A TLB miss on an address map address is illustrated by the curved line from block
32
to block
30
. There is a significant chance that the virtual-to-physical address mapping for the address map address will not be present in the pmap, and it will then be necessary to continue back to execution block
32
. This circular execution might continue indefinitely.
To avoid this situation, referred to as recursion, certain entries in pmap
26
of the Mach system are considered per

Affiliated with

Also associated with

Rating

Virtual memory system and methods does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Virtual memory system and methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Virtual memory system and methods will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3186528