Parallel traversal of a dynamic list

• US 7,516,151 B2
• Filed: 11/01/2004
• Issued: 04/07/2009
• Est. Priority Date: 11/01/2004
• Status: Expired due to Fees

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Kim, Hyun J., Norton, Scott J.
• Primary Examiner(s): Chace; Christian P.
• Assistant Examiner(s): Vu; Bai D
• Application Number:
  US10/979,413
• Publication Number:
  US 20060095910A1
• Time in Patent Office: 1,618 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 9/485 Task life-cycle, e.g. stopping, restarting, resuming execution G06F9/4881 takes precedence
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals

Abstract

A computer-implemented method for traversing a first set of objects in a first dynamic list in a computer system. The method includes partitioning copies of the first set of objects into a plurality of second dynamic lists, each of the plurality of second dynamic lists being configured to contain a subset of the copies of the first set of objects, copies of the first set of objects being disposed in the plurality of second dynamic lists. The method also includes traversing the plurality of second dynamic lists using a plurality of traversal threads, thereby causing at least some of the copies of the first set of objects to be traversed in parallel.

Claims

1. A computer-implemented method for traversing a first set of objects in a first dynamic list in a computer system, comprising:

providing said first dynamic list that includes said first set of objects;

copying said first set of objects by using a computer;

partitioning copies of said first set of objects in said first dynamic list in an operating system of the computer system into a plurality of second dynamic lists in the operating system, each second dynamic list of said plurality of second dynamic lists contains a different subset of said copies of said first set of objects, copies of said first set of objects being disposed in said plurality of second dynamic lists;

wherein said first dynamic list represents an active threads list being used in conjunction with a scheduler in said computer system, said first set of objects represent thread objects in said active threads list; and

traversing said plurality of second dynamic lists in parallel by using a plurality of kernel traversal threads, thereby causing at least some of said copies of said first set of objects to be traversed in parallel by the kernel traversal threads;

wherein said traversing of said plurality of second dynamic lists in parallel includes re-calculating priority values associated with said copies of said first set of objects that are disposed in said plurality of second dynamic lists; and

wherein said traversing of said plurality of second dynamic lists includes modifying a priority value associated with each of said copies of said first set of objects.

2. The method of claim 1 wherein a number of said second dynamic lists equals a number of available processors in said computer system.

3. The method of claim 1 wherein said partitioning employs a hashing algorithm.

4. The method of claim 3 wherein said hashing algorithm employs thread IDs of said thread objects.

5. The method of claim 1 wherein each of said plurality of second dynamic lists is associated with a hash bucket.

6. The method of claim 1 wherein said plurality of second dynamic lists is implemented by a plurality of double-linked lists.

7. The method of claim 1 further comprising:

inserting a first object into said first dynamic list in the operating system; and

placing a copy of said first object in said first dynamic list into one of said plurality of second dynamic lists in the operating system upon said inserting said first object into said first dynamic list.

8. The method of claim 1 further comprising:

removing a first object from said first dynamic list; and

removing a copy of said first object from one of said plurality of second dynamic lists upon said removing said first object from said first dynamic list.

26. The method of claim 1, further comprising:

determining a hash of an object in the first set of objects; and

inserting a copy of the object into a list in the plurality of second dynamic lists, wherein a hash bucket that points to the list is associated with the hash of the object.

30. The method of claim 1, wherein the priority values are used by a scheduler in the operating system.

31. The method of claim 1, wherein re-calculating the priority values includes re-prioritizing the priority values in parallel.

9. An article of manufacture comprising a computer-readable program storage medium for storing computer readable code embodied therein, said computer readable code being configured to permit a computer system to traverse a first set of objects in a first dynamic list in the computer system, comprising:

computer-implemented code for providing said first dynamic list that includes said first set of objects, copying said first set of objects, and permitting the computer system to partition copies of said first set of objects in said first dynamic list in an operating system of the computer system into a plurality of second dynamic lists in the operating system, each second dynamic list of said plurality of second dynamic lists contains a different subset of said copies of said first set of objects, said copies of said first set of objects being disposed in said plurality of second dynamic lists;

wherein said first dynamic list represents an active threads list being used in conjunction with a scheduler in said computer system, said first set of objects represent thread objects in said active threads list; and

computer-implemented code for permitting the computer system to traverse said plurality of second dynamic lists in parallel by using a plurality of kernel traversal threads, thereby causing at least some of said copies of said first set of objects to be traversed in parallel by the kernel traversal threads;

wherein traversal of said plurality of second dynamic lists in parallel includes re-calculating priority values associated with said copies of said first set of objects that are disposed in said plurality of second dynamic list; and

wherein said traversal of said plurality of second dynamic lists includes modifying a priority value associated with each of said copies of said first set of objects.

10. The article of manufacture of claim 9 wherein a number of said plurality of said second dynamic lists equals a number of available processors in said computer system.

11. The article of manufacture of claim 9 wherein said computer readable code for permitting the computer system to partition includes computer readable code for permitting the computer system to implement a hashing algorithm.

12. The article of manufacture of claim 11 wherein said hashing algorithm employs thread IDs of said thread objects.

13. The article of manufacture of claim 9 wherein each of said plurality of second dynamic lists is associated with a hash bucket.

14. The article of manufacture of claim 9 wherein said plurality of second dynamic lists is implemented by a plurality of double-linked lists.

15. The article of manufacture of claim 9 further comprising:

