Multi-threaded Processing Using Path Locks

• US 20080077926A1
• Filed: 09/27/2006
• Published: 03/27/2008
• Est. Priority Date: 09/27/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.), Crane Payment Innovations, GMBH (Crane Company)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Marshall, John, Jeter, Robert, Garner, Trevor, Kirk, Aaron
• Granted Patent: US 8,010,966 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

Abstract

In one embodiment, a method includes receiving at a thread scheduler data that indicates a first thread is to execute next a particular instruction path in software to access a particular portion of a shared computational resource. The thread scheduler determines whether a different second thread is exclusively eligible to execute the particular instruction path on any processor of a set of one or more processors to access the particular portion of the shared computational resource. If so, then the thread scheduler prevents the first thread from executing any instruction from the particular instruction path on any processor of the set of one or more processors. This enables several threads of the same software to share a resource without obtaining locks on the resource or holding a lock on a resource while a thread is not running.

Claims

1. A method comprising the steps of:

causing all threads of a plurality of threads that access a particular portion of a shared computational resource during a particular instruction path though one or more sequences of instructions to be scheduled at a thread scheduler for a set of one or more processors;

receiving, at the thread scheduler, data that indicates a first thread of the plurality of threads is to execute next the particular instruction path to access the particular portion of the shared computational resource;

determining whether a second thread of the plurality of threads is exclusively eligible to execute the particular instruction path on any processor of the set of one or more processors to access the particular portion of the shared computational resource, and

if it is determined that the second thread is exclusively eligible to execute the particular instruction path, then preventing the first thread from executing any instruction from the particular instruction path on any processor of the set of one or more processors.

2. A method as recited in claim 1, further comprising, if it is determined that no other thread is exclusively eligible to execute the particular instruction path to access the particular portion of the shared computational resource, then marking the first thread as exclusively eligible to execute the particular instruction path on any processor of the set of one or more processors to access the particular portion of the shared computational resource.

3. A method as recited in claim 1, further comprising, if it is determined that the second thread is exclusively eligible to execute the particular instruction path to access the particular portion of the shared computational resource, then performing the steps of:

receiving data that indicates the second thread rescinds exclusive use of the particular instruction path to access the particular portion of the shared computational resource; and

in response to receiving data that indicates the second thread rescinds exclusive use of the particular instruction path, marking the second thread as not exclusively eligible to execute the particular instruction path on any processor of the set of one or more processors to access the particular portion of the shared computational resource.

4. A method as recited in claim 3, the step of receiving data that indicates the second thread rescinds exclusive use of the particular instruction path further comprising receiving data that indicates the second thread is to executer next an instruction path different from the particular instruction path.

5. A method as recited in claim 1, wherein the particular instruction path does not include an instruction to request an exclusive lock on the particular portion of the shared computational resource.

6. A method as recited in claim 2, wherein a thread of the plurality of threads is not marked as exclusively eligible to execute the particular instruction path on any processor of the set of one or more processors based on order of data packets received on a network interface.

7. A method as recited in claim 1, further comprising, if it is determined that no other thread is exclusively eligible to execute the particular instruction path to access the particular portion of the shared computational resource, then storing, in flag data associated with data that indicates the first thread, a value that indicates a lock is granted for the first thread for exclusive execution of the particular instruction path to access the particular portion of the shared computational resource.

8. A method as recited in claim 7, wherein:

said step of receiving data that indicates the first thread of the plurality of threads is to execute next the particular instruction path further comprises the step of receiving a path identifier (ID) that uniquely indicates the particular instruction path to access the particular portion of the shared computational resource;

the method further comprises, in response to the step of receiving the path ID, storing data that indicates the path ID in association with data that indicates the first thread; and

said step of determining whether the second thread of the plurality of threads is exclusively eligible to execute the particular instruction path further comprises determining whether flag data associated with data that indicates the second thread holds a value that indicates a lock is granted for exclusive execution of the particular path to access the particular portion of the shared computational resource.

9. A method comprising the steps of:

receiving data that indicates a unique path identifier (ID) for a particular instruction path though one or more sequences of instructions wherein a particular portion of a shared computational resource is accessed within the particular instruction path;

receiving data that indicates a processor is to execute the particular instruction path;

in response to receiving data that indicates the processor is to execute the particular instruction path, sending, to a thread scheduler different from the processor, switch data that indicates the processor should switch to another thread and that indicates the path ID; and

executing the particular instruction path to access the particular portion of the shared computational resource when the thread scheduler determines based on the path ID that no other thread is eligible to execute the particular instruction path to access the particular portion of the shared computational resource.

10. A method as recited in claim 9, said step of receiving data that indicates the unique path identifier (ID) further comprising the steps of:

receiving data that indicates a particular queue of data to be processed by the particular instruction path; and

determining the path ID based on the particular queue of data.

11. An apparatus for processing a thread of a plurality of threads that share a processor, comprising:

means for causing all threads of a plurality of threads that access a particular portion of a shared computational resource during a particular instruction path though one or more sequences of instructions to be received at a thread scheduler for a set of one or more processors;

means for receiving, at the thread scheduler, data that indicates a first thread of the plurality of threads is to execute next the particular instruction path to access the particular portion of the shared computational resource;

