Concurrency-safe reader-writer lock with time out support

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.

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.

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.

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.

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.

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.

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.

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.

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.