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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.