Maintaining Processing Order While Permitting Parallelism

• US 20080235690A1
• Filed: 03/18/2008
• Published: 09/25/2008
• Est. Priority Date: 03/23/2007
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Ang, Boon Seong, Ramanan, Jyothir, Lambeth, Andrew
• Granted Patent: US 8,584,126 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 2209/548 Queue
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

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.

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;

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

2. The method of claim 1, wherein determining if the lock associated with the second stage is available comprises:

attempting to take the lock associated with the second stage; and

determining if the attempt to take the lock associated with the second stage was successful.

3. The method of claim 1, further comprising:

if the lock associated with the second stage is available, taking a second piece of work from the queue associated with the second stage and performing the task associated with the second stage on the second piece of work.

4. The method of claim 3, further comprising:

taking a lock associated with a third stage;

performing a task associated with the third stage on the second piece of work; and

performing the task associated with the third stage on the first piece of work.

5. The method of claim 1, further comprising:

if the lock associated with the second stage is not available, taking a second piece of work from the queue associated with the first stage and performing the task associated with the first stage on the second piece of work.

6. The method of claim 5, further comprising:

taking the lock associated with the second stage;

performing the task associated with the second stage on the first piece of work; and

performing the task associated with the second stage on the second piece of work.

7. The method of claim 1, further comprising:

determining if the queue associated with the second stage contains a second piece of work.

8. The method of claim 1, further comprising:

performing the task associated with the first stage on a second piece of work.

9. The method of claim 8, further comprising:

if the lock associated with the second stage is available, storing the second piece of work in a queue associated with a third stage.

10. The method of claim 8, further comprising:

if the lock associated with the second stage is not available, taking a lock associated with a third stage and performing a task associated with the third stage on the second piece of work.

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

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.

12. The method of claim 11, further comprising:

if the lock associated with the second stage is available, taking a second packet from the queue associated with the second stage and performing the task associated with the second stage on the second packet.

13. The method of claim 12, further comprising:

taking a lock associated with a third stage;

performing a task associated with the third stage on the second packet; and

performing the task associated with the third stage on the first packet.

14. The method of claim 11, further comprising:

if the lock associated with the second stage is not available, taking a second packet from the queue associated with the first stage and performing the task associated with the first stage on the second packet.

15. The method of claim 14, further comprising:

taking the lock associated with the second stage;

performing the task associated with the second stage on the first packet; and

performing the task associated with the second stage on the second packet.

16. The method of claim 11, further comprising:

performing the task associated with the first stage on a second packet.

17. The method of claim 16, further comprising:

if the lock associated with the second stage is available, storing the second packet in a queue associated with a third stage.

18. The method of claim 16, further comprising:

if the lock associated with the second stage is not available, taking a lock associated with a third stage and performing a task associated with the third stage on the second packet.

19. The method of claim 11, wherein performing the task associated with the first stage comprises checking the first packet for errors.

20. The method of claim 11, wherein performing the task associated with the first stage comprises identifying a destination address of the first packet.

21. The method of claim 11, wherein performing the task associated with the first stage comprises determining a virtual switch port for transmission of the first packet.

22. The method of claim 11, wherein performing the task associated with the second stage comprises delivering the first packet to a virtual machine monitor.

23. 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.

24. A system for maintaining processing order while permitting parallelism, the system comprising:

a first queue;

a first lock;

a second lock; and

a first thread of execution, the first thread of execution is configured to take the first lock, perform a first task on a first piece of work, determine if the second lock is available, and, 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.

25. The system of claim 24, further comprising:

a second thread of execution, the second thread of execution is configured to take the first lock, perform a first task on a second piece of work, determine if the second lock is available, and, if the second lock is available, take the second lock and perform a 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.

26. A computer program product for processing pieces of work in a plurality of stages, the computer program product comprising a computer-readable medium containing computer program code for:

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;

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

27. The computer program product of claim 26, wherein determining if the lock associated with the second stage is available comprises:

attempting to take the lock associated with the second stage; and

determining if the attempt to take the lock associated with the second stage was successful.

28. The computer program product of claim 26, wherein the computer-readable medium further contains computer program code for:

if the lock associated with the second stage is available, taking a second piece of work from the queue associated with the second stage and performing the task associated with the second stage on the second piece of work.

29. The computer program product of claim 28, wherein the computer-readable medium further contains computer program code for:

taking a lock associated with a third stage;

performing a task associated with the third stage on the second piece of work; and

performing the task associated with the third stage on the first piece of work.

30. The computer program product of claim 26, wherein the computer-readable medium further contains computer program code for:

if the lock associated with the second stage is not available, taking a second piece of work from the queue associated with the first stage and performing the task associated with the first stage on the second piece of work.

31. The computer program product of claim 30, wherein the computer-readable medium further contains computer program code for:

taking the lock associated with the second stage;

performing the task associated with the second stage on the first piece of work; and

performing the task associated with the second stage on the second piece of work.

32. The computer program product of claim 26, wherein the computer-readable medium further contains computer program code for:

determining if the queue associated with the second stage contains a second piece of work.

33. The computer program product of claim 26, wherein the computer-readable medium further contains computer program code for:

performing the task associated with the first stage on a second piece of work.

34. The computer program product of claim 33, wherein the computer-readable medium further contains computer program code for:

if the lock associated with the second stage is available, storing the second piece of work in a queue associated with a third stage.

35. The computer program product of claim 33, wherein the computer-readable medium further contains computer program code for:

if the lock associated with the second stage is not available, taking a lock associated with a third stage and performing a task associated with the third stage on the second piece of work.

36. A computer program product for processing packets in a virtual switch connected to a plurality of virtual machines, the computer program product comprising a computer-readable medium containing computer program code for:

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.

37. The computer program product of claim 36, wherein the computer-readable medium further contains computer program code for:

if the lock associated with the second stage is available, taking a second packet from the queue associated with the second stage and performing the task associated with the second stage on the second packet.

38. The computer program product of claim 37, wherein the computer-readable medium further contains computer program code for:

taking a lock associated with a third stage;

performing a task associated with the third stage on the second packet; and

performing the task associated with the third stage on the first packet.

39. The computer program product of claim 36 wherein the computer-readable medium further contains computer program code for:

if the lock associated with the second stage is not available, taking a second packet from the queue associated with the first stage and performing the task associated with the first stage on the second packet.

40. The computer program product of claim 39, wherein the computer-readable medium further contains computer program code for:

taking the lock associated with the second stage;

performing the task associated with the second stage on the first packet; and

performing the task associated with the second stage on the second packet.

41. The computer program product of claim 36, wherein the computer-readable medium further contains computer program code for:

performing the task associated with the first stage on a second packet.

42. The computer program product of claim 41, wherein the computer-readable medium further contains computer program code for:

if the lock associated with the second stage is available, storing the second packet in a queue associated with a third stage.

43. The computer program product of claim 41, wherein the computer-readable medium further contains computer program code for:

if the lock associated with the second stage is not available, taking a lock associated with a third stage and performing a task associated with the third stage on the second packet.

44. The computer program product of claim 36, wherein performing the task associated with the first stage comprises checking the first packet for errors.

45. The computer program product of claim 36, wherein performing the task associated with the first stage comprises identifying a destination address of the first packet.

46. The computer program product of claim 36, wherein performing the task associated with the first stage comprises determining a virtual switch port for transmission of the first packet.

47. The computer program product of claim 36, wherein performing the task associated with the second stage comprises delivering the first packet to a virtual machine monitor.

48. A computer program product for processing pieces of work in a plurality of stages, the computer program product comprising a computer-readable medium containing computer program code for:

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.