System and method for hardware assisted spinlock

• US 6,792,497 B1
• Filed: 05/09/2001
• Issued: 09/14/2004
• Est. Priority Date: 12/12/2000
• Status: Expired due to Fees

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Sanderson, Andrew F., McCrory, Duane J., Gold, Anthony P.
• Primary Examiner(s): Dang, Khanh
• Application Number:
  US09/851,795
• Time in Patent Office: 1,224 Days
• Field of Search: 710/200, 710/240, 710/317, 709/216, 709/104, 711/170, 711/216
• US Class Current: 710/317
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A crossbar structure for use in a multi-processor computer system to connect a plurality of processors to at least one shared resource. The crossbar structure comprises for each processor, a storage location for receiving from a respective processor a memory address of a lock control structure associated with the shared resource. When the processor needs to acquire a lock thereto, the crossbar structure, on behalf of the processor, performs memory operations on the lock control structure at the address specified in the storage location in order to acquire the lock on behalf of the processor.

Claims

1. A multiple processor computer system comprising:

a plurality of processors;

a shared resource;

a main memory in communication with the plurality of processors, at least a portion thereof comprising a control structure for controlling a lock on said shared resource; and

a crossbar structure connecting the plurality of processors to the shared resource for controlling access among the processors to the shared resource, the crossbar structure comprising;

for each processor, a corresponding first storage location, one of the plurality of processors writing to a first storage location corresponding to the one processor, an address of the lock control structure associated with said shared resource to acquire the lock thereto, the crossbar structure, on behalf the one processor, performing memory operations on the lock control structure at the address specified in the corresponding first storage location in order to acquire the lock on behalf of the one processor;

a second storage location corresponding to a respective processor in the multi-processor system, one of the plurality of processors writing to the corresponding second storage location an address of the lock control structure associated with said shared resource to release the lock thereto, the crossbar structure, on behalf of the processor, performing memory operations on the lock control structure at the address specified in the corresponding second storage location in order to release the lock on behalf of the processor; and

a third storage location corresponding to a respective processor in the multi-processor system for storing a current interrupt priority level associated with the processor wherein the current interrupt priority level represents the level of interrupt that the processor will service while spinning on a lock.

2. The multiple processor computer system of claim 1 wherein the crossbar structure further comprises a forth storage location corresponding to a respective processor in the multi-processor system for storing a future interrupt priority level associated with the processor wherein the future interrupt priority level represents the level of interrupt that the processor will operate at upon receiving a lock.

3. The multiple processor computer system of claim 1 wherein the crossbar structure further comprises a queue for determining which processor is granted a lock.

7. The multiple processor computer system of claim 1 further comprising a multi-processor module.

8. The multiple processor computer system of claim 7 wherein the multi-processor module comprises at least two of the plurality of processors.

9. The multiple processor computer system of claim 1 wherein the shared resource comprises at least a portion of memory.

10. The multiple processor computer system of claim 1 wherein the shared resource comprises an I/O device.

11. The multiple processor computer system of claim 1 wherein the shared resource comprises a register.

4. A multiple processor computer system comprising:

a plurality of processors;

a shared resource;

a main memory in communication with the plurality of processors, at least a portion thereof comprising a control structure for controlling a lock on said shared resource; and

a crossbar structure connecting the plurality of processors to the shared resource for controlling access among the processors to the shared resource, the crossbar structure comprising;

for each processor, a corresponding storage location, one of the plurality of processors writing to a storage location corresponding to the one processor, an address of the crossbar structure, on behalf of the one processor, performing memory operations on the lock control structure at the address specified in the corresponding storage location in order to acquire the lock on behalf of the one processor; and

,

a queue for determining which processor is granted a lock, wherein the queue comprises a plurality of entries, each entry comprising a first data field for containing a processor identification, a second data field for containing a lock request time, and a third data field for containing a priority of a request for a lock.

5. The multiple processor computer system of claim 4 wherein each request for a lock on the shared resource has a corresponding entry in the queue, and wherein the crossbar structure determines which request is granted the lock based at least in part upon the respective priorities contained in the third data fields of the queue entries for each request.

6. The multiple processor computer system of claim 5 wherein if the third data fields of more than one of the queue entries contains the same and highest priority, the crossbar structure further determines which request is granted the lock based upon the respective lock request times contained in the second data fields of those queue entries.

12. A crossbar structure for use in a multi-processor computer system to connect a plurality of processors to at least one shared resource, the crossbar structure comprising for each processor:

a corresponding second storage location for receiving from the respective processor a memory address of a lock control structure associated with said shared resource, wherein to release a lock thereto, the crossbar structure, on behalf of a processor, performs memory operations on the lock control structure at the address specified in the corresponding second storage location in order to release the lock on behalf of the processor, and,

a corresponding third storage location for receiving from the respective processor a current interrupt priority level associated with the processor wherein the current interrupt priority level represents the level of interrupt that the processor will service while spinning on a lock.

13. The crossbar structure of claim 12 further comprising:

