Synchronization mechanisms based on counters

• US 8,392,925 B2
• Filed: 03/26/2009
• Issued: 03/05/2013
• Est. Priority Date: 03/26/2009
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Magee, James M., Ramesh, Ananthakrishna
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US12/412,325
• Publication Number:
  US 20100250809A1
• Time in Patent Office: 1,440 Days
• Field of Search: None
• US Class Current: 718/102
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A method and apparatus which maintain a plurality of counters to synchronize a plurality of requests for a lock independent of interlocks. The plurality of counters include a lock counter and an unlock counter. The requests wait in a wait queue maintained separately from the counters without direct access between the counters and the wait queue. The lock counter indicates a cumulative number of lock requests to acquire the lock. The unlock counter indicates a cumulative number of unlock requests to release the lock acquired. One or more requests waiting for the lock are selected according to the counters to be granted with the lock when the lock is released. A request corresponds to a task performing synchronized operations when granted with the lock.

Claims

1. A computer implemented method, comprising:

maintaining a plurality of counters in memory including a lock counter and an unlock counter to synchronize a plurality of requests for a lock, the lock counter indicating a cumulative number of the requests, and the unlock counter indicating a cumulative number of a portion of the requests having released the lock, the requests stored with sequence numbers to wait for the lock, the sequence numbers counted via the lock counter, each request uniquely identified via one of the sequence numbers;

selecting at least one of the requests stored to grant the lock according to the sequence numbers, wherein the lock counter has a current count when the at least one request is selected, wherein the sequence numbers stored with the requests include consecutive sequence numbers less than the current count; and

performing the synchronized operations for the selected requests.

2. The method of claim 1, wherein maintaining the plurality of counters comprises:

counting up atomically the lock counter to initiate one of the requests; and

counting up atomically the unlock counter subsequent to performing the synchronized operations.

3. The method of claim 1, wherein the plurality of counters are maintained in an operating system for performing the synchronized operations.

4. The method of claim 1, wherein the selection of the at least one of the requests is independent of an interlock.

5. The method of claim 1, further comprising maintaining one or more flags indicating status of the lock.

6. The method of claim 5, wherein the flags include an exclusive flag indicating whether the lock is granted exclusively to at most one request at a time.

7. The method of claim 6, further comprising:

maintaining a wait queue to store the requests waiting for the lock.

8. The method of claim 7, wherein the counters and the wait queue are allocated in memory spaces with separate privileges in an operation system and wherein the maintenance of the counters and the maintenance of the wait queue are independent.

9. The method of claim 7, wherein the request is ordered in the wait queue based on the sequence numbers.

10. The method of claim 7, wherein maintaining the wait queue comprises:

locating the wait queue corresponding to the lock from a cache memory; and

creating the wait queue in the cache memory if the wait queue cannot be located.

11. The method of claim 7, wherein the one or more bit flags include a wait bit indicating whether there are remaining requests waiting in the wait queue.

12. The method of claim 1, wherein the lock is a mutex lock for synchronizing a plurality of threads corresponding to the plurality of lock requests.

13. The method of claim 1, wherein the selection is based on a synchronization scheme to grant the lock shared for a reader.

14. A machine-readable non-transitory storage medium having instructions, when executed by a machine, cause the machine to perform a method, the method comprising:

maintaining a plurality of counters in memory including a lock counter and an unlock counter to synchronize a plurality of requests for a lock, the lock counter indicating a cumulative number of the requests, and the unlock counter indicating a cumulative number of a portion of the requests having released the lock, the requests stored with sequence numbers to wait for the lock, the sequence numbers counted via the lock counter, each request uniquely identified via one of the sequence numbers;

selecting at least one of the requests stored to grant the lock according to the sequence numbers, wherein the lock counter has a current count when the at least one request is selected, wherein the sequence numbers stored with the requests include consecutive sequence numbers less than the current count; and

performing the synchronized operations for the selected requests.

15. An apparatus comprising a processor and a memory storing executable code including a synchronization library, a kernel library and an interface module, the processor coupled to the memory to execute the executable code, the processor configured to:

maintain a plurality of counters in memory via the synchronization library in a user mode, the counters including a lock counter and an unlock counter to synchronize a plurality of requests for a lock, the lock counter indicating a cumulative number of the requests, and the unlock counter indicating a cumulative number of a portion of the requests having released the lock, the requests stored with sequence numbers to wait for the lock, the sequence numbers counted via the lock counter, each request uniquely identified via one of the sequence numbers,

