I often find myself with a common concurrency problem when dealing with data structures that I want to keep thread-safe. I'll be reading from these structures more than 99% of the time, and writing to them the remaining 1%. Obtaining a lock for reads is usually a relatively expensive operation, and since my structures are very rarely written to it seems like the cost of the lock is often wasted. There have been various locking solutions to this problem for different languages, but one interesting one I've used recently is Java 8's stamped locks with reader/writer locking.
Here is one example of this type of locking in Java 8. It maintains a global mapping between int ids and words. The method will create a new id for any word it hasn't seen, or return the previously created id if one exists.
public static int id(String token) {
// First attempt an optimistic read
long attempt_read_lock = lock.tryOptimisticRead();
if (stringToId.containsKey(token)) {
int resultId = stringToId.get(token);
if (lock.validate(attempt_read_lock)) {
return resultId;
}
}
// The optimistic read failed, try a read with a stamped read lock
long read_lock_stamp = lock.readLock();
try {
if (stringToId.containsKey(token)) {
return stringToId.get(token);
}
} finally {
lock.unlockRead(read_lock_stamp);
}
// Looks like the id we want is not there, let's get a write lock and add it
long write_lock_stamp = lock.writeLock();
try {
if (stringToId.containsKey(token)) {
return stringToId.get(token);
}
int id = idToString.size() * (FormatUtils.isNonterminal(token) ? -1 : 1);
// register this (token,id) mapping with each language
// model, so that they can map it to their own private
// vocabularies
for (NGramLanguageModel lm: LMs)
lm.registerWord(token, Math.abs(id));
idToString.add(token);
stringToId.put(token, id);
return id;
} finally {
lock.unlockWrite(write_lock_stamp);
}
This method will return the id in the first code block the vast majority of the time it's called, meaning it very rarely obtains a lock of any kind. If the optimistic read call fails it falls back to a read/write lock.
My question is, is there any way to do something similar in modern C++? Would it be possible to provide a unique stamp somewhere in memory every time a write lock is obtained on a thread-safe data structure? Would it then be possible to ensure that readers can check this data structure for modifications without requiring the readers to acquire a lock (either for the stamp or for the thread-safe data structure). Would this have to be an operating system kernel feature, or could you do something like this with the current C++ memory model and primitives?
Aucun commentaire:
Enregistrer un commentaire