Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
1999-04-06
2002-12-17
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S152000, C711S207000, C711S210000, C710S200000
Reexamination Certificate
active
06496909
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to memory management in computer systems and, more particularly, to methods for managing concurrent access to virtual memory data if structures.
2. Description of the Related Art
Modern computer systems employ operating systems to manage the computer systems' resources and provide a foundation for application programs running on the computer systems. Some of the popular operating systems include DOS, Microsoft Windows®, Microsoft Windows NT®, Microsoft Windows 98™, UNIX, and LINUX™. The operating system provides a base for writing and running application programs thereby freeing programmers from the details of computer system hardware. In addition, the operating system manages processes, memory, file systems, I/O systems, and the like.
In an operating system, a process refers to a running program with input, output, and a state. For example, a process includes the current values of the program counter, the registers, and the variables of an executing program. Each process has a thread, which is associated with an address space. The thread is sometimes referred to as a lightweight process. Processes and threads are well known in the art and are described, for example, in Modern Operating Systems, Andrew S. Tannenbaum, (1992). Hence, running a process generally requires executing a thread by accessing the address space.
The operation of accessing an address space typically involves managing a memory system in the operating system. In particular, the operating system implements a virtual memory system to map a virtual address associated with a thread from a large virtual address space to a physical address of a physical memory, which is typically a RAM. A computer system is not limited to a single virtual address space. Indeed, it may implement as many virtual address spaces as its operating system is capable of supporting. For example, modern operating systems often support multiple processors and multiple threads of execution, thereby allowing the sharing of the system resources and further providing multiple concurrent processes and threads that execute simultaneously.
FIG. 1A
illustrates an exemplary conventional memory mapping method for mapping one or more virtual address spaces to a physical memory. A plurality of virtual address spaces
102
(VAS
0
),
104
(VAS
1
), and
106
(VASN) are provided. Each of the virtual address spaces
102
,
104
, and
106
is provided with a page table for mapping. Specifically, the virtual address spaces
102
,
104
, and
106
are associated with page tables
110
,
112
, and
114
, respectively. Each of the virtual address spaces has a plurality of virtual pages
116
. A physical memory
108
also includes a plurality of physical pages
118
. The virtual pages
116
and physical pages
118
are typically of same size and typically range from 4 kilobytes (KB) up to 16 KB. Nevertheless, computer systems may employ any suitable page size, which can be selected by the operating system based on supporting hardware.
In this configuration, pages in the virtual address spaces
102
,
104
, and
106
are mapped to pages in the physical memory
108
via page tables
110
,
112
, and
114
, respectively. For example, a virtual page
120
in the virtual address space
102
is mapped via page table
110
to physical page
126
. Likewise, a virtual page
122
in the virtual address space
104
is mapped to physical page
128
through page table
112
while virtual page
124
of the virtual address space
106
is mapped to physical page
130
via page table
114
. In those instances where a page is not present in the physical memory, a page fault is generated to load the page from a secondary storage device such as a hard drive, optical drive, tape drive, etc. Page mapping and page faults are well known in the art. It should be noted that page tables may be shared among several virtual address spaces. Indeed, even a portion of a page table may be shared among different address spaces.
A virtual address space, in abstract terms, is typically divided into a plurality of regions in accordance with data types.
FIG. 1B
shows a more detailed diagram of the exemplary virtual address space
102
. The virtual address space
102
is comprised of a plurality of regions
130
,
132
,
134
,
136
,
138
, and
140
. Each of the regions
130
through
140
is a contiguous region and the virtual pages within each region share common attributes. For example, the regions
130
,
134
, and
138
are empty regions that can be used to accommodate new data (e.g., files) from a secondary storage device or data from other contiguous regions
132
,
136
, and
140
. The code region
132
corresponds to the address space of codes (e.g., text in Unix) such as programs, instructions, and the like. On the other hand, the data region
136
includes a pair of sub-regions
142
and
144
that corresponds to address spaces of data and uninitialized data (e.g., HEAP), respectively. Likewise, the stack region
140
corresponds to the address space of a stack. The operating system maintains attributes such as the start address and the length of each region so that each region can be tracked accurately.
As mentioned above, the virtual pages in each region share common attributes. For example, the code region
132
may have an attribute specifying a file on a hard drive from which instructions can be fetched. The stack region
140
, on the other hand, usually grows dynamically and automatically downwards toward lower addresses and has an attribute that identifies it as a stack. Other common attributes include read and write attributes. For instance, the code region
132
is generally given an attribute of read only while data is associated with both read and write attributes. Other attributes also may be applied to any of the regions in a virtual address space.
In modern computer systems, operating systems generally allow multiple threads to execute virtually simultaneously in the virtual address space
102
. For example, UNIX and LINUX™ operating systems allow multiple threads to concurrently execute in a single virtual address space. In such instances, the threads may be performing an operation that affects the address space at once. For example, multiple threads on multiple CPUs could simultaneously perform page faults. Multiple threads may also execute a system call (e.g., MMAP in Unix) to map a file from a secondary storage device into the address space. To accommodate the new file, the operating system may create a region in one of the empty regions
130
,
134
, or
138
of the virtual address space
102
.
However, when multiple threads are attempting to access the same region in a virtual address space, a problem of contention arises. For example, if two threads are allowed to operate on the kernel data associated with the same virtual page in a region, the data may not be synchronized or updated properly. To address the contention problem, conventional techniques have used a “lock” to synchronize access by providing exclusive access to a thread such that other threads are not allowed to change the data accessed by the thread. In this manner, the lock ensures mutual exclusion of multiple threads for updates.
Conventional methods typically have provided a lock for each region in a virtual address space. The virtual memory system portion of the operating system generally maintains the regions of a virtual address space as a data structure, which is kept in a memory.
FIG. 1C
shows a simplified data structure
150
using locks
162
,
164
, and
166
to provide exclusive access to regions
152
,
154
, and
156
, respectively. The regions
152
,
154
, and
156
may correspond to a code region, data region, and stack region, respectively, and may be shared among different address spaces. It is noted that the word region is used herein in its most general form. In fact, it may actually be composed of multiple data structures within the kernel. The data structure
150
also includes an add
Anderson Matthew D.
Kim Matthew
Silicon Graphics Inc.
LandOfFree
Method for managing concurrent access to virtual memory data... 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 for managing concurrent access to virtual memory data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for managing concurrent access to virtual memory data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2987374