select at least one of the requests to grant a lock via the kernel library in a kernel mode according to the sequence numbers, wherein the lock counter has a current count when the at least one request is selected, wherein the sequence numbers stored with the requests include consecutive sequence numbers less than the current count, and

perform the synchronized operations via the interface module for the selected requests.

16. A computer implemented method, comprising:

maintaining one or more counters to synchronize a plurality of requests for a lock, the counters having a state indicating values of the counters, the requests stored with sequence numbers to wait for the lock, the sequenced numbers counted via the state of the counters, each request uniquely identified via one of the sequence numbers;

calling a first kernel interface with a first state of the counters to wait for the lock for a particular one of the requests, the counters having the first state when the first kernel interface was called, the particular request associated with a particular one of the sequence numbers, the first state including the particular sequence number, wherein the first kernel interface returns when the lock is granted, wherein the counters have a second state when the lock is granted, the second state including a current sequence number, wherein the sequence numbers stored with the requests include consecutive sequence numbers less than the current sequence number;

updating the counters atomically based on the second state of the counters returned from the first kernel interface; and

performing synchronized operations subsequent to the update of the counters.

17. The method of claim 16, wherein the plurality of counters are maintained in an operating system for performing the synchronized operations.

18. The method of claim 16, wherein the update of the counters is independent of an interlock.

19. The method of claim 16, wherein the updated counters have an update state, wherein the update comprises:

retrieving a current state of the counter; and

determining the update state based on the second state and the current state of the counters.

20. The method of claim 19, wherein the counters include status flags, wherein the status flags include an exclusive flag indicating whether the lock is granted exclusively to at most one request.

21. The method of claim 20, wherein the status flags include a wait flag indicating whether there are remaining ones of the requests waiting for the lock.

24. The method of claim 16, wherein the counters include a lock counter, wherein the state includes a lock count for the lock counter, and wherein the maintenance comprises:

retrieving a lock count from the lock counter; and

updating the lock counter atomically counting up from the current lock count.

25. The method of claim 24, wherein the atomic update of the lock counter comprises:

comparing the lock counter with the lock count for the update.

26. The method of claim 24, wherein the counters include an unlock counter, the maintenance further comprising:

retrieving a current state from the counters subsequent to performing the synchronized operations, the current state including a current unlock count corresponding to the unlock counter; and

updating the unlock counter atomically counting up from the current unlock count.

27. The method of claim 26, further comprising:

determining whether there are requests waiting for the lock; and

resetting the lock and unlock counters if there is no request waiting for the lock.

28. The method of claim 27, wherein the current state includes a current lock count for the lock counter and wherein determining whether there are requests waiting for the lock is based on a relationship between the current lock count and the current unlock count.

32. The method of claim 26, further comprising:

determining if the current state indicates the lock is ready for waiting requests; and

calling a second kernel interface according to the current state and the current unlock count if the lock is ready for the waiting requests.

33. The method of claim 32, wherein the counters include a waiter counter indicating a number of the waiting requests for the lock, wherein the current state includes a current waiter count for the waiter counter and a current lock count for the lock counter, and wherein the determination is based on a relationship among the lock count, the unlock count and the waiter count.

34. The method of claim 16, wherein the lock is exclusively acquired for the synchronized operations according to a synchronization scheme for a writer.

22. A computer implemented method, comprising:

maintaining one or more counters to synchronize a plurality of requests for a lock, the counters having a state indicating values of the counters;

calling a first kernel interface with a first state to wait for the lock;

updating the counters atomically based on a second state of the counters returned from the first kernel interface; and

performing synchronized operations subsequent to the update of the counters,

wherein the updated counters have an update state, wherein the update comprises;

retrieving a current state of the counter, and

determining the update state based on the second state and the current state of the counters,

wherein the counters include status flags, wherein the status flags include an exclusive flag indicating whether the lock is granted exclusively to at most one request, wherein the status flags include a wait flag indicating whether there are remaining ones of the requests waiting for the lock, wherein the determination includes a transition table mapping the current state and the second state to the update state of the counters.

23. The method of claim 22, wherein the second state includes a bit set for the status flags, wherein the current state includes a current bit set for the status flags, wherein the update state includes an update bit set for the status flags, and wherein the transition table includes a setting for the update bit set indexed according to the bit set and the current bit set.

