System for allocating and returning storage and collecting garbage using subpool of available blocks

• US 5,561,785 A
• Filed: 10/29/1992
• Issued: 10/01/1996
• Est. Priority Date: 10/29/1992
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Blandy, Geoffrey O., Samodovitz, Arthur J.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US07/969,870
• Time in Patent Office: 1,433 Days
• Field of Search: 395/600, 395/425, 395/200, 395/497.02, 395/497.01, 395/876, 395/736, 395/859, 395/292, 364/DIG. 1
• US Class Current: 711/170
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory

Abstract

A computer storage management system establishes a subpool of available blocks of one size from a multiplicity of different storage frames. The available blocks are queued in the subpool. A garbage collection routine periodically or occasionally determines which of the frames having blocks on the subpool queue are completely available based on the number of available blocks on the queue for each frame. Then, the garbage collection routine removes from the queue and thereby reclaims the blocks of the frames which are completely available. The garbage collection routine also requeues the blocks from the other frames such that the blocks of these other frames are clustered with the other blocks of the same frame. Blocks are allocated from the front of the queue. Blocks of the one size from frames other than those represented at or near the end of the queue are returned to the front of the queue after use. Blocks of the one size from frames represented at or near the end of the queue are returned to a different position than the other blocks and allocated after other blocks on the queue. Consequently, as blocks are subsequently allocated from and some returned to the front of the queue, the blocks from the frames at or near the end of the queue are not allocated assuming the subpool is under utilized.

Claims

1. A computer storage management system comprising:

means for queuing available blocks of one size from a multiplicity of different storage frames;

means for allocating blocks from a position in the queue to satisfy need for said blocks;

means for returning at least some blocks of said one size from different frames to said position in said queue after the need for said some blocks ends, a plurality of the returned blocks not being adjacent to a block of the same frame; and

garbage collection means, operated after blocks have been allocated and returned and subsequently after other blocks have been allocated and returned, for removing from said queue all blocks of a plurality of frames which are completely available and requeuing said queue such that all blocks, including the nonadjacent blocks, of a plurality of partially available frames are in clusters for respective frames.

2. A system as set forth in claim 1 wherein the garbage collection means is invoked periodically or occasionally, and the returning means returns the completely available frames to an available list or pool of frames of main storage during the next invocation of the garbage collection means.

3. A system as set forth in claim 1 wherein the queuing means comprises:

means, responsive to a request for a storage block of said one size and an absence of blocks in said queue to satisfy said request, for selecting a completely available frame from main storage, allocating a block of said frame to satisfy said request, dividing the remainder of said frame into other blocks of said one size, and queuing said other blocks in said queue.

4. A computer storage management system comprising:

means for queuing available blocks of one size from a multiplicity of different storage frames;

means for allocating blocks from a position in the queue to satisfy need for said blocks;

means for returning at least some blocks of said one size from different frames to said position in said queue after the need for said some blocks ends, a plurality of the returned blocks not being adjacent to a block of the same frame; and

garbage collection means, operated after blocks have been allocated and returned and subsequently after other blocks have been allocated and returned, for removing from said queue all blocks of a plurality of frames which are completely available and requeuing said queue such that all blocks, including the nonadjacent blocks of a plurality of partially available frames are in clusters for respective frames; and

wherein

the returning means returns blocks from one or more frames having blocks clustered at or near another position of said queue to a different position than the first said position of said queue; and

the allocating means allocates said blocks returned to said different position and the clustered blocks of said one or more frames after the returned and clustered blocks at and near the first said position of said queue.

5. A system as set forth in claim 4 wherein the first said position of said queue is one end of said queue, and said other position is an opposite end of said queue.

6. A system as set forth in claim 4 wherein the garbage collection means is invoked periodically or occasionally, and the returning means returns the completely available frames to an available list or pool of frames of main storage during the next invocation of the garbage collection means;

and

the garbage collection means queues the blocks in each completely available frame from one another in another queue at garbage collection time, and if a request is made for a block of said one size, the first said queue is empty and there are no blocks at said different position, the allocating means satisfies the request from one of the completely available frames on said other queue, said one frame being removed from the first said queue during the last garbage collection.

7. A computer storage management system comprising:

