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.
- I need a piece of code that will manage locks for me. Let’s call it a Lock Manager (LM for short).
- The LM will be used to lock entities of any type, not just objects. Let’s name such an entity a key.
- 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.
- 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.
- 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.
- 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.
- The set of keys is potentially huge and we don’t want to create a critical section/mutex for each key.
- A probability of collision (two threads trying to lock the same resource at the same time) is fairly low.
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.
- 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
- 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.
- 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.