Group and virtual locking mechanism for inter processor synchronization

• US 6,662,252 B1
• Filed: 12/08/2002
• Issued: 12/09/2003
• Est. Priority Date: 11/03/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Marshall, John William, Potter, Kenneth H.
• Primary Examiner(s): THAI, XUAN MARIAN
• Application Number:
  US10/314,748
• Time in Patent Office: 366 Days
• Field of Search: 710/200, 710/108, 709/213, 709/214, 709/215, 709/248, 709/200, 707/8, 711/100, 711/147, 711/150, 711/153, 711/163, 711/168
• US Class Current: 710/200
• CPC Class Codes: G06F 2209/522 Manager
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A group and virtual locking mechanism (GVLM) addresses two classes of synchronization present in a system having resources that are shared by a plurality of threads of execution: (1) synchronization of the multi-access shared resources; and (2) simultaneous requests for the shared resources. Broadly stated, the novel GVLM comprises a lock controller function associated with each thread of execution, and lock instructions executed by the threads that manipulate the lock controller to create a tightly integrated arrangement for issuing lock requests to the shared resources. The plurality of threads of execution may each execute in a different processor. Alternatively, the plurality of threads of execution may each execute in a single processor.

Claims

1. Apparatus for enabling a plurality of threads of execution to simultaneously access a shared resource of a programmable processor, comprising:

a lock controller associated with a plurality of threads of execution; and

a lock instruction, the lock instruction executed by a particular thread of execution of the plurality of threads of execution when the particular thread requires a lock in the shared resource, the lock instruction cooperating with the lock controller to generate a lock request to the shared resource, the lock request merged with group information from other threads of execution requesting a lock, the lock controller thereby managing requests by the plurality of threads of execution for the shared resource.

2. The apparatus as in claim 1, further comprising:

each thread of execution of the plurality of threads of execution executing in a different processor.

3. The apparatus as in claim 1, further comprising:

each thread of execution of the plurality of threads of execution executing in a different processor of an array of processors, the array arranged in rows and columns, and the lock controller associated a column of the array.

4. The apparatus as in claim 1, further comprising:

all threads of execution of the plurality of threads of execution executing in one processor.

5. The apparatus as in claim 1, further comprising:

the lock request includes a virtual semaphore identifier specifying at least one region of the shared resource for access by the processor.

6. The apparatus as in claim 1, further comprising:

the lock instruction is a get virtual semaphore (xgvs) instruction that allows a processor to obtain a virtual lock.

7. The apparatus as in claim 6, further comprising:

the xgvs instruction includes a group select parameter and a reference to a register storing the virtual semaphore identifier.

8. The apparatus as in claim 7 further comprising:

a clear semaphore (xcs) instruction that clears the virtual lock, the xcs instruction including a group select parameter indicating the region to be unlocked.

9. The apparatus as in claim 1, further comprising:

the lock instruction is a get binary semaphore instruction that allows a processor to lock the entire resource.

10. The apparatus as in claim 1, further comprising:

the lock instruction requests locking of multiple shared resources at the same time.

11. The apparatus as in claim 1, further comprising:

the lock instruction is one of a get virtual semaphore (xgvs) instruction and a get binary semaphore (xgbs) instruction that simultaneously specifies multiple regions to be locked, thereby avoiding a deadlock situation.

12. A method for accessing a shared resource of a processor, comprising:

associating a plurality of threads of execution with a lock controller;

executing a lock instruction, the lock instruction executed by a particular thread of execution of the plurality of threads of execution when the particular thread requires a lock in the shared resource, the lock instruction cooperating with the lock controller to generate a lock request to the shared resource; and

merging the lock request with group information from other threads of execution requesting a lock, the lock controller thereby managing requests by the plurality of threads of execution for the shared resource.

13. The method of claim 12, further comprising:

executing each thread of execution of the plurality of threads of execution in a different processor.

14. The method of claim 12, further comprising:

executing each thread of execution of the plurality of threads of execution in a different processor of an array of processors, the array arranged in rows and columns, and the lock controller associated a column of the array.

15. The method of claim 12, further comprising:

executing all threads of execution of the plurality of threads of execution in one processor.

16. The method of claim 12, further comprising:

specifying by the lock request a virtual semaphore identifier which specifies at least one region of the shared resource for access by the processor.

17. The method of claim 12, further comprising:

specifying the lock instruction as a get virtual semaphore (xgvs) instruction that allows a processor to obtain a virtual lock.

18. The method of claim 17, further comprising:

specifying the xgvs instruction to include a group select parameter and a reference to a register storing the virtual semaphore identifier.

19. The method of claim 17, further comprising:

specifying a clear semaphore (xcs) instruction that clears the virtual lock, the xcs instruction including a group select parameter indicating the region to be unlocked.

20. The method of claim 12, further comprising:

specifying the lock instruction as a get binary semaphore instruction that allows a processor to lock the entire resource.

21. The method of claim 12, further comprising:

the lock instruction requests locking of multiple shared resources at the same time.

22. The method of claim 12, further comprising:

specifying the lock instruction as one of a get virtual semaphore (xgvs) instruction and a get binary semaphore (xgbs) instruction that simultaneously specifies multiple regions to be locked, thereby avoiding a deadlock situation.

27. A computer readable media, comprising:

said computer readable media having instructions written thereon for execution on a processor for the practice of the method of claim 12.

28. Electromagnetic signals propagating on a computer network, comprising:

said electromagnetic signals carrying instructions for execution on a processor for the practice of the method of claim 12.

23. Apparatus for enabling a plurality of threads of execution to simultaneously access a shared resource of a programmable processor, comprising:

means for associating the plurality of threads of execution with a lock controller;

means for executing a lock instruction, the lock instruction executed by a particular thread of execution of the plurality of threads of execution when the particular thread requires a lock in the shared resource, the lock instruction cooperating with the lock controller to generate a lock request to the shared resource; and

means for merging the lock request with group information from other threads of execution requesting a lock, the lock controller thereby managing requests by the plurality of threads of execution for the shared resource.

24. The apparatus of claim 23, further comprising:

means for executing each thread of execution of the plurality of threads of execution in a different processor.

25. The apparatus of claim 23, further comprising:

means for executing each thread of execution of the plurality of threads of execution in a different processor of an array of processors, the array arranged in rows and columns, and the lock controller associated a column of the array.

26. The apparatus of claim 23, further comprising:

means for executing all threads of execution of the plurality of threads of execution in one processor.