Unified working storage management

• US 5,109,336 A
• Filed: 04/28/1989
• Issued: 04/28/1992
• Est. Priority Date: 04/28/1989
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Zelek, Mark C., Van Leer, Paul W., Guenther, Robert L., Spano, Joseph P., Rondeau, Stephen B.
• Primary Examiner(s): Bowler, Alyssa H.
• Application Number:
  US07/344,715
• Time in Patent Office: 1,096 Days
• Field of Search: 365/230.03
• US Class Current: 711/171
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence

Abstract

A process of efficiently managing working storage that unifies the use of queues of fixed size free storage blocks and a global list of blocks of random size. The process implements continuous garbage collection that continually purges unused storage blocks from the fixed size queues to ensure maximum free storage availability. Data processing system throughput is enhanced by reducing the processor overhead required to allocate and return free storage blocks and by reducing the overhead required to manage temporary extensions of working storage.

Claims

1. A process for controlling memory in a data processing system of the type including one or more processing units and a memory, said data processing system executing a plurality of tasks with each task issuing one or more requests for memory of a specified size, wherein a portion of said memory is designated working storage, wherein the data processing system maintains a plurality of queues, each queue containing an ordered list of addresses of working storage blocks of a specified size, and wherein the data processing system maintains an ordered free storage list containing the addresses of all working storage blocks not in the plurality of queues and ordered by said addresses, the process comprising the steps of:

allocating a working storage block to one of said plurality of tasks in response to a request for memory of a specified size, said allocating step determining a working storage block address of a working storage block of at least said specified size;

determining periodically a spill address for each of said plurality of queues as a function of the amount of storage addressed by said queue, said spill address representing a limiting address controlling placement of deallocated working storage blocks in one of said plurality of queues or in said free storage list;

deallocating an allocated working storage block having an address and size when no longer required by said one of said plurality of tasks;

testing each of said plurality of queues and selecting one of said plurality of queues having a size larger than the size of said deallocated working storage block;

inserting the address of said deallocated working storage block in the selected one of said plurality of queues, when said working storage block is deallocated as long as the address of said working storage block is between the beginning of working storage and said spill address and said size of said working storage block is less than or equal to the largest size block specified for any queue; and

inserting said address as an address entry in said free storage list otherwise.

2. The process of claim 1, wherein said step of determining periodically a spill address for each of said plurality of queues comprises the steps of:

setting said spill address equal to the address of a working storage block upon allocation by said data processing system if said block is the only block of the specified size that has been allocated;

setting said spill address equal to the address of said allocated block upon allocation by said data processing system if said address is further from the beginning of said free storage list than a current queue spill address, otherwise maintaining the current queue spill address;

modifying periodically said spill address of said queue by determining the total amount of storage addressed by said queue and adjusting the spill address to be closer than said current spill address to the beginning of said free storage list by said total amount.

3. The process of claim 2, further comprising the steps of:

testing a first address in said ordered list of addresses for each of said plurality of queues against the spill address determined for that queue; and

inserting into said free storage list the addresses of all storage blocks in each of said queues and removing them from said queues if said modified spill address for that queue is nearer the beginning of said free storage list than the first block in said ordered list.

4. The process of claim 1 wherein the step of inserting the address of said deallocated working storage block into the one of said queues comprises the steps of:

inserting said address as the first entry in said queue; and

shifting all previous entries to subordinate positions in said queue.

5. The process of claim 1 where the step of inserting said address into said free storage list comprises the steps of:

traversing said ordered free storage list comparing the address of the deallocated working storage block with a current free storage list address and an adjacent previous free storage list address until said deallocated storage block address is between said current and said previous free storage list addresses; and

inserting the address of the deallocated working storage block between said previous address and said current address.

6. The process of claim 5 wherein each entry in said ordered free storage list has a forward pointer indicating a next adjacent entry to said entry in said ordered list and a backward pointer indicating a previous adjacent entry to said entry in said ordered list, and wherein the step of inserting into said free storage list comprises the steps of:

traversing said ordered free storage list using the forward pointers of each entry in said working storage list until an entry is found whose address is nearer the beginning of the ordered list than the deallocated block and whose forward pointer points to a block with an address farther from the beginning of the list then the deallocated block;

