[發(fā)明專利]一種推測(cè)嵌套軟件事務(wù)存儲(chǔ)的沖突管理方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201510346790.3
• 申請(qǐng)日: 2015-06-19
• 公開（公告）號(hào): CN105045563B
• 公開（公告）日: 2017-10-10
• 發(fā)明（設(shè)計(jì)）人: 李翔;王長(zhǎng)浩;張鵬偉
• 申請(qǐng)（專利權(quán)）人: 陜西科技大學(xué)
• 主分類號(hào): G06F9/38
• 分類號(hào): G06F9/38
• 代理公司: 西安通大專利代理有限責(zé)任公司61200
• 代理人: 徐文權(quán)

技術(shù)領(lǐng)域

本發(fā)明屬于事務(wù)管理領(lǐng)域，具體涉及一種推測(cè)嵌套軟件事務(wù)存儲(chǔ)的沖突管理方法。

背景技術(shù)

隨著計(jì)算機(jī)硬件的迅速發(fā)展，多核處理器已經(jīng)廣泛應(yīng)用于工業(yè)設(shè)計(jì)和日常生活中。理論上增加處理器的核數(shù)，則可執(zhí)行的指令數(shù)就將有成倍的增長(zhǎng)，但是在多核處理器上運(yùn)行現(xiàn)存的大量串行程序并沒有獲得預(yù)期加速的效果，這是由于串行程序在多核處理器上并不能自動(dòng)并行而獲得加速。因此如何利用多核處理器加速已有的串行程序已經(jīng)成為學(xué)術(shù)界和工業(yè)界關(guān)注的熱點(diǎn)研究問題。

事務(wù)存儲(chǔ)技術(shù)和線程級(jí)推測(cè)技術(shù)成為提高串行程序在多核處理器上執(zhí)行效率的關(guān)鍵技術(shù)。事務(wù)存儲(chǔ)技術(shù)有效地解決了傳統(tǒng)并行編程模型中采用鎖和信號(hào)量機(jī)制實(shí)現(xiàn)線程間的同步/互斥以及對(duì)共享資源的訪問所帶來的死鎖、優(yōu)先級(jí)反轉(zhuǎn)等諸多問題。線程級(jí)推測(cè)技術(shù)打破了線程間依賴對(duì)線程并行執(zhí)行的限制，可以進(jìn)一步挖掘程序的并行性，有效提高程序的可擴(kuò)展性。

目前已有的支持線程級(jí)推測(cè)的事務(wù)存儲(chǔ)技術(shù)或者不支持嵌套事務(wù)存儲(chǔ)，或者僅僅將嵌套事務(wù)簡(jiǎn)化為單層次的事務(wù)。嵌套事務(wù)通過允許兩個(gè)事務(wù)在語義上不沖突時(shí)進(jìn)行嵌套處理來提高事務(wù)存儲(chǔ)的性能，但是嵌套事務(wù)的引入也帶來了邏輯上的復(fù)雜性和更多的沖突。沖突不僅是事務(wù)存儲(chǔ)技術(shù)的瓶頸，也是線程級(jí)推測(cè)技術(shù)的瓶頸，如何有效的檢測(cè)沖突、消解沖突，是提高系統(tǒng)性能的關(guān)鍵。因此，針對(duì)推測(cè)嵌套軟件事務(wù)存儲(chǔ)，設(shè)計(jì)一種沖突管理方法是非常必需的。

發(fā)明內(nèi)容

本發(fā)明的目的在于提供一種推測(cè)嵌套軟件事務(wù)存儲(chǔ)的沖突管理方法，以克服上述現(xiàn)有技術(shù)存在的缺陷。

為達(dá)到上述目的，本發(fā)明采用如下技術(shù)方案：

一種推測(cè)嵌套軟件事務(wù)存儲(chǔ)的沖突管理方法，包括以下步驟：

步驟1：創(chuàng)建事務(wù)；

步驟2：對(duì)所創(chuàng)建事務(wù)進(jìn)行讀操作或?qū)懖僮?，若進(jìn)行讀操作，則進(jìn)入步驟3，若進(jìn)行寫操作，則進(jìn)入步驟5；

