ThreadSafe Lock Manager: [1] Design

Few weeks ago I ran into a problem. I needed a thread-synchronizing code that would work similarly to a critical section, but would allow me to lock “anything”. If I could limit myself to objects, I could live with TMonitor.Enter/Exit, but I specifically wanted to limit access to some string keys. [In a way, my problem was similar to a problem of locking access to specific items in a string-keyed dictionary. Details differed, though.]

I was thinking about the problem and it turned out not to be a simple one. Yes, I could solve it by introducing a string-keyed dictionary of critical sections but that would be a little bit too limiting for my taste. I had some other requirements in mind which further complicated the implementation.

TL;DR – This lock manager is implemented in the OmniThreadLibrary as IOmniLockManager<K>/TOmniLockManager<K> in the OtlSync unit since revision 1268.

Requirements

1. I need a piece of code that will manage locks for me. Let’s call it a Lock Manager (LM for short).
2. The LM will be used to lock entities of any type, not just objects. Let’s name such an entity a key.
3. The LM must work similarly to a mutex. Caller should be able to wait on a key with a timeout. Timeouts of 0 and INFINITE should be supported.
4. The interface should be similar to TMonitor.Enter/Exit. Caller will call Lock to get exclusive access to a key and will call Unlock to release the key back to the public use.
5. The LM should be reentrant – if a thread manages to get a lock on a key, it should always succeed in getting another lock before releasing the first one. Only when number of Unlock calls for a thread matches the number of Lock calls, the key will be unlocked.
6. An exclusive access should be granted fairly. If a thread A has started waiting on a key before the thread B, it should also get access to that key before the thread B.
7. The set of keys is potentially huge and we don’t want to create a critical section/mutex for each key.
8. A probability of collision (two threads trying to lock the same resource at the same time) is fairly low.

Implementation

With all constraints in mind I came up with an algorithm that keeps a current state of locks in a table. Each entry in a table holds a key, a thread ID of the locking thread and a number of nested Lock/Unlock calls. An access to this table is protected by a critical section.

Locking

• atomically
  • check if the key is present in the table
  • if not, add the (key, thread ID, 1) to the table and exit
  • otherwise, check if the current thread ID is the same as thread ID in the table
  • if true, increment the nested count and exit
  • otherwise, create an event and add it to a notification list
• wait at most timeout time for the event to occur
• if wait timeouts, fail
• otherwise, retry from the beginning
• finally
  • if an event was created, remove it from the notification list and destroy it

All active events are kept in an ordered list. When an unlocking code releases a key, it locates the first event for that key in the list and signals the event. That way, threads are scheduled fairly.

Unlocking

• atomically
  • find the key in the table
  • if the nested count is larger then 1, decrement it and exist
  • remove the key from the table
  • find the key in the notification list
  • if found, signal the event

As you can see, locking is much simpler as it doesn’t need to take into account timeouts and retrying.

Next time we’ll take a look at the implementation.