Вы хотите заблокировать и хотите подождать.Таким образом, где-то должны быть «условия» (как 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 терминах, lockравно pthread_mutex_lock(), unlock равно pthread_mutex_unlock(), unlock-and-wait равно pthread_cond_wait() и signal равно pthread_cond_signal().unlock-and-wait атомарно освобождает мьютекс и помечает поток как ожидающий при условии;когда нить пробуждается, мьютекс автоматически восстанавливается.
Это означает, что каждая оболочка должна содержать условие.Это воплощает ваши различные требования:
- Никакие потоки не содержат мьютекс в течение длительного периода времени (ни блокирование, ни вычисление значения).
- Когда значение должно быть вычислено, толькоодин поток делает это, другие потоки, которые хотят получить доступ к значению, просто ждут его доступности.
Обратите внимание, что когда поток хочет получить значение и обнаруживает, что какой-то другой поток уже существуетЗанимаясь его вычислением, потоки блокируют глобальный мьютекс дважды: один раз в начале и один раз, когда значение становится доступным.Более сложное решение, с одним мьютексом на обертку, может избежать второй блокировки, но если конкуренция не очень высока, я сомневаюсь, что это стоит усилий.
Насчет множества мьютексов: мьютексы дешевы.Мьютекс - это, по сути, int, он стоит всего четыре байта оперативной памяти, используемой для его хранения.Остерегайтесь терминологии Windows: в Win32 то, что я здесь называю мьютексом, считается «взаимосвязанной областью»;то, что создает Win32 при вызове CreateMutex(), является чем-то совершенно другим, доступным из нескольких отдельных процессов и намного более дорогостоящим, поскольку включает в себя обращения к ядру.Обратите внимание, что в Java каждый экземпляр объекта содержит мьютекс, и разработчики Java, похоже, не слишком раздражительны в этом вопросе.