步驟3：在讀操作過程中檢測(cè)是否有寫后讀沖突，若有，則進(jìn)入步驟4，若無，則進(jìn)入步驟5；

步驟4：在讀操作過程中對(duì)寫后讀沖突進(jìn)行消解，并判斷沖突是否消解，若是，則進(jìn)入步驟5，若否，則進(jìn)入步驟9；

步驟5：判斷事務(wù)是否結(jié)束，若是，則進(jìn)入步驟6，若否，則回到步驟2；

步驟6：對(duì)事務(wù)進(jìn)行提交，并檢測(cè)是否有寫后寫沖突或讀后寫沖突，若有，則進(jìn)入步驟7，若無，則進(jìn)入步驟8；

步驟7：在提交過程中對(duì)寫后寫沖突或讀后寫沖突進(jìn)行消解，并判斷沖突是否消解，若是，則進(jìn)入步驟8；若否，則進(jìn)入步驟9；

步驟8：事務(wù)提交成功；

步驟9：放棄事務(wù)。

進(jìn)一步地，步驟3及步驟6中通過沖突檢測(cè)器檢測(cè)是否有沖突，沖突檢測(cè)器包括若干對(duì)象，每個(gè)對(duì)象包括讀集合、寫集合以及寫版本號(hào)，所述讀集合指向?qū)υ搶?duì)象存在讀操作的事務(wù)，每個(gè)事務(wù)節(jié)點(diǎn)包括事務(wù)ID、值和讀版本號(hào)，在事務(wù)執(zhí)行寫操作時(shí)，需要更新讀版本號(hào)的值；所述寫集合指向?qū)υ搶?duì)象存在寫操作的事務(wù)，每個(gè)事務(wù)寫操作節(jié)點(diǎn)包括事務(wù)ID、值、新值和寫版本號(hào)，在事務(wù)執(zhí)行寫操作時(shí)，需要更新寫版本號(hào)，并存入新值。

進(jìn)一步地，步驟4及步驟7中通過沖突消解器對(duì)沖突進(jìn)行消解，沖突消解器為每個(gè)事務(wù)創(chuàng)建一個(gè)管理器節(jié)點(diǎn)，每個(gè)管理器節(jié)點(diǎn)包括優(yōu)先級(jí)、開始時(shí)間、嘗試次數(shù)、中止次數(shù)、父事務(wù)ID、父事務(wù)優(yōu)先級(jí)、讀次數(shù)和寫次數(shù)。

進(jìn)一步地，步驟2中讀操作包括以下步驟：

步驟2.1：在事務(wù)tx及事務(wù)tx祖先的寫集合中查找對(duì)象s，若未找到，則進(jìn)入步驟2.2，若找到，則進(jìn)入步驟2.4；

步驟2.2：在事務(wù)tx的讀集合中查找對(duì)象s，若找到，則直接返回對(duì)象s 的值，若未找到，則進(jìn)入步驟2.3；

步驟2.3：在事務(wù)tx祖先的讀集合中查找對(duì)象s，找到后將對(duì)象s及其讀版本號(hào)并入事務(wù)tx的讀集合，并返回事務(wù)執(zhí)行前最近一次成功提交的事務(wù)對(duì)對(duì)象s的寫入值；

步驟2.4：判斷對(duì)對(duì)象s最后寫操作事務(wù)是否就是事務(wù)tx，若是，將對(duì)象s的值和其寫版本號(hào)并入事務(wù)tx的讀集合，并返回事務(wù)tx中對(duì)對(duì)象s存在寫操作的值；若否，則進(jìn)入步驟2.5；

步驟2.5：判斷事務(wù)tx和對(duì)對(duì)象s寫操作的祖先是否為兄弟節(jié)點(diǎn)，若是，則存在寫后讀沖突，并對(duì)沖突進(jìn)行消解，若否，將對(duì)象s的值和其寫版本號(hào)并入事務(wù)tx的讀集合，并返回事務(wù)tx中對(duì)對(duì)象s存在寫操作的值。

進(jìn)一步地，步驟6中事務(wù)提交包括以下步驟：

步驟6.1：判斷提交全局順序號(hào)serial是否小于事務(wù)tx的提交順序號(hào)，若是，則等待，若否，則進(jìn)入步驟6.2；