METHOD AND APPARATUS FOR IMPLEMENTING ATOMIC FIFO

• US 20100313208A1
• Filed: 06/03/2009
• Published: 12/09/2010
• Est. Priority Date: 06/03/2009
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Zarzycki, David A., Osborne, Joshua, Van Vechten, Kevin James
• Granted Patent: US 8,239,867 B2
• Time in Patent Office: Days
• US Class Current: 719/315
• 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

Techniques for implementing an atomic FIFO queue and system for processing queue elements are described herein. According to one embodiment, in a first thread of execution, new data is atomically merged with existing data of an object via an atomic instruction associated with hardware that executes the first thread. An attempt is made to acquire ownership of the object (exclusive access). If successful, the object is enqueued on an atomic FIFO queue as a continuation element for further processing. Otherwise, another thread of execution is safely assumed to have acquired ownership and taken responsibility to enqueue the object. A second thread of execution processes the atomic FIFO queue and assumes ownership of the continuation elements. The second thread invokes a function member of the continuation element with a data member of the continuation element, the data member including the newly merged data. Other methods and apparatuses are also described.

Claims

1. A computer-implemented method performed by a multi-processing system having multiple execution units capable of executing multiple threads concurrently, the method comprising:

in a first thread of execution;

atomically merging new data with existing data of an object via an atomic instruction associated with hardware that executes the first thread; and

attempting to acquire exclusive access to the object, and if successful, enqueuing the object as a continuation element onto a queue having a list of continuation elements pending therein;

in a second thread of execution which is executed concurrently with respect to the first thread;

processing the continuation elements pending on a queue and assuming exclusive access to each continuation;

executing a function member of the continuation element using a data member of the continuation element, the data member including the merged new data; and

terminating the exclusive access to the second continuation element; and

determining whether additional data was merged by a third thread of execution restarting the process if necessary.

2. The method of claim 1, wherein atomically merging new data with the existing data is atomically performed without having to acquire exclusive access to the object.

3. The method of claim 1, wherein the queue comprises a hierarchical structure having a plurality of levels, including a root level and one or more lower levels, each level having a list of continuation elements, wherein one or more threads are configured to process continuation elements of the root level and lower levels.

4. The method of claim 3, further comprising:

in the first thread of execution;

attempting to acquire exclusive access of the first continuation element, and if successful, pushing the first continuation element from a current level of the queue onto a higher level of the queue.

5. The method of claim 4, further comprising, in the first thread of execution, determining whether the first continuation element includes data pending to be processed, wherein the first continuation element is pushed onto the higher level of queue if there is data pending.

6. The method of claim 3, further comprising:

in the second thread of execution;

performing a first determination of whether the second continuation element has been suspended by another thread, wherein the execution of the function member of the second continuation element is performed if the second continuation element has not been suspended; and

performing a second determination of whether the second continuation element is suspended after the execution of the function member and terminating the exclusive access to the second continuation element.

7. The method of claim 3, further comprising:

in a third thread of execution which is executed concurrently with respect to the first thread and the second thread;

in response to a resume event of a third continuation element, determining whether the third continuation element has been suspended by another thread;

attempting to acquire exclusive access of the third continuation element, and if successful, pushing the third continuation element from a current level of the queue onto a higher level of the queue, if the current level is not the root level.

8. The method of claim 7, further comprising, in the third thread of execution, determining whether the third continuation element includes data pending to be processed, wherein the third continuation element is pushed onto the higher level of queue if there is data pending.

9. A machine-readable storage medium storing instructions, which when executed by a machine, cause a machine to perform a method of a multi-processing system having multiple execution units capable of executing multiple threads concurrently, the method comprising:

in a first thread of execution;

atomically merging new data with existing data of an object via an atomic instruction associated with hardware that executes the first thread; and

attempting to acquire exclusive access to the object, and if successful, enqueuing the object as a continuation element onto a queue having a list of continuation elements pending therein;

in a second thread of execution which is executed concurrently with respect to the first thread;

processing the continuation elements pending on a queue and assuming exclusive access to each continuation;

executing a function member of the continuation element using a data member of the continuation element, the data member including the merged new data; and

terminating the exclusive access to the second continuation element; and

determining whether additional data was merged by a third thread of execution restarting the process if necessary.

10. The machine-readable storage medium of claim 9, wherein atomically merging new data with the existing data is atomically performed without having to acquire exclusive access to the object.

