Concurrency-safe reader-writer lock with time out support

• US 6,546,443 B1
• Filed: 12/15/1999
• Issued: 04/08/2003
• Est. Priority Date: 12/15/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kakivaya, Gopala Krishna R., Lyon, James M., Cutler, David N.
• Primary Examiner(s): Ray, Gopal C.
• Application Number:
  US09/465,239
• Time in Patent Office: 1,210 Days
• Field of Search: 710/200, 710/108, 711/145, 711/151, 711/152, 711/163, 709/101, 709/102, 709/104, 709/107, 709/229, 709/232, 709/248, 709/400, 707/8-10, 707/1, 707/201, 714/2, 714/15
• US Class Current: 710/200
• CPC Class Codes: G06F 2209/523 Mode
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Synchronization services provide a concurrency-safe reader/writer lock supporting a time out feature. The lock can be implemented using lockless data structures to provide efficient synchronization services. Various features such as lock nesting and auto-transformation address common scenarios arising in componentized programs. The lock supports upgrading and suspension, and the time out feature can support an efficient, low-cost optimistic deadlock avoidance scheme. Peculiarities of the reader/writer scenario are addressed in an efficient way to maintain lock stability and consistency, thus providing synchronization services suitable for implementation at the kernel level. In one implementation using event objects, the events are managed for high efficiency and stability of the lock. For multiprocessor machines, a hybrid lock avoids a context switch by behaving as a spin lock before waiting for the lock to become available.

Claims

1. In a computer system, a method of granting a lock to a set of a plurality of concurrently-executing entities, the method comprising:

receiving a request of a first executing entity out of the set requesting the lock as a reader;

responsive to said receiving the request of a first executing entity requesting the lock as a reader, determining that no executing entities hold the lock as a writer;

responsive to said determining that no executing entities hold the lock as a writer, granting the lock to the first executing entity as a reader, wherein said determining that no executing entities hold the lock as a writer and granting the lock to the first executing entity are performed together with an interlocked operation;

receiving a request of a second executing entity out of the set requesting the lock as a writer;

responsive to said receiving the request of a second executing entity requesting the lock as a writer, determining that no executing entities hold the lock as a writer and no executing entities hold the lock as a reader; and

responsive to said determining that no executing entities hold the lock as a writer and no executing entities hold the lock as a reader, granting the lock to the second executing entity as a writer, wherein said determining that no executing entities hold the lock as a writer and no executing entities hold the lock as a reader and granting the lock to the second executing entity are performed together with an interlocked operation.

2. A computer-readable medium having computer-executable instructions for performing the steps of claim 1.

3. The method of claim 1 wherein the interlocked operations each are an interlocked compare and exchange operation.

4. The method of claim 1 wherein the interlocked operations each are an instruction native to a processor of the computer system.

5. The method of claim 1 wherein the first executing entity is a first thread executing in a process, and the second executing entity is a second thread executing in the process.

6. The method of claim 1 wherein the lock is represented by a data structure comprising a readers value and a writers value, and the interlocked operations are performed on the readers value and the writers value.

7. The method of claim 1 further comprising:

responsive to a request from a requesting executing entity out of the set for the lock, determining that the lock is not available for granting;

responsive to said determining that the lock is not available for granting, suspending execution of the requesting executing entity until a time out period expires;

after the time out period expires, determining that an executing entity out of the set has signaled the requesting executing entity after the time out period expired; and

responsive to said determining that an executing entity out of the set has signaled the requesting executing entity after the time out period expired, granting the lock to the requesting executing entity.

8. The method of claim 1 further comprising:

responsive to a request from a requesting executing entity out of the set for the lock, determining that the request cannot currently be granted; and

responsive to said determining that the request cannot currently be granted, suspending execution of the requesting executing entity out of the set.

9. The method of claim 8 wherein said suspending is performed by forcing the requesting executing entity to wait on an execution suspension mechanism to which a resume indication can be sent to resume execution of the requesting executing entity.

10. The method of claim 9 further comprising:

when releasing a lock held by a writer, resuming a plurality of readers waiting on the execution suspension mechanism.

11. The method of claim 9 wherein the lock is represented by a data structure comprising a waiting field, the method further comprising:

storing a reference to the execution suspension mechanism in the waiting field.

12. The method of claim 11 wherein said storing is performed with an interlocked instruction on the waiting field.

13. The method of claim 9 further comprising:

creating the execution suspension mechanism, wherein said creating is delayed until after the receiving the request of the requesting executing entity.

14. The method of claim 9 further comprising:

creating the execution suspension mechanism, wherein said creating is performed responsive to receiving the request of the requesting executing entity.

15. The method of claim 9 further comprising:

retrieving the execution suspension mechanism from a pool of at least one execution suspension mechanism previously used to suspend execution of one of the executing entities out of the set of executing entities.

16. The method of claim 9 wherein said suspending is performed by forcing the requesting executing entity to wait on an event object operable to be sent an indication to resume execution of the requesting executing entity.

17. The method of claim 16 wherein the event object is selected to be a manual event object for a requesting executing entity requesting the lock as a reader.

18. The method of claim 16 wherein the event object is selected to be an automatic event object for a requesting executing entity requesting the lock as a writer.

19. The method of claim 16 wherein the lock is held by a holding executing entity, the method further comprising:

when the holding executing entity releases the lock, resuming the requesting executable entity via the event to grant the lock to the requesting executing entity.

20. The method of claim 19 wherein the lock is a first lock, the method further comprising:

after said resuming, releasing the event to free computing resources; and

after said releasing, creating an event object, wherein the event object is created responsive to lock contention on a lock other than the first lock.

21. The method of claim 9 further comprising:

receiving a request of the second executing entity to release the lock as a writer;

responsive to said receiving a request of the second executing entity to release the lock, determining that there is at least one executing entity other than the second executing entity waiting for the lock and no event suspension mechanism has been created for the at least one executing entity;

responsive to said determining that there is at least one executing entity other than the second executing entity waiting for the lock and no event suspension mechanism has been created for the at least one executing entity, attempting to create an execution suspension mechanism;

determining that said attempting to create has failed while there is at least one executing entity other than the second executing entity waiting for the lock and no event suspension mechanism has been created for the at least one executing entity; and

responsive to determining that said attempting to create has failed, repeating said attempting to create until an execution suspension mechanism has been created.

22. The method of claim 8 wherein the lock'"'"'s availability is represented by a data structure, the method further comprising:

responsive to a request from a requesting executing entity out of the set for the lock, spinning on the data structure a plurality of times before said suspending execution of the requesting executing entity out of the set.

23. The method of claim 8 further comprising:

after a time out period has elapsed, resuming execution of the requesting executing entity out of the set even though the request still cannot be granted.

24. The method of claim 23 further comprising:

providing an indication to the requesting executing entity that the request has timed out.

25. The method of claim 24 wherein the lock is a first lock and the requesting executing entity holds a second lock, the method further comprising:

responsive to the indication that the request has timed out, releasing the second lock to avoid a deadlock condition.

26. The method of claim 25 further comprising:

after releasing the second lock, reacquiring with the requesting entity the first lock and the second lock.

27. The method of claim 1 further comprising:

receiving a request of a third executing entity out of the set requesting the lock subject to a time out;

responsive to said receiving a request of a third entity, determining that the lock is not available to the third executing entity;

responsive to said determining that the lock is not available to the third executing entity, suspending execution of the third entity; and

after suspending execution of the third entity, resuming execution of the third entity after a time out period expires.

28. The method of claim 1 further comprising:

while the second executing entity holds the lock as a writer, receiving a request from the second executing entity for the lock as a reader; and

responsive to determining that the second executing entity holds the lock as a writer, granting the request from the second executing entity for the lock as a reader.

29. The method of claim 1 further comprising:

while the second executing entity holds the lock as a writer, receiving a request from the second executing entity for the lock as a reader; and

responsive to determining that the second executing entity holds the lock as a writer, transforming the request from the second executing entity for the lock as a reader into a request for the lock as a writer.

30. The method of claim 29 wherein the request from the second executing entity for the lock as a writer results from logic in a first component and the request from the second executing entity for the lock as a reader results from logic in a second component called by the first component.