29. A computer implemented method, comprising:

maintaining one or more counters to synchronize a plurality of requests for a lock, the counters having a state indicating values of the counters;

calling a first kernel interface with a first state to wait for the lock;

updating the counters atomically based on a second state of the counters returned from the first kernel interface;

performing synchronized operations subsequent to the update of the counters,

wherein the counters include a lock counter, wherein the state includes a lock count for the lock counter, and wherein the maintenance comprises;

retrieving a lock count from the lock counter, and

updating the lock counter atomically counting up from the current lock count,

wherein the counters include an unlock counter, the maintenance further comprising;

retrieving a current state from the counters subsequent to performing the synchronized operations, the current state including a current unlock count corresponding to the unlock counter, and

updating the unlock counter atomically counting up from the current unlock count;

determining whether there are requests waiting for the lock; and

resetting the lock and unlock counters if there is no request waiting for the lock, wherein the current state includes a current lock count for the lock counter, wherein determining whether there are requests waiting for the lock is based on a relationship between the current lock count and the current unlock count, wherein resetting the lock and unlock counters comprises;

updating the unlock counter from the current unlock count to a predetermined initial value,

performing a first atomic operation to update the lock counter from the current lock count to the predetermined initial value, and

if the first atomic operation is not successful, restoring the unlock counter from the predetermined initial value based on the current unlock count.

30. The method of claim 29, wherein restoring the unlock counter comprises:

retrieving a count from the unlock counter; and

performing a second atomic operation to update the unlock counter from the count to a sum of the count and the current unlock count.

31. The method of claim 30, wherein the restoration of the unlock counter is applied continuously until the second atomic operation is successful.

35. A machine-readable non-transitory storage medium having instructions, when executed by a machine, cause the machine to perform a method, the method comprising:

maintaining one or more counters in memory to synchronize a plurality of requests for a lock, the counters having a state indicating values of the counters, the requests stored with sequence numbers to wait for the lock, the sequence numbers counted via the state of the counters, each request uniquely identified via one of the sequence numbers;

calling a first kernel interface with a first state of the counters to wait for the lock for a particular one of the requests, the counters having the first state when the first kernel interface was called, the particular request stored with a particular one of the sequence numbers, the first state including the particular sequence number, wherein the first kernel interface returns when the lock is granted, wherein the counters have a second state when the lock is granted, the second state including a current sequence number, wherein the sequence numbers stored with the requests include consecutive sequence numbers less than the current sequence number;

updating the counters atomically based on the second state of the counters returned from the first kernel interface; and

performing synchronized operations subsequent to the update of the counters.

36. An apparatus comprising a processor and a memory storing executable code including a user library and an interface module, the processor coupled to the memory to execute the executable code, the processor configured to:

maintain one or more counters in memory via the user library to synchronize a plurality of requests for a lock, the counters having a state indicating values of the counters, the requests stored with sequence numbers to wait for the lock, the sequence numbers counted via the state of the counters, each request uniquely identified via one of the sequence numbers, the user library comprising;

a lock handler module configured to call a first kernel interface with a first state to wait for the lock for a particular one of the requests, the counters having the first state when the first kernel interface was called, the particular request stored with a particular one of the sequence numbers, the first state including the particular sequence number, wherein the first kernel interface returns when the lock is granted, wherein the counters have a second state when the lock is granted, the second state including a current sequence number, wherein the sequence numbers stored with the requests include consecutive sequence numbers less than the current sequence number, and

an unlock handler module configured to update the counters atomically based on the second state of the counters returned from the first kernel interface, and

perform synchronized operations via the interface module subsequent to the update of the counters.

37. A computer implemented method, comprising:

maintaining one or more counters in memory to synchronize a plurality of lock requests, the lock requests stored with sequence numbers to wait for a lock, the sequence numbers counted via the counters, each lock request uniquely identified via one of the sequence numbers corresponding to a lock count indicating a cumulative number of the lock requests already initiated for the lock when the lock request is received in a wait queue;

in response to receiving an unlock request to release the lock, the unlock request including a current lock count of the counters when the unlock request is received, comparing the current lock count with the sequence numbers to determine whether to expect additional lock requests for the lock, wherein no additional lock requests for the lock is expected if the sequence numbers stored with the requests include consecutive sequence numbers less than the current lock count;