means for queuing available blocks of one size from a multiplicity of different storage frames;

means for allocating blocks from a position in the queue to satisfy need for said blocks;

means for returning at least some blocks of said one size from different frames to said position in said queue after the need for said some blocks ends, a plurality of the returned blocks not being adjacent to a block of the same frame; and

garbage collection means, operated after blocks have been allocated and returned and subsequently after other blocks have been allocated and returned, for removing from said queue all blocks of a plurality of frames which are completely available and requeuing said queue such that all blocks, including the nonadjacent blocks, of all partially available frames are in clusters for respective frames.

8. A computer storage management system comprising:

means for queuing available blocks of one size from a multiplicity of different storage frames;

means for allocating blocks from a position in the queue to satisfy need for said blocks;

means for returning at least some blocks of said one size from different frames to said position in said queue after the need for said some blocks ends, a plurality of the returned blocks not being adjacent to a block of the same frame; and

garbage collection means, operated after blocks have been allocated and returned and subsequently after other blocks have been allocated and returned, for removing from said queue all blocks of a plurality of frames which are completely available and requeuing said queue such that all blocks, including the nonadjacent blocks, of a plurality of partially available frames are in clusters for respective frames; and

wherein the frames were originally obtained from an available list or available pool of frames of main storage; and

further comprising means for returning the completely available frames to said available list or available pool of frames of main storage.

9. A computer program product for storage management, said computer program product comprising:

a computer readable medium;

first program instruction means for instructing a computer processor to queue available blocks of one size from a multiplicity of different storage frames;

second program instruction means for instructing a computer processor to allocate blocks from a position in the queue to satisfy need for said blocks;

third program instruction means for instructing a computer processor to return at least some blocks of said one size from different frames to said position in said queue after the need for said some blocks ends, a plurality of the returned blocks not being adjacent to a block of the same frame; and

fourth program instruction means for instructing a computer processor, after blocks have been allocated and returned and subsequently after other blocks have been allocated and returned, to remove from said queue all blocks of a plurality of frames which are completely available and requeue said queue such that all blocks, including the nonadjacent blocks, from a plurality of partially available frames are in clusters for respective frames; and

wherein each of said program instruction means is recorded on said medium in executable form.

10. A computer program product as set forth in claim 9 wherein

said third program instruction means instructs the associated processor to return blocks from one or more frames having blocks clustered at or near another position of said queue to a different position than the first said position of said queue;

and

said second program instruction means instructs the associated processor to allocate said blocks returned to said different position and the clustered blocks of said one or more frames after the returned and clustered blocks at and near the first said position of said queue.

11. A computer program product as set forth in claim 9 wherein said fourth program instruction means instructs the associated processor to requeue said queue such that all blocks of all partially available frames are in clusters for respective frames.

12. A computer program product as set forth in claim 9 wherein said frames were originally obtained from an available list or available pool of main storage;

and

further comprising fifth program instruction means for instructing a computer processor to return the completely available frames to said available list or available pool of frames of main storage; and

wherein

the fourth program instruction means is invoked periodically or occasionally;

the fifth program instruction means instructs the associated processor to return the completely available frames to said available list or available pool of frames of main storage during the next invocation of the fourth program instruction means; and

said fifth program instruction means is recorded on said medium in executable form.

13. A computer program product as set forth in claim 9 wherein the first program instruction means comprises:

fifth program instruction means for instructing a computer processor to respond to a request for a storage block of said one size and an absence of blocks in said queue to satisfy said request, by selecting a completely available frame from main storage, allocating a block of said frame to satisfy said request, dividing the remainder of said frame into other blocks of said one size, and queuing said other blocks in said queue; and

wherein

said fifth program instruction means is recorded on said medium in executable form.

14. A computer program product as set forth in claim 9 wherein said program product, when loaded into a computer, forms part of a computer operating system.

15. A computer program product for storage management, said computer program product comprising:

a computer readable medium;

first program instruction means for instructing a computer processor to queue available blocks of one size from a multiplicity of different storage frames;

second program instruction means for instructing a computer processor to allocate blocks from one end of the queue to satisfy need for said blocks;

third program instruction means for instructing a computer processor to return at least some blocks of said one size from different frames to said one end of said queue after the need for said some blocks ends, a plurality of the returned blocks not being adjacent to a block of the same frame; and