31. The method of claim 1 wherein the request by the first executing entity is a first request, the method further comprising:

tracking a reader nesting count for the first executing entity, wherein the reader nesting count indicates how many unreleased requests for the lock as a reader have been granted to the first executing entity;

after granting the first request and before the first request is released, receiving a second request of the first executing entity requesting the lock as a reader;

consulting the reader nesting count to determine there is at least one unreleased request for the lock as a reader; and

responsive to said consulting, granting the second request of the first executing entity and increasing the nesting count.

32. The method of claim 31 wherein the reader nesting count resides in storage local to the first executing entity.

33. The method of claim 31 wherein the first executing entity is a thread and the reader nesting count resides in thread local storage of the thread.

34. The method of claim 31 wherein the first executing entity is a thread associated with a thread local storage, and the thread local storage stores a thread local data structure having a reference to a data structure representing the lock and a reader nesting count, the method further comprising:

checking the thread local data structure to determine if a fast path is available to acquire the lock as a reader; and

responsive to determining the fast path is available, taking the fast path to acquire the lock as a reader.

35. The method of claim 31 wherein the request by the second executing entity is a third request, and an identifier of the second executing entity identifies the identity of the second executing entity, the method further comprising:

tracking a writer nesting count, wherein the writer nesting count indicates how many unreleased requests for the lock as a writer have been granted;

after granting the third request and before the third request is released, receiving a fourth request of the second executing entity requesting the lock as a writer;

consulting an identifier of the second executing entity to determine there is at least one unreleased request for the lock as a writer by the second executing entity; and

responsive to said consulting, granting the fourth request of the second executing entity and increasing the writer nesting count.

36. The method of claim 35 wherein the writer nesting level is a field residing in a data structure representing the lock.

37. The method of claim 1 further comprising:

for the lock, tracking a writer sequence number, wherein the writer sequence number is modified upon grant of the lock to one of the executing entities out of the set as a writer.

38. The method of claim 1 further comprising:

granting a request from a requesting executing entity for the lock;

after granting the request from the requesting executing entity, receiving a request from the requesting executing entity to alter the granted request;

responsive to said request to alter the granted request, granting the request to alter the granted request; and

responsive to said request to alter the granted request, providing an indication of whether an executing entity out of the set other than the requesting executing entity held the lock as a writer after receiving the request to alter and before granting the request to alter.

39. The method of claim 38 further comprising:

tracking a writer sequence number for the lock; and

determining that an executing entity out of the set other than the requesting executing entity held the lock as a writer after receiving the request to alter and before granting the request to alter by comparing a value of the writer sequence number when receiving the request to a value of the writer sequence number when granting the request.

40. The method of claim 1 further comprising:

receiving a request from the first executing entity to upgrade the request for the lock as a reader to a request for the lock as a writer; and

responsive to said request to upgrade, granting the request to upgrade and providing an indication of whether an executing entity out of the set other than the first executing entity held the lock as a writer after the request to upgrade and before granting the request to upgrade.

41. The method of claim 1 further comprising:

receiving a request from the second executing entity to downgrade the request for the lock as a writer to a request for the lock as a reader; and

responsive to said request to downgrade, granting the request to downgrade and providing an indication of whether an executing entity out of the set other than the second executing entity held the lock as a writer after the request to downgrade and before granting the request to downgrade.

42. The method of claim 1 further comprising:

granting a request from a requesting executing entity out of the set for the lock;

after granting the request for the lock, receiving a request from the requesting executing entity to suspend the granted request;

responsive to said request to suspend the granted request, suspending the granted request;

after said suspending, receiving a request from the requesting executing entity to restore the granted request; and

responsive to said request to restore the granted request, providing an indication of whether an executing-entity out of the set other than the requesting executing entity held the lock as a writer after suspending the granted request and before granting the request to restore.

43. In a computer system, a method of protecting at least one protected resource during operations on the at least one protected resource by a set of a plurality of concurrently-executing entities, the method comprising:

receiving a request of a first executing entity out of the set requesting protection for a read operation on the at least one protected resource;

