Processor acquisition of ownership of access coordinator for shared resource

• US 7,861,042 B2
• Filed: 10/23/2006
• Issued: 12/28/2010
• Est. Priority Date: 10/23/2006
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Johnson, Robert, Larson, Douglas V.
• Primary Examiner(s): Ellis; Kevin L
• Assistant Examiner(s): Namazi; Mehdi
• Application Number:
  US11/552,103
• Publication Number:
  US 20080098180A1
• Time in Patent Office: 1,527 Days
• Field of Search: 711/152, 711/154, 711/156, 718/102, 718/103, 710/240, 710/36, 710/37, 710/38, 710107-125, 706/10, 714/2, 714/25
• US Class Current: 711/152
• CPC Class Codes: G06F 15/16 Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs coordinating program control therefor G06F9/52; in regulating and control system G05B

Abstract

A processor of an apparatus in an example upon a failure of an earlier attempt to directly acquire ownership of an access coordinator for a resource shared with one or more additional processors, locally determines an amount to delay a later attempt to directly acquire ownership of the access coordinator. Upon a failure of the later and/or a subsequent attempt to directly acquire ownership of the access coordinator the processor would enter into an indirect waiting arrangement for ownership of the access coordinator.

Claims

1. An apparatus, comprising:

a first processor that upon a failure of an earlier attempt to directly acquire ownership of an access coordinator for a resource shared with one or more additional processors, is configured to locally determine an amount to delay a later attempt to directly acquire ownership of the access coordinator,

wherein upon a failure of the later and/or a subsequent attempt to directly acquire ownership of the access coordinator, the first processor is configured to enter into an indirect waiting arrangement for ownership of the access coordinator, wherein the indirect waiting arrangement for ownership of the access coordinator involves organizing the first and the one or more additional processors waiting for ownership of the access coordinator to access separate structures to avoid interference between or among the first and the one or more additional processors.

2. The apparatus of claim 1, wherein the first processor, upon the failure of the later attempt to directly acquire ownership of the access coordinator, is configured to locally determine an amount to delay the subsequent attempt after the later attempt to directly acquire ownership of the access coordinator, wherein upon an occurrence of the failure of the subsequent attempt to directly acquire ownership of the access coordinator, the first processor is configured to enter into the indirect waiting arrangement for ownership of the access coordinator.

3. The apparatus of claim 1, wherein the access coordinator for the resource comprises one or more spinlocks and/or one or more blocking locks on the resource.

4. The apparatus of claim 1, wherein a plurality of processors comprise the first processor and the one or more additional processors, wherein the first processor is configured to locally determine the amount to delay the later attempt to directly acquire ownership of the access coordinator through employment of a proportional relationship between the amount and a quantity that represents how far back in line the first processor is among the plurality of processors waiting for the access coordinator.

5. The apparatus of claim 1, wherein the access coordinator for the resource comprises a single spinlock on the resource.

6. The apparatus of claim 1, wherein the first processor, upon success of the later attempt to directly acquire ownership of the access coordinator, avoids one or more cache misses that would be associated with an occurrence of entry of the first processor into the indirect waiting arrangement for ownership of the access coordinator.

7. The apparatus of claim 4, wherein the amount to delay the later attempt is based on multiplying the quantity with a parameter that represents a configurable wait time, wherein that the processor is configured to further adjust a value of the parameter based on a detected condition.

8. The apparatus of claim 7, wherein the value of the parameter is increased in response to detecting that the later attempt results in the quantity being greater than a threshold, and wherein the quantity is decreased in response to detecting that the later attempt results in another value of the quantity.

9. The apparatus of claim 8, wherein the another value of the quantity indicates that the first processor is an owner of the access coordinator.

10. The apparatus of claim 6, wherein the indirect waiting arrangement for ownership of the access coordinator comprises prearbitration for ownership of the access coordinator, wherein the separate structures include separate cache lines, and wherein the prearbitration involves organizing the first and the one or more additional processors to access the separate cache lines to avoid interference.

11. The apparatus of claim 1, wherein the first processor is configured to heuristically determine the amount to delay the later attempt to directly acquire ownership of the access coordinator.

12. An apparatus, comprising:

a first processor configured to locally determine an amount of delay for a later attempt by the first processor to directly acquire ownership of an access coordinator for a resource shared with one or more additional processors, wherein upon a completion of the amount of delay the first processor is configured to adjust a heuristic based on an occurrence of success or failure of the attempt to directly acquire ownership of the access coordinator, wherein the adjusted heuristic is to adapt a subsequent attempt by the first processor to directly acquire ownership of the access coordinator,

