計算圖：提前計算值

Question

我有一個computing map（與soft values），我用它來緩存昂貴的計算結果。

現在我有一種情況，我知道在接下來的幾秒鐘內可能會查找某個特定的按鍵。這個密鑰的計算也比大多數昂貴。

我想在最低優先級的線程中提前計算該值，以便最終請求該值時，它將被緩存，從而縮短響應時間。

什麼是做一個好辦法這使得：

1. 我有過在計算執行的線程（特別是其優先級）控制。
2. 避免重複的工作，即計算只進行一次。如果計算任務已在運行，則調用線程將等待該任務，而不是再次計算該值（FutureTask實現此操作。使用番石榴的計算映射時，如果您只撥打get，則撥打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（）方法來檢索結果，等待它可以根據需要計算。爲了避免priority inversion你添加一些額外的代碼到任務：

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 OS將其切換出來。池應該與硬件線程的數量相同，例如，將池的大小設爲Runtime.availableProcessors()。如果任務沒有開始執行，而不是等待執行程序安排它（這是一種優先級反轉形式，因爲高優先級線程正在等待低優先級線程完成），那麼您可以選擇取消它當前的執行程序並重新提交執行程序只運行高優先級的線程。

Answer 2

協調這種情況的一種常見方式是創建一個映射，其值爲FutureTask對象。所以，作爲一個例子，我從我的一個web服務器上寫了一些代碼，其基本思想是對於一個給定的參數，我們看看是否已經有一個FutureTask（意味着這個參數的計算已經被調度），以及如果是的話，我們等待它。在這個例子中，我們另有安排查找，但可能在其他地方有一個單獨的調用來完成，如果這是可取的：

private final ConcurrentMap<WordLookupJob, Future<CharSequence>> cache = ... 

    private Future<CharSequence> getOrScheduleLookup(final WordLookupJob word) { 
    Future<CharSequence> f = cache.get(word); 
    if (f == null) { 
     Callable<CharSequence> ex = new Callable<CharSequence>() { 
     public CharSequence call() throws Exception { 
      return doCalculation(word); 
     } 
     }; 
     Future<CharSequence> ft = executor.submit(ex); 
     f = cache.putIfAbsent(word, ft); 
     if (f != null) { 
     // somebody slipped in with the same word -- cancel the 
     // lookup we've just started and return the previous one 
     ft.cancel(true); 
     } else { 
     f = ft; 
     } 
    } 
    return f; 
    } 

在線程優先級方面：我不知道這是否會達到什麼你認爲它會？我並不完全理解你在等待線程上方提高查找的優先級：如果線程正在等待，那麼它正在等待，無論其他線程的相對優先級是什麼......（您可能想看看一些我寫過的文章是關於thread priorities和thread scheduling的，但是爲了簡短起見，我不確定改變優先順序是否會向您購買您所期望的。）

Answer 3

我懷疑你正在往重點關注線程優先級錯誤的路徑。通常，由於I/O（內存不足數據）與CPU限制（邏輯計算）相比，高速緩存保存的數據計算起來很昂貴。如果您預先猜測用戶未來的行爲，例如查看未讀郵件，那麼它表明您的工作可能會受到I/O限制。這意味着只要不發生線程匱乏（哪些調度程序不允許），使用線程優先級來玩遊戲就不會提供很大的性能改進。

如果成本是I/O調用，則後臺線程被阻塞，等待數據到達並且處理該數據應該相當便宜（例如，反序列化）。由於線程優先級的改變不會提供太多的加速，所以在後臺線程池上異步執行工作應該足夠了。如果緩存缺失懲罰太高，那麼使用多層緩存往往有助於進一步減少用戶感知的延遲。

Answer 4

作爲線程優先級的替代方法，只有當沒有高優先級任務正在進行時，纔可以執行低優先級任務。這裏有一個簡單的方法來做到這一點：

AtomicInteger highPriorityCount = new AtomicInteger(); 

void highPriorityTask() { 
    highPriorityCount.incrementAndGet(); 
    try { 
    highPriorityImpl(); 
    } finally { 
    highPriorityCount.decrementAndGet(); 
    } 
} 

void lowPriorityTask() { 
    if (highPriorityCount.get() == 0) { 
    lowPriorityImpl(); 
    } 
} 

在你的使用情況，無論是默認地將Impl（）方法會調用get（）計算地圖上，highPriorityImpl（）在不同的線程在同一線程和lowPriorityImpl（） 。

你可以寫一個更復雜的版本，推遲低優先級的任務，直至完成高優先級任務和限制的併發低優先級任務的數量。