Method for managing allocation of memory space

• US 5,339,411 A
• Filed: 10/22/1993
• Issued: 08/16/1994
• Est. Priority Date: 12/21/1990
• Status: Expired due to Term

• Current Assignee: Pitney Bowes Incorporated (Böwe Systec AG)
• Original Assignee: Pitney Bowes Incorporated (Böwe Systec AG)
• Inventors: Heaton, Charles J. Jr.
• Primary Examiner(s): Dixon, Joseph L.
• Assistant Examiner(s): Kim, Matthew M.
• Application Number:
  US08/142,541
• Time in Patent Office: 298 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 395/600, 395/400, 395/425
• US Class Current: 711/171
• CPC Class Codes: G06F 12/023 Free address space management

Abstract

A method of managing the memory space of a data processing device includes defining a number of memory blocks in the memory space and establishing a different maximum memory fragment size for each of the memory blocks. When a memory allocation request is received, it is attempted to allocate the request in the memory block that has the smallest maximum fragment size that is not exceeded by the size of the allocation request. Consequently, smaller allocation requests tend to be loaded in the blocks with smaller maximum fragment sizes, while larger allocation requests are restricted to blocks with a sufficiently large maximum fragment size. The resulting segregation by size of memory fragments among blocks leads to more efficient use of the memory space. Memory fragments may also be segregated by size within a memory block. This is accomplished by establishing a fragment size dividing point for the memory block and then loading allocation requests that exceed the dividing point from the end of the block and loading smaller requests from the beginning of the block.

Claims

1. A method of operation of a data processing device having a memory space to manage allocation of said memory space, operation of said data processing device comprising the steps of:

a) storing first data, said first data specifying first and second ends for a first memory block;

b) storing second data, said second data specifying a maximum fragment size which can be allocated from said first memory block;

c) responding to a memory request generated by an application being executed by said data processing device to allocate a fragment to said application, said memory request specifying a requested fragment size, said responding step including the further steps of;

c1) comparing said requested fragment size to said maximum fragment size; and

c2) allocating an unallocated fragment to said application from said block only if said requested fragment size is less than said maximum fragment size, and otherwise;

c3) responding to said memory request in a predetermined manner without making said requested allocation from said block;

c4) allocating to said application another unallocated fragment of said memory space which has no addressed portions in common with said first memory block;

c5) storing third data, said third data specifying first and second ends for a second memory block;

c6) storing fourth data, said fourth data specifying a maximum fragment size which can be allocated from said second memory block, wherein said maximum fragment size which can be allocated from said second memory block is greater than said maximum fragment size which can be allocated from said first memory block;

c7) if said requested fragment size is greater than said memory fragment size which can be allocated from said first memory block, then responding to said memory request by allocating an unallocated fragment from said second memory block to said application only if said requested fragment size is less than said maximum fragment size which can be allocated from said second memory block; and

otherwise

c8) responding to said memory request in a predetermined manner without making said requested allocation from said first memory block and without making said requested allocation from said second memory block;

c9) allocating to said application said another unallocated fragment of said memory space which has no addressed portions in common with said first memory block and which further has no addressed portions in common with said second memory block.

2. A method of operation of a data processing device having a memory space to manage allocation of said memory space, operation of said data processing device comprising the steps of:

a) storing first data, said first data specifying first and second ends for a first memory block;

b) storing second data, said second data specifying a maximum fragment size which can be allocated from said first memory block;

c) responding to a memory request generated by an application being executed by said data processing device to allocate a fragment to said application, said memory request specifying a requested fragment size, said responding step including the further steps of;

c1) comparing said requested fragment size to said maximum fragment size; and

c2) allocating an unallocated fragment to said application from said block only if said requested fragment size is less than said maximum fragment size, and otherwise;

c3) responding to said memory request in a predetermined manner without making said requested allocation from said block;

c4) storing additional data, said additional data specifying a dividing point fragment size, said dividing point fragment size being less than said maximum fragment size which can be allocated from said first memory block; and

wherein said allocating step (b) further comprises the steps of;

b1) allocating said fragment to said application as closely as possible to said first end of said first memory block if requested fragment size is not greater than said dividing point fragment size; and

b2) allocating said fragment to said application as closely as possible to said second end if said requested fragment size is greater than dividing point fragment size.

3. A method of operation of a data processing device having a memory space to manage allocation of said memory space, operation of said data processing device comprising the steps of:

a) storing first data, said first data specifying first and second ends for a first memory block;

b) storing second data, said second data specifying a maximum fragment size which can be allocated from said first memory block;

c) responding to a memory request generated by an application being executed by said data processing device to allocate a fragment to said application, said memory request specifying a requested fragment size, said responding step including the further steps of;

c1) comparing said requested fragment size to said maximum fragment size; and

c2) allocating an unallocated fragment to said application from said block only if said requested fragment size is less than said maximum fragment size, and otherwise;

c3) responding to said memory request in a predetermined manner without making said requested allocation from said block;

d) executing an initialization routine;

e) receiving a request from said initialization routine to allocate a segment of said memory space as said first memory block and determine said first data, said request from said initialization routine specifying a desired first memory block size, a minimum first memory block size, and a size reduction decrement;

f) using standard facilities of said data processing device to make said requested allocation of said memory space as said first memory block, said using step further comprising the steps of;

f1) determining if an unallocated segment of said memory space can be allocated as said first memory block, and if so specifying storing said first data;

otherwise

f2) determining if said desired first memory block size is greater than said minimum first memory block size, and if not, exiting to a predetermined error routine; and

f3) if said desired first memory block size is greater than said minimum first memory block size reducing said desired first memory block size by said size reduction decrement and returning to step (f1).