for each processor, a corresponding fourth storage location for storing a future interrupt priority level associated with the processor wherein the future interrupt priority level represents the level of interrupt that the processor will operate upon receiving a lock.

14. The crossbar structure of claim 12 further comprising a queue for determining which processor is granted a lock.

15. A crossbar structure for use in a multi-processor computer system to connect a plurality of processors to at least one shared resource, the crossbar structure comprising:

for each processor, a corresponding storage location for receiving from the respective processor a memory address of a lock control structure associated with said shared resource;

wherein to acquire a lock thereto, the crossbar structure, on behalf of a processor, performs memory operations on the lock control structure at the address specified in the corresponding storage location in order to acquire the lock on behalf of the processor; and

,

a queue for determining which processor is granted a lock, wherein the queue comprises a plurality of entries, each entry comprising a first data field for containing a processor identification, a second data field for containing a lock request time, and a third data field for containing a priority of a request for a lock.

16. The crossbar structure of claim 15 wherein each request for a lock on the shared resource has a corresponding entry in the queue, and wherein the crossbar structure determines which request is granted the lock based at least in part upon the respective priorities contained in the third data fields of the queue entries for each request.

17. The crossbar structure of claim 16 wherein if the third data fields of more than one of the queue entries contains the same and highest priority, the crossbar structure further determines which request is granted the lock based upon the respective lock request times contained in the second data fields of those queue entries.

18. A method for acquiring a lock to a shared resource in a multiprocessor computer system, the multiprocessor computer system comprising a plurality of processors, a main memory, and a crossbar structure comprising, for each processor, a first storage location for storing a memory address of a control structure associated with said shared resource to be locked, the method comprising:

writing, by one of said processors, the memory address of said control structure to said first storage location corresponding to said one processor when said one processor needs to acquire a lock on said shared resource;

performing, by said crossbar structure, on behalf of said one processor, a memory operation on the control structure at the memory address stored in said corresponding first storage location in an attempt to acquire a lock to said shared resource;

returning a status of the memory operation to said one processor; and

,

storing a current interrupt priority level associated with said one processor wherein the current interrupt priority level represents the level of interrupt that said one processor will service while spinning on a lock.

19. The method of claim 18 wherein performing a memory operation comprises performing a test and set operation.

20. The method claim 18 further comprising storing a future interrupt priority level associated with said one processor wherein the future interrupt priority level represents the level of interrupt that said one processor will service upon receiving a lock.

21. The method of claim 20 further comprising a comprising a determining a processor from the plurality of processors to be granted a lock based on a queue.

22. The method of claim 21 wherein determining a processor further comprises:

reading at least one priority field and a processor identification corresponding to each priority field, from the queue;

determining that more than one priority field contains the same and highest priority;

reading a time field corresponding to each priority field containing the same and highest priority;

determining a processor based on the processor identification corresponding the earliest time in the fields; and

granting the lock to the determined processor corresponding to the earliest time in the time fields.

23. The method of claim 21 wherein the determining a processor further comprises:

reading at least one priority and a processor identification corresponding to each priority, from the queue;

selecting the highest priority of the read at least one priority;

determining a processor based on the processor identification corresponding the selected highest priority; and

granting the lock to the determined processor corresponding to the selected highest priority.

24. The method of claim 20 wherein storing the future interrupt priority level further comprises copying a value contained in a current interrupt priority register to a future interrupt priority register prior to writing, one of said processors, the memory address.

25. The method of claim 24 further comprising copying a value contained in a future interrupt priority register to a current interrupt priority register.

26. A method for use in a multi-processor computer system having a crossbar structure that connects a plurality of processors to at least one shared resource, the method comprising:

receiving at the crossbar form one of said processors, a memory address of a lock control structure associated with said shared resource when the processor needs to acquire a lock thereto;

performing at the crossbar structure, on behalf of said one processor, a memory operation on the lock control structure at the memory address received from said one processor in order to acquire the lock on behalf of said one processor, and,

performing at the crossbar structure memory operations on the lock control structure at the memory address received from said one processor, continually, until an unlock status is received.

27. The method of claim 26 further comprising storing the memory address received from said one processor in a respective storage location within the crossbar structure.

28. The method of claim 26 further comprising determining a status of the lock control structure at the memory address received from said one processor.

29. The method of claim 28 further comprising sending to said one processor the determined status of the lock control structure.

30. The method of claim 26 wherein performing a memory operation comprises performing a test and set operation.

31. The method of claim 26 further comprising a receiving a current interrupt priority level associated with said one processor wherein the current interrupt priority level represents the level of interrupt that said one processor will service while spinning on a lock.

32. The method of claim 26 further comprising storing a future interrupt priority level associated with said one processor wherein the future interrupt priority level represents the level of interrupt that said one processor will service upon receiving a lock.

33. The method of claim 26 further comprising determining a processor from the plurality of processors to be granted a lock based on a queue.

34. A method for use in a multi-processor computer system having a crossbar structure that connects a plurality of processors to at least one shared resource, the method comprising:

receiving at the crossbar from one of said processors, a memory address of a lock control structure associated with said shared resource when the processor needs to acquire a lock thereto;

