Methods for single-owner multi-consumer work queues for repeatable tasks

• US 9,135,083 B2
• Filed: 04/20/2012
• Issued: 09/15/2015
• Est. Priority Date: 07/14/2008
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Michael, Maged M., Saraswat, Vijay Anand, Vechev, Martin
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US13/452,286
• Publication Number:
  US 20120210322A1
• Time in Patent Office: 1,243 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 2209/521 Atomic
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

There are provided methods for single-owner multi-consumer work queues for repeatable tasks. A method includes permitting a single owner thread of a single owner, multi-consumer, work queue to access the work queue using atomic instructions limited to only a single access and using non-atomic operations. The method further includes restricting the single owner thread from accessing the work queue using atomic instructions involving more than one access. The method also includes synchronizing amongst other threads with respect to their respective accesses to the work queue.

Claims

1. A method, comprising:

permitting a single owner thread of a single owner, multi-consumer, work queue to access the work queue using atomic instructions limited to only a single access and using non-atomic operations;

restricting the single owner thread from accessing the work queue using atomic instructions involving more than one access; and

synchronizing amongst other threads with respect to their respective accesses to the work queue,

wherein the atomic instructions limited to only a single access consist of only one of a single read or a single write.

2. The method of claim 1, further comprising prohibiting the single owner thread from re-writing, to the work queue, shared, non-initialization-related variables that have already been written by the other threads to the work queue.

3. The method of claim 1, further comprising prohibiting the other threads from re-writing, to the work queue, shared variables that have already been written by the single owner thread to the work queue.

4. The method of claim 1, wherein operations performed by the single owner thread comprise an insertion operation that involves atomically reading at least two integer values from a single shared variable having at least two integer components respectively relating to a head of the work queue and a number of items in the work queue into a first and a second local variable respectively, writing an item into a work queue entry having an index based on a sum of the first and the second local variables, and atomically writing at least two values to the single shared variable, the at least two values respectively comprising the first local variable and a sum of the second local variable plus one.

5. The method of claim 1, wherein operations performed by the single owner thread comprise an extraction operation that involves atomically reading at least two integer values from a single shared variable having at least two integer components respectively relating to a head of the work queue and a number of items in the work queue into a first and a second local variable respectively, reading a work queue entry having an index based on a sum of the first local variable and the second local variable minus one, and atomically writing at least two values to the single shared variable, and returning the work queue entry, the at least two values respectively comprising the first local variable and the second local variable minus one.

6. The method of claim 1, wherein an operation performed by at least one of the other threads comprises atomically reading at least two integer values from a single shared variable having at least two integer components respectively relating to a head of the work queue and a number of items in the work queue into a first and a second local variable respectively, reading a work queue entry having an index equal to the first local variable, checking that the value of the single shared variable is currently equal to an initially read value there for during the operation, writing a sum of the first local variable plus one and a difference of the second local variable minus one to the single shared variable and providing an indication of success and returning the work queue entry when the value of the single shared variable is currently equal to the initially read value there for, wherein the checking and the writing are performed together atomically.

7. The method of claim 1, wherein operations performed by the single owner thread comprise an insertion operation that involves atomically reading an integer value from a single shared variable having a single integer component relating to a tail of the work queue into a local variable, writing an item into a work queue entry having an index based on the local variable, and atomically writing a sum of the local variable plus one to the single shared variable.

8. The method of claim 1, wherein operations performed by the single owner thread comprise an extraction operation that involves atomically reading an integer value from a single shared variable having a single integer component relating to a tail of the work queue and maintaining the integer value minus one in a local variable, atomically writing the local variable into the single shared variable, atomically reading another integer value from another single shared variable having another single integer component relating to a head of the work queue into another local variable, checking whether the local variable is less than the other local variable, writing the other local variable to the single shared variable when the local variable is less than the other local variable, and atomically writing a sum of the other local variable plus one into the single shared variable and the other single shared variable and returning a work queue item having an index equal to the local variable when the local variable is not less than the other local variable.

