Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1996-05-02
2002-07-30
Courtenay, III, St. John (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
Reexamination Certificate
active
06427162
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to the field of computer systems. In particular, the present invention relates to memory management subsystems.
2. Description of the Related Art
A major concern for operating systems is managing memory allocation to various processes in view of the restricted amount of physical memory residing in the computer hardware. Designers must determine where a process will be placed in the main memory and how memory is allocated to the process as the process is modified during its execution. One problem common to all operating systems is determining how to handle memory addressing when memory becomes sparse. To address this problem, numerous operating systems have adopted virtual memory addressing.
Virtual memory addressing allows a programmer and the compilation system to choose addresses that are convenient to work with, with rather than those forced by the hardware architecture. This allows the operating system to run a program that requires more than the space available in the physical memory. As a process runs, it references code and data by using virtual addresses that are transparently translated to physical addresses. In order to run, a program must reside in physical memory and it must have a real address for both its code and data. A translation mechanism is thus needed to convert virtual memory addresses to physical memory addresses at run time. To map a virtual address to a physical memory address, a mapping function is used. The mapping function takes a virtual address and converts it into a physical address by using a predetermined address mapping.
In a non-limiting illustrative example, a virtual address includes three parts: a virtual segment number
111
, a page number
112
, and an offset
113
within that page as shown in the forwarded page table scheme illustrated in
FIG. 1
a
. Virtual segment
111
, virtual page
112
, and offset
113
are converted to a physical page number (also referred to as the page frame number) and offset at run-time. Using a combination of software and hardware techniques, a virtual address is looked up in a segment table
130
and a page table
140
to generate a physical page number. The forwarded page table scheme
100
involves the translation of a virtual address
110
into a physical address
150
by successively accessing three distinct tables: a Context table
120
, a Segment table
130
and a Page table
140
. More specifically, the virtual address
110
is translated into the physical address
150
by first combining the contents of a processor register (i.e., Root Table pointer
115
), set up during initialization of a memory management unit (MMU) and information within a Context register
116
. The Context register
116
is a storage element (e.g., processor register) that stores information uniquely identifying processes that happen to possess the same virtual address. By combining the Root Table pointer
115
with the information of the Context register
116
, a pointer to an entry
121
of the Context table
120
is produced. This entry
121
is used as an index for accessing the contents of an entry
131
in the Segment table
130
. The entry
131
has its base address set by the contents of the Segment portion
111
of the virtual address
110
. Likewise, the contents of the entry
131
are used as an index for the Page table
140
, having a page portion
112
as its base address, in order to access the contents of a page entry
141
. The contents of the page entry
141
is combined with a page offset
113
of the virtual address
110
to form the physical address
150
.
Page tables, such as the ones shown in
FIG. 1
a
, are data structures which are usually held in physical memory. Each time a virtual address is referenced, it must be looked up in this table to yield its corresponding physical address. However, searching this table every time the operating system needs a virtual page could be very time-consuming. The tables shown in
FIG. 1
a
, in the alternative, can be more conveniently stored in an associative memory often built into a processor chip.
An increasing number of architectures provide virtual memory support through software managed translation look-aside buffers (TLB). This is mainly due to the advent of 64-bit address pages which requires huge amounts of physical memory to hold the address translation page tables. A software managed TLB
170
, shown in
FIG. 1
b
, is a small associative cache of the most recent virtual to physical address translations and is managed by the operating system. The TLB
170
includes a number of translation entries
172
which include a data portion
174
and a tag portion
176
. The tag portion
176
includes a virtual address and a process context identification (“Contex ID” )
178
which uniquely identifies a process. The data portion
174
includes a physical page number
180
and page attributes (e.g., protection, reference, modify, etc.)
187
. When a process references an address the processor looks up the virtual address in the TLB. If the virtual address is not found in the TLB, the execution of the currently running process is suspended and an exception is generated (fault or trap). An exception handler searches the page tables in the main memory to see if there is an entry corresponding to the virtual address that was not found in the cache associative memory. If one is found, then the translation information for this page is placed in the cache associative memory (TLB). The instruction that caused the TLB miss is then re-executed. The virtual address is thus looked up again in the TLB, but this time the virtual address is found in the TLB and is translated to the physical address which the processor can then access.
In Unix System V release 4, the address space of a process is divided into different sections called segments or regions. A segment is a continuous portion of the virtual address space. A segment provides a convenient method for allowing a process to share a portion of its address space with other processes. It also allows the operating system to protect the process
1
address space so that the process itself cannot alter it.
FIG. 2
shows a process address space
202
including text segment
204
, data segment
206
and stack segment
208
. The text segment typically contains the executable code (or machine instructions) for a process. Generally this segment is marked read-only so that a process cannot alter its own code, or have it altered by other processes. A text segment can be shared among many processes that execute the same code. For example, there may be many users running a specific program at the same time. The operating system will place the code for the specific program in a text segment that is shared amongst all the processes executing it.
The data segment
206
holds the data used and modified by a process during its execution. A data segment is usually marked for read and write. However, the data segment is never shared with other processes but rather it remains private. If this segment was shareable then a process might inadvertently alter the data of another process. Finally the process address space
202
includes the stack segment
208
which contains the process stack. The stack segment
208
is marked read and write, and similarly to the data segment is not shared with other processes.
The shareability of the text segment of the process address space
202
is a particularly useful feature in time sharing and database systems where a large number of users are concurrently executing the same program.
FIG. 3
illustrates two processes i and j,
303
respectively
304
having at least one segment
310
respectively
314
running the same program (object) included at the same location in the physical page
308
of physical memory
306
. Physical memory
306
which includes the common object stored at page
308
is typically accessed by retrieving the virtual address VA, corresponding to the common object and looking up a translation key
Blakely & Sokoloff, Taylor & Zafman
Courtenay III St. John
Lao S.
Sun Microsystems Inc.
LandOfFree
Separate code and data contexts: an architectural approach... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Separate code and data contexts: an architectural approach..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Separate code and data contexts: an architectural approach... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2818683