US5784699A — Dynamic memory allocation in a computer using a b…

Claim 1

Independent Claim 135 words

A method for allocating memory in a computer system, said method comprising the steps of: assigning portions of memory of equal size into one of a plurality of slots such that each slot includes zero or more memory blocks of equal size; generating a bit map index comprising a plurality of bit flags, wherein each bit flag corresponds to one of said slots and indicates availability of at least one memory block for a corresponding slot; receiving a request, including a size, for a memory block; searching for available memory in response to said request by examining one or more of said bit flags in said bit map index to identify an available memory block to accommodate said memory block request; and assigning a memory block not in use to accommodate said memory block request.

Claim 2

Independent Claim 135 words

A method for allocating memory in a computer system, said method comprising the steps of: assigning portions of memory of equal size into one of a plurality of slots such that each slot includes zero or more memory blocks of equal size; generating a bit map index comprising a plurality of bit flags, wherein each bit flag corresponds to one of said slots and indicates availability of at least one memory block for a corresponding slot; receiving a request, including a size, for a memory block; searching for available memory in response to said request by examining one or more of said bit flags in said bit map index to identify an available memory block to accommodate said memory block request; and assigning a memory block not in use to accommodate said memory block request.

Claim 3

Dependent Claim 188 words

The method as set forth in claim 1, wherein: the step of generating a bit map index comprises the step of generating a hierarchical bit map index including the steps of: assigning said slots to a plurality of groups; generating, for each group, a group bit map index comprising a plurality of bit flags, wherein each bit flag corresponds to one of said groups, and each bit flag indicates availability of at least one memory block in a corresponding group; generating, for each slot, a slot bit map index comprising a plurality of bit flags, wherein each bit flag corresponds to one of said slots, and each bit flag indicates availability of at least one memory block in a corresponding slot; the step of searching by examining one or more of said bit flags comprises the steps of: examining said group bit index to identify an available group of memory blocks that accommodate said memory block requested; and examining one or more slot bit map indexes based on said bit flags in said group bit index to identify an available memory block to accommodate said memory block requested.

Claim 4

Dependent Claim 117 words

The method as set forth in claim 1, wherein the step of searching for available memory in response to said request comprises the steps of: searching for an available memory block corresponding to said nearest slot rounded up for said memory block requested; searching, if no memory block of size equal to said nearest slot rounded up for said memory block requested is available, for an available memory block corresponding to a next largest slot; and searching, if no memory block in a prior slot searched is available, for an available memory block from a slot corresponding to a next largest slot until either an available block is located or until a largest slot has been searched.

Claim 5

Dependent Claim 110 words

The method as set forth in claim 1, wherein the step of assigning portions of memory of equal size into one of a plurality of slots comprises the steps of: assigning said memory into a plurality of slots, in increments of a first size, for small block allocations, wherein small block allocations include allocations of memory blocks smaller than a predefined maximum small block size; and assigning said memory into a plurality of slots, in increments of a second size, for large block allocations, wherein large block allocations include allocations of memory blocks smaller than a predefined maximum large block size and greater than said predefined maximum small block size.

Claim 6

Dependent Claim 63 words

The method as set forth in claim 1, further comprising the steps of: referencing a special block; and apportioning said special block into a memory block of a size to accommodate said memory block requested if, as identified by said bit map index, a memory block is not available and if said special block is large enough to accommodate said memory block requested.

Claim 7

Dependent Claim 71 words

The method as set forth in claim 5, further comprising the steps of: discarding, as a reference, said special block if said special block is not large enough to accommodate said memory block requested; referencing a new special block; dividing said new special block into a memory block of a size to accommodate said memory block requested; and allocating said memory block of a size to accommodate said memory block requested.

Claim 8

Dependent Claim 63 words

The method as set forth in claim 1, further comprising the steps of: apportioning a memory block for a large allocation if a memory block located is large enough for division into two large allocation memory blocks; and generating, for an apportioned memory block, a double linked pointer to identify physically adjacent blocks and a virtual page for each divided memory block portion.

Claim 9

Dependent Claim 73 words

