System for performing action by sorting actions into immediate and deferred queues, processing immediate queue while still sorting, and appending deferred queue to immediate after sorting
First Claim
1. In a procedural environment having an action processing capacity and a plurality of N actions to perform, wherein the actions may be performed in any order, wherein a variable cost Fn =(0,1) can be assigned for each said action, wherein Fn =0 represents the lowest cost, and wherein N and n≦
- N are positive integers, a machine-implemented method for processing said actions, said method comprising the steps of;
(a) arranging a plurality of M≦
N of said actions into a processing queue ordered by said variable-cost Fm, wherein M and m≦
M are positive integers, said arranging step comprising the steps of;
(a.1) apportioning said M actions into an immediate queue and a deferred queue by performing steps comprising;
(a.1.1) defining the variable-cost threshold T=[0,1];
(a.1.2) placing the mth said action in said immediate queue if Fm ≦
T;
(a.1.3) placing the mth said action at the beginning of said immediate queue if Fm =0; and
(a.1.4) otherwise placing said mth action in said deferred queue;
(a.2) sorting said actions in order of said variable cost Fm in said deferred queue after completion of said apportioning step (a.1); and
(a.3) appending said deferred queue to said immediate queue to represent said processing queue after completion of said sorting step (a.2);
(b) before completion of said apportioning step (a.1) performing repeatedly the steps of(b.1) performing to completion the first action in said immediate queue, and(b.2) removing said action from said processing queue.
1 Assignment
0 Petitions
Accused Products
Abstract
A procedure for the optimal processing of variable-cost actions such as encountered in the storage reclamation procedures for a multivolume data library. The procedure introduces a temporary processing queue to minimize idle processing capacity during the scanning and sorting of a large plurality of variable-cost actions such as the recycling of a plurality of data storage volumes each having a variable recycle processing cost related to the action of valid data remaining on the volume. Volumes (actions) are selected for the immediate queue according to a dynamically-adjusted threshold test for the processing cost. This processing cost threshold is dynamically adjusted to optimize the immediate queue in relation to the available processing capacity. After scanning and sorting all volumes according to recycle processing cost, the temporary (immediate) queue is updated to a final recycle processing queue by appending a sorted deferred queue to the remainder of the immediate queue. The procedure of this invention minimizes idle processing capacity during the queue-building interval, thereby optimizing the number of recovered data storage volumes released in a given time interval.
-
Citations
20 Claims
-
1. In a procedural environment having an action processing capacity and a plurality of N actions to perform, wherein the actions may be performed in any order, wherein a variable cost Fn =(0,1) can be assigned for each said action, wherein Fn =0 represents the lowest cost, and wherein N and n≦
- N are positive integers, a machine-implemented method for processing said actions, said method comprising the steps of;
(a) arranging a plurality of M≦
N of said actions into a processing queue ordered by said variable-cost Fm, wherein M and m≦
M are positive integers, said arranging step comprising the steps of;(a.1) apportioning said M actions into an immediate queue and a deferred queue by performing steps comprising; (a.1.1) defining the variable-cost threshold T=[0,1]; (a.1.2) placing the mth said action in said immediate queue if Fm ≦
T;(a.1.3) placing the mth said action at the beginning of said immediate queue if Fm =0; and (a.1.4) otherwise placing said mth action in said deferred queue; (a.2) sorting said actions in order of said variable cost Fm in said deferred queue after completion of said apportioning step (a.1); and (a.3) appending said deferred queue to said immediate queue to represent said processing queue after completion of said sorting step (a.2); (b) before completion of said apportioning step (a.1) performing repeatedly the steps of (b.1) performing to completion the first action in said immediate queue, and (b.2) removing said action from said processing queue. - View Dependent Claims (2, 3)
- N are positive integers, a machine-implemented method for processing said actions, said method comprising the steps of;
-
4. In a data storage library having a recycle processing capacity and a plurality N of volumes for storing data, wherein a fraction Fn =[0,1] of the nth said volume contains valid data and wherein N and n≦
- N are positive integers, a machine-implemented method for compacting said valid data to recover empty volumes, said method comprising the steps of;
(a.1) arranging a plurality M≦
N of said volumes into a recycle processing queue ordered by said fraction Fm, wherein M and m≦
M are positive integers, said arranging step comprising the steps of;(a.1.1) apportioning said M volumes into an immediate queue and a deferred queue by performing steps comprising; (a.1.2) defining a valid data occupancy fraction threshold T=[0,1]; (a.1.3) placing the mth said volume in said immediate queue if Fm ≦
T;
queue if Fm =0; and(a.1.4)otherwise placing said mth volume in said deferred queue; (a.2) sorting said volumes in order of said faction Fm in said deferred queue after completion of said apportioning step (a.1); and (a.3) appending said deferred queue to said immediate queue to form said recycle processing queue after completion of said sorting step (a.2); (b) before completion of said apportioning step (a.1), performing repeatedly the steps of (b.1) transferring said valid data from the first volume in said immediate queue to a compaction target volume, and (b.2) removing said first volume from said recycle processing queue. - View Dependent Claims (5, 6)
- N are positive integers, a machine-implemented method for compacting said valid data to recover empty volumes, said method comprising the steps of;
-
7. In an apparatus for automatic management of a data storage library having a recycle processing capacity and a plurality N of volumes for storing data, wherein a fraction Fn =[0,1] of the nth said volume contains valid data and wherein N and n≦
- N are positive integers, a storage recovery system for compacting said valid data to recover empty volumes for reuse, said system comprising;
queuing means for arranging a plurality M≦
N of said volumes into a recycle processing queue ordered by said fraction Fm, wherein M and m≦
M are positive integers;recycling means coupled to said queuing means for transferring said valid data from the first volume in said recycle processing queue to a compaction target volume and for removing said first volume from said recycle processing queue; selection means in said queuing means for apportioning said plurality M of volumes into an immediate queue and a deferred queue; launching means coupled to said queuing means and said recycling means for starting said recycling means before formation of said recycle processing queue, whereby said first volume is taken from said immediate queue; sorting means in said queuing means for sorting the volumes in order of said fraction Fm =[0,1] in said deferred queue and for appending said deferred queue to said immediate queue to firm said recycle processing queue; thresholding means coupled to said selection means for comparing said fraction Fm for the mth said volume with a valid data occupancy fraction threshold T=[0,1], whereby said mth volume is added to said immediate queue if Fm ≦
T and otherwise is added to said deferred queue; andbypass means coupled to said thresholding means for adding said mth volume to the front of said immediate queue when Fm =0. - View Dependent Claims (8, 9)
- N are positive integers, a storage recovery system for compacting said valid data to recover empty volumes for reuse, said system comprising;
-
10. An automated data storage tape library having a recycle processing capacity and a plurality N of tape volumes for storing data, wherein a fraction Fn =[0,1] of the nth said tape volume contains valid data and wherein N and n≦
- N are positive integers, said tape library including volume recovery means for compacting said valid data to recover empty tape volumes for reuse, wherein said volume recovery means comprises;
queuing means for arranging a plurality M≦
N of said tape volumes into a recycle processing queue ordered by said fraction Fm, wherein M and m≦
M are positive integers;recycling means coupled to said queuing means for transferring said valid data from the first tape volume in said recycle processing queue to a compaction target volume and for removing said first tape volume from said recycle processing queue; selection means in said queuing means for apportioning said plurality M of tape volumes into an immediate queue and a deferred queue; launching means coupled to said queuing means and said recycling means for starting said recycling means before formation of said recycle processing queue, whereby said first tape volume is taken from said immediate queue; sorting means in said queuing means for sorting the tape volumes in order of said fraction Fm =[0,1] in said deferred queue and for appending said deferred queue to said immediate queue to form said recycle processing queue; thresholding means coupled to said selection means for comparing said fraction Fm for the mth said tape volume with a valid data fraction occupancy threshold T=[0,1], whereby said mth tape volume is added to said immediate queue if Fm ≦
T and otherwise is added to said deferred queue; andbypass means coupled to said thresholding means for adding said mth tape volume to the front of said immediate queue when Fm =0. - View Dependent Claims (11, 12)
- N are positive integers, said tape library including volume recovery means for compacting said valid data to recover empty tape volumes for reuse, wherein said volume recovery means comprises;
-
13. An automated optical data storage library having a recycle processing capacity and a plurality N of optical volumes for storing data, wherein a fraction Fn =[0,1] of the nth said optical volume contains valid data and wherein N and n≦
- N are positive integers said optical data storage library including volume recovery means for compacting said valid data to recover empty optical volumes for reuse wherein said volume recovery means comprises;
queuing means for arranging a plurality M≦
N of said optical volumes into a recycle processing queue ordered by said fraction Fm, wherein M and m≦
M are positive integers;recycling means coupled to said queuing means for transferring said valid data tom the first optical volume in said recycle processing queue to a compaction target volume and for removing said first optical volume from said recycle processing queue; selection means in said queuing means for apportioning said plurality M of optical volumes into an immediate queue and a deferred queue; launching means coupled to said queuing means and said recycling means for starting said recycling means before formation of said recycle processing queue, whereby said first optical volume is taken from said immediate queue; sorting means in said queuing means for sorting the optical volumes in order of said fraction Fm =[0,1] in said deferred queue and for appending said deferred queue to said immediate queue to form said recycle processing queue; thresholding means coupled to said selection means for comparing said fraction Fm for the mth said optical volume with a valid data fraction occupancy threshold T=[0,1], whereby said mth optical volume is added to said immediate queue if Fm ≦
T and otherwise is added to said deferred queue; andbypass means coupled to said thresholding means for adding said mth optical volume to the front of said immediate queue when Fm =0. - View Dependent Claims (14, 15)
- N are positive integers said optical data storage library including volume recovery means for compacting said valid data to recover empty optical volumes for reuse wherein said volume recovery means comprises;
-
16. A machine-implemented method for reclaiming data storage volumes in a multi-volume data storage library having a plurality of said data storage volumes, each volume having a variable-cost of reclaiming valid data thereon, said method comprising the steps of:
arranging a plurality of data storage volumes into a processing queue and ordering said volumes according to their variable-costs by performing steps comprising; apportioning the volumes into an immediate queue and a deferred queue by performing steps comprising; defining a variable-cost threshold; for each data storage volume, performing steps comprising; placing the volume in the immediate queue if its variable-cost does not exceed the variable-cost threshold; otherwise placing the volume in the deferred queue; and reconfiguring the processing queue by sorting the volumes in the deferred queue in order of variable cost and then appending the sorted deferred queue to the immediate queue; and repeatedly performing the steps of (a) copying valid data from the first volume in the processing queue to a designated compaction target volume, and (b) removing the first volume from said processing queue. - View Dependent Claims (17, 18, 19, 20)
Specification