means for determining whether a second thread of the plurality of threads is exclusively eligible to execute the particular instruction path on any processor of the set of one or more processors to access the particular portion of the shared computational resource, and

means for preventing the first thread from executing any instruction from the particular instruction path on any processor of the set of one or more processors, if it is determined that the second thread is exclusively eligible to execute the particular instruction path.

12. An apparatus comprising:

one or more processors;

software encoded as instructions in one or more computer-readable media for execution on the one or more processors;

a computational resource to be shared among a plurality of execution threads executing the software on the one or more processors;

a single thread scheduler for scheduling the plurality of execution threads, wherein the thread scheduler includes logic encoded in one or more tangible media for execution and, when executed, operable for;

receiving data that indicates a first thread of the plurality of execution threads is to execute next a particular instruction path in the software to access a particular portion of the computational resource;

determining whether a second thread of the plurality of threads is exclusively eligible to execute the particular instruction path on any processor of the one or more processors to access the particular portion of the computational resource, and

if it is determined that the second thread is exclusively eligible to execute the particular instruction path, then preventing the first thread from executing any instruction from the particular instruction path on any processor of the one or more processors.

13. An apparatus as recited in claim 12, wherein the logic, when executed, is further operable for, if it is determined that no other thread is exclusively eligible to execute the particular instruction path to access the particular portion of the shared computational resource, then marking the first thread as exclusively eligible to execute the particular instruction path on any processor of the one or more processors to access the particular portion of the shared computational resource.

14. An apparatus as recited in claim 12, wherein the logic, when executed, is further operable for, if it is determined that the second thread is exclusively eligible to execute the particular instruction path to access the particular portion of the shared computational resource, then performing the steps of:

receiving data that indicates the second thread rescinds exclusive use of the particular instruction path to access the particular portion of the shared computational resource; and

in response to receiving data that indicates the second thread rescinds exclusive use of the particular instruction path, marking the second thread as not exclusively eligible to execute the particular instruction path on any processor of the one or more processors to access the particular portion of the shared computational resource.

15. An apparatus as recited in claim 14, the step of receiving data that indicates the second thread rescinds exclusive use of the particular instruction path further comprising receiving data that indicates the second thread is to executer next an instruction path different from the particular instruction path.

16. An apparatus as recited in claim 12, wherein the particular instruction path does not include an instruction to request an exclusive lock on the particular portion of the shared computational resource.

17. An apparatus as recited in claim 13, wherein a thread of the plurality of execution threads is not marked as exclusively eligible to execute the particular instruction path on any processor of the one or more processors based on order of data packets received on a network interface.

18. An apparatus as recited in claim 12, wherein the logic, when executed, is further operable for, if it is determined that no other thread is exclusively eligible to execute the particular instruction path to access the particular portion of the shared computational resource, then storing, in flag data associated with data that indicates the first thread, a value that indicates a lock is granted for the first thread for exclusive execution of the particular instruction path to access the particular portion of the shared computational resource.

19. An apparatus as recited in claim 18, wherein:

said step of receiving data that indicates the first thread of the plurality of threads is to execute next the particular instruction path further comprises the step of receiving a path identifier (ID) that uniquely indicates the particular instruction path to access the particular portion of the shared computational resource;

the method further comprises, in response to the step of receiving the path ID, storing data that indicates the path ID in association with data that indicates the first thread; and

said step of determining whether the second thread of the plurality of threads is exclusively eligible to execute the particular instruction path further comprises determining whether flag data associated with data that indicates the second thread holds a value that indicates a lock is granted for exclusive execution of the particular path to access the particular portion of the shared computational resource.

20. An apparatus as recited in claim 12, wherein:

the apparatus further comprises a network interface that is in communication with a packet-switched network for communicating therewith a data packet;

all data packets belonging to a particular flow are processed by the one or more processors for which threads are scheduled by the thread controller.

21. An apparatus as recited in claim 12, wherein the software, when executed on the one or more processors, is operable for:

receiving data that indicates a unique path identifier (ID) for the particular instruction path within the software;

determining that the particular instruction path is to be executed by a processor executing a current thread of the plurality of threads;

in response to determining that the particular instruction path is to be executed, sending, to the thread scheduler, switch data that indicates the processor executing the current thread should switch to another thread and that indicates the path ID; and

executing the particular instruction path to access the particular portion of the computational resource when the thread scheduler determines based on the path ID that no other thread is eligible to execute the particular instruction path to access the particular portion of the shared computational resource.

22. A method for achieving near line rate processing of data packets at a router comprising the steps of:

receiving over a first network interface a first set of one or more data packets;

storing data based on the first set of one or more data packets in a particular queue in a shared memory; and

determining a second set of one or more data packets to send through a different second network interface based on data in the particular queue, including the steps of;

receiving, at a thread scheduler, data that indicates a first thread of a plurality of threads is to execute next a particular instruction path that includes one or more instructions to access the particular queue;

determining whether a second thread of the plurality of threads is exclusively eligible to execute the particular instruction path on any processor of a set of one or more processors to access the particular queue; and

if it is determined that the second thread is exclusively eligible to execute the particular instruction path to access the particular queue, then preventing the first thread from executing any instruction from the particular instruction path on any processor of the set of one or more processors to access the particular queue.