Systems and methods for enabling threads to lock a stage prior to processing data
First Claim
Patent Images
1. A method for processing pieces of work in a plurality of stages, the method comprising:
- taking a lock associated with a first stage;
performing a task associated with the first stage on a first piece of work;
determining if a lock associated with a second stage is available; and
if the lock associated with the second stage is not available, storing the first piece of work in a queue associated with the second stage and taking a second piece of work from a queue associated with the first stage and performing the task associated with the first stage on the second piece of work.
2 Assignments
0 Petitions
Accused Products
Abstract
A system and method for maintaining processing order while permitting parallelism. Processing of a piece of work is divided into a plurality of stages. At each stage, a task advancing the work towards completion is performed. By performing processing as a sequence of tasks, processing can be done in parallel, with progress being made simultaneously on different pieces of work in different stages by a plurality of threads of execution.
-
Citations
49 Claims
-
1. A method for processing pieces of work in a plurality of stages, the method comprising:
-
taking a lock associated with a first stage; performing a task associated with the first stage on a first piece of work; determining if a lock associated with a second stage is available; and if the lock associated with the second stage is not available, storing the first piece of work in a queue associated with the second stage and taking a second piece of work from a queue associated with the first stage and performing the task associated with the first stage on the second piece of work. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A method for processing packets in a virtual switch connected to a plurality of virtual machines, the method comprising:
-
taking a lock associated with a first stage; performing a task associated with the first stage on a first packet; determining if a lock associated with a second stage is available; and if the lock associated with the second stage is not available, storing the packet in a queue associated with the second stage and taking a second packet from a queue associated with the first stage and performing the task associated with the first stage on the second packet. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
21. A method for processing pieces of work in a plurality of stages, the method comprising:
-
taking a first lock associated with a first stage; performing a task associated with the first stage on a first piece of work; taking a second lock associated with the first stage; releasing the first lock associated with the first stage; determining if a lock associated with a second stage is available; if the lock associated with the second stage is available, taking the lock associated with the second stage, releasing the second lock associated with the first stage, and performing a task associated with the second stage on the first piece of work; and if the lock associated with the second stage is not available, storing the first piece of work in a queue associated with the second stage and releasing the second lock associated with the first stage.
-
-
22. A system for maintaining processing order while permitting parallelism, the system comprising:
-
a first queue associated with a first stage; a first lock associated with the first stage; a second lock associated with a second stage; a first thread of execution assigned to a first piece of work, wherein the first thread of execution is configured to; take the first lock; perform a first task associated with the first stage on the first piece of work; determine if the second lock is available; if the second lock is available, take the second lock and perform a second task on the first piece of work; and if the second lock is not available, store the first piece of work in the first queue; and a second thread of execution assigned to a second piece of work, wherein the second thread of execution is configured to; take the first lock; perform the first task on the second piece of work; determine if the second lock is available; if the second lock is available, take the second lock and perform the second task on the second piece of work; and if the second lock is not available, store the second piece of work in the first queue.
-
-
23. A non-transitory computer-readable storage medium comprising computer-readable instructions for processing pieces of work in a plurality of stages, the computer-readable storage medium causing one or more processors to perform the steps of:
-
taking a lock associated with a first stage; performing a task associated with the first stage on a first piece of work; determining if a lock associated with a second stage is available; and if the lock associated with the second stage is not available, storing the first piece of work in a queue associated with the second stage and taking a second piece of work from a queue associated with the first stage and performing the task associated with the first stage on the second piece of work. - View Dependent Claims (24, 25, 26, 27, 28, 29, 30, 31)
-
-
32. A non-transitory computer-readable storage medium comprising computer-readable instructions for processing packets in a virtual switch connected to a plurality of virtual machines, the computer-readable storage medium causing one or more processors to perform the steps of:
-
taking a lock associated with a first stage; performing a task associated with the first stage on a first packet; determining if a lock associated with a second stage is available; if the lock associated with the second stage is available, taking the lock associated with the second stage, releasing the lock associated with the first stage, and performing a task associated with the second stage on the first packet; and if the lock associated with the second stage is not available, storing the packet in a queue associated with the second stage and taking a second packet from a queue associated with the first stage and performing the task associated with the first stage on the second packet. - View Dependent Claims (33, 34, 35, 36, 37, 38, 39, 40, 41, 42)
-
-
43. A non-transitory computer-readable storage medium for processing pieces of work in a plurality of stages, the computer-readable storage medium causing one or more processors to perform the steps of:
-
taking a first lock associated with a first stage; performing a task associated with the first stage on a first piece of work; taking a second lock associated with the first stage; releasing the first lock associated with the first stage; determining if a lock associated with a second stage is available; if the lock associated with the second stage is available, taking the lock associated with the second stage, releasing the second lock associated with the first stage, and performing a task associated with the second stage on the first piece of work; and if the lock associated with the second stage is not available, storing the first piece of work in a queue associated with the second stage and releasing the second lock associated with the first stage.
-
-
44. A method for processing packets in a virtual switch connected to a plurality of virtual machines, the method comprising:
-
assigning a thread of execution to a first packet; executing the thread of execution, wherein executing the thread of execution comprises; taking a lock associated with a first stage; performing a task associated with the first stage on the first packet; determining if a lock associated with a second stage is available; and if the lock associated with the second stage is available; taking the lock associated with the second stage; releasing the lock associated with the first stage; determining if a second packet is in a queue associated with the second stage; and if a second packet is in the queue associated with the second stage, performing a task associated with the second stage on the second packet prior to performing the task associated with the second stage on the first packet. - View Dependent Claims (45, 46)
-
-
47. A system comprising:
-
a virtual machine monitor comprising a virtual network interface controller, the virtual network interface controller comprising a first processing stage and a lock for the first processing stage; a virtual network switch comprising a second processing stage and a lock for the second processing stage; and at least one processor programmed to; take the lock for the first processing stage; perform a task associated with the first processing stage on a piece of work; determine if the lock for the second stage is available; and if the lock associated with the second stage is not available, store the piece of work in a queue associated with the second stage, take a second packet from a queue associated with the first stage, and perform the task associated with the first stage on the second packet.
-
-
48. A system comprising:
-
a virtual network switch comprising a first processing stage and a lock for the first processing stage; a virtual machine monitor comprising a virtual network interface controller, the virtual network interface controller comprising a second processing stage and a lock for the second processing stage; and at least one processor programmed to; take the lock for the first processing stage; perform a task associated with the first processing stage on a piece of work; determine if the lock for the second stage is available; and if the lock associated with the second stage is not available, store the piece of work in a queue associated with the second stage, take a second packet from a queue associated with the first stage, and perform the task associated with the first stage on the second packet.
-
-
49. A method for maintaining processing order while permitting parallelism, the method comprising:
-
assigning a first thread of execution to a first piece of work; executing the first thread of execution, wherein executing the first thread of execution comprises; taking a first lock associated with a first stage; performing a first task associated with the first stage on the first piece of work; determining if a second lock associated with a second stage is available; if the second lock is available, taking the second lock and perform a second task on the first piece of work; and if the second lock is not available, storing the first piece of work in a first queue associated with the first stage; and assigning a second thread of execution to a second piece of work; and executing the second thread of execution, wherein executing the second thread of execution comprises; taking the first lock; performing the first task on the second piece of work; determining if the second lock is available; if the second lock is available, taking the second lock and performing the second task on the second piece of work; and if the second lock is not available, storing the second piece of work in the first queue.
-
Specification