Managing sequenced lock requests

• US 8,595,729 B2
• Filed: 11/06/2006
• Issued: 11/26/2013
• Est. Priority Date: 11/06/2006
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Rosenbluth, Mark B.
• Primary Examiner(s): ZHE, MENG YAO
• Application Number:
  US11/556,778
• Publication Number:
  US 20080109807A1
• Time in Patent Office: 2,577 Days
• Field of Search: 718/102
• 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:

assigning a sequence number to a first software thread;

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

placing said first software thread into a wait queue, said wait queue comprising said first software thread and at least a second software thread, wherein said second software thread precedes said first software thread in said wait queue;

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

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

acquiring said software lock and removing said first software thread from said wait queue if said sequence number of said first software thread matches said updated current sequence number; and

remaining in said wait queue and passing said notification to said second software thread if said updated current sequence number does not match said sequence number of said first software thread.

2. The method of claim 1, wherein placing said first software thread into said wait queue comprises associating a node with said wait queue corresponding to said first software thread, said node comprising a pointer to a node of said wait queue corresponding to said second software thread.

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

4. The method of claim 1, wherein determining if said sequence number of said first software 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 software thread to said current sequence number; and

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

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

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

7. An article comprising a non-transitory storage medium having stored thereon instruction that when executed by a machine result in the following:

assigning a sequence number to a first software thread;

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

placing said first software thread into a wait queue, said wait queue comprising said first software thread and at least a second software thread, wherein said second software thread precedes said first software thread in said wait queue;

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

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

acquiring said software lock and removing said first software thread from said wait queue if said sequence number of said first software thread matches said updated current sequence number; and

remaining in said wait queue and passing said notification to said second software thread if said updated current sequence number does not match said sequence number of said first software thread.

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

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

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

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

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

11. The article of claim 7, wherein the instructions that result in determining if said sequence number of said first software 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 software thread to said current sequence number; and

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

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

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

14. 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;

assign a sequence number to a first software thread;

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

place said first software thread into a wait queue, said wait queue comprising said first software thread and at least a second software thread, wherein said second software thread precedes said first software thread in said wait queue;

receive a notification of an updated current sequence number;

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

acquire said software lock and removing said first software thread from said wait queue if said sequence number of said first software thread matches said updated current sequence number; and

remain in said wait queue and passing said notification to said second software thread if said updated current sequence number does not match said sequence number of said first software thread.

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

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

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

18. The network device of claim 14, wherein said IC configured to determine if said sequence number of said first software 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 software thread to said current sequence number; and

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

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

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