The method as set forth in claim 7, further comprising the steps of: merging, if possible, adjacent and available memory blocks through use of said double linked pointers to generate a new large block; referencing said new large block from a new slot; and merging, if possible, adjacent and available memory blocks that constitute a virtual page of memory through use of said double linked pointers to free said virtual page of memory.

Claim 10

Dependent Claim 61 words

The method as set forth in claim 1, further comprising the steps of: generating a plurality of pointers to identify one or more virtual pages of memory; requesting a virtual page of memory if no memory blocks are available as identified from said bit map index; and allocating, if possible, a virtual page of memory identified from one of said pointers.

Claim 11

Dependent Claim 42 words

The method as set forth in claim 9, further comprising the step of generating a request to an operating system of said computer to obtain a virtual page of memory if a virtual page, as identified by said pointers, is not available.

Claim 12

Independent Claim 126 words

A method for allocating memory in a computer system, said method comprising the steps of: assigning portions of memory of equal size into one of a plurality of slots such that each slot includes zero or more memory blocks of equal size; generating a plurality of free lists, one for each slot, such that each free list identifies memory blocks, corresponding to a slot size, not currently in use; receiving a request, including a size, for a memory block; rounding up said size of said memory block requested to a nearest slot; searching one or more of said free lists to identify an available memory block to accommodate said memory block requested; and assigning a memory block not in use to accommodate said memory block requested.

Claim 13

Independent Claim 126 words

A method for allocating memory in a computer system, said method comprising the steps of: assigning portions of memory of equal size into one of a plurality of slots such that each slot includes zero or more memory blocks of equal size; generating a plurality of free lists, one for each slot, such that each free list identifies memory blocks, corresponding to a slot size, not currently in use; receiving a request, including a size, for a memory block; rounding up said size of said memory block requested to a nearest slot; searching one or more of said free lists to identify an available memory block to accommodate said memory block requested; and assigning a memory block not in use to accommodate said memory block requested.

Claim 14

Dependent Claim 40 words

The method as set forth in claim 11, wherein the step of assigning portions of memory of equal size into one of a plurality of slots comprises the step of assigning memory of equal size into at least 32 slots.

Claim 15

Dependent Claim 145 words

A computer readable medium having a set of instructions stored therein, which when executed by a computer, causes the computer to perform the steps of: assigning portions of memory of equal size into one of a plurality of slots such that each slot includes zero or more memory blocks of equal size; generating a bit map index comprising a plurality of bit flags, wherein each bit flag corresponds to one of said slots and indicates availability of at least one memory block for a corresponding slot; receiving a request, including a size, for a memory block; searching for available memory in response to said request by examining one or more of said bit flags in said bit map index to identify an available memory block to accommodate said memory block requested; and assigning a memory block not in use to accommodate said memory block requested.

Claim 16

Dependent Claim 145 words

A computer readable medium having a set of instructions stored therein, which when executed by a computer, causes the computer to perform the steps of: assigning portions of memory of equal size into one of a plurality of slots such that each slot includes zero or more memory blocks of equal size; generating a bit map index comprising a plurality of bit flags, wherein each bit flag corresponds to one of said slots and indicates availability of at least one memory block for a corresponding slot; receiving a request, including a size, for a memory block; searching for available memory in response to said request by examining one or more of said bit flags in said bit map index to identify an available memory block to accommodate said memory block requested; and assigning a memory block not in use to accommodate said memory block requested.

Claim 17

Dependent Claim 186 words

The computer readable medium as set forth in claim 13, wherein: the instructions for generating a bit map index comprises instructions for generating a hierarchical bit map index including instructions for: assigning said slots to a plurality of groups; generating, for each group, a group bit map index comprising a plurality of bit flags, wherein each bit flag corresponds to one of said groups, and each bit flag indicates availability of at least one memory block in a corresponding group; generating, for each slot, a slot bit map index comprising a plurality of bit flags, wherein each bit flag corresponds to one of said slots, and each bit flag indicates availability of at least one memory block in a corresponding slot; instructions for searching by examining one or more of said bit flags comprises instructions for: examining said group bit index to identify an available group of memory blocks that accommodate said memory block requested; and examining one or more slot bit map indexes based on said bit flags in said group bit index to identify an available memory block to accommodate said memory block requested.