selecting one or more of the lock requests from the wait queue to grant the lock if no additional lock requests for the lock is expected; and

performing synchronized operations for the selected lock requests.

38. The method of claim 37, wherein the counters are maintained in an operating system for performing the synchronized operations.

39. The method of claim 37, wherein the maintenance of the counters is independent of an interlock.

40. The method of claim 37, wherein the counters include one or more sequence counters including a target sequence counter for identifying the additional lock requests expected, wherein the counters include a wait counter indicating a number of the additional lock requests expected, and wherein the state includes a target count and a wait count corresponding to the target sequence counter and the wait counter.

47. The method of claim 40, wherein each lock request in the wait queue is associated with a sequence number corresponding to the lock count of the lock request, the sequence number indicating a consecutive order within the wait queue.

60. The method of claim 37, wherein the lock is selected shared according to a synchronization scheme for a long reader and wherein the wait queue is updated to grant all waiting readers with the lock.

41. A computer implemented method, comprising

maintaining one or more counters in memory to synchronize a plurality of lock requests, each lock request being associated with a lock count indicating a cumulative number of the lock requests initiated for a lock when the lock request is received in a wait queue;

in response to receiving an unlock request to release the lock, comparing a state of the counters with the unlock request to determine whether to expect additional lock requests;

selecting one or more of the lock requests from the wait queue to grant the lock if no additional lock requests is expected; and

performing synchronized operations for the selected lock requests,

wherein the counters include one or more sequence counters including a target sequence counter for identifying the additional lock requests expected, wherein the counters include a wait counter indicating a number of the additional lock requests expected, and wherein the state includes a target count and a wait count corresponding to the target sequence counter and the wait counter, and wherein the maintenance comprises;

in response to receiving a lock request including a lock count, determining if the lock request is one of the additional requests expected; and

inserting the lock request to the wait queue if the lock request is not one of the additional requests expected.

42. The method of claim 41, wherein the determination is based on a comparison between the target count and the lock count.

43. The method of claim 41, wherein the lock request in the wait queue is associated with a sequence number corresponding to the lock count.

44. The method of claim 41, wherein there is no additional requests expected if the sequence counters are empty.

45. The method of claim 41, wherein the lock request is not one of the additional requests expected if the lock count is greater than the target count.

46. The method of claim 41, wherein the maintenance further comprises:

counting down the wait counter atomically from the wait count if the lock request is one of the additional requests expected.

48. A computer implemented method, comprising:

maintaining one or more counters in memory to synchronize a plurality of lock requests, each lock request being associated with a lock count indicating a cumulative number of the lock requests initiated for a lock when the lock request is received in a wait queue;

in response to receiving an unlock request to release the lock, comparing a state of the counters with the unlock request to determine whether to expect additional lock requests;

selecting one or more of the lock requests from the wait queue to grant the lock if no additional lock requests is expected;

performing synchronized operations for the selected lock requests,

wherein the counters include one or more sequence counters including a target sequence counter for identifying the additional lock requests expected, wherein the counters include a wait counter indicating a number of the additional lock requests expected, and wherein the state includes a target count and a wait count corresponding to the target sequence counter and the wait counter,

wherein each lock request in the wait queue is associated with a sequence number corresponding to the lock count of the lock request, the sequence number indicating a consecutive order within the wait queue;

in response to receiving an unlock request to release the lock, determining whether the unlock request is a spurious request; and

determining the number of the additional lock requests expected if the unlock request is not a spurious request.

49. The method of claim 48, wherein the unlock request is associated with a waiter count indicating an expected number of lock requests waiting in the wait queue, and wherein the number of the additional lock request is determined based on a difference between a total number of one or more requests currently waiting in the wait queue and the waiter count.

50. The method of claim 49, wherein the one or more requests are associated with sequence numbers no greater than the lock count.

51. The method of claim 48, wherein a last unlock sequence number is associated with a latest unlock request releasing the lock, and wherein the spurious request is determined based on a comparison between an unlock count associated with the unlock request and the last unlock sequence number.

52. The method of claim 48, wherein no additional lock request is expected if lock requests associated with sequence numbers smaller than the lock count associated with the unlock request are consecutive in order from the lock count within the wait queue.

57. The method of claim 48, further comprising:

