Managing Sequenced Lock Requests

• US 20080109807A1
• Filed: 11/06/2006
• Published: 05/08/2008
• Est. Priority Date: 11/06/2006
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Rosenbluth, Mark B.
• Granted Patent: US 8,595,729 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A method according to one embodiment may include determining if a sequence number of a first thread matches a current sequence number of a lock. If the sequence number of the first thread does not match the current sequence number, the method further includes placing the first thread into a wait queue; receiving a notification of an updated current sequence number by the first thread; determining if the sequence number of the first thread matches the updated current sequence number; acquiring the lock if the sequence number of the first thread matches the updated current sequence number; and remaining in the wait queue if the updated current sequence number does not match the sequence number of the first thread. Of course, many alternatives, variations, and modifications are possible without departing from this embodiment.

Claims

1. A method comprising:

determining if a sequence number of a first thread matches a current sequence number of a lock, and if said sequence number of said first thread does not match said current sequence number of said lock, said method further comprising;

placing said first thread into a wait queue;

receiving, by said first thread, a notification of an updated current sequence number;

determining if said sequence number of said first thread matches said updated current sequence number;

acquiring said lock if said sequence number of said first thread matches said updated current sequence number; and

remaining in said wait queue if said updated current sequence number does not match said sequence number of said first thread.

2. The method of claim 1, wherein placing said first thread into said wait queue comprises associating a node with said wait queue corresponding to said first thread, said node comprising a pointer to a node of said wait queue corresponding to a second thread, said second thread preceding said first thread in said wait queue, said first thread passing said notification to said second thread if said updated sequence number does not match said sequence number of said first thread.

3. The method of claim 1, further comprising acquiring said lock and removing said first thread from said wait queue if said updated current sequence number matches said sequence number of said first thread.

4. The method of claim 3, wherein removing said first thread from said wait queue comprising providing a node in said wait queue corresponding to a thread following said first thread in said wait queue with a pointer to a node in said wait queue preceding said first thread.

5. The method of claim 1, wherein determining if said sequence number of said first thread matches said current sequence number comprises:

replacing said current sequence number with a busy flag in a shared memory location, said busy flag preventing said current sequence number from being modified;

comparing said sequence number of said first thread to said current sequence number; and

replacing said busy flag with said current sequence number in said shared memory location.

6. The method of claim 5, wherein determining if said sequence number of said first thread matches said current sequence number further comprising placing said first thread into said wait queue.

7. The method of claim 6, comprising removing said first thread from said wait queue if said sequence number of said first thread matches said current sequence number.

8. An article comprising a storage medium having stored thereon instructions that when executed by a machine result in the following:

determining if a sequence number of a first thread matches a current sequence number of a lock, and if said sequence number of said first thread does not match said current sequence number, said instructions further resulting in;

placing said first thread into a wait queue;

receiving, said first thread, a notification of an updated current sequence number;

determining if said sequence number of said first thread matches said updated current sequence number;

acquiring said lock if said sequence number of said first thread matches said updated current sequence number; and

remaining in said wait queue if said updated current sequence number does not match said sequence number of said first thread.

9. The article of claim 8, wherein the instructions that when executed result in placing said first thread into said wait queue, result in the operations of:

associating a node with said wait queue corresponding to said first thread, said node comprising a pointer to a node of said wait queue corresponding to a second thread, said second thread preceding said first thread in said wait queue; and

said first thread passing said notification to said second thread if said updated sequence number does not match said sequence number of said first thread.

10. The article of claim 8, wherein the instructions when executed further result in acquiring said lock and removing said first thread from said wait queue if said updated current sequence number matches said sequence number of said first thread.

11. The article of claim 10, wherein the instructions that result in removing said first thread from said wait queue result in providing a node in said wait queue corresponding to a thread following said first thread in said wait queue with a pointer to a node in said wait queue preceding said first thread.

12. The article of claim 8, wherein the instructions that result in determining if said sequence number of said first thread matches said current sequence number when executed result in:

replacing said current sequence number with a busy flag in a shared memory location, said busy flag preventing said current sequence number from being modified;

comparing said sequence number of said first thread to said current sequence number; and

replacing said busy flag with said current sequence number in said shared memory location.

13. The article of claim 12, wherein the instructions that result in determining if said sequence number of said first thread matches said current sequence number further result in placing said first thread into said wait queue.

14. The article of claim 13, wherein the instructions, when executed, further result in removing said first thread from said wait queue if said sequence number of said first thread matches said current sequence number.

15. A network device comprising:

a switch fabric; and

multiple blades coupled to the switch fabric, at least one of the blades comprising an integrated circuit (IC) configured to execute instructions using a plurality of threads, said IC is further configured to;

determine if a sequence number of a first thread matches a current sequence number of a lock, and if said sequence number of said first thread does not match said current sequence number, said IC is further configured to;

place said first thread into a wait queue;

receive a notification of an updated current sequence number;

determine if said sequence number of said first thread matches said updated current sequence number;

acquire said lock if said sequence number of said first thread matches said updated current sequence number; and

remain in said wait queue if said updated current sequence number does not match said sequence number of said first thread.

16. The network device of claim 15, wherein said IC configured to place said first thread into said wait queue is configured to associate a node with said wait queue corresponding to said first thread, said node comprising a pointer to a node of said wait queue corresponding to a second thread, said second thread preceding said first thread on said wait queue, wherein said IC is further configured to pass said notification from said first thread to said second thread if said updated sequence number does not match said sequence number of said first thread.

17. The network device of claim 15, wherein said IC is further configured to acquire said lock and remove said first thread from said wait queue if said updated current sequence number matches said sequence number of said first thread.

18. The network device of claim 17, wherein said IC configured to remove said first thread from said wait queue is configured to provide a node in said wait queue corresponding to a thread following said first thread in said wait queue with a pointer to a node in said wait queue preceding said first thread.

19. The network device of claim 15, wherein said IC configured to determine if said sequence number of said first thread matches said current sequence number is configured to:

replace said current sequence number with a busy flag in a shared memory location, said busy flag configured to prevent said current sequence number from being modified;

compare said sequence number of said first thread to said current sequence number; and

replace said busy flag with said current sequence number in said shared memory location.

20. The network device of claim 19, wherein said IC configured to determine if said sequence number of said first thread matches said current sequence number is further configured to place said first thread into said wait queue.

21. The network device of claim 20, wherein said IC is configured to remove said first thread from said wait queue if said sequence number of said first thread matches said current sequence number.