Method for enabling multi-processor synchronization

• US 8,539,188 B2
• Filed: 01/29/2009
• Issued: 09/17/2013
• Est. Priority Date: 01/30/2008
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Moudgill, Mayan, Kalashnikov, Vitaly, Senthilvelan, Murugappan, Srikantiah, Umesh, Li, Tak-po, Balzola, Pablo
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): DARE, RYAN A
• Application Number:
  US12/362,329
• Publication Number:
  US 20090193279A1
• Time in Patent Office: 1,692 Days
• Field of Search: None
• US Class Current: 711/167
• 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 method for providing at least one sequence of values to a plurality of processors is described. In the method, a sequence generator from one or more sequence generators is associated with a memory location. The sequence generator is configured to generate the at least one sequence of values. One or more read accesses of the memory location are enabled by a processor from the plurality of processors. In response to enabling the read access, the sequence generator is executed so that it returns a first value from the sequence of values to the processor. After executing the sequence generator, the sequence generator is advanced so that the next access generates a second value from the sequence of values. The second value is sequentially subsequent to the first value.

Claims

1. A method executed by a plurality of processors for a plurality of mutexes, comprising:

associating a sequence generator with each mutex, each sequence generator being adapted to generate a value for each of the processors from a sequence of values, starting from a first value;

associating a turn indicator with each mutex, wherein a first value of the turn indicator is initialized to the first value from the sequence of values;

when entering a section of code associated with the mutex,

accessing the associated sequence generator to read a second value from the sequence of values, and

waiting until the associated turn indicator equals the said second value from the sequence of values before accessing the section of code; and

when exiting the section of code, setting the turn indicator to a third value subsequent to the second value in the sequence of values.

2. The method of claim 1, wherein the turn indicator comprises a plurality of turn indicators, the method further comprising:

when entering the section of code, waiting until at least one of the plurality of turn indicators equals the said second value from the sequence of values before accessing the section of code; and

when exiting the section of code, setting all of the plurality of turn indicators to the third value in the sequence of values.

3. The method of claim 2, wherein associating the plurality of turn indicators comprises associating a number of turn indicators equal to the number of the processors.

4. The method of claim 3, wherein associating a sequence generator comprises setting the first value of the sequence generator to 0.

5. The method of claim 2, wherein accessing the turn indicator comprises accessing a turn indicator for a mutex for a processor, the turn indicator located in memory positions local to the processor.

6. The method of claim 2, wherein the synchronization generator and the turn indicator have the same bit width.

7. The method of claim of claim 2, wherein all of the plurality of turn indicators are set to the third value simultaneously.

8. The method of claim 1, wherein accessing the associated sequence generator to read a second value comprises:

generating the second value greater than the first value by an integer equal to or greater than 1, and

if the second value is equal to or greater than an integer, N, the second value is restarted to the first value.

9. The method of claim 8, wherein:

if the second value is equal to or greater than N, the second value is restarted to 0.

10. The method of claim 9, wherein:

the second value is greater than the first value by 1.

11. The method of claim 1, wherein the plurality of processors are initialized simultaneously.

12. The method of claim 11, wherein the plurality of processors operate disjunctively after initialization.

13. The method of claim 1, wherein the plurality of processors share common operating attributes.

14. The method of claim 1, wherein one of the plurality of processors has operating attributes that differ from operating attributes of another of the plurality of processors.

15. The method of claim 1, wherein the plurality of processors operate in parallel.

16. A computer readable, non-transitory medium having computer readable program code embodied therein for processing a plurality of mutexes for a plurality of processors, the program code, when executed, causing the processor to:

associate a sequence generator with each mutex, each sequence generator being adapted to generate a value for each of the processors from a sequence of values, starting from a first value;

associate a turn indicator with each mutex, wherein a first value of the turn indicator is initialized to the first value from the sequence of values;

when entering a section of code associated with the mutex,

access the associated sequence generator to read a second value from the sequence of values, and

wait until the associated turn indicator equals the said second value from the sequence of values before accessing the section of code; and

when exiting the section of code, set the turn indicator to a third value subsequent to the second value in the sequence of values.

17. The computer readable, non-transitory medium of claim 16, wherein the turn indicator comprises a plurality of turn indicators, the program code, when executed, further causing the processor to:

when entering the section of code, waiting until at least one of the plurality of turn indicators equals the said second value from the sequence of values before accessing the section of code; and

when exiting the section of code, set all of the plurality of turn indicators to the third value in the sequence of values.

18. The computer readable, non-transitory medium of claim 17, wherein associating a turn indicator comprises associating a number of turn indicators equals the number of the processors.

19. The computer readable, non-transitory medium of claim 16, wherein the plurality of processors share common operating attributes.

20. The computer readable, non-transitory medium of claim 16, wherein one of the plurality of processors has operating attributes that differ from operating attributes of another of the plurality of processors.