[發明專利]動態二進制翻譯中代碼Cache管理方法

有效

• 申請號: 201310048645.8
• 申請日: 2013-02-07
• 公開（公告）號: CN103150196A
• 公開（公告）日: 2013-06-12
• 發明（設計）人: 李瑩;羅艷;尹建偉;吳健;鄧水光;吳朝暉
• 申請（專利權）人: 浙江大學
• 主分類號: G06F9/45
• 分類號: G06F9/45;G06F12/08
• 代理公司: 杭州裕陽專利事務所(普通合伙) 33221
• 代理人: 應圣義

技術領域

本發明涉及計算機應用領域中的動態二進制翻譯技術，特別涉及一種動態二進制翻譯中代碼Cache管理方法。

背景技術

動態二進制翻譯技術是解決遺留代碼和提高軟件平臺適應性的一種有效手段。它在不需要可執行程序源代碼的情況下，動態地將源體系結構上的二進制程序經過轉換，運行于其他目標體系結構上。動態二進制翻譯基本上是這樣工作的：以基本塊為單位翻譯源體系結構二進制代碼，通過翻譯生成相應的目標體系結構支持的代碼塊，并緩存在代碼Cache中，這樣當程序再次運行到這個基本塊時，就直接從代碼Cache中得到相應的目標體系結構代碼并執行，從而提高程序執行速度。利用代碼Cache加速翻譯效率的同時，需要對翻譯出來的代碼塊進行有效的管理，需要既節省本地內存空間，又不至于引起代碼Cache由于空間不足導致頻繁的替換操作以致性能下降。常見的代碼Cache管理策略包括：

(1)???全清空策略

在全清空策略下，當代碼Cache空間不足時，代碼Cache中所有的代碼塊都被清除，該策略最大的優點就是算法簡單，實現起來容易，管理起來也較為方便，所以被很多二進制翻譯系統所采用，但是該策略沒有考慮到程序執行特性，對時間空間的局部性考慮不夠，可能會導致很多較熱的代碼塊被替換出去，許多塊被重新導入導出，增加了不必要的開銷。

(2)???不替換原則

一次性開辟足夠大的空間使得所有代碼塊都由始至終保存在代碼Cache中，每個代碼塊翻譯只有在第一次會發生未命中，代碼塊在被翻譯后，被翻譯的代碼塊會被保存至代碼Cache供下次調用，該策略通過犧牲大量空間的方式來換取高速的優勢，對于資源受限的系統來說，該策略不可取。

(3)???LRU(Least-Recently-Used)?策略

LRU?策略在發生代碼Cache滿的情況下，選擇將使用次數最少的代碼塊替換出去。當被替換的代碼塊大小小于新翻譯的代碼塊時，需要將被替換代碼塊后序的代碼塊進行替換，以獲得足夠大的連續空間。該策略的優點在于考慮了程序的執行特性和程序的時間局限性。缺點在于：1)需要額外的有序鏈表來管理代碼塊，實現起來復雜，且增加了運行時開銷；2)為產生足夠大的空間來存儲新產生的代碼塊，使得不符合LRU原則的代碼塊被替換；3)會產生Cache內存碎片。

(4)???LFU(Least-Frequently-Used)策略

LFU策略與LRU策略實現類似，也存在LRU的優點和缺點，只是LFU替換原則在于每次選擇使用最不頻繁的代碼塊進行替換。

(5)???FIFO(First-In-First-Out)策略

利用環形緩存實現Cache管理，將指針指向最早進入Cache的代碼塊，當代碼Cache空間不足時，將指針指向的代碼塊換出，并將指針后移。該策略實施簡單，同時也考慮了程序的局部性特性，因為最早進入的代碼塊可能后面不會再被執行到，且不會產生碎片問題，因此使用廣泛。但由于FIFO策略對程序執行特性理解不夠透徹，還是存在將熱代碼被換出的情況。

除了上述5種代碼Cache管理策略外還存在一些，如最大塊優先替換、最適合大小塊優先替換等策略。由于它們只考慮空間的利用效率而沒有或很少考慮程序的時間空間局部性和程序的執行特性，因而它們一般不被動態二進制翻譯和優化系統采用。

代碼Cache管理策略在動態二進制翻譯中對提高翻譯效率具有重要作用，它需要綜合考慮管理開銷、代碼局部性、代碼碎片等問題，然而現有的代碼Cache管理策略依然存在著各種不足，因此，亟需提出一種更有效的代碼Cache管理策略。

發明內容

本發明針對現有的代碼Cache管理策略中存在的代碼塊重復換出頻繁，重復翻譯率高、翻譯效率較低等缺點，提供了一種可以避免重復執行代碼塊的換出，減少重復翻譯的新型動態二進制翻譯中代碼Cache管理方法。

為實現上述目的，本發明可采取下述技術方案：

動態二進制翻譯中代碼Cache管理方法，所述代碼Cache包括非跳轉目標Cache和跳轉目標Cache，所述代碼Cache采用FIFO策略，包括以下具體步驟：

1）確定帶翻譯基本塊的類型，所述類型包括跳轉目標基本塊、非跳轉目標基本塊，所述跳轉目標基本塊存儲在跳轉目標Cache中，所述非跳轉目標基本塊存儲在非跳轉目標Cache中，其中，所述跳轉目標基本塊為由跳轉指令跳轉執行的基本塊，所述非跳轉目標基本塊為由非跳轉指令順序執行的基本塊；