[發(fā)明專利]一種基于多線程的長(zhǎng)事務(wù)并行執(zhí)行方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210579859.3
• 申請(qǐng)日: 2012-12-27
• 公開(kāi)（公告）號(hào): CN103077006B
• 公開(kāi)（公告）日: 2015-08-26
• 發(fā)明（設(shè)計(jì)）人: 張?jiān)Q;肖剛;高飛;陸佳煒;徐俊;吳利群
• 申請(qǐng)（專利權(quán)）人: 浙江工業(yè)大學(xué)
• 主分類號(hào): G06F9/38
• 分類號(hào): G06F9/38
• 代理公司: 杭州天正專利事務(wù)所有限公司 33201
• 代理人: 王兵;黃美娟

1.一種基于多線程的長(zhǎng)事務(wù)并行執(zhí)行方法，其特征在于：并行執(zhí)行長(zhǎng)事務(wù)包括以下步驟：

(1)、將長(zhǎng)事務(wù)描述為一個(gè)擴(kuò)展的有向圖；長(zhǎng)事務(wù)可以形式化表示為一個(gè)擴(kuò)展的有向圖LT＝(T，E，R)，其中T＝{t1,t2,…,tn}是原子事務(wù)集合，且每個(gè)原子事務(wù)且都具有ACID特性；E＝{e1,e2,…em}是原子事務(wù)間依賴關(guān)系集合，如ei＝ti→tk表示原子事務(wù)tk的開(kāi)始由ti的執(zhí)行結(jié)果決定，若ti提交時(shí)tk開(kāi)始執(zhí)行，則稱為提交依賴，若ti回滾時(shí)tk開(kāi)始執(zhí)行，則稱為回滾依賴；R＝{r1,r2,…,rn}是邏輯關(guān)系的集合，如ri表示一個(gè)以ti為終點(diǎn)的事務(wù)之間的“與”、“或”邏輯表關(guān)系；

(2)、將長(zhǎng)事務(wù)LT分割為若干個(gè)可以并行執(zhí)行的子事務(wù)LT’；LT’是長(zhǎng)事務(wù)的一個(gè)子集，可以包含一個(gè)或多個(gè)原子事務(wù)，即子事務(wù)LT’＝(T’，E’，R’)，其中通過(guò)將長(zhǎng)事務(wù)劃分為若干個(gè)子事務(wù)，當(dāng)子事務(wù)之間不存在依賴關(guān)系時(shí)即可并行執(zhí)行；其分割過(guò)程包括以下步驟：

(2.1)、分析長(zhǎng)事務(wù)中所包含的原子事務(wù)、原子事務(wù)之間的依賴關(guān)系、原子事務(wù)直接的邏輯關(guān)系實(shí)現(xiàn)，建立長(zhǎng)事務(wù)擴(kuò)展有向圖EDG；

(2.2)、根據(jù)長(zhǎng)事務(wù)擴(kuò)展有向圖EDG，合并有環(huán)子圖，生成擴(kuò)展有向無(wú)環(huán)圖EDAG；

(2.3)、循環(huán)查找EDAG中的順序事務(wù)；若當(dāng)前事務(wù)只有唯一的孩子事務(wù)并且該孩子事務(wù)的父事務(wù)也是唯一的，則將它們是順序事務(wù)，合并它們；

(2.4)、如果EDAG中僅包含一個(gè)子事務(wù)，則說(shuō)明該長(zhǎng)事務(wù)無(wú)法并行執(zhí)行，否則輸出并行結(jié)果，該結(jié)果是包含多個(gè)可并行執(zhí)行的子事務(wù)；

(3)、基于POSIX線程庫(kù)派生若干個(gè)子線程并行執(zhí)行長(zhǎng)事務(wù)，所述的POSIX線程庫(kù)采用OpenM語(yǔ)言或者Windows線程API；長(zhǎng)事務(wù)被劃分為若干個(gè)子事務(wù)之?后，其執(zhí)行過(guò)程如下：

(3.1)、在長(zhǎng)事務(wù)開(kāi)始執(zhí)行時(shí)，只生成一個(gè)線程，所述的線程稱為主線程，由它負(fù)責(zé)執(zhí)行；

(3.2)如果遇到可以并行執(zhí)行的子事務(wù)時(shí)，則根據(jù)子事務(wù)的數(shù)量派生出若干個(gè)子線程并行執(zhí)行，所述的子線程稱為輔助線程；

(3.3)、在并行子事務(wù)執(zhí)行過(guò)程中，如果又遇到可以并行執(zhí)行的子事務(wù)，則繼續(xù)派生新的輔助線程來(lái)執(zhí)行新的并行子事務(wù)，此即為并行嵌套，可派生的輔助線程數(shù)目依賴于多核處理器的核數(shù)；

(3.4)、當(dāng)輔助線程執(zhí)行完畢后，則與主線程會(huì)和，由主線程單獨(dú)執(zhí)行長(zhǎng)事務(wù)，如果又遇到可并行的子事務(wù)，則轉(zhuǎn)到(3.2)，否則直到長(zhǎng)事務(wù)執(zhí)行完畢；

(4)、長(zhǎng)事務(wù)并行執(zhí)行的硬件環(huán)境是多核處理器或多CPU處理器，這些平臺(tái)為TLP技術(shù)提供了平臺(tái)支撐。