Patent US2548369A successfully refreshed from Google Patents.
US6065019A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for allocating and freeing storage utilizing multiple tiers of storage organization
Assignee: International Business Machines Corp
•
Filing: 1997-10-20
•
Granted: 2000-05-16
•
Expires: 2017-10-20
Abstract
Abstract A method and system for allocating and freeing storage are provided. The method can be built on top of any existing storage management algorithm. The method is described as being built upon the heap storage algorithm most often associated with the C programming environment. The method operates by breaking all storage requests into a fixed number of pools. Each pool is then managed by three tiers of management. The first tier is a so-called quick pool consisting of storage blocks which have already been used and freed and are managed on a LIFO queue. The second tier is made up of cell pool extents that are carved from the heap and then further subdivided into blocks of the appropriate size for each pool. The third tier is made up of the existing heap management algorithms or any other storage management algorithm. The method relies on atomic hardware instructions for removing blocks from the quick pools and cell extents. The lack of blocking serialization allows this method to provide a high performing storage manager, even in multithreaded applications with a high degree of concurrency in malloc( ) and free( ) requests from the threads. Any storage request of a size beyond the largest pool size is satisfied by use of the old malloc( ) interface.
Inventors
- 👤 Donald F. Ault
- 👤 John F. Fischer
- 👤 Eric T. Miller
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 10:56
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F9/5005; G06F9/5011; G06F9/5016; G06F12/00; G06F12/02; G06F12/0223; G06F12/023; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99956; Y10S707/99957
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
179 words
In an information handling system having a predetermined routine for obtaining storage from a repository, said predetermined routine requiring a lock for serialization, a method for obtaining storage for a requester while minimizing use of said predetermined routine, comprising the steps of: maintaining a set of previously assigned storage blocks that have been released by requesters; maintaining a set of unassigned storage blocks that have been obtained from said repository using said predetermined routine but have not been assigned to a requester; completing an incoming storage request from said previously assigned storage blocks without acquiring a lock for serialization if said storage request can be completed from said previously assigned storage blocks; completing said storage request from said unassigned storage blocks without acquiring a lock for serialization if said storage request cannot be completed from said previously assigned storage blocks but can be completed from said unassigned storage blocks; and completing said request from said repository using said predetermined routine if said storage request cannot be completed from either said previously assigned storage blocks or said unassigned storage blocks.
Claim 2
Dependent Claim
179 words
In an information handling system having a predetermined routine for obtaining storage from a repository, said predetermined routine requiring a lock for serialization, a method for obtaining storage for a requester while minimizing use of said predetermined routine, comprising the steps of: maintaining a set of previously assigned storage blocks that have been released by requesters; maintaining a set of unassigned storage blocks that have been obtained from said repository using said predetermined routine but have not been assigned to a requester; completing an incoming storage request from said previously assigned storage blocks without acquiring a lock for serialization if said storage request can be completed from said previously assigned storage blocks; completing said storage request from said unassigned storage blocks without acquiring a lock for serialization if said storage request cannot be completed from said previously assigned storage blocks but can be completed from said unassigned storage blocks; and completing said request from said repository using said predetermined routine if said storage request cannot be completed from either said previously assigned storage blocks or said unassigned storage blocks.
Claim 3
Dependent Claim
36 words
The method of claim 1 wherein said first maintaining step comprises the step of: maintaining a plurality of sets of previously assigned storage blocks, the storage blocks in each of said sets having a predetermined size.
Claim 4
Dependent Claim
35 words
The method of claim 1 wherein said second maintaining step comprises the step of: maintaining a plurality of sets of unassigned storage blocks, the storage blocks in each of said sets having a predetermined size.
Claim 5
Dependent Claim
26 words
The method of claim 1 wherein said step of completing an incoming storage request from said previously assigned storage blocks is performed using an atomic operation.
Claim 6
Dependent Claim
25 words
The method of claim 1 wherein said step of completing an incoming storage request from said unassigned storage blocks is performed using an atomic operation.
Claim 7
Dependent Claim
17 words
The method of claim 1 in which said set of previously assigned storage blocks is initially empty.
Claim 8
Dependent Claim
16 words
The method of claim 1 in which said set of unassigned storage blocks is initially empty.
Claim 9
Dependent Claim
18 words
The method of claim 1 in which said previously assigned storage blocks are maintained as a linked list.
Claim 10
Dependent Claim
19 words
The method of claim 1 in which said previously assigned storage blocks are maintained as a LIFO data structure.
Claim 11
Dependent Claim
38 words
The method of claim 1, further comprising the steps of: maintaining counts of the number of blocks requested for each of a plurality of storage sizes; and determining one or more optimum block sizes based upon said counts.
Claim 12
Dependent Claim
53 words
The method of claim 1 wherein said step of completing an incoming storage request from said previously assigned storage blocks is performed using an atomic instruction in which a first value is compared with a second value to produce a comparison result and, depending on the comparison result, replaced with a third value.
Claim 13
Dependent Claim
51 words
The method of claim 1 wherein said step of completing said storage request from said unassigned storage blocks is performed using an atomic instruction in which a first value is compared with a second value to produce a comparison result and, depending on the comparison result, replaced with a third value.
Claim 14
Dependent Claim
185 words
In an information handling system having a predetermined routine for obtaining storage from a repository, said predetermined routine requiring a lock for serialization, apparatus for obtaining storage for a requester while minimizing use of said predetermined routine, comprising: means for maintaining a set of previously assigned storage blocks that have been released by requesters; means for maintaining a set of unassigned storage blocks that have been obtained from said repository using said predetermined routine but have not been assigned to a requester; means for completing an incoming storage request from said previously assigned storage blocks without acquiring a lock for serialization if said storage request can be completed from said previously assigned storage blocks; means for completing said storage request from said unassigned storage blocks without acquiring a lock for serialization if said storage request cannot be completed from said previously assigned storage blocks but can be completed from said unassigned storage blocks; and means for completing said request from said repository using said predetermined routine if said storage request cannot be completed from either said previously assigned storage blocks or said unassigned storage blocks.
Claim 15
Dependent Claim
185 words
In an information handling system having a predetermined routine for obtaining storage from a repository, said predetermined routine requiring a lock for serialization, apparatus for obtaining storage for a requester while minimizing use of said predetermined routine, comprising: means for maintaining a set of previously assigned storage blocks that have been released by requesters; means for maintaining a set of unassigned storage blocks that have been obtained from said repository using said predetermined routine but have not been assigned to a requester; means for completing an incoming storage request from said previously assigned storage blocks without acquiring a lock for serialization if said storage request can be completed from said previously assigned storage blocks; means for completing said storage request from said unassigned storage blocks without acquiring a lock for serialization if said storage request cannot be completed from said previously assigned storage blocks but can be completed from said unassigned storage blocks; and means for completing said request from said repository using said predetermined routine if said storage request cannot be completed from either said previously assigned storage blocks or said unassigned storage blocks.
Claim 16
Dependent Claim
35 words
The apparatus of claim 13 wherein said first maintaining means comprises: means for maintaining a plurality of sets of previously assigned storage blocks, the storage blocks in each of said sets having a predetermined size.
Claim 17
Dependent Claim
34 words
The apparatus of claim 13 wherein said second maintaining means comprises: means for maintaining a plurality of sets of unassigned storage blocks, the storage blocks in each of said sets having a predetermined size.
Claim 18
Dependent Claim
39 words
The apparatus of claim 13, further comprising: means for maintaining counts of the number of blocks requested for each of a plurality of storage sizes; and means for determining one or more optimum block sizes based upon said counts.
Claim 19
Dependent Claim
51 words
The apparatus of claim 13 wherein said means for completing an incoming storage request from said previously assigned storage blocks uses an atomic instruction in which a first value is compared with a second value to produce a comparison result and, depending on the comparison result, replaced with a third value.
Claim 20
Dependent Claim
49 words
The apparatus of claim 13 wherein said means for completing said storage request from said unassigned storage blocks uses an atomic instruction in which a first value is compared with a second value to produce a comparison result and, depending on the comparison result, replaced with a third value.
Claim 21
Dependent Claim
198 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for obtaining storage for a requester while minimizing use of a predetermined routine for obtaining storage from a repository in an information handling system having said routine, said predetermined routine requiring a lock for serialization said method steps comprising: maintaining a set of previously assigned storage blocks that have been released by requesters; maintaining a set of unassigned storage blocks that have been obtained from said repository using said predetermined routine but have not been assigned to a requester; completing an incoming storage request from said previously assigned storage blocks without acquiring a lock for serialization if said storage request can be completed from said previously assigned storage blocks; completing said storage request from said unassigned storage blocks without acquiring a lock for serialization if said storage request cannot be completed from said previously assigned storage blocks but can be completed from said unassigned storage blocks; and completing said request from said repository using said predetermined routine if said storage request cannot be completed from either said previously assigned storage blocks or said unassigned storage blocks.
Claim 22
Dependent Claim
198 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for obtaining storage for a requester while minimizing use of a predetermined routine for obtaining storage from a repository in an information handling system having said routine, said predetermined routine requiring a lock for serialization said method steps comprising: maintaining a set of previously assigned storage blocks that have been released by requesters; maintaining a set of unassigned storage blocks that have been obtained from said repository using said predetermined routine but have not been assigned to a requester; completing an incoming storage request from said previously assigned storage blocks without acquiring a lock for serialization if said storage request can be completed from said previously assigned storage blocks; completing said storage request from said unassigned storage blocks without acquiring a lock for serialization if said storage request cannot be completed from said previously assigned storage blocks but can be completed from said unassigned storage blocks; and completing said request from said repository using said predetermined routine if said storage request cannot be completed from either said previously assigned storage blocks or said unassigned storage blocks.
Claim 23
Dependent Claim
38 words
The program storage device of claim 19 wherein said first maintaining step comprises the step of: maintaining a plurality of sets of previously assigned storage blocks, the storage blocks in each of said sets having a predetermined size.
Claim 24
Dependent Claim
37 words
The program storage device of claim 19 wherein said second maintaining step comprises the step of: maintaining a plurality of sets of unassigned storage blocks, the storage blocks in each of said sets having a predetermined size.
Claim 25
Dependent Claim
28 words
The program storage device of claim 19 wherein said step of completing an incoming storage request from said previously assigned storage blocks is performed using an atomic operation.
Claim 26
Dependent Claim
27 words
The program storage device of claim 19 wherein said step of completing an incoming storage request from said unassigned storage blocks is performed using an atomic operation.
Claim 27
Dependent Claim
19 words
The program storage device of claim 19 in which said set of previously assigned storage blocks is initially empty.
Claim 28
Dependent Claim
18 words
The program storage device of claim 19 in which said set of unassigned storage blocks is initially empty.
Claim 29
Dependent Claim
20 words
The program storage device of claim 19 in which said previously assigned storage blocks are maintained as a linked list.
Claim 30
Dependent Claim
21 words
The program storage device of claim 19 in which said previously assigned storage blocks are maintained as a LIFO data structure.
Claim 31
Dependent Claim
40 words
The program storage device of claim 19, said method steps further comprising: maintaining counts of the number of blocks requested for each of a plurality of storage sizes; and determining one or more optimum block sizes based upon said counts.
Claim 32
Dependent Claim
55 words
The program storage device of claim 19 wherein said step of completing an incoming storage request from said previously assigned storage blocks is performed using an atomic instruction in which a first value is compared with a second value to produce a comparison result and, depending on the comparison result, replaced with a third value.
Claim 33
Dependent Claim
53 words
The program storage device of claim 19 wherein said step of completing said storage request from said unassigned storage blocks is performed using an atomic instruction in which a first value is compared with a second value to produce a comparison result and, depending on the comparison result, replaced with a third value.
References Cited (Backward Citations)
US5063500A
Cited
US5088036A
Cited
US5371885A
Cited
US5345588A
Cited
US5247634A
Cited
US5404521A
Cited
US5367637A
Cited
US5325526A
Cited
US5652883A
Cited
US5561786A
Cited
US5440692A
Cited
US5430871A
Cited
US5561785A
Cited
US5485626A
Cited
US5608893A
Cited
US5577243A
Cited
US5623654A
Cited
US5809554A
Cited
US5625819A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-05-16 | 2003-11-15 | 2004-05-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-16 | 2007-11-15 | 2008-05-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-16 | 2011-11-15 | 2012-05-16 | $7700.00 | Window Closed / Lapsed |