modifying the forward pointer of the located block to be equal to the address of the deallocated block;

modifying the forward pointer of the deallocated block to be the address of the block previously pointed to by the located block;

modifying the backward pointer of the deallocated block to be the address of the located block; and

modifying the backward pointer of the block previously pointed to by the located block to be the address of the deallocated block.

7. The process of claim 5 wherein each of said plurality of queues contains a block entry pointer to the ordered free storage list indicating the first working storage block potentially having available storage blocks of the size stored in said queue and wherein the step of examining the forward pointers is preceded by the steps of:

examining the block entry pointer of each of said plurality of queues to determine the largest pointer less than the address of said deallocated working storage block; and

beginning examining at the free storage list entry pointed to by said block entry position.

8. The process of claim 1 wherein each of said plurality of queues contains a block entry pointer to the ordered free storage list indicating the first working storage block potentially having available storage blocks of the size stored in said queue.

9. The process of claim 1, further comprising the steps of:

testing free storage list entries adjacent to said address entry inserted in said free storage list to determine whether or not a working storage block at one of said adjacent addresses is contiguous with the working storage block at said inserted address; and

merging said adjacent working storage block with said inserted working storage block if it is contiguous.

10. The process of claim 9, wherein the step of merging comprises the steps of:

comparing said adjacent address with said inserted address and selecting as a new block address the address closest to the origin of working storage;

summing the sizes of the adjacent and inserted working storage blocks and assigning the sum as the size of the new block; and

deleting the address entry not selected in the comparing step from the free storage list.

11. A process for controlling the allocation and deallocation of memory space in a data processing system of the type including one or more processing units and a memory, said data processing system executing a plurality of tasks with each task requiring allocation of a portion of said memory to said task by issuing one or more requests for allocation of a storage block,

said process comprising the steps of:

designating a block of memory of predetermined size as free storage, said free storage block having a beginning address and capable of being divided into a plurality of storage blocks each having an address;

establishing a free storage list containing the addresses of all unallocated storage blocks in said free storage;

establishing a plurality of queues, each queue designated to contain entries of available storage blocks of a different fixed size and each having a spill address;

performing the following steps for each request for allocation of a storage block of a requested size by one of said tasks;

determining whether an available storage block exists in a fixed size queue containing blocks of storage of the nearest larger size than said requested size;

if said queue is empty and said free storage is at least as large as said requested size, allocating storage of said requested size from said free storage;

if said free storage is not as large as said requested size, obtaining extended storage and allocating storage of said requested size from said extended free storage;

resetting said spill address for said fixed size queue of the nearest larger size as the address of said allocated storage, if said storage is the only one of said size allocated;

otherwise resetting said spill address as the address of storage just allocated or the old spill address, whichever is further from beginning address of free storage;

performing the following steps for each deallocation of a storage block of a size given;

inserting said storage block into said free storage list if the size of said storage block is greater than the size of the largest size fixed size queue;

rounding said given size to the nearest larger fixed size queue;

inserting said storage block into said fixed size queue, as the first element in said queue if the address of said storage is between said beginning address of free storage and said spill address;

otherwise inserting said storage into said free storage list;

modifying periodically each of said spill addresses of said fixed size queues by determining the total amount of storage contained in all storage blocks in said queue, and adjusting said spill address closer to said beginning address of free storage by said total amount;

returning storage from said fixed size queue to said free storage list if the address of said first block of storage in said queue is not between the beginning address of free storage and said adjusted spill address.

12. The process of claim 11, further comprising the steps of:

testing free storage list entries adjacent to said address entry inserted in said free storage list to determine whether or not a working storage block at one of said adjacent addresses are contiguous with the working storage block at said inserted address; and

merging said adjacent working storage block with said inserted working storage block if it is contiguous.

13. The process of claim 12, comparing said adjacent address with said inserted address and selecting as a new block address the address closest to the origin of working storage;

summing the sizes of the adjacent and inserted working storage blocks and assigning the sum as the size of the new block; and

deleting the address entry not selected in the comparing step from the free storage list.