resetting the counters if none of the additional lock requests is expected.

58. The method of claim 48, wherein each of the selected lock requests is associated with a return value including one or more status flags indicating whether there is any remaining lock request requesting the lock as a writer.

59. The method of claim 58, wherein the status flags indicate whether the lock is exclusively granted to the selected lock requests.

53. The method of 52, further comprising:

updating the counters according to the unlock request and the number of the additional lock requests expected.

54. The method of claim 53, wherein the target sequence counter is updated with the lock count of the unlock request.

55. The method of claim 53, wherein the unlock request is associated with an unlock count indicating a cumulative number of the lock requests having released the lock after completing the synchronized operations.

56. The method of claim 53, wherein the wait counter is updated with the number of the additional lock requests expected.

61. A machine-readable non-transitory storage medium having instructions, when executed by a machine, cause the machine to perform a method, the method comprising:

maintaining one or more counters in memory to synchronize a plurality of lock requests, the lock requests stored with sequence numbers to wait for the lock, the sequence numbers counted via the counters, each lock request uniquely identified via one of the sequence numbers corresponding to a lock count indicating a cumulative number of the lock requests already initiated for a lock when the lock request is received in a wait queue;

in response to receiving an unlock request to release the lock, the unlock request including a current lock count of the counters when the unlock request is received, comparing the current lock count with the sequence numbers to determine whether to expect additional lock requests for the lock, wherein no additional lock requests for the lock is expected if the sequence numbers stored with the requests include consecutive sequence numbers less than the current lock count;

selecting one or more of the lock requests from the wait queue to grant the lock if no additional lock requests for the lock is expected; and

performing synchronized operations for the selected lock requests.

62. An apparatus comprising a processor and a memory storing executable code including a kernel library and an interface module, the processor coupled to the memory to execute the executable code, the processor configured to:

store one or more lock requests in a wait queue, the lock requests stored with sequence numbers counted via the counters, each lock request uniquely identified via one of the sequence numbers corresponding to a lock count indicating a cumulative number of the lock requests already initiated for a lock wherein the lock request is received in the wait queue;

maintain one or more counters in memory via the kernel library to synchronize the lock requests, wherein the sequence numbers correspond to different lock counts counted via the counters;

in response to receiving an unlock request to release the lock, the unlock request including a current lock count of the counters when the unlock request is received, compare the current lock count with the sequence numbers via the kernel library to determine whether to expect additional lock requests for the lock, wherein no additional lock requests for the lock is expected if the sequence numbers stored with the requests include consecutive sequence numbers less than the current lock count;

select one or more of the lock requests from the wait queue via the kernel library to grant the lock if no additional lock requests for the lock is expected; and

perform synchronized operations via the interface module subsequent to the update of the counters.

63. A computer implemented method, comprising:

counting up a lock counter in memory atomically to wait for a lock for a particular task to synchronize operations among a plurality of tasks including the particular task, the tasks stored with sequence numbers to wait for the lock, the sequence numbers counted via the lock counter, each task uniquely identified via one of the sequence numbers, the particular task stored with a particular one of the sequence numbers, wherein the lock counter is counted up to a particular value corresponding to the particular sequence number;

when the lock is granted for the particular task, performing the synchronized operations for at least one of the plurality of tasks, wherein the lock counter has a current value when the lock is granted, and wherein the sequence numbers stored with the tasks include consecutive sequence numbers less than the current value; and

counting up an unlock counter in the memory atomically subsequent to the synchronized operations.

64. The method of claim 63, wherein the lock and unlock counters are allocated in an operating system for performing the synchronized operations.

65. The method of claim 63, wherein the counting of the lock and unlock counters is independent of an interlock.

66. The method of claim 63, further comprising:

determining if any of the tasks is still waiting for the lock subsequent to the synchronized operations.

67. The method of claim 66, wherein the determination is based on a comparison of the lock counter and the unlock counter.

68. The method of claim 66, wherein the unlock counter is counted up if at least one of the tasks is determined waiting for the lock.

69. The method of claim 63, wherein one or more waiters are queued waiting for the lock, the method further comprising:

maintaining one or more status flags to indicate a status of the waiters.

70. The method of claim 64, wherein the lock is exclusively granted according to a synchronization scheme for a yielding writer based on the lock and unlock counters, and wherein one of the status flags indicates no yielding writer remaining in the waiters.