fourth program instruction means for instructing a computer processor, after blocks have been allocated and returned and subsequently after other blocks have been allocated and returned, to remove from said queue all blocks of a plurality of frames which are completely available and requeue said queue such that all blocks, including the nonadjacent blocks, from a plurality of partially available frames are in clusters for respective frames; and

wherein

said third program instruction means instructs the associated processor to return blocks from one or more frames having blocks clustered at or near an opposite end of said queue to a different position than said one end of said queue;

said second program instruction means instructs the associated processor to allocate said blocks returned to said different position and the clustered blocks of said one or more frames after the returned and clustered blocks at and near said one end of said queue; and

each of said program instruction means is recorded on said medium in executable form.

16. A method for managing computer storage, said method comprising the steps of:

queuing available blocks of one size from a multiplicity of different storage frames;

allocating blocks from a position in the queue to satisfy need for said blocks;

returning at least some blocks of said one size from different frames to said position in said queue after the need for said some blocks ends, a plurality of the returned blocks not being adjacent to a block of the same frame; and

after blocks have been allocated and returned and subsequently after other blocks have been allocated and returned, removing from said queue all blocks of a plurality of frames which are completely available and requeuing said queue such all blocks, including the nonadjacent blocks, of a plurality of partially available frames are in clusters for respective frames.

17. A method as set forth in claim 16 further comprising the steps of:

responsive to a request for a storage block of said one size and an absence of blocks in said queue to satisfy said request, selecting a completely available frame from main storage, allocating a block of said frame to satisfy said request, dividing the remainder of said frame into other blocks of said one size, and queuing said other blocks in said queue.

18. A method for managing computer storage, said method comprising the steps of:

queuing available blocks of one size from a multiplicity of different storage frames;

allocating blocks from a position in the queue to satisfy need for said blocks;

returning at least some blocks of said one size from different frames to said position in said queue after the need for said some blocks ends, a plurality of the returned blocks not being adjacent to a block of the same frame; and

after blocks have been allocated and returned and subsequently after other blocks have been allocated and returned, removing from said queue all blocks of a plurality of frames which are completely available and requeuing said queue such all blocks, including the nonadjacent blocks, of a plurality of partially available frames are in clusters for respective frames; and

wherein

the returning step returns blocks from one or more frames having blocks queued at or near another position of said queue to a different position than the first said position of said queue; and

the allocating step allocates said blocks returned to said different position and the clustered blocks of said one or more frames after the returned and clustered blocks at and near the first said position of said queue.

19. A method as set forth in claim 18 wherein the first said position of said queue is one end of said queue, and said other position is an opposite end of said queue.

20. A method for managing computer storage, said method comprising the steps of:

queuing available blocks of one size from a multiplicity of different storage frames;

allocating blocks from a position in the queue to satisfy need for said blocks;

returning at least some blocks of said one size from different frames to said position in said queue after the need for said some blocks ends, a plurality of the returned blocks not being adjacent to a block of the same frame; and

after blocks have been allocated and returned and subsequently after other blocks have been allocated and returned, removing from said queue all blocks of a plurality of frames which are completely available and regueuing said queue such all blocks, including the nonadjacent blocks, of all partially available frames are in clusters for respective frames.

21. A method for managing computer storage, said method comprising the steps of:

queuing available blocks of one size from a multiplicity of different storage frames;

allocating blocks from a position in the queue to satisfy need for said blocks;

returning at least some blocks of said one size from different frames to said position in said queue after the need for said some blocks ends, a plurality of the returned blocks not being adjacent to a block of the same frame; and

after blocks have been allocated and returned and subsequently after other blocks have been allocated and returned, removing from said queue all blocks of a plurality of frames which are completely available and requeuing said queue such all, blocks, including the nonadjacent blocks, of a plurality of partially available frames are in clusters for respective frames; and

wherein said frames were originally obtained from an available list or available pool of frames of main storage; and

further comprising the step of returning the completely available frames to said available list or available pool of frames of main storage and wherein the removing and requeuing steps are performed periodically or occasionally, and further comprising the step of returning completely available frames to said available list or available pool of frames of main storage during the next performance of the removing and requeuing steps.

