计算地图:提前计算价值

Question

我有一个计算映射(带有软值),我用它来缓存昂贵的计算结果.

现在我有一种情况,我知道在接下来的几秒钟内可能会查找一个特定的密钥.该密钥的计算成本也比大多数都要高.

我想在最小优先级线程中提前计算该值,以便在最终请求该值时,它已经被缓存,从而缩短了响应时间.

这样做的好方法是:

1. 我可以控制执行计算的线程(特别是它的优先级).
2. 避免重复工作,即仅进行一次计算.如果计算任务已经在运行,那么调用线程会等待该任务而不是再次计算该值(FutureTask实现这一点.使用Guava的计算映射,如果你只调用get它,那么这是真的,但如果你将它与调用混合,则不是put.)
3. "预先计算值"方法是异步的和幂等的.如果计算已在进行中,则应立即返回,而不等待该计算完成.
4. 避免优先级倒置,例如,如果高优先级线程在中等优先级线程执行不相关的操作时请求该值,但计算任务在低优先级线程上排队,则高优先级线程不能被饿死.也许这可以通过临时提升计算线程的优先级和/或在调用线程上运行计算来实现.

如何在所涉及的所有线程之间进行协调？

---

附加信息
我的应用程序中的计算是图像过滤操作,这意味着它们都是CPU绑定的.这些操作包括仿射变换(范围从50μs到1ms)和卷积(最多10ms).当然,不同线程优先级的有效性取决于操作系统抢占较大任务的能力.

Answer 1

您可以通过使用带有ComputedMap的Future来安排后台计算的"一次性"执行.未来代表了计算价值的任务.未来由ComputedMap创建,同时传递给ExecutorService以进行后台执行.执行程序可以配置自己的ThreadFactory实现,该实现创建低优先级线程,例如

class LowPriorityThreadFactory implements ThreadFactory
{
   public Thread newThread(Runnable r) {
     Tread t = new Thread(r);
     t.setPriority(MIN_PRIORITY);
     return t;
   }
}

当需要该值时,您的高优先级线程然后从映射中获取未来,并调用get()方法以检索结果,等待必要时计算结果.要避免优先级倒置,请在任务中添加一些额外的代码:

class HandlePriorityInversionTask extends FutureTask<ResultType>
{
   Integer priority;  // non null if set
   Integer originalPriority;
   Thread thread;
   public ResultType get() {
      if (!isDone()) 
         setPriority(Thread.currentThread().getPriority());
      return super.get();
   }
   public void run() {
      synchronized (this) {
         thread = Thread.currentThread();
         originalPriority = thread.getPriority();
         if (priority!=null) setPriority(priority);
      } 
      super.run();
   }
   protected synchronized void done() {
         if (originalPriority!=null) setPriority(originalPriority);
         thread = null;
   }

   void synchronized setPriority(int priority) {
       this.priority = Integer.valueOf(priority);
       if (thread!=null)
          thread.setPriority(priority);
   }
}

get()如果任务尚未完成,这将负责将任务的优先级提高到线程调用的优先级,并在任务完成时(正常或其他方式)将优先级返回到原始优先级.(为了保持简洁,代码不会检查优先级是否确实更高,但这很容易添加.)

当高优先级任务调用get()时,未来可能尚未开始执行.您可能想通过在执行程序服务使用的线程数上设置一个较大的上限来避免这种情况,但这可能是一个坏主意,因为每个线程可能以高优先级运行,消耗尽可能多的CPU操作系统将其切换出来.池的大小可能与硬件线程的大小相同,例如池的大小Runtime.availableProcessors().如果任务尚未开始执行,而不是等待执行程序安排它(这是一种优先级倒置形式,因为您的高优先级线程正在等待低优先级线程完成),那么您可以选择从当前执行程序并在仅运行高优先级线程的执行程序上重新提交.