[發明專利]一種軟件實時事務內存的實現方法

有效

• 申請號: 201210358174.6
• 申請日: 2012-09-24
• 公開（公告）號: CN102929711A
• 公開（公告）日: 2013-02-13
• 發明（設計）人: 顧宗華;李紅;王鑄;張勁超;章明;吳朝暉
• 申請（專利權）人: 浙江大學
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 杭州裕陽專利事務所(普通合伙) 33221
• 代理人: 江助菊

技術領域

本發明涉及計算機領域的嵌入式實時操作系統，特別涉及一種用于嵌入式實時操作系統軟件實時事務內存的一種實現方法。

技術背景

嵌入式實時系統是指對于任務處理時間有著嚴格限制的操作系統。如果任務的處理時間超過截止期（deadline），可能會產生嚴重的后果。實時性分為硬實時和軟實時，在硬實時系統中，如果任務的運行時間超時會產生很嚴重的后果，在軟實時系統中，則會有影響，但不會很嚴重。

事務內存（Transactional?Memory）是操作系統中多任務互斥訪問共享數據的一種方式。在傳統的操作系統中，實現共享數據互斥訪問的方法一般是使用自旋鎖（Spinlock）來保證的。在這種實現方式下，一個任務在獲取到共享資源之前首先需要得到一個鎖，如果它檢測到該鎖已經被其他任務獲取到了，那么就進行循環等待，直到該鎖被釋放為止。這種方式的缺點在于，如果存在多個任務同時訪問共享數據，那么它們的訪問是串行進行的。在數據競爭比較激烈的環境下，這種方式是比較低效的。而事務內存的實現方式則不同，任務并不會在進入到臨界區以前檢測其他任務的存在，而是在進入臨界區以前記錄一下處理器的狀態，然后在執行臨界區或者執行完臨界區的時候進行沖突檢測。如果發生沖突，那么就將各種狀態（寄存器的值和共享數據的值等等）恢復到進入到臨界區以前，然后重新執行，這個操作叫做回滾。如果沒有沖突，那么就將修改的內容寫入到共享數據中，這個操作叫做提交。這種方式與自旋鎖的區別在于，當多個任務訪問共享數據時，多個任務可以一起執行臨界區，是一種并行的方式。在競爭比較激烈的環境中（也就是會有很多任務同時訪問臨界區），事務內存相比自旋鎖有更大的優勢。事務內存的工作原理可以參考圖1。事務的實現方式可以分為硬件事務內存和軟件事務內存，本文只考慮軟件事務內存,還有，本文所提出的方法能夠在單處理器上實現，也可以在多處理器的環境下實現。如果是在處理器的環境下實現，任務只能在它所屬的處理器上運行，不能遷移到其他處理器上。

事務內存主要由兩個過程組成：沖突檢測和管理（conflict?detection?and?management）和版本管理（version?management）。沖突檢測是負責檢測在事物內存運行的時候是否與其他的事物內存發生沖突，沖突管理是負責在沖突發生了以后處理沖突的部分，如果兩個事務內存發生了沖突，由這個部分判斷由哪個事務內存繼續運行。事物內存的運行原理其實是上將修改的內容保存在日志中，如果成功提交了那么再將修改的內容寫入共享數據中，如果發生沖突了并且被沖突管理決策判斷需要回滾，那么放棄日志中的內容，然后恢復處理器環境，或者反過來，將共享數據原來的內容保存在日志中，回滾的時候將日志中的內容恢復到共享數據中去。這些都是版本管理需要負責的部分。

上面已經說過，在實時系統中，任務的運行時間超時可能會產生比較嚴重的后果。所以通常在實時系統的實現中，必須要保證任務時間的可預測性。但是在平常的事務內存的實現中，任務在執行臨界區的時候可能會回滾很多次，甚至無限回滾。這種情況在實時系統中是不能接受的。

發明內容

針對上述技術缺陷，本發明提出軟件實時事務內存的實現方法。

為了解決上述技術問題，本發明的技術方案如下：

軟件實時事務內存的實現方法，包括如下步驟：

11）根據任務之間是否會產生沖突,產生任務之間的沖突關系圖，并且依據這個沖突關系圖將所有任務劃分為幾個隊列，每個任務屬于且只能屬于一個隊列;12)增加了一個常量,所述常量規定了任務的最大回滾次數,如果某任務回滾次數超出該常量，則將該任務加入到其所屬于的隊列中去，在該隊列的隊尾進行排隊，并且任務會進入到休眠狀態,只有當該任務排列到隊首的時候，該任務才會被喚醒，然后重新執行事務內存的代碼;

如果一旦有兩個任務發生沖突，則依據以下兩種情況處理：

13)當其中一個任務是排列在隊首，另外一個任務沒有在隊列中,那么這時候就優先讓不在隊列中的任務回滾，這樣確保隊首的任務能夠提交，如果該任務回滾的次數達到了所述常量規定的次數時，那么它就會進入到它所屬的隊列中進行排隊，并且進入到休眠狀態，等待喚醒;

14)如果兩個任務都沒有在隊列中，那么根據哪個任務的優先級高，讓優先級高的任務執行，另一個任務則回滾，并且如果有任務的回滾次數達到了所述常量規定的次數時，那么這個任務就加入到它所屬的隊列。