System and method for overflow queue processing

• US 5,893,924 A
• Filed: 08/29/1997
• Issued: 04/13/1999
• Est. Priority Date: 07/28/1995
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Vakkalagadda, Anuradha V.
• Primary Examiner(s): Ellis, Richard L.
• Assistant Examiner(s): Winder, Patrice L.
• Application Number:
  US08/921,258
• Time in Patent Office: 592 Days
• Field of Search: 711/165, 711/154, 711/159, 395/874, 395/877
• US Class Current: 711/165
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0674 Disk device
• CPC Class Codes: G06F 5/06 for changing the speed of data flow, i.e. speed regularising or timing, e.g. delay lines, FIFO buffers; over- or underrun control therefor G06F7/78 takes precedence

Abstract

A database management system is described. The system includes a computer storage medium having a primary storage medium and an overflow storage medium. The system also includes a manager for managing a plurality of data structures (queues) stored in the computer storage medium. The manager receives a request to store a data object in a target data structure. The manager determines whether an overflow mode condition currently exists. If an overflow mode condition does not currently exist, then the manager determines whether a combined size of all data structures stored in the primary storage medium plus a size of the data object is greater than a predetermined threshold. If a combined size of all data structures stored in the primary storage medium plus a size of the data object is greater than a predetermined threshold, then the manager enters an overflow mode. Also, the manager selects one or more data structures currently stored in the primary storage medium, and moves the selected data structures from the primary storage medium to the overflow storage medium. The overflow storage medium is then directly accessed to process any subsequent actions involving these data structures.

Claims

1. A method for managing a plurality of data structures stored in a computer storage medium, the computer storage medium comprising a primary storage medium and an overflow storage medium, the method comprising the steps of:

(1) receiving a request to store a data object in a target data structure;

(2) determining whether an overflow mode condition currently exists;

(3) if an overflow mode condition does not currently exist, then determining whether a combined size of all data structures stored in the primary storage medium plus a size of the data object is greater than a predetermined threshold;

(4) if a combined size of all data structures stored in the primary storage medium plus a size of the data object is greater than a predetermined threshold, then;

(a) entering an overflow mode such that an overflow mode condition exists;

(b) selecting one or more data structures currently stored in the primary storage medium; and

(c) moving said selected data structures from the primary storage medium to the overflow storage medium, wherein said selected data structures are retained in the overflow storage medium and not moved back to the primary storage medium as long as the overflow mode condition exists, even if adequate storage capacity becomes available in the primary storage medium.

2. The method of claim 1, wherein said data structures represent queues.

3. The method of claim 1, wherein said predetermined threshold is equal to a percentage of a total storage capacity of said primary storage medium.

4. The method of claim 1, wherein step (b) comprises the step of:

selecting one or more data structures having the greatest number of elements until a size of said selected data structures is greater than a predetermined amount.

5. The method of claim 1, wherein step (b) comprises the step of:

selecting a predetermined number of data structures having the greatest number of elements.

6. The method of claim 1, further comprising the step of:

(5) if a combined size of all data structures stored in the primary storage medium plus a size of the data object is not greater than a predetermined threshold, then storing the data object in said target data structure in said primary storage medium.

7. The method of claim 1, further comprising the steps of:

(5) if an overflow mode condition currently exists, then determining whether the target data structure is stored in the overflow storage medium;

(6) if the target data structure is stored in the overflow storage medium, then determining whether the overflow storage medium has adequate available storage capacity to accommodate the data object;

(7) if the overflow storage medium has adequate available storage capacity to accommodate the data object, then storing the data object in the target data structure in the overflow storage medium, even if there is adequate storage capacity to store the data object in the primary storage medium; and

(8) if the overflow storage medium does not have adequate available storage capacity to accommodate the data object, then rejecting the data object, even if there is adequate storage capacity to store the data object in the primary storage medium.

8. The method of claim 7, wherein step (c) comprises the step of:

placing identifiers of said selected data structures in an overflow name list;

wherein step (5) comprises the step of;

checking said overflow name list to determine whether said target data structure is stored in the overflow storage medium.

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

(5) if an overflow mode condition currently exists, then determining whether the target data structure is stored in the overflow storage medium;

(6) if the target data structure is not stored in the overflow storage medium, then determining whether a combined size of all data structures stored in the primary storage medium plus a size of the data object is greater than a second predetermined threshold;

