SYNCHRONIZATION MECHANISMS BASED ON COUNTERS

• US 20100250809A1
• Filed: 03/26/2009
• Published: 09/30/2010
• Est. Priority Date: 03/26/2009
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: MAGEE, JAMES M., RAMESH, ANANTHAKRISHNA
• Granted Patent: US 8,392,925 B2
• Time in Patent Office: Days
• US Class Current: 710/200
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A method and apparatus to maintain a plurality of counters to synchronize a plurality of requests for a lock independent of interlocks are described. 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, 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;

selecting at least one of the requests to grant a lock according to the counters; 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 each request is associated with a sequence number corresponding to a lock count of the lock counter and wherein the request is ordered in the wait queue based on the sequence number.

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 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, 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;

selecting at least one of the requests to grant a lock according to the counters; and

performing the synchronized operations for the selected requests.

15. An apparatus, comprising:

a synchronization library configured in a user mode to maintain a plurality of counters in memory including a lock counter and an unlock counter to synchronize a plurality of requests, 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;

a kernel library configured in a kernel mode to select at least one of the requests to grant a lock according to the counters; and

an interface module configured to performing the synchronized operations 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;

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.

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.

22. The method of claim 21, 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.

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.

29. The method of claim 27, 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.

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.

35. A machine-readable 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;

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.

36. An apparatus, comprising:

a user library configured to maintain 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, comprising;

a lock handler module configured to count the lock counter for calling a first kernel interface with a first state to wait for the lock, and

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

an interface module configured to perform synchronized operations 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, 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.

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.

41. The method of claim 40, 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.

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.

48. The method of claim 47, further comprising:

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.

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.

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 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, 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.

62. An apparatus, comprising:

a wait queue to store one or more lock requests, each lock request being

associated with a lock count indicating a cumulative number of the lock requests initiated for a lock;

a kernel library configured to

maintain one or more counters in memory to synchronize the lock requests,

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

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

an interface module configured to perform synchronized operations 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 to synchronize operations among a plurality of tasks;

when the lock is granted, performing the synchronized operations for at least one of the plurality of tasks; 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.