Bedrock Computer Technologies, LLC v. Softlayer Technologies, Inc. et al

Filing 845

MOTION for Judgment as a Matter of Law Regarding Invalidity (Renewed) by Yahoo! Inc.. (Attachments: #1 Text of Proposed Order, #2 Exhibit 1 - Declaration of Alexey Kuznetsov - DX-48, #3 Exhibit 2 - Source Code - key.c - DX-37, #4 Exhibit 3 - U.S. Patent 5,121,495 - DX-65, #5 Exhibit 4 - Application Approval for Filing - DX-57, #6 Exhibit 5 - U. S. Patent 6,119,214 - DX101, #7 Exhibit 6 - U.S. Patent 4,996,663 - DX-64, #8 Exhibit 7 - Donald Knuth, Sorting and Searching, vol. 3, of The Art of Computer Programming - DX-98, #9 Exhibit 8 - Kruse, "Data Structures and Program Design" - DX-108, #10 Exhibit 9 - Daniel F. Stubbs and Neil W. Webre, Data Structures with Abstract Data Types and Pascal - DX-118, #11 Exhibit 10 - Kuznetsov email to Day re contact request - DX-436, #12 Exhibit 11 - Absher email to Kuznetsov re Linux route.c question - DX-440, #13 Exhibit 12 - Kuznetsov email to Absher re Linux route.c question - DX-441)(Doan, Jennifer)

Exhibit 5

111111111111111111111111111111111111111111111111111111111111111111111111111
US006119214A

United States Patent

[11]

Dirks
[54]

METHOD FOR ALLOCATION OF ADDRESS
SPACE IN A VIRTUAL MEMORY SYSTEM

[75]

Inveutor;

6,119,214
Sep.12,2000

Patent Number:

[45]

[19)

Date of Patent:

POlVer PC 601 RISC Microprocessor User's Manual,
Motorola, Inc., 1993, pp. 6-1 to 6-64.

Patrick W. Penzias Dirks, San Jose,
Calif.

Primary Examiner-Jack A. Lane
Attorney, Agent, or Firm-Ilurns, Doane, Swecker &
Mathis, L.L.P.

[73]

Assignee: Apple Computer, Inc., Cupertino,
Calif.

[21]

Appl. No.: 08/231,657

[22]

Filed:

[51]
[52]
[58]

Int. CI? ............................. G06F 12/10; G06F 12/12
U.S. CI ............................. 711/206; 711/159; 711/209
Field of Search ............................... 395/486,497.03,
395/412,419,497.01,497.02,600

[57]

A mernory manager for a virtual memory system maintains
three lists of virtual addresses: those which are free to be
mapped to a program, those which are currently mapped but
no longer being used, and those which are being removed
from a page table, i.e. unmapped. The allocation of free
addresses to programs proceeds in parallel with the removal
of old entries from the page table, such that new free
addresses are guaranteed to be available at all times. Each
time that a new address is allocated to a program, a limited
number of entries in the page table are examined, to determine whether the addresses associated with those entries are
no longer in use, and the entries can be removed from the
page tahle. By the time that all of the availahle addresses in
the free list have been allocated, the entire page table will
have been examined and all addresses which are no longer
in use will have had their correspondiug page table entries
removed, so that they are available as free addresses. As a
result, a constant supply of free addre&~es are provided with
only a linlited amouut of processing time at regular intervals
during the operation of a computer.

Apr. 25, 1994

[56]

References Cited
U.S. PATENT DOCUMENTS
4,577,274 3/1986 Ho et aJ. ................................. 395/415
4,967,353 10/1990 Brenner et al. ......................... 395/487
5,101,485 3/1992 Perazzoli, Jr. .. ........................ 395/416
5,109,336 4/1992 Guenther el al. .................. 395/497.02
5,125,086 6/1992 Pcrazzoli, Jr. .. ........................ 395/486
5,175,834 12/1992 Sawai ...................................... 395/478
5,'237,673 8/1993 Orbits et al. ....................... 395/497.01
5,269,109 12/1993 Abramson et al. ..................... 395/650
5,392,415 2/1995 Badovinatz et al. .................... 395/406

OlliER PUBLICATIONS
Beretvas, T., et ai, "Blocked Page-Out", IBM Technical
Disclosure Bulletin, vol. 26, No.9, Feb. 1984, pp.
4753-4754.

EFFECTIVE
ADDRESS
(32-BIT)

r sRI
I
20,--

VIRTUAL
ADDRESS
(52-BIT)

I VIRTUAL

SEGMENT
REGISTERS

I

SEGMENT /D, VSID, (24 BITS)

ABSTRACT

23 Claims, 7 Drawing Sheets

I PAGE INDEX (16 BITS) I BYTE OFFSET (12 BI7S)1
I

I

I

I PAGE INDEX (16 BITS) IBYTE OFFSET (12 BITS) I

I

I PTA

I

18,-,
PAGE TABLE

PHYSICAL
ADDRESS
(J2-BIT)

I PHYSICAL

1
PAGE NUMBER, PPN, 20 BITS

IBYTE OFFSET {12 BlTS)l
Defendants' Exhibit
Exhibit No. 101
Case No. 6:09-cv-00269-LED

DEF00000797

u.s. Patent

Sep.12,2000

~Wi~sl'---.. . . . .

~I I I I L.I. I. .-Il

111111..u...u..u.LIIIIIII..L.L.I.J.I,.I,1111111

t

6,119,214

Sheet 1 of 7

_-----I

j

RLEA

FIG. 1

EFFECTIVE
ADDRESS

PHYSICAL

VIRTUAL

ADDRESS

ADDRESS
14

10
18
12

1---eI

PAGE TABLE

I---~

16

FIG. 2

DEF00000798

d

•
rJJ.
•

EFFECTIVE
ADDRESS
(32-BIT)

I SRI I PAGE INDEX (16 BITS) IBYTE OFFSET (12 BITS) I
I
2Ol.-

SEGMENT
REGISTERS

I

I
I

I

~

~
.....
.....
=
~

'JJ
~

'?
.....
~N

N

VIRTUAL
ADDRESS
(52-BIT)

IVIRTUAL

SEGMENT ID, VSID, (24 BITS)

I PAGE INDEX (16 BITS) IBYTE OFFSET (12 BITS) I

l

g
o

I
'JJ

=-

PTA

~

....
~

18\...-;-

N

....

o

PAGE TABLE

o

m
"'Tl

o
o
o
o
o
......
<D
<D

PHYSICAL
ADDRESS
(32-BIT)

I PHYSICAL PAGE NUMBER,
FIG. 3

PPN, 20 BITS

-...J

IBYTE OFFSET (12 Bf~

0"\

'"
~
~

\C

N
~
~

u.s. Patent

Sep.12,2000

Sheet 3 of 7

6,119,214

FIG. 4

CREATE
THREAD

DELETE
THREAD

26

22

FIG. 5
DEF00000800

u.s.

Patent

Sep.12,2000

Sheet 4 of 7

REQUEST FOR

6,119,214

10

ADDRESS
NO

18

RETURN
FAILURE

NO

YES

22
32

26

30

SWEEP
PTk{n-1)

TO
PTk(n)-1

36

L - - -_ _ _ _

~

NO

TRANSFER
RECYCLE

38

TO FREE

24

FIG. 6
DEF00000801

u.s.

Patent

Sep.12,2000

Sheet 5 of 7

REQUEST FOR

6,119,214

10

ADDRESS
NO

18

RETURN
FAILURE

NO
22

32
28
SWEEP
PTk{n-1)
TO
PTk{n)-1

38

36

'---------.1

FIG. 7

NO

24

DEF00000802

u.s. Patent

Sep.12,2000

Sheet 6 of 7

6,119,214

REMOVE
ENTRY

MOVE
TO
PRIMARY

54

FIG. 8

DEF00000803

u.s. Patent

Sep. 12, 2000

Sheet 7 of 7

VSID 1

00

VSID 2

00

VSID J

01

VSID 4

10

VSID 5

10

VSID 6

6,119,214

01

VSID n-1 00
VSID n

00

FIG. 9
DEF00000804

6,119,214
1

2

access the file. In this situation, the page table contains
multiple references to the same physical address.
Since available physical addresses are mapped to logical
FIELD OF THE INVENTION
addrcsses as nceded, adjaccnt logical addrcsses arc typically
TIle present invention is directed to the management of 5 mapped to widely separated portion"; of p~ysical me111<?ry,
and vice versa. Furthermore, durmg operatIOn the phYSIcal
memory in a computer system, and more particularly to the
addresses are constantly being remapped as different operaallocation of address space in a virtual memory system for
tions are carried out. As a result, there is not necessarily a
a computer.
direct relationship between logical and physical addresses.
When an action occurs which removes the need for
BACKGROUND OF THE INVENTION
10
further memory accesses, e.g. an application program or a
In the operation of a computer, software programs that are
file is closed, it is no longer necessary to assign address
running on the computer require access to the computer's
space to that entity. Upon the occurrence of such an action,
main memory, e.g., RAM, in order to carry out their operatherefore, a command is sent to the memory manager to
tions. To this end, therefore, each program is allocated a 15 delete an area, or range of addresses, assigned to the file. At
range of memory addresses, which are available for use by
this point, however, the physical memory still has an entry
that program. This range of allocated addresses is sometimes
or address mapped in the page table, which is therefore not
referred to as the program's address space. In actual practice,
free for other uses.
a program may only use a fraction of its allocated addresses
In order to free the addresses for further use, their
at any given time. Consequently, if the allocated address
20 corresponding entries must be removed from the page table.
space corresponds to actual physical space within the main
In some types of page tables, contiguous logical addresses
memory, a large portion of the memory will not be used.
are mapped to contiguous page table entries. In these types
While this situation may be acceptable if only one proof page tables, when an address area is deleted, all of the
gram is running on the computer, it can present significant
page table entries associated with that area can be readily
limitations if multiple programs are to be nm, for example 25 identified and removed [rom the table.
in a multi-tasking environment. More particularly, once
In other types of architectures, however, there is not such
address space is allocated to a particular program, it cannot
a direct relationship between logical addresses and page
be accessed by other programs, even if it is not being
table entries. For example, in some architectures the physicurrently used, because it must always be available for use
cal address of the page table entry is determined by means
by the program to which it has been allocated. As a result,
30 of a hashing function. In this approach, the page table entry
once all available memory has been allocated, additional
might be determined through a logical combination of
programs cannot be run until some memory space is freed
different components of an address, for example in accorup, for example by closing a program.
dance with a prescribed function, rather than a straight index
To alleviate this situation, virtual memory technology has
using one or more components of the address. A'S a result,
been developed. In this technology, the addresses that are 35 page table entries which map adjacent logical addresses
assigned for use by individual programs are distinct from the
could be widely separated in the table. There is no fixed
actual physical addresses of the main memory. The
relationship hetween the locations of page tahle entries for
addresses which are allocated to the programs are often
adj acent logical addresses.
referred to as "logical" or "virtual" or "effective" addresses,
Consequently, when a file is closed, or portions of
to distinguish them from the "physical" addresses of the 40 memory are otherwise rendered inactive, there is no simple,
main memory. Whenever a program requires access to
effective way to locate all page table entries that might be
memory, it makes a call to a logical address within its
associated with the inactive addresses. Since the page table
assigned address space. A memory manager associates this
entries for a file could he scattered throughout the tahle, it
logical address with a physical address in the main memory,
may be necessary to check every entry in the page table, i.e.
where the information called for by the program is actually 45 to scan the table. Alternatively, it is possible to compute all
stored. The identification of each physical address that
possible page table entries for the given range of inactive
corresponds to a logical address is commonly stored in a
addresses, using the hashing function, and check each such
data structure known as a page table. This term is derived
entry. During the time that the scanning of the page table is
from the practice of dividing the memory into individually
being carried out to identify inactive entries, software proaddressable blocks known as "pages".
50 grams might need to be temporarily halted. For computers
Through the use of virtual memory, the available physical
having relatively large amounts of address space, and a large
memory can be utilized more effectively. More particularly,
number of entries in their page tables, the time required to
physical addresses only need to be assigned to those logical
scan all of the entries in the page table can be considerable.
addresses which are currently active. If a program is not
If a complete scan of the page table is carried out at once,
using a portion of its assign~d address space, no physical 55 delays in the running of the programs can result. In addition,
addresses need be associated with these unused logIcal
a complete scan of the page table may be too expensive an
addresses. By marking pages of data as temporarily
operation, in terms of operating efficiency, to carry out every
inaccessible, the associated physical page can be copied to
time a range of addresses is inactivated.
secondary storage and reassigned to map some other virtual
Accordingly, it is desirable to provide a method for
page. As a result, a larger portion of the main memory is 60 efficiently allocating and de allocating large amounts of
available for use by other programs. Each program can
address space in a virtual memory system that does not
continue to operate as if it has a large contiguous address
require excessive processing time and therefore does not
space availahle to it, however.
result in unacceptable delays in the operation of a computer.
In many instances, two or more logical addresses may be
DRlEr STATEMENT or TIlE INVENTION
mapped to the same locations in the physical memory. For 65
example, two or more applications might share a common
In accordance with the present invention, virtual memory
data file. Each application uses a different logical address to
space is managed in a mallller which allows new address

METHOD FOR ALLOCATION OF ADDRESS
SPACE IN A VIRTUAL MEMORY SYSTEM

DEF00000805

6,119,214

3

4

ranges to be allocated and deallocated in a constant, small
amount of time, such that the need for a single complete
sweep of all memory allocation records in a page table, to
remove unused entries and prepare the addresses for further
use, can be avoided.
Thc memory manager of the present invention maintains
three lists of virtual address ranges, namely those which are
free to be allocated, i.e. mapped, to a program, those which
are currently assigned but no longer being used, and those
which are being removed from the page table. The removal
of old entries from the page table proceeds in parallel with
the allocation of free addresses to programs, such that new
free addresses are guaranteed to be available at all times.
More specifically, each time that a new range of addresses is
allocated to a program, a limited number of entries in the
page table are examined, to determine whether the addresses
associated with those entries are no longer in use and the
entries can be removed from the page table. By the time that
all of the addresses in the free list have been allocated, the
entire page table has been examined and all entries associ ated with unused addresses have been removed. The
addresses whose entries have been removed can then be
transferred to the list of free addresses, so that allocation can
continue uninterrupted.
Thus, rather than halting the operation of the computer for
a considerable period of time to scan the entire page table
when a logical address area is deleted, the memory manager
of the present invention carries out a limited, time-bounded
examination upon each address allocation. A constant supply
of free address ranges is provided in exchange for a fixed
amount of computation time at regular intervals.
The foregoing features and advantages of the invention,
as well as others, are described in greater detail hereinafter
with reference to specific embodiments illustrated in the
accompanying drawings.

are not limikd to this particular embodiment, and that its
description is for exemplary purposes only.
Generally speaking, information that is accessed by a
computer's Central Processing Unit (CPU) is specified by a
location, often referred to as a logical address. A program is
assigncd a domain of logical addresses, known as a logical
address space, as part of the process of preparing the
program to run. In a virtual memory computer, a portion of
the computer's hardware is responsible for converting given
logical addresses into concrete physical addresses, through
the use of a page table. This conversion process is referred
to as memory mapping. The primary purpose of using this
approach is to achieve the virtual memory effect that logical
addressing is independent of physical memory addressing.
Referring to FIG. 1, a schematic representation of
memory mapping is illustrated. The memory mapping architecture illustrated in FIG. 1 employs three address spaces.
An effective address is generated by the currently active
program. In a 32-bit system, for example, there are 232
possible effective addresses. The second address space consists of virtual addresses. The effective address and the
virtual address together are analogous to a logical address in
a conventional two-address system. The virtual addresses

5

10

15

20

25

30

35

BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is an illustration of file mapping by means of a
page table in accordance with one embodiment of the
present invention;
FIG. 2 is a diagram showing the location of a file in a
logical address space;
FIG. 3 is a more detailed diagram showing the generation
of a physical address from an effective address;
FIG. 4 is a state diagram of the possible states for virtual
addresses;
FIG. 5 is a state diagram of address states as monitored in
accordance with the present invention;
FIG. 6 is a flow chart of the operation of a memory
manager in accordance with the present invention;
PIG. 7 is a flow chart of an alternative embodiment of the
operation of the memory manager; and
FIG. 8 is a flow chart of the sweeping routine for the
alternate embodiment; and
FIG. 9 is a bitmap of the states of the virtual segment
identifiers.
DETAILED DESCRIPTION
To facilitate an understanding of the invention and its
applications, a brief overview of computer memory management is first provided with reference to FIGS. 1-3. The
particular example illustrated in these figures pertains to the
MPC601 RISC microprocessor sold by Motorola Inc. It will
be appreciated however, that the principles of the invention

40

45

50

55

60

65

:~~~::e:p~~~s~sn!~di~~~~~~i~~et~~e~rn~h~~~:~;a~f~nv~~t~;~
final addresses, namely the real or physical addresses for the
memory. Only the physical addresses are presented to a
memory controller interface, or the like, to read or write
locations in physical memory.
The memory mapping architecture illustrated in FIG. 1
implements a paged, virtual address mapping. The eflective
address range is divided into a number of segments 10, 12,
each of which can be individually mapped to any range 14,
16 of contiguous virtual addresses. Although not illustrated
in FIG. 1, two different segments of the effective address
range can be mapped to the same range of virtual addresses,
and two distinct virtual addresses can be mapped to the same
physical address. The virtual addresses are mapped to the
physical addresses, using a page table 18. For an exemplary
32-bit system, the effective address range might be divided
into 16 segments, each of which is mapped to a 256 MB
range of contiguous virtual addresses. The particular segment of the effective address range is designated by the first
four bits of the address. The size of the virtual address range
is defined by the remaining number of bits in the effective
address (in this case, 28 bits). The number of segments and
size of this range can be varied to meet different memory
management hardware requirements.
Referring to FIG. 2, during operation of the computer, the
system may use a secondary storage file A to hold copies of
physical pages used to map address ranges A'to A". In other
words, the file A is mapped into that effective address space.
Although not illustrated in FIG. 2, the addresses in the
effective address space can be discontiguous, and can be
shared among plural programs. The memory manager functions to convert the effective addresses in this range to
physical addresses in the main memory.
The translation from effective address to virtual address,
and from virtual address to physical address, is illustrated in
greater detail in FIG. 3. To facilitate an understanding of the
translation mechanism, it will be described with specific
reference to its implementation in an exemplary 32-bit
system, in which the memory is divided into pages each
having a size of 4K bytes. In the first step of the translation,
the four most significant bits of the effective address
(labelled SR#) are used to select one of sixteen segment

DEF00000806

6,119,214
5

6

regislers 20. Each segmml regisler holds a 24-bil virlual
removed frum the page table before the range of virtual
segment identifier (VSID) which identifies a unique 256
addresses can be assigned to another thread. Otherwise, the
MRyte range in the virtual address space.
reused addresses might refer to old memory mappings that
are no longer valid. Since the page table is hashed, entries
The lower order 28 bits of the effective address are
divided into a 16-bit page index and a 12-bit byte offset. A 5 belonging 10 a given thread are likely to be scallered
throughout the page table. The VSID, by itself, does not
given page in the virtual address space is mapped onto a
provide sufficient information to locate all page tahle entries
page in the physical address space through the page table 18.
that might belong to a given virtual segment, without
The specific entry in the page table is identified by the VSID
checking every entry in the page table. Scanning the comand the 16-bit page index. The 12-bit byte offset defines an
individual one of the 4K bytes within the page of memory. 10 plete page table every time a thread is created or deleted
would be too inefficient and time consuming. Accordingly,
In order to efficiently map a sparsely populated effective
the present invention is directed to an efficient approach
address space or virtual address space, the identification of
which provides constant removal of unused entries of the
the entries in the page table can be implemented with a
hashing function. Any suitable hashing function can be
page table, in parallel with the creation and deletion of
employed to determine the address for a page table entry. 15 threads and applications.
For example, a variable number of the lower-order bits of the
In the implementation of the present invention, the virtual
VSID can be logically combined with the page index bits in
addresses are designated as being in one of several states.
the virtual address, by means of an EXCLUSIVE-OR funcMore particularly, in the control of the memory system, all
tion. The resulting value can then be combined with any
of the addresses (VSIDS) for the virtual address space can
suitable base offset, to produce a 32-bit address page table 20 reside in one of three states. Referring to FIG. 4, all of the
address (PTA) which identifies an entry in the page table 18.
VSIDs are initially in a free state in which they have not
The value stored at this entry comprises a 20-bit physical
been reserved for use by a thread or application. When a
page number (PPN). The physical page number is then
VSID is subsequently allocated to an application or thread,
combined with the byte offset (the 12 lowest order bits of the
it is labeled as active. At some point in time, the VSID
25 becomes inactive. This can occur, for example, when a
effective address) to produce a 32-bit physical address.
Through the use of the hashing function, the page table
thread terminates. In the inactive state, pages within the
entries are efficiently distributed within the page table. The
virtual address range of the VSID are still mapped to the
page table size itself is variable. It can be adjusted to allow
page table. However, the data contained in the associated
room for more page table entries on systems with more
pages of physical memory is no longer being accessed by the
physical memory or where more sharing of physical 30 CPU. In this state, the entries can be removed from the page
memory pages is anticipated.
table, and the VSID subsequently returned to the free state.
In practice, an operating system typically needs to deal
Until such time as the entries are removed from the page
with two types of addressing contexts, namely large areas
table, however, they remain mapped and are therefore not
mapping the code related to an active application or task,
available to be allocated to other applications or threads.
and small areas that hold information specific to a thread of 35
Generally speaking, the return ofVSTDs from the inactive
control running in the application's context to execute a
state to the free state is carried out by sweeping the entries
specific task. Some of these areas might be shared, i.e. two
in the page table, i.e. examining each entry to determine
or more effective addresses can point to the same location in
whether it is associated with an inactive VSID, and removphysical memory. While large application contexts are gening every entry which has been so identified. In accordance
erally allocated and removed infrequently, in practice 40 with the present invention, the sweeping of the page table is
threads can be created and deleted at high rates. Thread
not carried out in one colossal step, for example after all of
creation and deletion are important operations that must be
the free VSIDs have been allocated. Rather, the sweeping is
carried out efficiently if an operating system is to perform
carried out in an incremental, ongoing manner to avoid
well. In the following discussion, therefore, specific refersignificant interruptions in the running of programs. Reference will be made to operations that occur upon the creation 45 ring to FIG. 5, the memory manager of the present invention
and deletion of threads. It will be appreciated that these
maintains three lists of VSIDs. One list 22 comprises free
operations apply to the addressing of applications as well.
VSIDs which have not been allocated to a program or
In operation, the memory manager assigns a range of
thread. A second list 24 identifies those VSIDs which have
virtual address space to threads as they are created, mapping
been deleted and are therefore inactive. A third list 26,
segments in the effective address space to virtual segments 50 labelled the recycle list, contains those VSIDs whose entries
in the virtual address space. This results in an active virtual
are in the process of being removed from the page table.
address space that is larger than the effective address space
Although the active state of the VSIDs is also shown in FIG.
of any given thread. The amount of virtual address space that
5, the VSIDs in this state do not need to be explicitly stored
is in use at any given time is a concatenation of all threads'
in a list. Typically, they are tracked in other data structures,
and applications' address spaces. This space can be much 55 such as process control tables.
greater than the size of the physical memory, depending on
Although described as three different lists, in a practical
the amount of sharing of physical memory. However, only
implementation these items of information need not be
the pages which are actually mapped consume space in the
stored as three separate entities in the memory manager. For
page table.
example, all possible VSlDs can be stored in a single
As the thread is running and generates requests for pages 60 bitmap, as shown in FIG. 9. Associated with each entry in
of memory, virtual pages within the 256 MD range are
the bitmap is an identifier which indicates whether the VSID
mapped to the page table. When a thread is switched, the
is free (00), inactive (01) or being recycled (10). Suitable
data structures other than a hitmap can he employed as well
operating system switches from one segment register to
to identify the states of the respective VSIDs, such as a list
another to change the mapping of effective addresses to
virtual addresses, as well as the resulting physical addresses. 65 which maps each VSID to one of the three states.
In operation, the VSIDs on the inactive list are transferred
When a thread is deleted, all page table entries that refer
to virtual addresses which are valid for that thread must be
to the recyele list at a certain time, for example when a

DEF00000807

6,119,214

7

8

predetermined number of VSIDs have been placed on the
the present invention, is illustrated in FIG. 6. Referring
inactive list. Thereafter, each time a VSID is assigned from
thereto, operation begins when a request for address space is
the free list to a new application or thread, a fixed numher
generated (Step 10). This can occur when a thread is created,
of entries in the page table are scanned to determine whether
for example. In response thereto, the operating system
they have become inactive, by checking them against the 5 checks the free list to determine whether a free VSID is
VSIDs on the recycle list. Each entry which is identified as
available (Step 12). If so, a free VSID is allocated to the
heing inactive is removed from the page tahle. After all of
thread that generated the request (Step 14). Tn the case of an
the entries in the page table have been examined in this
application, two or more VSIDs might be assigned. If no free
manner, the VSIDs in the recycle list can be transferred to
VSID is available at Step 12, a failure status is returned (Step
the free list, since all of their associated page table entries 10 18). In practice, however, such a situation should not occur,
will have heen removed. This approach therehy guarantees
since the process of the present invention ensures that free
that a predetermined number of VSIDs are always available
VSIDs are always available.
in the free list without requiring a time-consuming scan of
After the new VSID has been allocated, the system checks
the complete page table at once.
a flag RFLG to determine whether a recycle sweep is
currently in progress (Step 20). If there is no sweep in
In one embodiment of the invention, the number of page
table entries that are examined upon each allocation of a 15 progress, i.e. RPLG is not equal to one, a determination is
VSID in the free list can be determined from the total
made whether a sweep should be initiated. This is done by
number of entries in the page table and the number of
checking whether the inactive list is full, i.e. whether it
threads and applications that are allowed to be active at any
contains x entries (Step 22). If the number of entries I on the
given time. Por example, if the page table contains 10,000
inactive list is less than x, no further action is taken, and
entries and 500 threads/applications are allowed to be active 20 processing control returns to the operating system (Step 24).
at any given time, the 10,000 page table entries should be
If, however, the inactive list is full at this time, the flag
covered in a maximum of 500 steps (assuming each thread
RFLG is set (Step 26), the VSIDs on the inactive list are
and application is assigned one segment each). The number
transferred to the recycle list, and an index n is reset to 1
of entries that are swept in each step is therefore 10,0001
(Step 28). The system then sweeps a predetermined number
500~20 cntries per step. Thus, for example, as the first VSID 25 of page table entries PT i on the page table, to detect whether
in the free list is assigned to a thread or application, entries
any of them are inactive, i.e. their associated VSID is on the
0-19 in the page table are examined. Each of those entries
recycle list (Step 30). The predetermined number of entries
which is associated with an inactive VSID on the recycle list
that are swept is identified as k, where
is removed from the page table. As the next VSID in the free
state is allocated, entries 20-39 in the page table are exam- 30
k = total number of page table entries
ined. The process continues in this manner. Thus, after 500
maximumnwnber of active threads
VSIDs have been allocated from the free list, all 10,000
entries in the page table will have been examined. At this
In the example given previously, k~10000!500~20. For a
point, all of the entries in the page table that are associated
given value of the index n, therefore, the system sweeps
with inactive VSIDs on the recycle list will have been 35
table cntrics PTk.(n-1) to PTk-0)-1. Thus, during the first
removed. The VSIDs can therefore be transferred to the free
sweep, table entnes PTo to l'T19 are examined in the
list, and the process begun anew.
example given above.
Any other suitable approach can be employed to deterIf a recycling sweep is already in progress, i.e. the
mine the number of entries to be examined during each step
response is affirmative at Step 20, the index n is incremented
of the sweeping process. In this regard, it is not necessary 40 (Step 32) and a sweep of the next k entries is carried out.
that the number of examined entries be fixed for each step.
Thus, where n~2, entries PT20 to PT39 will he examined.
Rather, it might vary from one step to the next. The only
The process continucs in this manncr, with k entrics in thc
criterion is that the number of entries examined on each step
page table being examined each time a free VSID is allobe such that all entries in the page table are examined in a
cated. Each entry is examined to determine whether it
determinable amount of time or by the occurrence of a 45 contains a mapping for a VSID on the recycle list. If it does,
ccrtain cvcnt, c.g. by thc time the list of free VSIDs is empty.
that entry is removed from the page table.
Generally speaking, the sizes of the free, inactive and
After each sweep, the system determines whether all
recycle lists are determined by the range of VSIDs that need
entries in the page table have been checked (Step 36). This
to be allocated. If at most x threads/applications can be
situation will occur when n~x. Once all of the entries have
active at any time, the free list should start with 3x entries. 50 been examined, the VSIDs in the recycle list are transferred
A recycling sweep, i.e. a removal of inactive entries from the
to the free list (Step 38), yielding x new VSIDs that are
page table, can begin as soon as the inactive list contains x
available to be allocated. In addition, the recycle sweep flag
entries. At this point, the free list will contain between x and
RFLG is reset, and control is then returned to the program.
2x entries, depending upon the number of active threads and
If all of the entries in the page table have not yet been
applications at that timc. In the worst ease, the free list will 55 checked, i.e. the response is negative at Step 36, control is
always contain at least x VSIDs.
directly returned to the application program, at Step 24.
Once the inactive list contains x entries, the VSIDs on the
From the foregoing, it can be seen that the present
inactive list are transferred to the recycle list, for example by
invention provides an efficient approach to the allocation of
changing a pointer or other suitable identifier in a bitmap
large amounts of address space, without requiring timelisting of VSIDs. The recycling sweep is carried out as free 60 consuming, and therefore annoying, interruptions in proVSIDs are consumed. Since the free list contains at least x
cessing. Free addresses are always guaranteed to be availentries at this time, the sweep is guaranteed to be complete
able while avoiding the need for a single complete sweep of
hefore the free list is completely empty. Once the sweep is
all memory allocation records in a page table to remove
completed, it will yield x ncw VSIDs that are transferred to
unused entries and determine which addresses are free. The
the free list.
65 amount of work that is done is bounded, because only a
limited number of entries, k, is examined at each step of the
A flowchart which depicts the operation of the address
allocation portion of a memory manager, in accordance with
process.

DEF00000808

6,119,214
9

10

Varialions of lht fortgoing proct:ss can bt: carrit:d oul
within the scope of the present invention. For example, it is
not necessary to wait for the inactive list to fill before
initiating the scanning of entries in the page table. To
improve page table efficiency, its entries can be examined
while waiting for the inactive list to fill. This variation is
illustrated in the flow chart of PIG. 7. Referring thereto, if
the response at Step 22 is negative, i.e. the inactive list is not
yet full, the index n is incremented at Step 40, and the
proccss thcn procccds to Stcp 30, whcrc the next k cntries
are swept. In the sweeping process, each page table entry is
checked to determine whether it has a corresponding VSID
on the inactive list. If so, that entry is removed from the page
table.
This approach provides a two-fold advantage. First, some
inaclivt: pagt: labk t:nlrit:s art: rt:movt:d mort: rapidly, sinct
it is not necessary to wait for their VSIDs to be transferred
to the recycle list. As a result, the efficiency of the page table
is increased, i.e. it contains fewer inactive entries than it
otherwise would. Secondly, less work is required during the
sweep of the recycle list. In particular, since at least some of
the page table entries for inactive VSIDs were removed prior
to the time those VSIDs were transferred to the recycle list,
there will not be as many entries to remove dming the
recycle sweep of those VSIDs.
After a sweep is completed at Step 30, the status of the
flag RFLG is again checked, at Step 42, to determine
whether the sweep was of the inactive list or the recycle list.
If RFLG=O, indicating that the inactive list was being swept,
the process returns to the main program. Otherwise, it
proceeds to Step 36, as in the flowchart of FIG. 6.
While the page table entries are being examined dming
the sweeping process, it is possible to further enhance the
efficiency of the page table by carrying out other operations
as welL For example, in some page tables, a suitable number
of entries are grouped together, and the addressing of entries
is done by groups. In other words, the page table address
PTA that results from the operation of the hashing function
is thc physical address of a pagc table entry group. Whcnever a call is made to a particular virtual address, the
individual page table entries within an addressed group are
then checked, one by one, to determine whether they correspond to the virtual address that generated a page table
search. Thus, it can be seen that it takes longer to locate an
entry that resides in the last position in the group, relative to
an entry in the first position in the group.
Further along these lines, two page table entry groups can
be associated with one another. The hashing function value
for the two groups can have any suitable relationship to one
another that would enable the hashing function value of one
group to be derived if the value for the other group is known.
For example, they can be complements of one another. If a
desired page table entry is not found in one group (the
primary group), its associatcd group (thc sccondary group)
is checked. Again, it takes longer to find a page table entry
in the secondary group, relative to those in the primary
group.
During the sweeping process, therefore, as each page
table entry is being examined, its location within a group can
bt: oplimizt:d if il is nol bt:ing rt:movt:d from lht: pagt: labk.
A more detailed flow chart of the sweeping process, in which
such optimization is carried out, is illustrated in FIG. 8.
Referring thereto, when the sweeping process is entered
(Step 30 of FIG. 7), the memory manager first determines
whether the VSID associated with the page table entry of
interest is on the recycle list (Step 44). If so, the entry is

rt:movt:d from lht: pagt: labk, al Slt:p 46. If lht: VSID is nol
on the recycle list, a determination is made whether it is on
the inactive list (Step 48). If so, the entry is removed at Step
46. If the VSID is not on either of these two lists, it is still
aclivt:. In lhis cast:, lht: mt:mory managt:r ddt:rmint:s
whether the entry is in the primary group (Step 50). If not,
a check is made at Step 52 to determine whether a slot is
available in the primary group, and if so the entry is moved
10 lht primary group al Slt:p 54. If lht: t:nlry is alrt:ady in lht:
primary group, a determination is made at Step 56 whether
it is in the highest availahle slot, and if not its location is
optimized. With this approach, the efficiency of the page
labk is conlinually bt:ing t:nhanct:d.
It will be appreciated that the present invention is not
limited to the specific embodiments which have been
described herein to facilitate an understanding of its underlying principles. For example, while the memory management approach of the present invention is particularly applicable to page tables whose entries are hashed or otherwise
randomly distributed throughout the table, its implementation is not limited thereto. Similarly, it is possible to initiate
the sweep of page table entries in response to regularly
occurring events other than the assignment of a free VSID.
For example, a limited number of entries can be examined
each time a thread is deleted. Furthermore, it is not necessary
10 t:xamint: lht: pagt: labk t:nlrit:s in a st:qut:nlial mannt:r, as
described above. Rather, any systematic approach can be
employed which assures that all entries will be swept.
Further along these lines, the transfer of VSIDs from the
recycle list to the free list need not occur only at the end of
a complete sweep. Depending on the structure of the page
table, it may be possible to transfer some of the VSIDs after
a partial sweep of the page table, as long as it is known that
all possible entries associated with those VSIDs have been
cxamincd.
The scope of the invention is therefore defined by the
claims which are appended hereto, rather than the foregoing
description, and all equivalents which are consistent with the
meaning of the claims are intended to be embraced therein.
What is claimed is:
1. A method for allocating address space in a virtual
memory system for a computer, comprising the steps of:
maintaining a list of available addresses that are free to be
allocated to a program;
allocating addresses to a program in response to requests
for address space;
recording entries in a page table relating to addresses that
have heen allocated;
upon each allocation of an available address, examining a
number of entries in the page table, which number is
less than the total number of entries in the table, to
determine whether the entries have been identified as
no longer active;
removing the entries from the table which have been
determined to be no longer active, and maintaining a
list of the addresses associated with the entries being
removed; and
transferring the list of addresses associated with removed
entries to the list of allocatable addresses.
2. The method of claim 1 wherein said transferring step is
carrit:d oul aflt:r all of lht: t:nlrit:s in lht: labk havt: bt:t:n
examined.
3. The method of claim 1 wherein said number of entries
that are examined upon each allocation equals pix, where p
is the total number of available addresses, and x is the
maximum number of addresses that can be active at any
given time.

5

10

15

20

25

30

35

40

45

50

55

60

65

DEF00000809

6,119,214
11

12

4. The method of claim 3 wherein said examining step is
16. The method of claim 15 wherein said processing
initiated after x addresses have been identified as inactive.
includes the step of optimizing the entry's location within
5. The method of claim 1 wherein said numher of entries
the page table.
that are examined upon each allocation is variable from one
17. A system for managing memory in a computer,
allocation to another.
6. In a computer system of the type in which ranges of 5 comprising:
means for allocating ranges of logical addresses to prological addresses are assigned to programs and the assigned
addresses are mapped to physical memory through entries in
vide access to the memory of the computer;
a page table, a method fur removing entries from the pagt
a page table containing entries which map allocated
table when a range of addresses is deleted, comprising the 10
logical addresses to physical addresses for the memory;
steps of:
means for indicating that a range of logical addresses has
a) maintaining a list of addresses that have been deleted;
b) upon the occurrence of a predetermined event, exambeen deallocated;
ining a defined number of entries in the page table to
means responsive to the occurrence of a predetermined
determine whether those entries are associated with any 15
event for examining a limited number of the entries in
of the addresses on said list;
the page table to determine whether they are associated
c) removing each examined entry from the page table
with an address that has been deallocated, and for
which is associated with an address on said list;
removing each such entry from the page table; and
d) repeating steps band c upon the occurrence of said
event until all of the entries in the page table have been 20
means for indicating that addresses whose entries have
examined; and
been removed from the page table are available for
e) identifying the addresses in said list as addresses which
further allocation.
are available to be assigned to programs.
18. The memory management system of claim 17,
7. The method of claim 6 wherein said predetermined
wherein said indicating means comprise a data structure
event is the assignment of an address from those which are
25 containing a list of logical addrcsses and an indicator
identified as being available.
associated with each address which identifies whether the
8. The method of claim 6 wherein said defined number is
address is available for allocation or has been deallocated.
related to the ratio of the number of addresses available to
19. The memory manager of claim 18 wherein said data
be assigned to programs relative to the number of entries in
the page table.
structure identifies addresses as being in one of three states
9. The method of claim 6 wherein said defined number is 30 which respectively indicate whether the address is available
variahle.
for allocation, deallocated, or being processed for further
10. The method of claim 6 wherein the step of maintaining
availability, and further including means for changing the
a list of addresses includes the steps of identifying addresses
state of addresses from being processed to available in
that have been deleted as being in an inactive state, and
response to a predetermined occurrence.
35
transferring the inactive addresses to a recycle state.
20. The memory manager of claim 19 wherein said
11. The method of claim 10 wherein said examining step
predetermined occurrence is the examination of all entries in
determines whether the examined entries are associated with
the page table.
addresses in the recycle state.
21. The memory manager of claim 20 wherein said
12. The method of claim 11, wherein said examining step
processing includes optimization of the location of the
also determines whether the examined entries are also 40
examined entry in the page table.
associated with addresses in the inactive state.
22. The memory manager of claim 17 wherein said
13. The method of claim 10 wherein the state of a logical
predetermined event is the allocation of a range of logical
address is indicated by an associated identifier stored in a
addresses.
data structure.
23. The memory manager of claim 17 further including
14. The method of claim 13 wherein said data structure is 45
means for processing each examined entry in the page table
a bitmap.
that is not associated with a deallocated address to enhance
15. The method of claim 6, further including the step of
the efficiency of the page table.
processing each examined entry which is not associated with
an address on said list to enhance the efficiency of the page
table.
* * * * *

DEF00000810