(7) if a combined size of all data structures stored in the primary storage medium plus a size of the data object is greater than the second predetermined threshold, then;

(I) selecting one or more second data structures currently stored in the primary storage medium;

(II) determining whether the overflow storage medium has sufficient available storage capacity to accommodate said selected second data structures; and

(III) if the overflow storage medium has sufficient available storage capacity to accommodate said selected second data structures, then moving said selected second data structures from the primary storage medium to the overflow storage medium.

10. The method of claim 9, further comprising the step of:

(8) if it is determined in step (6) that a combined size of all data structures stored in the primary storage medium plus a size of the data object is not greater than the second predetermined threshold, then storing the data object in the target data structure in the primary storage medium.

11. The method of claim 9, further comprising the steps of:

(8) if the overflow storage medium does not have sufficient available storage capacity to accommodate said selected second data structures, then determining whether the target data structure is one of said selected second data structures;

(9) if the target data structure is one of said selected second data structures, then rejecting the data object;

even if there is adequate storage capacity to store the data object in the primary storage medium; and

(10) if the target data structure is not one of said selected second data structures, then storing the data object in the target data structure in the primary storage medium.

12. The method of claim 9, wherein said first predetermined threshold is equal to said second predetermined threshold.

13. The method of claim 1, further comprising the steps of:

(5) receiving a request to retrieve a second data object from a second target data structure;

(6) determining whether an overflow mode condition currently exists;

(7) if an overflow mode condition does not currently exist, then accessing said primary storage medium to retrieve said second data object from said second target data structure;

(8) if an overflow mode condition currently exists, then determining whether said second target data structure is stored on said overflow storage medium;

(9) if said second target data structure is stored on said overflow storage medium, then accessing said overflow storage medium to retrieve said second data object from said second target data structure;

otherwise, accessing said primary storage medium to retrieve said second data object from said second target data structure.

14. The method of claim 1, further comprising the step of:

(5) if an overflow mode condition currently exists, then exiting the overflow mode condition if;

(I) no data structures are stored in the overflow storage medium; and

(II) a combined size of all data structures stored in the primary storage medium is less than the predetermined threshold.

15. A manager for managing a plurality of data structures stored in a computer storage medium, the computer storage medium comprising a primary storage medium and an overflow storage medium, the manager comprising:

receiving means for receiving a request to store a data object in a target data structure;

overflow determining means for determining whether an overflow mode condition currently exists;

threshold determining means, responsive to a determination that an overflow mode condition does not currently exist, for determining whether a combined size of all data structures stored in the primary storage medium plus a size of the data object is greater than a predetermined threshold;

overflow mode means, responsive to a determination that a combined size of all data structures stored in the primary storage medium plus a size of the data object is greater than a predetermined threshold, for entering an overflow mode such that an overflow mode condition exists;

data structure selecting means, responsive to said overflow mode means, for selecting one or more data structures currently stored in the primary storage medium; and

data structure moving means, responsive to said data structure selecting means, for moving said selected data structures from the primary storage medium to the overflow storage medium, wherein said selected data structures are retained in the overflow storage medium and not moved back to the primary storage medium as long as the overflow mode condition exists, even if adequate storage capacity becomes available in the primary storage medium.

16. The manager of claim 15, wherein said data structures represent queues.

17. The manager of claim 15, wherein said predetermined threshold is equal to a percentage of a total storage capacity of said primary storage medium.

18. The manager of claim 15, wherein said data structure selecting means comprises:

means for selecting one or more data structures having the greatest number of elements until a size of said selected data structures is greater than a predetermined amount.

19. The manager of claim 15, wherein said data structure selecting means comprises:

means for selecting a predetermined number of data structures having the greatest number of elements.

20. The manager of claim 15, further comprising:

means, responsive to a determination that a combined size of all data structures stored in the primary storage medium plus a size of the data object is not greater than a predetermined threshold, for storing the data object in said target data structure in said primary storage medium.

21. The manager of claim 15, further comprising:

content determining means, responsive to a determination that an overflow mode condition currently exists, for determining whether the target data structure is stored in the overflow storage medium;

means, responsive to a determination that the target data structure is stored in the overflow storage medium, for determining whether the overflow storage medium has adequate available storage capacity to accommodate the data object;

