Проектные решения для C++ ориентированный на многопотоковое исполнение объектный кэш
Я нахожусь в процессе записи библиотеки шаблонов для кэширования данных в C++, где параллельное чтение может быть сделано и параллельная запись также, но не для того же ключа. Шаблон может быть объяснен со следующей средой:
- Взаимное исключение для записи кэша.
- Взаимное исключение для каждого ключа в кэше.
Таким образом, если поток запрашивает ключ от кэша и присутствует, может запустить заблокированное вычисление для того уникального ключа. Тем временем другие потоки могут получить или вычислить данные для других ключей, но поток, который пытается получить доступ к первому ключу, заблокирован - ожидают.
Основные ограничения:
- Никогда не вычисляйте значение для ключа одновременно.
- Вычисление значения для 2 различных ключей может быть сделано одновременно.
- Поиск данных не должен блокировать другие потоки от, получают данные из других ключей.
Мои другие ограничения, но уже разрешенный:
- зафиксированный (известный во время компиляции) максимальный размер кэша с основанным на MRU (последний раз используемый) перегрузка.
- извлечение ссылкой (вовлекают mutexed, совместно использовало подсчет),
Я не уверен, что использование 1 взаимного исключения для каждого ключа является правильным способом реализовать это, но я не нашел никакой другой существенно другой путь.
Вы знаете других шаблонов к реализациям это, или Вы находите это подходящим решением? Мне не нравится идея наличия приблизительно 100 mutexs. (размер кэша является приблизительно 100 ключами),
3 ответа
Вы хотите заблокировать и хотите подождать. Таким образом, где-то должны быть «условия» (например, pthread_cond_t в Unix-подобных системах).
Я предлагаю следующее:
- Существует глобальный мьютекс, который используется только для добавления или удаления ключей на карте.
- Карта сопоставляет ключи со значениями, где значения являются оболочками. Каждая оболочка содержит условие и потенциально значение. Состояние сигнализируется, когда значение установлено.
Когда поток хочет получить значение из кеша, он сначала получает глобальный мьютекс. Затем он просматривает карту:
- Если существует оболочка для этого ключа, и эта оболочка содержит значение, тогда поток имеет свое значение и может освободить глобальный мьютекс.
- Если для этого ключа существует оболочка, но еще нет значения, это означает, что какой-то другой поток в настоящее время занят вычислением значения. Затем поток блокируется по условию, чтобы его разбудил другой поток по завершении.
- Если оболочки нет, поток регистрирует новую оболочку в карте, а затем переходит к вычислению значения. Когда значение вычисляется, оно устанавливает значение и сигнализирует об условии.
В псевдокоде это выглядит так:
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
}
В терминах pthreads , блокировка равна pthread_mutex_lock () , unlock равна pthread_mutex_unlock () , unlock-and-wait - это pthread_cond_wait () , а сигнал - это pthread_cond_signal () . unlock-and-wait атомарно освобождает мьютекс и отмечает поток как ожидающий выполнения условия; когда поток пробуждается, мьютекс автоматически восстанавливается.
Это означает, что каждая оболочка должна содержать условие. Это воплощает ваши различные требования:
- Ни один поток не удерживает мьютекс в течение длительного периода времени (блокируя или вычисляя значение).
- Когда значение должно быть вычислено, это делает только один поток, другие потоки, которые хотят получить доступ к значению, просто ждут, пока оно станет доступным.
Обратите внимание, что когда поток желает получить значение и обнаруживает, что какой-то другой поток уже занят его вычислением, потоки заканчивают тем, что блокируют глобальный мьютекс дважды: один раз в начале и один раз, когда значение доступно. Более сложное решение, с одним мьютексом на оболочку, может избежать второй блокировки, но я сомневаюсь, что затраченные усилия стоят того, если конкуренция очень высока.
О наличии большого количества мьютексов: мьютексы дешевы. Мьютекс - это, по сути, int , он стоит не больше четырех или около того байтов ОЗУ, используемых для его хранения. Остерегайтесь терминологии Windows: в Win32 то, что я здесь называю мьютексом, считается «блокируемой областью»; то, что Win32 создает при вызове CreateMutex () , представляет собой нечто совершенно иное, доступное из нескольких отдельных процессов и намного более дорогое, поскольку включает в себя обратные обращения к ядру. Обратите внимание, что в Java каждый отдельный экземпляр объекта содержит мьютекс, и разработчики Java, похоже, не слишком сварливы по этому поводу.
Вы можете использовать пул Mutex вместо выделения одного мьютекса на ресурс. Как чтения запрашиваются, сначала проверьте рассматриваемое слот. Если у него уже есть метка Mutex, блокируйте на этом Mutex. Если нет, назначьте Moutex к этому слоту и сигнализируйте о нем, принимая MUTEX из бассейна. Как только Mutex несильнен, очистите слот и верните Mutex в пул.
Одной из возможностей, что было бы гораздо более простым решением, будет использоваться один замок считывателя / писателя на весь кеш. Учитывая, что вы знаете, что есть максимальное количество записей (и относительно мало), звучит как добавление новых ключей в кэш - это «редкое» событие. Общая логика была бы:
acquire read lock
search for key
if found
use the key
else
release read lock
acquire write lock
add key
release write lock
// acquire the read lock again and use it (probably encapsulate in a method)
endif
не зная больше о моделях использования, я не могу сказать наверняка, если это хорошее решение. Хотя очень просто, и если использование преимущественно читается, то он очень недорого с точки зрения блокировки.