responsive to said receiving the request of the first executing entity requesting protection for a read operation, granting the request of the first executing entity responsive to determining that no granted request to an executing entity out of the set for a modify operation on the at least one protected resource has not yet been released, wherein said granting the request of the first executing entity and said determining that no granted request to an executing entity out of the set for a modify operation on the at least one protected resource has not yet been released are performed together with an interlocked operation;

receiving a request of a second executing entity out of the set requesting protection for a modify operation on the at least one protected resource; and

responsive to said receiving the request of the second executing entity requesting protection for a modify operation, granting the request of the second executing entity responsive to determining that no granted request to an executing entity out of the set for a read operation on the at least one protected resource has not yet been released and no granted request to an executing entity out of the set for a modify operation on the at least one protected resource has not yet been released, wherein said granting the request of the second executing entity and said determining that no granted request to an executing entity out of the set for a read operation has not yet been released and no granted request to an executing entity out of the set for a modify operation are performed together with an interlocked operation.

44. A computer-readable medium having computer-executable instructions for performing the steps of claim 43.

45. In a computer system, a method of protecting at least one protected resource during operations on the at least one protected resource by a set of a plurality of concurrently-executing entities, the method comprising:

receiving a request of a first executing entity out of the set requesting protection for a read operation on the at least one protected resource;

responsive to receiving the request of the first executing entity requesting protection for a read operation, determining that the at least one protected resource can be protected for reading by the first executing entity;

responsive to said determining that the at least one protected resource can be protected for reading by the first executing entity, granting the request of the first executing entity for protection for a read operation on the at least one protected resource;

after the request for protection for a read operation has been granted and before the protection for a read operation has been released, receiving a request of a second executing entity requesting protection for a modify operation on the at least one protected resource;

determining that the second executing entity requesting protection for a modify operation has requested protection for a modify operation after the request for protection for a read operation has been granted and before the protection for a read operation has been released;

responsive to said determining that the second executing entity has requested protection for a modify operation, suspending execution of the second executing entity requesting protection for a modify operation to wait for the protection for a read operation to be released until a time out period has expired; and

before the protection for a read operation has been released, responsive to determining that the time out period has expired, executing a time out sequence comprising resuming execution of the second executing entity requesting protection for a modify operation,

wherein said determining that the at least one protected resource can be protected for reading by the first executing entity and said granting the request of the first executing entity for protection for a read operation on the at least one protected resource are performed simultaneously with an interlocked operation.

46. The method of claim 45 wherein logic for both said determining that the at least one protected resource can be protected for reading by the first executing entity and said granting the request of the first executing entity for protection for a read operation on the at least one protected resource consists of a single interlocked operation.

47. The method of claim 45 further comprising:

after granting the request of the first executing entity for protection for a read operation and before receiving the request of a second executing entity requesting protection for a modify operation, receiving a request of a third executing entity out of the set requesting protection for a read operation on the at least one protected resource; and

responsive to said receiving the request of the third executing entity requesting protection for a read operation, after granting the request of the first executing entity for protection for a read operation and before receiving the request of a second executing entity requesting protection for a modify operation, determining that the at least one protected resource can be protected for reading by the third executing entity; and

responsive to said determining that the at least one protected resource can be protected for reading by the third executing entity, granting the request of the third executing entity for protection for a read operation on the at least one protected resource;

wherein said determining that the at least one protected resource can be protected for reading by the third executing entity and said granting the request of the third executing entity for protection for a read operation on the at least one protected resource are simultaneously performed with an interlocked operation.

48. In a computer system having a plurality of executing threads and a plurality of protected resources, a method of avoiding deadlock in a deadlock avoidance scheme, the method comprising:

tracking how many threads are reading each protected resource and whether a thread is writing to each protected resource in locks having per-lock data structures;

whenever a first thread is unable to acquire a first lock protecting a first resource due to contention on the first lock, blocking the first thread on an event, specifying a time out period;

if contention on the lock has not ceased after the time out period, timing out on the event to unblock the first thread;

after unblocking the first thread, releasing, with the first thread, a lock on a second protected resource; and

waiting for a sleep period to allow a thread other than the unblocked thread to access the first protected resource and the second protected resource, thereby avoiding deadlock.

49. The method of claim 48 further comprising:

performing an interlocked operation on the data structure of the first lock to grant the first lock to the first thread.

50. In a computer system, a method of providing reader/writer synchronization services to a set of a plurality of threads via a lock, the method comprising:

allowing a plurality of the threads to simultaneously hold the lock as a reader; and

preventing any of the of the plurality of the threads from holding the lock as a writer while any other of the plurality of the threads holds the lock as a reader, wherein said preventing any of the of the plurality of the threads from holding the lock as a writer while any other of the plurality of the threads holds the lock as a reader comprises observing failure of an interlocked operation; and

preventing any of the plurality of the threads to hold the lock as a writer while any other of the plurality of the entities holds the lock as a writer, wherein said preventing any of the plurality of the threads to hold the lock as a writer while any other of the plurality of the entities holds the lock as a writer comprises observing failure of an interlocked operation.

51. The method of claim 50 further comprising:

resuming execution of a thread waiting on the lock after a time out period has expired.

52. The method of claim 51 further comprising:

providing an indication to the thread waiting on the lock that a time out period has expired.

53. In a computer system, a method of altering a reader/writer lock'"'"'s state to release the lock, wherein the lock is acquirable by a set of reading executing entities and a set of writing executing entities and the lock'"'"'s state comprises an is-there-a-writer field, a reader-signaled field, and a writer-signaled field, the method comprising:

reading the lock state into a temporary variable, wherein the temporary variable comprises an is-there-a-writer field and a waiter-signaled field;

storing the temporary variable into an old value variable;

altering the is-there-a-writer field of the temporary variable to indicate there will be no writer holding the lock;

determining whether there is at least one reading executing entity waiting on the lock;

responsive to determining that there is at least one reading executing entity waiting on the lock, altering the reader-signaled field of the temporary variable to indicate the at least one reading entity is being signaled;

if there is not at least one reading executing entity waiting on the lock, determining whether there is at least one writing executing entity waiting on the lock;

if there is not at least one reading executing entity waiting on the lock, responsive to said determining that there is at least one writing executing entity waiting on the lock, altering the writer-signaled field of the temporary variable to indicate the at least one writing entity is being signaled; and

updating the lock'"'"'s state with an interlocked instruction, specifying the old value variable as a comparand and the temporary variable as an exchange value.

54. The method of claim 53 further comprising

after altering the reader-signaled field of the lock'"'"'s state, and after a time out period has expired, resuming execution of a timing out executing entity;

determining that the reader-signaled field of the lock'"'"'s state has been altered; and

responsive to said determining that the reader-signaled field of the lock'"'"'s state has been altered, granting the lock to the timing out executing entity.

55. In a computer system, a lock object for providing reader/writer synchronization services to a set of a plurality of executing entities, the lock object comprising:

a readers field for tracking how many executing entities out of the set currently hold the lock as a reader;

a writer field indicating whether an executing entity out of the set currently holds the lock as a writer;

a callable method for receiving a request to hold the lock as a reader, the callable method comprising performing an interlocked operation on the readers field and the writers field to grant the request to hold the lock as a reader; and

a callable method for receiving a request to hold the lock as a writer, the callable method comprising performing an interlocked operation on the writer field and the reader field to grant the request to hold the lock as a writer.

56. The lock object of claim 55 further comprising:

a callable method for altering a granted request to hold the lock, wherein the callable method for altering provides an indication of writers intervening before the granted request is altered.

57. The lock object of claim 55 further comprising:

a callable method for upgrading a granted request to hold the lock as a reader to a request to hold the lock as a writer, wherein the callable method for upgrading provides an indication of writers intervening before the granted request is upgraded.

58. The lock object of claim 55 further comprising:

a callable method for suspending holding the lock; and

a callable method for resuming holding the lock, wherein the callable method for resuming provides an indication of writers intervening before holding the lock is resumed.

59. In a computer system, a synchronization service comprising:

the lock object of claim 55; and

a field stored local to an executing entity indicating a reader nest level for the executing entity.

60. In a computer system, a synchronization service comprising:

the lock object of claim 55; and

at least one event object on which the lock object forces an executing entity out of the set to wait until a request for protection of the resource can be granted.

61. The synchronization service of claim 60 wherein the at least one event object supports a time out.