wherein the adjusted heuristic comprises an adjusted delay time that controls an amount of delay that the first processor is to wait to make the subsequent attempt after the later attempt to directly acquire ownership of the access coordinator, in response to the first processor failing to acquire ownership of the access coordinator in the later attempt, and

wherein adjusting the heuristic comprises;

in response to determining that the first processor is an owner of the access coordinator upon the completion of the amount of delay for the later attempt, reduce the heuristic to reduce the adjusted delay time, and

in response to determining that the first processor is behind greater than a predetermined number of other processors waiting for the access coordinator upon the completion of the amount of delay for the later attempt, increase the heuristic to increase the adjusted delay time.

13. The apparatus of claim 12, wherein the first processor, upon an occurrence of the later attempt to acquire the ownership of the access coordinator, is configured to locally determine a different amount to delay the subsequent attempt to directly acquire ownership of the access coordinator.

14. The apparatus of claim 13, wherein the first processor is configured to employ the heuristic to locally determine the different amount to delay the subsequent attempt to directly acquire ownership of the access coordinator.

15. The apparatus of claim 12, wherein the delay for the later attempt by the first processor to directly acquire ownership of the access coordinator comprises a first delay portion and a second delay portion;

wherein the first processor, upon completion of the first delay portion, is configured to locally determine that additional waiting should be performed and to make a determination of the second delay portion, wherein upon completion of the second delay portion the first processor is configured to execute the later attempt to directly acquire ownership of the access coordinator.

16. The apparatus of claim 12, wherein upon an occurrence of failure of the later attempt to directly acquire ownership of the access coordinator, the first processor is configured to enter into an indirect waiting arrangement for ownership of the access coordinator, wherein the indirect waiting arrangement for ownership of the access coordinator involves organizing the first and the one or more additional processors waiting for ownership of the access coordinator to access separate structures to avoid interference between or among the first and one or more additional processors.

17. The apparatus of claim 16, wherein the indirect waiting arrangement for ownership of the access coordinator comprises prearbitration for ownership of the access coordinator, wherein the separate structures include separate cache lines, and wherein the prearbitration involves organizing the first and the one or more additional processors to access the separate cache lines to avoid interference.

18. The apparatus of claim 12, wherein the access coordinator for the resource comprises a member selected from the group consisting of one or more spinlocks, one or more read/write spinlocks, one or more blocking locks, one or more read/write blocking locks, one or more adaptive locks, one or more mutexes, one or more condition variables, and one or more semaphores on the resource.

19. The apparatus of claim 12, wherein adjusting the heuristic further comprises:

in response to determining that the first processor is not an owner of the access coordinator and that the first processor is behind less than or equal to the predetermined number of the other processors waiting for the access coordinator upon the completion of the amount of delay for the later attempt, leaving the heuristic unchanged.

20. An apparatus, comprising:

a plurality of processors; and

a computer operating system to coordinate ownership of a spinlock for a resource shared among the plurality of processors;

wherein upon an occurrence of owned status of the spinlock contemporaneous with a request for ownership of the spinlock by a plural set of processors of the plurality of processors, the computer operating system is configured to allow a plural subset of processors of the plural set of processors to directly wait for ownership of the spinlock;

wherein the computer operating system is configured to cause additional processors of the plural set of processors in excess of the plural subset of processors, to indirectly wait for ownership of the spinlock, wherein indirect waiting for ownership of the spinlock comprises causing the additional processors waiting for ownership of the access coordinator to access separate structures to avoid interference between or among the additional processors.

21. The apparatus of claim 20, wherein upon an occurrence of owned status of the spinlock contemporaneous with a request for ownership of the spinlock by a single processor of the plurality of processors, the computer operating system is configured to allow the single processor to directly wait for ownership of the spinlock.

22. The apparatus of claim 21, wherein the plural subset of processors comprises the single processor and multiple processors, wherein upon an occurrence of owned status of the spinlock contemporaneous with the single processor directly waiting for ownership of the spinlock and a request for ownership of the spinlock by the multiple processors and the additional processors of the plural set of processors, the computer operating system is configured to allow the single processor and the multiple processors to directly wait for ownership of the spinlock and to cause the additional processors to indirectly wait for ownership of the spinlock.

23. The apparatus of claim 20, wherein indirect waiting for ownership of the spinlock comprises prearbitration for ownership of the spinlock, wherein the separate structures include separate cache lines, and wherein the prearbitration involves organizing the additional processors to access the separate cache lines to avoid interference.