I'm in the process of writing a template library for data-caching in C++ where concurrent read can be done and concurrent write too, but not for the same key. The pattern can be explained with the following environment:
This way if a thread requests a key from the cache and is not present can start a locked calculation for that unique key. In the meantime other threads can retrieve or calculate data for other keys but a thread that tries to access the first key get locked-wait.
The main constraints are:
My other constraints but already resolved are:
I'm not sure using 1 mutex for each key is the right way to implement this but i didn't find any other substantially different way.
Do you know of other patterns to implements this or do you find this a suitable solution? I don't like the idea of having about 100 mutexs. ( the cache size is around 100 keys )
You want to lock and you want to wait. Thus there shall be "conditions" somewhere (as pthread_cond_t
on Unix-like systems).
I suggest the following:
When a thread wishes to obtain a value from the cache, it first acquires the global mutex. It then looks in the map:
In pseudo code this looks like this:
mutex_t global_mutex hashmap_t map lock(global_mutex) w = map.get(key) if (w == NULL) { w = new Wrapper map.put(key, w) unlock(global_mutex) v = compute_value() lock(global_mutex) w.set(v) signal(w.cond) unlock(global_mutex) return v } else { v = w.get() while (v == NULL) { unlock-and-wait(global_mutex, w.cond) v = w.get() } unlock(global_mutex) return v }
In pthreads
terms, lock
is pthread_mutex_lock()
, unlock
is pthread_mutex_unlock()
, unlock-and-wait
is pthread_cond_wait()
and signal
is pthread_cond_signal()
. unlock-and-wait
atomically releases the mutex and marks the thread as waiting on the condition; when the thread is awaken, the mutex is automatically reacquired.
This means that each wrapper will have to contain a condition. This embodies your various requirements:
Note that when a thread wishes to get a value and finds out that some other thread is already busy computing it, the threads ends up locking the global mutex twice: once in the beginning, and once when the value is available. A more complex solution, with one mutex per wrapper, may avoid the second locking, but unless contention is very high, I doubt that it is worth the effort.
About having many mutexes: mutexes are cheap. A mutex is basically an int
, it costs nothing more than the four-or-so bytes of RAM used to store it. Beware of Windows terminology: in Win32, what I call here a mutex is deemed an "interlocked region"; what Win32 creates when CreateMutex()
is called is something quite different, which is accessible from several distinct processes, and is much more expensive since it involves roundtrips to the kernel. Note that in Java, every single object instance contains a mutex, and Java developers do not seem to be overly grumpy on that subject.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With