22. A computer storage management system comprising:

means for allocating blocks from a queue to satisfy a need for said blocks, said queue comprising available blocks of one size from a multiplicity of different storage frames;

means for returning at least some blocks of said one size from a plurality of different frames to a predetermined position in said queue after the need for said some blocks ends, a plurality of the returned blocks not being adjacent to a block of the same frame; and

means, operated after blocks have been allocated and returned and subsequently after other blocks have been allocated and returned, for removing from said queue all blocks of a plurality of frames which are completely available and requeuing said queue such that all blocks, including the nonadjacent blocks, of a plurality of partially available frames are in clusters for respective frames; and

wherein the allocating means re-allocates said some blocks before allocating clustered blocks of a plurality of said frames.

23. A system as set forth in claim 22 wherein:

the allocating means allocates blocks from a fixed position in said queue;

the returning means returns blocks from one or more frames to a different position than said predetermined position of said queue, said one or more frames having blocks clustered away from said fixed position; and

the allocating means re-allocates said some blocks before re-allocating said blocks returned to said different position and the clustered blocks of said one or more frames.

24. A system as set forth in claim 23 wherein the allocating means also allocates clustered blocks of frames near said fixed position before allocating said blocks returned to said different position and the clustered blocks of said one or more frames.

25. A computer storage management system comprising:

means for allocating blocks from a predetermined position in a queue to satisfy a need for said blocks, said queue comprising available blocks of one size from a multiplicity of different storage frames;

means for returning at least some blocks of said one size from a plurality of different frames to said predetermined position in said queue after the need for said some blocks ends, a plurality of the returned blocks not being adjacent to a block of the same frame; and

means, operated after blocks have been allocated and returned and subsequently after other blocks have been allocated and returned, for removing from said queue all blocks of a plurality of frames which are completely available and requeuing said queue such that all blocks, including the nonadjacent blocks, of a plurality of partially available frames are in clusters for respective frames; and

wherein

the allocating means re-allocates said some blocks before allocating clustered blocks of a plurality of said frames;

the returning means returns blocks from one or more frames to a different position than said predetermined position of said queue, said one or more frames having blocks clustered away from said predetermined position;

the allocating means re-allocates said some blocks before re-allocating said blocks returned to said different position and the clustered blocks of said one or more frames.

26. A computer implemented method for managing storage, said method comprising the steps of:

queuing all blocks of one size of a multiplicity of partially available frames of storage into clusters for respective frames;

after the quelling step, allocating blocks from the queue to satisfy a need for said blocks and returning at least some blocks of said one size from a plurality of different frames to a predetermined position in said queue after the need for said some blocks ends, a plurality of the returned blocks not being adjacent to a block of the same frame, and re-allocating said some blocks before allocating clustered blocks of a plurality of said frames; and

after blocks have been allocated, returned and re-allocated, removing from said queue all blocks of a plurality of frames which are completely available and requeuing said queue such that all blocks, including nonadjacent blocks, of a plurality of partially available frames are in clusters for respective frames.

27. A computer implemented method for managing storage, said method comprising the steps of:

queuing all blocks of one size of a multiplicity of partially available frames of storage into clusters for respective frames;

after the queuing step, allocating blocks from a fixed position in the queue to satisfy a need for said blocks and returning at least some blocks of said one size from a plurality of different frames to a predetermined position in said queue after the need for said some blocks ends, a plurality of the returned blocks not being adjacent to a block of the same frame, and re-allocating said some blocks before allocating clustered blocks of a plurality of said frames;

after blocks have been allocated, returned and re-allocated, removing from said queue all blocks of a plurality of frames which are completely available and requeuing said queue such that all blocks, including nonadjacent blocks, of a plurality of partially available frames are in clusters for respective frames;

returning blocks from one or more frames to a different position than said predetermined position of said queue, said one or more frames having blocks clustered away from said fixed position; and

re-allocating said some blocks before re-allocating said blocks returned to said different position and the clustered blocks of said one or more frames.

28. A method as set forth in claim 27 wherein the allocating step also allocates clustered blocks of frames near said fixed position before allocating said blocks returned to said different position and the clustered blocks of said one or more frames.

29. A method as set forth in claim 27 wherein said predetermined position is said fixed position.