62. The lock object of claim 55 wherein the callable method for receiving a request to protect the resource during a modify operation on the resource is called by a requesting executing entity and comprises spinning the request before suspending execution of the executing entity.

63. In a computer system, a lock object for providing reader/writer synchronization services to a set of a plurality of components executing on a thread, the lock object comprising:

a readers field for tracking how many executing entities out of the set currently hold the lock as a reader;

a writer field indicating whether an executing entity out of the set currently holds the lock as a writer;

a callable method for receiving a request from a first component out of the set to hold the lock as a reader, the callable method comprising performing an interlocked operation on the readers field and the writers field to grant the request to hold the lock as a reader, wherein the callable method for receiving a request to hold the lock as a reader maintains a reader nest level field for each thread, wherein the reader nest level tracks how many unreleased grants of the lock have been made to a thread as a reader, the callable method operable for receiving a request to hold the lock as a reader from a component called by the first component and responsive to said call to increase the reader nest level; and

a callable method for receiving a request to hold the lock as a writer, the callable method comprising performing an interlocked operation on the writer field and the reader field to grant the request to hold the lock as a writer, wherein the callable method for receiving a request to hold the lock as a writer maintains a writer nest level, wherein the writer nest level tracks how many unreleased grants of the lock have been made to a thread as a writer.

64. The lock object of claim 63 wherein the reader nest level for each thread is maintained at storage local to each thread.

65. The lock object of claim 63 wherein the lock object further comprises:

a callable method for upgrading a lock grant from reader to writer, wherein the callable method for upgrading the lock provides an indication of whether a writer intervened before the lock grant was upgraded to writer; and

a callable method for downgrading the lock from writer to reader, wherein the callable method for downgrading the lock provides an indication of whether a writer intervened before the lock grant was downgraded to reader.

66. In a computer system, a synchronization service for protecting at least one protected resource, the synchronization service comprising:

means for tracking how many executing entities currently have outstanding granted requests to protect the at least one resource during a read operation;

means for initiating an interlocked operation on the means for tracking how many executing entities currently have outstanding requests during a read operation to grant a request for protection for a read operation;

means for tracking whether there is an outstanding granted request to protect the at least one resource during a modify operation; and

means for initiating an interlocked operation on the means for tracking whether there is an outstanding granted request to protect the at least one resource during a modify operation to grant a request for protection for a modify operation.

67. The synchronization service of claim 66 further comprising:

means for tracking how many outstanding requests for protection during a read operation have been granted to an executing entity, wherein said means is accessible in storage local to the executing entity.

68. A computer-readable medium comprising a lock data structure representing a reader/writer lock, the lock data structure comprising the following fields:

a waiting readers field indicating how many readers are waiting to acquire the reader/writer lock;

a waiting writers field indicating how many writers are waiting to acquire the reader/writer lock;

a reader event field referencing an execution suspension mechanism on which at least one of the readers out of the readers waiting to acquire the reader/writer lock is waiting; and

a writer event field referencing an execution suspension mechanism on which at least one of the writers out of the writers waiting to acquire the reader/writer lock is waiting.

69. The computer-readable medium of claim 68, the data structure further comprising:

a readers field indicating how many readers currently hold the lock, wherein the readers field is situated at a least significant portion of a unit of memory.

70. The computer-readable medium of claim 68 wherein the reader/writer lock supports time outs, the data structure further comprising:

a reader-signaled field indicating the lock is being passed to a reader waiting on the execution suspension mechanism on at least one of the readers out of the readers waiting to acquire the reader/writer lock is waiting; and

a writer-signaled field indicating the lock is being passed to a writer waiting on the execution suspension mechanism on which at least one of the writers out of the writers waiting to acquire the reader/writer lock is waiting.

71. The computer-readable medium of claim 68 wherein the data structure further comprises:

a writer nesting level indicating how many unreleased lock requests have been granted to a writer.

72. The computer-readable medium of claim 68 wherein the data structure further comprises:

a reader nesting level indicating how many unreleased lock requests have been granted to a reader.

73. The computer-readable medium of claim 72 wherein the reader nesting level is stored at a location local to the reader.