Cache aware memory allocation

Details Cache aware memory allocation Cache aware memory allocation

1999-06-22

2002-04-02

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Memory configuring

C711S129000, C711S153000, C711S159000, C711S173000, C711S202000

Reexamination Certificate

active

06366994

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to allocating memory in a computer system, and more particularly, to a methodology of allocating memory to increase the availability of frequently accessed pages in a cache of the computer system.
2. Description of the Related Art
Modem multiuser/multitasking computer systems run complex operating systems to accomplish concurrent execution of a myriad of user applications. Broadly speaking, an operating system may be defined as system software that schedules tasks for execution by one or more processing units in a computer system, allocates storage among various application programs, handles a system interface to the peripheral hardware, and presents a default interface to the user when no application program is running. Operating systems may also perform other functions. Some examples of operating systems include Sun Microsystems' SOLARIS operating system, AT&T's UNIX operating system, IBM's OS/2 operating system, Microsoft's WINDOWS and MS-DOS family of operating systems, Apple's MACINTOSH operating system, Novell's NETWARE operating system, and Digital Equipment Corporation's VMS operating system.
An operating system is generally responsible for allocating memory from a system memory to itself as well as applications to be executed by a computer system. A prior art system memory allocation scheme in a computer system is illustrated in FIG.
1
. As shown in
FIG. 1
, the operating system typically allocates a portion of system memory
100
to itself, shown as operating system
110
, and a portion of system memory
100
to applications, shown as applications
120
. An application program may be defined as a program that performs a specific function directly for the user. Word processing and spreadsheet software are common examples of application programs. The remainder of system memory
100
is shown as unallocated memory
130
. The unallocated memory
130
can be allocated by the operating system as the need arises. System memory
100
may be visualized as being divided into a number of memory blocks or pages. The operating system
110
and the applications
120
may require one or more memory pages depending on, among other things, the page size and the number of applications currently being executed.
During the execution of a program, such as an operating system or an application, a copy of a memory block or page allocated to the program may be loaded into a cache. As used herein, the term page can be defined to include a block of memory of any size that is store in a cache.
FIG. 1
, for example, indicates cache
105
storing memory page
150
a
at cache location
160
. Pages are typically mapped into designated cache locations according to their addresses. As shown in
FIG. 1
, for example, memory pages
150
a
,
150
b
,
150
c
, and
150
d
all map to cache location
160
.
Unfortunately, mapping multiple pages to a particular cache location often results in cache collisions. Cache collisions occur when one memory page replaces another memory page in a cache. In order to access the memory page that was originally in the cache, a system must re-access the memory page from system memory. Consequently, cache collisions can adversely affect system performance as additional time is generally needed to retrieve memory pages from system memory. As shown in
FIG. 1
, a cache collision can occur when the system accesses memory page
150
b
or
150
c
or when the system allocates memory page
150
d
. The system may attempt to store memory page
150
b
,
150
c
, or
150
d
into cache location
160
.
Cache collisions can occur with greater frequency when portions of memory allocated to different programs map to the same cache location. In
FIG. 1
, for example, collisions can occur between pages from the operating system
110
and applications
120
since memory pages
150
a
,
150
b
,
150
c
, or
150
d
map to the same cache location
160
. Thus, if an application that includes memory page
150
b
,
150
c
or
150
d
is executed, memory page
150
b
,
150
c
, or
150
d
would displace the operating system memory page
150
a
in cache
105
. Consequently, when the portion of the operating system that included memory page
150
a
is subsequently executed, memory page
150
a
would need to be accessed from system memory
100
instead of cache
105
.
Caches generally work more efficiently when frequently accessed pages are present in the cache for longer periods of time than infrequently accessed pages. However, when a memory page from one type of program displaces a memory page from another type of program, it can be difficult to maintain frequently accessed pages in the cache. Therefore, a method of increasing the availability of frequently accessed pages in a cache is needed.
SUMMARY OF THE INVENTION
The problems outlined above are in large part solved by an apparatus and method as described herein. Generally speaking, an apparatus and method for allocating a memory in a cache aware manner are provided. An operating system can be configured to partition a system memory into regions. The operating system can then allocate corresponding portions within each region to various programs that include the operating system and applications. The portions within each region of the system memory can map into designated portions of a cache. The size of a portion of memory allocated for a program can be determined according to the needs of the program.
The use of the apparatus and method for allocating a memory in a cache aware manner may provide performance advantages over other memory allocation methods. First, cache collisions between the operating system and applications can be reduced. Next, cache collisions between different applications can be reduced. Also, frequently accessed routines can be locked into the cache to insure a cache hit. Further, a system memory can be allocated in an efficient manner by tuning the size of memory allocated to a particular program. Still further, the system memory can be dynamically re-allocated to efficiently accommodate new programs and changing memory needs.
Broadly speaking, a computer system is contemplated. The computer system includes a processing unit, a system memory, a cache memory, and an operating system to manage execution of a plurality of applications using the processing unit, the system memory, and the cache memory. The operating system is configured to allocate a first portion of the system memory to a first program and a second portion of the system memory to the first program. The first portion of the system memory begins at a first address and the second portion of the system memory begins at a second address. A first portion of the first address equals a first portion of the second address.
Another computer system is also contemplated. The computer system includes a processing unit, a system memory, a cache memory, and an operating system to manage execution of a plurality of applications using the processing unit, the system memory, and the cache memory. The operating system is configured to partition the system memory into a plurality of regions. The operating system is configured to allocate a first portion of each of the plurality of regions to a first program. The operating system is configured to allocate a second portion of each of the plurality of regions to a second program. The first portion of each of the plurality of regions maps to a first portion of the cache memory. The second portion of each of the plurality of regions maps to second portion of the cache memory.
Next, a method is contemplated. The method includes partitioning a system memory into a plurality of regions, allocating a first portion of each of the plurality of regions to a first program, and allocating a second portion of each of the plurality of regions to a second program. The first portion of each of the plurality of regions maps to a first portion of a cache memory and the second portion of each of the plurality of regions maps to s

Affiliated with

Also associated with

Rating

Cache aware memory allocation does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2924498