11. The machine-readable storage medium of claim 9, wherein the queue comprises a hierarchical structure having a plurality of levels, including a root level and one or more lower levels, each level having a list of continuation elements, wherein one or more threads are configured to process continuation elements of the root level and lower levels.

12. The machine-readable storage medium of claim 11, wherein the method further comprises:

in the first thread of execution;

attempting to acquire exclusive access of the first continuation element, and if successful, pushing the first continuation element from a current level of the queue onto a higher level of the queue.

13. The machine-readable storage medium of claim 12, wherein the method further comprises, in the first thread of execution, determining whether the first continuation element includes data pending to be processed, wherein the first continuation element is pushed onto the higher level of queue if there is data pending.

14. The machine-readable storage medium of claim 11, wherein the method further comprises:

in the second thread of execution;

performing a first determination of whether the second continuation element has been suspended by another thread, wherein the execution of the function member of the second continuation element is performed if the second continuation element has not been suspended; and

performing a second determination of whether the second continuation element is suspended after the execution of the function member and terminating the exclusive access to the second continuation element.

15. The machine-readable storage medium of claim 11, wherein the method further comprises:

in a third thread of execution which is executed concurrently with respect to the first thread and the second thread;

in response to a resume event of a third continuation element, determining whether the third continuation element has been suspended by another thread;

attempting to acquire exclusive access of the third continuation element, and if successful, pushing the third continuation element from a current level of the queue onto a higher level of the queue, if the current level is not the root level.

16. The machine-readable storage medium of claim 15, wherein the method further comprises, in the third thread of execution, determining whether the third continuation element includes data pending to be processed, wherein the third continuation element is pushed onto the higher level of queue if there is data pending.

17. A system, comprising:

a first execution unit to execute a first thread to atomically merge new data with existing data of an object via an atomic instruction associated with hardware that executes the first thread, to attempt to acquire exclusive access to the object, and if successful, to enqueue the object as a continuation element onto a queue having a list of continuation elements pending therein; and

a second execution unit to execute a second thread concurrently with respect to the first thread to

process the continuation elements pending on a queue and assuming exclusive access to each continuation,

execute a function member of the continuation element using a data member of the continuation element, the data member including the merged new data,

terminate the exclusive access to the second continuation element, and

determine whether additional data was merged by a third thread of execution restarting the process if necessary.

18. The system of claim 17, wherein atomically merging new data with the existing data is atomically performed without having to acquire exclusive access to the first continuation element.

19. The system of claim 17, further comprising a memory to store the queue, wherein the queue includes a hierarchical structure having a plurality of levels, including a root level and one or more lower levels, each level having a list of continuation elements, wherein the first thread is configured to process continuation elements of a lower level, and wherein the second thread is configured to process continuation elements of the root level.

20. A computer-implemented method performed by a multi-processing system having multiple execution units capable of executing multiple threads concurrently, the method comprising:

in a first thread of execution;

atomically merging new data with existing data of a first continuation element via an atomic instruction associated with hardware that executes the first thread; and

enqueuing the first continuation element having merged data into a queue having a list of continuation elements pending therein;

in a second thread of execution;

acquiring exclusive access to a second continuation element;

executing a function member of the second continuation element using a data member of the second continuation element, the data member including the merged new data;

terminating the exclusive access to the second continuation element, wherein the queue comprises a hierarchical structure having a plurality of levels, including a root level and one or more lower levels, each level having a list of continuation elements, wherein the first thread is configured to process continuation elements of a lower level, and wherein the second thread is configured to process continuation elements of the root level; and

in a third thread of execution;

in response to a resume event of a third continuation element, determining whether the third continuation element has been suspended by another thread;

acquiring exclusive access of the third continuation element;

pushing the third continuation element from a current level of the queue onto a higher level of the queue, if the current level is not the root level; and

terminating the exclusive access of the third continuation element,

wherein the first thread, the second thread, and the third thread are executed substantially concurrently.

21. The method of claim 20, wherein atomically merging new data with the existing data is atomically performed without having to acquire exclusive access to the first continuation element.

22. The method of claim 20, further comprising:

in the first thread of execution;

acquiring exclusive access of the first continuation element;

pushing the first continuation element from a current level of the queue onto a higher level of the queue, if the current level is not the root level; and

terminating the exclusive access of the first continuation element.