Power managed lock optimization

• US 8,578,079 B2
• Filed: 11/06/2012
• Issued: 11/05/2013
• Est. Priority Date: 05/13/2009
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: de Cesare, Josh P, Wadhawan, Ruchi, Smith, Michael J, Kumar, Puneet, Semeria, Bernard J
• Primary Examiner(s): AUVE, GLENN ALLEN
• Application Number:
  US13/669,890
• Publication Number:
  US 20130067257A1
• Time in Patent Office: 364 Days
• Field of Search: 710/200, 713/320, 713/323, 713/324, 718/100, 718/102, 718/104, 718/106
• US Class Current: 710/200
• CPC Class Codes: G06F 1/3228 Monitoring task completion, e.g. by use of idle timers, stop commands or wait commands
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

In an embodiment, a timer unit may be provided that may be programmed to a selected time interval, or wakeup interval. A processor may execute a wait for event instruction, and enter a low power state for the thread that includes the instruction. The timer unit may signal a timer event at the expiration of the wakeup interval, and the processor may exit the low power state in response to the timer event. The thread may continue executing with the instruction following the wait for event instruction. In an embodiment, the processor/timer unit may be used to implement a power-managed lock acquisition mechanism, in which the processor is awakened a number of times to check the lock and execute the wait for event instruction if the lock is not free, after which the thread may block until the lock is free.

Claims

1. A method comprising:

a first processor of a plurality of processors attempting to acquire a lock for a thread being executed;

responsive to failing to acquire the lock, determining that at least one additional iteration of attempting to acquire the lock is permitted for the thread;

responsive to determining that the additional iteration is permitted, waiting for an event prior to initiating another iteration in the first processor;

a second processor of the plurality of processors releasing the lock; and

the second processor sending an event message to an event control unit responsive to releasing the lock, wherein the event message indicates the event; and

the event control unit waking the first processor responsive to the event message.

2. The method as recited in claim 1 wherein waiting for the event causes the first processor to enter a low power state, reducing power consumption.

3. The method as recited in claim 1 further comprising:

responsive to determining that the additional iteration is permitted, permitting the thread to remain scheduled on the first processor.

4. The method as recited in claim 3 wherein performing the additional iteration comprises:

the first processor attempting to acquire the lock for the thread; and

responsive to failing to acquire the lock, determining that yet another iteration of attempting to acquire the lock is not permitted for the thread; and

descheduling the thread responsive to determining that yet another iteration of attempting to acquire the lock is not permitted for the thread.

5. The method as recited in claim 4 further comprising:

a thread scheduler detecting that the thread is descheduled waiting for the lock;

the thread scheduler detecting that the lock is released; and

the thread scheduler marking the thread as eligible to schedule responsive to detecting that the lock is released and to detecting that the thread is descheduled waiting for the lock.

6. The method as recited in claim 1 further comprising:

the first processor performing the additional iteration responsive to being awakened by the event control unit.

7. A computer accessible storage medium storing a plurality of instructions which, when executed on a plurality of processors in a system, cause a first processor of the plurality of processors to:

attempt to acquire a lock for a thread being executed by the first processor;

responsive to failing to acquire the lock, determine that at least one additional iteration of attempting to acquire the lock is permitted for the thread; and

responsive to determining that the additional iteration is permitted, wait for an event prior to initiating another iteration in the first processor; and

wherein the computer accessible storage medium is further storing a second plurality of instructions which, when executed on a second processor of the plurality of processors, cause the second processor to send an event message to an event control unit indicating the event indicating a release of the lock, wherein the event control unit is configured to wake the first processor responsive to the event message.

8. The computer accessible storage medium as recited in claim 7 wherein the plurality of instructions, when executed responsive to determining that the additional iteration is permitted, permit the thread to remain scheduled on the first processor.

9. The computer accessible storage medium as recited in claim 8 wherein the plurality of instructions which, when executed, perform the additional iteration comprise instructions which, when executed:

attempt to acquire the lock for the thread on the first processor; and

responsive to failing to acquire the lock, determine that yet another iteration of attempting to acquire the lock is not permitted for the thread; and

wherein the plurality of instructions, when executed, deschedule the thread responsive to determining that yet another iteration of attempting to acquire the lock is not permitted for the thread.

10. The computer accessible storage medium as recited in claim 9 wherein the plurality of instructions comprise a thread scheduler which, when executed:

detects that the thread is descheduled waiting for the lock;

detects that the lock is released; and

marks the thread as eligible to schedule responsive to detecting that the lock is released and to detecting that the thread is descheduled waiting for the lock.

11. An apparatus comprising:

a plurality of processors;

an event control unit coupled to the plurality of processors; and

a storage device configured to store a plurality of instructions;

wherein a first processor of the plurality of processors, responsive to executing instructions from the plurality of instructions;

attempts to acquire a lock for a thread being executed;

responsive to failing to acquire the lock, determines that at least one additional iteration of attempting to acquire the lock is permitted for the thread; and

responsive to determining that the additional iteration is permitted, waits for an event prior to initiating another iteration in the first processor; and

wherein a second processor of the plurality of processors, responsive to executing instructions from the plurality of instructions;

releases the lock; and

sends an event message to the event control unit indicating the event responsive to releasing the lock, wherein the event control unit is configured to wake the first processor responsive to the event message.

12. The apparatus as recited in claim 11 wherein the first processor is configured to wait for the event by entering a low power state, reducing power consumption.

13. The apparatus as recited in claim 11 wherein the memory is configured to store a thread scheduler, and wherein the first processor of the plurality of processors is configured to execute the thread scheduler and, responsive to determining that the additional iteration is permitted, permits the thread to remain scheduled on the first processor.

14. The apparatus as recited in claim 13 wherein the first processor is configured to perform the additional iteration in response to being awakened by the event control unit, wherein performing the additional iteration comprises:

the first processor attempting to acquire the lock for the thread;

responsive to failing to acquire the lock, determining that yet another iteration of attempting to acquire the lock is not permitted for the thread; and

descheduling the thread responsive to determining that yet another iteration of attempting to acquire the lock is not permitted for the thread.

15. The apparatus as recited in claim 14 wherein the thread scheduler, when executed by one of the plurality of processors:

detects that the thread is descheduled waiting for the lock;

detects that the lock is released; and

marks the thread as eligible to schedule responsive to detecting that the lock is released and to detecting that the thread is descheduled waiting for the lock.

16. The apparatus as recited in claim 11 wherein the first processor is configured to perform the additional iteration responsive to being awakened by the event control unit.

17. A system comprising:

a plurality of processors; and

an event control unit coupled to the plurality of processors, wherein a first processor of the plurality of processors is configured to transmit an event message to the event control unit responsive to releasing a lock, and wherein a second processor of the plurality of processors is configured to wake from a low power state responsive to an indication from the event control unit, wherein the event control unit is configured to transmit the indication responsive to the event message, and wherein the second processor is configured wait for the event responsive to detecting that the lock is not available and responsive to detecting that another iteration of attempting to acquire the lock is permitted for a thread executing on the second processor.

18. The system as recited in claim 17 wherein the system is configured, responsive to determining that the additional iteration is permitted, to permit the thread to remain scheduled on the second processor.

19. The system as recited in claim 17 wherein the second processor is configured to perform the additional iteration in response to being awakened by the event control unit, wherein performing the additional iteration comprises:

the second processor attempting to acquire the lock for the thread;

responsive to failing to acquire the lock, determining that yet another iteration of attempting to acquire the lock is not permitted for the thread; and

descheduling the thread responsive to determining that yet another iteration of attempting to acquire the lock is not permitted for the thread.

20. The system as recited in claim 17 wherein the second processor is configured to wait for the event by entering the low power state, reducing power consumption.