Claim 18

Dependent Claim 118 words

The computer readable medium as set forth in claim 13, wherein the instructions for searching for available memory in response to said request comprises instructions for: searching for an available memory block corresponding to said nearest slot rounded up for said memory block requested; searching, if no memory block of size equal to said nearest slot rounded up for said memory block requested is available, for an available memory block corresponding to a next largest slot; and searching, if no memory block in a prior slot searched is available, for an available memory block from a slot corresponding to a next largest slot until either an available block is located or until a largest slot has been searched.

Claim 19

Dependent Claim 111 words

The computer readable medium as set forth in claim 13, wherein the instructions for assigning portions of memory of equal size into one of a plurality of slots comprises instructions for: assigning said memory into a plurality of slots, in increments of a first size, for small block allocations, wherein small block allocations include allocations of memory blocks smaller than a predefined maximum small block size; and assigning said memory into a plurality of slots, in increments of a second size, for large block allocations, wherein large block allocations include allocations of memory blocks smaller than a predefined maximum large block size and greater than said predefined maximum small block size.

Claim 20

Dependent Claim 64 words

The computer readable medium as set forth in claim 13, further comprising instructions for: referencing a special block; and apportioning said special block into a memory block of a size to accommodate said memory block requested if, as identified by said bit map index, a memory block is not available and if said special block is large enough to accommodate said memory block requested.

Claim 21

Dependent Claim 72 words

The computer readable medium as set forth in claim 17, further comprising instructions for: discarding, as a reference, said special block if said special block is not large enough to accommodate said memory block requested; referencing a new special block; dividing said new special block into a memory block of a size to accommodate said memory block requested; and allocating said memory block of a size to accommodate said memory block requested.

Claim 22

Dependent Claim 64 words

The computer readable medium as set forth in claim 13, further comprising instructions for: apportioning a memory block for a large allocation if a memory block located is large enough for division into two large allocation memory blocks; and generating, for an apportioned memory block, a double linked pointer to identify physically adjacent blocks and a virtual page for each divided memory block portion.

Claim 23

Dependent Claim 74 words

The computer readable medium as set forth in claim 19, further comprising instructions for: merging, if possible, adjacent and available memory blocks through use of said double linked pointers to generate a new large block; referencing said new large block from a new slot; and merging, if possible, adjacent and available memory blocks that constitute a virtual page of memory through use of said double linked pointers to free said virtual page of memory.

Claim 24

Dependent Claim 157 words

A computer system comprising: a central processing unit; system memory; a software program resident in said memory and executed by said central processing unit, for a request, including a size, for a memory block; and a dynamic memory allocator for assigning portions of memory of equal size into one of a plurality of slots such that each slot includes zero or more memory blocks of equal size, said dynamic memory allocator for generating a bit map index comprising a plurality of bit flags, wherein each bit flag corresponds to one of said slots and indicates availability of at least one memory block for a corresponding slot, for searching for available memory in response to said request by examining one or more of said bit flags in said bit map index to identify an available memory block to accommodate said memory block request, and for assigning a memory block not in use to accommodate said memory block requested.

Claim 25

Dependent Claim 157 words

A computer system comprising: a central processing unit; system memory; a software program resident in said memory and executed by said central processing unit, for a request, including a size, for a memory block; and a dynamic memory allocator for assigning portions of memory of equal size into one of a plurality of slots such that each slot includes zero or more memory blocks of equal size, said dynamic memory allocator for generating a bit map index comprising a plurality of bit flags, wherein each bit flag corresponds to one of said slots and indicates availability of at least one memory block for a corresponding slot, for searching for available memory in response to said request by examining one or more of said bit flags in said bit map index to identify an available memory block to accommodate said memory block request, and for assigning a memory block not in use to accommodate said memory block requested.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2001-07-20	2002-01-19	2002-07-21	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2005-07-20	2006-01-19	2006-07-21	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2009-07-20	2010-01-19	2010-07-21	$7700.00	Window Closed / Lapsed

Dynamic memory allocation in a computer using a bit map index

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag