Operating system page placement to maximize cache data reuse

Details Operating system page placement to maximize cache data reuse Operating system page placement to maximize cache data reuse

1999-06-15

2002-06-18

Lane, Jack A. (Department: 2185)

Electrical computers and digital processing systems: memory

Storage accessing and control

Control technique

C711S163000

Reexamination Certificate

active

06408368

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to cache data management in a computer system, and more particularly to a software methodology to control replacement of one or more selected pages within a cache memory in the computer system.
2. Description of the Related Art
Modern multiuser/multitasking computer systems run complex operating systems to accomplish concurrent executions of myriad user applications. Broadly speaking, an operating system may be defined as a system software that schedules tasks for execution by one or more processing units in the computer system, allocates storage among various application programs, handles the system interface to the peripheral hardware, and presents a default interface to the user when no application program is running. Some examples of operating systems include the AT&T UNIX operating system; the IBM OS/2 operating system; the Microsoft Windows family of operating systems and MS-DOS; the Macintosh operating system; the Novell Netware; and the Digital Equipment Corporation's VMS operating system.
An operating system program may be divided into two parts: (1) the operating system kernel that contains the major operating system functions, such as the scheduler; and (2) various system programs which use facilities provided by the kernel to perform higher-level house-keeping tasks, such as providing an interface to various user application programs. An application program may be defined as a program that performs a specific function directly for the user (perhaps using one or more operating system services via the above mentioned interface). This is in contrast to system software, such as the operating system kernel, which supports the application programs. Word processing and spreadsheet software are common examples of popular application programs.
As used herein, the term “task” refers to a sequence of instructions arranged to perform a particular operation. Application software and the operating system may comprise one or more tasks.
In a typical multitasking operating system, memory management is usually employed for: (1) providing additional memory space when the physical memory space accessed by a processing unit is not large enough to hold all of the operating system and all of the application programs that are being executed by one or more users of the computer system; and (2) ensuring that executing tasks do not access protected areas of the physical system memory or those areas of the physical system memory allocated to other tasks. Generally, memory management may include allocating pages of physical memory for use by one or more tasks, mapping addresses generated by the tasks (“virtual addresses”) to the allocated physical pages (“physical addresses”) through an address translation mechanism, and deallocating pages released by a task.
A prior art system memory physical page allocation scheme is illustrated in FIG.
1
. The computer system physical memory or system memory
12
may be visualized as being divided into a number of memory blocks or pages. Normally, the operating system kernel routines and relevant data as well as various software routines forming portions of one or more application programs being simultaneously executed by the operating system reside in the system memory
12
, as respectively shown by the blocks numbered
11
and
13
. The operating system software routines (block
11
) and the application software (block
13
) may require more than one memory page depending, among other things, on the page size and on the number of applications currently being executed.
During a program execution, a copy of a memory page
141
(i.e., the memory page
14
) allocated to a program may be placed in the system cache memory
10
. If the system cache memory
10
has no allocable space, then the system cache memory
10
may “flush ” a corresponding page from the cache memory
10
to make space for the more recently accessed memory page
141
. The cached page
14
typically contains a plurality of cache lines (or blocks), and caching is typically performed on a block by block basis rather than a page by page basis. Accordingly, caching a page actually involves caching the multiple cache lines of a page. Caching improves the rate of program execution by providing faster access for the processing unit to read data from/write data into the cached page
14
in the cache memory
10
during the corresponding application program execution.
It is understood that the cache memory space
16
of the cache memory
10
is typically smaller than that of the system memory
12
. For example, when the cache memory space
16
is 1 MB in size and when the page size is 8 KB, the cache memory
10
may store up to
128
complete pages. However, the typical system memory physical space may be on the order of 64 MB, 80 MB, or even more. In that case, the system memory
12
may be visualized to contain 8192 or 10240 or more pages respectively. Further, it may not be desirable to increase the cache memory size
16
beyond a certain limit. In that event, the operating system may need to efficiently manage the resources of the cache memory
10
for a large number of applications that are currently under execution in the computer system.
When the user switches tasks or adds more applications for execution, the operating system may need to allocate one or more pages from the system memory
12
for the new tasks or applications. Under the prior art scheme of
FIG. 1
, the operating system uses a uniform method for allocating memory space, i.e., a request for a page of memory is allocated uniformly across the available memory space
20
according to any of the existing page allocation algorithms. This is illustrated in detail in FIG.
1
.
The allocable memory space
20
may be considered to comprise two sections: (1) memory pages that map to the same cache memory storage locations as the cached page
14
when placed in the cache memory
10
; and (2) the remaining memory pages,
15
-
1
through
15
-N+2 and further, in the allocable memory space
20
that do not map to the same cache memory storage locations as the cached page
14
. For the present discussion, the memory pages under (1) may be termed as conflict pages
18
and may be designated as conflict_page-
1
(
18
-
1
) through conflict_page-N+2 (
18
-N+2) and onwards. The number of conflict pages depends on the size of the allocable physical memory space and on the size of the cache memory
10
. In the previous example of the cache memory of 1MB size, the system memory of 80 MB can have a maximum of 79 conflict pages. The 80
th
“conflict page” would be the cached page
141
. In any event, the actual number of conflict pages may not be insubstantial. The memory pages under (2) may then be termed as non-conflict pages or free pages
15
(e.g., pages
15
-
1
through
15
-N+2 and further) for the present discussion.
Under the uniform method of allocation mentioned above, the operating system may simply allocate a conflict page, e.g., the conflict_page-
1
(
18
-
1
), after allocating the page
141
. The same method is repeated when the need to allocate an additional system memory page arises. In that event, the operating system may again allocate another conflict page, e.g., the conflict_page-
2
(
18
-
2
), after storing the conflict_page-
1
into the appropriate memory location, i.e., the memory location
18
-
1
. Unfortunately, allocating one or more conflict pages may cause the cached page
14
to be displaced from the cache memory
10
(when the conflict pages are accessed). Subsequent accesses to the page
141
may miss in the cache memory
10
, increasing memory latency for the task to which the page
141
is allocated.
The increased latency described above is particularly a problem in that some data and text (i.e., instruction sequences) are frequently accessed and thus heavily limit access latency when not present in the cache. For the present discussion, these data may be referred to as “critical data” and may include not o

Affiliated with

Also associated with

Rating

Operating system page placement to maximize cache data reuse does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Operating system page placement to maximize cache data reuse, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Operating system page placement to maximize cache data reuse will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2967832