means, responsive to a determination that the overflow storage medium has adequate available storage capacity to accommodate the data object, for storing the data object in the target data structure in the overflow storage medium, even if there is adequate storage capacity to store the data object in the primary storage medium; and

means, responsive to a determination that the overflow storage medium does not have adequate available storage capacity to accommodate the data object, for rejecting the data object, even if there is adequate storage capacity to store the data object in the primary storage medium.

22. The manager of claim 21, wherein said data structure moving means places identifiers of said selected data structures in an overflow name list, and wherein said content determining means checks said overflow name list to determine whether said target data structure is stored in the overflow storage medium.

23. The manager of claim 15, further comprising:

means, responsive to a determination that an overflow mode condition currently exists, for determining whether the target data structure is stored in the overflow storage medium;

second predetermined threshold means, responsive to a determination that the target data structure is not stored in the overflow storage medium, for determining whether a combined size of all data structures stored in the primary storage medium plus a size of the data object is greater than a second predetermined threshold;

second data structure selecting means, responsive to a determination that a combined size of all data structures stored in the primary storage medium plus a size of the data object is greater than the second predetermined threshold, for selecting one or more second data structures currently stored in the primary storage medium;

overflow capacity determining means, responsive to said second data structure selecting means, for determining whether the overflow storage medium has sufficient available storage capacity to accommodate said selected second data structures; and

means, responsive to a determination that the overflow storage medium has sufficient available storage capacity to accommodate said selected second data structures, for moving said selected second data structures from the primary storage medium to the overflow storage medium.

24. The manager of claim 23, further comprising:

means, responsive to a determination by said second predetermined threshold means that a combined size of all data structures stored in the primary storage medium plus a size of the data object is not greater than the second predetermined threshold, for storing the data object in the target data structure in the primary storage medium.

25. The manager of claim 23, further comprising:

means, responsive to a determination that the overflow storage medium does not have sufficient available storage capacity to accommodate said selected second data structures, for determining whether the target data structure is one of said selected second data structures;

means, responsive to a determination that the target data structure is one of said selected second data structures, for rejecting the data object, even if there is adequate storage capacity to store the data object in the primary storage medium; and

means, responsive to a determination that the target data structure is not one of said selected second data structures, for storing the data object in the target data structure in the primary storage medium.

26. The manager of claim 23, wherein said first predetermined threshold is equal to said second predetermined threshold.

27. The manager of claim 15, further comprising:

means for receiving a request to retrieve a second data object from a second target data structure;

means for determining whether an overflow mode condition currently exists;

means, responsive to a determination that an overflow mode condition does not currently exist, for accessing said primary storage medium to retrieve said second data object from said second target data structure;

means, responsive to a determination that an overflow mode condition currently exists, for determining whether said second target data structure is stored on said overflow storage medium;

means, responsive to a determination that said second target data structure is stored on said overflow storage medium, for accessing said overflow storage medium to retrieve said second data object from said second target data structure;

otherwise, for accessing said primary storage medium to retrieve said second data object from said second target data structure.

28. The manager of claim 15, further comprising:

means, responsive to a determination that an overflow mode condition currently exists, for exiting the overflow mode condition if;

(I) no data structures are stored in the overflow storage medium; and

(II) a combined size of all data structures stored in the primary storage medium is less than the predetermined threshold.

29. A system, comprising:

a computer storage medium having a primary storage medium and an overflow storage medium; and

a manager for managing a plurality of data structures stored in said computer storage medium, said manager comprising;

receiving means for receiving a request to store a data object in a target data structure;

overflow determining means for determining whether an overflow mode condition currently exists;

threshold determining means, responsive to a determination that an overflow mode condition does not currently exist, for determining whether a combined size of all data structures stored in the primary storage medium plus a size of the data object is greater than a predetermined threshold;

overflow mode means, responsive to a determination that a combined size of all data structures stored in the primary storage medium plus a size of the data object is greater than a predetermined threshold, for entering an overflow mode such that an overflow mode condition exists;

data structure selecting means, responsive to said overflow mode means, for selecting one or more data structures currently stored in the primary storage medium; and

data structure moving means, responsive to said data structure selecting means, for moving said selected data structures from the primary storage medium to the overflow storage medium, wherein said selected data structures are retained in the overflow storage medium and not moved back to the primary storage medium as long as the overflow mode condition exists even if adequate storage capacity becomes available in the primary storage medium.

30. The system of claim 29, wherein said data structures represent queues.

