C ++线程安全对象缓存的设计选项

Question

我正在编写用于C ++中数据缓存的模板库，在该模板库中，可以完成并发读取和并发写入，但不能针对同一键。可以在以下环境中解释该模式：

1. 高速缓存写入的互斥量。
2. 缓存中每个键的互斥量。

这样，如果线程从缓存中请求密钥但不存在，则可以为该唯一密钥启动锁定的计算。同时，其他线程可以检索或计算其他密钥的数据，但是试图访问第一个密钥的线程将被锁定等待。

主要约束条件是：

1. 切勿同时计算键的值。
2. 可以同时计算2个不同键的值。
3. 数据检索一定不能锁定其他线程以防止从其他键检索数据。

我的其他约束但已经解决的是：

1. 固定（在编译时已知）最大缓存大小，并基于MRU（最近使用）打乱。
2. 通过引用检索（隐式共享计数互斥）

我不确定为每个键使用1个互斥锁是否是实现此目的的正确方法，但我没有发现其他任何本质不同的方法。

您是否知道实现此目标的其他模式？或者您找到合适的解决方案？我不喜欢约有100个互斥锁的想法。（缓存大小约为100个键）

Answer 1

你想要锁定并且想要等待。因此，某处应该有“条件”（如pthread_cond_t在类 Unix 系统上）。

我建议如下：

• 有一个全局互斥锁，仅用于在映射中添加或删除键。
• 该映射将键映射到值，其中值是包装器。每个包装器都包含一个条件和一个可能的值。当设置该值时，会发出该条件信号。

当线程希望从缓存中获取值时，它首先获取全局互斥体。然后它在地图中查找：

1. 如果该键有一个包装器，并且该包装器包含一个值，则该线程拥有其值并可以释放全局互斥体。
2. 如果该键有一个包装器但还没有值，则这意味着其他某个线程当前正忙于计算该值。然后，该线程会根据条件阻塞，并在完成后被另一个线程唤醒。
3. 如果没有包装器，则线程在映射中注册一个新的包装器，然后继续计算该值。当计算该值时，它会设置该值并发出条件信号。

在伪代码中，这看起来像这样：

mutex_t 全局互斥体
hashmap_t 映射

锁（全局互斥锁）
w = 地图.get(键)
如果（w==NULL）{
    w = 新包装
    地图.put（键，w）
    解锁（全局互斥体）
    v = 计算值()
    锁（全局互斥锁）
    w.set(v)
    信号（w.cond）
    解锁（全局互斥体）
    返回v
} 别的 {
    v = w.get()
    while (v == NULL) {
        解锁并等待（global_mutex，w.cond）
        v = w.get()
    }
    解锁（全局互斥体）
    返回v
}

用pthreads术语来说，lock是pthread_mutex_lock()，unlock是pthread_mutex_unlock()，unlock-and-wait是，pthread_cond_wait()是signal。以原子方式释放互斥体并将线程标记为等待条件；当线程被唤醒时，互斥量会自动重新获取。pthread_cond_signal()unlock-and-wait

这意味着每个包装器都必须包含一个条件。这体现了您的各种要求：

• 没有线程长时间持有互斥锁（无论是阻塞还是计算值）。
• 当要计算一个值时，只有一个线程执行此操作，希望访问该值的其他线程只需等待该值可用。

请注意，当一个线程希望获取一个值并发现其他线程已经在忙于计算该值时，线程最终会锁定全局互斥锁两次：一次在开始时，一次在该值可用时。一个更复杂的解决方案，每个包装器有一个互斥体，可以避免第二次锁定，但除非争用非常高，否则我怀疑这是值得的。

关于拥有多个互斥体：互斥体很便宜。互斥体基本上是一个int，它只花费大约四个字节左右的 RAM 来存储它。请注意 Windows 术语：在 Win32 中，我在这里所说的互斥量被视为“互锁区域”；Win32 在CreateMutex()调用时创建的内容是完全不同的，可以从多个不同的进程访问它，并且由于涉及到内核的往返，所以成本要高得多。请注意，在 Java 中，每个对象实例都包含一个互斥锁，并且 Java 开发人员在这个问题上似乎并没有过于暴躁。