9. The method of claim 1, wherein an operation performed by at least one of the other threads comprises atomically reading at least one integer value from a single shared variable having at least one integer component relating to a head of the work queue into a local variable, reading a work queue entry having an index equal to the local variable, checking that the value of the single shared variable is currently equal to an initially read value there for during the operation, writing a sum of the local variable plus one to the single shared variable and providing an indication of success and returning the work queue entry when the value of the single shared variable is currently equal to the initially read value there for, wherein the checking and the writing are performed together atomically.

10. The method of claim 1, wherein the work queue is configured as a circular array.

11. A non-transitory program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for queue access management, the method steps comprising:

permitting a single owner thread of a single owner, multi-consumer, work queue to access the work queue using atomic instructions limited to only a single access and using non-atomic operations;

restricting the single owner thread from accessing the work queue using atomic instructions involving more than one access; and

synchronizing amongst other threads with respect to their respective accesses to the work queue,

wherein the atomic instructions limited to only a single access consist of only one of a single read or a single write.

12. The program storage device of claim 11, further comprising prohibiting the single owner thread from re-writing, to the work queue, shared, non-initialization-related variables that have already been written by the other threads to the work queue.

13. The program storage device of claim 11, further comprising prohibiting the other threads from re-writing, to the work queue, shared variables that have already been written by the single owner thread to the work queue.

14. The program storage device of claim 11, wherein operations performed by the single owner thread comprise an insertion operation that involves atomically reading at least two integer values from a single shared variable having at least two integer components respectively relating to a head of the work queue and a number of items in the work queue into a first and a second local variable respectively, writing an item into a work queue entry having an index based on a sum of the first and the second local variables, and atomically writing at least two values to the single shared variable, the at least two values respectively comprising the first local variable and a sum of the second local variable plus one.

15. The program storage device of claim 11, wherein operations performed by the single owner thread comprise an extraction operation that involves atomically reading at least two integer values from a single shared variable having at least two integer components respectively relating to a head of the work queue and a number of items in the work queue into a first and a second local variable respectively, reading a work queue entry having an index based on a sum of the first local variable and the second local variable minus one, and atomically writing at least two values to the single shared variable, and returning the work queue entry, the at least two values respectively comprising the first local variable and the second local variable minus one.

16. The program storage device of claim 11, wherein an operation performed by at least one of the other threads comprises atomically reading at least two integer values from a single shared variable having at least two integer components respectively relating to a head of the work queue and a number of items in the work queue into a first and a second local variable respectively, reading a work queue entry having an index equal to the first local variable, checking that the value of the single shared variable is currently equal to an initially read value there for during the operation, writing a sum of the first local variable plus one and a difference of the second local variable minus one to the single shared variable and providing an indication of success and returning the work queue entry when the value of the single shared variable is currently equal to the initially read value there for, wherein the checking and the writing are performed together atomically.

17. The program storage device of claim 11, wherein operations performed by the single owner thread comprise an insertion operation that involves atomically reading an integer value from a single shared variable having a single integer component relating to a tail of the work queue into a local variable, writing an item into a work queue entry having an index based on the local variable, and atomically writing a sum of the local variable plus one to the single shared variable.

18. The program storage device of claim 11, wherein operations performed by the single owner thread comprise an extraction operation that involves atomically reading an integer value from a single shared variable having a single integer component relating to a tail of the work queue and maintaining the integer value minus one in a local variable, atomically writing the local variable into the single shared variable, atomically reading another integer value from another single shared variable having another single integer component relating to a head of the work queue into another local variable, checking whether the local variable is less than the other local variable, writing the other local variable to the single shared variable when the local variable is less than the other local variable, and atomically writing a sum of the other local variable plus one into the single shared variable and the other single shared variable and returning a work queue item having an index equal to the local variable when the local variable is not less than the other local variable.

19. The program storage device of claim 11, wherein an operation performed by at least one of the other threads comprises atomically reading at least one integer value from a single shared variable having at least one integer component relating to a head of the work queue into a local variable, reading a work queue entry having an index equal to the local variable, checking that the value of the single shared variable is currently equal to an initially read value there for during the operation, writing a sum of the local variable plus one to the single shared variable and providing an indication of success and returning the work queue entry when the value of the single shared variable is currently equal to the initially read value there for, wherein the checking and the writing are performed together atomically.

20. The program storage device of claim 11, wherein the work queue is configured as a circular array.