Method and apparatus for implementing atomic queues

• US 6,094,663 A
• Filed: 03/31/1998
• Issued: 07/25/2000
• Est. Priority Date: 03/31/1998
• Status: Expired due to Term

• Current Assignee: Apple Computer Incorporated (Apple Inc.)
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Snow, Kevin D., Carty, Derrick M.
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/052,745
• Time in Patent Office: 847 Days
• Field of Search: 707/200, 707/202, 707/203, 707/204, 701/120, 710/5, 711/163, 342/36, 375/371
• US Class Current: 707/799
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Methods and apparatus for implementing queues without disabling interrupts or using locks are disclosed. According to one aspect of the present invention, a queue structure, which is accessible to a plurality of threads, that is suitable for use in a computer system includes a head node and a first data-containing node. The head node includes a head field and a disruption field that is arranged to indicate a number of times the queue structure is accessed. The first data-containing node, which is identified by the head field in the head node, includes a link field and a data field. In one embodiment, the head node also includes a rank field, which is arranged to identify a preference level associated with the plurality of threads. In such an embodiment, the head field may be the first field in the head node, the rank field may be the second field in the head node, and the disruption field may be the third field in the head node.

Claims

1. A queue structure suitable for use in an overall computer system, the queue structure being arranged for data to be stored sequentially therein, wherein the queue structure facilitates access to the data within the overall computer system, the queue structure further being arranged to be accessed by a plurality of threads, the plurality of threads being associated with the overall computer system, the queue structure comprising:

a head node, the head node including a head field and a disruption field, the disruption field being arranged to indicate a number of times the queue structure is accessed; and

a first data-containing node, the first data-containing node being identified by the head field in the head node, wherein the first data-containing node includes a link field and a data field.

2. A queue structure as recited in claim 1 wherein the head node further includes a rank field, the rank field being arranged to identify a preference level associated with the plurality of threads.

3. A queue structure as recited in claim 2 wherein the head field is the first field in the head node, the rank field is the second field in the head node, and the disruption field is the third field in the head node.

4. A queue structure suitable for use in an overall computer system, the queue structure being arranged for data to be stored sequentially therein, wherein the queue structure facilitates access to the data within the overall computer system, the queue structure further being arranged to be accessed by a plurality of threads, the plurality of threads being associated with the overall computer system, the queue structure comprising:

a head node, the head node including a head field and a disruption field, the disruption field being arranged to indicate a number of times the queue structure is accessed;

a first data-containing node, the first data-containing node being identified by the head field in the head node, wherein the first data-containing node includes a link field and a data field; and

a second data-containing node, the second data-containing node including a link field and a data field.

5. A queue structure as recited in claim 4 wherein the link field of the first data-containing node is arranged to identify the second data-containing node.

6. A queue structure as recited in claim 5 wherein the link field of the second data-containing node is set to indicate that the second data-containing node is a final node in the queue structure.

7. A method for implementing a queue in a computer system, the method comprising:

providing a first data-containing node, the first data-containing node including a link field and a data field; and

providing a head node, the head node including a head field and a disruption field, the head field being arranged to identify the first data-containing node, the disruption field being arranged to indicate whether the queue has been disrupted.

8. A method for implementing a queue as recited in claim 7 further including providing the head node with a rank field, the rank field being arranged to identify a preference level associated with a plurality of threads which are arranged to manipulate the queue.

9. A method for implementing a queue as recited in claim 7 further including providing a second data-containing node, wherein the second data-containing node includes a link field and a data field.

10. A method for implementing a queue as recited in claim 9 further including arranging the link field of the first data-containing node to identify the second data-containing node.

11. A computer-implemented method for enqueuing an additional node on a queue, the additional node including a link field, the queue including a head and at least one node, the head including a head field and a disruption field, the head field including contents arranged to identify the at least one node, the disruption field arranged to contain a disruption level of the queue, the computer-implemented method comprising:

acquiring the disruption level of the queue;

reading the contents from the head field into the link field of the additional node;

determining whether the queue has been disrupted; and

storing an address of the additional node into the head field when it is determined that the queue has not been disrupted.

12. A computer-implemented method as recited in claim 11 wherein the head further includes a rank field arranged to contain a rank of the queue, the method further including:

acquiring the rank of the queue.

13. A computer-implemented method as recited in claim 12 wherein acquiring the rank of the queue includes:

reading the rank of the queue from the rank field of the head;

incrementing the rank of the queue; and

storing the rank of the queue in a computer memory that is separate from the queue.

14. A computer-implemented method as recited in claim 13 further including decrementing the rank of the queue after storing the address of the additional node into the head field.

15. A computer-implemented method as recited in claim 11 wherein acquiring the disruption level of the queue includes:

reading the disruption level of the queue from the disruption field into a first variable;

incrementing the first variable; and

storing the first variable in a computer memory that is separate from the queue.

16. A computer-implemented method for enqueuing an additional node on a queue, the additional node including a link field, the queue including a head and at least one node, the head including a head field and a disruption field, the head field including contents arranged to identify the at least one node, the disruption field arranged to contain a disruption level of the queue, the computer-implemented method comprising:

acquiring the disruption level of the queue, the disruption level being arranged to indicate whether the queue has been disrupted;

determining whether the queue has been disrupted using the disruption level; and

storing an address of the additional node into a link field of the at least one node when it is determined that the queue has not been disrupted.

17. A computer-implemented method as recited in claim 16 wherein acquiring the disruption level of the queue includes:

reading the disruption level of the queue from the disruption field into a first variable;

incrementing the first variable; and

storing the first variable in a computer memory that is separate from the queue.

18. A computer-implemented method as recited in claim 16 further including setting the link field of the additional node to indicate that the additional node is a tail of the queue.

19. A computer-implemented method for enqueuing an additional node on a queue, the additional node including a link field, the queue including a head and at least one node, the head including a head field, a disruption field, and a rank field, the head field including contents arranged to identify the at least one node, the disruption field arranged to contain a disruption level of the queue, the rank field arranged to contain a rank of the queue, the computer-implemented method comprising:

acquiring the disruption level of the queue;

determining whether the queue has been disrupted;

storing an address of the additional node into a link field of the at least one node when it is determined that the queue has not been disrupted; and

acquiring the rank of the queue.

20. A computer-implemented method as recited in claim 19 wherein acquiring the rank of the queue includes:

reading the rank of the queue from the rank field of the head;

incrementing the rank of the queue; and

storing the rank of the queue in a computer memory that is separate from the queue.

21. A computer-implemented method as recited in claim 20 further including decrementing the rank of the queue after storing the address of the additional node into the head field.

22. A computer system arranged to enqueue an additional node on a queue, the additional node including a link field, the queue including a head and at least one node, the head including a head field and a disruption field, the head field including contents arranged to identify the at least one node, the disruption field arranged to contain a disruption level of the queue, the computer system comprising:

a thread arranged to acquire the disruption level of the queue, the disruption level being arranged to indicate whether the queue has been disrupted;

a mechanism for reading the contents from the head field into the link field of the additional node;

a mechanism for determining whether the queue has been disrupted; and

a mechanism for storing an address of the additional node into the head field when it is determined that the queue has not been disrupted.

23. A computer system as recited in claim 22 wherein the head further includes a rank field arranged to contain a rank of the queue, the computer system further including:

a mechanism arranged to read the rank of the queue from the rank field of the head, increment the rank of the queue, and store the rank of the queue in a stack that is associated with the thread.

24. A computer system as recited in claim 22 wherein the mechanism for acquiring the disruption level of the queue is arranged to read the disruption level of the queue from the disruption field into a first variable, increment the first variable, and storing the first variable in a stack associated with the queue.