performing at the crossbar structure, on behalf of said one processor, a memory operation on the lock control structure at the memory address received from said one processor in order to acquire the lock on behalf of said one processor, and,

determining a processor from the plurality of processors to be granted a lock based on a queue, wherein the determining a processor further comprises;

reading at least one priority and a processor identification corresponding to each priority, from the queue;

selecting the highest priority of the read at least one priority;

determining a processor based on the processor identification corresponding the selected highest priority; and

granting the lock to the determined processor corresponding to the selected highest priority.

35. A computer-readable having instructions stored thereon for use in a multi-processor computer system having a crossbar structure that connects a plurality of processors to at least one shared resource, the instructions, when executed on the crossbar structure, causing the crossbar structure to perform the following:

receiving at the crossbar from one of said processors, a memory address of a lock control structure associated with said shared resource when the processor needs to acquire a lack thereto;

performing at the crossbar structure, on behalf of said one processor, a memory operation on the lock control structure at the memory address received from said one processor in order to acquire the lock on behalf of said one processor, and

receiving a current interrupt priority level associated with said one processor wherein the current interrupt priority level represents the level of interrupt that said one processor will service while spinning on a lock.

36. The computer-readable medium of claim 35 wherein the instructions further cause the crossbar to perform storing the memory address received from said one processor in a respective storage location within the crossbar structure.

37. The computer-readable medium of claim 35 wherein the instructions further cause the crossbar to perform determining a status of the lock control structure at the memory address received from said one processor.

38. The computer-readable medium of claim 37 wherein the instructions further cause the crossbar to perform sending to said one processor the determined status of the lock control structure.

39. The computer-readable medium of claim 35 wherein the instructions further cause the crossbar to perform performing at the crossbar structure memory operations on the lock control structure at the memory address from said one processor, continually, until an unlocked status is received.

40. The computer-readable medium of claim 35 wherein performing a memory operation comprises performing a test and set operation.

41. The computer-readable medium of claim 35 wherein the instructions further cause the crossbar to perform storing a future interrupt priority level associated with said one processor wherein the future interrupt priority level represents the level of interrupt that said one processor will service upon receiving a lock.

42. The computer-readable medium of claim 35 wherein the instructions further cause the crossbar to perform determining a processor from the plurality of processors to be granted a lock based on a queue.

43. A computer-readable medium having instructions stored thereon for use in a multi-processor computer system having a crossbar structure that connects a plurality of processors to at least one shared resource, the instructions, when executed on the crossbar structure, causing the crossbar structure to perform the following:

receiving at the crossbar from one of said processors, a memory address of a lock control structure associated with said shared resource when the processor needs to acquire a lock thereto;

performing at the crossbar structure, on behalf of said one processor, a memory operation on the lock control structure at the memory address received from said one processor in order to acquire the lock on behalf of said one processor; and

,

determining a processor from the plurality of processors to be granted a lock based on a queue, wherein the determining a processor further comprises;

reading at least one priority and a processor identification corresponding to each priority, from the queue;

selecting the highest priority of the read at least one priority;

determining a processor based on the processor identification corresponding the selected highest priority; and

granting the lock to the determined processor corresponding to the selected highest priority.

44. A method for use in a multi-processor computer system having a crossbar structure that connects a plurality of processors to at least one shared resource, the method comprising:

receiving at the crossbar from one of said processors, a memory address of a lock control structure associated with said shared resource when the processor needs to acquire a lock thereto;

performing at the crossbar structure, on behalf of said one processor, a memory operation on the lock control structure at the memory address received from said one processor in order to acquire the lock on behalf of said one processor; and

,

determining a processor from the plurality of processors to be granted a lock based on a queue, wherein determining a processor further comprises;

reading at least one priority field and a processor identification corresponding to each priority field, from the queue;

determining that more than one priority field contains the same and highest priority,

reading a time field corresponding to each field containing the same and highest priority;

determining a processor based on the processor identification corresponding the earliest time in the time fields; and

granting the lock to the determined processor corresponding to the earliest time in the time fields.

45. A computer-readable medium having instructions stored thereon for use in a multi-processor computer system having a crossbar structure that connects a plurality of processors to at least one shared resource, the instructions, when executed on the crossbar structure, causing the crossbar structure to perform the following:

receiving at the crossbar from one of said processors, a memory address of a lock control structure associated with said shared resource when the processor needs to acquire a lock thereto; and

performing at the crossbar structure, on behalf of said one processor, a memory operation on the lock control structure at the memory address received from said one processor in order to acquire the lock on behalf of said one processor; and

,

determining a processor from the plurality of processors to be granted a lock based on a queue, wherein determining a processor further comprises;

reading at least one priority field and a processor identification corresponding to each priority field, from the queue;

determining that more than one priority field contains the same and highest priority;

reading a time field corresponding to each priority field containing the same and highest priority;

determining a processor based on the processor identification corresponding the earliest time in the time fields; and

granting the lock to the determined processor corresponding to the earliest time in the time fields.