[發明專利]一種新型緩存優化多線程確定性方法

在審

• 申請號: 201811298378.9
• 申請日: 2018-11-02
• 公開（公告）號: CN109582474A
• 公開（公告）日: 2019-04-05
• 發明（設計）人: 王開宇;季振洲;吳倩倩;張源悍;王楷
• 申請（專利權）人: 哈爾濱工業大學
• 主分類號: G06F9/54
• 分類號: G06F9/54
• 代理公司: 北京匯捷知識產權代理事務所(普通合伙) 11531
• 代理人: 李宏偉

1.一種緩存優化多線程確定性系統，其特征在于：能夠保證多線程環境下，線程按照確定性順序運行，避免由于線程訪存沖突而產生的數據競爭和競爭通過同步點順序產生的同步競爭，同時采用更加適合多線程環境的LIRS緩存替換算法優化系統性能，減少確定性帶來的開銷。所述系統包括線程確定性結構模塊，多線程通信隔離模塊，原子事務階段劃分模塊，線程同步策略研究模塊以及LIRS緩存優化。

線程確定性結構模塊，用于在多線程確定性中，設置線程運行規則，在串行階段和并行階段之間設置柵欄，強制線程進行同步；

多線程通信隔離模塊，用于在線程運行的并行階段阻止線程之間的數據通信和線程與內存之間的通信行為，防止線程在并行階段以非確定性的方式訪問內存，從而產生數據競爭。

原子事務階段劃分模塊，用于劃分線程運行階段，通過將線程運行階段劃分為并行階段和串行階段，提升系統運行的并行度。其中并行階段線程并行執行，并在柵欄處阻塞等待同步，然后按照確定性順序獲取令牌依次開始串行階段，執行與內存的交互任務。

線程同步策略研究模塊，用于保證同步處的線程按照同步策略中的令牌傳遞順序，依次獲取令牌開始串行階段執行，避免由于線程競爭通過同步點而出現的同步競爭。

LIRS緩存替換算法優化，用于優化系統性能，減少多線程頻繁讀寫造成的緩存失效，改善系統由于保證確定性所產生的額外開銷。

2.根據1所述的應用于緩存優化多線程確定性系統。其特征在于，所述線程確定性結構模塊；

由于系統中Posix thread多線程環境中，線程結構可以分為線程控制、鎖結構和線程中的程序，并沒有控制線程運行狀態的結構，因此線程在運行階段轉換之間需要設置柵欄強制線程進行同步，同時確保線程的創建，殺死都在獲得令牌的前提下完成，所述方法包括如下步驟：

步驟1：設置線程運行階段轉換點的柵欄；

步驟2：保證線程獲取令牌和獲取鎖資源的一致性；

步驟3：線程在獲取令牌之后進行創建子線程和關閉操作；

步驟4：線程在并行階段結束后，按照獲取令牌的順序開始串行階段；

步驟5：線程在串行階段結束后，所有線程均到達同步點，開始下一輪事務執行。

3.根據1所述的緩存優化多線程確定性系統系統。其特征在于隔離線程在并行階段的交互通信。

多線程產生數據競爭的主要原因在于線程競爭訪問相同內存地址時的順序，因此如果能控制線程訪問內存的順序就可以避免出現數據競爭。本方法通過隔離線程在并行階段的交互通信，避免了線程之間和線程與內存間的數據交換，本階段線程執行的數據來自與上輪事務串行階段結束后各個線程的內存拷貝，這種方法將線程與內存的數據交換推遲到串行階段執行，在串行階段線程按照獲取令牌的確定性順序訪問內存，避免出現數據競爭保證了線程運行的確定性。

4.根據1所述的應用于緩存優化多線程確定性系統系統系統。其特征在于劃分線程運行階段，將線程的運行階段分為串行與并行兩部分，在并行階段中為線程運行設置柵欄，每一個并行階段只能允許線程執行一定數量的指令，在執行結束后線程被柵欄阻塞，等待其他線程進入同步操作。

在串行階段，線程在同步點按照令牌傳遞算法獲取令牌，申請對內存加鎖，然后提交執行結果。獲取令牌和申請加鎖都是互斥行為，每個線程在每一輪中只能執行一次。線程在執行完提交操作后被柵欄阻塞，等待后面的線程進入串行階段，當全部線程都結束串行階段后，線程將各自的私有頁面提交到共享頁面中，與共享頁面進行比對，獲得本輪執行后最新的共享數據，為下一輪并行階段開始做準備。

5.根據1所述的應用于緩存優化多線程確定性系統系統系統。其特征在于通過令牌傳遞機制保證線程按照確定性順序進入串行階段。

為了防止出現數據競爭，在并行階段不允許線程向內存進行讀寫操作，因此線程進入串行階段的順序就決定了線程讀寫內存的順序，該順序具有確定性就保證了多線程不會出現數據競爭。線程在同步點按照線程ID順序獲取令牌，保證了線程在同步點不會因為競爭通過柵欄的順序而出現同步競爭和死鎖的情況，避免了出現同步競爭，保證多線程運行的確定性。

6.根據1所述的應用于緩存優化多線程確定性系統系統系統。其特征在于使用了LIRS緩存替換算法替代原本的LRU算法。由于LRU 算法在結構上的缺陷，使得該算法不能很好的適應反復讀寫的需求，因此在多線程環境下表現較差。本方法使用更加適合多線程環境的LIRS算法替換LRU算法，提高因為多線程程序反復讀寫造成的緩存命中率低下問題，改善由于設置確定性規則所產生的系統開銷，使得本系統具有更好的性能指標和更廣泛的應用環境。