25. A computer system for enqueuing an additional node on a queue, the additional node including a link field, the queue including a head and at least one node, the head including a head field and a disruption field, the head field including contents arranged to identify the at least one node, the disruption field arranged to contain a disruption level of the queue, the computer system comprising:

a thread for acquiring the disruption level of the queue;

a mechanism for determining whether the queue has been disrupted; and

a mechanism for storing an address of the additional node into a link field of the at least one node when it is determined that the queue has not been disrupted.

26. A computer system as recited in claim 25 wherein the head further includes a rank field arranged to contain a rank of the queue, the computer system further including:

a mechanism arranged to read the rank of the queue from the rank field of the head, increment the rank of the queue, and store the rank of the queue in a stack that is associated with the thread.

27. A computer system as recited in claim 25 wherein the mechanism for acquiring the disruption level of the queue is arranged to read the disruption level of the queue from the disruption field into a first variable, increment the first variable, and storing the first variable in a stack associated with the queue.

28. A computer program product arranged for enqueuing an additional node on a queue, the additional node including a link field, the queue including a head and at least one node, the head including a head field and a disruption field, the head field including contents arranged to identify the at least one node, the disruption field arranged to contain a disruption level of the queue, the computer program product comprising:

computer code that acquires the disruption level of the queue;

computer code that reads the contents from the head field into the link field of the additional node;

computer code that determines whether the queue has been disrupted;

computer code that stores an address of the additional node into the head field when it is determined that the queue has not been disrupted; and

a computer readable medium that stores the computer codes.

29. A computer program product according to claim 28 wherein the head further includes a rank field arranged to contain a rank of the queue, the computer program product further including:

computer code that reads the rank of the queue from the rank field of the head;

computer code that increments the rank of the queue; and

computer code that stores the rank of the queue in a computer memory that is separate from the queue.

30. A computer program product according to claim 28 wherein the computer code that acquires the disruption level of the queue includes:

computer code that reads the disruption level of the queue from the disruption field into a first variable;

computer code that increments the first variable; and

computer code that stores the first variable in a computer memory that is separate from the queue.

31. A computer-implemented method for dequeuing a first node from a queue, the queue including a head, the head including a head field and a disruption field, the head field including contents arranged to identify the at least one node, the disruption field arranged to contain a disruption level of the queue, the first node including a link field, the computer-implemented method comprising:

acquiring the disruption level of the queue;

determining whether the queue has been disrupted; and

storing contents of the link field of the first node into the head field when it is determined that the queue has not been disrupted.

32. A computer-implemented method as recited in claim 31 wherein the head further includes a rank field arranged to contain a rank of the queue, the method further including:

acquiring the rank of the queue.

33. A computer-implemented method as recited in claim 32 wherein acquiring the rank of the queue includes:

reading the rank of the queue from the rank field of the head;

incrementing the rank of the queue; and

storing the rank of the queue in a computer memory that is separate from the queue.

34. A computer-implemented method as recited in claim 31 wherein acquiring the disruption level of the queue includes:

reading the disruption level of the queue from the disruption field into a first variable;

incrementing the first variable; and

storing the first variable in a computer memory that is separate from the queue.

35. A computer-implemented method for dequeuing a first node from a queue, the queue including a head, the first node, and a second node, wherein the second node immediately precedes the first node, the first node including a link field, the head including a head field and a disruption field, the head field including contents arranged to identify one of the plurality of nodes, the disruption field arranged to contain a disruption level of the queue, the computer-implemented method comprising:

acquiring the disruption level of the queue;

determining whether the queue has been disrupted; and

storing contents of the link field of the first node into a link field of the second node when it is determined that the queue has not been disrupted.

36. A computer-implemented method as recited in claim 35 wherein the head further includes a rank field arranged to contain a rank of the queue, the method further including:

acquiring the rank of the queue.

37. A computer-implemented method as recited in claim 36 wherein acquiring the rank of the queue includes:

reading the rank of the queue from the rank field of the head;

incrementing the rank of the queue; and

storing the rank of the queue in a computer memory that is separate from the queue.