31. The system of claim 29, wherein said predetermined threshold is equal to a percentage of a total storage capacity of said primary storage medium.

32. The system of claim 29, wherein said data structure selecting means comprises:

means for selecting one or more data structures having the greatest number of elements until a size of said selected data structures is greater than a predetermined amount.

33. The system of claim 29, wherein said data structure selecting means comprises:

means for selecting a predetermined number of data structures having the greatest number of elements.

34. The system of claim 29, wherein said manager further comprises:

means, responsive to a determination that a combined size of all data structures stored in the primary storage medium plus a size of the data object is not greater than a predetermined threshold, for storing the data object in said target data structure in said primary storage medium.

35. The system of claim 29, wherein said manager further comprises:

content determining means, responsive to a determination that an overflow mode condition currently exists, for determining whether the target data structure is stored in the overflow storage medium;

means, responsive to a determination that the target data structure is stored in the overflow storage medium, for determining whether the overflow storage medium has adequate available storage capacity to accommodate the data object;

means, responsive to a determination that the overflow storage medium has adequate available storage capacity to accommodate the data object, for storing the data object in the target data structure in the overflow storage medium, even if there is adequate storage capacity to store the data object in the primary storage medium; and

means, responsive to a determination that the overflow storage medium does not have adequate available storage capacity to accommodate the data object, for rejecting the data object, even if there is adequate storage capacity to store the data object in the primary storage medium.

36. The system of claim 29, wherein said manager further comprises:

means, responsive to a determination that an overflow mode condition currently exists, for determining whether the target data structure is stored in the overflow storage medium;

second predetermined threshold means, responsive to a determination that the target data structure is not stored in the overflow storage medium, for determining whether a combined size of all data structures stored in the primary storage medium plus a size of the data object is greater than a second predetermined threshold;

second data structure selecting means, responsive to a determination that a combined size of all data structures stored in the primary storage medium plus a size of the data object is greater than the second predetermined threshold, for selecting one or more second data structures currently stored in the primary storage medium;

overflow capacity determining means, responsive to said second data structure selecting means, for determining whether the overflow storage medium has sufficient available storage capacity to accommodate said selected second data structures; and

means, responsive to a determination that the overflow storage medium has sufficient available storage capacity to accommodate said selected second data structures, for moving said selected second data structures from the primary storage medium to the overflow storage medium.

37. The system of claim 36, wherein said manager further comprises:

means, responsive to a determination by said second predetermined threshold means that a combined size of all data structures stored in the primary storage medium plus a size of the data object is not greater than the second predetermined threshold, for storing the data object in the target data structure in the primary storage medium.

38. The system of claim 36, wherein said manager further comprises:

means, responsive to a determination that the overflow storage medium does not have sufficient available storage capacity to accommodate said selected second data structures, for determining whether the target data structure is one of said selected second data structures;

means, responsive to a determination that the target data structure is one of said selected second data structures, for rejecting the data object, even if there is adequate storage capacity to store the data object in the primary storage medium; and

means, responsive to a determination that the target data structure is not one of said selected second data structures, for storing the data object in the target data structure in the primary storage medium.

39. The system of claim 36, wherein said first predetermined threshold is equal to said second predetermined threshold.

40. The system of claim 35, wherein said data structure moving means places identifiers of said selected data structures in an overflow name list, and wherein said content determining means checks said overflow name list to determine whether said target data structure is stored in the overflow storage medium.

41. The system of claim 29, wherein said manager further comprises:

means for receiving a request to retrieve a second data object from a second target data structure;

means for determining whether an overflow mode condition currently exists;

means, responsive to a determination that an overflow mode condition does not currently exist, for accessing said primary storage medium to retrieve said second data object from said second target data structure;

means, responsive to a determination that an overflow mode condition currently exists, for determining whether said second target data structure is stored on said overflow storage medium; and

means, responsive to a determination that said second target data structure is stored on said overflow storage medium, for accessing said overflow storage medium to retrieve said second data object from said second target data structure;

otherwise, for accessing said primary storage medium to retrieve said second data object from said second target data structure.

42. The system of claim 29, wherein said manager further comprises:

means, responsive to a determination that an overflow mode condition currently exists, for exiting the overflow mode condition if;

(I) no data structures are stored in the overflow storage medium; and

(II) a combined size of all data structures stored in the primary storage medium is less than the predetermined threshold.