computer-implemented code for permitting the computer system to insert a first object into said first dynamic list in the operating system; and

computer-implemented code for permitting the computer system to place a copy of said first object in said first dynamic list into one of said plurality of second dynamic lists in the operating system upon inserting said first object into said first dynamic list.

16. The article of manufacture of claim 9 further comprising:

computer-implemented code for permitting the computer system to remove a first object from said first dynamic list; and

computer-implemented code for permitting the computer system to remove a copy of said first object from one of said plurality of second dynamic lists upon removing said first object from said first dynamic list.

27. The article of manufacture of claim 9, further comprising:

computer readable code for determining a hash of an object in the first set of objects; and

computer readable code for inserting a copy of the object into a list in the plurality of second dynamic lists, wherein a hash bucket that points to the list is associated with the hash of the object.

32. The article of manufacture of claim 9, wherein the priority values are used by a scheduler in the operating system.

33. The article of manufacture of claim 9, wherein re-calculating the priority values includes re-prioritizing the priority values in parallel.

17. An arrangement configured for traversing a first set of objects in a first dynamic list in a computer system, the arrangement comprising:

a processor;

a computer-readable program storage medium;

means for providing said first dynamic list that includes said first set of objects;

means for copying said first set of objects;

means for partitioning copies of said first set of objects in said first dynamic list in an operating system of the computer system into a plurality of second dynamic lists in the operating system, each second dynamic list of said plurality of second dynamic lists contains a different subset of said copies of said first set of objects, copies of said first set of objects being disposed in said plurality of second dynamic lists;

wherein said first dynamic list represents an active threads list being used in conjunction with a scheduler in said computer system, said first set of objects represent thread objects in said active threads list; and

means for traversing said plurality of second dynamic lists in parallel by using a plurality of kernel traversal threads, thereby causing at least some of said copies of said first set of objects to be traversed in parallel by the kernel traversal threads;

wherein said traversing of said plurality of second dynamic lists in parallel includes re-calculating priority values associated with said copies of said first set of objects that are disposed in said plurality of second dynamic lists; and

wherein said traversing of said plurality of second dynamic lists includes modifying a priority value associated with each of said conies of said first set of objects.

18. The arrangement of claim 17 wherein a number of said plurality of first means equals a number of available processors in said computer system.

19. The arrangement of claim 17 wherein each of said plurality of first means is implemented by a linked list.

20. The arrangement of claim 17 wherein each of said plurality of first means is implemented by a double-linked list.

21. The arrangement of claim 17 further comprising:

means for inserting a first object into the first dynamic list in the operating system; and

means for placing a copy of the first object in said first dynamic list into one of the plurality of second dynamic lists in the operating system upon inserting the first object into the first dynamic list.

22. The arrangement of claim 17 further comprising:

means for removing a first object from the first dynamic list; and

means for removing a copy of the first object from one of the plurality of second dynamic lists upon removing the first object from the first dynamic list.

28. The arrangement of claim 17, further comprising:

means for determining a hash of an object in the first set of objects; and

means for inserting a copy of the object into a list in the plurality of second dynamic lists, wherein a hash bucket that points to the list is associated with the hash of the object.

34. The arrangement of claim 17, wherein the priority values are used by a scheduler in the operating system.

35. The arrangement of claim 17, wherein re-calculating the priority values includes re-prioritizing the priority values in parallel.

23. An apparatus for traversing a first set of objects in a first dynamic list in a computer system, the apparatus comprising:

a processor;

a computer-readable program storage medium;

an operating system configured to provide said first dynamic list that includes said first set of objects, copy said first set of objects, and partition copies of said first set of objects in said first dynamic list in the operating system of the computer system into a plurality of second dynamic lists in the operating system, each second dynamic list of said plurality of second dynamic lists contains a different subset of said copies of said first set of objects, copies of said first set of objects being disposed in said plurality of second dynamic lists,

wherein said first dynamic list represents an active threads list being used in conjunction with a scheduler in said computer system, said first set of objects represent thread objects in said active threads list, and

wherein the operating system is configured to traverse said plurality of second dynamic lists in parallel by using a plurality of kernel traversal threads, thereby causing at least some of said copies of said first set of objects to be traversed in parallel by the kernel traversal threads;

wherein traversal of said plurality of second dynamic lists in parallel includes re-calculating priority values associated with said copies of said first set of objects that are disposed in said plurality of second dynamic lists; and

wherein said traversal of said plurality of second dynamic lists includes modifying a priority value associated with each of said copies of said first set of objects.

24. The apparatus of claim 23 wherein the operating system is configured to insert a first object into the first dynamic list in the operating system, and to place a copy of the first object in the first dynamic list into one of the plurality of second dynamic lists in the operating system upon inserting the first object into the first dynamic list.

25. The apparatus of claim 23 wherein the operating system is configured to remove a first object from the first dynamic list;

and to remove a copy of the first object from one of the plurality of second dynamic lists upon removing the first object from the first dynamic list.

29. The apparatus of claim 23, wherein the operating system is configured to determine a hash of an object in the first set of objects and insert a copy of the object into a list in the plurality of second dynamic lists, wherein a hash bucket that points to the list is associated with the hash of the object.

36. The apparatus of claim 23, wherein the priority values are used by a scheduler in the operating system.

37. The apparatus of claim 23, wherein re-calculating the priority values includes re-prioritizing the priority values in parallel.